Intuición algorítmica para la complejidad logarítmica.

60

Creo que tengo una comprensión razonable de complejidades como O(1) , Θ(n) y Θ(n2) .

En términos de una lista, O(1) es una búsqueda constante, por lo que solo está encabezando la lista. Θ(n) es donde recorrería toda la lista, y Θ(n2) recorre la lista una vez para cada elemento de la lista.

¿Existe una forma intuitiva similar de comprender Θ(logn) no sea simplemente saber que se encuentra en algún lugar entre O(1) y Θ(n) ?

Khanzor
fuente
8
log n es para "buscar": piense en la búsqueda binaria
Suresh
2
Usar para hacer esta pregunta es incorrecto, ya que solo denota un límite superior. Por ejemplo, el tiempo constante es O ( log n ) . θ sería más apropiado. Ver meta pregunta: meta.cs.stackexchange.com/questions/182/…OO(logn)θ
Aryabhata
1
Más información sobre SO: ¿qué significa exactamente? O(logn).
Ran G.
Una pequeña nota: en la configuración clásica de Turing Machine, todos los algoritmos son , ya que necesitan leer cada símbolo de la entrada al menos una vez. La búsqueda binaria se puede hacer en O ( log n ) porque tenemos la promesa de que la lista está ordenada, por ejemplo. Ω(n)O(logn)
chazisop
1
Una contribución tardía: por definición, el logaritmo de base de un número n es solo la cantidad de veces que multiplica b por sí mismo para obtener n . b l = nbnbn . Por ejemplo, 2 3 = 8bl=nl=logb(n) . Entonces, si tiene un número n y desea averiguar qué l o g b ( n ) = ? sigue dividiéndolo por b hasta llegar a 1 (suponiendo que n es una potencia de b por simplicidad). El número de divisiones es igual a l o g b ( n ) . Los algoritmos que exhiben este comportamiento de división tienen tiempos de ejecución en O ( l o g23=8log2(8)=3nlogb(n)=?b1nblogb(n) . O(log(n))
saadtaame

Respuestas:

54

La complejidad generalmente está relacionada con la subdivisión. Cuando utilice listas como ejemplo, imagine una lista cuyos elementos están ordenados. Puede buscar en esta lista en el tiempo O ( log n ) ; en realidad, no necesita mirar cada elemento debido a la naturaleza ordenada de la lista.Θ(Iniciar sesiónnorte)O(Iniciar sesiónnorte)

Si observa el elemento en el medio de la lista y lo compara con el elemento que busca, puede decir de inmediato si se encuentra en la mitad izquierda o derecha de la matriz. Luego puede tomar esta mitad y repetir el procedimiento hasta que lo encuentre o llegar a una lista con 1 elemento que compara trivialmente.

Puede ver que la lista efectivamente reduce a la mitad cada paso. Eso significa que si obtiene una lista de longitud , los pasos máximos que necesita para llegar a la lista de un elemento son 5 . Si tiene una lista de 128 = 2 7 elementos, solo necesita 7 pasos, para una lista de 1024 = 2 10 solo necesita 10 pasos, etc.325128=2771024=21010

Como puede ver, el exponente en 2 n siempre muestra el número de pasos necesarios. El logaritmo se usa para "extraer" exactamente este número de exponente, por ejemplo log 2 2 10 = 10 . También se generaliza para enumerar longitudes que no son potencias de dos largos.n2nlog2210=10

Karel Petranek
fuente
44
Cabe señalar que esto es solo O(log n)si la lista tiene acceso aleatorio de tiempo constante. En implementaciones de listas más típicas (listas enlazadas) esto esO(n log n)
asm
1
La búsqueda binaria no funciona en las listas por la falta de punteros; generalmente se realiza en matrices.
Raphael
La búsqueda binaria funciona bien en las listas. Es bastante inútil debido a que es mucho más complicado de lo requerido / útil / práctico.
Anton
@AndrewMyers La búsqueda de una lista vinculada es más precisa O(n)
phant0m
1
@ phant0m Sí, me tomó un tiempo darme cuenta de que está asumiendo que te estás moviendo desde la posición actual en lugar de atravesar desde el principio cada vez.
asm
38

En términos de árboles (equilibrados) (por ejemplo, árbol binario, todos los son base 2):log

  • está obteniendo la raíz del árbolΘ(1)
  • es un pie de la raíz a la hojaΘ(logn)
  • atraviesa todos los nodos del árbolΘ(n)
  • es acciones en todos los subconjuntos de dos nodos en el árbol, por ejemplo, el número de rutas diferentes entre dos nodos.Θ(n2)
  • : generalización de lo anterior para cualquier subconjunto de k nodos (para una constante k )Θ(nk)kk
  • es acciones en todos los subconjuntos posibles de nodos (subconjuntos de todos los tamaños posibles, es decir, k = 1 , 2 , ... , n .). Por ejemplo, el número desubárbolesdiferentesdel árbol.Θ(2n)k=1,2,...,norte
Sonó.
fuente
55
Para agregar a esto, intuición para proviene de dos cosas: 1.) La recurrencia T ( n ) = T ( Θ(loglogn)y 2.) Búsqueda binaria en algo de tamañolog(n)es decir, una búsqueda binaria en la altura del árbol. T(n)=T((n))+1log(n)
mcorley
17

Para que sea ​​posible, debe poder reducir el tamaño del problema proporcionalmente en una cantidad arbitraria con respecto a n con una operación de tiempo constante.O(logn)n

Por ejemplo, en el caso de la búsqueda binaria, puede reducir el tamaño del problema a la mitad con cada operación de comparación.

Ahora, ¿tiene que reducir el tamaño del problema a la mitad, en realidad no? Un algoritmo es incluso si puede reducir el espacio de búsqueda del problema en un 0,0001%, siempre que el porcentaje y la operación que utiliza para reducir el tamaño del problema permanezca constante, es un algoritmo O ( log n ) , no será un algoritmo rápido, pero sigue siendo O ( log n ) con una constante muy grande. (Suponiendo que estamos hablando de log n con un log de base 2)O(logn)O(logn)O(logn)logn

Ken Li
fuente
1
¿Qué sería si la 'cantidad de reducción' no fuera constante?
Svish
@Svish Si puede reducir el problema a una tasa positiva, seguiría siendo un algoritmo , aunque probablemente ya no sería un límite estrecho. La tasa negativa es difícil de decir. Se supuso que la respuesta es bastante simple en este caso, dado que esta pregunta tiene sus propios méritos, es más que bienvenido a hacer esta pregunta por sí sola. O(logn)
Ken Li
Sí, quería decir que el espacio de búsqueda del problema siempre disminuía, pero no necesariamente a un ritmo constante. Estaba pensando en su "mientras el porcentaje y la operación que utiliza para reducir el tamaño del problema permanezca constante, es un algoritmo O (log n)"; si tuviera un nombre diferente si el porcentaje no fuera constante.
Svish
8

Piense en el algoritmo para convertir el número decimal a binarion

while n != 0:
   print n%2, 
   n = n/2

Este whileciclo se ejecuta veces.log(n)

Pratik Deoghare
fuente
1
Ciertamente, este programa loops n veces, pero generalmente cuando hablamos de la complejidad O ( f ( s ) ) , s es el tamaño de su entrada. Aquí el tamaño de su entrada ya es s = log n , por lo que diría que este programa es solo lineal (en O ( s ) )lognO(f(s))ss=lognO(s)
jmad
@jmad bien. Pero este ejemplo te da intuición en log (n).
Pratik Deoghare
@jmad Podría haber usado un algoritmo para generar números aleatorios también, pero quería que fuera lo más simple posible.
Pratik Deoghare
8

Sí, es de entre 1 y n , pero está más cerca de 1 que n . ¿Qué es log ( n ) ? La función de registro es la función inversa de la exponenciación. Permítanme comenzar con la exponenciación y deberían tener una mejor idea de qué es el logaritmo.log(n)1n1nlog(n)

Considere dos números, y 2 100 . 2 100 es 2 multiplicado consigo mismo 100 veces. Con un poco de esfuerzo puedes contar 100 números, pero ¿puedes contar 2 100 ? Apuesto a que no puedes. ¿Por qué? 2 100 es un número tan grande que es mayor que el número de todos los átomos en el universo. Reflexiona sobre eso por un momento. Es un número tan enorme que le permite dar un nombre (número) a cada átomo. Y la cantidad de átomos en la uña de tu dedo probablemente sea del orden de miles de millones. 2 100 debería ser suficiente para cualquiera (juego de palabras :)).100210021002100100210021002100

Ahora, entre los dos números, y 2 100 , 100 es el logaritmo de 2 100 (en la base 2 ). 100 es comparativamente un número tan pequeño que 2 100 . Cualquiera debería tener 100 artículos diferentes en su hogar. Pero, 2 100 es lo suficientemente bueno para el universo. Piense en casa vs universo cuando piense en log ( n ) y n .10021001002100210021001002100log(n)n

¿De dónde vienen la exponenciación y los logaritmos? ¿Por qué les interesa tanto la informática? Puede que no lo notes, pero la exponenciación está en todas partes. ¿Pagó intereses con tarjeta de crédito? Acaba de pagar un universo por su hogar (no está tan mal, pero la curva se ajusta). Me gusta pensar que la exponenciación proviene de la regla del producto, pero otros son bienvenidos para dar más ejemplos. ¿Cuál es la regla del producto? Y responderé.

Digamos que tiene dos ciudades y B , y hay dos formas de ir entre ellas. ¿Cuál es el número de caminos entre ellos? Dos. Eso es trivial Ahora digamos, hay otra ciudad C , y puedes ir de B a C de tres maneras. ¿Cuántos caminos hay entre A y C ahora? Seis, ¿verdad? ¿Cómo conseguiste eso? ¿Los contaste? ¿O los multiplicaste? De cualquier manera, es fácil ver que ambas dan un resultado similar. Ahora, si agrega una ciudad D a la que se puede llegar desde C de cuatro maneras, ¿cuántas maneras hay entre A y D?ABCBCACDCAD? Cuenta si no confías en mí, pero es igual a que es 24 . Ahora, si hay diez ciudades y hay dos caminos de una ciudad a otra, y están dispuestos como si estuvieran en línea recta. ¿Cuántos caminos hay de principio a fin? Multiplíquelos si no confía en mí, pero le diré que hay 2 10 , que es 1024 . Vea que 2 10 es el resultado exponencial de 10 , y 10 es el logaritmo de 2 10 . 10 es un número pequeño en comparación con 1024 .2342421010242101010210101024

La función logaritmo es n lo que nlog2(n)nn es (tenga en cuenta que 2 es la base del logaritmo). Si multiplica el registro b ( n ) consigo mismo b veces (tenga en cuenta que b es la base del logaritmo) obtendrá n . log ( n ) es tan pequeño, tan pequeño en comparación con n , que es el tamaño de su hogar donde n es el tamaño del universo.2n2logb(n)bbnlog(n)nn

En una nota práctica, las funciones realizan funciones muy similares a las constantes. Crecen con n , pero crecen muy lentamente. Si optimizó un programa para que se ejecute en tiempo logarítmico que estaba tardando un día antes, probablemente lo ejecutará en el orden de minutos. Compruébelo usted mismo con problemas en el Proyecto Euler.log(n)n

Ravi
fuente
3
Aunque está bien escrita, esta respuesta apenas contiene información además de " es realmente pequeño". log(n)
Raphael
3
Estaba tratando de dar una intuición de lo pequeño que es.
Ravi
5

Para continuar con su tema, es como adivinar repetidamente dónde está x en la lista y que le digan "más alto" o "más bajo" (en términos de índice).O(logn)x

Todavía se basa en el tamaño de la lista, pero solo necesita visitar una fracción de los elementos.

dpatchery
fuente
4

Si tenemos un algoritmo de divide y vencerás , y hacemos una sola llamada recursiva para un subproblema, y ​​es el segundo caso en el teorema maestro , es decir, la complejidad temporal de la parte no recursiva es , entonces el La complejidad del algoritmo será Θ ( lg k + 1 n ) .Θ(lgkn)Θ(lgk+1n)

En otras palabras, cuando tenemos un algoritmo de divide y vencerás con una llamada recursiva a sí mismo en un problema con el tamaño un factor constante del problema actual, y el tiempo en la parte no recursiva es (constante), entonces el tiempo de ejecución del algoritmo será lg n .Θ(1)lgn

El algoritmo de búsqueda binaria es el ejemplo clásico.

Kaveh
fuente
1

La intuición es cuántas veces puede reducir a la mitad un número, digamos n, antes de que se reduzca a 1 es O (lg n).

Para visualizar, intente dibujarlo como un árbol binario y cuente el número de niveles resolviendo esta progresión geométrica.

2^0+2^1+...+2^h = n
usuario1234
fuente
Bienvenido al sitio! Lo que usted dice es, por supuesto, cierto, pero no veo lo que agrega a las respuestas existentes. Varias de las respuestas ya dicen que el logaritmo es la cantidad de veces que se puede dividir entre dos antes de tocar 1, y la respuesta de Ran ya dice que es la altura de un árbol binario con n hojas. lognn
David Richerby