Trong lập trình thi đấu và khoa học máy tính, độ phức tạp của thuật toán là một khái niệm cực kỳ quan trọng giúp chúng ta đánh giá hiệu suất của một thuật toán dựa trên hai yếu tố chính:
- Thời gian thực thi (Time Complexity): Thuật toán mất bao lâu để hoàn thành khi kích thước dữ liệu đầu vào (~N~) thay đổi.
- Không gian bộ nhớ (Space Complexity): Thuật toán tiêu tốn bao nhiêu tài nguyên bộ nhớ (RAM) khi chạy.
Để biểu diễn độ phức tạp, người ta thường dùng ký hiệu Big O (~O~) nhằm mô tả trường hợp xấu nhất (worst-case scenario).
1. Độ phức tạp thời gian thường gặp (Time Complexity)
Dưới đây là các độ phức tạp phổ biến từ tốt nhất đến kém nhất:
- ~O(1)~ - Độ phức tạp hằng số: Thời gian chạy không phụ thuộc vào kích thước dữ liệu ~N~.
- Ví dụ: Truy xuất một phần tử trong mảng bằng chỉ số
A[i].
- Ví dụ: Truy xuất một phần tử trong mảng bằng chỉ số
- ~O(\log N)~ - Độ phức tạp logarit: Thường gặp trong các thuật toán chia để trị. Thuật toán loại bỏ một nửa dữ liệu ở mỗi bước.
- Ví dụ: Tìm kiếm nhị phân (Binary Search).
- ~O(N)~ - Độ phức tạp tuyến tính: Thời gian chạy tỷ lệ thuận với kích thước dữ liệu ~N~.
- Ví dụ: Duyệt qua một mảng để tìm giá trị lớn nhất.
- ~O(N \log N)~: Thường thấy trong các thuật toán sắp xếp tối ưu.
- Ví dụ: Merge Sort, Quick Sort, Heap Sort.
- ~O(N^2)~ - Độ phức tạp bình phương: Thường xuất hiện khi có 2 vòng lặp lồng nhau duyệt qua ~N~ phần tử.
- Ví dụ: Sắp xếp nổi bọt (Bubble Sort), Insertion Sort.
- ~O(2^N)~ - Độ phức tạp lũy thừa: Thường gặp trong các bài toán sinh tổ hợp, quay lui (Backtracking). Rất chậm, chỉ giải quyết được ~N~ nhỏ (thường ~N \le 20~).
- ~O(N!)~ - Độ phức tạp giai thừa: Thuật toán duyệt mọi hoán vị của ~N~ phần tử. Chỉ chạy được với ~N \le 10~.
2. Cách ước lượng giới hạn thời gian (Time Limit)
Trong các kỳ thi lập trình (như kỳ thi HSG, chuyên Tin, Codeforces,...), máy chấm (Judge) thường có thể thực hiện khoảng ~10^8~ phép toán cơ bản trong 1 giây. Dựa vào giới hạn này và kích thước dữ liệu bài cho (~N~), bạn có thể thiết kế thuật toán phù hợp để tránh bị Time Limit Exceeded (TLE).
| Kích thước dữ liệu (~N~) | Độ phức tạp tối đa cho phép (thời gian 1s) |
|---|---|
| ~N \le 10~ | ~O(N!)~ |
| ~N \le 20~ | ~O(2^N)~ |
| ~N \le 500~ | ~O(N^3)~ |
| ~N \le 5 \times 10^3~ | ~O(N^2)~ |
| ~N \le 10^5 \to 5 \times 10^5~ | ~O(N \log N)~ |
| ~N \le 10^7~ | ~O(N)~ |
| Kích thước rất lớn | ~O(1)~ hoặc ~O(\log N)~ |
Lời khuyên
Khi giải quyết các bài toán trên hệ thống CT1OJ:: THPT Châu Thành 1 Online Judge!, việc phân tích độ phức tạp thuật toán ngay từ khâu đọc đề là bước không thể thiếu để tránh lãng phí thời gian viết code rồi mới nhận ra thuật toán bị quá thời gian.
Chúc các em học sinh luyện tập thật tốt và đạt được nhiều Accepted!
Bình luận
Đây là dòng bình luận mẫu đầu tiên!