Page 111 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

복잡도

프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라
집니다. 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라고 합니다.
복잡도는 아래의 두 가지 요소를 가지고 있습니다.

1. 시간 복잡도(time complexity) : 실행에 필요한 시간을 평가한 것
2. 공간 복잡도(space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

앞 장에서 배운 ‘소수’를 찾는 프로그램(버전 1, 2, 3)은 알고리즘을 선택할 때 두 복잡도(시간, 공
간)의 균형을 생각할 필요성이 있음을 말해 줍니다. 여기서는 선형 검색과 이진 검색의 시간
복잡도에 대해서 더 자세히 살펴보겠습니다.

선형 검색의 시간 복잡도
아래의 선형 검색 함수를 바탕으로 시간 복잡도를 살펴보겠습니다.

int search(const int a[], int n, int key)
{
1 int i = 0;
2 while(i < n) {
3 if(a[i] == key)
4 return i; /* 검색 성공 */
5 i++;
}
6 return –1; /* 검색 실패 */
}

이 프로그램은 실습 3-1의 search 함수를 수정한 코드입니다.

표 3-1은 1 ~ 6 의 각 단계가 몇 회 실행되는지에 대한 내용을 정리한 것입니다.

변수 i에 0을 대입( 1 )하는 횟수는 처음 한 번 실행한 이후에는 없습니다(데이터 수 n과는 무관합
니다). 이렇게 한 번만 실행하는 경우 복잡도는 O(1)로 표기합니다. 물론 함수에서 값을 반환
하는 4 와 6 도 한 번만 실행하기 때문에 O(1)로 표기합니다. 배열의 맨 끝에 도달했는지를

판단하는 2 와 현재 검사하고 있는 요소와 찾고자 하는 값이 같은지를 판단하는 3 의 평균
실행 횟수는 n / 2입니다. 이처럼 n에 비례하는 횟수만큼 실행하는 경우의 복잡도를 O(n)이
라고 표기합니다.

복잡도를 표기할 때 사용하는 O는 Order에서 따온 것으로, O(n)은 ‘O – n’, ‘Order n’, ‘n의 Order’라고 읽습니다.
03•검색 111