[알고리즘] 시간 복잡도

다들 백준 문제 풀다가 이런 상황 겪어보셨을 겁니다.

이는 백준에서 문제를 채점할 때 시간제한을 두기 때문인데요, 코드를 비효율적으로 작성하면 그만큼 실행하는 데 시간이 더 오래 걸리게 되겠죠? 이를 방지하기 위해 코드의 실행 시간이 얼마나 걸릴지 파악하는 것이 좋은데요, 이를 위해 사용하는 방법이 코드의 '시간 복잡도'를 파악하는 것입니다. 이는 정확한 실행 시간을 구하는 방법이 아니고, 알고리즘이 얼마만큼의 시간을 사용할지 근사적으로 알려주는 방법입니다.

 

시간복잡도는 Big-O Notation을 이용해 표기합니다. O(n)과 같이 작성하며, 괄호 안에는 알고리즘이 사용할 시간과 관련된 식이 들어갑니다. 시간복잡도를 작성하는 규칙이 몇 가지 있는데요, 이에 대해 알아보도록 하겠습니다.

 

1. 기본적인 작성법

이 함수는 호출되었을 때 몇 번 실행될까요?

def ManOfPassion(A, n):
    i = int(n/2)
    return A[i]

다들 쉽게 파악했겠지만, n의 크기와 상관없이 1번 실행됩니다. 이 경우는 상수 시간복잡도이며, O(1)과 같이 표기합니다.

for i in range(n):
    print(i)

위 반복문의 경우, i를 총 n번 출력하게 되는데요, 실행 횟수가 반복 횟수인 n에 비례하는 것을 볼 수 있습니다.

이 경우는 O(n)으로 표기합니다.

for i in range(n):
    for j in range(m):
        print(j)

위 이중 반복문의 경우에는 j를 총 n x m번 실행하며, 실행 횟수가 총 반복 횟수인  n x m에 비례하는 것을 볼 수 있습니다.

이 경우에는 O(nm)으로 표기하지만, 일반적으로 이중 반복문의 경우에는 O(n^2)로 표기합니다.

참고로, k번 중첩된 반복문의 시간복잡도는 O(n^k)입니다.

 

반복문의 시간복잡도는 매우 직관적으로 파악이 가능합니다. 그러면 재귀함수를 사용한 경우 시간복잡도는 어떻게 될까요?

def func(n):
    if n==1 return
    func(n-1)
    func(n-1)

함수 func를 재귀적으로 호출할 때마다 실행횟수가 2배로 증가하는데요, 재귀적으로 n번째 호출된 함수는 총 2^(n-1)개가 됩니다. 따라서 총 실행 횟수는 다음과 같습니다.

이를 Big-O Notation으로 표기하면 O(2^n)이 됩니다. 뒤에서 설명하겠지만, 실행 횟수를 Big-O Notation으로 표기할 때 상수 인자를 무시합니다.

2. 여러 알고리즘 같이 사용된 경우

# Part 1
for i in range(n):
    print(i)
    
# Part 2
for i in range(n):
    for j in range(n):
        print(j)

사실 코딩을 하다 보면, 코드의 각 부분의 시간복잡도가 모두 다릅니다. 이 경우 전체 코드의 시간복잡도는 어떻게 판단할까요? 여러 알고리즘이 같이 사용된 경우에는 각 부분의 시간복잡도 중 가장 큰 시간복잡도가 전체 코드의 시간복잡도가 됩니다. 위 코드의 경우, Part 1의 시간복잡도는 O(n)이고 Part 2의 시간복잡도는 O(n^2)이므로, 둘 중 시간복잡도가 더 큰 O(n^2)가 전체 코드의 시간복잡도가 됩니다.

3. 상수 인자 포함된 경우

# Part 1
for i in range(3*n):
    print(i)
    
# Part 2
for i in range(n+5):
    print(i)
    
# Part 3
for i in range(n/2):
    print(i)

위 코드에서 각 부분의 시간복잡도는 다음과 같습니다.

Part 1	Part 2	Part 3
O(3n)	O(n+5)	O(n/2)

하지만, Big-O Notation을 사용할 때 상수 인자는 무시합니다. 따라서, 시간복잡도를 다음과 같이 표기하는 것이 맞습니다.

Part 1	Part 2	Part 3
O(n)

세 코드 모두 시간복잡도가 O(n)으로 같군요! 이처럼 코드의 실행 횟수가 완벽히 일치하지 않아도 시간복잡도는 같은 경우가 여럿 있습니다.

 

지금까지 알고리즘의 시간복잡도를 파악하는 방법에 대해 알아보았습니다. 흔히 접하는 시간 복잡도는 크게 3가지인데요, O(n)과 O(n^2),  그리고 O(nlogn) 정도가 백준에서 가장 많이 사용됩니다.

위 그래프에서 볼 수 있듯이, 시간복잡도가 증가할수록 코드의 실행 횟수는 매우 큰 폭으로 증가하게 됩니다. 따라서 백준에서 시간초과가 나지 않게 하려면 시간복잡도를 O(n^2) 이하가 되도록 효율으로 작동하는 코드를 작성하는 것이 중요합니다. 사실 그마저도 O(n^2)가 시간초과가 나는 경우가 빈번하게 발생하기 때문에, O(n^2)를 시간초과가 발생하는 마지노선 정도로 생각하면 될 것 같습니다.