传习Chuanxi

简单算法复杂度的估算

简单算法复杂度的估算

简单算法复杂度的估算，含多项式、指数复杂度。

复杂度用大 O 表示数据规模 n 增长时，时间或空间随 n 增长的主要趋势。双重循环常是 O(n²)，单循环 O(n)，二分 O(log n)。多项式如 O(n²)、O(n log n) 在 n 较大时仍可能可行；指数如 O(2ⁿ) 稍大 n 就不可接受。

GESP 四级不要求严格推导，但要会：数循环层数、识别「n 每增 1 工作量乘常数倍」的指数形态、比较两种算法谁更优。120 分钟笔试里常见「给片段选复杂度」或「n=1000 能否 1 秒内跑完」的直觉判断。

for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
        cnt++;          // O(n²)

见到嵌套循环，先问「每层依赖 n 吗」，再相乘或相加，别被常数迷惑。

下面关于排序算法（冒泡排序、插入排序和选择排序）的描述中，不正确的是（ ）。

给定如下代码，其时间复杂度为（ ）。

int cellRecur(int n) {
    if (n == 1)
        return 1;
    return cellRecur(n - 1) + cellRecur(n - 1) + 1;
}

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

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

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

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

下述斐波那契数列计算的时间复杂度是（ ）。

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

关于插入排序的时间复杂度，下列说法正确的是（ ）。

假设有一个班级的成绩单，存储在一个长度为 nn 的数组 scores 中，每个元素是一个学生的分数。老师想要找出所有满足 scores[i] + scores[j] + scores[k] == 300 的三元组，其中 i<j<ki < j < k。下面代码实现该功能，请问其时间复杂度是（ ）。

int cnt = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            if (scores[i] + scores[j] + scores[k] == 300) {
                cnt++;
            }
        }
    }
}

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

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

下列代码段的时间复杂度为（ ）。

int cnt=0;
for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        if( (i+j) % 3 == 0) cnt++;
    }
}

下面用递推方式计算斐波那契数列第 nn 项的程序，时间复杂度是 O(2n)O(2^n)。

int fib(int n) {
    if (n <= 1) return n;
    int f0 = 0, f1 = 1, cur = 0;
    for (int i = 2; i <= n; i++) {
        cur = f0 + f1;
        f0 = f1;
        f1 = cur;
    }
    return cur;
}

下面代码的时间复杂度是 O(2n)O(2^n)。

int cnt = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        cnt++;
    }
}