深入理解数据结构中的时间与空间复杂度

二、典型场景解析

1. 常数阶 O(1)

无论输入规模如何，操作次数固定。

#include<stdio.h>
int main() {
    int x = 0;
    scanf("%d", &x); // 修正了原稿拼写错误 scnaf -> scanf
    printf("%d", x);
    return 0;
}

执行次数恒定为 3 次，复杂度 O(1)。

2. 线性阶 O(N)

操作次数随 N 线性增长。

void Func2(int N) {
    int count = 0;
    for (int k = 0; k < 2 * N; ++k) {
        ++count;
    }
    int M = 10;
    while (M--) {
        ++count;
    }
    printf("%d\n", count);
}

总次数 2N + 10，去低阶和系数后为 O(N)。

若存在两个独立变量 M 和 N：

void Func3(int N, int M) {
    int count = 0;
    for (int k = 0; k < M; ++k) ++count;
    for (int k = 0; k < N; ++k) ++count;
    printf("%d\n", count);
}

总次数 M + N。若 M 和 N 同阶，则为 O(N)；若差异巨大，则取较大者。

3. 平方阶 O(N²)

嵌套循环的典型特征。

#include<stdio.h>
int main() {
    int x = 0;
    int begin = clock();
    int n = 100000;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            x++;
        }
    }
    int end = clock();
    printf("%dms\n", end - begin);
    return 0;
}

注意：此处需包含 <time.h> 头文件才能使用 clock()。双重循环导致复杂度为 O(N²)。

4. 对数阶 O(log N)

每次迭代将问题规模减半。

void func5(int n) {
    int cnt = 1;
    while (cnt < n) {
        cnt *= 2;
    }
}

设执行次数为 x，则 2^x = n，解得 x = log₂n。最坏情况复杂度为 O(log₂n)。

5. 递归函数

递归的时间复杂度取决于调用次数与单次调用的开销。

单递归示例：

long long Fac(size_t N) {
    if (N == 0) return 1; // 修正了原稿逻辑错误，增加基准条件
    return Fac(N-1) * N;
}

每次调用耗时 O(1)，共调用 N 次，总复杂度 O(N)。

双递归示例： 若递归内部包含循环或多次递归调用，复杂度会显著上升。例如斐波那契数列的朴素递归实现，其时间复杂度接近 O(2^N)，因为存在大量重复计算。

三、空间复杂度

空间复杂度衡量算法运行时临时占用的存储空间大小，同样使用大 O 表示法。在实际开发中，时间复杂度往往比空间复杂度更受关注，但在嵌入式等内存受限场景下，空间复杂度至关重要。

需注意：函数栈帧（参数、局部变量）通常在编译期确定，空间复杂度主要看运行时显式申请的空间。

冒泡排序 O(1)

void BubbleSort(int* a, int n) {
    assert(a);
    for (size_t end = n; end > 0; --end) {
        int exchange = 0; // 仅使用了有限个局部变量
        for (size_t i = 1; i < end; ++i) {
            if (a[i-1] > a[i]) {
                Swap(&a[i-1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0) break;
    }
}

除输入数组外，仅使用了常数个额外变量，空间复杂度为 O(1)。

数组反置 O(N)

void reverse(int* nums, int left, int right) {
    while (left < right) {
        int temp = nums[left]; // 修正变量名 tap -> temp
        nums[left] = nums[right];
        nums[right] = temp;
        left++;
        right--;
    }
}

int main() {
    int nums[] = { 1,2,3,4,5,6,7 };
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int k = 0;
    scanf("%d", &k);
    k %= numsSize;
    reverse(nums, 0, numsSize - k - 1);
    reverse(nums, numsSize - k, numsSize - 1);
    reverse(nums, 0, numsSize - 1);
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

此例中虽然创建了数组，但这是输入数据本身。若算法内部需要创建与 N 等大的辅助数组，空间复杂度则为 O(N)。通常情况下，空间复杂度多为 O(1)、O(N) 或 O(N²)，实际优化时仍以时间复杂度为首要考量。