Ký hiệu Big O — Giải thích độ phức tạp thời gian đơn giản

Ký hiệu Big O cho biết thời gian chạy hoặc mức dùng bộ nhớ của một thuật toán có thể tăng nhanh thế nào khi kích thước đầu vào tăng lên. Nếu bạn đang hỏi: “Điều gì xảy ra khi bài toán trở nên lớn hơn rất nhiều?”, thì Big O là cách chuẩn để trả lời.

Đó là lý do người ta nói tìm kiếm tuyến tính là $O(n)$ còn tìm kiếm nhị phân là $O(\log n)$. Mục tiêu không phải là dự đoán chính xác số mili giây trên một máy cụ thể. Mục tiêu là so sánh các kiểu tăng trưởng.

Big O có nghĩa là gì

Nếu một thuật toán mất thời gian $T(n)$ trên đầu vào có kích thước $n$, thì

$$T(n) = O(f(n))$$

có nghĩa là tồn tại các hằng số $C > 0$ và $n_0$ sao cho

$$T(n) \le C f(n) \quad \text{for all } n \ge n_0$$

Điều này nói rằng Big O là một phát biểu về cận trên của tốc độ tăng khi đầu vào đủ lớn.

Nói đơn giản: khi $n$ đủ lớn, thời gian chạy không tăng nhanh hơn một bội số hằng của $f(n)$.

Vì sao Big O hữu ích

Big O cung cấp một cách độc lập với máy tính để so sánh các thuật toán. Một chương trình có thể chạy nhanh hơn trên laptop này so với laptop khác, nhưng xu hướng tăng trưởng vẫn là điều quan trọng.

Xu hướng đó đặc biệt quan trọng khi kích thước đầu vào thay đổi nhiều. Một thuật toán ổn với $100$ phần tử có thể trở nên không thực tế với $10^6$ phần tử nếu tốc độ tăng của nó kém.

Các độ phức tạp thời gian thường gặp

• $O(1)$: lượng công việc vẫn bị chặn khi $n$ tăng.
• $O(\log n)$: lượng công việc tăng chậm, thường khi kích thước bài toán liên tục bị giảm xuống.
• $O(n)$: lượng công việc tăng gần như tỉ lệ với kích thước đầu vào.
• $O(n \log n)$: lớn hơn tuyến tính một chút, thường gặp trong các thuật toán sắp xếp hiệu quả.
• $O(n^2)$: lượng công việc tăng như bình phương của kích thước đầu vào, thường do các vòng lặp lồng nhau trên cùng một dữ liệu.

Các nhãn này dùng để so sánh tốc độ tăng, không phải tốc độ chính xác. Một thuật toán $O(n)$ vẫn có thể chậm hơn thuật toán $O(n^2)$ với đầu vào nhỏ nếu các hệ số hằng của nó lớn.

Ví dụ minh họa: Vì sao tìm kiếm tuyến tính là $O(n)$

Giả sử bạn duyệt một danh sách từ trái sang phải để tìm một giá trị đích. Trong trường hợp xấu nhất, giá trị đó không có trong danh sách hoặc nằm ở cuối cùng, nên bạn có thể phải kiểm tra từng phần tử đúng một lần.

Nếu danh sách có $n$ phần tử, số lần kiểm tra nhiều nhất là $n$. Đó là lý do thời gian chạy trong trường hợp xấu nhất là

$$O(n)$$

Điểm rút ra hữu ích rất đơn giản: nếu kích thước danh sách tăng gấp đôi, thì số lần kiểm tra trong trường hợp xấu nhất cũng có thể tăng gần gấp đôi. Đó chính là kiểu mẫu mà Big O đang mô tả.

Big O bỏ qua điều gì

Big O cố ý bỏ qua các hệ số hằng và các hạng bậc thấp hơn khi so sánh tốc độ tăng với đầu vào lớn.

Ví dụ, nếu

$$T(n) = 3n + 2$$

thì $T(n)$ vẫn là $O(n)$. Hằng số $3$ và số cộng thêm $2$ có ý nghĩa với thời gian chạy chính xác, nhưng chúng không làm thay đổi kiểu tăng trưởng chính.

Điều đó không có nghĩa là các hằng số không bao giờ quan trọng trong thực tế. Nó chỉ có nghĩa là Big O trả lời một câu hỏi hẹp hơn: chi phí tăng theo cách nào khi $n$ trở nên lớn.

Những lỗi thường gặp về Big O

Lỗi 1: Xem Big O như thời gian chạy chính xác

$O(n)$ không có nghĩa là thời gian chạy chính xác bằng $n$ bước. Nó có nghĩa là tốc độ tăng bị chặn trên bởi một bội số hằng của $n$ khi $n$ đủ lớn.

Lỗi 2: Quên điều kiện $n$ lớn

Định nghĩa hình thức chỉ cần đúng với mọi $n \ge n_0$. Big O nói về hành vi tiệm cận, không phải mọi đầu vào rất nhỏ.

Lỗi 3: Cho rằng Big O luôn có nghĩa là thời gian chạy điển hình

Trong thảo luận về thuật toán, Big O thường mô tả thời gian chạy trong trường hợp xấu nhất, nhưng đó là một quy ước phụ thuộc vào ngữ cảnh. Độ phức tạp trung bình và tốt nhất là những câu hỏi khác và cần được ghi rõ.

Lỗi 4: Chỉ so sánh thuật toán bằng Big O

Big O rất quan trọng, nhưng mức dùng bộ nhớ, chi phí triển khai và các hệ số hằng vẫn có thể ảnh hưởng rất nhiều trong các hệ thống thực tế.

Bạn sẽ gặp ký hiệu Big O ở đâu

Big O xuất hiện trong khoa học máy tính, toán rời rạc và phân tích hiệu năng. Nó đặc biệt hữu ích khi so sánh các thuật toán tìm kiếm, sắp xếp, duyệt đồ thị và quy hoạch động.

Rộng hơn, nó được dùng bất cứ khi nào bạn quan tâm đến cách một quá trình mở rộng theo kích thước, thay vì chỉ cách nó hoạt động ở một kích thước cố định.

Hãy thử một ví dụ tương tự

Hãy lấy một vòng lặp lồng nhau đơn giản chạy qua một lưới $n \times n$. Đếm xem hành động bên trong chạy bao nhiêu lần. Nếu tổng lượng công việc tăng như $n^2$, bạn sẽ có một ví dụ cụ thể cho thấy vì sao các vòng lặp lặp lại trên cùng một dữ liệu thường dẫn đến hành vi $O(n^2)$.