[Algorithm] 시간복잡도(Time Complexity) 평가

프로그램의 성능을 평가하는 것은 개발자에게 매우 중요하다. 성능이 뛰어난 프로그램은 자원을 효율적으로 사용하며, 사용자에게 더 나은 경험을 제공한다. 성능 평가 방법 중 가장 기본적이고 확실한 방법은 연산 횟수를 계산하는 것이다. 이번 글에서는 코드의 시간복잡도를 분석하는 방법과 이를 통해 프로그램의 효율성을 평가하는 방법을 알아본다.

기본 연산의 시간복잡도

가장 단순한 연산은 대입 연산이다. 예를 들어, set a = 10과 같은 대입 연산은 O(1)의 시간복잡도를 가진다. 이는 한 줄의 코드가 일정한 시간 내에 실행된다는 것을 의미한다.

조건문도 비슷하다. 다음 코드를 보자.

set a = 5
if a != 10:
    print('hello')

대입 연산 set a = 5는 O(1), 조건문 if a != 10도 O(1), 그리고 print('hello')도 O(1)이다. 따라서 전체 코드의 시간복잡도는 O(1)이다. 이처럼 간단한 코드의 시간복잡도를 계산하는 것은 비교적 쉽다.

반복문과 시간복잡도

코드가 길어지고 복잡해지면, 특히 반복문이나 재귀 함수가 등장하면 시간복잡도를 계산하는 것이 어려워진다. 하지만 반복문의 시간복잡도를 계산하는 것은 여전히 중요한 일이다. 다음 예제를 보자.

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

이 코드는 n번 반복되므로, 시간복잡도는 O(n)이다. n이 커질수록 실행 시간이 선형적으로 증가한다.

중첩 반복문의 시간복잡도

중첩 반복문은 더 복잡한 시간복잡도를 가진다.

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

이 코드는 n * n번 반복되므로, 시간복잡도는 O(n²)이다. n이 커질수록 실행 시간이 제곱에 비례하여 증가한다.

시간복잡도의 활용

시간복잡도를 이용하면 코드의 효율성을 평가하고, 제한 시간 내에 실행될 수 있는지 판단할 수 있다. 보통 for 루프를 1억 번 도는 데 걸리는 시간이 1초 정도 된다. 이를 이용하면 다음과 같은 사실을 알 수 있다.

제한시간이 1초인 경우, N의 범위에 따른 시간복잡도의 한계를 알아보자.

• N ≤ 10: O(N!), O(2ⁿ), O(3ⁿ)
• N ≤ 20: O(2ⁿ)
• N ≤ 100: O(N⁴)
• N ≤ 500: O(N³)
• N ≤ 1,000: O(N²), O(N² log N)
• N ≤ 100,000: O(N), O(N log N), O(log N), O(1)

제한시간과 솔루션의 시간복잡도를 비교하여, 시간 내에 답이 나오지 않는다면 다른 솔루션을 떠올려야 한다.