algorithm - 硕士定理 f(n)=log n

Question

对于硕士定理T(n) = a*T(n/b) + f(n)，我使用了 3 种情况：

1. 如果a*f(n/b) = c*f(n)对于某个常数c > 1那么T(n) = (n^log(b) a)
2. 如果a*f(n/b) = f(n)那时T(n) = (f(n) log(b) n)
3. 如果a*f(n/b) = c*f(n)对于某个常数c < 1那么T(n) = (f(n))

但是当f(n) = log n或时n*log n， 的值c取决于 n 的值。如何使用大师定理解决递归函数？

Answer 1

通常，f(n) 必须是多项式才能应用主定理 - 它不适用于所有函数。然而，主定理有一个有限的“第四种情况”，它允许它应用于多对数函数。

如果f(n) = O(n ^{log _b a} log ^k n)，则T(n) = O(n ^{log _b a} log ^k+1 n)。

换句话说，假设你有 T(n) = 2T (n/2) + n log n。f(n) 不是多项式，而是 f(n)=n log n，并且 k = 1。因此，T(n) = O(n log ² n)

有关更多信息，请参阅此讲义：http: //cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-HandoutNoNotes.pdf

Answer 2

您可能会从有关 Master theorem 的 Wikipedia 文章中发现这三个案例更有用：

• 案例 1：f(n) = Θ(n ^c )，其中 c < log _b a
• 情况 2：f(n) = Θ(n ^c log ^k n)，其中 c = log _b a
• 案例 3：f(n) = Θ(n ^c )，其中 c > log _b a

现在不再直接依赖于 n 的选择——重要的是 f 的长期增长率以及它与常数 a 和 b 的关系。如果没有看到您要解决的特定重复发生的更多细节，我无法提供任何更具体的建议。

希望这可以帮助！

Answer 3

当 f(n)=log(n) 时，Master 定理不适用。您应该使用更广义的定理Akra–Bazzi。

结果，T(n)=O(n)。

来源。

找到该结果的更具体证明的另一种方法是寻找“最优排序矩阵搜索”算法的计算复杂性的证明。