[자료구조] ch 3. 알고리즘의 성능

Ch 2 재귀함수 내용이 날아가버렸습니다. 슬픕니다…(저장을 잘 합시다…)

알고리즘 수행 시간이란

​ 알고리즘의 효율성은 ‘자원을 얼마나 효율적으로 사용하는가’ 로 판단합니다. 자원은 시간, 저장공간, 네트워크 대역 등이 될 수 있는데 자료구조나 알고리즘 효율성을 말할 때 99% 이상은 시간에 관한 것입니다.

​ 알고리즘의 수행 시간은 입력 크기에 대해 시간이 얼마나 걸리는지로 표현합니다. 보통 for loop 가 얼마나 중첩되었는지를 기준으로, 입력값이 n 이면 총 수행 시간은 n^(중첩 for loop 수) 가 됩니다. 재귀 함수도 수행시간에 영향을 주는데요. 재귀함수가 몇 번 호출되는지(얼마나 깊이 반복되는지) 가 시간을 좌우합니다. 예를 들어 아래와 같이 factorial(n) 이 있습니다.

fatorial(n):
	if(n = 1) return 1
	return n * factorial(n-1)

factorial(n) 이 factorial(n-1) 을 호출하고, 다시 factorial(n-2) 를 호출하고, …, factorial(2) 가 factorial(1) 을 호출하면서 끝납니다. 총 호출 횟수는 n 이므로 수행 시간은 n 에 비례합니다. 이처럼 알고리즘의 시간 복잡도를 분석할 때에는 수행 시간을 지배하는 부분이 어디인지 파악하는 것이 우선입니다.

알고리즘 복잡도

​ 알고리즘의 복잡도를 나타낼 때는 점근적 표기를 사용합니다. 점근적 복잡도 분석에는 최고차항의 차수만 중요하고 나머지는 다 무시합니다. n 이 충분히 크다면 상수를 곱하든, 다른 차항이 있든 영향이 미미하기 때문입니다. 그래서 각 차수의 대표는 계수가 없는 최고차항이 됩니다. (n, nlogn, n^2, n^3 등)

대표적인 점근적 표기법은 아래와 같습니다.

• O(빅오)-표기 : 점근적 상한
• Ω(오메가)-표기 : 점근적 하한
• θ(세타)-표기 : 점근적 동일

O - 표기

O(n^2) 는 최고차항의 차수가 n^2 를 넘지 않는 모든 함수의 집합을 뜻합니다. n^2, n, nlogn + 5n, 3n^2 + 4n 등을 모두 포함합니다. 따라서 nlogn + 5n 은 O(n^2) 에도 속하고, O(nlogn) 에도 포함됩니다. 이 경우 O(n^2) 로 표현해도 되지만 이는 정보 가치가 전혀 없는 표현이 됩니다. 이처럼 점근적으로 복잡도를 표현할 때는 파악하고 있는 한도 내에서 정보 손실이 덜한 쪽으로 표현해야 합니다. 이것은 분석 능력과도 관계되는데, 어떤 알고리즘을 분석할 때 한 사람은 O(n^2) 까지밖에 파악하지 못했지만 다른 사람이 O(nlogn) 까지 파악할 수 있다면 그것은 분석 능력의 차이입니다.

Ω-표기

Ω 는 O 표기법과 정 반대입니다. Ω(n^2) 은 최고차항의 차수가 n^2 보다 작지 않은 모든 함수의 집합입니다. 5n^2 + 7n, 100n^20 등의 함수가 포함됩니다. 마찬가지로 오메가 표기법에서도 가능하면 정보 손실이 덜한 쪽으로 표현해야 합니다.

θ-표기

θ(n^2) 는 최고차항의 차수가 정확히 n^2 인 모든 함수의 집합을 뜻합니다. θ(n^2) 은 O(n^2) 와 Ω(n^2) 의 교집합이 됩니다. θ 표기가 상한과 하한을 다 포함하고 있으므로 O 로 사용해도 되지만 그러면 θ 표기가 갖는 의미의 반을 잃어버리는 것입니다. 예를 들어 아래와 같은 코드가 있습니다.

sample4(A[], n):
	sum <- 0
	for i <- 0 to n-1 
		for j <- 0 to n-1 
			k <- A[0...n-1] 에서 임의로 [n/2] 개를 뽑은 것들 중 최댓값
			sum <- sum + k
    return sum

for loop 가 2중으로 되어 있으며, 임의의 n/2 개를 뽑은 것 중 최대값도 n 번 수행되므로, 점근적 수행 시간은 O(n^3) 이기도 하고 Ω(n^3) 이기도 합니다. 또한 상한과 하한이 겹치므로 θ(n^3) 이기도 합니다. 이렇게 θ 로 표현할 수 있는 경우에는 θ 를 쓰는 것이 가장 좋습니다. 하지만 상황에 따라 상한과 하한이 겹치지 않거나 하나를 파악하기 힘들다면 O 나 Ω 를 쓸 수밖에 없습니다.

집합 표기를 대신하는 ‘=’

어떤 알고리즘의 수행 시간은 흔히 T(n) 으로 표기합니다. 이 알고리즘이 최대 n^2 에 비례하는 시간이 든다면 T(n) ∈ O(n^2) 입니다. 하지만 ∈ 기호를 계속 사용하는 것은 번거롭기 때문에 일반적으로 T(n) = O(n^2) 로 표기합니다.