Xem mẫu
- Lời nói đầu
Xây dựng một thuật toán tốt để giải bài bài toán đã cho là bước quan trọng nhất
trong việc giải bài toán đó trên máy tính điện tử. Để có được một thuật một thuật toán
tốt cần phải nắm vững các kỹ thuật thiết kế, phân tích, đánh giá thuật toán cùng các
thuật toán cơ bản cho một số lớp bài bài toán điển hình.
Tài liệu Thiết kế và đánh giá thuật toán được biên soạn nhằm phục vụ công việc
giảng dạy và học tập môn học Thiết kế và đánh giá thuật toán của ngành học Khoa học
máy tính thuộc khoa Công nghệ thông tin trường Đại học sư phạm kỹ thuật Nam Định.
Tài liệu cũng rất cần thiết cho tất cả các ngành học thuộc khoa Công nghệ thông tin.
Nội dung của tài liệu trình bày các kỹ thuật thiết kế thuật toán thông dụng và cơ
sở phân tích, đánh giá độ phức tạp của thuật toán. Tài liệu gồm 6 chương:
Chương 1: Tổng quan về thiết kế và đánh giá thuật toán
Chương 2: Kỹ thuật chia để trị
Chương 3: Kỹ thuật tham lam
Chương 4: Kỹ thuật quay lui
Chương 5: Kỹ thuật nhánh và cận
Chương 6: Kỹ thuật quy hoạch động
Trong từng chương các vấn đề đưa ra đều được minh họa bằng các ví dụ. Cuối
mỗi chương đều có một hệ thống các bài tập nhằm giúp người học củng cố các kiến
thức đã được học đồng thời rèn luyện khả năng vận dụng các kiến thức để giải quyết
một số bài toán trong thực tế. Với các bài tập khó tài liệu đã đưa ra hướng dẫn giải để
giúp người học thuận lợi trong qua trình nghiên cứu và giải quyết các bài tập. Cuối tài
liệu là phần cài đặt một số thuật toán đã được thiết kế nhằm giúp người học thuận lợi
hơn trong việc nắm bắt và vận dụng các kỹ thuật thiết kế thuật toán.
Tài liệu được biên soạn theo chương trình môn học Thiết kế và đánh giá thuật
toán của ngành học Khoa học máy tính thuộc khoa Công nghệ thông tin trường Đại học
sư phạm kỹ thuật Nam Định. Nội dung tài liệu được biên soạn dựa trên cơ sở nội dung
các bài giảng của tác giả trong một số năm qua tại khoa Công nghệ thông tin trường
Đại học sư phạm kỹ thuật Nam Định.
Trong quá trình biên soạn, tác giả đã nhận được nhiều ý kiến đóng góp cùng với
sự động viên, khích lệ của bạn bè đồng nghiệp trong khoa và trong trường. Tác giả xin
được tỏ lòng cảm ơn với những ý kiến đóng góp và động viên khích lệ này.
i
- Với lần biên soạn đầu tiên, mặc dù đã hết sức cố gắng song chắc chắn tài liệu
không thể tránh khỏi những thiếu sót. Rất mong nhận được các ý kiến đóng góp để tài
liệu ngày càng hoàn thiện hơn.
Phạm Cao Hào
ii
- MỤC LỤC
Chương 1. Tổng quan về thiết kế và đánh giá thuật toán 1
1.1. Thuật toán 1
1.1.1. Khái niệm thuật toán 1
1.1.2. Các đặc trưng cơ bản của thuật toán 1
1.2. Sự cần thiết của thiết kế và đánh giá thuât toán 2
1.3. Diễn tả thuật toán 3
1.4. Thiết kế thuật toán 7
1.4.1. Modul hoá và thiết kế từ trên xuống 7
1.4.2. Phương pháp là mịn dần (tinh chỉnh từng bước) 7
1.4.3. Một số kỹ thuật thiết kế 8
1.5. Phân tích thuật toán 9
1.5.1. Thời gian thực hiên thuật toán 9
1.5.2. Độ phức tạp tính toán của thuật toán 10
1.5.3. Ðộ phức tạp của chương trình có gọi chương trình con không đệ qui 16
1.5.4. Phân tích các thuật toán đệ quy 17
1) Thành lập phương trình truy hồi 18
2) Giải phương trình truy hồi 19
Bài tập chương 1. 31
Chương 2. Kỹ thuật chia để trị 37
2.1 Nội dung kỹ thuật 37
2.2. Các ví dụ áp dụng 37
2.2.1. Tìm min và max 37
2.2.2. Một số thuật toán sắp xếp 40
1) Sắp xếp nhanh 40
2) Sắp xếp trộn 44
2.2.3. Tìm kiếm nhị phân 51
2.2.4. Nhân các số nguyên lớn 53
Bài tập chương 2. 57
Chương 3. Kỹ thuật tham lam 62
3.1. Nội dung kỹ thuật 62
3.1.1. Bài toán tối ưu tổ hợp 62
3.1.2. Nội dung kỹ thuật tham lam 62
3.2. Các ví dụ áp dụng 62
iii
- 3.2.1. Bài toán người giao hàng 62
3.2.2. Bài toán chiếc ba lô 65
3.2.3. Bài toán tô màu bản đồ 70
3.2.4. Tìm cây khung nhỏ nhất 74
3.2.5. Tìm đường đi ngắn nhất 77
3.2.6. Bài toán phân công công việc 79
Bài tập chương 3. 84
Chương 4. Kỹ thuật quay lui 86
4.1. Nội dung kỹ thuật 86
4.2. Các ví dụ áp dụng 87
4.2.1. Đưa ra các dãy nhị phân độ dài n 87
4.2.2. Đưa ra các hoán vị của n số nguyên 88
4.2.3. Đưa ra các tập con của tập gồm n số nguyên 90
4.2.4. Bài toán xếp hậu 92
4.2.5. Tìm đường đi trên đồ thị 94
4.2.6. Bài toán ngựa đi tuần 99
Bài tập chương 4 104
Chương 5. Kỹ thuật nhánh và cận 111
5.1. Nội dung kỹ thuật 111
5.2. Các ví dụ áp dụng 114
5.2.1. Bài toán người du lịch 114
5.2.2. Bài toán chiếc ba lô 128
Bài tập chương 5. 133
Chương 6. Kỹ thuật quy hoạch động 137
6.1. Nội dung kỹ thuật 137
6.2. Các ví dụ áp dụng 140
6.2.1. Tính số tổ hợp 140
6.2.2. Bài toán nhân nhiều ma trận 143
6.2.3. Bài toán chiếc ba lô 149
6.2.4. Xâu con chung dài nhất 154
Bài tập chương 6. 164
Phụ lục 171
Tài liệu tham khảo 195
iv
- v
- Chƣơng 1
TỔNG QUAN VỀ THIẾT KẾ VÀ ĐÁNH GIÁ THUẬT TOÁN
1.1. Thuật toán
1.1.1. Khái niệm thuật toán
Thuật toán (Algorithm) đã được biết đến từ rất lâu. Đầu tiên thuật toán được
hiểu như là các qui tắc thực hiện các phép tính số học với các con số được viết trong
hệ thập phân. Cùng với sự phát triển của máy tính, khái niệm thuật toán được hiểu
theo nghĩa rộng hơn. Khái niệm thuật toán được định nghĩa một cách hình thức
chính xác thông qua máy Turing. ở đây chúng ta sẽ xem xét khái niệm thuật toán
một cách trực quan.
Thuật toán (hay giải thuật, thuật giải) là một khái niệm cơ sở của tin học.
Mỗi bài toán trong thực tế bao gồm hai phần:
- Input: Các đại lượng cho trước (đại lượng vào)
- Output: Các đại lượng cần tìm (đại lượng ra)
Như vậy việc giải bài toán là việc xác định tường minh output theo input
bằng một quá trình có thể thực hiện một cách hiệu quả. Đó chính là nội dung cơ bản
của lý thuyết tính toán. Khi cho bài toán, ta cần tìm ra 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 theo đó, từ input ta sẽ tìm
ra được output theo yêu cầu.
Một cách trực quan thuật toán giải một bài toán là một dãy hữu hạn các chỉ
dẫn (quy tắc, thao tác hay phép toán) hết sức rõ ràng và chính xác được sắp xếp theo
một trình tự xác định để sao cho sau một số hữu hạn lần thực hiên các chỉ dẫn đó thì
biến đổi được input thành output.
1.1.2. Các đặc trƣng cơ bản của thuật toán
1) Dữ liệu vào
Mỗi thuật toán có thể có một hoặc nhiều đại lượng vào mà ta thường gọi là
dữ liệu vào
2) Dữ liệu ra
Sau khi thực hiên xong thuật toán, tuỳ theo chức năng mà thuật toán đảm
nhiệm ta có thể thu được một số đại luợng ra mà ta gọi là dữ liệu ra.
3) Tính xác định
Tính xác định của thuật toán đòi hỏi ở chỗ ở mỗi bước các thao tác phải hết
sức rõ ràng, không thể gây nên sự nhập nhằng, lẫn lộn, tuỳ tiện. Nói cách khác trong
cùng một điều kiện hai bộ xử lý (người hoặc máy) thực hiện cùng một bước của
thuật toán thì phải cho cùng một kết quả.
1
- 4) Tính dừng
Thuật toán phải dừng và cho kết quả sau một số hữu hạn bước thực hiện.
5) Tính hiệu quả
Yêu cầu của tính hiệu quả là trong số các thuật toán thực hiện cùng một chức
năng ta cần chọn thuật toán tốt nhất. Tiêu chuẩn tốt ở đây được hiểu là: thuật toán
thực hiện nhanh, tốn ít thời gian nhất, dùng ít giấy hoặc từ nhớ để lưu trữ các kết
quả trung gian.
6) Tính phổ dụng
Một thuật toán được xem là có tính phổ dụng cao nếu nó có thể dùng để giải
bất cứ bài toán nào trong một lớp các bài toán chứ không phải là một bài toán cụ
thể.
1.2. Sự cần thiết của thiết kế và đánh giá thuật toán
Xây dựng một thuật toán tốt để giải bài toán đã cho là bước quan trọng nhất
trong việc giải bài toán đó trên máy tính điện tử. Để có được một thuật toán tốt cần
phải nắm vững các kỹ thuật thiết kế, phân tích, đánh giá thuật toán cùng các thuật
toán cơ bản cho một số lớp bài toán điển hình.
Trong khi giải một bài toán chúng ta có thể có một số thuật toán khác nhau,
vấn đề là cần phải đánh giá các thuật toán đó để lựa chọn một thuật toán tốt (nhất).
Thông thường thì ta sẽ căn cứ vào các tiêu chuẩn sau:
(1) Thuật toán đúng đắn.
(2) Thuật toán đơn giản.
(3) Thuật toán thực hiện nhanh.
Với yêu cầu (1), để kiểm tra tính đúng đắn của thuật toán chúng ta có thể cài
đặt thuật toán đó và cho thực hiện trên máy với một số bộ dữ liệu mẫu rồi lấy kết
quả thu được so sánh với kết quả đã biết. Thực ra thì cách làm này không chắc chắn
bởi vì có thể thuật toán đúng với tất cả các bộ dữ liệu chúng ta đã thử nhưng lại sai
với một bộ dữ liệu nào đó. Vả lại cách làm này chỉ phát hiện ra thuật toán sai chứ
chưa chứng minh được là nó đúng. Tính đúng đắn của thuật toán cần phải được
chứng minh bằng toán học. Điều này không đơn giản và do vậy chúng ta sẽ không
đề cập đến ở đây.
Khi chúng ta viết một chương trình để sử dụng một vài lần thì yêu cầu (2) là
quan trọng nhất. Chúng ta cần một giải thuật dễ viết chương trình để nhanh chóng
có được kết quả , thời gian thực hiện chương trình không được đề cao vì dù sao thì
chương trình đó cũng chỉ sử dụng một vài lần mà thôi. Tuy nhiên khi một chương
trình được sử dụng nhiều lần thì thì yêu cầu tiết kiệm thời gian thực hiện chương
2
- trình lại rất quan trọng đặc biệt đối với những chương trình mà khi thực hiện cần dữ
liệu nhập lớn do đó yêu cầu (3) sẽ được xem xét một cách kĩ càng. Ta gọi nó là hiệu
quả thời gian thực hiện của thuật toán.
1.3. Diễn tả thuật toán
Có nhiều cách diễn tả thuật toán. Người ta thường diễn tả thuật toán bằng
một trong các cách sau:
1) Liệt kê từng buớc
Thuật toán có thể trình bày dưới dạng ngôn ngữ tự nhiện theo trình tự các
bước thực hiện trong thuật toán
2) Sơ đồ khối (Lưu đồ)
Dùng các hình vẽ (có qui ước) để diễn tả thuật toán. Lưu đồ cho hình ảnh
trực quan và tổng thể của thuật toán nên thường được sử dụng.
3) Ngôn ngữ lập trình
Dùng cấu trúc lệnh, dữ liệu của một ngôn ngữ lập trình nào đó để mô tả.
4) Dạng giả mã
Thuật toán trình bày dưới dạng văn bản bằng ngôn ngữ tự nhiên tuy dễ hiểu
nhưng khó cài đặt. Dùng một ngôn ngữ lập trình nào đó để diễn tả thì phức tạp, khó
hiểu. Thông thường thuật toán cũng được trình bày dưới dạng văn bản và không
ràng buộc nhiều vào cú pháp qui định của ngôn ngữ lập trình, nhưng cũng tuân theo
một số qui ước ban đầu- Ta gọi dạng này là dạng giả mã. Tuỳ theo việc định hướng
cài đặt thuật toán theo ngôn ngữ lập trình nào mà tả fiễn đạt thuật toán gần với ngôn
ngữ ấy. Trong tài liệu naứy ta trình bày các thuật toán dưới dạng giả mã của ngôn
ngữ lập trình C. Dưới đây là một số quy ước của ngôn ngữ lập trình C:
* Các ký tự
- Bộ chữ cái: 26 chữ cái
- 10 chữ số thập phân.
- Các dấu phép toán số học.
- Các dấu phép toán quan hệ.
...
* Các phép toán số học và logic
Các từ sau xem như là các từ khoá : if, else, case, for, while , do while
...
3
- * Các phép toán số học và logic
- Các phép toán số học : +, -, *, /, %.
- Các phép toán Logic : &&, ||, !
* Lệnh gán: biến=biểu thức;
* Khối lệnh:
{
A1;
A2;
...
An;
}
* Cấu trúc rẽ nhánh if
Toán tử if cho phép lựa chọn chạy theo một trong hai nhánh tuỳ thuộc vào sự
bằng không và khác không của biểu thức. Nó có hai cách viết sau :
if (biểu thức) if (biểu thức)
khối lệnh 1 khối lệnh 1
/* Dạng một */ else
khối lệnh 2
/* Dạng hai */
Sự lồng nhau của các toán tử if :
C cho phép sử dụng các toán tử if lồng nhau có nghĩa là trong các khối lệnh
(1 và 2) ở trên có thể chứa các toán tử if - else khác. Trong trường hợp này, nếu
không sử dụng các dấu đóng mở ngoặc cho các khối thì sẽ có thể nhầm lẫn giữa các
if-else. Chú ý là máy sẽ gắn toán tử else với toán tử if không có else gần nhất.
* Cấu trúc rẽ nhánh - toán tử switch:
switch (biểu thức nguyên)
{
case n1
khối lệnh 1
case n2
4
- khối lệnh 2
.......
case nk
khối lệnh k
[ default
khối lệnh k+1]
}
Với ni là các số nguyên, hằng ký tự hoặc biểu thức hằng. Các ni cần có giá
trị khác nhau. Đoạn chương trình nằm giữa các dấu { } gọi là thân của toán tử
switch.
default là một thành phần không bắt buộc phải có trong thân của switch.
* Cấu trúc lặp với toán tử while :
Toán tử while dùng để xây dựng chu trình lặp dạng :
while (biểu thức)
Lệnh hoặc khối lệnh;
Như vậy toán tử while gồm một biểu thức và thân chu trình. Thân chu trình
có thể là một lệnh hoặc một khối lệnh.
Hoạt động của chu trình như sau :
Máy xác định giá trị của biểu thức, tuỳ thuộc giá trị của nó máy sẽ chọn cách
thực hiện như sau :
Nếu biểu thức có giá trị 0 (biểu thức sai), máy sẽ ra khỏi chu trình và chuyển
tới thực hiện câu lệnh tiếp sau chu trình trong chương trình.
Nếu biểu thức có giá trị khác không (biểu thức đúng), máy sẽ thực hiện lệnh
hoặc khối lệnh trong thân của while. Khi máy thực hiện xong khối lệnh này nó lại
thực hiện xác định lại giá trị biểu thức rồi làm tiếp các bước như trên.
* Cấu trúc lặp với toán tử for :
Toán tử for dùng để xây dựng cấu trúc lặp có dạng sau :
for (biểu thức 1; biểu thức 2; biểu thức 3)
Lệnh hoặc khối lệnh ;
Toán tử for gồm ba biểu thức và thân for. Thân for là một câu lệnh hoặc một
khối lệnh viết sau từ khoá for. Bất kỳ biểu thức nào trong ba biểu thức trên có thể
5
- vắng mặt nhưng phải giữ dấu ;
Thông thường biểu thức 1 là toán tử gán để tạo giá trị ban đầu cho biến điều
khiển, biểu thức 2 là một quan hệ logic biểu thị điều kiện để tiếp tục chu trình, biểu
thức ba là một toán tử gán dùng để thay đổi giá trị biến điều khiển.
Hoạt động của toán tử for :
Toán tử for hoạt động theo các bước sau :
Xác định biểu thức 1
Xác định biểu thức 2
Tuỳ thuộc vào tính đúng sai của biểu thức 2 để máy lựa chọn một trong hai
nhánh :
Nếu biểu thức 2 có giá trị 0 (sai), máy sẽ ra khỏi for và chuyển tới câu lệnh
sau thân for.
Nếu biểu thức 2 có giá trị khác 0 (đúng), máy sẽ thực hiện các câu lệnh trong
thân for.
Tính biểu thức 3, sau đó quay lại bước 2 để bắt đầu một vòng mới của chu
trình.
* Cấu trúc do-while
Khác với các toán tử while và for, việc kiểm tra điều kiện kết thúc đặt ở đầu
chu trình, trong chu trình do while việc kiểm tra điều kiện kết thúc đặt cuối chu
trình. Như vậy thân của chu trình bao giờ cũng được thực hiện ít nhất một lần.
do
Lệnh hoặc khối lệnh;
while (biểu thức) ;
Hoạt động của chu trình như sau :
Máy thực hiện các lệnh trong thân chu trình.
Khi thực hiện xong tất cả các lệnh trong thân của chu trình, máy sẽ xác định
giá trị của biểu thức sau từ khoá while rồi quyết định thực hiện như sau :
Nếu biểu thức đúng (khác 0) máy sẽ thực hiện lặp lại khối lệnh của chu trình
lần thứ hai rồi thực hiện kiểm tra lại biểu thức như trên.
Nếu biểu thức sai (bằng 0) máy sẽ kết thúc chu trình và chuyển tới thực hiện
lệnh đứng sau toán tử while.
6
- Những điều lưu ý với toán tử while ở trên hoàn toàn đúng với do while.
* Câu lệnh break
Câu lệnh break cho phép ra khỏi các chu trình với các toán tử for, while, do
while và switch. Khi có nhiều chu trình lồng nhau, câu lệnh break sẽ đưa máy ra
khỏi chu trình bên trong nhất chứa nó không cần điều kiện gì.
* Câu lệnh continue :
Trái với câu lệnh break, lệnh continue dùng để bắt đầu một vòng mới của
chu trình chứa nó. Trong while và do while, lệnh continue chuyển điều khiển về
thực hiện ngay phần kiểm tra, còn trong for điều khiển được chuyển về bước khởi
đầu lại (tức là bước : tính biểu thức 3, sau đó quay lại bước 2 để bắt đầu một vòng
mới của chu trình). Lệnh continue chỉ áp dụng cho chu trình chứ không áp dụng cho
switch.
1.4. Thiết kế thuật toán
1.4.1. Modul hoá và thiết kế từ trên xuống
Các bài toán giải được trên máy tính ngày càng phức tạp và đa dạng. Các
thuật toán giải chúng ngày càng có quy mô lớn đòi hỏi nhiều thời gian và công sức
của nhiều người. Tuy nhiên công việc sẽ đơn giản hơn nếu như ta chia bài toán ra
thành các bài toán nhỏ. Điều đó cũng có nghĩa là nếu coi bài toán là modul chính thì
cần chia thành các modul con. Đến lượt mình các modul con lại phân rã thành các
modul con thích hợp...
Như vậy việc tổ chức lời giải thể hiện theo một cấu trúc phân cấp. Chiến thuật
giải bài toán như vậy là “chia để trị”, thể hiện chiến thuật đó ta
dùng thiết kế từ trên xuống. Đó là cách nhìn nhận vấn đề một cách tổng quát, đề cập
đến các công việc chính, sau đó mới bổ sung dần các chi tiết.
1.4.2. Phƣơng pháp làm mịn dần (tinh chỉnh từng bƣớc)
Đầu tiên thuật toán được trình bày dưới dạng ngôn ngữ tự nhiên thể hiện ý
chính công việc. Các bước sau sẽ chi tiết hóa dần tương ứng với các công việc nhỏ
hơn. Đó là các bước làm mịn dần đặc tả thuật toán và hướng về ngôn ngữ lập trình
mà ta dự định cài đặt.
Quá trình thiết kế và phát triển thuật toán sẽ thể hiện dần từ ngôn ngữ tự
nhiên, sang ngôn ngữ mã giả rồi đến ngôn ngữ lập trình, và đi từ mức “làm cái
gì“đến “làm như thế nào”.
7
- 1.4.3. Một số kỹ thuật thiết kế
Trên cơ sở lý thuyết máy Turing, người ta chia được các bài toán thành 2 lớp
không giao nhau : Lớp giải được bằng thuật toán, và lớp không giải được bằng thuật
toán.
Đối với lớp các bài toán giải được bằng thuật toán, dựa vào các đặc trưng của
quá trình thiết kế của thuật toán, ta có thể chỉ ra một số các kỹ thuật thiết kế thuật
toán cơ bản sau đây :
1) Kỹ thuật chia để trị
Chia bài toán thành các bài toán đủ nhỏ, giải các bài toán nhỏ rồi tổng hợp kết
quả lại .
2) Kỹ thuật quay lui
Tìm kiếm theo ưu tiên.
Đối với mỗi bước thuật toán, ưu tiên theo độ rộng hay chiều sâu để tìm kiếm.
Chẳng hạn thuật toán giải bài toán 8 hậu.
3) Kỹ thuật tham lam
Ý tưởng là : Xác định trật tự xử lý để có lợi nhất, Sắp xếp dữ liệu theo trật tự
đó, rồi xử lý dữ liệu theo trật tự đã nêu. Công sức bỏ ra là tìm ra trật tự đó. Chẳng
hạn thuật toán tìm cây khung nhỏ nhất.
4) Kỹ thuật nhánh và cận
Trong quá trình tìm kiếm lời giải, ta phân hoạch tập các phương án của bài
toán ra thành hai hay nhiều tập con được biểu diễn như là các nút của cây tìm kiếm
và cố gắng bằng phép đánh giá cận cho các nút, tìm cách loại bỏ các nhánh của cây
mà ta biết chắc không chứa phương án tối ưu.
5) Kỹ thuật Quy hoạch động
Kỹ thuật quy hoạch động dựa vào một nguyên lý, gọi là nguyên lý tối ưu của
Bellman :
“ Nếu lời giải của bài toán là tối ưu thì lời giải của các bài toán con cũng tối
ưu ”.
Kỹ thuật này tổ chức tìm kiếm lời giải theo kiểu từ dưới lên. Xuất phát từ các
bài toán con nhỏ và đơn giản nhất, tổ hợp các lời giải của chúng để có lời giải của
bài toán con lớn hơn...và cứ như thế cuối cùng được lời giải của bài toán ban đầu.
8
- 1.5. Phân tích thuËt toán
Trong khi giải một bài toán chúng ta có thể có một số thuật toán khác nhau,
vấn đề là cần phải đánh giá các thuật toán đó để lựa chọn một thuật toán tốt (nhất).
Thông thường thì ta sẽ căn cứ vào các tiêu chuẩn sau:
- Thuật toán đơn giản
- Thuật toán thực hiện nhanh
Khi chúng ta viết một chương trình để sử dụng một vài lần thì yêu cầu thuật
toán đơn giản là quan trọng. Chúng ta cần một giải thuật dễ viết chương trình để
nhanh chóng có được kết quả, thời gian thực hiện chương trình không được đề cao
vì dù sao thì chương trình đó cũng chỉ sử dụng một vài lần mà thôi.
Tuy nhiên khi một chương trình được sử dụng nhiều lần thì yêu cầu tiết kiệm
thời gian thực hiện chương trình lại rất quan trọng đặc biệt đối với những chương
trình mà khi thực hiện cần dữ liệu nhập lớn do đó yêu cầu thuật toán thực hiện
nhanh sẽ được xem xét một cách kĩ càng. Ta gọi nó là hiệu quả thời gian thực hiện
của thuật toán. Hơn nữa khối lượng dữ liệu lớn mà dung lượng bộ nhớ lại có giới
hạn thì không thể bỏ qua yêu cầu về tiết kiệm bộ nhớ được. Tuy nhiên cân đối giữa
yêu cầu về thời gian và không gian không mấy khi có được một giải phấp trọn vẹn.
Sau đây ta sẽ chỉ chú ý đến việc phân tích thời gian thực hiện thuật toán.
1.5.1. Thêi gian thùc hiÖn thuËt toán
Một phương pháp để xác định hiệu quả thời gian thực hiện của một thuật
toán là lập trình nó và đo lường thời gian thực hiện của hoạt động trên một máy
tính xác định đối với tập hợp được chọn lọc các dữ liệu vào.
Thời gian thực hiện không chỉ phụ thuộc vào thuật toán mà còn phụ thuộc
vào tập các chỉ thị của máy tính, chất lượng của máy tính và kĩ xảo của người lập
trình. Sự thi hành cũng có thể điều chỉnh để thực hiện tốt trên tập đặc biệt các dữ
liệu vào được chọn. Ðể vượt qua các trở ngại này, các nhà khoa học máy tính đã
chấp nhận tính phức tạp của thời gian được tiếp cận như một sự đo lường cơ bản sự
thực thi của thuật toán. Thuật ngữ tính hiệu quả sẽ đề cập đến sự đo lường này và
đặc biệt đối với sự phức tạp thời gian trong trường hợp xấu nhất.
Nói chung thì thời gian thực hiện thuật toán không chỉ phụ thuộc vào kích
thước mà còn phụ thuộc vào tính chất của dữ liệu vào. Nghĩa là dữ liệu vào có cùng
kích thước nhưng thời gian thực hiện giải thuật có thể khác nhau. Chẳng hạn
chương trình sắp xếp dãy số nguyên tăng dần, khi ta cho vào dãy có thứ tự thì thời
gian thực hiện khác với khi ta cho vào dãy chưa có thứ tự, hoặc khi ta cho vào một
9
- dãy đã có thứ tự tăng thì thời gian thực hiện cũng khác so với khi ta cho vào một
dãy đã có thứ tự giảm.
Vì vậy thường ta coi T(n) là thời gian thực hiện chương trình trong trường
hợp xấu nhất trên dữ liệu vào có kích thước n, tức là: T(n) là thời gian lớn nhất để
thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n.
Để đánh giá thời gian thực hiện thuật toán người ta tìm cách đánh giá độc lập
với các yếu tố bên ngoài như máy tính hay các yếu tố liên quan đến máy tính. Cách
đánh giá như vậy dẫn tới khái niệm về cấp độ lớn của thời gian thực hiện thuật toán
hay độ phức tạp tính toán của thuật toán.
1.5.2. Độ phức tạp tính toán của thuật toán
Nếu thời gian thực hiện một thuật toán là T(n) =cn2 (với c là hằng số, n là
kích thước dữ liệu đầu vào) thì ta nói: Độ phức tạp tính toán của thuật toán này có
cấp là n2 (hay cấp độ lớn của thời gian thực hiện thuật toán là n2) và ta ký hiệu:
T(n) = O(n2) (ký hiệu chữ O lớn)
Một cách tổng quát có thể định nghĩa:
Một hàm f(n) được xác định là O(g(n)) và viết là f(n) =O(g(n)) và được gọi
là cấp g(n) nếu tồn tại các hằng số c và n0 sao cho:
f(n) ≤ cg(n) khi n ≥ n0
nghĩa là f(n) bị chặn trên bởi một hằng số nhân với g(n), với mọi giá trị của n tăng
từ một điểm nào đó. Thông thường các hàm thể hiện độ phức tạp tính toán của thuật
toán có dạng :
log2n, n, nlog2, n2, n3, 2n, n!, nn
Sau đây là bảng giá trị của một số hàm đó
Log2n n nlog2n n2 n3 2n
0 1 0 1 1 2
1 2 2 4 8 4
2 4 8 16 64 16
3 8 24 64 512 256
4 16 64 256 40963 65536
5 32 160 1024 32768 2.147.483.648
Hình 1.1. Bảng giá trị của một số hàm số
Các hàm như 2n , n!, nn được gọi là hàm loại mũ. Một thuật toán mà thời gian
10
- thực hiện của nó có cấp là các hàm loại mũ thì tốc độ rất chậm. Các hàm như n3 , n2,
nlog2n, n, log2n được gọi là các hàm loại đa thức. Một thuật toán mà thời gian thực
hiện có độ phức tạp là một hàm đa thức thì chấp nhận được tức là có thể cài đặt để
thực hiện, còn các thuật toán có độ phức tạp hàm mũ thì phải tìm cách cải tiến thuật
toán.
Các quy tắc xác định độ phức tạp của thuật toán:
Xác định độ phức tạp tính toán của một thuật toán bất kỳ có thể dẫn tới
những bài toán phức tạp. Tuy nhiên, trong thực tế, đối với một số thuật toán ta cũng
có thể phân tích được bằng một số quy tắc đơn giản.
* Quy tắc tổng:
Giả sử T1(n) và T2(n) là độ phức tạp tính toán của hai đoạn chương trình P1
và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì độ phức tạp tính toán khi thực hiện P1
và tiếp theo là P2 sẽ là: T1(n) + T2(n) = O(max (f(n),g(n))
Chứng minh:
Vì T1(n) = O(f(n)); T2(n) = O(g(n)) nên theo định nghĩa tồn tại các hằng số
dương c1 , n1 và c2 , n2 sao cho:
T1(n) ≤ c1 f(n), với mọi n > n1
T2(n) ≤ c2 g(n) với mọi n > n2.
Chọn c = c1 + c2; n0 = max {n1, n2}.
Khi đó: T1(n) + T2(n) c1 f(n) + c2 g(n) c max(f(n), g(n)) , với mọi n
> n0 .
Do vậy: O(f(n)) + O(g(n)) = O(max(f(n), g(n))).
Ví dụ 1.1.
Trong một chương trình có 3 bước thực hiện mà độ phức tạp tính toán từng
bước lần lượt là O(n2), O(n3) và O(nlog2n) thì độ phức tạp tính toán hai bước đầu là
O(max (n2, n3) = O(n3). Độ phức tạp tính toán của chương trình sẽ là: O(max(n3,
nlog2n)) = O(n3).
Nhận xét:
Từ quy tắc này có thể nhận thấy rằng: nếu g(n) ≤ f(n) với mọi n ≥ n0 thì:
O(f(n)+g(n)) = O(f(n)).
Chẳng hạn: O(n4+n2) = O(n4)
O(n + log2n) = O(n).
11
- * Quy tắc nhân:
Giả sử T1(n) và T2(n) là độ phức tạp tính toán của hai đoạn chương trình P1
và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì độ phức tạp tính toán khi P1 và P2 lồng
nhau sẽ là: T1(n).T2(n) = O(f(n).g(n))
Chứng minh:
Ta có: T1(n) = O(f(n)), T2(n) = O(g(n) theo định nghĩa tồn tại các hằng số
dương c1 , n1và c2 , n2 sao cho:
T1(n) ≤ c1 f(n), với mọi n > n1
T2(n) ≤ c2 g(n) với mọi n > n2.
Chọn c = c1 * c2; n0 = max {n1, n2}.
Khi đó: T1(n).T2(n) c1 f(n) c2 g(n) = c (f(n) g(n)).
Do vậy: T1(n).T2(n) = O(f(n).g(n)).
Ví dụ 1.2.
Câu lệnh gán : x = x+1 có thời gian thực hiện bằng c (hằng số) nên được
đánh giá là O(1).
Câu lệnh: for ( i=1; i
- Ví dụ 1.3.
Giải thuật tính giá trị của ex theo công thức gần đúng:
ex = 1 + x/1! +x2/2! + …+ xn/n! với x và n cho trước
EXP1();
{
scanf(x) ;
S =1;
for (i=1;i
- Bây giờ độ phức tạp tính toán lại là: T(n) = O(n). Vì phép gán p=p*x/i chỉ thực
hiện n lần.
Ví dụ 1.4.
Thuật toán sắp xếp kiểu nổi bọt
void Bubble(a)
{
for(i=1;i=i+1; j--)
if (a[j-1]>a[j])
{
tg:= a[j-1];
a[j-1] := a[j];
a[j]:= tg;
}
}
Trong thuật toán ta coi phép so sánh (a[j-1]>a[j]) là phép toán tích cực. Phép
toán này nằm trong vòng lặp for(j=n; j>=i+1; j--) nên nó được thực hiện (n-i) lần.
Vòng lặp for(j=n; j>=i+1; j--) nằm trong vòng lặp for(i=1;ia[j]) sẽ là:
n 1
n( n 1 )
( n i )
i 1 2
Nên độ phức tạp tính toán của thuật toán là O(n2).
Chú ý:
Ta biết rằng thời gian thực hiện thuật toán không phải chỉ phụ thuộc vào
kích thước dữ liệu mà còn phụ thuộc vào tình trạng dữ liệu nhập nữa. Chẳng hạn,
khi xếp tăng dần một dãy các số nguyên mà dãy các so nguyên đĩ đã có sẵn thứ tự
tăng dần, hoặc ngược lại, hoặc ngẫu nhiên. Lúc đó khi phân tích thời gian thực hiện
thuật toán ta sẽ phải xét tới: đối với mọi dữ liệu vào có kích thước n thì T(n) trong
trường hợp tốt nhất, xấu nhất là như thế nào? T(n) trung bình? Việc xác định T(n)
trung bình thường khó và phức tạp đòi hỏi những công cụ toán học đặc biệt, hơn
nữa việc tính trung bình có thể có nhiều cách quan niệm khác nhau. Trong trường
hợp T(n) khó xác định người ta thường đánh giá thuật toán qua giá trị xấu nhất của
T(n)
14
- VÝ dô 1.5.
timkiem(v)
/*Cho vectơ V có n phần tử, thuật toán này thực hiện tìm trong V một phần tử có
giá trị bằng X cho trước. Nếu tìm thấy trả về chỉ số của phần tử đó, nếu không tìm
thấy trả về giá trị 0*/
i =1;
while ((V[i] !=X)&& (i
nguon tai.lieu . vn