(알고리즘/주 2) 교과서 1장 실습 #34

by

문제

34. 아래 중첩 루프의 시간 복잡도 T(n)은 얼마입니까? 모든 경우를 고려하면 너무 복잡하므로 n이 2의 거듭제곱이라고 가정할 수 있습니다.

즉, 양의 정수 k에 대해 n = 2^k입니다.

나는 = 엔;
( I >= 1 ) 동안
{
j-i;
동안 ( j <= n ) {
// Θ(1)이 걸립니다.


 j = 2 * j;
}
나는 = 나는 / 2;
}

답변

T(n) = O(n log n)

'추천 관련글,

설명

외부 루프에서 i는 i를 1/2로 줄임으로써 log n번 반복되고 내부 루프에서는 j가 i에서 시작하여 2배 증가하므로 j가 log n번 반복됩니다.

내부 루프의 본체는 일정한 시간이 걸리므로(즉, 시간 복잡도 O(1)) 위 중첩 루프의 시간 복잡도 T(n)은 O(nlogn)입니다.

확인


ChatGPT 선생님께 물어보니…