Каково время работы алгоритма, объединяющего mergeSort и heapsort?

Question

Мне задали эту проблему, которая просит вычислить наихудшее время выполнения алгоритма, точно такого же, как mergeSort, но один из двух рекурсивных вызовов заменяется Heapsort.

Итак, я знаю, что деление по слиянию занимает постоянное время и что слияние равно O (n). Heapsort принимает O (nlogn). Вот что я придумал: T (n) = 2T (n / 2) + O ((n / 2) logn) + O (n). У меня есть некоторые сомнения по поводу части O ((n / 2) logn). Это n или n / 2? Я написал n / 2, потому что я делаю heapsort только на половине массива, но я не уверен, что это правильно

Answer 1

Давайте разберемся, каким должно быть отношение повторения в этом случае. Здесь мы

• разбиение массива пополам,
• рекурсивная сортировка одной половины (T (n / 2)),
• heapsorting одна половина (O (n log n)), а затем
• объединение двух половинок (O (n)).

Это дает нам это рекуррентное соотношение:

T (n) = T (n / 2) + O (n log n).

Почему это O (n log n), а не, скажем, O ((n / 2) log (n / 2))? Причина в том, что нотация big-O содержит постоянные множители, поэтому O (n log n) выражает ту же асимптотическую скорость роста, что и O ((n / 2) log (n / 2)). И почему нет коэффициента 2 на T (n / 2)? Это потому, что мы делаем только один рекурсивный вызов; помните, что другой вызов был заменен на heapsort.

Все, что осталось сделать сейчас, - это решить эту проблему. Это действительно помогает O (n log n), и я оставлю вам решать, как вы хотите это показать. Метод итерации является отличным вариантом здесь.

Answer 2

Вопрос спрашивает о времени выполнения, но стоит ли задавать вопрос о сложности времени?

Поскольку упоминается рекурсия, речь идет о сортировке слиянием сверху вниз (в отличие от сортировки слиянием снизу вверх).

С кодом, написанным так, как описано, поскольку сортировка кучи не является рекурсивной, рекурсия происходит только в одном из каждого подразделяемого массива. Сортировка кучи будет вызываться для сортировки подмассивов размера n / 2, n / 4, n / 8, n / 16, ..., и объединение не будет происходить, пока два подмассива размера 1 не станут результатом рекурсивное расщепление. В простом случае, когда размер массива равен степени 2, «сортировка слиянием» используется только для одного элемента, а остальные подмассивы размером {1, 2, 4, 8, ..., n / 8, n / 4, n / 2} сортируются по кучи, а затем объединяются.

Поскольку сортировка в куче медленнее, чем сортировка слиянием, время выполнения будет больше, но сложность времени остается на уровне O (n log (n)), поскольку постоянные или более низкие коэффициенты терения игнорируются для сложности времени.