Изменения

Рассмотрим алгоритм получения случайного битового вектора. В битовом векторе может находиться только два типа элементов: <tex> 0 </tex> и <tex> 1 </tex>, следовательно <tex> k = 2 </tex>. Заметим что для любого префикса длины <tex> l </tex> число возможных комбинаторных объектов одинаково и равно, следовательно на каждм шаге алгоритма небходмо выбирать с равной вероятностью один из двух элементов<tex> 0 </tex> или <tex> 1 </tex> '''vector<int>''' randomBitVector(n: '''int'''): <font color = green> // <tex> n </tex> {{---}} размер битового вектора.</font> '''for''' i = 1 '''to''' n r = random(0, 1) v[i] = r '''return''' prefix Сложность алгоритма {{---}} <tex>O(n) </tex>, так как в случае двоичных векторов <tex> k </tex> постоянно и равно <tex> 2 </tex>.