Другой способ получения упорядоченного набора целых чисел
Другой способ получения упорядоченного набора целых чисел заключается в перемешивании п-элементного массива с числами О..п-l и сортировке его первых m элементов, которые затем могут быть выведены. Алгоритм Р из раздела 3.4.2 монографии Кнута предназначен для перемешивания массива х[0..п-1].
for 1 = [0. п)
swap(i. randint(i, n-1))
Эшли Шепхерд (Ashley Shepherd) и Алекс Воронов (Alex Woronow) пришли к выводу, что в этой задаче нужно перемешать только первые m элементов массива. В итоге получаем следующую программу на C++:
Листинг 12.3 Программа 3
void genshuf(int m. int n)
{ int i . j :
int *x = new int[n]; for (i = 0, i < n. i ++) x [ i ] = i : for (i = 0, i < m; i ++) { j = randi nt(i . n -1) ; int t = x[i]. x[13 = x[j]; x[j3 = t:}
sort(x. x+m) for (i = 0. i < m; i++) cout << x[i] << "\n”;}
Данный алгоритм использует п слов памяти и работает за время 0{п + т log m), но метод, примененный в задаче 9 из главы 1, уменьшает время выполнения до 0(m\ogm). Алгоритм можно рассматривать в качестве альтернативы программе 2, в которой набор выбранных элементов хранится в х[0. .i-1], а оставшиеся элементы помещаются в x[i..n-l]. Явно представляя невыбранные элементы, мы исключаем необходимость проверки, был ли уже выбран ранее данный элемент. К сожалению, этот метод работает за время О(п) и требует такого же количества памяти, поэтому обычно он уступает алгоритму Кнута.
Мы рассмотрели несколько вариантов решения задачи, но описанные программы ни в коей мере не покрывают все пространство разработки. Предположим, что n = 1 ООО ООО, a m « п - 10. Мы можем сформировать отсортированный набор из 10 элементов, а потом выдать пользователю все остальные элементы основного множества, которые в этот набор не вошли. Предположим, что п = 10 000 000, a m = 231. Можно сгенерировать 11 миллионов целых чисел, отсортировать их, удалить повторяющиеся элементы, а затем выбрать из них 10 миллионов и отсортировать их. В решении задачи 9 описан хитроумный алгоритм Боба Флойда, основанный на поиске.
Опубликовал vovan666
April 17 2013 00:03:01 ·
0 Комментариев ·
3064 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
