math - little - big o rap
Gran confusión O: log2(N) vs log3(N) (4)
¿Por qué O (log 2 N) = O (log 3 N)?
No entiendo esto ¿O grande no significa límite superior de algo?
¿No es log 2 N más grande que log 3 N? Cuando los graficé, log 2 N está por encima de log 3 N.
Big O no trata con factores constantes, y la diferencia entre Log x (n) y Log y (n) es un factor constante.
Para decirlo de forma un poco diferente, la base del logaritmo básicamente solo modifica la pendiente de una línea / curva en el gráfico. Big-O no se preocupa por la pendiente de la curva en el gráfico, solo por la forma de la curva. Si puede hacer que una curva coincida con otra desplazando su pendiente hacia arriba o hacia abajo, entonces, en lo que respecta a la notación Big-O, son la misma función y la misma curva.
Para intentar poner esto en perspectiva, tal vez sería útil un dibujo de algunas de las formas de curvas más comunes:
Sin embargo, como se señaló anteriormente, solo la forma de una línea importa, no su pendiente. En la siguiente figura:
... todas las líneas son rectas, por lo que, aunque sus pendientes difieren radicalmente, siguen siendo todas idénticas en lo que respecta a la gran O: son todas O (N), independientemente de la pendiente. Con los logaritmos, obtenemos aproximadamente el mismo efecto: cada línea se curvará como la línea O (log N) en la imagen anterior, pero al cambiar la base del logaritmo la curva girará alrededor del origen, por lo que (de nuevo) tienen la misma forma de línea, pero en diferentes pendientes (así que, nuevamente, en lo que respecta a la gran O, todos son idénticos). Entonces, al llegar a la pregunta original, si cambiamos las bases de los logaritmos, obtenemos curvas que se parecen a esto:
Aquí puede ser un poco menos obvio que todo lo que está sucediendo es un cambio constante en la pendiente, pero esa es exactamente la diferencia aquí, al igual que con las líneas rectas de arriba.
Depende del contexto en el que se utiliza la notación O. Cuando lo está utilizando en el razonamiento de complejidad algorítmica, está interesado en el comportamiento asintótico de una función, es decir, cómo crece / disminuye cuando tiende al infinito (más o menos) (u otro punto de acumulación).
Por lo tanto, mientras que f(n) = 3n es siempre menor que g(n) = 1000n , ambos aparecen en O(n) ya que crecen de manera asintótica (de acuerdo con sus expresiones).
Se puede tomar el mismo patrón de razonamiento para el caso de logaritmo que se publicó, ya que los logaritmos de diferentes bases difieren por un factor constante, pero comparten el mismo comportamiento asintótico.
Cambio de contexto, si estaba interesado en calcular el rendimiento exacto de un algoritmo dado que sus estimaciones son exactas y no aproximadas, preferiría el más bajo, por supuesto. En general, todas las comparaciones de complejidad computacional son aproximaciones, por lo tanto, se realizan mediante razonamiento asintótico.
Es porque cambiar la base de los logaritmos es igual a multiplicarlo por una constante. Y a la gran O no le importan las constantes.
log_a(b) = log_c(b) / log_c(a)
Entonces, para pasar de log2(n) a log3(n) necesitas multiplicarlo por 1 / log(3) 2 .
En otras palabras, log2(n) = log3(n) / log3(2) .
log3(2) es una constante y O(cn) = O(n) , por lo tanto O (log2(n)) = O (log3(n))
Ya hay una buena respuesta aquí, así que por favor léalas también. Para comprender por qué Log2 (n) es O (log3 (n)), debe comprender dos cosas.
1) ¿Qué significa la notación BigO? Le sugiero que lea esto: http://en.wikipedia.org/wiki/Big_O_notation Si lo subestima, sabrá que 2n y 16n+5 son O(N)
2) Cómo funcionan los logaritmos. La diferencia entre log 2 (N) y log 10 (N) será una proporción simple, que se calculará fácilmente si lo desea según la respuesta de luk32.
Dado que los registros en diferentes bases difieren solo en una proporción constante, y Big O es indiferente a cosas menores como factores de multiplicación constante, a menudo encontrará que O (logN) en realidad omite la base, porque la elección de cualquier base constante (por ejemplo, 2 3,10, e ) no hace ninguna diferencia en este contexto.