UC知道算X的N次的两种算法之间的效率问题（用C）
来源：百度知道 编辑：UC知道 时间：2024/05/21 18:34:28
算法一是用N-1次乘法计算，而算法二则是用了迭代，这两种算法计算X的N次都是正确的，但计算时间复杂度时，第一种为O（N），第二种算法的时间复杂度虽然不好计算，但是可以明显看出来当N足够大的时候，第二种算法的效率显然高很多，可是我在实际测试的过程中，同样是计算1.0001的1000次，第二种算法居然比第一种算法慢3倍多！！这让我很不理解，希望哪位高手帮我看一下。
int IsEven(long n)
{
if(n/2==0)
return 1;
else
return 0;
}
double Algo1(double X, long int N)
{
long int i;
double Mul;
if(N==0)
return 1;
Mul=X;
for(i=1;i<=N-1;i++){
Mul=Mul*X;
}
return Mul;
}
double Algo2(double X, long int N)
{
double X1=1.0, X2;
X2=X;
if(N==0)
return 1.0;
if(N==1)
return X;
while(N>1)
{
if(IsEven(N))
{
X2=X2*X2;
N=N/2;
}
else
{
X1=X1*X2;
N=N-1;
}
}
return X1=X1*X2;
}
这是我用的测试程序：
void Measure(double X, long int N, int n
int IsEven(long n)
{
if(n/2==0)
return 1;
else
return 0;
}
double Algo1(double X, long int N)
{
long int i;
double Mul;
if(N==0)
return 1;
Mul=X;
for(i=1;i<=N-1;i++){
Mul=Mul*X;
}
return Mul;
}
double Algo2(double X, long int N)
{
double X1=1.0, X2;
X2=X;
if(N==0)
return 1.0;
if(N==1)
return X;
while(N>1)
{
if(IsEven(N))
{
X2=X2*X2;
N=N/2;
}
else
{
X1=X1*X2;
N=N-1;
}
}
return X1=X1*X2;
}
这是我用的测试程序：
void Measure(double X, long int N, int n
可能有出栈操作吧，次数多了就表现出来了
2的赋值运算比较运算和乘法除法太多，尤其是乘除法太多会影响效率。IsEven()调用函数也会浪费时间。在n比较小的情况下1会比2快，但是n大了以后2应该会比1快 。
给你一个我写的函数，效率应该很快，你测试一下（记得把int改成double)
int fun(int m, int n)
{
if(n == 0 && m != 0) return 1;
int fac = m;
int r = 1;
while(n > 0)
{
if(n&1)
{
r*=fac;
}
fac*=fac;
n >>= 1;
}
return r;
}
采用2进制思想和位运算
IsEven()是形参调用，函数每次调用都会复制一个'N'，在内存的中划出一段存储N的值，然后对N进行操作后再返回值，耗用了大量cpu时间。解决办法是用引用，或指针调用。如：IsEven(long & n){...}
我刚才也试了下确实1比2快，仔细想了下发现是你的迭代有问题，迭代用于条件判断当然不会提高速度，应把迭代用于乘法运算中。