1. 재귀함수를 통한 표현 방법
|
1
2
3
4
5
6
7
|
def fibo(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibo(n-1) + fibo(n-2)
|
cs |
기본적으로 사용되는 피보나치 함수이다.
하지만 이 함수는 하나의 함수호출이 다른 두개의 함수 호출로 나뉘어지는 바이너리 형태이다.
따라서 시간 복잡도는 O(2^n)로 n이 커질수록 결과를 가져오는 시간이 급증한다.
2. 반복문을 통한 표현 방법
|
1
2
3
4
5
6
7
8
9
|
def fibo(n):
zero = 1
one = 0
tmp = 0
for _ in range(n):
tmp = one
one = one + zero
zero = tmp
return one
|
cs |
앞의 함수와 다르게 for문의 반복을 통해 결과를 가져온다.
총 n번의 실행을 거쳐 결과를 가져오므로 시간복잡도는 O(n)으로
앞의 함수에 비해 n이 커졌을때에도 결과를 가져오는 시간이 짧다.
결론 : 같은 역할을 하는 함수라도 시간복잡도를 더 작게 만들 수 있다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| BFS의 기본 방식 (0) | 2020.09.10 |
|---|