是否存在时间复杂度为O(n*(log n)^ 2)的算法？

Question

我知道heapsort的时间复杂度为O(n log n),但我真的不能想到一个具有O(n(log n)²)的算法.

Answer 1

构建一个非常容易.最明显的例子是:

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的拟线性时间复杂度.