Hệ thức truy hồi
(Recurrence)

 !"#$%&'()*+
Nguyễn Thị Thanh Tâm
Lê Bá Minh Phong
Trần Thị Thành
Nguyễn Vũ Cát Tường
Trần Như Đăng Tuyên


,-.+/"0 1" 2*34
50 1" 2*346(7 89 1"+3
7 :; 89 1" 287 (8<"
0 = 0>*+ 2-"?+"@(8
2""8ABACD&
2E(3BF8/"GHD
=>*3I # 1" 2*34&,6(

D I

D"J38#>*3

D+B K2

&LD I

=# 1" 2*34:MD I4
:"
"&,N"?+#

8S8TB!B*38&,A# 1" 2*34
&U"S +="Z2+2M" R"QMBA"
8?68R"^ 2b"68S8/*Y#
:&*3U3*"E*(380YJ32+7 BA
;8/&=B]c&_c Xb"6
8Ib"6cJ* *c&O8U
2V<"DBa"?+"1>*3NY0
C+d @8S8T&
,RYT"["8/*(3
–
Chọn điều kiện biên n0, chứng minh (n)≤cnlgn với
n>=n0.
–
Ta có thể chọn n=3 là điều kiện biên. Khi đó T(3)=5 và
T(3) ≤ C3lg3 . Với C>=2

5"B*38# A 
•
0"D"*"#"8#
•
O!+(Y#(B!B N
•
I* "0 1" 2*3 4 " N 8d ^ 2" X +
8# D !
 
nnTnT ++= )172/(2)(
Xét ví dụ:
Mới nhìn vào công thức truy hồi này có vẻ phức tạp vì
sự có mặt của tham số 17. Tuy nhiên tham số 17 này
về cơ bản không ảnh hưởng đến nghiệm của hệ thức

bcn
bcnbncbncnT
−≤
+−=+−+−≤ 121)2/()2/()(
(với b ≥1)
Ta đoán rằng nghiệm là O(n), và gắng chứng tỏ T(n) ≤ cn
với một chọn lựa thích hợp cho hằng c. Thay thế suy
đoán vào phép truy hồi ta có:
sai

I8h:IBA"?+# 1"/N @"<
,0Y"Z"E8/*"ZC 28ABA6(YI7
# 1" 2*34"+8<"W"8- 2a (N
D
!8d^ 2"8&
ij # 1" 2*34
5 R8D=+# 1" 2*34(3:M"" +3
8h"":IU8R #[ +BFY0>*+ J/#"
6( 2`"" 2-BF6(""BA*3&
,^ c6&
+"

c
k
l
J3V +" R8^ 6N'c

8R"8<"# 1"
2*34B+*
'c'kl

8#>*3&nS a g1" 2"J38#>*38N#
""@"B ="-*a1"8 2>* 2X
J2d&

V+ !"# *G  BF6( h"@ K
(:7""1""?+"J38#>*3&O!+ 2 h8U"S
+BF2S 2+8<"8/ V+ !"#"?+ *G
:M"":I8h Q"&

ij @[U"9NWj 7 "J38#>*38R8+2+
7
C8# 1" 2*34B+*
5S +:T 8E*:M"" G 2*( X"G 2
"
6V=(3&5S +BF N7 "J38#>*3 g# 1"
2*3
4U"o&
 
)()4/(3)(
2
nnTnT Θ+=
 
)()4/(3)(
2
nnTnT Θ+=•
Kích thước của bài toán con giảm khi chúng ta triển khai
tiếp cho đến khi chúng ta đạt đến điều kiện biên.

n
- 1, là 3
i
c(n/4
i
)
2
=
(3/16)
i
cn
2
. Ở mức cuối cùng tại độ sâu log4
n
có nút với chi phí đóng
góp là T(1) vì vậy tổng chi phí của mức này là T(1) với .
3log
4
n
3log
4
n
)(
3log
4
nΘ
Chi phí cây đệ quy:

J3V"S + @ h"@"?+ ; "=""
1"8RW"8-"@" (:7"J3

4
4
4
4
ncn
ncn
ncncncncnnT
n
n
i
i
n
Θ+
−
−
=
Θ+






=
Θ+






cH k% lp⌊ ⌋


5S +*A"Z2+2Mb

6(7 MBAo

=B]2M= I >*3N8Sk%U".+6(
⌊k%⌋b⌊k%⌋
I:; 89 1"a= I >*3N(# 1" 2*34
+"
 bH⌊k% l⌋ "

bH⌊k%⌋

l"

bHk%

l"

cHkq

l"

b

UrHkq"&
_G3#"?+cH k% lp⌊ ⌋


,-6e+B K2
•
5+r(:o6(""MUv6(7 (U(8<"
8-.+ 2""BA*3Y0J K"0 1"
2*34
c+k:lv
1. Nếu f(n) = O(n
log
:
+
–
w
) với ε > 0 nào đó, thì T(n)=Θ(n
log
:
+
)
2. Nếu f(n) = Θ(n
log
:
+
) thì T(n)= Θ(n
log
b
a
lgn)
3. Nếu f(n) = Ω(n
log
:
+ +

cpv&
•
2 2V<I*+("PY@""xU +J
7  g+BA6+2 (#BF6(c
6
:
+
6c
pv6&

( 2!""U"7 (" I =
8<"6(2u&
•
2 2V<UY0"Zv=C
DU"`=CD K8+ 1"&1"
6(U K #"Gv=CD
6
:
+
7 
g+BA7 Mo(8&
•
2 2V< 1:+UY0"Z=v
=6D
6
:
+
U"`=6D K
8+ 1"((2+"`= C+8/*Y#
y @"J8Az+vk:b"v&,/*Y#(3

•
50 1" 2*34 2"

a=9

b=3

f(n)=n
•
'*32+U
6
:
+
c


6
H
|
cp


•
_Xvcm
6
H
|$w
wcU[ 2V
<"?+8-6e+B K2( *8<"YI >*=
cp

)=Θ(1) áp dụng cho trường hợp 2 ta
được
T(n) =Θ(n
log
3/2
1
lgn)=Θ(lgn)