읽기 전
- 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다.
- 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.
매개 변수의 증가폭이 지수적으로 증가할 때 시간 복잡도
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$값에 따라 위 코드의 시간 복잡도는 가변적이다.
$k=1$일 때
$SUM = 1+2+\cdots+n = \cfrac{n(n+1)}{2}=\cfrac{n^2+n}{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}$
$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})$으로 표현할 수 있다.