Изменения

Перейти к: навигация, поиск

Многопоточная сортировка слиянием

1 байт убрано, 17:22, 7 июня 2014
→‎Оценка при фиксированном числе потоков
==Оценка при фиксированном числе потоков==
ОчевидноПонятно, что при отсутствии возможности запуска неограниченного количества независимых потоков, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоков. Обозначим такое количество как <tex dpi="120">N_{ind}</tex>. Допустим, <tex dpi="120">n</tex> много больше <tex dpi="120">N_{ind}</tex>, что в общем случае верно для ПК и достаточно больших объемов данных. Оценим приведенные выше алгоритмы с учетом наложенных ограничений и допущений:<br>
::[[#.D0.A1.D0.BE.D1.80.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.BA.D0.B0_.D1.81_.D0.BE.D0.B4.D0.BD.D0.BE.D0.BF.D0.BE.D1.82.D0.BE.D1.87.D0.BD.D1.8B.D0.BC_.D1.81.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5.D0.BC|Сортировка с однопоточным слиянием]] будет иметь асимптотику <tex dpi="135">\Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}} + n) = \Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})</tex>:
::::<tex dpi="135">\Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})</tex> операций нужно на последовательную сортировку массива длиной <tex dpi="135">\frac{n}{N_{ind}}</tex>.
::::<tex dpi="135">T_{\mathrm {mergeSort}}'(\frac{n}{N_{ind}}) = 2T_{\mathrm {mergeSort}}'(\frac{n}{2N_{ind}}) + \Theta(\frac{n}{N_{ind}})^{\log_{\frac{4}{3}}2} = \Theta(\frac{n}{N_{ind}})^{\log_{\frac{4}{3}}2}</tex>
Очевидно, что нижняя оценка алгоритма сортировки с многопоточным слиянием выше. Таким образом, при приведенных выше допущениях алгоритм сортировки с однопоточным слиянием эффективнее и его асимптотика составляет <tex dpi="120">\Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})</tex>.
 
==Источники информации==
*Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. {{---}} Introduction to Algorithms, Third Edition
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/37910»

Навигация