1. Độ phức tạp thời gian của thuật toán
- Trong các cuộc thi lập trình, chương trình của bạn cần chạy xong trong một khung thời gian nhất định. Với quy ước hiện nay mỗi giây máy tính có thể tính được $10^8 - 5 \cdot 10^8$ phép tính. Vì vậy việc tối ưu phép tính trong việc giải các bài toán rất quan trọng trong lập trình thi đấu.
- Độ phức tạp thời gian là một khái niệm trong khoa học máy tính, là kết quả ước lượng thời gian thực hiện các chương trình cài đặt thuật toán để xử lí một lượng dữ liệu đầu vào có độ lớn $n$. Ước lượng này thể hiện số phép toán cần thiết để thực hiện thuật toán khi đã biết dữ liệu đầu vào có kích thước $n$.
2. Kí pháp $\mathcal O$ và các bậc độ phức tạp thời gian
Khái niệm
Để tính độ phức tạp thời gian tính toán, ta có thể sử dụng kí pháp $\mathcal O$, dùng để biểu thị độ phức tạp thời gian trong trường hợp xấu nhất dưới dạng một hàm của $n$.
Độ phức tạp thời gian thuật toán Tên gọi độ phức tạp thời gian thuật toán $\mathcal O(1)$ Hằng số $\mathcal O(\log n)$ Logarit $\mathcal O(n)$ Tuyến tính (linear) $\mathcal O(n^2)$ Bậc hai (quadratic) $\mathcal O(C^n)$ Hàm mũ (exponential) $\mathcal O(n!)$ Giai thừa Một số quy ước về cách tính độ phức tạp thời gian thực hiện thuật toán:
- Thuật toán có độ phức tạp thời gian hằng số khi mà số phép toán cần thực hiện không phụ thuộc kích thước $n$ của dữ liệu đầu vào bài toán.
- Thuật toán có độ phức tạp thời gian tuyến tính khi mà số phép toán cần thực hiện là hàm tuyến tính của kích thước $n$ của dữ liệu đầu vào bài toán.
- Độ phức tạp thời gian của vòng lặp là số lần lặp của vòng lặp. Độ phức tạp tính toán của nhiều vòng lặp lồng nhau được tính bằng cách nhân các độ phức tạp tính toán của mỗi vòng lặp với nhau.
- Nếu thuật toán có nhiều đoạn rời nhau thì độ phức tạp thời gian sẽ là độ phức tạp cao nhất trong các đoạn.
Một số ví dụ về độ phức tạp thời gian:
- Các công thức toán học chỉ các biến: $\mathcal O(1)$
- Đọc đầu vào mảng gồm phần tử: $\mathcal O(n)$
- Duyệt qua một mảng gồm phần tử: $\mathcal O(n)$
- Các thuật toán tìm kiếm nhị phân: $\mathcal O(\log n)$ ...
Một số công thức liên quan:
- Đối với hai cấu trúc điều khiển được thực hiện tuần tự (hai đoạn code rời nhau):
$$ \begin{cases} f_1(n) = \mathcal O(g_1(n))\\ f_2(n) = \mathcal O(g_2(n)) \end{cases} \Rightarrow f_1(n) + f_2(n) = \mathcal O(\max(g_1(n), g_2(n))) $$
- Đối với hai cấu trúc điều khiển lồng nhau (hai đoạn code lồng nhau):
$$ \begin{cases} f_1(n) = \mathcal O(g_1(n))\\ f_2(n) = \mathcal O(g_2(n)) \end{cases} \Rightarrow f_1(n) \times f_2(n) = \mathcal O(g_1(n) \times g_2(n)) $$
Ví dụ
Độ phức tạp thời gian hằng số
int a = 5;
int b = 6;
int c = 7;
int d = a + b + c + 8;
Độ phức tạp thuật toán của đoạn code trên là $\mathcal O(1)$ vì số lượng phép tính là hằng số, không phụ thuộc vào dữ liệu đầu vào.
Độ phức tạp thời gian tuyến tính
for (int i = 0; i <= n; ++i){
// tính toán trong một phép tính O(1)
}
Độ phức tạp thuật toán của đoạn code trên là $\mathcal O(n)$ do vòng lặp thực hiện $n$ lần.
Độ phức tạp thời gian vòng lặp
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= m; ++j){
// tính toán trong một phép tính O(1)
}
Trong ví dụ này độ phức tạp tính toán là $\mathcal O(n \cdot m)$ bởi vì độ phức tạp tính toán của vòng lặp ngoài là $\mathcal O(n)$ và vòng lặp trong là $\mathcal O(m)$, vậy nên $\mathcal O(n) \cdot \mathcal O(m) = \mathcal O(n \cdot m)$.
Độ phức tạp thuật toán của các đoạn rời nhau
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j){
// tính toán trong một phép tính O(1)
}
for (int i = 0; i <= n; ++i){
// tính toán trong một phép tính O(1)
}
Trong trường hợp này, độ phức tạp sẽ là $\mathcal O(n^2)$, bởi đoạn code trên có độ phức tạp là $\mathcal O(n^2)$, còn đoạn dưới có độ phức tạp nhỏ hơn, $\mathcal O(n)$.
3. Một số độ phức tạp và giới hạn phổ biến
| Giới hạn $n$ | Độ phức tạp thường dùng |
|---|---|
| $n \leq 10$ | $\mathcal O(n^7)$, $\mathcal O(n^6)$, $\mathcal O(n!)$ |
| $n \leq 20$ | $\mathcal O(n^5)$, $\mathcal O(2^n \times n)$ |
| $n \leq 80$ | $\mathcal O(n^4)$ |
| $n \leq 400$ | $\mathcal O(n^3)$ |
| $n \leq 7500$ | $\mathcal O(n^2)$ |
| $n \leq 7 \cdot 10^4$ | $\mathcal O(n \sqrt n)$ |
| $n \leq 10^5$ | $\mathcal O(n \log_2n)$ |
| $n \leq 5 \cdot 10^5$ | $\mathcal O(n \log n)$ |
| $n \leq 5 \cdot 10^6$ | $\mathcal O(n)$ |
| $n \leq 10^{18}$ | $\mathcal O(\log_2 n)$, $\mathcal O(\log n)$, $\mathcal O(1)$ |
Bình luận