поиск и минимизация анализа времени выполнения алгоритма сортировки слиянием

Question

допустим, у меня есть массив размером n, я хочу разделить его на k новых массивов размером n / k .- какое время выполнения этого шага может быть? **** Я подумал так как, когда мы разделяем массив на 2, мы смотрим на него как 2 ^ x = n => x = log N => O (log n), тогда он работает также и здесь: k ^ (n / k) = n => n / k = log N ****, но что дальше?

Теперь я запускаю алгоритм пузырьковой сортировки для каждого из k массивов-O (n ^ 2) и использую алгоритм слияния для всех k массивов, чтобы создать отсортированный массив размера n-скажем, сложность объединения O (кН).

Кроме того, я не хочу найти K, чтобы я мог минимизировать время выполнения алгоритма, как я могу это сделать? Я подумал, что если взять производную функции времени выполнения и найти ее минимум, то это правильный путь.

Answer 1

Традиционно мы используем сортировку слиянием для внешних алгоритмов сортировки, и в ответе на этот вопрос доминирует один факт. Для сортировки слиянием требуется потоковая передача данных из нескольких файлов и запись в один. Узкое место в потоке, а не в процессоре. Если вы пытаетесь выполнить потоковую передачу из слишком большого количества мест на диске одновременно, диск выходит из строя и начинает выполнять произвольный поиск. Ваша пропускная способность при случайном поиске - отстой.

Правильный ответ на вашем оборудовании будет отличаться (особенно если вы используете SSD-диски), но традиционная сортировка Unix остановилась на 16 путях слияния в качестве разумного значения по умолчанию.

Answer 2

Сортировка слиянием разбивает массив на последовательно меньшие куски, пока не дойдет до группы из 2-х элементных подмассивов. Затем он начинает применять алгоритм слияния к последовательно большим подмассивам.

Представьте, что у вас есть массив из 16 элементов. Сортировка слиянием выполняет слияние следующим образом:

8 merges of two 1-item subarrays
4 merges of two 2-item subarrays
2 merges of two 4-item subarrays
1 merge of two 8-item subarrays

Существует четыре (log ₂ (16)) прохода, и на каждом проходе проверяется каждый предмет. Каждый проход O (n). Таким образом, время выполнения этой сортировки слияния равно O (n * log ₂ (n)).

Теперь представьте, что у вас есть массив с 81 элементом, и вы хотите объединить его, используя сортировку с 3-сторонним слиянием. Теперь у вас есть следующая последовательность слияний:

27 merges of three 1-item subarrays (gives 27 3-item subarrays)
 9 merges of three 3-item subarrays (gives 9 9-item subarrays)
 3 merges of three 9-item subarrays (gives 3 27-item subarrays)
 1 merge of three 27-item subarrays

Существует четыре (log ₃ (81)) прохода. Каждое объединение - это O (m * log ₂ (k)), где m - общее количество элементов, которые должны быть объединены, а k - количество списков. Таким образом, первый проход имеет 27 слияний, которые выполняют 3 * log ₂ (3) сравнения. Следующий проход имеет 9 слияний, которые выполняют 9 * log ₂ (3) сравнения и т. Д. В итоге получается, что общее слияние составляет O (n * log ₃ (n) * log _{2 * 1 026 * (3)) * * тысяча двадцать-семь Вы можете видеть, что трехсторонняя сортировка слиянием позволяет делать меньше проходов (для трехсторонней сортировки из 16 элементов потребуется всего три прохода), но каждый проход немного дороже. Что вы должны определить, если:}

n * log _k (n) * log ₂ (k) 2 (n)

Где k - количество подмассивов, на которые вы хотите разбить массив. Я позволю тебе сделать эту математику.

Вы должны быть осторожны, потому что асимптотический анализ не учитывает реальных эффектов. Например, двухстороннее слияние невероятно просто. Когда вы переходите к k-way слиянию, где k> 2, вы в конечном итоге вынуждены использовать кучу или другую структуру данных очереди приоритетов, которая имеет довольно много накладных расходов. Таким образом, даже если приведенная выше математика говорит вам, что сортировка с 3-сторонним слиянием должна быть быстрее, вам нужно сравнить ее со стандартным 2-сторонним слиянием.

Обновление

Ты прав. Если вы упростите уравнение, вы в итоге получите те же уравнения. Таким образом, вычислительная сложность одинакова независимо от значения k.

Это имеет смысл, потому что если k = x, то вы получите сортировку кучи.

Итак, вам нужно определить, есть ли точка, где накладные расходы на слияние, которые увеличиваются с увеличением k, компенсируются уменьшением числа проходов. Возможно, вам придется определить это эмпирически.