Изменения

Перейти к: навигация, поиск

Методы генерации случайного сочетания

2 байта добавлено, 17:40, 16 декабря 2014
Нет описания правки
'''int[]''' randomCombination('''int[]''' arrayOfElements, '''int''' n, '''int''' k)
'''for''' i = 1 '''to''' k
r = randrandom(1..(n - i + 1))
cur = 0
'''for''' j = 1 '''to''' n
'''else'''
a[i] = 0
randomshufflerandomShuffle(a)
'''for''' i = 1 '''to''' n
'''if''' a[i] == 1
===Оценка временной сложности===
Алгоритм состоит из 2 невложенных циклов по <tex>n</tex> итераций каждый и функции генерации случайной перестановки <tex>\mathrm{randomshufflerandomShuffle()}</tex>, работающей за <tex>O(n)</tex> по алгоритму [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|Фишера—Йетcа]]. Следовательно, сложность и всего алгоритма <tex>O(n)</tex>
== См. также ==
Анонимный участник

Навигация