recursion - 递归和大 O

Question

我一直在完成最近的计算机科学作业，涉及递归和大 O 表示法。我相信我非常了解这一点（当然，当然不完美！）但是有一个问题特别给我带来了最多的问题。奇怪的是，看着它，它看起来是作业中最简单的一个。

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

T(1) = 2

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

选择是：

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

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

score 17 · Accepted Answer

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

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

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) = 2 ^n-1 ⋅T(1) + 2 ^n-2 + 2 ^n-3 + ... + 1
T(n) = 2 ^n-1 ⋅2 + 2 ^n-2 + 2 ^{n- 3} + ... + 1
T(n) = 2 ⁿ + 2 ^n-2 + 2 ^n-3 + ... + 1

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

score 15 · Accepted Answer

我想你有点误解了这个问题。它不会问您解决复发需要多长时间。它询问解决方案本身的大 O（渐近界）是什么。

你要做的是想出一个封闭形式的解决方案，即T(n)的非递归公式，然后确定那个表达式的大O是什么。

score 2 · Accepted Answer

我认为这将是指数级的。每次增加 n 都会使值增加一倍。

T(2) = 2 * T(1) = 4
T(3) = 2 * T(2) = 2 * 4
...

T(x) 将是以下程序的运行时间（例如）：

def fn(x):
 if (x == 1):
  return    # a constant time
 # do the calculation for n - 1 twice
 fn(x - 1)
 fn(x - 1)

score 2 · Accepted Answer

问题是要求求解递归的大哦符号，而不是计算递归的成本。

换句话说：重复产生：

  1 -> 2
  2 -> 5
  3 -> 11
  4 -> 23
  5 -> 47

什么大哦符号最能描述序列 2, 5, 11, 23, 47, ...

解决这个问题的正确方法是求解递推方程。

score 1 · Accepted Answer

我认为这将是指数级的。n 的每一个增量都会带来两倍的计算量。

不，它没有。恰恰相反：

考虑对于n次迭代，我们得到运行时间R。然后对于n + 1 次迭代，我们将准确地得到R + 1。

因此，增长率是恒定的，整体运行时间确实是O ( n )。

但是，我认为 Dima 对这个问题的假设是正确的，尽管他的解决方案过于复杂：

你要做的是想出一个封闭形式的解决方案，即T(n)的非递归公式，然后确定那个表达式的大O是什么。

检查T ( n ) 和T ( n + 1) 迭代的相对大小并确定相对增长率就足够了。数量明显翻倍，直接给出了渐近增长。

score 1 · Accepted Answer

首先，所有四个答案都比 O(n) 差... O(n*log n) 比普通的旧 O(n) 更复杂。更大的：8 或 8 * 3、16 或 16 * 4 等...

关于实际问题。如果您不进行递归，则通用解决方案显然可以在恒定时间内解决

（ T(n) = 2^(n - 1) + 2^(n) - 1 ），所以这不是他们要的。

如您所见，如果我们编写递归代码：

int T( int N )
{
    if (N == 1) return 2;
    return( 2*T(N-1) + 1);
}

这显然是 O(n)。

所以，这似乎是一个措辞不好的问题，他们可能问的是函数本身的增长，而不是代码的复杂性。那是 2^n。现在去做剩下的作业......然后学习 O(n * log n)

score 1 · Accepted Answer

计算递归的封闭形式解决方案很容易。通过检查，您猜测解决方案是

T(n) = 3*2^(n-1) - 1

然后你通过归纳证明这确实是一个解决方案。基本情况：

T(1) = 3*2^0 - 1 = 3 - 1 = 2。好的。

就职：

假设 T(n) = 3*2^(n-1) - 1。那么
T(n+1) = 2*T(n) + 1 = 3*2^n - 2 + 1 = 3*2^((n+1)-1) - 1。好的。

其中第一个等式源于递归定义，第二个源于归纳假设。QED。

3*2^(n-1) - 1 显然是 Theta(2^n)，因此正确答案是第三个。

对于回答 O(n) 的人：我完全同意 Dima。该问题不要求计算 T(n) 的算法的计算复杂度的最严格上限（现在为 O(1)，因为已经提供了它的封闭形式）。该问题要求T(n) 本身的最严格上限，即指数上限。

7 回答 7