Exemplos notáveis ​​da ideia da raiz quadrada na análise de complexidade

Existem vários algoritmos e estruturas de dados que exploram a idéia de que obtém seu valor mínimo em k = \ sqrt n . Exemplos comuns incluem$\max \left\{k, n/k\right\}$$k=\sqrt n$

• algoritmo de passo gigante de baby-step para calcular logaritmo discreto em $O(\sqrt n)$ ,
• faixa ortogonal 2D estática contando em $O(\sqrt n)$ tempo e $O(n)$ memória,
• fila de prioridade com EXTRACT-MIN em $O(\sqrt[k] n)$ e DECREASE-KEY em $O(1)$ ,
• colorindo um gráfico de três cores com $O(\sqrt n)$ cores em tempo polinomial,

só para citar alguns.

Embora esses algoritmos geralmente sejam abaixo do ideal, eles são fáceis de entender pelos alunos e bons para mostrar rapidamente que limites ingênuos não são ótimos. Além disso, as estruturas de dados de idéia de raiz quadrada às vezes são mais práticas do que suas contrapartes baseadas em árvore binária por causa da facilidade de cache (sem considerar as técnicas que ignoram o cache). É por isso que dou bastante atenção a esse tópico enquanto ensino.

Estou interessado em exemplos mais distintos desse tipo. Então, eu estou procurando por quaisquer algoritmos (de preferência elegantes), estruturas de dados, protocolos de comunicação, etc., cuja análise se baseie na idéia da raiz quadrada. Seus assintóticos não precisam ser ótimos.

O artigo de Chazelle, Liu e Magen, Algoritmos Geométricos Sublineares (STOC 2003, SICOMP 2006), tem várias aplicações inteligentes do seguinte truque de amostragem aleatória. Variações do mesmo truque foram usadas anteriormente por Gärtner e Welzl [ DCG 2001 ], que citam a primeira edição do CLR (1990).

Suponha que recebamos uma lista circular ordenada de números, armazenados em um bloco de memória contíguo. Ou seja, temos duas matrizes e N e x t [ 1 .. n ] , em que$Key[1..n]$$Next[1..n]$

• armazena um conjunto de n números emordem arbitrária ;$Key[1..n]$$n$
• Se for o maior número do conjunto, então K e y [ N e x t [ i ] ] é o menor número do conjunto; caso contrário, K e y [ N e x t [ i ] ] é o menor número no conjunto que é maior que K e y [ i ] .$Key[i]$$Key[Next[i]]$$Key[Next[i]]$$Key[i]$

Então podemos encontrar o sucessor de um dado número em O ( $x$tempo esperado da seguinte forma:$O(\sqrt{n})$

• Escolha uma amostra aleatória de elementos da matrizKey. SejaKey[j]a maior amostra menor quex(ou a maior amostra, se todas as amostras forem maiores quex).$\sqrt{n}$$Key$$Key[j]$$x$$x$

• Siga os ponteiros de K e y [ j ] até vermos um número maior ou igual a x (depois de agrupar se todas as amostras forem maiores que x ).$Next$$Key[j]$$x$$x$

Uma aplicação relativamente simples do lema de Yao implica que o limite de tempo esperado é ideal. Qualquer algoritmo determinístico para esse problema requerΩ(n)tempo no pior caso.$O(\sqrt{n})$$\Omega(n)$

Existem triângulos em qualquer m -Edge gráfico e que eles podem ser encontrados em O ( m 3 / 2 ) do tempo. Existem muitas maneiras de fazer isso, mas acho que uma das primeiras é Itai e Rodeh (STOC 1977), que fornecem um algoritmo que passa por uma sequência de iterações de tempo linear, cada uma das quais remove uma floresta de abrangência do gráfico. Nas iterações iniciais, quando a floresta restante possui pelo menos n - k componentes, o algoritmo remove pelo menos k arestas por etapa e nas iterações finais, quando possui no máximo$O(m^{3/2})$$m$$O(m^{3/2})$$n-k$$k$ componentes, o grau máximo é k e diminui em pelo menos um em cada etapa. Portanto, o número total de iterações é no máximo m / k + k e a escolha da troca certa fornece o limite geral de O ( $n-k$$k$$m/k+k$no iterações eS(m 3 / 2 )sobre o tempo.$O(\sqrt m)$$O(m^{3/2})$