Độ phức tạp

Trước khi viết code, người làm competitive programming luôn tự hỏi: "Thuật toán này chạy có kịp giới hạn thời gian không?". Phân tích độ phức tạp trả lời câu hỏi đó — ước lượng thời gian chạy và bộ nhớ theo kích thước đầu vào $N$, giúp bạn chọn đúng thuật toán trước khi mất công cài đặt.

Các trang trong mục này

Đọc theo thứ tự sau:

1. Độ phức tạp thời gian (Big-O) — ký hiệu Big-O và cách ước lượng số phép tính khi $N$ tăng. Nền tảng quan trọng nhất.
2. Độ phức tạp không gian — ước lượng bộ nhớ theo $N$, tránh vượt Memory Limit.
3. Ước lượng giới hạn bài toán — nhìn vào ràng buộc ($N\le {10}^5$, $N\le 20$...) để đoán ngay độ phức tạp cần thiết. Kỹ năng "đọc đề ra hướng giải".

Mẹo nhanh

Với giới hạn ~1 giây, máy chấm xử lý được khoảng ${10}^8$ phép tính đơn giản. Đối chiếu con số này với $N$ để loại nhanh các hướng quá chậm — chi tiết trong trang Ước lượng giới hạn bài toán.