目录一 算法效率1、复杂度的概念二 时间复杂度1、大O的渐进表示法2、时间复杂度计算示例三 空间复杂度1、空间复杂度计算示例四 常见复杂度对比五 复杂度算法题1、旋转数组六 线性表七 顺序表1、概念与结构2、分类3、动态顺序表实现4、顺序表算法题一、算法效率1、复杂度的概念算法在编写成可执行程序后运行时需消耗时间资源和空间资源。因此衡量一个算法的好坏一般是从空间和时间两个维度衡量的即为时间复杂度、空间复杂度。时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需的额外空间。二、时间复杂度由于执行每条指令的时间基本一样所以执行次数和运行时间就是等比正相关。指令的执行次数就可以代表程序时间效率的优劣。例如下面的程序计算一下count语句一共执行了多少次。voidfunc(intN){intcount0;for(int-0;iN;i){for(intj0;jn;j){count;}}for(intk0;k2*N;k){count;}intM10;while(M--){count;}}func执行的基本操作次数TNN^22*N10;N10时TN130N100时TN10210N1000时TN1002010实际我们计算时间复杂度时计算的也不是程序的精确执行次数当我们只想比较算法程序的增长量级时就只需要计算程序能代表增长量级的大概执行次数复杂度的表示通常使用大O渐进表示法。1、大O渐进表示法推导大O阶规则时间复杂度函数式TN中只保留最高阶项如果最高阶项系数存在且不是1则去除这个常数系数TN中如果没有N相关的项只有常数项用常数1取代所有加法常数2、时间复杂度计算示例示例1voidfunc(intN){intcount0;for(intk0;k2*N;k){count;}intM10;while(M--){count;}}func执行的基本操作次数TN2*N10根据第三条规则推出func的时间复杂度为ON示例2voidfunc1(intN,intM){intcount0;for(intk0;kM;k){count;}for(intk0;kN;k){count;}coutcount;}func1执行的基本操作次数TNMNfunc1的时间复杂度ON示例3voidfunc2(intN,intM){intcount0;for(intk0;k100;k){count;}coutcount;}func2的基本操作次数TN100根据第一条规则得出func2的时间复杂度O1示例4constchar*strchr(constchar*str,intcha){constchar*pstr;while(*p!cha){if(*p\0)returnnullptr;p;}returnp;}在最好情况时函数内部循环执行一次就可以结束而当遇到最坏情况时循环需要执行n次才能结束。大O的渐进表示法在实际中一般情况关注的是·算法的上界也就是最坏运行情况。示例5voidbubble_sort(int*arr,intsz){for(intisz-1;i0;i--){intflag0;for(intj0;ji;j){if(arr[j]arr[j1]){flag1;inttmparr[j];arr[j]arr[j1];arr[j1]tmp;}}if(flag0)break;}}若数组有序TNN若数组为降序TNN*N-1/ 2因此冒泡排序的时间复杂度为On^2)示例6voidfun(intn){intk1;while(kcnt){k*2;}}fun函数执行次数为以2为底的n的对数次用大O渐进表示法表示为OlogN示例7intfun(inti){if(i0){return1;}elsereturnfun(i-1)*i;}阶乘递归时间复杂度为ON三、空间复杂度空间复杂度是表示算法在运行过程中因算法需要额外临时开辟的空间空间复杂度因常规情况每个对象大小差异不会很大所以空间复杂度算的是变量的个数空间复杂度也要用大O渐进表示法表示空间复杂度主要通过函数在运行时显示申请的额外空间确定算法复杂度计算示例示例1voidbubble_sort(int*arr,intsz){for(intisz-1;i0;i--){intflag0;for(intj0;ji;j){if(arr[j]arr[j1]){flag1;inttmparr[j];arr[j]arr[j1];arr[j1]tmp;}}if(flag0)break;}}函数栈帧在编译期间已经确定只需关注在运行时额外申请的空间bubble_sort只额外申请了一些局部变量使用了常数个空间因此空间复杂度为O1示例2intfun(inti){if(i0){return1;}elsereturnfun(i-1)*i;}fun函数额外开辟了n个函数栈帧每个栈帧开辟了常数个空间因此空间复杂度为ON四、常见复杂度对比五、复杂度算法题1、旋转数组添加链接描述思路一两层循环使所有元素向后移动最后一位元素放到首位这样时间复杂度为ON^2)空间复杂度为O1这种方法时间复杂度过大一旦测试数据要执行多次轮转就会超时voidrotate(int*nums,intnumsSize,intk){while(k--){inttmpnums[numsSize-1];for(intinumsSize-1;i0;i--){nums[i]nums[i-1];}nums[0]tmp;}}思路二以空间换时间先将后k个数据放进新创建的数组中再将剩下的元素挪到新数组中时间复杂度为ON空间复杂度为ONvoidrotate(int*nums,intnumsSize,intk){intnewarr[numsSize];for(inti0;inumsSize;i){newarr[(ik)%numsSize]nums[i];}for(intj0;jnumsSize;j)nums[j]newarr[j];}思路三三次逆置先将数组中前n-k个数据逆置再将最后k个数据逆置最后数组整体逆置这样时间复杂度为ON空间复杂度为O1voidreverse(int*nums,intbegin,intend){while(beginend){inttmpnums[begin];nums[begin]nums[end];nums[end]tmp;end--;begin;}}voidrotate(int*nums,intnumsSize,intk){reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-1);}六、线性表线性表是由n个具有相同特性的数据元素的有限序列是一种使用广泛的数据结构常见的线性表有顺序表、链表、栈和队列。线性表在逻辑上是线性结构但在物理结构上不一定连续通常在存储时以数组或链式结构存储。七、顺序表1、概念与结构顺序表是一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况用数组存储顺序表与数组的关系顺序表底层是数组但对数组进行了封装并增加了对数据增删查改的接口2、分类静态顺序表使用定长数组存储元素这种顺序表容易造成空间给少不够用空间给多造成浪费的问题typedefintSLDataType;#defineN10typedefstructSeqlist{SLDataType a[N];intsize;}seqlist;动态顺序表按需申请空间3、动态顺序表的实现seqlist.h:#pragmaonce#includeiostream#includecstringtypedefintSLDataType;typedefstructSeqlist{SLDataType*a;intCapacity;intsize;}seqlist;//初始化和销毁、打印顺序表voidInit(seqlist*ptr);voidDestory(seqlist*ptr);voidPrint(seqlist*ptr);//扩容voidCheckCapacity(seqlist*ptr);//头部/尾部插入删除voidpushfront(seqlist*ptr,SLDataType ele);voidpopfront(seqlist*ptr);voidpushback(seqlist*ptr,SLDataType ele);voidpopback(seqlist*ptr);//指定位置之前插入或删除voidInsert(seqlist*ptr,SLDataType ele,intpos);voidDelete(seqlist*ptr,SLDataType pos);//查找顺序表中有无待查找元素boolFind(seqlist*ptr,SLDataType ele);seqlist.cpp:#defineCRTSECURE NO WARNINGSs#includeSeqlist.h#includeiostream#includecstring#includecassertvoidInit(seqlist*ptr){ptr-a(SLDataType*)malloc(sizeof(SLDataType)*4);ptr-Capacity4;ptr-size0;}voidDestory(seqlist*ptr){free(ptr-a);ptr-anullptr;ptr-Capacity0;ptr-size0;}voidPrint(seqlist*ptr){if(!ptr-size)return;for(inti0;iptr-size-1;i){std::coutptr-a[i] ;}std::coutstd::endl;}voidCheckCapacity(seqlist*ptr){if(ptr-sizeptr-Capacity){SLDataType*tmp(SLDataType*)realloc(ptr-a,2*ptr-Capacity*sizeof(SLDataType));//通常成倍扩容if(tmp!nullptr){ptr-atmp;ptr-Capacity*2;}else{std::cout申请空间失败std::endl;exit(1);}}}voidpushfront(seqlist*ptr,SLDataType ele){CheckCapacity(ptr);ptr-size;for(intiptr-size-2;i0;i--){ptr-a[i1]ptr-a[i];}ptr-a[0]ele;}voidpopfront(seqlist*ptr){assert(ptr-size);for(inti0;iptr-size-2;i){ptr-a[i]ptr-a[i1];}ptr-size--;}voidpushback(seqlist*ptr,SLDataType ele){CheckCapacity(ptr);ptr-a[ptr-size]ele;}voidpopback(seqlist*ptr){assert(ptr-size);ptr-size--;}voidInsert(seqlist*ptr,SLDataType ele,intpos){assert(0posposptr-size);CheckCapacity(ptr);for(intiptr-size-1;ipos;i--){ptr-a[i1]ptr-a[i];}ptr-a[pos]ele;ptr-size;}voidDelete(seqlist*ptr,SLDataType pos){assert(0posposptr-size);for(intipos;iptr-size-1;i){ptr-a[i]ptr-a[i1];}ptr-size--;}boolFind(seqlist*ptr,SLDataType ele){if(!ptr-size)returnfalse;for(inti0;iptr-size;i){if(ptr-a[i]ele)returntrue;}returnfalse;}4、顺序表算法题4.1移除元素添加链接描述思路一使用顺序表查找出val值的下标删除该下标的数据思路二双指针使用dst占住为val值的位置将src位置的数据赋值给dst位置的值intremoveElement(int*nums,intnumsSize,intval){intdst0,src0;while(srcnumsSize){if(dst!src)nums[dst]nums[src];if(nums[dst]!val)dst;src;}returndst;}4.2 删除有序数组中的重复项添加链接描述思路三指针intremoveDuplicates(int*nums,intnumsSize){intp10,p21,p30;//p1,p2用来排查相同元素p3用来占住重复元素的位置if(numsSize0)return0;if(numsSize1)return1;while(p2numsSize){if(nums[p1]!nums[p2]){nums[p3]nums[p1];p1p2;}p2;}nums[p3]nums[p1];returnp3;}4.3合并两个有序数组添加链接描述这个题目描述不由得让我们想到这是归并排序的在递归中进行的一个步骤所以可以使用三指针将排好序的数组存在tmp中再挪到nums1中voidmerge(int*nums1,intnums1Size,intm,int*nums2,intnums2Size,intn){inttmp[nums1Size];intp10,p20,p30;while(p1nums1Size-nums2Sizep2nums2Size){if(nums1[p1]nums2[p2])tmp[p3]nums1[p1];elsetmp[p3]nums2[p2];}while(p1nums1Size-nums2Size)tmp[p3]nums1[p1];while(p2nums2Size)tmp[p3]nums2[p2];for(inti0;inums1Size;i)nums1[i]tmp[i];}