¿La base logarítmica de Big O (logn) es e?

Para el tipo de árbol de búsqueda binario de estructuras de datos, veo que la notación Big O generalmente se indica como O (logn). Con una 'l' minúscula en log, ¿esto implica log base e (n) como lo describe el logaritmo natural? Perdón por la pregunta simple, pero siempre he tenido problemas para distinguir entre los diferentes logaritmos implícitos.

Una vez expresados ​​en notación O grande (), ambos son correctos. Sin embargo, durante la derivación del polinomio O (), en el caso de la búsqueda binaria , solo log ₂ es correcto. Supongo que esta distinción fue la inspiración intuitiva de su pregunta para empezar.

Además, en mi opinión, escribir O (log ₂ N) es mejor para su ejemplo, porque comunica mejor la derivación del tiempo de ejecución del algoritmo.

En la notación Big-O (), se eliminan los factores constantes. La conversión de una base logarítmica a otra implica multiplicar por un factor constante.

Entonces, O (log N) es equivalente a O (log ₂ N) debido a un factor constante.

Sin embargo, si puede escribir fácilmente log ₂ N en su respuesta, hacerlo es más pedagógico. En el caso de la búsqueda de árbol binario, tiene razón en que log ₂ se introduce N durante la derivación del tiempo de ejecución big-O ().

Antes de expresar el resultado como notación O grande (), la diferencia es muy importante. Al derivar el polinomio que se comunicará a través de la notación O grande, sería incorrecto para este ejemplo utilizar un logaritmo distinto de log ₂ N, antes de aplicar la notación O (). Tan pronto como el polinomio se use para comunicar un tiempo de ejecución en el peor de los casos mediante la notación big-O (), no importa qué logaritmo se use.

La notación Big O no se ve afectada por la base logarítmica, porque todos los logaritmos en bases diferentes están relacionados por un factor constante , O(ln n)es equivalente a O(log n).

Realmente no importa qué base sea, ya que la notación de O grande generalmente se escribe mostrando solo el orden asintóticamente más alto de n, por lo que los coeficientes constantes desaparecerán. Dado que una base logarítmica diferente es equivalente a un coeficiente constante, es superflua.

Dicho esto, probablemente asumiría log base 2.

Ambos son correctos. Piensa sobre esto

log2(n)=log(n)/log(2)=O(log(n))
log10(n)=log(n)/log(10)=O(log(n))
logE(n)=log(n)/log(E)=O(log(n))

Sí, cuando se habla de notación Big-O, la base no importa. Sin embargo, computacionalmente cuando se enfrenta a un problema de búsqueda real, sí importa.

Al desarrollar una intuición sobre las estructuras de los árboles, es útil comprender que un árbol de búsqueda binario se puede buscar en O (n log n) tiempo porque esa es la altura del árbol, es decir, en un árbol binario con n nodos, el árbol la profundidad es O (n log n) (base 2). Si cada nodo tiene tres hijos, el árbol todavía se puede buscar en tiempo O (n log n), pero con un logaritmo de base 3. Computacionalmente, la cantidad de hijos que tiene cada nodo puede tener un gran impacto en el rendimiento (ver, por ejemplo: texto del enlace )

¡Disfrutar!

Pablo

Técnicamente, la base no importa, pero generalmente puedes pensar en ella como base-2.

Primero debe comprender lo que significa que una función f (n) sea O (g (n)).

La definición formal es: * Se dice que una función f (n) es O (g (n)) sif | f (n) | <= C * | g (n) | siempre que n> k, donde C y k son constantes. *

así que sea f (n) = log base a de n, donde a> 1 y g (n) = log base b of n, donde b> 1

NOTA: Esto significa que los valores ayb pueden ser cualquier valor mayor que 1, por ejemplo, a = 100 y b = 3

Ahora obtenemos lo siguiente: log base a de n se dice que es O (log base b of n) iff | log base a of n | <= C * | base logarítmica b de n | siempre que n> k

Elija k = 0 y C = base logarítmica a de b.

Ahora nuestra ecuación se parece a la siguiente: | base logarítmica a de n | <= base logarítmica a de b * | base logarítmica b de n | siempre que n> 0

Observe el lado derecho, podemos manipular la ecuación: = base logarítmica a de b * | base logarítmica b de n | = | base logarítmica b de n | * base logarítmica a de b = | base logarítmica a de b ^ (base logarítmica b de n) | = | base logarítmica a de n |

Ahora nuestra ecuación se parece a la siguiente: | base logarítmica a de n | <= | base logarítmica a de n | siempre que n> 0

La ecuación es siempre verdadera sin importar cuáles sean los valores n, bo a, además de sus restricciones a, b> 1 y n> 0. Entonces, la base logarítmica a de n es O (base logarítmica b de n) y dado que a, b no importa, simplemente podemos omitirlos.

Puede ver un video de YouTube aquí: https://www.youtube.com/watch?v=MY-VCrQCaVw

Puede leer un artículo al respecto aquí: https://medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca