排序算法的时间与空间复杂度分析_当一个算法的空间复杂度与n成线性比例关系时,可表示为o(n)

时间复杂度

时间复杂度是同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。

在我们常用的排序算法中，最常见的5种时间复杂度为 $O\left (log_{2}n \right )$，$O\left (n \right )$，$O\left (nlog_{2}n \right )$，$O\left (n^{2} \right )$，$O\left ( n! \right )$

其函数图像如下：横坐标代表数据量，纵坐标代表所需时间

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。 

一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。

若一个算法为 递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表示开始进行的一次非递归调用)。

算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；

当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；

当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n)。

 

每种排序的时间与空间复杂度

 

对快速排序进行复杂度分析：

以下内容摘自算法图解

快速排序的性能高度依赖于你选择的基准值。假设你总是将第一个元素用作基准值，且要处理的数组是有序的。由于快速排序算法不检查输入数组是否有序，因此它依然尝试对其进行排序。

注意，数组并没有被分成两半，相反，其中一个子数组始终为空，这导致调用栈非常长。现在假设你总是将中间的元素用作基准值，在这种情况下，调用栈如下。

调用栈短得多！因为你每次都将数组分成两半，所以不需要那么多递归调用。你很快就到达了基线条件，因此调用栈短得多。

第一个示例展示的是最糟情况，而第二个示例展示的是最佳情况。在最糟情况下，栈长为$O\left ( n^{2} \right )$，而在最佳情况下，栈长为$O\left (log_{2}n \right )$。

现在来看看栈的第一层。你将一个元素用作基准值，并将其他的元素划分到两个子数组中。这涉及数组中的全部8个元素，因此该操作的时间为$O\left ( n \right )$。在调用栈的第一层，涉及全部8个元素，但实际上，在调用栈的每层都涉及$O\left ( n \right )$个元素。

即便以不同的方式划分数组，每次也将涉及$O\left ( n \right )$个元素。

因此，完成每层所需的时间都为$O\left ( n \right )$。

在这个示例中，层数为$O\left (log_{2}n \right )$（用技术术语说，调用栈的高度为$O\left (log_{2}n \right )$），而每层需要的时间为$O\left ( n \right )$。因此整个算法需要的时间为$O\left ( n \right )$ * $O\left (log_{2}n \right )$ = $O\left (nlog_{2}n \right )$。这就是最佳情况。
在最糟情况下，有$O\left ( n \right )$层，因此该算法的运行时间为$O\left ( n \right )$ * $O\left ( n \right )$ = $O\left (n^{2} \right )$。

这里要告诉你的是，最佳情况也是平均情况。只要你每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为$O\left (nlog_{2}n \right )$。