求解递归T(n)= T(n/2)+ lg n? [英] Solving the recurrence T(n) = T(n/2) + lg n?

问题描述

我在解决递归关系方面遇到一些问题.

I am having some issues on how to solve recurrence relations.

T(n)= T(n/2)+ log2(n)，T(1)= 1，其中n是2的幂.

T(n) = T(n/2) + log2(n), T(1) = 1, where n is a power of 2

这是一个作业问题，所以不要只给我答案.我只是想知道如何开始这个问题.

This is a homework problem, so don't just give me the answer. I was just wondering how to start the problem.

在课堂上，我们回顾了大师定理.但是我认为这不是解决这种特殊关系的最佳方法.

In class we went over the Master theorem. But I don't think that would be the best way to solve this particular relation.

我真的不知道如何解决这个问题...我应该去

I don't really know how to start the problem... should I just be going

T(n) = T(n/2) + log_base2(n)
T(n/2) = [T(n/4)+log_base2(n/2)]
  T(n) = [T(n/4)+log_base2(n/2)] + log_base2(n) 

只要继续努力就可以得到我能看到的基本方程式?

And just keep working my way down to get something I can see makes a basic equation?

推荐答案

此重复解决了Θ((log n) ² ).这是两种查看方法.

This recurrence solves to Θ((log n)²). Here are two ways to see this.

如果您知道n是2的完美幂(即n = 2 ^k )，则可以将递归重写为

If you know that n is a perfect power of two (that is, n = 2^k), you can rewrite the recurrence as

T(2 ^k )= T(2 ^k-1 )+ k

T(2^k) = T(2^k-1) + k

让我们定义一个新的递归S(k)= T(2 ^k ).然后我们得到了

Let's define a new recurrence S(k) = T(2^k). Then we get that

S(k)= S(k-1)+ k

S(k) = S(k - 1) + k

如果我们扩大这种重复发生，我们就会得到

If we expand out this recurrence, we get that

S(k)= S(k-1)+ k

S(k) = S(k - 1) + k

= S(k-2)+(k-1)+ k

= S(k - 2) + (k - 1) + k

= S(k-3)+(k-2)+(k-1)+ k

= S(k - 3) + (k - 2) + (k - 1) + k

= S(k-4)+(k-3)+(k-2)+(k-1)+ k

= S(k - 4) + (k - 3) + (k - 2) + (k - 1) + k

...

= S(0)+1 + 2 + 3 + ... + k

= S(0) + 1 + 2 + 3 + ... + k

= S(0)+Θ(k ² )

= S(0) + Θ(k²)

假设S(0)= 1，则此递归求解为&θ;(k ² ).

Assuming S(0) = 1, then this recurrence solves to Θ(k²).

因为S(k)= T(2 ^k )= T(n)，所以我们得到T(n)=Θ(k ² )=&Theta ;(log ² n).

Since S(k) = T(2^k) = T(n), we get that T(n) = Θ(k²) = Θ(log² n).

这里的另一种选择是扩展一些重复项，并查看是否出现了任何不错的模式.这就是我们得到的:

Another option here is to expand out a few terms of the recurrence and to see if any nice patterns emerge. Here’s what we get:

T(n)= T(n/2)+ lg n

T(n) = T(n / 2) + lg n

= T(n/4)+ lg(n/2)+ lg n

= T(n / 4) + lg (n / 2) + lg n

= T(n/8)+ lg(n/4)+ lg(n/2)+ lg n

= T(n / 8) + lg (n / 4) + lg (n / 2) + lg n

...

最终，在lg n层之后，这种重复出现了，我们剩下了以下表达式:

Eventually, after lg n layers, this recurrence bottoms out and we’re left with this expression:

lg n + lg(n/2)+ lg(n/4)+ ... + lg(n/2 ^{lg n)}

lg n + lg (n / 2) + lg (n / 4) + ... + lg (n / 2^{lg n)}

使用对数的属性，我们可以将其重写为

Using properties of logarithms, we can rewrite this as

lg n +(lg n-1)+(lg n-2)+(lg n-3)+ ... +(lg n-lg n)

lg n + (lg n - 1) + (lg n - 2) + (lg n - 3) + ... + (lg n - lg n)

或者相反，这是总和

0 +1 + 2 + 3 + ... + lg n

0 + 1 + 2 + 3 + ... + lg n

该和是高斯与lg n的和，其求和为(lg n)(lg n +1)/2 =Θ((log n)2 ).

That sum is Gauss’s sum up to lg n, which evaluates to (lg n)(lg n + 1) / 2 = Θ((log n)2).

希望这会有所帮助！

这篇关于求解递归T(n)= T(n/2)+ lg n?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！