    
a
  
   

Kthut thit k
Sp xp gp
Tính ly tha
Tìm kim nhphân
Tính sFibonacci
Tháp Hanoi
Nhân ma trn
Thut toán Strassen
  a
Chia bài toán ln thành các bài toán nh
Bài toán nh ơn gin, gii trc tip
Nu không tip tc chia nhbài toán con
Gp li gii ca các bài toán con
!ee#
Chia: chia ôi mng
Tr: Sdng  quy sp xp 2 mng con
Gp: gp 2 mng vi thi gian tuyn tính
MergeSort (,1,)
1 if = 1 return
2 MergeSort (,1, /2 )
3 MergeSort (, /2 +1,)
4 Merge (,1, /2 , /2 +1,)
()= 2(/2)+Θ()
 ln bài toán con# bài toán con
chia và gp
 $   %  &#
=  / +()
1. Nu ∈ ()vi hng s > 0
∈ ()
2. Nu ∈ ()
∈ (log)
3. Nu ∈ "(#)vi hng s > 0
và tha mãn  / ≤ %() vi % < 1
∈ (())
Sp xp gp: = 2, = 2 ⇒ = ()=
⇒trng hp 2 ⇒ () ∈ (log)