[📚누구나 자료구조와 알고리즘] 3. Big-O Notation : O(N), O(1), O(logN), O(N^2)

빅오 (Big-O)

컴퓨터 과학자들이 알고리즘의 효율성(시간복잡도)을 표기하기 위해 수학적 개념을 차용한 방법이 빅 오 표기법이다. 

[1] 원소가 N개일 때, 알고리즘에 최대 몇 단계가 필요할까?
[2] 원소가 N개일 때, 원소가 늘어남에 따라 알고리즘에 필요한 단계 수가 어떻게 늘어날까?  중요 !

빅오표기법은 결국 위의 질문에 대한 답을 O()의 괄호 내에 나타내는 것이다. 

 

O(N)

선형검색 알고리즘의 경우, 최악의 경우 원소 갯수 만큼의 단계가 필요하다. 예를 들어 100개의 원소 중 찾는 원소가 맨 마지막에 있거나, 없는 경우 100번을 모두 검색해야 하기 때문이다. 고로 선형검색을 위의 1번 질문에 대입해보자면 (= 원소가 N개일 때, 선형 검색에는 최대 몇 단계가 필요할까?) 답은 N 이다. 

 

이를 빅오표기법으로 나타내면 O(N) 이다. 빅 오 N, 차수 N, 오 N 등으로 읽을 수 있다. 정리하자면 선형검색 알고리즘을 빅오로 나타내면 O(N)이고, 이는 N개의 원소가 있을 때 최대 N 단계가 필요하다는 의미이다. O(N)인 알고리즘을 선형시간(linear time)을 갖는 알고리즘이라고 부르기도 한다. 

 

그런데 빅오에서 1번 질문 보다 더 중요한 것은 바로 2번 질문이다. 데이터가 늘어남에 따라 필요한 단계수가 어떻게 늘어나는지이다. O(N)알고리즘의 본질은 '데이터가 N개일 때, 단계도 N개' 가 아니라, '데이터와 단계 수는 비례관계' 라는 것이다. 그래서 빅오는 상수를 무시한다. 데이터가 하나 늘어날때마다 2단계씩 늘어나는 알고리즘이 있다고 할 때, 이를 빅오로 표기할 때 O(2N)라고 하지 않고 O(N) 이라고 한다. 

 

 

O(1)

이전 포스팅에서 다루었듯이, 배열의 읽기는 한 큐에 끝난다. 배열의 크기가 아무리 크더라도 한 번에 값을 읽을 수 있다. 원소의 갯수와 상관없이 항상 1단계면 끝나는 것이다. 즉 원소가 N일 때 1 단계면 끝이 난다. 

 

이를 빅오표기법으로 나타내면 O(1)이다. N이 얼마든 항상 상수 단계만 필요하기 때문에 O(1)인 알고리즘은 가장 빠른 알고리즘 유형으로 분류된다. O(1)알고리즘을 상수시간(constant time)을 갖는 알고리즘이라고 부르기도 한다. 

 

위에서 살펴본 것과 마찬가지로, 빅오에서 중요한 것은 데이터가 늘어남에 따라 필요한 단계수가 어떻게 늘어나는지이다. O(1) 알고리즘의 본질은 '데이터가 N개일 때, 단계도 1개' 가 아니라, '데이터가 늘어나더라도 단계 수가 일정한 관계' 이다. 따라서 배열의 읽기 처럼 항상 한 단계가 필요한 작업 뿐 아니라, 항상 3 단계가 걸리는 알고리즘, 항상 100단계가 걸리는 알고리즘 등과 같이, 상수 단계가 걸리는 알고리즘은 모두 O(1)이다. 3단계라고 O(3)이나, 100단계라고 O(100)이 아니라는 것을 명심하자. 원소의 수가 늘어나도 단계수가 일정하다면 모두 O(1)이다! 

 

 

O(logN)

이전 포스팅에서 다루었듯이, 이진 검색의 경우 데이터가 2배가 될 때 단계는 최대 1단계만 증가한다. 이를 빅오로 어떻게 나타낼까? 

 

빅오는 log를 사용해서 이를 나타낸다. 아래와 같이 간단하게 log를 설명할 수 있다. 2의 a제곱이 b라면, a는 log_2b로 나타낸다.

고등학교 수학에서 다루는 log (로가리즘)

예를 들어 log_2(8)은 2를 몇 제곱해야 8이 되는지를 표현한다. 2를 세번 곱해야 (2*2*2) 8이 되므로 log_2(8)은 3이다. 

 

이진 검색에 log를 접목하기 쉽게 다른 방식으로 이를 이해해보면 log_2(8)은 8을 2로 몇 번 나눠야 1이 될지를 표현한 것이다. 8/2/2/2 = 1 이므로(2로 세번 나눠야 1이 됨) log_2(8)는 3이다. 이진 검색도 원소가 하나 남을 때까지 전체 원소를 계속해서 반으로 나누면서 값을 찾아가므로 이진검색에서 원소의 갯수가 N일때 필요한 단계는 log_2(N) 으로 나타낸다. 단, 컴퓨터 과학에서는 log의 밑 2를 생략해서 log_2(N)을 logN으로 표기한다. 

 

따라서 이진검색을 빅오로 O(logN)으로 나타낼 수 있다. 원소가 하나만 남을 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계 수가 걸리는 것을 의미한다. 

 

O(N^2)

빅오에는 크게 네 개의 카테고리(종류)가 있다. 앞서 다룬 O(1), O(logN), O(N) 와 더불어 O(n^2) 카테고리가 있다. 빅오는 상수와 계수를 무시하기 때문에 (e.g. O(2)와 O(1)를 구분하지 않고 상수면 모두 O(1)로 표기, O(2N)과 O(N)을 구분하지 않고 비례하면 O(N)으로 표기) 빅오를 카테고리로 묶는다. 

 

이중 O(N^2)는 데이터가 증가할때마다 그 제곱만큼 단계가 증가하는 알고리즘으로, 이차 시간을 갖는 알고리즘으로도 불린다. 다음 포스팅에서 다룰 버블정렬이 이에 해당한다. 

 

 

빅오 카테고리와 효율성 비교 

지금까지 네 개의 빅오 카테고리 O(1), O(logN), O(N), O(n^2)를 간단하게 살펴보았다. 각 카테고리의 효율성을 아래 그래프로 확인해보면 아래와 같다. x축(가로축)은 원소의 수를 나타내고, y축(세로축)은 단계의 수를 나타낸다. 

 

다시 한번, 빅오는 '카테고리'로서, 차수만 고려하고 상수와 계수는 고려하지 않기 때문에 항상 이와 같지는 않다. 그래프의 '모양'만 중점적으로 보도록 하자. 빅오 카테고리끼리의 효율성을 비교할 때는 n이 충분히 클 때 & 최악의 시나리오를 상정한다는 것을 기억하자. 

 

예를 들어, 항상 100 단계가 걸리는 O(1) 알고리즘이 있다고 할때, 원소의 개수가 99개일때 까지는 선형검색(O(N))이 더 빠르지만, 100개 이후 부터 무한대까지는 O(1) 알고리즘이 항상 더 효율적이다. 따라서 O(1)이 O(N)보다 비효율적인 경우가 존재할 수도 있지만, '전반적으로' O(1)이 O(N)보다 효율적인 알고리즘이라고 할 수 있는 것이다. 

초록색 그래프: 항상 100단계가 걸리는 O(1)알고리즘

 

 

다음 포스팅에서는 버블 정렬과 O(N^2) 를 다루어 볼 예정이다!

 

---

참고문헌:  제이 웬그로우, 『누구나 자료구조와 알고리즘』, 심지현, 길벗, 2011

 

누구나 자료 구조와 알고리즘 - YES24