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

Question

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

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

在第一个我使用替代方法为n，logn等;都给了我错误的答案。
复发树：我不知道我是否可以申请，因为根将是一个常数。

有人可以帮忙吗？

Answer 1

让我们看看第一个。首先，你需要知道T（基本情况）。你提到这是一个常数，但是当你解决这个问题时，记住它是很重要的。通常它就像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)。这是一个很好的记忆，但here's how you'd figure it out。

总之，一切的一切，我们得到

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的输入步数是多少？

Answer 2

使用Master Theorem来解决这样的递归关系。

让一个是一个整数大于或等于1并且b是一个实数大于 1.让Ç是正的实数和 d非负实数。给出的形式

• T（n）的复发=αT（N/B）+ N ^Ç ..如果n> 1

• T（N）= d ..如果n = 1的

然后对于b的NA功率，

1. 如果日志 _b一个< C，T（N）=Θ（N ^Ç），
2. 如果日志 _b一个= C，T（N）=Θ（N ^ç log n）的，
3. 如果日志 _{b T（n）=Θ（n ^{log b a}）。}

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

在这种情况下

A = B = 2;
log _b a = 1; c = 0（因为n ^c = 1 => c = 0）

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

---

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

设M =登录 N;

=> T（2^米）= T（2^{米/ 2}）+ 0(1)

立即重命名K（M）= T（2^米）=> K（M）= K（m/2）+ 0(1)

应用案例（2）。

---

Answer 3

让我们来看看第一次复发，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。

Answer 4

对于第1部分，您可以使用@Prasoon Saurav建议的主定理。

对于第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)。

Answer 5

递归关系和递归函数也应该从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））关系。

Answer 6

大部分的时间来处理复发的最好方法是画复发树慎重处理基本情况。

不过在这里我给大家略带使用替换的方法来解决。

在复发第一次尝试替代n = 2^k 再次发生第二次尝试替代n = 2^2^k