Persistence

피보나치 수열 문제: 피보나치 수열에서 n번째 오는 값을 구하시오. e.g. n이 6일 때, 1, 1, 2, 3, 5, 8 ... 이므로 답은 8 재귀로 아래처럼 간단하게 풀 수 있으나, 이 방법은 O(2^n) 시간 복잡도를 가진다. def fib(n): if n == 1 or n == 2: return 1 return fib(n-2) + fib(n-1) 시간 복잡도를 생각하는 방법은, 아래와 같은 예시를 생각해보면 된다. 위의 피보나치 수열을 구하는 재귀와 밑의 코드의 시간복잡도는 비슷하리라 짐작할 수 있다. 하나의 n에서 두 개의 가지를 뻗어서 자기 자신을 재호출하고 있는 구조이기 때문이다. -1씩 깎이는 거나 -2씩 깎이는거는 나중에 가면 상수값이 되어서 빅오표기법에서는 의미가 없다. (이 영상 의..