GESP 四级 · GESP 202512 C++ 四级 第 13 题

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

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;
}

答案B。在循环中遍历数组并累积结果时，注意累加变量的初始值和每次循环的更新方式。

for循环体可能一次都不执行！这是和while循环一样的"先判断后执行"机制。

【考点】时间复杂度｜循环嵌套

GESP四级算法模块第3章，考查基础循环嵌套复杂度分析。命题人用双层循环卡住只会算单层或误判指数级的考生，这是入门算法的必考门槛。时间复杂度是算法分析的核心，必须熟练掌握基本循环的阶乘关系。

双层循环嵌套，内层循环执行次数恒为n，外层循环执行n次，总操作量≈n×n。通法：数清楚每层循环的迭代次数，相乘即得阶乘级复杂度。若外层循环次数随i变化（如for(int i=0;i<n;i++)），则需累加内层次数，形成更复杂的复杂度。

选项D最阴险，看到1<<j就误判为指数级，但内层循环次数仍固定为n。若只背结论，容易把位运算当成复杂度倍增的钩子。实际上，位运算只是条件判断，不改变循环次数。命题人喜欢在细节处埋雷，考生必须分清循环次数和条件判断。

若把内层循环改为for(int j=0;j<i;j++)，复杂度仍为O(n^2)；若改成for(int j=0;j<(1<<i);j++)，则变O(2^n)。刷题前先问自己：循环次数到底是多少？如果循环次数是指数级，那么总复杂度就是指数级乘以n，即O(n·2^n)。但本题内层循环次数固定为n，所以是O(n^2)。