master-theorem - 带logn的主定理

Question

这里有一个问题。

我真的很困惑c等于0.5部分。其实总的来说我很困惑怎么logn会变成n^(0.5)。难道我不能让c等于100which 意味着100 < d使用不同的情况吗？我在这里想念什么？

Answer 1

您当然可以设置c = 100为n^c的（非常非常）粗略的渐近上限log(n)，但这会给您的运行时间带来可怕且绝对无用的估计T(n)。

它告诉你的是：每个多项式函数n^c的增长速度都比对数快，不管它有多小c，只要它保持正数。你可以采取c=0.0000000000001，一开始它看起来会变得非常小，但在某些时候它会变得比它更大，log(n)并且比它更快地发散到无穷大log(n)。因此，为了摆脱该n^2 log(n)术语并能够应用主定理的仅多项式版本，您可以将对数项设置为增长足够慢（但仍比 快log(n)）的值。在这个例子中，n^cwithc=0.5就足够了，但你也可以使用c=10^{-10000}“just to make sure”。

然后你应用 Master 定理，并为你的T(n).