Độ phức tạp Big-O từ bản chất — Theta, Omega, amortized intro

Bạn nhận một ticket: tính xem danh sách 100.000 user ID có phần tử trùng không. Bạn viết vòng lặp lồng nhau, test vài trăm phần tử — chạy tốt. Deploy lên production với 100.000 bản ghi thật, request đó mất 10 giây. Cùng lúc đó, đồng nghiệp commit một đoạn thay thế chỉ vài dòng — chạy 5 mili giây. Gấp 2.000 lần. Cùng kết quả đúng, cùng ngôn ngữ, cùng máy chủ.

Sự chênh lệch đó không đến từ constant, không đến từ JVM warm-up. Nó đến từ cấu trúc tăng trưởng khác nhau khi n lớn — thứ mà Big-O đo chính xác.

Bài này giải thích Big-O từ bản chất toán học và kỹ thuật: tại sao bỏ constants vẫn đúng, phân biệt O / Theta / Omega, 7 complexity class với code Java 21 thực tế, và những pitfall khiến dev hiểu nhầm "Big-O thấp hơn là luôn nhanh hơn".

1. Analogy — Tìm tên trong danh bạ điện thoại

Bạn cần tìm số điện thoại của Nguyễn Văn Trung trong cuốn danh bạ 10.000 trang, sắp xếp theo tên.

Cách 1 — Linear scan: lật từng trang từ đầu, đọc tên, so sánh. Xui thì lật hết 10.000 trang. Danh bạ dày gấp đôi → mất gấp đôi thời gian.

Cách 2 — Binary divide: mở giữa sách. Trung đứng sau trang giữa → bỏ nửa đầu. Mở giữa nửa còn lại. Tiếp tục. Sau 14 lần chia đôi, tìm thấy (vì 2^14 = 16.384). Danh bạ dày gấp đôi → chỉ cần thêm 1 bước.

2. Hai cách giải hasDuplicate — gấp 2.000 lần

Đây là code gây ra ticket 10 giây nói ở đầu bài:

// O(n^2) — naive nested loop
// For each pair (i, j), compare. Total: n*(n-1)/2 comparisons.
public boolean hasDuplicateNaive(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] == arr[j]) return true;
        }
    }
    return false;
}

Với n = 100.000, vòng lặp trong chạy tổng cộng 100.000 * 99.999 / 2 ≈ 5 tỷ lần so sánh. Ở tốc độ ~500M phép/giây → 10 giây.

Và đây là đoạn thay thế 5ms:

// O(n) — HashSet lookup
// One pass: add each element, return true if add() returns false (already present).
public boolean hasDuplicateFast(int[] arr) {
    Set<Integer> seen = new HashSet<>();
    for (int x : arr) {
        if (!seen.add(x)) return true; // add() returns false if already present
    }
    return false;
}

HashSet.add() chạy O(1) amortized (sẽ giải thích ở mục 7). Vòng lặp chạy tối đa n lần → tổng O(n). Với n = 100.000: 100.000 phép thay vì 5 tỷ — 50.000 lần ít hơn.

Đây chính là Big-O trong thực tế: cùng đúng, khác nhau về cấu trúc tăng trưởng.

3. Định nghĩa — Big-O, Theta, Omega

3.1 Big-O đo gì

Big-O không đo thời gian chạy tuyệt đối. Nó đo upper bound của tốc độ tăng khi n tiến đến vô cực.

Nói chính thức: T(n) = O(f(n)) nếu tồn tại hằng số c > 0 và n₀ sao cho với mọi n ≥ n₀, T(n) ≤ c * f(n).

Nghĩa thực tế: dù constants cụ thể là bao nhiêu, khi n đủ lớn, T(n) bị chặn trên bởi một bội số của f(n).

3.2 Tại sao bỏ constants

Xét hàm thực tế: T(n) = 3n² + 100n + 5.

Khi n tăng lên:

• n = 10: 3*100 + 100*10 + 5 = 1.305. Hạng 100n chiếm 76%.
• n = 1.000: 3*1.000.000 + 100.000 + 5 ≈ 3.100.005. Hạng 3n² chiếm 97%.
• n = 1.000.000: 3n² chiếm 99,997%.

Ở n lớn, 3n² nuốt toàn bộ các hạng còn lại. Constant 3 cũng mờ dần — nếu phần cứng nhanh gấp đôi, 3 thành 1.5, nhưng bậc vẫn là n². Phần cứng tốt hơn cải thiện constant, không cải thiện bậc.

Kết quả: T(n) = 3n² + 100n + 5 = O(n²). Ta bỏ hạng bậc thấp và constant của hạng cao nhất.

3.3 Ba ký hiệu — O, Theta, Omega

Ví dụ với Merge Sort:

• Best case và worst case đều là n log n → Θ(n log n).
• Ta viết O(n log n) — đúng nhưng không tight (nói "không tệ hơn", không nói "chính xác").

Ví dụ với Linear Search:

• Best case: tìm thấy ngay phần tử đầu → Ω(1).
• Worst case: phần tử cuối cùng → O(n).
• Không có Θ đơn giản vì best/worst case khác nhau.

Trong thực tế, dev dùng O gần như toàn bộ thời gian vì:

1. Ta quan tâm worst case nhiều hơn — đó là SLA production.
2. Nói "không tệ hơn O(n log n)" an toàn hơn cam kết tight bound.
3. API doc, Javadoc đều dùng O — nhất quán với ecosystem.

4. Bảy complexity class — code và tăng trưởng

4.1 O(1) — Constant

Số bước không phụ thuộc n. HashMap lookup là ví dụ kinh điển:

// O(1) amortized — hash computation + array index, independent of map size
Map<String, Integer> scores = new HashMap<>();
scores.put("alice", 95);
int score = scores.get("alice"); // does not scan all entries

Lưu ý: "amortized O(1)" — sẽ giải thích nghĩa tại mục 7.

4.2 O(log n) — Logarithmic

Mỗi bước loại bỏ nửa input còn lại. Binary search:

// O(log n) — halves the search space each iteration
public int binarySearch(int[] sorted, int target) {
    int lo = 0, hi = sorted.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2; // avoid integer overflow
        if (sorted[mid] == target) return mid;
        else if (sorted[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

n = 1.000.000 → tối đa 20 bước (vì log₂(1.000.000) ≈ 20).

4.3 O(n) — Linear

Đọc qua từng phần tử một lần:

// O(n) — visits every element exactly once
public int sumArray(int[] arr) {
    int total = 0;
    for (int x : arr) total += x;
    return total;
}

4.4 O(n log n) — Linearithmic

Merge Sort: chia đôi O(log n) lần, mỗi lần merge mất O(n):

// O(n log n) — divide and conquer: log n levels, each level merges O(n) total
public void mergeSort(int[] arr, int lo, int hi) {
    if (lo >= hi) return;
    int mid = (lo + hi) / 2;
    mergeSort(arr, lo, mid);
    mergeSort(arr, mid + 1, hi);
    merge(arr, lo, mid, hi); // O(n) merge of two sorted halves
}

Collections.sort() và Arrays.sort() cho object đều là O(n log n) (TimSort).

4.5 O(n²) — Quadratic

Vòng lặp lồng, mỗi vòng chạy n lần:

// O(n^2) — for each of n elements, scan remaining n elements
public int[] bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp;
            }
        }
    }
    return arr;
}

4.6 O(2ⁿ) — Exponential

Mỗi lần gọi đệ quy, tạo ra 2 nhánh con — cây nhị phân:

// O(2^n) — each call spawns two recursive calls, exponential call tree
public long fibNaive(int n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2); // two branches per level
}

n = 50 → khoảng 2^50 ≈ 10^15 lần gọi. Không thực tế dùng với n vừa phải.

4.7 O(n!) — Factorial

Sinh mọi hoán vị:

// O(n!) — generates all n! permutations of the input array
public void permute(int[] arr, int start, List<int[]> result) {
    if (start == arr.length) {
        result.add(arr.clone());
        return;
    }
    for (int i = start; i < arr.length; i++) {
        int tmp = arr[start]; arr[start] = arr[i]; arr[i] = tmp;
        permute(arr, start + 1, result);
        tmp = arr[start]; arr[start] = arr[i]; arr[i] = tmp; // swap back
    }
}

Bảng tăng trưởng

Dấu — nghĩa là con số vượt xa khả năng tính toán thực tế.

5. Cơ chế bên dưới — tại sao hạng bậc cao thống trị

Hãy nhìn ba hàm cùng lúc khi n tăng:

n=1:       f1 = 3n^2 + 100n + 5 =    108
           f2 = 100n              =    100
           f3 = 3n^2              =      3

n=100:     f1 = 3*10000 + 10000 + 5 = 40005
           f2 = 100*100            =  10000
           f3 = 3*100^2            =  30000

n=1000:    f1 = 3*1M + 100K + 5  = 3100005
           f2 = 100*1000         =  100000    <-- 3% of f1
           f3 = 3*1000^2         = 3000000    <-- 97% of f1

Khi n đạt 1.000, hạng 100n chỉ còn 3% tổng — và tỷ lệ này tiếp tục thu nhỏ khi n tăng. Hạng n² "nuốt" hạng n theo tỷ lệ n/1 → tỷ lệ đó tăng vô hạn.

Sơ đồ phân kỳ của ba hàm:

xychart-beta
    title "Tang truong theo n"
    x-axis [1, 10, 50, 100, 200, 500]
    y-axis "So buoc" 0 --> 800000
    line [1, 100, 2500, 10000, 40000, 250000]
    line [1, 10, 50, 100, 200, 500]
    line [0, 33, 282, 664, 1530, 4483]

6. Pitfall tổng hợp

Pitfall 1: O(n) + O(n) = O(2n) — sai.

// Two separate O(n) passes over same array
// Total: O(n) + O(n) = O(n), NOT O(2n)
public void processTwice(int[] arr) {
    for (int x : arr) System.out.println(x);  // O(n)
    for (int x : arr) doSomething(x);         // O(n)
}

Hai vòng lặp tuần tự: O(n) + O(n) = O(2n). Nhưng O(2n) = O(n) vì constant 2 bị bỏ. Tổng là O(n).

✅ Quy tắc: vòng lặp tuần tự thì cộng complexity, nhưng sau đó bỏ constant và hạng thấp.

Pitfall 2: Vòng lặp lồng không phải lúc nào cũng O(n²).

// Outer loop: O(n). Inner loop: O(log n) — binary search.
// Total: O(n log n), NOT O(n^2).
public int[] findTargets(int[] data, int[] queries) {
    int[] result = new int[queries.length];
    Arrays.sort(data); // O(n log n)
    for (int i = 0; i < queries.length; i++) {           // O(n) outer
        result[i] = binarySearch(data, queries[i]);      // O(log n) inner
    }
    return result; // total: O(n log n)
}

✅ Quy tắc: vòng lặp lồng thì nhân complexity — O(n) * O(log n) = O(n log n). Phân tích từng vòng riêng.

Pitfall 3: "Big-O thấp hơn không luôn nhanh hơn ở n nhỏ — constant matter."

Insertion Sort có O(n²) worst case, Merge Sort có O(n log n). Tưởng Merge Sort luôn thắng. Thực tế:

• Insertion Sort có constant rất thấp: ít phép tính, cache-friendly (in-place), không cần allocate bộ nhớ phụ.
• Merge Sort có constant cao hơn: phân bổ mảng phụ, overhead recursive call, copy data.

Với n dưới 32, Insertion Sort nhanh hơn Merge Sort trong thực đo. Đây là lý do TimSort (thuật toán Java, Python dùng) luôn dùng Insertion Sort cho run nhỏ hơn 32 phần tử, Merge Sort cho phần còn lại — kết hợp tốt nhất của hai thế giới.

✅ Quy tắc: Big-O dự đoán tương đối ở n lớn. Với n nhỏ, đo thực tế và xem xét constant.

7. Amortized O(1) và ứng dụng thực tế

Collections.sort() contract rõ ràng trong Javadoc. Javadoc ghi O(n log n) — đó là contract, không chỉ là note. Developer có thể tin rằng sort một million phần tử sẽ mất khoảng 20 * 1.000.000 = 20M đơn vị công việc, không phải 10^12. Complexity là ngôn ngữ để đặt SLA.

HashMap.get() là O(1) amortized — không phải O(1) tuyệt đối. HashMap lưu entry theo hashCode() % capacity. Nếu hash function tốt, mỗi bucket có vài entry — lookup gần như O(1). Nhưng worst case, tất cả n entry hash vào cùng bucket → duyệt linked list dài n → O(n). Java 8 treeify bucket dài trên 8 node thành cây đỏ-đen → worst case O(log n) (Module 3 sẽ phân tích chi tiết). "Amortized O(1)" nghĩa là trung bình qua nhiều lần gọi là O(1), dựa trên giả định hash function phân phối đều.

Database query plan — EXPLAIN cho biết O(n) vs O(log n). Khi thêm WHERE user_id = 123 vào query, có hai kịch bản:

• Không có index: PostgreSQL dùng Seq Scan — quét toàn bộ bảng, O(n). Bảng 10M row → 10M bước.
• Có index B-tree: Index Scan — O(log n). 10M row → khoảng 24 bước.

Chạy EXPLAIN ANALYZE SELECT ... để thấy plan. Đây là debug Big-O trong production thực tế.

Stream.sorted() là O(n log n) — cẩn thận trong hot loop.

// Bad: calling sorted() on an already-sorted list inside a tight loop
// Each call allocates, sorts — O(n log n) per invocation
for (Request req : requests) {
    List<Item> ordered = req.getItems().stream()
        .sorted(Comparator.comparing(Item::getPriority))
        .toList(); // O(n log n) allocation + sort every iteration
    process(ordered);
}

Nếu getItems() đã sorted, gọi sorted() là O(n log n) lãng phí. Kiểm tra trước hoặc giữ items đã sorted từ lúc insert.

8. 📚 Deep Dive tài liệu gốc

9. Tóm tắt

• Big-O đo tốc độ tăng của thời gian chạy theo n — upper bound của growth rate, không phải thời gian tuyệt đối.
• Bỏ constants và hạng bậc thấp vì ở n đủ lớn, hạng bậc cao thống trị toàn bộ — tỷ lệ hạng thấp/hạng cao tiến về 0.
• O (upper bound), Theta (tight bound), Omega (lower bound). Thực tế dùng O vì quan tâm worst case.
• 7 class chuẩn: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!) — khác nhau cơ bản về khả năng scale.
• Vòng lặp tuần tự → cộng complexity rồi bỏ constant. Vòng lặp lồng → nhân complexity.
• Big-O thấp hơn không luôn nhanh hơn ở n nhỏ — TimSort dùng Insertion Sort cho n < 32 vì constant thấp hơn.
• HashMap.get() là O(1) amortized — giả định hash function tốt. Worst case O(log n) sau Java 8 treeify.
• Production: Complexity là contract trong Javadoc, là ngôn ngữ chung để dự đoán scale. Database EXPLAIN cho thấy O(n) vs O(log n) trực tiếp.

10. Tự kiểm tra

for (int i = 0; i < n; i++) {          // outer
  for (int j = 0; j < n; j++) {       // inner-1
      process(arr[i][j]);
  }
}
for (int k = 0; k < n; k++) {           // separate
  log(arr[0][k]);
}

Bài tiếp theo: Recursion và call stack