5

Todo algoritmo com complexidade que envolva um "log", tem recursividade envolvida? Tipo: O(n log n). Se não, quando terá "log" em alguma complexidade?

6
  • Explique melhor isso aí.
    – Maniero
    11/05/2016 às 21:50
  • acho que esse exemplo não fez muito sentido a pergunta.
    – pmargreff
    12/05/2016 às 0:42
  • Geralmente os algoritmos que têm complexidade com log(n) é porque envolve busca binária (divide and conquer). Muitos que tem recursividade envolvem essa técnica. Mas não, existem algoritmos com log(n) que não são recursivos, por exemplo encontrar um elemento em um vetor ordenado. 13/05/2016 às 11:14
  • 1
    Olá @SérgioMucciaccia no seu caso você deu um exemplo de algo que poderia ser implementado de forma recursiva, acho que a ideia da pergunta é descobrir algo que não seja possível de fazer de forma recursiva e ainda sim tenha complexidade log(n) ...
    – pmargreff
    18/05/2016 às 10:45
  • Existe uma implementação de um algoritmo que tem log na complexidade e não tem recursividade envolvida. Logo a afirmativa como foi feita é falsa, pois nem todo algoritmo satisfaz obrigatoriamente essa condição. Bom, isso foi o que eu entendi da pergunta. Agora com a sua interpretação realmente, qualquer algoritmo com log envolvido pode ser implementado com recursividade, então a afirmativa seria verdadeira. Pra mim se pode ser implementado sem recursividade então não tem recursividade envolvida (pode ter mas não necessariamente tem). Mas ai já é questão da interpretação de cada um. 29/05/2016 às 15:31

1 Resposta 1

2

O que exatamente é dizer que temos algo com complexidade log n ?

Vamos dizer que você tenha uma árvore balanceada com 32 - 1 elementos.

Árvore com 4 níveis

Essa árvore tem 4 níveis, se você quiser adicionar um novo nível, vai praticamente dobrar seu tamanho (64 - 1 elementos) porém seu tempo de busca cresce a uma razão muito baixa comparada a isso (razão logarítmica), por que agora na pior das hipóteses ao invés de usarmos 4 passos para encontrar o resultado teremos que fazer 5 passos. Comparado com as outras razões de complexidade é um resultado muito bom (essa pergunta/resposta é uma boa referência), aqui você pode ter uma ideia da complexidade dos algoritmos mais populares.


Agora indo ao ponto da pergunta log(n)/log(i) é uma solução com relação à recorrência.

f(n) =  f(n/i) + c

Acontece toda vez que uma função que pode ser escrita recursivamente onde o tamanho do parametro é dividido por uma constante em cada iteração, como em:

funcao(entrada, n){
 //faça algo aqui
 retorne funcao(entrada, n/constante);
}

Então então dizemos que a complexidade θ(log(n)).

Exemplos:

  • Quando você busca em uma árvore balanceada: comece pela raiz, se o valor de n for gual retorne o nodo (constante), caso contrário se for menor vá para o lado esquerdo da árvore (tamanho/2), se for maior vá para o lado direito (tamanho/2).
  • Exponenciação: a^n: caso n = 1 então retorne a, caso contrário a^(n/2) (eleve a à metade de n) = b (tamanho n/2), multiplique b por b e volte ao inicio.

Traduzida de SO - en


Fonte 1 + Imagem

Fonte 2

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .