알고리즘 : 복잡도(Big O notation, Omega notation)

지난 글의 마지막에 코드의 복잡도를 알아보는 시간에, n, n+1, n+2, 2n, .... 은 O(n)에 속한다고 하였는데, O(n)은 일종의 "카테고리"라고 생각하시면 됩니다. 이렇게 묶은 이유는 코드에 따라서 복잡도 카테고리가 달라지기 때문입니다.

이러한 복잡도 카테고리는

• O(1) : constant complexity
• O(loglogn)
• O(logn) : logarithmic complexity
• O(n) : linear complexity
• O(nlogn)
• O(n²) : quadratic complexity
• O(n³) : cubic complexity
• O(2ⁿ) : exponential complexity

으로 나뉘어 집니다.

 

O(1)은 입력한 자료 수에 무관하게 1번만 연산되는 알고리즘입니다. for 루프나 함수 호출이 없이 단순한 코드라면 시간 복잡도가 O(1)이 되겠죠. 나중에 소개 할 Hashing이 여기 포함됩니다.

 

이제부턴 입력의 크기 n을 2의 32승이라는 어마어마한 수라고 가정해 보겠습니다.

O(logn)은 log2³² = 32가 되고, O(loglogn)은 이 logn 값에 log를 한번 더 씌워 버린겁니다.  log32 = 5가 되겠죠.

여기서 O(logn)의 시간 복잡도를 갖는 알고리즘에는 이진 검색이 포함됩니다.

 

O(n)은 말 그대로 2³²이며, 단순 scan을 할 때 O(n)의 시간 복잡도를 갖습니다.

 

O(nlogn)은 2³² * 32가 되며, 병합정렬(Merge Sort), 퀵 정렬(Quick Sort)이 이 시간 복잡도를 갖습니다.

 

O(n²)은 2³² * 2³²이고, 이중 루프, 삽입정렬(Insertion Sort), 선택정렬(Selection Sort)이 이 시간 복잡도를 갖습니다.

 

O(n³)은 2³² * 2³² * 2³²이고, 삼중 루프가 이 시간 복잡도를 갖습니다. 행렬곱에 삼중 for문을 사용하니까 행렬곱이 O(n³)의 시간 복잡도를 갖는다고 생각하면 되겠죠.

 

그런데 O(2ⁿ)은 이전까지의 복잡도랑은 차원이 다릅니다.

2³²가 대략 42억인데, 2의 42억승이라니 정말 상상조차 못할 숫자이죠.

이렇게 천문학적인 복잡도가 나오는 알고리즘을 exponential 하다고 합니다.

위에 소개한 O(1)부터 O(n³) 까지, 그나마 실행이라도 되겠다 싶은 알고리즘은 polynomial 하다고 합니다.

---

알고리즘 설계의 최종 목적은 이 복잡도에 있습니다.

 

여기 개발자 두 명이 같은 기능을 하는 코드를 짰습니다.

한명은 O(logn)을 갖는 코드, 다른 한명은 O(n²)를 갖는 코드룰 짰다면, 당연히 O(logn)의 알고리즘을 설계한 개발자의 코드가 선택되겠죠. 전자의 개발자는 개발자다운 대접을 받으면서 네카라쿠배 옮겨다닌다는 소리도 농담 반 진담 반으로 다들 합니다.

 

위의 글 처럼 월클 개발자가 되기 위해 내 코드의 복잡도를 줄이려고 공부하는 것도 있지만, 우리 뿐만이 아닌 전세계 모든 개발자들은 코드의 복잡도를 줄여나가서 실행 시간의 한계를 깨기 위한 노력을 끊임없이 하고 있습니다. 

---

아까 말했듯 n+1, n+2, 2n... 등은 O(n) 카테고리에 속합니다.

그렇다면 이걸 눈대중으로 한 것도 아닐테고 어떻게 여러 카테고리로 나눴을까요?

정답은 Big O 표기법(Big O notation)이라는 방법에 있습니다.

주어진 복잡도 함수 f(n)에 대해서 g(n) ∈ O(f(n)) 이면 다음을 만족한다.
n ≥ N인 모든 정수 n에 대해서 g(n) ≤ c * f(n)이 성립하는 실수 c(> 0)와 음이 아닌 정수 N이 존재한다.

g(n) 을 n+1 이라고 한다면, n+1 ∈ O(n) 이라고 할 수 있겠죠.

그렇다면 그 결과를 도출할 수 있는 부등식인 g(n) ≤ c * f(n)가 무슨 소리인지 알아보겠습니다.

위의 그래프에서, n이 N0 이상일 때부터 g(n)은 cf(n)을 넘지 못합니다.

n이 아무리 높아져봤자 g(n)은 붉은색 칠 한 부분을 절대 넘지 못하는데요, 이 때 cf(n)을 tight upper bound라고 하며, "이 알고리즘은 이 시간을 넘지 않는다", "아무리 늦어도 이 시간이면 된다" 라는 의미입니다. "최악의 경우 이 시간이면 된다" 가 적절한 표현이겠네요.

그렇다면, "c와 N0이 어떠한 값일 때 g(n) ∈ O(f(n)) 이다"라고 말할 수 있습니다.

 

c와 N0 값을 구해야 이렇게 당당히 말할 수 있겠죠? 그렇다면 그 과정을 알아보겠습니다.

1. 부등식을 세워라. 
2. 부등식을 만족하는 c와 N0을 선택하라.

예를 들어, g(n) = n²+10n 이라고 합시다.

그렇다면 n²+10n의 tight upper bound는 c*n²이 되겠죠?

물론 n²+10n는 c*n³도 절대 넘지 못합니다. 그러나 그렇게 표현 해 버리면 이 알고리즘의 특성을 알 수 없기에 tight upper bound를 사용해야 합니다.

 

그렇게 n²+10n ≤ c*n² 의 부등식을 세웠다면, 이 부등식을 만족하는 c와 N0을 선택하면 됩니다.

n²+10n는 n이 일정 숫자 이상일 때 2n²을 이길 수 없으므로, c=2를 선택합니다.

n²+10n ≤ 2n²는 n=10 이상일 때부터 성립하며, 이 때 10을 N0이라고 합니다.

따라서 c=2, N0=10 일 때 n²+10n ∈ O(n²) 이 성립합니다.

---

g(n)의 상한이 있다면, 하한도 있지 않을까요?그런 하한을 나타내는 표기법을 Ω 표기법(Omega notation)이라고 합니다.

주어진 복잡도 함수 f(n)에 대해서 g(n) ∈ Ω(f(n)) 이면 다음을 만족한다.
n ≥ N인 모든 정수 n에 대해서 g(n) ≥ c * f(n)이 성립하는 실수 c(> 0)와 음이 아닌 정수 N이 존재한다.

Big O 표기법과는 달리, n이 N0 이상일 때부터 cf(n)은 g(n)을 넘지 못합니다.이런 하한을 tight lower bound 라고 하며, "이 알고리즘의 시간은 f(n)보다 더 빠를 순 없다" "최소한 이만한 시간은 걸린다" 라는 의미입니다.예를 들자면 모든 정렬 알고리즘은 Ω(n)인데, n개의 데이터를 정렬하려면 n개 모두를 한번쯤은 읽어야 하므로 무조건 Ω(n) 이상의 시간이 걸립니다.

---

그렇다면 Big O 표기법이나 Ω 표기법에서, 그래프가 다음과 같다면 어떻게 될까요?

이런 경우에는, c값을 정한 후 처음 얻는 N0의 값이 N1인데, n의 값을 더 높이면 g(n) ≥ cf(n)이 되는 구간이 생기므로,

최종적으로 g(n) ≤ cf(n)이 성립하는 N2를 N0의 값으로 선택해야 합니다.

---

마지막으로 Big O 표기법과 Ω 표기법을 모두 만족할 때 사용하는 것이 Θ 표기법(Big-Theta notation) 입니다.

g(n)이 c2*f(n)을 상한, c1*f(n)을 하한으로 가질 때, g(n) ∈ Θ(f(n)) 이라고 표현할 수 있습니다.

원래 시간 복잡도를 표현할 때 Θ(n) 형식을 쓰지만, 편의상 O(n) 꼴로 표기하는 경우가 많습니다.

 

 

<틀린 점이 있다면 지적 부탁드립니다. 감사합니다.>