算法可视化
入门执行逻辑
斐波那契:递归 vs 递推
递归版 f(5) 会重复计算很多次(红色节点是重复计算的);递推版从前往后每个只算一次,效率高得多。
main.cpp第 2 行
1// 递归版: f(5) 有大量重复计算
2int fib(int n) {
3 if (n <= 1) return n;
4 return fib(n-1) + fib(n-2);
5}
6// 递推版: 从前往后, 每个只算一次
7int f[6]; f[0] = 0; f[1] = 1;
8for (int i = 2; i <= 5; i++)
9 f[i] = f[i-1] + f[i-2];
10// f[5] = 5
变量表0 个变量
还没有变量,执行到声明语句后出现
二叉树(左小右大)
空树
1/8
递归版:fib(5) = fib(4) + fib(3),一层层展开
1 / 8