1.3 시간 복잡도 예제
이 절에서는 코드만 보고 함수의 시간 복잡도를 빅오로 표현할 수 있는 예제를 살펴봅니다.
예제 1-1
int fun1(int n)
{
int m = 0;
for (int i = 0; i < n; i++) {
m += 1;
}
return m;
}
분석 시간 복잡도는 O(n)입니다.
예제 1-2
int fun2(int n)
{
int i, j, m = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
m += 1;
}
}
return m;
}
분석 시간 복잡도는 O(n2)입니다.