斐波那契斯威夫特游乐场
假设您正站在一个有n楼梯的楼梯前面。 您一次只能上一两个楼梯。 您到达顶部的独特方式的总数将是多少？
如果我们知道到达n-1和n-2的方法的数量，那么到达n点的总方法就是将这两个值相加。 这实际上与计算斐波那契数列的第n个数相同。 在这里，我试图提出解决斐波那契问题的不同方法，其中包括算法比较以及围绕时间和空间复杂度的讨论。
递归方法
我们可以从递归方法开始。 假设我们已经知道所有先前的数字，所以不用说当前数字是最后两个数字的和（自顶向下方法）。
func fib（_ n：Int）-> Int {
守卫n> 1 else {return n}
返回fib（n-1）+ fib（n-2）
}
时间复杂度：O（2 ^ n）
空间复杂度：O（2 ^ n）
该解决方案的问题在于，我们不断地重复计算相同的子问题。 换句话说，我们的算法做了很多重复的工作。 该算法呈指数增长，需要付出很多努力，尤其是当n大时。
迭代法
这种方法来自相同的想法，但稍有调整。 如果我们将所有值存储在数组中以备将来使用，则可以避免冗余工作。 每当再次调用该函数时，该函数将直接从备注数组返回结果。
func fib（_ n：Int）-> Int {
var fibs：[Int] = [1，1]
（2 ... n）.forEach {我在
fibs.append（fibs [i-1] + fibs [i-2]）
}
返回fibs.last！
}
时间复杂度：O（n）
空间复杂度：O（n）
只需对算法进行少量更改，我们就可以进行巨大的优化。 以n = 45为例，它需要90步（而我们的递归方法则超过了10亿步），大约快了1000万倍。
迭代方法-优化
我们真的不需要存储整个数组。 我们需要的是最后两个值：
func fib（_ n：Int）-> Int {
var a = 1
var b = 1
守卫n> 1 else {返回}
（2 ... n）.forEach {_ in
（a，b）=（a + b，a）
}
返回一个
}
时间复杂度：O（n）
空间复杂度：O（1）
在for循环内，我们将新值分配给（元组的美） a和b 。 如果您注意到方程(a, b) = (a + b, a)是黄金分割率的确切定义。
矩阵法的力量
让我们假设矩阵M为：
为了具有第n个斐波那契数，矩阵M必须与其自身相乘n-1次，并形成n-1次幂：
假设我们有一个很棒的方法multiply ，将两个矩阵相乘并返回结果矩阵，该算法将像这样简单：
func fib（_ n：Int）-> Int {
守卫n> 2 else {return n}
令M = [[1，1]，[1，0]]
var结果：[[Int]] = M
（1 .. <n）.forEach {_在结果中=乘以（结果，M）}
返回结果[0] [0]
}
时间复杂度：O（n）
空间复杂度：O（1）
矩阵方法的力量-优化
为了形成矩阵M的n次幂，我们不需要将其乘以n次。 这就是想法，假设您要计算5⁸，原始方法是将5乘以自身8次。 更好的方法是重复平方并加倍指数：
5²= 25
25²=5⁴= 625
625²=5⁸= 390,625
如您所见，这种平方方法比原始方法使用的乘法要少得多（三对八，换句话说就是减少对数）。 相同的想法适用于矩阵：
func fib（_ n：Int）-> Int {
var M = [[1，1]，[1，0]]
守卫n> 2 else {return n}
功率（＆M，n）
返回M [0] [0]
}
func power（_矩阵：inout [[Int]]，_ n：Int）{
守卫n> 1 else {return}
功率（＆matrix，n / 2）
矩阵=乘法（矩阵，矩阵）
如果n％2！= 0 {
令M = [[1，1]，[1，0]]
矩阵=乘（矩阵，M）
}
}
时间复杂度：O（log n）
空间复杂度：O（log n），由于递归堆栈
在上面的代码片段中， power函数尝试通过对第(n/2)次幂进行平方来计算M的第(n/2)次幂。 但是，如果n为奇数，则对n/2四舍五入并平方该M幂将得到第(n-1)次幂，再乘以M一个因数即可构成该单个因数。 这肯定是我们可以用来获得第n个斐波那契数的最快，最优化的算法。
您可能会问inout关键字或&符号，它们在我们的算法中并没有真正发挥重要作用。 它们只是让我们出于性能目的通过递归堆栈传递矩阵引用。 如果您想了解更多信息，请在Swift中查看“值类型与引用类型”。
如果您有任何建议，请让我知道，随时发表您的评论。 您可以在此处找到此帖子的所有代码。
斐波那契数
斐波那契数字程序— GeeksforGeeks
斐波那契难题
这篇文章致亚历克斯·斯米尔诺夫（Alex Smirnoff）一直在激励
这个故事发表在中等规模最大的企业家精神出版物The Startup中，紧随其后的是281,454人。
订阅以在此处接收我们的热门新闻。