[코딩인터뷰] 알고리즘 시간 복잡도 분석 방법

알고리즘 시간 복잡도 분석 방법

코딩 테스트는 시간 제한이 있습니다. 이미 구현한 전략이 제한된 실행 시간 안에 풀 수 없다는걸 깨닫고 다른 전략을 시도할 시간은 없습니다. 따라서 문제를 어떻게 풀까 고민하다 떠올린 아이디어가 실행 시간 안에 해결할 수 있는지를 가늠할 줄 알아야, 잘못된 구현을 하는 불상사를 피할 수 있습니다. 내가 구현할 알고리즘 전략이 주어진 실행 시간 안에 동작할 수 있는지를 간단하게라도 가늠할 줄 알아야 합니다.

일반적으로 10의 8승, 1억번 이상 의 연산 시간이 필요한 전략은 코딩 테스트 문제에 일반적으로 주어지는 '1초' 라는 제한된 실행 시간 안에 해결할 수 없습니다. 특히나 Python 는 타 언어에 비해 실행 시간이 더 걸리는 편이라 제한된 실행시간 안에 완료할 수 있을지 더 주의해야 합니다. 대체로 코딩 테스트에서는 적절한 알고리즘으로 푼 문제의 정답을 언어적 한계로 인해 놓치는 경우는 흔하지 않지만, 정확하게 문제를 풀지만 시간이 너무 오래 걸려 탈락하게 되거나 점수를 잃는건 흔하게 발생합니다.

코딩 테스트 문제는 실제 어플리케이션을 구현하는 것보다는 단순하기 때문에 실행 시간이 얼마나 걸릴지 가늠하는 건 어렵지 않습니다. 입력도 단순하고 여러 클래스를 거치지도 않고 설계의 영향도 받지 않습니다. 주로 반복문과 회귀 함수로 문제를 푸는데 다인 경우가 많습니다.

반복문의 시간 복잡도

반복문의 시간 복잡도는 직관적으로 이해하기 편합니다. 반복문은 대체로 입력의 크기만큼 또는 배열의 크기만큼 반복하여 연산하게 됩니다. 만약 같은 데이터의 반복을 중첩한다면 중첩하는 만큼 계산하면 됩니다. 반복문은 간단하게 아래와 같이 계산하게 됩니다.

# 'len(b)' 크기만큼 실행 시간이 걸립니다.
for a in b:
    print(a)

# 'len(x) * len(y)' 만큼 실행 시간이 걸립니다.
for i in x:
    for j in y:
        print(d[i][j])

# '2 * len(r)'만큼 실행 시간이 걸립니다.
for k in r:
    print(k)

for k in r:
    print(k)

이진 탐색 트리의 시간 복잡도

이진 탐색 트리는 높이 즉 Level 만큼 탐색을 하는데 이를 수식으로 표현하면 O(h) 라 할 수 있습니다. 하지만 높이는 입력되는 데이터 크기와 다르기 때문에 데이터 크기 n 에 대한 수식으로 변경해야 합니다.

이진 탐색 트리는 원하는 데이터를 찾을 때까지 탐색을 반복합니다. 매 Level 을 탐색할 때마다 탐색 범위가 반으로 줄어들게 되며 이를 수식으로 표현하면 아래와 같습니다.

(1/2)^h * n = 1 (h = 탐색한 Level 횟수)

위 수식을 'h' 에 대해서 정리하면 h = log n 이 됩니다. 따라서 O(h) = O(log n) 으로 데이터 입력에 대한 표현으로 변경할 수 있습니다.

회귀 함수의 시간 복잡도

회귀 함수를 분석하는 건 까다롭습니다. 회귀 함수는 실행 시간이 얼마나 걸릴지 직관적으로 보이지 않습니다. 따라서 회귀 함수의 실행 시간을 가늠하기 위한 방법인 Recurrence Tree Method 을 배워야 합니다.

병합 정렬의 시간 복잡도

병합 정렬 (Merge Sort)을 예시로 Recurrence Tree Method 가 어떻게 회귀 함수의 시간 복잡도를 계산하는지 설명하겠습니다.

병합 정렬은 데이터를 나눌 수 없을 때까지 둘로 나누는 과정을 진행한 뒤 합하면서 정렬을 완성하는 알고리즘입니다. 이를 기호로 표시하면 아래와 같이 표현할 수 있습니다.

T(n) = T(n/2) + T(n/2) + O(n) ('O(n) = cn', 병합할 때 실행 시간)

T(n/2) 는 다시 T(n/2) = T(n/4) + T(n/4) + O(n/2) 가 됩니다. 이를 계속 반복하는걸 표현하면 아래와 같은 그림이 만들어지게 됩니다.

https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/analysis-of-merge-sort

위 그림에서 각 Level 을 수평으로 합하면 그림의 오른쪽 수식만큼 실행 시간이 걸립니다. 신기하게도 매 Level 마다 동일한 시간이 걸리게 됩니다. 그리고 각 Level 수식을 수직으로 합하면 병합 정렬의 전체 실행 시간인 k * c * n (k = Level 횟수) 가 됩니다. 여기서 k 의 경우는 Level 횟수 인데 병합 정렬은 데이터를 반으로 나눌 때마다 Level 이 만들어집니다.

2 개를 정렬하면, 2 = 1 + 1 로 한 번만 나누니까 'k = 1'
4 개를 정렬하면, 4 = 2 + 2 = (1 + 1) + (1 + 1) 로 두 번 나누니까 'k = 2'
8 개를 정렬하면, 8 = 4 + 4 = (2 + 2) + (2 + 2) = (1 + 1 + 1 + 1) + (1 + 1 + 1 + 1) 로 나누니까 'k = 3'

즉 'k' 는 입력 'n' 에 대하여 k = log n 이 됩니다. 따라서 병합 정렬의 전체 수식은 log n * c * n 이고 Big-O 로 표시하면 상수 'c' 는 사라지므로, 병합 정렬의 시간 복잡도는 O(log n * n) 이라 할 수 있습니다.