tony9402

3. 피보나치 수열의 시간 복잡도 본문

알고리즘/공부

3. 피보나치 수열의 시간 복잡도

ssu_gongdoli 2018. 9. 26. 21:16
반응형

1. 재귀를 이용한 피보나치 수열



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
 
using namespace std;
 
typedef long long ll;
 
ll fibo(int n)
{
    if(n <= 1)return n;
    else return fibo(n - 1) + fibo(n - 2);
}
 
int main()
{
    int n;
    cin >> n;
    cout << fibo(n);
    return 0;
}
 

cs


함수 호출 부분에서 중복으로 호출해서 n이 어느 정도 클 때 시간이 매우 길다. 


 n

계산하는 항의 개수 

0 

1 

1 

1 

2 

3 

3 

5 

4 

9 

5 

15 

6

25 



이를 시간에 대한 점화식으로 세워보면 다음과 같다. 




이를 귀납적으로 T(n)의 시간을 계산해보면 아래와 같다.




이 결과를 이용하여 유도한 식이 맞는지 확인해보자.






2. 반복문을 이용한 피보나치 수열


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
 
using namespace std;
 
typedef long long ll;
 
int main()
{
    int n;
    ll a, b, c;
    a = b = 1;
    c = 2;
    cin >> n;
    if (n <= 2)cout << 1;
    else {
        for (int i = 0; i < n - 3; i++)
        {
            a = b;
            b = c;
            c = a + b;
        }
        cout << c;
    }
    return 0;
}

cs

이것의 장점은 중복된 계산이 없다는 것이다. 따라서 시간 복잡도는 재귀를 이용한 것보다 작다.


이를 시간에 대한 함수 T(n)을 구해보면 아래와 같다.





반응형
저작자표시 비영리 동일조건

'알고리즘 > 공부' 카테고리의 다른 글

숭실대 대회  (0) 2018.12.30
4. 차수 표기법 및 차수에 대한 정의  (0) 2018.09.26
2. Search algorithm  (0) 2018.09.16
1. 알고리즘이란  (0) 2018.09.16
2. 시간복잡도와 공간복잡도 (1)  (0) 2018.08.26
'알고리즘/공부' Related Articles more
Comments