有人可以帮助解决这种复发关系吗？ [关闭

StackOverflow https://stackoverflow.com/questions/3956403

题 

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

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

在第一个中，我使用n，logN等的替换方法；所有人都给了我错误的答案。
复发树：我不知道我是否可以应用，因为根部将是一个常数。

有人可以帮忙吗？

有帮助吗？

解决方案

让我们看看第一个。首先，您需要知道T（基本案例）。您提到这是一个常数，但是当您做问题时，写下它很重要。通常，它像t（1）= 1。我会使用它，但是您可以推广到它。

接下来，找出您的复发次数（即递归树的高度）。 n 您的问题大小是否可以反复将n除以2？从数学上讲，我是什么时候 n/(2^i) = 1？弄清楚，请稍等。

接下来，进行一些替换，直到您开始注意到模式。

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

好的，模式是我们将t（）乘以两次，然后将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对使用主方法是正确的，但是重要的是要知道复发关系在说什么。要问的事情是，我在每个步骤中要做多少工作，以及大小输入的步骤数是多少 n?

其他提示

利用 Master Theorem 解决这种复发关系。

让 一个 成为大于或等于1的整数，并且 b 是一个大于1的实际数字 C 是一个积极的实际数字， d 一个非负实数。给定表格的复发

  • t（n）= a t（n/b） + nC ..如果n> 1

  • t（n）= d ..如果n = 1

然后，对于B的NA力量，

  1. 如果logb a <c，t（n）=θ（nC),
  2. 如果logb a = c，t（n）=θ（nC log n），
  3. 如果logb a> c，t（n）=θ（n日志b 一个).

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

在这种情况下

a = b = 2;
日志b a = 1; C = 0（由于nC = 1 => c = 0）

因此，案例（3）是适用的。所以 T(n) = Θ(n) :)

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

令M =日志2 n;

=> t（2m）= t（2M / 2 ) + 0(1)

现在重命名k（m）= t（2m）=> k（m）= k（m/2） + 0(1)

适用案例（2）。

对于第1部分，您可以使用@prasoon Saurav建议使用Master定理。

对于第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, ， IE 2^k = log n 或者 k = log log n. 。那给了 T(n) = k * O(1) = O(log log n).

让我们看一下第一次复发，t（n）= 2t（n/2）+1。n/2是我们的线索：每个嵌套项的参数是其父的一半。因此，如果我们从n = 2^k开始，则在扩展中将具有k项，每个术语在总体案例t（0）之前，每个术语将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添加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。

还应通过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（log（n））关系）。

在大多数情况下，处理复发的最佳方法是绘制复发树并仔细处理基本情况。

但是，在这里，我将使用替代方法给您一些提示。

在重复中首先尝试替代 n = 2^k在复发中第二次尝试替代 n = 2^2^k

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top