理解快速排序的空间复杂度

2021-02-02

在网上关于快排的时间复杂度基本没有啥争议（最好和平均情况O(nlogn)，最坏情况O(n^2)），因为快排的定义本身就包括了对它的时间复杂度的定义。而空间复杂度则是没有定义的，所以中文互联网上有各种说法，而且粗略看了一下，并没有说的特别明白的。所以这篇笔记就简单谈一下我对快排的空间复杂度的理解。

首先，说一下对空间复杂度的这个概念，一般来说是指算法执行时所需要的临时存储空间的大小。换句话说，存储输入所占用的空间是不计入的。

用更简单一点的冒泡排序举例，对长度为n的数组做排序，首先要一块大小为n的存储空间去存它，这个空间是不算在空间复杂度里的。那么冒泡排序实际需要的空间就是每次选出两个数进行比较的空间，并且这个空间是可以复用的，所以是一个常数，因此记为O(1)。

那么说回到快速排序，快排每一轮会确定一个元素的位置，并且以这个排好的元素为界，分成左边和右边两个子数组，再分别对这两个子数组递归地进行快排。

从这个原理出发，我们可以了解到几点：首先，快排是可以原地进行的，也就是不复制数组，只对数组的元素做位置交换；而上面已经说过，存储数组元素的空间不计入空间复杂度，所以这部分消耗的空间可以忽略。

第二，快排的空间复杂度会有最好和最坏两种极端，因为每轮都把数组分为左右两部分，就像是两个人合作完成一个任务，最好的情况下，左边和右边长度相等，两个调用可以均匀地分担工作；最坏情况下，其中一个数组永远是空的（pivot总是选到最值），那就完全由另一个调用去排序。

我们分别讨论这两种情况，首先想象一下快排的递归调用到最末端会是什么情况：因为每轮都把数组分为左右两部分，所以最末端调用的输入只会是一个长度为1或者为0的数组，直接返回（也就是递归的停止条件）。

那么调用的结构其实就可以用二叉树的形式来表示，比如说对一个长度为5的数组排序，最好情况是（空的括号表示这个调用的输入为空数组）：

            xxxxx
             / \
            /   \
           /     \
          /       \
         xx        xx
        / \        / \
       /   \      /   \
      /     \    /     \   
     x      ()  x       ()

最坏情况是：

              xxxxx
               / \
              /   \
             /     \
            /       \
          xxxx      ()
          / \ 
         /   \
        /     \
      xxx     ()
      / \ 
     /   \ 
    xx    ()
   / \ 
  /   \ 
 x    ()

除了调用结构，快排需要的空间是否还和别的因素相关呢？从快排的原理我们知道，要实现快排，还剩下的部分就是partition，也就是把小于pivot的都移到左边、大于的都移到右边这个过程。显然这个过程里面用到的空间是可以复用的（在循环中复用变量就可以），也就是说partition只需要常量的空间就可以执行。

因此，快排的空间复杂度只和调用的结构有关。那么具体是什么关系？空间复杂度是不是 O(调用树中所有节点的个数) 呢？

并不是这样，实际上调用栈的空间复杂度总是 O(调用树深度)，和调用结构里到底有多少个节点没有关系。为什么？因为实际调用的时候不需要去存一个完整的树，而是使用调用栈，栈是既能进也能出的，当某一个调用结束，它的结果就可以向上合并然后出栈，不需要一直存在栈里面。

举个实际的调用过程的例子：

因此，可以说快排算法的空间复杂度只和的调用栈（调用树）的深度相关。那么现在我们来到了最后一个问题，调用树的深度怎么计算？

从上面最好和最坏情况两个例子中，很容易看出最坏情况，调用树深度就是n-1（认为树的根节点深度为0）。最好情况则要麻烦一点，麻烦在于我们知道调用树每向下一层，都会有一个点被选为pivot，导致数组长度减少1。那不妨先来考虑数组长度不减少的情况，那么一个长度n的数组递归地左右平分，展开的数深度就是log2 n向上取整，我们记为Ceiling(log2 n)。并且这棵树的最底部必然是这样的结构：

      aa
     / \
    /   \
   a     a

这个结构的上一层只有两种可能的情况（因为我们找的是最底部的结构）：长度为3或者为4，即

      xxx
      / \ 
     /   \ 
    aa    x
   / \ 
  /   \ 
 a     a

或者

         xxxx
         / \
        /   \
       /     \
      /       \
     aa        xx
    / \        / \
   /   \      /   \
  /     \    /     \   
 a       a  x       x

在每一层都减少一位长度后，第一种结构的深度会减少1，变成这样：

    aa
   / \
  /   \
 a     ()

而第二种结构的深度则不会改变，变成下面这样：

      xxx
      / \
     /   \
    aa    x
   / \
  /   \
 a    ()

所以根据最底部的结构不同，会有相差1深度的两种情况。而更上面的结构，层数肯定是不变的，因为上面必有数组长度大于1的节点，从而继续向下分叉。

所以总结一下，最好情况，调用树的深度就是Ceiling(log2 n)或Ceiling(log2 n)-1。而最坏的情况是n-1。

根据大O的定义，就可以写成最好情况O(log n)和最坏情况O(n)。最后一点，平均情况的空间复杂度和最好情况是一样的，也是O(log n)。为什么？简单来说，平均情况和最好情况相比，变得糟糕的程度是一个常数倍，所以表示成大O的形式是相同的。更加具体的讨论可以看这篇文章。

另外顺便一提，Robert Sedgewick提出的一个对快排的优化算法可以使最坏情况的空间复杂度下降到O(log n)。思路是把快排实现中对左右两个子数组的递归换成一个循环和一个递归，并且总是把长度较短的子数组交给递归。