    
  
  
   

Thut toán  quy
Phng pháp:
Phân tích toán hc (mathematical tool)
Thay th(substitution)
Cây  quy (recurrence tree)
nh lý tng quát (master theorem)
! " #$ 
MergeSort (,1,)
1 if = 1 return
2 MergeSort (,1, /2 )
3 MergeSort (, /2 +1,)
4 Merge (,1, /2 , /2 +1,)
Hàm: Merge
Gp 2 dãy ã sp xp làm mt
∈ ()  gpphn t(thi gian tuyn tính)
! "    
MergeSort (,1,)
1(1) if = 1 return
2(/2) MergeSort (,1, /2 )
3(/2) MergeSort (, /2 +1,)
4() Merge (,1, /2 , /2 +1,)
! "    a
Thông thng bqua trng hp cbn khi
thi gian chy nh, nhng chkhi không làm
nh hng n kt quca tim cn
=
1 nếu = 1
2 /2 + nếu > 1
Tính = 2 /2 +, vi hng s > 0