Collected by The_Wall (11/10/2005)
Giáo trình môn Phân tích Gii Thut – I C CN TH........................................................................ Trang 1
1. Mc tiêu
2. Kin thc c bn cn có hc chng này
3. Tài liu tham kho có liên quan n chng
4. Ni dung:
I.1 - S cn thit phi phân tích gii thut.
I.2 - Thi gian thc hin ca gii thut.
I.3 - T sut tng và phc tp ca gii thut.
I.4 - Cách tính phc tp.
I.5 - Phân tích các chng trình quy.
5. Vn nghiên cu ca trang k tip
Trong chng này chúng ta s nghiên cu các vn sau:
· S cn thit phi phân tích các gii thut.
· Thi gian thc hin ca chng trình.
· T sut tng và phc tp ca gii thut.
· Tính thi gian thc hin ca chng trình.
· Phân tích các chng trình quy.
I.1- S CN THIT PHI PHÂN TÍCH GII THUT
Trong khi gii mt bài toán chúng ta có th có mt s gii thut khác nhau, vn là cn phi
ánh giá các gii thut ó la chn mt gii thut tt (nht). Thông thng thì ta s cn c vào các
tiêu chun sau:
1.- Gii thut úng n.
2.- Gii thut n gin.
3.- Gii thut thc hin nhanh.
Vi yêu cu (1), kim tra tính úng n ca gii thut chúng ta có th cài t gii thut ó
và cho thc hin trên máy vi mt s b d liu mu ri ly kt qu thu c so sánh vi kt quã
bit. Thc ra thì cách làm này không chc chn bi vì có th gii thut úng vi tt c các b d liu
chúng ta ã th nhng li sai vi mt b d liu nào ó. V li cách làm này ch phát hin ra gii thut
sai ch cha chng minh c là nó úng. Tính úng n ca gii thut cn phi c chng minh
ng toán hc. Tt nhiên u này không n gin và do vy chúng ta s không cp n ây.
c xác nh bi s các lnh c thc hin trong mt máy tính lý tng.
Ví d 1-2: Khi ta nói thi gian thc hin ca mt chng trình là T(n) = cn thì có ngha là
chng trình y cn cn ch th thc thi.
I.2.3- Thi gian thc hin trong trng hp xu nht.
Nói chung thì thi gian thc hin chng trình không ch ph thuc vào kích thc mà còn
ph thuc vào tính cht ca d liu vào. Ngha là d liu vào có cùng kích thc nhng thi gian thc
hin chng trình có th khác nhau. Chng hn chng trình sp xp dãy s nguyên tng dn, khi ta
cho vào dãy có th t thì thi gian thc hin khác vi khi ta cho vào dãy cha có th t, hoc khi ta
cho vào mt dãy ã có th t tng thì thi gian thc hin cng khác so vi khi ta cho vào mt dãy ã
có th t gim.
Vì vy thng ta coi T(n) là thi gian thc hin chng trình trong trng hp xu nht trên
liu vào có kích thóc n, tc là: T(n) là thi gian ln nht thc hin chng trình i vi mi d
liu vào có cùng kích thc n.
I.3- T SUT TNG VÀ PHC TP CA GII THUT
Collected by The_Wall (11/10/2005)
Giáo trình môn Phân tích Gii Thut – I C CN TH........................................................................ Trang 3
I.3.1- T sut tng
I.3.2- Khái nim phc tp ca gii thut
I.3.1- T sut tng
Ta nói rng hàm không âm T(n) có sut tng (growth rate) f(n) nu tn ti các hng s c
và n
0
sao cho T(n) f(n) vi mi n n
0
.
Ta có th chng minh c rng “Cho mt hàm không âm T(n) bt k, ta luôn tìm c t
sut tng f(n) ca nó”.
Ví d 1-3: Gi s T(0) = 1, T(1) = 4 và tng quát T(n) = (n+1)
2
. t n
2
) và T2(n) = 5n
3
(vi t sut tng là n
3
). Gii thut nào s thc hin nhanh hn? Câu tr
i ph thuc vào kích thc d liu vào. Vi n < 20 thì P2 s nhanh hn P1 (T2<T1), do h s ca 5n
3
nh hn h s ca 100n
2
(5<100). Nhng khi n > 20 thì ngc li do s m ca 100n
2
nh hn s m
a 5n
3
(2<3). ây chúng ta ch nên quan tâm n trng hp n>20 vì khi n<20 thì thi gian thc
hin ca c P1 và P2 u không ln và s khác bit gia T1 và T2 là không áng k..
Nh vy mt cách hp lý là ta xét t sut tng ca hàm thi gian thc hin chng trình thay
vì xét chính bn thân thi gian thc hin.
Cho mt hàm T(n), T(n) gi là có phc tp f(n) nu tn ti các hng c, N
0
sao cho T(n)
cf(n) vi mi n N
0
(tc là T(n) có t sut tng là f(n)) và kí hiu T(n) là O(f(n)) (c là “ô ca f(n)”)
Ví d 1-5: T(n)= (n+1)
2
có t sut tng là n
2
nên T(n)= (n+1)
Giáo trình môn Phân tích Gii Thut – I C CN TH........................................................................ Trang 4
I.4.3- Qui tc tng quát phân tích mt chng trình
I.4.4- phc tp ca chng trình có gi chng trình con không qui
Cách tính phc tp ca mt gii thut bt k là mt vn không n gin. Tuy nhiên ta có
th tuân theo mt s nguyên tc sau:
I.4.1- Qui tc cng:
Nu T1(n) và T2(n) là thi gian thc hin ca hai n chng trình P1 và P2; và
T1(n)=O(f(n)), T2(n)=O(g(n) thì thi gian thc hin ca n hai chng trình ó i tip nhau là
T(n)=O(max(f(n),g(n)))
Ví d 1-6: Lnh gán x:=15 tn mt hng thi gian hay O(1)
Lnh c d liu READ(x) tn mt hng thi gian hay O(1)
Vy thi gian thc hin c hai lnh trên ni tip nhau là O(max(1,1))=O(1)
I.4.2- Qui tc nhân:
Nu T1(n) và T2(n) là thi gian thc hin ca hai n chng trình P1và P2 và T1(n) =
O(f(n)), T2(n) = O(g(n) thì thi gian thc hin ca n hai n chng trình ó ng nhau là T(n) =
O(f(n).g(n))
I.4.3- Qui tc tng quát phân tích mt chng trình:
- Thi gian thc hin ca mi lnh gán, READ, WRITE là O(1)
- Thi gian thc hin ca mt chui tun t các lnh c xác nh bng qui tc cng. Nh
y thi gian này là thi gian thi hành mt lnh nào ó lâu nht trong chui lnh.
- Thi gian thc hin cu trúc IF là thi gian ln nht thc hin lnh sau THEN hoc sau ELSE
và thi gian kim tra u kin. Thng thi gian kim tra u kin là O(1).
- Thi gian thc hin vòng lp là tng (trên tt c các ln lp) thi gian thc hin thân vòng
p. Nu thi gian thc hin than vòng lp không i thì thi gian thc hin vòng lp là tích ca s ln
p vi thi gian thc hin thân vòng lp.
Ví d 1-7: Tính thi gian thc hin ca n chng trình
procedure Bubble (var a: array[1..n] of integer);
var i,j,temp: integer;
begin
{1} for i:=1 to n-1 do
begin
temp := x;
x := y;
y := temp;
end;
Collected by The_Wall (11/10/2005)
Giáo trình môn Phân tích Gii Thut – I C CN TH........................................................................ Trang 6
procedure Bubble (var a: array[1..n] of integer);
var i,j :integer;
begin
{1} for i:=1 to n-1 do
{2} for j:=n downto i+1 do
{3} if a[j-1]>a[j] then Swap(a[j-1], a[j]);
end;
Trong cách vit trên, chng trình Bubble gi chng trình con Swap, do ó tính thi gian
thc hin ca Bubble, trc ht ta cn tính thi gian thc hin ca Swap. D thy thi gian thc hin
a Swap là O(1) vì nó ch bao gm 3 lnh gán.
Trong Bubble, lnh {3} gi Swap nên ch tn O(1), lnh {2} thc hin n-i ln, mi ln tn
O(1) nên tn O(n-i). Lnh {1} thc hin n-1 ln nên
I.5- PHÂN TÍCH CÁC CHNG TRÌNH QUY
I.5.1- Thành lp phng trình quy
I.5.2- Gii phng trình quy
Vi các chng trình có gi các chng trình con quy, ta không th áp dng cách tính nh
a trình bày trong mc I.4.4 bi vì mt chng trình quy s gi chính bn thân nó.
Vi các chng trình quy, trc ht ta cn thành lp các phng trình quy, sau ó gii
phng trình quy, nghim ca phng trình quy s là thi gian thc hin ca chng trình
quy.
I.5.1- Thành lp phng trình quy
Phng trình quy là mt phng trình biu din mi liên h gia T(n) và T(k), trong ó
T(n) là thi gian thc hin chng trình vi kích thc d liu nhp là n, T(k) thi gian thc hin
Hàm MergeSort nhn mt danh sách có dài n và tr v mt danh sách ã c sp xp. Th
c Merge nhn hai danh sách ã c sp L1 và L2 mi danh sách có dài n/2, trn chúng li vi
nhau c mt danh sách gm n phn t có th t. Gii thut chi tit ca Merge ta s bàn sau,
chúng ta ch ý rng thi gian Merge các danh sách có dài n/2 là O(n).
Collected by The_Wall (11/10/2005)
Giáo trình môn Phân tích Gii Thut – I C CN TH........................................................................ Trang 8
Gi T(n) là thi gian thc hin MergeSort mt danh sách n phn t thì T(n/2) là thi gian thc
hin MergeSort mt danh sách n/2 phn t , ta có th vit phng trình quy nh sau:
Trong ó c1 là thi gian phi tn khi L có dài 1. Trong trng hp n > 1, thi gian ca
MergeSort c chia làm hai phn. Phn gi quy MergeSort mt danh sách có dài n/2 là T(n/2)
do ó ta có 2T(n/2). Phn th hai bao gm phép th n >1, chia danh sách L thành hai na bng nhau và
Merge. Ba thao tác này ly thi gian không i i vi phép th hoc t l vi n i vi ngt và
Merge. Nh vy hng c
2
c chn và c
2
n là thi gian tng làm các vic ó ngoi tr gi quy.
I.5.2- Gii phng trình quy
Có ba phng pháp gii phng trình quy:
1.- Phng pháp truy hi
2.- Phng pháp oán nghim.
3.- Li gii tng quát ca mt lp các phng trình quy.
Phng pháp truy hi
Dùng quy thay th bt k T(m) vi m < n vào phía phi ca phng trình cho n khi tt
T(m) vi m > 1 c thay th bi biu thc ca các T(1). Vì T(1) luôn là hng nên chúng ta có công
thc ca T(n) cha các s hng ch liên quan n n và các hng s.
Gii phng trình.
Ví d 1-10: Gii phng trình:
Ta có:
Gi s n = 2
.
ôi khi chúng ta choán dng ca f(n) trong ó có mt vài tham s cha xác nh (chng hn
f(n) = an
2
vi a cha xác nh) và trong quá trình chng minh quy np ta s suy din ra giá tr thích
p ca các tham s.
Ví d 1-11: Gii phng trình quy
Gi s chúng ta oán f(n) = anlogn. Vi n = 1 ta thy rng cách oán nh vy không c bi
vì anlog n có giá tr 0 không ph thuc vào giá tr ca a. Vì th ta th tip theo f(n) = anlogn + b.
Vi n = 1 ta có, T(1) = C
1
và f(1) = b, mun T(1) f(1) thì b C
1
(*)
Gi s rng T(k) aklogk + b vi mi k < n (I.2).Ta s chng minh T(n) anlogn + b
Gi s n 2, t (I.1) ta có T(n) = 2T(n/2) + C
2
n
Áp dng (I.2) vi k = n/2 < n ta có:
T(n) = 2T(n/2) + C
2
n 2[an/2log(n/2) + b] + C
2
n
T(n) anlogn - an + 2b + C
2
n
T(n) (anlogn + b) + [b + (C
2
- a)n] . Nu ly a C
quy.
Gi thit rng mi bài toán con kích thc 1 ly mt n v thi gian và thi gian chia bài
toán kích thc n thành các bài toán con kích thc n/b và tng hp kt qu t các bài toán con
c li gii ca bài toán ban u là d(n). (Chng hn i vi thí d MergeSort, chúng ta có a = b = 2,
và d(n) = C
2
n/C
1
. Xem C
1
là mt n v).
Gi T(n) là thi gian gii bài toán kích thc n thì ta có phng trình quy:
Ta s dng phng pháp truy hi gii phng trình này
Gi s n = b
k
ta c: T(n/b
k
) = T(1) = 1. Thay vào trên vi i = k ta có:
Hàm tin trin, nghim thun nht và nghim riêng
Trong phng trình quy (I.1) hàm thi gian d(n) c gi là hàm tin trin (driving
function)
Trong công thc (I.2), a
k
= n
log
b
a
c gi là nghim thun nht (homogeneous solutions).
Nghim thun nht là nghim chính xác khi d(n) = 0 vi mi n. Nói mt cách khác, nghim
thun nht biu din thi gian gii tt c các bài toán con.
k
) = O(n
log
b
a
). Nh vy nghim riêng và nghim thun
nht bng nhau do ó T(n) là O(n
log
b
a
).
Ta cng thy thi gian thc hin ch ph thuc vào a, b mà không ph thuc vào hàm tin trin
d(n). Vì vy ci tin gii thut ta cn gim a hoc tng b.
2.- Nu a < d(b) thì nghim riêng là O(d(b)
k
) = O(n
log
b
d(b)
). Trong trng hp này nghim riêng
n hn nghim thun nht nên T(n) = O(n
log
b
d(b)
).
ci tin gii thut chúng ta cn ý n c d(n), a và b cùng mc nh nhau.
Trng hp c bit quan trng khi d(n) = n
. Khi ó d(b) = b
ta c T(n) = O(n
logn).
Chú ý khi gii mt phng trình quy c th, ta phi xem phng trình ó có thuc dng
phng trình tng quát hay không. Nu có thì phi xét xem hàm tin trin có phi là hàm nhân không.
u có thì ta xác nh a, d(b) và da vào s so sánh gia a và d(b) mà vn dng mt trong ba trng
p nói trên.
Ví d 1-13: Gii các phng trình quy sau vi T(1) = 1 và
1/- T(n) = 4T(n/2) + n
2/- T(n) = 4T(n/2) + n
2
3/- T(n) = 4T(n/2) + n
3
Trong mi trng hp, a=4, b=2 và nghim thun nht là n
2
. Vi d(n) = n ta có d(b) = 2 vì a =
4 > d(b) nên nghim riêng cng là n
2
và T(n) = O(n
2
) trong phng trình (1).
Trong phng trình (3), d(n) = n
3
, d(b) = 8 và a < d(b). Vì vy nghim riêng là O(n
log
b
d(b)
) =
O(n
O(n
1.59
). Vì a = 3 và b = 2 và b
1.5
= 2.82 < a, nghim riêng cng là O(n
1.59
) và do ó U(n) = O(n
1.59
) . Vì
Collected by The_Wall (11/10/2005)
Giáo trình môn Phân tích Gii Thut – I C CN TH........................................................................Trang 13
T(n) = 2U(n) nên T(n) = O(n
1.59
) hay T(n) = O(n
log3
).
Ví d 1-15: Gii phng trình quy sau :
T(1) = 1
T(n) = 2T(n/2) + nlogn
Vì a = b = 2 nên nghim thun nht là n. Tuy nhiên, d(n) = nlogn không phi là hàm nhân ta
phi tính nghim riêng bng cách xét trc tip:
Vì k = logn chúng ta có nghim riêng là O(nlog
2
n), nghim này ln hn nghim thun nht và
T(n) = O(nlog
2
n).
Bài 1: Tính thi gian thc hin ca các n chng trình sau:
a) Tính tng ca các s
Sum := 0;
Bài 5: Gii các phng trình quy sau bng phng pháp oán nghim:
a) T(1) = 2 và T(n) = 2T(n-1) + 1 vi ∀ n 2
b) T(1) = 1 và T(n) = 2T(n-1) + n vi ∀ n 2
Bài 6: Cho mt mng n s nguyên c sp th t tng. Vit hàm tìm mt s nguyên trong
ng ó, nu tìm thy thì tr v TRUE, ngc li tr v FALSE.
dng hai phng pháp tìm kim tun t và tìm kim nh phân. Vi mi phng pháp hãy vit mt
hàm tìm và tính thi gian thc hin ca hàm ó.
Bài 7: Tính thi gian thc hin ca gii thut quy gii bài toán Tháp Hà ni vi n tng?
Bài 8: Xét nh ngha s t hp chp k ca n nh sau:
a) Vit mt hàm quy tính s t hp chp k ca n.
Tính thi gian thc hin ca gii thut nói trên.
Collected by The_Wall (11/10/2005)
Giáo trình môn Phân tích Gii Thut – I C CN TH........................................................................Trang 15
1. Mc tiêu
2. Kin thc c bn cn có hc chng này
3. Tài liu tham kho có liên quan n chng
4. Ni dung:
II.1 - Bài toán sp xp.
II.2 - Các phng pháp sp xp n gin
II.3 - Quicksort.
II.4 - Heapsort.
II.5 - Binsort.
5. Vn nghiên cu ca trang k tip
Trong chng này chúng ta s nghiên cu các vn sau:
· Bài toán sp xp.
· Mt s gii thut sp xp n gin.
· QuickSort
· HeapSort
· BinSort
II.1- BÀI TOÁN SP XP
type
KeyType = integer;
OtherType = real;
RecordType = Record
Key : KeyType;
OtherFields : OtherType;
end;
var
a : array[1..N] of RecordType;
procedure Swap(var x,y:RecordType);
var
temp : RecordType;
begin
temp := x;
x := y;
y := temp;
end;
n thy rng th tc Swap ly O(1) thi gian vì ch thc hin 3 lnh gán ni tip nhau.
II.2- CÁC PHNG PHÁP SP XP N GIN
II.2.1- Sp xp chn
II.2.2- Sp xp xen
II.2.3- Sp xp ni bt
Các gii thut n gin thng ly O(n
2
) thi gian sp xp n i tng và các gii thut này
thng ch dùng sp các danh sách có ít i tng.
Vi mi gii thut chúng ta s nghiên cu các phn: gii thut, ví d, chng trình và phân tích
ánh giá.
Collected by The_Wall (11/10/2005)
Giáo trình môn Phân tích Gii Thut – I C CN TH........................................................................Trang 17
c 5
6
12 9 10 9 10
c 6
9
12 10 9 10
c 7
9
10 12 10
c 8
10
12 10
c 9
10
12
t qu 2 2 3 5 6 9 9 10 10 12
Hình 2-1: Sp xp chn
Chng trình:
procedure SelectionSort;
var
i,j,LowIndex: integer;
LowKey: KeyType;
begin
(1) for i := 1 to n-1 do begin
(2) LowIndex := i;
(3) LowKey := a[i].key;
(4) for j := i+1 to n do
(5) if a[j].key < LowKey then
Collected by The_Wall (11/10/2005)
Giáo trình môn Phân tích Gii Thut – I C CN TH........................................................................Trang 18
Ban u
5 6 2 2 10 12 9 10 9 3
c 1
5 6
c 2
2 5 6
c 3
2 2 5 6
c 4
2 2 5 6 10
c 5
2 2 5 6 10 12
Collected by The_Wall (11/10/2005)
Giáo trình môn Phân tích Gii Thut – I C CN TH........................................................................Trang 19
c 6
2 2 5 6 9 10 12
c 7
2 2 5 6 9 10 10 12
c 8
2 2 5 6 9 9 10 10 12
c 9
2 2 3 5 6 9 9 10 10 12
Hình 2-2: Sp xp xen
Chng trình
procedure InsertionSort;
var
i,j: integer;
begin
{1} for i := 2 to n do begin
{2} J := i;
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
Ban u
5 6 2 2 10 12 9 10 9 3
c 1
2
5 6 2 3 10 12 9 10 9
c 2
2
5 6 3 9 10 12 9 10
c 3
3
5 6 9 9 10 12 10
c 4
5
6 9 9 10 10 12
c 5
6
9 9 10 10 12
c 6
9
9 10 10 12
c 7
9
10 10 12
c 8
10
10 12
c 9
10
12
(pivot). Ta phân hoch dãy a[1]..a[n] thành hai mng con "bên trái" và "bên phi". Mng con "bên trái"
bao gm các phn t có khóa nh hn cht, mng con "bên phi" bao gm các phn t có khóa ln hn
hoc bng cht.
Sp xp mng con “bên trái” và mng con “bên phi” thì mng ã cho sc sp bi vì tt c
các khóa trong mng con “bên trái “ u nh hn các khóa trong mng con “bên phi”.
Vic sp xp các mng con “bên trái” và “bên phi” cng c tin hành bng phng pháp
nói trên.
Mt mng ch gm mt phn t hoc gm nhiu phn t có khóa bng nhau thì xem nhã có
th t.
II.3.2- Thit k gii thut
n chn cht
Chn khóa ln nht trong hai phn t có khóa khác nhau u tiên k t trái qua. Nu mng ch
m mt phn t hay gm nhiu phn t có khóa bng nhau thì không có cht.
n phn hoch
phân hoch mng ta dùng 2 "con nháy" L và R trong ó L t bên trái và R t bên phi, ta
cho L chy sang phi cho ti khi gp phn t có khóa cht và cho R chy sang trái cho ti khi gp
phn t có khóa < cht. Ti ch dng ca L và R nu L<R thì hoán v a[L],a[R]. Lp li quá trình dch
sang phi, sang trái ca 2 "con nháy" L và R cho n khi L>R. Khi ó L s là m phân hoch, c th
là a[L] là phn tu tiên ca mng con “bên phi”.
Gii thut QuickSort
sp xp mng a[i]..a[j] ta tin hành các bc sau:
· Xác nh cht,
· Phân hoch mng ã cho thành hai mng con a[i]..a[k-1] và a[k]..a[j].
· Sp xp mng a[i]..a[k-1] ( quy).
· Sp xp mng a[k]..a[j] ( quy).
Quá trình quy s dng khi không còn tìm thy cht.
Ví d 2-4: Ta cn sp mt mng mà khóa là các s nguyên ã c trình bày trong ví d 2-1.
Hai phn tu tiên có khóa khác nhau là 5 và 6, ta chn 6 làm cht và tin hành phân hoch mng
ban u làm hai mng con và quy cho hai mng con này.
Collected by The_Wall (11/10/2005)
a[i]..a[j] theo cht Pivot và tr v giá tr l là ch su tiên ca mng “bên phi”.
Collected by The_Wall (11/10/2005)
Giáo trình môn Phân tích Gii Thut – I C CN TH........................................................................Trang 23
Hai con nháy L, R sc s dng thc hin vic phân hoch nhã trình bày trong phn
II.3.2.
Function Partition(i,j:integer; pivot :KeyType):integer ;
var l,r : integer;
begin
l := i; {t con nháy L ì bên trái}
r := j; {t con nháy R ì bên phi}
while l <= r do begin
{L tin sang phi}
while a[l].key < pivot do l := l+1;
{R tin sang trái}
while a[r].key >= pivot do r := r-1;
if l <r then Swap(a[l],a[r]);
end;
Partition :=l;
end;
QuickSort
Bây gi chúng ta trình bày th tc cui cùng có tên là QuickSort và chú ý rng sp xp
ng A các record gm n phn t ca kiu Recordtype ta ch cn gi QuickSort(1,n).
Ta s s dng bin PivotIndex lu gi kt qu tr v ca hàm FindPivot, nu bin
PivotIndex nhn c mt giá tr khác 0 thì mi tin hành phân hoch mng. Bin Pivot sc s
ng lu gi giá tr cht và bin k lu gi giá tr ca m phân hoch do hàm Partition tr v.
Sau khia ã phân hoch xong ta s gi quy QuickSort cho mng con “bên trái” a[i]..a[k-1] và mng
con “bên phi” a[k]..a[j].
procedure Quicksort(i,j:integer);
var
Pivot : KeyType;
. . . . . . . . . . . . . . . . .
= T(n-i) + (n-i+2) + (n-i+3) + ... + n + (n+1) = T(n-i) +
Quá trình trên kt thúc khi i=n-1, khi ó ta có
Trong trng hp tt nht khi ta chn c cht sao cho hai mng con có kích thc bng
nhau và bng n/2. Lúc ó ta có phng trình quy nh sau:
Gii phng trình quy này (xem I.4.2) ta c T(n) = O(nlogn).
Ngi ta cng chng minh c rng trong trng hp trung bình QuickSort ly T(n) =
O(nlogn).
II.4- HEAPSORT
II.4.1- Heap
II.4.2- Ý tng
II.4.3- Thit k và cài t gii thut
II.4.4- Phân tích HeapSort
Collected by The_Wall (11/10/2005)
Giáo trình môn Phân tích Gii Thut – I C CN TH........................................................................Trang 25
II.4.1- Heap
Cây sp th t b phn hay còn gi là heap là cây nh phân mà giá tr ti mi nút (khác nút lá)
u không ln hn giá tr ca các con ca nó.
Ta có nhn xét rng nút gc a[1] ca cây sp th t b phn có giá tr nh nht.
Ví d 2-5: Cây sau là mt heap.
II.4.2- Ý tng
(1) Xem mng ban u là mt cây nh phân. Mi nút trên cây lu tr mt phn t mng,
trong ó a[1] là nút gc và mi nút không là nút lá a[i] có con trái là a[2i] và con phi là a[2i+1]. Vi
cách t chc này thì cây nh phân thu c s có các nút trong là các nút a[1],..,a[n DIV 2]. Tt c các
nút trong u có 2 con, ngoi tr nút a[n DIV 2] có th ch có mt con trái (trong trng hp n là mt
chn).
(2) Sp xp cây ban u thành mt heap cn c vào giá tr khoá ca các nút.
(3) Hoán i a[1] cho cho phn t cui cùng.
(4) p li cây sau khi ã bi phn t cui cùng nó tr thành mt heap mi.
Lp li quá trình (3) và (4) cho ti khi cây rng ta sc mng sp theo th t gim.
Copyright: Tài liệu đại học ©