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)一致: