# Mở đầu

Bằng cách tính toán độ phức tạp thời gian của một thuật toán, ta có thể dễ dàng kiểm tra xem trước khi triển khai thuật toán xem nó có đủ hiệu quả cho bài toán hay không. Đây cũng là điểm khởi đầu cho việc ước lượng về máy tính hiện đại có thể thực hiện hàng trăm phép tính trong một giây.

Ví dụ, giả sử giới hạn thời gian cho một bài toán là một giây và kích thước đầu vào là $n = 10^5$. Nếu độ phức tạp thời gian của thuật toán là $O(n^2)$, thuật toán sẽ thực hiện khoảng $(10^5)^2 = 10^{10}$ phép tính. Điều này sẽ mất ít nhất vài chục giây, vì vậy thuật toán có vẻ quá chậm để giải quyết bài toán.

Mặt khác, với kích thước đầu vào đã cho trước, ta có thể dự đoán được độ phức tạp về thời gian yêu cầu của thuật toán giải quyết bài toán. Bảng dưới chứa một số ví dụ hữu ích với giới hạn thời gian là một giây.

| Kích thước đầu vào | Độ phức tạp thời gian yêu cầu |
|--------------------|-------------------------------|
| $n \leq 10$ | $O(n!)$ |
| $n \leq 20$ | $O(2^n)$ |
| $n \leq 500$ | $O(n^3)$ $(3FOR)$ |
| $n \leq 5000$ | $O(n^2)$ $(2FOR)$ |
| $n \leq 10^6$ | $O(n\log n)$ hoặc $O(n)$ |
| $n$ lớn | $O(1)$ hoặc $O(\log n)$ |
| | |

* FOR ở đây tức là vòng lặp for ta duyệt từ 1 đến n sẽ tốn 2 hoặc 3 vòng lặp FOR

Ví dụ, nếu kích thước đầu vào là $n = 10^5$, thì ta có thể dự đoán độ phức tạp thời gian của thuật toán là $O(n)$ hoặc $O(n\log n)$. Với thông tin này sẽ giúp ta dễ dàng định hướng được thuật toán sẽ sử dụng, vì cần loại trừ các phương pháp có độ phức tạp thời gian có không tối ưu.

Tuy nhiên, một điều quan trọng ta cần phải nhớ rằng độ phức tạp về thời gian chỉ là ước chừng về hiệu suất, vì nó có thể ẩn đi các hệ số hằng số. Ví dụ, một thuật toán chạy trong thời gian $O(n)$ có thể thực hiện $\frac{n}{2}$ hoặc $5n$ phép tính. Điều này ảnh hưởng quan trọng đến thời gian chạy thực tế của thuật toán.