18_LinearSort
.pdfТрудоѐмкости сортировок
Трудоѐмкости представленных реализаций (побитовая и побайтовая) восходящей сортировки линейны за счѐт того, что:
–сортировка по каждому биту (байту) выполняется независимо;
–независимо от n требуется выполнить ―проход‖ по всем битам (байтам) чисел.
Н.Новгород, 2009 г. |
Оптимизация ПО. |
91 |
|
Сортировки |
|
|
|
3.
Вычислительные эксперименты
Н.Новгород, 2009 г. |
Оптимизация ПО. |
92 |
|
Сортировки |
|
|
|
Сравнение реализаций
Н.Новгород, 2009 г. |
Оптимизация ПО. |
93 |
|
Сортировки |
|
|
|
Сравнение реализаций (x(n)/n)
Н.Новгород, 2009 г. |
Оптимизация ПО. |
94 |
|
Сортировки |
|
|
|
Тестовая система
Н.Новгород, 2009 г. |
Оптимизация ПО. |
95 |
|
Сортировки |
|
|
|
Литература
Press W., Teukolsky S., Vetterling W., Flannery B. Numerical Recipes in C. The Art of Scientific Computing. Second Edition. — Cambridge University Press, 1992.
Столлингс, Вильям. Структурная организация и архитектура компьютерных систем, 5-е изд.: Пер. с англ.
—М.: Издательский дом «Вильямс», 2002. — 896 с.: ил.
—Парал. тит. англ.
Н.Новгород, 2009 г. |
Оптимизация ПО. |
96 |
|
Сортировки |
|
|
|