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.Diferencia entre O (n) y O (log (n)) - ¿cuál es mejor y qué es exactamente O (log (n))?
Esto significa que la cosa en cuestión (por lo general el tiempo de funcionamiento) las escalas de una manera que es consistente con el logaritmo de su tamaño de entrada.
Big-O notation no significa una ecuación exacta , sino más bien un obligado. Por ejemplo, la salida de las siguientes funciones es todo O (n):
f(x) = 3x
g(x) = 0.5x
m(x) = x + 5
Debido a medida que aumenta x, sus salidas todo aumento linealmente - si hay una relación 6: 1 entre f(n) y g(n), también habrá aproximadamente una relación de 6: 1 entre f(10*n) y g(10*n) y así sucesivamente.
En cuanto a si O(n) o O(log n) es mejor, considere: si n = 1000, entonces log n = 3 (por log-base-10). ¿Qué prefieres que ejecute tu algoritmo para ejecutar: 1000 segundos o 3 segundos?
Bien explicado. Además, me gustaría agregar algo de información acerca de lo que es un logaritmo incluso para aquellos que no saben. log n en medios informáticos, el exponente que necesitaría elevar el número 2 para obtener n. Entonces imagine, si n = 16. Nuestro exponente sería mucho más pequeño que el valor de n real. Sería 4. Espero que esto tenga sentido. En el ejemplo anterior de Amber, ella está dando un ejemplo similar pero elevando 10 a la potencia de 3. –
+1 - La explicación más clara posible en el menor número de palabras. Gracias. – techfoobar
http://en.wikipedia.org/wiki/Big_oh
O (log n) es mejor.
O (log n) significa que el tiempo de funcionamiento del algoritmo depende del logaritmo de la magnitud 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 (log n) también son O (n), pero no al revés ...
"O (n) es más ajustado que O (logn) y también es mejor en términos de análisis de algoritmos" ... claramente O (log (n)) es mejor que O (n). Creo que querías decir lo contrario. – LuxuryMode
Silly :) editado – Eyal
Para la entrada de tamaño n, un algoritmo de O(n) llevará a cabo los pasos perportional a n, mientras que otro algoritmo de O(log(n)) llevará a cabo pasos aproximadamente log(n).
Claramente log(n) es menor que n por lo tanto, el algoritmo de complejidad O(log(n)) es mejor. Ya que será mucho más rápido.
definición formal:
g (x) = O (f (x)) < => hay x0 y constante C que para cada x0 x>, | 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 menor o igual que f (n) asintóticamente, cuando n es generalmente el tamaño de entrada. (n puede ser cualquier cosa)
Para obtener más información: http: //en.wikipedia.org/wiki/Big_O_notation.
Una posible repetición de http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o/487278#487278 – sank
Whoa, 1429 upvotes? Estaré contento con la mitad de eso para mi enlace de wikipedia. –