零、前言1.这篇文章有很多帮助理解的解释如果觉得太多太长了可以直接跳着看加粗部分。2.本篇文章有引用参考别人的资料如有雷同纯属巧合不是抄袭本文章主要是我一个新手的学习记录与思考。3.本文可能有错如果有看见错误恳请指正4.学习建议多理解多尝试。一、由一道题引入复杂度首先在介绍复杂度之前我们先看一道题189. 轮转数组 - 力扣LeetCode​对于这道题来说我们有第一种思路它不是要轮转k次也就是将最右边的那个搬到最左边搬k次吗那我们可以用一种化整为零的思想我们先看下搬一次是怎么样的再将这个过程执行k次不就达到我们的目的了吗我们可以使用for循环不断让nums[i]nums[i-1]这样除了最右边的一个数据左边的所有数据都往右移了一下。但你会发现一个小问题这样最右边的数据不就被它左边的数据覆盖了吗因此我们需要一个临时变量存储最右边的那个数据。即int tepnums[numsSize-1]。最后将nums[0]tep就把最右边的数据放在了最左边如此就完成了我们一次轮转操作。接下来轮转k次在外面套个whilek--就实现了执行k次轮转。代码如下void rotate(int* nums, int numsSize, int k) { while(k--){ int tepnums[numsSize-1]; for(int inumsSize-1;i0;i--){ nums[i]nums[i-1]; } nums[0]tep; } }当我们测试时两个用例均通过​但是当我们提交代码时,意外出现了:​有一个超出了时间限制,说明我们的代码并不完美,在面对大数据的时候不过关,那怎么降低我们的运行时间,防止它超出时间限制呢?这就要引入复杂度的概念.二、复杂度一复杂度与算法的概念查阅资料,有这样的概念:算法在编写成可执⾏程序后运⾏时需要耗费时间资源和空间(内存)资源 。因此衡量⼀个算法的好坏⼀般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。时间复杂度主要衡量⼀个算法的运⾏快慢⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。在计算机发展的早期计算机的存储容量很⼩。所以对空间复杂度很是在乎。但是经过计算机⾏业的迅速发展计算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。由于这里提到了算法,也附上算法的概念:算法(Algorithm):就是定义良好的计算过程他取⼀个或⼀组的值为输⼊并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤⽤来将输⼊数据转化成输出结果。从以上概念我们知道复杂度分为时间与空间复杂度那我们就来一一介绍二时间复杂度与空间复杂度1.时间复杂度定义在计算机科学中算法的时间复杂度是⼀个函数式T(N)它定量描述了该算法的运⾏时间。时间复杂度是衡量程序的时间效率那么为什么不去计算程序的运⾏时间呢1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系⽐如同⼀个算法程序⽤⼀个⽼编译器进⾏编译和新编译器编译在同样机器下运⾏时间不同。2. 同⼀个算法程序⽤⼀个⽼低配置机器和新⾼配置机器运⾏时间也不同。3. 并且时间只能程序写好后测试不能写程序前通过理论思想计算评估。这样让我们对算法不能事前预判好坏。那么算法的时间复杂度是⼀个函数式T(N)到底是什么呢这个T(N)函数式计算了程序的执⾏次数。通过c语⾔编译链接章节学习我们知道算法程序被编译后⽣成⼆进制指令程序运⾏就是cpu执⾏这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执⾏次数的函数式T(N)假设每句指令执⾏时间基本⼀样(实际中有差别但是微乎其微)那么执⾏次数和运⾏时间就是等⽐正相关这样也脱离了具体的编译运⾏环境。执⾏次数就可以代表程序时间效率的优劣。⽐如解决⼀个问题的算法a程序T(N) N算法b程序T(N) N^2那么算法a的效率⼀定优于算法b。所以简明扼要的说由于每条代码执行时间基本相同时间复杂度就只由执行次数决定即只关于执行次数的函数式子我们只要算代码的执行次数就行了次数越少效率越高时间越少代码越好如何计算我们拿例子来说明案例1//请计算⼀下Func1中count语句总共执⾏了多少 次 void Func1(int N) { int count 0; for (int i 0; i N ; i) { for (int j 0; j N ; j) { count; } } for (int k 0; k 2 * N ; k) { count; } int M 10; while (M--) { count; } }嵌套循环执行N*N次第二个循环执行2*N次第三个循环M为10whileM--执行10次所以总次数TNN^22N10这就是时间复杂度吗其实并不是。真正的时间复杂度是ON^2),这里有ON^2)的规则大O的渐进表示法1. 时间复杂度函数式T(N)中只保留最⾼阶项去掉那些低阶项因为当N不断变⼤时低阶项对结果影响越来越⼩当N⽆穷⼤时就可以忽略不计了。2. 如果最⾼阶项存在且不是1则去除这个项⽬的常数系数因为当N不断变⼤这个系数对结果影响越来越⼩当N⽆穷⼤时就可以忽略不计了。3. T(N)中如果没有N相关的项⽬只有常数项⽤常数1取代所有加法常数。为啥这么做原因是什么结合deepseek与我的想法1.小数据时算法的实际时间优劣可能看不出来甚至会出现“坏算法比好算法快”的反常现象。所以我们需要拉到无穷大来看——在无穷大的极限下那些常数和低次项的影响会彻底消失只剩下算法的“本质速度”。这个本质速度才是区分算法优劣的可靠标准。我们程序员毕竟不是数学家我们只要关注执行的大概量级就行了就像我们上面超出时间限制的那个大数据我们就看出来了这个算法对于大数据是不够格的。我们实际不可能都是小数据得让算法根据承受大数据的本事来分辨优劣2.时间复杂度反映的是增长的趋势像O(1) 常数时间 n 从 1 到 100 万时间不变。就像无论书架有几层你都能直接抽出一本固定位置的书。O(\log n) 对数时间 n 翻倍100→200时间只增加1步。比如查英文字典每次翻到中间扔掉一半100页和200页的查找次数差异微乎其微。O(n) 线性时间 n 翻倍时间也精确翻倍。比如逐个核对一列名单人数翻倍核对的耗时也翻倍。O(n \log n) 线性对数 n 翻倍时间比翻倍略多一点比如 1000 \to 2200 步。这是快速排序的效率。O(n^2) 平方时间 n 翻倍时间变成4倍。例如一个 100 \times 100 的网格变成 200 \times 200 格子总数变成4万原1万耗时也变成4倍。O(2^n) 指数时间 n 增加 1时间翻倍 n 增加 10时间变为约 1000倍。比如用暴力法破解10位密码比破解9位密码要多花一倍的时间。3.实际中我们计算时间复杂度时计算的也不是程序的精确的执⾏次数精确执⾏次数计算起来还是很⿇烦的(不同的⼀句程序代码编译出的指令条数都是不⼀样的)计算出精确的执⾏次数意义也不⼤因为我们计算时间复杂度只是想⽐较算法程序的增⻓量级也就是当N不断变⼤时T(N)的差别上⾯我们已经看到了当N不断变⼤时常数和低阶项对结果的影响很⼩所以我们只需要计算程序能代表增⻓量级的⼤概执⾏次数复杂度的表⽰通常使⽤⼤O的渐进表⽰法。这是一些解释供大家参考。解释完了再回到计算给大家更多计算的案例情况案例2// 计算Func3的时间复杂度 void Func3(int N, int M) { int count 0; for (int k 0; k M; k) { count; } for (int k 0; k N ; k) { count; } printf(%d\n, count); }执行次数MN对于M与N。他们两个从性质来说其实都是变量那你就可以都看成N表示变量这个大的范围所以就是2N因为2N与N在无穷大时几乎没区别都一个量级所以最后时间复杂度答案是ON。案例3计算Func4的时间复杂度 void Func4(int N) { int count 0; for (int k 0; k 100; k) { count; } printf(%d\n, count); }代码只执行了100次其实和常数是一个量级的时间复杂度写为O1这里的1表示是个常数。案例4// 计算strchr的时间复杂度 const char * strchr ( const char *str, int character) { const char* p_begin s; while (*p_begin ! character) { if (*p_begin \0) return NULL; p_begin; } return p_begin; }这是一个查找字符的代码1若要查找的字符在字符串第⼀个位置则T (N) 12若要查找的字符在字符串最后的⼀个位置则T (N) N3若要查找的字符在字符串中间位置则T (N) 2N因此strchr的时间复杂度分为最好情况 O(1)最坏情况 O(N)平均情况 O(N)这道题有些不一样了。通过上⾯我们会发现有些算法的时间复杂度存在最好、平均和最坏情况。最坏情况任意输⼊规模的最⼤运⾏次数(上界)平均情况任意输⼊规模的期望运⾏次数最好情况任意输⼊规模的最⼩运⾏次数(下界)⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界也就是最坏运⾏情况。所以时间复杂度取最坏情况ON。案例5// 计算BubbleSort的时间复杂度 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; } }冒泡排序1若数组有序那么无需交换只有一个最大的for循环则T (N) N2若数组有序且为降序endN时内层N-1次endN-1时内层N-2次一直到end2时内层1次所有次数就是等差数列求和12···N-1N-1*N/2。注为什么end1不算因为end1时内层循环i1i1;i不执行所以是无效轮相当于已经排完了则T (N) N ∗ (N - 1)/2因此BubbleSort的时间复杂度取最差情况为 O(N^2 )。案例6void func5(int n) { int cnt 1; while (cnt n) { cnt * 2; } }第1次cnt1一次后cnt2n2时只有1次第2次cnt2一次后cnt4n4时只有2次观察规律执行次数N和n的关系是2^Nn即Nlog₂nn不为2的倍数时加个取整号就行了量级是一样的这边就是log₂n了。这边当n无穷大时底数的影响可以忽略不计了所以我们这边可以把底数忽略虽然数学中不写底数不行但是计算机中可以。所有我们的时间复杂度为Ologn。案例7// 计算阶乘递归Fac的时间复杂度 long long Fac(size_t N) { if(0 N) return 1; return Fac(N-1)*N;}记住公式递归的时间复杂度单次递归的时间复杂度*递归次数这里单次递归代码只运行一次没有循环所以单次递归复杂度为O(1),递归次数我们举个例子来理解比如求55*Fac44*Fac3,3*Fac22*Fac11*Fac00N结束递归5递归5次那N递归N次所以递归时间复杂度为O1*ONON。可能有的小疑惑我们这些函数它里面不止有循环还有一些赋值语句等比如int i0这些要算入执行次数吗?其实是要算的只是它们都是有限行代码也就是常数个代码在N^2那些量级上不值一提就不用考虑了。占大头的还是我们的循环。2.空间复杂度1.定义空间复杂度也是⼀个数学表达式是⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占⽤了多少bytes的空间因为常规情况每个对象⼤⼩差异不会很⼤所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使⽤⼤O渐进表⽰法。注意函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定。定义有点难懂我们简单解释概括一下。简单的来说空间复杂度 算法内部新申请的局部变量 动态开辟的空间再套大O化简。具体分两类1. 新局部变量基本就是除形参外新创造的局部变量固定个数 → O(1)例如int i;、int sum;、int temp;2. 新申请的空间大小随n变化 → O(n) / O(n²) 等例如malloc(n * sizeof(int))、递归调用的n层栈帧什么要被算入空间复杂度呢1.输入参数形参不算例如 int func(int arr[], int n) 中的 arr 和 n它们属于“输入本身”不是算法额外申请的临时空间。2. 函数内部创造的算包括◦ 普通新创造的局部变量 int i;◦ 局部数组 int temp[100];◦ 动态申请的内存 malloc(n * sizeof(int))◦ 递归调用中每一层的局部变量我们做题分析就看下新局部变量和新申请的空间就行了。我们讲一些案例来辅助理解吧。案例1// 计算BubbleSort的空间复杂度 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; } }函数栈帧在编译期间已经确定好了只需要关注函数在运⾏时额外申请的空间。BubbleSort额外申请的空间有exchange等有限个局部变量使⽤了常数个额外空间因此空间复杂度为 O(1)。案例2//计算阶乘递归Fac的空间复杂度 long long Fac(size_t N) { if(N 0) return 1; return Fac(N-1)*N; }递归空间复杂度单次递归空间复杂度*递归次数单次没创造新变量吧那就是常数个O1递归次数上面案例7讲过N次所以这个的空间复杂度就是O1*NON。案例3void func(int n) { int *p (int*)malloc(n * sizeof(int)); // 局部变量p只占1个指针大小O(1) // 但malloc申请了 n 个 int 空间O(n) } // 空间复杂度是 O(n)因为malloc的空间才是大头开辟n个空间注释解释的很清楚了空间复杂度就是ON。三复杂度对比这里附上一张图像来说明豆包ai生成大概了解一下量级差别即可。三、回到最开始那道题我们不是时间太长了吗我们原来的代码是void rotate(int* nums, int numsSize, int k) { while(k--){ int tepnums[numsSize-1]; for(int inumsSize-1;i0;i--){ nums[i]nums[i-1]; } nums[0]tep; } }执行次数是k*numsSize-1k*numsSize-k因为knumsSize都是变量所以统称为N就是N^2-N,时间复杂度就是ON^2。复杂度这么大的确用时很长我们要把时间复杂度给他降下来。方法2那怎么做呢你复杂度不是由嵌套循环引起的吗那我们就减少循环我们可以这样再创造一个数组把原数组的内容搬到新数组上然后运用循环把新数组的内容再搬回原数组就行了。因为题目要的还是nums原数组。具体怎么操作呢我们举例子来理解我画了个图仔细观察下标关系k3左边四个就右移3下就是arr[ik]nums[i]这个过程循环4次那么一般化来看就是循环numsSize-k次总个数-移出去的就是剩下的个数不难理解。那右边3个呢下标4,5,6到0,1,2。仔细观察一下就可以知道运算关系其实就是ik%numsSize43%70,53%71,63%72。想不到的话积累一下这个思路即可记住这种数组轮转的运算关系是取余。当然取余对于左边四个关系仍然成立03%7313%74数字1从下标0到下标3数字2从下标1到下标4成立吧。那么我们只要遍历原数组一个一个根据我们观察的运算关系把数据搬去新数组就行了。代码如下void rotate(int* nums, int numsSize, int k) { int arr[numsSize]; int i0; for(i0;inumsSize;i){ arr[(ik)%numsSize]nums[i]; } for(i0;inumsSize;i){ nums[i]arr[i]; } }测试与提交均通过循环2*numsSize次即2*N次这里我们的时间复杂度是ON创建了一个同样空间大小的新数组还有局部变量i空间复杂度是ON。时间复杂度降低了能不能再降一下空间复杂度呢方法3新奇思路这个思路可能想不到积累即可。我们可以逆置3次。同样举例说明一下啥是逆置。我们神奇的发现这都行。以前四个为例将一下怎么实现我们需要两个指针指向最开始和最末尾left和right把left和right的数据对调完成一次left右移1下right左移一下。用whileleftright控制过程。有没有回想起两个数交换怎么写需要一个临时变量tep实现。然后我们一般化的范围是啥呢第一次逆置轮转k次左边剩下的元素共有numsSize-k个元素那left0rightnumsSize-k-1。第二次逆置本该出去的元素k个其实就是上一个的right的右边一个到最后结束。leftnumsSize-krightnumsSize-1。最后一次逆置所有从最开始到最末就行left0rightnumsSize-1。那我们代码实现一下void reverse(int* nums,int left,int right){ while(leftright){ int tep0; tepnums[left]; nums[left]nums[right]; nums[right]tep; left; right--; } } void rotate(int* nums, int numsSize, int k) { reverse(nums,0,numsSize-k-1); reverse(nums,numsSize-k,numsSize-1); reverse(nums,0,numsSize-1); }但是这个代码是错误的你k的范围可是0到10^5超过numsSize怎么办那你就kk%numsSize这样就解决了因为比如数组7个元素它转了8次和转一次是一样的这样就防止numsSize出现小于0的情况。正确代码void reverse(int* nums,int left,int right){ while(leftright){ int tep0; tepnums[left]; nums[left]nums[right]; nums[right]tep; left; right--; } } void rotate(int* nums, int numsSize, int k) { kk%numsSize; reverse(nums,0,numsSize-k-1); reverse(nums,numsSize-k,numsSize-1); reverse(nums,0,numsSize-1); }这个新代码的执行次数为N/2N/2N/23N/2,时间复杂度为ON空间复杂度只创造了tep有限个局部变量空间复杂度为O1。空间复杂度也降下来了提交与测试全部通过。至此最开始的题目被解决复杂度也顺便讲完了写代码时遇到的小困难小经验写这个的时候在力扣上答题的有时候明明代码正确但是还是不对一定一定检查一下有没有用中文的标点符号因为我是边写文章边打代码有时候混用了就错了一定一定要注意。