97
правок
Изменения
м
Нет описания правки
::::Части массива длиной <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
