[자료구조] 빅오 표기법

빅오 표기법은 알고리즘에 필요한 단계 수를 나타내는 표기법이다.

O(N)(빅 오 N으로 읽는다.)

알고리즘에 N단계가 필요하다는 뜻이다.

O(1)(빅 오 1으로 읽는다.)

알고리즘에 1단계가 필요하다는 뜻이다. 배열 개수와 상관없이 한 단계만 필요하다. 연산에서의 읽기가 그렇다.

 

사이즈가 10이든 20이든 단계가 3인 알고리즘이 있다고 할 때 빅오 표기법을 어떻게 써야 할까? 위에서 적힌 대로라면 O(3)이 답인 것 같다. 하지만 실제로는 O(1)이다.

사이즈가 n일 때 단계가 2n인 알고리즘이 있다고 할 때 빅오 표기법을 어떻게 써야 할까? 위에서 적힌 대로라면 O(2N)이 답인 것 같다. 하지만 실제로는 O(N)이다.

 

빅오 표기법은 데이터가 늘어날 때 알고리즘 성능이 어떻게 바뀌는지를 뜻한다. 즉, 단계 N의 크기에 따라 알고리즘이 필요로 하는 단계가 변하는 정도를 나타낸다고 생각하면 된다.

 

예시로 O(N²)와 O(100,000 N)이 있다고 가정하자. N이 100,000 이하 일 때는 O(N²)가 O(100,000N)보다 작아 효율적일 수 있다. 하지만 N이 굉장히 크다고 가정하면 O(N²)은 O(100,000N)보다 커지게 되어 비효율적이 된다. 결국 O(N²)이 O(100,000N)보다 비효율적이다. 빅오 표기법은 이 알고리즘이 얼마정도의 단계를 가지는 지를 표기하는 것이 아닌 얼마나 효율적인지를 표기하는 것이다.

 

그럼 선형검색의 경우 최선의 경우 O(1)이고 최악의 경우 O(N)을 가지는 데 빅오 표기법을 사용하면 중간값인 O((N+1)/2)일까? 이 경우 빅오 표기법은 최악의 경우를 선택한다. 따라서 선형검색의 빅오 표기법은 O(N)이다.

 

이진검색은 어떠한가. 이는 1028일 때 10의 알고리즘 단계를 가지므로 O(logN)을 가진다. 이처럼 데이터가 두 배로 증가할 때마다 한 단계씩 증가하는 알고리즘을 O(logN)으로 표현한다.

 

효율적인 순서로 나타내면 O(1)>O(logN)>O(N) 순이다.

빅오 표기법