Fibonacci Number

Q: Qual é a complexidade de tempo da função recursiva de Fibonacci?

A recursão ingênua faz 2 × F(n+1) - 1 chamadas, uma contagem que cresce como 1.618^n e geralmente é escrita como O(2^n) . Para n = 45 , são cerca de 3.7 × 10^9 chamadas. Armazenar cada resultado uma única vez, em uma tabela ou em duas variáveis, reduz isso para O(n) .

Q: Como resolver Fibonacci com programação dinâmica?

Comece pela recorrência F(n) = F(n-1) + F(n-2) e calcule os valores em ordem crescente de n , armazenando cada um. Você pode preencher uma tabela de baixo para cima ou manter a função recursiva e armazenar em cache seus resultados, o que é chamado de memoização. De qualquer forma, cada valor é calculado uma vez, então o trabalho total é O(n) .

Q: É possível calcular Fibonacci usando espaço O(1)?

Sim. Cada número depende apenas dos dois anteriores, então duas variáveis são suficientes. Mantenha os dois últimos valores e avance-os a cada etapa. Isso resulta em tempo O(n) com espaço extra O(1) .

Q: Existe uma maneira mais rápida do que O(n)?

Sim. A matriz [[1, 1], [1, 0]] elevada à potência n contém F(n) no canto superior direito, e a exponenciação por quadrados repetidos calcula essa potência em O(log n) multiplicações de matrizes. Também existe uma fórmula fechada com potências da razão áurea, mas ela usa ponto flutuante e perde precisão à medida que n cresce; por isso, os métodos com inteiros são preferidos.

InicianteProgramação dinâmica Recursão

+10

Os números de Fibonacci começam com F(0) = 0 e F(1) = 1, e cada número seguinte é a soma dos dois anteriores: F(n) = F(n-1) + F(n-2). A sequência começa com 0, 1, 1, 2, 3, 5, 8, 13. Sua função recebe n e retorna F(n).

Função

fib(n: integer) → integer

ninteger: a posição na sequência de Fibonacci, contando a partir de 0
Retornainteger: o número de Fibonacci F(n)

Restrições

0 ≤ n ≤ 45
O resultado cabe em um inteiro de 32 bits com sinal: F(45) = 1134903170.

Exemplos

Entrada: n = 4
Saída: 3
Explicação: Conte a partir do início: F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2 e F(4) = 2 + 1 = 3.

Entrada: n = 10
Saída: 55
Explicação: A sequência a partir do índice 0 é 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. O número no índice 10 é 34 + 21 = 55.

+13 testes ocultos ao enviar

Para ir além

Você consegue calcular F(n) em tempo O(log n)?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

A definição já é uma função recursiva, e escrevê-la dessa forma produz a resposta correta. A armadilha é o tempo de execução: as duas chamadas recursivas refazem o trabalho uma da outra, e o número de chamadas cresce exponencialmente com n. A programação dinâmica resolve isso calculando cada número de Fibonacci uma única vez, de baixo para cima. O último passo mantém apenas os dois números necessários para calcular o próximo.

Recursão diretamente a partir da definição

Correta, mas não termina nos maiores testes

Intuição

Traduza a definição palavra por palavra. fib(0) é 0, fib(1) é 1, e qualquer valor maior retorna fib(n-1) + fib(n-2). Toda cadeia de chamadas termina em um dos dois casos-base, então a resposta está correta.

Agora conte as chamadas. fib(5) chama fib(4) e fib(3), mas fib(4) chama fib(3) novamente. No fim, fib(3) é executada duas vezes, fib(2) três vezes e fib(1) cinco vezes, e fib(5) faz 15 chamadas no total. Os mesmos valores são recalculados repetidamente.

A contagem de chamadas acompanha os próprios números de Fibonacci: calcular F(n) faz 2 × F(n+1) - 1 chamadas. Para n = 45, são cerca de 3.7 × 10^9 chamadas, muito mais do que caberia em um limite de tempo. O limite costuma ser escrito como O(2^n); o crescimento exato é de cerca de 1.618^n. A recursão tem apenas n níveis de profundidade, então a pilha precisa de O(n) espaço.

Algoritmo

Se n for 0 ou 1, retorne n.
Caso contrário, chame a função para n-1 e para n-2.
Retorne a soma dos dois resultados.

def fib(n):
    if n < 2:
        return n  # F(0) = 0, F(1) = 1
    return fib(n - 1) + fib(n - 2)

Preencha uma tabela de baixo para cima

Intuição

A recursão é lenta apenas porque se esquece. Se você anotar cada número de Fibonacci na primeira vez que o calcular, cada um custará uma única adição. Crie uma tabela f com posições para os índices de 0 a n, defina f[0] = 0 e f[1] = 1, e preencha o restante da esquerda para a direita com f[i] = f[i-1] + f[i-2].

A ordem da esquerda para a direita é o que faz isso funcionar: quando você chega a f[i], os dois números de que precisa já estão na tabela. Para n = 10, a tabela é preenchida com 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, e a resposta é a última posição.

Isso é programação dinâmica em sua forma mais simples: uma relação de recorrência mais uma tabela de respostas para casos menores. São n-1 adições, tempo O(n), e a tabela contém n + 1 números, espaço O(n). n = 45 agora leva 44 adições em vez de bilhões de chamadas.

Algoritmo

Se n for 0 ou 1, retorne n.
Crie uma tabela com n + 1 números, com f[0] = 0 e f[1] = 1.
Para i de 2 até n, defina f[i] = f[i-1] + f[i-2].
Retorne f[n].

def fib(n):
    if n < 2:
        return n
    f = [0] * (n + 1)  # f[i] will hold F(i)
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]

Manter apenas os dois últimos números

Intuição

Observe o que o loop da tabela lê. Para preencher f[i], ele precisa de f[i-1] e f[i-2], e nada mais antigo; portanto, todos os espaços anteriores são desnecessários. Use duas variáveis em vez de uma tabela: prev armazena o número de dois passos atrás, e curr, o número de um passo atrás.

Comece com prev = 0 e curr = 1, que são F(0) e F(1). A cada passo, calcule next = prev + curr e, em seguida, avance o par: prev recebe o valor antigo de curr, e curr recebe next. Para n = 4, o par passa de (0, 1) para (1, 1), (1, 2) e (2, 3), e curr = 3 é a resposta.

O trabalho é o mesmo: n-1 adições, tempo O(n), com três inteiros na memória, espaço O(1). A ordem das atualizações importa: se você sobrescrever prev antes de somá-lo, a soma usará o valor errado.

Algoritmo

Se n for 0 ou 1, retorne n.
Defina prev = 0 e curr = 1.
Repita n-1 vezes: calcule next = prev + curr, depois defina prev = curr e curr = next.
Retorne curr.

def fib(n):
    if n < 2:
        return n
    prev, curr = 0, 1  # F(0) and F(1)
    for _ in range(n - 1):
        prev, curr = curr, prev + curr
    return curr

Armadilhas e casos extremos

Fibonacci é o primeiro problema clássico de programação dinâmica, e a maioria dos bugs vem da recursão ou dos dois primeiros valores.

Entregar a recursão ingênua. Ela passa nos testes pequenos e então precisa de bilhões de chamadas em n = 45. Armazene os resultados em uma tabela ou em duas variáveis.
Errar o início. Aqui, F(0) = 0 e F(1) = 1, então F(2) = 1 e F(10) = 55. Começar a sequência em 1, 1 desloca cada resposta em um índice.
Construir a tabela sem uma verificação para valores pequenos de n. Para n = 0, uma tabela de tamanho n + 1 = 1 não tem espaço para f[1], e escrevê-lo ultrapassa os limites. Retorne n imediatamente quando n < 2.
Atualizar o par na ordem errada. prev = curr seguido por curr = prev + curr soma o novo prev e dobra curr. Calcule primeiro a soma em next ou use uma atribuição simultânea, quando a linguagem oferecer esse recurso.
Executar um passo a mais. Um loop que também calcula F(n+1) chega a F(46) = 1836311903 no limite, que ainda cabe em 32 bits apenas por sorte. F(47) não cabe.

Perguntas frequentes4

Qual é a complexidade de tempo da função recursiva de Fibonacci?

A recursão ingênua faz 2 × F(n+1) - 1 chamadas, uma contagem que cresce como 1.618^n e geralmente é escrita como O(2^n). Para n = 45, são cerca de 3.7 × 10^9 chamadas. Armazenar cada resultado uma única vez, em uma tabela ou em duas variáveis, reduz isso para O(n).

Como resolver Fibonacci com programação dinâmica?

Comece pela recorrência F(n) = F(n-1) + F(n-2) e calcule os valores em ordem crescente de n, armazenando cada um. Você pode preencher uma tabela de baixo para cima ou manter a função recursiva e armazenar em cache seus resultados, o que é chamado de memoização. De qualquer forma, cada valor é calculado uma vez, então o trabalho total é O(n).

É possível calcular Fibonacci usando espaço O(1)?

Sim. Cada número depende apenas dos dois anteriores, então duas variáveis são suficientes. Mantenha os dois últimos valores e avance-os a cada etapa. Isso resulta em tempo O(n) com espaço extra O(1).

Existe uma maneira mais rápida do que O(n)?

Sim. A matriz [[1, 1], [1, 0]] elevada à potência n contém F(n) no canto superior direito, e a exponenciação por quadrados repetidos calcula essa potência em O(log n) multiplicações de matrizes. Também existe uma fórmula fechada com potências da razão áurea, mas ela usa ponto flutuante e perde precisão à medida que n cresce; por isso, os métodos com inteiros são preferidos.

Python

def fib(n):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Entrada

n = 4

Esperado

Fibonacci Number

Função

Restrições

Exemplos

Dicas

Solução

Recursão diretamente a partir da definição

Preencha uma tabela de baixo para cima

Manter apenas os dois últimos números

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos