1. 점근표기법(Asymptotic Notation)
1) 빅 오 표기법(O(n))
빅 오 표기법의 정의는 다음과 같다.
모든 N≥N₀에 대해 f(N)≤cg(N)이 성립하는 양의 상수 c와 N₀가 존재하면, f(N)=O(g(N))이다.
이때 g(N)이 f(N)의 상한이 된다.
예를 들어 f(N)= 4N²+N+1 이라는 식이 있을 때 2보다 큰 N에 대해서 g(N)=N², c=5라면 항상 f(N)≤cg(N)이 성립한다.
주의할 점은 g(N)을 찾을 때 가장 차수가 낮은 함수를 선택하는 것이다.
차수가 높은 함수를 선택하게 될 경우 시간복잡도를 과장해서 추정하게 되기 때문이다.
2) 빅 오메가 표기법(Ω(n))
빅 오메가 표기법의 정의는 다음과 같다.
모든 N≥N₀에 대해 f(N)≥cg(N)이 성립하는 양의 상수 c와 N₀가 존재하면, f(N)=Ω(g(N))이다.
이때 g(N)은 f(N)의 하한이 된다.
빅 오 표기법과 마찬가지로 g(N)을 찾을 때 차수가 가장 높은 함수를 선택해야 한다.
3) 세타 표기법(Θ(n))
모든 N≥N₀에 대해 c₁g(N)≤f(N)≤c₂g(N)이 성립하는 양의 상수 c₁, c₂, N₀가 존재하면, f(N)=Θ(g(N))이다.
즉, Θ표기는 수행시간의 O표기와 Ω표기가 같은 경우 사용한다.
위의 두 표기법 보다 정확한 수행시간을 표현할 때 사용한다.
2. 정렬 알고리즘 시간복잡도
1) 선택정렬
N개의 input에 대해 수행시간은 (N-1)+(N-2)+...+2+1=½N(N-1)이 된다.
이것을 빅 오 표기법으로 표현하면 O(N²)이 된다.
선택정렬이 다른 정렬들과 다른 점은 주어진 input이 정렬이 되어있든 되어있지 않든 상관없이 수행시간이 항상 O(N²)가 된다는 것이다.
2) 선택정렬
선택정렬은 주어진 input이 역으로 정렬되어 있을 때 최악의 수행시간을 가진다.
이때 수행시간은 (N-1)+(N-2)+...+2+1=½N(N-1)이 되어 O(N²)이라고 표현할 수 있다.
3) 합병정렬
합병정렬은 주어진 배열을 여러 개의 부분으로 나누고 정렬한 뒤, 정렬한된 부분 배열들을 합병하여 배열을 정렬하는 방식이다.
합병정렬의 수행시간 T(n)은 다음과 같이 표현할 수 있다.
i) n=1일 때, Θ(1)의 수행시간을 가진다.
ii) n>1일 때, T(n)=2T(n/2)+Θ(n) 이다.
Θ(n)=cn (c>0)이라고 하면 배열을 분할하여 원소가 1개인 n개의 부분 배열을 생성한다고 했을 때, 다음과 같은 그림으로 나타낼 수 있다.
이 경우 leaf 노드에서 원소가 1개이기 때문에 n=1이고 수행시간은 Θ(1)이 된다.
그리고 해당 leaf 노드들이 총 n개 존재하기 때문에 leaf 노드들의 총 수행시간은 Θ(n)이 된다.
또한 그림에서 표현된 트리의 높이는 log₂n으로 표현할 수 있다.
Θ(n)=cn이고, 수행시간이 cn인 과정이 log₂n만큼 존재하므로, 총 수행시간은 cnlog₂n이다.
빅 오 표기법으로 표현하면 O(nlog₂n)이다.
3. 재귀 트리 방법(recursion tree method)
- 간단하게 재귀 트리를 그린다.
- 트리의 각 단계 노드들에 대한 수행시간을 계산한다
- 수행시간의 총합을 계산하여 시간복잡도를 찾는다.
4. 마스터 정리(master method)
재귀함수의 시간복잡도를 구하는 방법 중 하나이다.
마스터 정리는 T(n)=aT(n/b)+f(n) (a≥1, b>1, f는 점근적 양의 함수) 형태의 식에 사용할 수 있다.
추론 과정이나, 귀류법을 통한 증명과정을 거칠 필요없이 바로 수행시간을 구할 수 있다는 것이 장점이다.
하지만 항상 적용되는 것은 아니다.
1) f(n)=O(n^(logba-ε)) (ε>0) 일 때
ε인자 때문에 f(n)은 n^(logba) 보다 다항식으로 천천히 증가한다.
이 말은 재귀 트리에서 leaf 노드의 개수가 수행시간을 지배한다는 것을 의미한다.
왜냐하면 leaf 노드의 개수를 n^(logba)로 표현할 수 있기 때문이다.
- leaf 노드 개수 구하기
트리의 높이를 h, 한 노드가 가지는 자식노드의 개수를 a라고 하자.
이때 leaf 노드들의 개수는 a^h와 같다.
h=logbn이므로 leaf 노드들의 개수는 a^h=n^(logba)가 된다.
따라서, T(n)=Θ(n^(logba))
2) f(n)=O(n^(logba)*(log₂^(k)n))) (k≥0) 일 때
f(n)과 n^(logba)는 비슷한 증감률을 보인다.
따라서, T(n)=Θ(n^(logba)*(log₂^(k+1)n))
3) f(n)=O(n^(logba+ε)) (ε>0) 일 때
f(n)이 af(n/b)≤cf(n) (c<1) 을 만족할 때 부분적으로 T(n)=Θ(f(n))이 성립한다.
예시
i) T(n)=4T(n/2)+n
a=4, b=2, f(n)=n 이다. 즉, logba=2 이다.
이는 1번 경우에 해당하므로 f(n)=n=O(n)이고, ε=1 이다.
따라서 T(n)=Θ(n²)
ii) T(n)=4T(n/2)+n²
a=4, b=2, f(n)=n² 이다. 즉, logba=2 이다.
f(n)=n²=O(n²)=O(n²∙(lg⁰n)) -> 이는 2번 경우에 해당하고, k=0 이다.
따라서 T(n)=Θ(n²∙(lgn))
댓글