单选题 适中
#19849

给定如下算法,其时间复杂度为( )。 bool f ( int arr [ ] , int n , int target ) { for ( int i = 0…

给定如下算法,其时间复杂度为( )。

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
解析
分析算法中循环结构的执行次数与输入规模n的关系。首先确定外层循环的迭代次数,再分析内层操作是否依赖于n或存在嵌套循环。若存在嵌套且内外层均与n线性相关,则总执行次数为n的多项式形式。若每层循环的迭代次数均与n成正比,则时间复杂度由最高次项决定。若无嵌套循环,仅单层线性遍历,则执行次数与n成正比。根据代码中循环层数和每层控制条件判断总体增长趋势。