[통계] 알고리즘의 복잡도 (2) - 알고리즘의 여러 차수

지난 게시글에 이어 알고리즘의 여러가지 차수를 계산하여 비교해보고자 한다. 또한, 피보나치 수열을 예제로 재귀적, 반복적 프로그램을 구현해보고 각각의 효율성을 비교할 것이다.

 

---

지난 게시글

2020/12/27 - [Machine Learning/#Statistic] - [통계] 알고리즘의 복잡도 (1)

[통계] 알고리즘의 복잡도 (1)

---

 

1/ 알고리즘의 여러 가지 차수

지수차수 > 다항식차수 > 로그차수 순으로 빠르게 증가

Input size가 커지거나 복잡한 문제일수록 차수 비교가 중요해짐

eg) 외판원 문제 (traveling salesman problem): n개의 도시를 방문할 때 최단의 경로를 찾는 문제

• local optimum choice는 전체적 관점에서는 최단이 아닐 수 있음

• (n-1)! 개의 선택지 - 차수: O(n!) (지수차수보다 빠른 증가율)

 

eg) 피보나치 수열

피보나치 함수

a/ 재귀 프로그램

# 피보나치 수열 재귀적 구현
01 fiborecursive = function(i){
02	if (i <= 2) {
03    	value = 1
04    }
05    else {
06    	return(fiborecursive(i-1) + fiborecursive(i-2))
07    }
08}

재귀함수를 사용하는 경우에는 직관적이고 편리하게 구현이 가능하지만 깊이가 깊어질수록 효율성은 저하됨

재귀 프로그램의 메모리 비용-지수차수

 

b/ 반복 프로그램

# 반복 프로그램
01fiboiterative = function(i) {
02	if(i<=2){
03    	value = 1
04    }
05    else{
06    	value1 = 1
07        value2 = 2
08        for (j in 3:i){ #loop
09        	value = value1+value2
10            value1 = value2
11            value2 = value #swapping
12        }
13    }
14    return (value)
15}

반복 프로그램의 시간 복잡도는 선형적으로 증가하는 O(n)으로 O(2^n)을 갖는 재귀 프로그램보다 효율적임

 

---

다음 게시글

수치적 방법- 최적화 (최대하강법, 뉴튼-랩슨 알고리즘, 선형 계획법)

---

 

I'm a Senior Student in Data Science ! 

데이터 사이언스를 공부하고 있는 4학년 학부생의 TIL 블로그입니다. 게시글이 도움 되셨다면 구독과 좋아요 :)