我刚刚了解了各种排序方法的时间复杂度。 (例如合并排序,快速排序)但是我仍然是这个领域的初学者。我知道如果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);
}
}
时间复杂度的递归关系是
- G(n)
是g(n)
的时间复杂性。解决此问题的方法,例如O(n^2)
:
O(...)
放到最后):
- 在m
扩张之后。第二项包含converges to 2的几何系列,因此它可以作为常数忽略。应用停止条件n = 1
: