手动计算递归斐波那契算法的时间复杂度
Manually calculating time complexity of recursive Fibonacci algorithm
我想了解递归斐波那契算法的时间复杂度。
fib(n)
if (n < 2)
return n
return fib(n-1)+fib(n-2)
没有太多的数学背景，我尝试用手计算它。也就是随着n的增加我手动统计步数。我忽略所有我认为是恒定时间的东西。我是这样做的。假设我想计算 fib(5).
n = 0 - just a comparison on an if statement. This is constant.
n = 1 - just a comparison on an if statement. This is constant.
n = 2 - ignoring anything else, this should be 2 steps, fib(1) takes 1 step and fib(0) takes 1 step.
n = 3 - 3 steps now, fib(2) takes two steps and fib(1) takes 1 step.
n = 4 - 5 steps now, fib(3) takes 3 steps and fib(2) takes 2 steps.
n = 5 - 8 steps now, fib(4) takes 5 steps and fib(3) takes 3 steps.
从这些判断，我认为 运行 时间可能是 fib(n+1)。我不太确定 1 是否是常数因子，因为 fib(n) 和 fib(n+1) 之间的差异可能非常大。
我在 SICP 上阅读了以下内容：
In general, the number of steps required by a tree-recursive process
will be proportional to the number of nodes in the tree, while the
space required will be proportional to the maximum depth of the tree.
在这种情况下，我相信树中的节点数是 fib(n+1)。所以我相信我是正确的。但是，this video 让我感到困惑：
So this is a thing whose time complexity is order of actually, it
turns out to be Fibonacci of n. There's a thing that grows exactly as
Fibonacci numbers.
...
That every one of these nodes in this tree has to be examined.
我绝对震惊了。我已经检查了树中的所有节点，并且总是有 fib(n+1) 个节点，因此计算 fib(n) 时的步骤数。我不明白为什么有些人说它是 fib(n) 步数而不是 fib(n+1)。
我做错了什么？
在您的程序中，您有这个耗时的操作（按每个操作使用的时间排序，快速操作在列表顶部）：
- 加法
- IF（条件跳转）
- Return 来自子例程
- 函数调用
让我们看看执行了多少个动作，并将其与 n 和 fib(n) 进行比较：
n | fib | #ADD | #IF | #RET | #CALL
---+-----+------+-----+------+-------
0 | 0 | 0 | 1 | 1 | 0
1 | 1 | 0 | 1 | 1 | 0
对于 n≥2 你可以这样计算数字：
- fib(n) = fib(n-1) + fib(n-2)
- ADD(n) = 1 + ADD(n-1) + ADD(n-2)
- IF(n) = 1 + IF(n-1) + IF(n-2)
- RET(n) = 1 + RET(n-1) + RET(n-2)
- 呼叫(n) = 2 + 呼叫(n-1) + 呼叫(n-2)
为什么？
- ADD：一个加法直接在程序的顶层实例中执行，但是在两个子程序中，你调用的也是加法，需要执行。
- IF 和 RET：与之前相同的参数。
- CALL：也一样，但是你在top实例中执行了两个调用。
因此，这是您的其他 n 值的列表：
n | fib | #ADD | #IF | #RET | #CALL
---+--------+--------+--------+--------+--------
0 | 0 | 0 | 1 | 1 | 0
1 | 1 | 0 | 1 | 1 | 0
2 | 1 | 1 | 3 | 3 | 2
3 | 2 | 2 | 5 | 5 | 4
4 | 3 | 4 | 9 | 9 | 8
5 | 5 | 7 | 15 | 15 | 14
6 | 8 | 12 | 25 | 25 | 24
7 | 13 | 20 | 41 | 41 | 40
8 | 21 | 33 | 67 | 67 | 66
9 | 34 | 54 | 109 | 109 | 108
10 | 55 | 88 | 177 | 177 | 176
11 | 89 | 143 | 287 | 287 | 286
12 | 144 | 232 | 465 | 465 | 464
13 | 233 | 376 | 753 | 753 | 752
14 | 377 | 609 | 1219 | 1219 | 1218
15 | 610 | 986 | 1973 | 1973 | 1972
16 | 987 | 1596 | 3193 | 3193 | 3192
17 | 1597 | 2583 | 5167 | 5167 | 5166
18 | 2584 | 4180 | 8361 | 8361 | 8360
19 | 4181 | 6764 | 13529 | 13529 | 13528
20 | 6765 | 10945 | 21891 | 21891 | 21890
21 | 10946 | 17710 | 35421 | 35421 | 35420
22 | 17711 | 28656 | 57313 | 57313 | 57312
23 | 28657 | 46367 | 92735 | 92735 | 92734
24 | 46368 | 75024 | 150049 | 150049 | 150048
25 | 75025 | 121392 | 242785 | 242785 | 242784
26 | 121393 | 196417 | 392835 | 392835 | 392834
27 | 196418 | 317810 | 635621 | 635621 | 635620
你可以看到，加法的次数刚好是函数调用次数的一半（嗯，你也可以直接从代码中读到这个）。如果将初始程序调用算作第一个函数调用，那么 IF、returns 和调用的数量完全相同。
因此，您可以将 1 个 ADD、2 个 IF、2 个 RET 和 2 个 CALL 组合成一个需要恒定时间量的超级动作。
从列表中也可以看出，Additions的个数比fib(n+1)少1个（可以忽略）
因此，运行 时间顺序为 fib(n+1)。
比率fib(n+1) / fib(n)越来越接近Φ，n越大。 Φ 是黄金比例，即 1.6180338997，它是一个常数。订单中忽略常数因素。所以，顺序 O(fib(n+1)) 与 O(fib(n)).
完全相同
现在让我们看看 space:
确实，处理一棵树所需的最大值 space 等于树与最远叶子之间的最大距离。这是真的，因为您在 f(n-1) 返回后调用 f(n-2)。
所以你的程序需要的 space 是 n.
我想了解递归斐波那契算法的时间复杂度。
fib(n)
if (n < 2)
return n
return fib(n-1)+fib(n-2)
没有太多的数学背景，我尝试用手计算它。也就是随着n的增加我手动统计步数。我忽略所有我认为是恒定时间的东西。我是这样做的。假设我想计算 fib(5).
n = 0 - just a comparison on an if statement. This is constant.
n = 1 - just a comparison on an if statement. This is constant.
n = 2 - ignoring anything else, this should be 2 steps, fib(1) takes 1 step and fib(0) takes 1 step.
n = 3 - 3 steps now, fib(2) takes two steps and fib(1) takes 1 step.
n = 4 - 5 steps now, fib(3) takes 3 steps and fib(2) takes 2 steps.
n = 5 - 8 steps now, fib(4) takes 5 steps and fib(3) takes 3 steps.
从这些判断，我认为 运行 时间可能是 fib(n+1)。我不太确定 1 是否是常数因子，因为 fib(n) 和 fib(n+1) 之间的差异可能非常大。
我在 SICP 上阅读了以下内容：
In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree.
在这种情况下，我相信树中的节点数是 fib(n+1)。所以我相信我是正确的。但是，this video 让我感到困惑：
So this is a thing whose time complexity is order of actually, it turns out to be Fibonacci of n. There's a thing that grows exactly as Fibonacci numbers.
...
That every one of these nodes in this tree has to be examined.
我绝对震惊了。我已经检查了树中的所有节点，并且总是有 fib(n+1) 个节点，因此计算 fib(n) 时的步骤数。我不明白为什么有些人说它是 fib(n) 步数而不是 fib(n+1)。
我做错了什么？
在您的程序中，您有这个耗时的操作（按每个操作使用的时间排序，快速操作在列表顶部）：
- 加法
- IF（条件跳转）
- Return 来自子例程
- 函数调用
让我们看看执行了多少个动作，并将其与 n 和 fib(n) 进行比较：
n | fib | #ADD | #IF | #RET | #CALL
---+-----+------+-----+------+-------
0 | 0 | 0 | 1 | 1 | 0
1 | 1 | 0 | 1 | 1 | 0
对于 n≥2 你可以这样计算数字：
- fib(n) = fib(n-1) + fib(n-2)
- ADD(n) = 1 + ADD(n-1) + ADD(n-2)
- IF(n) = 1 + IF(n-1) + IF(n-2)
- RET(n) = 1 + RET(n-1) + RET(n-2)
- 呼叫(n) = 2 + 呼叫(n-1) + 呼叫(n-2)
为什么？
- ADD：一个加法直接在程序的顶层实例中执行，但是在两个子程序中，你调用的也是加法，需要执行。
- IF 和 RET：与之前相同的参数。
- CALL：也一样，但是你在top实例中执行了两个调用。
因此，这是您的其他 n 值的列表：
n | fib | #ADD | #IF | #RET | #CALL
---+--------+--------+--------+--------+--------
0 | 0 | 0 | 1 | 1 | 0
1 | 1 | 0 | 1 | 1 | 0
2 | 1 | 1 | 3 | 3 | 2
3 | 2 | 2 | 5 | 5 | 4
4 | 3 | 4 | 9 | 9 | 8
5 | 5 | 7 | 15 | 15 | 14
6 | 8 | 12 | 25 | 25 | 24
7 | 13 | 20 | 41 | 41 | 40
8 | 21 | 33 | 67 | 67 | 66
9 | 34 | 54 | 109 | 109 | 108
10 | 55 | 88 | 177 | 177 | 176
11 | 89 | 143 | 287 | 287 | 286
12 | 144 | 232 | 465 | 465 | 464
13 | 233 | 376 | 753 | 753 | 752
14 | 377 | 609 | 1219 | 1219 | 1218
15 | 610 | 986 | 1973 | 1973 | 1972
16 | 987 | 1596 | 3193 | 3193 | 3192
17 | 1597 | 2583 | 5167 | 5167 | 5166
18 | 2584 | 4180 | 8361 | 8361 | 8360
19 | 4181 | 6764 | 13529 | 13529 | 13528
20 | 6765 | 10945 | 21891 | 21891 | 21890
21 | 10946 | 17710 | 35421 | 35421 | 35420
22 | 17711 | 28656 | 57313 | 57313 | 57312
23 | 28657 | 46367 | 92735 | 92735 | 92734
24 | 46368 | 75024 | 150049 | 150049 | 150048
25 | 75025 | 121392 | 242785 | 242785 | 242784
26 | 121393 | 196417 | 392835 | 392835 | 392834
27 | 196418 | 317810 | 635621 | 635621 | 635620
你可以看到，加法的次数刚好是函数调用次数的一半（嗯，你也可以直接从代码中读到这个）。如果将初始程序调用算作第一个函数调用，那么 IF、returns 和调用的数量完全相同。
因此，您可以将 1 个 ADD、2 个 IF、2 个 RET 和 2 个 CALL 组合成一个需要恒定时间量的超级动作。
从列表中也可以看出，Additions的个数比fib(n+1)少1个（可以忽略）
因此，运行 时间顺序为 fib(n+1)。
比率fib(n+1) / fib(n)越来越接近Φ，n越大。 Φ 是黄金比例，即 1.6180338997，它是一个常数。订单中忽略常数因素。所以，顺序 O(fib(n+1)) 与 O(fib(n)).
现在让我们看看 space:
确实，处理一棵树所需的最大值 space 等于树与最远叶子之间的最大距离。这是真的，因为您在 f(n-1) 返回后调用 f(n-2)。
所以你的程序需要的 space 是 n.