[알고리즘] 빅오(Big-O) 표기법

어떠한 알고리즘을 작성했을 때 알고리즘의 성능은 어떻게 측정할 수 있을까? Big-O 표기법은 알고리즘의 수행 시간을 측정하여 성능을 표기하는 것이다. 그렇다면 Big-O 표기법을 사용하는 이유와 대략적으로 본인이 설계한 알고리즘의 시간 복잡도를 어떻게 구하는지 알아보자.

---

Big-O를 사용하는 이유

알고리즘의 성능을 측정하기 위해서 Big-O, Big-Ω, Big-θ 를 사용할 수 있다. 

• Big-Ω : 빅 오메가는 어떠한 알고리즘이 최적의 조건에서 실행될 때 사용할 수 있는 표기법이다. 예를 들어 이미 정렬되어 있는 숫자들에 퀵 정렬을 진행하면 N만큼의 시간 복잡도를 갖게되며 더 이상 빠르게 할 수 없을 것이다. 이처럼 알고리즘이 최선의 경우 수행되는 시간을 측정할 때 사용할 수 있다.
• Big-θ : 빅 세타는 빅 오와 빅 오메가의 평균을 의미한다. 보통 최악과 최선의 경우 자주 일어나지 않을 것이다. 어떠한 알고리즘의 평균 수행 시간을 빅 세타로 표기한다.
• Big-O : 빅 오메가는 최악의 경우 알고리즘의 수행 시간을 표기한다. 예를 들어 정렬되어있지 않은 숫자들에 퀵 정렬을 진행하면 최악의 경우 N^2만큼의 수행시간이 필요하다. 

위에서 각 표기법의 쓰임새를 파악하면 알고리즘을 Big-O를 통해 표기하는 이유를 알 수 있을 것이다. 모든 조건을 고려하여 알고리즘을 설계할 수 없을 것이다. 알고리즘은 컴퓨터의 성능과 입력되는 값 등에 의해 성능이 좌우된다. 따라서 최악의 경우를 생각하여 시간 복잡도를 구해야할 필요가 있기 때문에 Big-O를 사용한다.

 

Big-O의 특징

• 상수항은 무시한다. Big-O 표기법은 입력 데이터가 충분히 크다고 가정하기 때문에 O(2N) -> O(N)처럼 상수항은 무시하여 표기한다.
• 영향력이 없는 항은 무시한다. Big-O 표기법은 입력 데이터의 크기에 영향을 받기 때문에 가장 영향력이 큰 항을 제외한 나머지 항을 무시한다. O(N^2 + N) -> O(N^2)로 표기할 수 있다.