演算法筆記:Linear Search, Binary Search, Selection Sort, Bubble Sort, Insertion Sort, Merge Sort

為什麼需要了解演算法?

必須注意語言內建的 api 如何實現我們運算,才能選擇最有效率的寫法。

以 Leetcode 977. Squares of a Sorted Array 為例:

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

  1. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. A is sorted in non-decreasing order.

使用 Javascript 的解法如下,這時候陣列是從大到小,因此需要反轉。這時候必須查看必須要查看 .reverse() 的說明:方法會原地(in place)反轉(reverses)一個陣列。陣列中的第一個元素變為最後一個,而最後一個元素則變成第一個。可以知道時間複雜度會增加 O (n/2) 可以省略常數為 O (n)。

var sortedSquares = function(A) {
    let i = 0;
    let n = A.length -1;
    let answer = []
    while (i !== n) {
        if (Math.abs(A[i]) > A[n]) {
            answer.push(A[i]*A[i])
            i += 1;
        } else {
            answer.push(A[n]*A[n])
            n -= 1;
        }
    }
    answer.push(A[n]*A[n])
    answer.reverse()
    return answer
};

這時候還有另一種寫法,answer.push(A[n]*A[n]) 改成 answer.unshift(A[n]*A[n]) ,但unshift 每添加一個元素,都要把現有元素往下移一個位置,因此時間複雜度為 O (n(n+1)/2),可以省略常數為 O (n^2),因此可以得知選擇 push 再 reverse 的做法會比較好。push 與 unshift 的效率比較可以參考此文章

接下來介紹這次課程的演算法:

Linear Search

Linear Search 概念十分簡單,跑一個 for loop 走訪每一項元素,找到目標值,因此效率是 O(n)。

要怎麼加速搜尋呢?這時候就需要排序過的數列來執行 Binary Search

Selection Sort

概念是反覆從未排序的數列中取出最小的元素,加入到另一個的數列,結果即為已排序的數列。運算流程如下:

  1. 從未排序的數列中找到最小的元素。
  2. 將此元素取出並加入到已排序數列最後。
  3. 重複以上動作直到未排序數列全部處理完成。
selection_sort
流程示意圖

然而實作上通常不使用額外的數列來儲存已排序的部分,而使用原地(In-place)的方式來完成,數列的左半部表示已排序部分,右半部表示未排序部分,不另外使用數列。從未排序部分找到最小的元素,利用交換的方式將元素放置已排序部分的尾端。運算流程如下:

  1. 從未排序的數列中找到最小的元素。
  2. 將此元素與已排序部分的尾端元素進行交換。
  3. 重複以上動作直到未排序數列全部處理完成。
selection_sort2
流程示意圖

時間複雜度:O(n^2),空間複雜度:O(1)

Bubble Sort

演算法過程會將最大的數值移動到陣列最後面,而較小的數值則逐漸的往陣列前端移動。

  1. 比較相鄰的兩個元素,若前面的元素較大就進行交換。
  2. 重複進行1的動作直到最後面,最後一個元素將會是最大值。
  3. 重複進行 1 , 2 的動作,每次比較到上一輪的最後一個元素。
  4. 重複進行以上動作直到沒有元素需要比較。
bs
流程示意圖

實作上直接使用迭代法迴圈就可以很容易的完成。另外可以使用額外的旗標(Flag)來判斷這一輪是否有發生交換情形,若都沒有發生交換表示數列已經是排序好的,即可跳出迴圈,因此最佳時間複雜度是有可能達到O(n)。

時間複雜度:O(n^2),空間複雜度:O(1)

Insertion Sort

概念是利用另一個數列來存放已排序部分,逐一取出未排序數列中元素,從已排序數列由後往前找到適當的位置插入。運算流程如下:

  1. 從未排序數列取出一元素。
  2. 由後往前和已排序數列元素比較,直到遇到不大於自己的元素並插入此元素之後;若都沒有則插入在最前面。
  3. 重複以上動作直到未排序數列全部處理完成。
aaa
流程示意圖

然而實作上通常不使用額外的數列來儲存已排序的部分,而使用原地(In-place)的方式來完成,數列的左半部表示已排序部分,右半部表示未排序部分,不另外使用數列。在與已排序的部分比較時,利用指派(Assign)的方式將元素往右位移,來達到插入的效果,因為位移的關係需要有另一個變數來暫存最右邊的數值。運算流程如下:

  1. 將未排序的部分最左邊元素儲存到暫存變數。
  2. 由後往前和已排序部分元素比較,若比自己大則將該元素往右邊位移。
  3. 重複2的動作直到遇到不大於自己的元素,將暫存變數寫入在該元素之後;若都沒有則寫入在最前面。
  4. 重複以上動作直到未排序部分全部處理完成。
bbb
流程示意圖

時間複雜度:O(n^2),空間複雜度:O(1)

Merge Sort

排序時需要額外的空間來處理,過程依照以下步驟進行:

  1. 將陣列分割直到只有一個元素。
  2. 開始兩兩合併,每次合併同時進行排序,合併出排序過的陣列。
  3. 重複2的動作直接全部合併完成。

流程範例如圖所示:

618px-Merge_sort_algorithm_diagram_svg

最佳時間複雜度:O(nlog n),空間複雜度:O(n),目前排序的速度一般會認為 O(nlog n) ,除了純數列可以用 Radix sort O(n)

Binary Search

搜索的目標資料必須是已經排序過的(以小到大排序為例)。其概念是每次挑選中間位置的資料來比對,若該資料小於目標值,則縮小範圍為左半部,反之亦然;因此使用這個方法每次比對後都可以濾掉一半的資料,以增快搜索速度。過程依以下步驟進行:

  1. 取出搜索範圍中點的元素。
  2. 與搜索目標比較,若相等則回傳位址。若小於則將左邊邊界改為中點右側,若大於則將右邊邊界改為中點左側。
  3. 左邊邊界不超過右邊邊界(還有資料)則重複以上動作,若已無資料則回傳-1(找不到)。
binary_search
流程範例如圖所示,例如搜索值為4的元素

時間複雜度:O(log n),空間複雜度:O(1)

參考資料:

  1. https://emn178.pixnet.net/blog/post/93915544
  2. https://emn178.pixnet.net/blog/post/93779892
  3. https://emn178.pixnet.net/blog/post/93791164
  4. https://emn178.pixnet.net/blog/post/88780407
Share on facebook
Facebook
Share on linkedin
LinkedIn
Share on twitter
Twitter

More to explorer

Close Menu