Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 1
Cấutrúcdữ liệuvàGiảithuật
Chương I: Các kiếnthứccơ bản
Các kiếnthứccơ bản
Nội dung
 Các khái niệm
 Giảithuật
 Cấutrúcdữ liệu
 Phân tích giảithuật
 Giả ngôn ngữ
 Thờigianthựchiệngiảithuật
 Đánh giá độ phứctạpsử dụng tiệmcận
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 2
– Mộtthủ tục bao gồmmột dãy hữuhạncácbước
cầnthựchiện để thu được đầurachođầuvào
cho trướccủamột bài toán
Giảithuật
Giảithuật
z Đặctrưng củagiảithuật
– Đầuvào
– Đầura
– Tính hữuhạn
– Tính hiệuquả
– Tính xác định
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 3
GiảithuậtvàChương trình
Chươngtrìnhlàmộtthể hiệncủaGiảithuật trong một
ngôn ngữ lập trình nào đó

z Gồmcácbước
– Thu thậpyêucầu: Hiểurõđầuvàovàkếtquảđầura
– Thiếtkế : Xây dựng giảithuật, bỏ qua các chi tiếtvề cách thức
cài đặtdữ liệu hay các phương thức, tập trung vào các bướcxử
lý
– Phân tích : Tìm, so sánh vớigiảithuật khác
– Cài đặt: Xây dựng chương trình, quan tâm đếncáchthứctổ
chức, biểudiễnvàcàiđặt các phương thức
– Kiểmthử : Bao gồmchứng minh tính đúng đắncủachương
trình, kiểmthử các trường hợp, tìm, sửalỗi
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 5
Thuậttoánvàđộ phứctạp
– Đánh giá lượng tài nguyên các loạimàmộtgiải
thuật đãsử dụng.
z Giảithuậtnàythựchiện trong thờigianthế nào Æ
Phân tích về thờigianthựchiệngiảithuật
z Giảithuậtnàysử dụng bao nhiêu bộ nhớ Æ Phân tích
độ khônggiannhớ mà giảithuật(chương trình) cầncó.
Phân tích thờigianthựchiệngiảithuật
– Mụctiêucủaviệcxácđịnh thờigianthựchiện
mộtgiảithuật:
z Để ướclượng mộtchương trình sẽ thựchiện trong bao
lâu
z Để ướclượng kích thướcdữ liệu đầuvàolớnnhấtcó
thể cho mộtgiảithuật
z Để so sánh hiệuquả của các giảithuật khác nhau, từđó
lựachọnramộtgiảithuậtthíchhợpchomột bài toán
z Để giúp tập trung vào đoạngiảithuật đượcthựchiện
vớithờigianlớnnhất

– Mộtcáchtiếpcận để khái quát hóa độ phứctạpvề thờigian
Mô tả giảithuật–Giả ngôn ngữ
z Giả ngôn ngữ (Pseudo-code)
– Mô tả mức khái quát cao đượcsử dụng trong diễntả
giảithuật
Giả ngôn ngữ = Cấutrúclập trình + Ngôn ngữ tự nhiên
Algorithm arrayMax(A,n)
Input: Mảng chứan phầntử là số nguyên
Output: Phầntử lớnnhất trong mảng
Begin
currentMax = A[0]
for i = 1 to n-1 do
if currentMax < A[i] then currentMax = A[i]
return currentMax
End.
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 8
Giả ngôn ngữ
– Các cấutrúclập trình trong giả ngôn ngữ
z Câu lệnh gán: V = E hoặcV Å E
z Cấutrúcđiềukhiển:
– if B then S
1
[else S
2
]
– Case
B
1
: S

Function <tên hàm> (<danh sách tham số>)
Begin
<các câu lệnh>
return (giá trị)
End
z Gọihàm: Hàm đượcgọibằng tên hàm cùng danh sách
giá trị tham số thựcsự, nằm trong biểuthức
Giả ngôn ngữ
Function AVERAGE(A,n)
Begin
{A là mộtmảng gồmn phầntử là số nguyên. Giảithuậttrả ra giá trị
trung bình của các giá trị trong mảng}
1. sum = 0;
2. {Duyệtmảng} for I = 1 to n do
sum = sum + A[i];
3. average = sum/n
4. return(average)
End.
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 10
Giả ngôn ngữ
– Khai báo thủ tục
– Thủ tục đượcgọibằng cách sử dụng câu lệnh
Call <tên thủ tục> (<danh sách giá trị tham số>)
Procedure <tên thủ tục> (<danh sách tham số>)
Begin
<các câu lệnh>
End
Phân tích thờigianthựchiệngiảithuật
– Độ đothời gian tính sử dụng trong phương pháp

Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 11
Phân tích thờigianthựchiệngiảithuật
– Các phép toán cơ bảnthường dùng
z Gán giá trị cho biếnsố
z Gọi hàm hay thủ tục
z Thựchiện các phép toán số học
z Tham chiếuvàomảng
z Trả kếtquả
z Thựchiện các phép so sánh
Phân tích thờigianthựchiệngiảithuật
– Dòng 1: 2 phép toán cơ bản
– Dòng 2: phép gán giá trịđầu
cho i, phép so sánh i < n
đượcthựchiệnn lần
– Thân vòng lặpthựchiệnn-1
lần, trong thân, tốithiểuphải
thựchiện phép so sánh (2 phép
toán cơ bản) , tăng i lên 1 (2 phép
toán cơ bản) tối đaphải có thêm
phép gán (2 phép toán cơ bản)
– Dòng 3: 1 phép toán cơ bản
Tổng số phép toán cơ bảntrong
Trường hợpxấunhất: 7n-2
Function ARRAY-MAX(A,n)
Đâu vào : mảng A gồmn phầntử.
Đầu ra: phầntử lớnnhấttrong
mảng
Begin
1. currentMax = A[0]
2. for i = 1 to n-1 do

Phân tích thờigianthựchiệngiảithuật
– Ví dụ : Tìm kiếmtuầntự mộtgiátrị trên mộtmảng
– Thờigianxấunhất: n
– Thờigiantốtnhất: 1
– Thời gian trung bình: T(n) = ∑i.pi
trong đó pi là xác suấtgiátrị cầntìmxuấthiệntại
a[i]. pi = 1/n thì thờigiansẽ là (n+1)/2
817791623622142110784
a[12]a[11]a[10]a[9]a[8]a[7]a[6]a[5]a[4]a[3]a[2]a[1]
Ký hiệutiệmcận
– Khái niệmBig-O
– Cho hàm số t(n) và g(n), ta nói rằng t(n) là O(g(n)) nếutồntại
2 hằng số nguyên dương c và
n
0
sao cho
t(n) ≤ cg(n) for n ≥ n
0
t(n) thuộc O(g(n))
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 14
Ký hiệutiệmcậnBig -O
– 7n -2
z 7n-2 là O(n)
tìm c > 0 và n0 ≥ 1 sao cho 7n-2 ≤ c*n vớin ≥ n0
điều này đúng với c = 7 và n0 = 1
– 3n3 + 20n2 + 5
z 3n3 + 20 n2 + 5 là O(n3)
tìm c > 0 và n0 ≥ 1 sao cho 3n3 + 20n2 + 5 ≤ c*n3 vơin ≥ n0
điều này đúng với c = 4 và n0 = 21

z Big-O là ký hiệutiệmcậntrêncủamộthàm
z NếutacóT(n) làO(g(n)) thìđộ tăng trưởng của T(n)
không vượtquáđộ tăng trưởng củag(n)
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 16
Ký hiệutiệmcậnBig -O
– Qui tắcxácđịnh độ phứctạpvề thờigian
z Hàm thời gian T(n) củamột đoạncủathuật toán là đa
thứcbậc k thì T(n) là O(n
k
)
z n
x
= O(a
n
), vớibấtkỳ x > 0 và a > 1
z log n
x
= O(log n), vớix > 0
Ký hiệutiệmcậnBig -O
– Qui tắcxácđịnh độ phứctạp
z Cấutrúctuầntự -Qui tắctổng
z Cho 2 đoạncủathuật toán P
1
và P
2
vớithờigian
thựchiệntương ứng là T
1
(n) và T

và P
2
vớithờigianthực
hiệntương ứng là T
1
(n) và T
2
(n) . Thờigianthựchiện
P
1
và P
2
lồng vào nhau là: T
1
(n)T
2
(n)
– Độ phứctạpcủa hai đoạnchương trình P
1
và P
2
liên
tục nhau có thể xác định là O(f(n)*g(n)) nếuT
1
(n) =
O(f(n)) và T
2
(n) = O(g(n)).
Ký hiệutiệmcậnBig -O
for i = 1 to n

while (i <= n) do
begin
j := 1 ;
while (j <= n) do
begin
P ; {đoạngiảithuậtvới
thờigianthựchiệnT}
j := j × 2;
end
i =: i + 1;
end
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 19
Ký hiệutiệmcậnBig -O
z Ví dụ
i = 1
while (i <= n) do
begin
j := 1 ;
while (j <= n) do
begin
P;
j := j +1;
end
i =: i + 1;
end
Các khái niệmtiệmcậnkhác
-Big-Omega
z t(n) đượccoilàΩ(g(n)) nếutồntạimộthằng số c >0 và
mộtsố nguyên n

2
= Θ(n
2
) vớic = 5 vàn
0
= 1
– 3 log(n) + log (log n) = Ω(log n) với c = 3 và n
0
= 2
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 21