algorithm - 求主定理的 lambda

Question

假设我有一个案例

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

那应该是第一种情况，因为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 来产生结果。

Answer 2

f(n)=logn

Epsilon 可以是 1/4，因为

n ^{(log _b a-epsilon)} =n ^{(log ₄ 2-1/4)} =n ^(1/2-1/4) =n ^(1/4)。

f(n)=O(n ^(1/4) )。

因此，根据主定理 T(n)=Θ(n ^{log _b a} )=Θ(n ^(1/2) ) 的情况 1。