本文介绍了是否有任何 O(n^2) 算法来生成数组的所有子序列?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我想知道是否有任何 O(n^2) 复杂度算法来生成数组的所有子序列.我知道一个算法,但它需要 O((2^n)*n) 时间.
I was wondering if there is any O(n^2) complexity algorithm for generating all sub-sequences of an array. I know an algorithm but it takes O((2^n)*n) time.
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)
.
There cannot be any algorithm of less than O(2^n)
complexity simply because there are O(2^n)
sub-sequences. You need to print each of them hence the time complexity has to be greater than or equal to O(2^n)
.
这篇关于是否有任何 O(n^2) 算法来生成数组的所有子序列?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!