시간 복잡도(Time Complexity)는 문제를 해결하는 데 걸리는 시간을 문제의 크기로 표현하는 관계이고, 공간 복잡도(Space Complexity)는 문제를 해결하는 데 필요한 메모리 공간을 문제의 크기로 표현하는 관계이다.
시간 복잡도에는 평균(Average) 시간 복잡도와 최악(Worst) 시간 복잡도가 존재한다. 평균 시간 복잡도는 임의의 입력 패턴을 가정했을 때 문제 풀이에 소요되는 시간의 평균을 말하고, 최악 시간 복잡도는 가장 문제 풀이에 긴 시간이 걸리는 입력에 대한 풀이 시간이다.
빅오 표기법(Big-O Notation)은 점근 표기법(Asymptotic notation)의 하나로, 알고리즘의 복잡도를 표현할 때 흔히 쓰이는 표기법이다.
어떤 함수의 증가 양상을 다른 함수와 비교해 표현한다. $O(n)$, $O(n^2)$, $O(\mathrm log n)$, $O(2^n)$ 등으로 표시한다. 가령 $O(n)$이라면 입력의 크기 n에 비례하는 시간이 걸린다는 뜻이고, $O(n \ \mathrm log n)$이라면 입력의 크기에 로그를 곱한 값에 비례하는 시간이 소요된다는 뜻이다.
이때 계수는 중요하지 않다. $O(2n)$도 $O(n)$이라 표시한다. 컴퓨터 관련 수학에선 보통 로그는 밑이 2이다.
선형 시간 알고리즘의 경우 $O(n)$이다. n개의 정수 중 최솟값을 찾으려한다면 처음부터 끝까지 살펴봐야 하므로 평균/최악 시간복잡도 둘 다 $O(n)$이다.
로그 시간 알고리즘은 $O(\mathrm log n)$이다. 이진 탐색 알고리즘의 경우 한 번 탐색할 때마다 절반씩 줄어들기 때문에 $n = 2^k$에서 $\mathrm log \ n$이 나와 $O(\mathrm log n)$이 된다.
이차 시간 알고리즘은 $O(n^2)$이다. 삽입 정렬의 경우 n개 원소 각각에 대해 다른 원소들을 돌며 자기 자리를 찾아 끼워넣어야 하므로 $N \times N = N^2$ 연산이 필요하다. 역순으로 정렬된 최악의 경우(worst case) $O(n^2)$의 복잡도를 가지나, 만약 주어진 배열이 이미 정렬된 상태라면(best case) $O(n)$의 복잡도를 가지기도 한다.
정렬 문제에 있어 $O(n \ \mathrm log n)$보다 낮은 복잡도를 가질 수 없음이 증명되어 있다. 일례로 병합 정렬(merge sort)가 $O(n \ \mathrm log n)$의 복잡도를 갖는다. 배열을 반으로 나누어 각각을 정렬시키는 데 $O(\mathrm log n)$이 걸리고, 정렬된 것을 한 곳에 합치는 데 하나씩 비교하므로 $O(n)$이 소요된다.
영화 <아이언맨>을 보고 무턱대고 공대에 진학, 이제는 기술로 세상을 안전하게 만들고자 합니다.
자율주행 개발에서 시작해, 지금은 컴퓨터 비전과 딥러닝을 공부하고 있습니다.
뭐든지 차근차근, 설령 느리더라도 멈춤은 없이 가고 싶습니다.
