Chương I Các kiến thức cơ bản - CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT | Trường Đại học Bách khoa Hà Nội

Việc cài đặt các kiểu dữ liệu trừu tượng đòi hỏi phải chọn các cấu trúc dữ liệu để biểu diễn. Liên quan đến cách thức tổ chức và truy nhập các phần tử dữ liệu. Đối với cây biểu thức, duyệt theo thứ tự trước ta sẽ được biểu thức trung tố, duyệt theo thứ tự sau ta sẽ được biểu thức hậu tố, duyệt theo thứ tự giữa ta được biểu thức tiền tố. Tài liệu được sưu tầm, giúp bạn ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!

10 5 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cấu trúc dữ liệu và giải thuật (ET2100)

Trường: Đại học Bách Khoa Hà Nội

Thông tin:

21 trang 2 tháng trước

Tác giả:

Profile Lân Nguyễn
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 đó
Cấutrúcdữ liệu
z Kiểudữ liệutrừutượng (Abstract Data Type)
– Là mô hình toán họcvànhững phép toán thực
hiệntrênmôhìnhtoánhọc này
– Ví dụ: ADT List
z Dữ liệu: Các nút
z Các phép toán:
– Bổ sung mộtnútmới
– Loạibỏ mộtnút
– Tìm kiếmmột nút có giá trị cho trước
– …
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 4
Cấutrúcdữ liệu
z Cấu trúc dữ liệu
– Sử dụng để biểudiễnmôhìnhtoánhọc trong
ADT
– Việccàiđặtcáckiểudữ liệutrừutượng đòi hỏi
phảichọncáccấutrúcdữ liệu để biểudiễn
– Liên quan đếncáchthứctổ chứcvàtruynhập
các phầntử dữ liệu
– Ví dụ: ADT List
z Cài đặtsử dụng cấutrúcmảng đơngiản
z Cài đặtsử dụng cấu trúc con trỏ
Xây dựng chương trình giảibàitoán
– Lờigiảimột bài toán bao gồm
z Cấutrúcdữ liệu
z Thuật toán
– Xây dựng chương trình giải bài toán
z Tương tự như vòng đờicủaphầnmềm
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
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 6
Phân tích thờigianthựchiệngiảithuật
z Cách thức
– Xác định độ phụ thuộccủathời gian tính của
thuật toán vào kích thướccủadữ liệu đầuvào
– Các phương pháp thựchiện
z Phương pháp thực nghiệm
z Phương pháp phân tích dựatrênmôhìnhlýthuyết
Phân tích thờigianthựchiệngiảithuật
z Phương pháp thực nghiệm
– Cài đặtgiảithuậtbằng ngôn ngữ lậptrình
– Chạychương trình vớicácdữ liệu đầu vào khác nhau
– Đothờigianthựcthichương trình và đánh giá độ tăng
trưởng so vớikíchthướccủadữ liệu đầuvào
z Hạnchế:
– Sự hạnchế về số lượng và chấtlượng củamẫuthử
– Đòi hỏimôitrường kiểmthử (phầncứng và phầnmềm)
thống nhất, ổn định
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 7
Phân tích thờigianthựchiệngiảithuật
z Phương pháp lý thuyết
– Có khả năng xem xét dữ liệu đầuvàobấtkỳ
– Sử dụng để đánh giá các giảithuật mà không phụ thuộc
vào môi trường kiểmthử
– Sử dụng vớinhững mô tảởmứccaocủagiảithuật
z Thựchiệnphương pháp này cần quan tâm
– Ngôn ngữ mô tả giảithuật
– Xác định độ đothời gian tính
– 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
1
;
B
2
: S
2
;
…
B
n
: S
n
else S
n+1
end case;
Giả ngôn ngữ
z Câu lệnh lặp
z Vòng lặpvớisố lầnlặpbiếttrước
for i = m to n do S hoặc for i = n down to m do S
z Vớisố lầnlặp không biếttrước
while B do S hoặc repeat S until B
z Câu lệnh vào ra
– Đọcdữ liệuvào
read (<danh sách biến>);
Ghi dữ liệu
write (<danh sách biếnhoặc dòng ký tự>);
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 9
Giả ngôn ngữ
z Khai báo hàm
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
phântíchlỳ thuyết
z Phép toán cơ bản là phép toán có thểđượcthựchiện
vớithời gian bi chặnbởimộthằng số không phụ thuộc
vào kích thướcdữ liệu
– Thời gian tính củagiảithuật đượcxácđịnh bằng
cách đếmsố phép toán cơ bảnmàgiảithuậtthực
hiện
T
T
(
(
n
n
)
)
≈
≈
c
c
op*
op*
C
C
(
(
n
n
)
)
Cấu trúc dữ liệu và Giải thuật
Đỗ 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
if currentMax < A[i] then
currentMax = A[i]
3. return currentMax
End.
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 12
Phân tích thờigianthựchiệngiảithuật
– Thời gian tính tồinhất (Worst-case)
z Thờigiannhiềunhất để thựchiệnthuật toán vớimộtbộ
dữ liệu vào kích thướcn
– Thời gian tính tốtnhất (Best-case)
z Thờigianítnhất để thựchiệnthuật toán vớimộtbộ dữ
liệucũng vớikíchthướcn
– Thời gian tính trung bình (Average case)
z Thời gian trung bình cầnthiết để thựchiệnthuậttoán
trên tậphữuhạncácđầu vào kích thướcn
Phân tích thờigianthựchiệngiảithuật
Input
1 ms
2 ms
3 ms
4 ms
5 ms
ABCDEFG
worst-case
best-case
}
average-case?
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 13
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
– 3 log n + 5
z 3 log n + 5 là O(log n)
cần c > 0 và n0 ≥ 1 sao cho 3 log n + 5 ≤ c*log n vớin ≥ n0
ta xác định được c = 8 và n0 = 2
Ký hiệutiệmcậnBig -O
– Ví dụ: Giảithuật có T(n)
= 2n +10 thìcóđộ
phứctạplàO(n)
z 2n +10≤ cn
z (c − 2) n ≥ 10
z n ≥ 10/(c − 2)
z Lấy c = 3 và n
0
= 10
1
10
100
1,000
10,000
1 10 100 1,000
n
3n
2n+10
n
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 15
Ký hiệutiệmcậnBig -O
– Đồ thị mộtsố hàm cơ bản
Ký hiệutiệmcậnBig -O
– Big-O và độ tăng trưởng
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
2
(n) . Thời
gian thựchiệnP
1
và P
2
kế tiếp nhau là: T
1
(n) +
T
2
(n)
z Độ phứctạpcủa hai đoạnchương trình P
1
và
P
2
liên tụcnhaucóthể xác định là O(max(f(n),
g(n))) nếuT
1
(n) = O(f(n)) và T
2
(n) = O(g(n)).
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 17
Ký hiệutiệmcậnBig -O
– Qui tắcxácđịnh độ phứctạp
z Cấutrúclồng - Quy tắcnhân
– Cho 2 đoạnchương trình P
1
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
begin
P; {đoạngiảithuậtvớithời
gian thựchiệnT}
end
i: = 1
while (i <= n) do
begin
P; {đoạngiảithuậtvớithời
gian thựchiệnT}
i: = i+2;
end
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 18
Ký hiệutiệmcậnBig -O
i := 1
while (i<= n) do
begin
P; {đoạngiảithuậtvớithời
gian thựchiệnT}
i:= i *2;
end
i :=n
while (i >= 1) do
begin
P; {đoạngiảithuậtvớithời
gian thựchiệnT}
i:= i/2
end
Ký hiệutiệmcậnBig -O
i = 1
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
0
≥ 1saochoT(n) ≥ c*g(n) vớimọin ≥
n
0
t(n) ∈Ω(g(n))
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 20
Các khái niệmtiệmcậnkhác
– Big-Theta
z t(n) đựoc coi là Θ(g(n)) nếutồntại hai hằng số c’ > 0 và
c’’ > 0 và mộtsố nguyên n
0
≥ 1 sao cho c’*g(n) ≤ T(n) ≤
c’’*g(n) vớimọin ≥ n
0
t(n) ∈Θ(g(n))
Các khái niệmtiệmcậnkhác
– 5n
2
= Ω(n
2
)vớic = 5 vàn
0
= 1
– 5n
2
= Ω(n) với c = 1 và n
0
= 1
– 5n
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
| 1/21
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

Cấu trúc dữ liệu và Giải thuật
Cấu trúc dữ liệu và Giải thuật
Chương I: Các kiến thức cơ bản
Các kiến thức cơ bản Nội dung Các khái niệm Giải thuật Cấu trúc dữ liệu Phân tích giải thuật Giả ngôn ngữ
Thời gian thực hiện giải thuật
Đánh giá độ phức tạp sử dụng tiệm cận
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 1
Cấu trúc dữ liệu và Giải thuật Giải thuật
– Một thủ tục bao gồm một dãy hữu hạn các bước
cần thực hiện để thu được đầu ra cho đầu vào
cho trước của một bài toán Giải thuật
z Đặc trưng của giải thuật – Đầu vào – Đầu ra – Tính hữu hạn – Tính hiệu quả – Tính xác định
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 2
Cấu trúc dữ liệu và Giải thuật
Giải thuật và Chương trình
Chương trình là một thể hiện của Giải thuật trong một
ngôn ngữ lập trình nào đó Cấu trúc dữ liệu
z Kiểu dữ liệu trừu tượng (Abstract Data Type)
– Là mô hình toán học và những phép toán thực
hiện trên mô hình toán học này – Ví dụ: ADT List z Dữ liệu: Các nút z Các phép toán: – Bổ sung một nút mới – Loại bỏ một nút
– Tìm kiếm một nút có giá trị cho trước – …
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 3
Cấu trúc dữ liệu và Giải thuật Cấu trúc dữ liệu z Cấu trúc dữ liệu
– Sử dụng để biểu diễn mô hình toán học trong ADT
– Việc cài đặt các kiểu dữ liệu trừu tượng đòi hỏi
phải chọn các cấu trúc dữ liệu để biểu diễn
– Liên quan đến cách thức tổ chức và truy nhập các phần tử dữ liệu – Ví dụ: ADT List
z Cài đặt sử dụng cấu trúc mảng đơn giản
z Cài đặt sử dụng cấu trúc con trỏ
Xây dựng chương trình giải bài toán
– Lời giải một bài toán bao gồm z Cấu trúc dữ liệu z Thuật toán
– Xây dựng chương trình giải bài toán
z Tương tự như vòng đời của phần mềm z Gồm các bước
– Thu thập yêu cầu: Hiểu rõ đầu vào và kết quả đầu ra
– Thiết kế : Xây dựng giải thuật, bỏ qua các chi tiết về cách thức
cài đặt dữ liệu hay các phương thức, tập trung vào các bước xử lý
– Phân tích : Tìm, so sánh với giải thuật khác
– Cài đặt: Xây dựng chương trình, quan tâm đến cách thức tổ
chức, biểu diễn và cài đặt các phương thức
– Kiểm thử : Bao gồm chứng minh tính đúng đắn của chương
trình, kiểm thử các trường hợp , tìm, sửa lỗi
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 4
Cấu trúc dữ liệu và Giải thuật
Thuật toán và độ phức tạp
– Đánh giá lượng tài nguyên các loại mà một giải thuật đã sử dụng.
z Giải thuật này thực hiện trong thời gian thế nào Æ
Phân tích về thời gian thực hiện giải thuật
z Giải thuật này sử dụng bao nhiêu bộ nhớ Æ Phân tích
độ không gian nhớ mà giải thuật (chương trình) cần có.
Phân tích thời gian thực hiện giải thuật
– Mục tiêu của việc xác định thời gian thực hiện một giải thuật:
z Để ước lượng một chương trình sẽ thực hiện trong bao lâu
z Để ước lượng kích thước dữ liệu đầu vào lớn nhất có thể cho một giải thuật
z Để so sánh hiệu quả của các giải thuật khác nhau, từ đó
lựa chọn ra một giải thuật thích hợp cho một bài toán
z Để giúp tập trung vào đoạn giải thuật được thực hiện với thời gian lớn nhất
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 5
Cấu trúc dữ liệu và Giải thuật
Phân tích thời gian thực hiện giải thuật z Cách thức
– Xác định độ phụ thuộc của thời gian tính của
thuật toán vào kích thước của dữ liệu đầu vào
– Các phương pháp thực hiện
z Phương pháp thực nghiệm
z Phương pháp phân tích dựa trên mô hình lý thuyết
Phân tích thời gian thực hiện giải thuật
z Phương pháp thực nghiệm
– Cài đặt giải thuật bằng ngôn ngữ lập trình
– Chạy chương trình với các dữ liệu đầu vào khác nhau
– Đo thời gian thực thi chương trình và đánh giá độ tăng
trưởng so với kích thước của dữ liệu đầu vào z Hạn chế:
– Sự hạn chế về số lượng và chất lượng của mẫu thử
– Đòi hỏi môi trường kiểm thử (phần cứng và phần mềm) thống nhất , ổn định
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 6
Cấu trúc dữ liệu và Giải thuật
Phân tích thời gian thực hiện giải thuật z Phương pháp lý thuyết
– Có khả năng xem xét dữ liệu đầu vào bất kỳ
– Sử dụng để đánh giá các giải thuật mà không phụ thuộc
vào môi trường kiểm thử
– Sử dụng với những mô tả ở mức cao của giải thuật
z Thực hiện phương pháp này cần quan tâm
– Ngôn ngữ mô tả giải thuật
– Xác định độ đo thời gian tính
– Một cách tiếp cận để khái quát hóa độ phức tạp về thời gian
Mô tả giải thuật – Giả ngôn ngữ
z Giả ngôn ngữ (Pseudo-code)
– Mô tả mức khái quát cao được sử dụng trong diễn tả giải thuật
Giả ngôn ngữ = Cấu trúc lập trình + Ngôn ngữ tự nhiên Algorithm arrayMax(A,n)
Input: Mảng chứa n phần tử là số nguyên
Output: Phần tử lớn nhấ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.
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 7
Cấu trúc dữ liệu và Giải thuật Giả ngôn ngữ
– Các cấu trúc lập trình trong giả ngôn ngữ
z Câu lệnh gán: V = E hoặc V Å E
z Cấu trúc điều khiển:
– if B then S [else S ] 1 2 – Case B : S ; 1 1 B : S ; 2 2 … B : S n n else Sn+1 end case; Giả ngôn ngữ z Câu lệnh lặp
z Vòng lặp với số lần lặp biết trước
for i = m to n do S hoặc for i = n down to m do S
z Với số lần lặp không biết trước
while B do S hoặc repeat S until B z Câu lệnh vào ra – Đọc dữ liệu vào read (); Ghi dữ liệu write ();
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 8
Cấu trúc dữ liệu và Giải thuật Giả ngôn ngữ z Khai báo hàm Function () Begin
return (giá trị) End
z Gọi hàm: Hàm được gọi bằng tên hàm cùng danh sách
giá trị tham số thực sự, nằm trong biểu thức Giả ngôn ngữ Function AVERAGE(A,n) Begin
{A là một mảng gồm n phần tử là số nguyên. Giải thuật trả ra giá trị
trung bình của các giá trị trong mảng} 1. sum = 0;
2. {Duyệt mảng} for I = 1 to n do sum = sum + A[i]; 3. average = sum/n 4. return(average) End.
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 9
Cấu trúc dữ liệu và Giải thuật Giả ngôn ngữ – Khai báo thủ tục Procedure () Begin End
– Thủ tục được gọi bằng cách sử dụng câu lệnh Call ()
Phân tích thời gian thực hiện giải thuật
– Độ đo thời gian tính sử dụng trong phương pháp phân tích lỳ thuyết
z Phép toán cơ bản là phép toán có thể được thực hiện
với thời gian bi chặn bởi một hằng số không phụ thuộc
vào kích thước dữ liệu
– Thời gian tính của giải thuật được xác định bằng
cách đếm số phép toán cơ bản mà giải thuật thực hiện
T(n) ≈ cop*C(n)
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 10
Cấu trúc dữ liệu và Giải thuật
Phân tích thời gian thực hiện giải thuật
– Các phép toán cơ bản thường dùng
z Gán giá trị cho biến số z Gọi hàm hay thủ tục
z Thực hiện các phép toán số học z Tham chiếu vào mảng z Trả kết quả
z Thực hiện các phép so sánh
Phân tích thời gian thực hiện giải thuật
– Dòng 1: 2 phép toán cơ bản
Function ARRAY-MAX(A,n)
– Dòng 2: phép gán giá trị đầu
Đâu vào : mảng A gồm n phần tử.
cho i, phép so sánh i < n
Đầu ra: phần tử lớn nhất trong được thực hiện n lần mảng
– Thân vòng lặp thực hiện n-1 Begin
lần, trong thân, tối thiểu phải 1. currentMax = A[0]
thực hiện phép so sánh (2 phép 2. for i = 1 to n-1 do if currentMax < A[i] then
toán cơ bản) , tăng i lên 1 (2 phép currentMax = A[i]
toán cơ bản) tối đa phải có thêm
phép gán (2 phép toán cơ bản) 3. return currentMax
– Dòng 3: 1 phép toán cơ bản End.
Tổng số phép toán cơ bản trong
Trường hợp xấu nhất : 7n-2
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 11
Cấu trúc dữ liệu và Giải thuật
Phân tích thời gian thực hiện giải thuật
– Thời gian tính tồi nhất (Worst-case)
z Thời gian nhiều nhất để thực hiện thuật toán với một bộ
dữ liệu vào kích thước n
– Thời gian tính tốt nhất (Best-case)
z Thời gian ít nhất để thực hiện thuật toán với một bộ dữ
liệu cũng với kích thước n
– Thời gian tính trung bình (Average case)
z Thời gian trung bình cần thiết để thực hiện thuật toán
trên tập hữu hạn các đầu vào kích thước n
Phân tích thời gian thực hiện giải thuật 5 ms worst-case 4 ms }average-case? 3 ms best-case 2 ms 1 ms A B C D E F G Input
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 12
Cấu trúc dữ liệu và Giải thuật
Phân tích thời gian thực hiện giải thuật
– Ví dụ : Tìm kiếm tuần tự một giá trị trên một mảng a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] 4 8 7 10 21 14 22 36 62 91 77 81
– Thời gian xấu nhất : n
– Thời gian tốt nhất : 1
– Thời gian trung bình: T(n) = ∑i.pi
trong đó pi là xác suất giá trị cần tìm xuất hiện tại
a[i]. pi = 1/n thì thời gian sẽ là (n+1)/2 Ký hiệu tiệm cận – Khái niệm Big-O
– Cho hàm số t(n) và g(n), ta nói rằng t(n) là O(g(n)) nếu tồn tại
2 hằng số nguyên dương c và n sao cho 0
t(n) ≤ cg(n) for n ≥ n0 t(n) thuộc O(g(n))
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 13
Cấu trúc dữ liệu và Giải thuật
Ký hiệu tiệm cận Big - O – 7n -2 z 7n-2 là O(n)
tìm c > 0 và n0 ≥ 1 sao cho 7n-2 ≤ c*n với n ≥ 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ơi n ≥ n0
điều này đúng với c = 4 và n0 = 21 – 3 log n + 5 z 3 log n + 5 là O(log n)
cần c > 0 và n0 ≥ 1 sao cho 3 log n + 5 ≤ c*log n với n ≥ n0
ta xác định được c = 8 và n0 = 2
Ký hiệu tiệm cận Big - O
– Ví dụ: Giải thuật có T(n)
= 2n + 10 thì có độ
phức tạp là O(n) 10,000 3n
z 2n + 10 ≤ cn
z (c − 2) n ≥ 10 1,000 2n+10
z n ≥ 10/(c − 2) n
z Lấy c = 3 và n = 10 0 100 10 1 1 10 100 1,000 n
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 14
Cấu trúc dữ liệu và Giải thuật
Ký hiệu tiệm cận Big - O
– Đồ thị một số hàm cơ bản
Ký hiệu tiệm cận Big - O
– Big-O và độ tăng trưởng
z Big-O là ký hiệu tiệm cận trên của một hàm
z Nếu ta có T(n) là O(g(n)) thì độ tăng trưởng của T(n)
không vượt quá độ tăng trưởng của g(n)
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 15
Cấu trúc dữ liệu và Giải thuật
Ký hiệu tiệm cận Big - O
– Qui tắc xác định độ phức tạp về thời gian
z Hàm thời gian T(n) của một đoạn của thuật toán là đa
thức bậc k thì T(n) là O(nk)
z nx = O(an), với bất kỳ x > 0 và a > 1
z log nx = O(log n), với x > 0
Ký hiệu tiệm cận Big - O
– Qui tắc xác định độ phức tạp
z Cấu trúc tuần tự - Qui tắc tổng
z Cho 2 đoạn của thuật toán P và P với thời gian 1 2
thực hiện tương ứng là T (n) và T (n) . Thời 1 2
gian thực hiện P và P kế tiếp nhau là: T (n) + 1 2 1 T (n) 2
z Độ phức tạp của hai đoạn chương trình P và 1
P liên tục nhau có thể xác định là O(max(f(n), 2
g(n))) nếu T (n) = O(f(n)) và T (n) = O(g(n)). 1 2
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 16
Cấu trúc dữ liệu và Giải thuật
Ký hiệu tiệm cận Big - O
– Qui tắc xác định độ phức tạp
z Cấu trúc lồng - Quy tắc nhân
– Cho 2 đoạn chương trình P và P với thời gian thực 1 2
hiện tương ứng là T (n) và T (n) . Thời gian thực hiện 1 2
P và P lồng vào nhau là: T (n)T (n) 1 2 1 2
– Độ phức tạp của hai đoạn chương trình P và P liên 1 2
tục nhau có thể xác định là O(f(n)*g(n)) nếu T (n) = 1 O(f(n)) và T (n) = O(g(n)). 2
Ký hiệu tiệm cận Big - O for i = 1 to n begin
P; {đoạn giải thuật với thời gian thực hiện T} end i: = 1 while (i <= n) do begin
P; {đoạn giải thuật với thời gian thực hiện T} i: = i+2; end
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 17
Cấu trúc dữ liệu và Giải thuật
Ký hiệu tiệm cận Big - O i := 1 while (i<= n) do begin
P; {đoạn giải thuật với thời gian thực hiện T} i:= i *2; end i :=n while (i >= 1) do begin
P; {đoạn giải thuật với thời gian thực hiện T} i:= i/2 end
Ký hiệu tiệm cận Big - O i = 1 while (i <= n) do begin j := 1 ; while (j <= n) do begin
P ; {đoạn giải thuật với thời gian thực hiện T} j := j × 2; end i =: i + 1; end
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 18
Cấu trúc dữ liệu và Giải thuật
Ký hiệu tiệm cận Big - 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ệm tiệm cận khác - Big- Omega
z t(n) được coi là Ω(g(n)) nếu tồn tại một hằng số c >0 và
một số nguyên n ≥ 1 sao cho T(n) ≥ c*g(n) với mọi n ≥ 0 n0 t(n) ∈ Ω(g(n))
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 19
Cấu trúc dữ liệu và Giải thuật
Các khái niệm tiệm cận khác – Big-Theta
z t(n) đựoc coi là Θ(g(n)) nếu tồn tại hai hằng số c’ > 0 và
c’’ > 0 và một số nguyên n ≥ 1 sao cho c’*g(n) ≤ T(n) ≤ 0
c’’*g(n) với mọi n ≥ n0 t(n) ∈ Θ(g(n))
Các khái niệm tiệm cận khác
– 5n2 = Ω(n2) với c = 5 và n0 = 1
– 5n2 = Ω(n) với c = 1 và n0 = 1
– 5n2 = Θ(n2) với c = 5 và n0 = 1
– 3 log(n) + log (log n) = Ω(log n) với c = 3 và n0 = 2
Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN 20