中位数算法运行时间的中位数不应该是O(nlogn)吗？

Question

由于我们以递归的方式划分子数组，我认为算法的时间复杂度应该是O(nlogn)。

例如，数组大小为1000，假设我们将数组分成大小为5的子数组，那么第一个子数组的数量将是1000/5=200。在找到这些子数组的中位数之后对于一个数组需要0(1)，我们将递归地找到中位数的中位数，新的子数组的数量将是200/5=40我们也将找到这些中位数，直到子数组的数量小于5。总运行时间将是这样的:

T(100)=200*O(1)+40*O(1)+8*O(1)+3*O(1)

和

T(n)=n/5*O(1)+n/25*O(1)+n/125*O(1)+n/625*O(1)+...=O(n)+O(n)O(n)+O(n)+O(n)+...

O(n)的个数将是ceil(log5(n))。因此:

T(n)=ceil(log5(n))*O(n)=O(nlogn)

为什么这是错误的?

Answer 1

你忘了

n/2 + n/4 + n/8 + ... 1 = n - 1.

---

教训是

O(f(n)) + O(f(n)) + ... O(f(n)) = O(n f(n))

与n项不一定成立。