Độ phực tạp thuật toán và tổ chức dữ liệu
Trần Đỗ Hùng
Trong Tin học, khi phân tích một bài toán người ta cũng tìm giả thiết và kết luận. Giả thiết
là những dữ liệu đưa vào máy tính xử lí kèm theo các điều kiện ràng buộc chúng (gọi là
input) và kết luận là những thông tin thu được sau xử lí (gọi là output). Bài toán trong Tin
học có thể hiểu là bất cứ công việc gì có thể giao cho máy tính thực hiện: vẽ một chữ, một
hình trên màn hình cũng là bài toán! …
Phương pháp giải bài toán có thể cài đặt thành chương trình máy tính (viết bằng ngôn ngữ
lập trình) gọi là thuật toán. Thuật toán được thể hiện là dãy các thao tác có thứ tự và hữu
hạn để sau khi thực hiện dãy thao tác này, từ input của bài toán sẽ nhận được output của
bài toán.
Một bài toán có thể được giải bằng một vài thuật toán khác nhau. Người ta cần lựa chọn
thuật toán thích hợp và do đó cần đánh giá thuật toán. Để đánh giá thuật toán người ta dựa
vào khái niệm độ phức tạp thuật toán. Độ phức tạp của thuật toán là đại lượng đánh giá
lượng thời gian và không gian bộ nhớ dành cho thực hiện thuật toán.
Từ ý nghĩa thực tiễn của các bài toán khác nhau, có khi người ta quan tâm tới thuật toán
đòi hỏi ít thời gian thực hiện, nhưng cũng có khi lại quan tâm nhiều hơn tới thuật toán cho
phép cài đặt dữ liệu chiếm ít không gian bộ nhớ.
Độ phức tạp về không gian bộ nhớ của thuật toán phụ thuộc phần lớn vào cấu trúc dữ liệu
được sử dụng khi cài đặt thuật toán.
Độ phức tạp về thời gian thực hiện (còn gọi là độ phức tạp tính toán) được đánh giá sơ bộ
dựa vào số lượng các thao tác cơ bản (gán, so sánh 2 số nguyên, cộng, nhân 2 số nguyên
…). Số lượng các thao tác này là một hàm số của kích cỡ dữ liệu input. Nếu kích cỡ dữ
liệu input là N thì thời gian thực hiện thuật toán là một hàm số của N. Với một thuật toán
trên các bộ dữ liệu input khác nhau (cùng kích cỡ N) có thể các hàm số này là khác nhau;
song điều quan tâm hơn cả là mức độ tăng của chúng như thế nào khi N tăng đáng kể.
Ví dụ: Xét thuật toán tìm giá trị lớn nhất trong dãy N số sau đây:
Input. Số nguyên dương N, dãy N số A
1
, A
2

, …, A
N
Output max{A
1
, A
2
,…, A
N
}
Bước 1. max ← A
1
Bước 2. for i ← 2 to N do
If max < A
i
then max ← A
i
Bước 3. Hiện max
Trường hợp xấu nhất: dữ liệu vào là dãy sắp tăng, thì số thao tác cơ bản là f(N)=2N+1
Trường hợp tốt nhất: giá trị lớn nhất ở ngay đầu dãy, thì thao tác cơ bản là g(N)= N.
Khi N lớn đáng kể thì f(N) và g(N) coi như xấp xỉ nhau và xấp xỉ hàm bậc nhất của N. Vậy
trong trường hợp này ta kí hiệu độ phức tạp thời gian của thuật toán trên là O(N).
Người ta phân lớp các bài toán theo độ phức tạp thuật toán. Có thể liệt kê một số lớp sau
có độ phức tạp tăng dần:
- Độ phức tạp hằng O(1)
- Độ phức tạp lôgarit O(logN)
- Độ phức tạp tuyến tính O(N)
- Độ phức tạp NlogN O(NlogN)
- Độ phức tạp đa thức O(N
k
) k: hằng nguyên

- Độ phức tạp luỹ thừa O(a
N
) a: cơ số nguyên dương khác 1
- Độ phức tạp giai thừa O(N!)
Tính hiệu quả (về thời gian) của thuật toán là đánh giá về thực hiện thuật toán trong một
khoảng thời gian cho phép. Tính hiệu quả được nhận xét gián tiếp qua độ phức tạp tính
toán của thuật toán. Độ phức tạp lớn thì thời gian thực hiện lâu hơn.
Chúng ta xét hai bài toán quen thuộc sau đây làm ví dụ về lựa chọn thuật toán và cài đặt dữ
liệu:
Bài toán 1. Dãy đơn điệu tăng dài nhất
Cho mảng ĂN) gồm N phần tử nguyên. Hãy xoá đi một số ít nhất các phần tử của mảng để
những phần tử còn lại lập thành dãy tăng dài nhất.
Dữ liệu vào từ file văn bản DAYTANG.IN
Dòng đầu là số nguyên N (1≤ N ≤ 30000)
Tiếp theo là N số nguyên lần lượt từ phần tử đầu đến phần tử cuối của mảng.
Kết quả ghi ra file văn bản DAYTANG.OUT
Dòng đầu là số K là số lượng các phần tử còn giữ lại
Tiếp theo là K dòng, mỗi dòng ghi 2 số: số thứ nhất là giá trị phần tử giữ lại, số thứ hai là
chỉ số (trong mảng ban đầu) của phần tử được giữ lại này. DAYTANG.IN
10
1 2 8 10 5 9 4 3 6 7
DAYTANG.OUT
5
1 1
2 2
5 5
6 9
7 10
Bài toán này thường được giải bằng Qui hoạch động. Có thể cài đặt dữ liệu như sau:
Xây dựng 2 mảng một chiều T và mảng D với ý nghĩa sau:

D[i] là độ dài của dãy kết quả khi bài toán chỉ xét dãy A
1
, A
2
,…, A
i
và nó được tính theo
công thức truy hồi:
D[i] = Max { D[i], D[j] +1 với mọi j mà j < i và A
j
≤A
i
} (1)
T[i]=j là chỉ số (trong dãy A ban đầu) của phần tử đứng ngay trước A
i
trong dãy kết quả.
Cách tìm T[i]: duyệt mảng A từ vị trí 1 đến vị trí i-1, vị trí j thoả mãn có D[j] lớn nhất và
A[j]≤A[i].
Khởi trị: T[1]:= 0 ; D[1]:= 1; Ví dụ:
Khi duyệt ngược tìm kết quả ta tiến hành như sau:
Tìm phần tử lớn nhất trong D, giả sử đó là D[i], ta đổi dấu của D[i] coi như đánh dấu nó,
tìm tiếp phần tử j = T[i], lại đổi dấu D[j], quá trình cứ như thế lùi chỉ số j đến khi j=0
Kết qủa được dãy con dài nhất là : 3 4 7 9 10
Độ phức tạp tính toán của thuật toán trên là O(N
2
). Với N=30000 thì mặc dù có thể tổ chức
các mảng động một chiều để cài đặt dữ liệu thực hiện thuật toán nhưng cũng không thể
chấp nhận được vì thời gian thực hiện thuật toán quá lâu!
Ta tìm kiếm một thuật toán khác (vẫn bằng qui hoạch động):
Về cài đặt dữ liệu:

+ Mảng một chiều A là dãy số đã cho ban đầu.
+ Mảng một chiều L dùng để lưu các chỉ số (trong dãy A ban đầu) của một số phần tử của
A xếp theo giá trị tăng dần (tạo thành một dãy trung gian là H) để dựa vào H ta có thể tìm
ra giá trị mảng Tr.
+ Mảng Tr có ý nghĩa như sau: Tr^[k] là chỉ số (trong dãy A ban đầu) của phần tử đứng
trước phần tử A
k
trong dãy kết quả. Dựa vào mảng Tr sẽ tìm ra dãy kết quả.
+ Dùng biến d để theo dõi độ dài dãy kết quả
Thuật toán:
- Ban đầu dãy kết quả có độ dài d=1, phần tử đầu của dãy H là A
1
. Xác nhận chỉ số (trong
dãy A ban đầu) của phần tử đầu dãy H là L[1]:=1, chỉ số (trong dãy A ban đầu) của phần
tử cuối dãy H là L[d]=1. Chưa có phần tử trước A
1
nên tạm coi chỉ số của phần tử trước A
1
là 0 (gán Tr^[1] :=0;)
- Duyệt tuyến tính các phần tử từ A
2
đến A
N
. Giả sử đã xét đến A
k
.
+ Nếu A
k
< A thì thay phần tử đầu của dãy H bằng A
k

nhờ gán lại L[1]:=k; Tr^[k]:= 0;
+ Nếu A
k
> = A
L[d]
thì thêm A
k
vào cuối dãy H(điều này tương ứng với sự kiện dãy kết quả
được kéo dài thêm 1 phần tử nữa vì phần tử A
k
có chỉ số k > L[d]. Tuy nhiên, chú ý rằng
dãy H không đồng nhất với dãy kết quả). Gán Tr^[k]:= L[d]; Inc(d); L[d]=k;
+ Trường hợp còn lại: dùng phương pháp tìm kiếm nhị phân để biết vị trí A
k
trong dãy
H={A
L[1]
, A
L[2]
, …, A
L[d]
). Giả sử tìm được chỉ số t sao cho A
L[t-1]
≤ A
k
≤ A
L[t]
thì ta gán
Tr^[k] :=L[t-1]; L[t] := k;
- Dựa vào mảng Tr^ tìm ngược dãy kết quả (dài bằng d). Chú ý rằng phần tử cuối cùng của

dãy kết quả là A
L[d]

Thủ tục chính của chương trình theo thuật toán trên là:
procedure lam;
var l : mg;
i,j,k,t : integer;
f : text;
begin
new(tr); { tr^[i]=j nghĩa là trong dãy tăng kết quả: liền trước A[i] là A[j] }
fillchar(l,sizeof(l),0);
fillchar(tr^,sizeof(tr^),0);
l[1]:=1; {Xác nhận phần tử đầu của dãy H có chỉ số là 1 }
d:=1; {d: số lượng phần tử của dãy kết qủa}
for k:=2 to n do {duyệt dãy A, từ phần tử thứ 2}
begin
if â[k]< then b>
begin
l[1]:=k; {phần tử đầu của dãy H là â[k]}
tr^[k]:=0; {â[k] có thể là phần tử đầu của dãy kết quả}
end
else
if â[k]>=â[l[d]] then
begin
tr^[k]:=l[d];{xác nhận l[d] là chỉ số của phần tử có thể đứng trước â[k] trong dãy kết
quả }
inc(d);
l[d]:=k; {thêm phần tử â[k] vào cuối dãy H}
end
else {bằng tìm kiếm nhị phân vị trí của â[k] trong dãy H}

begin
i:=1;j:=d;
while i< b>
begin
t:=(i+j)div 2;
if â[k]>=â[l[t]] then i:=t+1
else j:=t;
end;
t:=(i+j) div 2;
tr^[k]:=l[t-1];
l[t]:=k; {phần tử thứ t trong H là Â[k]}
end;
end;
k:=l[d]; {tìm vết dãy kết quả, lần từ cuối dãy}
fillchar(l,sizeof(l),0);
assign(f,fo);
rewrite(f);
writeln(f,d);
while k>0 do {ghi lại vết dãy kết quả}
begin
l[k]:=1;
k:=tr^[k];
end;
for k:=1 to n do
if l[k]=1 then writeln(f,â[k],#32,k); {ghi kết quả vào file output}
close(f);
end;
Độ phức tạp thời gian của thuật toán này là O(NlogN) nên có thể chấp nhận về thời gian
cho phép khi N=30000.
Bài toán 2. Palindrome (time limit 2s)

Một xâu được gọi là xâu đối gương nếu đọc từ trái qua phải cũng giống như đọc từ phải
qua trái. Ví dụ xâu "madam" là một xâu đối gương. Bài toán đặt ra là cho một xâu S gồm
các kí tự thuộc tập M=[’a’..’z’], hãy tìm cách chèn vào xâu S các kí tự thuộc tập M tại các
vị trí bất kì với số lượng kí tự chèn vào là ít nhất để xâu S thành xâu đối gương. Ví dụ:
xâu: "adbhbca" ta sẽ chèn thêm 2 kí tự ( c và d) để được xâu đối gương "adcbhbcda".
Dữ liệu vào trong file PALIN.IN có dạng:
Dòng thứ nhất là một số nguyên dương T (T <=10) là số bộ test
T dòng sau, mỗi dòng chứa một xâu S, độ dài mỗi xâu không vượt quá 500.
Kết quả ghi ra file PALIN.OUT có dạng: Gồm nhiều dòng, mỗi dòng là một xâu đối gương
sau khi đã chèn thêm ít kí tự nhất vào xâu S tương ứng ở file input.
Thuật toán.
Dùng Qui hoạch động:
Gọi L[i,j] là số kí tự cần chèn thêm vào đoạn S[i..j] để đoạn này thành đối gương (các đoạn
S[1..i-1] và S[j+1..n] đã đối xứng nhau rồi) thì:
L[i,j] = Min {L[i+1,j-1}, L[i+1,j]+1, L[i,j-1]+1} (2)
L[i,j] = L[i+1,j-1] chỉ khi S[i]=S[j]
L[i,j] = L[i+1,j]+1khi S[i]<>S[j] và ta chèn thêm S[i] vào bên phải S[j]. Đánh dấu hiện
tượng này bằng bít 1 trên mảng đánh dấu D.
L[i,j] = L[i,j-1]+1 khi S[i]<>S[j] và ta chèn thêm S[j] vào bên trái S[i]. Đánh dấu hiện
tượng này bằng bít 0 trên mảng đánh dấu D.
Nhãn L[1,N] chính là số kí tự chèn thêm cần tìm.
Do kích thước đề bài, không thể tổ chức mảng hai chiều L (kể cả cách tổ chức theo kiểu
mảng động cũng không thể được, vì mảng hai chiều kích thước 500�500 phần tử kiểu
Integer là quá lớn).
Vì vậy điều chủ chốt để thực hiện thuật toán này là vấn đề cài đặt dữ liệu theo cách khác
hợp lí hơn.
Ta có nhận xét: theo công thức truy hồi (2) thì L[i,j] chỉ liên quan tới L[i+1,j-1] , L[i,j-1] và
L[i+1,j].
Gọi độ dài đoạn S[i..j] là k=j-i+1. (hay là j=i+k-1)
Thay cho L[i, j] ta dùng C3[i] (ứng với khoảng cách từ i tới j là k).

Thay cho L[i+1, j] ta dùng C2[i+1] (ứng với khoảng cách từ i+1 tới j là k-1).
Thay cho L[i, j-1] ta dùng C2[i] (dùng C2 vì ứng với khoảng cách từ i tới j-1 vẫn là k-1).
Thay cho L[i+1, j-1] ta dùng C1[i+1] (ứng với khoảng cách từ i+1 tới j-1 là k-2)
Công thức truy hồi (2) có dạng mới là: