서로 영향을 미치는 루프 런타임을 어떻게 찾을 수 있습니까?

Question

나는 (하나라도있는 경우) 루프의 이러한 종류의 기술 용어 확실하지 않다, 그래서 예를 들어 제공 할 것입니다 :이 예에서

x=0 
i = 1 
while(i<n) 
    for(j=1 to n/i) 
     x = x + (i-j) 
    i*=2 
return(x) 

을, while 루프 직접 배의 수를 변화 어떤 이유로 나를 던지고있는 루프 실행을 위해

일반적으로 줄 단위로 이동하여 각 줄이 몇 번 실행되는지 확인하지만 횟수가 변경되기 때문에 합계를 시도했지만 조금 잃어버린 ...이 유형의 문제를 해결하기 위해 어떤 방법으로 단계적으로 될 것입니까? 당신이 알고있는 경우

주석에 답은 O (N),하지만 난 이런 짓을 할 때 내가 어떤 도움에 감사드립니다

(N) nlog있어, 이것은 또한 내 최종

에 대한 리뷰 기사입니다 이런 종류의 연습 문제를 발견하기에 좋은 곳이라면 고맙겠습니다!

는

Answer 1

이 코드에 대한 분석은 최대 힙을 구축하는 절차의 실행 시간을 찾으려면이 lecture의 것과 매우 유사하다 생각 감사드립니다. 그것의 간단한 분석 결과 nlgn 복잡하지만 summations을 사용하여 분석했을 때 그것은 당신의 문제와 마찬가지로 n 것으로 밝혀졌습니다.

그래서 질문에, 바깥 쪽 루프는 번 실행하고 내부 실행 n/i. 그러나 지수 적으로 커지기 때문에 루프 반복에서 한 번 증가 된 다른 변수 j를 사용할 수 있으므로 합계에 사용할 수 있고 관계 에 따라 경계를 변경할 수 있습니다.

합산 합은 그 결과이며, n은 무한대 때 그래서, 그것은 일정한 수렴 기하학적 시퀀스 이다 (2). 따라서 합계는 일정한 요소로 간주되며 O (n) 만인 코드의 점근 적 복잡성에는 영향을 미치지 않습니다.