递归 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();
}

对于第一个时间复杂度函数将是-

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

最后一个是-

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

正确吗？

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)

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

recursive X^N algorithm time complexity

algorithm

time-complexity