Tài liệu tham khảo môn học Cấu trúc dữ liệu
Tài liệu tham khảo môn học Cấu trúc dữ liệu gồm 8 chương với mục tiêu giới thiệu cho học sinh về khái niệm về kiểu dữ liệu trừu tượng, kiểu dữ liệu trừu tượng, cấu trúc dữ liệu thông dụng, nâng cao và những thao tác trên các cấu trúc đó, một số thuật toán cơ bản và rèn luyện một số kĩ năng phân tích thuật toán.
Tài liệu tham khảo
môn học cấu trúc dữ
liệu
-1-
LỜI NÓI ĐẦU
Giáo trình này được viết cho sinh viên các trường Cao đẳng Đại học
Để học tốt giáo trình này sinh viên cần có kiến thức về tin học cơ sở và đã biết một
ngôn ngữ lập trình bậc cao như Pascal, Delphi, C hay C++...
Giáo trình được viết nhằm những mục tiêu sau đây:
Giới thiệu cho học sinh về khái niệm về kiểu dữ liệu trừu tượng.
Cung cấp cho học sinh kiến thức cơ bản về những kiểu dữ liệu trừu tượng, cấu
trúc dữ liệu thông dụng, nâng cao và những thao tác trên các cấu trúc đó.
Cung cấp một số thuật toán cơ bản và rèn luyện một số kĩ năng phân tích thuật
toán cho học sinh.
Rèn luyện cho học sinh cách áp dụng các cấu trúc dữ liệu đã học và tư duy
thuật toán để có thể thiết kế và cài đặt một số chương trình bằng một ngôn ngữ
bậc cao.
Để có thể học tốt các chương sau, sinh viên cần đọc kĩ chương 1 và chương 2.
Chương 1 giới thiệu những khái niệm cơ bản về thuật giải. Chương 2 giới thiệu những
khái niệm cơ bản về kiểu dữ liệu trừu tượng. Đây là khái niệm mới đối với học sinh.
Một kiểu dữ liệu trừu tượng là một tập hợp các đối tượng và được xác định hoàn toàn
bởi các phép toán có thể biểu diễn trên các đối tượng đó. Người sử dụng được phép
tìm hiểu các đối tượng và thực hiện các thao tác trên các đối tượng của kiểu dữ liệu
thông qua các phép toán đó mà không cần quan tâm đến việc đối tượng được cài như
thế nào trong ngôn ngữ lập trình. Chúng tôi có đưa ra một vài ví dụ đơn giản về kiểu
dữ liệu trừu tượng, cách đặc tả và xây dựng chúng để định hướng cho việc đặc tả và
xây dựng những kiểu dữ liệu trừu tượng trong những chương sau.
Trong khi trình bày mỗi kiểu dữ liệu trừu tượng ở mỗi chương sau, chúng tôi cố gắng
khuyến khích sinh viên trước hết phải hiểu một cách khái quát về kiểu dữ đó trước khi
quan tâm đến việc cài đặt chi tiết bên trong. Điều đó không có nghĩa là chúng tôi
không coi trọng việc cài đặt. Việc tách riêng đặc tả bên ngoài và bên trong cho phép ta
nhìn rõ trước hết vào bản chất của một kiểu dữ liệu trừu tượng là tập các thao tác trên
-2-
các đối tượng của kiểu dữ liệu đó. Và chỉ khi đã hiểu rõ bản chất của các thao tác trên
một kiểu dữ liệu trừu tượng chúng ta mới chuyển tới việc cài đặt những thao tác đó
bằng một ngôn ngữ bậc cao nào đó. Công cụ cho phép ta bóc tách một cách khái niệm
hình thức bên ngoài và chi tiết bên trong đó chính là kiểu dữ liệu trừu tượng.
Từ chương 3 đến chương 6 dành cho việc nghiên cứu một số kiểu dữ liệu trừu tượng
cơ bản tuyến tính và phi tuyến. Đó là các kiểu dữ liệu trừu tượng ngăn xếp, hàng đợi,
cây, bảng tìm kiếm, tập hợp và đồ thị... Với mỗi kiểu dữ liệu trừu tượng đưa ra, chúng
đều được đặc tả bởi các thao tác cơ bản và hướng dẫn cài đặt một số thao tác. Những
thao tác đưa ra là những thao tác cơ bản nhất. Tuy nhiên, tuỳ theo điều kiện và hoàn
cảnh, học sinh có thể bổ sung thêm một số những thao tác khác. Trong việc xây dựng
các kiểu dữ liệu trừu tượng, chúng tôi rất nhấn mạnh việc quan tâm đầu tiên là đặc tả
được các thao tác cần thiết (xây dựng mô đun ngoài), sau đó mới đến việc cài đặt các
thao tác (xây dựng mô đun trong). Ngoài ra, chúng tôi cũng quan tâm đến việc hướng
dẫn sử dụng các kiểu dữ liệu trừu tượng thông qua những ví dụ về những mô đun ứng
dụng.
Sinh viên ắt hẳn đã được giới thiệu một vài thuật toán sắp xếp đơn giản trên mảng từ
phần Tin học đại cương. Tuy nhiên, bài toán sắp xếp và tìm kiếm là bài toán hết sức
cơ bản đối với mỗi sinh viên Cao đẳng và Đại học nên chúng tôi dành riêng chương 7
để nói về một số giải thuật sắp xếp đơn giản cũng như một số giải thuật sắp xếp nâng
cao, cần đến một chút kiến thức về kiểu dữ liệu trừu tượng vừa học trong các chương
trước. Một số phép so sánh các giải thuật sắp xếp cũng được đề cập trong chương này.
Để giúp học sinh có thêm một số kiến thức về thuật giải, trong chương 8, chúng tôi
trình bày một số phương pháp thiết kế thuật giải như đệ qui, quay lui, chia dể trị, tham
lam, qui hoạch động. Đây là những phương pháp rất cơ bản và thông dụng trong khoa
học máy tính. Bạn đọc có thể tìm thấy nhiều ví dụ minh hoạ cho những phương pháp
này. Các ví dụ đều được cài đặt cụ thể bằng ngôn ngữ lập trình Pascal.
Cuối mỗi chương đều có hệ thống bài tập để học sinh làm và tự kiểm tra kiến thức của
mình.
Cuối cùng là phần phụ lục, trong đó chúng tôi có đưa ra một số bài tập lớn, để học sinh
áp dụng những kiến thức đã học tập giải quyết những vấn đề phức tạp hơn so với bài
-3-
tập sau mỗi chương. Với những bài tập lớn này, để nâng cao hiệu quả, yêu cầu học
sinh cần đặc tả rõ bài toán, phân tích và thiết kế thuật giải, sau đó cài đặt trên một ngôn
ngữ cụ thể. Tiếp theo học sinh cần phải kiểm thử phần mềm mình vừa cài đặt và có
những nhận xét về độ phức tạp của thuật toán mình thiết kế, về các hướng cần mở rộng
cho các bài tập này. Chỉ khi nào học sinh làm tốt các bài tập lớn đó mới có thể nói là
họ đã thành công trong việc học tập môn học này.
Chủ biên và hiệu đính toàn bộ nội dung bản thảo:
Chương 1: Mở đầu
chương 2: .
Chương 3: .
Chương 4,
Chương 6:
Chương 7:
Chương 8:
-4-
CHƯƠNG I: MỞ ĐẦU
Chương này trình bày một số khái niệm cơ bản đầu tiên về bài toán theo quan điểm
Tin học, thuật giải, cấu trúc dữ liệu, mối quan hệ giữa cấu trúc dữ liệu và thuật giải.
Những khái niệm về độ phức tạp của thuật giải và phân tích thuật giải cũng được giới
thiệu trong chương.
1.1. Khái niệm về cấu trúc dữ liệu và thuật giải
1.1.1. Khái niệm bài toán
Trong phạm vi Tin học, ta có thể quan niệm bài toán là bất cứ việc gì ta muốn máy
tính thực hiện. Như vậy những việc như viết một dòng chữ ra màn hình, giải phương
trình bậc hai, giải hệ phương trình bậc nhất hai ẩn số, quản lý các cán bộ trong một cơ
quan... đều là các ví dụ về bài toán.
Khi dùng máy tính giải bài toán, ta chỉ cần quan tâm đến hai yếu tố: đưa vào máy
thông tin gì (thông tin vào) và cần lấy ra thông tin gì (thông tin ra), Thông tin vào còn
được gọi là Input, thông tin ra còn được gọi là Output. Như vậy để phát biểu một bài
toán, ta chỉ cần đặc tả Input và Output của bài toán.
Ví dụ 1. Bài toán tìm ước chung lớn nhất
Input. Hai số nguyên dương M và N
Output. Ước chung lớn nhất của M và N
Ví dụ 2. Bài toán tìm nghiệm của đa thức một biến:
Input: số nguyên dương n; các số thực a0, a1, . . ., an;
Output: Trả lời câu hỏi có bao nhiêu số thực x khác nhau và giá trị của chúng
(nếu có) sao cho
a0 + a1 x +...+ anxn = 0
Ví dụ 3. Bài toán phân tích số:
-5-
Input: Số nguyên dương N2;
Output: Các số nguyên tố p1,..., pk; các số nguyên dương 1,...,k; sao cho
n = p11...pkk;
Ví dụ 4. Bài toán kiểm tra tính nguyên tố:
Input: Số nguyên dương n;
Output: Trả lời câu hỏi n là số nguyên tố hay không?.
Ví dụ 5. Bài toán quản lý hồ sơ cán bộ:
Input: Hồ sơ gốc của các cán bộ trong cơ quan;
Output: Những biểu bảng thống kê, phân loại cán bộ, các quy trình lưu trữ,
quản lý hồ sơ cán bộ.
Ví dụ 6. Bài toán thứ 10 của Hilbert:
Input: P là đa thức (nhiều ẩn) với hệ số nguyên;
Output: Trả lời câu hỏi P có nghiệm nguyên hay không?
Qua các ví dụ trên, ta thấy các bài toán được cấu tạo bởi hai thành phần cơ bản:
- Thông tin vào (input): Cho ta biết những thông tin đã có (các giả thiết);
- Thông tin ra (output): Các thông tin cần tìm từ input (kết luận);
1.1.2. Khái niệm thuật giải
Như vậy trong giáo trình này, việc cho một bài toán có nghĩa là cho input và mô tả
output cần tìm. Vấn đề đặt ra là thế nào là giải một bài toán?
Trước hết cần lưu ý rằng trong toán học có một xu hướng nghiên cứu định tính các bài
toán. Theo xu hướng này, khi xem xét các bài toán, người ta chỉ cần chứng tỏ sự tồn
tại của output khi cho input và nếu có thể, xét xem có bao nhiêu "lời giải" và nghiên
cứu dáng điệu của chúng. Trong các nghiên cứu như vậy, nhiều khi ta không cần tìm
ra lời giải một cách tường minh nhưng bằng cách dùng các công cụ toán học khác
nhau một cách thích hợp ta vẫn có thể chứng minh chặt chẽ các điều khẳng định liên
-6-
quan đến lời giải. Mục tiêu của xu hướng nghiên cứu này là chỉ ra điều kiện tồn tại và
nếu có thể, sự duy nhất của lời giải. Sự tồn tại lời giải theo nghĩa này không luôn cho
ta cách thức thực tế để tìm ra lời giải.
Trong khuôn khổ của Tin học, việc giải bài toán có nghĩa trao được cho máy tính cách
giải. Để giao bài toán cho máy tính, ta cần hướng dẫn cho máy các thao tác mà về
nguyên tắc máy có thể thực hiện được. Một cách giải bài toán như vậy được gọi là một
thuật giải (còn gọi là thuật toán hay giải thuật).
Nói một cách đầy đủ hơn,
Thuật giải A để giải bài toán P là một dãy hữu hạn các thao tác đơn giản được
sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác đó, từ
Input của bài toán, ta nhận được Output cần tìm.
Chính quan niệm về việc giải bài toán như vậy là cốt lõi để ta có thể chuyển giao công
việc đó cho máy tính. Như vậy, khác với quan niệm về việc giải một bài toán theo toán
học truyền thống, việc giải bài toán theo quan niệm của Tin học là quá trình thực hiện
một dãy hữu hạn các thao tác đơn giản để có thể từ Input dẫn ra Output một cách
tường minh.
Trong định nghĩa nêu trên, thao tác đơn giản được hiểu là thao tác mà máy tính có thể
thực hiện được. Ví dụ các phép toán số học, các phép so sánh hai giá trị số là các thao
tác đơn giản.
1.1.3. Mô tả thuật giải
Ngay từ khi học môn Tin học cơ sở học sinh đã được làm quen với khái niệm thuật
giải và được học cách mô tả hay diễn đạt những thuật giải đơn giản. Thuật giải cho
những bài toán nhỏ hay thuật giải cho những bài toán lớn khi được thiết kế ở mức thô
hay được mô tả bằng sơ đồ khối. Cách dùng sơ đồ khối để minh họa thuật giải có lợi
thế là rất trực quan, dễ hiểu. Tuy nhiên, với những bài toán lớn, phức tạp, việc dùng sơ
đồ khối để mô tả thuật giải có những hạn chế nhất định. Hạn chế này là có thể là do
khuôn khổ giấy hay màn hình ta dùng để vẽ sơ đồ hay tầm bao quát, theo dõi của mắt
-7-
ta trên sơ đồ. Hạn chế này cũng nảy sinh khi bài toán của ta phức tạp, có nhiều vòng
lặp lồng nhau, khi đó việc trình bày sơ đồ có rất nhiều hạn chế.
Ta cũng hay dùng phương pháp liệt kê các bước giải để mô tả thuật giải. Phương pháp
này cũng rất dễ hiểu đối với các bài toán nhỏ. Tuy nhiên, đối với các bài toán lớn, việc
liệt kê sẽ trở nên khó khăn và nếu được thì cũng gây khó khó theo dõi, nhất là đối với
vòng lặp. Hơn thế nữa việc liệt kê các bước giải ta hay phải dùng ngôn ngữ tự nhiên
để mô tả các thao tác nên việc diễn đạt nhiều khi rất khó chính xác.
Phương pháp thứ ba hay được dùng để mô tả thuật giải là dùng giả mã hay ngôn ngữ
phỏng trình. Việc dùng ngôn ngữ phỏng trình khắc phục được những nhiều nhược
điểm của hai phương pháp trên, đặc biệt đối với những bài toán lớn, phức tạp. Cũng
có ý kiến là ta nên chọn một ngôn ngữ lập trình thông dụng làm công cụ để diễn đạt
thuật giải. Tuy nhiên, ai cũng biết là thuật giải cần phải độc lập với ngôn ngữ lập trình.
Khi thuật giải được viết tốt nó có thể được cài đặt bằng bất cứ ngôn ngữ lập trình nào,
tùy theo tính thích hợp của bài toán và ý muốn của người lập trình. Hơn thế nữa, thiết
kế thuật giải là một trong những công việc quan trọng nhất của người lập trình. Nếu ta
chọn một ngôn ngữ lập trình để mô tả thuật giải thì lúc nào ta cũng phải chú ý tuân thủ
các tiểu tiết cú pháp của ngôn ngữ. Điều đó sẽ gây mất thì giờ và ảnh hưởng lớn đến
sự tập trung vào công việc chính là thiết kế và mô tả thuật giải.
Sau đây là ví dụ về mô tả thuật giải tìm ước chung lớn nhất của hai số nguyên m và n.
Begin
Cách 1: Dùng sơ đồ khối
t m
True
m n mod m
nt m>0
False
Write n
-8-
End
Hình 1.1: Sơ đồ khối diễn tả thuật giải tìm ước chung lớn nhất của hai số nguyên
không âm
--------------------------------------
Cách thứ hai: Dùng phương pháp liệt kê các bước giải, ta có thể viết như sau:.
Bước 1. Khi m > 0 thực hiện
tm
m n mod m
n t
Bước 2. Kiểm tra xem nếu m > 0, quay lại bước 1
Bước 3. In kết quả là n và kết thúc
Cách thứ ba: Dùng ngôn ngữ phỏng trình.
Function Ucln(m,n)
var t
Begin
While m > 0 do
t m
m n mod m
n t
Return n
-----------------------------
Trong thực tế, tùy theo từng giai đoạn thiết kế thuật giải, tùy theo mức độ, và đối
tượng trình bày mà người lập trình thường hay chọn phương pháp thích hợp nhất trong
ba phương tiện nêu trên.
-9-
Như vậy, việc diễn tả một thuật giải giải một bài toán nào đó có nghĩa là trình bày
trình tự các thao tác cần thực hiện. Tuy nhiên, đó chỉ là cách diễn tả thuật giải giữa
người với người.
Ngay khi thuật giải đã được diễn tả như vậy, con người có thể dùng để giải bài toán
với mỗi bộ dữ liệu vào. Tuy nhiên, theo cách diễn tả này, máy tính vẫn chưa thể thực
hiện các thao tác trong thuật giải dù các thao tác đó rất đơn giản. Thuật giải cần được
diễn tả thành một chương trình gồm những dòng lệnh. Mỗi lệnh là một việc nào đó mà
ta đòi hỏi máy tính thực hiện.
Ngôn ngữ dùng để viết chương trình được gọi là ngôn ngữ lập trình.
Phần đọc thêm
Khái niệm thuật giải trình bày ở trên đủ để ta có thể hình dung để có thể chuyển giao cho
máy tính việc giải một bài toán ta cần diễn tả cách giải như thế nào và cũng là cách nhận
biết thế nào là thuật giải đối với một bài toán nào đó.
Trong quá trình nghiên cứu cách giải bài toán theo nghĩa nêu trên,trong toán học đã diễn
ra một quá trình phát triển đầy kịch tính. Cho tới đầu thế kỷ 20, với lòng tin tiên nghiệm
vào việc mọi bài toán được phát biểu đúng đắn đều có thuật giải giải, nhiều nhà toán học
đầy tài năng và tâm huyết đã tiến công vào các bài toán đang tồn tại như những lời thách
đố trí tuệ con người.
Vấn đề then chốt nhất của lý thuyết tính toán phát sinh ở đây. Để chứng minh một bài toán
nào đó có thuật giải giải nó, ta chỉ cần đề ra một thuật giải theo quan niệm trực giác của
khái niệm này và kiểm định tính đúng đắn của nó đối với bài toán đã cho. Tuy nhiên, khi
cần chứng minh việc không có thuật giải giải một bài toán nào đó, quan niệm trực quan về
thuật giải không thể là cơ sở bảo đảm cho một chứng minh toán học chặt chẽ được. Do đó,
muốn chứng minh những điều khẳng định "không có thuật giải giải một bài toán nào dó",
ta cần có một định nghĩa toán học cho khái niệm thuật giải.
Vào khoảng những năm 1930-1936, lần lượt các nhà toán học K.Gõdel, S. Kleene,
A.Church, A.Turing đã đề ra một số định nghĩa khác nhau cho khái niệm thuật giải. Trong
số các định nghĩa toán học khác nhau (nhưng tương đương) về thuật giải, các khái niệm
Máy Turing (1936) và Hàm đệ quy (1931-1936) được sử dụng rộng rãi hơn vì có nhiều
thuận tiện cho các nghiên cứu cả về lý thuyết lẫn thực hành. Ta có thể xem máy Turing là
một mô hình toán học của máy tính.
- 10 -
Chính nhờ có được định nghĩa toán học về thuật giải, người ta đã chứng minh được có
những bài toán không có thuật giải giải. Chẳng hạn, bài toán thứ 10 của Hilbert (Ví dụ 5
nêu trên) không có thuật giải đểgiải.
1.1.4. Một số ví dụ về thuật giải
Ví dụ 1. Một thuật giải tìm ước chung lớn nhất (viết tắt là UC) của hai số
nguyên dương M và N.(Bạn đọc có thể thấy sự khác nhau chút ít giữa thuật
toán này và thuật toán trình bày ở phần trên).
Bước 1. Nếu M=N thì UC=M và kết thúc, nếu không thì chuyển đến bước 2.
Bước 2. Nếu M 3.3. Tăng i một đơn vị và quay về bước 2.
Rõ ràng số thao tác cần tiến hành không quá n.
Ví dụ 3. Thuật giải để sắp xếp một dãy số cho trước thành một dãy đơn điệu không
tăng.
Ta xét bài toán sau:
Input: Số nguyên dương n và dãy n số a1, . . ., an.
Output: Dãy số trên được sắp xếp lại thành một dãy số không tăng tức là số
hạng trước lớn hơn hay bằng số hạng sau.
Một thuật giải giải bài toán này có thể nói vắn tắt như sau: với mỗi chỉ số i, 1in-1,
xét các chỉ số j đứng sau i, i+1jn, nếu aithức nhất định thành những cấu trúc dữ liệu để thuật giải tác động lên đó được hiệu
quả.
Trong giáo trình Tin học cơ sở, ta đã làm quen với một số cấu trúc dữ liệu đơn giản
như bản ghi, mảng...Trong giáo trình này ta sẽ lần lượt nghiên cứu những cấu trúc dữ
liệu phức tạp hơn cả tuyến tính và phi tuyến tính.
Khi lập chương trình cho máy tính, công việc tổ chức dữ liệu và thiết kế những thuật
giải tương thích, hiệu quả là rất quan trọng. Chính vì thế cấu trúc dữ liệu và thuật giải
là hai thành tố quan trọng của chương trình máy tính và đều là những đối tượng nghiên
cứu quan trọng của khoa học máy tính. Hơn nữa, chúng có quan hệ mật thiết với nhau,
ảnh hưởng và điều phối lẫn nhau để tạo ra lời giải cho bài toán. Trong phạm vi của
giáo trình này, ta nghiên cứu những cấu trúc dữ liệu cơ bản và những thuật giải hay
thao tác thường thực hiện trên các cấu trúc dữ liệu đó.
1.2. Khái niệm về độ phức tạp của thuật giải
Mỗi thuật giải chỉ giải một bài toán nào đó nhưng có thể có nhiều thuật giải khác nhau
giải cùng một bài toán. Ví dụ, để sắp xếp một dãy số bất kỳ thành một dãy đơn điệu,
có rất nhiều thuật giải khác nhau.
Cùng một bài toán, có thể có nhiều thuật giải khác nhau. Việc lựa chọn một thuật giải
thích hợp nhất hay tốt nhất cho một bài toán luôn là mối quan tâm của người lập trình.
Vậy làm thế nào để chọn được thuật giải thích hợp nhất trong những thuật giải của một
bài toán? Nói cụ thể hơn, những tiêu chí nào là quan trọng để đánh giá một thuật giải?
Thuật giải càng trong sáng, có cấu trúc tốt thì mã hóa càng nhanh, bảo trì chương trình
càng dễ dàng và do đó giảm được giá thành của phần mềm. Tuy nhiên, có những thuật
giải rất trong sáng, dễ hiểu nhưng lại không khả thi về mặt thời gian thực hiện hay
không gian nhớ cần thiết khi thực hiện nó. Vậy làm thế nào để đánh giá được thời
gian thực hiện và không gian nhớ dành cho một thuật giải? Cách đơn giản nhất là ta
cài đặt thuật giải rồi cho máy chạy chưong trình với một tập dữ liệu vào nào đó và đo
thời gian thực hiện chương trình cũng như tính không gian nhớ cần thiết cho nó và ta
có kết quả về thời gian và không gian cần thiết cho thuật giải. Tuy nhiên, cách tính
- 13 -
này chỉ mới áp dụng trên một tập dữ liệu đầu vào cụ thể. Sẽ là không thích hợp nếu ta
dùng kết quả này để áp dụng chung cho các tập dữ liệu đầu vào khác. Nếu bài toán
đơn giản và đầu vào chỉ gồm một số ít phần tử thì ta cũng chẳng cần quan tâm nhiều
đến việc lựa chọn thuật giải làm gì. Ví dụ như bài toán sau: Ta cần chọn ra số lớn nhất
trong 3 số nguyên hay thậm chí trong vài chục số nguyên đã cho. Bạn có thể dùng bất
cứ thuật giải nào bạn nghĩ ra hay bạn thích, miễn là nó đúng, có lẽ thời gian thực hiện
chúng cũng không khác nhau bao nhiêu. Một thuật toán tìm kiếm tuần tự để tìm một
số điện thoại trong một danh sách điện thoại gồm 50 số thì có thể chấp nhận được
nhưng nếu áp dụng thuật toán đó cho một danh sách gồm hàng chục ngàn số điện thoại
trong một thành phố, hẳn là không thể chấp nhận được.
Như vậy, vấn đề đặt ra rất tự nhiên là khi giải một bài toán, ta muốn chọn một thuật
giải tốt. Chúng ta cần tìm ra một phương pháp nào đó để có thể cho phép ta đánh giá
được thuật giải này tốt hơn thuật giải kia với một tập dữ liệu vào bất kì. Ví dụ, khi
một danh bạ điện thoại gồm từ một trăm số điện thoại trở lên, cách tổ chức thành thư
mục và việc tìm kiếm theo thư mục chắc chắn sẽ giúp ta tìm kiếm tốt hơn là việc tìm
kiếm tuần tự.
Nhưng thế nào là thuật giải tốt. Đây là nội dung nghiên cứu của lý thuyết độ phức tạp
tính toán. Lý thuyết này có thể được xây dựng trên một nền tảng toán học chặt chẽ từ
một hệ tiên đề. Tuy nhiên, trong phạm vi giáo trình này, chúng tôi chỉ giới thiệu một
số vấn đề đơn giản .
Khi dùng máy tính thực hiện một chương trình thể hiện một thuật giải nào đó, hệ điều
hành cần cung cấp cho chương trình đó các tài nguyên như giờ CPU, bộ nhớ, . . . Độ
phức tạp của một thuật giải được đo bằng số lượng các tài nguyên cần dùng để thực
hiện chương trình đó. Khi so sánh hai thuật giải cùng giải một bài toán, một thuật giải
này được xem là tốt hơn thuật giải kia nếu nó dùng ít tài nguyên hơn.
Trong các tài nguyên cần dùng để chạy chương trình, hiện nay người ta quan tâm
nhiều nhất đến thời gian vì đó là dạng tài nguyên không tái tạo được. Một thuật giải
được xem là tốt nếu chương trình tương ứng chạy nhanh hay chính xác hơn, chạy
- 14 -
trong thời gian chấp nhận được. Do đó, để đánh giá độ phức tạp của một thuật giải, ta
thường ước tính số thao tác cơ bản cần dùng để thực hiện thuật giải. Thao tác cơ bản
của một thuật giải là thao tác mà số lần thựchiện nó không ít hơn số lần thực hiện các
thao tác khác.
Ví dụ về thao tác cơ bản:
Bài toán Thao tác cơ bản
Tìm phần tử x trong một danh sách So sánh x với một phần tử của danh
sách
Nhân hai ma trận thực Phép nhân hai số thực, phép cộng hai số
thực
Sắp xếp một danh sách So sánh hai phần tử của danh sách
Với mỗi bài toán, ta xét kích thước đầu vào hay gọi đơn giản là kích thước của bài toán.
Kích thước đầu vào một bài toán được đo bằng số lượng dữ liệu vào cần xử lý. Ví dụ
nếu dữ liệu vào là một dãy số có N số hạng thì kích thước bài toán dược xem bằng N,
nếu dữ liệu vào là một đồ thị có N đỉnh, kích thước bài toán bằng N, nếu dữ liệu vào là
một xâu ký tự độ dài L thì kích thước bài toán bằng L, nếu dữ liệu vào là một bảng có
M dòng và N cột thì kích thước bài toán bằng MxN. . .
Khi đó, số các thao tác cơ bản mà một thuật giải sẽ được biểu thị như một hàm f(K)
của biến số K là kích thước của bài toán. Khi đánh giá hàm f(K) người ta thường dùng
ký hiệu O hay chính xác hơn là khái niệm của giải tích có nghĩa là cùng bậc. Ví dụ,
giải thuật tìm Min-Max của một dãy số trong Mục 8.1 có độ phức tạp 2N, ta nói độ
phức tạp đó cỡ (N) có nghĩa là cùng bậc với N khi N tiến đến vô cùng; tương tự, giải
thuật sắp xếp dãy số có độ phức tạp cở (N2).
- 15 -
Việc dùng ký hiệu để thể hiện độ phức tạp của giải thuật cho ta một đánh giá tổng
thể không bị sa vào những tính toán tỉ mỉ hơn nhưng không thật cần thiết. Ví dụ, cùng
là hai phép toán cộng và nhân hai số, rõ ràng phép cộng thực hiện nhanh hơn nhiều so
với phép nhân nhưng sự khác biệt đó chỉ thể hiện bằng việc thời gian tính toán sai
khác một hằng số nhân. Do đó, nếu dùng ký hiệu , ta có thể bỏ qua sự khác biệt đó.
Khi nói về độ phức tạp về thời gian, có một số bậc được sử dụng thường xuyên và
người ta đã đặt tên cho chúng. Một cách vắn tắt, nếu một thuật toán có độ phức tạp là
t và t < cn, với n > n0 và c là một hằng số dương, còn n là kích cỡ đầu vào thì người ta
gọi thuật toán đó có độ phức tạp tuyến tính. Nếu t < cn2 thì t được gọi là có độ phức
tạp bình phương. Tương tự t được gọi là có độ phức tạp lập phương, đa thức hay mũ
nếu nó có bậc lần lượt của các hàm n 3, nk hay an , với k và a là những hằng số nào đó.
Để dễ hình dung về sự tăng của một số hàm với n là kích thước của bài toán, dưới đây
ta phác họa một số đồ thị của độ phức tạp loga, độ phức tạp tuyến tính, độ phức tạp
bình phương, độ phức tạp lập phương và độ phức tạp mũ.
O(an)
O(n3)
O(n2)
O(n)
O(log(n)
- 16 -
Hình 2.1: Phác hoạ các đường biểu diễn độ phức tạp của một số thuật giải
-----------------------------------------
1.3. Phân tích thuật toán
1.3.1. Khái niệm về phân tích thuật toán
Phân tích một giải thuật có nghĩa là đánh giá độ phức tạp của giải thuật đó.
Thực ra không có một cẩm nang để phân tích thuật toán mà chủ yếu là ta sử dụng kiến
thức toán học, sự trực quan, suy luận, và một số kĩ thuật cơ bản để tính độ phức tạp
của một thuật giải.
Có một số cấu trúc phổ biến trong các thuật giải: cấu trúc tuần tự, cấu trúc lặp và cấu
trúc đệ quy.
Với cấu trúc tuần tự: Nếu ta có hai đoạn trình thực hiện tuần tự là P1 và P2 , độ phức
tạp của chúng lần lượt là t1 = O(f(n)), t2 = O(g(n)) thì độ phức tạp của cả hai đoạn P1
và P2 chính là O(max(f(n), g(n)).
Ví dụ: Khi ta thực hiện tuần tự hai đoạn trình P1 và P2, P1 có độ phức tạp là O(n 2) và
P2 có độ phức tạp là O(n3) thì hợp hai đoạn P1 và P2 sẽ có độ phức tạp là O(n3).
Tương tự, nếu P1 có độ phức tạp là O(2 n) còn P2 có độ phức tạp là O(n 5) thì độ phức
tạp của đoạn trình hợp là O(2 n).
Để ý rằng, với n đủ lớn ta luôn có: n! > an > nk > logn.
Cấu trúc lặp thường có một trong các dạng sau
For i:=a to b do ; (1)
While Do ; (2)
Repeat Until ; (3)
Số thao tác cần thực hiện trong một cấu trúc lặp có thể đễ dàng ước tính được sau khi
đã tính được các thao tác cần thực hiện trong . Đối với cấu trúc lặp loại
(1), nếu số thao tác trong là S thì số thao tác cần thực hiện tổng cộng
không lớn hơn S(b-a).
- 17 -
Ví dụ: trong phép nhân hai ma trận vuông A và B cấp n ta có:
Procedure Nhanmatran(A,B)
Var C;
Begin
for i 1 to n do
for j 1 to n do
Begin
C[i,j] 0
for k 1 to n do
C[i,j] C[i,j] + a[i,k] * b[k,j]
End;
Return C;
End
Ta thấy ngay là vòng lặp trong cùng (k là biến chạy) có độ phức tạp O(n), vòng lặp
trong tiếp theo (j là biến chạy) cũng có độ phức tạp O(n) và vòng lặp ngoài cùng (với i
là biến chạy) với độ phức tạp O(n). Do đó toàn bộ chương trình của ta có độ phức tạp
O(n 3).
Đối với cấu trúc lặp loại (2) và (3), căn cứ vào điều kiện lô gic, ta có thể ước lượng
được số lần lặp tối đa do đó có thể tính được số tối đa các thao tác cần thực hiện.
Đối với các cấu trúc đệ quy, việc ước lượng số thao tác khó khăn hơn vì nói ta phải
tiến hành tính số thao tác theo một công thức truy hồi.
Sau đây ta sẽ xét một số ví dụ nữa.
Ví dụ 1. Xét bài toán
Input. Mảng một chiều A[1..N] gồm các số nguyên;
Output. Giá trị nhỏ nhất Min và giá trị lớn nhất Max của các phần tử của mảng;
Xét thuật giải có tên FindMin-Max(1,N) sau:
Bước 1. Nếu N=1 thì nếu Min = Max = A[1] và kết thúc nếu không thì chuyển
sang Bước 2.
- 18 -
Bước 2. Nếu N=2 thì (A[1]A[2] thì Min = A[1] và Max = A[2] nếu không thì
Min = A[2] và Max = A[1] và kết thúc nếu không thì chuyển sang Bước 3.
Bước 3. Gọi FindMin1-Max1(1,N Div 2) và FindMin2-Max2(N div 2 +1,N);
nếu Min1Min2 thì Min = Min1 nếu không thì Min=Min2 và nếu Max1Max2
thì Max = Max1 nếu không thì Max=Max2; kết thúc.
Nếu dộ phức tạp tính theo số lần so sánh C(N) các số thì ta có
C(2) = 1;
C(2K) = 2C(K) +2 với K>1;
C(2K+1) = C(K) + C(K+1) + 2;
Từ đó ta có thể tính được C(N) = 3N/2 - 2.
Ví dụ 2. Bài toán Tháp Hà Nội
Ta sẽ diễn tả bài toán này bằng ngôn ngữ thông thường. Có N đĩa tròn đường kính
khác nhau với lỗ thủng ở tâm và ba cọc 1, 2, 3. Ban đầu N đĩa đặt trên cọc 1, đĩa lớn
hơn nằm dưới đĩa nhỏ hơn. Một di chuyển đĩa thực hiện bằng cách chuyển đĩa trên
cùng ở cọc A (nếu có) đặt lên trên cùng một cọc B khác với điều kiện đĩa đó nhỏ hơn
đĩa (nếu có) đang nằm trên cùng đĩa ở cọc B. Cần tiến hành một dãy các di chuyển đĩa
sao cho cuối cùng, N đĩa được chuyển sang cọc 2.
Bài toán này gắn với một giai thoại về sự thử thách của Thượng đế đối với lòng kiên
trì của con người. Nếu số đĩa bằng 64, mỗi di chuyển đĩa thực hiện trong 1 giây và một
người thực hiện một dãy các di chuyển đúng đắn thì người đó phải mất 500 tỷ năm
mới di chuyển xong.
Việc cần chuyển N đĩa từ cọc 1 sang cọc 2 một cách hợp lệ và tốt nhất có thể xem là
trường hợp riêng của việc chuyển M đĩa nhỏ nhất từ cọc i sang cọc j ,1i3, 1j3, ij,
một cách hợp lệ và tốt nhất có thể. Nếu ta thể hiện việc đó bằng một thủ tục Procedure
Hanoi(m,i,j); Việc ta cần làm chính là Hanoi(N,1,2);
Để làm việc đó, do quy định của một di chuyển đĩa, ta cần chuyển m-1 đĩa nhỏ nhất từ
cọc i sang cọc thứ ba, đó là cọc k = 6-i-j, chuyển đĩa thứ M từ cọc i sang cọc j và sau
đó chuyển M-1 đĩa từ cọc k sang cọc j. Nếu viết bằng Pascal, ta có
- 19 -
Procedure Hanoi(M,i,j: Byte);
Begin
If m=0 then Exit;
Hanoi(M-1,i,6-i-j);
Writeln(i,’ – ‘,j);
Hanoi(M-1,6-i-j,j);
End;
Nếu ký hiệu T(M) là số di chuyển cần thực hiện (xem như một thao tác cơ bản), ta có
T(M) = 2.T(M-1) - 1 (*)
Như vậy nếu xem N là kích thước của bài toán thì độ phức tạp tính toán của thuật giải
trên là T(N). Từ hệ thức (*), ta có thể suy ra T(N) = 2N - 1.
Hệ thức (*) là một hệ thức truy hồi.
1.3.2. Một số quan điểm phân tích thuật toán
Cách phân tích thuật toán trong mục 8.2.2 còn được gọi là phân tích theo tình huống
xấu nhất (Worst-Case Analysis). Với mỗi thuật giải đối với bài toán kích thước K, ta
luôn đánh giá số tối đa các thao tác cơ bản cần tiến hành là bao nhiêu.
Có nhiều cách khác để phân tích thuật giải như phân tích trung bình (Average
Analysis), phân tích tiệm cận (Asymptotic Analysis).
Ta sẽ giới thiệu cách phân tích trung bình. Câu chuyện bắt đầu từ việc xem xét thuật
giải đơn hình đối với bài toán Quy hoạch tuyến tính. Bài toán này có thể phát biểu
trong ngôn ngữ đại số tuyến tính như sau:
I. Ma trận A gồm M dòng, N cột; Véc tơ cột B M chiều; véc tơ dòng C N
chiều;
O. Cần tìm véc tơ cột N chiều X sao cho AXB và CX đạt giá trị nhỏ nhất.
Theo cách đánh giá xấu nhất, độ phức tạp của thuật toán đơn hình cỡ hàm mũ. Tuy
nhiên, trải qua mấy chục năm dùng thuật giải này để giải rất nhiều bài toán phát sinh
trong nhiều lĩnh vực khác nhau, các chương trình vẫn chạy trong thời gian chấp nhận
được. Công trình nghiên cứu của nhà toán học S.. Smale cho kết quả độ phức tạp trung
- 20 -