[자료구조(C언어)] 점근적 분석의 예시

※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다.

---

점근적 분석의 예시

 

1) 상수 시간복잡도

int sample(int data[], int n)
{
	/* 아래의 연산은 n의 크기에 관계없이 1번만 실행된다. */
	int k = n/2; 
	return data[k];
}

입력 데이터의 크기에 관계없이(n에 관계없이) 일정한 시간, 상수 시간이 소요된다.

이 경우 알고리즘의 시간복잡도는 O(1)이다.

 

2) 선형 시간복잡도

int sum(int data[], int n)
{
	int sum = 0;
	for (int i=0; i<n; i++) 
		sum = sum + data[i];
	return sum;
}

sum = sum + data[i]; 는 이 알고리즘에서 가장 자주 실행되는 문장이며,

실행 횟수는 항상 n번이다.

가장 자주 실행되는 문장의 실행 횟수가 n번이라면 모든 문장의 실행 횟수의 합은 n에 선형적으로 비례하며, 모든 연산들의 실행 횟수의 합도 역시 n에 선형적으로 비례한다.

(선형적으로 비례 = 동일한 차수를 가진다는 뜻 / 차수가 일차인 함수는 일차함수 또는 선형함수라고 부른다. )

 

⇒ 선형 시간복잡도를 가진다고 말하고, O(n)이라고 표기한다. 최악의 경우와 평균적인 경우 시간복잡도가 같다.

 

3) 순차탐색 (Sequential Search)

배열 data에 정수 target이 있는지 검색한다.

int search(int n, int data[], int target)
{
	for (int i=0; i<n; i++) {
		if (data[i] == target)
			return i;
	}
	return -1;
}

data[i] == target 는 이 알고리즘에서 가장 자주 실행되는 문장이며,

최악의 경우 실행 횟수는 n번이다. 따라서 최악의 경우 시간복잡도는 O(n)이다.

 

4) Quadratic (2차)

배열 x에 중복된 원소가 있는지 검사한다.

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;
}

x[i] == x[j] 는 이 알고리즘에서 가장 자주 실행되는 문장이며,

최악의 경우 배열에 저장된 모든 원소 쌍을 비교하므로 비교 연산의 횟수는 n(n-1)/2이다. ( 1 + 2 + 3 + .... + n-1 = n(n-1)/2 )

최악의 경우 시간복잡도는 O(n^2)으로 나타낸다.

 

정리

위 예시들을 통해 점근적 표기법은 최고차항의 차수만으로 표시하므로 가장 자주 실행되는 연산 혹은 문장의 실행횟수를 고려하는 것으로 충분하다는 것을 알 수 있다.