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

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

bool f(int arr[], int n, int target) {
    for (int i = 0; i < 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 种情况

考点：嵌套循环复杂度

解析

两层循环，外层 i 从 0 到 n-1，内层 j 从 0 到 n-1，位运算仅做 O(1) 判断，总操作量恒为 n×n，故时间复杂度 O(n²)。