이론적으로는 로그 복잡성이지만 실제로는 선형 일

Question

X^y를 찾으려면 다음 코드를 살펴보십시오.

/* Find exponent in logarithmic complexity */ 
int findPower(int base, exponent){ 
    if(1 == exponent) return base; 
    return (findPower(base, exponent/2)*findPower(base, exponent-exponent/2)); 
} 

int main(int argc, char *argv[]){ 
    if(argc < 3) { 
     printf("Usage :: logpow baseNumber power\n"); 
     return -1; 
    } 
    printf("%s^%s = %d\n", argv[1], argv[2], findPow(atoi(argv[1]), 
                  atoi(argv[2]))); 
    return 0; 
} 

분석 결과 이것이 theta (log (n))의 복잡성을 보여줍니다. 하지만 그것은 여기에 시간을 측정하고 달렸다는 우리가 실제 시간 복잡도는 대수보다는 오히려 선형 동작을 가지고 있음을 알 수 위의 결과

Run 1: (calculating 1^500_million) 
user-lm Programming # time ./a.out 1 500000000 
1^500000000 = 1 

real 0m5.009s 
user 0m5.000s 
sys 0m0.000s 


Run 2: (calculating 1^1_Billion) 
user-lm Programming # time ./a.out 1 1000000000 
1^1000000000 = 1 

real 0m9.667s 
user 0m9.640s 
sys 0m0.000s 


Run 3: (calculating 1^2_Billion) 
user-lm Programming # time ./a.out 1 2000000000 
1^2000000000 = 1 

real 0m18.649s 
user 0m18.630s 
sys 0m0.000s 

있습니다!

이렇게 큰 차이가 나는 이유는 무엇일까요?

감사합니다, 귀하의 분석이 잘못

Answer 1

실제로 각 호출에서 2 개의 함수 호출을 호출합니다. 재귀 트리는 높이가 log(exponent) 인 이진 트리이므로 노드의 수는 2^log(exponent) == exponent이됩니다. 전체적으로 선형 알고리즘이됩니다. 당신은 더 나은 성능을 위해이처럼 다시 작성할 수 있습니다 :

int findPower(int base, int exponent){ 
    if(0 == exponent) return 1; 
    int temp = findPower(base, exponent/2); 
    if(exponent % 2 == 0) return temp * temp; 
    return temp * temp * base; 
} 

트릭은, 당신은 로그 복잡성을 얻기 위해 findPower(base, exponent/2)의 값을 저장해야합니다. 재귀 트리는 여전히 높이가 log(exponent)이지만 각 노드에는 이제 하나의 하위 노드 만 있으므로 log(exponent) 노드가 있습니다. 실제로이라고 두 번 부르면 은의 성능을 선형 이상으로 저하시킵니다. 이미 동일한 값을 계산할 필요가 없습니다.

@David Schwartz가 지적했듯이 exponent이 두 배로되면 코드에서 호출 된 횟수가 두 배가됩니다. 그러나 값을 저장할 때 exponent을 두 배로 설정하면 이 하나만 추가로 호출됩니다.

n

T(n) = 2T(n/2) + c

는 지수입니다 :

Answer 2

, 그것은 O (N)이다

마이크로 커널.

N을 10 억에서 20 억으로 늘리면 10 억에 대해 2 개의 전원 작업을 수행해야합니다. 따라서 N을 두 배로 늘리면 수행해야 할 작업이 두 배로 늘어납니다. 그건 O (N)입니다.

Answer 3

는 알고리즘의 복잡성의 공식적인 표현이있다.

T(n) = Theta(n)

을 제공하는 분석이 올바르지 않습니다.