递归和大 O

Question

我最近一直在完成一项涉及递归和大 O 符号的计算机科学作业。我相信我很清楚这一点(当然，当然不是很完美!)但是有一个问题特别给我带来了最多的问题。奇怪的是，看着它，它看起来是家庭作业中最简单的。

使用 big-Oh 表示法提供最佳增长率以解决以下递归问题？

T(1) = 2

T(n) = 2T(n - 1) + 1 对于 n>1

选择是:

O(n log n)

O(n^2)

O(2^n)

O(n^n)

我知道大 O 是一个上限，用于描述该程序或进程将花费的最多计算量或最长运行时间。我觉得这个特定的递归应该是 O(n)，因为，对于 n 的每个值，最多只发生一次递归。由于 n 不可用，它要么比 O(nlogn) 好，要么更糟，作为其他三个选项。

所以，我的问题是:为什么这不是 O(n)？

Answer 1

有几种不同的方法可以解决递归问题:替换、递归树和主定理。主定理在这种情况下不起作用，因为它不符合主定理的形式。

您可以使用其他两种方法，但解决此问题的最简单方法是迭代解决。

T(n) = 2T(n-1) + 1
T(n) = 4T(n-2) + 2 + 1
T(n) = 8T(n-3) + 4 + 2 + 1
T(n) = ...

看到图案了吗？

T(n) = 2n-1⋅T(1) + 2n-2 + 2n-3 + ... + 1
T(n) = 2n-1⋅2 + 2n-2 + 2n-3 + ... + 1
T(n) = 2n + 2n-2 + 2n-3 + ... + 1

因此，最严格的界限是 Θ(2n)。