斐波那契数列
斐波那契数列是一个经典的数学问题，同时也是算法中的经典案例，并且衍生出了很多类似的问题，这个问题简单来说就是当前数列的元素是由前两个数的和构成。不如举个栗子：
比如 F(0) = 0, F(1) = 1, 那么 F(2) = F(0) + F(1)，也就是说F(2) = 0 + 1 = 2，依次循环得出相关的数列内容。
所以依据这样的规律特点，我们可以写出下面的递推内容：
F(3) = F(2) + F(1)
F(4) = F(3) + F(2)
F(5) = F(4) + F(3)
F(6) = F(5) + F(4)
......
递归解法
这就明显感觉是迭代求值的关系，所以依据这样的特点，可以采用最基本的递归的方法去完成求值。实现内容如下：
func fibRecurrence(_ n: Int) -> Int {
if n == 0 {
return 0
}
if n == 1 {
return 1
}
return fib(n - 1) + fib(n - 2)
}
但是仔细看一下当前的时间复杂度，会发现是O(2^n)的，效率略微有点差。
正推法求值
递归的方法求值实际上是从n往0，反向递推求其值，但是这样有一个不好的地方在于重复计算了已经算过的值，例如在求解F(5)的时候内容如下:
F(5) = F(4) + F(3)
再去求解F(4)的时候，你会发现F(3)重复计算了两次，如下：
F(4) = F(3) + F(2)
按照此内容推下去，计算就会增倍了。如果按照正向递推的方式的话，就刚好解决了这样的问题，在求解F(5)的时候已经正向求解F(4)与F(3)的结果了，所以直接累加即可得其结果。所以按照这样的思路，我们可以正向递推求值：
func fibCount(_ n: Int) -> Int {
if n == 0 {
return 0
}
if n == 1 {
return 1
}
var curValue = 1
var preValue = 0
var resValue = curValue + preValue
for _ in 2...n {
resValue = curValue + preValue
preValue = curValue
curValue = resValue
}
return resValue
}
这个时间复杂度是O(n)的。
矩阵乘法
真正的O(n)就是最优解了嘛？答案是否定的，因为有个神级的解法，叫做升维跨越，可以将其时间复杂度变成O(logn)的，具体做法就是利用矩阵乘法。
矩阵推理
矩阵推理
所以经过一系列的推倒，矩阵变换成了如下的内容：
最终形式
所以这个递推升维公式就成功的将F(n)的求解变成了二维矩阵的求幂问题。
这里解释一下为什么要将左边的格式改成2x2的写法？原因很简单，是为了保证与右边的2x2保持对应，这样的话比较直观，很快就能确定F(n)对应于矩阵的哪个元素了。比如这里的F(n)=Martrix[0][1]元素。
矩阵求解问题转换
此时如果把矩阵内容看成一个元素x，那么右边的内容就变成了求解x的n次幂，这样的话，我们可以通过计算x的n次幂来求的x的值了
-
关于求解x的n次幂问题
这里有两种方式去计算x的n次幂。分别是拆分分治的方法与按位运算取值。分治递归方法如下：
/*
使用拆分法，又叫分治归并算法
由于每次计算均为减半运算
所以时间复杂度O(logn)
*/
func powSplit(_ x: Int, _ n: Int) -> Int {
if n == 0 {
return 1
}
if n == 1 {
return x
}
//偶数
if n & 1 == 0 {
return self.powSplit(x, n/2) * self.powSplit(x, n/2)
}
//奇数
return self.powSplit(x, (n-1)/2) * self.powSplit(x, (n-1)/2) * x
}
采用按位取值的方法如下：
func powByByte(_ x: Int, _ n: Int) -> Int {
if x == 0 {
return 0
}
if x == 1 {
return x
}
var localN = n
var localX = x
var result = 1
while localN != 0 {
//当前位有效，乘以权值
if localN & 1 != 0 {
result = localX * result
}
//移位之前要按位加权
localX = (localX * localX)
localN = localN>>1
}
return result
}
这里特别注意的一点是加权的时候，需要当前值的平方操作，如果按照二进制进行排列的话，当前位置的平方是下一位权重的权值内容。例如：
image.png
所以这里要乘以当前位的自身值，来确定下一个位的权重值内容。将矩阵看成幂乘积之后，会发现关于矩阵乘积的方法又涉及到矩阵相乘的问题。
矩阵乘法
矩阵乘法的概念这里就不多说了，直接看一下代码实现。
/*
矩阵乘法算法
*/
func MartrixMutiply(_ leftMartrix: [[Int]], _ rightMartrix: [[Int]]) -> [[Int]] {
var resMartrix = [[Int]]()
var rowArr = [Int]()
for row in 0..<leftMartrix.count{
for col in 0..<rightMartrix[0].count{
rowArr.append(self.countElementIndex(leftMartrix, row, rightMartrix, col))
}
resMartrix.append(rowArr)
rowArr.removeAll()
}
return resMartrix
}
/*
计算某行元素与某一列元素的乘积和
*/
func countElementIndex(_ leftArray: [[Int]], _ rowIndex: Int, _ rightArray: [[Int]], _ colIndex: Int ) -> Int {
//要符合两个矩阵相乘的前提
guard leftArray.count == rightArray[0].count else {
return -1
}
var result = 0
for index in 0..<leftArray.count {
result = result + leftArray[rowIndex][index] * rightArray[index][colIndex]
}
return result
}
最终我们通过将矩阵看成一个整体，对其内容的求解转变为求解x的n次方的问题，所以可以实现如下的代码：
/*
升幂运算，依据矩阵推倒公式，相关的算法例如求解x的n次幂:x^n
*/
func powMartrix(_ x: [[Int]], _ n: Int) -> [[Int]] {
//先变成单位矩阵
var result = [[1,0],[0,1]]
var localN = n
var localX = x
while localN != 0 {
if localN & 1 != 0{
result = self.MartrixMutiply(localX, result)
}
localX = self.MartrixMutiply(localX, localX)
localN = localN >> 1
}
return result
}
依据公式F(n)对应位置刚好在Martrix[0][1]的位置，所以直接返回当前元素的值也即可得出F(n)的结果。如下：
/*
测试求值
*/
func fibTestDemo(_ n: Int) -> Int {
let res = self.fibMatrix(n)
return res[0][1]
}
利用矩阵来完成斐波那契的问题，是目前所能发现的算法的最优解，时间复杂度位O(logn)，这样的优质解法我觉得还是有必要掌握一下的，毕竟属于基本算法的范畴，值得深思与思考，更能够加强我们分析问题的能力，这也是众多公司要求开发者理解并且会适当的使用算法的原因吧，总之，每天进步一点点，何乐而不为呢~
网友评论