递归算法的时间复杂度分析（Greedy Academy）

1. 公式
   观察依据

   白板上预先写有数列 1, 1, 2, 3, 5, 8 ...

1, 1, 2, 3, 5, 8 ...

斐波那契数列的前几项

正整数序列

1. 公式
   观察依据

   白板上预先写有 $f(n) = f(n-1) + f(n-2)$

$f(n)$

斐波那契数列的第 n 项

n 为正整数

1. 公式
   观察依据

   白板上预先写有 $f(1) = f(2) = 1$

$f(1) = f(2) = 1$

斐波那契数列的初始条件（基准情况）

n 等于 1 或 2

1. 公式
   观察依据

   讲师在白板上写下 $f(7)$ 作为计算目标

2. 声音
   观察依据

   讲师说“假设我要计算的是 $f(7)$”

$f(7)$

需要计算的具体斐波那契数项

n 等于 7

1. 公式
   观察依据

   白板左侧写有 $f(n)=f(n-1)+f(n-2)$

$f(n)$

递归函数的第 n 项，视频中用于表示斐波那契型递归调用

n 为正整数

1. 公式
   观察依据

   白板左侧写有 $f(1)=f(2)=1$

$f(1)$, $f(2)$

递归基，视频明确给出二者都等于 1

固定初值

1. 图示
   观察依据

   右侧画出以 $f(7)$ 为根的二叉递归树，节点标注 $f(6)$、$f(5)$、$f(4)$、$f(3)$、$f(2)$、$f(1)$

$f(k)$

递归树中某一层的具体调用节点

k 为从 7 向下递减的整数

1. 公式
   观察依据

   树的右侧逐层写出 $2^0$、$2^1$、$2^2$、$2^3$，后续又补出 $2^6$

2. 声音
   观察依据

   讲解者说第二层有两个节点，第三层有四个节点，第四层有八个节点

$2^0$, $2^1$, $2^2$, $2^3$, $2^6$

对应递归树各层的节点数量，视频按“层”计数

非负整数指数

1. 公式
   观察依据

   白板左下写出 $O(2^n)$

2. 声音
   观察依据

   讲解者说复杂度可以写成 2 的 n 次方

$O(2^n)$

该递归算法的时间复杂度上界记号

n 为输入规模

1. 声音
   观察依据

   讲解者举例说把 2 的 0 次方加到 2 的 6 次方，等于 2 的 7 次方减 1

1. 该求和式未完整写在白板上，只在口头举例中出现

$2^0+2^1+\cdots+2^6$

示例中整棵理论二叉树各层节点数的总和

有限几何级数

1. 公式
   观察依据

   白板上预先写有 $f(n) = f(n-1) + f(n-2)$ 和 $f(1) = f(2) = 1$

视频通过白板上的公式给出了斐波那契数列的递归定义。对于 $n > 2$，第 n 项等于前两项之和；对于 $n = 1$ 和 $n = 2$，其值均为 1。这是后续构建递归树和分析时间复杂度的基础。

1. n 为正整数

2. 当 $n > 2$ 时使用递推公式

3. 当 $n = 1$ 或 $n = 2$ 时使用基准情况

1. 动画
   观察依据

   讲师以 $f(7)$ 为根节点，向下画出分支 $f(6)$ 和 $f(5)$，并继续将 $f(6)$ 拆分为 $f(5)$ 和 $f(4)$，以此类推，形成一棵倒置的二叉树。

2. 声音
   观察依据

   讲师解释“为了计算 $f(7)$ 呢，我们要知道这两项，也就是 $f(6)$ 和 $f(5)$... 为了计算 $f(6)$ 呢，我们首先要知道 $f(5)$ 和 $f(4)$...”

视频展示了如何通过递归展开来构建递归树。以目标计算 $f(n)$ 为根节点，根据其递归定义 $f(n) = f(n-1) + f(n-2)$，将其拆分为两个子节点 $f(n-1)$ 和 $f(n-2)$。对每个非基准情况的子节点重复此过程，直到所有叶子节点都达到基准情况（如 $f(1)$ 或 $f(2)$）。

1. 适用于具有多项递归调用的递归算法

2. 树的深度取决于递归的终止条件

1. 斐波那契数列的递归定义

1. 声音
   观察依据

   讲师明确指出：“在这棵树里面，每个节点我们可以把它看作是一个单位的计算。”

在递归树中，每一个节点代表一次函数调用，即一个单位的计算操作。通过分析树中节点的总数，可以直观地评估递归算法的执行次数，进而推导其时间复杂度。

1. 假设每次函数调用（除递归调用外）的开销为常数级别

1. 递归树的构建方法

1. 声音
   观察依据

   讲师总结：“为了分析咱们递归函数的时间复杂度，我们只需要去看一下在这棵树里面出现了多少个节点... 所以我们只需要去数一下就可以了。”

2. 动画
   观察依据

   讲师开始按层分析节点数量，第一层有 1 个节点，表示为 $2^0$。

该视频片段提出了一种分析递归时间复杂度的直观方法：将递归过程转化为递归树，然后统计树中所有节点（包括内部节点和叶子节点）的总数。节点总数即代表了算法执行的总计算次数。视频中讲师开始尝试按层寻找节点数量的规律（如第一层为 $2^0$）。

1. 适用于可以用递归树清晰表示的递归算法

1. 递归树节点的计算意义

1. 公式
   观察依据

   $f(n)$ 等于 f(n 减 1) 加上 f(n 减 2)

2. 公式
   观察依据

   $f(1)$ 和 $f(2)$ 都等于 1

3. 声音
   观察依据

   讲解者围绕这一递归式展开复杂度分析

视频以 $f(n)=f(n-1)+f(n-2)$ 且 $f(1)=f(2)=1$ 作为讨论对象，用它构造一棵二叉递归树，再分析递归调用次数。

1. n 为整数

2. 递归基为 $f(1)=f(2)=1$

1. 图示
   观察依据

   右侧递归树旁逐层标注 $2^0$、$2^1$、$2^2$、$2^3$

2. 声音
   观察依据

   讲解者依次说第二层两个节点、第三层四个节点、第四层八个节点

视频把一次递归调用展开成树形结构，并观察每一层节点数：第一层 1 个，第二层 2 个，第三层 4 个，第四层 8 个，因此第 k 层对应 $2^{k-1}$ 个节点。

1. 按完全二叉树方式计数

2. 视频中的“层”从 1 开始编号

1. 递归定义与递归基

1. 声音
   观察依据

   讲解者说要数整棵树有多少节点，相当于把这些值相加在一起

2. 公式
   观察依据

   白板写出 $O(2^n)$

3. 声音
   观察依据

   举例 $2^0+2^1+\cdots+2^6=2^7-1$

1. 视频没有写出一般形式的求和公式，只给出具体例子和最终大 O 结论

视频将递归算法的时间复杂度转化为递归树节点总数问题，再把各层节点数相加，得到指数级增长，并写成 $O(2^n)$。

1. 以递归调用次数衡量时间开销

2. 采用完全二叉树式上界估计

1. 递归树每层节点数按 2 的幂增长

1. 声音
   观察依据

   讲解者说这种复杂度叫做指数级的复杂度

视频把 $O(2^n)$ 这类随输入规模 n 呈 2 的幂增长的复杂度称为“指数级的复杂度”。

1. 复杂度形式为 $O(2^n)$ 或同类指数增长

1. 总节点数决定时间复杂度

1. 声音
   观察依据

   讲解者说：把 2 的 0 次方加上 2 的 1 次方一直加到 2 的 6 次方，其实它是等于 2 的 7 次方减 1 的

1. 这是口头举例，白板上没有完整写出该等式

2 的 0 次方加 2 的 1 次方加 2 的 2 次方加 2 的 3 次方加 2 的 4 次方加 2 的 5 次方加 2 的 6 次方等于 2 的 7 次方减 1

1. 求和从 $2^0$ 开始

2. 公比为 2

3. 末项为 $2^6$

对这一组有限项成立

1. 公式
   观察依据

   白板写出 $O(2^n)$

2. 声音
   观察依据

   讲解者说复杂度很明显就是 O(2 的 n 次方)

1. 视频未严格证明上界，只是通过递归树节点计数给出直观推导

针对视频中的递归问题，其时间复杂度可写成 $O(2^n)$

1. 以递归调用次数作为主要代价

2. 按完全二叉树式节点数进行上界估计

对输入规模 n 的渐近估计

1. 动画
   观察依据

   讲师在白板上逐步画出从 $f(7)$ 开始的递归拆分过程，直到 $f(3)$ 和 $f(2)$。

2. 声音
   观察依据

   讲师同步口述每一步的拆分逻辑：“为了计算 $f(7)$... 要知道 $f(6)$ 和 $f(5)$... 为了计算 $f(6)$... 要知道 $f(5)$ 和 $f(4)$...”

1. 公式

   $$f(7)$$
   解释

   设定计算目标为 $f(7)$。

   步骤依据

   视频初始设定的例子。

   视频直接表达
2. 公式

   $$f(7) \rightarrow f(6) + f(5)$$
   解释

   根据递归定义，将 $f(7)$ 拆分为 $f(6)$ 和 $f(5)$ 两个子问题。

   步骤依据

   应用公式 $f(n) = f(n-1) + f(n-2)$。

   视频直接表达
3. 公式

   $$f(6) \rightarrow f(5) + f(4), \quad f(5) \rightarrow f(4) + f(3)$$
   解释

   继续对新生成的非基准节点 $f(6)$ 和 $f(5)$ 进行拆分。

   步骤依据

   再次应用递归定义。

   视频直接表达
4. 公式

   $$f(5) \rightarrow f(4) + f(3), \quad f(4) \rightarrow f(3) + f(2), \quad f(4) \rightarrow f(3) + f(2), \quad f(3) \rightarrow f(2) + f(1)$$
   解释

   讲师持续向下展开树的分支，展示了大量重复的子问题（如多个 $f(4)$, $f(3)$, $f(2)$）。

   步骤依据

   递归定义的直接推演。

   视频直接表达

通过不断应用递归公式，$f(7)$ 被展开成一棵包含大量重复子问题的二叉树，直观展示了朴素递归算法的计算冗余。

1. 声音
   观察依据

   讲师解释：“假设我要计算 $f(6)$，然后我已经知道了 $f(5)$ 和 $f(4)$，那我只需要把这两个数相加之后... 我就可以得到 $f(6)$了。然后我得到这两个数之后，我把它俩做一个相加，我就可以得到 $f(7)$。”

2. 动画
   观察依据

   讲师用笔在树上从下往上指代节点，模拟求和过程。

1. 公式

   $$\text{Given} f(5), f(4) \Rightarrow f(6) = f(5) + f(4)$$
   解释

   当底层子问题的值求出后，可以通过相加得到上一层节点的值。

   步骤依据

   递归定义的逆过程（归）。

   视频直接表达
2. 公式

   $$\text{Given} f(6), f(5) \Rightarrow f(7) = f(6) + f(5)$$
   解释

   同理，利用刚求出的 $f(6)$ 和已有的 $f(5)$ 相加，最终得到根节点 $f(7)$ 的值。

   步骤依据

   递归定义的逆过程（归）。

   视频直接表达

递归算法不仅包含自上而下的“递”（拆分问题），还包含自下而上的“归”（汇总结果）。树的每个节点都参与了最终的加法运算。

1. 图示
   观察依据

   先画出 $f(7)$ 的二叉递归树，再在右侧标注 $2^0$、$2^1$、$2^2$、$2^3$

2. 声音
   观察依据

   讲解者逐层数节点，并说整棵树相当于把这些值相加

3. 公式
   观察依据

   最后写出 $O(2^n)$

1. 从具体例子 $f(7)$ 推广到一般 n 的过程是直观说明，不是形式化证明

1. 公式

   $$f(n)=f(n-1)+f(n-2),\ f(1)=f(2)=1$$
   解释

   先给出被分析的递归函数及其递归基。

   步骤依据

   白板左侧直接写出。

   视频直接表达
2. 公式

   $$f(7)\to f(6),f(5)\to f(5),f(4),f(3),f(2)\to \cdots$$
   解释

   把一次调用展开成二叉递归树，每个节点继续分裂成两个子调用。

   步骤依据

   右侧树状图直接展示了展开过程。

   视频直接表达
3. 公式

   $$2^0,\ 2^1,\ 2^2,\ 2^3$$
   解释

   逐层统计节点数：第一层 1 个，第二层 2 个，第三层 4 个，第四层 8 个。

   步骤依据

   讲解者口头逐层说明，并在树旁写出这些幂次。

   视频直接表达
4. 公式

   $$\sum_{k=0}^{m}2^k$$
   解释

   要估计整棵树的规模，就把各层节点数相加。

   步骤依据

   讲解者说“相当于把这些值把它相加在一起”。

   视频直接表达
5. 公式

   $$2^0+2^1+\cdots+2^6=2^7-1$$
   解释

   用具体例子说明几何级数求和结果是下一幂减一。

   步骤依据

   讲解者口头举例给出。

   视频直接表达
6. 公式

   $$O(2^n)$$
   解释

   由于总节点数随深度呈 2 的幂增长，视频把时间复杂度写成 $O(2^n)$。

   步骤依据

   白板左下写出 $O(2^n)$，讲解者同步说明。

   视频直接表达

视频通过递归树逐层计数，得出该递归算法的时间复杂度为 $O(2^n)$，并称其为指数级复杂度。

1. 声音
   观察依据

   讲解者说由于有基本条件是 $f(1)$ 和 $f(2)$ 分别等于 1，所以没必要把这个树完全画出来

2. 图示
   观察依据

   图中只画出部分层级，底部用省略号表示未继续展开

1. 视频没有给出截断后的精确节点数，只强调理论上需要这么多节点

1. 公式

   $$f(1)=f(2)=1$$
   解释

   递归基给出后，某些分支会在底层停止继续分裂。

   步骤依据

   白板左侧直接写出递归基。

   视频直接表达
2. 公式

   $$\text{theoretical number of nodes in a complete tree}$$
   解释

   讲解者仍先按完全二叉树方式估计规模，再说明实际画图时无需全部展开。

   步骤依据

   口头说明“从理论的角度来讲的话，其实我们需要这么多的节点”。

   视频直接表达

视频区分了“实际不必全画”和“理论上按完全树估计规模”这两个层面。

1. 动画
   观察依据

   整个视频片段都在白板上绘制和分析以 $f(7)$ 为根的递归树。

2. 声音
   观察依据

   讲师全程围绕 $f(7)$ 的计算过程进行讲解。

假设要计算斐波那契数列的第 7 项 $f(7)$，请分析其递归计算过程并探讨如何评估时间复杂度。

1. f 在 n 处的值等于 f 在 n 减 1 处的值加上 f 在 n 减 2 处的值

2. f 在 1 处的值和 f 在 2 处的值都等于 1

3. 目标计算 $f(7)$

构建 $f(7)$ 的递归树，并说明如何通过该树分析递归算法的时间复杂度。

1. 公式

   $$\text{Draw the root node} f(7)$$
   解释

   以目标计算 $f(7)$ 作为递归树的起点。

   步骤依据

   递归调用的入口。

   视频直接表达
2. 公式

   $$\text{Split nodes level by level} f(7) \to \{f(6), f(5)\}, f(6) \to \{f(5), f(4)\}, \dots$$
   解释

   根据递推公式，将每个大于 2 的节点拆分为两个子节点，直到出现 $f(2)$ 或 $f(1)$。

   步骤依据

   应用斐波那契数列的递归定义。

   视频直接表达
3. 公式

   $$\text{Examine the structure of the tree}$$
   解释

   发现树中存在大量重复计算的节点（如多个 $f(4)$, $f(3)$, $f(2)$）。

   步骤依据

   视觉观察递归树的形态。

   视频直接表达
4. 公式

   $$\text{Define the computational meaning of each node}$$
   解释

   将树中的每一个节点视为一次单位的函数调用计算。

   步骤依据

   讲师在视频中的明确设定。

   视频直接表达
5. 公式

   $$\text{Introduce a method for analyzing complexity}$$
   解释

   指出分析时间复杂度等价于统计这棵递归树中所有节点的总数。

   步骤依据

   总计算次数决定了算法的运行时间。

   视频直接表达
6. 公式

   $$\text{Attempt to count the number of nodes level by level}$$
   解释

   讲师开始分析第一层有 1 个节点（记为 $2^0$），准备寻找各层节点数的规律。

   步骤依据

   为了计算总节点数，先寻找局部规律。

   视频直接表达

通过构建 $f(7)$ 的递归树，可以直观看到朴素递归产生了大量重复子问题。分析其时间复杂度的方法是统计递归树中的节点总数，视频中讲师正准备通过按层寻找规律（如第一层 $2^0$ 个节点）来计算总节点数。

视频片段在讲师刚开始分析第二层节点时结束，未给出最终的复杂度结论（如 $O(2^n)$），但方法论和初始步骤已完整展示。

1. 图示
   观察依据

   以 $f(7)$ 为根画出递归树，并逐层标注节点数

2. 声音
   观察依据

   讲解者围绕 $f(7)$ 的展开过程逐层计数并求总复杂度

1. 视频没有计算 $f(7)$ 的函数值本身，重点在调用次数与复杂度

对 $f(n)=f(n-1)+f(n-2)$，$f(1)=f(2)=1$，分析 $f(7)$ 展开成递归树后的节点规模与时间复杂度。

1. $f(n)$ 等于 f(n 减 1) 加上 f(n 减 2)

2. $f(1)$ 和 $f(2)$ 都等于 1

3. 以 $f(7)$ 为根展开递归树

数出各层节点数，并据此给出时间复杂度。

1. 公式

   $$f(7)$$
   解释

   根节点对应一次 $f(7)$ 调用。

   步骤依据

   图中最上方节点为 $f(7)$。

   视频直接表达
2. 公式

   $$f(6),\ f(5)$$
   解释

   第二层有两个节点。

   步骤依据

   讲解者说第二层总共有两个节点，旁边写 $2^1$。

   视频直接表达
3. 公式

   $$f(5),\ f(4),\ f(3),\ f(2)$$
   解释

   第三层有四个节点。

   步骤依据

   讲解者说第三层总共有四个节点，旁边写 $2^2$。

   视频直接表达
4. 公式

   $$f(4),\ f(3),\ f(3),\ f(2),\ f(2),\ f(1),\ f(1),\ f(0)$$
   解释

   第四层有八个节点。

   步骤依据

   讲解者说第四层总共有八个，旁边写 $2^3$；图中底层可见多个 f 项继续展开。

   视频直接表达
5. 公式

   $$2^0+2^1+\cdots+2^6=2^7-1$$
   解释

   把各层节点数相加，视频用这个例子说明总和是下一幂减一。

   步骤依据

   讲解者口头举例说明。

   视频直接表达
6. 公式

   $$O(2^n)$$
   解释

   由总节点数的指数增长得到时间复杂度。

   步骤依据

   白板写出 $O(2^n)$，讲解者同步总结。

   视频直接表达

该递归算法的时间复杂度为 $O(2^n)$，视频称之为指数级复杂度。

视频通过逐层计数与几何级数例子验证总节点数呈 2 的幂增长。

1. 动画
   观察依据

   讲师的手持笔在白板上从上到下、从左到右逐步绘制出 $f(7)$ 的递归展开树。

1. 根节点 $f(7)$

2. 分支节点 $f(6)$, $f(5)$, $f(4)$, $f(3)$, $f(2)$

3. 连接线（箭头）

1. 节点数量随时间不断增加

2. 树的深度逐渐加深

3. 分支向两侧延展

1. 每个非叶子节点都有两个子节点

2. 子节点的参数总是比父节点小 1 或小 2

动态展示了递归算法“递”的过程，即问题如何被一步步分解为更小的子问题，直观暴露了重复计算的现象。

1. 动画
   观察依据

   讲师用笔尖在已画好的树上，从下方的节点指向上方的节点。

2. 声音
   观察依据

   配合口述“把这两个数相加之后... 就可以得到 $f(6)$了”。

1. 已绘制的递归树

2. 讲师的笔尖

1. 笔尖的焦点从树的底层逐渐移动到顶层

1. 树的结构保持不变

形象地演示了递归算法“归”的过程，即子问题的解如何逐层返回并组合成原问题的解。

1. 动画
   观察依据

   讲师在树的右侧写下虚线和 $2^0$，并用笔圈出第一层的 $f(7)$。

2. 声音
   观察依据

   讲师说“首先我们来看一下第一层... 一个节点我们可以通过 2 的 0 次方可以把它表示起来”。

1. 讲师刚提到“然后呢第二个”，视频即结束，第二层的具体分析未在画面中完整呈现。

1. 递归树的第一层

2. 手写公式 $2^0$

3. 虚线

1. 引入了按层计数的新视角

2. 在树旁添加了数学表达式

1. 递归树本身的结构未变

标志着从定性观察转向定量分析，试图通过寻找每一层节点数量的数学规律（等比数列）来求解总节点数。

1. 图示
   观察依据

   右侧递归树旁依次写出 $2^0$、$2^1$、$2^2$、$2^3$

2. 动画
   观察依据

   手和笔逐层指向 $f(7)$、$f(6)/f(5)$、更下层节点

1. $f(7)$ 根节点

2. $f(6)$、$f(5)$ 等子节点

3. 右侧幂次标注 $2^0$、$2^1$、$2^2$、$2^3$

1. 讲解者从上到下逐层指示节点

2. 每讲完一层就在右侧补写对应的 2 的幂

1. 树的结构保持不变

2. 每层节点数按 2 的幂增加

画面把抽象的递归调用次数转化为可视化的二叉树层计数。

1. 动画
   观察依据

   镜头回到白板左下，讲解者写下 $O(2^n)$

2. 公式
   观察依据

   $O(2^n)$ 出现在左下区域

1. $O(2^n)$ 记号

2. 左侧递归公式

3. 右侧递归树

1. 新增左下复杂度结论

2. 讲解者用笔指向该记号

1. 前面的递归树和公式仍作为依据保留在画面中

视觉上将“树节点总数”收束为一个渐近复杂度结论。

1. 动画
   观察依据

   白板画面切到深蓝背景，出现搜索框、网址 www.greedyai.com、Search 按钮和 AI 标志动画

1. 搜索框

2. www.greedyai.com

3. Search 按钮

4. AI 标志

1. 教学白板消失

2. 出现品牌搜索与标志动画

1. 无新的数学内容

这一段是片尾包装，不再承载数学推导。

1. 动画
   观察依据

   递归树中出现了大量相同的节点（如多个 $f(4)$, $f(3)$）。

2. 声音
   观察依据

   讲师通过不断重复“为了计算它，我们要知道...”强调了这种层层嵌套和重复。

初学者可能认为递归只是简单地调用自身，没有意识到像斐波那契数列这样的双分支递归会产生指数级的重复子问题。

通过绘制递归树可以清晰地看到，同一个子问题（如 $f(4)$）会被不同的父节点多次触发计算。这正是朴素递归时间复杂度高的根本原因，也是引入记忆化搜索或动态规划的动机。（注：此为基于视频画面的合理推导，视频本身未直接点明“记忆化”等后续概念）

1. 声音
   观察依据

   讲解者说由于有基本条件 $f(1)$ 和 $f(2)$ 分别等于 1，所以没必要把这个树完全画出来，但从理论角度需要这么多节点

看到图中没有把整棵树全部画完，就以为递归调用的理论规模也随之减少。

视频明确区分：画图时可以省略，但做复杂度分析时仍按理论上的节点规模来估计。

1. 声音
   观察依据

   讲师先给出 $f(n)$ 公式，随后立即开始画树：“为了计算 $f(7)$ 呢，我们要知道这两项...”

递归树的构建方法直接应用于斐波那契数列的递归定义，将抽象的递推公式转化为直观的图形结构。

1. 声音
   观察依据

   讲师先定义“每个节点... 是一个单位的计算”，接着说“为了分析... 时间复杂度，我们只需要去看一下... 出现了多少个节点”。

理解“节点代表单位计算”是采用“数节点法”分析时间复杂度的先决条件和理论基础。

1. 公式
   观察依据

   左侧给出 $f(n)=f(n-1)+f(n-2)$

2. 图示
   观察依据

   右侧立即画出对应的二叉递归树

视频先用递归定义建立问题，再用递归树把每次调用展开成可视化结构。

1. 声音
   观察依据

   讲解者先逐层数节点，再说要数整棵树有多少节点，相当于把这些值相加

2. 公式
   观察依据

   随后写出 $O(2^n)$

总节点数的估计依赖前面得到的每层 2 的幂规律。

1. 声音
   观察依据

   讲解者在得出 $O(2^n)$ 后说这种复杂度叫做指数级的复杂度

“指数级复杂度”是对 $O(2^n)$ 这一结果的命名和归类。

1. 动画
   观察依据

   完整的 $f(7)$ 递归树绘制过程。

1. 递归树的构建方法
2. $f(7)$ 的递归展开过程

1. 动画
   观察依据

   树上密集的重复节点。

1. $f(7)$ 的递归展开过程
2. 误以为朴素递归没有重复计算

1. 声音
   观察依据

   讲师关于数节点分析复杂度的讲解。

1. 递归树节点的计算意义
2. 通过计算递归树节点总数分析时间复杂度

1. 动画
   观察依据

   讲师写下 $2^0$ 并开始分层计数。

1. 视频在此处截断，未展示完整的求和过程。

1. 通过计算递归树节点总数分析时间复杂度
2. 开始按层分析节点数量

1. 公式
   观察依据

   $f(n)$ 等于 f(n 减 1) 加上 f(n 减 2)，且 $f(1)$ 和 $f(2)$ 都等于 1

2. 图示
   观察依据

   $f(7)$ 递归树

1. 递归定义与递归基
2. $f(7)$ 递归树示例

1. 声音
   观察依据

   逐层说明第二层 2 个、第三层 4 个、第四层 8 个

2. 图示
   观察依据

   右侧标注 $2^0$、$2^1$、$2^2$、$2^3$

1. 递归树每层节点数按 2 的幂增长

1. 声音
   观察依据

   把各层节点数相加

2. 公式
   观察依据

   时间复杂度为 2 的 n 次方阶

1. 总节点数决定时间复杂度
2. 由递归树层节点数推出 $O(2^n)$

1. 声音
   观察依据

   2 的 0 次方加 2 的 1 次方一直加到 2 的 6 次方等于 2 的 7 次方减 1

1. 有限几何级数示例
2. 由递归树层节点数推出 $O(2^n)$

1. 声音
   观察依据

   这种复杂度叫做指数级的复杂度

1. 指数级复杂度的命名

1. 声音
   观察依据

   因为有 $f(1)$ 和 $f(2)$ 等于 1，所以没必要把树完全画出来

2. 图示
   观察依据

   图中底部用省略号表示未继续展开

1. 递归定义与递归基
2. 递归基使实际树不必完整画出
3. 不要把“实际不必全画”误解为“理论规模更小”