Big-O mô tả xu hướng của một thuật toán khi dữ liệu lớn dần tới vô cùng. Vấn đề là dữ liệu thực của bạn gần như không bao giờ ở gần vô cùng — nó thường nhỏ hơn nhiều so với bạn tưởng. Và đó là nguồn gốc của một loạt quyết định kỹ thuật sai được biện minh bằng một ký hiệu đúng.
Big-O cố tình bỏ qua điều gì
Ký hiệu này được thiết kế để loại bỏ hằng số và các bậc thấp hơn — đó là điểm mạnh của nó khi so sánh xu hướng, nhưng cũng là điểm mù. Một thuật toán chạy 100n bước và một thuật toán chạy n bước đều là O(n), dù cái đầu chậm gấp một trăm lần ở mọi kích thước dữ liệu. Big-O nói chúng "cùng hạng"; đồng hồ nói khác.
Ví dụ kinh điển: sắp xếp mảng nhỏ
Sắp xếp chèn là O(n²), sắp xếp trộn là O(n log n) — theo lý thuyết, sắp xếp trộn thắng. Vậy mà gần như mọi thư viện chuẩn đều chuyển sang sắp xếp chèn khi mảng còn dưới vài chục phần tử. Lý do nằm hết ở phần Big-O bỏ qua:
- Sắp xếp chèn duyệt tuần tự nên bộ đệm CPU đoán trước được, gần như không bao giờ trượt.
- Nó không cần cấp phát bộ nhớ phụ, trong khi sắp xếp trộn phải cấp mảng tạm.
- Vòng lặp trong cực kỳ đơn giản, ít lệnh rẽ nhánh nên CPU chạy trơn.
Với n = 20, hằng số nhỏ của sắp xếp chèn thắng đứt bậc tăng trưởng tốt hơn của sắp xếp trộn. Bậc chỉ thắng khi n đủ lớn để bù cho hằng số — và "đủ lớn" thường lớn hơn dữ liệu thực của bạn.
Vì sao bộ nhớ giờ đắt hơn phép tính
Đây là sự thật đã đảo ngược trực giác của cả một thế hệ lập trình viên. Một phép cộng tốn chưa tới một phần tỉ giây. Một lần đọc trượt bộ đệm, phải ra tận RAM, tốn khoảng một trăm phần tỉ giây. Nghĩa là một lần trượt bộ đệm đắt bằng cả trăm phép tính.
Hệ quả thực tế: duyệt một mảng liên tục thường nhanh hơn nhiều so với duyệt một danh sách liên kết, dù cả hai đều là O(n) và làm cùng số thao tác logic. Mảng nằm liền nhau trong bộ nhớ nên khi CPU đọc một phần tử, nó nạp sẵn luôn vài phần tử kế tiếp — lần truy cập sau gần như miễn phí. Danh sách liên kết thì mỗi nút nằm một nơi ngẫu nhiên, nên gần như mỗi bước là một lần trượt bộ đệm. Big-O không thấy sự khác biệt này; phần cứng thì thấy rất rõ.
Cách dùng Big-O cho đúng
- Dùng nó để loại bỏ thiết kế tệ ngay từ đầu: O(n²) trên một triệu phần tử là không cần bàn cãi, phải bỏ.
- Đừng dùng nó để chọn giữa hai phương án cùng bậc — ở đó Big-O im lặng, và câu trả lời chỉ có được bằng cách đo trên dữ liệu thật, phần cứng thật.
- Luôn hỏi: dữ liệu thực lớn cỡ nào? Câu trả lời thường nhỏ hơn bạn tưởng, và ở kích thước nhỏ thì hằng số — thứ Big-O vứt đi — mới là thứ quyết định.
Big-O là một công cụ sàng lọc thô tuyệt vời và một công cụ tinh chỉnh tồi. Biết nó dùng để làm gì cũng quan trọng như biết nó nói gì.
Thảo luận