文章目录
 
算法效率度量
时间复杂度
master公式
常用排序算法及其时间复杂度
冒泡排序(bubblesort)：$O(N^{2})$
选择排序：$O(N^{2})$
插入排序：$O(N^{2})$
归并排序：$O(Nlog{N})$
总结
 

 
算法效率度量
 
1.时间复杂度O(n)
 原则：
 
常数1代替所有加法中的常数
只保留最高阶数项(且不要前面的系数)
O(1)<O(log n)<O(n)<O(n logn)<O(n^2)
 
2.空间复杂度
 常用空间换时间
 
时间复杂度
 
时间复杂度：算法性能指标（本质常数时间操作的个数）；先看指标再看系数；先看高阶项再看低阶项
常数时间操作：例如位操作、算术运算等。
 
master公式
 
$$T(N)=aT(N/b)+O(N^d)$$
 其中a表示子过程发生次数，b表示子过程样本量，
 $lo{g}_b^a>d\to$复杂度为$O(N^{lo{g}_b^a})$
 $lo{g}_b^a=d\to$复杂度为$O(N^{dlo{g}^N})$
 $lo{g}_b^a>d\to$复杂度为$O(N^d)$
 
常用排序算法及其时间复杂度
 
冒泡排序(bubblesort)：$O(N^2)$
 
选择排序：$O(N^2)$
 
插入排序：$O(N^2)$
 
时间复杂度与数据状况有关，最好$O(N)$最差$O(N^2)$。但算法性能一律按最差考虑，即插入排序时间复杂度为$O(N^2)$
 
归并排序：$O(NlogN)$
 
分治思想
 
总结
 
常用排序算法
时间复杂度
空间复杂度
稳定性
平均情况
最好情况
最坏情况
辅助存储
交换排序
冒泡排序
 O(n*n)
 O(n)
 O(n*n)
 O(1)
 稳定
快速排序
 O(n*logn)
 O(n*logn)
 O(n*n)
 O(n*logn)
 不稳定
插入排序
直接插入
 O(n*n)
 O(n)
 O(n*n)
 O(1)
 稳定
shell排序
 O(n*n)
 O(n)
 O(n*n)
 O(1)
 不稳定
选择排序
直接选择
 O(n*n)
 O(n*n)
 O(n*n)
 O(1)
 不稳定
堆排序
 O(n*logn)
 O(n*logn)
 O(n*logn)
 O(1)
 不稳定
归并排序
 O(n*logn)
 O(n*logn)
 O(n*logn)
 O(n)
 稳定

 
 
 
均按从小到大排列
k代表数值中的"数位"个数
n代表数据规模
m代表数据的最大值减最小值
 

一、常用排序算法的时间复杂度和空间复杂度表格
 
 
二、特点
 

 1.归并排序：
 

 （1）n大时好，归并比较占用内存，内存随n的增大而增大，但却是效率高且稳定的排序算法。
 
（2）归并排序每次递归都要用到一个辅助表，长度与待排序的表长度相同，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助空间
 
（3）虽然插入排序的时间复杂度为O(n2)，归并排序的时间复杂度为O(nlog2n)，但插入排序中的常数因子使得它在n较小时，运行更快一些。因此，在归并排序算法中，当子问题足够小时，采用插入排序算法就比较合适
 
（4）以时间换空间：网上很多blog分享空间复杂度只有O(1)的归并排序法；因为传统的归并排序所消耗的空间主要是在归并函数（把两个有序的函数合并成一个有序的函数），所以如果要让时间复杂度为O(1)，那么也只能在归并函数中做文章了。其主要思想就是借助于快速排序（其实就是相当于归并函数被快速排序函数替换了），这样的方法虽然可以减少内存的消耗，但是却会在时间上带来损失，因为这样时间复杂度却变成了O(n2)了；所以这种方法并不是一个两全其美的idea。
 

 2.冒泡排序
 
（1）冒泡排序是一种用时间换空间的排序方法，n小时好
 
（2）最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序，最差时间复杂度O(n2)只是表示其操作次数的数量级
 
（3）最好的情况是数据本来就有序，复杂度为O(n)
 
3.快速排序
 
（1）n大时好，快速排序比较占用内存，内存随n的增大而增大，但却是效率高不稳定的排序算法。
 
（2）划分之后一边是一个，一边是n-1个，这种极端情况的时间复杂度就是O(n2)
 
（3）最好的情况是每次都能均匀的划分序列，O(nlog2n)
 
（4）快速排序空间复杂度只是在通常情况下才为O(log2n)，如果是最坏情况的话，很显然就要O(n)的空间了。当然，可以通过随机化选择pivot来将空间复杂度降低到O(log2n)。
 
三、相关概念
 
1、时间复杂度
 
时间复杂度可以认为是对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
 
常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2)
 
时间复杂度O(1)：算法中语句执行次数为一个常数，则时间复杂度为O(1)
 
2、空间复杂度
 
空间复杂度是指算法在计算机内执行时所需存储空间的度量，它也是问题规模n的函数
 
空间复杂度O(1)：当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)
 
空间复杂度O(log2N)：当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)         
 
空间复杂度O(n)：当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n).
 --------------------- 

 原文：https://blog.csdn.net/jiajing_guo/article/details/69388331