[Algorithm] 시간복잡도에 대해서 (big-O, Ω, θ 표기법)

컴퓨터 알고리즘을 공부하다 보면 시간복잡도에 대해서 당연히 많이 마주하게 되고, 보통은 O(n)처럼 Big-O 표기법을 사용한다. 하지만 시간 복잡도를 나타내는 방법에는 위 세 가지가 있다는 것을 알게 되었다. 이를 간단하게 정리해보려고 한다.

시간복잡도

간단하게 시간복잡도를 살펴보면 아래와 같이 정수 n을 받으면 0부터 n까지 더해주는 함수가 있다고 해보자.

func solution(n: Int) -> Int {
    var result = 0
    for i in 0..<n {
        result += i
    }
    return result
}

 
이 코드가 실행되는데 걸리는 시간은 어떻게 계산할 수 있을까? n번 반복을 하기 때문에 an+b의 시간이 걸린다고 할 수 있다. 왜냐하면 상수를 선언하는데도 어느 정도 시간이 걸릴 것이고, return 하는데도 어느 정도의 시간이 걸릴 것이다. 하지만 여기서 a와 b는 아주아주 작은 수이므로 n만 생각해 주면 된다. 왜냐하면 우리가 시간 복잡도를 고려할 경우는 n이 엄청 엄청 커졌을 때이기 때문이다. 여기서의 시간복잡도는 θ(n)으로 볼 수 있다. 엥 갑자기 왜 θ? 일부로 써봤다. 이제 O, Ω, θ의 차이점에 대해서 알아보도록 하자.
 

Big-O 표기법

시간의 상한을 나타낸다. asymptotic upper bound(점근적 상한)이라고 표현하는것이 더 이해하기 쉬울 수 있겠다. 이론상으로만 보면 위의 코드의 시간복잡도를 Big-O 표기법으로 나타낸다면 O(n^2)여도 된다는 뜻이다.
 

Big-Ω 표기법

시간의 하한을 나타낸다. asymptotic lower bound(점근적 하한)이라고 설명된다. 따라서 위의 코드는 Big-Ω 표기법으로는 Ω(1)여도 된다.
 

Big-θ 표기법

살짝 복잡해지는데... 정의는 아래와 같다. Big-O, Big-Ω 표기법으로 해도 만족하는 식을 Big-θ 표기법으로 나타낼 수 있다. 그래서 사실 위의 코드의 시간복잡도를 θ(n)으로 표시해 봤다. Big-θ 표기법이 사실은 실제 시간복잡도에 가장 가까운 식을 표현하는 표기법이라고도 할 수 있겠다.

Let f(n) define running time of an algorithm. 
f(n) is said to be Θ(g(n)) if f(n) is O(g(n)) and f(n) is Ω(g(n))

0 <= f(n) <= C1g(n) for n >= n0
0 <= C2g(n) <= f(n) for n >= n0

 

실제로 쓰는 것은 Big-O 표기법!

실제로는 Big-O 표기법을 주로 사용한다. 결국 위의 코드는 O(n)으로 표현될 수 있고, 아무도 O(n^2)으로도 표현되는데요? 딴지걸지 않기로 약속한듯... n이 커질수록 시간복잡도는 아래와 같이 커지게 된다. 따라서 시간이 많이 걸리는 for문을 중첩하여 사용한다거나, n! 의 시간복잡도를 가지는 조합 등(보통 조합을 사용하여 답을 구하는 경우는 모든 경우의 수를 체크할때)을 최대한 덜 사용하는 알고리즘을 사용해야 된다.

출처: 위키피디아