我遇到了一些关于如何解决递归关系的问题。解决复发T（n）= T（n/2）+ lg n？
T（N）= T（N/2）+的log 2（N），T（1）= 1，其中n为2
此电源是一个家庭作业的问题，所以不要只给我答案。我只是想知道如何开始这个问题。
在课上我们去了the Master theorem。但我认为这不是解决这种特殊关系的最好方法。
我真的不知道如何下手这个问题......我应该只是被去
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)
而只是继续我的工作方式，以得到的东西，我可以看到使一个基本的公式？
这复发解决到Θ（（log n）的）。这里有两种方法可以看到这一点。
如果你知道n是两个完美的功率（即n = 2 ķ），你可以重写复发的
T（2 ķ）= T（2 K-1）+ K
让我们定义一个新复发S（k）的= T（2 ķ）。然后，我们得到了
S（K）= S（K - 1）+ K
如果我们扩大了这种复发，我们得到了
S（K）= S（的k - 1）+ K
= S（K - 2）+（K - 1）+ K
= S（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）+ Θ（K ）
假设S（0）= 1，则这个解决复发到Θ（K ）。
由于S（k）的= T（2 ķ）= T（n）时，我们得到T（N）= Θ（K ）= Θ（日志 N）。
另一个选择是扩大了复发的几个方面，并看看是否有很好的模式出现。下面是我们得到：
T（N）= T（N/2）+ LGñ
= T（N/4）+ LG（N/2）+ LGñ
= T（N/8）+ LG（N/4）+ LG（N/2）+ LGñ
...
最终，LG n个层之后，此复发降至最低点和我们留下这个表情：
LG的n + LG（N/2）+ LG（N/4）+ ... + LG（N/2 LG n）的
使用对数的特性，我们可以重写该作为
LG N +（LG N - 1）+（LG N - 2）+（LG N - 3）+ ... +（LG N - LG N）
或者，写在相反，这是总和
0 + 1 + 2 + 3 + ... + LGÑ
即总和为高斯总结给LG n，这个计算结果为（LG n）的（LG N + 1）/ 2 = （（log n）2）。
希望这会有所帮助！
您好先生，我无法前进在这里使用您的方法https://i.stack.imgur.com/6E3iB.png – laura
而不是将所有的日志术语分组在一起，将它们分开。使用lg（n/2^k）= lg n - k的事实。 – templatetypedef
是的，先生，我明白你的方法。你在上述qstn中完成了......我只是好奇地解决另一种方式，我给你的图像:)谢谢你的答复 – laura
这可以用Akra-Bazzi定理完成。请参见http://people.mpi-inf.mpg.de/~mehlhorn/DatAlg2008/NewMasterTheorem.pdf中的第三个示例。
如果n是2的幂，那么你可以扩大迭代并精确求解，使用lg（a/b）= lg（a） - lg（b）。
T(n) = lg(n) + lg(n/2) + lg(n/4) + ... + lg(1) + 1
= (lg(n) - 0) + (lg(n) - 1) .... + (lg(n) - lg(n)) + 1
= lg(n)*lg(n) - lg(n)*(lg(n)+1)/2 + 1
= lg(n)*lg(n)/2 - lg(n)/2 + 1
这可以用Master theorem来解决。您的a=1和b=2和f(n) = log(n)。然后c = log2(1) = 0。因为你的c和f(n)属于第二种情况（其中k=1）。
因此，解决办法是Θ（日志 N）
这个问题似乎是题外话，因为它不是一个编程问题。尝试math.stackexchange.com。 –
这个问题不适用于Stack Overflow，因为它不是关于编程。数学问题可能会在[math.SE] Stack Exchange上提出。 –
我投票结束这个问题作为题外话，因为它是关于数学，而不是编程。 – Pang