x^n的快速算法

pupilzeng

计算x^n的一个快速算法，时间复杂度大约是Log2(N)。
采用二分法：比方说算x^10:
x^10 = (x^5) * (x^5)
x^5   = (x^2) * (x^2) * x
x^2   = x * x
存在的问题：没有验证是否溢出。
实际意义不是很大，纯粹是为了好玩，不知道有没有人做过了。

1. 
   
2. double
   
3. fastpower(double x, unsigned long n)
   
4. {
   
5.         int i = 0;
   
6.         double ret = x;
   
7.         unsigned long m = n;
   
8.         if(!n)
   
9.                 return 1;
   
10.         /* to get the effective bits (low non-zero bits)
    
11.          * i.e. 5(101)->3, 1024(10000000000)->11
    
12.          * */
    
13.         for(i = 0; m; i++)
    
14.                 m >>= 1;
    
15. 
    
16.         /* most significant bit -> least significant bit
    
17.          * if the bits is 1: result = pri^2 * x;
    
18.          * if the bits is 0: result = pri^2
    
19.          * */
    
20.         for(i -= 1; i > 0; i--){
    
21.                 ret *= ret;
    
22.                 if(n & (1 << (i-1))){
    
23.                         ret *= x;
    
24.                 }
    
25.         }
    
26. 
    
27.         return ret;
    
28. }
    

复制代码

弥敦路九号

不错，不错。

pank7.yardbird

这个的时间复杂度为什么是log2（n）？

pupilzeng

Post by pank7.yardbird
这个的时间复杂度为什么是log2（n）？

为什么不是?
从我上面的例子看起来不是吗?我指的是乘法的复杂度

rickxbx

我们是否可以考虑一下 n 的取值范围?

jszhang3

用数组再结合楼主的二分法就完美了

gooddaytolinux

假设X=10
10X10，和100X100，和100000X100000
计算的时间会一样？
算时间复杂度都是算指令周期的，一般来说只有加法，逻辑运算等是一个指令周期的。

pupilzeng

Post by jszhang3
用数组再结合楼主的二分法就完美了

数组？怎么用？你的意思是防止溢出，还是什么？

pupilzeng

Post by gooddaytolinux
假设X=10
10X10，和100X100，和100000X100000
计算的时间会一样？
算时间复杂度都是算指令周期的，一般来说只有加法，逻辑运算等是一个指令周期的。

没有这样算吧？
要是这样的话，你根本就没有办法估算时间的复杂度了，因为很多时候，你根本就不知道编译器将它编译成什么指令了，这时你又怎么计算指令周期呢？
一般时间复杂度都是计算循环体中的某一个步骤，至于这个步骤的时间跟规模的关系，这不是这个算法的复杂度的事情了，应该归到这个步骤的复杂度中去考虑。

gooddaytolinux

Post by pupilzeng
没有这样算吧？
要是这样的话，你根本就没有办法估算时间的复杂度了，因为很多时候，你根本就不知道编译器将它编译成什么指令了，这时你又怎么计算指令周期呢？
一般时间复杂度都是计算循环体中的某一个步骤，至于这个步骤的时间跟规模的关系，这不是这个算法的复杂度的事情了，应该归到这个步骤的复杂度中去考虑。

首先 时间复杂度是一个理论问题，和编译器无关 。
其次 时间复杂度是用来衡量算法的所需要的计算时间的，如果用步骤作为时间复杂度计量单位，每个步骤得复杂度千差万别，怎么用时间复杂度比较两个算法的优劣。

ps：你最好仔细看看时间复杂度的定义和计算方法