Bài giảng Thiết kế và đánh giá thuật toán - Chương 3: Phân tích đệ quy - Lê Nguyên Khôi

Nội dung text: Bài giảng Thiết kế và đánh giá thuật toán - Chương 3: Phân tích đệ quy - Lê Nguyên Khôi

1. ế ế ậ ệ ườ ạ ọ ệ
2. ộ
   Thu ật toán đệ quy
   Ph ươ ng pháp:
   Phân tích toán học (mathematical tool)
   Thay th ế (substitution)
   Cây đệ quy (recurrence tree)
   Đị nh lý tổng quát (master theorem) 1
3. ắ ế ộ ả MergeSort (, 1, ) 1 if return = 1 2 MergeSort (, 1, /2 ) 3 MergeSort (, /2 + 1, ) 4 Merge (, 1, /2 , /2 + 1, )
   Hàm: Merge
   Gộp 2 dãy đã sắp xếp làm một để ộ ầ ử ờ ế
   ∈ () g p ph n t (th i gian tuy n tính) 2
4. ắ ế ộ ậ MergeSort (, 1, ) 1 if return (1) = 1 2 MergeSort (/2) (, 1, /2 ) 3 MergeSort (/2) (, /2 + 1, ) 4 Merge () (, 1, /2 , /2 + 1, ) 3
5. ắ ế ộ ờ a
   Thông th ườ ng bỏ qua tr ườ ng hợp cơ bản khi th ời gian ch ạy nh ỏ, nh ưng ch ỉ khi không làm ảnh hưở ng đế n kết qu ả của ti ệm cận 1 nếu = 1 = 2 /2 + nếu > 1 ớ ằ ố Tính = 2 /2 + , v i h ng s > 0 4
6. ọ ớ ằ ố
   Tính = 2 /2 + , v i h ng s > 0 = / + = + + = × + + + ⋮ = × ⋯ × 1 +++ + = + log ∈ log 5
7. a ế
   Ph ươ ng pháp ph ổ bi ến 1. Dự đoán bậc tăng 2. Ch ứng minh bằng quy nạp ụ
   Ví d : = 4 /2 + ả ử
   Gi s : 1 ∈ 1 ự đ ầ ứ
   D oán: ( ) (c n ch ng minh - và -) ả ử ớ
   Gi s : ≤ v i < ứ ằ ạ
   Ch ng minh b ng quy n p ≤ 6
8. a ế = /2 + ≤ /2 + = /2 + = − ( /2 − ) ≤ Khi /2 − ≥ 0 ụ ớ Ví d , v i ≥ 2 và ≥ 1 Tuy nhiên ch ặn này không ch ặt 7
9. a ế
   Ch ứng minh rằng ≤
   Gi ả sử ≤ với 0 8
10. a ế
    Làm ch ặt gi ả thi ết:
    Bằng cách tr ừ một bậc th ấp
    Gi ả sử ≤ − với < = /2 + ≤ ( /2 − (/2)) + = − 2 + = − − ( − ) nếu ≤ − ≥ 1 Ch ọn đủ lớn để th ỏa mãn tr ườ ng hợp cơ bản 9
11. a ế ậ Xác đị nh độ ph ức tạp thu ật toán với sau: = − 1 + (bài 4.3-1 tr.87) = /2 + 1 (bài 4.3-2 tr.87) = 2 /2 + (bài 4.3-3 tr.87) 10
12. ệ
    Ví dụ: xem tr.38
    Chi ti ết: Mục 4.4 tr.88-93 11
13. ị ổ Đị nh lý tổng quát = / + () Với ≥ 1, > 1, và dươ ng Ví dụ MergeSort : = 2 /2 + đ Trong ó = 2, = 2, = Khi đó ta có: ∈ log 12
14. ị ổ = / + () Xét tr ườ ng hợp đặ c bi ệt, khi = 0: = / 02 ph ươ ng pháp: 1. Phân tích toán học 2. Thay th ế thay th ế ∈ 13
15. ị ổ = / = / = = = = ⋯ = = ⋯ = 1 = (1) ∈ 14
16. ị ổ = / + () Tr ườ ng hợp khi > 0, cần so sánh độ tăng của / và (): 1. () tăng ch ậm hơn / ∈ 2. () tăng bằng / ∈ 3. () tăng nhanh hơn / ∈ 15
17. ị ổ = / + () So sánh () với : 1. ∈ ( ) với hằng số > 0 () tăng ch ậm hơn với hệ số khi đó: ∈ ( ) (bỏ các bậc th ấp, bậc tăng ch ậm) 16
18. ị ổ = / + () So sánh () với : 2. ∈ ( ) () tăng bằng khi đó: ∈ ( log ) 17
19. ị ổ = / + () So sánh () với : 3. ∈ ( ) với hằng số > 0 () tăng nhanh hơn với hệ số và th ỏa mãn / ≤ () với < 1 khi đó: ∈ (()) 18
20. ị ổ Cho 2 hằng số ≥ 1, ≥ 1, hàm () = / + () Ti ệm cận của : 1. Nếu ∈ ( ) với hằng số > 0 ∈ ( ) 2. Nếu ∈ ( ) ∈ ( log ) 3. Nếu ∈ ( ) với hằng số > 0 và th ỏa mãn / ≤ () với < 1 ∈ (()) Ch ứng minh: xem 4.6 tr. 97-106 19
21. ị ổ ậ \ = /2 + ()= (/2)+ ()= (/2)+ ()= (/2)+ log 20
22. ị ổ ậ = /2 + = , = 2 ⇒ = ; () = Tr ườ ng h ợp 1: ∈ = () với = 1 ⇒ () ∈ () 21
23. ị ổ ậ () = (/2)+ = , = 2 ⇒ = ; () = Tr ườ ng h ợp 2: ∈ = () ⇒ () ∈ ( log ) 22
24. ị ổ ậ () = (/2)+ = , = 2 ⇒ = ; () = Tr ườ ng h ợp 3: ∈ = () với = 1 và / ≤ () với < 1 ớ 4 /2 ≤ v i = 1/2 ⇒ () ∈ () 23
25. ị ổ ậ () = (/2)+ log = , = 2 ⇒ = ; () = log Không áp dụng đượ c Đị nh Lý Tổng Quát / ≤ () với < 1 4 (/ với 2) log ≤ log < 1 ớ log − ≤ log v i < 1 ớ (1−)log ≤1 v i < 1 24
26. ị ổ ậ = 2 /4 + 1 T.H.1: () ∈ ( ) () = 2(/4)+ T.H.2: () ∈ ( log ) () = 2(/4)+ T.H.3: () ∈ () () = 2(/4)+ T.H.3: () ∈ () 25
27. ị ổ ậ = 9 /3 + T.H.1: () ∈ () = 2/3 + 1 T.H.2: () ∈ (log) ()= 3(/4)+ log T.H.3: () ∈ (log) () = 2(/2)+ log Không áp d ụng đượ c T.H.3 ĐLTQ 26
28. ậ Problems 4-1 tr.107 Problems 4-3 tr.108 27