Complexidade computacional da sequência de Fibonacci

330

Entendo a notação Big-O, mas não sei como calculá-la para muitas funções. Em particular, tenho tentado descobrir a complexidade computacional da versão ingênua da sequência de Fibonacci:

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Qual é a complexidade computacional da sequência de Fibonacci e como é calculada?

Julieta
fonte
3
Veja a seção do formulário da matriz aqui: en.wikipedia.org/wiki/Fibonacci_number . fazendo essa matriz ^ n (de maneira inteligente), você pode calcular Fib (n) em O (lg n). O truque está em fazer a função de poder. Há uma palestra muito boa no iTunesU sobre esse problema exato e como resolver em O (lg n). O curso é de introdução aos algoritmos do MIT palestra 3 (sua absolutley livre para verificá-la se você estiver interessado)
Aly
1
Nenhum dos comentários acima aborda a questão, que é sobre a complexidade computacional da versão ingênua (no código publicado), não sobre versões mais inteligentes, como forma de matriz ou computação não recursiva.
Josh Milthorpe
Um vídeo muito bom aqui que fala sobre a complexidade do limite inferior (2 ^ n / 2) e a complexidade do limite superior (2 ^ n) da implementação recursiva.
RBT
1
Uma consulta de observação lateral: a implementação ingênua da série Fibonacci deve ser iterativa ou recursiva ?
RBT

Respostas:

374

Você modela a função de tempo para calcular Fib(n)como soma do tempo para calcular Fib(n-1)mais o tempo para calcular Fib(n-2)mais o tempo para adicioná-los ( O(1)). Isso pressupõe que avaliações repetidas do mesmo Fib(n)levam o mesmo tempo - ou seja, nenhuma memorização é usada.

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

Você resolve essa relação de recorrência (usando funções geradoras, por exemplo) e termina com a resposta.

Como alternativa, você pode desenhar a árvore de recursão, que terá profundidade ne descobrirá intuitivamente que essa função é assintoticamente . Você pode provar sua conjectura por indução.O(2n)

Base: n = 1é óbvio

Suponha , portantoT(n-1) = O(2n-1)

T(n) = T(n-1) + T(n-2) + O(1) que é igual a

T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)

No entanto, como observado em um comentário, esse não é o limite. Um fato interessante sobre essa função é que T (n) é assintoticamente o mesmo que o valor de, Fib(n)uma vez que ambos são definidos como

f(n) = f(n-1) + f(n-2).

As folhas da árvore de recursão sempre retornam 1. O valor de Fib(n)é a soma de todos os valores retornados pelas folhas na árvore de recursão, que é igual à contagem de folhas. Como cada folha levará O (1) para calcular, T(n)é igual a Fib(n) x O(1). Consequentemente, o limite restrito para essa função é a própria sequência de Fibonacci (~ ). Você pode descobrir esse limite usando funções geradoras, como eu mencionei acima.θ(1.6n)

Mehrdad Afshari
fonte
29
Também prova por indução. Agradável. +1
Andrew Rollings
Embora o limite não seja apertado.
Captain Segfault
@ Capitão Segfault: Sim. Eu esclareci a resposta. Você conseguiria o limite usando o método GF como eu havia escrito acima.
Mehrdad Afshari
Transforme sua StackOverflowException como uma piada. O tempo exponencial é facilmente percebido com valores bastante pequenos para n.
David Rodríguez - dribeas
1
"Como alternativa, você pode desenhar a árvore de recursão, que terá profundidade n e intuitivamente descobrirá que essa função é assintoticamente O (2n)." - Isso é completamente falso. A complexidade do tempo é O (golden_ratio ^ n). Nunca chega perto de O (2 ^ n). Se você pudesse alcançar o infinito, chegaria perto de O (golden_ratio ^ n). Isso é o que é uma assíntota, a distância entre as duas linhas deve se aproximar de zero.
bob
133

Apenas pergunte a si mesmo quantas instruções precisam ser executadas para F(n)serem concluídas.

Pois F(1), a resposta é 1(a primeira parte do condicional).

Pois F(n), a resposta é F(n-1) + F(n-2).

Então, qual função satisfaz essas regras? Tente n (a> 1):

a n == a (n-1) + a (n-2)

Divida por a (n-2) :

a 2 == a + 1

Resolver ae obter (1+sqrt(5))/2 = 1.6180339887, também conhecido como a proporção áurea .

Portanto, leva tempo exponencial.

Jason Cohen
fonte
8
Prova por indução. Agradável. +1
Andrew Rollings
2
30 votos para uma resposta errada? :-) Segue-se que 1 = F (1) = (1 + sqrt (5)) / 2? E a outra solução (1 sqrt (5)) / 2?
Carsten S
1
Não, 1 não é igual a 1 + 1. A função que satisfaz essas regras é mencionada na pergunta.
precisa saber é o seguinte
6
A resposta não está errada. Está certo de forma assintomática. A outra solução é negativa, portanto não faz sentido fisicamente.
Da Teng
10
Alguém pode explicar como a ^ n == a ^ (n-1) + a ^ (n-2) satisfaz essas regras? Como é satisfeito exatamente, por favor, seja específico.
Frank
33

Eu concordo com pgaur e rickerbh, a complexidade recursiva-fibonacci é O (2 ^ n).

Cheguei à mesma conclusão de uma maneira bastante simplista, mas acredito que o raciocínio ainda é válido.

Primeiro, trata-se de descobrir quantas vezes a função fibonacci recursiva (F () de agora em diante) é chamada ao calcular o número de N-ésimo fibonacci. Se for chamado uma vez por número na sequência de 0 a n, teremos O (n); se for chamado n vezes para cada número, obteremos O (n * n) ou O (n ^ 2), e assim por diante.

Portanto, quando F () é chamado para um número n, o número de vezes que F () é chamado para um determinado número entre 0 e n-1 cresce à medida que nos aproximamos de 0.

Como primeira impressão, parece-me que, se colocarmos de maneira visual, desenhar uma unidade por vez que F () é chamado para um determinado número, o molhado recebe uma espécie de forma de pirâmide (ou seja, se centralizarmos as unidades horizontalmente) ) Algo assim:

n              *
n-1            **
n-2           ****  
...
2           ***********
1       ******************
0    ***************************

Agora, a pergunta é: com que rapidez a base dessa pirâmide aumenta à medida que n cresce?

Vamos considerar um caso real, por exemplo F (6)

F(6)                 *  <-- only once
F(5)                 *  <-- only once too
F(4)                 ** 
F(3)                ****
F(2)              ********
F(1)          ****************           <-- 16
F(0)  ********************************    <-- 32

Vemos que F (0) é chamado 32 vezes, o que é 2 ^ 5, que para este caso de amostra é 2 ^ (n-1).

Agora, queremos saber quantas vezes F (x) é chamado, e podemos ver que o número de vezes que F (0) é chamado é apenas uma parte disso.

Se movermos mentalmente todos os *'s das linhas F (6) para F (2) para a linha F (1), veremos que as linhas F (1) e F (0) agora têm o mesmo comprimento. O que significa que o total de vezes que F () é chamado quando n = 6 é 2x32 = 64 = 2 ^ 6.

Agora, em termos de complexidade:

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)
JP
fonte
3
F (3) é chamado apenas 3 vezes e não 4 vezes. A segunda pirâmide está errada.
Avik 22/02
2
F (3) = 3, F (2) = 5, F (1) = 8, F (0) = 5. Eu consertaria isso, mas não acho que posso salvar essa resposta com uma edição.
Bernhard Barker
31

Há uma discussão muito boa sobre esse problema específico no MIT . Na página 5, eles afirmam que, se você assumir que uma adição requer uma unidade computacional, o tempo necessário para calcular Fib (N) está intimamente relacionado ao resultado de Fib (N).

Como resultado, você pode pular diretamente para uma aproximação muito próxima da série Fibonacci:

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

e dizer, portanto, que o pior desempenho do algoritmo ingênuo é

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

PS: Há uma discussão sobre a expressão de forma fechada do número N-ésimo de Fibonacci na Wikipedia, se você quiser obter mais informações.

Bob Cross
fonte
Obrigado pelo link do curso. Observação muito boa também
SwimBikeRun 15/08/19
16

Você pode expandi-lo e ter uma visulização

     T(n) = T(n-1) + T(n-2) <
     T(n-1) + T(n-1) 

     = 2*T(n-1)   
     = 2*2*T(n-2)
     = 2*2*2*T(n-3)
     ....
     = 2^i*T(n-i)
     ...
     ==> O(2^n)
Tony Tannous
fonte
1
Eu entendo a primeira linha. Mas por que há menos de um personagem <no final? Como você conseguiu T(n-1) + T(n-1)?
Quazi Irfan
@QuaziIrfan: D que é uma flecha. -> [(não menos que). Desculpe pela confusão em relação à última linha]. Para a primeira linha, bem ... T(n-1) > T(n-2)Então eu posso mudar T(n-2)e colocar T(n-1). Eu só vou conseguir um limite mais alto que ainda é válido paraT(n-1) + T(n-2)
Tony Tannous
10

É delimitada na extremidade inferior por 2^(n/2)e na extremidade superior por 2 ^ n (como observado em outros comentários). E um fato interessante dessa implementação recursiva é que ela possui um forte limite assintótico da própria Fib (n). Esses fatos podem ser resumidos:

T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)

O limite apertado pode ser reduzido ainda mais usando sua forma fechada, se você quiser.

Dave L.
fonte
10

As respostas da prova são boas, mas eu sempre tenho que fazer algumas iterações manualmente para realmente me convencer. Então, desenhei uma pequena árvore de chamada no meu quadro branco e comecei a contar os nós. Divido minhas contagens em nós totais, nós folha e nós interiores. Aqui está o que eu tenho:

IN | OUT | TOT | LEAF | INT
 1 |   1 |   1 |   1  |   0
 2 |   1 |   1 |   1  |   0
 3 |   2 |   3 |   2  |   1
 4 |   3 |   5 |   3  |   2
 5 |   5 |   9 |   5  |   4
 6 |   8 |  15 |   8  |   7
 7 |  13 |  25 |  13  |  12
 8 |  21 |  41 |  21  |  20
 9 |  34 |  67 |  34  |  33
10 |  55 | 109 |  55  |  54

O que salta imediatamente é que o número de nós foliares é fib(n). O que levou mais algumas iterações para perceber é que o número de nós internos éfib(n) - 1 . Portanto, o número total de nós é 2 * fib(n) - 1.

Como você reduz os coeficientes ao classificar a complexidade computacional, a resposta final é θ(fib(n)).

benkc
fonte
(Não, eu não desenhei uma árvore cheia de chamada 10-profunda no meu quadro branco Apenas 5 de profundidade..);)
benkc
Bom, eu queria saber quantas adições extras a Fib recursiva fez. Não é apenas a adição 1de um único Fib(n)tempo de acumulador , mas é interessante que ainda seja exatamente θ(Fib(n)).
Peter Cordes
Observe que algumas implementações (mais) recursivas gastam tempo adicionando 0, no entanto: os casos base de recursão são 0e 1, porque o fazem Fib(n-1) + Fib(n-2). Então, provavelmente a 3 * Fib(n) - 2partir dessa resposta só-link é mais preciso para o número total de nós, não 2 * Fib(n) - 1.
Peter Cordes
Não consigo obter os mesmos resultados nos nós das folhas. A partir de 0: F (0) -> 1 folha (em si); F (1) -> 1 folha (em si); F (2) -> 2 folhas (F (1) e F (0)); F (3) -> 3 folhas; F (5) -> 8 folhas; etc.
alexlomba87
9

A complexidade do tempo do algoritmo recursivo pode ser melhor estimada através do desenho da árvore de recursão. Nesse caso, a relação de recorrência para o desenho da árvore de recursão seria T (n) = T (n-1) + T (n-2) + O (1) observe que cada passo leva O (1), o que significa tempo constante, pois ele faz apenas uma comparação para verificar o valor de n em se o bloco.

          n
   (n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

Aqui vamos dizer que cada nível da árvore acima é indicado por i, portanto,

i
0                        n
1            (n-1)                 (n-2)
2        (n-2)    (n-3)      (n-3)     (n-4)
3   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)

digamos que, com um valor particular de i, a árvore termina, esse caso seria quando ni = 1, daí i = n-1, significando que a altura da árvore é n-1. Agora vamos ver quanto trabalho é feito para cada uma das n camadas da árvore. Observe que cada etapa leva O (1) tempo, conforme declarado na relação de recorrência.

2^0=1                        n
2^1=2            (n-1)                 (n-2)
2^2=4        (n-2)    (n-3)      (n-3)     (n-4)
2^3=8   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)    ..so on
2^i for ith level

já que i = n-1 é a altura da árvore, o trabalho realizado em cada nível será

i work
1 2^1
2 2^2
3 2^3..so on

Portanto, o trabalho total realizado somará o trabalho realizado em cada nível, portanto, será 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 ... + 2 ^ (n-1) desde que i = n-1. Por séries geométricas, essa soma é 2 ^ n, portanto, a complexidade do tempo total aqui é O (2 ^ n)

nikhil kekan
fonte
2

Bem, de acordo com mim, é O(2^n)que nessa função apenas a recursão está demorando um tempo considerável (dividir e conquistar). Vemos que, a função acima continuará em uma árvore até que as folhas se aproximem quando atingirmos o nível F(n-(n-1))ie F(1). Então, aqui, quando anotamos a complexidade de tempo encontrada em cada profundidade da árvore, a série de somatórios é:

1+2+4+.......(n-1)
= 1((2^n)-1)/(2-1)
=2^n -1

essa é a ordem de 2^n [ O(2^n) ].

pgaur
fonte
1

A versão ingênua de recursão de Fibonacci é exponencial por design devido à repetição no cálculo:

Na raiz, você está computando:

F (n) depende de F (n-1) e F (n-2)

F (n-1) depende de F (n-2) novamente e F (n-3)

F (n-2) depende de F (n-3) novamente e F (n-4)

em cada chamada recursiva de nível 2 que está desperdiçando muitos dados no cálculo, a função de tempo terá a seguinte aparência:

T (n) = T (n-1) + T (n-2) + C, com constante C

T (n-1) = T (n-2) + T (n-3)> T (n-2) então

T (n)> 2 * T (n-2)

...

T (n)> 2 ^ (n / 2) * T (1) = O (2 ^ (n / 2))

Este é apenas um limite inferior que, para os fins de sua análise, deve ser suficiente, mas a função em tempo real é um fator de constante pela mesma fórmula de Fibonacci e pela forma fechada é conhecida por ser exponencial da proporção áurea.

Além disso, você pode encontrar versões otimizadas do Fibonacci usando programação dinâmica como esta:

static int fib(int n)
{
    /* memory */
    int f[] = new int[n+1];
    int i;

    /* Init */
    f[0] = 0;
    f[1] = 1;

    /* Fill */
    for (i = 2; i <= n; i++)
    {
        f[i] = f[i-1] + f[i-2];
    }

    return f[n];
}

Isso é otimizado e executa apenas n etapas, mas também é exponencial.

As funções de custo são definidas de Tamanho da entrada até o número de etapas para resolver o problema. Quando você vê a versão dinâmica do Fibonacci ( n etapas para calcular a tabela) ou o algoritmo mais fácil para saber se um número é primo ( sqrt (n) para analisar os divisores válidos do número)). você pode pensar que esses algoritmos são O (n) ou O (sqrt (n)), mas isso simplesmente não é verdade pelo seguinte motivo: A entrada para o seu algoritmo é um número: n , usando a notação binária, o tamanho da entrada para um inteiro n é log2 (n) , fazendo uma alteração variável de

m = log2(n) // your real input size

vamos descobrir o número de etapas em função do tamanho da entrada

m = log2(n)
2^m = 2^log2(n) = n

então o custo do seu algoritmo em função do tamanho da entrada é:

T(m) = n steps = 2^m steps

e é por isso que o custo é exponencial.

Miguel
fonte
1

É simples de calcular diagramando as chamadas de função. Simplesmente adicione as chamadas de função para cada valor de n e veja como o número cresce.

O Big O é O (Z ^ n) onde Z é a proporção áurea ou cerca de 1,62.

Os números de Leonardo e de Fibonacci se aproximam dessa proporção à medida que aumentamos n.

Ao contrário de outras questões do Big O, não há variabilidade na entrada e o algoritmo e a implementação do algoritmo estão claramente definidos.

Não há necessidade de um monte de matemática complexa. Simplesmente faça um diagrama das chamadas de função abaixo e ajuste uma função aos números.

Ou, se você estiver familiarizado com a proporção áurea, a reconhecerá como tal.

Essa resposta é mais correta do que a resposta aceita, que afirma que se aproximará de f (n) = 2 ^ n. Isso nunca será. Abordará f (n) = golden_ratio ^ n.

2 (2 -> 1, 0)

4 (3 -> 2, 1) (2 -> 1, 0)

8 (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)


14 (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)

            (3 -> 2, 1) (2 -> 1, 0)

22 (6 -> 5, 4)
            (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

                        (3 -> 2, 1) (2 -> 1, 0)

            (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)
prumo
fonte
1
Você pode fornecer alguma fonte para essa alegação sobre a proporção áurea?
Nico Haase
-1

http://www.ics.uci.edu/~eppstein/161/960109.html

tempo (n) = 3F (n) - 2

nsh3
fonte
4
Também é bom se você puder explicar sua resposta, em vez de apenas postar um link.
Magnilex
2
Nenhuma explicação fornecida
Kunal B.