Como mencioné en el comentario, no mencionó exactamente lo que no pudo entender. Hay dos aspectos del capítulo Crecimiento de la función.
1. Qué son realmente las anotaciones asintóticas en términos de matemáticas
2. Cómo se pueden usar las anotaciones asintóticas en el análisis de algoritmos.
Cuando hablamos del tiempo de ejecución del algoritmo, generalmente estamos interesados en el peor tiempo de ejecución del algoritmo. Y cuando hacemos tal análisis ignoramos detalles menores.
En términos simples, utilizando el análisis asintótico que usted dice.
El algoritmo X con el tamaño de entrada 1000000 tomará aproximadamente 2 segundos
En lugar de decir
El algoritmo X con tamaño de entrada 1000000 tomará 2 segundos y 42 milisegundos y 56 microsegundos
Supongamos que un algoritmo realiza algunas operaciones en n números en tres partes
La primera parte requiere operaciones [matemáticas] n ^ 2 [/ matemáticas],
La segunda parte requiere operaciones [matemáticas] 3 * n [/ matemáticas] y
La tercera parte requiere 156 operaciones.
El número total de operaciones se puede expresar como función [matemáticas] f (n) = n ^ 2 + 3 * n + 156 [/ matemáticas]
Dado que el tiempo de ejecución [Diga T (n)] depende del número de operaciones
Por lo tanto [matemáticas] T (n) = f (n) = n ^ 2 + 3 * n + 156 [/ matemáticas]
Considere [matemáticas] g (n) = n ^ 2 [/ matemáticas]
Ahora [matemáticas] 0 \ leq f (n) \ leq 2 * g (n) [/ matemáticas] para [matemáticas] n> 14 [/ matemáticas]
Esta es la condición de Big O
entonces [matemáticas] f (n) = O (n ^ 2) [/ matemáticas]
(Supongo que leyó la parte en CLRS que aquí “=” es en realidad [matemáticas] \ en [/ matemáticas])
Por lo tanto [matemáticas] T (n) = O (n ^ 2) [/ matemáticas]
En lugar de escribir [matemáticas] T (n) = f (n) = n ^ 2 + 3 * n + 156 [/ matemáticas]
[matemática] T (n) [/ matemática] puede expresarse como [matemática] T (n) = O (n ^ 2) [/ matemática] en notación Big O.
- Quiero aprender a tocar la guitarra pero no quiero tener callos. ¿Es posible tocar la guitarra como un hobby decentemente bien para poder tocar canciones populares pero no desarrollar callosidades?
- Quiero postularme para universidades extranjeras, pero para eso tengo que dar los exámenes SAT, TOEFL y AP, que son bastante costosos para mí, y la admisión no está garantizada. ¿Qué tengo que hacer?
- Obtuve un aprendizaje en Querétaro, México. ¿Puedo ir allí con visa de turista y trabajar en lugar de visa de trabajo? Por favor lea los detalles.
- Le di mi gato a otra familia, ¿es una buena idea visitarlo?
- Tengo mala memoria. ¿Qué debo hacer para mejorarlo?
¿Cómo ayuda en el análisis de algoritmos?
considere [math] n = 10 ^ 5 [/ math] y la máquina en la que se ejecuta el algoritmo, realiza [math] 10 ^ 9 [/ math] operaciones por segundo.
Si utilizamos la expresión en tiempo de ejecución [matemática] T (n) = n ^ 2 + 3 * n + 156 [/ matemática]
entonces [matemáticas] T (100000) = 10000300156 [/ matemáticas]
Número total de segundos necesarios = 10000300156/10 ^ 9 = 10.000300156 segundos
Si expresamos [matemáticas] T (n) = O (n ^ 2) [/ matemáticas] o simplemente n ^ 2
entonces [matemáticas] T (100000) = 10000000000 [/ matemáticas]
Número total de segundos necesarios = 10000000000/10 ^ 9 = 10 segundos
Que es aproximadamente el mismo resultado que 10.000300156 segundos.
Entonces, mediante el uso de notaciones asintóticas, tratamos de obtener los límites en el tiempo de ejecución de los algoritmos y eso también al considerar solo el término de orden superior del polinomio y descuidar los términos y constantes de orden inferior.
espero que esto ayude
Puede ver la siguiente lista de reproducción para obtener más detalles.