C｜利用二分思维实现一个数的整数次方计算（对数阶效率）

大家好，欢迎来到IT知识分享网。

通常，计算一个数的整数次方的简单粗暴的方法是用一个循环，其时间复杂度为long(n);

double pow(double x, int n) // 这里没有考虑n为负数的情况 { double ret = 1.0; for(int i=1;i<=n;i++) ret *= x; return ret; }

简单直接粗暴的思路往往不是最佳解法，如我们计算，不会机械地计算= 2*2*2*2*2*2*2*2*2*2 = 1024

化简为=4*8*=32*32=1024

来计算就要简单些。

对于,其中的n可以可以表示为序列：的某个组合之和，也就是：

+ … (b==0 || b==1)

(b==0 || b==1)

关于指数n的迭代关系，有点像10进制求二进制，如将一个十进制数打印出二进制位：

void intPrintBinary(int n) { if(n<=0) return; if(n!=0) { intPrintBinary(n/2); printf("%d",n%2); } }

计算一个数的整数次方，，有如下伪代码：

double ret = 1; while(n>0{ if(n%2 == 1) // 相当于上述表达式中 (b==0 || b==1) ret *= x; // 连乘 n /=2； // 指数连续二分迭代 x *=2; // 相当于上述表达式中 x^2^i }

伪代码转换为代码：

#include <stdio.h> double pow(double x,int n) { double ret = 1.0; while(n>0) { if(n%2==1) // 相当于上述分析中的 (b==0 || b==1) ret *= x; // 当b==1时，项的值迭代到结果中 x *= x; // 相当于上述分析中 x^2^i n /= 2; // 对应x^2^i，x以自身倍数迭代增长，n以二分自己减小 } return ret; } int main() { for(int i=1;i<100;i++) printf("%10.2f\n",pow(i+i*.1,3)); getchar(); }

能以二分方法解决的问题的时间复杂度为O(long2n)，如上例，问题的边界为(0,n)，以n /= 2来迭代n，直到n==0，迭代的次数为log2n。

-End-