Чему будет равна сложность этого алгоритма?

Question

[bondle]

Код, который внутри цикла, вызывает функцию сортировки со сложностью O(n log n):

for item in N:
   sort(item)
   ...

С одной стороны кажется, что сложность N, но каждую итерацию мы вызываем n log n, значит это O(n^2 log n)? Какова будет его сложность?

Answer 1

[Wataru]

Зависит от размеров item. Если они там каждый O(N) размера, то ваша догадка правильная: O(n^2 log n).

Если же все item суммарно не превосходят N, то ответ O(N log N). Потому что если их размеры a_i, то у вас сумма ai log ai. log(ai) можно сверху ограничить log(N) и вынести за скобки и потом заменить сумму в скобках на N.

Comments

[Lynn «Кофеман»]

Единственное верная оценка это O(N * L * log L), где L это длина строки.

А дальше в зависимости от соотношения N и L можно эту оценку как-то упрощать и переоценивать. Может это O(N) если на самом деле L ограничено константой. Или наоборот O(L * log L), если N константа и т. п., но нам для такой оценки не хватает данных.