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

算法實例#1：二進制搜索

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

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

將中點與興趣值進行比較

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

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

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

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

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

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

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

如果數(shù)組只有一個元素，則返回，因為我們已經(jīng)對它進行了排序。

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

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

我們將設計兩種方法來實現(xiàn)合并排序。一種是處理數(shù)組的除法，另一種是將兩個未排序的數(shù)組重新合并成一個排序的數(shù)組。我們反復調(diào)用分割函數(shù)(merge sort)，直到我們的集合只有一個成員。然后我們再把它們合并一次，再給你我們的排序數(shù)組。

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

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

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

Ruby中的鏈接列表

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

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

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