algorithm - complexity - Big O notation Log Base 2 o Log Base 10
sorting algorithms big o (3)
Esta pregunta ya tiene una respuesta aquí:
- ¿Es Big O (logn) log base e? 7 respuestas
Cuando los artículos / preguntas indican que el tiempo de ejecución de Big O del algoritmo es O (LogN).
Por ejemplo, Quicksort tiene un tiempo de ejecución de Big O de O (LogN) donde está la base de registros 10 pero la altura del árbol binario es O (LogN + 1) donde está la base de registros 2
Pregunta
1) Estoy confundido sobre si se trata de Log base 10 o Log base 2, ya que diferentes artículos usan diferentes bases para su logaritmo.
2) ¿Hay alguna diferencia si su Log base 2 o Log base 10?
3) ¿Podemos asumir que significa Log base 10 cuando vemos O (LogN)?
Creo que no importa cuál sea la base del registro, ya que la complejidad relativa es la misma independientemente de la base utilizada.
Así que puedes pensar que es O (log 2 X) = O (log 10 X)
También mencionar que los logaritmos están relacionados por alguna constante.
Asi que
log₁₀ ( x ) = log₂ ( x ) / log₂ (10)
Por lo general, la mayoría de las veces ignoramos las constantes en el análisis de complejidad y, por lo tanto, decimos que la base no importa.
También es posible que la base se considere 2 la mayor parte del tiempo como en Merge Sort . El árbol tiene una altura de log₂ n , ya que el nodo tiene dos ramas.
1) Estoy confundido sobre si se trata de Log base 10 o Log base 2, ya que diferentes artículos usan diferentes bases para su logaritmo.
Entonces, como se explicó anteriormente, este cambio de base no importa.
2) ¿Hay alguna diferencia si su Log base 2 o Log base 10?
No, no importa.
3) ¿Podemos asumir que significa Log base 10 cuando vemos O (LogN)?
Sí, puede asumir que siempre que conozca la regla de conversión base.
En la notación Big O, O(log(n)) es el mismo para todas las bases. Esto se debe a la conversión de base logarítmica:
log2(n) = log10(n)/log10(2)
1/log10(2) es solo un factor multiplicador constante, por lo que O(log2(n)) es lo mismo que O(log10(n))
log₁₀ ( x ) = log₂ ( x ) / log₂ (10) para todas las x . 1 / log₂ (10) es un multiplicador constante y puede omitirse del análisis asintótico.
Más generalmente, la base de cualquier logaritmo puede cambiarse de a a b (ambas constantes wrt. N ) dividiendo por log by ( b ), de modo que puede cambiar libremente entre bases de registro mayores que uno: O (log₁₀ ( n )) es lo mismo que O (log₂ ( n )), O (ln ( n )), etc.
Un ejemplo de esto es que B-trees no superan asintóticamente los árboles de búsqueda binaria balanceados, a pesar de que proporcionan mayores bases de registro en el análisis. Los justos tienen mejores constantes.