1. Fib: 0, 1, 1, 2, 3, 5, 8, 13, 21, …
公式：F(n) = F(n – 1) + F(n – 2)
// 递归
fib(n: number): number {if (n <= 2) return n;
return fib(n - 1) + fib(n - 2);
}2. 算法递归函数中，主定理的利用
- 二分查找，一分为二，只查问一边，工夫复杂度为 O(log(n))
- 二叉树的遍历，每一个节点都被拜访一次，且仅拜访一次，工夫复杂度为 O(n)
- 最优排序矩阵查找，工夫复杂度为 O(n)
- 归并排序，工夫复杂度为 O(nlog(n))
3. 算法思考题一
二叉树遍历 - 前序、中序、后序：工夫复杂度是多少
图的遍历：工夫复杂度是多少
搜索算法：DFS（深度优先）、BFS（广度优先）的工夫复杂度是多少
二分查找：工夫复杂度是多少
（1）工夫复杂度为 O(n)，n 代表二叉树外面的树的节点总数（2）每一个节点都被拜访一次，且仅拜访一次，工夫复杂度为 O(n)，n 代表图的外面的节点总数（3）工夫复杂度为 O(n)，n 代表搜寻空间外面的节点总数（4）一分为二，只查问一边，工夫复杂度为 O(log(n))