Então vamos praticar a idéia de comparar dois polinômios,
por exemplo, e decidir se
eles pertencem ou não à mesma classe.
Então definimos a classe em si.
Para fazê-lo, começamos com
a idéia de notação Big-O,
que às vezes é denotado é
sublinhado o em texto escrito à mão.
O procedimento aqui é o seguinte.
Basicamente, assume que temos duas de nossas funções
como x ao quadrado e 5x ao quadrado menos 100x.
Nós, de alguma forma, estamos falando sobre
o limite superior de
uma função em relação a outra.
Basicamente, isso significa que uma função é maior não
mais do que em algum número fixo
de vezes do que a outra.
Por outras palavras, temos de escrever aqui uma desigualdade.
Basicamente, suponha que temos algum bairro
de um determinado ponto, um, por exemplo.
Chamamos uma função
Big-O de outra função neste bairro.
Se houver alguma constante,
constante positiva, C como a relação,
valor absoluto da relação de
funções f e g não excede
este valor c. Então vamos considerar,
por exemplo, o nosso caso.
Temos x ao quadrado,
por exemplo, vamos chamá-lo f é x ao quadrado,
g é 5x ao quadrado menos
100x e eu vou assumir que x se aproxima do infinito.
Então o que vamos fazer, vamos dizer,
é que alguma função é maior do que a
outra em algum bairro do infinito.
Precisamos escrever algo
como o valor absoluto de f
é menor ou igual alguma
constante multiplicada pelo valor absoluto de g, certo?
Em outras palavras, x ao quadrado menor ou maior que alguma
constante multiplicada por Epsilon
[inaudível] 5x ao quadrado menos 100x.
É muito fácil entender o que
constante é realmente bom para nós aqui.
Por exemplo, vamos começar com
a constante c, igual a um.
Bem, é óbvio que é,
porque se assumirmos que c é igual a um.
Assim, obtemos x ao quadrado de um lado e
5x quadrados menos 100x no outro lado.
Se subtrairmos x ao quadrado
de ambos os lados, assim, obtemos funções,
que são claramente positivas a partir de algum ponto,
porque estamos olhando para
uma função parabólica com positivo.
Meu coeficiente, portanto,
há uma raiz e depois dessa raiz,
temos apenas valores positivos.
Assim, essa desigualdade se mantém e um.
F é Big-O em direção a G,
esse foi um exemplo.
Um código facilmente argumenta que se precisamos
trocar essa função que ainda é segura,
só porque em vez de escrever c é igual a um.
Vamos tentar fazer isso interpretar aqui.
Então, basicamente, precisamos provar algo, como isso aqui.
Então, a fim de fazer cada um,
precisamos considerar outro c nada,
pequeno, mas um grande.
Então, basicamente, começamos com como c igual a cinco.
Então temos um bom resultado aqui.
Mas nem sempre é o caso, porque, por exemplo,
vamos olhar para um caso mais interessante.
Por exemplo, o que faz funções [inaudível],
seno de x e x,
como x se aproxima de zero? Nós sabemos o quê?
Eles são basicamente equivalentes como se deve esperar,
que o seno x é basicamente um Big-O de x.
é bastante fácil, porque
o valor absoluto do seno x, como dissemos,
enquanto estávamos falando sobre nosso segundo limite importante,
agora é maior que o modelo x,
porque o valor absoluto de x
é na verdade a área do setor,
e seno de x é a área do triângulo respectivamente.
Então, com isso, contamos que
usando uma constante c igual a um,
obtemos isso absolutamente certo.
Mas e se substituirmos um ponto de interesse de zero,
para digamos infinito?
Em primeiro lugar, as idéias de que o seno de x
é Big-O
em relação a x, ainda se mantêm neste exato ponto, porque basicamente, o
seno de x não é maior do que um e x é o maior.
Como você pode imaginar, x se aproxima do infinito.
Assim, essa desigualdade ainda se mantém,
por exemplo, para a mesma constante igual a um.
Mas se mudarmos,
se mudarmos duas funções,
então obtemos 380,
[inaudível] aqui, porque seno x
e x não estão relacionados em tempos.
Porque seno x ainda é, desculpe,
Eu disse-lhe que nós precisamos
trocar funções e não fazê-lo.
Então é um grande engano aqui.
Isso é menos enganador.
Então x é Big-O do seno de x.
Então, basicamente, seno de x é
delimitado por um e menos um e x é ilimitado.
Assim, se tentássemos chegar a ideia de
que x deve ser menor que alguma constante,
multiplicada pelo seno de x e dizemos que esta
constante, por exemplo, 10.000.
Então, qual é o erro?
Então podemos, por exemplo,
tomar x maior do que dois, já que n
, esta equação, vamos quase
definitivamente cair e
isso não é extremamente o caso.
Não está certo. Então, quando
estamos falando de notação Big-O,
você sempre precisa considerar a ordem aqui.
Qual função, em relação a que função? É grande?