Los términos O (log log n) pueden aparecer en una variedad de lugares diferentes, pero normalmente hay dos rutas principales que llegarán en este tiempo de ejecución.
Reducción de una raíz cuadrada
Como se mencionó en la respuesta a la pregunta vinculada, una forma común de que un algoritmo tenga complejidad de tiempo O (log n) es que ese algoritmo funcione reduciendo repetidamente el tamaño de la entrada por algún factor constante en cada iteración. Si este es el caso, el algoritmo debe terminar después de O (log n) iteraciones, porque después de hacer O (log n) divisiones por una constante, el algoritmo debe reducir el tamaño del problema a 0 o 1. Por eso, por ejemplo , la búsqueda binaria tiene complejidad O (log n).
Curiosamente, existe una forma similar de reducir el tamaño de un problema que produce tiempos de ejecución de la forma O (log log n). En lugar de dividir la entrada a la mitad en cada capa, ¿qué sucede si sacamos la raíz cuadrada del tamaño en cada capa?
Por ejemplo, tomemos el número 65.536. ¿Cuántas veces tenemos que dividir esto por 2 hasta que bajemos a 1? Si hacemos esto, obtenemos
- 65.536 / 2 = 32.768
- 32.768 / 2 = 16.384
- 16.384 / 2 = 8.192
- 8.192 / 2 = 4.096
- 4.096 / 2 = 2.048
- 2.048 / 2 = 1.024
- 1.024 / 2 = 512
- 512/2 = 256
- 256/2 = 128
- 128/2 = 64
- 64/2 = 32
- 32/2 = 16
- 16/2 = 8
- 8/2 = 4
- 4/2 = 2
- 2/2 = 1
Este proceso toma 16 pasos, y también se da el caso de que 65,536 = 2 16 .
Pero, si sacamos la raíz cuadrada en cada nivel, obtenemos
- √65.536 = 256
- √256 = 16
- √16 = 4
- √4 = 2
Tenga en cuenta que solo se necesitan cuatro pasos para llegar hasta 2. ¿Por qué?
Primero, una explicación intuitiva. ¿Cuántos dígitos hay en los números n y √n? Hay aproximadamente log n dígitos en el número n, y aproximadamente log (√n) = log (n 1/2 ) = (1/2) log n dígitos en √n. Esto significa que, cada vez que extraes una raíz cuadrada, estás reduciendo aproximadamente a la mitad el número de dígitos del número. Debido a que solo puede dividir a la mitad una cantidad k O (log k) veces antes de que caiga a una constante (digamos, 2), esto significa que solo puede tomar raíces cuadradas O (log log n) veces antes de reducir el número. a alguna constante (digamos, 2).
Ahora, hagamos algunos cálculos matemáticos para que esto sea riguroso. Reescribamos la secuencia anterior en términos de potencias de dos:
- √65,536 = √2 16 = (2 16 ) 1/2 = 2 8 = 256
- √256 = √2 8 = (2 8 ) 1/2 = 2 4 = 16
- √16 = √2 4 = (2 4 ) 1/2 = 2 2 = 4
- √4 = √2 2 = (2 2 ) 1/2 = 2 1 = 2
Observe que seguimos la secuencia 2 16 → 2 8 → 2 4 → 2 2 → 2 1 . En cada iteración, cortamos el exponente de la potencia de dos a la mitad. Eso es interesante, porque esto se conecta con lo que ya sabemos: solo puede dividir el número k por la mitad O (log k) veces antes de que caiga a cero.
Así que toma cualquier número n y escríbelo como n = 2 k . Cada vez que saca la raíz cuadrada de n, reduce a la mitad el exponente en esta ecuación. Por lo tanto, solo se pueden aplicar raíces cuadradas O (log k) antes de que k caiga a 1 o menos (en cuyo caso n cae a 2 o menos). Como n = 2 k , esto significa que k = log 2 n, y por lo tanto, el número de raíces cuadradas tomadas es O (log k) = O (log log n). Por lo tanto, si hay un algoritmo que funciona reduciendo repetidamente el problema a un subproblema de tamaño que es la raíz cuadrada del tamaño del problema original, ese algoritmo terminará después de O (log log n) pasos.
Un ejemplo del mundo real de esto es el árbol de van Emde Boas. estructura de datos (árbol vEB). Un árbol vEB es una estructura de datos especializada para almacenar números enteros en el rango 0 ... N - 1. Funciona de la siguiente manera: el nodo raíz del árbol tiene punteros √N, dividiendo el rango 0 ... N - 1 en √N cubos, cada uno con un rango de aproximadamente √N enteros. Luego, cada uno de estos cubos se subdivide internamente en cubos √ (√ N), cada uno de los cuales contiene aproximadamente √ (√ N) elementos. Para atravesar el árbol, comience en la raíz, determine a qué depósito pertenece y luego continúe recursivamente en el subárbol correspondiente. Debido a la forma en que está estructurado el árbol vEB, puede determinar en O (1) tiempo a qué subárbol descender, y luego de O (log log N) pasos llegará a la parte inferior del árbol. En consecuencia, las búsquedas en un árbol vEB solo toman tiempo O (log log N).
Otro ejemplo es el algoritmo del par de puntos más cercano de Hopcroft-Fortune . Este algoritmo intenta encontrar los dos puntos más cercanos en una colección de puntos 2D. Funciona creando una cuadrícula de cubos y distribuyendo los puntos en esos cubos. Si en cualquier punto del algoritmo se encuentra un depósito que tiene más de √N puntos, el algoritmo procesa de forma recursiva ese depósito. Por lo tanto, la profundidad máxima de la recursividad es O (log log n), y usando un análisis del árbol de recursividad se puede demostrar que cada capa en el árbol hace O (n) trabajo. Por lo tanto, el tiempo de ejecución total del algoritmo es O (n log log n).
O (log n) Algoritmos en entradas pequeñas
Hay algunos otros algoritmos que logran tiempos de ejecución O (log log n) mediante el uso de algoritmos como la búsqueda binaria en objetos de tamaño O (log n). Por ejemplo, la estructura de datos x-fast trie realiza una búsqueda binaria sobre las capas de un árbol de altura O (log U), por lo que el tiempo de ejecución de algunas de sus operaciones es O (log log U). El trie y-fast relacionado obtiene algunos de sus tiempos de ejecución O (log log U) al mantener BST balanceados de los nodos O (log U) cada uno, lo que permite que las búsquedas en esos árboles se ejecuten en el tiempo O (log log U). El árbol del tango y el árbol multipantalla relacionado estructuras de datos del terminan con un término O (log log n) en sus análisis porque mantienen árboles que contienen O (log n) elementos cada uno.
Otros ejemplos
Otros algoritmos logran el tiempo de ejecución O (log log n) de otras formas. La búsqueda de interpolación ha esperado que el tiempo de ejecución O (log log n) encuentre un número en una matriz ordenada, pero el análisis es bastante complicado. En última instancia, el análisis funciona mostrando que el número de iteraciones es igual al número k tal que n 2 -k ≤ 2, para lo cual log log n es la solución correcta. Algunos algoritmos, como el algoritmo Cheriton-Tarjan MST , llegan a un tiempo de ejecución que involucra O (log log n) resolviendo un problema complejo de optimización restringida.
¡Espero que esto ayude!
Una forma de ver el factor de O (log log n) en la complejidad del tiempo es mediante la división, como se explica en la otra respuesta, pero hay otra forma de ver este factor, cuando queremos hacer un intercambio entre tiempo y espacio / tiempo. y aproximación / tiempo y dureza / ... de algoritmos y tenemos alguna iteración artificial en nuestro algoritmo.
Por ejemplo, SSSP (ruta más corta de fuente única) tiene un algoritmo O (n) en gráficos planos, pero antes de ese algoritmo complicado había un algoritmo mucho más fácil (pero aún bastante difícil) con tiempo de ejecución O (n log log n), el La base del algoritmo es la siguiente (solo una descripción muy aproximada, y me ofrecería omitir la comprensión de esta parte y leer la otra parte de la respuesta):
Pero mi punto es que aquí elegimos que la división sea de tamaño O (log n / (log log n)). Si elegimos otras divisiones como O (log n / (log log n) ^ 2) que puede correr más rápido y traer otro resultado. Quiero decir, en muchos casos (como en algoritmos de aproximación o algoritmos aleatorios, o algoritmos como SSSP como arriba), cuando iteramos sobre algo (subproblemas, posibles soluciones, ...), elegimos el número de iteración correspondiente al comercio de ese tenemos (tiempo / espacio / complejidad del algoritmo / factor constante del algoritmo, ...). Así que puede ser que veamos cosas más complicadas que "log log n" en algoritmos de trabajo reales.
fuente