递归X^N算法的时间复杂度

Question

我有两个C程序

其中输入的N应是任意整数2^N：N> = 1

一个是 -

int power(int x,int n) 
{ 
if(n==2) 
return x*x; 
else 
return power(x,n/2)*power(x,n/2); 
} 
int main() 
{ 
    int x=6; 
    int n=8; 
    printf("%d",power(x,n)); 
    getch(); 
} 

其他一个是 -

int power(int x,int n) 
{ 
if(n==2) 
return x*x; 
else 
{ 
int result=power(x,n/2); 
return result*result; 
} 
} 
int main() 
{ 
    int x=6; 
    int n=8; 
    printf("%d",power(x,n)); 
    getch(); 
} 

这是第一次复杂的功能将是─

因此，通过推导，我们将得到 O(log n)

在过去的一个210

T(n)=2T(n/2)+c将通过推导，我们将得到O(log n)

是正确的是─

T(n)=T(n/2)+c因此？

Answer 1

对于第一种关系，你实际上有

T(n) = 2 T(n/2)+c = 2^2*T(n/2^2) + 2c+c = ... 
= 2^(k-1)*T(n/2^(k-1)) + (k-1)*c+(k-2)*c+...+c = 
= 2^(k-1)*T(2) + (k-1)*k*c/2 = n/2 + c*(log n-1)(log n)/2 = O(n) 

，因为你有n=2^k和n/2主导c*(log n)^2（如n趋于无穷n/2变得比c*(log n)^2大得多）。

对于第二个你是对：

T(n) = 2*T(n/2)+c = T(n/2^2) + 2c = ... = T(n/2^(k-1)) + (k-1)c = T(2)+(k-1)*c= 
= 1 + c*(logn-1) = O(log n)