六十八、快速幂算法、牛顿迭代法、累加数组+二分查找的变形

@Author：Runsen

编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。 ---- Runsen

上次介绍了二分查找算法及其四个变形问题，下面介绍二分法常用的场景和典型的例题。

快速幂算法

题目是来自Leetcode：50. Pow(x, n)，https://leetcode-cn.com/problems/powx-n/

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

  

 

  
1
  
2
  
3
  
4
 

其实快速幂相关的问题，个人觉得只要你是一名程序员，就必须要掌握快速幂算法。

当我们遇到一个问题需要让我们求得一个数 n 的 m 次方，那么最简单的方法是将 n 乘以 m 次，得到结果，但是如果我们现在需要计算的是 2^10000000 这样的式子呢，显然如果我们的程序需要计算 2 的更高次方的时候这样的算法，对于算法竞赛而言时间上显然是不允许的，因此提出了快速幂算法。

其实在计算这样的式子的时候有大量的运算步骤是可以避免的，我们现在拿 2 8

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/108279533