Phân tích và thiết kế giải thuật - Chương 1: Tổng quan chi tiết

Môn h c:Ph ân tích và thi t k gi ithu t

Ch

ng 1

CÁCKH ÁINI M C N B N

N i dung

quy

1. Ki u d li u tr u t 2. 3. Phân tíchgi

i thu t

1.Ki u d li utr u t

ng

t thi công (implementation details). • Mô t m t c utr úc d li utheo c ác tác v (operations) làm vi ctr ên c utr úc d li uth ì ti n l i h n là di n t nó theo nh ng chiti

• Chúngta n ên táchnh ngkh áini m v c utr úc d li ura

kh i nh ngchiti tthi c ông.

c nhngh atheo c áchnh • Khi m t c utr úc d li u

có m t ki u d li utr u t ng (abstractdata type )

v yta s hay ADT.

ng là m t mô hìnhto án

c nhngh atr ên

M tki u d li utr u t h c i cùng v inh ng tác v mô hình này.

Vàith í d v Ki u d li utr u t

ng

• M t t p (set) là m t t p h p g mzero hay nhi uph n t .

cph épxu thi nnhi u h n m t

c ký hi u là {a1,

trong m t t p là

M tph n t không l ntrong t p. M t t p g m n ph n t a2,…,an},nh ng v trí c a m tph n t khôngquantr ng.

• M t a t p (multiset) là m t t p mà trong ó m t ph n t

c phép xu t hi nnhi u h n m t l n.Th í d ,{5,7,5,2} l à

m t a t p. M t a t p có th có nh ng tác v sau:

a t p có r ng)

initialize (kh i t o) insert (thêm vào) is_empty (th delete (xoá) findmin (tìm ph n t bé nh t)

Vàith í d v Ki u d li utr u t

ng(tt)

• M t chu i (sequence) là m t t p h p có th t c azero hay

c ký hi u là . V trí c a

trong m tchu i là có ý nghiã. M t chu i có th

nhi uph n t ; m tph n t có nh ng tác v sau:

initialize (kh i t o) length (chi u dài) head (ph n t tail (ph n uôi) concatenate (ghép k hai chu i)

Gi i m t bàito án b ngADT

th y ích l i c aki u d li utr u t ng,th xét bàito án

sau: Cho m t m ng(array) g m n s , A[1..n], hãy xác nh k ph n l nnh ttrong m ng, v i k n.Th í d , n uA l à {5,3, 1, 9, t 6}, và k = 3, thì k t qu là {5, 9, 6}.

xây d ng m t gi ithu t gi i bàito ántr ên.

ng a t p (multiset) v i các

Không d Tath dùngki u d li utr u t tác v :

initialize(M), insert(x, M), deleteMin(M), findMin(M)

ithu tnh

Suy ngh trên a t pM,ta c ó th vi t m tgi sau:

Initialize(M); for i:= 1 to k do Insert(A[i],M); for i:= k+ 1 to n do

then

if A[i]>FindMin(M) begin

DeleteMin(M);Insert(A[i],M)

end;

ng ã làm Trongth í d trên,tath yki u d li utr u t

ngi n hóavi c xây d ng gi ithu t b ng cáchkh ông b n

tâm nnh ng chiti tthi c ônghayhi nth c hóa.

Thi công m tki u d li utr u t

ng

c g i là thi côngki u d li utr u t hi nth c hóa ng.Trong

thi công này, ph n d li utr u t c hi nth c hóa ng

Abstract Data

Data Structure

Operations

Concrete operations

Quá trình dùng m t c utr úc d li u c th m tADT s b ng m t c utr úc d li u c th và ph n các tác v tr u t c hi nth c hóa b ng các tác v c th h n. ng

Thi công m tki u d li utr u t

ng(tt.)

Có th dùng m ng (array) hay danh sáchli ên k t (linkedlist)

thi công t p h p (set).

Có th dùng m ng (array) hay danh sáchli ên k t (linkedlist)

thi công chu i.

c,ta

ng a t p nh trongth í d tr uti ên (priority queue) thi

thi

V iki u d li utr u t i có có th dùng hàng công. Và sau ó ta có th dùng c utr úc d li u heap uti ên. công hàng i có

2. quy

H th ctruy h i

Thí d 1: Hàm tínhgiaith a N! = N.(N-1)!

v i N 1 0!= 1

Nh ng nhngh a hàm quy mà ch anh ng i s nguyên

c g i là nh ng h th ctruy h i (recurrencerelation ).

function factorial(N:integer):integer; begin

if N= 0 then factorial:= 1 else factorial:= N*factorial(N-1);

end;

H th ctruy h i

Thí d 2: S Fibonacci

H th ctruy h i: FN = FN-1 + FN-2

for N 2 F0 = F1 = 1 1, 1, 2, 3, 5, 8,13, 21, …

function fibonacci(N: integer): integer; begin

if N<= 1 then fibonacci:= 1 else fibonacci:=fibonacci(N-1) +

fibonacci(N-2);

end;

M t cáchkh ác:Ta c ó th dùng m t m ng ch anh ngtr s

ctrongkhi t ính hàmfibonacci.Ta c ó m t gi ithu t

itr không quy.

procedure fibonacci; const max= 25; var i:integer; F: array[0..max] of integer; begin

F[0]:=1; F[1]:=1; for i:= 2 to max do

F[i]:=F[i-1]+ F[i-2]

end;

Chi n l

cChia-

-tr

gi i m t v n i phó v i

con (subproblem) có quan h ch tch v i nhau. quy: ithu thay c ó c utr úc Nhi ugi gi ithu t g i chính nó m thaynhi u l n nh ng v n

Nh ng gi ithu t nh v ytu ântheo c áchti p c n chia- -tr

(divide andconquer) :

Gi ithu tph ân rã v n

thànhnh ng v n con này và k t h pnh ng l igi con, gi i i c anh ng

conth ành l igi icho v n nguyênth y. nh ng v n v n

Chi n l c này bao g m 3 b csau ây m i c p quy:

phân chia (divide) tr (conquer) k t h p (combine)

c: có m t nét v ch t i

Thí d : Xétvi c v chnh ng v ch cáchnhau1 inchtr ên 1 câyth i n ½ inch, nét v chng n h n nh ng o n ¼ inch, nét v ch ng n h n n a nh ng

o n1/8inch, v.v...

th t c

procedure rule(l,r,h: integer); /*l:left positionoftheruler;r:right position

oftheruler*/

Gi s mark(x,h) v m t n v t i v v ch h trí x.

var m: integer; begin

if h> 0 then begin

div 2;mark(m, h);

m:=(1+r) rule(l,m, h-1); rule(m,r , h-1)

end;

Kh

quy

:Gi ithu tkh ông quy th ng làm vi c h u hi u

V n và d ki mso át h n1 gi ithu t quy.

Làm cách nào i m tch quy

chuy n ngtr ìnhkh ông- -quy t ngtr ình ng ng. thành m tch

quyP, m i l n có m t l nh g i quy

ngph áp: Cho m tth t c nP, gi á tr hi n hành c a cáctham s và cácbi n c c b

c c t vào các ng n x p (stack) x lý sau.

quy v P,gi á tr c a các ckh ôiph c l i t cácng n

M i l n có m t s quay v tham s và cácbi n c c b s x p.

Kh

quy(tt.)

i phó v i ach kh h i (return address) cth c

th t cPch a m t l nh g i quy t i b c l nh

Vi c hi nnh sau: Gi s a ch kh h i K+1 s c dùng quay v m cth cthith c l u t i m tng n x p và s t cP hi n hành.

procedure hanoi(n, beg,aux, end); begin

if n= 1 then writeln(beg, end) else begin

hanoi(n-1, beg, end, aux) ; writeln(beg, end); hanoi(n-1, aux, beg, end);

Thí d :Th t c hanoi là m tth i bài quygi t c toánTh áp Hà N i

end

end;

3:writeln(beg,end);

top:= top+1; /*second

recursivecall*/

procedure hanoi(n,beg,aux,end: integer); /StacksSTN,STBEG,STAUX, STEND,andSTADDcorrespond, respectively,tovariablesN,BEG,AUX, ENDandADD/ label 1,3,5; var t: integer; begin

top:=0; /*preparation forstacks*/

STN[top]:=n; STBEG[top]:=beg; STAUX[top]:aux; STEND[top]:=end; STADD[top]:=5; /*savingreturnaddress*/ n:=n-1; t:=beg;beg:=aux; aux:= t; goto 1;

1: if n= 1 then

5. /* translationofreturnpoint*/

if top<> 0 then begin

begin writeln(beg,end); goto 5 end; top:= top+1; /* firstrecursivecall*/ STN[top]:=n;STBEG[top]:=beg; STAUX [top]:=aux; STEND [top]:=end; STADD [top]:=3;

n:=STN[top]; beg:=STBEG [top]; aux:=STAUX [top]; end:=STEND [top]; add:=STADD [top]; top:= top – 1; goto add

end

/savingreturnaddress/ n:=n-1; t:=aux;aux:=end; end:= t; goto 1;

end;

S duy t cây

quy

ngi nnh t duy t các núttrong m t câynh

Cách phântheo th t n i là nh m tth t c

quynh sau: //duy tth t n i(Inordertraversal)

type

link = node; node = record

info: …….; l,r:link

end; procedure traverse(t: link); begin

if t<> z then /*zisdummy node */ begin

traverse(t.l); visit(t); traverse(t.r)

end end;

Th t cduy t cây ti nth

t

(Pre-order)

procedure traverse(t:link) begin

if t<> z then begin

visit(t); traverse(t.1);traverse(t .r)

end

end;

ckhikh Tr

quyth hai d dàng vì không có mã ch quyth t c này,ta c ó th lo i b l nh g i ngtr ình isau

quyth hai có th cchuy nth ành m t l nh

nó. L nh g i goto nh sau:

Kh

quy uôi

procedure traverse(t:link); label 0,1; begin 0: if t= z thengoto 1;

visit(t); traverse(t. l); t:= t .r; goto 0;

1: end;

c g i là kh quy uôi (tail-recursion

K thu t này removal).

áp d ng ph ngph áp t ngqu át,ta c ó th kh l nh

Bâygi g i quy còn l itrongch ngtr ình.

procedure traverse(t: link); label 0, 1, 2, 3; begin 0:if t= z then goto 1;

visit(t); push(t); t:= t .l; goto 0;

3:t:= t .r; goto 0; 1: if stack_empty thengoto 2;

t:= pop; goto 3;

2: end;

ach kh h i, 3, mà là c nh, nên

Chú ý: Doch có m t takh ôngph i nh i nó vàostack.

Ta có th lo i b vàiph át bi u goto b ng cách dùng vòng l p while nh sau.

procedure traverse(t: link); label 0,2; begin 0: while t<> z do

begin

visit(t); push(t.r);t:= t .1;

end; if stack_empty thengoto 2; t:=pop; goto 0;

2: end;

M t l n n ata c ó th lo i b hai l nh goto còn l i b ng cách dùng vòng l p repeat .

procedure traverse(t: link); begin

push(t); repeat

t:= pop; while t<> z do begin

visit(t); push(t.r);t:= t .l;

end;

until stack_empty;

end;

c

ngi n hóa

Hai vòng l p l ngnhau c ó th nh sau:

procedure traverse(t: link); begin

push(t); repeat

t:= pop; if t<> z then begin

visit(t); push(t.r); push(t.1);

end;

until stack_empty;

end;

tránh anh ng câycon r ng vàostack,ta c ó th s a

ch ngtr ìnhtr ênth ành:

procedure traverse(t: link); begin

push(t); repeat

t:= pop; visit(t); if t.r <> z then push(t.r); if t.l<> z then push(t.l);

until stack_empty;

end;

ngtr ìnhkh ông quy hoàn ch nh duy t cây

ây là ch nh phân.

Kh hàm quy

quyP l à m t hàm,ta c n b sung vào qui t c

N uth t c chuy n i t ng quát m t s i msau ây:

1. T i câu l nh có g n a ch

then

Thí d : Hàm tính t h p function comb(m,n: int):int If (n=morm= 0) return 1

kh h i,ta ph i khôi ph ctr stack; n u c nth ì hàm t thêm l nh s d ngtr hàm này.

else begin

a 2. T i câu l nh return, c n

a:= comb(n-1,m); b:= comb(n-1, m-1); return (a+b);

end

vào phátbi u nhtr bi u th c ili nsau t khóa return và c ttr hàm tr v này vào stack.

n= n-1;m=m-1;

goto L0;

int comb(int n, int m) {

L2: a=stackF[topF], topF = topF –1; –1;

b=stackF[topF],topF=topF c =a+ b; L3: if (top>0)

{

int top, topF; int stackN[100]; int stackM[100]; int stackADD[100]; int stackF[100]; int a, b, add, c; top= topF = 0; //stack initialize

L0: if (m==0|| n ==m)

{ c = 1, goto L3;} else { // 1st recursive call top= top+1 ; stackN[top]= n; stackM[top]=m; stackADD[top]=1; n= n-1; goto L0; L1:// 2nd recursive call

n=stackN[top]; m=stackM[top]; add=stackADD[top]; top= top –1; // push theresult topF= topF+ 1; stackF[top]= c; if (add== 1) goto L1; else if (add== 2) goto L2; } return c;

}

top= top+1 ;stackN[top]= n; stackM[top]=m; stackADD[top]=2;

ph c t pgi

ithu t

3. Phân tích

ng có nhi u gi ithu tkh ác

gi i m t bàito án.

ch ngi ithu t t tnh t gi i m t bài

so sánh cácgi ithu t cùnggi i c m t

V i ph n l n các bàito án,th nhau Làm cách nào toán? Làm cách nào bàito án?

ph c t p c a m tgi ithu t: d oán các tài

Phân tích nguyên mà gi ithu t ó c n.

Tàinguy ên: Ch b nh

Th igian t ínhto án

Th i gian tínhto án là tàinguy ênquantr ngnh t.

Hai cáchph ân tích

Th igian t ínhto án c a m tgi

ng là

m t hàm c a kíchth

ithu tth c d li unh p.

Chúngtaquan t âm n:

 Tr

ng h ptrung b ình (average case):th igian ithu t c n i v i m t “d ng” (typicalinputdata).

tínhto án mà m tgi li unh âpth ôngth

 Tr

ng h p x unh t (worstcase ):th igian t ính i v i m t “d li u

ithu t c n

toán mà m tgi nhâp x unh t”

Khungth c c a s phân tích

B c1: ctr ng hóa d li unh p và quy t nhki u

ng,ta t ptrung v àovi c

i v i m t d li u

phân tíchth ích h p. Thôngth -ch ngminh r ngth igian t ínhto ánlu ônnh h n m t “c n trên” (upper bound),hay - d nxu trath igianch ytrung b ình nh png unhi ên.

B c2:nh n d ng thao táctr u t ng (abstract operation)

mà gi ithu t d a vào ó làmvi c.

Thí d :thao t ácso s ánhtronggi

ngth ithu t s pth t . ng tùythu c vào m t vài i

T ng s thao táctr u t l ng.

B c3:th chi nph ân tíchto án h c tìmra c ácgi á tr

trung bình và giá tr x unh t c a các i l ng quantr ng.

Haitr

ng h pph ân tích

• Th

ngth ì khôngkh ó

gian tínhto án c a m tgi

tìmra c ntr ên c ath i i thu t.

ng h ptrung b ìnhth

ng òi

• Nh ngph ân tíchtr

h i m t s phân tíchto án h c c u k , ph c t p.

• V nguyên t c, m tgi

i thu t có th

n m t m c

chính xác r tchili.Nh c l ngch tính

cph ân tích ngtrong ng

th c t ,ch úngtath (estimating) mà thôi

• Tóm l i,ch úngta t ìmki m m t

c l

ngth ô v th i

i thu t(nh m m c ích

gian tínhto án c a m tgi phân l p

ph c t p).

Phân l p

ph c t p

ithu tth ng có m tth ông s chính, N, s

H u h t cácgi m u d li unh p mà c x lý.

c s pth t ho c tìmki m.

Thí d : Kíchth S nút c a m t c c a m ng(array) th .

Gi ithu t có th có th igian t ínhto án t l v i

cth cthi m t vài l n.

1. N u tác v chính  th igian t ínhto án là h ng s .

log2N lgN

t ng c aN. 2.lgN(logarithmic) Gi ithu t t ngch m h n s

3. N (linear)

4.NlgN

5. N2 (quadratic) khi gi ithu t là vòng l p l ng hai

6. N3 (cubic) khi gi ithu t là vòng l p l ng ba

7. 2N m t s gi ithu t có th igianch ylu th a.

ithu tkh ác có th có th igianch y ,(lgN) 2 … M t vàigi N3/2, N1/2

ph c t p tínhto án

ng h p x unh t. Khi xác nh s ph

i v i kíchth c d li u

Chúngta t ptrung v àoph ân tíchtr phân tích, b qua nh ngth a s h ng s thu c hàm c ath igian t ínhto án nh p.

ngph áp

Thí d :Th igian t ínhto án c a s pth t b ngph tr n (mergesort ) là t l v i NlgN.

Khái ni m “t l v i” (proportionalto )

làmch ính xáckh áini m này là

Công c toán h c ký hi u – O (O-notation).

nhngh a: M t hàmg(N) c g i là O(f(N)) n u t n t ihai

h ng s c0 và N0 saochog(N) nh h n c0f(N) v i m i N > N0.

Ký hi u O

c l p i v i phátbi u c ntr ên v th i c tính d li u nh p và

Ký hi u O là m t cách h u ích gian tínhto án mà chiti t hi nth c hóa.

i” c ath i

Chúngta c g ng tìm c “c ntr ên” l n “c n d gian tínhto ántrongph ân tíchtr ng h p x unh t.

Nh ng c n d i (lower-bound )th ì th ngkh ó xác nh.

Phân tíchtr

ng h ptrung b ình

V i ki uph ân tích này, taph i

ctr ng hóa d li unh p c agi

i thu t

- - tínhgi á tr trung bình c a s l n m tph átbi u

c

th cthi.

- tínhth igian t ính toán trung bình c ato àngi

i

thu t.

ngth ì khó

Nh ngth - xác nhth igianch y c a m i phát bi u. -

c tr ng hóach ính xác d li u nh ptrongth c t .

Các k tqu ti m c n và x p x

ngmang t ính x p

K tqu c a m t s phân tíchto án h cth x (approximate): nó có th là m tbi uth c g m m tchu i nh ng s h nggi m d n t mquantr ng.

ng ý n các s h ng d n u trongbi uth cto án

Tath h c.

ngtr ình

Thí d :Th igian t ínhto ántrung b ình c a m tch là:

a0NlgN+ a 1N + a2

Ta có th vi t l i là:

a0NlgN+O(N)

V iN l n,takh ông c n tìmgi á tr c a a1 hay a2.

Các k tqu x p x

Ký hi u Ochota m t cách tìmra k tqu x p x khi N l n.

ngch úngta c ó th b qua m t s

i

ngkhi c ó t n t i m t s h ng d n

u trongbi u

Do ó, thôngth l th c.

Example: n u bi uth c là N(N-1)/2,ch úngta c ó th b o r ng nó kho ngch ng N2/2.

Phân tích m t gi

ithu t l p

l n nh ttrong

Thí d 1 Cho m t gi ithu t tìmph n t m t m ng1 chi u.

procedure MAX(A,n,max) /SetmaxtothemaximumofA(1:n)/ begin

integeri,n; max:=A[1]; for i:= 2 to n do if A[i]>max then max:=A[i]

end

ph c t p tínhto án c a gi ithu t c tính

N uC(n) l à theothao t ác so sánh (A[i]>max). H ãy xác nh C(n) trongtr ng h p x u nh t.

Phân tích m tgi

ithu t l p(tt.)

Thao tác c n b n c ath t cMAX l à thao tác so sánh.

T ng s thao tácso s ánh c ath t c MAX chính là s l n thân vòng l p cth cthi: (n-1).

ph c t p tínhto án c agi ithu t là O(n). V y

ây là ph c t p c a c hai tr ng h ptrung b ình và x u

nh t.

Ghich ú: N uthao t ác c n b n là phátbi u gán (max:= A[i]) thì O(n) là ng h p x u nh t. ph c t ptrongtr

Phân tích m tgi

ithu t l p(tt.)

ithu tki mtraxem c ó ph i m iph n t trong

Thí d 2:Gi m ng 1chi u là khác bi tnhau.

function UniqueElements(A, n) begin for i:= 1 to n –1 do

for j:= i+ 1 to n do

if A[i]= A[j] returnfalse

returntrue end

so sánh di n ra m ikhith ân vòng l p

ng h p x u nh t, m ngkh ông h có hai ph n t Trongtr nào b ngnhau ho c m ng có hai ph n t cu i cùng b ng nhau. Lúc ó m t s trong cth chi n.

i= 1 i= 2 n n t c n – 1 l nso s ánh n n t c n – 2 l nso s ánh

nso s ánh

i= n -2 i= n -1 j ch y t 2cho j ch y t 3cho . . jch y t n-1 cho n n t c2 l jch y t n cho n n t c1 l nso s ánh

Tóm l i, t ng s l nso s ánh là:

1 + 2 +3 + … +(n-2)+(n-1) =n(n-1)/2

ph c t p tínhto án c agi ithu ttrongtr ng h p x u

V y nh t là O(n2).

Phân tích m tgi

ithu t l p(tt.)

-stringmatching): T ìm t t c Thí d 3 (Sotr ùng dòng ký t nh ng s xu t hi n c a m tkhu ôn m u(pattern)trong m t v n b n(text).

và ki u m u là m t

V n b n là m t m ngT[1..n] g m n ký t m ngP[1..m] g m m ký t .

d chchuy n (shift) s trong v n

c là,Pxu thi n b t u t v trí s+1 trong v n b n

s n – m và T[s+1..s+m]=P[1..m]. Ki u m uPxu thi n v i b nT(t T) n u 1

ngi n nh t ithu t tìm t t c nh ng s xu t

dùng m t vòng l p mà ki mtra i u

i m itr trong n – m+ 1 tr có

M tgi hi n c aPtrongT s ki nP[1..m]=T[s+1..s+m] v th có c a s.

procedure NATIVE-STRING-MATCHING(T,P); begin

n:=|T|; m:=|P|; for s:= 0 to n – m do if P[1..m]=T[s+1,..,s+m] then

print “Patternoccurs withshift ” s;

end

procedure NATIVE-STRING-MATCHING(T,P); begin

n:=|T|; m:=|P|; for s:= 0 to n – m do begin

exit:=false; k:=1; while k  m and not exit do

if P[k]  T[s+k] then exit:=true else k:=k+1; if not exit then print “Patternoccurs withshift ” s;

end

ithu ttrongtr

ng h p

Gi ithu tNAIVESTRINGMATCHER c ó hai vòng l p l ngnhau : - vòng l pngo ài l p n – m + 1 l n. - vòng l ptrong l p t i a m l n. ph c t p c agi Do ó, x unh t là: O((n – m + 1)m).

ithu t

quy: các côngth ctruy

Phân tíchgi h i c n b n

ngph áp c n b n phân tích ph c t p c a

Có m tph cácgi ithu t quy.

ithu t quy th igianch y i

c N tùythu c vàoth igian

Tínhch t c a m tgi v i b d li unh p kíchth ch y c anh ng b d li unh pnh h n.

c mô t b ng m t côngth cto án h c c

Tínhch t này g i là h th ctruy h i (recurrencerelation ).

d nxu tra ph c t p c a m tgi ithu t quy, chúng

ta ph i gi i h th ctruy h i này.

Phân tíchgi

ithu t

quy b ngph

ngph áp l p

ngtr ình

quy mà l pqua b d li u i m tph n t . H th ctruy h i c a nó nh sau: Côngth c 1: M tch lo i nh p

N 2

CN = CN-1 + N C1 = 1

CN = CN-1 + N

ph c ng

Cáchsuyra t p b ngph pháp l p:

= CN-2 +(N – 1)+ N = CN-3 +(N – 2)+(N – 1)+ N

. . .

= C1 + 2 + … +(N – 2)+(N – 1)+ N = 1+ 2 + … +(N – 1)+ N =N(N-1)/2 = N2/2

Thí d 2

quy mà tách ôi b d

ngtr ình c làmvi c. H th ctruy h i là:

Côngth c 2: M tch li unh ptrong m t b CN = CN/2 + 1

N 2 C1 = 0

Cáchsuyra ph c t p:

Gi s N= 2 n C(2n) = C(2n-1) + 1 =C(2 n-2 )+1+ 1 =C(2 n-3 )+ 3

. . .

=C(2 0 )+ n = C1 +n= n

CN =n =lgN lgN CN

Thí d 3

ng trình

quy mà tách ôi b d li u

c làmvi cnh ngph ixem x ét t ngph n t

for

N 2

Công th c 3. M tch nh p trong m t b trong d li unh p. H th c truy h i là CN =2C N/2 + N

C1 = 0

Cáchsuyra

ph c t p:

Assume N= 2 n C(2n)= 2C(2 n-1)+ 2 n C(2n)/2n = C(2n-1)/ 2n-1 + 1

=C(2 n-2)/ 2n-2 + 1 +1

. .

= n C(2n )= n.2 n CN =NlgN CN NlgN

Thí d 4

ng trình

quy mà tách ôi d li unh p

c làmvi c. H th c truy h i là

Côngth c 4. M tch thànhhai n a trong m t b C(N) =2C(N/2)+ 1

for N 2 C(1)= 0

ph c t p:

Cáchsuyra Gi s

N= 2 n. C(2n)=2C(2 n-1)+ 1

C(2n)/ 2n =2C(2 n-1)/ 2n +1/2 n =C(2n-1)/ 2n-1 +1/2 n

=[C(2n-2)/ 2n-2 + 1/2n-1 ]+1/2 n . . .

=C(2n-i)/ 2n-i + 1/2n – i +1 + … +1/2 n

Cu i cùng,khi i= n -1, ta

c:

C(2n)/2n = C(2)/2 + ¼ +1/8 + …+1/2 n

= ½ + ¼ + ….+1/2n 1

C(2n)= 2 n

C(N) N

ng m c

ich úng

tìm ph c t pth ì có th r t

M t s h th ctruy h i có v gi ngnhaunh khó khigi khácnhau.

Nguyên t cph ân tích

ph c t ptrung b ình

ph c t p trung bình c a m tgi

i thu tA,taph

i làm

tính m t s b

c:

1.Quy t nh m t khônggian l y m u (samplingspace) u vào(k ích th

cn) c ó th có.Gi

di n t s không

nh ng d li u gian l y m u là S ={ I 1, I2,…, Ik}

2.Taph i nhngh a m tph ân b xácxu t p trên S mà bi udi n

m c

ch cch n mà d li u

u vào ó có th x yra.

3.Taph i tính t ng s tác v c n b n

x lý m t tr

i thu tAth chi n cgi ng h p m u.Ta d ùngv(I k) ký hi u t ng s tác ng h p

u vào thu c tr

li u

c th chi n b iAkhi d

v Ik.

Phân tích

ph c t ptrung b ình(tt.)

4.Ta t ính tr trung bình c a s tác v c n b n b ng cách tính k v ngsau:

Cavg(n)=v(I 1).p(I1)+v(I 2).p(I2) + …+v(Ik).p(Ik).

Thí d :Cho m t m ng A có n ph n t . Tìmki m v trí mà tr Xxu t hi ntrong m ngA.

begin i:=1; while i<= n and X<>A[i] do i:=i+1;

end

Thí d : Tìmki mtu n t

Gi s X có xu thi ntrong m ng và gi

nó xu thi n t i m t v trí b t k trong m ng là nh r ng xácxu t unhau

và xácxu t m itr ng h p x y ra là p =1/n.

tìmth y X n u nó xu t hi n t i v trí 1 là 1 tìmth yX n u nó xu t hi n t i v trí 2 là 2

tìmth yX n u nó xu t hi n t i v trí n là n S l nso s ánh S l nso s ánh … S l nso s ánh

T ng s tác v so sánhtrung b ình là: C(n)= 1.(1/n)+ 2.(1/n) + …+N.(1/n)

=(1 + 2 + …+n).(1/n) =(1+2+ …+n)/n= n(n+1)/2.(1/n)=(n+1)/2.

Vàichu i s thông d ng

cph ân tích

Có m t vàichu i s thông d ngtrongvi ph c t pgi ithu t.

Chu i s c ng

n2/2

n3/3 S1 = 1+ 2+ 3 + … + n S1 =n(n+1)/2 S2 = 1+ 2 2 + 32 + …+ n2 S2 =n(n+1)(2n+1)/6

Chu i s nhân

S = 1+ a+ a 2 + a3 + … + an S = (an+1 -1)/(a-1) If0< a<1,then S 1/(1-a) Và khi n , S ti n v 1/(1-a).

Phân tích và thiết kế giải thuật - Chương 1

Môn h c:Ph ân tích và thi t k gi ithu t

Ch

ng 1

CÁCKH ÁINI M C N B N

N i dung

1.Ki u d li utr u t

ng

ng là m t mô hìnhto án

c nhngh atr ên

M tki u d li utr u t h c i cùng v inh ng tác v mô hình này.

Vàith í d v Ki u d li utr u t

ng

Vàith í d v Ki u d li utr u t

ng(tt)

Gi i m t bàito án b ngADT

Thi công m tki u d li utr u t

ng

Thi công m tki u d li utr u t

ng(tt.)

2.

quy

H th ctruy h i

Chi n l

cChia-

-tr

Kh

quy

Kh

quy(tt.)

procedure hanoi(n, beg,aux, end); begin

if n= 1 then writeln(beg, end) else begin

end

end;

procedure hanoi(n,beg,aux,end: integer); /*StacksSTN,STBEG,STAUX, STEND,andSTADDcorrespond, respectively,tovariablesN,BEG,AUX, ENDandADD*/ label 1,3,5; var t: integer; begin

if top<> 0 then begin

begin writeln(beg,end); goto 5 end; top:= top+1; /* firstrecursivecall*/ STN[top]:=n;STBEG[top]:=beg; STAUX [top]:=aux; STEND [top]:=end; STADD [top]:=3;

end

/*savingreturnaddress*/ n:=n-1; t:=aux;aux:=end; end:= t; goto 1;

end;

S duy t cây

quy

Th t cduy t cây ti nth

t

(Pre-order)

Kh

quy uôi

c

ngi n hóa

Hai vòng l p l ngnhau c ó th nh sau:

Kh hàm quy

then

Thí d : Hàm tính t h p function comb(m,n: int):int If (n=morm= 0) return 1

else begin

a:= comb(n-1,m); b:= comb(n-1, m-1); return (a+b);

end

goto L0;

int comb(int n, int m) {

int top, topF; int stackN[100]; int stackM[100]; int stackADD[100]; int stackF[100]; int a, b, add, c; top= topF = 0; //stack initialize

{ c = 1, goto L3;} else { // 1st recursive call top= top+1 ; stackN[top]= n; stackM[top]=m; stackADD[top]=1; n= n-1; goto L0; L1:// 2nd recursive call

n=stackN[top]; m=stackM[top]; add=stackADD[top]; top= top –1; // push theresult topF= topF+ 1; stackF[top]= c; if (add== 1) goto L1; else if (add== 2) goto L2; } return c;

ph c t pgi

ithu t

3. Phân tích

Hai cáchph ân tích

Th igian t ínhto án c a m tgi

ng là

m t hàm c a kíchth

ithu tth c d li unh p.

Chúngtaquan t âm n:

ng h ptrung b ình (average case):th igian ithu t c n i v i m t “d ng” (typicalinputdata).

tínhto án mà m tgi li unh âpth ôngth

ng h p x unh t (worstcase ):th igian t ính i v i m t “d li u

ithu t c n

toán mà m tgi nhâp x unh t”

Khungth c c a s phân tích

Haitr

ng h pph ân tích

ngth ì khôngkh ó

gian tínhto án c a m tgi

procedure hanoi(n,beg,aux,end: integer); /StacksSTN,STBEG,STAUX, STEND,andSTADDcorrespond, respectively,tovariablesN,BEG,AUX, ENDandADD/ label 1,3,5; var t: integer; begin

/savingreturnaddress/ n:=n-1; t:=aux;aux:=end; end:= t; goto 1;

procedure MAX(A,n,max) /SetmaxtothemaximumofA(1:n)/ begin