大师定理-最好的情况下大哦?

我对算法和时间复杂性非常陌生,正在读一本书。根据我对Big-Oh函数的了解,对于任何f(n)都不是唯一的,取决于常数c和n0。我的第一个疑问是Master定理是否给出了Big Oh函数的最佳情况。我的第二个疑问-可能很愚蠢-在解决问题1和2之后,我试图继续前进并验证答案,却感到困惑。

现在我的尝试如下: 1)cn2≥3T(n / 2)+n2⇒kn2≥T(n / 2) ⇒k''(n / 2)2≥T(n / 2),因此与O(n2)一致。 为什么对概率2来说不一样,即为什么不是O(n2)而是O(n2logn)?我想它背后有一些数学运算,我想知道(如果我到目前为止有足够的背景知识)。

评论
  • bby
    bby 回复

    Depending on your conditions, Masters theorem gives either the worst-case time complexity Big-O or a tight bound Big-Theta

    Now the actual proof of Master's theorem involves drawing the recurrence tree and some approximations using the geometric series progression. Here's a link to a pdf containing the process.