表示二進(jìn)制搜索的時(shí)間復(fù)雜性。我們可以使用合并排序?qū)?shù)組進(jìn)行有效排序。這種排序算法的一個(gè)例子是添加到/刪除一個(gè)鏈表。對(duì)于一個(gè)排序算法來說，合并排序的時(shí)間復(fù)雜度是最好的：O(log N) 。本課將介紹三種最流行的算法，即搜索、排序和在鏈表中添加/刪除。眾多其他的算法共享這些算法例子背后的概念。通過對(duì)這三個(gè)算法實(shí)例的講解，我們可以打下堅(jiān)實(shí)的基礎(chǔ)，并在未來自信地接受新的算法挑戰(zhàn)。

算法實(shí)例#1：二進(jìn)制搜索

基本的搜索算法被稱為二進(jìn)制搜索，它接受一個(gè)排序的數(shù)組作為輸入。它返回我們想找的值的索引。下面的步驟是我們?nèi)绾瓮瓿蛇@個(gè)任務(wù)的：

找到排序后的數(shù)組的中心點(diǎn)。

將中點(diǎn)與興趣值進(jìn)行比較

在數(shù)組的右邊進(jìn)行二進(jìn)制搜索，如果中點(diǎn)大于該值。

如果中點(diǎn)小于興趣值，在數(shù)組的左邊進(jìn)行二進(jìn)制搜索。

繼續(xù)下去，直到感興趣的值等于平均值，或者直到清楚地發(fā)現(xiàn)該事項(xiàng)不在數(shù)組中。

從上面的階段可以看出，我們的解決方案可能是遞歸的。在每次迭代中，直到我們的數(shù)組只包括我們感興趣的值，我們將向我們的函數(shù)提供一個(gè)較小的品種。為了從原始數(shù)組中檢索出我們項(xiàng)目的索引，我們必須為我們的集合建立正確的索引，并在每次迭代中保持對(duì)索引偏移的跟蹤。

O是二進(jìn)制搜索(login)的時(shí)間復(fù)雜性。這一點(diǎn)從以下事實(shí)中可以看出：即使我們的輸入數(shù)組的大小增加了一倍，我們的方法仍然只需要增加一次迭代就可以達(dá)到預(yù)期的結(jié)果。我們把二進(jìn)制搜索的重要性歸結(jié)為計(jì)算機(jī)科學(xué)中的一種屬性算法。

算法的例子#2：合并排序

與 "分而治之 "類似，合并排序可以有效地對(duì)數(shù)組進(jìn)行排序。我們可以在下面的階段使用合并排序的實(shí)現(xiàn)。

如果數(shù)組只有一個(gè)元素，則返回，因?yàn)槲覀円呀?jīng)對(duì)它進(jìn)行了排序。

把一個(gè)數(shù)組分成兩半，直到不能再分為止。

一旦我們有了初始排序的數(shù)組，我們就把較小的數(shù)組按相同的順序合并。

我們將設(shè)計(jì)兩種方法來實(shí)現(xiàn)合并排序。一種是處理數(shù)組的除法，另一種是將兩個(gè)未排序的數(shù)組重新合并成一個(gè)排序的數(shù)組。我們反復(fù)調(diào)用分割函數(shù)(merge sort)，直到我們的集合只有一個(gè)成員。然后我們?cè)侔阉鼈兒喜⒁淮?，再給你我們的排序數(shù)組。

一個(gè)排序算法的最佳時(shí)間復(fù)雜度是O(N log N)，而合并排序就擁有這樣的復(fù)雜度。通過使用分割和征服的策略，我們大大增加了排序的有效性，而排序本來就是一個(gè)昂貴的計(jì)算過程。

算法的例子#3：從鏈接列表中添加和刪除項(xiàng)目

作為計(jì)算機(jī)科學(xué)的一個(gè)重要組成部分，鏈表以其恒定時(shí)間的插入和刪除而聞名。通過采用節(jié)點(diǎn)和指針，我們可以比利用數(shù)組更快速有效地完成一些任務(wù)。

Ruby中的鏈接列表

一個(gè)鏈接列表由包含一些數(shù)據(jù)的節(jié)點(diǎn)和一個(gè)指向它之后的節(jié)點(diǎn)的指針組成。我們可以在Ruby中通過定義一個(gè)名為Node的結(jié)構(gòu)來表達(dá)這一點(diǎn)，其參數(shù)為：數(shù)據(jù)和下一個(gè)Node。唯一要做的就是指定兩個(gè)方法，插入Node和刪除Node，這兩個(gè)方法分別接受一個(gè)頭部節(jié)點(diǎn)和一個(gè)要插入或刪除的地方。我們希望插入的節(jié)點(diǎn)結(jié)構(gòu)是插入節(jié)點(diǎn)函數(shù)的一個(gè)額外參數(shù)，名為Node。然后我們進(jìn)行循環(huán)，直到我們到達(dá)我們想要添加或刪除的地方。一旦我們到達(dá)目的地，我們就修改指針以反映我們的插入或刪除。

當(dāng)利用鏈表而不是數(shù)組時(shí)，我們可以從一個(gè)集合的中心刪除項(xiàng)目，而不需要重新組織內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)的其余部分。通過選擇最適合我們要求的數(shù)據(jù)結(jié)構(gòu)，我們可以實(shí)現(xiàn)最大的效率。

海馬課堂留學(xué)生作業(yè)輔導(dǎo)，根據(jù)學(xué)生的輔導(dǎo)需求匹配背景相符的專業(yè)老師。1V1個(gè)性化備課，雙語教學(xué)，實(shí)時(shí)輔導(dǎo)，講解相關(guān)知識(shí)點(diǎn)和解題思路，提供大型作業(yè)任務(wù)的解決方案，輔導(dǎo)計(jì)算機(jī)編程語言操作，教授學(xué)生高效完成PPT和演講稿，針對(duì)性解決留學(xué)生各類作業(yè)中遇到的困擾，提高作業(yè)成績(jī)！