Master Theorem混淆与三种情况
Master Theorem confusion with the three cases
我知道当递归关系的形式为：
时，我们可以应用主定理来找到分而治之算法的 运行 时间
T(n) = a*T(n/b) + f(n)
我们知道以下内容：
a是算法划分原问题的子问题个数b 是太阳问题的大小，即 n/b- 最后..
f(n) 包括划分问题和组合子问题结果的成本。
现在我们接着找东西（我会回到术语"something"）
我们有 3 个案例要检查。
f(n) = O(n^log(b)a-ε)对于某些ε>0的情况；那么T(n)就是O(n*log(b)a)f(n) = O(n^log(b)a)的情况；那么T(n)就是O(n^log(b)a * log n).- 如果
n^log(b)a+ε = O(f(n)) 表示某个常量 ε > 0，如果 a*f(n/b) =< cf(n) 表示某个常量
c < 1和几乎所有n，然后T(n) = O(f(n))。
很好，我正在回忆这个词。我们如何使用一般示例（即使用变量而不是实际数字）来确定算法属于哪种情况？
例如。考虑以下因素：
T(n) = 8T(n/2) + n
所以 a = 8、b = 2 和 f(n) = n
那我将如何进行？我如何确定是哪种情况？而函数 f(n) = some big-Oh notation 这两个东西有什么可比性？
上面只是举个例子，给大家看一下我哪里没看懂，所以问题笼统。
谢谢
正如 CLRS 所建议的，基本思想是将 f(n) 与 n^log(b)a 进行比较，即 n 的幂次（log a 以 b 为底）。在您的假设示例中，我们有：
f(n) = nn^log(b)a = n^3，即 n 次方，因为您的循环会在每一步产生 8 个大小减半的问题。
因此，在这种情况下，n^log(b)a 更大 因为 n^3 总是 O(n)解决方案是：T(n) = θ(n^3).
显然，子问题的数量大大超过了您为每个子问题所做的工作（线性，f(n) = n）。因此，直觉告诉和主定理验证是 n^log(b)a 支配递归。
有一个微妙的技术细节，主定理说 f(n) 不仅应该小于 n^log(b)a O-wise，它应该小于 多项式.
我知道当递归关系的形式为：
时，我们可以应用主定理来找到分而治之算法的 运行 时间T(n) = a*T(n/b) + f(n)
我们知道以下内容：
a是算法划分原问题的子问题个数b是太阳问题的大小，即n/b- 最后..
f(n)包括划分问题和组合子问题结果的成本。
现在我们接着找东西（我会回到术语"something"） 我们有 3 个案例要检查。
f(n) = O(n^log(b)a-ε)对于某些ε>0的情况；那么T(n)就是O(n*log(b)a)f(n) = O(n^log(b)a)的情况；那么T(n)就是O(n^log(b)a * log n).- 如果
n^log(b)a+ε = O(f(n))表示某个常量ε > 0，如果a*f(n/b) =< cf(n)表示某个常量c < 1和几乎所有n，然后T(n) = O(f(n))。
很好，我正在回忆这个词。我们如何使用一般示例（即使用变量而不是实际数字）来确定算法属于哪种情况？
例如。考虑以下因素：
T(n) = 8T(n/2) + n
所以 a = 8、b = 2 和 f(n) = n
那我将如何进行？我如何确定是哪种情况？而函数 f(n) = some big-Oh notation 这两个东西有什么可比性？ 上面只是举个例子，给大家看一下我哪里没看懂，所以问题笼统。
谢谢
正如 CLRS 所建议的，基本思想是将 f(n) 与 n^log(b)a 进行比较，即 n 的幂次（log a 以 b 为底）。在您的假设示例中，我们有：
f(n) = nn^log(b)a = n^3，即 n 次方，因为您的循环会在每一步产生 8 个大小减半的问题。
因此，在这种情况下，n^log(b)a 更大 因为 n^3 总是 O(n)解决方案是：T(n) = θ(n^3).
显然，子问题的数量大大超过了您为每个子问题所做的工作（线性，f(n) = n）。因此，直觉告诉和主定理验证是 n^log(b)a 支配递归。
有一个微妙的技术细节，主定理说 f(n) 不仅应该小于 n^log(b)a O-wise，它应该小于 多项式.