Aula 05 – Complexidade de Fibonacci O(n) iterativa e O(1) pela fórmula

More videos
Views
   

Aula 05 – Complexidade de Fibonacci O(n) iterativa e O(1)

Fibonacci O(n) iterativa e O(1) pela fórmula

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

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()  

Ficamos por aqui, até mais. 🙂

Aula 04                       Aula 06

Todas as aulas desse curso

Voltar para página principal do blog

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

Obrigado, até a próxima e bons estudos. 😉

(Visited 12 times, 1 visits today)
About The Author
-

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>