algorithm - principio - la complejidad de algoritmos

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

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

Reducir por una raíz cuadrada

Como se menciona en la respuesta a la pregunta vinculada, una forma común para que un algoritmo tenga una complejidad de tiempo O (log n) es que el algoritmo trabaje cortando 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 las iteraciones O (log n), porque después de hacer las 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 cual, 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 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 es el caso de 65,536 = 2 ¹⁶ .

Pero, si tomamos 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é es esto? Bueno, reescribamos esta secuencia en términos de poderes de dos:

√65,536 = √2 ¹⁶ = (2 ¹⁶ ) ^1/2 = 2 ⁸ = 256
√256 = √2 ⁸ = (2 ⁸ ) ^1/2 = 2 ⁴ = 16
√16 = √2 ⁴ = (2 ⁴ ) ^1/2 = 2 ² = 4
√4 = √2 ² = (2 ² ) ^1/2 = 2 ¹ = 2

Observe que seguimos la secuencia 2 ¹⁶ → 2 ⁸ → 2 ⁴ → 2 ² → 2 ¹ . En cada iteración, cortamos el exponente de la potencia de dos por la mitad. Eso es interesante, porque esto se conecta nuevamente con lo que ya sabemos: solo se puede dividir el número k en la mitad O (log k) veces antes de que caiga a cero.

Así que toma cualquier número ny escríbelo como n = 2 ^k . Cada vez que tomas la raíz cuadrada de n, reduces 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). Dado que n = 2 ^k , esto significa que k = log ₂ 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 ( árbol de vEB). Un vEB-tree 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 punteros √N, dividiendo el rango 0 ... N - 1 en rangos √N cada uno con un rango de enteros √N aproximadamente. Estos segmentos se subdividen cada uno internamente en segmentos √ (√ N), cada uno de los cuales contiene aproximadamente √ (√ N) elementos. Para atravesar el árbol, empiezas desde la raíz, determinas a qué cubo perteneces, luego continúas recursivamente en el subárbol apropiado. Debido a la forma en que está estructurado el árbol vEB, puede determinar en O (1) en qué subárbol descenderá, por lo que después de los pasos O (log log N) llegará al final del árbol. En consecuencia, las búsquedas en un árbol vEB solo toman tiempo O (log log N).

Otro ejemplo es el algoritmo de par de puntos más cercano a Hopcroft-Fortune . Este algoritmo intenta encontrar los dos puntos más cercanos en una colección de puntos 2D. Funciona al crear una grilla de cubos y distribuir los puntos en esos cubos. Si en algún punto del algoritmo se encuentra un cubo que tiene más de √N puntos, el algoritmo procesa recursivamente ese cubo. La profundidad máxima de la recursión es, por lo tanto, O (log log n), y utilizando un análisis del árbol de recursión se puede mostrar que cada capa en el árbol funciona 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

Existen otros algoritmos que logran tiempos de ejecución O (log log n) utilizando algoritmos como la búsqueda binaria en objetos de tamaño O (log n). Por ejemplo, la estructura de datos trie x-fast realiza una búsqueda binaria sobre las capas de un árbol de altura O (log U), por lo que el tiempo de ejecución para algunas de sus operaciones es O (log log U). El trie relacionado y-fast obtiene algunos de sus tiempos de ejecución O (log log U) manteniendo BST balanceados de nodos O (log U) cada uno, permitiendo que las búsquedas en esos árboles se ejecuten en el tiempo O (log log U). El árbol de tango y las estructuras de datos de árbol multipantallas 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 obtienen el tiempo de ejecución O (log log n) de otras maneras. La búsqueda de interpolación ha esperado el tiempo de ejecución O (log log n) para encontrar un número en una matriz ordenada, pero el análisis está bastante involucrado. 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 el cual log log n es la solución correcta. Algunos algoritmos, como el algoritmo MST Cheriton-Tarjan , llegan a un tiempo de ejecución que implica O (log log n) al resolver un complejo problema de optimización restringida.

¡Espero que esto ayude!

Esta pregunta anterior aborda algunos de los factores que pueden causar que un algoritmo tenga complejidad O (log n).

¿Qué podría hacer que un algoritmo tenga complejidad de tiempo O (log log n)?

Una forma de ver el factor de O (log log n) en la complejidad del tiempo es por división como las cosas explicadas en la otra respuesta, pero hay otra forma de ver este factor, cuando queremos hacer un intercambio de 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 (descripción muy aproximada, y ofrecería omitir la comprensión de esta parte y leer la otra parte de la respuesta):

divida el gráfico en las partes del tamaño O (log n / (log log n)) con alguna restricción.
Supongamos que cada una de las partes mencionadas es un nodo en el nuevo grafo G ''y luego calculamos SSSP para G'' en el tiempo O (| G ''| * log | G'' |) ==> aquí porque | G ''| = O (| G | * log log n / log n) podemos ver el factor (log log n).
Compute SSSP para cada parte: nuevamente porque tenemos O (| G ''|) parte y podemos calcular SSSP para todas las partes en el tiempo | n / logn | * | log n / log logn * log (logn / log log n).
actualizar pesos, esta parte se puede hacer en O (n). para más detalles, estas notas de clase son buenas.

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 ejecutarse más rápido y trae otro resultado. Es decir, en muchos casos (como en algoritmos de aproximación o algoritmos aleatorios, o algoritmos como SSSP como el anterior), 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, ...). Entonces podemos ver cosas más complicadas que "log log n" en algoritmos de trabajo real.