ĐỘ PHỨC TẠP CỦA THUẬT TOÁN
Một chương trình máy tính thường được cài đặt dựa trên một thuật toán
đúng để giải quyết bài toán hay vấn đề. Tuy nhiên, ngay cả khi thuật toán đúng,
chương trình vẫn có thể không sử dụng được đối với một dữ liệu đầu vào nào đó
vì thời gian để cho ra kết quả là quá lâu hoặc sử dụng quá nhiều bộ nhớ (vượt
quá khả năng đáp ứng của máy tính).
Khi tiến hành phân tích thuật toán nghĩa là chúng ta tìm ra một đánh giá về
thời gian và "không gian" cần thiết để thực hiện thuật toán. Không gian ở đây
được hiểu là các yêu cầu về bộ nhớ, thiết bị lưu trữ, của máy tính để thuật
toán có thể làm việc. Việc xem xét về không gian của thuật toán phụ thuộc phần
lớn vào cách tổ chức dữ liệu của thuật toán. Trong phần này, khi nói đến độ
phức tạp của thuật toán, chúng ta chỉ đề cập đến những đánh giá về mặt thời
gian mà thôi.
Phân tích thuật toán là một công việc rất khó khăn, đòi hỏi phải có những
hiểu biết sâu sắc về thuật toán và nhiều kiến thức toán học khác. Ðây là công
việc mà không phải bất cứ người nào cũng làm được. Rất may mắn là các nhà
toán học đã phân tích cho chúng ta độ phức tạp của hầu hết các thuật toán cơ sở
(sắp xếp, tìm kiếm, các thuật toán số học, ). Chính vì vậy, nhiệm vụ còn lại
của chúng ta là hiểu được các khái niệm liên quan đến độ phức tạp của thuật
toán.
Ðánh giá về thời gian của thuật toán không phải là xác định thời gian tuyệt
đối (chạy thuật toán mất bao nhiêu giây, bao nhiêu phút, ) để thực hiện thuật
toán mà là xác định mối liên quan giữa dữ liệu đầu vào (input) của thuật toán và
chi phí (số thao tác, số phép tính cộng,trừ, nhân, chia, rút căn, ) để thực hiện
thuật toán. Sở dĩ người ta không quan tâm đến thời gian tuyệt đối của thuật toán
vì yếu tố này phụ thuộc vào tốc độ của máy tính, mà các máy tính khác nhau thì
có tốc độ rất khác nhau. Một cách tổng quát, chi phí thực hiện thuật toán là một
hàm số phụ thuộc vào dữ liệu đầu vào :
T = f(input)
Tuy vậy, khi phân tích thuật toán, người ta thường chỉ chú ý đến mối liên
quan giữa độ lớn của dữ liệu đầu vào và chi phí. Trong các thuật toán, độ lớn

max
= a
1
.
2. i = 2.
3. Nếu (i ? n) thì thực hiện các bước sau, ngược lại sang bước 5.
3.1. Nếu (a
i
> a
max
) thì
3.1.1. Ghi nhớ a
max
= a
i
.
3.2. Tăng i lên 1.
4. Trở lại bước 3.
5. Phần tử lớn nhất dãy a chính là amax .Kết thúc.
Trong thuật toán trên, để đơn giản, ta chỉ xem chi phí là số lần so sánh ở
bước 3.1 và số lần "ghi nhớ" trong bước 3.1.1. Trường hợp tốt nhất của thuật
toán này xảy ra khi con số lớn nhất nằm đầu dãy (a
max
= a
1
); trường hợp xấu nhất
xảy ra khi con số lớn nhất nằm ở cuối dãy (a
max
=a
n

-1< a
i
(do định nghĩa dãy được sắp xếp tăng dần) nên
điều kiện a
i
>a
max
ở bước 3.1 luôn thỏa, bước 3.1.1 luôn được thực hiện. Như vậy,
ngoài chi phí chung là n-1 phép so sánh, ta cần phải dùng thêm n-1 phép "ghi
nhớ" ở bước 3.1.1. Như vậy, tổng chi phí của trường hợp này là
T = f(n) = 2(n-1)=2n-2
Ðịnh nghĩa
Cho hai hàm f và g có miền xác định trong tập số tự nhiên . Ta viết
f(n) = O(g(n))
và nói f(n) có cấp cao nhất là g(n) khi tồn tại hằng số C và k sao cho
| f(n) | ? C.g(n) với mọi n > k
Tuy chi phí của thuật toán trong trường hợp tốt nhất và xấu nhất có thể nói
lên nhiều điều nhưng vẫn chưa đưa ra được một hình dung tốt nhất về độ phức
tạp của thuật toán. Ðể có thể hình dung chính xác về độ phức tạp của thuật toán,
ta xét đến một yếu tố khác là độ tăng của chi phí khi độ lớn n của dữ liệu đầu
vào tăng.
Theo định nghĩa ở trên, ta nhận thấy chi phí thấp nhất và lớn nhất của thuật
toán tìm số lớn nhất đều bị chặn bởi O(n) (tồn tại hằng số C=10, k=1 để 2n-2 <
10n với mọi n>1).
Một cách tổng quát, nếu hàm chi phí của thuật toán (xét trong một trường
hợp nào đó) bị chặn bởi O(f(n)) thì ta nói rằng thuật toán có độ phức tạp là
O(f(n)) trong trường hợp đó.
Như vậy, thuật toán tìm số lớn nhất có độ phức tạp trong trường hợp tốt
nhất và xấu nhất đều là O(n). Người ta gọi các thuật toán có độ phức tạp O(n) là
các thuật toán có độ phức tạp tuyến tính.