网站建设中需要注意的问题,网站应具有的功能模块,wordpress需要的系统,wordpress vtrois算法之矩阵计算斐波那契数列 本节内容 斐波那契介绍普通方式求解斐波那契矩阵概念矩阵求幂矩阵求解斐波那契1.斐波那契介绍 斐波那契数列有关十分明显的特点#xff0c;那是#xff1a;前面相邻两项之和#xff0c;构成了后一项。即f(n)f(n-1)f(n-2),f(0)0,f(1)f(2)1,推导下… 算法之矩阵计算斐波那契数列 本节内容 斐波那契介绍普通方式求解斐波那契矩阵概念矩阵求幂矩阵求解斐波那契1.斐波那契介绍 斐波那契数列有关十分明显的特点那是前面相邻两项之和构成了后一项。即f(n)f(n-1)f(n-2),f(0)0,f(1)f(2)1,推导下去f(3)2,f(4)3,f(5)5。。。。。。 2.普通方式求解斐波那契 按照上面提供的推导公式普通方式求解斐波那契数列代码如下 1 def normal(n):
2 a,b,c0,1,1
3 while n:
4 a,b,cb,c,bc
5 n-1
6 return a 使用上面的方式求解第n项斐波那契数列的时间复杂度为O(n),也就是说时间复杂度随着n的增长而线性增长。 3.矩阵概念 开始先来介绍一下矩阵的概念在数学中矩阵Matrix是一个按照长方阵列排列的复数或实数集合最早来自于方程组的系数及常数所构成的方阵。 这里不介绍矩阵的各方面知识了如果那样的话。。。就是一篇数学笔记了。。。这里只讲解矩阵相乘的概念。 矩阵相乘矩阵相乘最重要的方法是一般矩阵乘积。它只有在第一个矩阵的列数column和第二个矩阵的行数row相同时才有意义。一般单指矩阵乘积时指的便是一般矩阵乘积。一个m×n的矩阵就是m×n个数排成m行n列的一个数阵。由于它把许多数据紧凑的集中到了一起所以有时候可以简便地表示一些复杂的模型。 设A为m*p的矩阵B为p*n的矩阵那么称m*n的矩阵C为矩阵A与B的乘积记作CAB 4.矩阵求幂 上面已经介绍过了矩阵相乘的概念了那么斐波那契该怎么由矩阵标示呢 从第三项开始每一项都是前两项之和。 F(n)F(n−1)F(n−2), n⩾3 把斐波那契数列中 相邻的两项F(n)和F(n−1)写成一个2×1的矩阵。 斐波那契数列用矩阵推导如下 求F(n)等于求二阶矩阵的n - 1次方结果取矩阵第一行第一列的元素。 问题转换为二阶矩阵的n次幂。 而计算二阶矩阵的N次幂运算由于二阶矩阵乘法满足结合律这样可以快速计算二阶矩阵的n次幂运算。 假设A为一个二阶矩阵则A的幂运算满足下面的条件 A**6A**3∗A**3 A**7A**3∗A**3∗A**1A**4*A**2*A**1 在这里我们可以类似地把A看做是二进制中的22**72**4*2**2*2**1也就是说可以把矩阵的幂转换成二进制来表示。从而可以将n次幂拆解成长度为logn的二进制数来表示7111(二进制)。 这就是快速求二阶矩阵的核心方法。 5. 矩阵求解斐波那契 前戏做足了下面就该秀代码了。 1 def multi(a,b): # 计算二阶矩阵的相乘2 c[[0,0],[0,0]] # 定义一个空的二阶矩阵3 for i in range(2):4 for j in range(2):5 for k in range(2): # 新二阶矩阵的值计算6 c[i][j]c[i][j]a[i][k]*b[k][j]7 return c8 9
10 def matrix(n):
11 base[[1,1],[1,0]] # 元矩阵这里可以把元矩阵看做是2**01
12 ans[[1,0],[0,1]] # 结果矩阵 最开始的结果矩阵也可以看做是1因为这个矩阵和任意二阶A矩阵相乘结果都是A
13 while n:
14 if n1: # 取n的二进制的最后一位和1做与运算如果最后一位是1则进入if体内部
15 ansmulti(ans,base) # 如果在该位置n的二进制为1则计算ans和base矩阵
16 basemulti(base,base) # base矩阵相乘相当于初始base矩阵的幂*2
17 n1 # n的二进制往右移一位
18 return ans[0][1] # 最后获取到的二阶矩阵的[0][1]即f(n)的值 最后把例子的完整代码贴出来 1 import time2 3 4 def multi(a,b):5 c[[0,0],[0,0]]6 for i in range(2):7 for j in range(2):8 for k in range(2):9 c[i][j]c[i][j]a[i][k]*b[k][j]
10 return c
11
12
13 def matrix(n):
14 base[[1,1],[1,0]]
15 ans[[1,0],[0,1]]
16 while n:
17 if n1:
18 ansmulti(ans,base)
19 basemulti(base,base)
20 n1
21 # for i in range(2):
22 # print(ans[i])
23 return ans[0][1]
24
25 def normal(n):
26 a,b,c0,1,1
27 while n:
28 a,b,cb,c,bc
29 n-1
30 return a
31
32 nint(input())
33 starttime.time()
34 print(Normal:,normal(n))
35 print(use:,time.time()-start)
36 starttime.time()
37 print(Matrix:,matrix(n))
38 print(use:,time.time()-start)
39 #计算结果
40 65536
41 Normal: 731992144602......
42 use: 0.07219505310058594
43 Matrix: 731992144602......
44 use: 0.023076772689819336 可以看出来当n的值越来越大的时候两种方式计算出结果的时间差距将越来越大正常的计算时间复杂度是O(n),矩阵求值的时间复杂度是O(logn)。 后记 由此可以看出使用推导式f(n)f(n-1)f(n-2)求斐波那契的第n项的算法复杂度极限为O(n)这是一维世界下的极限。将其从一维上升到二维用二阶矩阵推导斐波那契数列时计算的算法复杂度为O(logn)也就是说使用升维的手段将一维空间进行扭曲从而将距离缩短可以更快的计算出结果。 由此推导出如果人来要突破光速的极限需要将现有的三维空间升级到四维空间扭曲空间从而缩短距离达到突破光速的目的。 转载于:https://www.cnblogs.com/huxianglin/p/5995649.html
