空间复杂度&时间复杂度

空间复杂度是算法运行过程中，临时占用空间存储空间大小的量度；

时间复杂度是描述算法运行的耗时情况的量度。

复杂度的大O表示法

复杂度是表示算法对时间或者存储的要求与输入数据n之间的关系；n一般可以简单理解为数据量。0

O(1) 表示算法对时间或存储的要求是常量，不随着数据量的增加而增加

O(n) 表示算法对时间或存储的要求与数据量成线性关系，随着数据量增加，对时间或存储的要求也随之增加。

O(n^2) 表示数据量增加n倍，算法对时间或者存储的要求增加n^2倍

类似的有 O(log(n))、O(n!)等

常见排序算法的时间复杂度与空间复杂度

不了解算法具体实现的，请先阅读：

面试：经典排序算法思路及源码（收藏不看系列）

面试：经典排序算法 - 堆排序

插入排序

空间复杂度为1；（仅仅在交换的时候需要一个元素）

时间复杂度：对于第n个元素，其最多需要比较n次，最少需要比较1次；那么最坏的情况下需要比较n*(n+1) / 2，即时间复杂度为O(n^2); 最好的情况下需要比较n次，时间复杂度为O(n)

直接选择排序

选择排序的空间复杂度为O(1)；

时间复杂度，从两个角度分析 一个是比较，另一个是交换；交换的复杂度与插入排序相同，但比较的复杂度为n*(n+1) / 2，所以最终的时间复杂度为O(n^2)

堆排序

空间复杂度为O(1);（仅仅在交换的时候需要一个元素）

时间复杂度：第一次构建堆的时间复杂度，针对第i层，为 2^( i - 1 ) * ( k - i )，其中i-1表示层数，k表示总的层数；2^( i - 1 )表示第i层的元素数，k-1表示最多需要比较k-1次。

各个层求和：S = 2^(k-2) * 1 + 2^(k-3)2…..+2(k-2)+2^(0)*(k-1) = 2^k -k -1 (等比数列求和)，其中k = log(n); 得 S = n - longn -1 所以，到这儿时间复杂度为O(n)

取出根与最后一个元素交换之后，再次重建堆的过程只需要为交换后的最后一个元素找到位置即可，时间复杂度为log(n)，整个过程需要重复n-1次，所以时间复杂度为O(nlog(n))

冒泡排序

空间复杂度为O(1);（仅仅在交换的时候需要一个元素）

第一轮元素需要比较n-1次，找到最大元素；第二轮需要比较n-1次，找到次大元素... ..

(n-1) + (n-2) + ... + 1 = n^2/2,所以时间复杂度为n^2

快速排序

时间复杂度，一般情况下，需要进行2 * log(n)次递归，每次递归需要指针移动n步，期望值是n * log(n)；

但如果恰好每次取到的都是数组中最大的，或者是最小的；那么就退化为冒泡排序，所以最差时间复杂度为n^2.

空间复杂度，因算法实现而异：

归并排序

时间复杂度，与快速排序的期望时间复杂度类似，nlog(n)

空间复杂度，需要一个长度为n的辅助数组，所以时间复杂度为O(n),但也许有更优实现。

以上算法，插入排序、冒泡排序、归并排序是稳定排序，其余是非稳定排序。