|
Дискретная математика, 1994, том 6, выпуск 1, страницы 83–99
(Mi dm618)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Предельные теоремы для числа отрезков возрастания в случайных перестановках, порождаемых алгоритмами сортировки
В. А. Ватутин
Аннотация:
Для файла $\mathcal F$, содержащего $n$ записей, помеченных ключами $F_1,\ldots,F_n$, принадлежащими линейно упорядоченному множеству ключей
$$
\mathcal K_m=\{K_j, 1\le j\le m\colon\ K_1<K_2<\ldots<K_m\}
$$
рассматривается перестановка (сортировка) записей $\sigma=\sigma(1)\ldots\sigma(n)$ такая, что
$$
F_{\sigma(1)}\leq F_{\sigma(2)}\le\ldots\le F_{\sigma(n)},
$$
и для любого $i=1,2,\ldots,n-1$ соотношение $F_{\sigma(i)}=F_{\sigma(i+1)}$ влечет неравенство $\sigma(i)<\sigma(i+1)$. В предположении, что ключ $F_i$ для $i$-й записи выбирается случайно и равновероятно из множества ключей $\mathcal K_m$, доказаны предельные теоремы о распределении числа отрезков возрастания в перестановке $\sigma$ при $n,m\to\infty$. Вид этих теорем зависит от асимптотического поведения величины $ne^{-n/m}$ при $n,m\to\infty$.
Статья поступила: 16.02.1993
Образец цитирования:
В. А. Ватутин, “Предельные теоремы для числа отрезков возрастания в случайных перестановках, порождаемых алгоритмами сортировки”, Дискрет. матем., 6:1 (1994), 83–99; Discrete Math. Appl., 4:1 (1994), 31–44
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm618 https://www.mathnet.ru/rus/dm/v6/i1/p83
|
Статистика просмотров: |
Страница аннотации: | 299 | PDF полного текста: | 117 | Первая страница: | 3 |
|