시간 복잡도

컴퓨터과학(CS)/알고리즘

sondiaa 2021. 8. 26. 22:09

시간 복잡도를 계산하면 알고리즘을 구현하지 않고 알고리즘의 속도의 빠름 여부를 알 수 있다.

for(int i=0; i<n; i++)
{
    ...
}

...에 해당하는 코드의 시간 복잡도를 O(1)이라 가정할 때 위의 코드의 시간 복잡도는 O(n)이다.

반복문 안의 내용이 총 n번 반복되기 때문이다.

for(int i=0; i<n; i++)
{
    for(int j=0; j<n; j++)
        ...
}

위의 반복문의 경우 반복문이 2중으로 중첩되어 있으므로 O(n^2)이다.

만약 반복문이 k중이라면 O(n^k)이다. 이는 시간 복잡도에서는 함수의 차수만 중요하고 상수 인자는 무시되기 때문이다.

for(int i=0; i<3n; i++){
    ... // 3n번 수행
}

for(int i=0; i<n+5; i++)
{
    ... // n+5번 수행
}

그러나 시간 복잡도는 내부 코드의 수행 횟수를 정확히 알려주지 않고 상수 인자를 무시하기에 두 반복문 모두 시간 복잡도가 O(n)으로 같다.

for(int i=0; i<n; i++)
{
    for(int j=0; j<i; j++)
    {
        ...
    }

}

위의 식의 경우 반복 횟수가 1 + 2 + 3 + ... + n 이므로 1/2(n^2+n)이므로 시간 복잡도는 O(n^2)이다.

그 경우에는 전체 복잡도는 가장 큰 시간 복잡도가 된다.

for(int i=0; i<n; i++)
{
    
}

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

for(int j=0; j<n; j++)
{
    
}

위의 코드에서는 O(n^2)이 가장 크므로 전체 시간 복잡도는 O(n^2)이 된다.

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

시간 복잡도는 여러 인자에 영향을 받는 경우도 있다.

위의 코드의 경우 n과 m의 영향을 받아 시간 복잡도가 O(nm)이다.

이외에도

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

전체 시간 복잡도는 이 둘을 곱한 형태가 된다.

O(1)

상수 시간 알고리즘으로 입력의 크기에 영향을 받지 않고 공식을 이용하여 답을 바로 계산하는 경우이다.

O(logn)

로그 시간 알고리즘은 단계마다 입력의 크기를 절반으로 줄여 나간다. n을 계속 2로 나눠가면서 1이 되도록 하는데 필요한 단계 수가 log2n이다.

O(n)

선형 시간 알고리즘은 입력을 살펴보는 과정을 상수 번 수행한다.

보통 선형 시간이 가장 효율적인 시간 복잡도인데, 이는 답을 구하기 위해서 입력을 적어도 한 번은 봐야하기 때문이다.

O(nlogn)

이 알고리즘은 입력을 정렬하는 과정의 시간 복잡도를 기술할 때 자주 사용된다.

이는 효율적인 정렬 알고리즘이 O(nlogn)이기 때문이다.

O(n^2)

제곱 시간 알고리즘은 보통 2중으로 중첩된 반복문을 사용한다.

O(2^n)

입력 원소로 만들 수 있는 모든 부분집합을 한 번씩 살펴보는 알고리즘의 시간 복잡도를 기술할 때 자주 사용된다.

O(n!)

입력 원소로 만들 수 있는 모든 순열을 한 번씩 살펴보는 알고리즘의 시간 복잡도를 기술할 때 자주 사용된다.

보통 알고리즘의 시간 복잡도를 계산하면 알고리즘을 구현하기 전에 문제를 풀 만큼 효율적인지 아닌지를 알 수 있다.

만약 시간 제한이 1초이고 입력의 크기가 10^5이라고 하면

시간 복잡도가 O(n^2)이라면 수십초가 필요하므로 문제를 풀기에는 매우 느리다.

그러나 시간 복잡도가 O(nlogn)이라면 알고리즘이 시간 제한 안에 드렁오게 된다.

즉, 입력의 크기와 시간 제한을 통해서 역으로 적합한 알고리즘의 시간 복잡도를 추정할 수 있다. 그렇지만 이러한 시간 복잡도의 개념은 추정치이므로 실제 수행 시간과는 다를 수 있다.

O 표기법은 충분히 큰 입력에 대해 알고리즘 수행 시간의 상한을 의미한다.

Ω 표기법은 하한을 의미한다.

마지막으로 Θ는 시간 복잡도를 정확하게 알려준다.

즉 어떤 알고리즘의 시간 복잡도가 Θ(n)이라면 Ω(n)이면서 O(n)이다.