¿Por qué el registro en la gran O de la búsqueda binaria no es base 2?

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

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.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *