algorithm - t(n)=2t(n/2)+n^0.5/logn可以用masters定理解决吗？

Question

我和我的朋友吵架，我们昨天考试了。我说不能，他说这是案例 1。可能他是对的，但我似乎不明白为什么。提前致谢。

Answer 1

对于任何大于 1 的 n 值，n^(0.5/log n) 的常数值为 exp(0.5)。这很容易证明：

   x = n^(0.5/log n)
   log(x) = (log n) * 0.5 / (log n) = 0.5
=> x = exp(0.5) = 1.64872...

因此，表达式的第二项可以被视为常数。使用恒定的第二项，您的公式等效于t(n) = 2t(n/2) + 1，其复杂度为 O(n)。

是的，你的朋友是对的。这对应于案例 1，其中 f(n) ∈ O(n^c) 中 c 的值为零。