哈喽，各位C语言学习者！👋 今天咱们深入聊聊算法效率的核心衡量指标——时间复杂度。不管是笔试面试还是日常开发优化，时间复杂度都是绕不开的重点。这篇笔记会从基础概念讲起，结合C语言实例拆解计算方法，新手也能轻松看懂～
一、什么是时间复杂度？🤔
时间复杂度（Time Complexity）本质是算法执行时间与输入规模的增长关系，它不计算具体的执行时间，而是描述当输入数据量n增大时，算法执行步骤的增长趋势。
为什么不用具体时间衡量？因为不同设备（CPU、内存）的运行速度不同，同样的算法在不同机器上执行时间差异很大。而时间复杂度能剥离硬件影响，直接反映算法的“效率好坏”。
在C语言中，我们分析时间复杂度，主要关注循环语句、递归调用等重复执行的代码块——这些是消耗时间的核心部分。
二、时间复杂度的表示方法：大O符号
时间复杂度通常用大O符号（O-notation）表示，格式为 O(f(n))，其中 f(n) 是输入规模n的函数，代表算法执行步骤的增长量级。
大O符号的核心原则：忽略常数项、低次项，只保留最高次项。
举个例子：如果算法执行步骤是 3n² + 2n + 5，忽略常数3、2、5和低次项2n，时间复杂度就是 O(n²)。
三、C语言中常见的时间复杂度（从优到劣）
下面结合C语言实例，逐个拆解最常用的时间复杂度，理解它们的增长规律～
1. 常数阶 O(1)
无论输入规模n多大，算法执行步骤都是固定的，时间复杂度为O(1)。常见于无循环、无递归的简单操作。
C语言实例：
#include <stdio.h> // 交换两个整数的值，执行步骤固定（3步：临时变量存储、赋值、赋值） void swap(int* a, int* b) { int temp = *a; // 1步 *a = *b; // 2步 *b = temp; // 3步 } int main() { int x = 10, y = 20; swap(&x, &y); printf("x=%d, y=%d\n", x, y); return 0; }说明：swap函数无论a、b的值是多少，都只执行3步操作，因此时间复杂度是 O(1)。
2. 线性阶 O(n)
算法执行步骤与输入规模n成正比，n越大，步骤越多。常见于单重循环。
C语言实例：遍历数组
#include <stdio.h> // 遍历数组并打印所有元素，循环执行n次（n是数组长度） void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { // 循环n次 printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {1,2,3,4,5}; int len = sizeof(arr) / sizeof(arr[0]); printArray(arr, len); return 0; }说明：printArray函数的循环执行次数等于数组长度n，因此时间复杂度是 O(n)。
3. 线性对数阶 O(nlogn)
执行步骤为 n 乘以 logn（通常以2为底），增长速度介于 O(n) 和 O(n²) 之间。常见于分治思想的算法，比如快速排序、归并排序、二分查找的循环调用。
C语言实例：简化版归并排序核心逻辑（分治过程）
#include <stdio.h> // 归并排序核心：将数组分成两部分，递归排序后合并 void mergeSort(int arr[], int left, int right) { if (left < right) { int mid = (left + right) / 2; // 分：将数组一分为二 mergeSort(arr, left, mid); // 递归排序左半部分 mergeSort(arr, mid+1, right); // 递归排序右半部分 // merge(arr, left, mid, right); // 合并两个有序子数组（O(n)操作） } } int main() { int arr[] = {5,3,8,6,2}; int len = sizeof(arr) / sizeof(arr[0]); mergeSort(arr, 0, len-1); return 0; }说明：归并排序每次将数组分成2份（logn层），每一层的合并操作是 O(n)，因此总时间复杂度是 O(nlogn)。
4. 平方阶 O(n²)
执行步骤与输入规模n的平方成正比，常见于双重嵌套循环。
C语言实例：冒泡排序
#include <stdio.h> // 冒泡排序：双重循环，外层n次，内层最多n次 void bubbleSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { // 外层循环：n-1次 for (int j = 0; j < n-1 - i; j++) { // 内层循环：最多n-1次 if (arr[j] > arr[j+1]) { // 交换元素 int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } int main() { int arr[] = {5,3,8,6,2}; int len = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, len); return 0; }说明：冒泡排序的外层循环执行n-1次，内层循环最多执行n-1次，总步骤数约为 n×n，因此时间复杂度是 O(n²)。
5. 指数阶 O(2ⁿ)、阶乘阶 O(n!)（尽量避免）
这两种复杂度的算法，随着n增大，执行步骤会爆炸式增长，效率极低，仅适用于n极小的场景（比如n≤20）。常见于无优化的递归算法（如斐波那契数列递归）。
C语言实例：斐波那契数列递归（O(2ⁿ)）
#include <stdio.h> // 递归计算第n个斐波那契数，重复计算量极大 int fib(int n) { if (n <= 2) return 1; return fib(n-1) + fib(n-2); // 双重递归调用 } int main() { int n = 10; printf("第%d个斐波那契数：%d\n", n, fib(n)); return 0; }说明：fib(n)会重复计算大量fib(k)（k<n），执行步骤随n呈指数增长，时间复杂度为 O(2ⁿ)。实际开发中会用动态规划优化为 O(n)。
四、时间复杂度的计算技巧 📝
只看核心循环：忽略顺序执行的常数项操作（如变量定义、简单赋值），重点分析重复执行的循环或递归。
嵌套循环取乘积：外层循环复杂度 × 内层循环复杂度（如双重循环 O(n)×O(n)=O(n²)）。
并列循环取最大值：多个并列的循环，取复杂度最高的那个（如 O(n) + O(n²) = O(n²)）。
递归看调用次数：递归算法的时间复杂度 = 每次递归的操作复杂度 × 递归调用次数。
五、总结
时间复杂度是评估C语言算法效率的核心指标，记住从优到劣的顺序：
O(1) ＜ O(logn) ＜ O(n) ＜ O(nlogn) ＜ O(n²) ＜ O(2ⁿ) ＜ O(n!)
实际开发中，尽量选择 O(nlogn) 及以下复杂度的算法；对于 O(n²) 及以上的算法，要考虑是否有优化空间（如用二分查找替代线性查找、用归并排序替代冒泡排序）。
如果有疑问，欢迎在评论区交流～ 👇
#C语言 #时间复杂度 #算法基础 #数据结构 #程序员面试
)