算法從入門(mén)到入土(一)

《我的第一本算法書(shū)》學(xué)習(xí)記錄

數(shù)據(jù)結(jié)構(gòu)

什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)用于描述數(shù)據(jù)的順序和位置關(guān)系句葵，數(shù)據(jù)存儲(chǔ)于計(jì)算機(jī)的內(nèi)存中厕鹃。內(nèi)存如圖所示兢仰，形似排成1列的箱子，1個(gè)箱子里存儲(chǔ)1個(gè)數(shù)據(jù)剂碴。數(shù)據(jù)存儲(chǔ)于內(nèi)存時(shí)把将，決定了數(shù)據(jù)順序和位置關(guān)系的便是“數(shù)據(jù)結(jié)構(gòu)”。

數(shù)據(jù)結(jié)構(gòu)

三種比較常見(jiàn)的存儲(chǔ)格式：

• 全局無(wú)序隨機(jī)排列（適合需要不斷添加數(shù)據(jù)）
• 全局有序排列（不需要修改數(shù)據(jù)）
• 部分有序排列（兩者合一）

鏈表

鏈表是數(shù)據(jù)結(jié)構(gòu)之一忆矛，其中的數(shù)據(jù)呈線性排列察蹲。在鏈表中，數(shù)據(jù)的添加和刪除都較為方便洪碳，就是訪問(wèn)比較耗費(fèi)時(shí)間递览。

鏈表

這就是鏈表的概念圖。Blue瞳腌、Yellow、Red這3個(gè)字符串作為數(shù)據(jù)被存儲(chǔ)于鏈表中镜雨。每個(gè)數(shù)據(jù)都有1個(gè)“指針”嫂侍，它指向下一個(gè)數(shù)據(jù)的內(nèi)存地址。

在鏈表中荚坞，數(shù)據(jù)一般都是分散存儲(chǔ)于內(nèi)存中的挑宠，無(wú)須存儲(chǔ)在連續(xù)空間內(nèi)。但是讀取時(shí)需要按順序讀取颓影，比如需要讀取“red”就需要先從“Blue”讀起各淀。

在鏈表中添加數(shù)據(jù)只需要改變對(duì)應(yīng)的指針指向的位置，將需要添加數(shù)據(jù)的位置前后的指針指向改變即可诡挂。

image

同時(shí)刪除只需要將對(duì)應(yīng)數(shù)據(jù)存儲(chǔ)的指針取消即可碎浇，不需要?jiǎng)h除實(shí)際數(shù)據(jù)，在正常運(yùn)行過(guò)程中璃俗，數(shù)據(jù)會(huì)被后續(xù)結(jié)果覆蓋奴璃。

image

復(fù)雜度：把鏈表中的數(shù)據(jù)量記成。訪問(wèn)數(shù)據(jù)時(shí)城豁，我們需要從鏈表頭部開(kāi)始查找（線性查找）苟穆，如果目標(biāo)數(shù)據(jù)在鏈表最后的話，需要的時(shí)間就是唱星，添加數(shù)據(jù)或刪除數(shù)據(jù)只需要該表指針位置雳旅，復(fù)雜度為

如果在數(shù)據(jù)的結(jié)尾添加一個(gè)指針指向開(kāi)始數(shù)據(jù)，就會(huì)構(gòu)成循環(huán)列表间聊，適用于固定數(shù)量的數(shù)據(jù)更新攒盈。

數(shù)組

數(shù)組也是數(shù)據(jù)呈線性排列的一種數(shù)據(jù)結(jié)構(gòu)。與鏈表不同甸饱，在數(shù)組中沦童，訪問(wèn)數(shù)據(jù)十分簡(jiǎn)單仑濒，而添加和刪除數(shù)據(jù)比較耗工夫。

image

由于數(shù)據(jù)是存儲(chǔ)在連續(xù)空間內(nèi)的偷遗，所以每個(gè)數(shù)據(jù)的內(nèi)存地址（在內(nèi)存上的位置）都可以通過(guò)數(shù)組下標(biāo)算出墩瞳，我們也就可以借此直接訪問(wèn)目標(biāo)數(shù)據(jù)（這叫作“隨機(jī)訪問(wèn)”）。

復(fù)雜度： 假設(shè)數(shù)組中有n個(gè)數(shù)據(jù)氏豌，由于訪問(wèn)數(shù)據(jù)時(shí)使用的是隨機(jī)訪問(wèn)（通過(guò)下標(biāo)可計(jì)算出內(nèi)存地址）喉酌，所以需要的運(yùn)行時(shí)間僅為恒定的。向數(shù)組中添加新數(shù)據(jù)時(shí)泵喘，必須把目標(biāo)位置后面的數(shù)據(jù)一個(gè)個(gè)移開(kāi)泪电。所以，如果在數(shù)組頭部添加數(shù)據(jù)纪铺，就需要的時(shí)間相速。

數(shù)組與列表的比較

棧

棧也是一種數(shù)據(jù)呈線性排列的數(shù)據(jù)結(jié)構(gòu)，不過(guò)在這種結(jié)構(gòu)中鲜锚，我們只能訪問(wèn)最新添加的數(shù)據(jù)突诬。棧就像是一摞書(shū)，拿到新書(shū)時(shí)我們會(huì)把它放在書(shū)堆的最上面芜繁，取書(shū)時(shí)也只能從最上面的新書(shū)開(kāi)始取旺隙。

入棧：往棧中添加數(shù)據(jù)的操作叫“入棧”（Push）

出棧：從棧中取出數(shù)據(jù)的操作叫“出椏チ睿”（POP）

image	image

從棧中取出數(shù)據(jù)時(shí)蔬捷，是從最上面，也就是最新的數(shù)據(jù)開(kāi)始取出的榔袋。

像棧這種最后添加的數(shù)據(jù)最先被取出周拐，即“后進(jìn)先出”的結(jié)構(gòu)，我們稱為L(zhǎng)ast In First Out摘昌，簡(jiǎn)稱LIFO速妖。與鏈表和數(shù)組一樣，棧的數(shù)據(jù)也是線性排列聪黎，但在棧中罕容，添加和刪除數(shù)據(jù)的操作只能在一端進(jìn)行，訪問(wèn)數(shù)據(jù)也只能訪問(wèn)到頂端的數(shù)據(jù)稿饰。想要訪問(wèn)中間的數(shù)據(jù)時(shí)锦秒，就必須通過(guò)出棧操作將目標(biāo)數(shù)據(jù)移到棧頂才行。

隊(duì)列

與前面提到的數(shù)據(jù)結(jié)構(gòu)相同喉镰，隊(duì)列中的數(shù)據(jù)也呈線性排列旅择。雖然與棧有些相似，但隊(duì)列中添加和刪除數(shù)據(jù)的操作分別是在兩端進(jìn)行的侣姆。就和“隊(duì)列”這個(gè)名字一樣生真，把它想象成排成一隊(duì)的人更容易理解沉噩。在隊(duì)列中，處理總是從第一名開(kāi)始往后進(jìn)行柱蟀，而新來(lái)的人只能排在隊(duì)尾川蒙。

入隊(duì)：往隊(duì)列中添加數(shù)據(jù)的操作叫“入隊(duì)”

出隊(duì)：從隊(duì)列中刪除數(shù)據(jù)的操作叫“出隊(duì)”

image	image

像隊(duì)列這種最先進(jìn)去的數(shù)據(jù)最先被取來(lái)，即“先進(jìn)先出”的結(jié)構(gòu)长已，我們稱為First In FirstOut畜眨，簡(jiǎn)稱FIFO。與棧類似术瓮，隊(duì)列中可以操作數(shù)據(jù)的位置也有一定的限制康聂。在棧中，數(shù)據(jù)的添加和刪除都在同一端進(jìn)行胞四，而在隊(duì)列中則分別是在兩端進(jìn)行的恬汁。隊(duì)列也不能直接訪問(wèn)位于中間的數(shù)據(jù)，必須通過(guò)出隊(duì)操作將目標(biāo)數(shù)據(jù)變成首位后才能訪問(wèn)撬讽。

哈希表

哈希表存儲(chǔ)的是由鍵（key）和值（value）組成的數(shù)據(jù)蕊连。例如，我們將每個(gè)人的性別作為數(shù)據(jù)進(jìn)行存儲(chǔ)游昼，鍵為人名，值為對(duì)應(yīng)的性別尝蠕。

image

一般來(lái)說(shuō)烘豌，我們可以把鍵當(dāng)成數(shù)據(jù)的標(biāo)識(shí)符，把值當(dāng)成數(shù)據(jù)的內(nèi)容看彼。

操作：

1. 計(jì)算key的哈希值
2. 將得到的哈希值除以數(shù)組的長(zhǎng)度廊佩，求得其余數(shù)
3. 將key的數(shù)據(jù)存進(jìn)對(duì)應(yīng)余數(shù)號(hào)的箱子中
4. 如果出現(xiàn)同樣余數(shù)的情況，則稱之為“沖突”靖榕，遇到這種情況标锄，可使用鏈表在已有數(shù)據(jù)的后面繼續(xù)存儲(chǔ)新的數(shù)據(jù)。
5. 存儲(chǔ)完所有數(shù)據(jù)茁计，哈希表也就制作完成

在存儲(chǔ)數(shù)據(jù)的過(guò)程中料皇，如果發(fā)生沖突，可以利用鏈表在已有數(shù)據(jù)的后面插入新數(shù)據(jù)來(lái)解決沖突星压。這種方法被稱為“鏈地址法”践剂。

除了鏈地址法以外，還有幾種解決沖突的方法娜膘。其中逊脯，應(yīng)用較為廣泛的是“開(kāi)放地址法”。這種方法是指當(dāng)沖突發(fā)生時(shí)竣贪，立刻計(jì)算出一個(gè)候補(bǔ)地址（數(shù)組上的位置）并將數(shù)據(jù)存進(jìn)去军洼。如果仍然有沖突巩螃，便繼續(xù)計(jì)算下一個(gè)候補(bǔ)地址，直到有空地址為止匕争”芊Γ可以通過(guò)多次使用哈希函數(shù)或“線性探測(cè)法”等方法計(jì)算候補(bǔ)地址。

在哈希表中汗捡，我們可以利用哈希函數(shù)快速訪問(wèn)到數(shù)組中的目標(biāo)數(shù)據(jù)淑际。如果發(fā)生哈希沖突，就使用鏈表進(jìn)行存儲(chǔ)扇住。這樣一來(lái)春缕，不管數(shù)據(jù)量為多少，我們都能夠靈活應(yīng)對(duì)艘蹋。如果數(shù)組的空間太小锄贼，使用哈希表的時(shí)候就容易發(fā)生沖突，線性查找的使用頻率也會(huì)更高女阀；反過(guò)來(lái)宅荤，如果數(shù)組的空間太大，就會(huì)出現(xiàn)很多空內(nèi)容浸策，造成內(nèi)存的浪費(fèi)冯键。因此，給數(shù)組設(shè)定合適的空間非常重要庸汗。

堆

堆是一種圖的樹(shù)形結(jié)構(gòu)惫确，被用于實(shí)現(xiàn)“優(yōu)先隊(duì)列”（priority queues）。優(yōu)先隊(duì)列是一種數(shù)據(jù)結(jié)構(gòu)蚯舱，可以自由添加數(shù)據(jù)改化，但取出數(shù)據(jù)時(shí)要從最小值開(kāi)始按順序取出。在堆的樹(shù)形結(jié)構(gòu)中枉昏，各個(gè)頂點(diǎn)被稱為“結(jié)點(diǎn)”（node）陈肛，數(shù)據(jù)就存儲(chǔ)在這些結(jié)點(diǎn)中。

image

• 結(jié)點(diǎn)內(nèi)的數(shù)字就是存儲(chǔ)的數(shù)據(jù)兄裂。堆中的每個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)句旱。樹(shù)的形狀取決于數(shù)據(jù)的個(gè)數(shù)。另外懦窘，結(jié)點(diǎn)的排列順序?yàn)閺纳系较虑棒幔恍欣飫t為從左到右。
• 子結(jié)點(diǎn)必定大于父結(jié)點(diǎn)畅涂。因此港华，最小值被存儲(chǔ)在頂端的根結(jié)點(diǎn)中。往堆中添加數(shù)據(jù)時(shí)午衰，為了遵守這條規(guī)則立宜，一般會(huì)把新數(shù)據(jù)放在最下面一行靠左的位置冒萄。當(dāng)最下面一行里沒(méi)有多余空間時(shí)，就再往下另起一行橙数，把數(shù)據(jù)加在這一行的最左端尊流。

當(dāng)父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最大堆。當(dāng)父結(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最小堆灯帮。

堆中最頂端的數(shù)據(jù)始終最小崖技，所以無(wú)論數(shù)據(jù)量有多少，取出最小值的時(shí)間復(fù)雜度都為O（1）钟哥。

另外迎献，因?yàn)槿〕鰯?shù)據(jù)后需要將最后的數(shù)據(jù)移到最頂端，然后一邊比較它與子結(jié)點(diǎn)數(shù)據(jù)的大小腻贰，一邊往下移動(dòng)吁恍，所以取出數(shù)據(jù)需要的運(yùn)行時(shí)間和樹(shù)的高度成正比。假設(shè)數(shù)據(jù)量為n播演，根據(jù)堆的形狀特點(diǎn)可知樹(shù)的高度為log2n冀瓦，那么重構(gòu)樹(shù)的時(shí)間復(fù)雜度便為O（logn）。

添加數(shù)據(jù)也一樣写烤。在堆的最后添加數(shù)據(jù)后翼闽，數(shù)據(jù)會(huì)一邊比較它與父結(jié)點(diǎn)數(shù)據(jù)的大小，一邊往上移動(dòng)洲炊，直到滿足堆的條件為止肄程，所以添加數(shù)據(jù)需要的運(yùn)行時(shí)間與樹(shù)的高度成正比，也是O（logn）选浑。

二叉查找樹(shù)

二叉查找樹(shù)（又叫作二叉搜索樹(shù)或二叉排序樹(shù)）是一種數(shù)據(jù)結(jié)構(gòu)，采用了圖的樹(shù)形結(jié)構(gòu)玄叠，數(shù)據(jù)存儲(chǔ)于二叉查找樹(shù)的各個(gè)結(jié)點(diǎn)中古徒。

image

二叉查找樹(shù)有兩個(gè)性質(zhì)：

• 第一個(gè)是每個(gè)結(jié)點(diǎn)的值均大于其左子樹(shù)上任意一個(gè)結(jié)點(diǎn)的值。
• 第二個(gè)是每個(gè)結(jié)點(diǎn)的值均小于其右子樹(shù)上任意一個(gè)結(jié)點(diǎn)的值读恃。

往二叉查找樹(shù)中添加數(shù)據(jù)：

• 從二叉查找樹(shù)的頂端結(jié)點(diǎn)開(kāi)始尋找添加數(shù)字的位置隧膘，小于它則往左移，大于它則往右移寺惫。

刪除數(shù)據(jù)：

• 如果需要?jiǎng)h除的結(jié)點(diǎn)沒(méi)有子結(jié)點(diǎn)疹吃，直接刪掉該結(jié)點(diǎn)即可。
• 如果需要?jiǎng)h除的結(jié)點(diǎn)只有一個(gè)子結(jié)點(diǎn)西雀，那么先刪掉目標(biāo)結(jié)點(diǎn),然后把子結(jié)點(diǎn)移到被刪除結(jié)點(diǎn)的位置上即可
• 如果需要?jiǎng)h除的結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)萨驶，那么先刪掉目標(biāo)結(jié)點(diǎn),然后在被刪除結(jié)點(diǎn)的左子樹(shù)中尋找最大結(jié)點(diǎn),最后將最大結(jié)點(diǎn)移到被刪除結(jié)點(diǎn)的位置上。

比較的次數(shù)取決于樹(shù)的高度艇肴。所以如果結(jié)點(diǎn)數(shù)為n腔呜，而且樹(shù)的形狀又較為均衡的話叁温，比較大小和移動(dòng)的次數(shù)最多就是log2n。因此核畴，時(shí)間復(fù)雜度為O（logn）膝但。但是，如果樹(shù)的形狀朝單側(cè)縱向延伸谤草，樹(shù)就會(huì)變得很高跟束，此時(shí)時(shí)間復(fù)雜度也就變成了O（n）。

排序

所謂排序

排序就是將輸入的數(shù)字按照從小到大的順序進(jìn)行排列丑孩。

image	image

冒泡算法

冒泡排序就是重復(fù)“從序列右邊開(kāi)始比較相鄰兩個(gè)數(shù)字的大小冀宴，再根據(jù)結(jié)果交換兩個(gè)數(shù)字的位置”這一操作的算法。在這個(gè)過(guò)程中嚎杨，數(shù)字會(huì)像泡泡一樣花鹅，慢慢從右往左“浮”到序列的頂端，所以這個(gè)算法才被稱為“冒泡排序”枫浙。

image

在冒泡排序中刨肃，第1輪需要比較n-1次，第2輪需要比較n-2次……第n-1輪需要比較1次箩帚。因此真友，總的比較次數(shù)為（n-1）+（n-2）+…+1≈n2/2。這個(gè)比較次數(shù)恒定為該數(shù)值紧帕，和輸入數(shù)據(jù)的排列順序無(wú)關(guān)盔然。不過(guò)，交換數(shù)字的次數(shù)和輸入數(shù)據(jù)的排列順序有關(guān)是嗜。假設(shè)出現(xiàn)某種極端情況愈案，如輸入數(shù)據(jù)正好以從小到大的順序排列，那么便不需要任何交換操作鹅搪；反過(guò)來(lái)站绪，輸入數(shù)據(jù)要是以從大到小的順序排列，那么每次比較數(shù)字后便都要進(jìn)行交換丽柿。因此恢准，冒泡排序的時(shí)間復(fù)雜度為O（n2）。

選擇算法

選擇排序就是重復(fù)“從待排序的數(shù)據(jù)中尋找最小值甫题，將其與序列最左邊的數(shù)字進(jìn)行交換”這一操作的算法馁筐。在序列中尋找最小值時(shí)使用的是線性查找。

image

選擇排序使用了線性查找來(lái)尋找最小值坠非，因此在第1輪中需要比較n-1個(gè)數(shù)字敏沉，第2輪需要比較n-2個(gè)數(shù)字……到第n-1輪的時(shí)候就只需比較1個(gè)數(shù)字了。因此，總的比較次數(shù)與冒泡排序的相同赦抖，都是（n-1）+（n-2）+…+1≈n2/2次舱卡。每輪中交換數(shù)字的次數(shù)最多為1次。如果輸入數(shù)據(jù)就是按從小到大的順序排列的队萤，便不需要進(jìn)行任何交換轮锥。選擇排序的時(shí)間復(fù)雜度也和冒泡排序的一樣，都為O（n2）要尔。

插入排序

插入排序是一種從序列左端開(kāi)始依次對(duì)數(shù)據(jù)進(jìn)行排序的算法舍杜。在排序過(guò)程中，左側(cè)的數(shù)據(jù)陸續(xù)歸位赵辕，而右側(cè)留下的就是還未被排序的數(shù)據(jù)既绩。插入排序的思路就是從右側(cè)的未排序區(qū)域內(nèi)取出一個(gè)數(shù)據(jù)，然后將它插入到已排序區(qū)域內(nèi)合適的位置上还惠。

image

在插入排序中饲握，需要將取出的數(shù)據(jù)與其左邊的數(shù)字進(jìn)行比較。就跟前面講的步驟一樣蚕键，如果左邊的數(shù)字更小救欧，就不需要繼續(xù)比較，本輪操作到此結(jié)束锣光，自然也不需要交換數(shù)字的位置笆怠。然而，如果取出的數(shù)字比左邊已歸位的數(shù)字都要小誊爹，就必須不停地比較大小蹬刷，交換數(shù)字，直到它到達(dá)整個(gè)序列的最左邊為止频丘。具體來(lái)說(shuō)办成，就是第k輪需要比較k-1次。因此搂漠，在最糟糕的情況下诈火，第2輪需要操作1次，第3輪操作2次……第n輪操作n-1次状答，所以時(shí)間復(fù)雜度和冒泡排序的一樣，都為O（n2）刀崖。和前面講的排序算法一樣惊科，輸入數(shù)據(jù)按從大到小的順序排列時(shí)就是最糟糕的情況。

堆排列

堆排序的特點(diǎn)是利用了數(shù)據(jù)結(jié)構(gòu)中的堆亮钦。

首先馆截，在堆中存儲(chǔ)所有的數(shù)據(jù)，并按降序來(lái)構(gòu)建堆。 從降序排列的堆中取出數(shù)據(jù)時(shí)會(huì)從最大的數(shù)據(jù)開(kāi)始取蜡娶，所以將取出的數(shù)據(jù)反序輸出混卵，排序就完成了。

堆排序一開(kāi)始需要將n個(gè)數(shù)據(jù)存進(jìn)堆里窖张，所需時(shí)間為O（nlogn）幕随。排序過(guò)程中，堆從空堆的狀態(tài)開(kāi)始宿接，逐漸被數(shù)據(jù)填滿赘淮。由于堆的高度小于log2n，所以插入1個(gè)數(shù)據(jù)所需要的時(shí)間為O（logn）睦霎。每輪取出最大的數(shù)據(jù)并重構(gòu)堆所需要的時(shí)間為O（logn）梢卸。由于總共有n輪，所以重構(gòu)后排序的時(shí)間也是O（nlogn）副女。因此蛤高，整體來(lái)看堆排序的時(shí)間復(fù)雜度為O（nlogn）。這樣來(lái)看碑幅，堆排序的運(yùn)行時(shí)間比之前講到的冒泡排序戴陡、選擇排序、插入排序的時(shí)間O（n2）都要短枕赵，但由于要使用堆這個(gè)相對(duì)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)猜欺，所以實(shí)現(xiàn)起來(lái)也較為困難。

歸并排序

歸并排序算法會(huì)把序列分成長(zhǎng)度相同的兩個(gè)子序列拷窜，當(dāng)無(wú)法繼續(xù)往下分時(shí)（也就是每個(gè)子序列中只有一個(gè)數(shù)據(jù)時(shí)）开皿，就對(duì)子序列進(jìn)行歸并。歸并指的是把兩個(gè)排好序的子序列合并成一個(gè)有序序列篮昧。該操作會(huì)一直重復(fù)執(zhí)行赋荆，直到所有子序列都?xì)w并為一個(gè)整體為止。

image

歸并排序中懊昨，分割序列所花費(fèi)的時(shí)間不算在運(yùn)行時(shí)間內(nèi)（可以當(dāng)作序列本來(lái)就是分割好的）窄潭。在合并兩個(gè)已排好序的子序列時(shí)，只需重復(fù)比較首位數(shù)據(jù)的大小酵颁，然后移動(dòng)較小的數(shù)據(jù)嫉你，因此只需花費(fèi)和兩個(gè)子序列的長(zhǎng)度相應(yīng)的運(yùn)行時(shí)間。也就是說(shuō)躏惋，完成一行歸并所需的運(yùn)行時(shí)間取決于這一行的數(shù)據(jù)量幽污。看一下上面的圖便能得知簿姨，無(wú)論哪一行都是n個(gè)數(shù)據(jù)距误，所以每行的運(yùn)行時(shí)間都為O（n）簸搞。而將長(zhǎng)度為n的序列對(duì)半分割直到只有一個(gè)數(shù)據(jù)為止時(shí)，可以分成log2n行准潭，因此趁俊，總共有l(wèi)og2n行。也就是說(shuō)刑然，總的運(yùn)行時(shí)間為O（nlogn）寺擂，這與前面講到的堆排序相同。

快速排序

快速排序算法首先會(huì)在序列中隨機(jī)選擇一個(gè)基準(zhǔn)值（pivot）闰集，然后將除了基準(zhǔn)值以外的數(shù)分為“比基準(zhǔn)值小的數(shù)”和“比基準(zhǔn)值大的數(shù)”這兩個(gè)類別沽讹，再將其排列成以下形式。

[比基準(zhǔn)值小的數(shù)] 基準(zhǔn)值 [比基準(zhǔn)值大的數(shù)]

接著武鲁，對(duì)兩個(gè)“[ ]”中的數(shù)據(jù)進(jìn)行排序之后爽雄，整體的排序便完成了。對(duì)“[ ]”里面的數(shù)據(jù)進(jìn)行排序時(shí)同樣也會(huì)使用快速排序沐鼠。

image

快速排序是一種“分治法”挚瘟。它將原本的問(wèn)題分成兩個(gè)子問(wèn)題（比基準(zhǔn)值小的數(shù)和比基準(zhǔn)值大的數(shù)），然后再分別解決這兩個(gè)問(wèn)題饲梭。

子問(wèn)題乘盖，也就是子序列完成排序后，再像一開(kāi)始說(shuō)明的那樣憔涉，把他們合并成一個(gè)序列订框，那么對(duì)原始序列的排序也就完成了。不過(guò)兜叨，解決子問(wèn)題的時(shí)候會(huì)再次使用快速排序穿扳，甚至在這個(gè)快速排序里仍然要使用快速排序。只有在子問(wèn)題里只剩一個(gè)數(shù)字的時(shí)候国旷，排序才算完成矛物。像這樣，在算法內(nèi)部繼續(xù)使用該算法的現(xiàn)象被稱為“遞歸”跪但。

如果數(shù)據(jù)中的每個(gè)數(shù)字被選為基準(zhǔn)值的概率都相等履羞，那么需要的平均運(yùn)行時(shí)間為O（nlogn）

數(shù)組的查找

線性查找

線性查找是一種在數(shù)組中查找數(shù)據(jù)的算法。

image

檢查數(shù)組中最左邊的數(shù)字屡久，將其與6進(jìn)行比較忆首。如果結(jié)果一致，查找便結(jié)束被环，不一致則向右檢查下一個(gè)數(shù)字雄卷。

線性查找需要從頭開(kāi)始不斷地按順序檢查數(shù)據(jù)，因此在數(shù)據(jù)量大且目標(biāo)數(shù)據(jù)靠后蛤售，或者目標(biāo)數(shù)據(jù)不存在時(shí)，比較的次數(shù)就會(huì)更多，也更為耗時(shí)悴能。若數(shù)據(jù)量為n揣钦，線性查找的時(shí)間復(fù)雜度便為O（n）。

二分查找

二分查找也是一種在數(shù)組中查找數(shù)據(jù)的算法,它只能查找已經(jīng)排好序的數(shù)據(jù)漠酿。

image

二分查找利用已排好序的數(shù)組冯凹，每一次查找都可以將查找范圍減半。查找范圍內(nèi)只剩一個(gè)數(shù)據(jù)時(shí)查找結(jié)束炒嘲。數(shù)據(jù)量為n的數(shù)組宇姚，將其長(zhǎng)度減半log2n次后，其中便只剩一個(gè)數(shù)據(jù)了夫凸。也就是說(shuō)浑劳，在二分查找中重復(fù)執(zhí)行“將目標(biāo)數(shù)據(jù)和數(shù)組中間的數(shù)據(jù)進(jìn)行比較后將查找范圍減半”的操作log2n次后，就能找到目標(biāo)數(shù)據(jù)（若沒(méi)找到則可以得出數(shù)據(jù)不存在的結(jié)論）夭拌，因此它的時(shí)間復(fù)雜度為O（logn）魔熏。

圖的搜索

什么是圖

計(jì)算機(jī)科學(xué)或離散數(shù)學(xué)中說(shuō)的“圖”

image

上圖中的圓圈叫作“頂點(diǎn)”（也叫“結(jié)點(diǎn)”），連接頂點(diǎn)的線叫作“邊”鸽扁。也就是說(shuō)蒜绽，由頂點(diǎn)和連接每對(duì)頂點(diǎn)的邊所構(gòu)成的圖形就是圖。

加權(quán)圖	有向圖
加權(quán)圖	有向圖

圖的搜索指的就是從圖的某一頂點(diǎn)開(kāi)始桶现，通過(guò)邊到達(dá)不同的頂點(diǎn)躲雅，最終找到目標(biāo)頂點(diǎn)的過(guò)程。根據(jù)搜索的順序不同骡和，圖的搜索算法可分為“廣度優(yōu)先搜索”和“深度優(yōu)先搜索”這兩種相赁。

廣度優(yōu)先搜索

廣度優(yōu)先搜索是一種對(duì)圖進(jìn)行搜索的算法。假設(shè)我們一開(kāi)始位于某個(gè)頂點(diǎn)（即起點(diǎn)）即横，此時(shí)并不知道圖的整體結(jié)構(gòu)噪生，而我們的目的是從起點(diǎn)開(kāi)始順著邊搜索，直到到達(dá)指定頂點(diǎn)（即終點(diǎn)）东囚。在此過(guò)程中每走到一個(gè)頂點(diǎn)跺嗽，就會(huì)判斷一次它是否為終點(diǎn)。廣度優(yōu)先搜索會(huì)優(yōu)先從離起點(diǎn)近的頂點(diǎn)開(kāi)始搜索页藻。

image

此處桨嫁，候補(bǔ)頂點(diǎn)是用“先入先出”（FIFO）的方式來(lái)管理的，因此可以使用“隊(duì)列”這個(gè)數(shù)據(jù)結(jié)構(gòu)份帐。

廣度優(yōu)先搜索的特征為從起點(diǎn)開(kāi)始璃吧，由近及遠(yuǎn)進(jìn)行廣泛的搜索。因此废境，目標(biāo)頂點(diǎn)離起點(diǎn)越近畜挨，搜索結(jié)束得就越快筒繁。

深度優(yōu)先搜索

深度優(yōu)先搜索和廣度優(yōu)先搜索一樣，都是對(duì)圖進(jìn)行搜索的算法巴元，目的也都是從起點(diǎn)開(kāi)始搜索直到到達(dá)指定頂點(diǎn)（終點(diǎn)）毡咏。深度優(yōu)先搜索會(huì)沿著一條路徑不斷往下搜索直到不能再繼續(xù)為止，然后再折返逮刨，開(kāi)始搜索下一條候補(bǔ)路徑呕缭。

image

候補(bǔ)頂點(diǎn)是用“后入先出”（LIFO）的方式來(lái)管理的，因此可以使用“椥藜海”這個(gè)數(shù)據(jù)結(jié)構(gòu)恢总。

深度優(yōu)先搜索的特征為沿著一條路徑不斷往下，進(jìn)行深度搜索。雖然廣度優(yōu)先搜索和深度優(yōu)先搜索在搜索順序上有很大的差異，但是在操作步驟上卻只有一點(diǎn)不同肖卧，那就是選擇哪一個(gè)候補(bǔ)頂點(diǎn)作為下一個(gè)頂點(diǎn)的基準(zhǔn)不同拼苍。廣度優(yōu)先搜索選擇的是最早成為候補(bǔ)的頂點(diǎn)，因?yàn)轫旤c(diǎn)離起點(diǎn)越近就越早成為候補(bǔ)，所以會(huì)從離起點(diǎn)近的地方開(kāi)始按順序搜索；而深度優(yōu)先搜索選擇的則是最新成為候補(bǔ)的頂點(diǎn)，所以會(huì)一路往下奸鸯，沿著新發(fā)現(xiàn)的路徑不斷深入搜索。

貝爾曼-福特算法

貝爾曼-福特（Bellman-Ford）算法是一種在圖中求解最短路徑問(wèn)題的算法可帽。最短路徑問(wèn)題就是在加權(quán)圖指定了起點(diǎn)和終點(diǎn)的前提下娄涩，尋找從起點(diǎn)到終點(diǎn)的路徑中權(quán)重總和最小的那條路徑。

image

將圖的頂點(diǎn)數(shù)設(shè)為n映跟、邊數(shù)設(shè)為m蓄拣，我們來(lái)思考一下貝爾曼-福特算法的時(shí)間復(fù)雜度是多少。該算法經(jīng)過(guò)n輪更新操作后就會(huì)停止努隙，而在每輪更新操作中都需要對(duì)各個(gè)邊進(jìn)行1次確認(rèn)球恤，因此1輪更新所花費(fèi)的時(shí)間就是O（m），整體的時(shí)間復(fù)雜度就是

狄克斯特拉算法

與前面提到的貝爾曼-福特算法類似荸镊，狄克斯特拉（Dijkstra）算法也是求解最短路徑問(wèn)題的算法咽斧，使用它可以求得從起點(diǎn)到終點(diǎn)的路徑中權(quán)重總和最小的那條路徑路徑。

image

將圖的頂點(diǎn)數(shù)設(shè)為n躬存、邊數(shù)設(shè)為m张惹，那么如果事先不進(jìn)行任何處理，該算法的時(shí)間復(fù)雜度就是O（n2）岭洲。不過(guò)宛逗，如果對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化，那么時(shí)間復(fù)雜度就會(huì)變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=O%EF%BC%88m%2Bnlogn%EF%BC%89" alt="O（m+nlogn）" mathimg="1">盾剩。

總的來(lái)說(shuō)雷激，就是不存在負(fù)數(shù)權(quán)重時(shí)替蔬，更適合使用效率較高的狄克斯特拉算法，而存在負(fù)數(shù)權(quán)重時(shí)屎暇，即便較為耗時(shí)进栽，也應(yīng)該使用可以得到正確答案的貝爾曼-福特算法。

A*算法

A（A-Star）算法也是一種在圖中求解最短路徑問(wèn)題的算法恭垦，由狄克斯特拉算法發(fā)展而來(lái)。狄克斯特拉算法會(huì)從離起點(diǎn)近的頂點(diǎn)開(kāi)始格嗅，按順序求出起點(diǎn)到各個(gè)頂點(diǎn)的最短路徑番挺。也就是說(shuō)，一些離終點(diǎn)較遠(yuǎn)的頂點(diǎn)的最短路徑也會(huì)被計(jì)算出來(lái)屯掖，但這部分其實(shí)是無(wú)用的玄柏。與之不同，A就會(huì)預(yù)先估算一個(gè)值贴铜，并利用這個(gè)值來(lái)省去一些無(wú)用的計(jì)算粪摘。

image

A*算法就是在Dijkstra算法的基礎(chǔ)上添加一個(gè)人工預(yù)估距離

由人工預(yù)先設(shè)定的估算距離被稱為“距離估算值”。如果事先根據(jù)已知信息設(shè)定合適的距離估算值绍坝，再將它作為啟發(fā)信息輔助計(jì)算徘意，搜索就會(huì)變得更加高效

如果我們能得到一些啟發(fā)信息，即各個(gè)頂點(diǎn)到終點(diǎn)的大致距離（這個(gè)距離不需是準(zhǔn)確的值）我們就能使用A*算法轩褐。

當(dāng)然椎咧，有時(shí)這類信息是完全無(wú)法估算的，這時(shí)就不能使用A算法把介。距離估算值越接近當(dāng)前頂點(diǎn)到終點(diǎn)的實(shí)際值勤讽，A算法的搜索效率也就越高；反過(guò)來(lái)拗踢，如果距離估算值與實(shí)際值相差較大脚牍，那么該算法的效率可能會(huì)比狄克斯特拉算法的還要低。如果差距再大一些巢墅，甚至可能無(wú)法得到正確答案诸狭。

不過(guò)，當(dāng)距離估算值小于實(shí)際距離時(shí)砂缩，是一定可以得到正確答案的（只是如果沒(méi)有設(shè)定合適的距離估算值作谚，效率會(huì)變差）。

安全算法

傳輸數(shù)據(jù)時(shí)的四個(gè)問(wèn)題

image	image	image	image
竊聽(tīng)	假冒	篡改	事后否認(rèn)

• 竊聽(tīng):A向B發(fā)送的消息可能會(huì)在傳輸途中被X偷看
• 假冒:A以為向B發(fā)送了消息庵芭，然而B(niǎo)有可能是X冒充的
• 篡改:即便B確實(shí)收到了A發(fā)送的消息妹懒，但也有可能像右圖這樣，該消息的內(nèi)容在途中就被X更改了双吆。
• 事后否認(rèn):B從A那里收到了消息眨唬，但作為消息發(fā)送者的A可能對(duì)B抱有惡意会前，并在事后聲稱“這不是我發(fā)送的消息”

解決這些問(wèn)題的安全技術(shù)

問(wèn)題和解決方法可以對(duì)應(yīng)如下表格

image	image

“數(shù)字簽名”技術(shù)存在“無(wú)法確認(rèn)公開(kāi)密鑰的制作者”這一問(wèn)題。要想解決這個(gè)問(wèn)題匾竿，可以使用“數(shù)字證書(shū)”技術(shù)瓦宜。

加密的基礎(chǔ)知識(shí)

我們需要給想要保密的數(shù)據(jù)加密。加密后的數(shù)據(jù)被稱為“密文”岭妖。

收到密文后临庇，需要解除加密才能得到原本的數(shù)據(jù)。把密文恢復(fù)為原本數(shù)據(jù)的操作就叫作“解密”昵慌。

在加密運(yùn)算上會(huì)用到“密鑰”假夺。所以加密就是用密鑰對(duì)數(shù)據(jù)進(jìn)行數(shù)值運(yùn)算，把數(shù)據(jù)變成第三者無(wú)法理解的形式的過(guò)程.

哈希函數(shù)

哈希函數(shù)可以把給定的數(shù)據(jù)轉(zhuǎn)換成固定長(zhǎng)度的無(wú)規(guī)律數(shù)值斋攀。轉(zhuǎn)換后的無(wú)規(guī)律數(shù)值可以作為數(shù)據(jù)摘要應(yīng)用于各種各樣的場(chǎng)景已卷。

輸出的無(wú)規(guī)律數(shù)值就是“哈希值”。哈希值雖然是數(shù)字淳蔼，但多用十六進(jìn)制來(lái)表示侧蘸。

哈希函數(shù)的特征

• 輸出的哈希值數(shù)據(jù)長(zhǎng)度不變
• 如果輸入的數(shù)據(jù)相同，那么輸出的哈希值也必定相同
• 即使輸入的數(shù)據(jù)相似鹉梨，但哪怕它們只有一比特的差別讳癌，那么輸出的哈希值也會(huì)有很大的差異。輸入相似的數(shù)據(jù)并不會(huì)導(dǎo)致輸出的哈希值也相似
• 即使輸入的兩個(gè)數(shù)據(jù)完全不同俯画，輸出的哈希值也有可能是相同的析桥，雖然出現(xiàn)這種情況的概率比較低。這種情況叫作“哈希沖突”
• 不可能從哈希值反向推算出原本的數(shù)據(jù)艰垂。輸入和輸出不可逆這一點(diǎn)和加密有很大不同
• 求哈希值的計(jì)算相對(duì)容易

哈希函數(shù)的算法中具有代表性的是MD5泡仗、SHA-1和SHA-2等。其中SHA-2是現(xiàn)在應(yīng)用較為廣泛的一個(gè)猜憎，

而MD5和SHA-1存在安全隱患娩怎，不推薦使用。不同算法的計(jì)算方式也會(huì)有所不同胰柑，比如SHA-1需要經(jīng)過(guò)數(shù)百次的加法和移位運(yùn)算才能生成哈希值截亦。

共享密鑰加密

共享密鑰加密是加密和解密都使用相同密鑰的一種加密方式。由于使用的密鑰相同柬讨，所以這種算法也被稱為“對(duì)稱加密”

實(shí)現(xiàn)共享密鑰加密的算法有凱撒密碼崩瓤、AES、DES踩官、動(dòng)態(tài)口令等却桶，其中AES的應(yīng)用最為廣泛。

存在的問(wèn)題:密鑰可能被竊聽(tīng)

公開(kāi)密鑰加密

公開(kāi)密鑰加密是加密和解密使用不同密鑰的一種加密方法。由于使用的密鑰不同颖系，所以這種算法也被稱為“非對(duì)稱加密”嗅剖。加密用的密鑰叫作“公開(kāi)密鑰”，解密用的叫作“私有密鑰”嘁扼。

實(shí)現(xiàn)公開(kāi)密鑰加密的算法有RAS算法信粮、橢圓曲線加密算法等，其中使用最為廣泛的是RSA算法趁啸。

存在的問(wèn)題: 中間人攻擊（man-in-the-middleattack）--通過(guò)中途替換公開(kāi)密鑰來(lái)竊聽(tīng)數(shù)據(jù)

混合加密

共享密鑰加密存在無(wú)法安全傳輸密鑰的密鑰分配問(wèn)題强缘，公開(kāi)密鑰加密又存在加密解密速度較慢的問(wèn)題。結(jié)合這兩種方法以實(shí)現(xiàn)互補(bǔ)的一種加密方法就是混合加密不傅。

該機(jī)制的主要過(guò)程為：先用非對(duì)稱加密（計(jì)算復(fù)雜度較高）協(xié)商出一個(gè)臨時(shí)的對(duì)稱加密密鑰（或稱會(huì)話密鑰）欺旧，然后雙方再通過(guò)對(duì)稱加密算法（計(jì)算復(fù)雜度較低）對(duì)所傳遞的大量數(shù)據(jù)進(jìn)行快速的加密處理。

混合加密在安全性和處理速度上都有優(yōu)勢(shì)蛤签。能夠?yàn)榫W(wǎng)絡(luò)提供通信安全的SSL協(xié)議也應(yīng)用了混合加密方法。SSL是Secure Sockets Layer（安全套接層）的簡(jiǎn)寫(xiě)栅哀，該協(xié)議經(jīng)過(guò)版本升級(jí)后震肮，現(xiàn)在已正式命名為T(mén)LS（Transport Layer Security，傳輸層安全）留拾。但是戳晌，SSL這個(gè)名字在人們心中已經(jīng)根深蒂固，因此該協(xié)議現(xiàn)在也常被稱為SSL協(xié)議或者SSL / TLS協(xié)議痴柔。

迪菲-赫爾曼密鑰交換

迪菲-赫爾曼（Diffie-Hellman）密鑰交換是一種可以在通信雙方之間安全交換密鑰的方法沦偎。這種方法通過(guò)將雙方共有的秘密數(shù)值隱藏在公開(kāi)數(shù)值相關(guān)的運(yùn)算中，來(lái)實(shí)現(xiàn)雙方之間密鑰的安全交換咳蔚。

image

根據(jù)素?cái)?shù)P豪嚎、生成元G和“GX mod P”求出X的問(wèn)題就是“離散對(duì)數(shù)問(wèn)題”，人們至今還未找到這個(gè)問(wèn)題的解法谈火，而迪菲-赫爾曼密鑰交換正是利用了這個(gè)數(shù)學(xué)難題侈询。

數(shù)學(xué)原理

消息認(rèn)證碼

消息認(rèn)證碼可以實(shí)現(xiàn)“認(rèn)證”和“檢測(cè)篡改”這兩個(gè)功能。密文的內(nèi)容在傳輸過(guò)程中可能會(huì)被篡改糯耍，這會(huì)導(dǎo)致解密后的內(nèi)容發(fā)生變化扔字，從而產(chǎn)生誤會(huì)。消息認(rèn)證碼就是可以預(yù)防這種情況發(fā)生的機(jī)制温技。

由密鑰和密文生成的值就是消息認(rèn)證碼革为，以下簡(jiǎn)稱為MAC（Message Authentication Code）。

我們可以把MAC想象成是由密鑰和密文組成的字符串的“哈希值”舵鳞。計(jì)算MAC的算法有HMAC震檩、OMAC、CMAC等系任。目前恳蹲，HMAC的應(yīng)用最為廣泛虐块。

數(shù)字簽名

數(shù)字簽名不僅可以實(shí)現(xiàn)消息認(rèn)證碼的認(rèn)證和檢測(cè)篡改功能，還可以預(yù)防事后否認(rèn)問(wèn)題的發(fā)生嘉蕾。由于在消息認(rèn)證碼中使用的是共享密鑰加密贺奠，所以持有密鑰的收信人也有可能是消息的發(fā)送者，這樣是無(wú)法預(yù)防事后否認(rèn)行為的错忱。而數(shù)字簽名是只有發(fā)信人才能生成的儡率，因此使用它就可以確定誰(shuí)是消息的發(fā)送者了。

數(shù)字證書(shū)

“公開(kāi)密鑰加密”和“數(shù)字簽名”無(wú)法保證公開(kāi)密鑰確實(shí)來(lái)自信息的發(fā)送者以清。因此儿普，就算公開(kāi)密鑰被第三者惡意替換，接收方也不會(huì)注意到掷倔。所以需要向認(rèn)證中心（Certification Authority, CA）申請(qǐng)發(fā)行證書(shū)眉孩，證明公開(kāi)密鑰PA確實(shí)由自己生成。

數(shù)字證書(shū)就是像這樣通過(guò)認(rèn)證中心來(lái)?yè)?dān)保公開(kāi)密鑰的制作者勒葱。這一系列技術(shù)規(guī)范被統(tǒng)稱為“公鑰基礎(chǔ)設(shè)施”（Public Key Infrastructure, PKI）浪汪。

聚類

什么是聚類

聚類就是在輸入為多個(gè)數(shù)據(jù)時(shí)，將“相似”的數(shù)據(jù)分為一組的操作凛虽。1個(gè)組就叫作1個(gè)“簇”死遭。下面的示例中每個(gè)點(diǎn)都代表1個(gè)數(shù)據(jù)，在平面上位置較為相近凯旋、被圈起來(lái)的點(diǎn)就代表一類相似的數(shù)據(jù)呀潭。也就是說(shuō)，這些數(shù)據(jù)被分為了3個(gè)簇至非。

image

k-means算法

k-means算法是聚類算法中的一種钠署，它可以根據(jù)事先給定的簇的數(shù)量進(jìn)行聚類。

算法步驟

1. 首先準(zhǔn)備好需要聚類的數(shù)據(jù)荒椭，然后決定簇的數(shù)量,本例中我們將簇的數(shù)量定為
2. 隨機(jī)選擇3個(gè)點(diǎn)作為簇的中心點(diǎn)
3. 計(jì)算各個(gè)數(shù)據(jù)分別和3個(gè)中心點(diǎn)中的哪一個(gè)點(diǎn)距離最近
4. 將數(shù)據(jù)分到相應(yīng)的簇中踏幻。這樣，3個(gè)簇的聚類就完成了
5. 計(jì)算各個(gè)簇中數(shù)據(jù)的重心戳杀，然后將簇的中心點(diǎn)移動(dòng)到這個(gè)位置
6. 重新計(jì)算距離最近的簇的中心點(diǎn)该面，并將數(shù)據(jù)分到相應(yīng)的簇中
7. 重復(fù)執(zhí)行“將數(shù)據(jù)分到相應(yīng)的簇中”和“將中心點(diǎn)移到重心的位置”這兩個(gè)操作，直到中心點(diǎn)不再發(fā)生變化為止

image

k-means算法中信卡，隨著操作的不斷重復(fù)隔缀，中心點(diǎn)的位置必定會(huì)在某處收斂，這一點(diǎn)已經(jīng)在數(shù)學(xué)層面上得到證明傍菇。

除了k-means算法以外猾瘸，聚類算法還有很多，其中“層次聚類算法”較為有名。與k-means算法不同牵触，層次聚類算法不需要事先設(shè)定簇的數(shù)量淮悼。在層次聚類算法中，一開(kāi)始每個(gè)數(shù)據(jù)都自成一類揽思。也就是說(shuō)袜腥，有n個(gè)數(shù)據(jù)就會(huì)形成n個(gè)簇。然后重復(fù)執(zhí)行“將距離最近的兩個(gè)簇合并為一個(gè)”的操作n-1次钉汗。每執(zhí)行1次羹令，簇就會(huì)減少1個(gè)。執(zhí)行n-1次后损痰，所有數(shù)據(jù)就都被分到了一個(gè)簇中福侈。在這個(gè)過(guò)程中，每個(gè)階段的簇的數(shù)量都不同卢未，對(duì)應(yīng)的聚類結(jié)果也不同肪凛。只要選擇其中最為合理的1個(gè)結(jié)果就好。合并簇的時(shí)候辽社，為了找出“距離最近的兩個(gè)簇”显拜，需要先對(duì)簇之間的距離進(jìn)行定義。根據(jù)定義方法不同爹袁，會(huì)有“最短距離法”“最長(zhǎng)距離法”“中間距離法”等多種算法。

其他算法

歐幾里得算法

歐幾里得算法（又稱輾轉(zhuǎn)相除法）用于計(jì)算兩個(gè)數(shù)的最大公約數(shù)矮固，被稱為世界上最古老的算法失息。

image

素性測(cè)試

素性測(cè)試是判斷一個(gè)自然數(shù)是否為素?cái)?shù)的測(cè)試。素?cái)?shù)（prime number）就是只能被1和其自身整除档址，且大于1的自然數(shù)盹兢。素?cái)?shù)從小到大有2、3守伸、5绎秒、7、11尼摹、13……目前在加密技術(shù)中被廣泛應(yīng)用的RSA算法就會(huì)用到大素?cái)?shù)见芹，因此“素性測(cè)試”在該算法中起到了重要的作用.

費(fèi)馬定理

網(wǎng)頁(yè)排名

網(wǎng)頁(yè)排名（PageRank，也叫作佩奇排名）是一種在搜索網(wǎng)頁(yè)時(shí)對(duì)搜索結(jié)果進(jìn)行排序的算法蠢涝。

image