有没有时间复杂度为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).
构建一个超级容易。最明显的例子是：
for i in xrange(n * int(log(n, 2) ** 2)):
// do something O(1)
对于更有用的示例，您可以使用 Master's theorem 来提出满足您需要的无限数量的递归（任何 k 都可以）：
如果你正在寻找一个真正的算法，那么Shellsort has a worst case complexity of O(n (log n)2). The same for an inplace mergesort。
P.S. 你正在寻找的东西的一个奇特的名字是 k = 2 的拟线性时间复杂度。
https://en.wikipedia.org/wiki/Dynamization 往往会增加 log n 倍的复杂性，因此如果您对具有基础成本 log n 的数据结构的动态版本进行 n 查询，您将得到 n log(n) ^2
一个经典的（也是最实用的）例子是STL的stable_sort。对数二次因子是由于合并阶段本身是递归的（这允许整个算法就地运行）。
我知道 heapsort 的时间复杂度为 O(n log n)，但我真的想不出一种算法具有 O(n (log n)2).
构建一个超级容易。最明显的例子是：
for i in xrange(n * int(log(n, 2) ** 2)):
// do something O(1)
对于更有用的示例，您可以使用 Master's theorem 来提出满足您需要的无限数量的递归（任何 k 都可以）：
如果你正在寻找一个真正的算法，那么Shellsort has a worst case complexity of O(n (log n)2). The same for an inplace mergesort。
P.S. 你正在寻找的东西的一个奇特的名字是 k = 2 的拟线性时间复杂度。
https://en.wikipedia.org/wiki/Dynamization 往往会增加 log n 倍的复杂性，因此如果您对具有基础成本 log n 的数据结构的动态版本进行 n 查询，您将得到 n log(n) ^2
一个经典的（也是最实用的）例子是STL的stable_sort。对数二次因子是由于合并阶段本身是递归的（这允许整个算法就地运行）。