Amarengo

Articles and news

¿Qué causaría que un algoritmo tuviera complejidad O(log log n)?

Los términos O(log log n) pueden aparecer en una variedad de lugares diferentes, pero generalmente hay dos rutas principales que llegarán a este tiempo de ejecución.

Reducir por 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 iteraciones O(log n), porque después de hacer divisiones O(log n) por una constante, el algoritmo debe reducir el tamaño del problema a 0 o 1. Esta es la razón por la que, por ejemplo, la búsqueda binaria tiene complejidad O(log n).

Curiosamente, hay 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 por la mitad en cada capa, ¿qué sucede si tomamos 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 llegar a 1? Si hacemos esto, tenemos

  • 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 tiene 16 pasos, y es también el caso de que 65.536 = 216.

Pero, si tomamos la raíz cuadrada en cada nivel, tenemos

  • √65,536 = 256
  • √256 = 16
  • √16 = 4
  • √4 = 2

Observe que sólo lleva cuatro pasos para obtener todo el camino hacia abajo a 2. ¿Por qué es esto?

En primer lugar, una explicación intuitiva. Cuántos dígitos hay en los números n y √n? Hay aproximadamente registro de n dígitos en el número n, y aproximadamente log (√n) = log (n1/2) = (1/2) log n dígitos en √n. Esto significa que, cada vez que tomas una raíz cuadrada, estás reduciendo aproximadamente a la mitad el número de dígitos en el número. Debido a que solo puede reducir a la mitad una cantidad k O(log k) veces antes de que descienda 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 una constante (digamos, 2).

Ahora, hagamos algunas matemáticas para hacer esto riguroso. Le’ts reescribe la secuencia anterior en términos de potencias de dos:

  • √65,536 = √216 = (216)1/2 = 28 = 256
  • √256 = √28 = (28)1/2 = 24 = 16
  • √16 = √24 = (24)1/2 = 22 = 4
  • √4 = √22 = (22)1/2 = 21 = 2

Observe que hemos seguido la secuencia 216 → 28 → 24 → 22 → 21. 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 se puede dividir el número k por la mitad O(log k) veces antes de que caiga a cero.

Así que tome cualquier número n y escríbalo como n = 2k. Cada vez que se toma la raíz cuadrada de n, se reduce a la mitad el exponente en esta ecuación. Por lo tanto, solo puede haber raíces cuadradas de O(log k) aplicadas antes de que k caiga a 1 o inferior (en cuyo caso n caiga a 2 o inferior). Dado que n = 2k, esto significa que k = log2 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 los pasos O(log log n).

Un ejemplo real de esto es la estructura de datos del árbol de van Emde Boas (vEB-tree). Un árbol vEB es una estructura de datos especializada para almacenar enteros en el rango 0 … N-1. Funciona de la siguiente manera: el nodo raíz del árbol tiene √N punteros, dividiendo el rango 0 … N – 1 en cubos √N, cada uno con un rango aproximado de enteros √N. Estos cubos se subdividen internamente en cubos √ (√ N), cada uno de los cuales contiene aproximadamente elementos √(√ N). Para recorrer el árbol, comience por la raíz, determine a qué cubo pertenece y, a continuación, continúe recursivamente en el subárbol apropiado. Debido a la forma en que está estructurado el árbol vEB, puede determinar en O(1) tiempo en qué subárbol descender, y así después de pasos de O(log log N) 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 de pares de puntos más cercanos 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 algún punto del algoritmo se encuentra un bucket que tiene más de √N puntos, el algoritmo procesa recursivamente ese bucket. Por lo tanto, la profundidad máxima de la recursión es O(log log n), y utilizando un análisis del árbol de recursión se puede mostrar que cada capa del árbol hace un trabajo de O(n). Por lo tanto, el tiempo de ejecución total del algoritmo es O(n log log n).

Algoritmos O(log n) en entradas pequeñas

Hay algunos otros algoritmos que logran tiempos de ejecución O(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 at tree of height 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) manteniendo BST equilibrados de nodos O(log U) cada uno, permitiendo que las búsquedas en esos árboles se ejecuten en tiempo O(log log U). El árbol tango y las estructuras de datos de árbol multisplay relacionadas terminan con un término O (log log n) en sus análisis porque mantienen árboles que contienen elementos O(log n) cada uno.

Otros ejemplos

Otros algoritmos logran el tiempo de ejecución O (log log n) de otras maneras. La búsqueda por 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 n2-k ≤ 2, para el cual log log n es la solución correcta. Algunos algoritmos, como el algoritmo MST de Cheriton-Tarjan, llegan a un tiempo de ejecución que involucra O(log log n) al resolver un problema complejo de optimización restringida.

Espero que esto ayude!

Deja una respuesta

Tu dirección de correo electrónico no será publicada.