常见时间复杂度与空间复杂度解析

常见复杂度对比

常数阶 O(1)

int main() {
    int x = 0;
    scanf("%d", &x);
    printf("%d", x);
    return 0;
}

无论输入如何，操作次数固定，复杂度为 O(1)。

线性阶 O(N)

例如 Func2 中，循环次数与 N 成正比，忽略常数项后为 O(N)。如果是两个独立循环分别依赖 M 和 N，且 M 与 N 无关，则复杂度为 O(M+N)，通常简化为 O(N)。

平方阶 O(N^2)

嵌套循环是典型的平方阶结构。内层循环每执行一次外层就执行一次，总次数约为 N*N。

对数阶 O(log N)

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

每次迭代数值翻倍，执行次数 x 满足 2^x = n，即 x = log₂n。

递归函数

递归的时间复杂度是所有递归调用次数的累加。 单递归如阶乘，调用深度为 N，每次操作 O(1)，总复杂度 O(N)。 若递归内部包含循环，复杂度会相应增加，例如 O(N^2)。

空间复杂度

空间复杂度衡量的是临时占用存储空间的大小，同样使用大 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)

如果涉及创建新数组或动态分配内存，空间复杂度通常为 O(N)。例如反转数组的操作，若原地修改则为 O(1)，若需辅助数组则为 O(N)。

总的来说，在复杂度分析中，时间复杂度通常是首要考量指标。