효율성과 관련하여이 두 기능간에 차이가 있습니까?

Question

이 두 기능을 만났습니다. 다른 기능보다 효과적입니까? 첫 번째 기능에서 pow1(x^2, n/2) * x을 return x*pow1(x^2, n/2)으로 변경하면 어떻게됩니까?

int pow1(int x, int n){ 
if(n==0) 
    return 1; else 
if(n==1) 
    return x; else 
if("n is odd") 
    return pow1(x^2, n/2) * x ; else // change to return x*pow1(x^2, n/2) ? 
if("n is even") 
    return pow1(x^2, n/2); 
} 

int pow2(int x, int n){ 
p=1; 
for(int i=1;i<=n;i++){ 
    p = p*x; 
} 
return p; 
} 

Answer 1

먼저 O(logn)이고, 두 번째는 O(n)이다. 따라서 충분히 큰 n의 경우, 첫 번째 것은 빠릅니다.

Answer 2

두 번째 알고리즘은 n 개의 곱셈을 수행합니다. 첫 번째는 각각 비트에 대해 하나의 곱셈을 수행합니다. 이것은 n에서 대수를 만듭니다. 이 방법을 exponentiation by squaring이라고합니다.

pow1 (x^2, n/2) * x를 변경하여 첫 번째 함수에서 x * pow1 (x^2, n/2)를 반환하면 어떻게됩니까? 곱셈은 교환 가능하므로 아무 것도 변경되지 않습니다.

사이드 노드에서 일부 프로그래밍 언어에서 사용합니까 아니면 의사 코드입니까? 많은 언어에서 x^2는 x 제곱이 아니라 x와 2 사이의 비트 XOR을 나타냅니다. x를 제곱하려면 x * x를 사용하면됩니다.