算法分析与设计——2.7 快速幂算法
2021/10/20 20:39:46
本文主要是介绍算法分析与设计——2.7 快速幂算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题描述:给定一个正整数n和一个实数a,快速计算a^n。
输入:输入实数a 正整数n 。如(2,93)
输出:2^93的值
算法思想:
分治:求a^n的问题可以划分为求a^(n/2)的子问题。并有如下几个条件。
a=0,return 0;
n=0,return 1;
n=2k,return (a^(n/2))^2;
n=2k+1,return (a^(n/2))^2*a;
代码如下
template <typename T> T exp2(T a, int n) { if (a == 0)return 0; if (n <= 0)return 1; else { double x = exp2(a, n / 2); if (n % 2)return (a*x*x); else return (x * x); } }
非递归:可以利用二分法。如 计算a^93。n=93转化为二进制表示为:
所以a^93=a^64 * a^16 * a^8 * a^4 * a^1。
代码如下:
template<typename T> T exp2(T a, int n) { int i = n; double b = a, s = 1.0; while (i > 0) { if (i % 2)s *= b; i /= 2; b *= b; } return s; }
这两种实现方式的时间复杂度都是O(logn)。
这篇关于算法分析与设计——2.7 快速幂算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-08如何在敏捷项目中实现高效测试?
- 2024-07-08用户故事一定要有 “So that...” 吗?
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt