Họ đang đo gì
Bạn hiểu Big-O như một công cụ suy luận hay như một nghi thức phải đọc thuộc.
Trả lời ngắn~30 giây
Big-O mô tả chi phí tăng thế nào khi đầu vào lớn dần, bỏ qua hằng số và các số hạng bậc thấp. Nên không, O(1) không luôn nhanh hơn: một thao tác O(1) với hằng số lớn — băm một chuỗi dài, đi qua nhiều tầng gián tiếp — có thể chậm hơn việc quét tuyến tính 20 phần tử nằm liền nhau trong bộ nhớ. Big-O trả lời câu hỏi “điều gì xảy ra khi n gấp mười lần”, không trả lời “cái nào nhanh hơn ngay bây giờ”.
Giải thích sâu
Chi tiết hay bị bỏ trong thực tế là vị trí bộ nhớ. Duyệt một mảng nhanh hơn nhiều so với duyệt danh sách liên kết cùng độ dài, dù cả hai đều O(n), vì mảng nằm liền nhau nên CPU đọc trước được cả dòng cache còn danh sách liên kết thì mỗi bước là một lần nhảy ngẫu nhiên. Chênh lệch có thể tới hàng chục lần — lớn hơn nhiều so với khác biệt giữa hai độ phức tạp gần nhau.
Cũng nên phân biệt trường hợp trung bình, xấu nhất và phân bổ. HashMap là O(1) trung bình nhưng O(n) xấu nhất khi mọi khoá va chạm. ArrayList.add là O(1) phân bổ: hầu hết lần thêm là hằng số, thỉnh thoảng có một lần O(n) để nhân đôi mảng, và chia đều ra thì vẫn là hằng số. Trong hệ thống có yêu cầu độ trễ chặt, cái “thỉnh thoảng” đó chính là p99 của bạn.
Câu hỏi tiếp theo họ sẽ hỏi
?Độ phức tạp không gian tính thế nào?
Bộ nhớ PHỤ mà thuật toán cấp phát, không tính đầu vào. Nên sắp xếp tại chỗ là O(1) không gian dù mảng có lớn thế nào. Với đệ quy nhớ tính cả ngăn xếp lời gọi — đó là O(depth), và nó là lý do đệ quy sâu gây StackOverflowError.
Trả lời thế này là mất điểm
- Nói “O(n log n) luôn tốt hơn O(n²)”. Với n = 10 thì thường không, và rất nhiều thư viện chuyển sang insertion sort cho mảng nhỏ vì lý do đó.
Xem thêm trên site
Nguồn
- Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, ch. 3