如何使用递归求解T(n)= 5T(n/2)+ O(nlogn)
tox*_*ing 2 algorithm math big-o recurrence
所以这可能很愚蠢,但我坚持这个递归T(n) = 5T(n/2) + O(nlogn).我从大师定理中知道它应该是
,但我真的无法到达那里.
到目前为止,我得到了一点
我只是想知道我是否正朝这个方向前进
你肯定在这里正确的轨道!让我们看看我们是否可以简化这种求和.
首先,请注意您可以从求和中提取log n项,因为它与总和无关.这给了我们
(n log n)(k = 0到lg n(5/2)k之和)
这个总和是几何系列的总和,所以它解决了
((5/2)log n + 1 - 1)/(5/2 - 1)
= O((5/2)lg n)
在这里,我们可以使用log(c b = c log b a)重写的(可爱)标识
O((5/2)lg n)= O(n lg 5/2)
= O(n lg 5 - 1)
并将其重新插入我们的原始配方中
n log n·O(n lg 5 - 1)= O(n lg 5 log n).
嗯,那不太合适.不过,我们真的非常非常接近在这里工作的东西!一个很好的问题是为什么这不起作用,为此,我们必须回到你如何得到原始总和.
让我们尝试使用递归方法扩展递归T(n)的几个项.第一次扩张给了我们
T(n)= 5T(n/2)+ n log n.
下一个是事情变得有趣的地方:
T(n)= 5T(n/2)+ n log n
= 5(5T(n/4)+(n/2)log(n/2))+ n log n
= 25T(n/4)+(5/2)log(n/2)+ n log n
然后我们得到
T(n)= 25T(n/4)+(5/2)log(n/2)+ n log n
= 25(5T(n/8)+(n/4)log(n/4))+(5/2)log(n/2)+ n log n
= 125T(n/8)+(25/4)n log(n/4)+(5/2)log(n/2)+ n log n
这里的一般模式似乎是以下总和:
T(n)=从i = 0到lg n(5/2)k n lg(n/2 k)之和
= n从i = 0到lg n(5/2)k lg(n/2 k)之和
请注意,这不是您原来的总和!特别要注意的是,日志项不是log n,而是一个比这更慢的函数.事实上,随着k变大,这个对数项变得更小,更小.事实上,如果你考虑一下,我们唯一真正支付全部费用的时候是k = 0.
这是一个可爱的小技巧,我们可以使用它来使这个总和更容易使用.对数函数非常非常缓慢地增长,事实上,我们可以说log n = o(nε)对于任何ε> 0.那么如果我们通过替换lg来尝试上限这个求和会发生什么呢？ N/2 ķ)与(N/2 ķ)ε对于一些非常小,但正ε？好吧,那我们就搞定了
T(n)= n从i = 0到lg n(5/2)k lg(n/2 k)之和
= O(n = i = 0到lg n(5/2)k(n/2 k)ε)
= O(N从i求和= 0向LG N(5/2)ķ Ñ ε(1/ε)ķ)
= O(从i = 0到lg n(5/2 1 +ε)的n 1 +ε和)
这可能看起来像某种巫术,但这种技术 - 用微小的微小多项式替换原木 - 是一个很好的保存在你的后袋.它往往出现在很多情况下!
我们这里的表达可能看起来比我们开始时的情况要糟糕得多,但它会变得更好.让我们假设我们选择ε足够小 - 比如说,那么5/2 1 +ε大于1.然后,内部求和再一次是几何级数的总和,因此我们将其简化为
((5/2 1 +ε)lg n + 1 - 1)/(5/2 1 +ε - 1)
= O((5/2 1 +ε)lg n)
= O(n lg(5/2 1 +ε))(使用之前的技巧)
= O(n lg 5 - 1 - ε)
这很好,因为我们的整体运行时间就是这样
T(N)= O(N 1 +ε Ñ LG 5 - 1 - ε)
= O(n lg 5),
你有你的上限!
总结一下:
您可以使用几何级数之和的公式以及log b c = c log b a的奇怪标识来简化原始求和.
但是,这不会给你一个紧张的上限,因为你的原始总和与你从递归方法得到的结果略有偏差.
通过使用递归方法重复分析,您可以得到更严格的总和,但是更难以评估.
我们可以通过使用log n = o(nε)对任何ε> 0 的事实来简化该求和,并使用它来重新调整总和以使其更容易操作.
通过这种简化,我们基本上使用与以前相同的技术重做分析 - 几何系列的总和,在指数和日志中交换术语 - 以得到结果.
希望这可以帮助!