Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Thuật toán và phân tích thuật toán
Ch-¬ng I
ThuËt to¸n vµ ph©n tÝch thuËt to¸n
1.1. ThuËt to¸n.
1.1.1. Kh¸i niÖm thuËt to¸n.
ThuËt to¸n (algorithm) lµ mét trong nh÷ng kh¸i niÖm quan träng nhÊt
trong tin häc. ThuËt ng÷ thuËt to¸n xuÊt ph¸t tõ nhµ to¸n häc A rËp Abu Ja'far
Mohammed ibn Musa al Khowarizmi (kho¶ng n¨m 825). Tuy nhiªn lóc bÊy
giê vµ trong nhiÒu thÕ kû sau, nã kh«ng mang néi dung nh- ngµy nay chóng ta
quan niÖm. ThuËt to¸n næi tiÕng nhÊt, cã tõ thêi cæ Hy l¹p lµ thuËt to¸n Euclid,
thuËt to¸n t×m -íc chung lín nhÊt cña hai sè nguyªn. Cã thÓ m« t¶ thuËt to¸n
nµy nh- sau :
ThuËt to¸n Euclid.
Input : m, n nguyªn d-¬ng
Output : g, -íc chung lín nhÊt cña m vµ n
Ph-¬ng ph¸p :
B-íc 1 : T×m r, phÇn d- cña phÐp chia m cho n
B-íc 2 : NÕu r = O, th× g n (g¸n gi¸ trÞ cña n cho g) vµ dõng l¹i.
Trong tr-êng hîp ng-îc l¹i (r 0), th× m n, n r vµ quay l¹i b-íc 1.
Chóng ta cã thÓ quan niÖm c¸c b-íc cÇn thùc hiÖn ®Ó lµm mét mãn ¨n,
®-îc m« t¶ trong c¸c s¸ch d¹y chÕ biÕn mãn ¨n, lµ mét thuËt to¸n. Còng cã thÓ
xem c¸c b-íc cÇn tiÕn hµnh ®Ó gÊp ®å ch¬i b»ng giÊy, ®-îc tr×nh bÇy trong
s¸ch d¹y gÊp ®å ch¬i b»ng giÊy, lµ thuËt to¸n. Ph-¬ng ph¸p thùc hiÖn phÐp
céng, nh©n c¸c sè nguyªn, chóng ta ®· häc ë cÊp I còng lµ c¸c thuËt to¸n.
Trong s¸ch nµy chóng ta chØ cÇn ®Õn ®Þnh nghÜa kh«ng h×nh thøc vÒ
thuËt to¸n :
ThuËt to¸n lµ mét d·y h÷u h¹n c¸c b-íc, mçi b-íc m« t¶ chÝnh x¸c c¸c
phÐp to¸n hoÆc hµnh ®éng cÇn thùc hiÖn, ®Ó gi¶i quyÕt mét sè vÊn ®Ò.
(Tõ ®iÓm Oxford Dictionary ®Þnh nghÜa, Algorithm: set of well - defined
rules for solving a problem in a finite number of steps.)
§Þnh nghÜa nµy, tÊt nhiªn, cßn chøa ®ùng nhiÒu ®iÒu ch-a râ rµng. §Ó
hiÓu ®Çy ®ñ ý nghÜa cña kh¸i niÖm thuËt to¸n, chóng ta nªu ra 5 ®Æc tr-ng sau
®©y cña thuËt to¸n (Xem D.E. Knuth [1968]. The Art of Computer
Programming, vol. I. Fundamental Algorithms).
5
1. Input. Mçi thuËt to¸n cÇn cã mét sè (cã thÓ b»ng kh«ng) d÷ liÖu vµo
(input). §ã lµ c¸c gi¸ trÞ cÇn ®-a vµo khi thuËt to¸n b¾t ®Çu lµm viÖc. C¸c d÷
liÖu nµy cÇn ®-îc lÊy tõ c¸c tËp hîp gi¸ trÞ cô thÓ nµo ®ã. Ch¼ng h¹n, trong
thuËt to¸n Euclid trªn, m vµ n lµ c¸c d÷ liÖu vµo lÊy tõ tËp c¸c sè nguyªn
d-¬ng.
2. Output. Mçi thuËt to¸n cÇn cã mét hoÆc nhiÒu d÷ liÖu ra (output). §ã
lµ c¸c gi¸ trÞ cã quan hÖ hoµn toµn x¸c ®Þnh víi c¸c d÷ liÖu vµo vµ lµ kÕt qu¶
cña sù thùc hiÖn thuËt to¸n. Trong thuËt to¸n Euclid cã mét d÷ liÖu ra, ®ã lµ g,
khi thùc hiÖn ®Õn b-íc 2 vµ ph¶i dõng l¹i (tr-êng hîp r = 0), gi¸ trÞ cña g lµ
-íc chung lín nhÊt cña m vµ n.
3. TÝnh x¸c ®Þnh. Mçi b-íc cña thuËt to¸n cÇn ph¶i ®-îc m« t¶ mét
c¸ch chÝnh x¸c, chØ cã mét c¸ch hiÓu duy nhÊt. HiÓn nhiªn, ®©y lµ mét ®ßi hái
rÊt quan träng. Bëi v×, nÕu mét b-íc cã thÓ hiÓu theo nhiÒu c¸ch kh¸c nhau, th×
cïng mét d÷ liÖu vµo, nh÷ng ng-êi thùc hiÖn thuËt to¸n kh¸c nhau cã thÓ dÉn
®Õn c¸c kÕt qu¶ kh¸c nhau. NÕu ta m« t¶ thuËt to¸n b»ng ng«n ng÷ th«ng
th-êng, kh«ng cã g× ®¶m b¶o ng-êi ®äc hiÓu ®óng ý cña ng-êi viÕt thuËt to¸n.
§Ó ®¶m b¶o ®ßi hái nµy, thuËt to¸n cÇn ®-îc m« t¶ trong c¸c ng«n ng÷ lËp
tr×nh (ng«n ng÷ m¸y, hîp ng÷ hoÆc ng«n ng÷ bËc cao nh- Pascal, Fortran, C,
...). Trong c¸c ng«n ng÷ nµy, c¸c mÖnh ®Ò ®-îc t¹o thµnh theo c¸c qui t¾c có
ph¸p nghiªm ngÆt vµ chØ cã mét ý nghÜa duy nhÊt.
4. TÝnh kh¶ thi. TÊt c¶ c¸c phÐp to¸n cã mÆt trong c¸c b-íc cña thuËt
to¸n ph¶i ®ñ ®¬n gi¶n. §iÒu ®ã cã nghÜa lµ, c¸c phÐp to¸n ph¶i sao cho, Ýt nhÊt
vÒ nguyªn t¾c cã thÓ thùc hiÖn ®-îc bëi con ng-êi chØ b»ng giÊy tr¾ng vµ bót
ch× trong mét kho¶ng thêi gian h÷u h¹n. Ch¼ng h¹n trong thuËt to¸n Euclid, ta
chØ cÇn thùc hiÖn c¸c phÐp chia c¸c sè nguyªn, c¸c phÐp g¸n vµ c¸c phÐp so
s¸nh ®Ó biÕt r = 0 hay r 0.
5. TÝnh dõng. Víi mäi bé d÷ liÖu vµo tho¶ m·n c¸c ®iÒu kiÖn cña d÷
liÖu vµo (tøc lµ ®-îc lÊy ra tõ c¸c tËp gi¸ trÞ cña c¸c d÷ liÖu vµo), thuËt to¸n
ph¶i dõng l¹i sau mét sè h÷u h¹n b-íc thùc hiÖn. Ch¼ng h¹n, thuËt to¸n Euclid
tho¶ m·n ®iÒu kiÖn nµy. Bëi v× gi¸ trÞ cña r lu«n nhá h¬n n (khi thùc hiÖn b-íc
1), nÕu r 0 th× gi¸ trÞ cña n ë b-íc 2 lµ gi¸ trÞ cña r ë b-íc tr-íc, ta cã n > r =
n1 > r1 = n2 > r2 ... D·y sè nguyªn d-¬ng gi¶m dÇn cÇn ph¶i kÕt thóc ë 0, do
®ã sau mét sè b-íc nµo ®ã gi¸ trÞ cña r ph¶i b»ng 0, thuËt to¸n dõng.
Víi mét vÊn ®Ò ®Æt ra, cã thÓ cã mét hoÆc nhiÒu thuËt to¸n gi¶i. Mét vÊn
®Ò cã thuËt to¸n gi¶i gäi lµ vÊn ®Ò gi¶i ®-îc (b»ng thuËt to¸n). Ch¼ng h¹n, vÊn
®Ò t×m nghiÖm cña hÖ ph-¬ng tr×nh tuyÕn tÝnh lµ vÊn ®Ò gi¶i ®-îc. Mét vÊn ®Ò
kh«ng tån t¹i thuËt to¸n gi¶i gäi lµ vÊn ®Ò kh«ng gi¶i ®-îc (b»ng thuËt to¸n).
Mét trong nh÷ng thµnh tùu xuÊt s¾c nhÊt cña to¸n häc thÕ kû 20 lµ ®· t×m ra
nh÷ng vÊn ®Ò kh«ng gi¶i ®-îc b»ng thuËt to¸n.
6
Trªn ®©y chóng ta ®· tr×nh bµy ®Þnh nghÜa kh«ng h×nh thøc vÒ thuËt
to¸n. Cã thÓ x¸c ®Þnh kh¸i niÖm thuËt to¸n mét c¸ch chÝnh x¸c b»ng c¸ch sö
dông c¸c hÖ h×nh thøc. Cã nhiÒu hÖ h×nh thøc m« t¶ thuËt to¸n : m¸y Turing,
hÖ thuËt to¸n Mark«p, v¨n ph¹m Chomsky d¹ng 0, ... Song vÊn ®Ò nµy kh«ng
thuéc ph¹m vi nh÷ng vÊn ®Ò mµ chóng ta quan t©m. §èi víi chóng ta, chØ sù
hiÓu biÕt trùc quan, kh«ng h×nh thøc vÒ kh¸i niÖm thuËt to¸n lµ ®ñ.
1.1.2. BiÓu diÔn thuËt to¸n.
Cã nhiÒu ph-¬ng ph¸p biÓu diÔn thuËt to¸n. Cã thÓ biÓu diÔn thuËt to¸n
b»ng danh s¸ch c¸c b-íc, c¸c b-íc ®-îc diÔn ®¹t b»ng ng«n ng÷ th«ng th-êng
vµ c¸c ký hiÖu to¸n häc. Cã thÓ biÓu diÔn thuËt to¸n b»ng s¬ ®å khèi. Tuy
nhiªn, nh- ®· nãi, ®Ó ®¶m b¶o tÝnh x¸c ®Þnh cña thuËt to¸n, thuËt to¸n cÇn
®-îc viÕt trong c¸c ng«n ng÷ lËp tr×nh. Mét ch-¬ng tr×nh lµ sù biÓu diÔn cña
mét thuËt to¸n trong ng«n ng÷ lËp tr×nh ®· chän. §Ó ®äc dÔ dµng c¸c phÇn tiÕp
theo, ®éc gi¶ cÇn lµm quen víi ng«n ng÷ lËp tr×nh Pascal. §ã lµ ng«n ng÷
th-êng ®-îc chän ®Ó tr×nh bµy c¸c thuËt to¸n trong s¸ch b¸o.
Trong s¸ch nµy chóng ta sÏ tr×nh bµy c¸c thuËt to¸n bëi c¸c thñ tôc hoÆc
hµm trong ng«n ng÷ tùa Pascal. Nãi lµ tùa Pascal, bëi v× trong nhiÒu tr-êng
hîp, ®Ó cho ng¾n gän, chóng ta kh«ng hoµn toµn tu©n theo c¸c qui ®Þnh cña
Pascal. Ngoµi ra, cã tr-êng hîp, chóng ta xö dông c¶ c¸c ký hiÖu to¸n häc vµ
c¸c mÖnh ®Ò trong ng«n ng÷ tù nhiªn (tiÕng Anh hoÆc tiÕng ViÖt). Sau ®©y lµ
mét sè vÝ dô.
VÝ dô 1 : ThuËt to¸n kiÓm tra sè nguyªn n(n > 2) cã lµ sè nguyªn tè hay
kh«ng.
function
var
NGTO (n : integer) : boolean ;
a : integer ;
begin
NGTO : = true ;
a : = 2 ;
while a <= sqrt (n) do
if n mod a = 0 then NGTO : = false
else a : = a +1 ;
end ;
VÝ dô 2 : Bµi to¸n th¸p Hµ Néi. Cã ba cäc A, B, C. Lóc ®Çu, ë cäc A cã
n ®Üa ®-îc lång vµo theo thø tù nhá dÇn tõ thÊp lªn cao. §ßi hái ph¶i chuyÓn n
7
®Üa tõ cäc A sang cäc B, ®-îc quyÒn sö dông cäc C lµm vÞ trÝ trung gian,
nh-ng kh«ng ®-îc phÐp ®Æt ®Üa lín lªn trªn ®Üa nhá.
§Ó chuyÓn n ®Üa tõ cäc A sang cäc B, ta thùc hiÖn thñ tôc sau : ®Çu tiªn
lµ chuyÓn n - 1 ®Üa bªn trªn tõ cäc A sang cäc C, sau ®ã chuyÓn ®Üa lín nhÊt tõ
cäc A sang cäc B. §Õn ®©y, chØ cÇn cuyÓn n - 1 ®Üa tõ cäc C sang cäc B. ViÖc
chuyÓn n-1 ®Üa tõ cäc nµy sang cäc kia ®-îc thùc hiÖn b»ng c¸ch ¸p dông ®Ö
qui thñ tôc trªn.
Procedure MOVE (n, A, B, C) ;
{thñ tôc chuyÓn n ®Üa tõ cäc A sang cäc B}
begin
if n=1 then chuyÓn mét ®Üa tõ cäc A sang cäc B
else
begin
MOVE (n-1, A, C, B) ;
ChuyÓn mét ®Üa tõ cäc A sang cäc B ;
MOVE (n-1, C, B, A) ;
end
end ;
A
B
C
1.1.3. C¸c vÊn ®Ò liªn quan ®Õn thuËt to¸n.
ThiÕt kÕ thuËt to¸n.
§Ó gi¶i mét bµi to¸n trªn MT§T, ®iÒu tr-íc tiªn lµ chóng ta ph¶i cã
thuËt to¸n. Mét c©u hái ®Æt ra lµ, lµm thÕ nµo ®Ó t×m ra thuËt to¸n cho mét bµi
to¸n ®· ®Æt ra ? Líp c¸c bµi to¸n ®-îc ®Æt ra tõ c¸c ngµnh khoa häc kü thuËt tõ
c¸c lÜnh vùc ho¹t ®éng cña con ng-¬× lµ hÕt søc phong phó vµ ®a d¹ng. C¸c
thuËt to¸n gi¶i c¸c líp bµi to¸n kh¸c nhau còng rÊt kh¸c nhau. Tuy nhiªn, cã
mét sè kü thuËt thiÕt kÕ thuËt to¸n chung nh- chia-®Ó-trÞ (divide-and-conquer),
ph-¬ng ph¸p tham lam (greedy method), qui ho¹ch ®éng (dynamic
programming), ... ViÖc n¾m ®-îc c¸c chiÕn l-îc thiÕt kÕ thuËt to¸n nµy lµ hÕt
8
søc cÇn thiÕt, nã gióp cho b¹n dÔ t×m ra c¸c thuËt to¸n míi cho c¸c bµi to¸n
cña b¹n. C¸c ®Ò tµi nµy sÏ ®-îc ®Ò cËp ®Õn trong tËp II cña s¸ch nµy.
TÝnh ®óng ®¾n cña thuËt to¸n.
Khi mét thuËt to¸n ®-îc lµm ra, ta cÇn ph¶i chøng minh r»ng, thuËt to¸n
khi ®ùoc thùc hiÖn sÏ cho ta kÕt qu¶ ®óng víi mäi d÷ liÖu vµo hîp lÖ. §iÒu nµy
gäi lµ chøng minh tÝnh ®óng ®¾n cña thuËt to¸n. ViÖc chøng minh mét thuËt
to¸n ®óng ®¾n lµ mét c«ng viÖc kh«ng dÔ dµng. Trong nhiÒu tr-êng hîp, nã
®ßi hái ta ph¶i cã tr×nh ®é vµ kh¶ n¨ng t- duy to¸n häc tèt.
Sau ®Êy ta sÏ chØ ra r»ng, khi thùc hiÖn thuËt to¸n Euclid, g sÏ lµ -íc
chung lín nhÊt cña hai sè nguyªn d-¬ng m vµ n bÊt kú. ThËt vËy khi thùc hiÖn
b-íc 1, ta cã m = qn + r, trong ®ã q lµ sè nguyªn nµo ®ã. NÕu r = 0 th× n lµ -íc
cña m vµ hiÓn nhiªn n (do ®ã g) lµ -íc chung lín nhÊt cña m vµ n. NÕu r 0,
th× mét -íc chung bÊt kú cña m vµ n còng lµ -íc chung cña n vµ r (v× r = m -
qn). Ng-îc l¹i mét -íc chung bÊt kú cña n vµ r còng lµ -íc chung cña m vµ n
(v× m = qn + r). Do ®ã -íc chung lín nhÊt cña n vµ r còng lµ -íc chung lín
nhÊt cña m vµ n. V× vËy, khi thùc hiÖn lÆp l¹i b-íc 1 víi sù thay ®æi gi¸ trÞ cña
m bëi n gi¸ trÞ cña n bëi r (c¸c phÐp g¸n m , nr ë b-íc 2) cho tíi khi r = 0,
ta sÏ nhËn ®-îc gi¸ trÞ cña g lµ -íc chung lín nhÊt cña c¸c gi¸ trÞ m vµ n ban
®Çu.
Ph©n tÝch thuËt to¸n.
Gi¶ sö ®èi víi mét bµi to¸n nµo ®ã chóng ta cã mét sè thuËt to¸n gi¶i.
Mét c©u hái míi xuÊt hiÖn lµ, chóng ta cÇn chän thuËt to¸n nµo trong sè c¸c
thuËt to¸n ®ã ®Ó ¸p dông. ViÖc ph©n tÝch thuËt to¸n, ®¸nh gi¸ ®é phøc t¹p cña
nã lµ néi dung cña phÇn sau.
1.2. Ph©n tÝch thuËt to¸n.
1.2.1. TÝnh hiÖu qu¶ cña thuËt to¸n.
Khi gi¶i mét vÊn ®Ò, chóng ta cÇn chän trong sè c¸c thuËt to¸n, mét
thuËt to¸n mµ chóng ta cho lµ "tèt" nhÊt. VËy ta cÇn lùa chän thuËt to¸n dùa
trªn c¬ së nµo ? Th«ng th-êng ta dùa trªn hai tiªu chuÈn sau ®©y :
1. ThuËt to¸n ®¬n gi¶n, dÔ hiÓu, dÔ cµi ®Æt (dÔ viÕt ch-¬ng tr×nh)
2. ThuËt to¸n sö dông tiÕt kiÖm nhÊt c¸c nguån tµi nguyªn cña m¸y tÝnh,
vµ ®Æc biÖt, ch¹y nhanh nhÊt cã thÓ ®-îc.
Khi ta viÕt mét ch-¬ng tr×nh chØ ®Ó sö dông mét sè Ýt lÇn, vµ c¸i gi¸ cña
thêi gian viÕt ch-¬ng tr×nh v-ît xa c¸i gi¸ cña ch¹y ch-ong tr×nh th× tiªu chuÈn
(1) lµ quan träng nhÊt. Nh-ng cã tr-êng hîp ta cÇn viÕt c¸c ch-¬ng tr×nh (hoÆc
thñ tôc, hµm) ®Ó sö dông nhiÒu lÇn, cho nhiÒu ng-êi sö dông, khi ®ã gi¸ cña
thêi gian ch¹y ch-¬ng tr×nh sÏ v-ît xa gi¸ viÕt nã. Ch¼ng h¹n, c¸c thñ tôc s¾p
9
xÕp, t×m kiÕm ®-îc sö dông rÊt nhiÒu lÇn, bëi rÊt nhiÒu ng-êi trong c¸c bµi
to¸n kh¸c nhau. Trong tr-êng hîp nµy ta cÇn dùa trªn tiªu chuÈn (2). Ta sÏ cµi
®Æt thuËt to¸n cã thÓ rÊt phøc t¹p, miÔn lµ ch-¬ng tr×nh nhËn ®-îc ch¹y nhanh
h¬n c¸c ch-¬ng tr×nh kh¸c.
Tiªu chuÈn (2) ®-îc xem lµ tÝnh hiÖu qu¶ cña thuËt to¸n. TÝnh hiÖu qu¶
cña thuËt to¸n bao gåm hai nh©n tè c¬ b¶n.
1. Dung l-îng kh«ng gian nhí cÇn thiÕt ®Ó l-u gi÷ c¸c d÷ liÖu vµo, c¸c
kÕt qu¶ tÝnh to¸n trung gian vµ c¸c kÕt qu¶ cña thuËt to¸n.
2. Thêi gian cÇn thiÕt ®Ó thùc hiÖn thuËt to¸n (ta gäi lµ thêi gian ch¹y).
Chóng ta sÏ chØ quan t©m ®Õn thêi gian thùc hiÖn thuËt to¸n. V× vËy, khi
nãi ®Õn ®¸nh gi¸ ®é phøc t¹p cña thuËt to¸n, cã nghÜa lµ ta nãi ®Õn ®¸nh gia
thêi gian thùc hiÖn. Mét thuËt to¸n cã hiÖu qu¶ ®-îc xem lµ thuËt to¸n cã thêi
gian ch¹y Ýt h¬n c¸c thuËt to¸n kh¸c.
1.2.2. T¹i sao l¹i cÇn thuËt to¸n cã hiÖu qu¶.
Kü thuËt m¸y tÝnh tiÕn bé rÊt nhanh, ngµy nay c¸c m¸y tÝnh lín cã thÓ
®¹t tèc dé tÝnh to¸n hµng tr¨m triÖu phÐp tÝnh mét gi©y. VËy th× cã bâ c«ng
ph¶i tiªu tèn thêi gian ®Ó thiÕt kÕ c¸c thuËt to¸n cã hiÖu qu¶ kh«ng ? Mét sè vÝ
dô sau ®©y sÏ tr¶ lêi cho c©u hái nµy.
VÝ dô 1 : TÝnh ®Þnh thøc.
Gi¶ sö M lµ mét ma trËn vu«ng cÊp n :
a
a12 ... a
1n
11
a21 a22 ... a2n
M
.
.
.
.
an1 an2 ... ann
§Þnh thøc cña ma trËn M ký hiÖu lµ det(M) ®-îc x¸c ®Þnh ®Ö qui nh-
sau :
NÕu n = 1, det(M) = a11. NÕu n >1, ta gäi Mij lµ ma trËn con cÊp n -1,
nhËn ®-îc tõ ma trËn M b»ng c¸ch lo¹i bá dßng thø i vµ cét thø j, vµ
n
det( M) (1)1 j a det M
1 j
1 j
j1
DÔ dµng thÊy r»ng, nÕu ta tÝnh ®Þnh thøc trùc tiÕp dùa vµo c«ng thøc ®Ö
qui nµy, cÇn thùc hiÖn n! phÐp nh©n. Mét con sè khæng lå víi n kh«ng lÊy g×
10
lµm lín. Ngay c¶ víi tèc ®é cña m¸y tÝnh lín hiÖn ®¹i, ®Ó tÝnh ®Þnh thøc cña
ma trËn cÊp n = 25, còng cÇn hµng triÖu n¨m !
Mét thuËt to¸n cæ ®iÓn kh¸c, ®ã lµ thuËt to¸n Gauss - Jordan thuËt to¸n
nµy tÝnh ®Þnh thøc cÊp n trong thêi gian n3.
§Ó tÝnh ®Þnh thøc cÊp n = 100 b»ng thuËt to¸n nµy trªn m¸y tÝnh lín ta
chØ cÇn ®Õn 1 gi©y.
VÝ dô 2 : Bµi to¸n th¸p Hµ Néi.
Trong vÝ dô 2, môc 1.1 ta ®· ®-a ra mét thuËt to¸n ®Ó chuyÓn n ®Üa tõ
cäc A sang cäc B. Ta thö tÝnh xem, cÇn thùc hiÖn bao nhiªu lÇn chuyÓn ®Üa tõ
cäc nµy sang cäc kh¸c (kh«ng ®Æt ®Üa to lªn trªn ®Üa nhá) ®Ó chuyÓn ®-îc n
®Üa tõ cäc A sang cäc B. Gäi sè ®ã lµ F(n). Tõ thuËt to¸n, ta cã :
F(1) = 1,
F(n) = 2F(n-1) + 1 víi n > 1.
víi n = 1, 2, 3 ta cã F(1) = 1, F(2) = 3, F(3) = 7.
B»ng c¸ch qui n¹p, ta chøng minh ®-îc F(n) = 2n - 1.
Víi n = 64, ta cã F(64) = 264 -1 lÇn chuyÓn. Gi¶ sö mçi lÇn chuyÓn mét
®Üa tõ cäc nµy sang cäc kh¸c, cÇn 1 gi©y. Khi ®ã ®Ó thùc hiÖn 264 -1 lÇn
chuyÓn, ta cÇn 5 x 1011 n¨m. NÕu tuæi cña vò trô lµ 10 tØ n¨m, ta cÇn 50 lÇn
tuæi cña vò trô ®Ó chuyÓn 64 ®Üa !.
§èi víi mét vÊn ®Ò cã thÓ cã nhiÒu thuËt to¸n, trong sè ®ã cã thÓ thuËt
to¸n nµy hiÖu qu¶ h¬n (ch¹y nhanh h¬n) thuËt to¸n kia. Tuy nhiªn, còng cã
nh÷ng vÊn ®Ò kh«ng tån t¹i thuËt to¸n hiÖu qu¶, tøc lµ cã thuËt to¸n, song thêi
gian thùc hiÖn nã lµ qu¸ lín, trong thùc tÕ kh«ng thÓ thùc hiÖn ®-îc, dï lµ trªn
c¸c m¸y tÝnh lín hiÖn ®¹i nhÊt.
1.2.3. §¸nh gi¸ thêi gian thùc hiÖn thuËt to¸n nh- thÕ nµo ?
Cã hai c¸ch tiÕp cËn ®Ó ®¸nh gi¸ thêi gian thùc hiÖn cña mét thuËt
to¸n.Trong ph-¬ng ph¸p thö nghiÖm, chóng ta viÕt ch-¬ng tr×nh vµ cho ch¹y
ch-¬ng tr×nh víi c¸c d÷ liÖu vµo kh¸c nhau trªn mét m¸y tÝnh nµo ®ã. Thêi
gian ch¹y ch-¬ng tr×nh phô thuéc vµo c¸c nh©n tè chÝnh sau ®©y :
1. C¸c d÷ liÖu vµo
2. Ch-¬ng tr×nh dÞch ®Ó chuyÓn ch-¬ng tr×nh nguån thµnh m· m¸y.
3. Tèc ®é thùc hiÖn c¸c phÐp to¸n cña m¸y tÝnh ®-îc sö dông ®Ó ch¹y
ch-¬ng tr×nh.
V× thêi gian ch¹y ch-¬ng tr×nh phô thuéc vµo nhiÒu nh©n tè, nªn ta
kh«ng thÓ biÓu diÔn chÝnh x¸c thêi gian ch¹y lµ bao nhiªu ®¬n vÞ thêi gian
chuÈn, ch¼ng h¹n nã lµ bao nhiªu gi©y.
11
Trong ph-¬ng ph¸p lý thuyÕt (®ã lµ ph-¬ng ph¸p ®-îc sö dông trong
s¸ch nµy), ta sÏ coi thêi gian thùc hiÖn thuËt to¸n nh- lµ hµm sè cña cì d÷ liÖu
vµo. Cì cña d÷ liÖu vµo lµ mét tham sè ®Æc tr-ng cho d÷ liÖu vµo, nã cã ¶nh
h-ëng quyÕt ®Þnh ®Õn thêi gian thùc hiÖn ch-¬ng tr×nh. C¸i mµ chóng ta chän
lµm cì cña d÷ liÖu vµo phô thuéc vµo c¸c thuËt to¸n cô thÓ. §èi víi c¸c thuËt
to¸n s¾p xÕp m¶ng, cì cña d÷ liÖu lµ sè thµnh phÇn cña m¶ng. §èi víi thuËt
to¸n gi¶i hÖ n ph-¬ng tr×nh tuyÕn tÝnh víi n Èn, ta chän n lµ cì. Th«ng th-êng
cì cña d÷ liÖu vµo lµ mét sè nguyªn d-¬ng n. Ta sÏ sö dông hµm sè T(n), trong
®ã n lµ cì d÷ liÖu vµo, ®Ó biÓu diÔn thêi gian thùc hiÖn cña mét thuËt to¸n.
Thêi gian thùc hiÖn thuËt to¸n T(n) nãi chung kh«ng chØ phô thuéc vµo
cì cña d÷ liÖu vµo, mµ cßn phô thuéc vµo d÷ liÖu vµo c¸ biÖt. Ch¼ng h¹n, ta xÐt
bµi to¸n x¸c ®Þnh mét ®èi t-îng a cã mÆt trong danh s¸ch n phÇn tö (a1, a2, ...
an) hay kh«ng. ThuËt to¸n ë ®©y lµ, so s¸nh a víi tõng phÇn tö cña danh s¸ch ®i
tõ ®Çu ®Õn cuèi danh s¸ch, khi gÆp phÇn tö ai ®Çu tiªn ai = a th× dõng l¹i, hoÆc
®i ®Õn hÕt danh s¸ch mµ kh«ng gÆp ai nµo b»ng a, trong tr-êng hîp nµy a
kh«ng cã trong danh s¸ch. C¸c d÷ liÖu vµo lµ a vµ danh s¸ch (a1, a2, ..., an) (cã
thÓ biÓu diÔn danh s¸ch b»ng m¶ng, ch¼ng h¹n). Cì cña d÷ liÖu vµo lµ n. NÕu
a1 = a chØ cÇn mét phÐp so s¸nh. NÕu a1a, a2 = a, cÇn 2 phÐp so s¸nh. Cßn nÕu
ai a, i = 1, ..., n-1 vµ an = a, hoÆc a kh«ng cã trong danh s¸ch, ta cÇn n phÐp
so s¸nh. NÕu xem thêi gian thùc hiÖn T(n) lµ sè phÐp to¸n so s¸nh, ta cã T(n)
<= n, trong tr-êng hîp xÊu nhÊt T(n) = n. Trong c¸c tr-êng hîp nh- thÕ, ta nãi
®Õn thêi gian thùc hiÖn thuËt to¸n trong tr-êng hîp xÊu nhÊt.
Ngoµi ra, ta cßn sö dông kh¸i niÖm thêi gian thùc hiÖn trung b×nh. §ã lµ
thêi gian trung b×nh Ttb(n) trªn tÊt c¶ c¸c d÷ liÖu vµo cã cì n. Nãi chung thêi
gian thùc hiÖn trung b×nh khã x¸c ®Þnh h¬n thêi gian thùc hiÖn trong tr-êng
hîp xÊu nhÊt.
Chóng ta cã thÓ x¸c ®Þnh thêi gian thùc hiÖn T(n) lµ sè phÐp to¸n s¬ cÊp
cÇn ph¶i tiÕn hµnh khi thùc hiÖn thuËt to¸n. C¸c phÐp to¸n s¬ cÊp lµ c¸c phÐp
to¸n mµ thêi gian thùc hiÖn bÞ chÆn trªn bëi mét h»ng sè chØ phô thuéc vµo
c¸ch cµi ®Æt ®-îc sö dông (ng«n ng÷ lËp tr×nh, m¸y tÝnh ...). Ch¼ng h¹n c¸c
phÐp to¸n sè häc +, - , *, /, c¸c phÐp to¸n so s¸nh = , < >, <, <= , > , > = lµ c¸c
phÐp to¸n s¬ cÊp. PhÐp to¸n so s¸nh hai x©u ký tù kh«ng thÓ xem lµ phÐp to¸n
s¬ cÊp, v× thêi gian thùc hiÖn nã phô thuéc vµo ®é dµi cña x©u.
1.2.4 Ký hiÖu « lín vµ ®¸nh gi¸ thêi gian thùc hiÖn thuËt to¸n b»ng
ký hiÖu « lín.
Khi ®¸nh gi¸ thêi gian thùc hiÖn b»ng ph-¬ng ph¸p to¸n häc, chóng ta
sÏ bá qua nh©n tè phô thuéc vµo c¸ch cµi ®Æt chØ tËp trung vµo x¸c ®Þnh ®é lín
cña thêi gian thùc hiÖn T(n). Ký hiÖu to¸n häc « lín ®-îc sö dông ®Ó m« t¶ ®é
lín cña hµm T(n).
12
Gi¶ sö n lµ sè nguyªn kh«ng ©m, T(n) vµ f(n) lµ c¸c hµm thùc kh«ng ©m.
Ta viÕt T(n) = 0(f(n)) (®äc : T(n) lµ « lín cña f(n)), nÕu vµ chØ nÕu tån t¹i c¸c
h»ng sè d-¬ng c vµ no sao cho T(n) c f(n), víi mäi n no.
NÕu mét thuËt to¸n cã thêi gian thùc hiÖn T(n) = 0(f(n)), chóng ta sÏ nãi
r»ng thuËt to¸n cã thêi gian thùc hiÖn cÊp f(n). Tõ ®Þnh nghÜa ký hiÖu « lín, ta
cã thÓ xem r»ng hµm f(n) lµ cËn trªn cña T(n).
VÝ dô : Gi¶ sö T(n) = 3n2 + 5n + 4. Ta cã
3n2 + 5n + 4 <= 3n2 + 5n2 + 4n2 = 12n2, víi mäi n 1.
VËy T(n) = 0(n2). Trong tr-êng hîp nµy ta nãi thuËt to¸n cã thêi gian
thùc hiÖn cÊp n2, hoÆc gän h¬n, thuËt to¸n cã thêi gian thùc hiÖn b×nh ph-¬ng.
DÔ dµng thÊy r»ng, nÕu T(n) = 0(f(n)) vµ f(n) = 0(f1(n)) , th×
T(n)=0(f1(n)). ThËt vËy, v× T(n) lµ « lín cña f(n) vµ f(n) lµ « lín cña f1(n), do
®ã tån t¹i c¸c h»ng sè co, no, c1, n1 sao cho T(n) co f(n) víi mäi n no vµ f(n)
c1f1(n) víi mäi n n1. Tõ ®ã ta cã T(n) coc1f1(n) víi mäi n max(no,n1).
Khi biÓu diÔn cÊp cña thêi gian thùc hiÖn thuËt to¸n bëi hµm f(n), chóng
ta sÏ chän f(n) lµ hµm sè nhá nhÊt, ®¬n gi¶n nhÊt cã thÓ ®-îc sao cho T(n) =
0(f(n)). Th«ng th-êng f(n) lµ c¸c hµm sè sau ®©y : f(n) = 1 ; f(n)=logn; f(n)=n
; f(n) = nlogn ; f(n) = n2, n3, ... vµ f(n) = 2n.
NÕu T(n) = 0(1) ®iÒu nµy cã nghÜa lµ thêi gian thùc hiÖn bÞ chÆn trªn bëi
mét h»ng sè nµo ®ã, trong tr-êng hîp nµy ta nãi thuËt to¸n cã thêi gian thùc
hiÖn h»ng.
NÕu T(n) =0(n), tøc lµ b¾t ®Çu tõ mét no nµo ®ã trë ®i ta cã T(n)<=cn víi
mét h»ng sè c nµo ®ã, th× ta nãi thuËt to¸n cã thêi gian thùc hiÖn tuyÕn tÝnh.
B¶ng sau ®©y cho ta c¸c cÊp thêi gian thùc hiÖn thuËt to¸n ®-îc sö dông
réng r·i nhÊt vµ tªn gäi th«ng th-êng cña chóng.
Ký hiÖu « lín
Tªn gäi th«ng th-êng
0(1)
0 (logn)
0(n)
h»ng
logarit
tuyÕn tÝnh
nlogn
b×nh ph-¬ng
lËp ph-¬ng
mò
0(n logn)
0(n2)
0(n3)
0(2n)
Danh s¸ch trªn s¾p xÕp theo thø tù t¨ng dÇn cña cÊp thêi gian thùc hiÖn.
§Ó thÊy râ sù kh¸c nhau cña c¸c cÊp thêi gian thùc hiÖn thuËt to¸n, ta
xÐt vÝ dô sau. Gi¶ sö ®èi víi mét vÊn ®Ò nµo ®ã, ta cã hai thuËt to¸n gi¶i A vµ
13
B. ThuËt to¸n A cã thêi gian thùc hiÖn TA(n) = 0(n2), cßn thuËt to¸n B cã thêi
gian thùc hiÖn TB(n) = 0(nlogn). Víi n = 1024, thuËt to¸n A ®ßi hái kho¶ng
1048.576 phÐp to¸n s¬ cÊp, cßn thuËt to¸n B ®ßi hái kho¶ng 10.240 phÐp to¸n
s¬ cÊp. NÕu cÇn mét micr«-gi©y cho mét phÐp to¸n s¬ cÊp th× thuËt to¸n A cÇn
kho¶ng 1,05 gi©y, trong khi thuËt to¸n B chØ cÇn kho¶ng 0,01 gi©y. NÕu n =
1024 x 2, th× thuËt to¸n A ®ßi hái kho¶ng 4,2 gi©y, trong khi thuËt to¸n B chØ
®ßi hái kho¶ng 0,02 gi©y. Víi n cµng lín th× thêi gian thùc hiÖn thuËt to¸n B
cµng Ýt h¬n so víi thêi gian thùc hiÖn thuËt to¸n A. V× vËy, nÕu mét vÊn ®Ò nµo
®ã ®· cã mét thuËt to¸n gi¶i víi thêi gian thùc hiÖn cÊp n2, b¹n t×m ra thuËt
to¸n míi víi thêi gian thùc hiÖn cÊp nlogn, th× ®ã lµ mét kÕt qu¶ rÊt cã ý
nghÜa.
Nh÷ng thuËt to¸n cã thêi gian thùc hiÖn cÊp nk, víi k lµ sè nguyªn nµo
®ã 1, ®-îc gäi lµ c¸c thuËt to¸n cã thêi gian thùc hiÖn ®a thøc.
1.2.5 C¸c qui t¾c ®Ó ®¸nh gi¸ thêi gian thùc hiÖn thuËt to¸n.
Sau ®©y chóng ta ®-a ra mét qui t¾c cÇn thiÕt vÒ « lín ®Ó ®¸nh gi¸ thêi
gian thùc hiÖn mét thuËt to¸n.
Qui t¾c tæng : NÕu T1(n) = 0(f1(n) vµ T2(n) = 0(f2(n) th×
T1(n) + T2(n) = 0(max(f1(n), f2(n))).
ThËt vËy, v× T1(n), T2(n) lµ « lín cña f1(n), f2(n) t-¬ng øng do ®ã tån t¹i
h»ng sè c1, c2, n1, n2 sao cho T1(n) c1f1 (n) víi mäi n n1 vµ T2(n) c2f2(n)
víi mäi n n2.. §Æt no = max(n1, n2). Khi ®ã víi mäi n no, ta cã T1(n) +
T2(n) (c1 + c2) max (f1(n), f2(n)).
Qui t¾c nµy th-êng ®-îc ¸p dông nh- sau. Gi¶ sö thuËt to¸n cña ta ®-îc
ph©n thµnh ba phÇn tuÇn tù. PhÇn mét cã thêi gian thùc hiÖn T1(n) ®-îc ®¸nh
gi¸ lµ 0(1), phÇn hai cã thêi gian T2(n) lµ 0(n2), phÇn ba cã thêi gian T3(n) lµ
0(n). Khi ®ã thêi gian thùc hiÖn thuËt to¸n T(n) = T1(n) + T2(n) + T3(n) sÏ lµ
0(n2), v× n2 = max (1,n2,n).
Trong s¸ch b¸o quèc tÕ c¸c thuËt to¸n th-êng ®-îc tr×nh bÇy d-íi d¹ng
c¸c thñ tôc hoÆc hµm trong ng«n ng÷ tùa Pascal. §Ó ®¸nh gi¸ thêi gian thùc
hiÖn thuËt to¸n, ta cÊn biÕt c¸ch ®¸nh gi¸ thêi gian thùc hiÖn c¸c c©u lÖnh cña
Pascal. Tr-íc hÕt, chóng ta h·y x¸c ®Þnh c¸c c©u lÖnh trong Pascal. C¸c c©u
lÖnh trong Pascal ®-îc ®Þnh nghÜa ®Ö qui nh- sau :
1. C¸c phÐp g¸n, ®äc, viÕt, goto lµ c©u lÖnh. C¸c lÖnh nµy ®-îc gäi lµ
c¸c lÖnh ®¬n.
2. NÕu S1, S2,..., Sn lµ c©u lÖnh th×
begin S1, S2, ..., Sn end
lµ c©u lÖnh. LÖnh nµy ®-îc gäi lµ lªnh hîp thµnh (hoÆc khèi).
3. NÕu S1 vµ S2 lµ c¸c c©u lÖnh vµ E lµ biÓu thøc logic th×
14
if E then S1 else S2
lµ c©u lÖnh, vµ
if E then S1
lµ c©u lÖnh. C¸c lÖnh nµy ®-îc gäi lµ lÖnh if.
4. NÕu S1, S2, ..., Sn+1 lµ c¸c c©u lÖnh, E lµ biÓu thøc cã kiÓu thø tù ®Õm ®-îc,
vµ v1, v2,...vn lµ c¸c gi¸ trÞ cïng kiÓu víi E th×
case E
of
v1 : S1 ;
v2 : S2 ;
. . . . . . .
vn : Sn ;
[else Sn+1]
end
lµ c©u lÖnh. LÖnh nµy ®-îc gäi lµ lÖnh case
5. NÕu S lµ c©u lÖnh vµ E lµ biÓu thøc logie th×
while E do S
lµ c©u lÖnh. LÖnh nµy ®-îc gäi lµ lÖnh while.
6. NÕu S1, S2, ..., Sn lµ c¸c c©u lÖnh, vµ E lµ biÓu thøc logic th×
repeat S1, S2, ..., Sn until E
lµ c©u lÖnh. LÖnh nµy ®-îc gäi lµ lÖnh repeat.
7. Víi S lµ c©u lÖnh, E1 vµ E2 lµ c¸c biÓu cïng mét kiÓu thø tù ®Õm ®-îc, th×
for i : = E1 to E2 do S
lµ c©u lÖnh, vµ
for i : = E2 downto E1 do S
lµ c©u lÖnh. C¸c c©u lÖnh nµy ®-îc gäi lµ lÖnh for.
Nhê ®Þnh nghÜa ®Ö qui cña c¸c lÖnh, chóng ta cã thÓ ph©n tÝch mét
ch-¬ng tr×nh xuÊt ph¸t tõ c¸c lÖnh ®¬n, råi tõng b-íc ®¸nh gi¸ c¸c lÖnh phøc
t¹p h¬n, cuèi cïng ®¸nh gi¸ ®-îc thêi gian thùc hiÖn ch-¬ng tr×nh.
Gi¶ sö r»ng, c¸c lÖnh g¸n kh«ng chøa c¸c lêi gäi hµm. Khi ®ã ®Ó ®¸nh
gi¸ thêi gian thùc hiÖn mét ch-¬ng tr×nh, ta cã thÓ ¸p dông ph-¬ng ph¸p ®Ö qui
sau ®©y :
1. Thêi gian thùc hiÖn c¸c lÖnh ®¬n : g¸n, ®äc, viÕt, goto lµ 0(1).
2. LÖnh hîp thµnh. Thêi gian thùc hiÖn lÖnh hîp thµnh ®-îc x¸c ®Þnh
bëi luËt tæng.
15
3. LÖnh if. Gi¶ sö thêi gian thùc hiÖn c¸c lÖnh S1, S2 lµ 0(f1(n)) vµ
0(f2(n)) t-¬ng øng. Khi ®ã thêi gian thùc hiÖn lÖnh if lµ 0(max(f1(n), f2(n))).
4. LÖnh case. §-îc ®¸nh gi¸ nh- lÖnh if.
5. LÖnh while. Gi¶ sö thêi gian thùc hiÖn lÖnh S (th©n cña lÖnh while) lµ
0(f(n)). Gi¶ sö g(n) lµ sè tèi ®a c¸c lÇn thùc hiÖn lÖnh S, khi thùc hiÖn lÖnh
while. Khi ®ã thêi gian thùc hiÖn lÖnh while lµ 0(f(n)g(n).
6. LÖnh repeat. Gi¶ sö thêi gian thùc hiÖn khèi begin S1, S2, ... Sn end lµ
0(f(n)). Gi¶ sö g(n) lµ sè tèi ®a c¸c lÇn lÆp. Khi ®ã thêi gian thùc hiÖn lÖnh
repeat lµ 0(f(n)g(n)).
7. LÖnh for. §-îc ®¸nh gi¸ t-¬ng tù lÖnh while vµ repeat.
NÕu lÖnh g¸n cã chøa c¸c lêi gäi hµm, th× thêi gian thùc hiÖn nã kh«ng
thÓ xem lµ 0(1) ®-îc, v× khi ®ã thêi gian thùc hiÖn lÖnh g¸n cßn phô thuéc vµo
thêi gian thùc hiÖn c¸c hµm cã trong lÖnh g¸n. ViÖc ®¸nh gi¸ thêi gian thùc
hiÖn c¸c thñ tôc (hoÆc hµm) kh«ng ®Ö qui ®-îc tiÕn hµnh b»ng c¸ch ¸p dông
c¸c qui t¾c trªn. ViÖc ®¸nh gi¸ thêi gian thùc hiÖn c¸c thñ tôc (hoÆc hµm) ®Ö
quy sÏ khã kh¨n h¬n nhiÒu.
§¸nh gi¸ thñ tôc (hoÆc hµm) ®Ö qui.
Tr-íc hÕt chóng ta xÐt mét vÝ dô cô thÓ. Ta sÏ ®¸nh gi¸ thêi gian thùc
hiÖn cña hµm ®Ö qui sau (hµm nµy tÝnh n!).
function
begin
fact(n : integer) : integer ;
if n <=1 then fact : =1
else fact : = n * fac(n-1)
end ;
Trong hµm nµy cì cña d÷ liÖu vµo lµ n. Gi¶ sö thêi gian thùc hiÖn hµm
lµ T(n). Víi n=1, chØ cÇn thùc hiÖn lÖnh g¸n fact : = 1, do ®ã T(1) = 0(1). Víi
n > 1, cÇn thùc hiÖn lÖnh g¸n fact : = n*fact(n-1). Do ®ã, thêi gian T(n) lµ 0(1)
(®Ó thùc hiÖn phÐp nh©n vµ phÐp g¸n) céng víi T(n-1) (®Ó thùc hiÖn lêi gäi ®Ö
qui fact(n-1). Tãm l¹i, ta cã quan hÖ ®Ö qui sau :
T(1) = 0(1) ;
T(n) = 0(1) + T(n-1).
Thay c¸c 0(1) bëi c¸c h»ng nµo ®ã, ta nhËn ®-îc quan hÖ ®Ö qui sau
T(1) = C1
T(n) = C2 + T(n-1)
§Ó gi¶i ph-¬ng tr×nh ®Ö qui, t×m T(n), chóng ta ¸p dông ph-¬ng ph¸p
thÕ lÆp. Ta cã ph-¬ng tr×nh ®Ö qui
16
T(m) = C2 + T(m-1), víi m > 1
Thay m lÇn l-ît bëi 2,3,..., n - 1, n, ta nhËn ®-îc c¸c quan hÖ sau.
T(2) = C2 + T(1)
T(3) = C2 + T(2)
...............................
T(n-1) = C2 + T(n-2)
T(n) = C2 + T(n-1)
B»ng c¸c phÐp thÕ liªn tiÕp, ta nhËn ®-îc
T(n) = (n-1)C2 + T(1)
hay T(n) = (n-1) C2 + C1, trong ®ã C1 vµ C2 lµ c¸c h»ng nµo ®ã. Do ®ã,
T(n)=0(n).
Tõ vÝ dô trªn, ta suy ra ph-¬ng ph¸p tæng qu¸t sau ®©y ®Ó ®¸nh gi¸ thêi
gian thùc hiÖn thñ tôc (hµm) ®Ö qui. §Ó ®¬n gi¶n, ta gi¶ thiÕt r»ng c¸c thñ tôc
(hµm) lµ ®Ö qui trùc tiÕp. §iÒu ®ã cã nghÜa lµ c¸c thñ tôc (hµm) chØ chøa c¸c
lêi gäi ®Ö qui ®Õn chÝnh nã (kh«ng qua mét thñ tôc (hµm) kh¸c nµo c¶). Gi¶ sö
thêi gian thùc hiÖn thñ tôc lµ T(n), víi n lµ cì d÷ liÖu vµo. Khi ®ã thêi gian
thùc hiÖn c¸c lêi gäi ®Ö qui thñ tôc sÏ lµ T(m), víi m < n. §¸nh gi¸ thêi gian
T(n0), víi n0 lµ cì d÷ liÖu vµo nhá nhÊt cã thÓ ®-îc (trong vÝ dô trªn, ®ã lµ
T(1). Sau ®ã ®¸nh gi¸ th©n cña thñ tôc theo c¸c qui t¾c 1-7, ta sÏ nhËn ®-îc
quan hÖ ®Ö qui sau ®©y.
T(n) = F(T(m1), T(m2), ..., T(mk))
trong ®ã m1, m2, ...,mk < n. Gi¶i ph-¬ng tr×nh ®Ö qui nµy, ta sÏ nhËn ®-îc sù
®¸nh gi¸ cña T(n). Tuy nhiªn, cÇn biÕt r»ng, viÖc gi¶i ph-¬ng tr×nh ®Ö qui,
trong nhiÒu tr-êng hîp, lµ rÊt khã kh¨n, kh«ng ®¬n gi¶n nh- trong vÝ dô ®·
tr×nh bµy.
1.2.6. Ph©n tÝch mét sè thuËt to¸n.
Sau ®©y chóng ta sÏ ¸p dông c¸c ph-¬ng ph¸p ®· tr×nh bµy ®Ó ph©n tÝch
®é phøc t¹p cña mét sè thuËt to¸n.
VÝ dô 1 : Ph©n tÝch thuËt to¸n Euclid. Chóng ta biÓu diÔn thuËt to¸n
Euclid bëi h¹m sau.
function
Euclid (m, n : integer) : integer ;
var r : integer ;
begin
(1)
(2)
r : = m mod n ;
while r < > 0 do
begin
17
(3)
(4)
(5)
m : = n ;
n : = r ;
r : = m mod n ;
end ;
Euclid : = n ;
(6)
end ;
Thêi gian thùc hiÖn thuËt to¸n phô thuéc vµo sè nhá nhÊt trong hai sè m
vµ n. Gi¶ sö n n > 0, do ®ã cì cña d÷ liÖu vµo lµ n. C¸c lÖnh (1) vµ (6) cã thêi
gian thùc hiÖn lµ 0(1). V× vËy thêi gian thùc hiÖn thuËt to¸n lµ thêi gian thùc
hiÖn lÖnh while ta ®¸nh gi¸ thêi gian thùc hiÖn lÖnh while (2). Th©n cña lÖnh
nµy, lµ khèi gåm ba lÖnh (3), (4) vµ (5). Mçi lÖnh cã thêi gian thùc hiÖn lµ
0(1), do ®ã khèi cã thêi gian thùc hiÖn lµ 0(1). Cßn ph¶i ®¸nh gi¸ sè lín nhÊt
c¸c lÇn thùc hiÖn lÆp khèi.
Ta cã :
m = n.q1 + r1 , 0 r1 < n
n = r1q2 + r2 , 0 r2 < r1
NÕu r1 n/2 th× r2 < r1 n/2, do ®ã r2 < n/2. NÕu r1 > n/2 th× q2 = 1, tøc lµ n =
r1 + r2 , do ®ã r2 < n/2. Tãm l¹i, ta lu«n cã r2 < n/2
Nh- vËy, cø hai lÇn thùc hiÖn khèi th× phÇn d- r gi¶m ®i mét nöa cña n.
Gäi k lµ sè nguyªn lín nhÊt sao cho 2k n. Sè lÇn lÆp khèi tèi ®a lµ
2k+12log2n+1. Do ®ã thêi gian thùc hiÖn lÖnh while lµ 0(log2n). §ã còng lµ
thêi gian thùc hiÖn thuËt to¸n.
VÝ dô 2. D·y sè Fibonacci ®-îc x¸c ®Þnh mét c¸ch ®Ö qui nh- sau :
fo = 0 ;
f1 = 1 ;
fn = fn-1 + fn-2 víi n 2
C¸c thµnh phÇn ®Çu tiªn cña d·y lµ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... D·y
nµy cã nhiÒu ¸p dông trong to¸n häc, tin häc vµ lý thuyÕt trß ch¬i.
ThuËt to¸n ®Ö qui :
function Fibo1 (n : integer) : integer ;
begin
if n <= 2 then Fibo1 : = n
else Fibo1 : = Fibo1(n-1) + Fibo1(n-2)
end ;
Cã thÓ ®¸nh gi¸ ®-îc hµm nµy cã thêi gian thùc hiÖn lµ 0(n), víi =(1+
)/2. Tøc lµ, thuËt to¸n Fibo1 cã thêi gian thùc hiÖn mò, nã kh«ng cã ý nghÜa
5
18
thùc tiÔn víi n l¬n. Sau ®©y lµ mét thuËt to¸n kh¸c, cã thêi gian thùc hiÖn chØ
lµ 0(n).
funciton Fibo2 (n: integer) : integer ;
var i, j, k : integer
begin
(1)
(2)
(3)
i : = 1 ;
j : = 0 ;
for k : = 1 to n do
begin
j : = i + j ;
i : = j - i ;
end ;
(4)
Fibo2 : = j ;
end ;
Ta ph©n tÝch hµm Fibo2. C¸c lÖnh g¸n (1) , (2) vµ (4) cã thêi gian thùc
hiÖn 0(1). Th©n cña lÖnh for(3) cã thêi gian thùc hiÖn lµ 0(1), sè lÇn lÆp lµ n.
Do ®ã lÖnh for(3) cã thêi gian thùc hiÖn lµ 0(n). KÕt hîp l¹i, ta cã thêi gian
thùc hiÖn hµm Fibo2 lµ 0(n).
Víi n = 50, thuËt to¸n Fibo1 cÇn kho¶ng 20 ngµy trªn m¸y tÝnh lín,
trong khi ®ã thuËt to¸n Fibo2 chØ cÇn kho¶ng 1 micr« gi©y. Víi n = 100, thêi
gian ch¹y cña thuËt to¸n Fibo1 lµ 109 n¨m ! cßn thuËt to¸n Fibo2 chØ cÇn
kho¶ng 1,5 micro gi©y. ThuËt to¸n Fibo2 ch-a ph¶i lµ thuËt to¸n hiÖu qu¶ nhÊt.
B¹n thö t×m mét thuËt to¸n hiÖu qu¶ h¬n.
19
15 trang
20360
Free
Bạn đang xem tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Thuật toán và phân tích thuật toán", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_1_thuat_toan.doc
