通过斐波那契数列探讨时间复杂度和空间复杂度

男娘i 2022-11-25 10:28 45阅读 0赞

**目录**

1.斐波那契数简介

2.计算斐波那契数

3.时间复杂度计算

4.空间复杂度计算

5.斐波那契非递归实现

6.怎么在时间复杂度O(1)，空间复杂度O(1)下计算斐波那契数

--------------------

# 1.斐波那契数简介 #

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N\*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

这个问题并不是很复杂，但是从这个问题本身来分析时间复杂度和空间复杂度问题。

# 2.计算斐波那契数 #

序列依次为1,1,2,3,5,8,13,21，...问题：怎么求出序列中第N个数字？递归需要注意退出条件，避免死循环。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70][]

如果使用递归的话，当输入比较大数字40或者更大的数字的时候，就会计算非常慢，甚至计算不出结果。这个时候我们就要计算算法的时间复杂度和空间复杂度，首先我们看一下时间复杂度。

# 3.时间复杂度计算 #

我们通过上面那个程序，我们通常通过递归树的方式计算这个递归的时间复杂度。求解F(n),必须先计算F(n-1)和F(n-2),计算F(n-1)和F(n-2)，又必须先计算F(n-3)和F(n-4)。。。。。。以此类推，直至必须先计算F(1)和F(0),然后逆推得到F(n-1)和F(n-2)的结果，从而得到F(n)要计算很多重复的值，在时间上造成了很大的浪费，算法的时间复杂度随着N的增大呈现指数增长，**时间的复杂度为O(2^n)，即2的n次方。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 1][]

![2020080812550858.png][]

网上还有另一个版本的求时间复杂度方法，也附在下面了：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 2][]

# 4.空间复杂度计算 #

类似于时间复杂度的讨论，一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间（**存储变量的空间**），它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地\\”进行的，是节省存储的算法，有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。

一个递归，我们应该怎么计算他的空间复杂度呢？这样的代码效率十分低下，每次递归相当于是重新在原有的函数栈帧上再次开辟空间来运行函数，直到函数找到了递归出口。可见当n = 5的时候，函数一共被调用了九次，这个就是问题所在，f(5)被调用了好多次，实际上调用一次就行，只要函数未到达递归出口（n < = 2）就会一直在现有函数栈上开辟新的空间，所以也很好地说明了为什么函数递归太深会引起栈溢出的现象。每次上下文切换，都有内存空间的使用（内存占用可以是变量占用，也可以是上下文空间切换【用stack实现】）。

下面的过程，就是展现上下文空间切换时候，**stack中不断入栈出栈过程**：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 3][]

程序结束之后，main也会出栈，我们可以看到在运行f(8)的时候，我们最多用到的资源是8个内存空间。空间复杂度就是树的高度 O(n)。

# 5.斐波那契非递归实现 #

我们可以维护一个数组，但是可能会有一些额外开销，因为结果只与前面两个数字相关，存储一个数字必定还是比存储两个数字占用内存大一些。

![20200808132204646.png][]

![20200808132312310.png][]

从n(>2)开始计算，用F(n-1)和F(n-2)两个数相加求出结果，这样就避免了大量的重复计算，它的效率比递归算法快得多，算法的时间复杂度与n成正比，即算法的时间复杂度为O(N)。上面程序空间复杂度O(N)，下面空间复杂度O(1)。

# 6.怎么在时间复杂度O(1)，空间复杂度O(1)下计算斐波那契数 #

斐波拉契数列的计算是一个非常经典的问题，对于小规模的n，很容易用递归的方式来获取，对于稍微大一点的n，为了避免递归调用的开销，可以用动态规划的思想轻松获得，时间复杂度为O(n)，空间复杂度为O(1). 但是对于更大规模，比如上题中的n的范围，动态规划所花的时间也不少了。

考虑下面三个矩阵：

F(n)   F(n-1)        1,1         F(n-1)  F(n-2)

F(n-1) F(n-1)  与   1,0   与   F(n-2)  F(n-3)

分别设为S(n), M, S(n-1).  S(n) = M x S(n-1).

于是

S(n) = M^(n-1) x S(1) = M^n;   （关系1）

再来看看，若n为32位正整数，设c\[32\]为其二进制序列的逆序列， c\[i\] =0,1;

n = Σ(c\[i\]\*2^i),  i=0,...,31;

所以只要我知道M的2^i 方幂（i=0,1,2,...,31)，我们可以轻松计算出S(n)

而计算出32个M的幂需要做32次矩阵乘法，而计算M^n次方，即M^( Σ(c\[i\]\*2^i) ) 也最多需要做32次矩阵乘法

因而最多64次矩阵乘法即可计算出任意32位正整数范围的n对应的S(n)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 4][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70]: /images/20221124/20d4da5e4783445381309b41aa5a6ba4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 1]: /images/20221124/90c8668a806242748fa87d6e9a811fbe.png
[2020080812550858.png]: /images/20221124/12a55940f72a4e4a8ce4336d32b5cd40.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 2]: /images/20221124/2bc13c193b0647beb78aadfcc205ec64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 3]: /images/20221124/b8b7d9f7a26e47118a9dec4e6815c511.png
[20200808132204646.png]: /images/20221124/30ab557efa2242ee98ef0b12e5c4e3b2.png
[20200808132312310.png]: /images/20221124/f6673c0bf48b456681039cd6566d5303.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 4]: /images/20221124/f75c2be95fb04900a2a8828a50cf5dd7.png