algorithm - notación - Diferencia entre O(n) y O(log(n))-¿cuál es mejor y qué es exactamente O(log(n))?
notacion de un algoritmo (5)
Definicion formal:
g (x) = O (f (x)) <=> hay x0 y constante C que para cada x> x0, | g (x) | <= C | f (x) |.
Por lo tanto, si encuentra el algoritmo A para el problema P que es su complejidad O (f (n)), puede decir que el número de pasos que su algoritmo hará, es más o menos asintóticamente a f (n), cuando n suele ser el tamaño de entrada (n puede ser cualquier cosa)
Para más información: http: //en.wikipedia.org/wiki/Big_O_notation.
Este es mi primer curso en estructuras de datos y cada conferencia / conferencia TA, hablamos de O(log(n)) . Esta es probablemente una pregunta tonta, pero agradecería que alguien me explique exactamente qué significa.
O (logn) significa que el tiempo de ejecución del algoritmo depende del logaritmo del tamaño de entrada. O (n) significa que el tiempo de ejecución del algoritmo depende del tamaño de la entrada.
básicamente, O (algo) es un límite superior en el número de instrucciones del algoritmo (atómicas). por lo tanto, O (logn) es más ajustado que O (n) y también es mejor en términos de análisis de algoritmos. Pero todos los algoritmos que son O (logn) también son O (n), pero no al revés ...
Para la entrada de tamaño n , un algoritmo de O(n) realizará los pasos per proporcionales a n , mientras que otro algoritmo de O(log(n)) realizará los pasos aproximadamente log(n) .
Claramente log(n) es más pequeño que n tanto, el algoritmo de complejidad O(log(n)) es mejor. Ya que será mucho más rápido.
Significa que la cosa en cuestión (usualmente el tiempo de ejecución) escala de una manera que es consistente con el logaritmo de su tamaño de entrada.
La notación Big-O no significa una ecuación exacta , sino un límite . Por ejemplo, el resultado de las siguientes funciones es todo O (n):
f(x) = 3x
g(x) = 0.5x
m(x) = x + 5
Debido a que a medida que aumentas x, todas sus salidas aumentan linealmente, si hay una relación de 6: 1 entre f(n) g(n) , también habrá una relación aproximada de 6: 1 entre f(10*n) g(10*n) y así sucesivamente.
En cuanto a si O(n) u O(log n) es mejor, considere: si n = 1000 , entonces log n = 3 (para log-base-10). ¿Qué prefieres que ejecute tu algoritmo para ejecutar: 1000 segundos o 3 segundos?
http://en.wikipedia.org/wiki/Big_oh
O (log n) es mejor.