C|利用二分思维实现一个数的整数次方计算(对数阶效率)

C|利用二分思维实现一个数的整数次方计算(对数阶效率)通常 计算一个数的整数次方的简单粗暴的方法是用一个循环 其时间复杂度为 long n double pow double x int n 这里没有考虑 n 为负数的情况 double ret 1

大家好,欢迎来到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-

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/94868.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信