 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 查看: 9821 | 回復(fù): 34 | ||||||||||||||||||||||||
[交流]
28個不得不看的經(jīng)典編程算法��！ 已有34人參與
|
|
前十個是來自圣經(jīng)的十大算法： 發(fā)起人的描述：《來自圣經(jīng)的證明》收集了數(shù)十個簡潔而優(yōu)雅的數(shù)學(xué)證明，迅速贏得了大批數(shù)學(xué)愛好者的追捧。如果還有一本《來自圣經(jīng)的算法》，哪些算法會列入其中呢？ 第一名：Union-find 嚴格地說，并查集是一種數(shù)據(jù)結(jié)構(gòu)，它專門用來處理集合的合并操作和查詢操作。并查集巧妙地借用了樹結(jié)構(gòu)，使得編程復(fù)雜度降低到了令人難以置信的地步；用上一些遞歸技巧后，各種操作幾乎都能用兩行代碼搞定。而路徑壓縮的好主意，更是整個數(shù)據(jù)結(jié)構(gòu)的畫龍點睛之筆。并查集的效率極高，單次操作的時間復(fù)雜度幾乎可以看作是常數(shù)級別；但由于數(shù)據(jù)結(jié)構(gòu)的實際行為難以預(yù)測，精確的時間復(fù)雜度分析需要用到不少高深的技巧。 第二名：Knuth-Morris-Pratt字符串匹配算法 關(guān)于此算法的介紹，請參考此文：六、教你從頭到尾徹底理解KMP算法。KMP算法曾經(jīng)落選于二十世紀最偉大的十大算法，但人們顯然不能接受，如此漂亮、高效的KMP算法竟然會落選。所以，此次最終投票產(chǎn)出生，KMP算法排到了第二名。 第三名：BFPRT 算法 1973 年，Blum、Floyd、Pratt、Rivest、Tarjan集體出動，合寫了一篇題為 “Time bounds for selection” 的論文，給出了一種在數(shù)組中選出第 k 大元素的算法，俗稱"中位數(shù)之中位數(shù)算法"。依靠一種精心設(shè)計的 pivot 選取方法，該算法從理論上保證了最壞情形下的線性時間復(fù)雜度，打敗了平均線性、最壞 O(n^2) 復(fù)雜度的傳統(tǒng)算法。一群大牛把遞歸算法的復(fù)雜度分析玩弄于骨掌股掌之間，構(gòu)造出了一個當(dāng)之無愧的來自圣經(jīng)的算法。 我在這里簡單介紹下在數(shù)組中選出第k大元素的時間復(fù)雜度為O（N）的算法： 類似快排中的分割算法： 每次分割后都能返回樞紐點在數(shù)組中的位置s,然后比較s與k的大小 若大的話，則再次遞歸劃分array[s..n]， 小的話，就遞歸array[left...s-1] //s為中間樞紐點元素。 否則返回array[s]，就是partition中返回的值。 //就是要找到這個s。 找到符合要求的s值后，再遍歷輸出比s小的那一邊的元素。 各位可參考在：算法導(dǎo)論上，第九章中，以期望線性時間做選擇，一節(jié)中， 我找到了這個 尋找數(shù)組中第k小的元素的，平均時間復(fù)雜度為O（N）的證明：上述程序的期望運行時間，最后證明可得O(n)，且假定元素是不同的。 第四名：Quicksort（快速排序） 快速排序算法幾乎涵蓋了所有經(jīng)典算法的所有榜單。它曾獲選二十世紀最偉大的十大算法（參考這：細數(shù)二十世紀最偉大的10大算法）。關(guān)于快速排序算法的具體介紹，請參考我寫的這篇文章：一之續(xù)、快速排序算法的深入分析，及十二、快速排序算法之所有版本的c/c++實現(xiàn)。 第五名：Floyd-Warshall all-pairs最短路徑算法 關(guān)于此算法的介紹，可參考我寫的此文：幾個最短路徑算法比較（http://blog.csdn.net/v_JULY_v/archive/2011/02/12/6181485.aspx）。 d[]: 二維數(shù)組. d[i,j]最小花費、或最短路徑的鄰邊。 for k from 1 to n: for i from 1 to n: for j from 1 to n: d[i,j] = min(d[i,j], d[i,k] + d[k,j]) 第六名：Gentry's Fully Homomorphic Encryption Scheme（紳士完全同態(tài)加密機制）算法。 此算法很漂亮，它允許第三方執(zhí)行任意加密數(shù)據(jù)運算得不到私鑰（不是很了解）。 第七名：Depth First Search、Breadth First Search（深度、廣度優(yōu)先搜索） 它們是許多其他算法的基礎(chǔ)。關(guān)于深度、廣度優(yōu)先搜索算法的具體介紹，請參考此文：教你通透徹底理解：BFS和DFS優(yōu)先搜索算法。 第八名：Miller-Rabin作的類似的試驗測試 這個想法是利用素數(shù)的性質(zhì)(如使用費馬大定理)的小概率尋找見證不數(shù)素數(shù)。如果沒有證據(jù)是足夠的隨機檢驗后發(fā)現(xiàn),這一數(shù)字為素數(shù)。 第九名：Binary Search （二分查找） 在一個有序的集合中查找元素，可以使用二分查找算法，也叫二分搜索。二分查找算法先比較位于集合中間位置的元素與鍵的大小，有三種情況（假設(shè)集合是從小到大排列的）： 1.鍵小于中間位置的元素，則匹配元素必在左邊（如果有的話），于是對左邊的區(qū)域應(yīng)用二分搜索。 2.鍵等于中間位置的元素，所以元素找到。 3.鍵大于中間位置的元素，則匹配元素必在右邊（如果有的話），于是對右邊的區(qū)域應(yīng)用二分搜索。 另外，當(dāng)集合為空，則代表找不到。 第十名：Huffman coding（霍夫曼編碼） 霍夫曼編碼(Huffman Coding)是一種編碼方式，是一種用于無損數(shù)據(jù)壓縮的熵編碼（權(quán)編碼）算法。1952年，David A. Huffman在麻省理工攻讀博士時所發(fā)明的，并發(fā)表于《一種構(gòu)建極小多余編碼的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。 十一、Cooley-Tukey FFT算法�？焖俑道锶~變換算法。關(guān)于傅里葉變換算法的介紹，請參考此文：十、從頭到尾徹底理解傅里葉變換算法、上，及十、從頭到尾徹底理解傅里葉變換算法、下。 十二、linear programming，線性規(guī)劃。 十三、Dijkstra 算法。與上第五一樣，又一種最短路徑算法。具體介紹，請參考：二之續(xù)、徹底理解Dijkstra算法，和二（再續(xù)）、Dijkstra 算法+fibonacci堆的逐步c實現(xiàn)。 十四、Merge Sort。歸并排序。 十五、Ford–Fulkerson算法。網(wǎng)絡(luò)最大流算法。 十六、輾轉(zhuǎn)相除法。 在數(shù)學(xué)中，輾轉(zhuǎn)相除法，又稱歐幾里得算法，是求最大公約數(shù)的算法，即求兩個正整數(shù)之最大公因子的算法。此算法作為TAOCP第一個算法被闡述，足見此算法被重視的程度。它是已知最古老的算法, 其可追溯至3000年前。輾轉(zhuǎn)相除法首次出現(xiàn)于歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現(xiàn)的《九章算術(shù)》。擴展的輾轉(zhuǎn)相除法則構(gòu)造性地證明了，對任意整數(shù)a和b ，存在一對x、y使得 ax + by = gcd(a, b) 。 十七、RSA加密演算法。一種加密算法，日后再做詳細介紹。 十八、遺傳算法�？蓞⒖急救藢懙年P(guān)于GA 算法的這篇文章：七、遺傳算法 透析GA本質(zhì)。 十九、最大期望（EM）算法。 此算法入選數(shù)據(jù)挖掘領(lǐng)域十大經(jīng)典算法。在統(tǒng)計計算中，最大期望（EM）算法是在概率（probabilistic）模型中尋找參數(shù)最大似然估計的算法，其中概率模型依賴于無法觀測的隱藏變量（Latent Variable）。最大期望經(jīng)常用在機器學(xué)習(xí)和計算機視覺的數(shù)據(jù)聚類（Data Clustering）領(lǐng)域。最大期望算法經(jīng)過兩個步驟交替進行計算，第一步是計算期望（E），利用對隱藏變量的現(xiàn)有估計值，計算其最大似然估計值；第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數(shù)的值。M 步上找到的參數(shù)估計值被用于下一個 E 步計算中，這個過程不斷交替進行。 二十、數(shù)據(jù)壓縮 數(shù)據(jù)壓縮是通過減少計算機中所存儲數(shù)據(jù)或者通信傳播中數(shù)據(jù)的冗余度，達到增大數(shù)據(jù)密度，最終使數(shù)據(jù)的存儲空間減少的技術(shù)。數(shù)據(jù)壓縮在文件存儲和分布式系統(tǒng)領(lǐng)域有著十分廣泛的應(yīng)用。數(shù)據(jù)壓縮也代表著尺寸媒介容量的增大和網(wǎng)絡(luò)帶寬的擴展。 二十一、Hash函數(shù) Hash，一般翻譯做“散列”，也有直接音譯為“哈�！钡�，就是把任意長度的輸入（又叫做預(yù)映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。關(guān)于hash表的詳細闡述，請參考此篇文章：十一、從頭到尾徹底解析Hash表算法。 二十二、Dynamic Programming（動態(tài)規(guī)劃）。關(guān)于動態(tài)規(guī)劃的粗略介紹，請參考此文：三、dynamic programming。 二十三、堆排序算法。 堆排序算法作為一種快速穩(wěn)定的算法，其平均時間復(fù)雜度（最壞也為）O（n*lgn）。當(dāng)然，在實際應(yīng)用中，一個實現(xiàn)的好的快速排序算法仍然要優(yōu)于堆排序算法。不過，堆數(shù)據(jù)結(jié)構(gòu)還可以作為高效的優(yōu)先級隊列。對堆排序算法作簡單了解，可參考這：堆排序算法。 二十四、遞歸與回溯算法。此倆個算法，相信各位比較熟悉，在此不做贅述。 二十五、最長公共子序列 最長公共子序列，英文縮寫為LCS（Longest Common Subsequence）。其定義是，一個數(shù)列 S ，如果分別是兩個或多個已知數(shù)列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。 動態(tài)規(guī)劃的一個計算最長公共子序列的方法如下： 以兩個序列 X、Y 為例子： 設(shè)有二維數(shù)組 f[j] 表示 X 的 i 位和 Y 的 j 位之前的最長公共子序列的長度，則有： f[1][1] = same(1,1) f[j] = max{f[i-1][j-1]+same(i,j)，f[i-1][j]，f[j-1]} 其中，same(a,b)當(dāng) X 的第 a 位與 Y 的第 b 位完全相同時為“1”，否則為“0”。 此時，f[j]中最大的數(shù)便是 X 和 Y 的最長公共子序列的長度，依據(jù)該數(shù)組回溯，便可找出最長公共子序列。 該算法的空間、時間復(fù)雜度均為O(n2)，經(jīng)過優(yōu)化后，空間復(fù)雜度可為O(n)，時間復(fù)雜度為O(nlogn)。更多詳情，參見之前寫的一篇拙文（不過，鑒于寫的糟，日后會重寫）：三、dynamic programming。 二十六、紅黑樹的算法與實現(xiàn) 關(guān)于紅黑樹，linux內(nèi)核中有實現(xiàn)，本BLOG內(nèi)也已經(jīng)寫了4篇紅黑樹系列的文章。詳情，請參考：五（續(xù)）、教你透徹了解紅黑樹。 二十七、A*搜尋算法。 相對于BFS、Dijkstra 等算法，A*搜尋算法作為一種高效的最短路徑搜索算法，如今，已得到日益廣泛的應(yīng)用。初步了解A*搜尋算法的高效及與其它最短路徑算法的比較，請參考此文：一（續(xù)）、A*，Dijkstra，BFS算法性能比較及A*算法的應(yīng)用。 二十八、圖像特征提取與匹配之SIFT算法 sift，尺度不變特征轉(zhuǎn)換，是一種電腦視覺的算法用來偵測與描述影像中的局部性特征，它在空間尺度中尋找極值點，并提取出其位置、尺度、旋轉(zhuǎn)不變量，此算法由 David Lowe 在1999年所發(fā)表，2004年完善總結(jié)。關(guān)于此算法，請參考如下，粗略介紹：九、圖像特征提取與匹配之SIFT算法，利用第三方庫編譯過程：九（續(xù)）、sift算法的編譯與實現(xiàn)，c語言一步一步實現(xiàn)sift算法：九之再續(xù)：一步一步用c語言實現(xiàn)sift算法、上，及九之再續(xù)：教你一步一步用c語言實現(xiàn)sift算法、下。 |
回復(fù)此樓» 收錄本帖的淘帖專輯推薦
 先進材料與分子模擬 | 模式識別-圖像處理-水印-隱藏 | 模擬與仿真 | c++及c |
| 小波變換 | 數(shù)學(xué)分析 | 精品收藏 | 電腦網(wǎng)絡(luò)電子書軟件 |
| source | 專業(yè)課件 | Algorithm | 學(xué)習(xí) |
| 各種資料 | 數(shù)據(jù)結(jié)構(gòu)與算法 | 注會 | 臨時記錄 |
| 很好的資料 | 夢落梅梢 | 日積月累 | 一一集 |
| 計算機相關(guān) |
» 本帖已獲得的紅花（最新10朵）
想飛的豬» 猜你喜歡
0703化學(xué)調(diào)劑 ，六級已過，有科研經(jīng)歷
已經(jīng)有8人回復(fù)
-
268求調(diào)劑
已經(jīng)有8人回復(fù)
-
材料，紡織，生物（0856、0710），化學(xué)招生啦
已經(jīng)有7人回復(fù)
-
301求調(diào)劑
已經(jīng)有5人回復(fù)
-
281求調(diào)劑（0805）
已經(jīng)有7人回復(fù)
-
材料與化工求調(diào)劑
已經(jīng)有6人回復(fù)
-
299求調(diào)劑
已經(jīng)有4人回復(fù)
-
277調(diào)劑
已經(jīng)有6人回復(fù)
-
341求調(diào)劑
已經(jīng)有7人回復(fù)
-
328求調(diào)劑，英語六級551，有科研經(jīng)歷
已經(jīng)有8人回復(fù)
» 本主題相關(guān)價值貼推薦，對您同樣有幫助:
- MATLAB經(jīng)典算法程序
已經(jīng)有531人回復(fù)
- 關(guān)于遺傳算法中交叉的程序
已經(jīng)有5人回復(fù)
- 遺傳算法的一段程序請教解釋
已經(jīng)有9人回復(fù)
- 請教關(guān)于遺傳算法編程的問題（俺是小白）
已經(jīng)有4人回復(fù)
- 【討論】線性預(yù)測編碼中Levinson-Durbin算法在音頻信號去相關(guān)應(yīng)用中的問題
已經(jīng)有6人回復(fù)
- 【求助】VC++數(shù)值算法集應(yīng)用到MFC中報錯，程序調(diào)試求助
已經(jīng)有8人回復(fù)
- 【求助】多目標pso算法的MATLAB程序
已經(jīng)有3人回復(fù)
- 【分享】C/C++常用算法設(shè)計方法,fortran其他語言編程也可以參考下
已經(jīng)有8人回復(fù)
- 【討論】ZZ個人開發(fā)的人臉識別軟件，大家可以來比較一下算法能力
已經(jīng)有9人回復(fù)
- 【求助】算法書籍
已經(jīng)有11人回復(fù)
- C數(shù)值算法程序大全
已經(jīng)有7人回復(fù)
imyourkobe
鐵桿木蟲 (著名寫手)
- 應(yīng)助: 26 (小學(xué)生)
- 貴賓: 0.126
- 金幣: 7477
- 散金: 6
- 紅花: 9
- 沙發(fā): 3
- 帖子: 1688
- 在線: 459.5小時
- 蟲號: 183723
- 注冊: 2006-02-13
- 專業(yè): 計算機軟件
2樓2011-10-23 19:29:47
3樓2011-11-01 11:38:29
 |
4樓2011-11-01 15:54:51
 |
5樓2011-11-01 16:25:00
6樓2011-11-26 00:37:04
yongyux
新蟲 (小有名氣)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 520.3
- 帖子: 87
- 在線: 47.6小時
- 蟲號: 1384420
- 注冊: 2011-08-30
- 專業(yè): 聲學(xué)
7樓2011-11-29 16:33:23
roadbb
新蟲 (初入文壇)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 5.3
- 帖子: 33
- 在線: 5.1小時
- 蟲號: 1511928
- 注冊: 2011-11-27
- 性別: GG
- 專業(yè): 制造系統(tǒng)與自動化
8樓2011-11-30 13:48:38
liuxuanli
新蟲 (初入文壇)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 9.5
- 帖子: 3
- 在線: 57分鐘
- 蟲號: 1517600
- 注冊: 2011-11-30
- 專業(yè): 計算機網(wǎng)絡(luò)
9樓2011-12-01 12:23:35
le_tian68
鐵蟲 (小有名氣)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 34.5
- 散金: 10
- 帖子: 109
- 在線: 95.7小時
- 蟲號: 713187
- 注冊: 2009-03-02
- 專業(yè): 信號理論與信號處理
10樓2011-12-04 02:54:43
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 zh6570328 的主題更新
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 268求調(diào)劑 +8 | 一定有學(xué)上- 2026-03-14 | 9/450 |
|
|---|---|---|---|---|
|
[考研] 材料專碩306英一數(shù)二 +7 | z1z2z3879 2026-03-16 | 9/450 |
|
|
|
[考研] 304求調(diào)劑 +8 | 小熊joy 2026-03-14 | 8/400 |
|
|
|
[考研] 344求調(diào)劑 +4 | knight344 2026-03-16 | 4/200 |
|
|
|
[考研] 296求調(diào)劑 +4 | 大口吃飯 身體健 2026-03-13 | 4/200 |
|
|
|
[考研] 一志愿天津大學(xué)化學(xué)工藝專業(yè)（081702）315分求調(diào)劑 +5 | yangfz 2026-03-17 | 5/250 |
|
|
|
[考研]
 11408 一志愿西電，277分求調(diào)劑
+3
|
zhouzhen654 2026-03-16 | 3/150 |
|
|
|
[考研] 東南大學(xué)364求調(diào)劑 +5 | JasonYuiui 2026-03-15 | 5/250 |
|
|
|
[考研] 288求調(diào)劑 +4 | 奇點0314 2026-03-14 | 4/200 |
|
|
|
[考研] 材料工程327求調(diào)劑 +3 | xiaohe12w 2026-03-11 | 3/150 |
|
|
|
[考研] 一志愿哈工大材料324分求調(diào)劑 +5 | 閆旭東 2026-03-14 | 5/250 |
|
|
|
[考研] 學(xué)碩285求調(diào)劑 +13 | Wisjxn 2026-03-12 | 46/2300 |
|
|
|
[考研] 266求調(diào)劑 +4 | 學(xué)員97LZgn 2026-03-13 | 4/200 |
|
|
|
[考研] 求調(diào)劑（材料與化工327） +4 | 愛吃香菜啦 2026-03-11 | 4/200 |
|
|
|
[考研] 26調(diào)劑/材料/英一數(shù)二/總分289/已過A區(qū)線 +6 | 步川酷紫123 2026-03-13 | 6/300 |
|
|
|
[考研] 求調(diào)劑 +7 | 18880831720 2026-03-11 | 7/350 |
|
|
|
[考研] 土木第一志愿276求調(diào)劑，科研和技能十分豐富，求新興方向的導(dǎo)師收留 +3 | 土木小天才 2026-03-12 | 3/150 |
|
|
|
[考研] 085600材料與化工 309分請求調(diào)劑 +7 | dtdxzxx 2026-03-12 | 8/400 |
|
|
|
[考研] 0856化學(xué)工程280分求調(diào)劑 +4 | shenzxsn 2026-03-11 | 4/200 |
|
|
|
[考博] 26讀博 +4 | Rui135246 2026-03-12 | 10/500 |
|