math - little - big-o notation java
¿Es Big O(logn) base de registro e? (7)
Para el tipo de árbol de búsqueda binario de estructuras de datos, veo que la notación de Big O se anota típicamente como O (logn). Con una ''l'' minúscula en el registro, ¿esto implica la base de registro e (n) según lo describe el logaritmo natural? Perdón por la simple pregunta, pero siempre he tenido problemas para distinguir entre los diferentes logaritmos implícitos.
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))
En realidad, no importa de qué base se trate, ya que la notación de grandes O se escribe usualmente mostrando solo el orden más alto asintóticamente de n , de modo que los coeficientes constantes desaparecerán. Como una base de logaritmo diferente es equivalente a un coeficiente constante, es superflua.
Dicho esto, probablemente asumiría la base de registro 2.
La notación Big O no se ve afectada por la base logarítmica, porque todos los logaritmos en diferentes bases están relacionados por un factor constante , O(ln n) es equivalente a O(log n) .
Primero debes entender lo que significa para una función f (n) ser O (g (n)).
La definición formal es: * Se dice que una función f (n) es O (g (n)) iff | f (n) | <= C * | g (n) | siempre que n> k, donde C y k son constantes. *
entonces, f (n) = log base a de n, donde a> 1 yg (n) = log base b de n, donde b> 1
NOTA: Esto significa que los valores a y b podrían ser cualquier valor mayor que 1, por ejemplo a = 100 yb = 3
Ahora obtenemos lo siguiente: la base de registro a de n se dice que es O (base de registro b de n) iff | base de registro a de n | <= C * | base de registro b de n | siempre que n> k
Elija k = 0, y C = log base a de b.
Ahora nuestra ecuación tiene el siguiente aspecto: | base de registro a de n | <= base de registro a de b * | base de registro b de n | siempre que n> 0
Observe el lado derecho, podemos manipular la ecuación: = log base a de b * | log base b de n | = | base de registro b de n | * base de registro a de b = | log base a de b ^ (base de registro b de n) | = | base de registro a de n |
Ahora nuestra ecuación tiene el siguiente aspecto: | base de registro a de n | <= | base de registro a de n | siempre que n> 0
La ecuación es siempre verdadera sin importar cuáles sean los valores n, b, o a, además de sus restricciones a, b> 1 y n> 0. Así que la base de registro a de n es O (base de registro b de n) y dado que a, b no importa, podemos simplemente omitirlos.
Puede ver un video de YouTube aquí: https://www.youtube.com/watch?v=MY-VCrQCaVw
Puede leer un artículo aquí: https://medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca
Sí, cuando se habla de notación de gran O, la base no importa. Sin embargo, computacionalmente cuando se enfrenta con un problema de búsqueda real sí importa.
Al desarrollar una intuición sobre estructuras de árbol, es útil comprender que un árbol de búsqueda binario puede buscarse en el tiempo O (n log n) 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 aún se puede buscar en el 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 (véase, por ejemplo, el texto del enlace ).
¡Disfrutar!
Pablo
Técnicamente, la base no importa, pero en general se puede considerar como base-2.
Una vez expresados en notación big-O (), ambos son correctos. Sin embargo, durante la derivación del polinomio O (), en el caso de la búsqueda binaria , solo el log 2 es correcto. Supongo que esta distinción fue la inspiración intuitiva para su pregunta, para empezar.
Además, como una cuestión de mi opinión, escribir O (log 2 N) es mejor para su ejemplo, porque comunica mejor la derivación del tiempo de ejecución del algoritmo.
En notación big-O (), los factores constantes se eliminan. Convertir de una base de logaritmo a otra implica multiplicar por un factor constante.
Entonces O (log N) es equivalente a O (log 2 N) debido a un factor constante.
Sin embargo, si puede escribir fácilmente log 2 N en su respuesta, hacerlo es más pedagógico. En el caso de la búsqueda de árbol binario, tiene la razón de que se introduce log 2 N durante la derivación del tiempo de ejecución big-O ().
Antes de expresar el resultado como notación grande-O (), la diferencia es muy importante. Al derivar el polinomio a comunicar a través de la notación de O grande, sería incorrecto para este ejemplo usar un logaritmo distinto de log 2 N, antes de aplicar la notación O (). Tan pronto como el polinomio se usa para comunicar el tiempo de ejecución del peor de los casos a través de la notación big-O (), no importa qué logaritmo se use.