점근식 시간복잡도 계산 - 반복 대치, 추정 후 검증, 마스터 정리

시간 복잡도를 계산할 때, 반복문과 알고리즘의 동작 과정을 이해하면서 대략적으로 추정하면 실제 복잡도와 근사하게 맞을 때가 많다. 그러나 알고리즘을 재귀식 형태로 표현하게 되면 직관적으로 복잡도를 추정하기가 훨씬 어려워진다.

 

예를 들어, 다음과 같은 코드가 있다고 하자.

def T(n):
    if n <= 1:
        return 1
    return 2 * T(n // 2) + n

 

이 식의 시간 복잡도를 예측할 수 있을까?

 

이와 같은 구조를 자주 접해본 사람이라면, 경험적으로 O(nlogn)이라고 추정할 수 있다. 하지만 코드가 더 복잡해지면 이런 식의 ‘감'에 의존한 추정은 한계에 부딪힌다.

예를 들어, T(n) = T(n/2) + T(n/3) + n 와 같은 점화식의 복잡도를 정확히 계산할 수 있는 사람은 많지 않다.

 

이러한 어려움을 체계적으로 해결하기 위해 제안된 방법이 반복 대치(iterative substitution), 추정 후 검증(guess and check), 그리고 마스터 정리(master theorem)이다.

지금부터 이 세 가지 접근법을 중심으로 시간 복잡도 분석 방법을 살펴보도록 하겠다.

 

1. 반복 대치 (iterative substitution)

이 방법은 특히 고등학교 수학에서 많이 쓰이는 "일반화"의 과정을 떠올리면 쉽다. 

예로 들어서 어떤 수식이

라고 해보자. 

그렇다면 이를 일반화 시킨다면

로 설명할 수 있다. 이 방법을 사용하는 것이다. 

 

T(n) = 2T(n/2) + n도 같은 방식으로 해결할 수 있다.

 

핵심 아이디어: 

- 재귀식을 여러 번 전개하여 패턴을 찾는다

- n부터 시작해서 점점 작아지며 n → n/2 → n/4 → ... → 1로 진행된다

- 종료 조건 T(1) = c (c는 상수)에 도달할 때까지 반복한다

 

1단계: 반복 대치

 

2단계: 일반화

이 공식을 일반화를 시킨다면

3단계: 종료조건을 이용해서 시간복잡도 계산 

n/2^k = 1일 경우 종료된다. 이를 통해 k를 구해보자.

k를 통해서 식 안에 있는 내용을 T(1)로 만들어 식을 단순화 시키는 것이 목표이다. 이는 다음과 같이 T(n/2^k)로 바꾸면 쉽게 표현할 수 있다.

이후 k값을 2단계의 식에 넣어보면?

시간복잡도는 cn은 nlogn보다 낮으므로 시간복잡도에 큰 영향을 주기 않기에 cn은 삭제

이런 방식으로 시간복잡도는 간단하게 계산된다.

 

이 방법에는 장점과 단점이 명확하다.

장점: 명확하고 직관적이고 자연스럽게 계산이 가능하다

 

단점: 단순한 계산인 만큼 복잡한 식에는 적용되지 않는 경우가 많고 규칙을 찾아내지 못해 일반화를 하지 못하는 경우 시간이 소요된다. 일일히 넣어봐서 생각해야 하기에 시간도 많이 소요될 가능성이 있다.

 

2. 추정 후 검증(guess and check)

반복 대치의 단점을 보안할 수 있는 방법으로 추정 후 검증이 있다. 이 방법은 시간복잡도를 먼저 추측하고, 그 추측이 맞는지 수학적 귀납법으로 증명하는 방식이다. (엄밀히 말하면 추정 후 검증 전체가 수학적 귀납법의 한 형태이지만, 이해를 돕기 위해 '추정'과 '검증'으로 나누어 설명한다)

 

예로 들어, T(n) = 2T(n/2) + n라는 식을 다시 계산해보자. 처음에 T(n)을 n^2의 시간복잡도를 가진다고 생각하면 이렇게 계산 가능하다.

 

1단계: 추정

라고 가정이 되어진다.

 

2단계: 귀납 가정

수학적 귀납법 - 위키백과, 우리 모두의 백과사전

 

수학적 귀납법

 

여기서 사용되는 귀납법은 고등학교에서 배우는 "n=1 → n=2 → ... → n=k"로 가는 방식이 아니다.

 

대신 "n보다 작은 모든 값들(n/2, n/4, ...)에 대해 이미 성립한다고 가정" 하고 그것을 이용해 T(n)이 성립함을 보이는 귀납법을 사용하도록 하겠다.

 

이는 "강한 귀납법(Strong Induction)"이라는 전문용어로 불리는 방법이다. 

 

 

3단계: 재귀식 전개

이를 다음 식에 대입한다. 

4단계: 귀납 가정 적용

이를 다음 식에 대입한다. 

5단계: 검증

T(n) ≤ cn²가 성립하는가? 확인해보도록 하자

여기서 직관적으로 2n은 n^2에 비해 너무나 작은 값이기에 제외해서 생각하면 c의 값에 의해 값이 많이 달라질 수 있다는 것을 알 수 있다.

 

즉, 이 부등식은 c의 값에 따라 성립할 수도, 성립하지 않을 수도 있다.

그러므로 T(n) = O(n²)은 올바른 추측이 아니다고 설명할 수 있다.

 

그렇다면 위의 내용으로 다시 O(n) = nlogn이라고 가정해서 풀어보면 어떻게 될까?

장점: 반복대치보단 간단할 수 있다. 예로 들어 T(n) = T(n/3) + T(n/2) + n 와 같은 복잡한 수식의 경우 반복대치에 반해 추정 후 검증은 간단한 편이다. 수학적으로 엄밀하다.

 

단점: 경험이나 직관이 "틀릴 경우" 상당한 시간이 소요된다.

 

3. 마스터 정리(master theorem)

마스터 정리는 앞의 두 가지 방법보다 매우 빠르고 공식 위주의 정리다. "쉽게 배우는 알고리즘"이라는 책에서는 간단하게 근사 버전으로 알려준다. 이 내용은 엄밀한 수학적 증명을 생략한 것이기에 맹신해서는 안 되지만, 빠르게 시간복잡도를 추정할 때는 매우 유용하다.

 

간단하게 설명하면 

라고 가정한 뒤

 

이 공식에 값들을 집어넣어 값을 간단하게 구한다. 

 

예로 들어서 아까전에 T(n) = 2T(n/2) + n식을 바꾸어 a=2, b=2, f(n) = n, h(n) = n

이경우에는 case1에 해당하므로 O(nlogn).

 

간단하게 계산이 가능하다.

 

마스터 정리 - 위키백과, 우리 모두의 백과사전

 

<자료구조 알고리즘> 마스터 정리 Master theorem

 

이것의 가장 큰 문제는 특정 문제에서는 안풀릴 가능성이 높고 완전한 이론이 아니라는 것이다. 이는 작자가 보여준 마스터 정리 근사버전에도 나타나는 문제점이다. 그러므로 이 방법은 조심스러운 사용이 요구된다.

 

장점: 빠르다. 

단점: 수학적 엄밀성이 낮다. 특정 상황에서는 틀릴 수 있다.

 

4. 점근식에 대한 유의사항

점근식을 계산할 때, 알고리즘에 대한 이해가 없다면 T(n) = 3T(n) + 2T(n/2) + n² 과 같은 형태의 재귀식을 분석하고자 하는 현상이 발생할 수 있다. 

 

그러나 이러한 재귀식은 근본적으로 알고리즘의 정의를 위반하고 있으므로, 시간복잡도를 논하는 것 자체가 무의미하다.

 

알고리즘이 되기 위한 필수 조건 중 하나는 유한성으로 알고리즘은 유한한 단계 내에 반드시 종료되어야 하며, 명확한 출력을 생성해야 한다.

 

위의 재귀식 T(n) = 3T(n) + 2T(n/2) + n²을 살펴보자. 이 식은 크기 n인 문제를 해결하기 위해 다시 크기 n인 문제 3개를 호출한다. 문제의 크기가 전혀 줄어들지 않으므로, 재귀 호출은 끝없이 반복될 수밖에 없다. 결과적으로 이 재귀식은 종료 조건에 도달할 수 없으며, 출력을 생성할 수도 없다.

 

재귀식이 의미를 갖기 위해서는 문제 크기가 점진적으로 감소하여 결국 기저 사례(base case)에 도달해야 한다.

 

예를 들어:

• T(n) = 2T(n/2) + n에서는 n → n/2 → n/4 → ... → 1로 크기가 감소한다
• T(n) = T(n-1) + n에서는 n → n-1 → n-2 → ... → 1로 크기가 감소한다

반면 T(n) = 3T(n) + 2T(n/2) + n²에서 T(n)이 다시 T(n)을 호출하는 부분은 크기 감소가 전혀 없으므로, 무한 재귀에 빠지게 된다.

---

출처: 쉽게 배우는 알고리즘

쉽게 배우는 알고리즘 - 예스24