时间戳

首页 > 解决方案 > 是否有任何 O(n^2) 算法来生成数组的所有子序列？

c++ - 是否有任何 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;
    }
}

标签： c++arraysalgorithmsubsequence

解决方案

不

O(2^n)仅仅因为存在O(2^n) 子序列，就不可能有任何低于复杂度的算法。您需要打印它们中的每一个，因此时间复杂度必须大于或等于O(2^n).

推荐阅读