¶ Độ phức tạp thời gian
Người viết:
- Nguyễn Minh Hiển - Trường Đại học Công nghệ, ĐHQGHN
Reviewer:
- Nguyễn Đức Kiên - Trường Đại học Công nghệ, ĐHQGHN
- Phạm Hoàng Hiệp - University of Georgia
- Ngô Nhật Quang - The University of Texas at Dallas
¶ Giới thiệu
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.
¶ Khái niệm độ phức tạp thời gian (ĐPT)
Độ phức tạp thời gian là một hàm đo số thao tác cơ bản mà một thuật toán thực thi, với tham biến là kích thước đầu vào:
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:
- Trường hợp xấu nhất ít xảy ra. Ví dụ với thuật toán Quick Sort.
Trong trường hợp xấu nhất là khi ta luôn chọn phải phần tử chốt là phần tử lớn nhất hay nhỏ nhất của dãy, và ĐPT sẽ là , nhưng xác suất trường hợp này xảy ra rất nhỏ. Còn trong phần lớn các trường hợp khác, ĐPT là . - Thuật toán có yếu tố ngẫu nhiên. Ví dụ như việc sử dụng sinh số ngẫu nhiên.
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 (với 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ế.
¶ Độ phức tạp BigO
Xét 2 hàm số dương và
Ta ký hiệu:
Theo định nghĩa giải tích, ký hiệu trên tương đương với:
Gọi là "hàm không tăng (tiệm cận) nhanh hơn ".
Nói một cách dễ hiểu: thì tồn tại hằng số để khi đủ to với mọi nào đó thì .
Ví dụ:
- là vì khi chọn , chỉ cần thì
- thì không phải là nữa, mà sẽ là (chọn và )
¶ Một số quy tắc tính toán ĐPT
¶ Các quy tắc cơ bản
- Các phép sau được tính là lệnh đơn: phép đọc, viết, gán và các toán tử cơ bản (toán tử số học, quan hệ, logic, bit, gán, hỗn hợp)
Các phép này có ĐPT - Xét các lệnh
S1, S2, ..., Smvà ĐPT tương ứng của chúng là với là các hàm của dữ liệu đầu vào.
là một biểu thức logic.- Chuỗi các lệnh liên tiếp:
S1; S2; ...; Sm;có ĐPT - Khối lệnh rẽ nhánh
if E then S1 else S2có ĐPT - Các khối lặp:
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ử được lặp lại lần thì ĐPT sẽ là với cũng là hàm của dữ liệu đầu vào.
- Chuỗi các lệnh liên tiếp:
¶ Một số chú ý quan trọng
- Tất cả các bài toán có ĐPT đa thức bậc thì có ĐPT là . Các hằng số, hệ số đa thức thường (không phải luôn luôn) được bỏ qua.
Ký hiệu là logarit của theo cơ số (với được định nghĩa bằng tùy sách). Tuy nhiên với phép chuyển cơ số và là một hằng số nhỏ nên ta sẽ không cần quá quan tâm là cơ số bao nhiêu nữa).
- Coi với
- Dựa vào định nghĩa BigO, khi gặp một thuật toán có ĐPT là , thì nói "thuật toán đó có ĐPT " không hề sai. Hay tổng quát hơn là một thuật toán có ĐPT là mà ta bảo "nó có ĐPT " cũng không hề sai tùy ý.
Tuy nhiên, khi tính toán ĐPT, ta nên chọn nhỏ nhất sao cho thuật toán có ĐPT . Điều này sẽ giúp ta có cái nhìn chính xác hơn để đánh giá thuật toán. - Khi gặp các hàm nhiều biến, ta vẫn tính toán như thường.
Ví dụ: - Một số độ phức tạp thường gặp trong lập trình thi đấu và các dữ liệu phù hợp để thuật toán chạy trong khoảng (khoảng lệnh):
| ĐPT | Tên gọi | n |
|---|---|---|
| Hằng số (Constant) | Tùy yêu cầu bài toán | |
| Tuyến tính (Linear) | ||
| Linearithmic | ||
| Bậc 2 (Quadratic) | ||
| Bậc 3 (Cubic) | ||
| Bậc 4 (Quartic) | ||
| Exponential | ||
| Giai thừa (factorial) |
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 ). Bạn đọc có thể xem chi tiết trong phần Mở rộng. Hằng số ĐPT
¶ Ví dụ
¶ Vòng lặp
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 phép cộng, nên ĐPT sẽ là
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 nên ĐPT sẽ là
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 lần, nên ĐPT chung vẫn sẽ là dù số phép tính đã được giảm đi khá nhiều.
¶ Hai con trỏ
Cho một mảng a[] đã được sắp xếp. Xác định xem liệu có tồn tại phần tử trong mảng mà cách nhau đơ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 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":
- Trong Ví dụ i.2. biến
jnhận giá trị từ1đếnn, mỗi giá trịnlần, và ĐPT chung sẽ là . - Tuy nhiên trong Lời giải trên thì biến
ichạy từ1đếnn, mỗi giá trị xét lần. Còn biếnjchạy từ1đếnn, mỗi giá trị xét tối đa lần. Nên ĐPT trong trường hợp xấu nhất là hay .
Nhận xét:
- Thuật toán trên sở dĩ gọi là con trỏ bởi biến và độc lập, dù cho vòng lặp nằm trong vòng lặp .
- Khi gặp vòng lặp lồng, ta cần chú ý hơn, hoặc để chính xác thì nên cộng từng vòng lặp con bên trong. Sau này ta sẽ gặp các thuật toán tối ưu khá ảo như
Knuth's OptimizationhayKnapsack 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.
¶ Tìm kiếm nhị phâ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 bước, thì số phần tử của mảng là và dừng tìm kiếm.
Từ đó ĐPT của thuật toán là với là số phần tử ban đầu của không gian tìm kiếm.
¶ Đệ quy
¶ Thuật toán quay lui sinh cấu hình tổ hợp
Đây là một đoạn code sinh tất cả các hoán vị từ đến với
#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
Vì thế ta có tổng cộng phép toán. Hay ĐPT bài toán là .
¶ Chia để trị
Đôi khi ĐPT của một thuật toán đệ quy không quá lớn như .
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 là ĐPT của hàm MergeSort(S) với
Dễ thấy:
- Bước đều mất
- Bước sẽ mất bước với hai con trỏ
- Bước sẽ mất và
Trong đó:
là số nguyên lớn nhất (phần nguyên dưới).
là số nguyên nhỏ nhất (phần nguyên trên).
Từ đó, ta có :
ĐPT thuật toán này là 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ố nào đó mà với ta có
Bằng quy nạp, ta có:
- Với , rõ ràng luôn tồn tại để
- Giả sử điều này đúng đến , ta cần chứng minh đúng với :
- Thật vậy,
Chọn , 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ợ)
¶ ĐPT và chuỗi nghịch đảo
¶ Ví dụ 1
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 , vòng lặp sẽ chạy lần.
Vì thế độ phức tạp sẽ là .
Và đến đây rút gọn thế nào nhỉ?
- với mọi nên
- Lại có:
- Chặn được thế này thì ta được kết quả là
Nhận xét:
Rõ ràng, là số số và chia hết cho . Vì thế với là số ước dương của thì bản chất độ phức tạp của bài toán trên là:
cũng chính là số cặp số nguyên dương thỏa mãn: .
¶ Ví dụ 2
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 là số nguyên tố thì biến sẽ chạy lần, ngược lại biến không phải chạy 1 vòng nào.
Vì thế độ phức tạp thời gian là với là số nguyên tố .
Đế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.
¶ Mở rộng
¶ Họ hàm 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 lớn) và (Theta lớn).
Tuy đánh giá cận chính xác không phải cận trên như , nhưng ta vẫn sử dụng vì sự phổ biến và dễ viết của nó.
¶ Hằng số ĐPT
-
Với hầu hết các thuật toán thường gặp trong thực tế, giá trị hằng số của (hoặc ) thường là khá nhỏ. Nếu một thuật toán là , ĐPT chính xác là vào khoảng chứ không phải .
Nói cách khác: nếu hằng số quá lớn thì thường là các hằng số đó có liên quan tới các đại lượng có sẵn trong đề bài. Khi đó, ta cần gán một tên gọi cho hằng số đó và thêm nó vào đánh giá ĐPT, thay vì bỏ qua.- Ví dụ: thay vì để rồi suy ra ĐPT là thì nên viết thành với
- Trong toán học, vẫn là . Tuy nhiên điều này chỉ đúng khi cực lớn .
- Còn trong lập trình thi đấu, ta hay gặp bộ dữ liệu , nên rõ ràng sẽ chạy lâu hơn . Vì thế trong Ví dụ, việc đặt là hoàn toàn phù hợp.
-
Cũng như vừa đề cập, hằng số của thuật toán trong ĐPT cũng có ảnh hưởng đến thời gian thực thi.
-
Hai thuật toán có ĐPT ngang nhau không có nghĩa là chúng chạy nhanh như nhau.
- Ví dụ khi xét việc sắp xếp số nguyên,
std::sort,std::priority_queue,std::set/std::mapđều có ĐPT . - Tuy nhiên khi so sánh về thời gian chạy thì
std::sortstd::priority_queuestd::set/std::map
- Ví dụ khi xét việc sắp xếp số nguyên,
-
Thuật toán có ĐPT bậc cao hơn không có nghĩa là chúng chạy chậm hơn trong mọi bộ dữ liệu.
- Ví dụ điển hình là hàm
std::sortcủa C++. Thuật toán chính được sử dụng là Intro Sort, bắt đầu với Quick Sort. Để tối ưu, khi kích thước mảng nhỏ, hàm sẽ sử dụng Insertion Sort. Trong trường hợp độ sâu đệ quy vượt quá ngưỡng nhất định (khi chọn phần tử chốt của Quick-sort không hiệu quả), hàm sẽ chuyển sang Heap Sort để duy trì độ phức tạp trong trường hợp xấu nhất.
- Ví dụ điển hình là hàm
-
-
Vì thế, trong từng trường hợp, ta nên chú ý chọn thuật toán cho phù hợp nhất để tối ưu thời gian chạy chương trình.
Và đặc biệt khi sử dụng các hàm trong thư viện sẵn có hay các code sẵn có thì nên hiểu cơ bản cách hoạt động và tốc độ của nó.
¶ Lời kết
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.