|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Polubasoff 2:5020/400 06 Jan 2003 22:12:54
To : Nickita A Startcev
Subject : масив чисел
--------------------------------------------------------------------------------
Привет, Hикита!
В воскресенье, 05.01.2003 18:26, Nickita A Startcev писал к Evgenij
Masherov:
EM>> Похоже, что вообще гарантировать равновероятность менее чем за NlogN
EM>> операций не выйдет...
IMHO, ты спутал с числом обменов для сортировки. Ломать (перемешивать)
обычно проще, чем строить (сортировать). :)
NA> А алгоритм типа нижеприведенного сильно плохое распределение даст?
NA> for(i=0;i<10;i++)
NA> {
NA> a=random();
NA> b=random();
NA> swap(array[a],array[b]);
NA> }
Сильно. Будем считать, что random() даёт равномерно распределённые целые
от 0 до 9 и при этом разные вызовы независимы. Поскольку random() вызывается
20 раз, то всего (равновероятных) путей выполнения программы - 10^20. Так
как различных перестановок - 10!, то понятно, что некоторые из путей
порождают одинаковые перестановки. Hо невозможно поровну распределить пути
между перестановками, так как 10^20 не делится нацело на 10!, следовательно
некоторые перестановки получаются большим числом путей, чем другие.
По этой же причине плох и следующий алгоритм:
for (int i = 9; i > 0; --i)
swap (array[i], array[RND(10)]);
А правильный алгоритм уже неоднократно приводили, он имеет 10! возможных
путей выполнения, и разные пути порождают разные перестановки:
for (int i = 9; i > 0; --i)
swap (array[i], array[RND(i+1)]);
2Oleg Khovayko:
RND(n) часто определяют как random()%n, и для практических целей этого
обычно вполне достаточно. Hо, если, как ты говоришь, интересует именно
"математически верный" алгоритм, то надо иметь ввиду, что результат
random()%n может быть распределён не равномерно. Hапример, если random()
даёт равномерно распределённые целые от 0 до N, и при этом N не делится
нацело на n, то некоторые остатки выпадают реже других.
О том, что последовательные вызовы random() обычно не независимы, молчу.
С уважением, Олег Полубасов. СПб.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
