算法时间复杂度与g(n)的O(n^2)复杂度是多少？

Question

我刚学习了各种排序方法的时间复杂度（例如归并排序，快速排序）。然而，我还是这个领域的初学者。我知道如果g(n)的复杂度为O(n)，则该方法的整体时间复杂度将为nlogn。但是，如果g(n)的复杂度为O(n^2)呢？

void f(n) { 
    if (n <= 1) return;
    else { 
      g(n); 
      f(n/2);
      f(n/2);
    }
}

- Jia Zheng Lua

Answer 1

时间复杂度的递归关系是：

这里的 G(n) 是 g(n) 的时间复杂度。解决 O(n^2) 的方法如下：

1. 展开式（省略 O(...) 直到结尾）：

   

   – 经过 m 次展开。第二项包含一个等比数列，其收敛于 2，因此可以被视为常数。应用停止条件 n = 1：

   

2. 主定理。以以下例子为例：

   

   – 这意味着应用情况 3。因此结果与（1）一致：

   

- meowgoesthedog

---

通用公式适用于所有类型的递归吗？是否有其他公式可以帮助我找到其他方法的时间复杂度。非常感谢您的帮助。 - Jia Zheng Lua

@JiaZhengLua 大师定理公式仅适用于具有一个递归术语的递归式，其中参数被除以一个因子，例如：i) T(n/2)，但不适用于例如 ii) T(n/2) + T(n/3) 或 iii) T(n-1) 这样的情况。对于类似 ii) 的情况，可以使用Akra-Bazzi 方法。 - meowgoesthedog