void gensets(int m, int n)
{ set<int> S; whi1e (S.size() < m)
S.insert(bigrand() % n) set<int>-:iterator i : for (i - S.begin(); i !- S.endO; ++i) cout << << "\n";}
Написав эту программу, я с удовольствием обнаружил, что длина псевдокода совпадает с длиной реальной программы. Эта версия формирует и выводит миллион упорядоченных 32-разрядных случайных целых примерно за 20 секунд. По
скольку на формирование и вывод миллиона неупорядоченных целых чисел требуется примерно 12,5 секунды, на операции с набором тратится примерно 7,5 секунды.
Спецификация C++ STL гарантирует, что любая операция вставки будет выполняться за время 0(log т), а перебор элементов списка потребует времени О(т), так что вся программа будет работать за время 0(m\ogm), где m мало по сравнению с п. Однако эта структура данных требовательна к памяти: мой компьютер со 128 Мбайт ОЗУ начинает обращаться к диску, когда m достигает величины порядка 1 700 ООО. В следующем разделе рассматриваются возможные реализации набора.
Опубликовал vovan666
April 17 2013 00:02:59 ·
0 Комментариев ·
3776 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
