알고리즘 | 알고리즘 표기법

✔ 학습목표

알고리즘 실행 시간의 상한과 하한을 표기할 수 있다.

 

알고리즘의 효율성

프로그램을 작성한 후에 실행하면 작업이 완료될 때까지 어느 정도 시간이 걸린다. 처리하는 데이터가 많아지고, 작업이 복잡해질수록 이 시간은 매우 중요하다. 그래서 알고리즘의 시간 효율성과 공간 효율성(메모리)을 나태 내기 위해 표기법을 사용한다. 두 가지 효율, 즉 시간 복잡도와 공간 복잡도를 나타내는 방법으로는 빅오(Big O), 빅오메가(big Ω),빅세타(big Θ) 표기법이 있다. 강의에서는 빅오와 빅오메가를 다룬다.

 

Big O

Big O는 알고리즘 실행 시간의 상한, 쉽게 말하자면 최악의 복잡도를 나타낸다. 복잡도를 비교하자면 다음과 같다.

 

앞서 배운 검색 알고리즘을 생각해보면 선형검색은 O(n), 이진 검색은 O(log n)이라 표기할 수 있다. 

 

* 알고리즘에서 Big O표기법을 볼 땐 데이터 양(n)이 충분히 크다고 가정한다. 그렇기 때문에 상수항이나 영향력이 없는 항은 무시한다(극한 개념을 생각해보자). 예를 들어 O(n/2)의 경우 n이 매우 커지면 1/2은 큰 의미가 없기 때문에 O(n)이라 본다.

 

Big Ω

Big Ω는 Big O와 반대로 실행 시간의 하한을 나타낸다. 예를 들어 n개의 항목 중 원하는 값을 찾고 싶을 때 선형 검색은 최대 n번 검색한다. 이를 O(n)이라 표기했다. 하지만 운이 좋다면 한 번만에 검색을 끝낼 수도 있다. 이를 Big Ω로 표기하면 Ω(1)이다. 이진검색에서도 마찬가지다.

 

선형 검색과 이진 검색을 Big O와 Big Ω로 정리하자면 다음과 같다.

 

	Big O	Big Ω
linear search	O(n)	O(log n)
Binary search	Ω(1)	Ω(1)

 

 

생각해보기

실행시간의 상한이 낮은 알고리즘이 더 좋을까, 하한이 낮은 알고리즘이 더 좋을까?

 

알고리즘을 비교할 때에는 상한을 보는 것이 좋다. 하한을 비교할 경우 실제 작동 시 얼마나 더 많은 시간이 걸릴지 모르기 때문이다. 반면 상한을 비교하면 해당 알고리즘은 실행 시간이 상한보다 항상 작거나 같다고 예측할 수 있다.

 

즉, 알고리즘의 효율성은 상한이 얼마나 낮은지로 본다.

---

 

이 글은 네이버 부스트 코스 David J. Malan(데이비드 J. 말란) 교수님의 모두를 위한 컴퓨터 과학(CS50 2019) 강의를 수강하고 작성한 글입니다. 본 강좌 내 실습에서는 CS50 Sandbox를 사용합니다.

 

모두를 위한 컴퓨터 과학 (CS50 2019)