시간 복잡도와 빅-오 표기법

"어떤 알고리즘이 어떠한 상황에서 더 빠르고 느리냐?"

"어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰냐?"

 

하나는 '속도'에 관한 것이고, 다른 하나는 '메모리의 사용량'에 관한 것이다. 이것을 수행하는 시간 분석 결과를 가리켜 앞에 것은 '시간 복잡도'라 하고, 뒤에 것은 '공간 복잡도'라 한다.

 

 

 

어떻게 속도를 평가할까?

 

① 연산의 횟수를 셉니다

② 그리고 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n) 을 구성합니다

 

 

연산의 횟수가 적어야 빠른 알고리즘이고,

②의 의미는 데이터의 수를 함수에 입력하면 연산의 횟수가 바로 계산이 되는 식을 구성한다는 뜻이다. 그 식은 책에 그림이 있는데 지수나 로그함수 식의 형태 같은 것들이다. 데이터 수의 변화에 따른 연산횟수의 변화 정도를 한눈에 파악이 가능해서 둘 이상의 알고리즘을 비교하기가 용이하다.

 

 

연산의 횟수를 세라고 했으니, 모든 연산자를 대상으로 연산횟수를 세어야할 것 같은 느낌이지만 핵심적인 연산자를 대상으로 횟수를 세면 된다. 예를 들어

for(i=0; i<len; i++)
{
	if(ar[i] == target)
    	return i;	// 찾은 대상의 인덱스 값 반환
}

이 코드에서의 핵심 연산은 값의 동등을 비교하는 == 연산이다. == 연산의 횟수를 대상으로 시간 복잡도를 분석하면 된다.

 

 

 

☆ 순차 탐색 알고리즘에서 운이 좋으면 탐색의 횟수는 1, 운이 안좋으면 탐색의 횟수는 n이 된다. 우리는 알고리즘을 평가하는데 있어서 운이 안좋은 최악의 경우만을 두고 성능 판단을 하도록 한다.

 

 

 

 

---

<이진 탐색 알고리즘>

( 처음 인덱스 + 마지막 인덱스 ) / 2 의 공식이 되며, 이때 계산해서 나오는 나머지는 버리는 것으로 한다. 그리고 값을 찾을 때까지 이 공식을 사용한다.

 

이진 탐색 알고리즘은 언제까지 진행되어야 할까? first와 last가 만났다는 것은 탐색의 대상이 아직 하나 남아있음을 뜻한다. 따라서 이진 탐색은 first<last 인 상황에서도 first==last 상황에서도 계속되어야 한다. 그러므로 다음과 같은 반복문으로 구성된다. 

 

while(first <= last)   // first <= last 가 반복의 조건임에 주의
{
	// 이진 탐색 알고리즘의 진행
}

 

그리고 first가 last보다 큰 경우 탐색은 종료된다. 그리고 이렇게 종료가 되었다는 것은 탐색에 실패했음을 의미한다.

 

#include <stdio.h>

int BSearch(int ar[], int len, int target)
{
	int first = 0;    // 탐색 대상의 시작 인덱스 값
	int last = len - 1;    // 탐색 대상의 마지막 인덱스 값
	int mid;

	while (first <= last) {
		mid = (first + last) / 2;  // 탐색 대상의 중앙을 찾는다.

		if (target == ar[mid]) {
			return mid;   // 탐색 완료!
		}
		else {    // 타겟이 아니라면 탐색 대상을 반으로 줄인다.
			if (target < ar[mid])
				last = mid - 1;   // 왜 -1을 하였을까?
			else
				first = mid + 1;   // 왜 +1을 하였을까?
		}
	}
	return -1;   // 찾지 못했을 때 반환되는 값 -1
}

 

계속 읽어보며 이 알고리즘을 따라가보자.

 

 

 

 

 

 

이진 탐색 알고리즘의 시간 복잡도 계산하기 : 최악의 경우(worst case)를 기준으로

T(n) = log2 n

 

 

빅-오 표기법

빅-오가 무엇일까? 혹시 O가 매우 크다는 뜻?

빅-오라는 것은 함수 T(n)에서 가장 영향력이 큰 부분이 어딘가를 따지는 것인데, 이때 사용되는 표기법에 대문자 O, 그러니까 큰 O가 사용되기 때문에 빅-오라 하는 것이다.

빅오의 표기법으로 T(n) = n^2 + 2n + 1 은 T(n) = n^2 라 표기할 수 있다. ( 2n+1의 영향은 미미하다 )

 

 

T(n) 이 다항식으로 표현이 된 경우, 최고차항의 차수가 빅-오가 된다. O(n^m)

 

O(log n) 이 의미하는 바는 다음과 같이 이해하여야 한다.

"데이터 수의 증가에 따른 연산횟수의 증가 형태를 좌표평면상에 그려놓으면, 증가하는 추세가 둔화되는 형태를 띤다. 다시 말해서 로그 그래프와 유사한 형태를 띤다.

 

 

 

 

 

 

빅-오 구하기 예제)

3n + 2  ->  n

7n^3 + 3n^2 + 2  -> n^3

2^n + n^2  -> 2^n

n + logn -> n

n + nlogn  -> nlogn          // logn의 n이 증가함에 따라 그 값은 1이상으로 커진다.

2^n + n^3 -> 2^n

 

 

 

 

---

대표적인 빅-오

 

O(1)

 

상수형 빅-오
데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘을 의미한다. 예를 들어, 연산의 횟수가 데이터 수에 상관없이 3회 진행되는 알고리즘일지라도 O(3)이 아닌 O(1)이라 한다.

 

O(logn)

 

로그형 빅-오
데이터 수의 증가율에 비해서 연산횟수의 증가율이 훨씬 낮은 알고리즘을 의미한다. 따라서 매우 바람직한 유형이다. 참고로 로그의 밑에 따라 차이가 나긴 하지만, 그 차이는 알고리즘의 성능관점에서 매우 미미하기 때문에 대부분의 경우에 있어서 무시된다.

 

O(n)

 

선형 빅-오
데이터의 수와 연산횟수가 비례하는 알고리즘을 의미한다.

 

O(nlogn)

 

선형로그형 빅-오
데이터의 수가 두 배로 늘어날 때, 연산횟수는 두 배 조금 넘게 증가하는 알고리즘을 의미한다. n과 logn을 곱한 형태라서 난해해 보이지만, 알고리즘 중에는 이에 해당하는 알고리즘이 적지 않다.

 

O(n2)

 

데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다. 따라서 데이터의 양이 많은 경우에는 적용하기 부적절하다. 이는 이중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우 발생한다. 달리 말하면 중첩된 반복문의 사용은 알고리즘 디자인에서 그리 바람직하지 못하다고 할 수 있다.

 

O(n3)

 

데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다. 이는 삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 이 역시 적용하기에 무리가 있는 알고리즘이다.

 

O(2^n)

 

지수형 빅-오
이는 '지수적 증가'라는 매우 무서운 연산횟수의 증가를 보이기 때문에, 사용하기에 매우 무리가 있는 알고리즘이다.

 

 

 

 

지금까지 설명한 빅-오 표기들의 성능(수행시간, 연산횟수)의 대소를 정리하면 다음과 같다.

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2^n)