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

问题描述 投票:2回答:1

我刚刚了解了各种排序方法的时间复杂度。 (例如合并排序,快速排序)但是我仍然是这个领域的初学者。我知道如果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);
    }
}
time complexity-theory mergesort
1个回答
0
投票

时间复杂度的递归关系是

enter image description here

- G(n)g(n)的时间复杂性。解决此问题的方法,例如O(n^2)

  1. 扩张(将O(...)放到最后): enter image description here - 在m扩张之后。第二项包含converges to 2的几何系列,因此它可以作为常数忽略。应用停止条件n = 1enter image description here
  2. Master Theorem。例如: enter image description here - 这意味着案例3适用。因此结果与(1)一致: enter image description here
© www.soinside.com 2019 - 2024. All rights reserved.