是否有任何 O(n^2) 算法来生成数组的所有子序列?
Is there any O(n^2) algorithm to generate all sub-sequences of an array?
我想知道是否有任何复杂度为 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;
我想知道是否有任何复杂度为 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;