88
правок
Изменения
Нет описания правки
Данный алгоритм работает за <tex>O(n^2) </tex>. Мы можем посчитать все <tex>P_{n} </tex> за <tex>O(n) </tex>. Асимптотику можно улучшить
до <tex>O(n \log {n}) </tex>, если использовать структуры данных, которые позволяют искать i-ый элемент множества и удалять элемент множества за <tex>O( \log {n}) </tex>. Например декартово дерево по неявному ключу.
== Битовые вектора ==
Для некоторых комбинаторных объектов, например битовых векторов, можно привести явную [[Отображения|биекцию]] из множества номеров в множество объектов.
В данном случае битовым вектором для номера n {{---}} будет являться его двоичное представление, которое можно получить гораздо легче,
чем генерировать объект общим алгоритмом. Если не учитовать особенности представления натуральных числе в памяти компьютера, то битовый вектор можно получить из числа за <tex>O(\log{n}) </tex>, где n {{---}} номер вектора (log n = длине битового вектора), простым переводом десятичного числа n в двоичную систему счисления.
== См. также ==
[[Получение номера по объекту|Получение номера по объекту]]
