数据结构——算法复杂度顺序表

目录
一 算法效率
1、复杂度的概念
二 时间复杂度
1、大O的渐进表示法
2、时间复杂度计算示例
三 空间复杂度
1、空间复杂度计算示例
四 常见复杂度对比
五 复杂度算法题
1、旋转数组
六 线性表
七 顺序表
1、概念与结构
2、分类
3、动态顺序表实现
4、顺序表算法题

一、算法效率
1、复杂度的概念
算法在编写成可执行程序后，运行时需消耗时间资源和空间资源。因此衡量一个算法的好坏一般是从空间和时间两个维度衡量的，即为时间复杂度、空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需的额外空间。
二、时间复杂度
由于执行每条指令的时间基本一样，所以执行次数和运行时间就是等比正相关。指令的执行次数就可以代表程序时间效率的优劣。例如下面的程序，计算一下++count语句一共执行了多少次。

voidfunc(intN){intcount=0;for(int-0;i<N;i++){for(intj=0;j<n;j++){++count;}}for(intk=0;k<2*N;k++){++count;}intM=10;while(M--){++count;}}

func执行的基本操作次数：
T（N）=N^2+2*N+10;

• N=10时T（N）=130
• N=100时T（N）=10210
• N=1000时T（N）=1002010

实际我们计算时间复杂度时，计算的也不是程序的精确执行次数，当我们只想比较算法程序的增长量级时，就只需要计算程序能代表增长量级的大概执行次数，复杂度的表示通常使用大O渐进表示法。
1、大O渐进表示法

推导大O阶规则

• 时间复杂度函数式T（N）中，只保留最高阶项
• 如果最高阶项系数存在且不是1，则去除这个常数系数
• T（N）中如果没有N相关的项，只有常数项，用常数1取代所有加法常数

2、时间复杂度计算示例
示例1：

voidfunc(intN){intcount=0;for(intk=0;k<2*N;k++){++count;}intM=10;while(M--){++count;}}

func执行的基本操作次数：
T（N）=2*N+10
根据第三条规则推出：func的时间复杂度为O（N）

示例2：

voidfunc1(intN,intM){intcount=0;for(intk=0;k<M;k++){++count;}for(intk=0;k<N;k++){++count;}cout<<count;}

func1执行的基本操作次数：
T（N）=M+N
func1的时间复杂度：O（N）

示例3：

voidfunc2(intN,intM){intcount=0;for(intk=0;k<100;k++){++count;}cout<<count;}

func2的基本操作次数：
T（N）=100
根据第一条规则得出func2的时间复杂度：O（1）

示例4：

constchar*strchr(constchar*str,intcha){constchar*p=str;while(*p!=cha){if(*p=='\0')returnnullptr;p++;}returnp;}

在最好情况时，函数内部循环执行一次就可以结束；而当遇到最坏情况时，循环需要执行n次才能结束。
大O的渐进表示法在实际中一般情况关注的是·算法的上界，也就是最坏运行情况。

示例5：

voidbubble_sort(int*arr,intsz){for(inti=sz-1;i>0;i--){intflag=0;for(intj=0;j<i;j++){if(arr[j]>arr[j+1]){flag=1;inttmp=arr[j];arr[j]=arr[j+1];arr[j+1]=tmp;}}if(flag==0)break;}}

若数组有序：T（N）=N；
若数组为降序：T（N）=N*（N-1）/ 2；
因此冒泡排序的时间复杂度为：O（n^2)

示例6：

voidfun(intn){intk=1;while(k<cnt){k*=2;}}

fun函数执行次数为以2为底的n的对数次，用大O渐进表示法表示为：O（logN）

示例7：

intfun(inti){if(i==0){return1;}elsereturnfun(i-1)*i;}

阶乘递归时间复杂度为O（N）
三、空间复杂度

空间复杂度是表示算法在运行过程中因算法需要额外临时开辟的空间
空间复杂度因常规情况每个对象大小差异不会很大，所以空间复杂度算的是变量的个数
空间复杂度也要用大O渐进表示法表示

• 空间复杂度主要通过函数在运行时显示申请的额外空间确定

算法复杂度计算示例：
示例1：

voidbubble_sort(int*arr,intsz){for(inti=sz-1;i>0;i--){intflag=0;for(intj=0;j<i;j++){if(arr[j]>arr[j+1]){flag=1;inttmp=arr[j];arr[j]=arr[j+1];arr[j+1]=tmp;}}if(flag==0)break;}}

函数栈帧在编译期间已经确定，只需关注在运行时额外申请的空间，bubble_sort只额外申请了一些局部变量，使用了常数个空间，因此空间复杂度为O（1）

示例2：

intfun(inti){if(i==0){return1;}elsereturnfun(i-1)*i;}

fun函数额外开辟了n个函数栈帧，每个栈帧开辟了常数个空间，因此空间复杂度为O（N）
四、常见复杂度对比

五、复杂度算法题
1、旋转数组
添加链接描述

• 思路一：两层循环使所有元素向后移动，最后一位元素放到首位，这样时间复杂度为O（N^2)，空间复杂度为O（1）
  这种方法时间复杂度过大，一旦测试数据要执行多次轮转就会超时

voidrotate(int*nums,intnumsSize,intk){while(k--){inttmp=nums[numsSize-1];for(inti=numsSize-1;i>0;i--){nums[i]=nums[i-1];}nums[0]=tmp;}}

• 思路二：以空间换时间，先将后k个数据放进新创建的数组中，再将剩下的元素挪到新数组中，时间复杂度为O（N），空间复杂度为O（N）

voidrotate(int*nums,intnumsSize,intk){intnewarr[numsSize];for(inti=0;i<numsSize;i++){newarr[(i+k)%numsSize]=nums[i];}for(intj=0;j<numsSize;j++)nums[j]=newarr[j];}

• 思路三：三次逆置，先将数组中前n-k个数据逆置，再将最后k个数据逆置，最后数组整体逆置，这样时间复杂度为O（N），空间复杂度为O（1）

voidreverse(int*nums,intbegin,intend){while(begin<end){inttmp=nums[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#include<iostream>#include<cstring>typedefintSLDataType;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#include"Seqlist.h"#include<iostream>#include<cstring>#include<cassert>voidInit(seqlist*ptr){ptr->a=(SLDataType*)malloc(sizeof(SLDataType)*4);ptr->Capacity=4;ptr->size=0;}voidDestory(seqlist*ptr){free(ptr->a);ptr->a=nullptr;ptr->Capacity=0;ptr->size=0;}voidPrint(seqlist*ptr){if(!ptr->size)return;for(inti=0;i<=ptr->size-1;i++){std::cout<<ptr->a[i]<<" ";}std::cout<<std::endl;}voidCheckCapacity(seqlist*ptr){if(ptr->size>=ptr->Capacity){SLDataType*tmp=(SLDataType*)realloc(ptr->a,2*ptr->Capacity*sizeof(SLDataType));//通常成倍扩容if(tmp!=nullptr){ptr->a=tmp;ptr->Capacity*=2;}else{std::cout<<"申请空间失败！"<<std::endl;exit(1);}}}voidpushfront(seqlist*ptr,SLDataType ele){CheckCapacity(ptr);ptr->size++;for(inti=ptr->size-2;i>=0;i--){ptr->a[i+1]=ptr->a[i];}ptr->a[0]=ele;}voidpopfront(seqlist*ptr){assert(ptr->size);for(inti=0;i<=ptr->size-2;i++){ptr->a[i]=ptr->a[i+1];}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(0<=pos&&pos<ptr->size);CheckCapacity(ptr);for(inti=ptr->size-1;i>=pos;i--){ptr->a[i+1]=ptr->a[i];}ptr->a[pos]=ele;ptr->size++;}voidDelete(seqlist*ptr,SLDataType pos){assert(0<=pos&&pos<ptr->size);for(inti=pos;i<ptr->size-1;i++){ptr->a[i]=ptr->a[i+1];}ptr->size--;}boolFind(seqlist*ptr,SLDataType ele){if(!ptr->size)returnfalse;for(inti=0;i<ptr->size;i++){if(ptr->a[i]==ele)returntrue;}returnfalse;}

4、顺序表算法题
4.1移除元素
添加链接描述

• 思路一：使用顺序表，查找出val值的下标，删除该下标的数据
• 思路二：双指针，使用dst占住为val值的位置，将src位置的数据赋值给dst位置的值

intremoveElement(int*nums,intnumsSize,intval){intdst=0,src=0;while(src<numsSize){if(dst!=src)nums[dst]=nums[src];if(nums[dst]!=val)dst++;src++;}returndst;}

4.2 删除有序数组中的重复项
添加链接描述

思路：三指针

intremoveDuplicates(int*nums,intnumsSize){intp1=0,p2=1,p3=0;//p1,p2用来排查相同元素，p3用来占住重复元素的位置if(numsSize==0)return0;if(numsSize==1)return1;while(p2<numsSize){if(nums[p1]!=nums[p2]){nums[p3++]=nums[p1];p1=p2;}p2++;}nums[p3++]=nums[p1];returnp3;}

4.3合并两个有序数组
添加链接描述

这个题目描述不由得让我们想到这是归并排序的在递归中进行的一个步骤，所以可以使用三指针将排好序的数组存在tmp中，再挪到nums1中

voidmerge(int*nums1,intnums1Size,intm,int*nums2,intnums2Size,intn){inttmp[nums1Size];intp1=0,p2=0,p3=0;while(p1<nums1Size-nums2Size&&p2<nums2Size){if(nums1[p1]<=nums2[p2])tmp[p3++]=nums1[p1++];elsetmp[p3++]=nums2[p2++];}while(p1<nums1Size-nums2Size)tmp[p3++]=nums1[p1++];while(p2<nums2Size)tmp[p3++]=nums2[p2++];for(inti=0;i<nums1Size;i++)nums1[i]=tmp[i];}