[Algorithm] HW2

rlawlgus·2023년 3월 9일

시간 복잡도 분석

문제 소개

1장 34번 문제

What is the time complexity T(n) of the nested loops below? For simplicity, you may assume that n is a power of 2.
That is, n = 2k for some positive integer k.

중첩 루프의 시간 복잡도 T(n)은 얼마인가?
간단하게 하기 위해, n의 2의 거듭제곱이라고 가정할 수 있다.
즉, 몇몇 양의 정수 k에 대해 n = 2k이다.

i = n ;
while ( i >= 1) {
	j = i ;
	while ( j <= n) {
		< body o f the while loop> //Needs ( 1 ) .
		j = 2 * j;
	}
	i = floor(i /2) ;
}

문제 해결

문제 해결해보기
솔루션 없이 문제를 해결하기
중첩된 루프는 모든 인덱스 쌍(i,j)에서 반복됩니다. 여기서 0 ≤ i,j < n. 외부 루프는 i의 모든 가능한 값에 대해 반복되는 반면, 내부 루프는 각 i에 대해 모든 가능한 j의 모든 값에 대해 반복된다. 따라서, 반복의 총 수는 외부 루프의 반복 횟수와 내부 루프의 반복 횟수의 곱이다.

외부 루프는 n번 반복되는데, 이는 문제 문장에서 주어진 것처럼 일부 양의 정수 k에 대해 2k이다. 내부 루프는 또한 외부 루프에서 i의 각 값에 대해 n번 반복된다. 따라서 총 반복 횟수는 다음과 같습니다:

T(n) = n n = (2k) (2k) = 2(2k) = 2n

중첩 루프의 시간 복잡성은 O(n^2) 또는 동등하게 O(2^(2k))이다.

i = n ;
while ( i >= 1) {
	j = i ;
	while ( j <= n) {
		< body o f the while loop> //Needs ( 1 ) .
		j = 2 * j;
	}
	i = floor(i /2) ;
}

T outer(n) = n
T inner(n) = 2n

중첩 루프의 시간 복잡성은 다음과 같이 분석할 수 있다:

외부 루프는 log_2(n)번 반복하는데, 이는 i가 1이 될 때까지 각 반복에서 반으로 줄어들기 때문이다.

내부 루프는 외부 루프의 각 반복에 대해 log_2(n)번 반복한다. 외부 루프의 첫 번째 반복에서는 내부 루프가 n/2회(j=i=n으로 시작) 반복되고, 외부 루프의 두 번째 반복에서는 내부 루프가 n/4회(j=i=n/2로 시작) 반복됩니다. 내부 루프의 반복 횟수는 다음과 같이 표현할 수 있다:

n/2 + n/4 + n/8 + ... + 2 + 1

이는 비율이 1/2이고 n-1의 합을 갖는 기하급수이다:

n/2 + n/4 + n/8 + ... + 2 + 1 = n-1

따라서, 내부 루프의 총 반복 횟수는 (log_2(n)(n-1)이다.

while 루프의 본문은 실행하는 데 일정한 시간이 걸리기 때문에, 중첩된 루프의 총 시간 복잡도는 다음과 같다:

T(n) = c(log_2(n))(n-1)

따라서 중첩 루프의 시간 복잡도는 O(n log n)입니다.

비교

원래 솔루션과 제공된 솔루션의 차이점은 무엇인가?
제공 솔루션

Solution: T(n) = (log2n + log n)/2 = O(log2n)

증명 및 차이점

원래 솔루션과 제공된 솔루션의 차이점은 무엇인가?
외부 루프는 log2(n) + 1번 반복하는데, i는 0에 도달할 때까지 각 반복에서 2로 나누기 때문이다. 반복 횟수는 1에 도달하기 전에 2로 나눌 수 있는 횟수이므로 log2(n)입니다. "+1"은 i가 n일 때 루프도 한 번 실행된다는 사실에서 비롯된다.

내부 루프는 외부 루프에서 i의 각 값에 대해 log2(n) - log2(i) + 1회 반복합니다. 이는 j가 i에서 시작하여 n에 도달할 때까지 각 반복에서 2를 곱하기 때문이다. 반복 횟수는 log2(n) - log2(i)입니다. 이는 n에 도달하기 전에 i에 2를 곱할 수 있는 횟수이기 때문입니다. "+1"은 j가 i와 같을 때 루프도 한 번 실행된다는 사실에서 비롯된다.

따라서 총 반복 횟수는 다음과 같습니다:

T(n) = (log2(n) + 1) (log2(n) - log2(1) + 1) T(n) = (log2(n) + 1) (log2(n) + 1)