了解 lambda 应用于主定理的情况
假设我有一个类似 T(n)=2T(n/4)+1 的情况。 f(n)=1 a=2 且 b=4。因此n^(1/2)＞1。这应该是情况 1。然而，情况 1 中也存在 lambda，因此对于某些 lambda >0，f(n)=O(n^((1/2)-lambda))。在这种情况下 lambda 将是 1/2？
Suppose i have a case like T(n)=2T(n/4)+1. f(n)=1 a=2 and b=4. Thus n^(1/2)>1. That should be case 1. However there is also a lambda in case 1, so that f(n)=O(n^((1/2)-lambda)) for some lambda >0. In this case lambda would be 1/2?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
是的，这是正确的。请注意，在这种情况下，我们有 a = 2 和 b = 4。在这种情况下，函数 f(n) 是 1，并且我们确实有 1 = θ(n1/2 - ε) 对于某些 ε > 0，在这种情况下 ε = 1/2。因此，根据主定理，您将得到 T(n) = θ(n1/2)。
这个 ε 的要点是，如果每个级别完成的工作量足够小（低于 logb a），那么工作主要由拆分而不是每个级别的工作主导。事实上，您可以减去 ε >指数为 0 表示每个级别的工作量必须严格渐近地慢于分裂率，并且必须以某个多项式量增长。
希望这有帮助！
Yes, that's correct. Note that, in this case, we have that a = 2 and b = 4. The function f(n) in this case is 1, and we do have that 1 = Θ(n1/2 - ε) for some ε > 0, where in this case ε = 1/2. Consequently, by the Master Theorem, you would get that T(n) = Θ(n1/2).
The point of this ε is that if the amount of work done per level is sufficiently small (below logb a), then the work is dominating primarily by the splitting rather than the work per level. The fact that you can subtract ε > 0 from the exponent indicates that the work per level must grow strictly asymptotically slower than the splitting rate, and must do so by some polynomial amount.
Hope this helps!