알고리즘의 시간 복잡도와 빅오 표기법

알고리즘의 시간 복잡도란?

알고리즘의 시간 복잡도는 특정 입력(n)에 대해 알고리즘이 얼마나 오래 걸리는지를 의미한다. 즉, 해당 알고리즘으로 어떤 기능을 수행하는데, 필요한 연산의 횟수로 볼 수 있다. 따라서 동일한 기능을 수행하며 동일한 메모리를 소요하는 알고리즘이 두 개가 있을 때 시간 복잡도가 더 낮은 알고리즘이 '더 나은' 알고리즘이라고 볼 수 있다. 이때 메모리를 더 많이 사용함으로써 시간을 줄이는 메모이제이션(Memoization) 기법도 존재한다.

 

 

빅오 표기법

이러한 알고리즘의 시간복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다. (이때 O는 on the order of, "~만큼의 정도로 커지는"의 약자이다.) 빅오는 알고리즘 실행 시간의 상한(최악의 경우)을 나타낸다. 소프트웨어 엔지니어가 가장 걱정하는 부분은 '최악의 경우'에 프로그램이 어떻게 동작하는지, 또는 '평균적으로' 어떻게 동작하는지이므로 Big O 값이 Big Ω보다 중요하다.

 

예를 들어, 단일 for문을 통해 일차원 배열을 탐색하는 경우 배열의 길이가 N이라고 할 때 배열의 요소를 하나씩 찾게 되므로(선형 검색) 시간 복잡도는 N에 비례한다. 따라서 이러한 알고리즘의 빅오 표기법은 O(N)이라고 할 수 있다. 또한, 이중 for문이라면 O(N^2), 1 + 1처럼 단순히 더하기 연산 한 번 수행하는 알고리즘의 빅오 표기법은 O(1)이라고 할 수 있다.

 

빅오 표기법은 알고리즘의 성능을 수학적으로 표현해주는 표기법이다. 이때 알고리즘의 실제 실행 시간을 표시하는 거라기 보다 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 게 목표로 상수와 같이 고정되어 있는 숫자들은 모두 1이 된다. 예를 들어, O(2n)의 알고리즘은 O(n) 아울러 데이터 증가와 상관없이 항상 일정한 속도로 실행되는 작업들 역시 마찬가지로 1이 된다.

 

※ 빅오메가(Big Ω)란?

Big O와 반대로 Big Ω는 알고리즘 실행 시간의 하한(최선의 경우)을 나타낸다. 예를 들어, 선형 검색에서는 n개의 항목이 있을 때 최대 n번의 검색을 해야하므로 상한이 O(n)이 되지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1)이 된다.

 

 

알고리즘별 빅오 표기법

각각의 검색 알고리즘에 따라 빅오 표기법은 다음과 같이 나타낼 수 있다.

 

Big O 표기법	명칭	알고리즘 예시
O(1)	상수 시간(constant time)	배열 인덱스 검색, Hashmap key를 통한 검색, ...
O(N)	선형 시간(linear time)	단일 for문, 선형 탐색, ...
O(N^2)	이차 시간(quadratic time)	2중 for문, 버블 정렬, 선택 정렬, ...
O(2^n)	지수 시간(exponential time)	피보나치 수열(재귀 구현), ...
O(logn)	로그 시간(log time)	이진 탐색, ...
O(N logN)	로그 선형 시간	병합 정렬, ...

 

알고리즘 시간 복잡도가 O(N^K) 일 때 이를 '다항 시간'(이차 시간, 삼차 시간 등)이라고 하는데, 데이터가 많아질수록 알고즘이 동작하는데 걸리는 시간이 기하급수적으로 증가하기 때문에 유의해야 한다.

 

또한 두 알고리즘이 빅오 표기법으로 표시한 시간 복잡도가 같을지라도 내부 로직, 차수가 낮은 항의 영향 등에 따라 실제 수행되는 연산 횟수(소요 시간)이 다를 수 있다.

 

 

빅오 표기법의 활용 예시

백준, 프로그래머스 등 알고리즘 문제를 풀면 시간 제한이 보통 1초로 되어있는 경우가 많이 있어 데이터의 최대 개수에 대해서도 1초 이내 알고리즘이 동작이 완료되도록 탐색기반을 설계할 필요가 있다. 다음은 시간 제한 1초를 충족시키기 위한 알고리즘의 빅오 표기법에 대한 예시이다.

 

데이터(N)의 범위	빅오 표기법
0 ~ 500	O(N^3)
0 ~ 2,000	O(N^2)
0 ~ 100,000	O(NlogN)
0 ~ 10,000,000	O(N)

 

 

참고자료

• 부스트코스 모두를 위한 컴퓨터과학
• 한빛미디어 출판 이것이 취업을 위한 코딩테스트다(with 파이썬)
• https://www.youtube.com/watch?v=6Iq5iMCVsXA