前言

事實上,要成為一個好的前端軟體工程師除了必須對於前端工程(Web 效能、build 工具、CSS layout 引擎)的部份有所了解外,也必須對於電腦科學的基礎知識有著堅實的基礎知識(資料結構、演算法、設計模式等)。接下來我們將來探討 JavaScript 常見演算法。

JavaScript 實作常見演算法

  1. Algorithm Basic
    事實上,演算法就是解決問題的方法,一般來說,所有的演算法都必須符合以下五個條件:

    1. 輸入:輸入可以沒有或是多筆資料輸入
    2. 輸出:至少產生一個輸出結果
    3. 明確性:每一個方法要很清楚明白,不可混淆不清,模稜兩可的情況
    4. 有限性:有限步驟停止完成
    5. 有效性:設計的演算法必須能證明其結果
    6. 複雜度分析:通常使用 bigO 來解釋時間複雜度:O(1) < O(loglogn) < log(logn) < O(sqrt(n)) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) < O(n^n)
    7. 問題分類
      • 無可解問題:並無演算法可以解決
      • 多項式問題:已存在多項式時間(Polynomial Time)的演算法
      • NP 問題:無確定多項式(Nondeterministic Polynomial),目前只有指數時間(Exponential Time)的演算法
      • NP-hard 問題:在 NP 問題中每一個問題可以在多項式時間轉為問題 X
      • NP-complete 問題:問題 X 屬於 NP 又屬於 NP-hard
  2. Algorithm Method

    • Brute Force 暴力法
      在各種解決問題的方法中,最原始也是最簡單的方法就是暴力法,也就是一種一種嘗試,對於小問題暴力法提供簡單的設計方式,此時我們也就沒有必要使用複雜的演算法解決這類問題,但複雜的問題效率會不好

    • Greedy Method 貪婪法
      在一種反覆的過程中,不斷取用資料的最大值最小值來進行處理,例如:

      1. 最小成本展開樹(minimum cost spanning tree),例如:Kruskal、Sollin、Prim
      2. 計算單一起源其他皆為目的地的 Dijkstra 演算法
      3. 選擇排序法(Selection Sort)
    • Divide and Conquer 個個擊破法

      將一個問題分解成數個較小的問題,逐一解決後再將各部分所得結果合併。是一種由上而下的演算法(例如:快速排序、合併排序)。基本步驟如下:

      1. 分割問題
      2. 解決子問題
      3. 組合解答
    • Dynamic Programming 動態規劃法
      若一個問題的解答可以由數個小問題解答組合而成,而且經由組合這些小問題解答得到整體解,則可以先將所有小問題的解先求出,然後再選擇最佳的組合作為整體解,是一種由下而上的演算法。使用 Dynamic Programming 一般來說會比暴力解來的有效率,特別是問題變得比較複雜時。例如:任意兩點最短距離的 Floyd-Warshall 演算法

    • Backtracking 回溯法
      逐一嘗試各種可能,以求出最佳解方式,在嘗試過程中若發現行不通時,可以退回前一步驟,重新嘗試其他可能,回溯法通常要使用堆疊來實作。
      例如:

      1. 迷宮問題(maze)
      2. 八皇后問題(eight queens)
      3. 騎士問題(knights)
    • Recursion 遞迴

  3. Sort
    排序是將一組資料根據鍵值大小作遞增或遞減排列。

    • 排序基本概念

      1. 排序可以根據資料儲存的位置來進行排序:
        內部排序、外部排序(放在輔助記憶體)
      2. 根據鍵值相同資料的相同資料是否改變與否
        穩定排序(具有相同鍵值的紀錄)、不穩定排序
      3. 根據時間複雜度
        簡單排序(平均 O(n^2))、高等排序(平均 O(nlogn)):合併、快速、堆積排序分為較小去執行
    • Bubble
      每一階段都會從頭開始比較相鄰兩記錄,若次序不正確即調換。第一階段完成後最大會跑到最右邊,依序第二大,就像泡泡浮出水面

      時間複雜度:

      1. 最佳狀況:O(n)
      2. 最差狀況:O(n^2)
      3. 平均情況:O(n^2)
    • Selection
      每次在剩餘的資料中選擇最小的資料,依大小放到正確位置

      時間複雜度:

      1. 最佳狀況:O(n)
      2. 最差狀況:O(n^2)
      3. 平均情況:O(n^2)
    • Shell
      首先先將整個陣列依照設定的間隔長度 D 交錯地分數個小陣列,並以插入排序法來排序每一個小陣列。最後再將間隔長度縮小,則排序陣列逐漸擴大,等間隔長度為 1 時為最後一次排序

      時間複雜度:

      1. 平均情況:O(nlogn) ~ O(n^2)
    • Insertion
      每拿到一個新資料,依照大小放入正確位置

      時間複雜度:

      1. 最佳狀況:O(nlog)
      2. 最差狀況:O(nlog2n)
      3. 平均情況:O(nlog2n)
    • Heap
      堆積排序主要步驟:

      1. 將所有記錄依序加入為完整二元樹
      2. 將完整二元樹調整成最大堆積樹,並將剩下節點調整成最大堆積樹,重複過程,直到最大堆積樹中沒有節點
      3. 樹根與最後節點位置對調
      4. 最後依序印出存放最大堆積樹的陣列每個元素值,得到由小到大結果

        時間複雜度:

      5. 最佳狀況:O(nlogn)
      6. 最差狀況:O(nlogn)
      7. 平均情況:O(nlogn)
    • Merge
      將資料分成好幾個 runs,然後把它們兩兩合成更大的 runs,直到合併剩一個 run。

      時間複雜度:

      1. 最佳狀況:O(nlog2n)
      2. 最差狀況:O(nlog2n)
      3. 平均情況:O(nlog2n)
    • Quick
      快速排序法的精神在於分隔的過程。分隔是利用第一個鍵值/中間做為分隔元素(pivot)並將所有資料項分為兩組,其中一組鍵值比分隔元素小,另一組鍵值比分隔元素大,分隔元素置於兩者之間。經過 n 回後所有資料會到正確位置。平均而言快速排序是最好的排序法,但非穩定排序

      時間複雜度:

      1. 最佳狀況:O(nlogn)
      2. 最差狀況:O(n^2)
      3. 平均情況:O(nlogn)
  4. Search
    搜尋是在一個檔案或是表格中找尋具有某種鍵值的資料。搜尋結果只有兩種:第一:可以成功找到該資料,第二:失敗無法找到該資料。一般來說搜尋分為循序搜尋和非循序搜尋兩種,循序搜尋又稱為線性搜尋,就是從頭開始,一筆一筆往下尋找資料。非循序搜尋在尋找資料時,不會按照順序一筆一筆尋找,常見有二分搜尋、內插搜尋及雜湊法等。

    • Sequential Search
      又稱線性搜尋法,不需事先排序,從第一筆開始逐一尋找,直到最後一筆若沒找到則資料不在檔案中。

      適用性:
      資料不需排序、資料結構不需要可以任意存取、資料結構簡單、適用動態資料、簡單

      時間複雜度:

      1. 最佳狀況:O(1)
      2. 最差狀況:O(n)
      3. 平均情況:O(n)
    • Binary Search
      使用二分搜尋前提是要先把資料排序好,其原理在於每次比對就把搜尋範圍減少一半,所以在 log2N + 1 次比對內就可以找出是否存在。類似於中序走訪由小到大

      適用性:
      資料需事先排序過、其資料結構需要可以任意存取、適用於固定資料,一般而言資料小用循序,資料大用二分搜尋

      時間複雜度:

      1. 最佳狀況:O(1)
      2. 最差狀況:O(log2N)
      3. 平均情況:O(log2N)
    • Heap Search
      雜湊法是資料結構搜尋中表現最好的演算法,平均時間複雜度 O(1),雜湊法所採用的方式是將所有的資料鍵值透過數學函數轉換成位置,再把資料鍵值存放在對應的位置上,搜尋時只要把鍵值透過函數就可以在 hash table 中找到。若是轉換位置發生碰撞則再產生新的鍵值,有點類似陣列的對應,有時又稱為字典(dictionary)

      1. 雜湊基本概念

        • 識別字:key
        • 雜湊函數:產生位置的數學函數
        • 雜湊表:記憶體中存放 key
        • 桶:將雜湊表分為數個桶,所有 key 經過函數轉換後可得到桶位置
        • 槽:每個桶有 s 個槽,通常 s = 1 也就是每個桶中只有一個槽
        • 識別字密度:n / T
        • 載入密度: alpha = n /sb
        • 同義字:f(x1) = f(x2),x1 和 x2 同義
        • 碰撞:產生相同位置
        • 溢位:滿了
        • 溢位處理
        • 叢集:資料值集中某一區段,常發生碰撞
      2. 雜湊函數

        • 中間平方法:n^2
        • 除法:f(x) = x % M
        • 摺疊法
        • 數位分析法
      3. 碰撞處理方式

        • 線性探測:index + 1
        • 鏈結串列
        • 再次雜湊
      4. 雜湊優點:不必排序,在沒有碰撞或溢位時只需讀取一次,搜尋和資料多寡無關,具備保密性,可以做資料壓縮

    • Interpolation Search

總結

以上介紹了前端工程工具箱:JavaScript 實作常見演算法,在接下來的章節中我們將為大家打開前端工程的工具箱,介紹那些必須掌握的前端軟體工程知識。

延伸閱讀

  1. 演算法筆記

喜歡我們的文章嗎?歡迎分享按讚給予我們支持和鼓勵!