递归和大O

题

我最近正在完成一项涉及递归和大 O 表示法的计算机科学作业。我相信我很好地理解了这一点（虽然当然不是完美的！）但是有一个问题给我带来了最多的问题。奇怪的是，一看，这似乎是作业上最简单的一个。

使用大哦符号提供最佳增长率来解决以下递归问题？

T(1) = 2

T(n) = 2T(n - 1) + 1（n>1）

选择是：

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

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

解决方案

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

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

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ⁿ).

其他提示

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

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

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

换一种方式：递归产生：

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

什么 big-Oh 表示法最能描述序列 2、5、11、23、47...

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

我认为这将是指数级的。每次增加 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)

我认为这将是指数级的。n 每增加一倍，计算量就会增加一倍。

不，事实并非如此。恰恰相反：

考虑一下对于 n 迭代，我们得到运行时间右. 。那么对于 n + 1次迭代我们将得到准确的结果右 + 1.

因此，增长率是恒定的，总体运行时间确实是氧(n).

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

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

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

首先，所有四个答案都比 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)

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

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

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

T(1) = 3*2^0 - 1 = 3 - 1 = 2. OK.

就职：

Suppose T(n) = 3*2^(n-1) - 1. Then
T(n+1) = 2*T(n) + 1 = 3*2^n - 2 + 1 = 3*2^((n+1)-1) - 1. OK.

第一个平等源于复发定义，第二个源于电感假设。量子ED。

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

对于回答 O(n) 的人：我非常同意迪马的观点。问题是不是询问计算 T(n) 的算法的计算复杂度的最严格上限（现在是 O(1)，因为已经提供了其封闭形式）。该问题要求最紧的上限 关于 T(n) 本身, ，这就是指数。

许可以下： CC-BY-SA 和归因