Существует ли какой-либо алгоритм с временной сложностью O (n * (log n)^2)?

Question

Я знаю, что heapsort имеет временную сложность O (п § п), но я не могу думать алгоритма, который имеет один из O (N (журнал N)).

Answer 1

Это очень легко построить. Наиболее очевидный пример:

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

Для более полезным, например, вы можете использовать Master's theorem придумать бесконечное количество рекурсии, которые удовлетворяют вашим потребностям (любой k будет работать):

---

Если вы ищете настоящий алгоритм, то Shellsort имеет худший случай сложности O (n (log n)). То же самое для inplace mergesort.

P.S. причудливого названия для материала, который Вы ищете квазилинейна временную сложность при к = 2.

Answer 2

https://en.wikipedia.org/wiki/Dynamization имеет тенденцию к увеличению сложности на коэффициенте лога п, так что если вы п запросы о динамизированных версиях данных структура с базовым журналом затрат n, вы получите n log (n)^2

Answer 3

Классическим (и наиболее практичным) примером является stable_sort STL. Лог-квадратичный фактор возникает из-за того, что сама слияющая рекурсия является рекурсивной (что позволяет реализовать весь алгоритм на месте).