---
id: "imported/blog/study/cs/timecomplexity"
title: "시간 복잡도"
description: "시간 복잡도 관련 정리"
kind: "record"
published: "2023-06-02T00:00:00.000Z"
tags: ["time complexity","algorithm"]
url: "https://www.readiz.com/blog/study/cs/timecomplexity/"
markdownUrl: "https://www.readiz.com/blog/study/cs/timecomplexity/index.md"
---

# 시간 복잡도

시간 복잡도 관련 정리

## 주요 시간 복잡도

시간 복잡도 그래프: O(n), O(log n), O(n log n), O(n²), O(√n)의 증가량을 비교합니다. 입력 범위 n은 10\~1,000입니다.

많이 쓰이는 시간 복잡도에 대한 비교이다. x축 기준으로 대략 1000까지의 범위에서 그린 그래프이다.

## 시간 복잡도와 실제 수행 시간

위에서 이야기하는 `O(n)` / `O(log n)` 따위의 이야기는 많이 들었지만, 그래서 실제로 어떻게 쓰는지에 대한 이야기는 많이 부딪혀보지 않으면 느끼기 어렵다. 내가 느낀대로 정리해본다. 당연히 절대적인 것은 아니다.

### 컴퓨터의 초당 연산 처리 능력

사람마다 말이 많은데, 대충 일반적인 사용자 PC 기준 초당 `1억` \~ `10억` 개의 연산 정도를 처리 가능하단 것이 중론이다. 물론 이것을 너무 믿으면 안되는게, 기본적으로 연산은 사람이 쓴 `line` 단위가 아니라 어셈블리 레벨의 `instruction`레벨로 봐야하기 때문이다 또한, 이 `instruction`을 어셈블리로 코드를 변환해서 정확히 몇개가 수행되는지 안다고 해도, 각 `instruction`마다의 수행시간이 동일하지 않으며, `CPU`가 `prefetching`도 하고, `branch prediction`도 하고, `pipelining`도 하기 때문에, 모든 요소를 알기란 어렵다. 정확한 수행시간이란 무조건 *부딪혀봐야* 아는 것(또한 시행시 항상 같지 않다)이다. 하지만 일반적으로는 보수적으로 `1억`을 기준점으로 잡아 풀고, 만약 이를 크게 넘어가지는 않을 것으로(즉, 10억 회 연산 정도라면) 예상된다면 상수최적화를 시도해보는 것이 좋을 것이다.

### N 값 기준 허용되는 시간 복잡도

나는 `N`의 값에 따라 대략 아래와 같은 기준을 쓰고 있다.

- `N <= 100`: `O(N^3)`, 최적화된 `O(N^4)` 알고리즘을 돌릴 수 있다.
- `N <= 1,000`: `O(N^2)`, 주로 `DP`로 푸는 문제에서 많이 사용되는 범위이다.
- `N <= 10,000`: 여기부턴 대략 `O(N^2)`도 `timeout` 나기 쉽다. `O(n log n)` 정도가 허용된다고 봐야한다.
- `N <= 100,000`: 십만 단위를 넘어가면 슬슬 빡세다. `O(N^2)`는 무조건 `timeout` 나기 시작하는 구간. `O(n log n)` 와 동등, 혹은 그 이상의 알고리즘을 사용해야 한다.
- `N <= 1,000,000`: 여기부터는 `O(n)`을 슬슬 써야하는 단위이다. `O(n log n)`도 슬슬 시간이 소요되는 것이 눈에 들어오기 시작한다.
  - 추가적으로 알아야 것 중 하나는 루트로 줄이는 `O(n^1/2)`, `O(n * n^1/2)` 기법도 자주 등장하는 시점이라는 것이다. 꼭 알아두자.
    - 가령 소수를 판정할 때 루트n까지 봐도 된다던지 등..
- `N >= 1,000,000,000`: `O(log n)`이 강제된다. `O(n^1/2)`도 잘 짜면 된다.

## Master Theorem

`마스터 정리` 라고도 불리는 이 이론은 다음 수식을 의미한다. 재귀 관계식으로 표현한 알고리즘의 시간 복잡도를 계산하는데에 쓰인다.

$$
T(n) = aT(n/b) + f(n)
$$

엄밀히는 $a(\geq1)$와 $b(>1)$는 상수고, $f(n)$은 점근적으로 양인 함수라고 한다. $n$은 문제 크기이다. 분할 정복으로 문제크기 $n$인 문제가 $n/b$인 $a$개의 하위 문제로 나뉘어진다고 하면, $a$개의 하위 문제는 각각 $T(n/b)$ 시간에 풀 수 있을 것이다. 이 때, 문제를 나누고 각각의 결과를 합치는데 드는 비용이 $f(n)$이 되는 것이다.

이 때, $f(n)$에 따라 아래처럼 시간 복잡도가 계산된다.

1. $f(n) > n^{log_ba}$: $O(f(n))$
2. $f(n) \simeq n^{log_ba}$: $O(f(n)\log n)$
3. $f(n) < n^{log_ba}$: $O(n^{log_ba})$

### Binary Search의 시간 복잡도 생각해보기

위 이론에 따르면, Binary Search의 시간 복잡도를 계산해볼 수 있다. 아래처럼 재귀로 구현한다고 생각해보자.

```cpp
int bs(int s, int e, int t) {
    int m = (s+e)>>1;
    if (arr[m] == t) return m;
    if (arr[m] > t) return bs(s,m-1);
    else return bs(m+1,e);
}
```

이 경우, 함수에 진입하면 1개의 함수로 쪼개진다. 즉, $a=1, b=1$인 경우이다. 이 경우 $n^{log_ba} = n^0 = 1$이고, $f(n) = 1$이므로, 두번째 case에 해당한다. 시간 복잡도는 $O(f(n)\log n) = O(\log n)$이 된다.

### Merge sort의 시간 복잡도 생각해보기

이 경우에도 마찬가지로 재귀로 구현된다고 생각해보자. 대략적인 함수는 아래처럼 된다.

```cpp
// [s, e]
void mergeSort(int s, int e) {
   if (s >= e) return;
   int m = (s+e)>>1;
   mergeSort(s, m); mergeSort(m+1, e);
   // 이하 생략은 합치는 과정... 전체 원소에 대해서 f(n) = O(n)이 걸린다.
}
```

이 경우, 함수에 진입하면 2개의 함수로 쪼개진다. 또한, 구간도 $n/2$로 줄어든다. 즉, $a=2, b=2$인 경우이다. 이 경우, $n^{log_ba} = n^1 = n$이고, $f(n) = n$이다. 즉, 두번째 case이다. 시간 복잡도는 $O(f(n)\log n) = O(n \log n)$이 되겠다.