矩阵在编程中的一个小应用
2023-09-27 14:22:41 时间
比如我们已经知道f1=1,f2=1,fn=a*fn-2+b*fn-1。用普通方法求fn就是一个循环。从3循环到n,时间复杂度为O(n)。下面用另一种方法求fn的值。
设矩阵 A = B =
则A*B= *
=
A*A*B = A*(A*B) = *
=
A*A*….*B=A(n-2) *B = 式(1)
如何求一个数a的b次幂a^b(使用快速幂算法,时间复杂度为lgn)。
假设b=6,用二制表示就是2^2*1+2^1*1+2^0*0 (6的二进制为110)
则a^b=a^(2^2+2^1)=a^(2^2)*a^(2^1) 注:A^(x+y)=A^x*A^y
求a^b的C伪代码
result=1;
while(b!=0)
{
if(b& 1)
result= result*a
a= a*a;
b= b>>1;
}
利用式1求f(1000)的值,需要进行大概10次的矩阵乘法运算,每次矩阵乘法需要8次乘法运算和4次加算法运算共需要大约120次运算就可以求出f(1000)的值。比原来的1000次运算快了近10倍。构造矩阵主要是为了能够使用快速幂来加快运算。
相关文章
- 物联网技术在智慧物流中的应用
- Qt5开发从入门到精通——第十二篇三节(Qt5 事件处理及实例——多线程应用、服务器端编程、客户端编程)
- 【python入门到精通】python函数式编程与应用详解
- iOS应用开发详解
- HTML5开发移动web应用—JQuery Mobile(1)
- 甲骨文推出应用编程接口平台云服务
- LSI加入多核联盟参与编程与应用标准制定
- Visual Studio串口通信与测控应用编程实践
- 新编Excel会计与财务管理应用大全(2016实战精华版)
- 【*** C语言 数组与static 应用 编程实例(值得思考 附static总结)——习题8.1(2)(苏小红版C语言(第3版))】
- 基于遗传算法改进的粒子群GA-PSO算法求解微分方程,GA-PSO优化shubert函数及MATLAB编程实现,应用实例3
- 2015年云计算或将成为企业主流应用
- 中国人工智能学会通讯——机器学习在商务智能中的创新应用 1.2 基于人工智能的商业分析应用
- 开放数据中心联盟推8个云计算应用模型
- Android应用开发提高篇(3)-----传感器(Sensor)编程(转)
- Matlab与C/C++混合编程接口应用总结 .
- Jquery+Json+Handler文件结合应用实例
- C++中for_each的应用
- Linux 系统应用编程——进程基础
- Linux应用编程之多次打开同一个文件
- 在大型应用中使用 Redux 的五个技巧
- iOS7应用开发2、关于新版的IDE:XCode 5