Giáo trình MS SQL Server 7.0

Collected by The_Wall (11/10/2005)

Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ........................................................................ Trang 1

1. Mөc tiêu

2. KiӃn thӭc cѫ bҧn cҫn có ÿӇ hӑc chѭѫng này

3. Tài liӋu tham khҧo có liên quan ÿӃn chѭѫng

4. Nӝi dung:

I.1 - Sӵ cҫn thiӃt phҧi phân tích giҧi thuұt.

I.2 - Thӡi gian thӵc hiӋn cӫa giҧi thuұt.

I.3 - Tӹ suҩt tăng và ÿӝ phӭc tҥp cӫa giҧi thuұt.

I.4 - Cách tính ÿӝ phӭc tҥp.

I.5 - Phân tích các chѭѫng trình ÿӋ quy.

5. Vҩn ÿӅ nghiên cӭu cӫa trang kӃ tiӃp

Trong chѭѫng này chúng ta sӁ nghiên cӭu các vҩn ÿӅ sau:

· Sӵ cҫn thiӃt phҧi phân tích các giҧi thuұt.

· Thӡi gian thӵc hiӋn cӫa chѭѫng trình.

· Tӹ suҩt tăng và ÿӝ phӭc tҥp cӫa giҧi thuұt.

· Tính thӡi gian thӵc hiӋn cӫa chѭѫng trình.

· Phân tích các chѭѫng trình ÿӋ quy.

I.1- SӴ CҪN THIӂT PHҦI PHÂN TÍCH GIҦI THUҰT

Trong khi giҧi mӝt bài toán chúng ta có thӇ có mӝt sӕ giҧi thuұt khác nhau, vҩn ÿӅ là cҫn phҧi

ÿánh giá các giҧi thuұt ÿó ÿӇ lӵa chӑn mӝt giҧi thuұt tӕt (nhҩt). Thông thѭӡng thì ta sӁ căn cӭ vào các

tiêu chuҭn sau:

1.- Giҧi thuұt ÿúng ÿҳn.

2.- Giҧi thuұt ÿѫn giҧn.

3.- Giҧi thuұt thӵc hiӋn nhanh.

Vӟi yêu cҫu (1), ÿӇ kiӇm tra tính ÿúng ÿҳn cӫa giҧi thuұt chúng ta có thӇ cài ÿһt giҧi thuұt ÿó

và cho thӵc hiӋn trên máy vӟi mӝt sӕ bӝ dӳ liӋu mүu rӗi lҩy kӃt quҧ thu ÿѭӧc so sánh vӟi kӃt quҧÿã

biӃt. Thӵc ra thì cách làm này không chҳc chҳn bӣi vì có thӇ giҧi thuұt ÿúng vӟi tҩt cҧ các bӝ dӳ liӋu

chúng ta ÿã thӱ nhѭng lҥi sai vӟi mӝt bӝ dӳ liӋu nào ÿó. Vҧ lҥi cách làm này chӍ phát hiӋn ra giҧi thuұt

sai chӭ chѭa chӭng minh ÿѭӧc là nó ÿúng. Tính ÿúng ÿҳn cӫa giҧi thuұt cҫn phҧi ÿѭӧc chӭng minh

Eҵng toán hӑc. Tҩt nhiên ÿLӅu này không ÿѫn giҧn và do vұy chúng ta sӁ không ÿӅ cұp ÿӃn ӣÿây.

Khi chúng ta viӃt mӝt chѭѫng trình ÿӇ sӱ dөng mӝt vài lҫn thì yêu cҫu (2) là quan trӑng nhҩt.

Chúng ta cҫn mӝt giҧi thuұt dӉ viӃt chѭѫng trình ÿӇ nhanh chóng có ÿѭӧc kӃt qӫa , thӡi gian thӵc hiӋn

chѭѫng trình không ÿѭӧc ÿӅ cao vì dù sao thì chѭѫng trình ÿó cNJng chӍ sӱ dөng mӝt vài lҫn mà thôi.

Tuy nhiên khi mӝt chѭѫng trình ÿѭӧc sӱ dөng nhiӅu lҫn thì thì yêu cҫu tiӃït kiӋm thӡi gian

Collected by The_Wall (11/10/2005)

Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ........................................................................ Trang 2

thӵc hiӋn chѭѫng trình lҥi rҩt quan trӑng ÿһc biӋt ÿӕi vӟi nhӳng chѭѫng trình mà khi thӵc hiӋn cҫn dӳ

liӋu nhұp lӟn do ÿó yêu cҫu (3) sӁÿѭӧc xem xét mӝt cách kӻ càng. Ta gӑi nó là hiӋu quҧ thӡi gian thӵc

hiӋn cӫa giҧi thuұt.

I.2- THӠI GIAN THӴC HIӊN CӪA GIҦI THUҰT

I.2.1- Thӡi gian thӵc hiӋn chѭѫng trình.

I.2.2- Ĉѫn vӏÿo thӡi gian thӵc hiӋn.

I.2.3- Thӡi gian thӵc hiӋn trong trѭӡng hӧp xҩu nhҩt.

Mӝt phѭѫng pháp ÿӇ xác ÿӏnh hiӋu quҧ thӡi gian thӵc hiӋn cӫa mӝt giҧi thuұt là lұp trình nó và ÿo

Oѭӡng thӡi gian thӵc hiӋn cӫa hoҥt ÿӝng trên mӝt máy tính xác ÿӏnh ÿӕi vӟi tұp hӧp ÿѭӧc chӑn lӑc các

Gӳ liӋu vào.

Thӡi gian thӵc hiӋn không chӍ phө thuӝc vào giҧi thuұt mà còn phө thuӝc váo tұp các chӍ thӏ

Fӫa máy tính, chҩt lѭӧng cӫa máy tính và kӻ xҧo cӫa ngѭӡi lұp trình. Sӵ thi hành cNJng có thӇÿLӅu

chӍnh ÿӇ thӵc hiӋn tӕt trên tұp ÿһc biӋt các dӳ liӋu vào ÿѭӧc chӑn. ĈӇ vѭӧt qua các trӣ ngҥi này, các

nhà khoa hӑc máy tính ÿã chҩp nhұn tính phӭc tҥp cӫa thӟi gian ÿѭӧc tiӃp cұn nhѭ mӝt sӵÿo lѭӡng cѫ

Eҧn sӵ thӵc thi cӫa giҧi thuұt. Thuұt ngӳ tính hiӋu quҧ sӁÿӅ cұp ÿӃn sӵÿo lѭӡng này và ÿһc biӋt ÿӕi

Yӟi sӵ phӭc tҥp thӡi gian trong trѭӡng hӧp xҩu nhҩt.

I.2.1- Thӡi gian thӵc hiӋn chѭѫng trình.

Thӡi gian thӵc hiӋn mӝt chѭѫng trình là mӝt hàm cӫa kích thѭӟc dӳ liӋu vào, ký hiӋu T(n) trong ÿó n

là kích thѭӟc (ÿӝ lӟn) cӫa dӳ liӋu vào.

Ví dө 1-1: Chѭѫng trình tính tәng cӫa n sӕ có thӡi gian thӵc hiӋn là T(n) = cn trong ÿó c là

Pӝt hҵng sӕ.

Thӡi gian thӵc hiӋn chѭѫng trình là mӝt hàm không âm, tӭc là T(n) ³0 "n³0.

I.2.2- Ĉѫn vӏÿo thӡi gian thӵc hiӋn.

Ĉѫn vӏ cӫa T(n) không phҧi là ÿѫn vӏÿo thӡi gian bình thѭӡng nhѭ giӡ, phút giây... mà thѭӡng

ÿѭӧc xác ÿӏnh bӣi sӕ các lӋnh ÿѭӧc thӵc hiӋn trong mӝt máy tính lý tѭӣng.

Ví dө 1-2: Khi ta nói thӡi gian thӵc hiӋn cӫa mӝt chѭѫng trình là T(n) = cn thì có nghƭa là

chѭѫng trình ҩy cҫn cn chӍ thӏ thӵc thi.

I.2.3- Thӡi gian thӵc hiӋn trong trѭӡng hӧp xҩu nhҩt.

Nói chung thì thӡi gian thӵc hiӋn chѭѫng trình không chӍ phө thuӝc vào kích thѭӟc mà còn

phө thuӝc vào tính chҩt cӫa dӳ liӋu vào. Nghƭa là dӳ liӋu vào có cùng kích thѭӟc nhѭng thӡi gian thӵc

hiӋn chѭѫng trình có thӇ khác nhau. Chҷng hҥn chѭѫng trình sҳp xӃp dãy sӕ nguyên tăng dҫn, khi ta

cho vào dãy có thӭ tӵ thì thӡi gian thӵc hiӋn khác vӟi khi ta cho vào dãy chѭa có thӭ tӵ, hoһc khi ta

cho vào mӝt dãy ÿã có thӭ tӵ tăng thì thӡi gian thӵc hiӋn cNJng khác so vӟi khi ta cho vào mӝt dãy ÿã

có thӭ tӵ giҧm.

Vì vұy thѭӡng ta coi T(n) là thӡi gian thӵc hiӋn chѭѫng trình trong trѭӡng hӧp xҩu nhҩt trên

Gӳ liӋu vào có kích thѭóc n, tӭc là: T(n) là thӡi gian lӟn nhҩt ÿӇ thӵc hiӋn chѭѫng trình ÿӕi vӟi mӑi dӳ

liӋu vào có cùng kích thѭӟc n.

I.3- TӸ SUҨT TĂNG VÀ ĈӜ PHӬC TҤP CӪA GIҦI THUҰT

Collected by The_Wall (11/10/2005)

Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ........................................................................ Trang 3

I.3.1- Tӹ suҩt tăng

I.3.2- Khái niӋm ÿӝ phӭc tҥp cӫa giҧi thuұt

I.3.1- Tӹ suҩt tăng

Ta nói rҵng hàm không âm T(n) có Wӹ suҩt tăng (growth rate) f(n) nӃu tӗn tҥi các hҵng sӕ c

và n0 sao cho T(n) f(n) vӟi mӑi n • n0.

Ta có thӇ chӭng minh ÿѭӧc rҵng “Cho mӝt hàm không âm T(n) bҩt kǤ, ta luôn tìm ÿѭӧc tӹ

suҩt tăng f(n) cӫa nó”.

Ví dө 1-3: Giҧ sӱ T(0) = 1, T(1) = 4 và tәng quát T(n) = (n+1)2

. Ĉһt n0 = 1 và c = 4 thì vӟi mӑi

n • 1 chúng ta dӉ dàng chӭng minh rҵng T(n) = (n+1)2

4n2

vӟi mӑi n • 1, tӭc là tӹ suҩt tăng cӫa T(n)

là n2

.

Ví dө 1-4: Tӹ suҩt tăng cӫa hàm T(n) = 3n3

+ 2n2

là n3

. Thӵc vұy, cho n0 = 0 và c = 5 ta dӉ

dàng chӭng minh rҵng vӟi mӑi n • 0 thì 3n3

+ 2n2

5n3

I.3.2- Khái niӋm ÿӝ phӭc tҥp cӫa giҧi thuұt

Giҧ sӱ ta có hai giҧi thuұt P1 và P2 vӟi thӡi gian thӵc hiӋn tѭѫng ӭng là T1(n) = 100n2

(vӟi tӹ

suҩt tăng là n2

) và T2(n) = 5n3

(vӟi tӹ suҩt tăng là n3

). Giҧi thuұt nào sӁ thӵc hiӋn nhanh hѫn? Câu trҧ

Oӡi phө thuӝc vào kích thѭӟc dӳ liӋu vào. Vӟi n < 20 thì P2 sӁ nhanh hѫn P1 (T2<T1), do hӋ sӕ cӫa 5n3

nhӓ hѫn hӋ sӕ cӫa 100n2

(5<100). Nhѭng khi n > 20 thì ngѭѫc lҥi do sӕ mNJ cӫa 100n2

nhӓ hѫn sӕ mNJ

Fӫa 5n3

(2<3). Ӣÿây chúng ta chӍ nên quan tâm ÿӃn trѭӡng hӧp n>20 vì khi n<20 thì thӡi gian thӵc

hiӋn cӫa cҧ P1 và P2 ÿӅu không lӟn và sӵ khác biӋt giӳa T1 và T2 là không ÿáng kӇ..

Nhѭ vұy mӝt cách hӧp lý là ta xét tӹ suҩt tăng cӫa hàm thӡi gian thӵc hiӋn chѭѫng trình thay

vì xét chính bҧn thân thӡi gian thӵc hiӋn.

Cho mӝt hàm T(n), T(n) gӑi là có ÿӝ phӭc tҥp f(n) nӃu tӗn tҥi các hҵng c, N0 sao cho T(n)

cf(n) vӟi mӑi n • N0 (tӭc là T(n) có tӹ suҩt tăng là f(n)) và kí hiӋu T(n) là O(f(n)) (ÿӑc là “ô cӫa f(n)”)

Ví dө 1-5: T(n)= (n+1)2

có tӹ suҩt tăng là n2

nên T(n)= (n+1)2

là O(n2

)

Chú ý: O(c.f(n))=O(f(n)) vӟi c là hҵng sӕ. Ĉһc biӋt O(c)=O(1)

Nói cách khác ÿӝ phӭc tҥp tính toán cӫa giҧi thuұt là mӝt hàm chһn trên cӫa hàm thӡi gian. Vì

Kҵng nhân tӱ c trong hàm chһn trên không có ý nghƭa nên ta có thӇ bӓ qua vì vұy hàm thӇ hiӋn ÿӝ phӭc

Wҥp có các dҥng thѭӡng gһp sau: log2n, n, nlog2n, n2

, n3

, 22

, n!, nn

. Ba hàm cuӕi cùng ta gӑi là dҥng

hàm mNJ, các hàm khác gӑi là hàm ÿa thӭc. Mӝt giҧi thuұt mà thӡi gian thӵc hiӋn có ÿӝ phӭc tҥp là mӝt

hàm ÿa thӭc thì chҩp nhұn ÿѭӧc tӭc là có thӇ cài ÿһt ÿӇ thӵc hiӋn, còn các giҧi thuұt có ÿӝ phӭc tҥp

hàm mNJ thì phҧi tìm cách cҧi tiӃn giҧi thuұt.

Khi nói ÿӃn ÿӝ phӭc tҥp cӫa giҧi thuұt là ta muӕn nói ÿӃn hiӋu quҧ cӫa thӡi gian thӵc hiӋn cӫa

chѭѫng trình nên ta có thӇ xem viӋc xác ÿӏnh thӡi gian thӵc hiên cӫa chѭѫng trình chính là xác ÿӏnh ÿӝ

phӭc tҥp cӫa giҧi thuұt.

I.4- CÁCH TÍNH ĈӜ PHӬC TҤP

I.4.1- Qui tҳc cӝng

I.4.2- Qui tҳc nhân

Collected by The_Wall (11/10/2005)

Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ........................................................................ Trang 4

I.4.3- Qui tҳc tәng quát ÿӇ phân tích mӝt chѭѫng trình

I.4.4- Ĉӝ phӭc tҥp cӫa chѭѫng trình có gӑi chѭѫng trình con không ÿӋ qui

Cách tính ÿӝ phӭc tҥp cӫa mӝt giҧi thuұt bҩt kǤ là mӝt vҩn ÿӅ không ÿѫn giҧn. Tuy nhiên ta có

thӇ tuân theo mӝt sӕ nguyên tҳc sau:

I.4.1- Qui tҳc cӝng:

NӃu T1(n) và T2(n) là thӡi gian thӵc hiӋn cӫa hai ÿRҥn chѭѫng trình P1 và P2; và

T1(n)=O(f(n)), T2(n)=O(g(n) thì thӡi gian thӵc hiӋn cӫa ÿRҥn hai chѭѫng trình ÿó Qӕi tiӃp nhau là

T(n)=O(max(f(n),g(n)))

Ví dө 1-6: LӋnh gán x:=15 tӕn mӝt hҵng thӡi gian hay O(1)

LӋnh ÿӑc dӳ liӋu READ(x) tӕn mӝt hҵng thӡi gian hay O(1)

Vұy thӡi gian thӵc hiӋn cҧ hai lӋnh trên nӕi tiӃp nhau là O(max(1,1))=O(1)

I.4.2- Qui tҳc nhân:

NӃu T1(n) và T2(n) là thӡi gian thӵc hiӋn cӫa hai ÿRҥn chѭѫng trình P1và P2 và T1(n) =

O(f(n)), T2(n) = O(g(n) thì thӡi gian thӵc hiӋn cӫa ÿRҥn hai ÿRҥn chѭѫng trình ÿó Oӗng nhau là T(n) =

O(f(n).g(n))

I.4.3- Qui tҳc tәng quát ÿӇ phân tích mӝt chѭѫng trình:

- Thӡi gian thӵc hiӋn cӫa mӛi lӋnh gán, READ, WRITE là O(1)

- Thӡi gian thӵc hiӋn cӫa mӝt chuӛi tuҫn tӵ các lӋnh ÿѭӧc xác ÿӏnh bҵng qui tҳc cӝng. Nhѭ

Yұy thӡi gian này là thӡi gian thi hành mӝt lӋnh nào ÿó lâu nhҩt trong chuӛi lӋnh.

- Thӡi gian thӵc hiӋn cҩu trúc IF là thӡi gian lӟn nhҩt thӵc hiӋn lӋnh sau THEN hoһc sau ELSE

và thӡi gian kiӇm tra ÿLӅu kiӋn. Thѭӡng thӡi gian kiӇm tra ÿLӅu kiӋn là O(1).

- Thӡi gian thӵc hiӋn vòng lһp là tәng (trên tҩt cҧ các lҫn lһp) thӡi gian thӵc hiӋn thân vòng

Oһp. NӃu thӡi gian thӵc hiӋn than vòng lһp không ÿәi thì thӡi gian thӵc hiӋn vòng lһp là tích cӫa sӕ lҫn

Oһp vӟi thӡi gian thӵc hiӋn thân vòng lһp.

Ví dө 1-7: Tính thӡi gian thӵc hiӋn cӫa ÿRҥn chѭѫng 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

{2} for j:=n downto i+1 do

{3} if a[j-1]>a[j] then begin

{ ÿәi chә a[i], a[j] }

{4} temp:=a[j-1];

{5} a[j-1]:=a[j];

{6} a[j]:=temp; end;

end;

Collected by The_Wall (11/10/2005)

Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ........................................................................ Trang 5

Cҧ ba lӋnh ÿәi chӛ {4} {5} {6} tӕn O(1) thӡi gian, do ÿó lӋnh {3} tӕn O(1).

Vòng lһp {2} thӵc hiӋn (n-i) lҫn, mӛi lҫn O(1) do ÿó vòng lһp {2} tӕn O((n-i).1)=O(n-i).

Vòng lһp {1} lһp (n-1) lҫn vұy ÿӝ phӭc tҥp cӫa giҧi thuұt là:

I.4.4- Ĉӝ phӭc tҥp cӫa chѭѫng trình có gӑi chѭѫng trình con không ÿӋ qui

NӃu chúng ta có mӝt chѭѫng trình vӟi các chѭѫng trình con không ÿӋ quy, ÿӇ tính thӡi gian

thӵc hiӋn cӫa chѭѫng trình, trѭӟc hӃt chúng ta tính thӡi gian thӵc hiӋn cӫa các chѭѫng trình con không

Jӑi các chѭѫng trình con khác. Sau ÿó chúng ta tính thӡi gian thӵc hiӋn cӫa các chѭѫng trình con chӍ

Jӑi các chѭѫng trình con mà thӡi gian thӵc hiӋn cӫa chúng ÿã ÿѭӧc tính. Chúng ta tiӃp tөc quá trình

ÿánh giá thӡi gian thӵc hiӋn cӫa mӛi chѭѫng trình con sau khi thӡi gian thӵc hiӋn cӫa tҩt cҧ các

chѭѫng trình con mà nó gӑi ÿã ÿѭӧc ÿánh giá. Cuӕi cùng ta tính thӡi gian cho chѭѫng trình chính.

Giҧ sӱ ta cô mӝt hӋ thӕng các chѭѫng trình gӑi theo sѫÿӗ sau:

Chѭѫng trình A gӑi hai chѭѫng trình con là B và C, chѭѫng trình B gӑi hai chѭѫng trình con là

B1 và B2, chѭѫng trình B1 gӑi hai chѭѫng trình con là B11 và B12.

ĈӇ tính thӡi gian thӵc hiӋn cӫa A, ta tính theo các bѭӟc sau:

- Tính thӡi gian thӵc hiӋn cӫa C, B2, B11 và B12.

- Tính thӡi gian thӵc hiӋn cӫa B1.

- Tính thӡi gian thӵc hiӋn cӫa B.

- Tính thӡi gian thӵc hiӋn cӫa A.

Ví dө 1-8: Ta có thӇ viӃt lҥi chѭѫng trình sҳp xӃp bubble nhѭ sau:

procedure Swap (var x, y: integer);

var temp: integer;

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 Giɠi Thuɪt – ĈɝI +͌C CɣN 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 viӃt trên, chѭѫng trình Bubble gӑi chѭѫng trình con Swap, do ÿó ÿӇ tính thӡi gian

thӵc hiӋn cӫa Bubble, trѭӟc hӃt ta cҫn tính thӡi gian thӵc hiӋn cӫa Swap. DӉ thҩy thӡi gian thӵc hiӋn

Fӫa Swap là O(1) vì nó chӍ bao gӗm 3 lӋnh gán.

Trong Bubble, lӋnh {3} gӑi Swap nên chӍ tӕn O(1), lӋnh {2} thӵc hiӋn n-i lҫn, mӛi lҫn tӕn

O(1) nên tӕn O(n-i). LӋnh {1} thӵc hiӋn n-1 lҫn nên

I.5- PHÂN TÍCH CÁC CHѬѪNG TRÌNH Ĉӊ QUY

I.5.1- Thành lұp phѭѫng trình ÿӋ quy

I.5.2- Giҧi phѭѫng trình ÿӋ quy

Vӟi các chѭѫng trình có gӑi các chѭѫng trình con ÿӋ quy, ta không thӇ áp dөng cách tính nhѭ

Yӯa trình bày trong mөc I.4.4 bӣi vì mӝt chѭѫng trình ÿӋ quy sӁ gӑi chính bҧn thân nó.

Vӟi các chѭѫng trình ÿӋ quy, trѭӟc hӃt ta cҫn thành lұp các phѭѫng trình ÿӋ quy, sau ÿó giҧi

phѭѫng trình ÿӋ quy, nghiӋm cӫa phѭѫng trình ÿӋ quy sӁ là thӡi gian thӵc hiӋn cӫa chѭѫng trình ÿӋ

quy.

I.5.1- Thành lұp phѭѫng trình ÿӋ quy

Phѭѫng trình ÿӋ quy là mӝt phѭѫng trình biӇu diӉn mӕi liên hӋ giӳa T(n) và T(k), trong ÿó

T(n) là thӡi gian thӵc hiӋn chѭѫng trình vӟi kích thѭӟc dӳ liӋu nhұp là n, T(k) thӡi gian thӵc hiӋn

chѭѫng trình vӟi kích thѭӟc dӳ liӋu nhұp là k, vӟi k < n. ĈӇ thành lұp ÿѭӧc phѭѫng trình ÿӋ quy, ta

phҧi căn cӭ vào chѭѫng trình ÿӋ quy.

Ví dө 1-9: Xét hàm tính giai thӯa viӃt bҵng giҧi thuұt ÿӋ quy nhѭ sau:

function Giai_thua(n:integer): integer;

begin

if n=0 then Giai_thua :=1

else Giai_thua := n* Giai_thua(n-1);

end;

*ӑi T(n) là thӡi gian thӵc hiӋn viӋc tính n giai thӯa, thì T(n-1) là thӡi gian thӵc hiӋn viӋc tính

n-1 giai thӯa. Trong trѭӡng hӧp n=0 thì chѭѫng trình chӍ thӵc hiӋn mӝt lӋnh gán Giai_thua:=1, nên tӕn

O(1), do ÿó ta có T(0) = C1. Trong trѭӡng hӧp n>0 chѭѫng trình phҧi gӑi ÿӋ quy Giai_thua(n-1), viӋc

Jӑi ÿӋ quy này tӕn T(n-1), sau khi có kӃt quҧ cӫa viӋc gӑi ÿӋ quy, chѭѫng trình phҧi nhân kӃt quҧÿó

Yӟi n và gán cho Giai_thua. Thӡi gian ÿӇ thӵc hiӋn phép nhân và phép gán là mӝt hҵng C2. Vұy ta có

Collected by The_Wall (11/10/2005)

Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ........................................................................ Trang 7

Ĉây là phѭѫng trình ÿӋ quy ÿӇ tính thӡi gian thӵc hiӋn cӫa chѭѫng trình ÿӋ quy Giai_thua.

Ví dө 1-10: Chúng ta xét thӫ tөc MergeSort mӝt cách phác thҧo nhѭ sau:

function MergeSort (L:List ; n:integer) : List;

var

L1,L2 : List;

begin

if n = 1 then return(L)

else

begin

Chia L thành 2 nӱa L1 và L2 , mӛi mӝt nӱa có ÿӝ dài n/2;

return(Merge(MergeSort (L1 , n/2), MergeSort(L2, n/2)));

end;

end;

Chҷng hҥn ÿӇ sҳp xӃp danh sách L gӗm 8 phҫn tӱ 7, 4, 8, 9, 3, 1, 6, 2 ta có mô hình minh hӑa

Fӫa MergeSort nhѭ sau:

Hàm MergeSort nhұn mӝt danh sách có ÿӝ dài n và trҧ vӅ mӝt danh sách ÿã ÿѭӧc sҳp xӃp. Thӫ

Wөc Merge nhұn hai danh sách ÿã ÿѭӧc sҳp L1 và L2 mӛi danh sách có ÿӝ dài n/2, trӝn chúng lҥi vӟi

nhau ÿӇÿѭӧc mӝt danh sách gӗm n phҫn tӱ có thӭ tӵ. Giҧi thuұt chi tiӃt cӫa Merge ta sӁ bàn sau,

chúng ta chӍÿӇ ý rҵng thӡi 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 Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ........................................................................ Trang 8

Gӑi T(n) là thӡi gian thӵc hiӋn MergeSort mӝt danh sách n phҫn tӱ thì T(n/2) là thӡi gian thӵc

hiӋn MergeSort mӝt danh sách n/2 phҫn tӱ , ta có thӇ viӃt phѭѫng trình ÿӋ quy nhѭ sau:

Trong ÿó c1 là thӡi gian phҧi tӕn khi L có ÿӝ dài 1. Trong trѭӡng hӧp n > 1, thӡi gian cӫa

MergeSort ÿѭӧc chia làm hai phҫn. Phҫn gӑi ÿӋ quy MergeSort mӝt danh sách có ÿӝ dài n/2 là T(n/2)

do ÿó ta có 2T(n/2). Phҫn thӭ hai bao gӗm phép thӱ n >1, chia danh sách L thành hai nӱa bҵng nhau và

Merge. Ba thao tác này lҩy thӡi gian không ÿәi ÿӕi vӟi phép thӱ hoһc tӹ lӋ vӟi n ÿӕi vӟi ngҳt và

Merge. Nhѭ vұy hҵng c2ÿѭӧc chӑn và c2n là thӡi gian tәng ÿӇ làm các viӋc ÿó ngoҥi trӯ gӑi ÿӋ quy.

I.5.2- Giҧi phѭѫng trình ÿӋ quy

Có ba phѭѫng pháp giҧi phѭѫng trình ÿӋ quy:

1.- Phѭѫng pháp truy hӗi

2.- Phѭѫng pháp ÿoán nghiӋm.

3.- Lӡi giҧi tәng quát cӫa mӝt lӟp các phѭѫng trình ÿӋ quy.

Phѭѫng pháp truy hӗi

Dùng ÿӋ quy ÿӇ thay thӃ bҩt kǤ T(m) vӟi m < n vào phía phҧi cӫa phѭѫng trình cho ÿӃn khi tҩt

Fҧ T(m) vӟi m > 1 ÿѭӧc thay thӃ bӣi biӇu thӭc cӫa các T(1). Vì T(1) luôn là hҵng nên chúng ta có công

thӭc cӫa T(n) chӭa các sӕ hҥng chӍ liên quan ÿӃn n và các hҵng sӕ.

Giҧi phѭѫng trình.

Ví dө 1-10: Giҧi phѭѫng trình:

Ta có:

Giҧ sӱ n = 2k

, quá trình suy rӝng sӁ kӃt thúc khi i =k, khi ÿó ta có:

T(n) = 2k

T(1) + kC2n

Vì 2k

= n nên k = logn và vӟi T(1) =C1 nên ta có