Big-O & độ phức tạp: vì sao API đơn hàng chậm dần

Cần, vì Big-O là thứ giải thích được câu "dev chạy nhanh, lên production chậm". shop-backend lúc mới có 100 đơn, giờ có 1 triệu đơn: code y hệt, nhưng có endpoint từ 20ms thành 30 giây.

1. Bài toán

Endpoint GET /orders/report: với mỗi đơn, tìm thông tin khách hàng trong List<Customer>.

for (Order o : orders) {                       // n đơn
    Customer c = customers.stream()            // m khách, quét từ đầu
            .filter(x -> x.id().equals(o.customerId()))
            .findFirst().orElseThrow();
    rows.add(new ReportRow(o.id(), c.name(), o.total()));
}

2. Vấn đề

• Mỗi đơn quét cả list khách: n × m phép so sánh. 100 × 50 = 5.000, không ai để ý. 1.000.000 × 100.000 = 10¹¹: treo.
• Big-O không đo thời gian chính xác. Nó đo tốc độ tăng của số bước khi n tăng. Đó là thứ quyết định code có "scale" không.

3. Giải pháp: các bậc độ phức tạp hay gặp

Quy tắc rút gọn: bỏ hằng số và bậc thấp. 3n + 100 là O(n); n² + n là O(n²).

4. Code từng bước: từ O(n·m) xuống O(n + m)

Bước 1: đổi list thành map một lần, O(m)

Map<String, Customer> byId = customers.stream()
        .collect(Collectors.toMap(Customer::id, Function.identity()));

Bước 2: tra cứu O(1) trong vòng lặp, tổng O(n)

for (Order o : orders) {
    Customer c = byId.get(o.customerId());     // O(1) trung bình
    rows.add(new ReportRow(o.id(), c.name(), o.total()));
}

Bước 3: N+1 query cũng là cùng một bệnh

// Tệ: 1 query lấy đơn + n query lấy khách
orders.forEach(o -> customerRepo.findById(o.customerId()));

// Tốt: 1 query lấy đơn + 1 query lấy tất cả khách cần thiết
Set<String> ids = orders.stream().map(Order::customerId).collect(Collectors.toSet());
Map<String, Customer> byId = customerRepo.findAllById(ids).stream()
        .collect(Collectors.toMap(Customer::id, Function.identity()));

Bước 4: đo lại

curl -w "%{time_total}s\n" -o /dev/null http://localhost:8080/orders/report

5. Cách hoạt động: số bước tăng thế nào

n          O(log n)   O(n)        O(n log n)     O(n²)
10         3          10          33             100
1.000      10         1.000       10.000         1.000.000
1.000.000  20         1.000.000   20.000.000     1.000.000.000.000

Binary search trên 1 triệu đơn đã sort theo id:
 1.000.000 → 500.000 → 250.000 → ... → 1      (~20 bước)

6. So sánh: chi phí thao tác của Java collection

7. Khi nào nên quan tâm / không nên

• Quan tâm: dữ liệu lớn hoặc tăng theo thời gian (đơn hàng, log), vòng lặp lồng, gọi DB/HTTP trong vòng lặp.
• Không cần tối ưu: list cố định vài chục phần tử (danh sách tỉnh, trạng thái). O(n) với n = 20 là không đáng kể; code dễ đọc quan trọng hơn.
• Big-O bỏ qua hằng số: I/O 1 lần mất 5ms "đắt" hơn hàng nghìn phép so sánh trong RAM.

Đúng rồi. Đó là space complexity: bộ nhớ thêm mà thuật toán cần, ngoài dữ liệu đầu vào.

Tính tổng tiền đơn          → 1 biến sum            → O(1) space
Build Map<id, Customer>     → m entry               → O(m) space
Merge sort                  → mảng phụ khi merge    → O(n) space
Đệ quy sâu d tầng            → d stack frame         → O(d) space

Ví dụ trên là trade-off kinh điển: đổi bộ nhớ lấy thời gian. Thêm O(m) RAM để từ O(n·m) xuống O(n + m). Với 100.000 khách, map tốn vài chục MB: hoàn toàn đáng. Nhưng nếu là 50 triệu bản ghi, đừng load hết vào heap; để DB JOIN hoặc xử lý theo batch.

Bạn hiểu đúng một nửa: lần add làm tràn đúng là O(n). Nhưng nó hiếm, nên tính trung bình trên chuỗi nhiều lần add thì mỗi lần chỉ tốn O(1). Đó là amortized (khấu hao).

capacity: 10 → 15 → 22 → 33 ... (tăng ~1.5 lần)

add 1..10     : mỗi lần O(1)
add 11        : copy 10 phần tử + add   ← đắt
add 12..15    : O(1)
add 16        : copy 15                 ← đắt
...
Tổng chi phí copy ≈ n + n/1.5 + n/1.5² + ... ≈ 3n  →  chia cho n lần add = O(1)

Mẹo thực tế: biết trước kích thước thì new ArrayList<>(orders.size()) để không resize lần nào. HashMap cũng tương tự (rehash khi vượt load factor 0.75).

Cũng nên phân biệt 3 trường hợp:

Cách ước lượng nhanh trong 4 bước:

1. n là gì?            số đơn, số khách, độ dài chuỗi...
2. Đếm vòng lặp:       1 vòng → O(n); lồng 2 vòng → O(n²); n và m khác nhau → O(n·m)
3. Chia đôi mỗi bước?  → có log n
4. Gọi hàm trong vòng: nhân chi phí của hàm (list.contains trong for = O(n²) ẩn!)
   Bỏ hằng số, giữ bậc lớn nhất.

Câu 1: Big-O là gì? Vì sao backend developer cần quan tâm?

🇻🇳 Tiếng Việt:

Big-O mô tả số bước hoặc bộ nhớ tăng thế nào khi kích thước input tăng, bỏ qua hằng số. Nó không đo thời gian chính xác, mà cho biết code có scale được không. Ví dụ trong dự án, báo cáo đơn hàng dùng vòng lặp lồng để tìm khách là O(n·m), chạy ổn với dữ liệu test nhưng chậm khi có một triệu đơn. Em đổi danh sách khách thành HashMap để tra cứu O(1), tổng còn O(n + m). Lỗi N+1 query cũng là cùng loại vấn đề.

🇬🇧 English:

Big-O describes how the number of steps or memory grows as input size grows, ignoring constants. It doesn't measure exact time; it tells you whether code scales. For example, an order report that used a nested loop to find each customer was O(n·m): fine with test data, slow with a million orders. I turned the customer list into a HashMap for O(1) lookups, making it O(n + m). The N+1 query problem is the same kind of issue.

Câu 2: Độ phức tạp của HashMap, ArrayList, TreeMap?

🇻🇳 Tiếng Việt:

HashMap get/put trung bình O(1), worst case O(log n) từ Java 8 vì bucket nhiều phần tử chuyển thành cây đỏ đen. ArrayList get theo index O(1), add cuối O(1) amortized, chèn/xóa giữa và contains O(n). TreeMap mọi thao tác O(log n) nhưng giữ key có thứ tự.

🇬🇧 English:

HashMap get and put are O(1) on average, and O(log n) worst case since Java 8 because crowded buckets become red-black trees. ArrayList get by index is O(1), appending is amortized O(1), inserting or removing in the middle and contains are O(n). TreeMap operations are O(log n) but keep keys sorted.

Câu 3: Amortized O(1) là gì?

🇻🇳 Tiếng Việt:

Là chi phí trung bình trên một chuỗi thao tác. ArrayList thỉnh thoảng phải copy sang mảng lớn hơn khoảng 1.5 lần, lần đó O(n), nhưng vì hiếm nên chia đều ra mỗi lần add vẫn O(1). Biết trước kích thước thì nên khởi tạo capacity để tránh resize.

🇬🇧 English:

It's the average cost per operation over a sequence of operations. ArrayList occasionally copies into an array about 1.5 times larger, which is O(n), but it happens rarely, so spread across all adds each one is still O(1). If I know the size up front, I set the initial capacity to avoid resizing.

Câu 4: Time và space complexity có đánh đổi không?

🇻🇳 Tiếng Việt:

Có, thường đổi bộ nhớ lấy tốc độ: cache, index, HashMap tra cứu. Merge sort nhanh ổn định O(n log n) nhưng tốn O(n) bộ nhớ phụ. Em chọn dựa trên kích thước dữ liệu: vài trăm nghìn bản ghi thì build map trong RAM được, còn hàng chục triệu thì để DB join hoặc xử lý theo batch.

🇬🇧 English:

Yes, usually we trade memory for speed: caches, indexes, HashMap lookups. Merge sort is a stable O(n log n) but needs O(n) extra space. I decide based on data size: a few hundred thousand records can go into an in-memory map, but tens of millions should be joined in the database or processed in batches.

Cách nhớ ngắn gọn

• 1 → log n → n → n log n → n²: HashMap, binary search, quét list, sort, vòng lồng.
• Vòng lặp lồng hoặc gọi DB trong vòng lặp = nghi ngay O(n²) / N+1.
• List → Map: đổi O(n) RAM lấy tra cứu O(1).
• Amortized: thỉnh thoảng đắt, trung bình rẻ (ArrayList.add).
• Big-O bỏ hằng số; một lần I/O có thể đắt hơn cả nghìn phép tính.