[알고리즘] 알고리즘의 설계와 분석 - 시간 복잡도와 점근성능

[알고리즘] 알고리즘의 설계와 분석 - 시간 복잡도와 점근성능

1. 알고리즘 설계 기법

주어진 문제, 속성, 조건 등에 따라 매우 다양한 알고리즘이 존재할 수 있다. 따라서 일반적이고 범용적인 알고리즘 설계 기법은 존재하지 않지만 그 중 대표적인 설계 기법 세 가지를 꼽으면 다음과 같다.

 

• 분할 정복 방법(Divide-and-Conquer)
• 동적 프로그래밍 방법(Dynamic Programming)
• 욕심쟁이 방법(Greedy)

따라서 알고리즘을 공부하며 위 세 가지 설계 기법은 꼭 알아둬야 할것이다.

 

2. 알고리즘의 효율성 분석

알고리즘의 효율성 분석은 알고리즘 수행에 필요한 메모리 양과 수행 시간을 계산하는 것이다.

 

• 메모리 양 → 공간 복잡도(Space Complexity) = 정적 공간 + 동적 공간
• 수행 시간 → 시간 복잡도(Time Complexity)

 

3. 시간 복잡도

알고리즘의 시간 복잡도에는 입력 크기(입력 데이터 크기)와 입력 데이터 상태(정렬 여부 등) 이 영향을 미친다.

시간 복잡도는 알고리즘의 최악의 수행 시간을 입력 크기 n의 함수로 표현한다.

다음 예를 보자. 입력 데이터의 합계와 평균을 구하는 알고리즘이다.

 

먼저 입력 크기가 n일 때 각 연산의 횟수를 구한다. (1, 1, n+1, n, n, 1, 1)

연산 횟수를 모두 더하면 f(n) = 3n+5이며 점근 성능의 big-oh 표기법으로 O(n)으로 표기할 수 있다.

 

4. 점근성능의 표기법

점근성능은 입력 크기 n이 무한대로 커짐에 따라 결정되는 성능이다.

수행 시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현한다.

점근성능은 수행 시간의 어림값이고 수행 시간의 증가 추세 파악이 용이하며 알고리즘의 우열을 구할 수 있다.

 

점근성능의 표기법은 크게 big-oh, big-omega, big-theta 세 가지가 있다.

 

(1) Big-Oh - 점근적 상한

양의 상수 c와 n0가 존재하여 모든 n≥n0에 대해 f(n)≤c·g(n)이면 f(n)=O(g(n))이다.

 

쉽게 말해 입력 크기가 n0를 넘어서면 f(n)은 항상 c·g(n)보다 수행시간이 작다는 의미이고 O(g(n))은 f(n)의 최악의 수행시간이다.

 

(2) Big-Omega - 점근적 하한

양의 상수 c와 n0가 존재하여 모든 n≥n0에 대해 f(n)≥c·g(n)이면 f(n)=Ω(g(n))이다.

 

 

쉽게 말해 입력 크기가 n0를 넘어서면 f(n)은 항상 c·g(n)보다 수행시간이 크다는 의미이고 Ω(g(n))은 f(n)의 최선의 수행시간이다.

 

(3) Big-Theta - 점근적 상하한

양의 상수 c1, c2와 n0가 존재하여 모든 n≥n0에 대해 c1·g(n)≤f(n)≤c2·g(n)이면 f(n)=Θ(g(n))이다.

 

 

Big-theta는 알고리즘의 수행시간을 더 엄밀하게 표현하는 표기법이다.

 

다음은 f(n)과 g(n)이 주어졌을때 f(n)을 세 가지 점근적 표기법으로 표현한 것이다.

 

 

(4) 주요 O-표기 간의 연산 시간의 크기 관계

 

5. 알고리즘의 시간 복잡도를 구하는 실용적인 접근 방법

지금까지 다룬 내용에 의하면 알고리즘의 시간 복잡도는 수행 시간 f(n)을 구한 후 f(n)=O(g(n))을 만족하는 최소 차수의 함수 g(n)을 찾아야 하지만 실용적인 접근 방법은 알고리즘의 루프 반복 횟수만 조사해서 시간 복잡도로 취하고 g(n)은 최고 차수에 의존하는 것이다.

 

좌측 알고리즘은 while문이 n번 반복되므로 O(n), 우측 알고리즘은 for문이 n번, 그 안에서 다시 n번 반복되므로 n*n = n^2 = O(n^2)이다.

 

6. 순환 알고리즘의 성능 - 점화식과 폐쇄형

자기 자신의 알고리즘을 다시 수행하는 형태의 순환(Recursion, 재귀) 알고리즘의 성능은 지금까지의 방법으로 구할 수 없고 일반적으로 점화식을 유도하고 점화식의 폐쇄형을 구해서 계산한다.

 

이진탐색 알고리즘의 점화식 유도

 

점화식의 폐쇄형 구하기

 

매번 점화식을 유도하고 폐쇄형을 구하기 보다는 기본 점화식과 폐쇄형이 존재하므로 이를 암기하는게 낫다.

 

기본 점화식과 폐쇄형

특히 (2), (3), (6)은 각각 퀵 정렬, 이진 탐색, 합병 정렬의 수행 시간이므로 필수적으로 암기하자. 나머지 (1), (4), (5)는 모두 Θ(n)이므로 암기하기 쉽다.

 

References

한국방송통신대학교 컴퓨터과학과 알고리즘 강의