高手定理——Best case大哦？

Question

我对算法和时间复杂度非常陌生，正在阅读一本书。根据我对 Big-Oh 函数的了解，它对于任何 f(n) 都不是唯一的，取决于常量 c 和 n₀。我的第一个疑问是 Master theorem 是否给出了最佳情况下的 Big Oh 函数。我的第二个疑问 - 可能很愚蠢 - 在尝试向后进行并验证答案时解决问题 1 和 2 后我感到困惑。

现在我的尝试如下-
1)cn²≥3T(n/2) + n²
⇒kn²≥T(n/2)
⇒k^''(n/2)²≥T(n/2)
所以和O(n²).
一致 为什么概率 2 不一样，即为什么不是 O(n²) 而是 O(n²logn)?我猜它背后有一些数学原理，我想知道它（如果我到现在为止有足够的背景知识）。

Answer 1

根据您的条件，Masters 定理给出了最坏情况下的时间复杂度 Big-O 或紧界 Big-Theta

现在马斯特定理的实际证明包括绘制递归树和一些使用几何级数的近似值。这是包含该过程的 pdf 文件的 a link。