complexidade computacional de Fibonacci Sequência

Question

Eu entendo notação Big-O, mas eu não sei como calculá-lo para muitas funções. Em particular, eu estive tentando descobrir a complexidade computacional da versão ingênua da seqüência de Fibonacci:

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

O que é a complexidade computacional da sequência de Fibonacci e como ele é calculado?

Answer 1

Você modelar a função de tempo para Fib(n) calcular como soma de tempo para Fib(n-1) calcular mais o tempo para Fib(n-2) calcular mais o tempo para adicioná-los juntos (O(1)). Isso supõe que as avaliações repetidas da mesma Fib(n) levar o mesmo tempo -. Ou seja, não memoization é o uso

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 você vai acabar com a resposta.

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

Base: n = 1 é óbvio

Suponha T(n-1) = O(2 n-1 ), , portanto,

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

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

No entanto, como observado em um comentário, este não é o apertado amarrado. Um fato interessante sobre esta função é que o T (n) é assintoticamente o mesmo como o valor da 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 retornará 1. O valor de Fib(n) é a soma de todos os valores devolvidos pelas folhas da árvore de recursão que é igual à contagem de folhas. Uma vez que cada folha vai demorar O (1) para computação, T(n) é igual a Fib(n) x O(1). Consequentemente, o apertado ligado para esta função é a seqüência de Fibonacci em si (~ θ(1.6 n )). Você pode descobrir este apertado ligado usando funções geradoras como eu tinha mencionado acima.

Answer 2

Apenas pergunte-se quantas declarações precisa executar para F(n) para ser concluído.

Para F(1), a resposta é 1 (a primeira parte da condicional).

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

Então, o que satisfaz função dessas regras? Tente um ⁿ (a> 1):

a ⁿ == um ^(n-1) + A ^(n-2)

Divide através de um ^(n-2) :

a ² == a + 1

Resolva para a e você começa (1+sqrt(5))/2 = 1.6180339887, também conhecido como o ouro relação .

Por isso, leva tempo exponencial.

Answer 3

Há um muito bom discussão deste problema específico ao longo do MIT . Na página 5, eles fazem o ponto que, se você assumir que uma adição leva uma unidade computacional, o tempo necessário para calcular Fib (N) está intimamente relacionada com o resultado de Fib (N).

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

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

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

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

PS: Há uma discussão sobre a forma fechada do número Nth Fibonacci sobre a Wikipedia se você quiser obter mais informações.

Answer 4

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

I chegou à mesma conclusão por um pouco simplista, mas eu acredito que o raciocínio ainda é válido.

Em primeiro lugar, é tudo sobre descobrir quantas vezes recursiva função fibonacci (F () a partir de agora) é chamado quando o cálculo do número de Fibonacci Nth. Se ele é chamado uma vez por número na seqüência de 0 a n, então temos que O (n), se ele é chamado n vezes para cada número, então nós começamos O (n * n) ou O (n ^ 2), e assim por diante.

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

Como uma primeira impressão, parece-me que, se colocá-lo em uma forma visual, desenho de uma unidade por tempo F () é chamado para um determinado número, molhar obter uma espécie de forma de pirâmide (ou seja, se nós unidades de centro horizontal). Algo parecido com isto:

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

Agora, a pergunta é, o quão rápido é a base desta pirâmide ampliando à medida que n cresce?

Vamos dar 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 F (0) é chamada 32 vezes, que é 2 ^ 5, que para este caso amostra é de 2 ^ (n-1).

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

Se mover mentalmente todos os * 's a partir de F (6) de F (2) linhas para o F (1) linha, vemos que F (1) e F (0) linhas são agora iguais em comprimento. O que significa, tempos totais F () é chamada quando n = 6 é 2x32 = 64 = 2 ^ 6.

Agora, em termos de complexidade:

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)

Answer 5

Você pode expandi-lo e ter uma visualizaçã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)

Answer 6

É delimitada na extremidade inferior por 2^(n/2) e na extremidade superior por 2 ^ n (como observado em outras observações). E um fato interessante de que a implementação recursiva é que ele tem uma assintótica apertado ligado de Fib (n) em si. Esses fatos podem ser resumidas:

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

O apertado ligado pode ser reduzido ainda mais usando seu forma fechada se você gosta.

Answer 7

As respostas de prova são bons, mas eu sempre tenho que fazer algumas iterações com a mão para realmente me convencer. Então eu desenhei uma árvore chamada pequena no meu quadro branco, e começou a contar os nós. Eu dividi minhas contagens de fora no total de nós, 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 imediatamente salta é que o número de nós de folha é fib(n). O que levou mais algumas iterações a notar é que o número de nós interiores é fib(n) - 1. Portanto, o número total de nós é 2 * fib(n) - 1.

Uma vez que você deixar cair os coeficientes ao classificar complexidade computacional, a resposta final é θ(fib(n)).

Answer 8

complexidade de tempo de recursiva algoritmo pode ser melhor estimada pelo desenho árvore de recursão, Neste caso, a relação de recorrência para desenhar árvore de recursão seria T (n) = T (n-1) + T (n-2) + O (1 ) Note que cada passo leva O (1), que significa constante de tempo, uma vez que faz apenas uma comparação para verificar valor de n em se block.Recursion árvore seria parecido

          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 é denotada 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)

vamos dizer que em determinado valor de i, as extremidades das árvores, nesse caso, seria quando n-i = 1, portanto, i = n-1, o que significa que a altura da árvore é n-1. Agora vamos ver quanto trabalho é feito para cada um de n camadas no tree.Note que cada passo leva O (1) tempo fixado 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

desde i = n-1 é a altura do trabalho árvore feita em cada nível serão

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

Daí trabalho total feito vai soma do trabalho feito, em cada nível, pelo que será de 2 ^ 0 + 2 ^ 1 + 2 + 2 ^ 2 ^ 3 ... + 2 ^ (n-1) uma vez que i = n -1. De séries geométricas desta soma é duas ^ n, Assim complexidade tempo total aqui é O (2 ^ n)

Answer 9

Bem, de acordo com me a ele é O(2^n) como em esta função apenas recursão está tomando o tempo considerável (dividir e conquistar). Vemos que, a função acima continuará em uma árvore até que as folhas são abordagens quando chegarmos ao nível F(n-(n-1)) ou seja F(1). Então, aqui quando anotar a complexidade de tempo encontradas em cada profundidade de árvore, a série somatório é:

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

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

Answer 10

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

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

Answer 11

A versão recursão ingênuo de Fibonacci é exponencial pelo projeto devido à repetição no cálculo:

Na raiz que você está computando:

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

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

f (n-2) depende F (n-3) de novo e F (n-4)

então você está tendo em cada nível 2 chamadas recursivas que estão desperdiçando uma grande quantidade de dados no cálculo, a função de tempo será parecido com este:

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

T (n-1) = T (n-2) + T (n-3)> T (n-2), em seguida,

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

...

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

Este é apenas um limite inferior que, para efeitos da sua análise deve ser suficiente, mas a função de tempo real é um fator de constante pela mesma fórmula de Fibonacci e do forma fechada é conhecido por ser exponencial da razão de ouro.

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

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 fazer apenas n passos, mas também é exponencial.

As funções de custo são definidos a partir do tamanho de entrada para o número de passos para resolver o problema. Quando você vê a versão dinâmica de Fibonacci ( n passos para calcular a tabela) ou o algoritmo mais fácil de saber se um número é primo ( sqrt (n) para analisar a validade divisores do número). você pode pensar que estes algoritmos são O (n) ou O (sqrt (n)) , mas isso simplesmente não é verdade para o seguinte motivo: A entrada para o seu algoritmo é um número: n , usando o binário notação o tamanho de entrada para um número inteiro n é log2 (n) seguida, fazendo uma mudança variável

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

Vamos descobrir o número de passos como uma 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 é um exponencial.