97
правок
Изменения
Нет описания правки
===Реализация===
Очевидно, что при отсутствии возможности запуска неограниченного количества независимых потоков, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоков. Обозначим такое количество как <tex>N_{ind}</tex>. Допустим, <tex>n</tex> много больше <tex>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>\Theta(\frac{n}{N_{ind}}\log(\frac{n}{N_{ind}}) + n) = \Theta(\frac{n}{N_{ind}}\log(\frac{n}{N_{ind}}))</tex>:::::<tex>\Theta(\frac{n}{N_{ind}}\log(\frac{n}{N_{ind}}))</tex> операций нужно на последовательную сортировку массива длиной <tex>\frac{n}{N_{ind}})</tex>.
::::<tex>\Theta(n)</tex> необходимо на последовательное слияние.
::'''[[#.D0.9C.D0.BD.D0.BE.D0.B3.D0.BE.D0.BF.D0.BE.D1.82.D0.BE.D1.87.D0.BD.D0.BE.D0.B5_.D1.81.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|Многопоточное слияние''' ]] будет работать за <tex>\Theta((\frac{n}{N_{ind}})^{(\log_{\frac{4}{3}}2)} + \log(n) \cdot min(N_{ind}, \log(n))=\Theta((\frac{n}{N_{ind}})^{(\log_{\frac{4}{3}}2)})</tex>:
::::Прежде чем достигнуть ограничения на создание нового потока, алгоритм углубится на <tex>min(N_{ind}, \log(n))</tex> уровней вглубь дерева рекурсии, где на каждом уровне выполняется бинпоиск за <tex>\Theta(\log(n))</tex>
::::Асимптотика многопоточного слияния при работе в одном потоке по основной теореме рекуррентных соотношений равна
::::<tex>T_{merge}'(n) = 2T_{merge}'(\frac {3}{4}n) + \Theta(\log(n)) = \Theta(n^{(\log_{\frac{4}{3}}2)})</tex>
::Оценим [[#.D0.A1.D0.BE.D1.80.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.BA.D0.B0_.D1.81_.D0.BC.D0.BD.D0.BE.D0.B3.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>\frac{n}{N_{ind}}</tex> гарантированно будут сортироваться последовательно, т.к. только алгоритм сортировки запустит к моменту вызова mergeSortMT2 от массива длиной <tex>\frac{n}{N_{ind}}</tex> число потоков, равное <tex>N_{ind}</tex>. Тогда по основной теореме рекуррентных соотношений:
::::<tex>T_{mergeSort}'(\frac{n}{N_{ind}}) = 2T_{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>\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
