最壞情況為線性時間的選擇算法

• 參考：【算法】算法導(dǎo)論：https://www.bilibili.com/video/BV1Tb411M7FA?p=6

提出問題：從一個數(shù)組中找到第K個最大數(shù)字，即TOPK問題，這個題目在面試和研究中經(jīng)常遇到，那么，這個題目應(yīng)該怎么解決呢？

• 理所當(dāng)然的我們會想到排序，我們可以使用排序算法將數(shù)組變得有順序，然后直接選取，使用快速排序，歸并排序，或者是堆排序，都可以使得時間復(fù)雜度是 O(nlgn)
• 建堆，取出前K個數(shù)字，當(dāng)k 接近于 0，或者是數(shù)組長度的時間，其時間復(fù)雜度幾乎是線性的，但是如果當(dāng)K 趨于中位數(shù)的時候，復(fù)雜度會變?yōu)?nlgn

今天我們要介紹的一種算法，使得選取TOPK的時間復(fù)雜度是O（n），即最壞情況為線性時間的選擇算法（算法導(dǎo)論，YYDS）。

1：詳解算法

• 將數(shù)組劃分為若干個數(shù)組，每個子數(shù)組中包含5個元素。由于數(shù)組的長度不一定是5的整數(shù)倍，所以允許最后一個數(shù)組的長度 小于5
• 找到每個子數(shù)組的中位數(shù)，放在每個子數(shù)組的二號位置上，即所有的中位數(shù)排列成一條直線
• 將獲得的中位數(shù)遞歸的調(diào)用select，找到中位數(shù)的中位數(shù)，即一條直線上的中位數(shù)
• 將原來的數(shù)組使用類似快拍的方法，分成兩個部分。讓K比劃分的低區(qū)的元素的數(shù)目多一個，因此X 是第K小的元素，并且有 n - k 個元素在劃分的高區(qū)。
• 如果 i = k，則說明我們找到了
  • 如果 i < k，則在低區(qū)遞歸的調(diào)用來找到第 i 小的元素。
  • 如果 i > k，則在高區(qū)遞歸的調(diào)用查找第 i - k小的元素（k個最小的我們已經(jīng)去掉了，故在后面的數(shù)組中查找第 i - k 小的元素）

2：代碼實(shí)現(xiàn)

#include <stdlib.h> #include <stdio.h> #define swap(a,b) (a)^=(b);(b)^=(a);(a)^=(b) #define MAX 1000void sort(int* input, int size){printf ( "sort arry size = %d\n", size );int i,j;for(i = 0; i< size ; i++){for(j = 0; j<size-i-1;j++){if(input[j]<input[j+1]){swap(input[j],input[j+1]);}}} } void output(int * input, int size){for(;size>0 && *input;size--,input++){printf("%d ", *input);}printf("\n");}int partion(int *input, int size, int key){printf ( "--------------Step4---------------\n" );printf("key = %d \n", input[key]);int *head, *tail;head = input;tail = head + size - 1;swap(*head, input[key]);int *k = head;while(head<tail){while(*tail && *k >= *tail){tail--;}if(tail<=head) break;swap(*k,*tail);k = tail;while(*head && *k < *head)head++;if(head>=tail) break;swap(*k,*head);k = head;}output(input, size);printf ( "--------------Step4 done--------------\n" );return k-input+1; }int kselect(int *input, int size, int k){printf ( "start element : %d \n", *input );if(size<=5){sort(input, size);return input[k-1];}int mid[MAX] = {0};int midvalue[MAX] = {0};int groups = size/5;int i;printf ( "-----------------step 1, 2--------------\n" );for(i = 0; i<groups;i++){sort(input+i*5, (i*5+5 > size) ? (size-1):5);printf ( "sorted group %d:\n", i );output(input+i*5, 5);mid[i] = i*5 + 2;midvalue[i] = input[i*5 + 2];}printf ( "-----------------step 1, 2 done--------------\n" );printf ( "---------step3-------------\n" );sort(midvalue, groups);printf ( "---------step3 done-------\n" );int m = -1;for(i = 0; i<5;i++){if(input[mid[i]] == midvalue[groups/2]){m = partion(input, size, mid[i]);}}if(m == k){return input[m-1];}if(k<m){return kselect(input,m,k);}else{return kselect(input+m, size - m, k-m);}return 0xffff; }int main(){int input[] = {1,3,2,10,5,11, 12, 8 ,6, 7};　　　　　/*輸出第７大的元素．*/int r = kselect(input,sizeof(input)/sizeof(int), 7);printf("result %d \n", r);return 0; }

3：關(guān)于作者

• 這個算法是由Blum，Floyd，Pratt，Rivest，Tarjan設(shè)計(jì)的。我剛開始看到這個，只認(rèn)識Floyd。我絲毫沒有意識到這里面的水有多深
  • Floyd，唯一熟悉的一個人。學(xué)習(xí)過Floyd算法，該算法可以計(jì)算出圖中任意兩個定點(diǎn)的距離，權(quán)重可以為負(fù)數(shù)，效率高于dijkstra算法。1978年Turing
  • Blum，在整數(shù)分解中，Blum Blum Shub加密算法中的第二個Blum就是他。 1995年Turing
  • Pratt，KMP算法中的P就是他！嗯？KMP怎么寫來著？
  • Rivest，RSA加密算法的發(fā)現(xiàn)者。RSA是對稱加密還是非對稱加密？他由此2002年獲得了Turing award
  • Tarjan，圖論的研究專家，發(fā)明了LCA（最近公共祖先），強(qiáng)連通分量算法。并且也發(fā)明了斐波拉契堆和splay數(shù)據(jù)結(jié)構(gòu)。并且他分析了并查集，在1986年獲得了Turing
• 幾乎全員Turing，每一個人都對計(jì)算機(jī)科學(xué)的發(fā)展做出了相當(dāng)杰出的貢獻(xiàn)！其中Tarjan是Floyd 和knuth的學(xué)生。Knuth是The Art of Computer Programming的作者，tex的發(fā)明者。36歲獲得Turing。

4：小思考

• 該算法把數(shù)組分成長度為5的小數(shù)組，為什么是5呢？
  • 3可以嗎？
  • 7可以嗎？

總結(jié)

以上是生活随笔為你收集整理的最坏情况为线性时间的选择算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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