알고리즘 복잡도 분석

알고리즘 복잡도 분석(complexity analysis)은 구현하지 않고도 모든 입력을 고려하는 방법으로 실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다.

알고리즘의 효율성은 알고리즘이 시작하여 결과가 나올 때까지의 수행시간과 컴퓨터 내에 있는 메모리와 같은 자원의 사용량에 대한 효율이다.

1. 시간 복잡도 함수

알고리즘 분석에는 수행시간, 필요로 하는 기억공간의 양, 이 2가지의 측면을 고려해야 한다. 알고리즘의 수행시간 분석을 시간 복잡도(time complexity)라고 하고 알고리즘이 사용하는 기억공간 분석을 공간 복잡도(space complexity)라고 한다. 알고리즘의 복잡도를 이야기 할 때 대개는 시간 복잡도를 말한다.

시간 복잡도는 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시한다. 일반적으로 연산의 수행횟수는 고정된 숫자(상수)가 아니라 𝑛에 대한 함수가 된다. 연산의 수를 입력의 개수 𝑛의 함수로 나타낸 것을 시간 복잡도 함수라고 하고 𝑇(𝑛)이라고 표기한다.

2. Big-O 표기법

일반적으로 입력의 개수 𝑛과 시간 복잡도 함수 𝑇(𝑛)의 관계는 상당히 복잡할 수 있다. 하지만 입력 자료의 개수가 큰 경우에는 차수가 가장 큰 항이 전체의 값을 주도함을 알 수 있다. 따라서 보통 시간 복잡도 함수에서 차수가 가장 큰 항만을 고려하면 충분하다.

시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 Big-O 표기법이라고 한다. 예를들어 알고리즘이 𝑛에 비례하는 수행시간을 가진다고 말하는 대신 해당 알고리즘의 시간 복잡도가 𝑂(n)이라고 한다. 이 표기법은 𝑛의 값에 따른 함수의 상한 값을 나타내는 방법이다.

Big-O 표기법의 수학적인 정의는 다음과 같다 :

두 개의 함수 𝑓(𝑛)과 𝑔(𝑛)이 주어졌을 때 모든 𝑛 ≥ 𝑛0에 대하여 |𝑓(𝑛)| ≤ 𝑐|𝑔(𝑛)|을 만족하는 2개의 상수 𝑐와 𝑛0가 존재하면 𝑓(𝑛) = 𝑂(𝑔(𝑛))이다.

예제 :

전제 :
|𝑓(𝑛)| ≤ 𝑐|𝑔(𝑛)| 을 증명할 수 있으면 𝑓(𝑛) = 𝑂(𝑔(𝑛)) 은 True

예제 :
𝑓(𝑛) = 2𝑛² + 3, 𝑔(𝑛) = 𝑛² 일 때 𝑓(𝑛) = 𝑂(𝑔(𝑛)) 가 성립하는지 증명해보자.
|𝑓(𝑛)| ≤ 𝑐|𝑔(𝑛)| 을 증명할 수 있으면 True

풀이 :
2𝑛² + 3 ≤ 𝑐 × 𝑛²
𝑐 = 1 이면 𝑛²		(×)
𝑐 = 2 이면 2𝑛²	(×)
𝑐 = 3 이면 3𝑛²	⬇

𝑛		2𝑛² + 3		  3𝑛²
--------------------------
1	   2·1²+3=5		3·1²=3		(×)
2	   2·2²+3=11	3·2²=12		(o)		n ≥ 2
3	   3·3²+3=21	3·3²=27		(o)

∴ 𝑓(𝑛) = 𝑂(𝑔(𝑛)) 은 true when 𝑐 = 3 and n ≥ 2

Big-O 표기법을 사용하면 시간 복잡도 함수의 증가에 별로 기여하지 못하는 항을 생략함으로써 시간 복잡도를 간단하게 표시할 수 있다. 얻는 방법은 기본연산의 횟수가 다항식으로 표현되었을 경우 다항식의 최고차항만을 남기고 다른 항들과 상수항을 버리는 것이다. 최고차항의 계수도 버리고 단지 최고차항의 차수만을 사용한다. 다만 주의할 것은 log𝑛은 없애면 안 된다는 것이다. log𝑛도 차수를 가지고 있기 때문이다.

다음은 많이 쓰이는 Big-O 표기법을 순서대로 표시한 것이다.

• 𝑂(1) : 상수형
• 𝑂(log𝑛) : 로그형
• 𝑂(𝑛) : 선형
• 𝑂(𝑛log𝑛) : 선형로그형
• 𝑂(𝑛²) : 2차형
• 𝑂(𝑛³) : 3차형
• 𝑂(2^𝑛) : 지수형
• 𝑂(𝑛!) : 팩토리얼형

다음은 알고리즘의 수행시간을 비교한 것이다.

• 𝑂(1) < 𝑂(log𝑛) < 𝑂(𝑛) < 𝑂(𝑛log𝑛) < 𝑂(𝑛²) < 𝑂(2^𝑛) < 𝑂(𝑛!)

3. Ω(Big-Omega) 표기법

사실 Big-O 표기법은 상한을 표기한 것이므로 상한은 여러 개가 존재할 수 있다. 그러나 Big-O 표기법이 최소 차수로 표기되었을 경우만 의미가 있다. 따라서 이와 같은 문제점을 보완하기 위하여 Ω(Big-Omega) 표기법과 Θ(Big-Theta) 표기법이 있다. Big-Omega 표기법은 어떤 함수의 하한을 표시하는 방법이다.

Big-O의 경우, 𝑓(𝑛) = 2𝑛 + 1인 경우 𝑓(𝑛) = 𝑂(𝑛)이라 하였지만 사실은 𝑓(𝑛) = 𝑂(𝑛²)라고도 할 수 있다. 왜냐하면 𝑛0 = 1, 𝑐 = 2로 잡으면 𝑛 > 1에 대하여 2𝑛 + 1 ≤ 2𝑛²이기 때문이다. 하지만 Big-Omega의 경우, 𝑓(𝑛) = 2𝑛 + 1이면 𝑛 > 1에 대하여 2𝑛 + 1 ≥ 𝑛이므로 𝑓(𝑛) = Ω(𝑛)이다.

Big-Omega 표기법의 수학적인 정의는 다음과 같다 :

두 개의 함수 𝑓(𝑛)과 𝑔(𝑛)이 주어졌을 때 모든 𝑛 ≥ 𝑛0에 대하여 |𝑓(𝑛)| ≥ 𝑐|𝑔(𝑛)|을 만족하는 2개의 상수 𝑐와 𝑛0가 존재하면 𝑓(𝑛) = Ω(𝑔(𝑛))이다.

예제 :

전제 :
|𝑓(𝑛)| ≥ 𝑐|𝑔(𝑛)| 을 증명할 수 있으면 𝑓(𝑛) = Ω(𝑔(𝑛)) 은 True

예제 :
𝑓(𝑛) = 2𝑛² + 3, 𝑔(𝑛) = 𝑛² 일 때 𝑓(𝑛) = Ω(𝑔(𝑛)) 가 성립하는지 증명해보자.
|𝑓(𝑛)| ≥ 𝑐|𝑔(𝑛)| 을 증명할 수 있으면 True

풀이 :
2𝑛² + 3 ≥ 𝑐 × 𝑛²
𝑐 = 1 이면 𝑛²		(o)

𝑛		2𝑛² + 3		  𝑛²
--------------------------
1	   2·1²+3=5		1²=1		(o)

∴ 𝑓(𝑛) = Ω(𝑔(𝑛)) 은 true

4. Θ(Big-Theta) 표기법

Θ(Big-Theta)는 동일한 함수로 상한과 하한을 만들 수 있는 경우, 즉 𝑓(𝑛) = 𝑂(𝑔(𝑛))이고 𝑓(𝑛) = Ω(𝑔(𝑛))인 경우를 𝑓(𝑛) = Θ(𝑔(𝑛))이라고 한다. 예를 들면 𝑓(𝑛) = 2𝑛 + 1이면 𝑛 > 1에 대하여 𝑛 ≤ 2𝑛 + 1 ≤ 3𝑛이므로 𝑓(𝑛) = Θ(𝑛)이다.

Big-Theta 표기법의 수학적인 정의는 다음과 같다 :

두 개의 함수 𝑓(𝑛)과 𝑔(𝑛)이 주어졌을 때 모든 𝑛 ≥ 𝑛0에 대하여 𝑐1|𝑔(𝑛)| ≤ |𝑓(𝑛)| ≤ 𝑐2|𝑔(𝑛)|을 만족하는 3개의 상수 𝑐1, 𝑐2와 𝑛0가 존재하면 𝑓(𝑛) = Θ(𝑔(𝑛))이다.

𝑓(𝑛) = Θ(𝑔(𝑛))가 성립하기 위해선 𝑓(𝑛) = 𝑂(𝑔(𝑛)) True && 𝑓(𝑛) = Ω(𝑔(𝑛)) True 여야한다.

References

• 『C언어로 쉽게 풀어쓴 자료구조』