为什么 Master 定理的时间复杂度与其他递推关系求解方法不同？
Why does the time complexity of the Master theorem differ in comparison to other recurrence relation solving methods?
考虑递推关系T(N) = 2T(n-1/2) + n。根据大定理第二种情况，我们可以得到时间复杂度为Θ(nlog(n))，同时利用代入法（+归纳法）也可以得到O(nlog(n)) ]，即我们可以证明 T(N) <= cnlog(n) 对于 c>1 和 n>1。为什么会有所不同，这有关系吗？谢谢！
大定理确实给出了 Θ(n log n) 的界限，这意味着它说运行时间是 O(n log n) 和 Ω(n log n)。从这个意义上说，它为您提供了使用替换方法证明的内容以及匹配的下限。当然，您也可以使用代入法和归纳法证明匹配下界，因此从这个意义上说，主定理不会给您任何您以前无法通过代入法和归纳法证明的东西。事实上，证明主定理的典型方法基本上是找到 substitution/induction 可以得出的一般形式，然后计算一次以证明一般情况。
考虑递推关系T(N) = 2T(n-1/2) + n。根据大定理第二种情况，我们可以得到时间复杂度为Θ(nlog(n))，同时利用代入法（+归纳法）也可以得到O(nlog(n)) ]，即我们可以证明 T(N) <= cnlog(n) 对于 c>1 和 n>1。为什么会有所不同，这有关系吗？谢谢！
大定理确实给出了 Θ(n log n) 的界限，这意味着它说运行时间是 O(n log n) 和 Ω(n log n)。从这个意义上说，它为您提供了使用替换方法证明的内容以及匹配的下限。当然，您也可以使用代入法和归纳法证明匹配下界，因此从这个意义上说，主定理不会给您任何您以前无法通过代入法和归纳法证明的东西。事实上，证明主定理的典型方法基本上是找到 substitution/induction 可以得出的一般形式，然后计算一次以证明一般情况。