O que faria com que um algoritmo tivesse complexidade O (log log n)?

Essa questão anterior aborda alguns dos fatores que podem fazer com que um algoritmo tenha complexidade O (log n).

O que faria com que um algoritmo tivesse complexidade de tempo O (log log n)?

Os termos do (log log n) podem aparecer em vários locais diferentes, mas normalmente há duas rotas principais que chegarão a esse tempo de execução.

Encolhendo por uma raiz quadrada

Como mencionado na resposta à pergunta vinculada, uma maneira comum para um algoritmo ter complexidade de tempo O (log n) é que esse algoritmo funcione cortando repetidamente o tamanho da input por algum fator constante em cada iteração. Se este for o caso, o algoritmo deve terminar após as iterações O (log n), porque depois de fazer divisões O (log n) por uma constante, o algoritmo deve reduzir o tamanho do problema para 0 ou 1. É por isso, por exemplo , a pesquisa binária tem complexidade O (log n).

Curiosamente, há uma maneira semelhante de diminuir o tamanho de um problema que produz tempos de execução na forma O (log log n). Em vez de dividir a input pela metade em cada camada, o que acontece se tomarmos a raiz quadrada do tamanho em cada camada?

Por exemplo, vamos pegar o número 65.536. Quantas vezes temos que dividir isso por 2 até chegarmos a 1? Se fizermos isso, conseguiremos

  • 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

Esse processo leva 16 etapas, e também é o caso que 65.536 = 2 16 .

Mas, se pegarmos a raiz quadrada em cada nível, chegaremos

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

Observe que são necessários apenas quatro passos para chegar ao 2. Por que isso acontece? Bem, vamos rewrite esta sequência em termos de poderes de dois:

  • ,565,536 = 162 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 a sequência 2 16 → 2 8 → 2 4 → 2 2 → 2 1 . Em cada iteração, cortamos o expoente do poder de dois pela metade. Isso é interessante, porque isso se conecta ao que já sabemos – você só pode dividir o número k ao meio O (log k) vezes antes de cair para zero.

Então pegue qualquer número n e escreva como n = 2 k . Cada vez que você pega a raiz quadrada de n, você reduz à metade o expoente nessa equação. Portanto, pode haver apenas O (log k) raízes quadradas aplicadas antes de k cair para 1 ou menor (caso em que n cai para 2 ou menos). Como n = 2 k , isso significa que k = log 2 n e, portanto, o número de raízes quadradas tomadas é O (log k) = O (log log n). Portanto, se houver um algoritmo que trabalhe reduzindo repetidamente o problema para um subproblema de tamanho que seja a raiz quadrada do tamanho original do problema, esse algoritmo terminará após as etapas O (log log n).

Um exemplo real disso é a estrutura de dados da tree van Emde Boas (vEB-tree). Uma vEB-tree é uma estrutura de dados especializada para armazenar números inteiros no intervalo 0 … N – 1. Funciona da seguinte maneira: o nó raiz da tree possui √N pointers, dividindo o intervalo 0 … N – 1 em bucketN baldes, cada um segurando um intervalo de aproximadamente integN inteiros. Esses baldes são então subdivididos internamente em baldes √ (√ N), cada um com aproximadamente √ (√ N) elementos. Para percorrer a tree, você começa na raiz, determina a qual bucket pertence e depois recursivamente continua na subtree apropriada. Devido ao modo como a vEB-tree está estruturada, você pode determinar em O (1) a hora em que a subtree deve descer, e assim, após as etapas O (log log N), você alcançará a parte inferior da tree. Assim, as pesquisas em uma tree vEB levam apenas tempo O (log log N).

Outro exemplo é o algoritmo de pontos mais próximo do Hopcroft-Fortune . Este algoritmo tenta encontrar os dois pontos mais próximos em uma coleção de pontos 2D. Ele funciona criando uma grade de buckets e distribuindo os pontos nesses buckets. Se em algum ponto do algoritmo for encontrado um bucket com mais de √N pontos, o algoritmo processará recursivamente esse bucket. A profundidade máxima da recursion é, portanto, O (log log n), e usando uma análise da tree de recursion pode ser mostrado que cada camada na tree faz O (n) funcionar. Portanto, o tempo de execução total do algoritmo é O (n log log n).

O (log n) Algoritmos em pequenas inputs

Existem alguns outros algoritmos que atingem tempos de execução de O (log log n) usando algoritmos como busca binária em objects de tamanho O (log n). Por exemplo, a estrutura de dados x-fast trie executa uma pesquisa binária sobre as camadas na tree de altura O (log U), portanto, o tempo de execução de algumas de suas operações é O (log log U). O y-fast trie relacionado obtém alguns de seus tempos de execução do O (log log U) mantendo BSTs balanceados de nós O (log U) cada, permitindo que as pesquisas nessas trees sejam executadas no tempo O (log log U). A tree de tango e as estruturas de dados da tree multiesplays relacionadas acabam com um termo O (log log n) em suas análises porque elas mantêm trees que contêm itens O (log n) cada.

Outros exemplos

Outros algoritmos atingem o tempo de execução O (log log n) de outras maneiras. A pesquisa de interpolação esperou que o tempo de execução O (log log n) localizasse um número em uma matriz classificada, mas a análise está razoavelmente envolvida. Por fim, a análise funciona mostrando que o número de iterações é igual ao número k tal que n 2 -k ≤ 2, para o qual log log n é a solução correta. Alguns algoritmos, como o algoritmo Cheriton-Tarjan MST , chegam a um tempo de execução envolvendo O (log log n) resolvendo um problema complexo de otimização restrita.

Espero que isto ajude!

Uma maneira de ver o fator O (log log n) na complexidade do tempo é por divisão como o material explicado na outra resposta, mas existe outra maneira de ver esse fator, quando queremos fazer uma troca entre tempo e espaço / tempo e aproximação / tempo e dureza / … de algoritmos e temos alguma iteração artificial em nosso algoritmo.

Por exemplo, SSSP (Single source shortest path) possui um algoritmo O (n) em charts planares, mas antes desse algoritmo complicado havia um algoritmo muito mais fácil (mas ainda bastante difícil) com tempo de execução O (n log log n), o A base do algoritmo é a seguinte (apenas uma descrição muito aproximada, e eu me ofereço para ignorar essa parte e ler a outra parte da resposta):

  1. divida o gráfico nas partes do tamanho O (log n / (log log n)) com alguma restrição.
  2. Suponha que cada parte mencionada seja nó no novo grafo G ‘e então calcule SSSP para G’ no tempo O (| G ‘| * log | G’ |) ==> aqui porque | G ‘| = O (| G | * log log n / log n) podemos ver o fator (log log n).
  3. Calcule o SSSP para cada parte: novamente, porque temos a parte O (| G ‘|) e podemos calcular o SSSP para todas as partes no tempo | n / logn | * | log n / log logn * log (log n / log log n).
  4. atualizar pesos, esta parte pode ser feita em O (n). Para mais detalhes, as notas desta aula são boas.

Mas meu ponto é, aqui nós escolhemos a divisão para ser de tamanho O (log n / (log log n)). Se escolhermos outras divisões como O (log n / (log log n) ^ 2), que pode ser executado mais rapidamente e traz outro resultado. Quero dizer, em muitos casos (como em algoritmos de aproximação ou algoritmos randoms, ou algoritmos como SSSP como acima), quando iteramos sobre algo (subproblemas, soluções possíveis, …), escolhemos o número de iteração correspondente ao comércio daquele temos (tempo / espaço / complexidade de algoritmo / fator constante do algoritmo, …). Assim, podemos ver coisas mais complicadas do que “log log n” em algoritmos reais de trabalho.