Độ phức tạp thuật toán
Tổng quan
Độ phức tạp thuật toán (Time Complexity) đo lường thời gian thực thi của một thuật toán tương quan với kích thước đầu vào. Đây là yếu tố quan trọng để đánh giá hiệu suất và lựa chọn thuật toán phù hợp.
So sánh hiệu suất
Bảng so sánh với n = 1000
| Độ phức tạp |
Số phép toán |
Thời gian ước tính |
| O(1) |
1 |
Tức thì |
| O(log n) |
~10 |
Tức thì |
| O(n) |
1,000 |
< 1ms |
| O(n log n) |
~10,000 |
~1ms |
| O(n²) |
1,000,000 |
~1 giây |
| O(2ⁿ) |
2¹⁰⁰⁰ |
Hàng tỷ năm! |
Bảng đánh giá tổng quát
| Độ phức tạp |
Đánh giá |
Mô tả hiệu suất |
| O(1) |
😎 Xuất sắc |
Tốc độ không phụ thuộc kích thước dữ liệu |
| O(log n) |
😁 Rất tốt |
Dữ liệu tăng x10 → thời gian chỉ tăng x2 |
| O(n) |
😕 Chấp nhận được |
Dữ liệu tăng x10 → thời gian tăng x10 |
| O(n log n) |
😖 Tạm được |
Dữ liệu tăng x10 → thời gian tăng x20 |
| O(n²) |
😫 Chậm |
Dữ liệu tăng x10 → thời gian tăng x100 |
| O(2ⁿ) |
😱 Thảm họa |
Dữ liệu tăng +1 → thời gian tăng x2 |
Lời khuyên thực tế
Khi nào dùng thuật toán nào?
- O(1), O(log n): Luôn ưu tiên khi có thể
- O(n): Phù hợp cho hầu hết trường hợp thông thường
- O(n log n): Tốt cho sắp xếp và tìm kiếm dữ liệu lớn
- O(n²): Chỉ dùng cho dữ liệu nhỏ (< 1000 phần tử)
- O(2ⁿ): Tránh hoàn toàn, trừ khi n < 20
Nguyên tắc vàng
- Hiểu rõ độ phức tạp của code bạn viết
- Tối ưu hóa những đoạn code chạy nhiều lần nhất
- Đo lường thực tế thay vì chỉ dựa vào lý thuyết
- Cân bằng giữa hiệu suất và độ phức tạp code