본인 혼자서 공부한 내용이라 부정확한 부분이 있을 수 있음. 지적은 언제나 환영.

거두절미하고 바로 시작해보도록 하자. 복잡도란, 어떠한 알고리즘의 복잡한 정도를 나타내는 지표를 의미한다. 당연한 얘기라고?

물론 그렇다. 하지만 노련한 사람이라면, 알고리즘의 복잡성은 단순하게 표현되지 않는다는 것을 알것이다. 왜냐하면 어떠한 프로그램을 실행 하는데에 있어서 기준이 될 수 있는 것은 시간과 메모리, 즉 2가지 이기 때문이다.

그리고 시간에 대한 복잡도를 시간 복잡도, 메모리에 대한 복잡도를 공간 복잡도라고 한다. 이것들에 대해서 할 말이 많지만, 복잡도에 대한 이야기만 다룰려고 한다.

우선 복잡도를 이해하기 위해서는 "점근 표기법"을 먼저 이해해야 한다. 이는 어떠한 함수의 증감 추이를 지표로 나타내게 하는 도구이다. 눈썰미가 좋은 사람이라면, 아마 미분을 연상할 것이다. 실제로 미분에서 중요하게 쓰이는 극한은 복잡도와 중요한 관계성이 있다.

대표적으로 많이 쓰이는 표기법 3가지를 알아보도록 하자.

첫번째로, Big-O notation이다. 아마 수많은 코딩과 관련된 사이트에서 이것을 볼 수 있었을 것이다. 표기는 다음과 같다.

f(x) = O(g(x))

사실 다들 이 수식이 나오면 습관적으로 반복문이 몇 개가 중첩되어 있는지 확인한다. 그러나, 우리가 원하는 것은 이것의 정확한 의미를 아는 것이니 일단 프로그래밍과 관련된 지식은 잠시 잊도록 하자.

이것의 수학적 의미는 다음과 같다. 

{f : R→R | ∃c, ∃k, ∀x>k , f(x) <= cg(x)} (이때 함수의 정의역은 실수 집합 외에 자연수 집합도 가능하다.)

그래서 이게 뭐냐고? 정의역과 치역이 실수인 함수 f에 대하여, 어떤 상수 c와 k가 존재하고 모든 k보다 큰 x에 대해 f <= cg 일때

f(x) = O(g(x))라는 의미다. 여전히 무슨 소린지 모르겠다고? 솔직히 나도 문장으로 풀어놓고 보니 뭔 소린지 납득이 안 된다.

더 직관적으로 이해해보자. 어떤 상수 c가 존재하여 f <= cg 임은, g를 상수개만큼 더한 값이 f보다 항상 크거나 같음을 의미한다.

이를 시각적으로 이해하면,

파란색 그래프와 초록색 그래프에 대하여, 파란색 그래프에 곱해지는 상수가 항상 양수임을 가정한다면, 어느 시점에 대해서 항상 초록색 그래프보다 위에 있음을 추정 할 수 있을 것이다.

지금까지 설명 한 것을 쉽게 설명하자면, 내가 복잡도를 구하고 싶은 함수보다 항상 상수배가 크거나 같은 함수, 즉 내가 구하고 싶은 함수의 최악의 케이스, 또는 최악보다 더 안좋은 케이스이다.(함수가 커지면 복잡도가 큰 것과 같다)

한번 수식으로 이해해보도록 하자!. 

f = 1 + 2 + 3 . . . . + n이 있다고 하자. n이 양수인 자연수라는 가정하에, g = n + n + n . . . . + n = n^2 이다.

그런데, c가 1(이거나 더 큰 수) 이면 항상 f <= cg 가 된다. 즉, f(n) = O(g(n))로 표기할 수 있는 것이다.

그런데, 한가지 의문점이 들 수 있다. "f <= cg를 만족하는 g가 유일한가?"라는 것이다.

예를 들어, 위의 f에 대해 f <= cg 를 만족하는 g(n) 은 n*3, n^n, n!, 2^n 등 무수히 많다.

그러면 f = O(n*3), f =  O(n*n), f =  O(n!), f = O(2^n)이 다 가능하냐고?! 된다. 된다고.

하지만, 우리는 적합한 수준의 최악의 케이스를 찾아내는 것이 중요한 것이니, 위와 같이 생각하지는 말자.

이걸 간단하게 생각하는 방법은 다음과 같다. x → ∞ 일때 f의 증가 속도와 g의 증가 속도가 가장 비슷한 g를 선택하면 된다.

더욱 간단하게 생각하는 방법은, 그냥 직관적으로 f와 g가 비슷한 모양인걸 찾으면 된다.

이제 Big-Omega 와 Big-Theta에 대해서 알아보자. 

Big-Omega의 표기법은 다음과 같다.

f(x) = Ω(g(x))

얘는 위의 Big-O를 이해했다면 쉽다. 수학적으로는 다음과 같다.

{f : R→R | ∃c, ∃k, ∀x>k , f(x) >= cg(x)} 이번엔 f가 cg보다 크거나 같은 경우를 바뀌었다.

Big-O가 최악의 케이스를 판별하는 것이었으니, 얘는 최선의 케이스를 찾아준다고 생각 할 수 있다.

그리고 그게 맞다!

예를 들어, f(n) = n^n = n*n*n*n . . . . *n , g(n) = 1*2*3* . . . . *n = n! 이라면 cg <= f를 만족한다.

즉, n^n = Ω(n!) 이다.

마지막으로 Big-Theta가 남았다.

이것의 표기는 다음과 같다.

f(x) = θ(g(x))

이것의 수학적 정의는 다음과 같다.

{f : R→R | ∃c1, ∃c2, ∃k, ∀x>k , c1g(x) <=f(x) <= c2g(x)} 

이 친구에 대해서 앞에 친구들을 짬뽕한 느낌이 든다면, 그건 사실이다. 이것의 수학적 버전을 더 간략한 버전으로 만들어보자.

( f(x) = O(g(x) ) ∧ ( f(x) = Ω(g(x)) )

Big-O가 최악의 케이스, Big-Omega가 최선의 케이스라면 얘는 뭘까? 얘는 최선과 최악이 같은 경우, 즉 가장 일반화된, 가장 유용한 복잡도이다.

근데 왜 Big-O를 제일 많이 쓰는지는 모른다.

앞에서 Big-O를 설명할때 g(x)가 유일하지 않다고 했던 것 기억하는가? 이 친구의 경우 g(x) 자체의 상수계수가 1이라고 가정한다면, g(x)는 거의 항상 유일하다. 여기까지가 복잡도에 대한 설명의 끝이다.

마지막으로 가장 널리 쓰이는 몇가지 복잡도들을 소개하고 마치도록 하겠다.

O(1) : 상수복잡도

O(n^b) :  가장 흔히 보이는 복잡도. 특히 b = 1인 경우는 선형탐색의 시간복잡도로 유명하다.

O(a^n) :  증가율이 상당히 큰 복잡도. 특히 재귀함수의 시간복잡도로 유명하다.

O(log n) : 로그로 이루어진 복잡도. 이진 탐색의 시간복잡도로 유명하다.

O(nlog n) : 로그와 일반항이 곱해진 복잡도. 병합정렬의 시간복잡도로 유명하다.

O(n!) : 증가율이 매우 매우 큰 복잡도. 볼일은 거의 없다.

O(n^n) : 일반화된 복잡도 중 증가율이 가장 큰 복잡도. 마찬가지로 볼일은 많이 없다.

번외) O(∞) : 시간이 무한대인 복잡도. 메모리에서 이런 복잡도가 정의된다면, 컴퓨터가 터질지도 모른다....

진짜 볼일 없겠지만, 굳이 예를 들자면 어떤 배열에서 아무 수나 랜덤으로 선택해서 원하는 수가 발견되기 전까지 탐색 하는 알고리즘의 시간 복잡도가 이와 같다.

써놓고 보니까 무슨 헛소리 늘어놓은 것 같아서 마음에 좀 걸림;

;

위에서 말했듯 지적은 언제나 환영이고 긴 글 읽어줘서 고마워