从“能跑就行”到“会算复杂度”时间/空间复杂度 两道力扣练习 二分查找复盘本文涉及的练习代码已经同步到 Gitee数据结构/数据结构练习一复杂度模块 · Luminous/Code_2026 - 码云 - 开源中国一、写在前面代码能跑之后还要考虑效率前面学习顺序表、单链表和双向循环链表时我关注得最多的还是“代码能不能正常运行”指针有没有连对、插入删除会不会崩、最后打印出来的结果是不是正确。进入复杂度这一部分之后开始多考虑一个以前容易忽略的问题——同样能得到正确答案的两份代码效率可能完全不是一个级别。这次感受最明显的还是旋转数组。暴力方法本身没有逻辑错误小数据运行也没有任何问题但它需要重复移动大量数组元素数据规模一大执行次数就会迅速增加。这让我开始真正理解逻辑正确只是算法成立的前提而时间和空间消耗决定了这个解法到底好不好。复杂度就是用来描述这种效率差异的工具。以后看到一个算法除了“能不能做出来”还要逐渐养成继续问一句的习惯它的时间复杂度和空间复杂度是多少有没有更优的做法二、时间复杂度不是算几毫秒而是看增长趋势时间复杂度并不是拿秒表统计一段代码具体运行了多少毫秒因为同样的代码换一台电脑、换一个编译器实际运行时间都会发生变化。真正需要分析的是当问题规模N不断增大时代码中基本操作的执行次数会按照什么趋势增长通常使用大 O 渐进表示法表示例如void Func1(int N) { int count 0; // 双层循环N*N 次 for (int i 0; i N; i) for (int j 0; j N; j) count; // 单层循环2*N 次 for (int k 0; k 2 * N; k) count; // 常数次10次 int M 10; while (M--) count; }如果比较精确地统计执行次数可以写成F(N) N² 2N 10但当N越来越大时真正起决定作用的是增长最快的N²所以最终只保留最高阶项时间复杂度O(N²)目前我把大 O 的化简先总结成三个容易记的规则与N无关的固定次数看成O(1)多项式只保留增长最快的最高阶项忽略最高阶项前面的常数系数。所以O(2N) → O(N)O(N² N 10) → O(N²)O(1000) → O(1)这里还有一个刚开始很容易看错的地方代码里出现两个for循环并不意味着一定是 O(N²)。如果两个循环是前后执行的就是N N 2N最终仍然是O(N)只有循环发生嵌套时才更可能出现N × N这样的平方级增长。2.1 最好、平均和最坏情况同一种算法面对不同输入时执行次数也可能不同。例如在长度为N的数组中顺序查找某个元素如果第一个位置就是目标只需要比较一次如果目标在最后或者根本不存在就可能需要把整个数组遍历完。因此复杂度还可以分成最好情况最少执行次数平均情况各种输入情况下的期望最坏情况最多执行次数。目前做题和学习时一般更关注最坏情况复杂度因为它给出了算法性能的一个上界。例如普通顺序查找即使最好情况下可以一次找到我们通常仍然把时间复杂度记为O(N)2.2 常见时间复杂度先建立直觉复杂度常见例子直观理解O(1)数组按下标访问数据量变化操作次数基本不变O(logN)二分查找每次排除大约一半O(N)数组遍历、链表查找数据翻倍工作量大致翻倍O(NlogN)归并排序、堆排序等常见高效排序量级O(N²)双层遍历、部分基础排序数据翻倍工作量约变四倍O(2^N)部分暴力递归数据稍大就快速增长O(N!)暴力全排列增长更快现在没必要把所有复杂度死背下来关键还是看到实际代码之后能够判断循环跑多少次有没有嵌套每次规模缩小多少三、空间复杂度重点看额外使用的空间空间复杂度同样使用大 O 表示不过它关注的不是算法一共占了多少内存而主要看为了完成算法额外使用了多少辅助空间。例如冒泡排序直接在原数组上交换只额外使用几个临时变量所以空间复杂度是O(1)如果为了处理一个长度为N的数组又额外申请了一个同样长度的数组那么辅助空间会随着N增长空间复杂度就是O(N)递归算法还要考虑递归调用栈。比如经典的暴力递归斐波那契虽然会产生大量重复计算时间复杂度可以达到O(2^N)但同一时刻函数调用栈最深大约只有N层因此它的空间复杂度是O(N)所以时间复杂度和空间复杂度不能混在一起看一个描述总共需要做多少工作一个描述运行过程中最多需要多少额外空间。四、LeetCode 练习一面试题 17.04——消失的数字题目给出一个数组nums其中包含从0到n的所有整数但缺少了一个数字需要在O(N)时间内找出缺失值。这道题我先写了第一种比较直接的方法。4.1 方法一先累加完整范围再减去已有数字我的第一版代码int missingNumber (int* nums, int numsSize) { int sum 0; for (int i 0;i numsSize; i) { sum i; } for (int j 0; j numsSize; j) { sum - nums[j]; } return sum; }思路很简单数组长度是numsSize那么完整数字范围就是0 ~ numsSize先把这个范围内所有数字全部加到sum中再依次减掉数组里真正存在的元素最后剩下的自然就是缺失的那个数字。例如[0,1,3]完整范围应该是0 1 2 3然后再减0、1、3最后只剩2这段代码有两个前后执行的循环第一个执行N1次第二个执行N次总执行量仍然和N成正比因此时间复杂度O(N)空间复杂度O(1)这里也刚好对应了前面提到的一点两个并列的 O(N) 循环加起来仍然是 O(N)而不是 O(N²)。4.2 方法二异或——又遇到了“单身狗”的思路第二种方法是int missingNumber (int* nums, int numsSize) { int n 0; for (int i 0;i numsSize; i) { n ^ i; } for (int j 0; j numsSize; j) { n ^ nums[j]; } return n; }这个思路让我想到之前做过的“只出现一次的数字”也就是我当时习惯叫的“单身狗”问题。它利用的是异或的几个性质a ^ a 00 ^ a a并且异或满足交换律和结合律。把完整的0 ~ n和数组里的所有数字全部异或一遍以后正常出现的数字都会出现两次并相互抵消最后只剩下缺失的那个数字。例如缺少20 ^ 1 ^ 2 ^ 3 ^ 0 ^ 1 ^ 3相同数字两两消掉以后 2这也是一道比较典型的“一种思想多次使用”的题。以前做单身狗时异或只是一个解题技巧这次再遇到类似结构就开始能够主动联想到之前的方法。它同样需要遍历N量级的数据时间复杂度O(N)空间复杂度O(1)除此之外还可以先给数组排序然后按照顺序逐个比较应该出现的数字和实际数字。但普通比较排序通常已经需要O(NlogN)的时间因此对于这道明确要求O(N)的题来说就不是更合适的选择了。五、LeetCode 练习二旋转数组——“能得到答案”和“解法够不够好”旋转数组要求把数组中的元素向右轮转k个位置一开始最直接的思路就是每次把最后一个元素取出来放到最前面其余元素整体向后移动一格一共重复k次。代码void rotate(int* nums, int numsSize, int k) { k k % numsSize; for (int i 0; i k; i) { int last nums[numsSize - 1]; for (int j numsSize - 1; j 0; j--) nums[j] nums[j - 1]; nums[0] last; } }这段代码逻辑完全正确但外层循环执行K次每次内层都需要移动N量级的数据因此时间复杂度O(N*K)空间复杂度O(1)当数据规模变大以后这种重复移动就会产生明显的效率问题。后来使用三次反转void Reverse(int* n, int left, int right) { while (left right) { int tmp n[left]; n[left] n[right]; n[right] tmp; left; right--; } } void rotate(int* nums, int numsSize, int k) { if (numsSize 1) return; k k % numsSize; if (k 0) return; Reverse(nums, 0, numsSize - k - 1); Reverse(nums, numsSize - k, numsSize - 1); Reverse(nums, 0, numsSize - 1); }例如[1,2,3,4,5,6,7]k 3第一步反转前四个[4,3,2,1,5,6,7]第二步反转后三个[4,3,2,1,7,6,5]第三步整体反转[5,6,7,1,2,3,4]虽然代码里调用了三次Reverse但总处理的数据量仍然只是N的常数倍所以时间复杂度O(N)空间复杂度O(1)这道题也是我这次学习复杂度之后感受最明显的一题暴力解法不是错而是还可以继续优化。以前看到输出正确可能就停下来了现在会开始继续想这份代码在大数据下还行不行六、课程补充老师再次强调二分查找我又重新写了一遍二分查找之前已经接触过所以这次不算是因为学习数据结构又重新学习了一遍。课程讲到复杂度之后老师又专门把它拿出来提醒尤其强调了一个非常容易写乱的问题二分查找的循环条件和边界更新必须和自己定义的搜索区间保持一致。二分查找确实非常快如果有大约十亿个已经排好序的数据每次比较之后都可以排除一半那么最多只需要大约 30 次比较就可以把范围缩小到一个元素。这也是O(logN)和普通O(N)顺序查找最直观的差别。不过数组上的二分查找也有明显的使用前提数据需要有序并且适合随机访问。后面课程还会继续学习二叉搜索树、红黑树以及 B 树等结构它们会从不同角度解决动态数据查找、插入和删除等问题。因为老师这次又强调了边界问题所以我也重新写了一遍并且相比之前稍微正式一些把它拆成Binary Search.hBinary Search.ctest.c三个文件。6.1 Binary Search.h#pragma once #define _CRT_SECURE_NO_WARNINGS #includestdio.h typedef int Typedata; Typedata BinarySearch(Typedata* arr,Typedata n,Typedata x);6.2 Binary Search.c#includeBinary Search.h //左闭右闭方法 Typedata BinarySearch(Typedata* arr, Typedata n,Typedata x) { int left 0; int right n - 1; while (left right) { int mid left ((right - left) / 2); if (x arr[mid]) { right mid - 1; } else if (x arr[mid]) { left mid 1; } else { return mid;//找到了返回下标 } } return -1;//没找到返回-1 } //左闭右开方法 //Typedata BinarySearch(Typedata* arr, Typedata n, Typedata x) //{ // int left 0; // int right n;//右开区间 // while (left right) // { // int mid left (right - left) / 2; // if (x arr[mid]) // { // right mid; // } // else if (x arr[mid]) // { // left mid 1; // } // else // { // return mid;//找到了返回下标 // } // } // return -1;//没找到返回-1 //}这里实际使用的是左闭右闭[left,right]。既然right本身属于搜索范围那么初始化就应该right n - 1当left right时区间里仍然还有一个元素所以循环条件必须是left right如果已经判断x arr[mid]那么mid自己也已经不可能是答案因此新的区间应该变成[left, mid - 1]也就是right mid - 1。第二种注释掉的写法则是左闭右开[left,right)。因为right本来就不包含在有效区间里所以初始化成right n循环使用left right当需要排除mid右侧时则直接right mid这次老师重新提醒之后我感觉二分最核心的其实不是背哪一种代码而是先定义区间再让整个代码从头到尾遵守同一套规则。、、mid - 1、mid并不是可以随便组合的它们都和区间的开闭状态对应。6.3 test.c#includeBinary Search.h int main() { Typedata arr[10] { 0,1,3,5,9,11,16,19,30,66 }; Typedata num (sizeof arr)/(sizeof arr[0]); int n 0; //scanf(%d,n); Typedata m BinarySearch(arr,num,n); if (m -1) { printf(No found!); } else { printf(Found it!\nsubscript is %d, m); } return 0; }相比一个文件里直接把函数和main全部写在一起这次继续沿用了前面数据结构学习时的习惯把接口声明、功能实现和测试代码分开。虽然二分查找本身代码并不长但这样写也算是继续练习更规范的代码组织方式。另外中间位置继续写成int mid left ((right - left) / 2);而不是(left right) / 2这样可以避免极端情况下left right先发生整数溢出也是老师讲二分时比较值得记住的细节。二分查找最终时间复杂度O(logN)空间复杂度O(1)。七、把这次内容放到一起看这次真正练习的内容其实不算多但刚好能够把几种复杂度对应到真实代码上内容时间复杂度空间复杂度主要收获消失的数字——累加减法O(N)O(1)两个并列循环仍然是 O(N)消失的数字——异或O(N)O(1)联系之前“单身狗”题的异或思想排序后查缺失值通常O(NlogN)视排序而定能做但不满足本题 O(N) 的目标旋转数组——暴力移动O(N*K)O(1)正确解法也可能效率不足旋转数组——三次反转O(N)O(1)用算法减少重复操作二分查找O(logN)O(1)区间定义和边界更新必须统一以前看到这些O(N)、O(logN)更像是在记概念现在开始逐渐能把它们和代码对应起来。尤其是两个地方印象比较深一是两个并列循环不等于 O(N²)二是代码能得到正确答案也不代表它已经是一个足够好的解法。八、写在最后从顺序表、单链表再到双向循环链表前面一段时间我写代码时关注的重点一直是“结构有没有写对”。进入复杂度之后开始多了一层新的判断写对之后它的效率怎么样消失的数字让我重新用到了之前“单身狗”的异或思想也第一次比较明确地把两个并列循环和O(N)联系起来旋转数组则让我真正看到暴力解和优化解之间的效率差距。二分查找算是这节课后额外的一次复习。不是第一次接触但老师再次强调开闭区间之后我重新写了一遍也把代码拆成三个文件。相比第一次只是“会写二分”这次更关注为什么是、为什么要-1、什么时候又应该直接写right mid。目前复杂度还只是刚刚入门但我觉得自己的思考方式已经开始发生一点变化。以前是这个代码怎么写出来现在会在后面再补一句写出来以后它还能不能更好后面继续学习栈、队列、树以及更多算法时也准备把复杂度分析逐渐变成每次写代码后的固定步骤而不是只在专门学复杂度的时候才去计算。完整练习代码已经上传至 Gitee 数据结构/数据结构练习一复杂度模块 · Luminous/Code_2026 - 码云 - 开源中国