GESP 四级 · GESP 202503 C++ 四级 第 11 题

给定如下算法，其时间复杂度为（ ）。

bool f(int arr[], int n, int target) {
    for (int i = 0; i < (1 << n); i++) {
        int sum = 0;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                sum += arr[j];
            }
        }
        if (sum == target) return true;
    }
    return false;
}

看到两层循环，先数外层迭代次数（2^n）再乘内层次数（n）。

误把(1<<n)当作n或n+1；看到两层就默认O(n²)。

考点：时间复杂度｜嵌套循环｜位运算

解析

外层循环迭代2^n次，内层循环n次，内层操作为常数时间，总复杂度O(n × 2^n)。