有没有时间复杂度为O（n *（log n）^ 2）的算法？(Is there any algorithm with the time complexity of O(n*(log n)^2)?)

有没有时间复杂度为O（n *（log n）^ 2）的算法？(Is there any algorithm with the time complexity of O(n*(log n)^2)?)

我知道heapsort的时间复杂度为O（n log n） ，但我真的不能想到一个具有O（n（log n） 2 ）的算法 。

I know that heapsort has a time complexity of O(n log n), but I can't really think of an algorithm that has one of O(n (log n)2).

最满意答案

构建一个非常容易。 最明显的例子是：

for i in xrange(n * int(log(n, 2) ** 2)): // do something O(1)

有关更有用的示例，您可以使用Master's定理来提供满足您需求的无限量递归（任何k都可以工作）：

---

如果您正在寻找一个真正的算法，那么Shellsort的最坏情况复杂度为O（n（log n） ² ） 。 对于inplace mergesort也是如此 。

PS你正在寻找的东西的奇特名称是k = 2的拟线性时间复杂度。

It is super easy to construct one. The most obvious example is:

for i in xrange(n * int(log(n, 2) ** 2)): // do something O(1)

For a more helpful example you can use Master's theorem to come up with infinite amount of recursions that satisfy your needs (any k will work):

---

If you are looking for a real algorithm, then Shellsort has a worst case complexity of O(n (log n)²). The same for an inplace mergesort.

P.S. a fancy name for the stuff you are looking for is quasilinear time complexity with k = 2.