理解拉姆达适用于主定理

Question

假设我有一个像T（n）= 2T（n/4）+1的情况。 f（n）= 1 a = 2和b = 4。因此n ^（1/2）> 1。这应该是情况1.然而，在情况1中也存在λ，所以对于一些λ> 0，f（n）= O（n ^（（1/2）-λ））。在这种情况下，lambda会是1/2？

Answer 1

是的，这是正确的。注意，在这种情况下，我们有a = 2和b = 4。在这种情况下函数f（n）是1，我们确实有1 = Θ（n ^{1/2 - ＆epsilon;}）一些＆epsilon; > 0，在这种情况下＆epsilon; = 1/2。因此，通过主定理，您将得到T（n）= Θ（n ^1/2）。

这个eps的点，如果每一层完成的工作量足够小（低于日志 _b a），那么工作主要由分裂而不是每层的工作来支配。事实上，你可以减去＆epsilon;指数中的> 0表示每层的工作必须严格地渐近地慢于分裂速率，并且必须通过一些多项式量来实现。

希望这会有所帮助！