0
Я знаю, что heapsort имеет временную сложность O (п § п), но я не могу думать алгоритма, который имеет один из O (N (журнал N)).Существует ли какой-либо алгоритм с временной сложностью O (n * (log n)^2)?
A
ответ
6
Это очень легко построить. Наиболее очевидный пример:
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.
1
https://en.wikipedia.org/wiki/Dynamization имеет тенденцию к увеличению сложности на коэффициенте лога п, так что если вы п запросы о динамизированных версиях данных структура с базовым журналом затрат n, вы получите n log (n)^2
2
Классическим (и наиболее практичным) примером является stable_sort STL. Лог-квадратичный фактор возникает из-за того, что сама слияющая рекурсия является рекурсивной (что позволяет реализовать весь алгоритм на месте).
Ответ - это определенное да. Легко построить такой алгоритм. Если вы хотите найти тот, который уже используется для чего-то, это другое дело. Вы должны подумать о том, что означают цифры: 'n *' означает, что вам нужно что-то сделать для каждого элемента набора входных данных, 'log n' означает какую-то операцию разделения и захвата, а квадрат означает, что вам, вероятно, нужен еще один разрыв и побеждать на каждом шаге предыдущего. – biziclop
'O (n * log n)' является подмножеством 'O (n * (log n)^2)', поэтому каждый алгоритм с временной сложностью «O (n * log n)» также имеет временную сложность of O (n * (log n)^2) '. –