使用 C++ 中的 Robert Sedwick 书自学算法
A recursive function that divides a problem of size N into two independent (nonempty) parts that it solves recursively calls itself less than N times.
If the parts are one of size k and one of size N-k, then the total number of recursive calls that we use is T(n) = T(k) + T(n-k) + 1, for N>=1 with T(1) = 0.
The solution T(N) = N-1 is immediate by induction. If the sizes sum to a value less than N, the proof that the number of calls is less than N-1 follows from same inductive argument.
我对以上文字的问题是
- 作者如何通过归纳得出解决方案 T(N) = N-1？请帮助我理解。
- 作者所说的“如果大小之和小于 N，调用次数小于 N-1 的证明来自相同的归纳论证”是什么意思？
我是数学归纳法的新手，所以理解起来有困难。
感谢您的时间和帮助
最佳答案
(1) 通过归纳法:
T(1) = 0 (base)
T(N) = T(k) + T(N-k) + 1 (definition of problem)
我们假设每个 n < N ，我们得到 T(n) = n-1
由于两者k和 N-k比N小, 我们从归纳假设得到:
T(N) = (k-1) + (N-k-1) + 1 = N-1
^ ^
T(k) T(N-k)
(2) 使用相同的参数: 如果
T(N) = T(k) + T(m) + 1 where k+m < N
那么同样的证明会导致T(N) < N-1
关于algorithm - 递归函数分析中的递归调用次数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12264936/