작성: 2021-02-08 23:59
수정: 2021-02-14 20:05
난이도: Unrated
복잡도?
복잡도는 문제의 크기에 비례하여 어느 정도의 자원(메모리, 시간)을 사용하는지를 나타내는 식이다. 일반적으로 시간이 문제의 크기에 어떻게 비례하는지 나타내는 시간 복잡도와 사용하는 메모리의 크기가 문제의 크기에 어떻게 비례하는지 나타내는 공간 복잡도를 사용한다.
표기법
Big-O notation(O)를 사용하여 나타낸다. 표기법에서는 Big-O 말고도 Big-Omega(Ω), Big-Theta(Θ), Small-O(o), Small-omega(ω) 등을 사용하지만 문제를 풀 때에는 복잡도를 시간 또는 공간의 상계를 맞추기 위한 용도로, 일반적인 경우는 알고리즘/프로그램의 일정 성능 보장을 표시하기 위한 용도로 사용하므로 최악의 경우를 나타내는 Big-O notation을 사용한다. 알고리즘에서 쓰이는 수학적 정의는 아래와 같다.
\[\exists k>0 \exists n_0\forall n>n_0 :0\le f(n)\le kg(n)\Rightarrow f(n)=O(g(n))\]또는,
n0보다 큰 모든 n에 대해 0≤f(n)≤k·g(n)을 만족시키는 양수 n0과 k가 존재하면 f(n)이 O(g(n))에 속한다고 한다.
이런 수학적 정의는 사실 대학원 갈 것이 아니라면 자세히 알 필요가 없으므로 간단한 설명으로 하는 것이 나을 것 같다. 알고리즘적 측면에서 간단하게 설명하면 O(g(n))은 주어진 입력 n에 대해 대략적으로 g(n)에 비례하는 자원이 소비될 것이라는 의미이다.1
시간 복잡도
시간 복잡도는 프로그램이 문제의 크기에 따라 얼마나 많은 시간을 소비하는지를 나타낸다. 일반적인 PS 문제라면 메모리보다는 시간 제한을 중점적으로 보기 때문에 복잡도 중에서 가장 중요하게 여긴다. 따라서 본격적으로 PS를 하게 된다면 신경을 많이 쓰게 된다. 그렇기 때문에 코드를 보고 시간 복잡도를 예측하여 시간 제한을 맞춘다거나, 자주 사용하는 라이브러리 함수의 시간 복잡도를 알아보거나, 또는 알고리즘을 검색해서 푸는 경우 해당 알고리즘의 시간 복잡도를 같이 검색하여 푸는 것이 좋다.
시간 복잡도는 구했는데 실제로 걸리는 시간을 모를 때 사용할 수 있는 방법이 있다. 가장 단순한 연산(단위 연산) 1회 당 10-8초가 걸린다고 가정하고 푸는 방법이다. 즉, 1초에 연산 1억 회를 수행할 수 있는 환경이라고 가정하고 푸는 것이다. 이 경우 시간 복잡도를 구할 때 가장 영향을 많이 주는 항만 남기되 계수는 버리지 않는다. 이를 이용하면 넉넉하게 문제를 통과할 수 있을 정도의 시간 복잡도를 계산하고 그에 맞는 알고리즘을 설계/검색할 수 있다.
공간 복잡도
공간 복잡도는 프로그램이 문제의 크기에 따라 얼마나 많은 메모리를 사용하는지를 나타낸다. 일반적인 상황에서는 메모리의 집적률이 계속 높아지면서 성능이 좋아졌기 때문에 크게 신경쓰는 부분은 아니다. 다만 문제를 풀 때에는 가끔 메모리 제한을 매우 작게 걸어두어 더 작은 공간 복잡도를 가진 알고리즘으로 풀게 유도하는 문제도 있으며, 굳이 그런 조건을 두지 않아도 문제 자체를 크게 만들어 공간 복잡도에 대해 생각해보게 하는 문제도 있다.
백준에서는 대부분 메모리 제한을 256MB로 두고, 이는 int형 크기로 226≒7×107개의 변수를 저장할 수 있는 크기이다. 실제로는 107개에 가까워지면 위태롭다. 따라서 106의 입력 크기를 가지는 문제는 공간 복잡도가 $O(n)$보다 커지면 메모리 제한으로 정답을 구하는 데에 실패할 확률이 높다. 103 정도의 입력이라면 $O(n^2)$의 공간 복잡도여도 잘 돌아갈 것이다.
예시
시간 기준의 복잡도의 종류와 예시는 아래와 같다.
| 복잡도 | 예시 |
|---|---|
| $O(1)$(상수) | 입출력 함수 실행, 사칙연산, 비트 연산 등 |
| $O(\log n)$ | 이분 탐색, 힙의 원소 추가/삭제 |
| $O(n)$(선형) | 무작위 배열에서 최대값/최소값 찾기 |
| $O(n\log n)$ | 합병 정렬, 힙 정렬 등의 정렬 |
| $O(n^2)$(제곱) | 선택 정렬, 삽입 정렬 등의 정렬 |
| $O(n^3)$ | 플로이드-와셜 알고리즘(그래프 정점 수의 세제곱에 비례) |
| $O(c^n)$(지수) | 단순 재귀를 사용하여 피보나치 수열 값을 계산 |
| $O(n!)$ | 무작위 배열을 섞은 모든 경우를 판별하여 정렬된 배열 찾기 |
위의 경우 외에도 $O(\log(\log n))$이나 $O(n^2 \log n)$, $e^{(c+o(1))(\ln n)^{\alpha}(\ln\ln n)^{1-\alpha}}$(!) 등 다양한 시간 복잡도 함수가 존재한다.
-
의미상 Big-Theta(Θ) notation을 쓰는 것이 맞는 것 같지만 왠지 모르게 Big-O를 쓴다고 한다. ↩