algorithm - 递归关系

Question

为什么递归阶乘算法的递归关系是这样的？

T(n)=1 for n=0
T(n)=1+T(n-1) for n>0

为什么不是这个？

T(n)=1 for n=0
T(n)=n*T(n-1) for n>0

输入 n 的值，即 1、2、3、4...... 第二个递归关系成立(正确计算阶乘)而不是第一个。

Answer 1

我们一般使用递推关系来求算法的时间复杂度。

---

这里，函数 T(n) 实际上不是用于计算阶乘的值，而是告诉您阶乘算法的时间复杂度。

---

这意味着找到 n 的阶乘比 n-1 的阶乘多 1 次操作(即 T(n)=T(n-1)+1)等等。

---

所以递归阶乘算法的正确递归关系是对于 n=0，T(n)=1对于 n>0，T(n)=1+T(n-1)不是你后面提到的。

---

就像汉诺塔的重现一样对于 n>0，T(n)=2T(n-1)+1；

更新:它与一般的实现没有任何关系。但是递归可以给出编程范式的直觉，例如如果 T(n)=2*T(n/2)+n(合并排序)这给出了分而治之的直觉，因为我们将 n 分成两半。

另外，如果你要求解方程式，它会给你一个运行时间的限制。例如大 oh 符号。