Complexidade do algoritmo recursivo de Fibonacci

13

Usando o seguinte algoritmo recursivo de Fibonacci:

def fib(n):
   if n==0:
      return 0
   elif n==1
      return 1
   return (fib(n-1)+fib(n-2))

Se eu inserir o número 5 para encontrar fib (5), sei que isso produzirá 5, mas como examino a complexidade desse algoritmo? Como calculo as etapas envolvidas?

palhaço
fonte
Eu estava procurando o mesmo, e me deparei com este vídeo da MyCodeSchool que recomendo verificar isso.
precisa saber é

Respostas:

23

Na maioria das vezes, você pode representar os algoritmos recursivos usando equações recursivas. Nesse caso, a equação recursiva para esse algoritmo é . Em seguida, você pode encontrar a forma fechada da equação usando o método de substituição ou o método de expansão (ou qualquer outro método usado para resolver recorrências). Nesse caso, você obtém T ( n ) = Θ ( ϕ n ) , onde ϕT(n)=T(n-1)+T(n-2)+Θ(1)T(n)=Θ(ϕn)ϕé a proporção áurea ( )ϕ=(1+5)2

Se você quiser descobrir mais sobre como resolver recorrências, recomendo fortemente que você leia o capítulo 4 da Introdução aos algoritmos .

ees_cu
fonte
0

como alternativa às relações de recorrência / análise matemática (mas não um substituto ), um simples exercício empírico, aparentemente não ensinado com muita frequência nas aulas, mas muito informativo, é contar o número de execuções da função e, em seguida, representar graficamente a contagem para um intervalo de pequenas n entradas e, em seguida, curva ajustam-se ao resultado. Os resultados geralmente correspondem à abordagem matemática teórica.

um bom material de apoio para este exercício pode ser encontrado no capítulo on-line gratuito 3, tempo de execução dos algoritmos / Foundations of Computer Science , Ullman

vzn
fonte
1) A plotagem não substitui a análise formal. É facilmente enganado. 2) Acho que você está deturpando a fonte que cita. Eles mencionam plotagem, mas não como uma maneira de determinar a "complexidade". 3) FWIW, eu discordo da abordagem e é usada como Ullman a apresenta, mas isso não é culpa sua.
Raphael
1
a resposta começa basicamente com o seu aviso, dizendo que a plotagem não substitui a análise matemática . plotar é um método científico e dizer / observar que às vezes é enganado é aprender sobre / evocar aspectos estatísticos dos dados, que é outro aspecto principal da análise científica . acho que dizer que é "enganado facilmente" é bastante dramático, há casos "patológicos" em que falha, mas geralmente são "inventados" ... a questão era examinar a complexidade do algoritmo e a análise empírica é um aspecto-chave / ângulo sobre isso, e obviamente não o único ângulo etc ...
vzn
0

O resultado de fib (n) é a soma de todas as chamadas recursivas que retornaram 1. Portanto, existem exatamente chamadas recursivas de fib (n) avaliando fib (1). Portanto, o tempo de execução é Ω (fib (n)); você precisaria mostrar que as chamadas retornando 0 e as outras chamadas recursivas não contribuem significativamente para isso.

O mesmo raciocínio se aplica a qualquer função definida recursivamente que retorne 1 ou 0 ou o resultado de outra chamada recursiva.

gnasher729
fonte
Ω
Sinta-se livre para editar a resposta, se você se sentir bem com isso.
gnasher729
0

Um limite inferior é intuitivo: T(n)=T(n-1)+T(n-2) T(n)>2T(n-2) Desde a T(n-1)>T(n-2) Conseqüentemente T(n)=Ω(cn)

wabbit
fonte