一、大O表示法只看趋势大O表示法描述的是算法执行时间随数据规模增长的变化趋势。推导时只需记住保留最高阶项去掉所有系数。例如2N 3logN 10最终记为O(N)。二、O(log N)折半就是对数对数复杂度的核心特征只有一个每次循环或递归问题的规模都缩小一半或按固定比例缩小。2.1 循环折半#include stdio.h /* * 功能演示对数复杂度 O(log N) * 关键特征循环变量 i 每次乘以 2翻倍 * * 推导设循环执行 x 次后结束 * 第1次i 2 * 第2次i 4 * 第3次i 8 * ... * 第x次i 2^x * * 结束条件2^x N x log₂N * 因此时间复杂度为 O(log N) */ void demoLogN(int N) { int count 0; int i 1; while (i N) { i i * 2; // 关键每次翻倍 count; } printf(N%d, 循环次数%d\n, N, count); } int main() { demoLogN(16); // N16, 循环4次 (log₂16 4) demoLogN(1024); // N1024, 循环10次 return 0; }快速判断看到循环变量i * 2或i / 2立刻想到O(log N)。底数是 2 还是 3 不影响大O表示。2.2 二分查找#include stdio.h /* * 功能二分查找在有序数组中查找目标值 * 时间复杂度O(log N) * * 核心思想每次比较后搜索范围缩小一半 * 无论目标在哪最多只需 log₂N 次比较 */ int binarySearch(int arr[], int n, int target) { int left 0; int right n - 1; while (left right) { int mid left (right - left) / 2; // 防止溢出的写法 if (arr[mid] target) { return mid; // 找到目标 } else if (arr[mid] target) { left mid 1; // 目标在右半部分范围减半 } else { right mid - 1; // 目标在左半部分范围减半 } } return -1; // 未找到 } int main() { int arr[] {3, 8, 12, 25, 31, 47, 58, 69, 81, 95}; int n 10; int result binarySearch(arr, n, 47); printf(查找结果下标%d\n, result); // 输出 5 return 0; }2.3 递归折半#include stdio.h /* * 功能递归方式演示对数复杂度 * 时间复杂度O(log N) * * 分析递归深度决定了执行次数 * 每次递归 N 变为 N/2深度为 log₂N * 每层只执行常数操作打印、判断 */ void recursiveHalve(int N) { if (N 1) { return; // 递归终止条件 } printf(当前 N %d\n, N); recursiveHalve(N / 2); // 关键每次规模减半 } int main() { recursiveHalve(16); // 会打印 16, 8, 4, 2共 log₂16 4 层 return 0; }三、O(N log N)线性遍历套折半操作O(N log N)是高效排序算法如归并排序、堆排序的典型复杂度。它的结构很固定外层是 N 次的线性遍历内层是 O(log N) 的折半操作。#include stdio.h /* * 功能演示线性对数复杂度 O(N log N) * * 外层循环i 从 1 到 N执行 N 次 * 内层循环j 每次翻倍执行 log N 次 * 总操作次数 N * log N */ void demoNLogN(int N) { int total 0; for (int i 1; i N; i) { // 外层线性 N 次 int j 1; while (j N) { // 内层对数 log N 次 j j * 2; total; } } printf(N%d, 总操作次数%d\n, N, total); } int main() { demoNLogN(8); // 8 * 3 24 demoNLogN(16); // 16 * 4 64 return 0; }实际场景对 N 个元素分别进行一次二分查找整体就是O(N log N)。四、快速判断口诀表格代码特征时间复杂度判断要点循环变量每次乘2或除2O(log N)折半、翻倍就是对数外层 N 次 内层折半O(N log N)线性套对数递归每次规模减半O(log N)递归深度为 log N递归先遍历 N 再折半递归两次O(N log N)类似归并排序的递归树五、练习题题目1void funcA(int N) { int i N; while (i 1) { i i / 3; // 每次变为原来的 1/3 } }时间复杂度是多少题目2void funcB(int N) { for (int i 0; i N; i) { int j 1; while (j N) { j j * 2; } } }时间复杂度是多少题目3递归void funcC(int N) { if (N 1) return; funcC(N / 2); }时间复杂度是多少题目4递归void funcD(int N) { if (N 1) return; for (int i 0; i N; i) { printf(%d , i); } printf(\n); funcD(N / 2); funcD(N / 2); }时间复杂度是多少题目5双参数void funcE(int N, int M) { for (int i 0; i N; i) printf(1); for (int j 0; j M; j) printf(2); }时间复杂度是多少提示O(MN)与O(max(M,N))在渐进意义下等价因为max(M,N) ≤ MN ≤ 2×max(M,N)两者只相差常数倍。通常写O(MN)更直观。答案与解析表格题号时间复杂度解析1O(log N)循环变量每次除以3底数不影响大O2O(N log N)外层N次 × 内层log N次3O(log N)递归深度为 log N每层常数操作4O(N log N)递归树深度为 log N每层总工作量约为 NN N/2 N/2 2N总复杂度为 O(N log N)5O(MN)两个独立循环复杂度相加。也可写作 O(max(M,N))