Есть ли O (n ^ 2) алгоритм для генерации всех подпоследовательностей массива?
Мне было интересно, есть ли какой-либо алгоритм сложности O (n ^ 2) для генерации всех подпоследовательностей массива. Я знаю алгоритм, но это занимает O ((2 ^ n) * n) времени.
int main() {
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i)
cin >> a[i];
int64_t opsize = pow(2,n);
for (int counter = 1; counter < opsize; counter++) {
for (int j = 0; j < n; j++) {
if (counter & (1 << j))
cout << a[j] << " ";
}
cout << endl;
}
}
Решение
нет
Не может быть никакого алгоритма меньше O(2^n) сложность просто потому, что есть O(2^n) суб-последовательности. Вам необходимо распечатать каждый из них, следовательно, сложность времени должна быть больше или равна O(2^n),
Другие решения
Вы не можете улучшить сложность алгоритма, но вы можете улучшить использование потока.
Как указывает другой ответ o(n * 2^n) лучшее, что вы можете иметь.
Когда вы используете std::endl вы очищаете буферы потоков. Для достижения наилучшей производительности буферы должны очищать себя, когда они заполнены.
Поскольку каждая подпоследовательность должна быть достаточно короткой (максимум 64 элемента), это означает, что вы часто очищаете поток и получаете серьезное снижение производительности.
Так что замена std::endl с '\n' обеспечит значительное улучшение производительности.
Другие приемы, которые могут помочь улучшить производительность потока:
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
cin >> n;