KC Blog

演算法日記

演算法日記 - Big-O 表示法

作者 WaitZ
FundamentalsbeginnerBig-OO(1), O(log n), O(n), O(n log n), O(n^2)algorithmsbig-obeginnercomplexity-analysis

今日主題

主題: Big-O 表示法
難度: 初級
分類: 演算法基礎

概念學習

核心概念

Big-O 表示法是一種數學符號，用於描述演算法時間複雜度或空間複雜度的上界。它表示最壞情況，幫助我們理解當輸入規模增長時演算法如何擴展。

核心原則：Big-O 關注增長率，而非精確執行時間。

  • 忽略常數：O(2n) → O(n)
  • 忽略低階項：O(n² + n) → O(n²)
  • 關注當 n 趨近無限大時的行為

常見時間複雜度（由快到慢）

  1. O(1) - 常數時間

    • 透過索引存取陣列元素
    • 雜湊表查找
    • 範例：array[5]、map.get(key)

  2. O(log n) - 對數時間

    • 已排序陣列的二元搜尋
    • 平衡樹的操作
    • 範例：透過將搜尋空間減半來尋找元素

  3. O(n) - 線性時間

    • 遍歷陣列一次
    • 線性搜尋
    • 範例：for (int i = 0; i < n; i++)

  4. O(n log n) - 線性對數時間

    • 高效排序演算法（合併排序、快速排序、堆積排序）
    • 範例：對陣列進行排序

  5. O(n²) - 平方時間

    • 巢狀迴圈遍歷陣列
    • 氣泡排序、選擇排序、插入排序
    • 範例：比較每個元素與其他所有元素

  6. O(2^n) - 指數時間

    • 解決子問題的遞迴演算法
    • 範例：樸素的費波那契遞迴解法

  7. O(n!) - 階乘時間

    • 產生所有排列組合
    • 旅行推銷員問題的暴力解法

關鍵重點

  • 去除常數：O(2n) = O(n)、O(1000) = O(1)
  • 去除非主導項：O(n² + n) = O(n²)、O(n + log n) = O(n)
  • 不同輸入使用不同變數：處理兩個陣列時使用 O(a + b) 而非 O(n)
  • Big-O 描述最壞情況（除非另有說明，最佳情況為 Big-Ω，平均情況為 Big-Θ）
  • 空間複雜度遵循相同規則但衡量記憶體使用量

實際比較

當 n = 1,000,000 時：

  • O(1)：1 次操作
  • O(log n)：約 20 次操作
  • O(n)：1,000,000 次操作
  • O(n log n)：約 20,000,000 次操作
  • O(n²)：1,000,000,000,000 次操作（太慢了！）

程式實作範例

O(1) - 常數時間

fun getFirstElement(array: Array<Int>): Int {
    return array[0]  // 無論陣列大小如何，總是花費相同時間
}

O(n) - 線性時間

fun findMax(array: Array<Int>): Int {
    var max = array[0]
    for (element in array) {  // 迴圈 n 次
        if (element > max) {
            max = element
        }
    }
    return max
}

O(n²) - 平方時間

fun printPairs(array: Array<Int>) {
    for (i in array.indices) {          // n 次
        for (j in array.indices) {      // 每個 i 執行 n 次
            println("${array[i]}, ${array[j]}")
        }
    }
    // 總計：n * n = n² 次操作
}

O(log n) - 對數時間

fun binarySearch(array: Array<Int>, target: Int): Int {
    var left = 0
    var right = array.size - 1
    
    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            array[mid] == target -> return mid
            array[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }
    return -1
    // 每次迭代將搜尋空間減半
}

重要細節

常見誤解

  • O(n) 不一定總是優於 O(n²)：對於小輸入，常數很重要
  • 更好的複雜度 ≠ 實際更快：常數為 1000 的 O(n) 可能比常數為 1 的 O(n²) 在小 n 時慢
  • 空間時間權衡：有時我們使用更多空間（記憶體）來達到更好的時間複雜度

何時需要最佳化

  • 大型資料集（n > 10,000）
  • 頻繁執行的程式碼
  • 即時系統
  • 對於小 n，可讀性 > 最佳化

分析技巧

  1. 識別迴圈及其迭代次數
  2. 檢查巢狀操作
  3. 考慮遞迴呼叫深度和分支
  4. 根據輸入大小計算操作次數
  5. 專注於 n 增大時的主導項

今日反思

心得：

  • 選擇演算法時始終考慮輸入大小
  • O(n) 迴圈內的 O(1) 操作會產生 O(n) 的總複雜度
  • 巢狀迴圈通常導致 O(n²) 或更差 - 盡量避免

相關概念：

  • 空間複雜度分析
  • 最佳/平均/最壞情況分析（Big-Ω、Big-Θ）
  • 攤銷時間複雜度
  • 分治演算法的主定理