점근적 실행 시간

점근적 실행 시간이란 입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 $$\lim_{n \to \infty}$$함수의 실행 시간의 추이를 의미한다.

입력 데이터가 적어 실행 횟수가 아주 조금일 때는 어떤 알고리즘이든 다 빠르다. 그러니 데이터가 엄청나게 많아졌을 때(무한대) 누가 더 안 지치고 끝까지 잘 버티는지(추이) 따져보자.

점근적 실행 시간이란 어떤 동작의 실행 횟수가 무한할 때, 그 실행 시간의 추이를 보는 것을 말한다. 점근적 실행 시간을 볼 때는 초기 값은 무시하고 어떤 기준점 이상의 실행 횟수와 실행 시간의 추이만 관찰한다. 초반의 데이터를 무시하는 이유는 대개 그 값이 미래의 추이에는 영향을 미치지 않기 때문이다.

빅오(big-O)

점근적 실행 시간은 달리 말하면 시간 복잡도라 할 수 있다. 시간 복잡도(Time Complexity)의 사전적 정의는 어떤 알고리즘을 수행하는데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity)를 의미하며, 계산 복잡도를 표기하는 대표적인 방법이 바로 빅오다.

계산 복잡도라는 큰 개념 안에 시간 복잡도와 공간 복잡도가 있으며, 빅오는 이 둘 모두를 표기할 수 있는 대표적인 도구이다. 따라서 빅오는 시간적 복잡도를 나타내는 대표 단위로 사용할 수 있다.

시간과 공간의 관계

시간적 복잡도와 공간적 복잡도는 서로 맞교환(트레이드오프)되는 관계에 있다. 시간적 복잡도이 높으면 공간적 복잡도는 낮고, 반대로 시간적 복잡도가 낮으면 공간적 복잡도는 높다.

예를 들어 모든 계산을 미리 다 해서 메모리에 저장해두면, 시간은 거의 들지 않지만 메모리라는 공간은 많이 차지하게 된다. 반대로 메모리 공간을 아끼기 위해 필요할 때 마다 CPU로 계산을 하게되면, 공간은 거의 들지 않지만 CPU 계산 시간은 많이 들게 된다. 요즘은 메모리 용량이 넉넉하여 시간적 복잡도를 낮추는 방향으로 알고리즘을 구현하는 것이 권장되고 있다.

빅오 표기법의 종류

빅오 표기법은 O(수식)으로 나타낸다. 이 때 수식의 상수항과, 최대 지수가 아닌 항, 그리고 계수는 무시한다. 데이터가 무한히 커지면 $100n$이나 $n$이나 결국 직선의 기울기 차이일 뿐, 차수가 높은 $n^2$의 압도적인 증가량을 따라갈 수 없기 때문이다. 가장 빠른 알고리즘의 빅오 표기법부터 순서대로 나타내면 다음과 같다.

$O(1) < O(\log n) < \mathbf{O(n)} < O(n \log n) < O(n^2) < O(2^n) < O(n!)$

상한과 최악

… 한가지 중요한 점은 상한을 최악의 경우와 혼동하는 것인데, 빅오 표기법은 정확하게 쓰기에는 너무 길고 복잡한 함수를 ‘적당히 정확하게’ 표현하는 방법일 뿐, 최악의 경우/평균적인 경우의 시간 복잡도와는 아무런 관계가 없는 개념이라는 점에 유의해야한다.

빅오 표기법이 값을 나타낸다고 착각해서는 안된다. 즉, 빅오 표기법은 ‘알고리즘을 실행하는데 걸리는 가장 느린 시간’이 아니다.

빅오 표기법에서 중요한 것은 실행 횟수가 무한할 때 보여지는 시간의 추이이기 때문에, ‘알고리즘을 실행하는데 걸릴 수 있는 시간의 수학적 상한선’이라고 표현해야 맞다.

분할 상환 분석

시간 또는 메모리를 분석하는 알고리즘의 복잡도를 계산할 때, 알고리즘 전체를 보지 않고 최악의 경우만을 살펴보는 것은 지나치게 비관적이라는 이유로 분할 상환 분석 방법이 등장하는 계기가 됐다.

분할 상환 분석은 어쩌다 한 번 알고리즘 실행에 걸리는 시간이 오래 걸릴 때, 가끔 발생하는 비싼 비용을 평소의 저렴한 비용들에 평균적으로 배분하여 전체적인 효율을 계산하는 방식이다. (해당 값을 무시하는 것이 아니라 전체 합계에 포함시킨 뒤 평균을 냄)