Bài giảng Cấu trúc dữ liệu và giải thuật - Các khái niệm cơ bản - Văn Chí Nam

Giảng viên: 
Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
2 
 Kenneth H.Rosen, Toán rời rạc ứng dụng trong 
Tin học, ltb. 5, nxb. Giáo Dục, 2007, tr. 131 -
143. 
 Mark A. Weiss, Data Structures & Algorithm 
Analysis in C++, 2nd edition, Addision Wesley, 
1998, p. 41 – 67. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
3 
Tổng quan về cấu trúc dữ liệu 
Tiêu chuẩn đánh giá thuật toán 
Độ tăng của hàm 
Độ phức tạp thuật toán 
Các phương pháp đánh giá độ phức tạp 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
4 
 According to Peter J. Denning, the fundamental 
question underlying computer science is, "What 
can be (efficiently) automated?“ 
[Wikipedia.org, tháng 9 – 2009] 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
5 
 Để giải quyết nhu cầu tự động hóa, nhu cầu căn 
bản của Khoa học Máy tính, các nhà khoa học máy 
tính phải tạo ra sự trừu tượng hóa về những bài 
toán trong thế giới thực, 
 để người sử dụng máy tính có thể hiểu được 
 và có thể biểu diễn và xử lý được bên trong máy tính. 
 Ví dụ: 
 Mô hình hóa việc biểu diễn cầu thủ bóng đá 
 Mô hình hóa mạch điện 
  
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
6 
 Thông thường, tìm ra một sự trừu tượng hóa 
thường rất khó, vì: 
Giới hạn về khả năng xử lý của máy. 
 Phải cung cấp cho máy một mô hình về thế giới đến 
mức chi tiết như những gì con người có, không chỉ là 
sự kiện mà còn cả các nguyên tắc và mối liên hệ. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
7 
 Sự trừu tượng hóa ở đây được sử dụng là sự đơn 
giản hóa, thay thế một tình huống phức tạp và 
nhiều chi tiết trong thế giới thực bằng một mô hình 
dễ hiểu để chúng ta có thể giải quyết được bài toán 
trong đó. 
 Có thể hiểu là chúng ta loại bớt những chi tiết có 
tác dụng rất ít hoặc không có tác dụng gì đối với lời 
giải của bài toán 
-> tạo ra một mô hình cho phép chúng ta giải quyết 
với bản chất của bài toán. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
8 
 Kiểu dữ liệu (của biến) xác định tập các giá trị 
mà biến có thể chấp nhận và các phép toán có 
thể thực hiện trên các giá trị đó. 
 Ví dụ: 
Kiểu dữ liệu kiểu số nguyên, 
Kiểu dữ liệu kiểu số thực, 
Kiểu dữ liệu ký tự. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
9 
 Kiểu dữ liệu sơ cấp là kiểu dữ liệu mà giá trị 
của nó là đơn nhất. 
 Ví dụ: Trong ngôn ngữ lập trình C chuẩn, kiểu int gọi 
là kiểu sơ cấp vì kiểu này bao gồm các số nguyên từ 
-32768 đến 32767 và các phép toán +, -, *, /, % 
 Mỗi ngôn ngữ đều có cung cấp sẵn các kiểu dữ 
liệu cơ bản (basic data type) dùng như những 
thành phần cơ sở để tạo nên các dữ liệu có cấu 
trúc phức tạp hơn. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
10 
 Kiểu dữ liệu có cấu trúc (Structured Data Type): 
là kiểu dữ liệu mà giá trị của nó là sự kết hợp 
các giá trị khác. 
 Ví dụ: 
Kiểu dữ liệu có cấu trúc gồm các giá trị giao dịch của 
một phiên giao dịch (chứng khoán). 
Kiểu dữ liệu mô tả lí lịch sinh viên. 
 
 Còn được gọi là kiểu dữ liệu tổ hợp. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
11 
 Kiểu dữ liệu trừu tượng (abstract data type - ADT) 
bao gồm tập hợp các dữ liệu và các thao tác trên 
các dữ liệu đó. 
 Cần phải chú ý nhiều về đó là thủ tục hoặc dữ liệu GÌ thay 
vì chú ý là LÀM SAO cài đặt hoặc hiện thực chúng. 
 Ví dụ: 
 Kiểu dữ liệu trừu tượng PhanSo. 
 Kiểu dữ liệu trừu tượng Ngay. 
 Kiểu dữ liệu trừu tượng Gio. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
12 
 Cấu trúc dữ liệu là các thành phần của ngôn 
ngữ lập trình dùng để lưu giữ dữ liệu trong kiểu 
dữ liệu trừu tượng. 
Ví dụ mảng (array), tập tin (file), danh sách liên kết 
(linked list), cây nhị phân, 
 Các cấu trúc dữ liệu được chọn phải có khả 
năng biểu diễn được tập input và output của bài 
toán cần giải. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
13 
 Mặc dù tên nghe có vẻ giống nhau, “danh sách” 
và “danh sách liên kết” là những khái niệm khác 
nhau. 
Danh sách là kiểu dữ liệu trừu tượng (ADT). 
Danh sách liên kết là một cấu trúc dữ liệu. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
14 
 Big-O. 
 Một số kết quả Big-O quan trọng. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
15 
 Khái niệm Big-O lần đầu tiên được đưa ra bởi nhà 
toán học người Đức Paul Bachmann vào năm 
1892. 
 Big-O được trở nên phổ biến hơn nhờ nhà toán học 
Landau. Do vậy, Big-O cũng còn được gọi là ký 
hiệu Landau, hay Bachmann-Landau. 
 Donald Knuth được xem là người đầu tiên truyền 
bá khái niệm Big-O trong tin học từ những năm 
1970. Ông cũng là người đưa ra các khái niệm Big-
Omega và Big-Theta. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
16 
 Cho f và g là hai hàm số từ tập các số nguyên 
hoặc số thực đến số thực. Ta nói f(x) là O(g(x)) 
nếu tồn tại hằng số C và k sao cho: 
 |f(x)| ≤ C |g(x)| với mọi x > k 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
17 
 Cho f và g là hai hàm số từ tập các số nguyên 
hoặc số thực đến số thực. Ta nói f(x) là O(g(x)) 
nếu tồn tại hằng số C và k sao cho: 
 |f(x)| ≤ C |g(x)| với mọi x > k 
• Ví dụ, hàm f(x) = x2 + 3x + 2 là O(x2). 
 Thật vậy, khi x > 2 thì x < x2 và 2 < 2x2 
 Do đó x2 + 3x + 2 < 6x2. 
 Nghĩa là ta chọn được C = 6 và k = 2. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
18 
 Big-O giúp xác định được mối quan hệ giữa 
f(x) và g(x), trong đó g(x) thường là hàm ta đã 
biết trước. Từ đó ta xác định được sự tăng 
trưởng của hàm f(x) cần khảo sát. 
 C và k trong định nghĩa của khái niệm Big-O 
được gọi là bằng chứng của mối quan hệ f(x) 
là O(g(x)). 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
19 
 Big-O phân hoạch được các hàm với các độ 
tăng khác nhau. Nếu có hai hàm f(x) và g(x) sao 
cho f(x) là O(g(x)) và g(x) là O(f(x)) thì ta nói hai 
hàm f(x) và g(x) đó là có cùng bậc. 
 Ví dụ: f(x) 7x2 là O(x2) (chọn k = 0, C = 7). 
 Do vậy 7x2 và x2 + 3x + 2, và x2 là 3 hàm có 
cùng bậc. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
20 
 Lưu ý: 7x2 cũng là O(x3) nhưng x3 không là 
O(7x2). 
 Thật vậy: Nếu x3 là O(7x2) thì ta phải tìm được C 
và k sao cho 
|x3| ≤ C|7x2|  x ≤ 7C với mọi x > k. 
 Điều này không thể xảy ra vì không thể tìm 
được k và C nào như vậy. 
 Do vậy, trong quan hệ f(x) là O(g(x)), hàm g(x) 
thường được chọn là nhỏ nhất có thể. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
21 
1. Hàm đa thức: 
 f(x) = anx
n + an-1x
n-1 +  + a1x + a0 
 Khi đó f(x) là O(xn). 
2. Hàm giai thừa: 
 f(n) = n! là O(nn) 
3. Logarit của hàm giai thừa: 
 f(n) = logn! là O(nlogn) 
4. Hàm điều hòa 
 H(n) = 1 + 1/2 + 1/3 + .. + 1/n là O(logn) 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
22 
 Nếu f(n) là O(g(n)) thì c.f(n) là O(g(n)) với c là 
hằng số. 
 Cho f1(x) là O(g1(x)) và f2(x) là O(g2(x)). 
Khi đó: 
Quy tắc tổng: 
(f1(x)+f2(x)) là O(max(|g1(x)|, |g2(x)|)) 
Quy tắc nhân: 
(f1(x) * f2(x)) là O(g1(x) * g2(x)). 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
23 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
24 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
25 
 Nói như sau là không chính xác: 
f(n) = O(g(n)) 
 Nói như dưới đây lại càng không chính xác: 
f(n) > O(g(n)) 
 Chỉ sử dụng như sau: 
f(n) là O(g(n)), hoặc 
f(n) với bậc O(g(n)) 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
26 
 Hãy cho biết các hàm số sau đây là Big-O của 
hàm số nào: 
 8n3 – 9n 
 7log2n + 20 
 7log2n + n 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
27 
Cấu 
trúc dữ 
liệu 
Giải 
thuật 
Chương 
trình 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
28 
 Tốc độ thực thi. 
 Tính chính xác. 
 Đơn giản, dễ hiểu, dễ bảo trì. 
 Mức phổ dụng 
  
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
29 
 Thời gian giải quyết một bài toán phụ thuộc vào 
nhiều yếu tố: 
 Tốc độ thực thi của máy tính (phần cứng lẫn 
phần mềm). 
 Tài nguyên (ví dụ: bộ nhớ). 
 Thuật toán. 
 Làm thế nào đánh giá được thời gian thực thi 
hiệu quả? 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
30 
 Đánh giá thời gian thực hiện dựa trên những 
phép toán quan trọng như: 
 Phép so sánh 
 Phép gán 
 Đánh giá bằng cách tính số lượng các phép 
toán quan trọng theo độ lớn của dữ liệu. 
 Từ đó, thời gian thực hiện của một thuật toán có 
thể được đánh giá theo một hàm phụ thuộc vào 
độ lớn đầu vào. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
31 
 Bước 1. Gán tổng = 0. Gán i = 0. 
 Bước 2. 
 Tăng i thêm 1 đơn vị. 
 Gán Tổng = Tổng + i 
 Bước 3. So sánh i với 10 
Nếu i < 10, quay lại bước 2. 
Ngược lại, nếu i ≥ 10, dừng thuật toán. 
 Số phép gán của thuật toán là bao nhiêu? Số phép 
so sánh là bao nhiêu? 
Gán: 2n + 2, So sánh: n 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
32 
Khi nào thuật 
toán cho lời giải 
thỏa đáng? 
Phải luôn cho 
đáp số đúng. 
Phải hiệu quả 
(độ phức tạp 
tính toán) 
Độ phức tạp 
thời gian 
Độ phức tạp 
của các thuật 
toán không đổi 
Trường hợp xấu 
nhất 
Trường hợp 
trung bình 
Trường hợp tốt 
nhất 
Độ phức tạp 
không gian 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
33 
 Thuật toán: 
 B1. Đặt giá trị cực đại tạm thời 
bằng số nguyên đầu tiên trong dãy. 
 B2. So sánh số nguyên tiếp sau với 
giá trị cực đại tạm thời. Nếu nó lớn 
hơn giá trị cực đại tạm thời thì đặt 
cực đại tạm thời bằng số nguyên đó. 
 B3. Lặp lại B2 nếu còn các số nguyên 
trong dãy. 
 B4. Dừng khi không còn số nguyên nào 
nữa trong dãy. Cực đại tạm thời 
chính là số nguyên lớn nhất của dãy. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
34 
 Vì phép sơ cấp sử dụng trong thuật toán là phép so 
sánh, nên phép so sánh được dùng làm thước đo 
độ phức tạp. 
 Tại mỗi số hạng, ta thực hiện 2 phép so sánh, 1 
phép xem đã hết dãy hay chưa và 1 phép so với 
cực đại tạm thời. 
 Vì hai phép so sánh được dùng từ số hạng thứ 2 
đến n, và thêm 1 phép so sánh nữa để ra khỏi vòng 
lặp, nên ta có chính xác 2(n-1) + 1 = 2n – 1 phép so 
sánh. 
 Do vậy, độ phức tạp của thuật toán là O(n). 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
35 
 Bước 1. Gán i = 1. 
 Bước 2. Trong khi i ≤ n và x ai 
thì tăng i thêm 1. 
 while (i ≤ n and x ai) 
 i = i + 1 
 Bước 3. 
 Nếu i ≤ n, trả về giá trị là i. 
 Ngược lại, i > n, trả về giá trị 0 
cho biết không tìm được x trong dãy 
a. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
36 
 Số phép so sánh dùng làm thước đo. 
 Ở mỗi bước của vòng lặp, thực hiện 2 phép so 
sánh. 
 Cuối vòng lặp, thực hiện 1 phép so sánh. 
 Như vậy, nếu x = ai, số phép so sánh thực hiện 
là (2i +1). 
 Trong trường hợp xấu nhất, không tìm được x 
thì tổng số phép so sánh là 2n + 2. 
 Từ đó, thuật toán tìm kiếm tuần tự đòi hỏi tối đa 
O(n) phép so sánh. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
37 
 Trong trường hợp tốt nhất, ta bắt gặp x ngay 
phần tử đầu tiên nên chỉ cần tốn 3 phép so 
sánh. 
 Khi đó, ta nói thuật toán tìm kiếm tuần tự đòi hỏi 
ít nhất O(1) phép so sánh. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
38 
 Nếu x là số hạng thứ i, số phép so sánh sử 
dụng để tìm ra x là 2i + 1. 
 Do đó, số phép so sánh trung bình ta cần sử 
dụng là: 
 Như vậy độ phức tạp trung bình của thuật toán 
tìm kiếm tuần tự là O(n) 
22
)1(
2
)...321(2)12(..753







n
n
n
nn
n
nn
n
n
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
39 
 Trong thực tế, các phép so sánh cần để xác định xem 
đã tới cuối vòng lặp hay chưa thường được bỏ qua, 
không đếm. 
 Trong đa số các trường hợp không đòi khỏi sự khắt khe 
về tính chính xác, người ta sử dụng Big-O cho mọi 
trường hợp. 
 Hệ số trong các hàm theo đa thức không được tính 
trong phân tích độ phức tạp, ví dụ O(n3) và O(20000n3) 
là như nhau, nhưng trong thực tế đôi khi hệ số rất quan 
trọng. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
40 
Độ phức tạp Thuật ngữ/tên phân lớp 
O(1) Độ phức tạp hằng số 
O(log2n) Độ phức tạp logarit 
O(n) Độ phức tạp tuyến tính 
O(nlog2n) Độ phức tạp nlog2n 
O(na) Độ phức tạp đa thức 
O(an), a > 1 Độ phức tạp hàm mũ 
O(n!) Độ phức tạp giai thừa 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
41 
logn n nlogn n2 2n n! 
10 3.10-9 10-8 3.10-8 10-7 10-6 3.10-3 
102 7.10-9 10-7 7.10-7 10-5 4.1013 năm * 
103 1,0.10-8 10-6 1.10-5 10-3 * * 
104 1,3.10-8 10-5 1.10-4 10-1 * * 
105 1,7.10-8 10-4 2.10-3 10 * * 
106 2.10-8 10-3 2.10-2 17 phút * * 
• Lưu ý: 
• Mỗi phép toán giả sử thực hiện trong 10-9 giây (~ 
CPU 1GHz). 
• *: thời gian lớn hơn 100100 năm 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
42 
 Có một số thuật toán có độ phức tạp trong trường 
hợp xấu nhất là rất lớn nhưng trong trường hợp 
trung bình lại chấp nhận được. 
 Đôi khi, trong thực tế ta phải tìm nghiệm gần đúng 
thay vì nghiệm chính xác. 
 Có một số bài toán tồn tại nhưng có thể chứng 
minh được không có lời giải cho chúng (ví dụ bài 
toán Halting). 
 Trong thực tế, đa số ta chỉ khảo sát các bài toán có 
độ phức tạp đa thức trở xuống. 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
43 
 Phương pháp đếm 
 Phương pháp hàm sinh 
 Một số kết quả hoán vị 
 Các kết quả, định lý liên quan đến các cấu trúc 
dữ liệu cụ thể 
  
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
44 
1. Các hàm sau đây có là O(x) hay không? 
a) f(x) = 10 
b) f(x) = 3x + 7 
c) f(x) = 2x2 + 2 
2. Mô tả thuật toán tìm số nhỏ nhất trong dãy hữu 
hạn các số tự nhiên. Có bao nhiêu phép so 
sánh, bao nhiêu phép gán trong thuật toán? 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
45 
3. Phân tích độ phức tạp của thuật toán tính tổng dãy số sau: 
4. Cho biết số phép gán, số phép so sánh trong đoạn code sau 
đây theo n: 
 sum = 0; 
 for (i = 0; i < n; i++) 
 { 
 sum = sum + i; 
 } 
!
1
...
6
1
2
1
1
n
S 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
46 
5. Cho biết số phép gán, số phép so sánh trong đoạn 
code sau đây theo n: 
for (i = 0; i < n ; i++) 
 for (j = 0; j < n; j++) 
 { 
 C[i][j] = 0; 
 for (k = 0; k < n; k++) 
 C[i][j] = C[i][j] + 
 A[i][k]*B[k][j]; 
 } 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
47 
6. Hãy cho biết các hàm g(n) cho các hàm f(n) 
dưới đây (f(n) là O(g(n))). 
 f(n) = (2 + n) * (3 + log2n) 
 f(n) = 11 * log2n + n/2 – 3542 
 f(n) = n * (3 + n) – 7 * n 
 f(n) = log2(n
2) + n 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
48