如何判断一个递归方程属于主定理的情形一还是情形二
How to tell whether a recurrence equation belongs to case one or two of the master theorem
如果 O(f(x)) 总是也是 Theta(f(x)) 因为 theta 是 O 而 omega 在同一时间。如何判断递归方程是否符合主定理的情况 1 或情况 2。
例如，()=4(/2)+²sqrt();
a=4,b=2 所以 logb(a)= 2.
这里 f(n) = O(n^2) 是情况 1。
但是 f(n) = Theta(n^2) 也是情况 2。
那我应该选择哪一个，为什么？
您的含义似乎发生了转变：Theta(f(x)) 中的成员身份始终意味着在 O(f(x)) 中，而不是相反。
主定理的情形 1 和情形 2（如 CLRS 的 算法简介 或 Wikipedia 中所见）是互斥的。
情况 1 适用于 f(n) 在多项式上严格小于 n^c、c > 0 的多项式（即渐近地小于 n^c、c > 0）的情况 n ^ logb(a)。
案例 2 在几个地方以不同的方式呈现，但仅适用于 f(n) 和 n ^ logb(a) 渐近相等的情况，直至可能的 多对数 n ^ logb(a).
的乘数
在您的情况下，f(n) 在 O(n^2) 中 而不是 ，甚至达到多对数因子。 f(n) 在 O(n^2.5) 中（因为它在 Theta(n^2.5) 中）。所以情况 2 不适用；情况 1 也没有。重要的是，在 CLRS 或维基百科的定义中，您可以 永远不会 在这三种情况中的任何一种之间有重叠。在你的例子中，情况3恰好适用，所以需要更多的分析和规律性条件来证明复杂性。
要准确知道 f(n) 是 O(n^logb(a)) 还是 Theta(n^logb(a))，一个简单的方法是计算当 n 趋于无穷大时 f(n)/n^logb(a) 的极限。
如果限制是 infinity 那么 f(n) 就是 O(n^logb(a))
如果限制是 finite 数字，则 f(n) 是 Theta(n^logb(a)).
如果 O(f(x)) 总是也是 Theta(f(x)) 因为 theta 是 O 而 omega 在同一时间。如何判断递归方程是否符合主定理的情况 1 或情况 2。
例如，()=4(/2)+²sqrt();
a=4,b=2 所以 logb(a)= 2.
这里 f(n) = O(n^2) 是情况 1。
但是 f(n) = Theta(n^2) 也是情况 2。
那我应该选择哪一个，为什么？
您的含义似乎发生了转变：Theta(f(x)) 中的成员身份始终意味着在 O(f(x)) 中，而不是相反。
主定理的情形 1 和情形 2（如 CLRS 的 算法简介 或 Wikipedia 中所见）是互斥的。
情况 1 适用于 f(n) 在多项式上严格小于 n^c、c > 0 的多项式（即渐近地小于 n^c、c > 0）的情况 n ^ logb(a)。
案例 2 在几个地方以不同的方式呈现，但仅适用于 f(n) 和 n ^ logb(a) 渐近相等的情况，直至可能的 多对数 n ^ logb(a).
在您的情况下，f(n) 在 O(n^2) 中 而不是 ，甚至达到多对数因子。 f(n) 在 O(n^2.5) 中（因为它在 Theta(n^2.5) 中）。所以情况 2 不适用；情况 1 也没有。重要的是，在 CLRS 或维基百科的定义中，您可以 永远不会 在这三种情况中的任何一种之间有重叠。在你的例子中，情况3恰好适用，所以需要更多的分析和规律性条件来证明复杂性。
要准确知道 f(n) 是 O(n^logb(a)) 还是 Theta(n^logb(a))，一个简单的方法是计算当 n 趋于无穷大时 f(n)/n^logb(a) 的极限。
如果限制是 infinity 那么 f(n) 就是 O(n^logb(a))
如果限制是 finite 数字，则 f(n) 是 Theta(n^logb(a)).