의사 코드의 실행 시간 결정

Question

런타임 T (n)을 결정하려는 다음 의사 코드가 있습니다. 누군가 따라야 할 단계를 줄 수 있습니까?

i := 1; 
while (i <= n) 
    j := i; 
    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

내 계산이 잘못없는 경우가 O(log log N)을 생각 : 다음은 코드입니다.

먼저 루프 시간에 영향을주지 않는 행을 생략하고 배열 임의 방문을 O(1)으로 가정합니다.

i := 1; 
while (i <= n) 
    j := i; 
    while (j > 0) 
     j = j/2; 
    i = 2 * i; 
return y; 

그러면 한 행의 모든 ​​연산이 O (1)에서 수행되었다고 가정하고 결과를 더합니다. (나는 또한 루프 시간에 영향을주지 않는 작업을 생략) 우리는 여러 차례의 조각을 실행하고 시간의 성장을 참조하십시오

수학 분석 외에, 우리는 또한 계산 사용할 수 있습니다.

#include <iostream> 
using namespace std; 

int main(){ 
    long long i, j, n; 
    double cost; 
    clock_t start, finish; 
    i = 1; 
    n = 1000000000000; 
    start = clock(); 
    while (i <= n) { 
     j = i; 
     while (j > 0) { 
      j = j/2; 
     } 
     i = 2 * i; 
    } 
    finish = clock(); 
    cout << (double)(finish - start)/CLOCKS_PER_SEC << endl; 
}