Ejemplos notables de la idea de raíz cuadrada en el análisis de complejidad

$\max \left\{k, n/k\right\}$$k=\sqrt n$

• Algoritmo de paso gigante de paso de bebé para calcular el logaritmo discreto en $O(\sqrt n)$ ,
• rango ortogonal 2D estático que cuenta en tiempo $O(\sqrt n)$ y memoria $O(n)$ ,
• cola prioritaria con EXTRACT-MIN en $O(\sqrt[k] n)$ y DECREASE-KEY en $O(1)$ ,
• colorear un gráfico de 3 colores con colores $O(\sqrt n)$ en tiempo polinómico,

Sólo para nombrar unos pocos.

Si bien estos algoritmos a menudo son subóptimos, son fáciles de entender por los estudiantes y buenos para mostrar rápidamente que los límites ingenuos no son óptimos. Además, las estructuras de datos de idea de raíz cuadrada a veces son más prácticas que sus contrapartes basadas en árboles binarios debido a la facilidad de almacenamiento en caché (sin considerar las técnicas ajenas al caché). Es por eso que presto un poco de atención a este tema mientras doy clases.

Estoy interesado en ejemplos más distintivos de este tipo. Así que estoy buscando algoritmos (preferiblemente elegantes), estructuras de datos, protocolos de comunicación, etc. cuyo análisis se base en la idea de raíz cuadrada. Sus asintóticos no necesitan ser óptimos.

El trabajo de Algoritmos geométricos sublineales de Chazelle, Liu y Magen (STOC 2003, SICOMP 2006) tiene varias aplicaciones inteligentes del siguiente truco de muestreo aleatorio. Las variaciones del mismo truco fueron utilizadas previamente por Gärtner y Welzl [ DCG 2001 ], quienes citan la primera edición de CLR (1990).

Supongamos que se nos da una lista ordenada de números circulares vinculados, almacenados en un bloque contiguo de memoria. Es decir, tenemos dos matrices y N e x t [ 1 .. n ] , donde$Key[1..n]$$Next[1..n]$

• almacena un conjunto de n números enorden arbitrario ;$Key[1..n]$$n$
• Si es el número más grande del conjunto, entonces K e y [ N e x t [ i ] ] es el número más pequeño del conjunto; de lo contrario, K e y [ N e x t [ i ] ] es el número más pequeño en el conjunto que es mayor que K e y [ i ] .$Key[i]$$Key[Next[i]]$$Key[Next[i]]$$Key[i]$

Entonces podemos encontrar el sucesor de un número dado en O ( $x$tiempo esperado de la siguiente manera:$O(\sqrt{n})$

• Elija una muestra aleatoria de elementos de la matrizKey. SeaKey[j]la muestra más grande que sea menor quex(o la muestra más grande, si todas las muestras son mayores quex).$\sqrt{n}$$Key$$Key[j]$$x$$x$

• Siga los punteros de K e y [ j ] hasta que veamos un número mayor o igual a x (después de ajustar si todas las muestras eran mayores que x ).$Next$$Key[j]$$x$$x$

Una aplicación relativamente simple del lema de Yao implica que el límite de tiempo esperado es óptimo. Cualquier algoritmo determinista para este problema requiere un tiempoΩ(n)en el peor de los casos.$O(\sqrt{n})$$\Omega(n)$

Hay triángulos en cualquier m -Edge gráfico y que se pueden encontrar en O ( m 3 / 2 ) tiempo. Hay muchas formas de hacer esto, pero creo que una de las primeras es Itai y Rodeh (STOC 1977) que proporcionan un algoritmo que pasa por una secuencia de iteraciones de tiempo lineal, cada una de las cuales elimina un bosque que se extiende del gráfico. En las primeras iteraciones, cuando el bosque restante tiene al menos n - k componentes, el algoritmo elimina al menos$O(m^{3/2})$$m$$O(m^{3/2})$$n-k$ bordes por paso, y en las últimas iteraciones cuando tiene como máximo$k$ componentes, el grado máximo es k y se reduce en al menos uno en cada paso. Entonces, el número total de iteraciones es como máximo m / k + k y elegir la compensación correcta da el límite general de O ( $n-k$$k$$m/k+k$en iteraciones yO(m 3 / 2 )en el tiempo.$O(\sqrt m)$$O(m^{3/2})$