細數(shù)那些改變計算技術(shù)的偉大算法
在過去，很多巧妙的計算機算法設(shè)計，改變了我們的計算技術(shù)。通過操作標(biāo)準(zhǔn)計算機中提供的中間運算符，可以產(chǎn)生很多的高效函數(shù)。這些函數(shù)導(dǎo)致了計算機程序的復(fù)雜性和多樣性，這也是今天計算機時代快速發(fā)展的重要原因。如下所示，我們列舉了一些算法，它們改變了我們的計算機使用。
壓縮技術(shù)
哈弗曼編碼
哈弗曼編碼在無損數(shù)據(jù)壓縮中廣泛應(yīng)用。為了找到一種***效的二進制編碼，哈弗曼在1951年提出了根據(jù)字符頻率排序的二叉樹這樣的編碼方法。這種方法被證明，是最有效的編碼方法。由于這種方法簡單、高效，這種方法被用在很多的壓縮方法中比如：DEFLATE（PKZIP壓縮軟件中的算法），以及很多的多媒體編碼包括JPEG和MP3中。
密碼學(xué)
公共秘鑰加密
對于加密算法而言，需要兩種不同的秘鑰，公共秘鑰是用來作為加密的明文或者驗證數(shù)字簽名。私鑰則用來解密密文，或生成數(shù)字簽名。公共秘鑰加密使得用戶可以在公共信道中安全傳送數(shù)據(jù)。雖然這種方法于1997年發(fā)表，但是由英國政府通訊總部（GCHQ）的James H. Ellis, Clifford Cocks, Malcolm Williamson在1973年設(shè)計完成，并且投入使用。
搜索算法
Dijkstra 最短路徑算法
這一算法由Dijkstra在1956年完成，這是一個為圖設(shè)計的搜索算法。它解決了單向圖中的最短路徑問題，因此，也可以用來生成最短路徑樹。很多基于圖的算法中，都應(yīng)用了這樣的算法來進行路徑規(guī)劃或是子路徑選擇。上圖展示了在單向圖中，利用這樣的算法求最短路徑的過程。
二分搜索算法
二分搜索算法用來在已經(jīng)有序的數(shù)組中找到關(guān)鍵字的位置。在說明詞義的字典中，詞的排列基本是有序的。電話本上，記錄也都按照人名、地址或是電話號碼排序。通過這樣的算法，我們可以由人名，很快地在電話本中找到相應(yīng)的電話以及地址。
快速排序
這種算法由Tony Hoare在1960年設(shè)計。這個算法本來用于調(diào)整待翻譯單詞的順序，從而使它們與詞典順序更加一致，方便翻譯。這種算法由于在Unix系統(tǒng)中被用作默認(rèn)排序算法而聲名大噪。同時，這種算法由于它在C語言標(biāo)準(zhǔn)庫中的函數(shù)名“qsort”而得名。
#p#
數(shù)學(xué)方法
Karatsuba快速相乘算法
這種算法用來更快完成相乘的數(shù)學(xué)操作。由Anatolii Alexeevitch Karatsuba在1962年提出。它減少了乘法中需要操作的數(shù)字，并且提供了一個快速的相乘計算方法。這種算法的改進算法是Toom–Cook算法。然而，對于大數(shù)相乘，Schönhage–Strassen 算法則是一種更快速的解決方案。
歐幾里得算法（輾轉(zhuǎn)相除）
利用歐幾里得算法，可以計算***公約數(shù)。即兩個正整數(shù)可以被整除的***數(shù)。雖然這種算法只通過減法和比較來找到***公約數(shù)，但是它被應(yīng)用在了許多高級算法中。歐幾里得被認(rèn)為是這個算法的***，歐幾里得的這個算法被認(rèn)為是歐幾里得時期（公元前300年左右）最古老的算法之一。
圖形學(xué)的發(fā)展
Bresenham直線算法
這種算法由Jack Elton Bresenham在1962年，他在IBM工作期間提出。這種算法本來用于在計算機屏幕上畫出直線。算法用到的操作非常簡單，整數(shù)的加法，減法和移位操作。這在計算機圖形學(xué)中是非常先進的方法?；谶@樣的方法，后來算法又有了一系列的拓展，比如：畫圓算法等。由于這種算法的高效、快捷，至今在很多硬件中（比如繪圖儀和現(xiàn)代圖形卡等）這種算法仍然十分重要并且仍在使用。.
平方根倒數(shù)速算法
這種算法提供了一種快速計算平方根的倒數(shù)的方法。這種方法在3D圖像中廣泛應(yīng)用于確定光線和投影關(guān)系，這可能需要每秒上千萬次的計算速度。在《雷神之錘三：競技場》的源代碼中就有這樣的算法，可是，直到2002年這種算法才被廣泛應(yīng)用。這個算法使用了一系列的簡單操作來解決復(fù)雜問題。雖然很多人認(rèn)為，這種算法由John Carmack研發(fā)，但是，SGI和3dfx早就曾在產(chǎn)品中應(yīng)用此算法，當(dāng)時應(yīng)用的是Gary Tarolli實現(xiàn)的版本。
原文鏈接： docsity 翻譯： 伯樂在線 - programmer_lin
