Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 3: Phân tích đệ quy - Lê Nguyên Khôi

T(n) = 4T(n/2) + n^2 log⁡n a = 4, b = 2 => n^log_b⁡a =n^2 f(n) = n^2 logn Không áp dụng được Định lý Tổng quát af (n/b) ≤ cf (n) với c < 1 4 ((〖n/2)〗^2 log⁡〖n/2〗) ≤ cn^2 logn với c < 1 n^2 logn - n^2 ≤ cn^2 logn với c < 1 (1-c) logn ≤ 1 với c < 1

pdf28 trang | Chia sẻ: thucuc2301 | Lượt xem: 601 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 3: Phân tích đệ quy - Lê Nguyên Khôi, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Thiết Kế & Đánh Giá Thuật Toán Phân Tích Đệ Quy TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung  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 Sắp Xếp Gộp – Mã Giả MergeSort (, 1, ) 1 if  = 1 return 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 Sắp Xếp Gộp – Phân Tích Thuật Toán MergeSort (, 1, ) 3 1 (1) if  = 1 return 2 (/2) MergeSort (, 1, /2 ) 3 (/2) MergeSort (, /2 + 1, ) 4 () Merge (, 1, /2 , /2 + 1, ) Sắp Xếp Gộp – Phân Tích Thời Gian  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  = 12 /2 +  nếu  > 1 Tính  = 2 /2 + , với hằng số  > 0 4 PP Phân Tích Toán Học  Tính  = 2 /2 + , với hằng số  > 0  = 2 /2 +  = 2 2   +    +  = 2 × 2 2   +    +    +  ⋮ = 2 ×⋯× 2 1 +  +  + +  =  +  log  ∈  log  5 PP Thay Thế  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 PP Thay Thế  = 4 /2 +  ≤ 4 /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 PP Thay Thế  Chứng minh rằng  ≤   Giả sử % ≤ % với % < :  = 4 /2 +  ≤ 4 /2  +  =  +  ≤  sai do phải chứng minh quy nạp =  − (−) ≤  không có  > 0 8 PP Thay Thế  Làm chặt giả thiết:  Bằng cách trừ một bậc thấp  Giả sử % ≤ % − % với % <   = 4 /2 +  ≤ 4( /2  − (/2)) +  =  − 2 +  =  −  − ( − ) ≤  −  nếu  ≥ 1 Chọn  đủ lớn để thỏa mãn trường hợp cơ bản 9 PP Thay Thế - Bài Tập 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 PP Cây Đệ Quy  Ví dụ: xem tr.38  Chi tiết: Mục 4.4 tr.88-93 11 Định Lý Tổng Quát Đị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 Định Lý Tổng Quát  = * /+ + ,() 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ế  ∈ -./0 1 13 Định Lý Tổng Quát  = * /+  = * /+ = * *  + = *  + = *"  +" = ⋯ = *2  +2 = ⋯ = *-./0  1 = -./0 1 (1)  ∈ -./0 1 14 Định Lý Tổng Quát  = * /+ + ,() Trường hợp khi ,  > 0, cần so sánh độ tăng của * /+ và ,(): 1. ,() tăng chậm hơn * /+ ∈ # -./0 1 2. ,() tăng bằng * /+ ∈ -./0 1 3. ,() tăng nhanh hơn * /+ ∈ $ -./0 1 15 Định Lý Tổng Quát  = * /+ + ,() So sánh ,() với -./0 1: 1. ,  ∈ #(-./0 134) với hằng số 5 > 0 ,() tăng chậm hơn -./0 1 với hệ số 4 khi đó:  ∈ (-./0 1) (bỏ các bậc thấp, bậc tăng chậm) 16 Định Lý Tổng Quát  = * /+ + ,() So sánh ,() với -./0 1: 2. ,  ∈ (-./0 1) ,() tăng bằng -./0 1 khi đó:  ∈ (-./0 1 log ) 17 Định Lý Tổng Quát  = * /+ + ,() So sánh ,() với -./0 1: 3. ,  ∈ $(-./0 164) với hằng số 5 > 0 ,() tăng nhanh hơn -./0 1 với hệ số 4 và ,  thỏa mãn *, /+ ≤ ,() với  < 1 khi đó:  ∈ (,()) 18 Định Lý Tổng Quát Cho 2 hằng số * ≥ 1, + ≥ 1, hàm ,()  = * /+ + ,() Tiệm cận của  : 1. Nếu ,  ∈ 7(-./0 134) với hằng số 5 > 0  ∈ (-./0 1) 2. Nếu ,  ∈ 8(-./0 1)  ∈ (-./0 1 log ) 3. Nếu ,  ∈ 9(-./0 164) với hằng số 5 > 0 và ,  thỏa mãn *, /+ ≤ ,() với  < 1  ∈ (,()) Chứng minh: xem 4.6 tr. 97-106 19 Định Lý Tổng Quát – Bài Tập \  = 4 /2 +  () = 4 (/2) +  () = 4 (/2) + " () = 4 (/2) +  log  20 Định Lý Tổng Quát – Bài Tập  = 4 /2 +  * = 4, + = 2 ⇒ -./0 1 = ; ,() =  Trường hợp 1: ,  ∈ < -./0 134 = <(34) với 5 = 1 ⇒ () ∈ () 21 Định Lý Tổng Quát – Bài Tập () = 4 (/2) +  * = 4, + = 2 ⇒ -./0 1 = ; ,() =  Trường hợp 2: ,  ∈ -./0 1 = () ⇒ () ∈ ( log ) 22 Định Lý Tổng Quát – Bài Tập () = 4 (/2) + " * = 4, + = 2 ⇒ -./0 1 = ; ,() = " Trường hợp 3: ,  ∈ < -./0 164 = <(64) với 5 = 1 và *, /+ ≤ ,() với  < 1 4 /2 " ≤ " với  = 1/2 ⇒ () ∈ (") 23 Định Lý Tổng Quát – Bài Tập () = 4 (/2) +  log  * = 4, + = 2 ⇒ -./0 1 = ; ,() =  log  Không áp dụng được Định Lý Tổng Quát *, /+ ≤ ,() với  < 1 4 (/2)log  ≤  log  với  < 1  log  −  ≤  log  với  < 1 (1 − ) log  ≤ 1 với  < 1 24 Định Lý Tổng Quát – Bài Tập  = 2 /4 + 1 T.H.1: () ∈ ( ) () = 2 (/4) +  T.H.2: () ∈ (  log ) () = 2 (/4) +  T.H.3: () ∈ () () = 2 (/4) +  T.H.3: () ∈ () 25 Định Lý Tổng Quát – Bài Tập  = 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 Bài Tập Problems 4-1 tr.107 Problems 4-3 tr.108 27

Các file đính kèm theo tài liệu này:

  • pdfthiet_ke_danh_gia_thuat_toanbaigiang03_phantichdequy_9484_2032090.pdf