Người viết:
Reviewer:
Thông thường khi viết một thuật toán, ta thường quan tâm nó chạy nhanh hay chậm, tốn nhiều bộ nhớ hay không.
Để ước lượng thời gian chạy của một thuật toán dựa trên kích thước đầu vào, chúng ta sử dụng khái niệm: Độ phức tạp thời gian của thuật toán.
Độ phức tạp thời gian là một hàm $f$ đo số thao tác cơ bản mà một thuật toán thực thi, với tham biến $n$ là kích thước đầu vào: $y = f(n)$
Trên thực tế, đa phần các thuật toán sẽ được đánh giá theo trường hợp xấu nhất (worst case) vì sự đơn giản và thực tế của nó.
Một số khác vẫn được đánh theo trường hợp trung bình (average case). Ví dụ như khi:
Trong từng trường hợp khác nhau của dữ liệu vào, việc tính toán chính xác hàm $f(n)$ (với $x$ tổng quát) thường rất khó. Và ở đây, chúng ta sử dụng độ phức tạp BigO hay O-lớn thay thế.
Xét 2 hàm số dương $f(n)$ và $g(n)$ Ta ký hiệu: $f(n) = O(g(n))$
Theo định nghĩa giải tích, ký hiệu trên tương đương với: $\lim\limits_{n \rightarrow \infty} \sup\dfrac{f(n)}{g(n)} < \infty$ Gọi là "hàm $f$ không tăng (tiệm cận) nhanh hơn $g$".
Nói một cách dễ hiểu: $f(n) = O(g(n))$ thì tồn tại hằng số $c > 0$ để khi $n$ đủ to $($với mọi $n \ge n_0$ nào đó$)$ thì $f(n) \le c\times g(n)$.
Ví dụ:
S1, S2, ..., Sm
và ĐPT tương ứng của chúng là $O(f_1), O(f_2), \ldots, O(f_m)$ với $f_i$ là các hàm của dữ liệu đầu vào.
$E$ là một biểu thức logic.
S1; S2; ...; Sm;
có ĐPT $O(f_1+f_2+ \ldots+f_m)$if E then S1 else S2
có ĐPT $O\left(\max(f_1,f_2)\right)$while E do S1
do S1 while E
for i := E1 to E2 do S1
Tính ĐPT sẽ tương tự chuỗi các lệnh liên tiếp. Giả sử $S_1$ được lặp lại $g$ lần thì ĐPT sẽ là $O(g \times f_1)$ với $g$ cũng là hàm của dữ liệu đầu vào.Ký hiệu $\log n$ là logarit của $n$ theo cơ số $X$ (với $X$ được định nghĩa bằng $2, e, 10$ tùy sách). Tuy nhiên với phép chuyển cơ số $\log_ab = \dfrac{\log b}{\log a}$ và $\log b$ là một hằng số nhỏ nên ta sẽ không cần quá quan tâm $X$ là cơ số bao nhiêu nữa).
ĐPT | Tên gọi | n |
---|---|---|
$O(1)$ | Hằng số (Constant) | Tùy yêu cầu bài toán |
$O(\sqrt n)$ | $10^{12}$ | |
$O(n)$ | Tuyến tính (Linear) | $10^{8}$ |
$O(n\log n)$ | Linearithmic | $10^6$ |
$O(n\sqrt n)$ | $2 \times 10^5$ | |
$O(n^2)$ | Bậc 2 (Quadratic) | $10^{4}$ |
$O(n^3)$ | Bậc 3 (Cubic) | $500$ |
$O(n^4)$ | Bậc 4 (Quartic) | $100$ |
$O(2^n)$ | Exponential | $20$ |
$O(n!)$ | Giai thừa (factorial) | $11$ |
Tuy nhiên, việc có ĐPT đáp ứng bộ dữ liệu như trong bảng trên, không có nghĩa thuật toán sẽ chạy nhanh (trong khoảng $1s$). Bạn đọc có thể xem chi tiết trong phần Mở rộng. Hằng số ĐPT
Dựa vào các quy tắc, ta rút ra được một số mẹo
khi tính ĐPT các vòng lặp:
1. Tính số lần lặp tối đa của một vòng lặp
2. Nếu các vòng lặp nối tiếp nhau thì cộng các cận đó với nhau
3. Nếu các vòng lặp lồng nhau thì nhân các cận với nhau
Ví dụ 1:
int sum = 0;
for (int i = 0; i < n; i++) sum += i;
for (int j = 0; j < n; j++) sum += j;
Hai vòng có tổng cộng $n \times 2$ phép cộng, nên ĐPT sẽ là $\boldsymbol{O(n)}$
Ví dụ 2:
int sum = 0;
for (int i = 0; i < n; i++){
int j = 0;
while (j < n){
sum += j;
j++;
}
}
Hai vòng lặp lồng nhau, mỗi vòng lặp có ĐPT $O(n)$ nên ĐPT sẽ là $\boldsymbol{O(n^2)}$
Ví dụ 3:
int sum = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < i; j++){
sum += j;
}
}
Vòng i
lặp n
lần, vòng j
lặp tổng cộng $1 + 2 + \ldots + n = \dfrac{n \times (n + 1)}{2}$ lần, nên ĐPT chung vẫn sẽ là $\boldsymbol{O(n^2)}$ dù số phép tính đã được giảm đi khá nhiều.
Cho một mảng a[]
đã được sắp xếp. Xác định xem liệu có tồn tại $2$ phần tử trong mảng mà cách nhau $d$ đơn vị hay không.
Xét lời giải sau:
int j = 0;
for (int i = 0; i < n; i++) {
while ((j < n-1) && (a[i] - a[j] > d))
j++;
if (a[i] - a[j] == d){
cout << "Ton tai!";
return 0;
}
}
cout << "Khong ton tai";
Thoạt nhìn, nó khá giống với vòng lặp lồng ở Ví dụ i.2. và cho ra ĐPT $O(n^2)$ nhưng thực chất, ĐPT nhỏ hơn vậy.
Phân tích: Ta xét trường hợp xấu nhất là khi "Khong ton tai"
:
j
nhận giá trị từ 1
đến n
, mỗi giá trị n
lần, và ĐPT chung sẽ là $O(n^2)$.i
chạy từ 1
đến n
, mỗi giá trị xét $1$ lần. Còn biến j
chạy từ 1
đến n
, mỗi giá trị xét tối đa $1$ lần. Nên ĐPT trong trường hợp xấu nhất là $O(2n)$ hay $\boldsymbol{O(n)}$.Nhận xét:
Knuth's Optimization
hay Knapsack on tree
, thì ta phải dùng cách này để tính ĐPT một cách chính xác hơn.Cho một dãy được sắp xếp tăng dần, kiểm tra xem dãy có tồn tại giá trị target
không.
Xét lời giải bằng tìm kiếm nhị phân như sau:
int binary_search(int a[], int sizeA, int target) {
int lo = 1, hi = sizeA;
while (lo <= hi) {
int mid = lo + (hi - lo)/2;
if (a[mid] == target)
return mid;
else if (a[mid] < target)
lo = mid+1;
else
hi = mid-1;
}
// không tìm thấy giá trị target trong mảng A
return -1;
}
Ở mỗi bước, kích thước của mảng cần tìm kiếm bị giảm đi một nửa. Sau $\lceil \log_2 n \rceil$ bước, thì số phần tử của mảng là $1$ và dừng tìm kiếm. Từ đó ĐPT của thuật toán là $\boldsymbol{O(\log n)}$ với $n$ là số phần tử ban đầu của không gian tìm kiếm.
Đây là một đoạn code sinh tất cả các hoán vị từ $1$ đến $n$ với $(n \le 10)$
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int n, a[N + 5];
bool used[N + 5];
void print(){
for (int i = 1; i <= n; i++)
cout << a[i];
cout << '\n';
}
void backtrack(int i){
if (i == n + 1){
print();
return;
}
for (int j = 1; j <= n; j++) if (used[j] == false) {
a[i] = j;
used[j] = true;
backtrack(i + 1);
used[j] = 0;
}
}
int main()
{
cin >> n;
backtrack(1);
}
Phân tích:
Ta gọi hàm backtrack(1)
nên i
sẽ bắt đầu từ 1
.
Tại vòng lặp j
đầu tiên, ta xét tất cả các giá trị có thể gán cho a[1]
(số hạng thứ 1
) và đánh dấu đã sử dụng giá trị đó.
Và ta sẽ gán lần lượt a[2], ..., a[n]
.
Đến i = n + 1
, chúng ta sẽ in ra kết quả và xét đến cấu hình tiếp. Việc in kết quả sẽ tốn 1 vòng $O(n)$
Vì thế ta có tổng cộng $n \times (n - 1) \times \ldots \times 1 \times n = n \times n!$ phép toán. Hay ĐPT bài toán là $\boldsymbol{O(n \times n!)}$.
Đôi khi ĐPT của một thuật toán đệ quy không quá lớn như $O(n!)$. Bạn đọc có thể thấy rõ với thuật toán sắp xếp Merge Sort (Sắp xếp trộn) sau đây:
MergeSort(mảng S) {
1. if (số phần tử của S <= 1)
return S;
2. chia đôi S thành hai mảng con S1 và S2 với số phần tử gần bằng nhau;
3. MergeSort(S1);
4. MergeSort(S2);
5. trộn S1 và S2 đã sắp xếp để thu được S mới đã sắp xếp;
6. return S mới;
}
Minh họa về cách thuật toán Merge Sort hoạt động:
Phân tích:
Gọi $f(n)$ là ĐPT của hàm MergeSort(S)
với $n = |S|$
Dễ thấy:
Trong đó: $\lfloor x \rfloor$ là số nguyên lớn nhất $\le x$ (phần nguyên dưới). $\lceil x \rceil$ là số nguyên nhỏ nhất $\ge x$ (phần nguyên trên).
Từ đó, ta có : $\begin{align}
\begin{cases}
f(1) = 1
f(n)=
f\left(\left\lfloor\dfrac{n}{2}\right\rfloor\right) + f\left(\left\lceil\dfrac{n}{2}\right\rceil\right)+ \alpha n \, (\alpha \ge 1)
\end{cases}
\end{align}$
ĐPT thuật toán này là $f(n) = \boldsymbol{O(n\log n)}$ trong cả worst case và average case.
Để có được kết luận trên, ta đi chứng minh phát biểu sau:
Tồn tại hằng số $c > 1$ nào đó mà với $\forall n \le T$ ta có $f(n)≤ n\log_2n + c\times n$
Bằng quy nạp, ta có:
- Với $n = 1$, rõ ràng luôn tồn tại $c''>1$ để $f(1)<c'' \times 1$
- Giả sử điều này đúng đến $n = k - 1$ $(k \ge 2)$, ta cần chứng minh đúng với $n = k$:
- Thật vậy, $\begin{align} f(k) &= f\left(\left\lfloor\frac{k}{2}\right\rfloor\right)+f\left(\left\lceil\frac{k}{2}\right\rceil\right) + \alpha k
\Rightarrow f(k) &\le 2f\left(\left\lceil\frac{k}{2}\right\rceil\right) + \alpha k
&\le \left( 2 \left\lceil\frac{k}{2}\right\rceil \times \log_2\left(\left\lceil\frac{k}{2}\right\rceil\right) + c' k \right) + \alpha k
&\le \left( 2 \times\frac{k}{2}\times \log_2\left(\frac{k}{2}\right) + \beta k \right) + (c'+\alpha) k
&= k \log_2 k - k + (c' + \alpha + \beta)\times k
&= k \log_2 k + c''\times k
\end{align}$
Chọn $c = \max\limits_{n \le T}(c'')$, ta được đpcm.
Bạn đọc có thể tham khảo dạng tổng quát của bài toán: Master theorem (Định lý thợ)
Tính độ phức tạp thời gian của đoạn code sau:
int cnt = 0;
for (int i = 1; i <= n; i++){
for (int j = i; j <= n; j += i){
cnt++;
}
}
Giải:
Rõ ràng, với mỗi biến $i$, vòng lặp $j$ sẽ chạy $\left\lfloor\dfrac{n}{i}\right\rfloor$ lần.
Vì thế độ phức tạp sẽ là $O\left( n \times \left(\dfrac{1}{1} + \dfrac{1}{2} +\ldots+\dfrac{1}{n} \right) \right) = O\left(n \cdot \sum\limits_{i = 1}^{n} \dfrac{1}{i}\right)$.
Và đến đây rút gọn thế nào nhỉ?
$x > \log(1 + x)$ với mọi $x > 0$ nên $\dfrac{1}{1} + \dfrac{1}{2} +\ldots+\dfrac{1}{n} \ge \log\dfrac{2}{1} + \log\dfrac{3}{2} +\ldots+ \log\dfrac{n+1}{n} = \log(n+1)$
Nhận xét: Rõ ràng, $\left\lfloor \dfrac{n}{i} \right\rfloor$ là số số $\le n$ và chia hết cho $i$. Vì thế với $\tau(n)$ là số ước dương của $n$ thì bản chất độ phức tạp của bài toán trên là: $f(n) = \tau(1) + \tau(2) + \ldots + \tau(n) = \sum\limits_{i = 1}^{n} \left\lfloor \dfrac{n}{i} \right\rfloor \sim n\log n$ $f(n)$ cũng chính là số cặp số nguyên dương $(i, j)$ thỏa mãn: $i \cdot j \le n$.
Tính độ phức tạp thời gian của giải thuật sàng nguyên tố Erathosenes:
for (int i = 2; i * i <= n; i++) is_prime[i] = true;
for (int i = 2; i <= n; i++) if (is_prime[i]){
for (int j = i * 2; j <= n; j += i){
is_prime[j] = false;
}
}
Giải:
Tương tự bài trên, nhưng chỉ khi biến $i$ là số nguyên tố thì biến $j$ sẽ chạy $n/i$ lần, ngược lại biến $j$ không phải chạy 1 vòng nào.
Vì thế độ phức tạp thời gian là $O\left( n \times \left(\dfrac{1}{2} + \dfrac{1}{3} +\ldots+\dfrac{1}{p} \right) \right)$ với $p \style{font-family:Cambria Math}{\large\text{ là số nguyên tố}}\le n$.
Đến đây việc tính toán độ phức tạp sẽ phải dùng đến kiến thức Lý thuyết số giải tích. Bạn đọc có thể tham khảo thêm Định lý Merten 2.
$O\left( n \times \left(\dfrac{1}{2} + \dfrac{1}{3} +\ldots+\dfrac{1}{p} \right) \right) = O\left(n \cdot \underset{{p \le n}}{\sum\limits_{p \style{font-family:Cambria Math}{\large\text{ nguyên tố}}}}\dfrac{1}{p}\right) = \boldsymbol{O( n \log (\log n))}$
$O(n)$ thuộc một họ hàm Bachmann–Landau. Và trong họ hàm này, có một số hàm cũng được dùng để đánh giá ĐPT là $\Omega(n)$ (Omega lớn) và $\Theta(n)$ (Theta lớn). Tuy $\Theta(n)$ đánh giá cận chính xác $($không phải cận trên như $O(n))$, nhưng ta vẫn sử dụng $O(n)$ vì sự phổ biến và dễ viết của nó.
std::sort
, std::priority_queue
, std::set
/std::map
đều có ĐPT $O(n\log n)$.std::sort
$<$ std::priority_queue
$<$ std::set
/std::map
std::sort
của C++. Thuật toán chủ yếu vẫn là Quick-sort
- $O(n\log n)$. Và để tối ưu, thì với bộ dữ liệu nhỏ, hàm sẽ sử dụng Insert-Sort
- $O(n^2)$. Còn khi chọn phần tử chốt của Quick-sort
không đẹp, thì sẽ sử dụng Heap-Sort
- $O(n\log n)$ thay thế.Với lập trình viên, độ phức tạp thời gian là một công cụ hữu ích để ước chừng thời gian thực thi của một thuật toán, hay so sánh giữa các thuật toán với nhau. Trong các kỳ thi lập trình, kích cỡ của tập dữ liệu thường được cho trước trong đề bài. Dựa vào điều đó, thí sinh có thể ước chừng độ phức tạp rồi tìm ra thuật toán phù hợp. Hoặc là khi đã nghĩ ra một vài thuật toán thì liệu thuật toán nào đáng để cài đặt? Nên chọn những thuật toán nào để cài đặt? ĐPT BigO - phân tích dựa trên tiệm cận là một công cụ mạnh mẽ. Nhưng Big O bỏ qua các hằng số, và đôi khi các hằng số lại quan trọng. Vì thế phải sử dụng nó một cách khôn khéo nhất để đạt hiệu quả cao trong lập trình.