文章目录
算法（algorithm）
时间复杂度（Time Complexity）
时间频度
时间复杂度
最坏时间复杂度和平均时间复杂度
时间复杂度计算
时间复杂度距离
空间复杂度分析
空间复杂度分析1
空间复杂度分析2

算法（algorithm）
是指令的集合，是为解决特定问题而规定的一系列操作，算法就是计算机解题的过程。

一个算法通常来说具有以下五个特性：

输入：一个算法应以待解决的问题的信息作为输入。
输出：输入对应指令集处理后得到的信息。
可行性：算法是可行的，即算法中的每一条指令都是可以实现的，均能再有限的时间内完成。
有穷性：算法执行的指令个数是有限的，每个指令优势再有限时间内完成的，因此整个算法也是再有限时间内可以结束的。
确定性：算法基于特定的合法输入，其对应的输出是唯一的，即当算法从一个特定的输入开始，多次执行同一指令集结果总是相同的。

举例：如何求1+2+3+…+100=?

算法1：依次相加while do-while for

算法2：高斯解法：首尾相加*50

算法3：使用递归实现：sum(100)=sum(99)+100 sum(99)=sum(98)+99…sum(2)=sum(1)+2 sum(1)=1

评价算法优劣的根据：复杂度（时间复杂度和空间复杂度）

算法的复杂性体现再运行算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间资源，因此复杂度分为时间和空间复杂度。

时间复杂度是指执行算法所需要的计算工作量；

空间复杂度是执行这个算法所需要的内存空间。
时间复杂度（Time Complexity）
时间频度
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试。

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。

一个算法中的语句执行次数称为语句频度或时间频度，表示为T（n），n表示问题的规模
时间复杂度
但有时我们想知道它变化时成型什么规律，想知道问题的规模，而不是具体的次数，此时一i纳入时间复杂度，一般情况下，算法中基本操作重复执行的次数时问题规模n的某个函数用T（n）表示。

时间复杂度就是时间频度去掉低阶项和首项常数。

比如某个算法的时间频度时T（n）=10000nn+10n+3

但是时间复杂度时T（n）=O（nn）
最坏时间复杂度和平均时间复杂度
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间，鉴于平均复杂度

第一：难计算

第二：由很多算法的平均情况和最差情况的复杂度时一样的。

所以一般讨论最坏时间复杂度

为了进一步说明算法的时间复杂度我们定义O、Ω、Θ符号

O符号给出了算法时间复杂度的上界（最坏情况 《=）

Ω符号给出了时间复杂度的下届（最好情况》=）

Θ符号给出了算法时间复杂度的精确阶（最好和最坏时同一阶 = ）
时间复杂度计算

找出算法中的基本语句；

算法中执行粗疏最多的那条语句就是基本语句，通常时内层循环的循环体
计算基本语句的执行次数的数量级；

只需计算基本语句执行次数的数量级，之久以为着要保证基本语句执行次数的函数中的最高次幂正确即可，

可以忽略所有低次幂和最好次幂的系数，这样能够简化算法分析，并且式注意力集中再最重要的一点上：增长率
用大O记号表示算法的时间性能

将基本语句执行次数的数量级放入大O记号中

时间复杂度距离

一个简单语句的时间复杂度O（1）。

int count = 0;

T（n）= 1

T（n）= O（1）

100个简单语句的时间复杂度也为O（1）。（100是常熟，不是去向无穷大的n）

int count = 0;
。。。
int count100 = 100；

T（n）= 1

T（n）= O（1）

一个循环的时间复杂度为O（n）

int n=8,count=0;
for(int i=1; i<10n+100;i++){
	count++;
}

T（n）= 10n+100

T（n）= O（n）

时间复杂度为O（log2 n）的循环语句

int n=8,count=0;
for(int i=1; i<n;i*=2){
	count++;
}


时间复杂度为O（n2）的二重循环

int n=8,count=0;
for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		count++;
	}
}


时间复杂度为O（nlog2 n）的二重循环

int n=8,count=0;
for(int i=1;i<=n;i*=2){
	for(int j=1;j<=n;j++){
		count++;
	}
}


时间复杂度为O（n2）的二重循环

int n=8,count=0;
for(int i=1;i<=n;i++){
	for(int j=1 ;   j<=i   ;j++){
		count++;
	}
}

1+2+3+4+。。。+n=（1+n）n/2 ==》T（n）= O（n2）
空间复杂度分析
空间复杂度分析1
int fun(int n){
	int i,j,k,s;
	s=0;
	for(i=0;i<=n;i++){
		for(j=0;j<=i;j++){
			for(k=0;k<=j;k++){
				s++;
			}
		}
	}
	return(s);
}

由于算法中临时变量的个数与问题规模n无关，所以空间复杂度均为S（n）=O（1）
空间复杂度分析2
void fun(int a[],int n, int k){
	//数组a共有n个元素
	int i;
	if(k==n-1){
		for(i=0;i<n;i++){
			printf("%d\n",a(i));//执行n次
		}
	}
	else{
		for(i=k ;i<n;i++){
			a[i]=a[i]+i*i;//执行n-k次
		}
		fun(a,n,k+1);
	}
}

此算法属于递归算法，每次调用本身都要分配空间，fun（a，n，0）的空间复杂度为O（n）
注意：

空间复杂度相比时间复杂度分析很少
对于递归算法来说，代码一般都比较简短，算法本身所占用的存储空间较少，但运行时需要占用较多的临时工作单元；若写成非递归算法，代码一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元。

排序算法经过长时间演变，大体可以分为两类：内排序和外排序。在排序过程中，全部记录存放在内存，则成为内排序；如果排序过程中需要使用外存，则称为外排序，本文讲的都属于内排序。

 

内排序有可以分为以下几类：

    （1）插入排序：直接插入排序、二分法插入排序、希尔排序

    （2）选择排序：直接选择排序、堆排序

    （3）交换排序：冒泡排序、快速排序

    （4）归并排序

    （5）基数排序

排序方法
			
时间复杂度(平均)
			
时间复杂度(最坏)
			
时间复杂度(最好)
			
空间复杂度
			
稳定性
			
复杂性
		
直接插入排序
			
O()
			
O()
			
O(n)
			
O(1)
			
稳定
			
简单
		
希尔排序
			
O()
			
O()
			
O()
			
O(1)
			
不稳定
			
较复杂
		
直接选择排序
			
O()
			
O()
			
O()
			
O(1)
			
不稳定
			
简单
		
堆排序
			
O()
			
O()
			
O()
			
O(1)
			
不稳定
			
较复杂
		
冒泡排序
			
O()
			
O()
			
O(n)
			
O(1)
			
稳定
			
简单
		
快速排序
			
O()
			
O()
			
O()
			
O()
			
不稳定
			
较复杂
		
归并排序
			
O()
			
O()
			
O()
			
O(n)
			
稳定
			
较复杂
		
基数排序
			
O(d(n+r))
			
O(d(n+r))
			
O(d(n+r))
			
O(n+r)
			
稳定
			
较复杂
		
 

1 如何评价、分析一个排序算法？
很多语言、数据库都已经封装了关于排序算法的实现代码。所以我们学习排序算法目的更多的不是为了去实现这些代码，而是灵活的应用这些算法和解决更为复杂的问题，所以更重要的是学会如何评价、分析一个排序算法并在合适的场景下正确使用。
分析一个排序算法，主要从以下3个方面入手：
1.1 排序算法的执行效率
1)最好情况、最坏情况和平均情况时间复杂度
待排序数据的有序度对排序算法的执行效率有很大影响，所以分析时要区分这三种时间复杂度。除了时间复杂度分析，还要知道最好、最坏情况复杂度对应的要排序的原始数据是什么样的。
2)时间复杂度的系数、常数和低阶
时间复杂度反映的是算法执行时间随数据规模变大的一个增长趋势，平时分析时往往忽略系数、常数和低阶。但如果我们排序的数据规模很小，在对同一阶时间复杂度的排序算法比较时，就要把它们考虑进来。
3)比较次数和交换(移动)次数
内排序算法中，主要进行比较和交换(移动)两项操作，所以高效的内排序算法应该具有尽可能少的比较次数和交换次数。
1.2 排序算法的内存消耗
也就是分析算法的空间复杂度。这里还有一个概念—原地排序，指的是空间复杂度为O(1)的排序算法。
1.3 稳定性
如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变，那么这种排序算法叫做稳定的排序算法；如果前后顺序发生变化，那么对应的排序算法就是不稳定的排序算法。
在实际的排序应用中，往往不是对单一关键值进行排序，而是要求排序结果对所有的关键值都有序。所以，稳定的排序算法往往适用场景更广。
2 三种时间复杂度为O(n2)的排序算法
2.1 冒泡排序
2.1.1 原理
两两比较相邻元素是否有序，如果逆序则交换两个元素，直到没有逆序的数据元素为止。每次冒泡都会至少让一个元素移动到它应该在的位置。
2.1.2 实现
void BubbleSort(int *pData, int n)    //冒泡排序
{int temp = 0;bool orderlyFlag = false;    //序列是否有序标志
for (int i = 0; i < n && !orderlyFlag; ++i)    //执行n次冒泡
{
orderlyFlag= true;for (int j = 0; j < n - 1 - i; ++j)    //注意循环终止条件
{if (pData[j] > pData[j + 1])    //逆序
{
orderlyFlag= false;
temp=pData[j];
pData[j]= pData[j + 1];
pData[j+ 1] =temp;
}
}
}
}
测试结果
2.1.3 算法分析
1)时间复杂度
最好情况时间复杂度：当待排序列已有序时，只需一次冒泡即可。时间复杂度为O(n)；
最坏情况时间复杂度：当待排序列完全逆序时，需要n次冒泡。时间复杂度为O(n2)；
平均情况时间复杂度：当待排序列完全逆序时，逆序度为n * (n - 1) / 2。只有当交换逆序对时才会才会使得有序，取中间逆序度n * (n - 1) / 4，那么就要进行n * (n - 1) /4次交换，而比较的次数大于交换次数，所以平均情况时间复杂度为O(n2)。
2)空间复杂度
只借助了一个临时变量temp，所以空间复杂度为O(1)。
3)稳定性
该算法中只有交换操作会改变数据元素的顺序，只要我们在数据元素值相等时不交换数据元素，那么算法就是稳定的。
4)比较和交换的次数
交换操作的执行次数与逆序度相等，比较操作的执行次数大于等于逆序度小于等于n * (n - 1) / 2。
2.2 插入排序
2.2.1 原理
将待排序序列分为已排序区间和未排序区间，开始时已排序区间只有一个数据元素也就是序列的第一个元素，将未排序区间中的数据元素插入已排序区间中同时保持已排序区间的有序，直到未排序区间没有数据元素。
2.2.2 实现
void InsertSort(int *pData, int n)    //插入排序
{int temp = 0, i, j;for (i = 1; i < n; ++i)    //未排序区间
{if (pData[i] < pData[i - 1])    //逆序
{
temp=pData[i];for (j = i - 1; pData[j] > temp; --j)    //搬移数据元素
pData[j + 1] =pData[j];
pData[j+ 1] = temp;    //插入数据
}
}
}
测试结果：
2.2.3 算法分析
1)时间复杂度
最好情况时间复杂度：当待排序列已有序时，只需遍历一次即可完成排序。时间复杂度为O(n)；
最坏情况时间复杂度：当待排序列完全逆序时，需要进行n-1次数据搬移和插入操作。时间复杂度为O(n2)；
平均情况时间复杂度：与冒泡法的分析过程一样，平均情况时间复杂度为O(n2)。
2)空间复杂度
排序过程中只需要一个临时变量存储待插入数据，空间复杂度为O(1)。
3)稳定性
插入排序过程中只有插入操作会改变数据元素的相对位置，只要元素大小比较时相等情况下不进行插入操作，插入排序算法就是稳定的。
4)比较操作和数据搬移操作执行次数
数据搬移操作执行次数和逆序度相同。比较操作次数大于等于逆序度，小于等于n * (n - 1) / 2。
2.3 选择排序
2.3.1 原理
选择排序的原理类似于插入排序都分为已排序区间和未排序区间，选择排序的已排序区间初始大小为零，每次从未排序区间取关键值最大(或最小)的数据元素放在已排序区间的后一个位置，直到未排序区间没有数据元素则完成排序。
2.3.2 实现
void SelectSort(int *pData, int n)    //选择排序
{inti, j, min, temp;for (i = 0; i < n; ++i)    //未排序区间
{
min= i;    //最小值下标
for (j = i + 1; j < n; ++j)
{if (pData[min] > pData[j])    //逆序
min = j;    //保存当前较小值下标
}if (i != min)    //如果不是最小值，交换元素
{
temp=pData[i];
pData[i]=pData[min];
pData[min]=temp;
}
}
}
测试结果：
2.3.3 算法分析
1)时间复杂度
不管是已有序序列还是完全逆序序列，都要进行n次遍历无序区间操作，时间复杂度为O(n2)。
2)空间复杂度
排序过程中只需要保存每次遍历无序区间最小值的下标和第i个元素的数值，所以空间复杂度为O(1)。
3)稳定性
选择排序算法中改变数据元素相对位置的操作为交换操作，当第i次中第i个数据元素不为当前无序区间最小值时则和最小值交换数据元素。当有重复元素时，就有可能发生相对位置改变。例如5，3，4，5，1第一次选择操作后为1，3，4，5，5，此时两个5的相对位置已经改变。所以选择排序算法不是稳定的。
4)比较操作和交换操作的执行次数
比较操作执行次数为n * (n - 1) / 2，交换操作执行次数小于等于n-1。
2.4 三种算法之间的比较
1)一般待排序列长度n较小时，我们选择这三种排序算法；
2)当排序要求稳定时，一般选择插入排序，因为相同的情况下，移动数据比交换数据执行速度快；
3)当数据元素信息量较大时，可以考虑用选择排序，因为它交换操作执行次数最少。
该篇博客是自己的学习博客，水平有限，如果有哪里理解不对的地方，希望大家可以指正！

上一篇文章学习了：如何分析、统计算法的执行效率和资源消耗？ 点击链接查看上一篇文章：复杂度分析上
今天的文章学习以下内容：

最好情况时间复杂度
最坏情况时间复杂度
平均情况时间复杂度
均摊时间复杂度

1、最好与最坏情况时间复杂度
我们首先来看一段代码，利用上一篇文章学习的知识看看能否分析出它的时间复杂度。
// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}


这段代码很简单：就是在一个数组中找到一个数X的下标，将其返回。
利用上一篇文章学习的大O表示法来分析时间复杂度的话，有一些问题。if循环中有一个breadk语句，当条件成立，得到下标值立马退出循环。那么时间复杂度，就不能笼统的说是O（n）。
因为当想要查找的数就在第一个位置时，时间复杂度实际上是O（1），当想要查找的数在最后一个位置的时候，时间复杂度是O（n）。那么这个时候，我们就需要引入几个新名词：最好情况时间复杂度，最坏情况时间复杂度。
很容易理解。

最好情况时间复杂度就是在最理想的情况下，执行代码需要的时间复杂度。就像上述代码，如果想要查找的数就是数组中的第一个位置，那么时间复杂度就是O（1），此时就是最好情况时间复杂度。
最坏情况时间复杂度是在最不理想的情况下，执行代码需要的时间复杂度。还是如上述代码，入股我们想要查找的数在数组的最后一个位置，那么时间复杂度就是O（n），此时就是最坏情况时间复杂度。

其实还有一种情况，就是我们想要查找的数不在第一个位置也不在最后一个位置的时候。此时的时间复杂度是多少呢？这种情况下叫做平均情况时间复杂度。
那么平均情况时间复杂度如何计算？它是多少呢？
2、平均情况时间复杂度
还是拿上面的代码做例子。
想要计算出它的平均情况时间复杂度，有两种方法，一种不严谨的感官上的方法，一种严格的概率上的方法。

不严谨的感官上的方法

我们知道，想要查找的数据x有两种情况的存在，一种是存在数组的0~n-1的某一个位置（n种可能），一种是不在这个数组中（1中可能，就是不在数组中）。这两种情况一共有n+1种可能。对于在数组中的n中可能中，每一种查找的次数分别是1,2,3,4…n。对于不在数组中的这种可能，查找次数是n。所以可以这么计算平均情况时间复杂度：
(1+2+3+...+n+n)/(n+1)=n(n+3)/2(n+1)

上一篇文章我们知道，利用大O表示法，，可以将计算结果的系数，低阶，常量去掉。那么上述的结果就是O（n）。
为什么说他不严谨呢？考虑以下情况。要找的数x存在于数组中与不存在于数组中的概率是否一样？x存在的话。它存在于数组中每个位置的概率是否一样？
很明显，上述方法没有考虑概率的问题。

概率的方法

现在假设，x出现在数组中与不出现在数组中的概率是相等的，都是1/2.同时假设x如果出现在数组中，则它存在数组中的每一个位置的概率都是一样的1/n。那么可以用如下方法计算平均情况时间复杂度。
$（1 \times \frac{1}{n}  \times \frac{1}{2}+2 \times \frac{1}{n}  \times \frac{1}{2} +3 \times \frac{1}{n}  \times \frac{1}{2} +...+n \times \frac{1}{n}  \times \frac{1}{2} + n \times \frac{1}{2}）= \frac{3n+1}{4}$
利用大O表示法来表示的话，依然是O（n）。这就是上面那段代码的平均情况时间复杂度。
一般情况下，我们只是用其中一种复杂度来分析问题就够了，不需要费力去求解三种时间复杂度。只有在时间复杂度有量级的差距时，才会在不同的情况下使用不同的时间复杂度。
3、均摊时间复杂度
上面学会了最好最坏与平均时间复杂度。还有一种时间复杂度叫做均摊时间复杂度。 为了理解均摊时间复杂度，我们先来看一个代码：
 // array 表示一个长度为 n 的数组
 // 代码中的 array.length 就等于 n
 int[] array = new int[n];
 int count = 0;
 
 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }


上述代码的意思是：往数组中插入数据。当数组没有满的时候，直接在最后插入，当数组满的时候，先把数组的所有元素求和，然后清空数组，将求得的和放到数组的第一个位置，然后将要插入的数插到第二个位置（聪明的人已经发现它其实就是一个求输入流中所有数字的和，至于清空数组，这个只是将下标count从末尾挪到第二个位置，就可以认为是清空数组）。
利用上述的分析，我们可以求得：

最好情况时间复杂度：O（1），因为数组不满的时候直接插入，不用计算和。
最坏情况时间复杂度：O（n），因为此时数组满了，需要遍历一遍数组然后求和。

平均时间复杂度，还可以利用上述的概率分析法来计算。假设数组长度是n，往数组插入数据会有两种情况发生。数组没满时，插入的时间复杂度是O（1），且插入的位置有n种可能。数组满时，插入的时间复杂度是O（n），插入的位置只有一种可能。所以一共有n+1种可能插入的位置，且插入到它们位置的概率是一样的都是1/（n+1）。所以可以利用下面的方法计算平均情况时间复杂度：

$（1 \times \frac{1}{n+1}+2 \times \frac{1}{n+1}   +3 \times \frac{1}{n+1}  +...+n \times \frac{1}{n+1}   + n \times \frac{1}{n+1}）= O（1）$
所以

平均情况时间复杂度：O（1）

上述计算平均时间复杂度的方法，不管怎么样，还是有一些复杂。毕竟我们不是研究数学的。所以还是希望尽可能简单。
针对上面的两个代码例子，一个是find函数，一个是insert函数。看看他们有什么不同。find函数是最极端的情况下时间复杂度是O（1），大多数的情况下时间复杂度是O（n），而insert函数是大多数情况下的时间复杂度是O（1），只有极端的情况下时间复杂度是O（n）。
而且，对于insert函数，它的O（1）出现的是连续出现多次，然后出现一次O（n）时间复杂度。这具有一种时序关系。
针对这种情况，给出一种特殊的时间复杂度分析方法，均摊时间复杂度。可以通过摊还分析法，的带均摊时间复杂度。那么针对insert函数，如何通过摊还分析法来得到均摊时间复杂度呢？
首先，对于insert函数，大多是出现O（1）时间复杂度的，一共出现n次O（1）时间复杂度后，才出现一次O（n）时间复杂度。虽然O（n）时间复杂度消耗的时间比较多，但是O（1）时间复杂度出现的次数多，我们可以将O（n）消耗的时间，均摊给其他n个O（1）时间复杂度操作上的话，对于O（1）时间复杂度，也并不会有多大的影响，就好比，100个人共同抬100斤水泥，而另外又有一个人在抬100斤水泥，如果这个人把水泥平均分给那100人，那100人也才每个人多抬了一斤的水泥，这相比让那一个人抬100斤水泥，简直不要太轻松！！！。 所以，对于insert函数均摊时间复杂度为O（1）。这等于大多数情况下的时间复杂度。
综上：

均摊时间复杂度为：O（1）

由以上的分析，我们得出，大概在以下情况下可以使用摊还分析来分析均摊时间复杂度
对一个数据结构进行连续的操作，如果大多数情况下的时间复杂度比较低，只有极端情况下时间复杂度很高，而且这些操作在时序上存在前后连贯的关系。那么此时，就可以将比较耗时的那个操作，均摊给大多数低的时间复杂度的操作上。
而且，一般可以用均摊时间复杂度分析的情况，均摊时间复杂度就等于最好情况时间复杂度
4、总结
上面学习了四种时间复杂度的分析。但是一般来说，平均时间复杂度用的很少，均摊时间复杂度用的就更少。而且，均摊时间复杂度，实际上是一种特殊的平均时间复杂度。
所以不必纠结到底用什么复杂度来分析问题，根据实际问题需要实际分析。对于一段代码，如果它的时间复杂度在不同情况下量级不同，可以采用不同的方法进行对比分析。其中最好最坏时间复杂度比较好分析，平均时间复杂度与均摊时间复杂度比较难分析。
但是对于平均和均摊。他们实际是一个意思，都有平均的意思。当出现O（1）操作的多于O（n）操作的时候，平均和均摊时间复杂度就都是O（1）。  这是一种感觉。一般情况下，我们都可以感觉对，而不用实际的计算。
本文是自己学习极客时间专栏-数据结构与算法之美后的笔记总结。如有侵权请联系我删除文章。
学习探讨加个人（免费送技术书籍PDF电子书）：

qq：1126137994

微信：liu1126137994