Время выполнения сортировки слиянием

Question

Я знаю, что время выполнения сортировки слиянием равно O (n * lg (n)), и что сортировка слиянием является сортировкой сравнения, что также означает, что для сортировки списка требуется Ω (n logn) в худшем случае.

Могу ли я поэтому заключить, что время выполнения сортировки слиянием - тета (n * lg n)?

Answer 1

Если что-то O(X) и Omega(X), это означает, что это Theta(X). И log_b1(...) - это то же самое, что log_b2(...) умноженная на коэффициент преобразования.

То, что вы сказали, было (переведено):

Я знаю, что время выполнения сортировки слиянием в худшем случае не хуже, чем n log(n). [Вы пришли к такому выводу по математике.] Но для сравнения в худшем случае требуется n log(n).

Таким образом, имеет смысл, что наихудшее поведение сортировки слиянием точно n log(n).

Это, конечно, с неявным предположением, что у вас нет информации о вашей последовательности.

edit: Вы также можете доказать это из первых принципов. Следует отметить, что вы можете объединять два отсортированных массива в линейное время тета (N1 + N2), сохраняя их объединенными (сканируя их параллельно). (Подразделение массива, независимо от того, какую последовательность вы получите, всегда будет занимать время Theta (log (N)), которое мало, поэтому мы просто игнорируем это. Теперь отметим, что каждый элемент должен быть объединен Theta (log (N)) раз (глубина дерева, если вы его вытягиваете). Таким образом, Тета (N log (N)).

Answer 2

Да, сложность сортировки слиянием - тета (n * lgn).И есть еще один способ убедиться в этом.

Известно, что сортировка слиянием является алгоритмом «разделяй и властвуй».Сначала он делит массив размером n на две n / 2 части, затем рекурсивно обрабатывает их обе и, наконец, объединяет результат в отсортированный массив.

Предположим, что время сортировки слияния равно T (n).Затем:
- операция деления является постоянной тета (1) - вам просто нужно найти средний элемент массива, разделив его длину на 2
- рекурсия для каждой части массива занимает T (n /2) время, которое составляет 2T (n / 2) для них обоих
- известно, что операция объединения имеет тэта (n) сложность

Итак, в итоге вы получаете следующее рекуррентное уравнение для T (n)=:
тета (1) |если n == 1
2 * T (n / 2) + theta (n) |если n> 1

Решая это уравнение, вы получите T (n) = theta (nlgn);

Более подробно вы можете обратиться к книге "Введение в алгоритмы" Кормана.