자구/Big_O란?

1. 개요

어떤 도구든 사용하기 전에 이 도구가 얼마나 효과적인지를 알아야 다른 도구와 비교를 해서 도구 선택을 잘 할 수 있다. 알고리즘도 마찬가지다. 따라서 알고리즘 성능을 아는 것은 중요하다. 점근적 알고리즘 분석(asymptotic algorithm analysis)이란 어떤 알고리즘의 성능(얼마나 빨리 과제를 수행하느냐 == 시간 복잡도)을 분석할 때 사용되는 방법이다. 빅-오 표기법은 점근적 표기법의 대표적인 방법인데, 걸리는 시간의 상한선을 나타낸다. 빅-오와 다른 표기법들에 대해 알아보자.

2. 왜 쓰는가?

점근적 알고리즘의 시간 복잡도를 계산하고 싶을 때 사용하는데, 빅-오는 시간복잡도의 상한선을 나타낸다. 알고리즘의 시간복잡도를 측정할 때에는 최악의 경우 / 평균적인 경우 두 가지를 놓고 계산한다. 주로 최악의 경우를 계산한다. 최선의 경우는 계산하지 않는다. 데이터가 최선의 경우로 배열되어 있는 경우를 가정하는 건 별 쓸모가 없기 때문이다.

빅-오(Big-O)는 성능이 "최소한 이 정도 이상이다"를 알려준다. 비용의 점근적 상한선(Asymptotic upper bound)을 가리키는데, 비용(걸리는 시간)이 아무리 커봤자 이만큼을 넘지 못한다고 알려주는 역할이다.

빅-오를 비교하면 알고리즘의 대략적인 성능을 알 수 있으므로, 알고리즘들끼리 성능을 비교할 때 지표가 된다.

3. 어떻게 빅-오를 찾는가?

어떻게 Big-O를 찾는가? 어떤 자료구조에서 특정 데이터를 탐색한다고 해보자.

우선 찾고자 하는 행위에서 핵심이 되는 연산이 무엇인지 찾는다. 탐색 알고리즘의 경우 찾고자 하는 데이터(타겟이라고 하자)의 값이 현재 인덱스가 가리키는 데이터 값과 일치하는지, 즉 target == index 인지 비교하는 연산이 핵심이다.

순차 탐색(Sequential Search or Linear Search)과 이진 탐색(Binary Search) 알고리즘을 비교해보자. 순차 탐색의 경우 데이터를 앞에서부터 차례차례 찾아야 하므로, n개의 데이터가 있다면, 찾으려는 데이터가 없는 최악의 경우 비교 연산을 n회 진행해야 한다. 따라서 빅-오는 \(O(n)\)이 된다.
반면 이진 탐색의 경우, 데이터가 정렬되어 있어야 한다는 제한이 있지만 훨씬 빠르게 데이터를 탐색할 수 있다. 한 번 비교연산을 진행할 때마다 그 횟수가 절반으로 줄어들기 때문에 최악의 경우에도 \(log_2n\)번을 진행한다. 따라서 빅-오는 \(log_2n\)이 된다.

\(n\)과 \(log_2n\)의 그래프를 그려보면 이진 탐색 알고리즘에 걸리는 시간이 순차 탐색보다 훨씬 완만하게 증가함을 확인할 수 있다. 따라서 정렬만 되어 있다면 이진 탐색 알고리즘을 사용하는 편이 훨씬 효율적이고 현명하다는 것을 알 수 있다.

4. 현실적으로 사용하기 어려운 알고리즘

만약 빅-오가 \(n^2\) 이상이라면, 이는 현실적으로 사용하기 어려운 알고리즘으로 생각된다. 너무 느려서 프로그램 한 번 돌리는 데 한 세월 지나갈 수도 있는 것이다. 당연히 이를 넘는 \(n^3\)이나 \(n!\), \(2^n\) 등의 알고리즘도 현실적으로 사용할 수 없다.