Data Structure - Analysis of Algorithms (알고리즘 분석 방법)
이 글은 PC기준으로 작성되었습니다.
1. Running Time
- 알고리즘의 실행 시간은 보통 입력의 양이 많아질수록 길어짐
- 평균 알고리즘 실행 시간을 구하는 것은 어려움
- 때문에 우리는 최악의 상황을 고려해서 알고리즘의 실행 시간을 분석함
2. Theoretical Analysis
1) 특징
- 직접 실행하지 않고 분석하는 기술
- input size n 에 따라 Running Time 특징지음
- 가능한 모든 input 고려
- 하드웨어 / 소프트웨어 성능과 관계없이 알고리즘 처리속도 평가가능
2) 7가지 중요한 함수 (이론적 분석시 자주 사용)
3) Counting Primitive Operations
엄밀하게 일일히 각 과정이 몇 번 발생하는지를 세리는 기술같다. 아래의 예를 보자
각 과정에서 # operations가 왜 저렇게 되었을까. Stack Overflow에서 본 내용과 내 생각을 정리해보면 아래와 같다.
식 : # operations
currentMax <- A[0] : A[0]에 접근 한번과 currentMax 변수에 값 저장 한번 = 총 2번
for i<-1 to n-1 do : 이는 곧 for(i = 1 ; i< n ; i++) 이므로 매 loop시 i<n 비교 n번 (i는 1부터 n까지) 과
for문이 한번 끝날때마다 다시 처음으로 돌아와서 loop하므로 총 처음으로 n-1번 loop
(i 는 1부터 n-1까지),
i = n 일때, for문 done 시킬때 1번 => 총 2n번
if A[i] > currentMax then : A[i]에 접근 n-1번과 비교연산자 계산 n-1번 => 총 2(n-1)번
currentMax<-A[i] : 마찬가지로 A[i]에 접근 n-1번과 currentMax에 대입 n-1 번 => 총 2(n-1)번
{increament counter i} : 이는 곧 i = i + 1과 같다. 따라서 i+1 (n-1)번, i에 대입 (n-1)번 => 총 2(n-1)번
return currentMax : currentMax의 리턴, 총 1번
4) Running Time 추정하기
위의 예시의 결과 arrayMax는 최악의 경우 (8n-3)번 primitive operation이 실행된다. 따라서 a를 가장 빠른 primitive operatioin을 처리하는데 걸린 시간, b를 가장 느린 primitive operation을 처리하는데 걸린 시간이라고 가정하면 arrayMax가 최악의 경우 실행되는데 걸리는 시간 T(n)은 다음을 만족한다.
a(8n-3) <= T(n) <= b(8n-3)
따라서 T(n)은 두개의 일차함수에 둘려싸여있다. 하드웨어나 소프트웨어를 바꾼다고 해도 T(n)의 상수만 바뀌고 그래프의 기울기가 바뀌는 것은 아니므로, T(n)은 이 알고리즘만의 고유한 성질이다.
5) Asymptotic Algorithm Analysis
이 분석기술은 big-Oh 표현법을 사용하기 위한 기본이다. 수학에서의 점근선과 비슷하게 앞에서 구한 Primitive Operations의 실행수를 나타낸 식에서 최고차항만을 남겨놓고 그 계수를 1로 바꿔주는 것이다. 앞의 예시 같은 경우, arrayMax는 최악의 경우 8n-3번 Primitive Operations가 실행되므로 이는 O(n)번 실행되는 것으로 볼 수 있다. 물론 최고차항의 계수가 사라지고 그 아래 차수의 식들이 사라지므로 어떻게 점근이 되냐는 질문이 생기기 마련인데, 아마 n을 무한대로 보내서 아래 차항들과 계수의 효과가 미미해져서 인것 아닌가라는 생각이 들지만 이후 교수님께 여쭤봐야겠다.
6) The Big-Oh Notation
그럼 빅 오 함수는 무엇일까. 정의는 이렇다.
f(n)과 g(n)이 음이 아닌 실수를 정의역 (Input Size) 으로 하는 함수일때, c>0, n0>=1 이고,
n>=n0인 n에 대하여f(n) <= cg(n) 이면 f(n)은 O(g(n))이다.
예를 들어 f(n) = 10n + 2, g(n)= n 인 두 함수가 있다. C = 11이면 Cg(n) = 11n 이고,
n>2인 영역에서 f(n) < 11g(n) 이므로 f(n)은 O(g(n)) = O(n)이다.
삼차함수의 예를 보자. f(n) = 3n^3 + 20n^2 + 5, g(n) = n^3 이면 C= 4, n1 = 21 일때
f(n) < g(n) 이므로 f(n) = O(n^3)이다.
로그함수의 경우도 마찬가지이다. f(n) = 3logn + 5 , g(n) = Clogn 이면 (log의 밑은 2이다),
C=8, n1 = 2일때, f(n) <= g(n) 이므로 f(n) = O(logn)이다.
이 정의를 통해, 보통 빅 오 함수는 최악의 상황을 나타냄을 알 수 있다.
7) 세 가지의 Big 함수
첫번째는 위에서 봤던 빅 오 함수이다. 나머지 두 개는 어떤게 있을까?
- 1. Big - Omega 함수 : 빅 오 함수의 반대이다. 똑같은 조건에서 f(n) >= Cg(n)인 n1이 존재하면
f(n) = Ω(g(n)), 최선의 케이스를 나타낸다.
- 2. Big - Seta 함수 : C₁g(n) <= f(n) <= C₂g(n) 인 n1, C₂가 존재하면 f(n) = Θ(g(n)).
평균적인 케이스를 나타낸다. 정의에 따라 빅 오와 빅 오메가를 모두 충족하면
빅 세타임을 알 수 있다.
8) 간단한 빅 오함수 규칙
빅 오 함수에 대해 알아 보았다. 이제와서긴 하지만 빅 오 함수의 규칙은 간단하다. 위에서 말했듯이, 최고차항의 차수가 d차인 함수 f(n)이 있으면 f(n)은 O(n^d)라는 것이다. 왜 항상 이를 만족하는가에 대해서는 따로 증명해봐야겠다.