Độ phức tạp thuật toán: hiểu nhanh để không bị quá giờ

Độ phức tạp cho biết số phép tính tăng thế nào khi dữ liệu tăng. Đây là công cụ để biết trước bài của em có chạy kịp không.

Các mức hay gặp

• O(n): duyệt một lượt.
• O(n log n): sắp xếp.
• O(n²): hai vòng lặp lồng nhau.
• O(log n): tìm kiếm nhị phân.

Ước lượng nhanh

Quy tắc thực hành: máy chạy được khoảng vài chục triệu đến 10⁸ phép tính đơn giản mỗi giây trong C++, còn Python chậm hơn nhiều.

• n ≤ 1000: O(n²) thường vẫn kịp.
• n ≤ 10⁵: cần O(n log n) hoặc O(n).
• n ≤ 10⁹: cần O(log n), O(√n) hoặc công thức.

Hãy đọc giới hạn trong đề trước khi viết code: nó thường gợi ý luôn thuật toán cần dùng.