34
правки
Изменения
Нет описания правки
===Псевдокод===
<code> '''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);</code>
===Доказательство корректности алгоритма===
===Оценка временной сложности===
Заметим, что алгоритм состоит из 2 невложенных циклов по <tex>n</tex> итераций каждый и функции генерации случайной перестановки <tex>random_shuffle()</tex>, работающей за <tex>O(n)</tex> по алгоритму [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|Фишера Йетца]]. Следовательно, временная сложность и всего алгоритма <tex>O(n)</tex>
== См. также ==
