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

Esta 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 O (log log n) podem aparecer em uma variedade de lugares diferentes, mas normalmente há duas rotas principais que chegarão neste tempo de execução.

Reduzindo por uma raiz quadrada

Conforme mencionado na resposta à pergunta vinculada, uma maneira comum de um algoritmo ter complexidade de tempo O (log n) é que esse algoritmo funcione cortando repetidamente o tamanho da entrada por algum fator constante em cada iteração. Se for esse o caso, o algoritmo deve terminar após O (log n) iterações, porque depois de fazer O (log n) divisões 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, existe uma maneira semelhante de reduzir o tamanho de um problema que produz tempos de execução da forma O (log log n). Em vez de dividir a entrada pela metade em cada camada, o que acontece se tirarmos a raiz quadrada do tamanho de 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, teremos

• 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 de 65.536 = 2 ¹⁶ .

Mas, se tomarmos a raiz quadrada em cada nível, obtemos

• √65.536 = 256
• √256 = 16
• √16 = 4
• √4 = 2

Observe que são necessários apenas quatro passos para descer até 2. Por que isso?

Primeiro, uma explicação intuitiva. Quantos dígitos existem nos números ne √n? Existem aproximadamente log n dígitos no número n, e aproximadamente log (√n) = log (n ^1/2 ) = (1/2) log n dígitos em √n. Isso significa que, cada vez que você obtém uma raiz quadrada, está reduzindo aproximadamente pela metade o número de dígitos do número. Porque você só pode reduzir pela metade uma quantidade k O (log k) vezes antes de cair para uma constante (digamos, 2), isso significa que você só pode tirar raízes quadradas O (log log n) vezes antes de reduzir o número a alguma constante (digamos, 2).

Agora, vamos fazer algumas contas para tornar isso rigoroso. Vamos reescrever a sequência acima em termos de potências de dois:

• √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 a sequência 2 ¹⁶ → 2 ⁸ → 2 ⁴ → 2 ² → 2 ¹ . Em cada iteração, cortamos o expoente da potência de dois pela metade. Isso é interessante, porque isso se conecta ao que já sabemos - você só pode dividir o número k pela metade O (log k) vezes antes que ele caia para zero.

Portanto, pegue qualquer número ne escreva n = 2 ^k . Cada vez que você tira a raiz quadrada de n, você divide o expoente nesta equação. Portanto, pode haver apenas O (log k) raízes quadradas aplicadas antes que k caia para 1 ou menos (nesse caso, n cai para 2 ou menos). Como n = 2 ^k , isso significa que k = log ₂ n e, portanto, o número de raízes quadradas obtidas é O (log k) = O (log log n). Portanto, se houver um algoritmo que funciona reduzindo repetidamente o problema a um subproblema de tamanho que é a raiz quadrada do tamanho do problema original, esse algoritmo terminará após O (log log n) etapas.

Um exemplo do mundo real disso é a árvore van Emde Boas(árvore vEB) estrutura de dados. Uma árvore vEB é uma estrutura de dados especializada para armazenar inteiros no intervalo 0 ... N - 1. Funciona da seguinte maneira: o nó raiz da árvore possui √N ponteiros, dividindo o intervalo 0 ... N - 1 em √N intervalos, cada um contendo um intervalo de aproximadamente √N inteiros. Esses baldes são então subdivididos internamente em √ (√ N) baldes, cada um deles contendo aproximadamente √ (√ N) elementos. Para percorrer a árvore, você começa na raiz, determina a qual intervalo você pertence e continua recursivamente na subárvore apropriada. Devido à forma como a árvore vEB está estruturada, você pode determinar em tempo O (1) em qual subárvore descer, e assim após O (log log N) passos você alcançará a parte inferior da árvore. Conseqüentemente, as pesquisas em uma árvore vEB demoram apenas O (log log N).

Outro exemplo é o algoritmo de par de pontos mais próximo de 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 baldes e distribuindo os pontos nesses baldes. Se, em qualquer ponto do algoritmo, for encontrado um depósito com mais de √N pontos, o algoritmo processa recursivamente esse depósito. A profundidade máxima da recursão é, portanto, O (log log n), e usando uma análise da árvore de recursão pode ser mostrado que cada camada na árvore faz O (n) trabalho. Portanto, o tempo de execução total do algoritmo é O (n log log n).

Algoritmos O (log n) em pequenas entradas

Existem alguns outros algoritmos que alcançam tempos de execução O (log log n) usando algoritmos como pesquisa binária em objetos de tamanho O (log n). Por exemplo, a estrutura de dados do trie rápido x executa uma pesquisa binária nas camadas de uma árvore de altura O (log U), de modo que o tempo de execução para algumas de suas operações é O (log log U). O teste y-fast relacionado obtém alguns de seus tempos de execução O (log log U) mantendo BSTs equilibrados de nós O (log U) cada, permitindo que as pesquisas nessas árvores sejam executadas em tempo O (log log U). A árvore do tango e as estruturas de dados da árvore multisplay relacionadas acabam com um termo O (log log n) em suas análises porque mantêm árvores que contêm itens O (log n) cada.

Outros Exemplos

Outros algoritmos alcançam o tempo de execução O (log log n) de outras maneiras. A pesquisa de interpolação esperava que o tempo de execução O (log log n) encontrasse um número em uma matriz classificada, mas a análise é bastante complexa. Em última análise, 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 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 de O (log log n) na complexidade do tempo é por divisão como as coisas explicadas na outra resposta, mas há outra maneira de ver este 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 (caminho mais curto de fonte única) tem um algoritmo O (n) em gráficos 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 ofereceria pular a compreensão desta parte e ler a outra parte da resposta):

1. divida o gráfico em partes de tamanho O (log n / (log log n)) com alguma restrição.
2. Suponha que cada parte mencionada seja um nó no novo grafo G ', 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 SSSP para cada parte: novamente porque temos a parte O (| G '|) e podemos calcular SSSP para todas as partes no tempo | n / logn | * | log n / log logn * log (logn / log log n).
4. pesos de atualização, esta parte pode ser feita em O (n). para mais detalhes, as notas desta aula são boas.

Mas meu ponto é, aqui escolhemos que a divisão seja 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 rápido e traz outro resultado. Quero dizer, em muitos casos (como em algoritmos de aproximação ou algoritmos aleatórios, 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 do algoritmo / fator constante do algoritmo, ...). Portanto, podemos ver coisas mais complicadas do que "log log n" em algoritmos de trabalho reais.