Giáo trình Giải thuật - Nguyễn Văn Linh
Th.s. NGUYỄN VĂN LINH
GIẢI THUẬT
Được biên soạn trong khuôn khổ dự án ASVIET002CNTT
”Tăng cường hiệu quả đào tạo và năng lực tự đào tạo của sinh viên
khoa Công nghệ Thông tin - Đại học Cần thơ”
ĐẠI HỌC CẦN THƠ - 12/2003
LỜI NÓI ÐẦU
N. Wirth, một nhà khoa học máy tính nổi tiếng, tác giả của ngôn
ngữ lập trình Pascal, đã đặt tên cho một cuốn sách của ông là
“Cấu trúc dữ liệu + Giải thuật = Chương trình”.
Ðiều đó nói lên tầm quan trọng của giải thuật trong lập trình nói
riêng và trong khoa học máy tính nói chung. Vì lẽ đó giải thuật, với tư
cách là một môn học, cần phải được sinh viên chuyên ngành tin học
nghiên cứu một cách có hệ thống.
Môn học “Giải thuật” được bố trí sau môn “Cấu trúc dữ liệu”
trong chương trình đào tạo kỹ sư tin học nhằm giới thiệu cho sinh viên
những kiến thức cơ bản nhất, những kỹ thuật chủ yếu nhất của việc
PHÂN TÍCH và THIẾT KẾ giải thuật. Các kỹ thuật được trình bày ở
đây đã được các nhà khoa học tin học tổng kết và vận dụng trong cài đặt
các chương trình. Việc nắm vững các kỹ thuật đó sẽ rất bổ ích cho sinh
viên khi phải giải quyết một vấn đề thực tế.
Giáo trình này được hình thành trên cơ sở tham khảo cuốn sách
“Data Structure and Algorithms” của A.V Aho, những kinh nghiệm
giảng dạy của bản thân và các bạn đồng nghiệp.
Mặc dù đã có nhiều cố gắng trong quá trình biên soạn nhưng chắc
chắn còn nhiều thiếu sót, rất mong nhận được sự đóng góp của quý bạn
đọc.
Cần thơ, ngày 8 tháng 12 năm 2003
Nguyễn Văn Linh
Giải thuật
Mục lục
MỤC LỤC
PHẦN TỔNG QUAN ................................................. i
Chương 1: KĨ THUẬT PHÂN TÍCH GIẢI THUẬT .......................... 1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
TỔNG QUAN................................................................................................................... 1
SỰ CẦN THIẾT PHẢI PHÂN TÍCH GIẢI THUẬT....................................................... 2
THỜI GIAN THỰC HIỆN CỦA GIẢI THUẬT.............................................................. 2
TỶ SUẤT TĂNG VÀ ÐỘ PHỨC TẠP CỦA GIẢI THUẬT .......................................... 3
CÁCH TÍNH ÐỘ PHỨC TẠP.......................................................................................... 4
PHÂN TÍCH CÁC CHƯƠNG TRÌNH ÐỆ QUY............................................................. 7
TỔNG KẾT CHƯƠNG 1 ............................................................................................... 16
BÀI TẬP CHƯƠNG 1 ................................................................................................................. 16
Chương 2: SẮP XẾP ............................................. 18
2.1
2.2
2.3
2.4
2.5
2.6
2.7
TỔNG QUAN................................................................................................................. 18
BÀI TOÁN SẮP XẾP..................................................................................................... 19
CÁC PHƯƠNG PHÁP SẮP XẾP ÐƠN GIẢN.............................................................. 20
QUICKSORT ................................................................................................................. 25
HEAPSORT.................................................................................................................... 31
BINSORT ....................................................................................................................... 39
TỔNG KẾT CHƯƠNG 2 ............................................................................................... 44
BÀI TẬP CHƯƠNG 2 ................................................................................................................. 44
Chương 3: KĨ THUẬT THIẾT KẾ GIẢI THUẬT ........................... 45
3.1
3.2
3.3
3.4
3.5
3.6
3.7
TỔNG QUAN................................................................................................................. 45
KĨ THUẬT CHIA ÐỂ TRỊ ............................................................................................. 45
KĨ THUẬT “THAM ĂN”............................................................................................... 50
QUY HOẠCH ÐỘNG.................................................................................................... 56
KĨ THUẬT QUAY LUI ................................................................................................. 63
KĨ THUẬT TÌM KIẾM ÐỊA PHƯƠNG ........................................................................ 78
TỔNG KẾT CHƯƠNG 3 ............................................................................................... 82
BÀI TẬP CHƯƠNG 3 ................................................................................................................. 82
Chương 4: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT LƯU TRỮ NGOÀI ......... 85
4.1
4.2
4.3
4.4
4.5
4.6
TỔNG QUAN................................................................................................................. 85
MÔ HÌNH XỬ LÝ NGOÀI............................................................................................ 85
ÐÁNH GIÁ CÁC GIẢI THUẬT XỬ LÝ NGOÀI......................................................... 86
SẮP XẾP NGOÀI........................................................................................................... 87
LƯU TRỮ THÔNG TIN TRONG TẬP TIN ................................................................. 93
TỔNG KẾT CHƯƠNG 4 ............................................................................................. 103
BÀI TẬP CHƯƠNG 4 ............................................................................................................... 104
Giải thuật
Tổng quan
PHẦN TỔNG QUAN
1. Mục đích yêu cầu
Môn học giải thuật cung cấp cho sinh viên một khối lượng kiến thức tương đối
hoàn chỉnh về phân tích và thiết kế các giải thuật lập trình cho máy tính. Sau khi
học xong môn học này, sinh viên cần:
- Nắm được khái niệm thời gian thực hiện của chương trình, độ phức tạp của
giải thuật. Biết cách phân tích, đánh giá giải thuật thông qua việc tính độ
phức tạp.
- Nắm được các giải thuật sắp xếp và phân tích đánh giá được các giải thuật
sắp xếp.
- Nắm được các kĩ thuật thiết kế giải thuật, vận dụng vào việc giải một số bài
toán thực tế.
- Nắm được các phương pháp tổ chức lưu trữ thông tin trong tập tin và các giải
thuật tìm, xen, xoá thông tin trong tập tin.
2. Đối tượng sử dụng
Môn học giải thuật được dùng để giảng dạy cho các sinh viên sau:
- Sinh viên năm thứ 3 chuyên ngành Tin học.
- Sinh viên năm thứ 3 chuyên ngành Điện tử (Viễn thông, Tự động hoá…)
- Sinh viên Toán-Tin.
3. Nội dung cốt lõi
Trong khuôn khổ 45 tiết, giáo trình được cấu trúc thành 4 chương
- Chương 1: Kĩ thuật phân tích đánh giá giải thuật. Chương này đặt vấn đề tại
sao cần phải phân tích, đánh giá giải thuật và phân tích đánh giá theo phương
pháp nào. Nội dung chương 1 tập trung vào khái niệm độ phức tạp thời gian
của giải thuật và phương pháp tính độ phức tạp giải thuật của một chương
trình bình thường, của chương trình có gọi các chương trình con và của các
chương trình đệ quy.
- Chương 2: Sắp xếp. Chương này trình bày các giải thuật sắp xếp, một thao
tác thường được sử dụng trong việc giải các bài toán máy tính. Sẽ có nhiều
giải thuật sắp xếp từ đơn giản đến nâng cao sẽ được giới thiệu ở đây. Với
mỗi giải thuật, sẽ trình bày ý tưởng giải thuật, ví dụ minh hoạ, cài đặt chương
trình và phân tích đánh giá.
- Chương 3: Kĩ thuật thiết kế giải thuật. Chương này trình bày các kĩ thuật
phổ biến để thiết kế các giải thuật. Các kĩ thuật này gồm: Chia để trị, Quy
hoạch động, Tham ăn, Quay lui và Tìm kiếm địa phương. Với mỗi kĩ thuật sẽ
trình bày nội dung kĩ thuật và vận dung vào giải các bài toán khá nổi tiếng
như bài toán người giao hàng, bài toán cái ba lô, bài toán cây phủ tối thiểu...
- Chương 4: Cấu trúc dữ liệu và giải thuật lưu trữ ngoài. Chương này trình
bày các cấu trúc dữ liệu được dùng để tổ chức lưu trữ tập tin trên bộ nhớ
ngoài và các giải thuật tìm kiếm, xen xoá thông tin trên các tập tin đó.
4. Kiến thức tiên quyết
Để học tốt môn học giải thuật cần phải có các kiến thức sau:
- Kiến thức toán học.
- Kiến thức và kĩ năng lập trình căn bản.
Giải thuật
Tổng quan
- Kiến thức về cấu trúc dữ liệu và các giải thuật thao tác trên các cấu trúc dữ
liệu.
Trong chương trình đào tạo, Cấu trúc dữ liệu là môn học tiên quyết của môn Giải
thuật.
5. Danh mục tài liệu tham khảo
[1] A.V. Aho, J.E. Hopcroft, J.D. Ullman; Data Structures and Algorithms;
Addison-Wesley; 1983.
[2] Jeffrey H Kingston; Algorithms and Data Structures; Addison-Wesley;
1998.
[3] Đinh Mạnh Tường; Cấu trúc dữ liệu & Thuật toán; Nhà xuất bản khoa học
và kĩ thuật; Hà nội-2001.
[4] Đỗ Xuân Lôi; Cấu trúc dữ liệu & Giải thuật; 1995.
[7] Trang web bài giảng về giải thuật:
[8] Trang tìm kiếm các giải thuật:
Giải thuật
Kĩ thuật phân tích giải thuật
CHƯƠNG 1: KĨ THUẬT PHÂN TÍCH GIẢI THUẬT
1.1 TỔNG QUAN
1.1.1 Mục tiêu
Sau khi học chương này, sinh viên cần phải trả lời được các câu hỏi sau:
- Tại sao cần phân tích đánh giá giải thuật?
- Tiêu chuẩn nào để đánh giá một giải thuật là tốt?
- Phương pháp đánh giá như thế nào? (đánh giá chương trình không gọi
chương trình con, đánh giá một chương trình có gọi các chương trình con
không đệ quy và đánh giá chương trình đệ quy).
1.1.2 Kiến thức cơ bản cần thiết
Các kiến thức cơ bản cần thiết để học chương này bao gồm:
- Kiến thức toán học: Công thức tính tổng n số tự nhiên đầu tiên, công thức
tính tổng n số hạng đầu tiên của một cấp số nhân, phương pháp chứng minh
quy nạp và các kiến thức liên quan đến logarit (biến đổi logarit, tính chất
đồng biến của hàm số logarit).
- Kĩ thuật lập trình và lập trình đệ quy.
1.1.3 Tài liệu tham khảo
A.V. Aho, J.E. Hopcroft, J.D. Ullman. Data Structures and Algorithms. Addison-
Wesley. 1983. (Chapters 1, 9).
Jeffrey H Kingston; Algorithms and Data Structures; Addison-Wesley; 1998.
(Chapter 2).
Đinh Mạnh Tường. Cấu trúc dữ liệu & Thuật toán. Nhà xuất bản khoa học và kĩ
1.1.4 Nội dung cốt lõi
Trong chương này chúng ta sẽ nghiên cứu các vấn đề sau:
• Sự cần thiết phải phân tích các giải thuật.
• Thời gian thực hiện của chương trình.
• Tỷ suất tăng và độ phức tạp của giải thuật.
• Tính thời gian thực hiện của chương trình.
• Phân tích các chương trình đệ quy.
Nguyễn Văn Linh
Trang 1
Giải thuật
Kĩ thuật phân tích giải thuật
1.2 SỰ CẦN THIẾT PHẢI PHÂN TÍCH GIẢI THUẬT
Trong khi giải một bài toán chúng ta có thể có một số giải thuật khác nhau, vấn đề
là cần phải đánh giá các giải thuật đó để lựa chọn một giải thuật tốt (nhất). Thông
thường thì ta sẽ căn cứ vào các tiêu chuẩn sau:
1.- Giải thuật đúng đắn.
2.- Giải thuật đơn giản.
3.- Giải thuật thực hiện nhanh.
Với yêu cầu (1), để kiểm tra tính đúng đắn của giải thuật chúng ta có thể cài đặt giải
thuật đó 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ể giải thuật đú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 giải thuật sai chứ chưa
chứng minh được là nó đúng. Tính đúng đắn của giải thuật cần phải được chứng
minh bằng toán học. Tất nhiên đ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 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 giải thuật.
1.3 THỜI GIAN THỰC HIỆN CỦA CHƯƠNG TRÌNH
Một phương pháp để xác định hiệu quả thời gian thực hiện của một giải thuật 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 giải thuật 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 giải thuật. 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.
1.3.1 Thời gian thực hiện chương trình.
Thời gian thực hiện một chương trình là một hàm của kích thước dữ liệu vào, ký
hiệu T(n) trong đó n là kích thước (độ lớn) của dữ liệu vào.
Ví dụ 1-1: Chương trình tính tổng của n số có thời gian thực hiện là T(n) = cn trong đó c
là một hằng số.
Nguyễn Văn Linh
Trang 2
Giải thuật
Kĩ thuật phân tích giải thuật
Thời gian thực hiện chương trình là một hàm không âm, tức là T(n) ≥ 0 ∀ n ≥ 0.
1.3.2 Ðơn vị đo thời gian thực hiện.
Ðơn vị của T(n) không phải là đơn vị đo thời gian bình thường như giờ, phút giây...
mà thường được xác định bởi số các lệnh được thực hiện trong một máy tính lý
tưởng.
Ví dụ 1-2: Khi ta nói thời gian thực hiện của một chương trình là T(n) = Cn thì có
nghĩa là chương trình ấy cần Cn chỉ thị thực thi.
1.3.3 Thời gian thực hiện trong trường hợp xấu nhất.
Nói chung thì thời gian thực hiện chương trình 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 chương trình 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 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.
1.4 TỶ SUẤT TĂNG VÀ ÐỘ PHỨC TẠP CỦA GIẢI THUẬT
1.4.1 Tỷ suất tăng
Ta nói rằng hàm không âm T(n) có tỷ suất tăng (growth rate) f(n) nếu tồn tại các
hằng số C và N0 sao cho T(n) ≤ Cf(n) với mọi n ≥ N0.
Ta có thể chứng minh được rằng “Cho một hàm không âm T(n) bất kỳ, ta luôn tìm
được tỷ suất tăng f(n) của nó”.
Ví dụ 1-3: Giả sử T(0) = 1, T(1) = 4 và tổng quát T(n) = (n+1)2. Ðặt N0 = 1 và C =
4 thì với mọi n ≥1 chúng ta dễ dàng chứng minh được rằng T(n) = (n+1)2 ≤ 4n2 với
mọi n ≥ 1, tức là tỷ suất tăng của T(n) là n2.
Ví dụ 1-4: Tỷ suất tăng của hàm T(n) = 3n3 + 2n2 là n3. Thực vậy, cho N0 = 0 và C
= 5 ta dễ dàng chứng minh rằng với mọi n ≥ 0 thì 3n3 + 2n2 ≤ 5n3
1.4.2 Khái niệm độ phức tạp của giải thuật
Giả sử ta có hai giải thuật P1 và P2 với thời gian thực hiện tương ứng là T1(n) =
100n2 (với tỷ suất tăng là n2) và T2(n) = 5n3 (với tỷ suất tăng là n3). Giải thuật nào
sẽ thực hiện nhanh hơn? Câu trả lời phụ thuộc vào kích thước dữ liệu vào. Với n <
20 thì P2 sẽ nhanh hơn P1 (T2<T1), do hệ số của 5n3 nhỏ hơn hệ số của 100n2
(5<100). Nhưng khi n > 20 thì ngươc lại do số mũ của 100n2 nhỏ hơn số mũ của 5n3
(2<3). Ở đây chúng ta chỉ nên quan tâm đến trường hợp n>20 vì khi n<20 thì thời
gian thực hiện của cả P1 và P2 đều không lớn và sự khác biệt giữa T1 và T2 là
không đáng kể.
Nguyễn Văn Linh
Trang 3
Giải thuật
Kĩ thuật phân tích giải thuật
Như vậy một cách hợp lý là ta xét tỷ suất tăng của hàm thời gian thực hiện chương
trình thay vì xét chính bản thân thời gian thực hiện.
Cho một hàm T(n), T(n) gọi là có độ phức tạp f(n) nếu tồn tại các hằng C, N0 sao
cho T(n) ≤ Cf(n) với mọi n ≥ N0 (tức là T(n) có tỷ suất tăng là f(n)) và kí hiệu T(n)
là O(f(n)) (đọc là “ô của f(n)”)
Ví dụ 1-5: T(n)= (n+1)2 có tỷ suất tăng là n2 nên T(n)= (n+1)2 là O(n2)
Chú ý: O(C.f(n))=O(f(n)) với C là hằng số. Ðặc biệt O(C)=O(1)
Nói cách khác độ phức tạp tính toán của giải thuật là một hàm chặn trên của hàm
thời gian. Vì hằng nhân tử C trong hàm chặn trên không có ý nghĩa nên ta có thể bỏ
qua vì vậy hàm thể hiện độ phức tạp có các dạng thường gặp sau: log2n, n, nlog2n,
n2, n3, 2n, n!, nn. Ba hàm cuối cùng ta gọi là dạng hàm mũ, các hàm khác gọi là hàm
đa thức. Một giải thuật 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 giải thuật có độ phức
tạp hàm mũ thì phải tìm cách cải tiến giải thuật.
Vì ký hiệu log2n thường có mặt trong độ phức tạp nên trong khôn khổ tài liệu này,
ta sẽ dùng logn thay thế cho log2n với mục đích duy nhất là để cho gọn trong cách
viết.
Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến hiệu quả của thời gian
thực hiện của chương trình nên ta có thể xem việc xác định thời gian thực hiên của
chương trình chính là xác định độ phức tạp của giải thuật.
1.5 CÁCH TÍNH ÐỘ PHỨC TẠP
Cách tính độ phức tạp của một giải thuật bất kỳ là một vấn đề không đơn giản. Tuy
nhiên ta có thể tuân theo một số nguyên tắc sau:
1.5.1 Qui tắc cộng
Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2; và
T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của đoạn hai chương trình đó
nối tiếp nhau là T(n)=O(max(f(n),g(n)))
Ví dụ 1-6: Lệnh gán x:=15 tốn một hằng thời gian hay O(1), Lệnh đọc dữ liệu
READ(x) tốn một hằng thời gian hay O(1).Vậy thời gian thực hiện cả hai lệnh trên
nối tiếp nhau là O(max(1,1))=O(1)
1.5.2 Qui tắc nhân
Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1và P2 và
T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện của đoạn hai đoạn chương
trình đó lồng nhau là T(n) = O(f(n).g(n))
1.5.3 Qui tắc tổng quát để phân tích một chương trình:
-
Thời gian thực hiện của mỗi lệnh gán, READ, WRITE là O(1)
Nguyễn Văn Linh
Trang 4
Giải thuật
Kĩ thuật phân tích giải thuật
-
-
-
Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng qui tắc
cộng. Như vậy thời gian này là thời gian thi hành một lệnh nào đó lâu nhất
trong chuỗi lệnh.
Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau THEN
hoặc sau ELSE và thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều
kiện là O(1).
Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực hiện
thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp không đổi thì thời gian
thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp.
Ví dụ 1-7: Tính thời gian thực hiện của thủ tục sắp xếp “nổi bọt”
PROCEDURE Bubble(VAR a: ARRAY[1..n] OF integer);
VAR i,j,temp: Integer;
BEGIN
{1} FOR i:=1 TO n-1 DO
{2}
{3}
{4}
{5}
{6}
FOR j:=n DOWNTO i+1 DO
IF a[j-1]>a[j]THEN BEGIN{hoán vị a[i], a[j]}
temp
a[j-1] := a[j];
a[j] := temp;
END;
:= a[j-1];
END;
Về giải thuật sắp xếp nổi bọt, chúng ta sẽ bàn kĩ hơn trong chương 2. Ở đây, chúng
ta chỉ quan tâm đến độ phức tạp của giải thuật.
Ta thấy toàn bộ chương trình chỉ gồm một lệnh lặp {1}, lồng trong lệnh {1} là lệnh
{2}, lồng trong lệnh {2} là lệnh {3} và lồng trong lệnh {3} là 3 lệnh nối tiếp nhau
{4}, {5} và {6}. Chúng ta sẽ tiến hành tính độ phức tạp theo thứ tự từ trong ra.
Trước hết, cả ba lệnh gán {4}, {5} và {6} đều tốn O(1) thời gian, việc so sánh a[j-1]
> a[j] cũng tốn O(1) thời gian, do đó lệnh {3} tốn O(1) thời gian.
Vòng lặp {2} thực hiện (n-i) lần, mỗi lần O(1) do đó vòng lặp {2} tốn O((n-i).1) =
O(n-i).
Vòng lặp {1} lặp có I chạy từ 1 đến n-1nên thời gian thực hiện của vòng lặp {1} và
cũng là độ phức tạp của giải thuật là
n−1
n(n −1)
T(n) = (n − i) =
= O(n2).
∑
2
i=1
Chú ý: Trong trường hợp vòng lặp không xác định được số lần lặp thì chúng ta phải
lấy số lần lặp trong trường hợp xấu nhất.
Ví dụ 1-8: Tìm kiếm tuần tự. Hàm tìm kiếm Search nhận vào một mảng a có n số
nguyên và một số nguyên x, hàm sẽ trả về giá trị logic TRUE nếu tồn tại một phần
tử a[i] = x, ngược lại hàm trả về FALSE.
Nguyễn Văn Linh
Trang 5
Giải thuật
Kĩ thuật phân tích giải thuật
Giải thuật tìm kiếm tuần tự là lần lượt so sánh x với các phần tử của mảng a, bắt đầu
từ a[1], nếu tồn tại a[i] = x thì dừng và trả về TRUE, ngược lại nếu tất cả các phần
tử của a đều khác X thì trả về FALSE.
FUNCTION Search(a:ARRAY[1..n] OF Integer;x:Integer):Boolean;
VAR i:Integer; Found:Boolean;
BEGIN
{1} i:=1;
{2} Found:=FALSE;
{3} WHILE(i<=n)AND (not Found) DO
{4}
IF A[i]=X THEN Found:=TRUE
ELSE i:=i+1;
{5} Search:=Found;
END;
Ta thấy các lệnh {1}, {2}, {3} và {5} nối tiếp nhau, do đó độ phức tạp của hàm
Search chính là độ phức tạp lớn nhất trong 4 lệnh này. Dễ dàng thấy rằng ba lệnh
{1}, {2} và {5} đều có độ phức tạp O(1) do đó độ phức tạp của hàm Search chính là
độ phức tạp của lệnh {3}. Lồng trong lệnh {3} là lệnh {4}. Lệnh {4} có độ phức tạp
O(1). Trong trường hợp xấu nhất (tất cả các phần tử của mảng a đều khác x) thì
vòng lặp {3} thực hiện n lần, vậy ta có T(n) = O(n).
1.5.4 Ðộ phức tạp của chương trình có gọi chương trình con không
đệ qui
Nếu chúng ta có một chương trình với các chương trình con không đệ quy, để tính
thời gian thực hiện của chương trình, trước hết chúng ta tính thời gian thực hiện của
các chương trình con không gọi các chương trình con khác. Sau đó chúng ta tính
thời gian thực hiện của các chương trình con chỉ gọi các chương trình con mà thời
gian thực hiện của chúng đã được tính. Chúng ta tiếp tục quá trình đánh giá thời
gian thực hiện của mỗi chương trình con sau khi thời gian thực hiện của tất cả các
chương trình con mà nó gọi đã được đánh giá. Cuối cùng ta tính thời gian cho
chương trình chính.
Giả sử ta có một hệ thống các chương trình gọi nhau theo sơ đồ sau:
A
B
B1
B11
C
B2
B12
Hình 1-1: Sơ đồ gọi thực hiện các chương trình con không đệ quy
Chương trình A gọi hai chương trình con là B và C, chương trình B gọi hai chương
trình con là B1 và B2, chương trình B1 gọi hai chương trình con là B11 và B12.
Ðể tính thời gian thực hiện của A, ta tính theo các bước sau:
Nguyễn Văn Linh
Trang 6
Giải thuật
Kĩ thuật phân tích giải thuật
1. Tính thời gian thực hiện của C, B2, B11 và B12. Vì các chương trình con
này không gọi chương trình con nào cả.
2. Tính thời gian thực hiện của B1. Vì B1 gọi B11 và B12 mà thời gian thực
hiện của B11 và B12 đã được tính ở bước 1.
3. Tính thời gian thực hiện của B. Vì B gọi B1 và B2 mà thời gian thực hiện
của B1 đã được tính ở bước 2 và thời gian thực hiện của B2 đã được tính ở
bước 1.
4. Tính thời gian thực hiện của A. Vì A gọi B và C mà thời gian thực hiện của
B đã được tính ở bước 3 và thời gian thực hiện của C đã được tính ở bước 1.
Ví dụ 1-9: Ta có thể viết lại chương trình sắp xếp bubble như sau: Trước hết chúng
ta viết thủ tục Swap để thực hiện việc hoàn đổi hai phần tử cho nhau, sau đso trong
thủ tục Bubble, khi cần ta sẽ gọi đến thủ tục Swap này.
PROCEDURE Swap (VAR x, y: Integer);
VAR temp: Integer;
BEGIN
temp := x;
x
y
:= y;
:= temp;
END;
PROCEDURE Bubble (VAR a: ARRAY[1..n] OF integer);
VAR i,j :Integer;
BEGIN
{1} FOR i:=1 TO n-1 DO
{2}
{3}
FOR j:=n DOWNTO i+1 DO
IF a[j-1]>a[j] THEN Swap(a[j-1], a[j]);
END;
Trong cách viết trên, chương trình Bubble gọi chương trình con Swap, do đó để tính
thời gian thực hiện của Bubble, trước hết ta cần tính thời gian thực hiện của Swap.
Dễ thấy thời gian thực hiện của Swap là O(1) vì nó chỉ bao gồm 3 lệnh gán.
Trong Bubble, lệnh {3} gọi Swap nên chỉ tốn O(1), lệnh {2} thực hiện n-i lần, mỗi
lần tốn O(1) nên tốn O(n-i). Lệnh {1} thực hiện n-1 lần nên
n−1
n(n −1)
T(n) = (n − i) =
= O(n2).
∑
2
i=1
1.6 PHÂN TÍCH CÁC CHƯƠNG TRÌNH ÐỆ QUY
Với các chương trình có gọi các chương trình con đệ quy, ta không thể áp dụng
cách tính như vừa trình bày trong mục 1.5.4 bởi vì một chương trình đệ quy sẽ gọi
chính bản thân nó. Có thể thấy hình ảnh chương trình đệ quy A như sau:
A
Hình 1-2: Sơ đồ chương trình con A đệ quy
Nguyễn Văn Linh
Trang 7
Giải thuật
Kĩ thuật phân tích giải thuật
Với phương pháp tính độ phức tạp đã trình bày trong mục 1.5.4 thì không thể thực
hiện được. Bởi vì nếu theo phương pháp đó thì, để tính thời gian thực hiên của
chương trình A, ta phải tính thời gian thực hiện của chương trình A và cái vòng luẩn
quẩn ấy không thể kết thúc được.
Với các chương trình đệ quy, trước hết ta cần thành lập các phương trình đệ quy,
sau đó giải phương trình đệ quy, nghiệm của phương trình đệ quy sẽ là thời gian
thực hiện của chương trình đệ quy.
1.6.1 Thành lập phương trình đệ quy
Phương trình đệ quy là một phương trình biểu diễn mối liên hệ giữa T(n) và T(k),
trong đó T(n) là thời gian thực hiện chương trình với kích thước dữ liệu nhập là n,
T(k) thời gian thực hiện chương trình với kích thước dữ liệu nhập là k, với k < n. Ðể
thành lập được phương trình đệ quy, ta phải căn cứ vào chương trình đệ quy.
Thông thường một chương trình đệ quy để giải bài toán kích thước n, phải có ít nhất
một trường hợp dừng ứng với một n cụ thể và lời gọi đệ quy để giải bài toán kích
thước k (k<n).
Để thành lập phương trình đệ quy, ta gọi T(n) là thời gian để giải bài toán kích
thước n, ta có T(k) là thời gian để giải bài toán kích thước k. Khi đệ quy dừng, ta
phải xem xét khi đó chương trình làm gì và tốn hết bao nhiêu thời gian, chẳng hạn
thời gian này là c(n). Khi đệ quy chưa dừng thì phải xét xem có bao nhiêu lời gọi đệ
quy với kích thước k ta sẽ có bấy nhiêu T(k). Ngoài ra ta còn phải xem xét đến thời
gian để phân chia bài toán và tổng hợp các lời giải, chẳng hạn thời gian này là d(n).
Dạng tổng quát của một phương trình đệ quy sẽ là:
C(n)
T(n) =
F(T(k)) + d(n)
Trong đó C(n) là thời gian thực hiện chương trình ứng với trường hợp đệ quy dừng.
F(T(k)) là một đa thức của các T(k). d(n) là thời gian để phân chia bài toán và tổng
hợp các kết quả.
Ví dụ 1-10: Xét hàm tính giai thừa viết bằng giải thuật đệ quy như sau:
FUNCTION Giai_thua(n:Integer): Integer;
BEGIN
IF n=0 then Giai_thua :=1
ELSE Giai_thua := n* Giai_thua(n-1);
END;
Gọi T(n) là thời gian thực hiện việc tính n giai thừa, thì T(n-1) là thời gian thực hiện
việc tính n-1 giai thừa. Trong trường hợp n = 0 thì chương trình chỉ thực hiện một
lệnh gán Giai_thua:=1, nên tốn O(1), do đó ta có T(0) = C1. Trong trường hợp n>0
chương trình phải gọi đệ quy Giai_thua(n-1), việc gọi đệ quy này tốn T(n-1), sau
khi có kết quả của việc gọi đệ quy, chương trình phải nhân kết quả đó với n và gán
cho Giai_thua. Thời gian để thực hiện phép nhân và phép gán là một hằng C2. Vậy
ta có
Nguyễn Văn Linh
Trang 8
Giải thuật
Kĩ thuật phân tích giải thuật
C1
nêu n = 0
T(n) =
T(n -1) + C2 nêu n > 0
Ðây là phương trình đệ quy để tính thời gian thực hiện của chương trình đệ quy
Giai_thua.
Ví du 1-11: Chúng ta xét thủ tục MergeSort một cách phác thảo như sau:
FUNCTION MergeSort (L:List; n:Integer):List;
VAR L1,L2:List;
BEGIN
IF n=1 THEN RETURN(L)
ELSE BEGIN
Chia đôi L thành L1 và L2, với độ dài n/2;
RETURN(Merge(MergeSort(L1,n/2),MergeSort(L2,n/2)));
END;
END;
Chẳng hạn để sắp xếp danh sách L gồm 8 phần tử 7, 4, 8, 9, 3, 1, 6, 2 ta có mô hình
minh họa của MergeSort như sau:
7 4 8 9 3 1 6 2
7 4 8 9
3 1 6 2
7 4
8 9
3 1
6 2
7
4
8
9
3
1
6
2
4 7
8 9
1 3
2 6
4 7 8 9
1 2 3 6
1 2 3 4 6 7 8 9
Hình 1-3: Minh hoạ sắp xếp trộn
Hàm MergeSort nhận một danh sách có độ dài n và trả về một danh sách đã được
sắp xếp. Thủ tục Merge nhận hai danh sách đã được sắp L1 và L2 mỗi danh sách có
n
độ dài , trộn chúng lại với nhau để được một danh sách gồm n phần tử có thứ tự.
2
Nguyễn Văn Linh
Trang 9
Giải thuật
Kĩ thuật phân tích giải thuật
Giải thuật chi tiết của Merge ta sẽ bàn sau, chúng ta chỉ để ý rằng thời gian để
n
Merge các danh sách có độ dài là O(n).
2
n
Gọi T(n) là thời gian thực hiện MergeSort một danh sách n phần tử thì T( ) là thời
2
n
gian thực hiện MergeSort một danh sách phần tử.
2
Khi L có độ dài 1 (n = 1) thì chương trình chỉ làm một việc duy nhất là return(L),
việc này tốn O(1) = C1 thời gian. Trong trường hợp n > 1, chương trình phải thực
n
hiện gọi đệ quy MergeSort hai lần cho L1 và L2 với độ dài do đó thời gian để gọi
2
n
hai lần đệ quy này là 2T( ). Ngoài ra còn phải tốn thời gian cho việc chia danh
2
sách L thành hai nửa bằng nhau và trộn hai danh sách kết quả (Merge). Người ta
xác đinh được thời gian để chia danh sách và Merge là O(n) = C2n . Vậy ta có
phương trình đệ quy như sau:
C1
nêu n = 1
n
T(n) =
2T( ) + C2 n nêu n >1
2
1.6.2 Giải phương trình đệ quy
Có ba phương pháp giải phương trình đệ quy:
1.- Phương pháp truy hồi
2.- Phương pháp đoán nghiệm.
3.- Lời giải tổng quát của một lớp các phương trình đệ quy.
1.6.2.1 Phương pháp truy hồi
Dùng đệ quy để thay thế bất kỳ T(m) với m < n vào phía phải của phương trình cho
đến khi tất cả T(m) với m > 1 được thay thế bởi biểu thức của các T(1) hoặc T(0).
Vì T(1) và T(0) luôn là hằng số nên chúng ta có công thức của T(n) chứa các số
hạng chỉ liên quan đến n và các hằng số. Từ công thức đó ta suy ra T(n).
C1
nêu n = 0
Ví dụ 1-12: Giải phương trình T(n) =
T(n -1) + C2 nêu n > 0
Ta có T(n) = T(n-1) + C2
T(n) = [T(n-2) + C2] + C2 = T(n-2) + 2C2
T(n) = [T(n-3) + C2] + 2C2 = T(n-3) + 3C2
……
T(n) = T(n-i) + iC2
Quá trình trên kết thúc khi n - i = 0 hay i = n. Khi đó ta có
T(n) = T(0) + nC2 = C1 + n C2 = O(n)
Nguyễn Văn Linh
Trang 10
Giải thuật
Kĩ thuật phân tích giải thuật
nêu n = 1
C1
n
Ví dụ 1-13: Giải phương trình T(n) =
2T( ) + C2 n nêu n >1
2
n
Ta có T(n) = 2T( ) + 2C2n
2
n
n
n
T(n) = 2[ 2T( ) + C2 ] + C2n = 4T( ) + 2C2n
4
n
2
n
4
n
T(n) = 4[ 2T( ) + C2 ] + 2C2n = 8T( ) + 3C2n
8
4
8
……….
n
T(n) = 2i T( ) + iC2n
2i
n
2i
Quá trình suy rộng sẽ kết thúc khi
= 1 hay 2i = n và do đó i = logn. Khi đó ta có:
T(n) = nT(1) + lognC2n = C1n + C2nlogn = O(nlogn).
1.6.2.2 Phương pháp đoán nghiệm
Ta đoán một nghiệm f(n) và dùng chứng minh quy nạp để chứng tỏ rằng T(n) ≤ f(n)
với mọi n.
Thông thường f(n) là một trong các hàm quen thuộc như logn, n, nlogn, n2, n3, 2n,
n
n!, n .
Ðôi khi chúng ta chỉ đoán dạng của f(n) trong đó có một vài tham số chưa xác định
(chẳng hạn f(n) = an2 với a chưa xác định) và trong quá trình chứng minh quy nạp ta
sẽ suy diễn ra giá trị thích hợp của các tham số.
C1
nêu n = 1
n
Ví dụ 1-12: Giải phương trình đệ quy T(n) =
2T( ) + C2 n nêu n >1
2
Giả sử chúng ta đoán f(n) = anlogn. Với n = 1 ta thấy rằng cách đoán như vậy
không được bởi vì anlogn có giá trị 0 không phụ thuộc vào giá trị của a. Vì thế ta
thử tiếp theo f(n) = anlogn + b.
Với n = 1 ta có, T(1) = C1 và f(1) = b, muốn T(1) ≤ f(1) thì b ≥ C1 (*)
Giả sử rằng T(k) ≤ f(k), tức là T(k) ≤ aklogk + b với mọi k < n (giả thiết quy nạp).
Ta phải chứng minh T(n) ≤ anlogn + b với mọi n.
n
Giả sử n ≥ 2, từ phương trình đã cho ta có T(n) = 2T( ) + C2n
2
n
Áp dụng giả thiết quy nạp với k =
< n ta có:
2
n
n
n
T(n) = 2T( ) + C2n
2
≤ 2[a log + b] + C2n
2
2
Nguyễn Văn Linh
Trang 11
Giải thuật
T(n) ≤ (anlogn - an + 2b) + C2n
Kĩ thuật phân tích giải thuật
T(n)
≤ (anlogn + b) + [b + (C2 - a)n] . Nếu lấy a ≥ C2 + b (**) ta được
T(n) ≤ (anlogn + b) + [b +(C2 - C2 - b )n ]
T(n) ≤ (anlogn + b) + (1-n) b
T(n) ≤ anlogn + b = f(n). (do b>0 và 1-n<0)
Nếu ta lấy a và b sao cho cả (*) và (**) đều thoả mãn thì T(n) ≤ an logn + b với mọi
n.
b ≥ C 1
⎧
⎨
⎩
b = C1
Ta phải giải hệ
Ðể đơn giản, ta giải hệ
a ≥ C 2 + b
a = C2 + b
Dễ dàng ta có b = C1 và a = C1 +C2 ta được T(n) ≤ (C1 + C2)nlogn +C1 với mọi n.
Hay nói cách khác T(n) là O(nlogn).
1.6.2.3 Lời giải tổng quát cho một lớp các phương trình đệ quy
Khi thiết kế các giải thuật, người ta thường vận dụng phương pháp chia để trị mà ta
sẽ bàn chi tiết hơn trong chương 3. Ở đây chi trình bày tóm tắt phương pháp như
sau:
Ðể giải một bài toán kích thước n, ta chia bài toán đã cho thành a bài toán con, mỗi
n
bài toán con có kích thước . Giải các bài toán con này và tổng hợp kết quả lại để
b
được kết quả của bài toán đã cho. Với các bài toán con chúng ta cũng sẽ áp dụng
phương pháp đó để tiếp tục chia nhỏ ra nữa cho đến các bài toán con kích thước 1.
Kĩ thuật này sẽ dẫn chúng ta đến một giải thuật đệ quy.
Giả thiết rằng mỗi bài toán con kích thước 1 lấy một đơn vị thời gian và thời gian để
n
chia bài toán kích thước n thành các bài toán con kích thước và tổng hợp kết quả
b
từ các bài toán con để được lời giải của bài toán ban đầu là d(n). (Chẳng hạn đối với
ví dụ MergeSort, chúng ta có a = b = 2, và d(n) = C2n. Xem C1 là một đơn vị).
Tất cả các giải thuật đệ quy như trên đều có thể thành lập một phương trinh đệ quy
tổng quát, chung cho lớp các bài toán ấy.
n
Nếu gọi T(n) là thời gian để giải bài toán kích thước n thì T( ) là thời gian để giải
b
n
bài toán con kích thước . Khi n = 1 theo giả thiết trên thì thời gian giải bài toán
b
kích thước 1 là 1 đơn vị, tức là T(1) = 1. Khi n lớn hơn 1, ta phải giải đệ quy a bài
n
n
toán con kích thước , mỗi bài toán con tốn T( ) nên thời gian cho a lời giải đệ
b
b
n
quy này là aT( ). Ngoài ra ta còn phải tốn thời gian để phân chia bài toán và tổng
b
hợp các kết quả, thời gian này theo giả thiết trên là d(n). Vậy ta có phương trình đệ
quy:
Nguyễn Văn Linh
Trang 12
Giải thuật
Kĩ thuật phân tích giải thuật
1
neu n =1
n
T(n) =
(I.1)
aT( ) + d(n) neu n > 1
b
Ta sử dụng phương pháp truy hồi để giải phương trình này. Khi n > 1 ta có
n
T(n) = aT( ) + d(n)
b
n
b2
n
n
b2
n
b
T(n)= a[aT(
) + d( ) ] + d(n) = a2T(
b
) + ad(
) + d(n)
n
b3
n
b2
n
n
b3
n
b2
n
T(n)= a2[a T( ) + d ( ) ]+ ad ( ) + d(n) = a3T ( ) + a2d ( ) + ad ( ) + d(n)
b
b
=
........
n
i-1
a
bj
= aiT(
) + a jd(
)
‡”
bi
j=0
Giả sử n = bk, quá trình suy rộng trên sẽ kết thúc khi i = k.
n
bk
Khi đó ta được T( ) = T(1) = 1. Thay vào trên ta có:
k-1
j
k-j
T(n) = ak + a d b
(I.2)
(
)
‡”
j=0
1.6.2.3.1 Hàm tiến triển, nghiệm thuần nhất và nghiệm riêng
Trong phương trình đệ quy (I.1) hàm thời gian d(n) được gọi là hàm tiến triển
(driving function)
Trong công thức (I.2), ak = nlog a được gọi là nghiệm thuần nhất (homogeneous
b
solutions).
Nghiệm thuần nhất là nghiệm chính xác khi d(n) = 0 với mọi n. Nói một cách khác,
nghiệm thuần nhất biểu diễn thời gian để giải tất cả các bài toán con.
k-1
j
k-j
(
)
Trong công thức (I.2), a d b được gọi là nghiệm riêng (particular solutions).
‡”
j=0
Nghiệm riêng biểu diễn thời gian phải tốn để tạo ra các bài toán con và tổng hợp các
kết quả của chúng. Nhìn vào công thức ta thấy nghiệm riêng phụ thuộc vào hàm tiến
triển, số lượng và kích thước các bài toán con.
Khi tìm nghiệm của phương trình (I.1), chúng ta phải tìm nghiệm riêng và so sánh
với nghiệm thuần nhất. Nếu nghiệm nào lớn hơn, ta lấy nghiệm đó làm nghiệm của
phương trình (I.1).
Việc xác định nghiệm riêng không đơn giản chút nào, tuy vậy, chúng ta cũng tìm
được một lớp các hàm tiến triển có thể dễ dàng xác định nghiệm riêng.
Nguyễn Văn Linh
Trang 13
Giải thuật
Kĩ thuật phân tích giải thuật
1.6.2.3.2 Hàm nhân
Một hàm f(n) được gọi là hàm nhân (multiplicative function) nếu f(m.n) = f(m).f(n)
với mọi số nguyên dương m và n.
Ví dụ 1-13: Hàm f(n) = nk là một hàm nhân, vì f(m.n) = (m.n)k = mk.nk = f(m) f(n)
Tính nghiệm của phương trình tổng quát trong trường hợp d(n) là hàm nhân:
Nếu d(n) trong (I.1) là một hàm nhân thì theo tính chất của hàm nhân ta có
d(bk-j) = [d(b)]k-j và nghiệm riêng của (I.2) là
a
[
]k -1
k-1
k-1
k-1
a
d(b)
a
a j[d(b)]k-j = [d(b)]k
[
]j = [d(b)]k
j
k-j
(
)
=
a d b
‡”
‡”
‡”d(b)
j=0
j=0
j=0
-1
d(b)
ak -[d(b)]k
Hay nghiệm riêng =
(I.3)
a
-1
d(b)
Xét ba trường hợp sau:
1.- Trường hợp 1: a > d(b) thì trong công thức (I.3) ta có ak > [d(b)]k, theo quy tắc
lấy độ phức tạp ta có nghiệm riêng là O(ak) = O(nlogba). Như vậy nghiệm riêng và
nghiệm thuần nhất bằng nhau do đó T(n) là O(nlog a).
b
Trong trương hợp này ta thấy thời gian thực hiện chỉ phụ thuộc vào a, b mà không
phụ thuộc vào hàm tiến triển d(n). Vì vậy để cải tiến giải thuật ta cần giảm a hoặc
tăng b.
2.- Trường hợp 2: a < d(b) thì trong công thức (I.3) ta có [d(b)]k > ak, theo quy tắc
lấy độ phức tạp ta cónghiệm riêng là O([d(b)]k) = O(nlog d(b)). Trong trường hợp này
b
nghiệm riêng lớn hơn nghiệm thuần nhất nên T(n) là O(nlog d(b)).
b
Ðể cải tiến giải thuật chúng ta cần giảm d(b) hoặc tăng b.
Trường hợp đặc biệt quan trọng khi d(n) = n . Khi đó d(b) = b và logbb = 1. Vì thế
nghiệm riêng là O(n) và do vậy T(n) là O(n).
3.- Trường hợp 3: a = d(b) thì công thức (I.3) không xác đinh nên ta phải tính trực
tiếp nghiệm riêng:
k-1
k-1
a
Nghiệm riêng = [d(b)]k
[
]j = ak 1 = akk (do a = d(b))
‡”d(b)
‡”
j=0
j=0
Do n = bk nên k = logbn và ak = nlogba. Vậy nghiệm riêng là nlogbalogbn và nghiệm
này lớn gấp logbn lần nghiệm thuần nhất. Do đó T(n) là O(nlog alogbn).
b
Chú ý khi giải một phương trình đệ quy cụ thể, ta phải xem phương trình đó có
thuộc dạng phương trình tổng quát hay không. Nếu có thì phải xét xem hàm tiến
triển có phải là hàm nhân không. Nếu có thì ta xác định a, d(b) và dựa vào sự so
sánh giữa a và d(b) mà vận dụng một trong ba trường hợp nói trên.
Nguyễn Văn Linh
Trang 14
Giải thuật
Kĩ thuật phân tích giải thuật
Ví dụ 1-14: Giải các phương trình đệ quy sau với T(1) = 1 và
n
1/- T(n) = 4T( ) + n
2
n
2
2/- T(n) = 4T( ) + n
2
n
3
3/- T(n) = 4T( ) + n
2
Các phương trình đã cho đều có dạng phương trình tổng quát, các hàm tiến triển
d(n) đều là các hàm nhân và a = 4, b = 2.
Với phương trình thứ nhất, ta có d(n) = n => d(b) = b = 2 < a, áp dụng trường hợp 1
ta có T(n) = O(nlogba) = O(nlog4) = O(n2).
Với phương trình thứ hai, d(n) = n2 => d(b) = b2 = 4 = a, áp dụng trường hợp 3 ta có
T(n) = O(nlogbalogbn) = O(nlog4logn) = O(n2logn).
Với phương trình thứ 3, ta có d(n) = n3 => d(b) = b3 = 8 > a, áp dụng trường hợp 2,
ta có T(n) = O(nlog d(b)) = O(nlog8) = O(n3).
b
1.6.2.3.3 Các hàm tiến triển khác
Trong trường hợp hàm tiến triển không phải là một hàm nhân thì chúng ta không
thể áp dụng các công thức ứng với ba trường hợp nói trên mà chúng ta phải tính
trực tiếp nghiệm riêng, sau đó so sánh với nghiệm thuần nhất để lấy nghiệm lớn
nhất trong hai nghiệm đó làm nghiệm của phương trình.
Ví dụ 1-15: Giải phương trình đệ quy sau :
T(1) = 1
n
T(n) = 2T( ) + nlogn
2
Phương trình đã cho thuộc dạng phương trình tổng quát nhưng d(n) = nlogn không
phải là một hàm nhân.
Ta có nghiệm thuần nhất = nlog a = nlog2 = n
b
Do d(n) = nlogn không phải là hàm nhân nên ta phải tính nghiệm riêng bằng cách
xét trực tiếp
k-1
k-1
k-1
k(k +1)
2j 2k-j log2k-j = 2k (k - j) = 2k
= O(2kk2)
j
k-j
(
)
Nghiệm riêng = a d b
=
‡”
‡”
‡”
j=0
2
j=0
j=0
Theo giả thiết trong phương trình tổng quát thì n = bk nên k = logbn, ở đây do b = 2
nên 2k = n và k = logn, chúng ta có nghiệm riêng là O(nlog2n), nghiệm này lớn hơn
nghiệm thuần nhất do đó T(n) = O(nlog2n).
Nguyễn Văn Linh
Trang 15
Tải về để xem bản đầy đủ
109 trang
27/04/2022
6560
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Giải thuật - Nguyễn Văn Linh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_giai_thuat_nguyen_van_linh.pdf
