从 T(N) 到大 O：时间与空间复杂度分析及旋转数组的三种方案

从 T(N) 到大 O时间与空间复杂度分析及旋转数组的三种方案从 T(N) 到大 O时间与空间复杂度分析及旋转数组的三种方案1. 阅读前问题卡算法复杂度1.1 阅读前先看这几个问题1.2 读完后完成这 3 道高频问题1.3 自检清单2. 前言2.1 数据怎样摆放处理步骤怎样安排2.2 比较工作量的增长也看输入落在哪里2.3 为减少挪动借用空间或在原处调整3. 课程介绍4. 数据结构前言4.1 数据结构4.2 算法4.3 数据结构和算法的重要性4.4 如何学好数据结构和算法4.5 书籍推荐5. 算法效率5.1 复杂度的概念5.2 复杂度的重要性6. 时间复杂度6.1 大 O 的渐进表示法6.2 时间复杂度计算示例6.2.1 示例 1Func26.2.2 示例 2Func36.2.3 示例 3Func46.2.4 示例 4strchr6.2.5 示例 5BubbleSort6.2.6 示例 6func56.2.7 示例 7Fac7. 空间复杂度7.1 空间复杂度计算示例7.1.1 示例 1BubbleSort7.1.2 示例 2Fac8. 常见复杂度对比9. 复杂度算法题9.1 旋转数组1. 阅读前问题卡算法复杂度建议先读第 5、6 节的复杂度定义与大 O 推导再用第 7、9 节对照空间分析和旋转数组方案。1.1 阅读前先看这几个问题数据结构与算法分别描述什么文中的顺序表、链表等内容与算法是什么关系旋转数组的逐次移动代码为什么引出效率问题时间复杂度和空间复杂度各衡量什么为什么文中用基本操作次数T(N)而不是一次运行的秒数评估算法怎样从N^2 2N 10得到大 OFunc2、Func4、func5和递归Fac的循环或调用方式分别怎样影响时间复杂度strchr和BubbleSort的最好、平均、最坏情况如何区分文中通常关注哪一种为什么BubbleSort与递归Fac的额外空间复杂度不同旋转数组的三种方案分别怎样移动数据或借用额外空间逆置方案如何得到目标顺序1.2 读完后完成这 3 道高频问题1.2.1 高频问题 1请说明如何从基本操作次数T(N)推导算法的时间复杂度并解释时间复杂度与空间复杂度各自衡量什么。1.2.2 高频问题 2为什么strchr和BubbleSort会出现最好、平均或最坏情况使用大 O 分析时文中通常关注哪种情况1.2.3 高频问题 3旋转数组的三种方案在操作方式和额外空间使用上有什么区别三次逆置方案如何得到旋转后的顺序1.3 自检清单我能区分数据结构的组织方式与算法的输入、步骤和输出。我能解释为何一次实测耗时不足以代表算法的增长趋势。我能由T(N) N^2 2N 10推得O(N^2)并说明大 O 的简化规则。我能根据常数循环、线性循环、倍增循环和递归调用判断文中示例的时间复杂度。我能用strchr或BubbleSort说明最好、平均、最坏情况及文中的关注重点。我能说明BubbleSort与Fac的额外空间来源以及旋转数组三种方案的取舍。2. 前言2.1 数据怎样摆放处理步骤怎样安排仓库收进一批物品先决定按什么关系摆放随后才谈收到订单时怎样逐步取出并交付。摆放方式和处理步骤相互配合但回答的是两个问题。对应到正文数据结构描述数据如何存储、组织以及元素之间的关系算法描述如何把输入经过一系列计算步骤变成输出。顺序表、链表、树等属于前一个问题。后面的复杂度分析则要考察处理步骤需要多少时间和额外空间。2.2 比较工作量的增长也看输入落在哪里两个人整理同样数量的物品所用钟表时间会受工具和环境影响。若要比较办法本身可以先数关键动作物品数量增加时动作次数是按固定量、按数量还是按数量的平方增长对应到算法输入规模是N基本操作次数用T(N)表示大 O 保留主要增长量级让比较不依赖某次运行的秒数。增长量级之外输入的位置也会改变实际步骤。找一件物品第一处就找到与最后一处才找到检查次数不同。正文的strchr用这种差别说明最好、平均、最坏情况带有提前结束判断的BubbleSort也分别讨论有序与逆序输入。2.3 为减少挪动借用空间或在原处调整搬动一排箱子时可以反复把末尾箱子移到开头也可以先借一块空地暂存再按目标位置放回还可以在原处依次翻转箱子的顺序。对应到旋转数组正文依次给出逐次移动、新数组和三次逆置新数组占用随元素数量增长的额外空间逆置方案只使用常数级额外空间。额外空间还可能来自调用过程。一个人把问题交给下一人自己等候答复如果层层转交等候者会累积。对应到递归Fac每层调用占用一个栈帧调用层数随N增长。它与旋转数组借新数组属于不同的空间来源读空间复杂度时要分开看。3. 课程介绍比特数据结构课程分为初阶数据结构和高阶数据结构当前课程是数据结构初阶。初阶课程将学习顺序表、链表、栈和队列、二叉树、常见排序算法等内容高阶数据结构后续将以录播形式上传到班级课程中。初阶数据结构继续使用 C 语言实现基础数据结构在掌握数据结构的同时巩固刚结束的 C 语法知识。图、哈希表、红黑树等数据结构将在 C 课程中学习。4. 数据结构前言4.1 数据结构数据结构Data Structure是计算机存储、组织数据的方式指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用因此要学习线性表、树、图、哈希等不同的数据结构。4.2 算法算法Algorithm是定义良好的计算过程它以一个或一组值为输入产生一个或一组值作为输出。简单来说算法是一系列将输入数据转化为输出结果的计算步骤。4.3 数据结构和算法的重要性校园招聘笔试必考校园招聘面试必考。4.4 如何学好数据结构和算法秘诀 1死磕代码秘诀 2画图、画图、画图 思考。4.5 书籍推荐书籍作者推荐理由《数据结构》严蔚敏C 语言版本内容详尽代码规整各大院校指定教材。《数据结构》殷人昆C 版本内容详尽代码规整。《算法导论》Thomas H. Cormen托马斯·科尔曼叙述严谨内容全面深入讨论各类算法。《大话数据结构》程杰趣味易读算法讲解细致深刻。5. 算法效率如何衡量一个算法的好坏以旋转数组为例思路是循环k次每次将数组所有元素向后移动一位。C复制voidrotate(int*nums,intnumsSize,intk){while(k--){intendnums[numsSize-1];for(intinumsSize-1;i0;i--){nums[i]nums[i-1];}nums[0]end;}}代码点击执行可以通过然而点击提交却无法通过。该如何衡量其好与坏5.1 复杂度的概念算法编写成可执行程序后运行时需要耗费时间资源和空间内存资源。因此衡量算法的好坏一般从时间和空间两个维度入手即时间复杂度和空间复杂度。时间复杂度主要衡量算法的运行快慢空间复杂度主要衡量算法运行所需要的额外空间。在计算机发展的早期存储容量很小因此很在乎空间复杂度。随着存储容量提高文中认为如今不需要再特别关注算法的空间复杂度。5.2 复杂度的重要性复杂度在校招中的考察已经很常见如下图6. 时间复杂度在计算机科学中算法的时间复杂度是函数式T(N)用于定量描述算法的运行时间。时间复杂度衡量程序的时间效率为什么不直接计算程序运行时间程序运行时间与编译环境有关。同一算法在同一台机器上使用不同编译器编译运行时间可能不同。程序运行时间与机器配置有关。同一算法在不同配置的机器上运行时间可能不同。程序写好后才能实测运行时间无法在写程序前通过理论计算评估。T(N)计算程序的执行次数。程序编译后生成二进制指令运行时由 CPU 执行。 文中假设每句指令的执行时间基本相同实际虽有差别但很小据此用执行次数代表时间效率以脱离具体编译运行环境。例如算法 a 的T(N) N算法 b 的T(N) N^2随着N增大前者的增长量级低于后者。以下示例计算Func1中count的执行次数C复制voidFunc1(intN){intcount0;for(inti0;iN;i){for(intj0;jN;j){count;}}intM10;while(M--){count;}for(intk0;k2*N;k){count;}}Func1的基本操作次数为T(N) N^2 2N 10N 10时T(N) 130N 100时T(N) 10210N 1000时T(N) 1002010。当N不断增大时影响最大的是N^2项。精确计算每条指令的执行次数既麻烦意义也不大比较算法只需关注增长量级。因此复杂度通常使用大 O 的渐进表示法。6.1 大 O 的渐进表示法大 O 符号Big O notation用于描述函数的渐进行为。推导大 O 阶的规则对时间复杂度函数式T(N)只保留最高阶项去掉低阶项。N不断变大时低阶项对结果的影响越来越小。如果最高阶项存在且系数不是 1去掉这一项的常数系数。N不断变大时系数对增长量级的影响越来越小。如果T(N)没有与N相关的项只有常数项用常数 1 取代所有加法常数。按上述方法Func1的时间复杂度为O(N^2)。6.2 时间复杂度计算示例6.2.1 示例 1Func2C复制// 计算 Func2 的时间复杂度voidFunc2(intN){intcount0;for(intk0;k2*N;k){count;}intM10;while(M--){count;}printf(%d\n,count);}Func2的基本操作次数为T(N) 2N 10时间复杂度为O(N)。6.2.2 示例 2Func3C复制// 计算 Func3 的时间复杂度voidFunc3(intN,intM){intcount0;for(intk0;kM;k){count;}for(intk0;kN;k){count;}printf(%d\n,count);}Func3的基本操作次数为T(N) M N。6.2.3 示例 3Func4C复制// 计算 Func4 的时间复杂度voidFunc4(intN){intcount0;for(intk0;k100;k){count;}printf(%d\n,count);}Func4的基本操作次数为T(N) 100时间复杂度为O(1)。6.2.4 示例 4strchrC复制// 计算 strchr 的时间复杂度constchar*strchr(constchar*str,intcharacter){constchar*p_begins;while(*p_begin!character){if(*p_begin\0)returnNULL;p_begin;}returnp_begin;}strchr的基本操作次数按目标字符所在位置区分在字符串第一个位置T(N) 1在字符串最后一个位置T(N) N在字符串中间位置T(N) N/2。因此最好情况为O(1)最坏情况为O(N)平均情况为O(N)。6.2.5 示例 5BubbleSort有些算法存在最好、平均和最坏情况最坏情况任意输入规模的最大运行次数上界。平均情况任意输入规模的期望运行次数。最好情况任意输入规模的最小运行次数下界。大 O 的渐进表示法在实际中一般关注算法的上界也就是最坏运行情况。C复制// 计算 BubbleSort 的时间复杂度voidBubbleSort(int*a,intn){assert(a);for(size_tendn;end0;--end){intexchange0;for(size_ti1;iend;i){if(a[i-1]a[i]){Swap(a[i-1],a[i]);exchange1;}}if(exchange0)break;}}BubbleSort的基本操作次数若数组有序则T(N) N。若数组为降序则T(N) N × (N 1) / 2。因此BubbleSort的时间复杂度取最差情况为O(N^2)。6.2.6 示例 6func5C复制voidfunc5(intn){intcnt1;while(cntn){cnt*2;}}当n 2时执行次数为 1当n 4时为 2当n 16时为 4。设执行次数为x则2^x nx log_2 n。因此func5的时间复杂度为O(log n)。课件和书籍中有log_2 n、lg n等写法。n接近无穷大时底数大小对增长量级影响不大因此可以省略底数写成log n。这里建议使用log n。6.2.7 示例 7FacC复制// 计算阶乘递归 Fac 的时间复杂度longlongFac(size_tN){if(0N)return1;returnFac(N-1)*N;}调用一次Fac的时间复杂度为O(1)Fac中存在N次递归调用因此阶乘递归的时间复杂度为O(N)。7. 空间复杂度空间复杂度也是一个数学表达式用于描述算法运行过程中因算法需要而额外临时开辟的空间。它不是程序占用了多少 bytes 的空间文中认为常规情况下每个对象的大小差异不大因此按变量的个数分析空间复杂度并同样使用大 O 渐进表示法。文中指出函数运行所需的栈空间存储参数、局部变量、寄存器信息等在编译期间已经确定因此空间复杂度主要通过函数运行时显式申请的额外空间来确定。7.1 空间复杂度计算示例7.1.1 示例 1BubbleSortC复制// 计算 BubbleSort 的空间复杂度voidBubbleSort(int*a,intn){assert(a);for(size_tendn;end0;--end){intexchange0;for(size_ti1;iend;i){if(a[i-1]a[i]){Swap(a[i-1],a[i]);exchange1;}}if(exchange0)break;}}函数栈帧在编译期间已经确定。BubbleSort额外申请了exchange等有限个局部变量使用常数个额外空间因此空间复杂度为O(1)。7.1.2 示例 2FacC复制// 计算阶乘递归 Fac 的空间复杂度longlongFac(size_tN){if(N0)return1;returnFac(N-1)*N;}Fac递归调用了N次额外开辟了N个函数栈帧每个栈帧使用常数个空间因此空间复杂度为O(N)。8. 常见复杂度对比9. 复杂度算法题9.1 旋转数组旋转数组题目思路 1循环k次将数组所有元素向后移动一位代码不通过。文中标注的时间复杂度为O(n^2)。C复制voidrotate(int*nums,intnumsSize,intk){while(k--){intendnums[numsSize-1];for(intinumsSize-1;i0;i--){nums[i]nums[i-1];}nums[0]end;}}思路 2申请新数组。先将后k个数据放到新数组中再将剩下的数据挪到新数组中。空间复杂度为O(n)。C复制voidrotate(int*nums,intnumsSize,intk){intnewArr[numsSize];for(inti0;inumsSize;i){newArr[(ik)%numsSize]nums[i];}for(inti0;inumsSize;i){nums[i]newArr[i];}}思路 3三次逆置。空间复杂度为O(1)。前n-k个逆置4 3 2 1 | 5 6 7后k个逆置4 3 2 1 | 7 6 5整体逆置5 6 7 1 2 3 4。C复制voidreverse(int*nums,intbegin,intend){while(beginend){inttmpnums[begin];nums[begin]nums[end];nums[end]tmp;begin;end--;}}voidrotate(int*nums,intnumsSize,intk){kk%numsSize;reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-1);}10.回答问题卡的问题问题 1数据结构与算法分别描述什么文中的顺序表、链表等内容与算法是什么关系答数据结构是计算机存储组织数据的方式指相互之间存在一种或多种特定关系的数据元素的集合。算法是定义良好的计算过程它以一个或一组值为输入。是一系列将输入数据转化为输出结果的计算步骤顺序表、链表是组织数据的数据结构算法是处理数据的步骤问题 2旋转数组的逐次移动代码为什么引出效率问题时间复杂度和空间复杂度各衡量什么答因为代码点击执行可以通过点击提交却无法通过而且逐次移动太慢了每次旋转都要移动整个数组重复k次就反复k次遍历数组时间复杂度主要衡量算法的运行快慢空间复杂度主要衡量算法运行所需要的额外空间问题 3为什么文中用基本操作次数T(N)而不是一次运行的秒数评估算法怎样从N^2 2N 10得到大 O答程序运行时间和编译环境机器配置有关而且要程序写好后才能实测运行时间无法在写程序前通过理论计算评估。对T(N) N^2 2N 10去掉增长影响较小的低阶项2N和常数项10保留最高阶的N^2得到O(N^2)。如果最高阶项还有常数系数也要去掉如果只有常数项则记为O(1)。问题 4Func2、Func4、func5和递归Fac的循环或调用方式分别怎样影响时间复杂度答Func2的基本操作次数为T(N) 2N 10时间复杂度为O(N)。循环随N线性增长Func4基本操作次数为T(N) 100固定循环100次时间复杂度为O(1)。设执行次数为xfunc5的时间复杂度为O(log n)n接近无穷大时底数大小对增长量级影响不大因此可以省略底数写成log n。这里建议使用log n每轮倍增调用一次Fac的时间复杂度为O(1)Fac中存在N次递归调用每次递归把N减1直到终止条件因此阶乘递归的时间复杂度为O(N)。问题 5strchr和BubbleSort的最好、平均、最坏情况如何区分文中通常关注哪一种答strchr找的字符若在开头只查一次最好情况为O(1)若接近结尾要查约N次最坏情况为O(N)中间位置为N/2则平均情况为O(N)。BubbleSort最好情况即数组已按顺序排列比较一趟便结束文中记为T(N) N即O(N)。最坏情况是降序输入要进行多趟比较文中记为T(N) N(N1)/2即O(N^2)。平均情况指同一规模下不同输入的期望运行次数。文中说用大 O 分析时一般关注上界也就是最坏运行情况。问题 6为什么BubbleSort与递归Fac的额外空间复杂度不同答BubbleSort额外申请了exchange等有限个局部变量使用常数个额外空间因此空间复杂度为O(1)。Fac递归调用了N次额外开辟了N个函数栈帧每个栈帧使用常数个空间因此空间复杂度为O(N)。问题 7旋转数组的三种方案分别怎样移动数据或借用额外空间逆置方案如何得到目标顺序答逐次移动是循环k次每次暂存末尾元素将其余元素都向后挪一位再把暂存元素放到开头只用常数个临时变量但要反复移动数组。使用额外数组借O(n)额外空间新建一个和原数组等长的数组temp对原数组每个位置i把它放到旋转后的位置(ik)%n最后把新数组复制回原数组。三次逆置只用常数级额外空间先逆置前n-k个再逆置后k个最后逆置整个数组。以1 2 3 4 | 5 6 7右旋 3 位为例前两次得到4 3 2 1 | 7 6 5整体逆置后就是5 6 7 1 2 3 4。高频问题 1请说明如何从基本操作次数T(N)推导算法的时间复杂度并解释时间复杂度与空间复杂度各自衡量什么。答先用T(N)表示输入规模为N时基本操作执行多少次再用大 O 只保留增长最快的项去掉低阶项和最高阶项的常数系数若只有常数项就写O(1)。例如N^2 2N 10得到O(N^2)。这样比较的是工作量随规模增长的趋势不依赖一次实测耗时。时间复杂度衡量运行工作量的增长空间复杂度衡量运行过程中需要的额外空间怎样随规模增长。高频问题 2为什么strchr和BubbleSort会出现最好、平均或最坏情况使用大 O 分析时文中通常关注哪种情况答同样规模的输入内容和排列顺序不同实际执行次数就可能不同。strchr找的字符在开头、中间或末尾检查次数不同所以文中分别得到最好O(1)、平均O(N)、最坏O(N)。BubbleSort遇到有序数组一趟后就能结束为O(N)遇到降序数组则需要多趟比较最坏为O(N^2)。平均情况看不同输入的期望运行次数。文中说用大 O 分析时通常关注最坏情况也就是运行次数的上界。高频问题 3旋转数组的三种方案在操作方式和额外空间使用上有什么区别三次逆置方案如何得到旋转后的顺序答逐次移动要做k轮每轮把整个数组向后挪一位只借用常数个临时变量但反复搬动数据。新数组方案开辟长度为n的空间把每个元素放到旋转后的下标再复制回原数组额外空间是O(n)。三次逆置在原数组中交换元素额外空间是O(1)。三次逆置先翻转前n-k个再翻转后k个最后翻转整体。前两步分别颠倒了两段内部顺序最后一步既交换两段的位置又恢复各段原有顺序。比如1 2 3 4 | 5 6 7右旋 3 位结果是5 6 7 1 2 3 4。