Aula 05 – Complexidade de Fibonacci O(n) iterativa e O(1) pela fórmula
Aula 05 – Complexidade de Fibonacci O(n) iterativa e O(1)
Fibonacci O(n) iterativa e O(1) pela fórmula
Voltar para página principal do blog
Todas as aulas desse curso
Aula 04 Aula 06
Se gostarem do conteúdo dêem um joinha 👍 na página do Código Fluente no
Facebook
Esse é o link do código fluente no Pinterest
Meus links de afiliados:
Hostinger
Digital Ocean
One.com
Meu github:
https://github.com/toticavalcanti
Implementações de Fibonacci O(n) iterativa e O(1) pela fórmula
O(n) iterativa
# Programa para encontrar o enésimo número de fibonacci em Python 3
# com complexidade O(n), implementação iterativa.
import time
def fib(n):
last = 1
penult = 1
if n == 1:
return penult
elif n == 2:
return last
else:
current = 0
for i in range(2, n):
current = last + penult
penult = last
last = current
return current
def main():
n = int(input())
t0= time.process_time()
print( fib(n) )
t1 = time.process_time() - t0
print("Time elapsed: ",abs(t1 - t0))
if __name__ == "__main__":
main()
Veja que temos um for i in range(2, n), já que os casos bases 0 e 1, ou seja, o primeiro e segundo número da sequência é 1, por isso não precisa ser calculado.
Na verdade é um for de tamanho n – 2, mas isso não faz diferença, como a complexidade tá relacionada ao tamanho do n, é uma complexidade de O(n).
Implementação mágica, O(1).
Agora a implementação mágica, a complexidade é de O(1), isto é, constante, porque simplesmente é só uma conta que tem que ser feita, só um cálculo, não precisa fazer nenhum loop.
A complexidade nesse caso não depende do tamanho do n.
A implementação segue essa fórmula:
Fórmula de fibonacci
O(1) Fórmula
# Programa para encontrar o enésimo número de fibonacci em Python 3
# com complexidade O(1)
import time
import math
def fib(n):
# phi é o número de ouro, número áureo, secção áurea,
#proporção de ouro, é uma constante real algébrica irracional
#Seu valor é 1.618033988749895... ao infinito
phi = (1 + math.sqrt(5)) / 2
return round(math.pow(phi, n) / math.sqrt(5))
def main():
n = int(input())
t0= time.process_time()
print( fib(n) )
t1 = time.process_time() - t0
print("Time elapsed: ",abs(t1 - t0))
if __name__ == "__main__":
main()
