[컴퓨터 과학 cs50] 알고리즘 시간복잡도 BigO와 오메가!

알고리즘을 실행하는데 걸리는 시간을 표현한다

 

 

 

위와 같은 그림을 공식으로 표기한 것이 Big O 표기법입니다.

여기서 O는 “on the order of”의 약자로, 쉽게 생각하면 “~만큼의 정도로 커지는” 것이라고 볼 수 있습니다.

O(n) 은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 됩니다. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있습니다.

 

빨간 선과 노란선이 같다고 말할 수 있는 이유는 만약 우리가 푸는 문제가 충분히 크다면, 즉 문제가 계속 커져서 이 정도 크기의 화면에 담기도록 축소해서 보기 위해 x축과 y축을 늘려본다면, 노란 선과 빨간선은 아주 가까워질 것이다.

계속 그림을 축소하며, 더욱더 크기가 큰 문제를 본다면, 두 선은 결국 거의 같아 보일 것이다.

따라서 컴퓨터 과학자는 알고리즘의 효율성을 설명할 때, 정확히는 O(n/2)일지라도 그냥 O(n)이라고 말한다.

로그의 경우도 그냥 O(log n)이라고 말한다. 밑이 뭐든 상관없다.

 

주로 아래 목록과 같은 Big O 표기가 실행 시간을 나타내기 위해 많이 사용됩니다.

실행시간이란 프로그램이나 알고리즘이 동작하는 데 걸리는 시간을 말한다.

몇 초가 걸리는지, 혹은 몇 번의 계산 과정이 필요한지를 말한다.

 

아래쪽으로 내려갈 수록 위쪽에 있는 것들보다 빠르다. 따라서 O(log n)이 O(n)보다 빠르다.

• O(n^2)
• O(n log n)
• O(n) - 선형 검색
• O(log n) - 이진 검색
• O(1)

 

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

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

역시 아래 목록과 같은 Big Ω 표기가 많이 사용됩니다.

• Ω(n^2)
• Ω(n log n)
• Ω(n) - 배열 안에 존재하는 값의 개수 세기
• Ω(log n)
• Ω(1) - 선형 검색, 이진 검색

Omega값과 Big-O값 중 어느 것이 좋아야 좋은 알고리즘일까요?

후자이다! 컴퓨터 과학자가 가장 걱정하는 부분은 최악의 경우에 프로그램이 어떻게 동작할지 또는 평균적으로 어떻게 동작하는지이다.

최선의 경우도 물론 좋지만, 이미 정렬된 입력값을 받아 매우 빠르게 정렬한다면, 누가 좋다고 생각할까? 물론 이경우는 예외적인 경우입니다. 

따라서 Omega는 알고리즘을 나타내는 좋은 도구이지만, Big-O와 상한선이 우리가 조금 더 신경 써볼 부분이다.