От переводчика. Перевод статьи 2007 года на arxiv.org о статистическом анализе модификации быстрой сортировки.
Наверняка найдутся люди, использующие описанный вариант интуитивно. Здесь — математическое обоснование эффективности при n <= 7 000 000
Ключевые слова
Внутренняя сортировка; Равномерное распределение; Средняя временная сложность; Статистический анализ; Статистическая оценка
Читать полностью »
Введение
Промышленность не стоит на месте. Еще в 1990 году псевдослучайные числа, длинной в целых 40 бит, сгенерированные на ЭВМ можно было угадать за несколько часов [1]. На сегодняшний же день, качественные характеристики псевдослучайных величин на ЭВМ поражает даже опытных математиков. Во многих областях применения алгоритмов генераций всевдослучайных чисел существует ряд ограничений, связанных с тем или иным недостатком методов их генерации. Совершенствованию существующих методов способствует высокий интерес к теме, который повышается с ростом числа публикаций. Пусть эта статья станет моим вкладом в развитие методов моделирования и генерации случайных процессов, так важных для моих исследований и разработок.
Читать полностью »
