알고리즘의 시간복잡도

PS를 하는데 시간복잡도 얘기를 안하고 넘어갈 수는 없습니다.

 

알고리즘의 시간복잡도는 입력의 크기에 대해 알고리즘이 어느정도의 시간을 사용할지 근사적으로 표현한 것을 말합니다.

어떤 문제를 풀고 내 알고리즘이 제한시간 안에 동작하는지 확인해 보려면 알고리즘의 시간복잡도를 계산해보면 됩니다.

 

시간복잡도는 \(O(\cdots)\)로 표기하고, 입력이 \(n\)일 때 코드가 몇 번 실행되는지 괄호안에 함수를 넣으면 됩니다.

 

예를 들어, 다음과 같은 반복문은 \(O(n^2)\) 입니다.

 

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        // do something
    }
}

 

물론 시간복잡도가 여러 인자에 영향을 받을 수 있습니다. 그때는 함수에 여러 변수가 포함됩니다.

다음과 같은 반복문은 \(O(nm)\) 입니다.

 

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < m; j++)
    {
        // do something
    }
}

 

하지만 시간복잡도가 코드가 실제로 정확히 몇번 수행되는지 나타내주지는 않습니다.

시간복잡도에서는 함수의 가장 큰 차수만 중요하고, 작은 차수의 항이나 계수는 전부 무시되기 때문입니다.

 

그래서 다음과 같은 코드들은 각각 \(5n\), \(n+100\), \(n/2\)번 수행되지만 시간복잡도는 \(O(n)\) 입니다.

 

for (int i = 0; i < 5 * n; i++)
{
    // do something
}
 
for (int i = 0; i < n + 100; i++)
{
    // do something
}
 
for (int i = 0; i < n; i += 2)
{
    // do something
}

 

사실 이런 빅오 표기법 (Big O notation)은 조금 더 엄밀한 정의가 있고, 다른 여러 표기법도 있지만 이 글에서는 생략합니다.

대충 입력에 대해 걸리는 시간을 이런 식으로 표기한다는 것만 알고 가셔도 괜찮습니다.

 

다음은 자주 쓰이는 시간복잡도입니다.

 

\(O(1)\)

상수 시간 알고리즘입니다. 입력의 크기에 영향 받지 않는 알고리즘 입니다.

주로 수학 공식등을 이용해 답을 바로 계산해내는 문제들의 시간복잡도입니다.

 

\(O(\log n)\)

로그 시간 알고리즘 입니다.

 

\(O(\sqrt n)\)

루트 시간 알고리즘 입니다.

가장 많이 쓰일 때는 어떤 수 \(n\)이 소수인지 판별할 때일 것입니다.

1부터 \(\sqrt n\)까지 모든 수로 나눠떨어지지 않는다면 \(n\)은 소수입니다.

\(O(n)\)

선형 시간 알고리즘 입니다.

문제 풀때 대부분의 풀이는 최소 이 시간복잡도를 깔고 가는데,

\(n\)회의 입력/출력을 하는데 이미 \(O(n)\)의 시간이 걸리기 때문입니다.

 

\(O(n\log n)\)

\(n\)개의 원소를 정렬할 때의 일반적인 시간복잡도 입니다.

또는 연산에 \(\log n\)의 시간이 걸리는 자료구조를 사용 할 때에도 흔히 볼 수 있습니다.

 

\(O(n^2)\), \(O(n^3)\)

\(k\)중 반복문을 사용했을 때 시간복잡도는 일반적으로 \(O(n^k)\)입니다.

 

\(O(2^n)\)

\(n\)개의 원소로 만들 수 있는 모든 부분집합을 탐색할 때 볼 수 있는 시간복잡도입니다.

 

\(O(n!)\)

\(n\)개의 원소로 만들 수 있는 모든 순열을 탐색할 때 볼 수 있는 시간복잡도입니다.

 

아무튼 이런식으로 시간복잡도를 계산해냈다면, 프로그램의 실제 수행시간도 예상할 수 있습니다.

수행시간을 예상하는 가장 많이 사용되는 방법은 1초에 1억번의 연산이 수행된다고 가정하는 것입니다.

 

이 기준으로 각각의 알고리즘이 시간안에 동작할지 예측해봅시다. 문제의 제한시간은 모두 1초라고 가정합시다.

입력 \(n\)의 크기가 \(10^5\)라면, \(O(n\log n)\)정도의 알고리즘까지는 큰 문제없이 돌아갈 것입니다.

 

\(O(n \sqrt n)\)는 어떨까요? \(10^{7.5} \approx 3.162 \times 10^7\) 입니다.

1억은 넘지 않으므로 가능하다고 행복회로를 돌리고 싶지만, 그렇지 않을 수도 있습니다.

시간복잡도 앞에 붙는 상수가 너무 크거나, 시간복잡도 외의 요소에 의해 시간이 더 걸릴 수 있기 때문입니다. 직접 돌려보기 전까진 모르겠네요.

 

그럼 \(n\)의 크기가 \(1000\)정도라면 어떨까요? \(O(n^2)\)정도는 문제없이 돌아갈겁니다.

\(n\)이 \(500\)정도라면? \(O(n^3)\)도 여유있게 돌아가겠네요.

 

\(n\)이 \(20\)이라면 \(O(2^n)\) 알고리즘도 생각할 수 있게 되고,

\(n\)이 \(10\)이면 \(O(n!)\)도 생각할 수 있게 됩니다.

 

물론 이 1억이라는 수는 절대 정확한 값이 아닙니다.

실제 요즘 CPU는 1초에 훨씬 더 많은 양의 연산을 할 수 있기 때문에, 간단한 연산이라면 10억번을 하더라도 1초안에 실행될 수 있지만,

위에서 말씀드렸다시피 시간복잡도상으로는 1억보다 작더라도 1초안에 실행되지 않을 수 있습니다.

다만 입력의 크기를 보았을 때, 어느정도의 시간복잡도를 가진 알고리즘까지 고려대상인지 결정하는데는 충분합니다.

 

 

공간복잡도라는 개념도 있습니다.

 

시간복잡도가 알고리즘의 실행시간을 나타낸다면, 공간복잡도는 알고리즘이 실행되는데 필요한 매모리를 나타냅니다.

대부분의 경우에는 문제에서 메모리를 충분히 주기 때문에 공간복잡도는 크게 신경쓰지 않아도 되는 부분입니다.

만약 간단한 문제를 푸는데 메모리 초과를 받았다면,

대부분의 경우는 무한루프 등으로 자료구조안에 원소가 너무 많이 들어갔거나, 배열 밖의 원소등을 접근하여 Segmentation Fault가 난 경우일 것입니다.

 

그래도 만약 공간복잡도를 계산할 필요가 있다면 계산방법은 간단합니다.

메모리 제한이 256MB일 경우, 4byte인 int형 배열의 크기는 약 2억 6천만개를 넘을 수 없습니다.

물론 실제로는 고정적으로 필요한 메모리가 있기 때문에 더 적은 공간만을 사용할 수 있을 것입니다.