我被一个反复出现的问题困住了。
t（n）=t（n/2）+对数n
我现在知道的是：
T（N）=T（N/2）+对数N
t（n/2）=t（n/4）+对数（n/2）
...
t（n）=t（n/2^k）+和[i=0和k{log（n/2^i）}]
我被困在下一步该做什么上。请给我一些建议。
谢谢！
最佳答案
另一种方法是使用Master Theorem（或Wikipedia）。对于大多数复发，它是适用的，并提供了非常快的答案。
它基本上给了你三个类别，然后答案就出来了给定t（n）=at（n/b）+f（n）形式的递推，我们寻找a、b和f（n）。在你的例子中，我们有a=1，b=2，f（n）=logn。
因此（你必须看看引用的链接）我们进入案例2，其中f（n）在θ（n^（log b（a-eps））log k（n））=θ（n^0 logn）），然后主定理指出T（n）在θ（n^（logb（a-eps））logk^（k+1）（n））=θ（log 2（n））中