BÀI GI
Ả
NG
CẤU TRÚC DỮLIỆU
ThS. Nguyễn ThịThúy Loan
6/8/2010 Nguyễn ThịThúy Loan 2
Cách đánh giá
Thực hành: 30%
Bài tập: 20%
Lý thuyết: 50%
6/8/2010 Nguyễn ThịThúy Loan 3
Tài liệu tham khảo
1. Bài giảng: ThS. Nguyễn Hà Giang
2. Cấu trúc dữliệu & giải thuật, Dương Anh Đức, Trần
Hạnh Nhi, NXB ĐHQG Tp.HCM, 2008.
3. Cấu trúc dữliệu, Nguyễn Trung Trực, ĐHBK, 1992.
4. Giải thuật & lập trình, Lê Minh Hoàng, ĐHSPHN,
1999-2002.
5. Cấu trúc dữliệu + giải thuật = chương trình, Nguyễn
Quốc Cường – Hoàng Đức Hải, NXB Giáo dục.
6. Fundamentals of Data Structures, Ellis Horowitz,
Sartaj Sahni.
6/8/2010 Nguyễn ThịThúy Loan 4
NỘI DUNG CHƯƠNG TRÌNH
Độ phức tạp thuật toán.
Tìm kiếm và sắp xếp.
Danh sách liên kết.
Stack & Queue.
Cây.
ĐỘPHỨC TẠP THUẬT
TOÁN
ThS. Nguyễn ThịThúy Loan
Chương I
6/8/2010 Nguyễn ThịThúy Loan 6
NỘI DUNG
I. ĐO THỜI GIAN
II. DỰA VÀO ĐỘ LỚN CỦA DỮLIỆU
III. MỘT SỐCÔNG THỨC THƯỜNG DÙNG
IV. CÁCH TÍNH ĐỘ PHỨC TẠP
6/8/2010 Nguyễn ThịThúy Loan 7
Đo thời gian
6/8/2010 Nguyễn ThịThúy Loan 8
Dựa vào độlớn của dữliệu
Gọi t(n) là thời gian thực hiện của thuật toán
A (thông thường là chu kỳcủa CPU), t(n)
sẽlà một trong các loại:
a. O(1): độ phức tạp là một hằng số.
VD: for (int i=1; i<= 10 ; i++)
printf (“%d”, i );
Phép so sánh: i = 1..10 và i =11 (để dừng) = 11.
Phép gán: i = 1 + (i = 1..10) = 11.
6/8/2010 Nguyễn ThịThúy Loan 9
Dựa vào độlớn của dữliệu
b. O(log2n): Tìm nhịphân.
c. O(√n): Kiểm tra một sốcó phải là số
nguyên tố?
VD: Kiểm tra sốnguyên tố, xét i=2 →(n/2),
nếu i là ước sốcủa n n không phải là
sốnguyên tố, ngược lại n là nguyên tố.
6/8/2010 Nguyễn ThịThúy Loan 10
Dựa vào độlớn của dữliệu
Nhận xét
Trừsố2, tất cảcác sốchẵn không phải
là sốnguyên tố.
Các sốlẻkhông có ước sốchẵn.
i là ước sốcủa n →(n/i) là ước sốcủa n.
6/8/2010 Nguyễn ThịThúy Loan 11
d. O(n): Độ phức tạp tuyến tính (áp dụng
duyệt mảng, dãy).
e. O(nlog2n): “thuật toán Logarit” (áp dụng
sắp xếp mảng).
f. O(nα)(α>1): đa thức.
g. O(2n), O(n!): mũ(áp dụng liệt kê tất cả
các tập con của tập gồm n phần tử).
Dựa vào độlớn của dữliệu
6/8/2010 Nguyễn ThịThúy Loan 12
Một sốcông thức thường dùng
n
i
nn
ib
12
)1(
.
n
i
na
1
1.


b
ai
b
i
a
i
Nbaab
1
1
1
)(1111
n
ai
aann
i
2
)11)(1()1(
2
1
22
2
)1(
n
i
nn
i
6/8/2010 Nguyễn ThịThúy Loan 13
n
i
nnn
ic
1
2
6
)12)(1(
.
n
ai
aaannn
i
6
)12)(1()12)(1(
2


n
i
n
i
nn
iid
1
22
2
1
3
4
)1(
.
Một sốcông thức thường dùng
6/8/2010 Nguyễn ThịThúy Loan 14
Cách tính độphức tạp
Ví dụ1: Cho thuật toán tính tổng như sau:
long Tong (int n)
{ long s = 0;
for (int i = 1 ; i <= n ; i ++)
s += i;
return s;
}
a. Tính độ phức tạp của thuật toán.
b. Cải tiến để thuật toán có độ phức tạp nhỏ hơn.
6/8/2010 Nguyễn ThịThúy Loan 15
Cách tính độphức tạp
GIẢI
a) Sốphép so sánh:
Sốphép gán:
Độ phức tạp là O(n).
n
i
n
1
111
n
i
n
1
22)11(11
6/8/2010 Nguyễn ThịThúy Loan 16
Cách tính độphức tạp
b) Thực chất là tính:
Cải tiến: long Tong (int n)
{ return (n * (n + 1))/2;
}
Không phép so sánh, không phép gán
O(1).
n
i
nn
is
12
)1(
6/8/2010 Nguyễn ThịThúy Loan 17
Cách tính độphức tạp
Vd2: Cho thuật toán sau:
long Tong (int n)
{ long s = 0;
for (int i = 1 ; i <= n ; i ++)
for (int j = i ; j<= n ; j ++)
s += j;
return s;
}
a. Tính độ phức tạp của thuật toán.
b. Cải tiến để thuật toán có độ phức tạp nhỏ hơn.
6/8/2010 Nguyễn ThịThúy Loan 18
Cách tính độphức tạp
Vd3: Cho thuật toán sau:
long Tong (int n)
{ long s = 0;
for (int i = 1 ; i <= n ; i ++)
for (int j = 1 ; j<= i*i ; j ++)
s += j;
return s;
}
a. Tính độ phức tạp của thuật toán.
b. Cải tiến để thuật toán có độ phức tạp nhỏ hơn.
TÌM KIẾM VÀ SẮP
XẾP
ThS. Nguyễn ThịThúy Loan
Chương II
Tham khảo bài giảng ThS. Nguyễn Hà Giang 6/8/2010 Nguyễn ThịThúy Loan 20
Nội dung trình bày
TÌM KIẾM
SẮP XẾP