二叉树的时间复杂度和空间复杂度_二叉树前中后序遍历

2024年 9月 6日下午9:43 • 激活谷笔记

三种时间复杂度算法求解斐波那契数列　　0. 问题描述　　在数学当中，由斐波那契数字（Fibonacci number，记作
F_n ）构成的序列，被称为斐波那契数列（Fibonacci sequence）。该数列中的每一个数字等于排在它前面的两个数字之和。数列从0和1开始：
$F_{0}=0$ ,
$F_{1}=1$ 数列第n个（n>1）数字为：
$F_{n}=F_{n-1}+F_{n-2}$ 　　按照上述公式，计算得到斐波那契数列为：
　　随着n的增大，斐波那契数列增长比例逐渐趋近于黄金分割比例。　　本文将尝试使用三种时间复杂度不同的算法求解该序列的第n个数字，分别为：递归法：时间复杂度
O(2^n) 循环法：时间复杂度
O(n) 矩阵连乘法：时间复杂度
O(1) (？有待商榷) 　　1. 递归解法　　从斐波那契数列的计算公式：
$F_{n}=F_{n-1}+F_{n-2}$ ，可自然想到该问题适合使用递归法求解，下面直接给出python代码。　　时间复杂度分析　　细心的读者应该能观察到递归求解的过程如同构造一棵二叉树，例如求解
F_5 依赖
F_4 和
F_3 ，我们把
F_5 作为树的根节点，
F_4 和
F_3 作为左右两个叶子节点，继续向下递归，左节点
F_4 继续向下分解为
F_3 和
F_2 ，右节点
F_3 继续向下分解为
F_2 和
F_1 ，依此类推，如下图所示：

　　因此，该算法的时间复杂度为
O(2^n) 。　　性能优化　　指数级的复杂度太高，在
较大时响应时长无法接受，幸好存在优化的空间。从上面的二叉树中可以发现，存在大量重复的节点。优化的方法是把计算过的结果存放在字典中，每次计算前查看字典中是否已经存在相同的节点，如果有则直接返回，否则将此新节点存放在字典中，优化后的程序如下。　　优化后的程序相当于给之前的递归树做了剪枝操作，相同的节点仅执行一次，因此时间复杂度降为
O(n) 。　　2. 循环解法　　如果说前面的递归解法是自顶向下将大问题拆解成小问题求解，那么循环解法则是逆向思维，自底向上，先求出小问题的解，再向上一步一步向上求取最终问题的解。

　　求解过程分为
步，将每一步的结果保存在列表中对应下标的位置，代码如下。　　时间复杂度分析　　单层循环，时间复杂度为
O(n) ，与优化后的递归解法复杂度相当。　　性能优化　　时间复杂度已经没有优化空间了，但可以使用两个临时变量替换掉长度为
的列表，使空间复杂度从
O(n) 降为
O(1) 。代码如下：　　3. 矩阵连乘法　　根据斐波那契数列自身的性质，我们可以构造如下方等式关系：　　
$\begin{cases} F_2 = F_1+F_0 \\ F_1 = F_1 \end{cases}$ 　　使用矩阵表示上述等式关系，即　　
$\left[\begin{array}{cccc} F_2 \\ F_1 \\ \end{array}\right] = \left[\begin{array}{cccc} 1 & 1 \\ 1 & 0 \\ \end{array}\right] \times \left[\begin{array}{cccc} F_1 \\ F_0 \\ \end{array}\right]$ 　　那么　　
$\left[\begin{array}{cccc} F_3 \\ F_2 \\ \end{array}\right] = \left[\begin{array}{cccc} 1 & 1 \\ 1 & 0 \\ \end{array}\right] \times \left[\begin{array}{cccc} F_2 \\ F_1 \\ \end{array}\right] = \left[\begin{array}{cccc} 1 & 1 \\ 1 & 0 \\ \end{array}\right]^2 \times \left[\begin{array}{cccc} F_1 \\ F_0 \\ \end{array}\right]$ 　　依次乘下去，可得一般形式　　
$\left[\begin{array}{cccc} F_n \\ F_{n-1} \\ \end{array}\right] = \left[\begin{array}{cccc} 1 & 1 \\ 1 & 0 \\ \end{array}\right]^{n-1} \times \left[\begin{array}{cccc} F_1 \\ F_0 \\ \end{array}\right] = \left[\begin{array}{cccc} 1 & 1 \\ 1 & 0 \\ \end{array}\right]^{n-1} \times \left[\begin{array}{cccc} 1 \\ 0 \\ \end{array}\right]$ 　　我们要求解的
F_n 即为向量
$\left[\begin{array}{cccc} F_n \\ F_{n-1} \\ \end{array}\right]$ 的第一个分量。代码如下：　　时间复杂度分析　　从程序上看，结果result几乎是一条语句返回的，这样看时间复杂度为
O(1) 。但语句涉及到乘方运算，即n个矩阵相乘，时间复杂度似乎又是
O(n) 。这一结论有待商榷。　　性能优化　　将矩阵对角化后，再进行连乘操作，可大大提升运算效率。对角化方法为　　
$A=S^{-1}\Lambda S$ ，其中
是要被对角化的矩阵，
为由
的特征向量组成的矩阵，
$\Lambda$ 为由
的特征值构成的对角矩阵。　　
$A^n=S^{-1}\Lambda SS^{-1}\Lambda S...S^{-1}\Lambda S=S^{-1}\Lambda^n S$ ，python代码如下：　　问题　　NumPy在处理矩阵乘法时会进行大量的浮点运算，在
90″ eeimg=”1″> 时，结果的精度有损失。　　4 小结　　经实际运行测试，不使用字典的递归算法在
15″ eeimg=”1″> 时几乎慢到不可用的程度。使用字典优化后的递归算法与循环算法性能相当，使用
n=1000 测试运行时长大概在万分之一秒。矩阵连乘算法虽看似简单，但运行效率不如循环算法，运行时长大概在千分之一秒，且矩阵对解化操作并没有带来明显的性能提升。最终的运行效率排序为：循环法
递归(带字典)
” eeimg=”1″> 矩阵连乘
$\gg$ 递归(不带字典)。　　参考　　[1] WikiPedia: Fibonacci number 　　[2] MIT线性代数: 矩阵对角化（网易公开课）

二叉树的时间复杂度和空间复杂度_二叉树前中后序遍历

相关推荐