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