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?