파이썬 알고리즘 3일차

1.7.4 피보나치 수열

: 첫째 및 둘째 항이 1이며, 그 이후의 모든 항은 바로 앞 두 항의 합인 수열

import math

# 첫 번째 방법
def find_fibonacci_seq_iter(n):
    if n<2: return n
    a, b = 0, 1
    for i in range(n):
        a, b = a, a+b
    return a

# 두 번째 방법
def find_fibonacci_seq_rec(n):
    if n<2: return n
    return (find_fibonacci_seq_rec(n-1)+find_fibonacci_seq_rec(n-2))

# 세 번째 방법
def find_fibonacci_seq_form(n):
    sq5 = math.sqrt(5)
    phi = (1+sq5)/2
    return int(math.floor(phi**n/sq5))

def test_find_fib():
    n = 10
    assert(find_fibonacci_seq_rec(n) == 55)
    assert(find_fibonacci_seq_iter(n) == 55)
    assert(find_fibonacci_seq_form(n) == 55)
    print("테스트 통과!")

if __name__ == "__main__":
    test_find_fib()

• 첫 번째 방법: 시간복잡도 = (O(2^n))
• 두 번째 방법: 시간복잡도 = (O(n))
• 세 번째 방법: 시간복잡도 = (O(1))

지금까지 공부하면서 느낀 것은 공부 방법의 변화가 필요하다... 유튜브나 다른 플랫폼의 방법들을 찾아보며 공부해야할 것 같다.

---

https://www.youtube.com/watch?v=H6z1_tnyhp0

이 분의 방법을 채택하여... 내일부터 새로운 알고리즘 4일차를 시작하도록 해야겠다....