P32. 爬楼梯方法数

https://algocasts.io/episodes/Y9pJNpAb

请教Hawstein, 为何使用f(n) =f(n-1) + f(n-2) 在这里的算法复杂度会比迭代高很多?而比如验证平衡二叉树等一些其他使用递归求解算法复杂度就和迭代差不多?
谢谢!

@williamhau01

这里你说的是两个不同的东西,是不能拿来对比的。

在这个题目或者 P118. 第 n 个斐波那契数 中,n 表示的是你要求解的第 n 项,放在解答树中,这个 n 仅仅表示解答树的高度 h。所以从解答树的视角来看,这两个题目是用 O(h) 就可以解决的,而不用遍历解答树上的所有节点(这要花费 O(2^h))。注意,在这两个问题中,我们的考察对象并不二叉树,解答树只是我们用来分析时间复杂度的。

而在考察对象本来就是二叉树的那些题目中,n 表示的是树上所有节点的数量。大部分问题都是需要我们至少去访问过每个节点,才可能得出答案的。因此递归也好,迭代也罢,都是花费 O(n) 的时间去访问了所有节点,时间复杂度上自然是一样的。