时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度衡量的是一个算法的运行空间。在计算器前期，空间缺乏。所以对空间复杂度很在乎。但是经过计算机行业发展，由摩尔定律，硬件每十八个月就会翻一番，所以手机的内存越来越高。

（一）时间复杂度：算法的大概基本执行次数

1.大O的渐进表示法：用于描述函数渐进行为的数学符号

常数操作：int a=air[i];一条指令即可。而int b=list.get[i];得遍历整个列表，直到找到i

如果一个操作和样本的数据量没有关系，每次都是固定时间内完成的操作称为常数操作

评价一个算法的时间好坏，先看时间复杂度的指标，再分析不同数据样本下的实际运行时间，也称为常数项时间。

1）如果最高项前面的系数存在并且不为1，就去除这个系数。

O(n^2)和O(2*n*n)没区别

2）在修改后的运行次数函数中，只保留最高项。

3）用常数1取代运行时间中的所有加法常数。

for(k=1;k<100;k++)
{
 printf("hehe");
}//  O(n)=1

4)但是有些时间复杂度的计算会存在最好，最坏和平均的情况。

比如在数组中查找一个数，最好是一次找到，最差N次找到，平均是N/2次找到。但是一般情况下，我们关注的都是最坏情况。

（二）排序算法具体剖析

1.冒泡排序：

最坏F（n)=1+2+3+4+...n-1=n^2 ; 最好F（n)=n;

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;
    }
}

2 选择排序

#include<iostream>
using namespace std;

int main()
{
  int a[10]={0};
  for(int i=0;i<10;i++)
 {
  cin>>a[i];
 }
 int min=a[0]
 for(int i=0;i<n-1;i++)
  for(int j=i+1;j<n;j++)
   {
     if(a[j]>a[i])
     swap(*a[j],*a[i])
   }
for(i=0;i<n-1;i++)
 {
  cout<<a[i]<<endl;
 }

每次排序：第一次看数字看了N眼，比了（N-1）次，1次swap

第二次看数字看了（N-1）眼，比了（N-1）次，1次swap

则总共的常数操作位：a*N^2+b*N+c 时间复杂度位O(n^2)

3、插入排序

时间复杂度不同，数据状况不同。最好O（n)，最差O（n^2)

下标：分别使得下标0~0，0~1，0~2...0~size-1所代表的值有序

void turnxu(int arr[],int size)
{
 if(arr==NULL||size<2)
    return;
 int i=0,j=0;
 for(i=1;i<size;i++)
  for(j=i-1;j>=0&&arr[j]>arr[j+1];j--)
   {
    swap(arr,i,j);
   }
}

4.归并排序

T（n)=2T( n/2)+O(n)=O(N*logN）//优点：没有浪费比较行为。变成了比较有序的部分去和下一个部分merge。空间复杂度O（N）

void xu(int arr[],int L,int R)
{
  if(L==R)
    return;
  int mid=L+((R-L)>>1);
  xu(arr,L,mid);//对左边排序
  xu(arr,mid+1,R);//对右侧排序
  merge(arr,L,mid,R);//对整体排序 外排序
}

void merge(int arr[],int L,int M,int R)
{
  int help[]=new int[L-R+1];
  int i=0,p1=L,p2=M+1;
  while(p1<=M&&p2<=R)
   help[i++]=arr[p1]<arr[p2]?arr[p1]:arr[p2];//从左右俩个数组里面找小的放进去
  while(p1<=M)
    help[i++]=arr[p1++];//p2越界而p1没有越界
  while(p2<=R)
    help[i++]=arr[p2++];
  for(i=0;i<L-R+1；i++)
    arr[L+i]=help[i];//合并到一个数组里面
 delete help[];
}

5，快排

void quicksort(int arr[],int L,int R)
{
  if(L<R)
   swap(arr,L+(int)(rand()*(R-L+1)),R);//等随机选一个数字和最右位置数字交换
   int  p[]=partition(arr,L,R);
   quicksort(arr,L,p[0]-1);//<区域 p[0]-1得到小于区域的右边界
   quicksort(arr,p[1]+1,R);//>区域 
}
//处理arr的函数,默认把arr[r]作为划分
//返回值为这个区域的左右边界，长度为2的数组 res[0],res[1]
int partition(int arr,int L,int R)
{
  int less=L-1;//小于区的右边边界
  int more=R;//大于区域的左边界
  while(L<more)
   {//用L表示当前数字的位置 arr[R]划分
    if(arr[L]<arr[R})
     swap(arr,++less,L++)
   else if(arr[L]>arr[R])
    swap(arr,--more,L);
   else{
    L++;
   }
  swap(arr,more,R);
 return new int[]={less+1,more};
}

快排的空间复杂度是O（logN) 类似于满二叉树的展开。最差为O（N）

6.堆排序

堆在逻辑上是一颗完全二叉树结构（满二叉树或者从左往右依次遍满）（数组从0开始的一段可以对应成完全二叉树）

大根堆：每某个结点为头的树的最大值是这个结点。

小根堆：每一个头结点的值是其所属这棵树的最小值。

//堆排序
void headinsert(int arr[],int index)
{
  while(arr[index]>arr[(index-1)/2])
   swap(arr,index,(index-1)/2);//跳出循环的时候是最大的确实是父节点或者是NULL
   index=(index-1)/2;
}

问题1：返回最大值并且把最大值移除之后仍然是大根堆

//返回最大值并且把最大值移除之后仍然是大根堆
int heapfy(int arr[],int index,int heapsize){
 //用index记录从哪里开始
 int left=index*2+1;//记录左孩子下标
  while(left<helpsize)
 {//保证下面还有数字
 //俩个孩子中谁的值大给leftlar
 int large=arr[left]>arr[left+1]?left:left+1;
 //父亲和最大儿子比较
 large=arr[index]>arr[large]?index：large；

 if(large==index)
  break;
 swap(arr,index,large);
 index=largest;
 left=index*2+1;
}
 }

（三）递归函数的T（n)

master公式：T(n)=a*T(n/b)+O(N^d)

使用条件：子问题的规模等量

log以b为底a的对数<d T(n)=O(N^d)

log以b为底a的对数>d T(n)=O(N的log以b为底a的对数）

log以b为底a的对数=d T(n)=O(N^d*logN)

1）T（n)代表母问题有n个子问题

2）a是每个子问题调用的次数

3）n/b代表每个子问题的规模

4）O（N^d）代表除子问题外调用的过程

1.斐波拉契数列

//递归算法复杂度=递归次数*每次递归函数的次数//O（n)
long long f(size_t N)
{
 return N<2?N:f(N-1)*N;
}

long long f(size_t N)
{
 return N<2?N:f(N-1)+f(N-2);
}//画图可得O(2^n)

改进斐波拉契数列

long l0ng*fi(int N)
{
  long long*f=malloc(sizeof(long long)*(N+1));
  f[0]=0;
  if(N==0)
     return f;
  f[1]=1;
  
  //以空间换时间
  for(int i=2;i<N;i++)
  {
     f[i]=f[i-1]+f[i-2];
  }
  return f;
    
}

long l0ng*fi(int N)
{
  long long*f=malloc(sizeof(long long)*(N+1));
  f[0]=0;
  if(N==0)
     return f;
  f[1]=1;
  
  //以空间换时间
  for(int i=2;i<N;i++)
  {
     f[i]=f[i-1]+f[i-2];
  }
  return f;
    
}

2. 例：求数组的最大值 T(n)=O（n)

int ismax(int arr[],int L,int R)//求[L,R]上数组的max
{
  if(L==R)
   return arr[L];
 int mid=L+((R-L)>>1);//求中点 直接求会导致越界，用L+（R-L）/2
 int leftmax=ismax(arr,L,mid);
 int righemax=ismax(arr,mid+1,R);
 return max(leftmax,rightmax);
}

数据结构与算法之复杂度讲解和排序算法

（一）时间复杂度：算法的大概基本执行次数

（二）排序算法具体剖析

（三）递归函数的T（n)