Aula 05 - Complexidade de Fibonacci O(n) iterativa e O(1)
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:
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:
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()
Ficamos por aqui, até mais. :)
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:
Meu github:
Obrigado, até a próxima e bons estudos. ;)
