시간 복잡성 중첩 루프

Question

문제 : 나는 큰 세타있어

s <-- 0; 
i = 2; 
while (i <= n^2) do 
    for j <-- i to 2i[ln(i)] do 
     s <-- s + i - j; 
    end 
    i <-- i + 2; 
end 
return (s); 

(N^2 (LN (N)) 루프에 대한 가입일 :

이 기능의 복잡성 (큰 세타를) 찾기 2i [ln (i)] - i times (ci [ln (i)) 시간이 될 것입니다. 그리고 나서 while 루프의 대략적인 시간이기 때문에 n^2로 곱합니다. 그것은 다른 방식으로 큰 세타 (n^4)를가집니다.

내 대답 중 하나가 맞다면, 그리고 루프가 의존적 인 경우 독립적 인 경우 이러한 문제를 해결하는 방법에 대한 혼란을 기반으로하는지 잘 모르겠습니다.

Answer 1

가장 강력한 솔루션은 2 <= i <= n^2/2에 대해 2*(2i)*ln(i) - 2i + 1을 합하는 것입니다. 우리는이 :

이

1 + 2 + ... + floor(n^2/2) = O(n^4) 

반면 님의

1*ln(1) + ... + floor(n^2/2)*ln(floor(n^2/2)) = O(n^4*ln(n)) 

(. 상수 4이 고려 될 필요가 없다)

사실, 당신도 얻을 수있는 표현 점근 적으로 동등한 comparison with an integral을 사용하는 합계입니다.

따라서 시간 복잡도는 O(n^4*ln(n))-O(n^4)+O(n) = O(n^4*ln(n))입니다.

MathJax 글쓰기 수학을 사용하지 않은 경우 고통은 here is a more detailed proof입니다.