算法导论 Chapter 9.3 Selection in worst-case linear time

本节要求以最坏情况下\(O(n)\)的时间复杂度找到长度为n的数组中第 i 大的数。

解决方案

《算法导论》上提供了一个算法，该算法实质上是利用了快排中划分的思想，但其通过一些比较复杂的预处理工作保证了快排划分的均匀，并且能够从理论上证明其最坏情况下的时间复杂度可以达到\(O(n)\)。

算法步骤

1. 如图所示，将n个数分成5个一组，共有⌊n/5⌋组。
2. 对⌈n/5⌉组（包括可能不到5个数的那组）的组内数据进行直接插入排序，排序完成之后，图中白色的数据即为组内数据的中位数。 并将这⌈n/5⌉个中位数挑出来，具体做法见后面的代码。
3. 递归调用本算法找到这⌈n/5⌉个中位数的中位数，假设它为图中的x。
4. 假定n个数是互不相同的（后面会讨论一般情况），以x为枢轴对n个数的数组进行一趟划分，使得x左边的数＜x，x右边的数＞x。假设划分完成之后，x在数组中从左到右排在第k个。
5. 如果 i == k，那么x就是我们要找的数，return x; 即可；
   如果 i < k，那么递归调用本算法在x左边的数中继续找第 i 个数；
   如果 i > k，那么递归调用本算法在x右边的数中继续找第 i - k个数；

为什么这个算法是O(n)?

1. 第1、2、4步都是\(O(n)\)的。
   其中第2步\(O(n)\)是因为，对n/5组进行组内直接插入排序的时间复杂度是(n/5) * (5^2) = 5n，也就是\(O(n)\)。
2. 根据第1、2、3步我们可以知道，由于n个数是互不相同的，且x是中值的中值，则图中阴影部分的数据肯定都比x大，具体来说，比x大的数据至少有（因为左下角和右上角的数据与x大小关系未知）：
   
   其中，⌈n/5⌉是组的个数（包括可能不到5个数的那组)，-2是去掉x所在的组以及有可能不到5个数的那组。
   同理，在x左上角的那部分数据也肯定比x小，并且也至少有这么多。
   所以无论在第5步中是哪种情况，到下一次递归时最多有7n/10+6个数(减去至少的情况)。
3. 假设本算法的最坏时间复杂度是\(T(n)\)的，那么第3步的时间复杂度是\(T(⌈n/5⌉)\)，第5步的时间复杂度是\(T(7n/10+6)\)。假设对于n<140的情况，找第i个数是\(O(1)\)的。
4. 现在我们只要证明，对于任意的n>0，都成找到一个常数 c 使得\(T(n) ≤ cn\)，那么，这个算法就是\(O(n)\)的。
   
   假设式中\(O(n)\)项的常数因子为a，则有：

\(T(n)\le c\lceil n/5\rceil +c(7n/10+6)+an\le cn/5+c+7cn/10+6c+an=9cn/10+7c+an=cn+(-cn/10+7c+an)\)

如果\((-cn/10 + 7c + an) ≤ 0\)，那么\(T(n) ≤ cn\)。

即需要\((-cn/10+7c+an)\le 0\Rightarrow c\ge 10a(n/(n-70))\)。

当\(n≥140\)时，\(n/(n - 70) ≤ 2\)，只要取c = 20a即可使\(T(n) ≤ cn\)，亦即本算法是\(O(n)\)的。

所以，注意这里的魔数(magic constant)\(140\)并没有什么特别之处，我们可以用任何一个严格大于\(70\)的数替代它。

下面讨论如果n个数中有重复数的情况

由于在算法步骤中的第四步以及证明步骤中的第二步都假定个n个数互不相同，这样才能保证能有3n/10-6个数一定比x小，同时有3n/10-6个数一定比x大，这样无论i和k（x在数组中从左到右排在第k个）之间的大小关系是什么，总能下进入下一次递归时排除掉3n/10-6个数。

而事实上，如果n个数中有重复元素与x相同，比如100个数（中间省略的都是2）：

2 2 1 2 2 0 2  …… 2 2 1 2 3

这样≤2的数在前99个，大于2的数（只有3）在第100个，如果我们要找第5个数，那么按照前面的算法进入下次递归的是前99个数，

这显然不能满足“至少除掉3n/10-6个数”的假设。为了实现在这种情况下仍然是\(O(n)\)，需要DIY一下划分算法，具体来说：

将n个数划分成三部分，第一部分＜x，第二部分＝x，第三部分＞x。按上面的例子划分结果是（中间省略的都是2）：

1 0 1 2 2 2 2  …… 2 2 2 2 3

我们知道从左至右第一个出现的x在第4个，最后出现的x在第99个，那么：

1. 如果 i >= 4 && i <= 99，那么x就是我们要找的数，return x;即可；
2. 如果 i < 4，那么递归调用本算法在x左边的数中继续找第i 个数；
3. 如果 i > 99，那么递归调用本算法在x右边的数中继续找第 i - 99个数；

这样，就能够保证进入每次“至少除掉3n/10-6个数”了。

实现代码

int ithSmallestLinear(vector<int> a, int beg, int end, int i)
 {
      int len = end - beg + 1;
  
      if (len < 140)
      {
          sort(a.begin()+beg, a.begin()+len);
          return beg + i - 1;
      }
  
     //divide the n elements into ⌊n/5⌋ groups and sort each group
     for (int j = 0; j != len / 5; ++j)
     {
         int b = beg + j * 5;
         int e = b + 4;
         sort(a.begin()+b, a.begin()+(e-b+1));
         //move the median of each group to the front of the array
         swap(a, beg + j, b + 2);
     }
  
     //find the median of each median
     int pivotLoc = ithSmallestLinear(a, beg, len / 5 - 1, (len / 5 + 1) / 2);
  
     //the number of the elements that equal to the pivot
     int pivotNum = 0;
     int pivotEndIndex = partitionSpecifyPivot(a, beg, end, pivotLoc, &pivotNum);    
     int n = pivotEndIndex - beg + 1;
     int m = n - pivotNum + 1;
 
    // 第二部分 ＝x 情况
     if (i >= m && i <= n)
     {
         //return the index of the ith smallest element
         return pivotEndIndex;
     }
     else if (i < m)
     {
         return ithSmallestLinear(a, beg, pivotEndIndex - pivotNum, i);
     }
     else
     {
         return ithSmallestLinear(a, pivotEndIndex + 1, end, i - n);
     }
}

int partitionSpecifyPivot(int a[], int beg, int end, int pivotloc, int *pivotNum)
{
     int pivot = a[pivotloc];
      int i = beg - 1;
      int j = beg - 1;
 
     //<=pivot的数换到前面,共有j个
      for (int k = beg; k <= end; ++k)
      {
          if (a[k] <= pivot)
          {
              swap(a, ++j, k);
          }
      }
     // <pivot的数换到前面，共有k个
      for (int k = beg; k <= j; ++k)
      {
          if (a[k] < pivot)
          {
              swap(a, ++i, k);
          }
      }
      //pivotNum is the number of the elements that equal to the pivot
      if (pivotNum != NULL)
      {
          *pivotNum = j - i;
      }    
      return j;
}