13 
T(n) = 2T(n/2) + 0(1)

T(n) = T(sqrt(n)) + 0(1)

在第一个中，我对 n、logn 等使用替换方法；都给了我错误的答案。
递归树：我不知道我是否可以申请，因为根将是一个常数。

有人可以帮忙吗？

4

6 回答 6

11

用于Master Theorem解决此类递归关系。

令a为大于或等于 1 的整数，b为大于 1 的实数。令c为正实数， d为非负实数。鉴于表格的重复

  • T (n) = a T(n/b) + n c .. 如果 n > 1

  • T(n) = d .. 如果 n = 1

那么对于 b 的 na 次方，

  1. 如果 log b a < c, T (n) = Θ(n c ),
  2. 如果 log b a = c, T (n) = Θ(n c log n),
  3. 如果 log b a > c，T (n) = Θ(n log b a )。

1)T(n) = 2T(n/2) + 0(1)

在这种情况下

a = b = 2;
日志b a = 1; c = 0 (因为 n c =1 => c= 0)

所以情况（3）是适用的。所以T(n) = Θ(n):)

2)T(n) = T(sqrt(n)) + 0(1)

设 m = log 2 n;

=> T(2 m ) = T( 2 m / 2 ) +0(1)

现在重命名 K(m) = T(2 m ) => K(m) = K(m/2) +0(1)

应用案例 (2)。

于 2010-10-18T03:19:05.033 回答
11

让我们看第一个。首先，你需要知道 T(base case)。你提到它是一个常数，但是当你做这个问题时，把它写下来很重要。通常它类似于 T(1) = 1。我会使用它，但你可以推广到它是什么。

接下来，找出你递归的次数（即递归树的高度）。n是您的问题大小，那么我们可以重复将 n 除以 2 多少次？从数学上讲，我是什么时候n/(2^i) = 1？想清楚，以后再坚持。

接下来，做一些替换，直到你开始注意到一个模式。

T(n) = 2(2(2T(n/2*2*2) + θ(1)) + θ(1)) + θ(1)

好的，模式是我们将 T() 多次乘以 2，然后将 n 除以 2 多次。多少次？i次。

T(n) = (2^i)*T(n/(2^i)) + ...

对于最后的大 θ 项，我们使用了一个可爱的技巧。看看上面我们有几个替换的地方，忽略 T() 部分。我们想要 θ 项的总和。请注意，它们加起来为(1 + 2 + 4 + ... + 2^i) * θ(1)。你能找到一个封闭的形式1 + 2 + 4 + ... + 2^i吗？我给你那个；它是 (2^i - 1)。只是记住它是一个很好的方法，但这是你如何弄清楚的。

无论如何，总而言之，我们得到

T(n) = (2^i) * T(n/(2^i)) + (2^i - 1) * θ(1)

如果你i早点解决了，那么你就知道了i = log_2(n)。把它插入，做一些代数，然后你就可以开始了

T(n) = n*T(1) + (n - 1)*θ(1). T(1) = 1. 所以T(n) = n + (n - 1)*θ(1)。即 n 乘以一个常数，加上一个常数，再加上 n。我们去掉了低阶项和常数，所以它是 θ(n)。

Prasoon Saurav 使用主方法是正确的，但重要的是你要知道递归关系在说什么。要问的是，我在每个步骤中做了多少工作，以及输入 size 的步骤数是多少n？

于 2010-10-18T04:40:58.457 回答
7

对于第 1 部分，您可以按照 @Prasoon Saurav 的建议使用 Master Theorem。

对于第 2 部分，只需扩展递归：

T(n) = T(n ^ 1/2) + O(1)         // sqrt(n) = n ^ 1/2
     = T(n ^ 1/4) + O(1) + O(1)  // sqrt(sqrt(n)) = n ^ 1/4
     etc.

该系列将继续k条款直到n ^ 1/(2^k) <= 1，即2^k = log n或k = log log n。这给了T(n) = k * O(1) = O(log log n).

于 2010-10-18T04:10:32.260 回答
1

让我们看看第一个递归，T(n) = 2T(n/2) + 1。n/2 是我们的线索：每个嵌套项的参数是其父项的一半。因此，如果我们从 n = 2^k 开始，那么在我们达到基本情况 T(0) 之前，我们将有 k 个项在我们的扩展中，每个项都加 1。因此，假设 T(0) = 1，我们可以说 T(2^k) = k + 1。现在，由于 n = 2^k，我们必须有 k = log_2(n)。因此 T(n) = log_2(n) + 1。

我们可以将相同的技巧应用于您的第二次重复，T(n) = T(n^0.5) + 1。如果我们从 n = 2^2^k 开始，我们将在展开式中有 k 个项，每个项加 1 到全部的。假设 T(0) = 1，我们必须有 T(2^2^k) = k + 1。由于 n = 2^2^k，我们必须有 k = log_2(log_2(n))，因此 T(n) = log_2(log_2(n)) + 1。

于 2010-10-18T04:02:09.597 回答
0

Most of the time the best way to deal with recurrence is to draw the recurrence tree and carefully handle the base case.

However here I will give you slight hint to solve using substitution method.

In recurrence first try substitution n = 2^k In recurrence second try substitution n = 2^2^k

于 2014-09-15T22:56:41.903 回答
0

递归关系和递归函数也应该从 f(1) 开始求解。在情况 1 中，T(1) = 1；T(2) = 3；T(4) = 7；T(8) = 15；很明显，T(n) = 2 * n -1，在 O 表示法中是 O(n)。
在第二种情况下 T(1) = 1; T(2) = 2; T(4) = 3；T(16) = 4；T(256) = 5；T(256 * 256) =6；很快就会发现 T(n) = log(log(n)) + 1 其中 log 以 2 为底。显然这是 O(log(log(n)) 关系。

于 2010-10-18T07:00:56.817 回答