g(n) 复杂度为 O(n^2) 的算法的时间复杂度

Question

我刚刚了解了各种排序方法的时间复杂度。（例如合并排序，快速排序）但是我在这个领域仍然是初学者。我知道如果 g(n) 的复杂度为 O(n)，则此方法的整个时间复杂度将为 n logn。但是如果 g(n) is O(n^2)?

的复杂度呢？

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

Answer 1

时间复杂度递推关系为

– 其中 G(n) 是 g(n) 的时间复杂度。解决这个问题的方法例如O(n^2):

扩展（删除 O(...) 直到结束）：

– m 扩展后。第二项包含一个几何级数，其中converges to 2，所以可以忽略不计。应用停止条件 n = 1:
Master Theorem。例如：

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

Time complexity of algorithm with g(n) complexity of O(n^2)