Big-O 記號：時間複雜度

Java 程式碼最佳化

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

什麼是時間複雜度？

時間複雜度：度量執行時間隨輸入規模成長的方式
幫你回答：「當資料放大 10× 會怎樣？」
不著重於絕對時間

Big-O 記號

用數學記號描述最壞情況。

常見的複雜度類別：

O(1)：常數時間－與大小無關

理解 O(1)

ArrayList 的 get() 是 O(1) 操作範例

以下是持有 Strings 的 ArrayList 內部（簡化）實作：

public class ArrayList {}
    private String[] data; // Internal array
    private int size;

    // Get operation - direct array access
    public String get(int index) {
        return data[index]; // O(1)
    }
}

Big-O 記號

用數學記號描述最壞情況

常見的複雜度類別：

O(1)：常數時間－與大小無關
O(n)：線性時間－隨輸入成長

理解 O(n)

類似例子：ArrayList 的 contains()

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    // Linear search through array
    for (int i = 0; i < size; i++) {
        if (o.equals(elementData[i])) {
            return i;
        }
    }
    return -1; // Not found
}

Big-O 記號

用數學記號描述最壞情況

常見的複雜度類別：

O(1)：常數時間－與大小無關
O(n)：線性時間－隨輸入成長
O(n²)：平方時間－隨輸入平方成長

平方複雜度的實用範例

// 找出和為目標值的一對數字
// 時間複雜度：O(n²)

public int[] findPairWithSum(ArrayList<Integer> numbers, int targetSum) {
    for (int i = 0; i < numbers.size(); i++) {
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers.get(i) + numbers.get(j) == targetSum) {
                console.log("Found them!")
            }
        }
    }
}

為什麼時間複雜度重要

輸入規模的影響：

O(1)：1,000 -> 1,000,000 筆＝時間相同！
O(n)：1,000 -> 1,000,000 筆＝慢 1,000×
O(n²)：1,000 -> 1,000,000 筆＝慢 1,000,000×

Screenshot 2025-05-10 at 2.27.06 PM.png

一起來練習吧！

Java 程式碼最佳化