Amarengo

Articles and news

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

o(log log n) termos podem aparecer em uma variedade de lugares diferentes, mas normalmente existem duas rotas principais que chegarão a este tempo de execução.

encolhendo 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 as iterações o(log n), porque depois de fazer as divisões O(log n) por uma constante, o algoritmo deve reduzir o tamanho do problema para 0 ou 1. É por isso que, por exemplo, a pesquisa binária tem complexidade O(log n).

curiosamente, existe uma maneira semelhante de diminuir o tamanho de um problema que produz tempos de execução do formulário O(log log n). Em vez de dividir a entrada ao meio 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, nós temos

  • 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 de 16 passos, e é também o caso que 65.536 = 216.

Mas, se tomamos a raiz quadrada em cada nível, temos

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

Observe que ele só tem quatro passos para obter toda a maneira para baixo a 2. Porquê?

primeiro, uma explicação intuitiva. Quantos dígitos existem nos números n e √n? Existem aproximadamente log n dígitos no número n, e aproximadamente log (√n) = log (n1/2) = (1/2) log n dígitos em √n. Isso significa que, cada vez que você toma uma raiz quadrada, você está reduzindo pela metade o número de dígitos no número. Como 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 tomar raízes quadradas o(log log n) vezes antes de reduzir o número para alguma constante (digamos, 2).

agora, vamos fazer algumas contas para tornar isso rigoroso. Le’TS reescreve a sequência acima em termos de poderes de dois:

  • √65,536 = √216 = (216)1/2 = 28 = 256
  • √256 = √28 = (28)1/2 = 24 = 16
  • √16 = √24 = (24)1/2 = 22 = 4
  • √4 = √22 = (22)1/2 = 21 = 2

Observe que seguimos a sequência 216 → 28 → 24 → 22 → 21. Em cada iteração, cortamos o expoente da potência de dois ao meio. Isso é interessante, porque isso se conecta de volta 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 = 2k. Cada vez que você toma a raiz quadrada de n, você reduz pela metade o expoente nesta equação. Portanto, pode haver apenas raízes quadradas O (log k) aplicadas antes que k caia para 1 ou inferior (caso em que n cai para 2 ou inferior). Desde n = 2k, isso significa que k = log2 n e, portanto, o número de raízes quadradas tomadas é O(log k) = o(log log n). Portanto, se houver um algoritmo que funcione reduzindo repetidamente o problema a um subproblema de tamanho que é a raiz quadrada do tamanho do problema original, esse algoritmo terminará após as etapas o(log log n).

um exemplo do mundo real disso é a estrutura de dados da van emde Boas tree (VEB-tree). Uma árvore vEB é uma estrutura de dados especializada para armazenar inteiros no intervalo 0 … N-1. Funciona da seguinte forma: o nó raiz da árvore tem √n ponteiros, dividindo o intervalo 0 … N-1 em √n baldes cada um segurando um intervalo de aproximadamente √n inteiros. Esses baldes são então subdivididos internamente em √ (√N) baldes, cada um dos quais contém aproximadamente √ (√N) elementos. Para atravessar a árvore, você começa na raiz, determina a qual balde você pertence e, em seguida, continua recursivamente na subárvore apropriada. Devido à forma como a árvore vEB é estruturada, você pode determinar em O(1) Tempo em que subárvore descer, e assim, após o(log log n) etapas, você alcançará o fundo da árvore. Assim, as pesquisas em uma árvore vEB levam tempo apenas O (log log N).

outro exemplo é o algoritmo Hopcroft-Fortune closest pair of points. 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 algum ponto do algoritmo for encontrado um bucket que tenha mais de √N pontos nele, o algoritmo processa recursivamente esse bucket. 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 funciona o(n). Portanto, o tempo de execução total do algoritmo é O(n log log n).

o(log n) algoritmos em pequenas entradas

existem alguns outros algoritmos que alcançam o (log log n) runtimes usando algoritmos como busca binária em objetos de tamanho O(log n). Por exemplo, a estrutura de dados x-fast trie executa uma pesquisa binária sobre as camadas de at tree of height o(log U), portanto, o tempo de execução de algumas de suas operações é o(log log u). O Trie 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 no tempo O(log log U). A árvore tango e as estruturas de dados de á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 runtime o (log log n) de outras maneiras. A pesquisa de interpolação espera que runtime O (log log n) encontre um número em uma matriz classificada, mas a análise está bastante envolvida. Em última análise, a análise funciona mostrando que o número de iterações é igual ao número k de tal forma que n2-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 isso ajude!

Deixe uma resposta

O seu endereço de email não será publicado.