[알고리즘의 분석] 시간복잡도

알고리즘의 자원 사용량을 분석합니다.

 

여기서의 자원이란 실행 시간, 메모리, 저장장치, 통신 등이 있으며 실행시간의 분석에 대해서 다룹니다. 

 

 

시간복잡도

 실행시간은 실행환경에 따라 달라집니다. (하드웨어, 운영체제, 언어, 컴파일러 등)

 

실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트합니다. 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현하며 데이터의 크기가 같더라도 실제 데이터에 따라서 달라집니다. 

 

- 최악의 경우 시간복잡도 

- 평균의 시간복잡도 

 

점근적 분석

점근적 표기법 사용

-데이터의 개수 n-> 무한대일때 수행시간이 증가하는 growth rate로 시간복잡도 표현하는 기법

- Θ- 표기, O-표기 등을 사용

 

유일한 분석법도 아니고 가장 좋은 분석법도 아님

-다만 가장 간단하며, 알고리즘의 실행 환경에 비의존적이기 때문에 가장 광범위하게 사용됨

bool is_distinct(int n, int x[])
{
	for (int i = 0; i < n - 1; i++)
		for (int j = i + 1; j < n; j++)
			if (x[i] == x[j])
				return false;
	return true;
}

최악의 경우 n(n-1)/2 에서 O(n^2)이 됩니다. 

 

for (i = 1; i < n; i *= 2)
{
    // do something
}

 

• 초기값: i = 1
• 조건: i < n
• 증가: i가 2배씩 증가 (i *= 2)

O(log n)

 

2k≥n

즉, 어떤 k에 대해 2^k가 처음으로 n 이상이 되는 순간, 반복이 멈춘다.

 

빅 o- 표기

upper bound를 표현하는 것으로  f(n) = 32n^2 + 17n^2 - 32라면 n^2이 최악의 시간복잡도가 될 것입니다. 물론 o(n^3)도 이것의 시간복잡도가 될 수가 있습니다. 왜 그럴까요?

 

upper bound를 표현하는 것이 O-의 역할이기 때문입니다. 책에서는 =을 써서 표현을 하겠지만 =이 아닌 엄밀하게 보면 =이 아닌 빅 O notation을 정확하게 정의를 하면 포함관계가 되는 것입니다.

n^2을 하나의 함수의 집합으로 보는 것이고 집합에 속한다는 것으로 개념화를 해야 정확한 수학적인 정의가 될 수 있는 것입니다. 

 

누가 처음 시작했는지는 모르겠지만 f(n) = O(g(n)) 이렇게 표기하지만 정확히는 포함관계라는 점을 아셔야 합니다. 

 

Ω표기

lower bound로 빅O의 반대입니다.

g(n)과 f(n)이 있을 때 작거나 같게 만든다는 것이 lower bound로 표기할 수 있습니다. 무엇보다 크거나 같다라는 주장은 더 걸리지 않는다 이거 이내다 이렇게 하지 이것보다 더 걸린다라고는 말하지 않기 때문에 Ω로 표기하는 일은 거의 없을 것입니다. 

 

하지만 세타 노테이션을 설명하기에 필수적으로 알아야 할 과정입니다. 

 

f(n) = 32n^2 + 17n - 32라고 할 때 f(n)은 Ω(n^2) 이 될 수도 있지만 Ω(n)이 될 수도 있습니다. 물론 이렇게 쓰지는 않지만 포함관계라는 가정 하에서 틀린 답은 아닌 것입니다. 

 

Θ표기

Θ

f(n)과 g(n)은 동일 차수의 함수라고 이해할 수 있습니다.

 

동일차수의 함수는 무엇의 상수가 더 크냐에 따라 값이 변경될 수 있습니다. f(n)이 똑같이 32n^2 이렇게 시작을 할 때 

Θ(n^2)이 될 수 있지만 Θ(n^3)이나 Θ(n)은 될 수 없습니다.

 

따라서 upper bound와 lower bound를 동시에 표현하는 것이라고 보면 됩니다.