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

이 글은 누구나 자료 구조와 알고리즘(저자 : 제이 웬그로우)의 내용을 개인적으로 정리하는 글임을 알립니다.

---

빅 오

단순히 어떤 알고리즘을 22단계 알고리즘, 400단계 알고리즘이라고 표시할 수 없다.

알고리즘에 필요한 단계 수를 하나의 수로 못 박을 수 없기 때문이다.

예를 들어 선형 검색에는 배열의 원소 수만큼의 단계가 필요하므로 배열에 따라 필요한 단계 수가 다르다.

 

선형 검색의 효율성을 정량화하는 보다 효과적인 방법은 배열에 N개의 원소가 있을 때 선형 검색에 N단계가 필요하다고 표현한다.

 

빅 오 표기법을 사용해 주어진 알고리즘의 효율성을 쉽게 분류하고 이해시킬 수 있다.

• 선형 검색 알고리즘을 빅 오로 나타내면 O(N)이다.
• O(N)은 알고리즘에 N단계가 필요하다는 뜻이다.
• 원소가 N개인 배열의 읽기는 딱 한 단계가 필요하므로 O(1)이다.
• 원소가 N개인 배열의 검색에는 N개의 단계가 필요하다.

배열의 읽기는 원소가 몇개이든 간에 한 단계만 거치면 되기 때문에 O(1)로 표기하고, O(1)은 가장 빠른 알고리즘으로 분류된다.

데이터가 늘어나도 O(1) 알고리즘의 단계 수는 증가하지 않는다. 

N이 얼마든 항상 상수 단계만 필요하다. 그래서 O(1) 알고리즘을 상수 시간을 갖는 알고리즘이라고도 표현한다.

데이터가 몇 개든 항상 3단계 걸리는 알고리즘은 O(3)??

빅 오의 본질은 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 뜻한다.
빅 오는 단순히 알고리즘에 필요한 단계수만 알려주지 않는다.
데이터가 늘어날 때 단계 수가 어떻게 증가하는지 설명한다.

이러한 관점에서 보면 O(1)이든 O(3)이든 별로 중요하지 않다.

두 알고리즘 모두 데이터 증가에 영향을 받지 않는, 즉 단계수가 변하지 않는 유형이므로 본질적으로 같은 알고리즘 유형이다.

따라서 O(3)이든 O(6)이든 O(1000)이든 모두 O(1)로 표기한다.

 

빅 오의 본질 더 파고들기

데이터 크기에 상관없이 항상 100단계가 걸리는 알고리즘과 O(N)인 알고리즘이 있다고 가정하자.

• 100보다 큰 모든 배열에서는 O(N)의 알고리즘에 더 많은 단계가 걸린다.
• 즉, 0~100개의 데이터를 가진 데이터 집합보다 101~무한대까지 데이터를 가진 데이터 집합이 더 많기 때문에  O(1)알고리즘에 실제로 몇 단계가 걸리든 O(N)이 전반적으로 O(1)보다 덜 효율적이라 할 수 있다.
• 항상 백만 단계가 걸리는 O(1) 알고리즘이라도 마찬가지이다. 데이터가 증가할수록 O(N)이 O(1)보다 덜 효율적인 어떤 지점에 반드시 다다르게 되며, 이 지점부터 데이터 양이 무한대로 갈 때까지 바뀌지 않는다.

 

 

같은 알고리즘, 다른 시나리오

선형 검색이 항상 O(N)은 아니다.

선형 검색의 효율성은 최선의 시나리오에선 O(1), 최악의 시나리오에서는 O(N)이다.

별도로 명시하지 않는 한 빅 오 표기법은 일반적으로 최악의 시나리오를 의미한다.

이는 비관적인 접근이 유용한 도구일 수 있기 때문이다.

최악의 시나리오에서 알고리즘이 얼마나 비효율적인지 정확히 알면 최악을 대비함과 동시에 알고리즘의 선택에 중요한 영향을 미칠 수 있다.

 

O(log N)

이진 검색을 빅 오 표기법의 관점에서는 데이터가 커질수록 단계 수가 늘어나므로 이진 검색은 O(1)이라 표현할 수 없다.

또한, 검색하고 있는 원소 수보다 단계수가 훨씬 적으므로 O(N)의 부류에도 맞지 않는다.

 

빅 오는 이진 검색의 시간 복잡도를 O(log N)으로 표현한다. (로그의 밑은 10이 아니라 2가 생략된 것이다.)

이러한 유형의 알고리즘을 로그 시간의 시간 복잡도라고 말한다.

 

O(log N)은 데이터가 두 배로 증가할 때마다 한 단계식 늘어나는 알고리즘을 설명하는 빅 오의 방법이다.

O(1), O(N), O(log N)을 그래프로 비교하면 아래와 같다.

 

로가리즘
로그는 로가리즘(logarithm)의 줄임말이다.
로가리즘은 지수와 역의 관계다.

2^3 은 2 x 2 x 2와 동치로서 값이 8이다.
log₂8은 2³의 역이다. 즉, 2를 몇 번 곱해야 8을 얻을 수 있는지를 뜻한다.
2를 세 번 곱해야 8이 나오므로 log₂8 = 3이다.

log₂8을 다른 방식으로 설명하면, 1이 될 때까지 8을 2로 계속해서 나눌 때 등식에 얼마나 많은 2가 등장하는지를 나타낸다.
즉 1이 나올때 까지 8을 2로 몇 번 나눠야 하는지이다.
8 / 2 / 2 / 2 = 1, 총 3번이다.

 

O(log N)의 해석

O(log N)은 log₂N을 줄여 부르는 말이다.

O(log₂N)은 데이터 원소가 N개 있을 때 알고리즘에 log₂N단계가 걸린다는 의미다.

원소가 8개 있으면 log₂8 = 3이므로 3단계가 걸린다.

바꿔 말해 원소 8개를 절반으로 계속해서 나누면 원소가 하나 남을 때까지 3단계가 걸릴 것이다.

이진 검색이 정확히 이렇게 동작한다.

즉, O(logN)은 원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계수가 걸린다는 뜻이다.