97
правок
Изменения
м
Нет описания правки
::::<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">\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 dpi="135">\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 dpi="110">min(N_{ind}, \log n)</tex> уровней вглубь дерева рекурсии, где на каждом уровне выполняется бинпоиск за <tex dpi="135">\Theta(\log n)</tex>
::::Асимптотика многопоточного слияния при работе в одном потоке по основной теореме рекуррентных соотношений равна
::::<tex dpi="135">T_{\mathrm {merge}}'(n) = 2T_{\mathrm {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 dpi="135">\frac{n}{N_{ind}}</tex> гарантированно будут сортироваться последовательно, т.к. только алгоритм сортировки запустит к моменту вызова <tex>\mathrm {mergeSortMT2} </tex> от массива длиной <tex dpi="135">\frac{n}{N_{ind}}</tex> число потоков, равное <tex dpi="135">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
