Time Complexity

시간 복잡도

입력에 대해 알고리즘이 얼마만큼의 시간을 사용할지 근사적으로 나타냄

계산 방법

기본적인 알고리즘

연산이 단일 명령어로 구성된 경우의 시간 복잡도는 O(1)이다.
단일 명령이 n 번 반복 수행하는 경우 시간 복잡도는 O(n)이다.
반복문이 k중으로 중첩되고 각 반복문이 n 번씩 수행한다면 시간 복잡도는 O($n^k$)이다.
시간 복잡도에서 상수항 및 계수는 고려하지 않는다.

여러 단계로 구성된 알고리즘

전체 알고리즘의 시간 복잡도는 각 단계의 시간 복잡도 중에서 제일 큰 것이 전체 알고리즘의 시간 복잡도가 된다.

가장 느린 단계의 알고리즘의 병목이 되기 때문

여러 인자에 영향을 받는 알고리즘

알고리즘이 여러 인자에 영향을 받을 때는 시간 복잡도 함수에 여러 변수가 포함된다.

for(int i = 1; i<=n; i++){
    for(int j = 1; j<=m; j++){

    }
}

위의 코드의 시간 복잡도는 O(nm)이다.

재귀 함수 알고리즘

재귀 함수의 경우에는 함수가 몇 번 호출되는지, 그리고 각 호출 때의 시간 복잡도가 어떻게 되는지에 따라 결정된다.

전체 시간 복잡도 = 함수 호출 횟수 * 호출 때의 시간 복잡도

void g(int n){
    if (n==1) return;
    g(n-1);
    g(n-1);
}

위의 코드의 시간 복잡도는 인자가 n-k 인 함수 호출이 $2^k$ 번 일어나고 호출 때의 시간 복잡도는 O(1) 이므로 전체 시간 복잡도는 O($2^n$)이다.

시간 복잡도 함수별 특징

시간 복잡도가 어떤 상수 k에 대해 $O(n^k)$를 넘지 않으면 다항 시간 알고리즘이다. 아직 다항 시간 알고리즘이 알려지지 않은 문제들의 집합을 NP-Hard 문제라 한다.

1. O(1)
   공식을 이용하여 답을 바로 계산해내는 알고리즘 등
2. $O(\log n)$
   대체로 단계마다 입력의 크기를 절반씩 줄여나감. 로그의 밑수가 시간 복잡도에 나타나 있지 않음

   n 을 계속 2로 나눠가면서 1이 되도록 하는 데에 필요한 단계 수가 $\log_{2} n$ 이다

3. $O(\sqrt n)$
   $\sqrt n = n \sqrt n$ 이 성립함

   n 개의 원소를 각각 $O(\sqrt n)$ 개씩의 원소로 이뤄진 그룹 $O(\sqrt n)$ 개로 나눌 수 있다.

4. O(n)
   선형 시간 알고리즘은 입력을 살펴보는 과정을 상수 번 수행

   대부분의 경우에 선형 시간이 가장 효율적

5. $O(n^2)$
   제곱 시간 알고리즘은 보통 2중으로 중첩된 반복문 사용

   입력 원소 두 개로 만들 수 있는 모든 조합을 한 번씩 살펴볼 수 있음

6. $O(2^n)$
   입력 원소로 만들 수 있는 모든 부분집합을 한 번씩 살펴볼 수 있음
7. O(n!)
   입력 원소로 만들 수 있는 모든 순열을 한 번씩 살펴볼 수 있음

시간 복잡도 비교

$O(1) < O(\log n) < O(\sqrt n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$

효율성 추정

| 입력의 크기 | 추정 시간 복잡도 |
|—–|——|
| $n \leq 10$ | O(n!) |
| $n \leq 20$ | $O(2^n)$ |
| $n \leq 500$ | $O(n^3)$ |
| $n \leq 5000$ | $O(n^2)$ |
| $n \leq 10^6$ | $O(n \log n)$ 이나 O(n) |
| n이 클 때 | O(1) 이나 $O(\log n)$ |