Как мне написать функцию getPowerset с наилучшим возможным порядком сложности? (Я думаю, это может быть O (2 ^ n).)
Переведено автоматически
Ответ 1
Да, это O(2^n) действительно, поскольку вам нужно сгенерировать, ну, 2^n возможные комбинации. Вот рабочая реализация, использующая дженерики и наборы:
Set<Integer> mySet = newHashSet<Integer>(); mySet.add(1); mySet.add(2); mySet.add(3); for (Set<Integer> s : SetUtils.powerSet(mySet)) { System.out.println(s); }
Ответ 2
На самом деле, я написал код, который выполняет то, что вы просите в O (1). Вопрос в том, что вы планируете делать с набором дальше. Если вы просто собираетесь вызвать size() для этого, это O (1), но если вы собираетесь повторить это, это очевидно O(2^n).
Вот решение, в котором я использую генератор, преимущество которого в том, что весь набор полномочий никогда не сохраняется сразу... Таким образом, вы можете перебирать его один за другим, не требуя его сохранения в памяти. Я хотел бы думать, что это лучший вариант... Обратите внимание, что сложность та же, O (2 ^ n), но требования к памяти снижены (при условии, что сборщик мусора работает нормально! ;) )
Если n < 63, что является разумным предположением, поскольку у вас все равно закончилась бы память (если только вы не используете реализацию итератора) при попытке создать набор полномочий, это более краткий способ сделать это. Двоичные операции намного быстрее, чем Math.pow() и массивы для масок, но почему-то пользователи Java их боятся...
List<T> list = newArrayList<T>(originalSet); intn= list.size();