Analysis of Algorithms | Time Complexity of Loop with Powers

읽기 전

• 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다.
• 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.

매개 변수의 증가폭이 지수적으로 증가할 때 시간 복잡도

void fun(int n, int k) 
{ 
    for (int i=1; i<=n; i++) 
    { 
      int p = pow(i, k);  
      for (int j=1; j<=p; j++) 
      { 
          // Some O(1) work 
      } 
    } 
} 

위 코드의 전체 수행 시간은 $1^k+2^k+\cdots+n^k$인 제곱수들의 합으로 표현할 수 있다. 즉, $k$값에 따라 위 코드의 시간 복잡도는 가변적이다.

1. $k=1$일 때

   $SUM = 1+2+\cdots+n = \cfrac{n(n+1)}{2}=\cfrac{n^2+n}{2}$

2. $k=2$일 때

   $SUM = 1^2+2^2+\cdots + n^2 = \cfrac{n(n+1)(2n+1)}{6}=\cfrac{n^3}{3}+\cfrac{n^2}{2}+\cfrac{n}{6}$

3. $k=3$일 때

   $SUM = 1^3+2^3+\cdots+n^3={\cfrac{n(n+1)}{2}}^2=\cfrac{n^2}{4}+\cfrac{n^3}{2}+\cfrac{n^2}{4}$

요약하자면 점근적 관점에서 복잡도는 $\cfrac{n^{k+1}}{k+1}$가 가장 큰 지수를 가지므로 시간 복잡도는 $\theta(\cfrac{n^{k+1}}{k+1})$으로 표현할 수 있다.

참고자료

1. Time Complexity of Loop with Powers