Soy nuevo en la comprensión de los algoritmos informáticos. Entiendo el proceso de búsqueda binaria, pero tengo un ligero malentendido con su eficiencia.
En un tamaño de $ s = 2 ^ n $ elementos, se necesitarían, en promedio, $ n $ pasos para encontrar un elemento en particular. Tomando el logaritmo en base 2 de ambos lados se obtiene $ \ log_2 (s) = n $. Entonces, ¿el número promedio de pasos para el algoritmo de búsqueda binaria no sería $ \ log_2 (s) $?
Este artículo de Wikipedia sobre el algoritmo de búsqueda binaria dice que el rendimiento promedio es $ O (\ log n) $. ¿Por qué es así? ¿Por qué no es este número $ \ log_2 (n) $?
Comentarios
- Duplicar en SO – ¿Es Big O (logn) log base e?
Respuesta
Cuando cambia la base del logaritmo, la expresión resultante difiere solo por un factor constante que, por definición de notación Big-O , implica que ambas funciones pertenecen a la misma clase con respecto a su comportamiento asintótico.
Por ejemplo $$ \ log_ {10} n = \ frac {\ log_ {2} n} {\ log_ {2} 10} = C \ log_ {2} {n} $$ donde $ C = \ frac {1} {\ log_ {2} 10} $.
Entonces $ \ log_ {10} n $ y $ \ log_ {2} n $ difieren en una constante $ C $, y por lo tanto ambos son verdaderos: $$ \ log_ {10} n \ text {is} O (\ log_ {2} n) $$ $$ \ log_ {2} n \ text {es} O (\ log_ {10} n) $$ En general $ \ log_ {a} {n} $ es $ O (\ log_ {b} {n}) $ para enteros positivos $ a $ y $ b $ mayores que 1.
Otro hecho interesante con las funciones logarítmicas es que mientras que para la constante $ k > 1 $, $ n ^ k $ NO es $ O (n) $, pero $ \ log {n ^ k} $ es $ O (\ log {n}) $ ya que $ \ log {n ^ k} = k \ log {n} $ que difiere de $ \ log {n} $ solo por el factor constante $ k $.
Comentarios
- No solo para enteros positivos: para todos los $ a, b > 1 $, p. Ej. $ e $.
- Yo agregaría que esta es la razón por la cual con la notación O grande, la base del logaritmo comúnmente no se especifica. También significa que no hay confusión acerca de qué base $ O (\ log n) $ usa: puede ser cualquiera de las que se usan comúnmente, ya que no ' no hace una diferencia.
Respuesta
Además de la respuesta de fade2black (que es completamente correcta), vale la pena señalar que la notación «$ \ log (n) $» es ambigua. La base no está realmente especificada y la base predeterminada cambia según el contexto. En matemáticas puras, casi siempre se asume que la base es $ e $ (a menos que se especifique), mientras que en ciertos contextos de ingeniería podría ser 10. En informática , la base 2 es tan ubicua que con frecuencia se asume que $ \ log $ es la base 2. Ese artículo de wikipedia nunca dice nada sobre la base.
Pero, como ya se ha mostrado, en este caso no » t terminan importando.
Comentarios
- Probablemente valga la pena señalar que mientras " log (n) " puede ser ambiguo que " O (log (n)) " no se debe a que este último solo tenga un significado, sin importar en qué base estés pensando.