Bài giảng Thiết kế và đánh giá thuật toán - 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