姓名：任思遠(yuǎn)
學(xué)號(hào)：17021210990
轉(zhuǎn)載自：https://mp.weixin.qq.com/s?__biz=MzA5NTMwMjIwNA==&mid=2650836143&idx=3&sn=a253fe856a784e81c90956657cafd6d0&pass_ticket=R4LrHafy9l60FNSePlN9dZjKuceEvyhWMIBaRyhQG6wAkZzbXfL2DcpGgKGZnvtO
【嵌牛導(dǎo)讀】：計(jì)算機(jī)算法的不斷進(jìn)步推動(dòng)著計(jì)算技術(shù)的發(fā)展灿巧，在文章中將列舉出九個(gè)頗具代表性的算法纠屋，他們都為計(jì)算機(jī)科學(xué)的發(fā)展做出了巨大的貢獻(xiàn)。
【嵌牛鼻子】：計(jì)算技術(shù)各墨、算法
【嵌牛提問(wèn)】：作為計(jì)算基礎(chǔ)的算法都有什么？
【嵌牛正文】
? ? ? ?在過(guò)去，很多巧妙的計(jì)算機(jī)算法設(shè)計(jì)，改變了我們的計(jì)算技術(shù)难述。通過(guò)操作標(biāo)準(zhǔn)計(jì)算機(jī)中提供的中間運(yùn)算符，可以產(chǎn)生很多的高效函數(shù)吐句。這些函數(shù)導(dǎo)致了計(jì)算機(jī)程序的復(fù)雜性和多樣性胁后，這也是今天計(jì)算機(jī)時(shí)代快速發(fā)展的重要原因。如下所示嗦枢，我們列舉了一些算法攀芯，它們改變了我們的計(jì)算機(jī)使用。
一文虏、壓縮技術(shù)
哈弗曼編碼
哈弗曼編碼在無(wú)損數(shù)據(jù)壓縮中廣泛應(yīng)用侣诺。為了找到一種最高效的二進(jìn)制編碼，哈弗曼在1951年提出了根據(jù)字符頻率排序的二叉樹這樣的編碼方法氧秘。這種方法被證明年鸳，是最有效的編碼方法。由于這種方法簡(jiǎn)單丸相、高效搔确，這種方法被用在很多的壓縮方法中比如：DEFLATE（PKZIP壓縮軟件中的算法），以及很多的多媒體編碼包括JPEG和MP3中。
二膳算、密碼學(xué)
公共秘鑰加密
對(duì)于加密算法而言座硕，需要兩種不同的秘鑰，公共秘鑰是用來(lái)作為加密的明文或者驗(yàn)證數(shù)字簽名畦幢。私鑰則用來(lái)解密密文坎吻，或生成數(shù)字簽名缆蝉。公共秘鑰加密使得用戶可以在公共信道中安全傳送數(shù)據(jù)宇葱。雖然這種方法于1997年發(fā)表，但是由英國(guó)政府通訊總部（GCHQ）的James H. Ellis, Clifford Cocks, Malcolm Williamson在1973年設(shè)計(jì)完成刊头，并且投入使用黍瞧。
三、搜索算法
Dijkstra 最短路徑算法
這一算法由Dijkstra在1956年完成原杂，這是一個(gè)為圖設(shè)計(jì)的搜索算法印颤。它解決了單向圖中的最短路徑問(wèn)題，因此穿肄，也可以用來(lái)生成最短路徑樹年局。很多基于圖的算法中，都應(yīng)用了這樣的算法來(lái)進(jìn)行路徑規(guī)劃或是子路徑選擇咸产。上圖展示了在單向圖中矢否，利用這樣的算法求最短路徑的過(guò)程。
二分搜索算法
二分搜索算法用來(lái)在已經(jīng)有序的數(shù)組中找到關(guān)鍵字的位置脑溢。在說(shuō)明詞義的字典中僵朗，詞的排列基本是有序的。電話本上屑彻，記錄也都按照人名验庙、地址或是電話號(hào)碼排序。通過(guò)這樣的算法社牲，我們可以由人名粪薛，很快地在電話本中找到相應(yīng)的電話以及地址。
四搏恤、排序算法
快速排序
這種算法由Tony Hoare在1960年設(shè)計(jì)违寿。這個(gè)算法本來(lái)用于調(diào)整待翻譯單詞的順序，從而使它們與詞典順序更加一致挑社，方便翻譯陨界。這種算法由于在Unix系統(tǒng)中被用作默認(rèn)排序算法而聲名大噪。同時(shí)痛阻，這種算法由于它在C語(yǔ)言標(biāo)準(zhǔn)庫(kù)中的函數(shù)名“qsort”而得名菌瘪。
五、數(shù)學(xué)方法
Karatsuba快速相乘算法
這種算法用來(lái)更快完成相乘的數(shù)學(xué)操作。由Anatolii Alexeevitch Karatsuba在1962年提出俏扩。它減少了乘法中需要操作的數(shù)字糜工，并且提供了一個(gè)快速的相乘計(jì)算方法。這種算法的改進(jìn)算法是Toom–Cook算法录淡。然而捌木，對(duì)于大數(shù)相乘，Sch?nhage–Strassen 算法則是一種更快速的解決方案嫉戚。
歐幾里得算法（輾轉(zhuǎn)相除）
利用歐幾里得算法刨裆，可以計(jì)算最大公約數(shù)。即兩個(gè)正整數(shù)可以被整除的最大數(shù)彬檀。雖然這種算法只通過(guò)減法和比較來(lái)找到最大公約數(shù)帆啃，但是它被應(yīng)用在了許多高級(jí)算法中。歐幾里得被認(rèn)為是這個(gè)算法的發(fā)明者窍帝，歐幾里得的這個(gè)算法被認(rèn)為是歐幾里得時(shí)期（公元前300年左右）最古老的算法之一努潘。
七、圖形學(xué)的發(fā)展
Bresenham直線算法
這種算法由Jack Elton Bresenham在1962年坤学，他在IBM工作期間提出疯坤。這種算法本來(lái)用于在計(jì)算機(jī)屏幕上畫出直線。算法用到的操作非常簡(jiǎn)單深浮，整數(shù)的加法压怠，減法和移位操作。這在計(jì)算機(jī)圖形學(xué)中是非常先進(jìn)的方法略号⌒滔浚基于這樣的方法，后來(lái)算法又有了一系列的拓展玄柠，比如：畫圓算法等突梦。由于這種算法的高效、快捷羽利，至今在很多硬件中（比如繪圖儀和現(xiàn)代圖形卡等）這種算法仍然十分重要并且仍在使用宫患。
平方根倒數(shù)速算法
這種算法提供了一種快速計(jì)算平方根的倒數(shù)的方法。這種方法在3D圖像中廣泛應(yīng)用于確定光線和投影關(guān)系这弧，這可能需要每秒上千萬(wàn)次的計(jì)算速度娃闲。在《雷神之錘三：競(jìng)技場(chǎng)》的源代碼中就有這樣的算法，可是匾浪，直到2002年這種算法才被廣泛應(yīng)用皇帮。這個(gè)算法使用了一系列的簡(jiǎn)單操作來(lái)解決復(fù)雜問(wèn)題。雖然很多人認(rèn)為蛋辈，這種算法由John Carmack研發(fā)属拾，但是将谊，SGI和3dfx早就曾在產(chǎn)品中應(yīng)用此算法，當(dāng)時(shí)應(yīng)用的是Gary Tarolli實(shí)現(xiàn)的版本渐白。
