알고리즘의 시간 복잡성을 찾는 방법

Question

이 알고리즘의 시간 복잡도를 알아야 겠지만이 문제를 해결하는 방법을 완전히 이해하고 있는지 잘 모르겠습니다. 누구든지이 알고리즘에 대해 big-O 표기법으로 big-tome 복잡도를 찾는 방법을 설명해 주시겠습니까?

주어진 배열 A [1, ..., n]은 정수

i := 1; 
x := 0; 
while(i <= n) 
    j := 1; 
    x := x+A[i]; 
    while(j > 0) 
     y := x/(2*j); 
     j = j/2; //Assume here that this returns the floor of the quotient 
    i = 2*i; 
return y; 

내가 무엇을 해달라고 부탁하는 것은 이와 같은 문제에 접근하는 방법에 대한 설명이다의.

Answer 1

내부 루프가 시작되기 전에 j이 항상 1로 설정되고 정수 나누기에서 0이되면 해당 내부 루프는 항상 정확히 한 번만 실행됩니다. 결과적으로 코드가 전체 시간의 복잡성에 영향을주지 않는 변수 J의 운영, 제거, 다음과 같이 볼 수 있습니다 :

i := 1; 
x := 0; 
while(i <= n) 
    x := x+A[i]; 
    y := x/2; 
    i = 2*i; 
return y; 

이 으로 내가 2의 거듭 제곱의 순서를 통해 갈 것이다, 나머지 루프는 1 + floor (log (n)) 번 반복됩니다.

일정 시간 내에 산술 연산이 수행된다고 가정하면 시간 복잡도는 O (log n)입니다.