* 시간 복잡도를 처음 접한다면 아래 글은 이해하기 어려울 수 있습니다.
시간 복잡도
같은 목적지를 향해 가는 길이 여러 갈래일 때 우리는 더 빠르게 도착하는 길을 찾는다. 마찬가지로 동일한 목적을 가지는 기능을 여러 알고리즘으로 구현했을 때 그것들의 효율성을 비교하기 위해 시간 복잡도를 사용한다. 당연히 더 오래 걸리면 더 안 좋다. 알고리즘A의 시간복잡도가 O(n)이고 알고리즘B의 시간복잡도가 O(1)이면 우리는 알고리즘 B를 사용할 것이다.
빅오, 빅오메가, 빅세타
시간 복잡도를 표기하기 위한 방법 중 빅오, 빅오메가, 빅세타가 있다.
빅오(Big-O, O)
특정 알고리즘의 최악의 시간복잡도를 나타낸다. 즉, 알고리즘의 수행 시간이 가장 오래 걸리는 경우를 표기한다. 예를 들어 O(n)의 경우 실제 소요시간이 1, logn 등 n보다 작을 수 있지만, n보다 큰 n^2과 같은 경우는 없다.
엄밀한 정의는 아니지만 조금 수학적으로 표현하면, 위 그림에서 n이 n0보다 클 때, f(n)은 항상 g(n) 보다 작거나 같다. 우리는 알고리즘을 구현할 때 항상 최악의 수를 생각해야 하기 때문에 빅오는 셋 중 가장 많이 쓰는 표현법이다.
빅오메가(Big-Omega,Ω)
빅오와 반대로 특정 알고리즘의 최선의 시간 복잡도를 나타낸다. 즉, 알고리즘의 수행 시간이 가장 짧은 경우를 표기한다. 예를 들어 Ω(n)의 경우 실제 소요시간이 n^2과 같이 n보다 클 수 있지만, n보다 작은 1, logn과 같은 경우는 없다.
위 그림에서 n이 n0보다 클 때, f는 항상 g보다 크거나 같다. 우리는 알고리즘을 구현할 때 항상 최악의 수를 고려하지 최선의 수를 고려할 일은 잘 없다. 그래서 가장 사용하지 않는 표현법이다.
빅세타(Big-Theta, Θ)
특정 알고리즘의 범위를 나타낸다. 다시 말해 알고리즘의 수행 시간이 A보다는 크고 B보다는 작다고 표기하는 표현법이다.
위 그림에서 n이 n0보다 클 때, f는 항상 g1보다 크거나 같고 g2보다 작거나 같다. 빅세타는 일종의 평균값과 유사한데, 평균값이 높은 정확성을 얻기 위해서는 많은 경우의 수가 필요하다. 또한 때로는 구하기 어려울 수도 있으며 공학적인 신뢰도는 평균보다는 최악의 값이 더 높기 때문에 빅세타보다 빅오를 가장 흔하게 사용한다.