3. Чтобы определить оптимальное значение cutoff, я прогнал программу со всеми возможными значениями cutoff от 1 до 100 (при п=1 000 000). На графике приведены результаты.
Время 7
выполнения, с
О,Э _
0,8 _
0, 7 _
0, 7 50 100 Значение cutoff
Я выбрал значение 50. Для всех значений cutoff от 30 до 70 результаты отличались не более чем на несколько процентов.
4. Обратитесь к литературе, упоминаемой в разделе 11.6 главы 11.
5. Программа Макилроя работала за время, пропорциональное объему сортируемых данных. Такая производительность является оптимальной для худшего случая. Предполагается, что каждая запись в массиве х[0..п-1] содержит целое значение длины length и указатель на массив bit[0..Length-1].
void bsort(1. u, depth) if 1 >= u return for i ~ [1 . u]
if x[i] 1ength < depth swap(i, 1++) m = 1
for i = [1 , u]
if x[i ] bi t[depth] == 0 swap(i. m++) bsort(1 . m-1, depth + 1) bsort(m. u. depth+1)
Первый раз функция вызывается как bsort (0, n-1,1). Учтите, что в этой программе значения параметров цикла изменяются в теле цикла. Линейное время работы программы в значительной степени обусловлено тем, что операция swap переставляет указатели на битовые строки, а не сами эти строки.
void s е1s о г t(^ for i = [Q. n-1) for j - [i, n) if x[j]<x[i] swap(i. j)
Опубликовал vovan666
April 17 2013 00:06:54 ·
0 Комментариев ·
4557 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
