Методы генерации случайного сочетания — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 36: Строка 36:
 
===Оценка временной сложности===
 
===Оценка временной сложности===
  
Заметим, что алгоритм состоит из 2 невложенных циклов по <tex>n</tex> итераций каждый и функции генерации случайной перестановки <tex>random_shuffle()</tex>, работающей за <tex>O(n)</tex> по алгоритму [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|Фишера Йетца]]. Следовательно, временная сложность и всего алгоритма <tex>O(n)</tex>
+
Заметим, что алгоритм состоит из 2 невложенных циклов по <tex>n</tex> итераций каждый и функции генерации случайной перестановки <tex>random\_shuffle()</tex>, работающей за <tex>O(n)</tex> по алгоритму [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|Фишера Йетца]]. Следовательно, временная сложность и всего алгоритма <tex>O(n)</tex>
  
 
== См. также ==
 
== См. также ==

Версия 02:35, 27 декабря 2012

Постановка задачи

Необходимо сгенерировать случайное сочетание из [math] n [/math] элементов по [math]k[/math] с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.

Решение за время O(n * k)

Псевдокод

Доказательство корректности алгоритма

Решение за время O(n)

Для более быстрого решения данной задачи воспользуемся следующим алгоритмом: пусть задан для определенности массив [math]a[][/math] размера [math]n[/math], состоящий из [math]k[/math] единиц и [math]n - k[/math] нулей. Применим к нему алгоритм генерации случайной перестановки. Тогда все элементы [math]i[/math], для которых [math]a[i] = 1[/math], включим в сочетание.

Псевдокод

 for i = 1 to n 
   if i <= k
     a[i] = 1;
   else
     a[i] = 0;
 random_shuffle(a);
 for i = 1 to n
   if a[i] == 1
     insertInAnswer(i);

Доказательство корректности алгоритма

Оценка временной сложности

Заметим, что алгоритм состоит из 2 невложенных циклов по [math]n[/math] итераций каждый и функции генерации случайной перестановки [math]random\_shuffle()[/math], работающей за [math]O(n)[/math] по алгоритму Фишера Йетца. Следовательно, временная сложность и всего алгоритма [math]O(n)[/math]

См. также

Источники