최악의 경우는 무엇입니까?

for(int i = 1 ; i < n ; i* = 2) 
for(int j = 1 ; j < i ; j* = 2)

누구나 설명 할 수 있습니까? 나는 그것이 log(n)*log(i)라고 생각한다. 맞습니까?최악의 경우는 무엇입니까?

2012-10-02 sanjay

이 루프는 중첩되어 있습니까? –

내가 생각하기에 nlog (i); 우리는 1에서 n 시간까지 실행되므로 n 일 것이고 n은 확실하지는 않지만 log (i) 일 것입니다. 그래서 그것은 n * log (i)가 될 것입니다; 당신이하는 말을 알려주세요. – Mudasar

@Mudasar 1에서 n까지 실행되지만 항상 2의 인수로 증가하므로, n * log (i)가 될 수 없다고 생각합니다. –

는

for (i = 1; i < n; i *= 2) 
    for (j = 1; j < i; j *= 2) 
     ...stuff...

"재료"는 1 + 2 + 3 + ... + 로그 (N) -1 회 실행한다고 가정한다. 1부터 N까지의 정수의 합이 N * (N + 1)/2이므로 최악의 경우 실행 시간은 O (log (n)^2)입니다.

2012-10-02 04:42:00

나는 그 이유에 동의한다. 나는 또한 그것을 경험적으로 점검했고 그것을 유지한다. –

답변