O(n)级选排名第k位数（附上算法复杂度分析）

淩亂°似流年 2022-05-11 06:58 50阅读 0赞

## 算法简述 ##

如果想要拿到第k位，一般说复杂度都比较高。例如，用快排等方式，要用了O(nlogn)水平的时间复杂度。就算是用快排改进，每次在快排的基础上，只排剩下的一部分，在平均水平上，也会变成了O(nlogn)。

原因是，如果是第一个数本来就比较小，这样在快排的基础上，第一步根本都没有能够发生多少的移动。那么，这样子算法复杂度降低会特别慢的。

一个比较好的方式就是，如果**能保证每次都能有很大一个比例（重点！！）的数据会被排开**，而不是一开始的快排的改进只做常数级别的降维。

**算法描述：**

**假设**

*  数据规模是：n，查找的是第k位的数。

**第一步：**

*  先将所有的数据都进行分组，这里不妨假设每个组的数据的数值都是一个固定的数额。（对于不恰好等分的数据，另外再做处理，但是这里先不妨假设每个数据组的规模都是一致的。**每个组的数据规模都是一个固定的数！**，这里假设为**5**。在每个组内进行排序。

那么总的时间为：

n 5 ∗ 5 l o g ( 5 ) \\frac\{n\}\{5\}\*5log(5) 5n∗5log(5)  
其中，后者为每个组内排序的时间（其实无论是怎样的排序方式，但是由于每个组都是固定的数额，所以，后者怎么说都是一个参数），所以，这个步骤的算法复杂度为**O(n)**。

**第二步：**

*  对于每个组的可以通过线性时间直接拿到对应的**中位数**。

n 5 \\frac\{n\}\{5\} 5n

复杂度也是**O(n)**

**第三步：（关键的一步）**

想到这里，大家肯定能猜到了，我们现在就是要拿到**这些中位数的中位数**。  
但是由于，这个数组的长度是 **O(n)** 的，如果我们要用以前的方法的话，那么最后就会使得整个东西变成了更高的时间复杂度了。

**但是，这里，我们注意到，中位数本身就是一个选k的问题。**

所以，就可以用一个递归来操作。

假设整个操作的复杂度为 f ( n ) f(n) f(n)  
那么，这里的操作就是

f ( n 5 ) f(\\frac\{n\}\{5\}) f(5n)

**第四步：递归关键步骤**

*  再用快排的分步的那种操作，将所找到的那个数字来放在中间，将整个数组进行划分。
 *  我们很容易可以留意到，这个操作最少可以把 n 4 \\frac\{n\}\{4\} 4n的数据给不用考虑了。最多甚至连 3 n 4 \\frac\{3n\}\{4\} 43n的数据都不用考虑了。

但是这一步的操作，所需要的时间复杂度是：

O ( n ) O(n) O(n)

通过这一步的描述，任然可以得到算法的复杂度问题。（**多个O(n)相加任然是O(n)**）

**递推公式为：**

f ( n ) = f ( n 5 ) + f ( 3 n 4 ) + O ( n ) f(n) = f(\\frac\{n\}\{5\}) + f (\\frac\{3n\}\{4\}) + O(n) f(n)=f(5n)\+f(43n)\+O(n)

通过这个递推公式，我们很容易就可以推理出来， f ( n ) f(n) f(n)的复杂度为 O ( n ) O(n) O(n)。

这里为 **O(n)** 的原因就是每次的降低比例和算法中前面的系数乘起来是小于1的。

### 简单推理计算递推公式 ###

**对这块没兴趣的，可以跳过了，直接看代码就好了。**

*  首先，我们假设整个算法的复杂度为**多项式级**的复杂度。（这里很容易通过放缩来获得证明。）
 *  对于**多项式的指数大于等于1**的情况下，下面的两个式子很容易发现是成立的。
 *   f ( n 5 ) < f ( 21 n 100 ) f(\\frac\{n\}\{5\})<f(\\frac\{21n\}\{100\}) f(5n)<f(10021n)
 *   f ( a ) + f ( b ) < = f ( a + b ) f(a) +f(b)<= f(a+b) f(a)\+f(b)<=f(a\+b)
 *  所以 f ( n 5 ) + f ( 3 n 4 ) < f ( 96 n 100 ) f(\\frac\{n\}\{5\}) + f (\\frac\{3n\}\{4\})<f(\\frac\{96n\}\{100\}) f(5n)\+f(43n)<f(10096n)，即得证。
 *  部分人发信息给我，到这一步可能还有些不懂
    
     *   f ( n ) = f ( α ∗ n ) + O ( n ) f(n) = f(\\alpha \* n) + O(n) f(n)=f(α∗n)\+O(n) 当 α \\alpha α在（0,1）之间时，不妨设O(n) = cn ，c是一个固定常数。（**可能有余项b，但是就算是n个也只会是O(n)所以这里就不用考虑了**）
     *   f ( n ) = f ( α ∗ n ) + c ∗ n = f ( α k ∗ n ) + c ∗ n ∗ 1 − α k 1 − α f(n) = f(\\alpha \* n) + c\*n =f(\\alpha^k \* n) + c\*n\*\\frac\{1-\\alpha^k\}\{1-\\alpha\} f(n)=f(α∗n)\+c∗n=f(αk∗n)\+c∗n∗1−α1−αk
     *  因为只有一个数字的时候，排序为O(1)的，这里就有  k = log ⁡ α 1 n k = \\log\_\{\\alpha\}\{\\frac\{1\}\{n\}\} k=logαn1
     *  就有 f ( n ) = O ( 1 ) + c ∗ n ∗ 1 − 1 / n 1 − α < O ( 1 ) + c ∗ n ∗ 1 1 − α f(n)=O(1) + c\*n\*\\frac\{1-1/n\}\{1-\\alpha\} < O(1) + c\*n\*\\frac\{1\}\{1-\\alpha\} f(n)=O(1)\+c∗n∗1−α1−1/n<O(1)\+c∗n∗1−α1
     *  很容易就知道，当 α \\alpha α属于（0,1）之间的时候，即为O(n)的复杂度

## 代码 ##

#include <iostream>
    #include <algorithm>
    using namespace std;
    int select(int n, int *arr, int begin, int k);
    int partition(int *arr, int begin, int end);
    int main(){ 
    	int n, *arr, k;
    	cin >> n;
    	arr = new int[n];
    	for (int i = 0; i < n; ++i)  cin >> arr[i];
    	cin >> k;
    	cout << select(n, arr, 0, k)<< endl;
    	delete[] arr;
    }
    
    int partition(int *arr, int begin, int end) { 
    	if (begin >= end) return arr[begin];
    	int i = begin, j = end;
    	int flag = arr[begin];
    	while (i < j) { 
    		while (i < j && flag < arr[j]) j--;
    		if (i < j) arr[i] = arr[j];
    		while (i < j && arr[i] < flag) i++;
    		if (i < j) arr[j] = arr[i];
    	}
    	arr[i] = flag;
    	return i - begin;
    }
    
    int select(int n, int *arr, int begin, int k) { 
    	if (n == 1) return arr[begin];
    	int end_ = 0;
    	for (int i = 0; i < n; i += 5) { 
    		end_ = (i + 5 <= n? i + 5: n);
    		sort(arr + begin + i, arr + begin + end_);
    	}
    
    	int mid_len = n / 5 + (n % 5 != 0), mid_index;
    	int *arr_ = new int [mid_len];
    
    	for (int i = 0; i < mid_len; ++i) { 
    		if (n - 5*i - 2 > 0) arr_[i] = arr[begin + 5*i + 2];
    		else arr_[i] = arr[begin + 5*i + 1];
    	}
    	int mid_k = select(mid_len, arr_, 0, mid_len / 2 + (mid_len % 2 != 0));
    
    	int index = 0;
    	for (int i = 0; i < n; i ++) { 
    		if (mid_k == arr[begin + i]){  index = i; break; }
    	}
    	int temp = arr[begin];
    	arr[begin] = mid_k;
    	arr[begin + index] = temp;
    	temp = partition(arr, begin, begin + n-1);
    	delete []arr_;
    	if (temp == k) return mid_k;
    	else if (temp > k) select(temp, arr, begin, k);
    	else if (temp < k) select(n - temp - 1, arr, temp + 1, k - temp - 1);
    }

又根据书上的算法描述写了另外一个版本。

#include <iostream>
    #include <algorithm>
    using namespace std;
    int select(int *arr, int n, int k);
    int main() {
    	int n, *arr, k;
    	cin >> n;
    	arr = new int[n];
    	for (int i = 0; i < n; ++i)  cin >> arr[i];
    	cin >> k;
    	cout << select(arr, n, k) << endl;
    	delete[] arr;
    	system("pause");
    }
    
    
    int select(int *arr, int n, int k) {
    
    	if (n <= 5) {
    		sort(arr, arr + n);
    		return arr[k - 1]; // 返回第k个元素
    	}
    
    	// 满五个才凑成一组
    	int *mid_ = new int[n / 5];
    	for (int i = 0; i < n / 5; ++i)
    	{
    		sort(arr + i * 5, arr + i * 5 + 5);
    		mid_[i] = arr[5 * i + 2];
    	}
    	int m = select(mid_, n / 5, n / 10 + (n / 5) % 2);
    	int* bigger = new int[3 * n / 4];
    	int* smaller = new int[3 * n / 4];
    	int* equal = new int[3 * n / 4];
    	int i = 0, j = 0, s = 0, t = 0;
    	for (t = 0; t < n; ++t) {
    		if (arr[t] > m)
    			bigger[i++] = arr[t];
    		else if (arr[t] == m)
    			equal[j++] = arr[t];
    		else
    			smaller[s++] = arr[t];
    	}
    	int ans;
    	if (s > k)
    		ans = select(smaller, s, k);
    	else if (s + j > k)
    		ans = m;
    	else
    		ans = select(bigger, i, k - s - j);
    
    	delete[] mid_; delete[] bigger; delete[] smaller; delete[] equal;
    	return ans;
    }