안녕하세요. 이번 시간에는 시간의 복잡도를 설명하겠습니다. 시간의 복잡도는 알고리즘을 수행하는 데 평균적으로, 또는 최악의 경우 얼마만큼의 시간이 걸리는 지 보여줍니다. 반대의 개념으로 공간의 복잡도도 있는데, 알고리즘이 얼마만큼의 메모리를 잡아먹는 지 보여줍니다. 보통은 시간의 복잡도를 더 중요하게 여기기 때문에 이번 강좌에서는 시간의 복잡도를 주로 다루겠습니다. 그리고 그냥 복잡도라고 해도 시간의 복잡도라고 생각하시면 편할 것 같습니다.
복잡도를 계산하는 과정은 정말 어려우니 여기서는 생략하겠습니다. 대학교에서 배우는데 학원에서는 가르쳐주지 않습니다. 우리는 간단히 복잡도를 표시하는 방법과 그것이 시사하는 바를 알아봅시다.
복잡도는 주로 빅오 표기법을 사용해서 나타냅니다. 최악의 경우 걸리는 시간을 표기하는 방법인데요. 이것을 분석할 때, 아무리 최악이더라도 이 정도는 넘지 않겠구나라고 생각하면 됩니다. 빅오의 순서는 다음과 같습니다. ^는 제곱을 의미합니다. N^3는 N의 세제곱입니다.
O(1),O(logN), O(N), O(NlogN), O(N^2), O(N^3), ..., O(2^N), O(N!)
모두 어떤 동작을 수행할 때 최악의 경우 걸리는 시간을 의미합니다. 왼쪽으로 갈수록 좋은 알고리즘이고, 오른쪽으로 갈수록 안 좋은 알고리즘입니다. 보통 NlogN까지를 괜찮다고 생각하고, N^2부터는 안 좋다고 생각합니다. 최악의 경우를 뜻하기 때문에 최선의 경우는 O(1)도 나올 수 있습니다. 즉 O(N^2)은 O(1)부터 O(NlogN)까지를 모두 포함하고 있습니다.
지난 시간의 삽입 정렬은 O(N^2)입니다. O(N^2)가 안 좋다고 했지만 사용하는 이유는 알고리즘 자체가 간단하기 때문입니다. 그리고 30개 이하의 숫자의 경우에는 괜찮은 성능을 보입니다. 대신 그 이상일 경우에는 다른 정렬 알고리즘을 사용해야 합니다.
간단하게 빅오의 차이가 성능을 얼마나 좌우하는 지 알아볼까요? 숫자가 작을 수록 시간이 덜 걸리는 겁니다.
O(N), O(NlogN), O(N^2), O(2^N)
N=1 1 0 1 2
N=10 10 23 100 1024
N=100 100 460 10000 0이 30개
하나당 0.01초가 걸린다고 생각해도 만약 100개를 정렬하는 경우, O(NlogN)은 4.6초로 괜찮다고 생각할 수 있지만, O(N^2)은 100초가 걸립니다. O(2^N)은.... 컴퓨터가 펑~ 할겁니다. (사실 컴퓨터가 터지거나 하진 않으니 걱정하지 않으셔도 됩니다)
기울기가 가파를수록 성능이 안 좋습니다. NlogN과 N^2의 차이가 보이시나요?
세타 표기법도 있습니다. 평균의 경우를 나타낸다고 생각하시면 됩니다. 최악의 경우가 잘 일어나지 않는 알고리즘의 경우는 최악의 경우를 제외하고 세타 표기법으로 성능을 파악하는 게 좀 더 도움이 됩니다. 빅오 표기법과 비슷하지만 O만 Θ로 바꾸면 됩니다. 역시 Θ(N^2)부터는 안 좋다고 여겨집니다. 평균적인 경우이기 때문에 Θ(N^2)은 최악의 경우나 최선의 경우 모두 Θ(N^2)입니다. O 표기법의 경우에는 최선의 경우 O(1)도 나올 수 있다는 점과는 다르죠.
빅오 표기법과 세타 표기법을 기억해두세요! 다음 시간에는 합병 정렬에 대해 알아봅시다!
비기너
