Para una función dada g(n), use (g(n)) para representar el conjunto de funciones: = {: Hay constantes positivas y tales que para todos, hay }.
Para cualquier función f(n), si hay constantes positivas , de modo que cuando n es lo suficientemente grande, f(n) puede intercalarse entre y , entonces f(n) pertenece al conjunto. Debido a que es un conjunto, se puede escribir como " ", lo que indica que f (n) es un elemento de. Sin embargo, normalmente se escribe " " para significar lo mismo.
La figura anterior ofrece una ilustración intuitiva de las funciones f(n) y g(n), donde f(n) = . Para todos los valores de n a la derecha de , el valor de f(n) cae entre y , en otras palabras, para todo n≥ , f(n) es igual a g(n) dentro de un factor constante. Decimos que g(n) es una cota asintóticamente compacta de f(n).
La definición requiere que cada miembro sea asintóticamente no negativo, es decir, f(n) es no negativo cuando n es lo suficientemente grande (una función asintóticamente positiva siempre es positiva cuando n es lo suficientemente grande valor). Esto requiere que la propia función g(n) también sea asintóticamente no negativa; de lo contrario, el conjunto es el conjunto vacío. Por lo tanto, se supone que toda función utilizada en notación es asintóticamente no negativa.
En primer lugar debemos determinar las constantes, y , de modo que para todo n≥, es decir,
se establece dividiendo la desigualdad, obtenemos
.La desigualdad del lado derecho es válida para todos los establecidos. Asimismo, la desigualdad del lado izquierdo es válida para todos cuando . De esta manera, eligiendo , y , podemos probar . Por supuesto, existen otras opciones de constantes y lo importante es que exista una. Cabe señalar que estas constantes dependen de la función y diferentes funciones generalmente requieren diferentes constantes.
Utilice la prueba por contradicción para demostrar, suponiendo que hay constantes y , de modo que para todos , existe , lo cual es imposible para cualquier n grande, porque es una constante.
Eliminar términos de orden inferior e ignorar términos constantes da . Se puede encontrar que cuando es constante y , para todos, satisface.
La notación asintóticamente proporciona los límites superior e inferior de una función. Cuando solo hay un límite superior asintótico, se utiliza la notación O. Para una función dada g(n), sea O(g(n)) (pronunciado "gran Og(n)", a veces simplemente "Og(n)") representa el conjunto de funciones: O(g(n))= {f(n): Hay constantes positivas c y tales que para todo n≥ , 0≤f(n)≤cg(n)}
La figura anterior ilustra la intuición de la notación O Significado, por valores de n a la derecha, el valor de la función f (n) está por debajo de g (n).
Utilizando la notación O, a menudo podemos describir el tiempo de ejecución de un algoritmo observando su estructura general. Por ejemplo, la estructura de doble bucle en el algoritmo de ordenación por inserción puede conducir inmediatamente al límite superior de su operación en el peor de los casos. El costo de cada iteración del bucle interno es (constante) como el límite superior y los subíndices i y j. puede tomar hasta n. El bucle interno se ejecuta como máximo una vez para cada par de valores i y j.
Así como la notación O proporciona un límite superior asintótico para una función, la notación proporciona un límite inferior asintótico.
Para una función dada g(n), represente (pronunciado "grande", a veces simplemente " ") el conjunto de las siguientes funciones: = {f(n): Hay constantes positivas c y tales que para todo n≥ , con 0≤cg(n)≤f(n)}
Las definiciones de notación O y notación o son similares. La principal diferencia es que para f(n)=O(g(n)), la El límite 0≤ f(n)≤ cg(n) es cierto para una determinada constante c>0, pero para f(n)=o(g(n)), el límite 0≤ f(n)≤ cg(n) es cierto para todas las constantes c>0. Intuitivamente, en la representación o, cuando n tiende a infinito, la función f(n) no es importante en relación con g(n), es decir, representa un límite inferior no asintóticamente ajustado, uno. La definición de ello es, si y sólo si. La forma de se define como un conjunto, para cualquier constante positiva c>0, existe una constante, con.
Por ejemplo: , pero ≠ . La relación f(n)= significa
cómo existe este límite. Es decir, cuando n llega al infinito, f(n) se vuelve arbitrariamente grande en relación con g(n).
Sea un polinomio de grado d de n, donde , y sea k una constante. Utilice la definición de notación asintótica para demostrar las siguientes propiedades:
1. Si k≥d, entonces .
2. Si k≤d, entonces .
3. Si k=d, entonces .
4. Si k>d, entonces .
5. Si k Solución: Esta fórmula se puede reescribir como: Para la propiedad 1 deje obtener más Simplemente obtenga de modo que para n> en este momento, la propiedad 1 esté demostrada. De la misma manera, cuando , se puede demostrar la propiedad 2. El resto de propiedades se demuestran de forma similar.