2016-06-22 4 views
0

Я знаю, что heapsort имеет временную сложность O (п § п), но я не могу думать алгоритма, который имеет один из O (N (журнал N)).Существует ли какой-либо алгоритм с временной сложностью O (n * (log n)^2)?

+3

Ответ - это определенное да. Легко построить такой алгоритм. Если вы хотите найти тот, который уже используется для чего-то, это другое дело. Вы должны подумать о том, что означают цифры: 'n *' означает, что вам нужно что-то сделать для каждого элемента набора входных данных, 'log n' означает какую-то операцию разделения и захвата, а квадрат означает, что вам, вероятно, нужен еще один разрыв и побеждать на каждом шаге предыдущего. – biziclop

+3

'O (n * log n)' является подмножеством 'O (n * (log n)^2)', поэтому каждый алгоритм с временной сложностью «O (n * log n)» также имеет временную сложность of O (n * (log n)^2) '. –

ответ

6

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

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

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

enter image description here


Если вы ищете настоящий алгоритм, то 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. Лог-квадратичный фактор возникает из-за того, что сама слияющая рекурсия является рекурсивной (что позволяет реализовать весь алгоритм на месте).

 Смежные вопросы

  • Нет связанных вопросов^_^