Big-O qua ví dụ code: Hiểu độ phức tạp thuật toán dễ dàng

1. Tổng quan

Big-O là cách mô tả tốc độ tăng của thời gian chạy (hoặc bộ nhớ) khi kích thước đầu vào tăng lên. Bài này không dùng công thức toán khô khan, mà đi qua từng mức độ phức tạp phổ biến bằng code Java thật, kèm phân tích dòng nào gây ra chi phí. Đọc xong, bạn sẽ nhìn vào một đoạn code và đoán được ngay nó là O(1), O(n), O(n log n) hay O(n²) mà không cần đếm bằng tay.

2. Big-O là gì, tại sao cần quan tâm

Big-O trả lời câu hỏi: “Nếu input tăng gấp đôi, thời gian chạy tăng bao nhiêu?” Nó bỏ qua hằng số và các yếu tố nhỏ, chỉ giữ lại xu hướng tăng trưởng khi n (kích thước input) tiến tới vô cực.

n = 1.000      -> O(n) chạy ~1.000 bước
n = 1.000.000  -> O(n) chạy ~1.000.000 bước (tăng tuyến tính)
n = 1.000.000  -> O(n²) chạy ~10^12 bước (tăng cực nhanh)

Hai đoạn code có thể “nhìn qua thì giống nhau” nhưng độ phức tạp khác hẳn nếu một bên có loop lồng nhau ẩn trong hàm gọi. Hiểu Big-O giúp bạn tránh viết code chạy tốt với 100 bản ghi test nhưng “đứng hình” khi lên production với 10 triệu bản ghi.

Lưu ý: Big-O mô tả trường hợp xấu nhất (worst case) theo quy ước phổ biến nhất, trừ khi nói rõ là best-case hay average-case.

3. O(1) – Thời gian hằng số

Thời gian chạy không đổi, bất kể input lớn cỡ nào.

public class InventoryCache {

    private final Map<String, Integer> stockBySku = new HashMap<>();

    public Integer getStock(String sku) {
        return stockBySku.get(sku); // HashMap.get là O(1) trung bình
    }
}

get() trên HashMap tính hash của key rồi nhảy thẳng tới bucket tương ứng, không phụ thuộc vào số lượng phần tử trong map. Tương tự, truy cập array[i] hay list.get(i) với ArrayList cũng là O(1) vì chỉ cần tính địa chỉ offset.

4. O(n) – Thời gian tuyến tính

Thời gian chạy tăng tỉ lệ thuận với kích thước input.

public class OrderValidator {

    public boolean hasExpiredItem(List<Order> orders) {
        for (Order order : orders) {
            if (order.isExpired()) {
                return true; // dừng sớm nhưng worst-case vẫn duyệt hết
            }
        }
        return false;
    }
}

Vòng for chạy qua tối đa n phần tử của orders. Worst case xảy ra khi không có đơn hàng nào hết hạn, bắt buộc kiểm tra toàn bộ danh sách. Đây là mẫu O(n) kinh điển: một vòng lặp đơn, không lồng nhau.

4.1. Bẫy thường gặp: contains() trong vòng lặp

public class DuplicateChecker {

    // O(n²) do contains() trên List là O(n), lặp n lần
    public boolean hasDuplicateSlow(List<String> emails) {
        List<String> seen = new ArrayList<>();
        for (String email : emails) {
            if (seen.contains(email)) {
                return true;
            }
            seen.add(email);
        }
        return false;
    }
}

seen.contains(email) trên ArrayList là O(n) vì phải duyệt tuyến tính để tìm kiếm. Gọi nó bên trong vòng for biến toàn bộ hàm thành O(n²) — một lỗi rất dễ mắc khi không để ý cấu trúc dữ liệu bên trong.

public class DuplicateChecker {

    // O(n) nhờ HashSet.add/contains là O(1)
    public boolean hasDuplicateFast(List<String> emails) {
        Set<String> seen = new HashSet<>();
        for (String email : emails) {
            if (!seen.add(email)) { // add() trả false nếu đã tồn tại
                return true;
            }
        }
        return false;
    }
}

Chỉ bằng cách đổi List sang HashSet, độ phức tạp giảm từ O(n²) xuống O(n). Đây là ví dụ thực tế nhất cho thấy chọn đúng cấu trúc dữ liệu quan trọng hơn “tối ưu vi mô”.

5. O(log n) – Thời gian logarit

Mỗi bước xử lý loại bỏ một nửa không gian tìm kiếm.

public class PriceLookup {

    // sortedPrices phải được sắp xếp tăng dần trước
    public int findIndex(int[] sortedPrices, int target) {
        int low = 0;
        int high = sortedPrices.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (sortedPrices[mid] == target) {
                return mid;
            } else if (sortedPrices[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

Binary search cắt đôi mảng ở mỗi vòng while, nên với n = 1.000.000 chỉ cần khoảng 20 bước (log₂ 1.000.000 ≈ 20) để tìm ra kết quả, thay vì duyệt tuyến tính cả triệu phần tử.

class PriceLookupTest {

    @Test
    void shouldFindIndexInSortedArray() {
        int[] prices = {10, 20, 30, 40, 50};
        PriceLookup lookup = new PriceLookup();

        int index = lookup.findIndex(prices, 40);

        assertThat(index).isEqualTo(3);
    }

    @Test
    void shouldReturnMinusOneWhenNotFound() {
        PriceLookup lookup = new PriceLookup();

        int index = lookup.findIndex(new int[] {1, 2, 3}, 99);

        assertThat(index).isEqualTo(-1);
    }
}

Test này xác nhận hành vi đúng cả khi tìm thấy (trả về index) và không tìm thấy (trả về -1), hai nhánh quan trọng nhất của binary search.

6. O(n log n) – Kết hợp tuyến tính và logarit

Đây là độ phức tạp của các thuật toán sắp xếp hiệu quả như merge sort, quick sort (average case), hay Collections.sort().

public class RevenueReport {

    public List<Order> sortByAmountDescending(List<Order> orders) {
        List<Order> copy = new ArrayList<>(orders);
        copy.sort(Comparator.comparing(Order::amount).reversed()); // O(n log n)
        return copy;
    }
}

Collections.sort()/List.sort() trong Java dùng Timsort (biến thể của merge sort), đảm bảo O(n log n) ở worst case. Nếu bạn thấy code gọi sort() bên trong một vòng lặp chạy n lần, tổng độ phức tạp sẽ nhân lên thành O(n² log n) — một dấu hiệu cần refactor.

7. O(n²) – Thời gian bậc hai

Hai vòng lặp lồng nhau, mỗi vòng chạy qua toàn bộ (hoặc gần toàn bộ) input.

public class PairFinder {

    // Tìm tất cả cặp sản phẩm có tổng giá bằng target
    public List<int[]> findPairsSlow(int[] prices, int target) {
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[i] + prices[j] == target) {
                    result.add(new int[] {prices[i], prices[j]});
                }
            }
        }
        return result;
    }
}

Vòng ngoài chạy n lần, vòng trong chạy tối đa n lần cho mỗi lần vòng ngoài — tổng số phép so sánh xấp xỉ n²/2, nên độ phức tạp là O(n²). Với n = 10.000, đây là 50 triệu phép so sánh — vẫn chạy được nhưng chậm thấy rõ.

public class PairFinder {

    // O(n) nhờ HashSet lưu giá trị đã thấy
    public List<int[]> findPairsFast(int[] prices, int target) {
        List<int[]> result = new ArrayList<>();
        Set<Integer> seen = new HashSet<>();
        for (int price : prices) {
            int complement = target - price;
            if (seen.contains(complement)) {
                result.add(new int[] {complement, price});
            }
            seen.add(price);
        }
        return result;
    }
}

Thay vì so sánh từng cặp, ta chỉ cần một vòng duy nhất và tra cứu O(1) trong HashSet. Đây là kỹ thuật “đổi thời gian bằng bộ nhớ” rất phổ biến: tốn thêm không gian lưu seen, nhưng giảm độ phức tạp từ O(n²) xuống O(n).

8. O(2^n) – Thời gian theo cấp số nhân

Thời gian chạy tăng gấp đôi mỗi khi input tăng thêm 1 đơn vị — thường gặp ở các hàm đệ quy tính tất cả tổ hợp con.

public class SubsetGenerator {

    public List<List<Integer>> generateAllSubsets(List<Integer> items) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(items, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(List<Integer> items, int index,
                            List<Integer> current, List<List<Integer>> result) {
        if (index == items.size()) {
            result.add(new ArrayList<>(current));
            return;
        }
        // Nhánh 1: không chọn item[index]
        backtrack(items, index + 1, current, result);

        // Nhánh 2: chọn item[index]
        current.add(items.get(index));
        backtrack(items, index + 1, current, result);
        current.remove(current.size() - 1);
    }
}

Mỗi phần tử tạo ra 2 nhánh đệ quy (chọn hoặc không chọn), nên với n phần tử ta có 2^n tập con. Với n = 20, đã là hơn 1 triệu tập con; n = 40 thì không máy nào chạy xong trong thời gian hợp lý. Đây là dấu hiệu cần cân nhắc thuật toán quy hoạch động (dynamic programming) nếu bài toán cho phép.

9. So sánh nhanh bằng benchmark thực tế

Một ví dụ test đơn giản để “nhìn thấy” sự khác biệt giữa O(n) và O(n²):

class DuplicateCheckerBenchmarkTest {

    @Test
    void fastVersionShouldHandleLargeInputQuickly() {
        List<String> emails = new ArrayList<>();
        for (int i = 0; i < 100_000; i++) {
            emails.add("user" + i + "@example.com");
        }
        DuplicateChecker checker = new DuplicateChecker();

        long start = System.nanoTime();
        boolean hasDuplicate = checker.hasDuplicateFast(emails);
        long elapsedMs = (System.nanoTime() - start) / 1_000_000;

        assertThat(hasDuplicate).isFalse();
        assertThat(elapsedMs).isLessThan(500); // O(n) nên vẫn rất nhanh với 100k phần tử
    }
}

Nếu bạn thử đổi hasDuplicateFast thành hasDuplicateSlow với cùng 100.000 email, thời gian chạy sẽ tăng vượt xa ngưỡng 500ms — minh chứng trực quan cho sự khác biệt giữa O(n) và O(n²) trên dữ liệu thực.

10. Bảng tổng hợp và quy tắc nhận diện nhanh

Big-O	Dấu hiệu trong code	Ví dụ
O(1)	Không có loop, truy cập trực tiếp (array index, HashMap.get)	map.get(key)
O(log n)	Mỗi bước loại bỏ một phần không gian tìm kiếm	Binary search
O(n)	Một loop đơn chạy qua input	for qua List
O(n log n)	Loop kết hợp sort, hoặc divide-and-conquer	Collections.sort()
O(n²)	Loop lồng loop, cùng chạy qua input	So sánh từng cặp
O(2^n)	Đệ quy với 2 nhánh tại mỗi bước, không cắt tỉa	Sinh tất cả tập con

Quy tắc đếm nhanh: đếm số loop lồng nhau chạy qua input — mỗi tầng loop thêm một “bậc n”. Nếu trong loop có gọi hàm thư viện (contains, sort, indexOf), hãy tra độ phức tạp của hàm đó trước khi cộng vào tổng.

Lưu ý: Big-O không nói gì về hằng số thực tế. Một thuật toán O(n) với hằng số lớn (ví dụ đọc file mỗi vòng lặp) có thể chậm hơn O(n log n) với hằng số nhỏ khi n chưa đủ lớn. Đừng tối ưu Big-O mù quáng khi chưa đo (profile) thực tế.

11. Kết luận

Big-O là công cụ để dự đoán xu hướng, không phải con số tuyệt đối — nhưng chính xu hướng đó quyết định code của bạn sống sót hay sập khi dữ liệu tăng trưởng. Mẹo thực dụng nhất: mỗi khi viết loop, tự hỏi “bên trong loop này có gọi hàm O(n) nào không?” — đó là nguồn gốc của hầu hết lỗi O(n²) không mong muốn trong thực tế. Nắm vững 6 mức độ phức tạp ở trên là đủ để đọc hiểu và phản biện phần lớn code thuật toán bạn gặp hàng ngày.