Así que practiquemos la idea de comparar dos polinomios
, por ejemplo, y decidir si
pertenecen o no a la misma clase.
Así que definimos la clase en sí.
Para hacerlo, comenzamos con
la idea de la notación big-o,
que a veces se denota se
subraya o en texto escrito a mano.
El procedimiento aquí es el siguiente.
Básicamente, asume que tenemos dos de nuestras funciones
como x cuadrado y 5x cuadrado menos 100x.
Nosotros, de alguna manera, estamos hablando
del límite superior de
una función con respecto a otra.
Básicamente, significa que una función no es
mayor que en algún número fijo
de veces que la otra.
En otras palabras, tenemos que anotar una desigualdad aquí.
Básicamente, supongamos que tenemos algún vecindario
de un punto dado, un, por ejemplo.
Llamamos a una función
Big-o de otra función en este vecindario.
Si hay alguna constante,
constante positiva, C como la relación,
valor absoluto de la relación de
funciones f y g no excede
este valor c. Así que consideremos,
por ejemplo, nuestro caso.
Tenemos x cuadrado,
por ejemplo, llamémoslo f es x cuadrado,
g es 5x cuadrado menos
100x y asumiré que x se acerca al infinito.
Así que lo que vamos a hacer, vamos a decir,
es que alguna función es mayor que la
otra en algún vecindario del infinito.
Necesitamos escribir algo
así como el valor absoluto de f
es menor o igual alguna
constante multiplicada por el valor absoluto de g, ¿de acuerdo?
En otras palabras, x cuadrado menor o mayor que alguna
constante multiplicada por Epsilon
[inaudible] 5x cuadrado menos 100x.
Es bastante fácil entender qué
constante es realmente bueno para nosotros aquí.
Por ejemplo, comencemos con
la constante c, igual a uno.
Bueno, es obvio que lo es,
porque si asumimos que c equivale a uno.
Por lo tanto, obtenemos x cuadrados en un lado y
5x cuadrados menos 100x en el otro lado.
Si restamos x al cuadrado
de ambos lados, por lo tanto, obtenemos funciones,
que son claramente positivas desde algún punto,
porque estamos viendo
una función parabólica con positivo.
Mi coeficiente, por lo tanto,
hay una raíz y después de esta raíz,
sólo tenemos valores positivos.
Por lo tanto, esta desigualdad se mantiene y uno.
F es grande hacia G,
ese fue un ejemplo.
Un código argumenta fácilmente que si necesitamos
intercambiar esta función que todavía se mantiene,
solo porque en lugar de escribir c es igual a uno.
Tratemos de hacer esta interpretación aquí.
Así que, básicamente, tenemos que probar algo, como esto aquí.
Así que para hacer cada uno,
tenemos que considerar otro c nada,
uno pequeño, pero uno grande.
Así que básicamente, comenzamos con como c equivale a cinco.
Entonces obtenemos un buen resultado aquí.
Pero no siempre es el caso, porque, por ejemplo,
veamos algún caso más interesante.
Por ejemplo, ¿qué hace funciones [inaudibles],
seno de x y x,
cuando x se acerca a cero? ¿Sabemos qué?
Son básicamente equivalentes como uno debería esperar,
que seno x es básicamente un gran o de x.
Es bastante fácil, porque
el valor absoluto de seno x, como dijimos,
mientras estábamos hablando de nuestro segundo límite importante,
es ahora mayor que el modelo x,
porque el valor absoluto de x
es en realidad el área del sector,
y seno de x es el área del triángulo respectivamente.
Entonces, con eso, contamos que
usando una constante c igual a uno,
obtenemos esto absolutamente correcto.
Pero, ¿y si sustituimos un punto de interés de cero,
digamos infinito?
En primer lugar, las ideas de que el seno de x
es grande hacia x,
todavía se mantienen en este mismo punto, porque básicamente, el
seno de x no es mayor que uno y x es el más grande.
Como puedes imaginar, x se acerca al infinito.
Por lo tanto, esta desigualdad todavía se mantiene,
por ejemplo, para la misma constante igual a uno.
Pero si lo cambiamos,
si cambiamos dos funciones,
entonces obtenemos 380,
[inaudible] aquí, porque seno x
y x no están relacionados en tiempos.
Porque sine x sigue siendo, lo
siento, te he dicho
que necesitamos intercambiar funciones y no lo hicimos.
Así que es un gran engaño aquí.
Eso es menos engañoso.
Así que x es Big-o del seno de x.
Así que básicamente, el seno de x está
limitado por uno y menos uno y x está ilimitado.
Por lo tanto, si tratamos de llegar a la idea de
que x debería ser menor que alguna constante,
multiplicado por seno de x y decimos que esta
constante, por ejemplo, 10.000.
Entonces, ¿cuál es el error?
Entonces podemos, por ejemplo,
tomar x más grande que dos, ya que n,
esta ecuación, casi
definitivamente simplemente caerse y
este no es extremadamente el caso.
No está bien. Así que cuando
estamos hablando de notación Big-o,
siempre necesita considerar el orden aquí.
¿ Qué función, con respecto a qué función? ¿Es Big-o?