如何找到算法的時間複雜度

Question

我應該找到這種算法的時間複雜性，但我不知道我完全理解如何去做這件事。任何人都可以幫我解釋一下，如何找到這種算法的大O標記複雜性？

給出的整數

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; 

我所要求的是對如何處理問題像這樣的解釋[1，...，N]數組中。

Answer 1

由於j在內部循環開始之前總是被設置爲1，然後在整數除法時變爲0，那麼內部循環總是隻運行一次。因此該代碼可以看出這樣的，消除了可變Ĵ的操作，不影響整體的時間複雜度：

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）。