[CS50] 알고리즘 표기법

프로그램을 실행하면 작업이 완료되기까지 어느 정도의 시간이 소요됩니다. 이 시간은 처리하는 데이터가 많아질수록, 처리하는 작업이 복잡해질수록 더욱 오래 걸리게 되고 이 실행시간은 매우 중요해집니다. 특정 알고리즘을 작성할 때 그 실행시간을 표기하는 방법에 대해 공부해보도록 하겠습니다.

 

알고리즘의 실행시간을 표기하는 방법에는 3가지가 있습니다. (얼마나 나누냐에따라 5가지로 표시하는 곳도 있습니다.)

1. Big-O 표기법

2. Big-Omega 표기법

3. Theta 표기법

이중에서 Big-O와 Big-Omega 표기법에 대해 조금 자세히 공부해보겠습니다.

 

Big-O

위의 그림을 공식으로 표기한 것을 Big-O 표기법이라고 합니다. 각각 O(n), O(n/2), O(log2 n)으로 표기할 수 있는데, 

여기에서 O는 "on the order of"의 약자로 ~만큼의 정도로 커지는 이라는 뜻을 가지고 있습니다.

그런데 여기서는 n의 앞에 인자나 log의 2와 같은 밑 수는 크게 의미가 없습니다. 무슨 뜻이냐면 만약 n이 매우 커진다면 O(n)은 n만큼 커지는 것이라 선형적으로 증가하게 될 겁니다. 그래서 O(n/2)도 결국 동일하게 매우 커지게 되기 때문에 1/2는 큰 의미를 갖지 못할 겁니다. log역시 마찬가지로 log의 밑변이 2나 3이나 10이나 결국 함수는 log n의 함수를 가지므로 동일하게 O(log n)이라고 표기할 수 있습니다.

그래서 아래 목록 같은 Big-O 표기법은 실행 시간을 나타내기 위해서 많이 사용됩니다.

O(n^2)

O(n log n)

O(n) - 선형검색

O(log n) - 이진검색

O(1)

 

Big-Omega(Ω)

Big-O가 알고리즘 실행시간의 상한을 나타낸 것이라면 반대로 Big-Omega는 실행시간의 하한을 나타냅니다.

예를 들자면 선형검색에서 n개의 항목이 있을 때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 되지만 운이 좋아서 한 번에 검색을 끝낸다면 하한은 Ω(1)이 됩니다.

역시 아래 목록의 Big-Omega 표기법도 많이 사용됩니다.

Ω(n^2)

Ω(n log n)

Ω(n) - 배열 안에 존재하는 값의 개수 세기

Ω(log n)

Ω(1) - 선형검색, 이진검색

 

Theta(Θ)

Theta는 Big-O와 Big-Omega의 공통부분이라고 생각하면 됩니다.

 

이러한 내용들을 표로 살펴본다면

이렇게 됩니다.

 

그렇다면 여기서 실행시간의 상한이 낮은 알고리즘과 하한이 낮은 알고리즘 어떤 게 더 효율적일까요??

알고리즘의 상한은 최악의 경우 하한은 최선의 경우라고 할 수 있는데요 알고리즘의 평균적인 시간은 사실 의미가 없는 경우가 많이 있습니다.

예를 들어 집에서 카카오 지도로 30분 거리의 장소가 있다고 할 때 보통 정확히 30분 만에 갈 수 있는 경우는 매우 드물 겁니다. 지하철을 놓칠 수도 있고 버스를 탔는데 차가 막힐 수도 있기 때문이죠 그래서 "나 30분 정도 걸려" 보다는 "나 늦어도 50분 안에는 도착한다"가 더 신뢰도가 높은 말일 겁니다. 그렇기 때문에 상한이 낮은 알고리즘이 좀 더 효율적이라고 말할 수 있습니다.

 

---

출처

본 내용은 CS50의 2019년 강의를 듣고 작성했습니다. (개념이 어느 정도 정리되면 최신강의도 다시 듣고 수정할 내용 있으면 수정하겠습니다.)

 

강의 자료는 EdX에서 무료로 사용할 수 있고 boostcourse에서 한글 강의로도 들을 수 있습니다.