算法簡(jiǎn)述

如果想要拿到第k位，一般說(shuō)復(fù)雜度都比較高。例如，用快排等方式，要用了O(nlogn)水平的時(shí)間復(fù)雜度。就算是用快排改進(jìn)，每次在快排的基礎(chǔ)上，只排剩下的一部分，在平均水平上，也會(huì)變成了O(nlogn)。

原因是，如果是第一個(gè)數(shù)本來(lái)就比較小，這樣在快排的基礎(chǔ)上，第一步根本都沒(méi)有能夠發(fā)生多少的移動(dòng)。那么，這樣子算法復(fù)雜度降低會(huì)特別慢的。

一個(gè)比較好的方式就是，如果能保證每次都能有很大一個(gè)比例（重點(diǎn)！！）的數(shù)據(jù)會(huì)被排開(kāi)，而不是一開(kāi)始的快排的改進(jìn)只做常數(shù)級(jí)別的降維。

算法描述：

假設(shè)

• 數(shù)據(jù)規(guī)模是：n，查找的是第k位的數(shù)。

第一步：

• 先將所有的數(shù)據(jù)都進(jìn)行分組，這里不妨假設(shè)每個(gè)組的數(shù)據(jù)的數(shù)值都是一個(gè)固定的數(shù)額。（對(duì)于不恰好等分的數(shù)據(jù)，另外再做處理，但是這里先不妨假設(shè)每個(gè)數(shù)據(jù)組的規(guī)模都是一致的。每個(gè)組的數(shù)據(jù)規(guī)模都是一個(gè)固定的數(shù)！，這里假設(shè)為5。在每個(gè)組內(nèi)進(jìn)行排序。

那么總的時(shí)間為：

$$\frac{n}{5}?5log(5)$$
其中，后者為每個(gè)組內(nèi)排序的時(shí)間（其實(shí)無(wú)論是怎樣的排序方式，但是由于每個(gè)組都是固定的數(shù)額，所以，后者怎么說(shuō)都是一個(gè)參數(shù)），所以，這個(gè)步驟的算法復(fù)雜度為O(n)。

第二步：

• 對(duì)于每個(gè)組的可以通過(guò)線性時(shí)間直接拿到對(duì)應(yīng)的中位數(shù)。

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

復(fù)雜度也是O(n)

第三步：（關(guān)鍵的一步）

想到這里，大家肯定能猜到了，我們現(xiàn)在就是要拿到這些中位數(shù)的中位數(shù)。
但是由于，這個(gè)數(shù)組的長(zhǎng)度是 O(n) 的，如果我們要用以前的方法的話，那么最后就會(huì)使得整個(gè)東西變成了更高的時(shí)間復(fù)雜度了。

但是，這里，我們注意到，中位數(shù)本身就是一個(gè)選k的問(wèn)題。

所以，就可以用一個(gè)遞歸來(lái)操作。

假設(shè)整個(gè)操作的復(fù)雜度為$f(n)$
那么，這里的操作就是

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

第四步：遞歸關(guān)鍵步驟

• 再用快排的分步的那種操作，將所找到的那個(gè)數(shù)字來(lái)放在中間，將整個(gè)數(shù)組進(jìn)行劃分。
• 我們很容易可以留意到，這個(gè)操作最少可以把$\frac{n}{4}$的數(shù)據(jù)給不用考慮了。最多甚至連$\frac{3n}{4}$的數(shù)據(jù)都不用考慮了。

但是這一步的操作，所需要的時(shí)間復(fù)雜度是：

$$O(n)$$

通過(guò)這一步的描述，任然可以得到算法的復(fù)雜度問(wèn)題。（多個(gè)O(n)相加任然是O(n)）

遞推公式為：

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

通過(guò)這個(gè)遞推公式，我們很容易就可以推理出來(lái)，$f(n)$的復(fù)雜度為$O(n)$。

這里為 O(n) 的原因就是每次的降低比例和算法中前面的系數(shù)乘起來(lái)是小于1的。

簡(jiǎn)單推理計(jì)算遞推公式

對(duì)這塊沒(méi)興趣的，可以跳過(guò)了，直接看代碼就好了。

• 首先，我們假設(shè)整個(gè)算法的復(fù)雜度為多項(xiàng)式級(jí)的復(fù)雜度。（這里很容易通過(guò)放縮來(lái)獲得證明。）
• 對(duì)于多項(xiàng)式的指數(shù)大于等于1的情況下，下面的兩個(gè)式子很容易發(fā)現(xiàn)是成立的。
• $f(\frac{n}{5})<f(\frac{21n}{100})$
• $f(a)+f(b)<=f(a+b)$
• 所以$f(\frac{n}{5})+f(\frac{3n}{4})<f(\frac{96n}{100})$，即得證。
• 部分人發(fā)信息給我，到這一步可能還有些不懂
  • $f(n)=f(\alpha ?n)+O(n)$ 當(dāng)$\alpha$在（0,1）之間時(shí)，不妨設(shè)O(n) = cn ，c是一個(gè)固定常數(shù)。（可能有余項(xiàng)b，但是就算是n個(gè)也只會(huì)是O(n)所以這里就不用考慮了）
  • $f(n)=f(\alpha ?n)+c?n=f({\alpha }^k?n)+c?n?\frac{1?{\alpha }^k}{1?\alpha }$
  • 因?yàn)橹挥幸粋€(gè)數(shù)字的時(shí)候，排序?yàn)镺(1)的，這里就有 $k={\log }_{\alpha }\frac{1}{n}$
  • 就有$f(n)=O(1)+c?n?\frac{1?1/n}{1?\alpha }<O(1)+c?n?\frac{1}{1?\alpha }$
  • 很容易就知道，當(dāng)$\alpha$屬于（0,1）之間的時(shí)候，即為O(n)的復(fù)雜度

代碼

#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); }

又根據(jù)書(shū)上的算法描述寫(xiě)了另外一個(gè)版本。

#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個(gè)元素}// 滿五個(gè)才湊成一組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];elsesmaller[s++] = arr[t];}int ans;if (s > k)ans = select(smaller, s, k);else if (s + j > k)ans = m;elseans = select(bigger, i, k - s - j);delete[] mid_; delete[] bigger; delete[] smaller; delete[] equal;return ans; }

總結(jié)

以上是生活随笔為你收集整理的O(n)级选排名第k位数（附上算法复杂度分析）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。