C语言算法复杂度分析（小白也能看懂的时间与空间复杂度入门教程）

什么是算法复杂度？

算法复杂度是用来衡量一个算法在运行时所消耗的时间和空间资源的指标。它不关心具体运行了多少秒或用了多少MB内存，而是关注当输入数据规模（通常用 n 表示）增大时，算法所需资源的增长趋势。

因此，算法复杂度分为两类：

• 时间复杂度（Time Complexity）：描述算法执行所需时间随输入规模增长的变化趋势。
• 空间复杂度（Space Complexity）：描述算法执行所需内存空间随输入规模增长的变化趋势。

为什么需要分析算法复杂度？

举个例子：假设有两个排序算法，A 和 B。在小数据量时，两者速度差不多；但当数据量达到百万级时，A 可能需要几分钟，而 B 只需几秒钟。这就是 算法效率 的差异。通过复杂度分析，我们可以在写代码前就预判哪种算法更适合大规模数据处理。

时间复杂度详解

时间复杂度通常用大 O 表示法（Big O Notation）来描述，比如 O(1)、O(log n)、O(n)、O(n²) 等。

O(1) — 常数时间

无论输入多大，执行时间不变。

// 访问数组第一个元素int getFirst(int arr[]) {    return arr[0];}

O(n) — 线性时间

执行时间与输入规模 n 成正比。

// 遍历数组求和int sumArray(int arr[], int n) {    int sum = 0;    for (int i = 0; i < n; i++) {        sum += arr[i];    }    return sum;}

O(n²) — 平方时间

常见于嵌套循环，如冒泡排序。

// 冒泡排序（简化版）void bubbleSort(int arr[], int n) {    for (int i = 0; i < n - 1; i++) {        for (int j = 0; j < n - i - 1; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }    }}

空间复杂度详解

空间复杂度关注的是算法运行过程中额外占用的内存空间（不包括输入本身占用的空间）。

例如，上面的 sumArray 函数只用了几个变量（sum、i），所以空间复杂度是 O(1) —— 常数空间。

而递归算法可能占用较多栈空间。比如计算阶乘：

int factorial(int n) {    if (n == 0 || n == 1)        return 1;    return n * factorial(n - 1);}

这个函数会递归调用 n 次，每次调用都会在栈中保存一次状态，因此空间复杂度是 O(n)。

如何快速判断复杂度？

• 没有循环或递归？→ O(1)
• 单层 for/while 循环？→ O(n)
• 两层嵌套循环？→ O(n²)
• 每次把问题规模减半（如二分查找）？→ O(log n)
• 递归调用次数等于 n？→ 空间复杂度可能是 O(n)

总结

掌握 C语言算法复杂度分析 是提升编程能力的关键一步。通过理解 时间复杂度 和 空间复杂度，你可以写出更高效的代码，避免在大数据场景下程序“卡死”。记住：优秀的程序员不仅让代码“能跑”，更要让它“跑得快、占得少”——这就是 算法效率 的真正意义！

现在，试着分析你写过的 C 语言函数吧！看看它们的时间和空间复杂度是多少？