Модифицированная среда выполнения MergeSort

Question

Помогите мне понять время выполнения модифицированного алгоритма MergeSort. В classi c MergeSort, когда входной массив делится на две части и рекурсивно сортируется, время выполнения составляет: nlogn

Каким будет время выполнения алгоритма MergeSort, если разделить входной массив на три части (не половина), рекурсивно сортируйте каждую треть и, наконец, объединяйте результаты, используя подпрограмму объединения с тремя аргументами.

1. n
2. nlogn
3. n (журнал n) ^ 2
4. n ^ 2logn

Answer 1

В алгоритме classi c Merge Sort имеется приблизительно n * log2(n) сравнений и столько же операций копирования элементов, следовательно, временная сложность O (n.log (n)) из-за мультипликативных констант являются неявными.

Если вместо разделения массива на 2 части, вы разбиваете на 3 части, выполняете одну и ту же сортировку рекурсивно для частей и объединяете 3 отсортированных среза в одну, количество сравнений увеличивается примерно до 2 * n * log3(n), а количество копий элементов уменьшено до n * log3(n), но оба они пропорциональны n * log(n). С учетом мультипликативных констант вы все равно получаете временную сложность O (n.log (n)) .