01. 시간복잡도 (Time Complexity, c++)

시간복잡도란?

알고리즘의 시간 복잡도는 알고리즘이 어떤 입력에 대해 얼마나 많은 시간을 사용할지를 추정합니다.

시간복잡도를 계산하면 구현하지 않고도 충분히 빠른지 확인할 수 있습니다.

---

Loops

예를 들면, 아래 코드의 시간복잡도는 O(n) 입니다.

    for (int i=1; i<=N; i++) {
        // code
    }

 

그리고 다음 코드의 시간복잡도는 O(n2) 입니다.

    for (int i=1; i<=N; i++) {
          for (int j=1; j<=M; j++) {
          // code
      }

 

일반적인 알고리즘들은 연속적인 단계로 구성됩니다. 전체 시간복잡도는 가장 오래 수행되는 단일 단계의 시간복잡도입니다.

그 이유는 가장 느린 단계에서 보통 코드의 병목 현상이 발생하기 때문입니다.

아래 코드는 여러 단계로 구성되어 있지만 시간 복잡도는 O(N^2) 입니다.

    for (int i=1; i<=N; i++) {
        // code
    }
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=M; j++) {
        // code
    }
    for (int i=1; i<=N; i++) {
        // code
    }

 

---

Complexity 분류

다음은 일반적으로 사용되는 알고리즘의 시간복잡도 입니다.

아래로 내려갈수록 오래 걸리는 시간복잡도 입니다.

 

Time Complexity
O(1)	input의 크기에 상관 없이 constant-time에 실행됩니다. 일반적으로 직접 수식을 사용하여 답을 계산 합니다.
O(logN)	logarithmic algorithm은 매 step에서 input 크기를 절반으로 줄입니다.
O(N)	답을 찾기 위해 각 input에 적어도 한번은 접근해야하기 때문에 종종 가능한 최고의 시간복잡도가 될 수 있습니다.
O(NlogN)	효과적인 정렬 알고리즘은 O(NlogN)에 동작하기 때문에 알고리즘이 input을 정렬한다는 것을 나타내기도 합니다. 또는 각 동작을 O(logN)에 수행하기 위한 Data Structure를 사용할 가능성도 있습니다.
O(N^2)	두개의 중첩된 Loop를 포함하며, input의 모든 쌍을 확인한다는 것을 의미하기도 합니다.
O(N^3)	세개의 중첩된 Loop를 포함합니다.
O(2^N)	input의 모든 subset을 반복한다는 것을 의미합니다. 예를 들어, {1, 2, 3} 에 대해 {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
O(N!)	input의 모든 순열을 반복한다는 것을 의미합니다. 예를 들어, {1, 2, 3} 에 대해 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}

 

위 시간 복잡도 중에서 O(2^N)과 O(N!)을 제외한 모든 시간 복잡도는 polynomial (다항 시간) 입니다.

즉 polynomial 시간복잡도는 대략적으로 알고리즘이 효과적이라는 것을 의미하기도 합니다.

 

대부분의 문제들은 polynomial 합니다.

 

그러나 NP-hard 문제들 (아무도 어떻게 효과적으로 해결하는지 모르는 그런 문제들)은 polynomial 시간에 해결할 수 있는 방법이 알려지지 않았습니다.

---

Estimating Efficiency

알고리즘을 구현하기 전, 시간복잡도를 계산함으로써 문제를 해결하는 것이 가능한지 확인할 수 있습니다.

현대적인 컴퓨터는 1초 안에 수억건의 작업을 처리한다고 생각하고 추정합니다.

 

예를 들어, 문제를 해결하는 제한 시간이 1초이고 input 크기가 10,000(10^5) 이라고 가정한다면

만약 시간복잡도가 O(N^2)인 경우 알고리즘은 대략 10^10번 연산을 수행할 것입니다.

 

그렇다면 대략 10초 정도 걸린다고 생각하면

문제를 해결하기에는 너무 느린 알고리즘이 됩니다.

---

Required Time Complexity

Input size	Required Time Complexity
N <= 10	O(N!)
N <= 20	O(2^N)
N <= 500	O(N^3)
N <= 5000	O(N^2)
N <= 10^6	O(NlogN) or O(N)
etc..	O(1) or O(logN)