|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Politov 2:5015/176.18 11 Feb 2002 06:19:21
To : Nickita A Startcev
Subject : Re: Re Случайный выбор
--------------------------------------------------------------------------------
До меня дошли слухи, что *10.02.02* *17:17:38* пролетало сообщение
от Nickita к *Sergey Politov* про *"Re Случайный выбор"*. И я решил вмешаться.
[...]
NAS> А насколько хорошая "случайность" у тебя получается? Почему надо именно
NAS> n перестановок делать, а не 2n?
имхо появление всех комбинаций равновероятно. Т.к. фактически там просто
выбирается первый элемент, потом второй и т.д. Могу и точное мат
доказательство привести, что вероятность появление какой то перестановки
есть 1/n!.
А вот у тебя не все равновероятно. Пример пусть имеем сортировку пузырьком,
которая сохраняет порядок следование элементов с одинаковыми ключами, и два
элемента которые переставляем. И пусть ключи по которым ты сортируешь
принимают значения 1..n, тогда вероятность получить 2,1 равна n(n-1)/2/n^2, а
1,2 - (n(n-1)/2+n)/n^2=n(n+1)/2/n^2.
Искренне Ваш
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: Человек - побочный продукт любви. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
