Fibonacci, Power Series e Big-O

Christopher Colosi Blocked Unblock Seguir Seguindo 4 de janeiro

Quando revisitamos conceitos que conhecemos sob uma nova luz, às vezes fazemos perguntas e descobrimos aspectos que nunca havíamos percebido antes.

Fui recentemente apresentado ao CoderPad , uma plataforma web para entrevistar engenheiros. Ele permite que o engenheiro escreva e execute código, produzindo saída de texto e relatando a quantidade de tempo que o programa levou para ser concluído. Como o CoderPad exibia essa imagem interessante de uma solução recursiva muito ineficiente para a série Fibonacci em seu site, decidi testar sua interface implementando-a junto com uma solução iterativa e comparando seus tempos de execução.

Solução recursiva ineficiente para a série Fibonacci – crédito https://coderpad.io/

Eu implementei as três soluções a seguir no Python 2 para produzir o enésimo elemento da série Fibonacci. O primeiro é o da imagem acima, e embora seja praticamente uma tradução exata da definição da série para o código, é muito ineficiente porque se chama duas vezes, fazendo exponencialmente mais trabalho do que o necessário. A segunda é uma solução recursiva que só se chama uma vez (uma recursão linear) e a terceira é uma solução iterativa.

 from __future__ import print_function 
 # solução recursiva muito ineficiente 
def fib (n):
se n em (0,1):
retornar n
retorno de fib (n-1) + fib (n-2)
 # solução recursiva ligeiramente mais eficiente 
def fibr2 (n):
se n == 0:
retornar 0, 0
se n == 1:
retornar 0, 1
componentes = fibr2 (n-1)
componentes de retorno [1], componentes [0] + componentes [1]
 solução #iterativa 
def fibit (n):
se n em (0,1):
retornar n
two_back = 0
one_back = 1
current = 1
para i em xrange (3, n + 1):
two_back = one_back
one_back = atual
current = two_back + one_back
retorno atual
 n = 20 
imprimir (n, fib (n), sep = ' t')
#print (n, fibr2 (n) [1], sep = ' t')
#print (n, fibit (n), sep = ' t')

Como esperado, a solução iterativa foi a mais rápida e foi capaz de calcular o maior índice da série, produzindo o milionésimo número de Fibonacci em cerca de 10 segundos. Em algum lugar entre lá e 2 milhões, os números ficam tão grandes que excedeu o limite de cpu permitido por Coderpad. A segunda função recursiva (fibr2) foi aproximadamente equivalente em velocidade, mas em n = 987, ela travou devido a transbordamento da pilha (onde armazena o estado de todas as chamadas de função esperando que as chamadas posteriores retornem antes que possam ser concluídas) das armadilhas da recursão. A verdadeira surpresa veio ao testar a primeira função recursiva; ele ficou visivelmente mais lento que n = 30, levando cerca de 6 segundos para calcular o 36º número de Fibonacci, e esgotou o uso de CPU permitido em apenas n = 39. Eu esperava que isso fizesse o pior, mas fiquei chocado por ter sido muito pior do que a outra função recursiva.

Eu realmente não tinha pensado em detalhes sobre a complexidade específica da Big-O da primeira solução, já que ela era obviamente a menos eficiente. Foi O (n²)? Não. Eu percebi que na verdade é O (fib (n)). Então, como isso se parece com o O (n²)? Eu estava lutando para entender mentalmente como e quando o fib (n) era maior do que o n², então adicionei uma instrução print à minha função iterativa e aumentei tanto o quadrado quanto a fib até n = 20.

 #print (n, n * n, fib (n), sep = " t") 
 Saída: 
 0 0 0 
1 1 1
2 4 1
3 9 2
4 16 3
5 25 5
6 36 8
7 49 13
8 64 21
9 81 34
10 100 55
11 121 89
12 144 144
13 169 233
14 196 377
15 225 610
16 256 987
17 289 1597
18 324 2584
19 361 4181
20 400 6765

Fib (n) passa n2 em n = 13 e aumenta a uma taxa exponencial muito mais rápida. Isso me levou a considerar como e por que de uma maneira que nunca tive antes. A série Fibonacci está adicionando valores para n menor, enquanto a série de energia está adicionando valores para o atual n. Como está a fibra subindo mais rápido? Eu poderia definir a série power-2 de maneira similar à série de fibonacci? Pensando em praças e olhando para os números, percebi que podia. Indo por exemplo de n = 12 para n = 13 (ie de 12 * 12 a 13 * 13), você precisa adicionar 1 para cada um dos 12 postos já calculados que deveriam ter sido multiplicados por 13 em vez de 12, e então você precisa adicionar 13. pow2 (13) = 12 * 12 + 12 + 13, ou escrito em termos do índice n…

 pow2 (n) = pow2 (n-1) + n-1 + n 
 #comparado a mentir 
fib (n) = fib (n-1) + fib (n-2)

Então, como o fib (n-2) se compara à soma (n-1 + n)? A série de fibonacci está de fato adicionando um valor dois índices de volta, mas está adicionando o resultado, não o índice. A série de energia está adicionando índices de nível mais alto, mas eles são os índices, que à medida que o índice cresce, são muito, muito, muito menores do que o valor resultante. Então, em n = 39, onde a função recursiva ficou fora do tempo de CPU permitido, pow2 (39) = 1.521, mas fib (39) = 63.245.986. É por isso que a complexidade do Big-O é tão importante na ciência da computação. fib (n) não é quadrático (O (n²)), é exponencial (O (2 ^ n)).

Texto original em inglês.