algorithm - 寻找主定理的 lambda

Question

假设我有这样的案例

T(n)=2T(n/4)+log(n). a=2, b=4, f(n)=log(n)

这应该是情况 1，因为 n^(1/2)>log(n)。在情况 1 中还有一个 lambda。f(n)=O(n^((1/2)-lambda)。这是正确的吗？我怎样才能找到这个 lambda？

Answer 1

常数 lambda 很重要:它的目的是避免考虑情况 1 和情况 2 之间的奇怪情况。由于 big-O 只是上限而不是下限，较小的lambda 的选择在涵盖更多功能的意义上是“更好的”。然而，由于 lambda 必须为正，因此没有“最佳”的 lambda 选择。 Lambda = 10^-3 应该让你通过足够多的例子来理解为什么大多数对主定理的处理都不能通过选择 lambda 来产生结果。