Giáo trình Cấu trúc dữ liệu và Giải thuật - Chương 1: Thiết kế và phân tích - Đỗ Tuấn Anh

ầu: Lưu trở lại file
⇒Đã cô đọng
Thiết kế Topdown – Bước 3
zXử lý TT
{Đầu vào: Mảng lưu thông tin của các sinh viên
{Yêu cầu:
zTìm một sinh viên cho trước
zHiển thị thông tin của sinh viên
zCập nhật thông tin của sinh viên
zIn bản tổng kết
Thiết kế Topdown
Quản lý học bổng
Đọc file Xử lý TT Ghi file
Tìm SV Hiển thị
TT SV
Cập nhật 
TT SV
In bản 
tổng kết
Tìm theo 
Mã SV
Tìm theo 
HB
Tìm theo 
ĐiểmTB
2.2 Phương pháp tinh chỉnh từng bước 
(Stepwise Refinement)
zBan đầu giải thuật được trình bày ở dạng 
ngôn ngữ tự nhiên
zChi tiết hóa dần – tinh chỉnh hướng về
phía ngôn ngữ lập trình
zGiai đoạn trung gian – giả ngôn ngữ
Ngôn ngữ tự
nhiên
Giả ngôn ngữ Ngôn ngữ lập 
trình
Tinh chỉnh từng bước – Ví dụ
z Bài toán: “Sắp xếp một dãy n số nguyên theo 
thứ tự tăng dần”
zGiải thuật:
{Từ dãy số nguyên chưa được sắp xếp chọn ra số nhỏ
nhất và đặt vào đầu dãy đã được sắp xếp
{Loại số nguyên đó ra khỏi dãy chưa được sắp xếp
{Lặp lại cho đến khi dãy chưa được sắp xếp là rỗng
Ngôn ngữ tự nhiên
84 60 74 23 30 35 46 57 12 78
84 60 74 23 30 35 46 5712 78
12 23 30 35 46 57 7884 60 74
Tinh chỉnh từng bước – Ví dụ
zCấu trúc dữ liệu: 
{Dãy số ban đầu được lưu trữ trong một mảng 
một chiều
{Dãy đã sắp xếp sẽ được lưu trùng với dãy 
chưa sắp xếp
=> Giải thuật: Đặt số nhỏ nhất của lượt thứ i vào 
dãy đã sắp xếp = đổi chỗ với số thứ i trong dãy 
Tinh chỉnh từng bước – Ví dụ
zTinh chỉnh bước 1
for(i=0; i<n; i++) 
{
1. Xét từ ai đến an-1 để tìm số nhỏ nhất aj
2. Đổi chỗ ai và aj
}
Giả ngôn ngữ
Tinh chỉnh từng bước – Ví dụ
zGiải thuật 1: Xét từ ai đến an-1 để tìm số nhỏ nhất 
aj
{Coi ai là “số nhỏ nhất” ( j = i)
{So sánh “số nhỏ nhất” và ai+1, số nào nhỏ hơn thì coi là
“số nhỏ nhất” (nếu ai+1< aj thì j = i+1)
{Tiếp tục so sánh “số nhỏ nhất” với ai+2, ai+3,  an-1, an
{Xác định “số nhỏ nhất” bằng cách nắm được chỉ số của 
nó
z Tinh chỉnh bước 1
j = i;
for (k = i+1; k<n; k++)
if(ak < aj) j = k;
Tinh chỉnh từng bước – Ví dụ
zGiải thuật 2: Đổi chỗ ai và aj
{ Sử dụng một biến trung chuyển
zTinh chỉnh bước 2.2
tmp = ai;
ai = aj;
aj = tmp;
Tinh chỉnh từng bước
function SapXep(a, n)
/* a là mảng các số nguyên
n là số phần tử mảng */
{
for(i = 0; i<n; i++)
{
/* 1. Tìm số nhỏ nhất */
j = i;
for (k = i+1; k<n; k++) 
if(ak < aj) j = k+1;
/* 2. Đổi chỗ */
tmp = ai; ai = aj; aj = tmp;
}
}
3. Phân tích giải thuật
zTại sao cần phân tích giải thuật ?
{Viết một chương trình chạy thông là chưa đủ
{Chương trình có thể thực hiện chưa hiệu quả!
{Nếu chương trình chạy trên một tập dữ liệu lớn, 
thì thời gian chạy sẽ là một vấn đề cần lưu ý
Ví dụ: Bài toán lựa chọn
zCho một dãy gồm N số, hãy tìm phần tử
lớn thứ k, với k ≤ N.
zThuật toán 1:
(1) Đọc N số vào một mảng
(2) Sắp xếp mảng theo thứ tự giảm dần
(3) Trả lại phần tử ở vị trí thứ k
Ví dụ: Bài toán lựa chọn
zThuật toán 2:
(1) Đọc k phần tử đầu tiên vào mảng và sắp xếp 
chúng theo thứ tự giảm dần
(2) Mỗi phần tử còn lại chỉ đọc một lần
zNếu phần tử đó là nhỏ hơn phần tử thứ k, bỏ qua
zNgược lại, đặt nó vào vị trí phù hợp của mảng, đẩy 
phần tử hiện tại ra khỏi mảng.
(3) Phần tử tại vị trí thứ k là phần tử cần tìm.
84 60 74 23 30 35 46 57 12 78
Ví dụ: Bài toán lựa chọn
zThuật toán nào là tốt hơn khi
{N =100 và k = 100?
{N =100 và k = 1?
zĐiều gì sẽ xảy ra khi N = 1,000,000 và k = 
500,000?
zCòn có những thuật toán tốt hơn
Phân tích thuật toán
z Chúng ta chỉ phân tích những thuật toán đúng
zMột thuật toán là đúng?
{Nếu, với một dữ liệu đầu vào, thuật toán dừng và đưa 
ra kết quả đúng
z Thuật toán không đúng
{Có thể không dừng với một số dữ liệu đầu vào
{Dừng nhưng đưa ra kết quả sai
z Phân tích thuật toán
{Dự đoán lượng tài nguyên mà thuật toán yêu cầu
{Tài nguyên gồm
zBộ nhớ
zBăng thông giao tiếp
zThời gian tính – Thời gian thực hiện GT (thường là
quan trọng nhất)
Thời gian thực hiện giải thuật
zCác nhân tố ảnh hưởng đến thời gian tính
{Máy tính 
{Chương trình dịch
{Thuật toán được sử dụng
{Dữ liệu đầu vào của thuật toán
zGiá trị của dữ liệu ảnh hưởng đến thời gian tính
zThông thường, kích thước của dữ liệu đầu vào là
nhân tố chính quyết định thời gian tính
• VD với bài toán sắp xếp⇒ số phần tử sắp xếp
• VD bài toán nhân ma trận⇒ tổng số phần tử của 2 ma 
trận
Độ phức tạp về thời gian
Thuật toán A mất 2 phút để chạy với dữ liệu đầu vào X.
Thuật toán B mất 1 phút 45 giây để chạy với cùng dữ liệu X.
Liệu B có phải là thuật toán “tốt hơn” A? Không hẳn là như vậy
Chỉ kiểm tra với một bộ dữ liệu X.
Có thể với dữ liệu X này B chạy nhanh hơn A, 
nhưng với phần lớn các dữ liệu khác B chạy chậm hơn A. 
Thuật toán A bị ngắt bởi các tiến trình khác.
Phép đo cần phải không phụ thuộc vào máy.
Đo bằng cách đếm số các phép tính cơ sở
(như phép gán, so sánh, các phép tính số học, vv.)
Thuật toán B được chạy trên máy tính có cấu hình cao hơn.
Ví dụ
Thuật toán 1
Bài toán Tính tổng các số nguyên từ 1 đến n.
int sum = 0; 
for (int i = 1; i <= n; i++) 
sum = sum + i; 
Thuật toán 2
int sum = ((n+1)*n) / 2; 
Trường hợp tồi nhất / trung bình / tốt nhất
zThêi gian tÝnh tèt nhÊt: Thêi gian tèi 
thiÓu cÇn thiÕt ®Ó thùc hiÖn thuËt to¸n 
víi mäi bé dữ liÖu ®Çu vµo kÝch th-íc 
n. 
zThêi gian tÝnh tåi nhÊt: Thêi gian nhiÒu nhÊt 
cÇn thiÕt ®Ó thùc hiÖn thuËt to¸n víi mäi bé
d÷ liÖu ®Çu vµo kÝch th-íc n.
zThê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.
Thời gian tính phụ thuộc vào kích thước dữ
liệu đầu vào
Điều quan trọng đối với giải thuật là
mất bao nhiêu giây để chạy với dữ liệu đầu vào có kích thước n.
tốc độ thay đổi của thời gian tính khi n tăng.
Thuật toán có thời gian hằng số nếu thời gian chạy của nó là không
đổi khi kích thước dữ liệu thay đổi.
Thuật toán có thời gian tuyến tính nếu thời gian chạy của nó tỷ lệ
thuận với n. 
Thuật toán có thời gian tính hàm số mũ nếu thời gian chạy tăng
theo một hàm số mũ của n. 
Tỉ suất tăng trưởng
z Thiết lập một thứ tự tương đối cho các hàm với đầu 
vào n lớn
z ∃ c , n0 > 0 sao cho f(n) ≤ c g(n) khi n ≥ n0
z f(n) tăng không nhanh bằng g(n) khi n “lớn”
Khái niệm O-lớn
Một thuật toán là O(f(n))=g(n) nếu
tồn tại một hằng số C > 0 và số nguyên n0 sao cho thuật toán yêu
cầu không vượt quá C• g(n) phép tính có tất cả các dữ liệu đầu 
vào có kích thước n ≥ n0.
Thuật toán 1 cần 4n + 3 phép tính.
int sum = 0; 
for (int i = 1; i <= n; i++) 
sum = sum + i; 
Khái niệm O-lớn
Cg(n)
n0
f(n)
f(n) = O(g(n))
Hàm g(n) trong O(g(n)) là hàm để so sánh với các thuật toán khác
Nó không quan tâm khi dữ liệu đầu vào có kích thước nhỏ
O-lớn quan tâm đến tỉ suất tăng trưởng của thời gian tính khi n→ ∞. 
Nhắc lại một số hàm logarit
xdx
xd
aaa
na
aba
a
bb
baab
abbx
bbb
an
b
m
m
a
x
a
1ln
log)(loglog
loglog
log
loglog
logloglog
log
loglog
=
≠=
=
=
=
+=
=⇔=
Một số quy tắc của O-lớn
O-lớn bỏ qua các giá trị có bậc thấp hơn.
Các bậc thấp hơn thường được tính bởi
các bước khởi tạo
phép tính đơn giản
O-lớn không tính đến hệ số nhân
Đây thường là khái niệm phụ thuộc vào máy tính
Không cần chỉ ra cơ số của hàm logarit
Hoàn toàn có thể thay đổi cơ số của hàm logarit bằng 
cách nhân với một hằng số
Thứ hạng của O-lớn
O(1)
O(log n)
O(n)
O(n log n)
O(n ) 2
O(n log n) 2
O(n ) 3
O(2 ) n
O(n!)
thời gian hằng số
thời gian logarit
thời gian tuyến tính
bình phương
mũ 3
hàm số mũ n
giai thừa
nhanh nhất
chậm nhất
Sự tăng trưởng của hàm?
Thuật toán 1 2 3 4 5
Thời gian (ms.) 33n 46 n log n 13n 3.4n 22 3 n
KT đầu vào (n) Thời gian thực tế
10 .00033 sec. .0015s .0013s .0034s .001s
100 .003s .03s .13s 3.4s 4 • 10 yr.
1,000 .033s .45s 13s .94hr
10,000 .33s 6.1s 22 min 39 days
100,000 3.3s 1.3 min 1.5 days 108 yr.
T/g cho phép Kích thước dữ liệu tối đa 
1 sec. 30,000 2,000 280 67 20
1 min. 1,800,000 82,000 2,200 260 26
Khái niệm Omega-lớn
z ∃ c , n0 > 0 sao cho f(n) ≥ c g(n) khi n ≥ n0
z f(n) tăng không chậm hơn g(n) với N “lớn”
Khái niệm Omega-lớn
z f(n) = Ω(g(n))
zTồn tại một hằng số dương c và n0 sao 
cho
f(n) ≥ c g(n) khi n ≥ n0
zTỉ suất tăng của f(n) thì lớn hơn hoặc bằng 
tỉ suất tăng của g(n).
Khái niệm Theta-lớn
z Tỉ suất tăng của f(n) bằng tỉ suất tăng của g(n)
Theta-lớn
z f(n) = Θ(g(n)) nếu và chỉ nếu
f(n) = O(g(n)) and f(n) = Ω(g(n))
z Tỉ suất tăng của f(n) bằng tỉ suất tăng của g(n)
z Ví dụ: f(N)=N2 , 
z Theta-lớn là cận chặt nhất có thể.
Một số quy tắc
zNếu T(N) là một đa thức bậc k, thì
T(N) = Θ(Nk).
zVới các hàm logarit,
T(logm N) = Θ(log N).
Ví dụ:
z t(n) = 90 n2 + 9n + 9
{ Do 
60n2 + 9n + 9 ≤ 60 n2 + 9n2 + n2 = 70 n2 với mọi n ≥ 1,
Chọn C1 = 70
60n2 + 9n + 9 = O(n2).
{ Do 
60n2 + 9n + 9 ≥ 60 n2 với mọi n ≥ 1,
Chọn C2=60
60n2 + 9n + 9 = Ω (n2).
{ Do 
60n2 + 9n + 9 = O(n2) và 60n2 + 9n + 9 = Ω (n2) 
nên 
60n2 + 9n + 9 = Θ(n2). 
Quy tắc L' Hopital
z Quy tắc L' Hopital
{Nếu và
thì =
z Quyết định tỉ suất tăng tương đối (sử dụng quy tắc L' 
Hopital khi cần thiết)
{Tính
{0: f(N) = O(g(N)) và f(N) k phải là Θ(g(N))
{Hằng số ≠ 0: f(N) = Θ(g(N))
{∞: f(N) = Ω(f(N)) và f(N) k phải là Θ(g(N))
{không xác định: không có mối quan hệ gì
)(
)(lim
Ng
Nf
n ∞→ )(
)(lim
Ng
Nf
n ′
′
∞→
∞=∞→ )(lim Nfn ∞=∞→ )(lim Ngn
)(
)(lim
Ng
Nf
n ∞→
Xác định độ phức tạp về thời gian
Nếu T1(n) = O(f(n)) and T2(n) = O(g(n)) thì
zQuy tắc tổng:
T1(n) + T2(n) = O(f(n)+g(n)) 
= max(O(f(n)),O(g(n)))
= O(max(f(n), g(n)))
zQuy tắc nhân:
T1(n) * T2(n) = O(f(n) * g(n))
Xác định độ phức tạp thời gian
zVới vòng lặp
{là thời gian chạy của các câu lệnh bên trong 
vòng lặp (kể cả lệnh kiểm tra điều kiện) nhân 
với số lần lặp.
zCác vòng lặp lồng nhau
{là thời gian chạy của câu lệnh nhân với tích 
của các kích thước của tất cả vòng lặp.
Xác định độ phức tạp thời gian
zCác câu lệnh kế tiếp
{Thực hiện tính tổng
{O(N) + O(N2) = O(N2)
z If S1
Else S2
{ thời gian của lệnh kiểm tra điều kiện + thời gian tính lớn 
hơn trong S1 và S2.