시간 복잡도 계산 관련

[LMS1229]

제가 이전 PPT 에 O(g1(n))O(g2(n)) = O(g1(n)g2(n)) 로 계산하는 부분이 반복문과 재귀호출 같은 경우에 많이 쓰인다고 이야기드렸는데 재귀호출에서 어떻게 쓰이는 지, 자세한 설명이 필요한 것 같아 올립니다.

먼저, 재귀호출을 하게 된다면 재귀호출 별로 다시 재귀호출을 하는 횟수와 최종적으로 재귀호출이 종료되는 시점에서 수행하는 연산의 시간복잡도 O(g(n)) 가 존재합니다.

예시로 다음과 같은 함수가 있다고 가정합니다.

function f(n):
    if n==0:
        return;
    for i in [1,m]:
        f(n-1)

이 때, 각 재귀 호출 별로 함수 f(n) 에서 f(n-1)를 호출하는 횟수는 m번이고 이는 총 n번 반복하게 됩니다.
그렇다면 T(0)=O(g(n))=O(1), T(n)=O(m)T(n-1) 로 나타낼 수 있습니다.

따라서 T(n)=O(m)O(m)O(m)...O(m)O(1) = O(m^n) 과 같이 계산할 수 있습니다.

이는 위의 O(g1(n))O(g2(n)) = O(g1(n)g2(n)) 를 확장한 형태로서, 재귀 호출에서 시간 복잡도를 계산할시엔 이렇게 이용할 수 있습니다.