如何选择基本情况作为求解递推式的替代方法？

Question

我试图找出如何使用替换方法解决递归问题，但我不明白当未明确给出基本情况时如何选择基本情况？

目前，我面临两个问题，例如 T(n) = 2T(floor(n/2)) + theta(n) ，其中基本情况是 n = 2,3 时，对于这个问题 T(n) = T (n-1) + n ，我不确定，但在互联网上检查基本情况应该是 1。 到目前为止，我所理解的是基本情况是没有递归的输入大小，因此对于第一个示例，为什么 n=1 不是基本情况，因为它也不涉及递归。 请帮忙！！ 谢谢

Answer 1

对于问题 2，
[...]
为什么 n=1 不是基本情况，因为它也不涉及递归？

在编程的背景下，问题（2）中的n是你的输入大小（所以不用担心递归地减少到无限负数）。如果在递归关系中没有给出明确的基本情况（这实际上是代码中递归函数的翻译）并且您的输入大小对于每个后续调用都在减小，那么默认情况下您的基本情况为零。这意味着您的函数没有剩余的输入需要处理，因此，没有完成任何工作。这相当于返回

Null

或

0

以防止类型评估问题。

如果您应用替换法来确定 T(n) = T(n - 1) + n 的界限，您最终将得到以下 k^th 项：

[k]：T(n) = T(n - k) + n - (k - 1) + n - (k - 2) + ... + n - (k - k)

在某个时刻（默认基本情况），不再需要处理输入，即 T([n - k] = 0) 返回 0。

如果 n - k = 0；那么 k = n。然后用 n 代替 [k] 中的 k 来确定 T(n) 的边界：

[k]：T(n) = 0 + 1 + 2 + ... + n

因此，T(n)只不过是n自然数的和，即n(n+1)/2。 因此，T(n) 是 O(n²)。

Q.E.D.