Большой O анализ модифицированной сортировки слиянием (делим на √n массивов вместо 2)

Question

Я работаю над модифицированным алгоритмом сортировки слиянием, использующим аналогичную процедуру для объединения двух отсортированных массивов, но вместо этого хочу объединить √n отсортированных массивов √n размера.Он начнется с массива размера n, а затем рекурсивно разделится на √n подзадач, как указано выше.Используется следующий алгоритм:

1.) Divide array of n elements into  √n pieces
2.) Pass elements back into method for recursion
3.) Compare pieces from step 1
4.) Merge components together to form sorted array

Я вполне уверен, что это правильный алгоритм, но я не уверен, как найти время выполнения Big O.Любое руководство в правильном направлении очень ценится!

Answer 1

Ключевой момент - найти сложность шага слияния.Предполагая, что используется метод, аналогичный методу 2-way:

• Нахождение минимального элемента из всех массивов √n равно O(√n).
• .быть сделано для всех n элементов, которые будут объединены;возможные крайние случаи, когда некоторые из массивов истощаются, вносят в сложность только вычтенные O(√n).

Следовательно, сложность объединения составляет O(n√n).Расширение повторения:

Где (*) обозначает расширение условий T().Определение шаблона для m -го расширения:

• Коэффициент T -термина составляет n к степени суммы степеней от 1/2 до m.
• Аргумент T -термина равен 1/2 в степени m.
• Накопленные условия сумма n в степени 1 + степени 1/2 upдо m.

Запись приведенных выше правил в виде компактной серии:

• (*)используется стандартная формула для геометрических рядов.
• (**) отмечает, что при суммировании степеней n доминирует самая высокая степень (1/2).Предположим, что условие остановки является некоторой небольшой константой, будь то n = 1:

Обратите внимание, что с увеличением n значение 2^(1 - ...) срок исчезает.Таким образом, первый член ограничен сверху O(n), который омрачен вторым членом.

Сложность по времени сортировки слиянием на √n пути составляет, следовательно, O(n^1.5), чтохуже, чем O(n log n) сложность двусторонней сортировки слиянием.