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

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