使用主定理解决分而治之的递归问题
Solving recurrence of divide and conquer using master theorem
T(n) = 3T(n/2) + c T(1)=0 可以用主定理求解吗？如果是的话，我现在正在努力理解主定理，谁能告诉我它属于哪种情况以及为什么。
主定理有不同的可能方法。我喜欢 Cormen 等人提出的那个。在他们的书 Introduction to Algorithms.
- 如果 f(n) = O(n^(logb(a-e))) 对于某个常数 e>0，则 T(n) = Θ(n^(logb(a)))
- 如果 f(n) = Θ(n^(logb(a)))，则 T(n) = Θ(n^( logb(a)) .lg n)
- 如果 f(n) = Ω(n^(logb(a+e))) 对于某个常数 e>0，并且如果 a.f( n/b) < c.f(n) 对于
一些常数 c<1 和所有足够大的 n，然后 T(n) = Θ(f(n))
现在我们需要比较 f(n) 和 n^(logb(a)).
- 如果 f(n) 多项式 小于 n^(logb(a)),它
属于第一种情况
- if n^(logb(a)) 多项式 小于 f(n)，它
属于第三种情况
- if f(n) 和 n^(logb(a))尺寸相同，属于
第二种情况
请注意，这三种情况并未涵盖 f(n) 的所有可能性。有
当 f(n) 小于 n^(logb(a)) 但不是多项式更小时，情况 1 和情况 2 之间的差距。同样，当 f(n) 较大时，情况 2 和情况 3 之间存在差距
比 n^(logb(a)) 但不是多项式更大。如果函数 f(n) 属于其中之一
间隙，或者如果情况 3 中的规律性条件不成立，则不能使用 master
解决复现的方法。
现在解决问题中的重复...
a=3, b=2, f(n) = c = n^0
所以我们有 n^(log2(3)) ≈ n^(1.58) 多项式大于 n^0，属于第一种情况。那么时间复杂度就是 T(n) = Θ(n^(logb(a))) --> T(n) = Θ(n^1.58)
T(n) = 3T(n/2) + c T(1)=0 可以用主定理求解吗？如果是的话，我现在正在努力理解主定理，谁能告诉我它属于哪种情况以及为什么。
主定理有不同的可能方法。我喜欢 Cormen 等人提出的那个。在他们的书 Introduction to Algorithms.
- 如果 f(n) = O(n^(logb(a-e))) 对于某个常数 e>0，则 T(n) = Θ(n^(logb(a)))
- 如果 f(n) = Θ(n^(logb(a)))，则 T(n) = Θ(n^( logb(a)) .lg n)
- 如果 f(n) = Ω(n^(logb(a+e))) 对于某个常数 e>0，并且如果 a.f( n/b) < c.f(n) 对于 一些常数 c<1 和所有足够大的 n，然后 T(n) = Θ(f(n))
现在我们需要比较 f(n) 和 n^(logb(a)).
- 如果 f(n) 多项式 小于 n^(logb(a)),它 属于第一种情况
- if n^(logb(a)) 多项式 小于 f(n)，它 属于第三种情况
- if f(n) 和 n^(logb(a))尺寸相同，属于 第二种情况
请注意，这三种情况并未涵盖 f(n) 的所有可能性。有 当 f(n) 小于 n^(logb(a)) 但不是多项式更小时，情况 1 和情况 2 之间的差距。同样，当 f(n) 较大时，情况 2 和情况 3 之间存在差距 比 n^(logb(a)) 但不是多项式更大。如果函数 f(n) 属于其中之一 间隙，或者如果情况 3 中的规律性条件不成立，则不能使用 master 解决复现的方法。
现在解决问题中的重复...
a=3, b=2, f(n) = c = n^0
所以我们有 n^(log2(3)) ≈ n^(1.58) 多项式大于 n^0，属于第一种情况。那么时间复杂度就是 T(n) = Θ(n^(logb(a))) --> T(n) = Θ(n^1.58)