Độ phức tạp thuật toán — Big-O Notation

Tại sao cần Big-O?

Cùng bài toán, 2 cách giải có thể khác nhau hàng triệu lần về tốc độ khi input lớn.

Big-O đo tốc độ tăng của thời gian chạy theo input size n.

Các Complexity Class

O(1)       — Constant    : HashMap.get()
O(log n)   — Logarithmic : Binary Search
O(n)       — Linear      : Array scan
O(n log n) — Linearithmic: Merge Sort, Quick Sort (avg)
O(n²)      — Quadratic   : Bubble Sort, nested loops
O(2ⁿ)      — Exponential : Brute-force subsets
O(n!)      — Factorial   : Brute-force permutations

Phân tích ví dụ

// O(n) — linear scan
public int findMax(int[] arr) {
    int max = arr[0];
    for (int x : arr) {        // n iterations
        if (x > max) max = x;  // O(1) per iteration
    }
    return max;
}

// O(n²) — nested loops
public boolean hasDuplicate(int[] arr) {
    for (int i = 0; i < arr.length; i++) {         // n
        for (int j = i + 1; j < arr.length; j++) { // n
            if (arr[i] == arr[j]) return true;
        }
    }
    return false;
}

// O(n) — HashSet approach (trade space for time)
public boolean hasDuplicateFast(int[] arr) {
    Set<Integer> seen = new HashSet<>();
    for (int x : arr) {
        if (!seen.add(x)) return true; // O(1) per lookup
    }
    return false;
}

Key insight: Big-O bỏ qua constants. O(2n) = O(n). Nhưng trong thực tế, constants matter — đó là lý do QuickSort nhanh hơn MergeSort dù cùng O(n log n).