Docker
Network
RxJS
Nginx
TypeScript
Data Structure And Algorithm
JavaScript
PostgreSQL
React
Git演算法筆記：Big O Notation、搜尋方法與解題手法
本文分為兩大部分：
- Big O 與常見搜尋演算法
- 常見解題手法（Multiple Pointers、Frequency Counter、Sliding Window）
一、Big O 與常見搜尋演算法
什麼是 Big O Notation
Big O Notation 用於描述演算法在輸入規模增長時，執行時間或佔用空間的變化趨勢。
- 時間複雜度（Time Complexity）： 估算演算法執行步驟數量。
- 空間複雜度（Space Complexity）： 估算演算法運行期間額外佔用的記憶體大小。
常見時間複雜度比較如下（方塊數量僅示意增長速度）：
| 複雜度 | 名稱 | 成長速度示意 | 典型範例 |
|---|---|---|---|
| O(1) | 常數 | ▇ | 陣列索引存取 |
| O(log N) | 對數 | ▇▇ | Binary Search |
| O(N) | 線性 | ▇▇▇ | Linear Search |
| O(N log N) | 線性對數 | ▇▇▇▇ | 合併排序、快速排序（平均） |
| O(N²) | 平方 | ▇▇▇▇▇ | 巢狀迴圈、氣泡排序 |
| O(2^N) | 指數 | ▇▇▇▇▇▇▇ | 遞迴暴力破解（費氏數列遞迴） |
NOTE: 當 N 變大時，指數與階乘級別會急遽變慢，實務上應避免。
1. 線性搜尋（Linear Search）
適用於任何類型的陣列，無需排序。透過逐一比對，直到找到目標值為止。
- 時間複雜度： O(N)
2. 二分搜尋（Binary Search）
需在已排序陣列中進行，每次從中間分割，判斷應往左或往右繼續搜尋。
- 時間複雜度： O(log N)
遞迴寫法
while 迴圈寫法
3. Naive 字串搜尋（Naive String Search）
計算目標字串在主字串中出現的次數。
- 時間複雜度（最差）： O(N * M)，其中 N 為主字串長度，M 為目標字串長度。
二、常見解題手法
以下三種模式能大幅降低許多問題的時間複雜度。
1. Multiple Pointers
在排序陣列上以兩端指標向中間推進，常用於和、差比對問題。
Example 1：找出和為 0 的第一對數字
給定一個已排序的陣列，從頭到尾找出第一組加起來等於 0 的兩個數字。如果有找到就回傳這組數字，找不到就回傳 undefined。
預期結果：
下方程式碼中第一種解法(sumZero)較粗糙，時間複雜度為O(n^2)，第二種(optimizedSumZero)解法時間複雜度為O(n)
Example 2：計算陣列中的獨立值數量
給定一個已排序的陣列，計算並回傳裡面有幾個不同的數字（unique value）。
2. Frequency Counter
這種做法是用迴圈把陣列裡的每個值存進一個物件（像是雜湊表），用來記錄每個元素出現的次數。這樣可以避免巢狀迴圈，讓效率從 O(n^2) 變成 O(n)，速度更快。
Example 1：比對兩陣列是否滿足平方對應
寫一個函式，傳入兩個陣列。如果第一個陣列裡每個數字的平方都剛好出現在第二個陣列，且出現的次數也一樣，就回傳 true；否則回傳 false。
預期結果：
下面的第一個寫法（same）比較慢，因為它的時間複雜度是 O(N^2)；第二個寫法（optimizedSame）有優化，速度更快，時間複雜度是 O(N)。
Example 2：判斷兩字串是否為 Anagrams
定義一個函式，傳入兩個字串，檢查這兩個字串是否可以透過重新排列字母變成一樣（即是否為 anagram）。
預期結果：
下方程式碼的兩種方法之時間複雜度皆為O
3. Sliding Window
這種方法就是在陣列上建立一個「視窗」（可以用索引或陣列表示），然後根據需求移動或調整這個視窗，來追蹤一段連續的資料。常見用法像是找出最大或最小的總和、最長的子字串等等。
Example：固定長度視窗 – 最大子陣列總和
寫一個函式，傳入一個陣列和一個數字 n，回傳陣列中連續 n 個數字加總的最大值。