Giáo trình nghiên cứu các kiểu dữ liệu có cấu trúc.pdf

1

GIíI THIÖU M¤N HäC

Trong ng«n ng÷ lË p tr× nh, d÷ liÖ u bao gåm hai kiÓ u chÝ nh lµ :

- KiÓ u d÷ liÖ u ®¬n gi¶ n: char, int, long, float, enumeration, subrange.

- KiÓ u d÷ liÖ u cã cÊ u tróc : struct, array, file (kiÓ u d÷ liÖ u cã kÝ ch th­íc

kh«ng ®æi)...

Gi¸ o tr× nh nµ y tË p trung vµ o viÖ c nghiª n cøu c¸ c kiÓ u d÷ liÖ u cã cÊ u tróc

cã kÝ ch th­íc kh«ng ®æi hoÆ c thay ®æi trong ng«n ng÷ lË p tr× nh, m« t¶ th«ng qua

ng«n ng÷ C. Ngoµ i ra cßn giíi thiÖ u c¸ c gi¶ i thuË t chung quanh c¸ c cÊ u tróc d÷

liÖ u nµ y nh­ c¸ ch tæ chøc, thùc hiÖ n c¸ c phÐ p to¸ n t× m kiÕ m, s¾ p thø tù néi, s¾ p

thø tù ngo¹ i...

§iÒ u kiÖ n ®Ó cã thÓ t× m hiÓ u râ rµ ng vÒ m«n häc nµ y lµ häc viª n ®∙ biÕ t

c¸ c kh¸ i niÖ m vÒ kü thuË t lË p tr× nh trª n ng«n ng÷ C. Trong phÇ n më ®Ç u, bµ i

gi¶ ng nµ y sÏ giíi thiÖ u c¸ ch thøc ph© n tÝ ch & thiÕ t kÕ mét gi¶ i thuË t tr­íc khi

t× m hiÓ u vÒ c¸ c cÊ u tróc d÷ liÖ u cô thÓ .

Vµ o cuèi khãa häc, sinh viª n cã thÓ :

- Ph© n tÝ ch ®é phøc t¹ p cña c¸ c ch­¬ng tr× nh cã kÝ ch th­íc nhá vµ trung

b× nh.

- NhË n thøc ®­îc sù cÇ n thiÕ t cña viÖ c thiÕ t kÕ cÊ u tróc d÷ liÖ u.

- Lµ m quen víi c¸ c kh¸ i niÖ m stacks, queues, danh s¸ ch ®Æ c, danh s¸ ch

liª n kÕ t, c© y nhÞ ph© n, c© y nhÞ ph© n t× m kiÕ m, ....

- HiÓ u ®­îc nguyª n lý cña viÖ c x© y dùng mét ch­¬ng tr× nh m¸ y tÝ nh.

- Cã thÓ chän lùa viÖ c tæ chøc d÷ liÖ u phï hîp vµ c¸ c gi¶ i thuË t xö lý d÷

liÖ u cã hiÖ u qu¶ trong khi x© y dùng ch­¬ng tr× nh. Sinh viª n cÇ n l­u ý r» ng, tïy

vµ o c«ng viÖ c cô thÓ mµ ta nª n chän cÊ u tróc d÷ liÖ u nµ o lµ thÝ ch hîp theo h­íng

tèi ­u vÒ thêi gian thùc hiÖ n hay tèi ­u vÒ bé nhí.

2

Ch­¬ng I

PH¢N TÝ CH & THIÕT KÕ

GI¶I THUËT

I. më ®Çu

HÇ u hÕ t c¸ c bµ i to¸ n ®Ò u cã nhiÒ u gi¶ i thuË t kh¸c nhau ®Ó gi¶ i quyÕ t chóng.

VË y lµ m thÕ nµ o chän ®­îc mét gi¶ i thuË t tèt nhÊ t ?

ViÖ c chän lùa phô thuéc vµ o nhiÒ u yÕ u tè nh­ : §é phøc t¹ p tÝ nh to¸ n cña

gi¶ i thuË t, chiÕ m dung l­îng bé nhí, tÇ n suÊ t sö dông, tÝ nh ®¬n gi¶ n, tèc ®é thùc

hiÖ n...

Th«ng th­êng môc tiª u chän lùa lµ :

1. Gi¶ i thuË t râ rµ ng, dÔ hiÓ u, dÔ m∙ hãa vµ hiÖ u chØ nh.

2. Gi¶ i thuË t sö dông cã hiÖ u qu¶ tµ i nguyª n cña m¸ y tÝ nh vµ ®Æ c biÖ t

ch¹ y cµ ng nhanh cµ ng tèt.

Do ®ã khi viÕ t ch­¬ng tr× nh ®Ó ch¹ y mét lÇ n hoÆ c Ý t ch¹ y th× môc tiª u 1 lµ

quan träng h¬n c¶ .

Ng­îc l¹ i khi viÕ t ch­¬ng tr× nh ®Ó ch¹ y nhiÒ u lÇ n th× phÝ tæn ch¹ y ch­¬ng

tr× nh cã thÓ v­ît qu¸ phÝ tæn lË p ch­¬ng tr× nh, nhÊ t lµ khi ph¶ i nhË p nhiÒ u sè

liÖ u. Nãi chung, ng­êi lË p tr× nh ph¶ i biÕ t chän lùa, viÕ t, ®¸ nh gi¸ c¸ c gi¶ i thuË t

®Ó cã ®­îc gi¶ i thuË t tèi ­u cho bµ i to¸ n cña m× nh.

II. ®¸nh gi¸ thêi gian ch¹y cña ch­¬ng tr× nh

Thêi gian ch¹ y cña ch­ong tr× nh phô thuéc vµ o :

1. Input cho ch­¬ng tr× nh

2. ChÊ t l­îng m∙ sinh ra cña ch­¬ng tr× nh dÞ ch.

3. Tr¹ ng th¸ i vµ tèc ®é cña c¸ c lÖ nh ch¹ y trª n m¸ y.

4. §é phøc t¹ p thêi gian cña gi¶ i thuË t.

§iÒ u 1 lµ chøc n¨ ng nhË p. KÝ ch th­íc cña input (vÝ dô lµ n) vµ ta th­êng ký

hiÖ u T(n) lµ ®¹ i l­îng thêi gian cÇ n thiÕ t ®Ó gi¶ i bµ i to¸ n kÝ ch th­íc n.

§iÒ u 2, 3 th­êng ®¸ nh gi¸ khã kh¨ n v× phô thuéc vµ o phÇ n mÒ m ch­¬ng

tr× nh dÞ ch vµ phÇ n cøng cña m¸ y.

§iÒ u 4 lµ ®iÒ u mµ ng­êi lË p tr× nh cÇ n kh¶ o s¸ t ®Ó lµ m t¨ ng tèc ®é cña

ch­¬ng tr× nh.

3

III. ký hiÖu o(n) vµ Ω(n) :

Ta ®¸ nh gi¸ tû lÖ ph¸ t triÓ n c¸ c hµ m T(n) qua ký hiÖ u O(n).

Ta nãi thêi gian ch¹ y T(n) cña ch­¬ng tr× nh lµ O(n2

) cã nghÜ a lµ :

∃ c > 0 vµ n0 sao cho ∀ n ≥ n0 ta cã T(n) ≤ c.n2

.

VÝ dô : Gi¶ sö T(0) = 1, T(1) = 4, v v...

Tæng qu¸ t T(n) = (n +1)

2

th× ta nãi T(n) lµ O(n2

) v× cã thÓ ®Æ t c1 = 4, n0 = 1,

th× khi n ≥ 1 ta cã (n +1)

2 ≤ 4n2

.

Nh­ng kh«ng thÓ lÊ y n0 = 0 v× T(0) = 1 kh«ng nhá h¬n c.02

= 0,∀c; gi¶ thiÕ t

r» ng n ≥ 0 vµ T(n) ≥ 0.

Ta nãi T(n) lµ O(f(n)) nÕ u ∃ const c vµ n0 sao cho T(n) ≤ c.f(n), ∀ n ≥ n0.

Ch­¬ng tr× nh ch¹ y víi thêi gian O(f(n)) ta nãi nã ph¸ t triÓ n tû lÖ víi f(n).

Khi nãi T(n) lµ O(f(n)) th× f(n) lµ chÆ n trª n cña T(n).

§Ó nãi chÆ n d­íi cña T(n) ta dïng ký hiÖ u Ω.

Ta nãi T(n) lµ Ω(g(n)) nÕ u ∃ const c, n0 sao cho T(n) ≥ c.g(n), ∀ n ≥ n0.

VÝ dô : §Ó kiÓ m tra T(n) = n3

+ 2n2

lµ Ω(n3

) ta ®Æ t c = 1 th× T(n) ≥ c.n3

, ∀n

= 0, 1,... (no= 0).

* Sù tr¸ i ng­îc cña tû lÖ ph¸ t triÓ n :

Ta gi¶ sö c¸ c ch­¬ng tr× nh cã thÓ ®¸ nh gi¸ b» ng c¸ ch so s¸ nh c¸ c hµ m thêi

gian cña chóng víi c¸ c h» ng tû lÖ kh«ng ®¸ ng kÓ . Khi ®ã ta nãi ch­¬ng tr× nh cã

thêi gian ch¹ y O(n2

). NÕ u ch­¬ng tr× nh 1 ch¹ y mÊ t 100.n2

thêi gian (mili gi© y)

th× ch­¬ng tr× nh 2 ch¹ y mÊ t 5.n3

thêi gian, th× ta cã tû sè thêi gian cña 2 ch­¬ng

tr× nh lµ 5.n3

/100.n2

= n/20, nghÜ a lµ khi n = 20 th× thêi gian ch¹ y 2 ch­¬ng tr× nh

lµ b» ng nhau, khi n < 20 th× ch­¬ng tr× nh 2 ch¹ y nhanh h¬n ch­¬ng tr× nh 1. Do

®ã khi n > 20 th× nª n dïng ch­¬ng tr× nh 1.

VÝ dô : Cã 4 ch­¬ng tr× nh cã 4 ®é phøc t¹ p kh¸ c nhau ®­îc biÓ u diÔ n trong

b¶ ng d­íi ®© y.

Thêi gian

ch¹ y T(n)

KÝ ch th­íc bµ i to¸ n

tèi ®a cho 103

s

KÝ ch th­íc bµ i to¸ n

tèi ®a cho 104

s

Tû lÖ t¨ ng vÒ

kÝ ch th­íc

100.n 10 100 10.0 lÇ n

5.n2 14 45 3.2 lÇ n

n3/2 12 27 2.3 lÇ n

2n 10 13 1.3 lÇ n

Gi¶ sö trong 103

s th× 4 ch­¬ng tr× nh gi¶ i c¸ c bµ i to¸ n cã kÝ ch th­íc tèi ®a

trong cét 2. NÕ u cã m¸ y tèt tèc ®é t¨ ng lª n 10 lÇ n th× kÝ ch th­íc tèi ®a t­¬ng øng

4

cña 4 ch­¬ng tr× nh tr× nh bµ y ë cét 3. TØ lÖ hai cét 1,2 ghi ë cét 4. Nh­ vË y nÕ u

®Ç u t­ vÒ tèc ®é 10 lÇ n th× chØ thu lîi cã 30% vÒ kÝ ch th­íc bµ i to¸ n nÕ u dïng

ch­¬ng tr× nh cã ®é phøc t¹ p O(2n

).

IV. c¸ch tÝ nh thêi gian ch¹y ch­¬ng tr× nh :

1. Qui t¾c tæng:

Gi¶ sö T1(n) vµ T2(n) lµ thêi gian ch¹ y ch­¬ng tr× nh P1 vµ P2 t­¬ng øng ®­îc

®¸ nh gi¸ lµ O(f(n)) vµ O(g(n)). Khi ®ã T1(n) + T2(n) sÏ lµ O(max(f(n),g(n)))

(ch¹ y xong ch­¬ng tr× nh P1 th× ch¹ y P2).

Chøng minh:

Theo ®Þ nh nghÜ a O(f(n)) vµ O(g(n)) th× ∃ c1, n1, c2, n2 sao cho

T1(n) ≤ c1.f(n) ∀ n ≥ n1 ; T2(n) ≤ c2.g(n) ∀ n ≥ n2.

§Æ t n0 = max(n1, n2)

NÕ u n ≥ no th× T1(n) + T2(n) ≤ (c1 + c2).max(f(n),g(n)).

2. Qui t¾c tÝ ch:

T1(n). T2(n) lµ O(f(n).g(n)).

Chøng minh : t­¬ng tù nh­ tæng.

VÝ dô : Cã 3 ch­¬ng tr× nh cã thêi gian ch¹ y t­¬ng øng lµ O(n2

), O(n3

),

O(n.logn). ThÕ th× thêi gian ch¹ y 3 ch­¬ng tr× nh ®ång thêi lµ O(max(n2

, n3

,

nlogn)) sÏ lµ O(n3

).

Nãi chung thêi gian ch¹ y mét d∙ y cè ®Þ nh c¸ c b­íc lµ thêi gian ch¹ y lín

nhÊ t cña mét b­íc nµ o ®ã trong d∙ y. Còng cã tr­êng hîp cã 2 hay nhiÒ u b­íc cã

thêi gian ch¹ y kh«ng t­¬ng xøng (kh«ng lín h¬n mµ còng kh«ng nhá h¬n). Khi

®ã qui t¾ c tÝ nh tæng ph¶ i ®­îc tÝ nh trong tõng tr­êng hîp.

n4 nÕ u n ch½ n

VÝ dô : f(n) = {

n2 nÕ u n lÎ

g(n) = n2 nÕ u n ch½ n

{

n3 nÕ u n lÏ

Thêi gian ch¹ y lµ O(max(f(n),g(n))) lµ n4

nÕ u n ch½ n vµ n3

nÕ u n lÎ .

NÕ u g(n) ≤ f(n), ∀ n ≥ no, no lµ const nµ o ®ã th× O(f(n)+g(n)) sÏ lµ O(f(n)).

VÝ dô : O(n2

+ n) = O(n2

)

Tr­íc khi ®­a ra qui t¾ c chung ®Ó ph© n tÝ ch thêi gian ch¹ y cña ch­¬ng tr× nh

th× ta xÐ t vÝ dô ®¬n gi¶ n sau.

5

VÝ dô : XÐ t ch­¬ng tr× nh Bubble dïng s¾ p d∙ y sè nguyª n theo chiÒ u t¨ ng.

Procedure Bubble (var A: array [1..n] of integer);

Var i, j, temp : integer ;

Begin

1 For i := 2 to n do

2 For j := n downto i do

3 If A[j-1] > A[j] then

Begin

4 temp := A[j-1] ;

5 A[j-1] := A[j] ;

6 A[j] := temp ;

End ;

End ;

Ph© n tÝ ch :

- N lµ sè phÇ n tö - kÝ ch th­íc cña bµ i to¸ n. Mçi lÖ nh g¸ n tõ dßng 4 - > dßng

6 mÊ t 3 ®¬n vÞ thêi gian, theo qui t¾ c tÝ nh tæng sÏ lµ O(max(1,1,1) = O(1).

- Vßng If vµ For lång nhau, ta ph¶ i xÐ t tõ trong ra ngoµ i. §èi víi ®iÒ u kiÖ n

sau If ph¶ i kiÓ m tra O(1) thêi gian. Ta kh«ng ch¾ c th© n lÖ nh If tõ 4 - 6 cã thùc

hiÖ n hay kh«ng. V× xÐ t trong tr­êng hîp xÊ u nhÊ t nª n ta gi¶ thuyÕ t lµ c¸ c lÖ nh tõ

4 - 6 ®Ò u cã thùc hiÖ n. VË y nhãm If tõ c¸ c lÖ nh 3 -6 lµ m mÊ t O(1) thêi gian.

- Ta xÐ t vßng lÆ p ngoµ i tõ 2 - 6. Nguyª n t¾ c chung cña vßng lÆ p: thêi gian

vßng lÆ p lµ tæng thêi gian mçi lÇ n lÆ p trong th© n vßng lË p. Ý t nhÊ t lµ O(1) cho

mçi lÇ n lÆ p khi chØ sè t¨ ng. Sè lÇ n lÆ p tõ 2 - 6 lµ n - i +1

VË y theo qui t¾ c tÝ ch : O((n - i +1), 1) lµ O(n -i +1).

- Ta xÐ t vßng ngoµ i cïng chøa c¸ c lÖ nh cña ch­¬ng tr× nh. LÖ nh 1 lµ m n-1

lÇ n, tèn n-1 ®¬n vÞ thêi gian. VË y tæng thêi gian ch¹ y cña ch­¬ng tr× nh bÞ chÆ n

d­íi bëi 1 thêi gian cè ®Þ nh lµ :

∑

=

− + = − n

i 2

(n i 1) n * (n 1)/ 2 tøc lµ O(n2

)

Tuy nhiª n kh«ng cã qui t¾ c ®Ç y ®ñ ®Ó ph© n tÝ ch ch­¬ng tr× nh.

Nãi chung thêi gian ch¹ y cña 1 lÖ nh hoÆ c 1 nhãm lÖ nh cã thÓ lµ 1 hµ m cña

kÝ ch th­íc c¸ c input hoÆ c 1 hay nhiÒ u biÕ n. Nh­ng chØ cã n - kÝ ch th­íc cña bµ i

to¸ n lµ th«ng sè cho phÐ p ®èi víi thêi gian ch¹ y cña ch­¬ng tr× nh.

6

3. Qui t¾c tÝ nh thêi gian ch¹y

a) Thêi gian ch¹ y cña mçi lÖ nh g¸ n, read, write cã gi¶ thiÕ t lµ O(1).

b) Thêi gian ch¹ y cña 1 d∙ y lÖ nh x¸ c ®Þ nh theo qui t¾ c tæng; nghÜ a lµ

thêi gian ch¹ y cña d∙ y lµ thêi gian lín nhÊ t cña 1 lÖ nh nµ o ®ã trong d∙ y lÖ nh.

c) Thêi gian ch¹ y lÖ nh If lµ thêi gian thùc hiÖ n lÖ nh ®iÒ u kiÖ n céng víi

thêi gian kiÓ m tra ®iÒ u kiÖ n.

Thêi gian thùc hiÖ n lÖ nh If cã cÊ u tróc If then eles lµ thêi gian kiÓ m

tra ®iÒ u kiÖ n céng víi thêi gian lín nhÊ t cña 1 trong 2 lÖ nh rÏ nh¸ nh true vµ

false.

d) Thêi gian thùc hiÖ n vßng lÆ p lµ tæng thêi gian thùc hiÖ n th© n vßng lÆ p

vµ thêi gian kiÓ m tra kÕ t thóc vßng lÆ p.

e) Gäi thñ tôc:NÕ u ch­¬ng tr× nh cã c¸ c thñ tôc vµ kh«ng cã thñ tôc nµ o

lµ ®Ö qui th× ta cã thÓ tÝ nh thêi gian ch¹ y cïng mét lóc, b¾ t ®Ç u tõ c¸ c thñ tôc

kh«ng gäi ®Õ n c¸ c thñ tôc kh¸ c. TÊ t nhiª n ph¶ i cã Ý t nhÊ t 1 thñ tôc nh­ vË y trong

tr­êng hîp nµ y, nÕ u kh«ng th× ph¶ i cã thñ tôc ®Ö qui. Sau ®ã ta cã thÓ ®¸ nh gi¸

thêi gian ch¹ y cña c¸ c thñ tôc cã gäi, ®Õ n c¸ c thñ tôc kh«ng chøa lêi gäi ®∙ ®­îc

®¸ nh gi¸ . Cø nh­ thÕ ta l¹ i ®¸ nh gi¸ thêi gian ch¹ y cña c¸ c thñ tôc cã lêi gäi ®Õ n

c¸ c thñ tôc ®∙ ®¸ nh gi¸ , nghÜ a lµ mçi thñ tôc ®­îc ®¸ nh gi¸ sau khi ®¸nh gi¸ hÕ t

c¸ c thñ tôc mµ ®­îc nã gäi.

NÕ u cã thñ tôc ®Ö qui th× kh«ng thÓ t× m ®­îc thø tù cña tÊ t c¶ c¸ c thñ tôc

sao cho mçi thñ tôc chØ gäi ®Õ n c¸ c thñ tôc ®∙ ®¸ nh gi¸ . Khi ®ã ta ph¶ i lË p 1 liª n

hÖ gi÷a mçi thñ tôc ®Ö qui víi 1 hµ m thêi gian ch­a biÕ t T(n) trong ®ã n lµ kÝ ch

th­íc cña ®èi sè cña thñ tôc. Lóc ®ã ta cã thÓ nhË n ®­îc sù truy håi ®èi víi T(n),

nghÜ a lµ 1 ph­¬ng tr× nh diÔ n t¶ T(n) qua c¸ c T(k) víi c¸ c gi¸ trÞ k kh¸ c nhau.

VÝ dô : XÐ t ch­¬ng tr× nh ®Ö qui tÝ nh n giai thõa (n!), trong ®ã n lµ kÝ ch

th­íc cña hµ m nª u trª n.

Function Fact (n:integer) : LongInt ;

Begin

1 If n <= 1 then

2 Fact := 1

Else

3 Fact := n*fact (n-1)

End ;

Ph© n tÝ ch:

Ta ký hiÖ u T(n) lµ thêi gian ch¹ y ®Ó tÝ nh hµ m Fact(n).

Thêi gian ch¹ y ®èi víi c¸ c dßng 1, 2 lµ O(1) vµ ®èi víi dßng 3 lµ O(1) +

T(n-1). VË y víi c¸ c h» ng c, d nµ o ®ã ta cã ph­¬ng tr× nh:

7

c + T(n-1) nÕ u n > 1

T(n) =

d nÕ u n ≤ 1

Gi¶ i ph­¬ng tr× nh :

Gi¶ sö n > 2, ta cã thÓ khai triÓ n T(n-1) trong c«ng thøc :

T(n) = 2.c + T(n-2) nÕ u n > 2

Sau ®ã ta l¹ i thay T(n-2) = c + T(n-3) ta ®­îc.

T(n) = 3.c + T(n-3) nÕ u n > 3

.....

T(n) = i.c + T(n-i) nÕ u n > i

Cuèi cïng ta thay i = n - 1, ta ®­îc

T(n) = c(n-1) + T(1) = c(n-1) + d

KÕ t luË n T(n) lµ O(n).

V. sù ph©n líp c¸c thuËt to¸n :

Nh­ ®∙ ®­îc chó ý ë trªn, hÇu hÕt c¸c thuËt to¸n ®Òu cã mét tham sè chÝ nh lµ

N, Th«ng th­êng ®ã lµ sè l­îng c¸ c phÇ n tö d÷ liÖ u ®­îc xö lý mµ ¶ nh h­ëng rÊ t

nhiÒ u tíi thêi gian ch¹ y. Tham sè N cã thÓ lµ bË c cña 1 ®a thøc, kÝ ch th­íc cña 1

tË p tin ®­îc s¾ p xÕ p hay t× m kiÕ m, sè nót trong 1 ®å thÞ ...HÇ u hÕ t tÊ t c¶ thuË t to¸n

trong bµ i gi¶ ng nµ y cã thêi gian ch¹ y tiÖ m cË n tíi 1 trong c¸ c hµ m sau :

1. HÇ u hÕ t tÊ t c¶ c¸ c chØ thÞ cña c¸c ch­¬ng tr× nh ®Ò u ®­îc thùc hiÖ n mét

lÇ n hay nhiÒ u nhÊ t chØ mét vµ i lÇ n. NÕ u tÊ t c¶ c¸c chØ thÞ cña cïng 1 ch­¬ng tr× nh

cã tÝ nh chÊ t nµ y th× chóng ta sÏ nãi r» ng thêi gian ch¹ y cña nã lµ h» ng sè. §iÒ u

nµ y hiÓ n nhiª n lµ môc tiª u phÊ n ®Ê u ®Ó ®¹ t ®­îc trong viÖ c thiÕ t kÕ thuË t to¸ n.

2. logN

Khi thêi gian ch¹ y cña ch­¬ng tr× nh lµ logarit, tøc lµ thêi gian ch¹ y

ch­¬ng tr× nh tiÕ n chË m khi N lín dÇ n. Thêi gian ch¹ y lo¹ i nµ y xuÊ t hiÖ n trong

c¸ c ch­¬ng tr× nh mµ gi¶ i 1 bµ i to¸ n lín b» ng c¸ ch chuyÓ n nã thµ nh bµ i to¸ n nhá

h¬n, b» ng c¸ ch c¾ t bá kÝ ch th­íc bít 1 h» ng sè nµ o ®ã. Víi môc ®Ý ch cña chóng

ta, thêi gian ch¹ y cã ®­îc xem nh­ nhá h¬n 1 h» ng sè "lín". C¬ sè cña logarit

lµ m thay ®æi h» ng sè ®ã nh­ng kh«ng nhiÒ u: Khi n lµ 1000 th× logN lµ 3 nÕ u c¬

sè lµ 10; lµ 10 nÕ u c¬ sè lµ 2 ; khi N lµ 1000000, logN ®­îc nh© n gÊ p ®«i. BÊ t cø

khi nµ o N ®­îc nh© n gÊ p ®«i, logN ®­îc t¨ ng lª n thª m mét h» ng sè, nh­ng logN

kh«ng ®­îc nh© n gÊ p ®«i tíi khi N t¨ ng tíi N2

.

3. N

Khi thêi gian ch¹ y cña ch­¬ng tr× nh lµ tuyÕ n tÝ nh, nãi chung ®© y lµ

tr­êng hîp mµ mét sè l­îng nhá c¸c xö lý ®­îc lµ m cho mçi phÇ n tö d÷ liÖu nhËp.

{

8

Khi N lµ 1.000.000 th× thêi gian ch¹ y còng cì nh­ vË y.

Khi N ®­îc nh© n gÊ p ®«i th× thêi gian ch¹ y còng ®­îc nh© n gÊ p ®«i.

§© y lµ t× nh huèng tèi ­u cho 1 thuË t to¸ n mµ ph¶ i xö lý N d÷ liÖ u nhË p (hay s¶ n

sinh ra N d÷ liÖ u xuÊ t).

4. NlogN

§© y lµ thêi gian ch¹ y t¨ ng dÇ n lª n cho c¸ c thuË t to¸ n mµ gi¶ i 1 bµ i to¸ n

b» ng c¸ ch t¸ ch nã thµ nh c¸ c bµ i to¸ n con nhá h¬n, kÕ ®Õ n gi¶ i quyÕ t chóng 1

c¸ ch ®éc lË p vµ sau ®ã tæ hîp c¸ c lêi gi¶ i. Bëi v× thiÕ u 1 tÝ nh tõ tèt h¬n (cã lÏ lµ

"tuyÕ n tÝ nh logarit" ?), chóng ta nãi r» ng thêi gian ch¹ y cña thuË t to¸ n nh­ thÕ lµ

"NlogN".

Khi N lµ 1000000, NlogN cã lÏ kho¶ ng 6 triÖ u.

Khi N ®­îc nh© n gÊ p ®«i, thêi gian ch¹ y bÞ nh© n lª n nhiÒ u h¬n gÊ p ®«i

(nh­ng kh«ng nhiÒ u l¾ m).

5. N2

Khi thêi gian ch¹ y cña 1 thuË t to¸ n lµ bËc hai, tr­êng hîp nµ y chØ cã ý

nghÜ a thùc tÕ cho c¸ c bµ i to¸ n t­¬ng ®èi nhá. Thêi gian b× nh ph­¬ng th­êng t¨ ng

lª n trong c¸ c thuË t to¸ n mµ xö lý tÊ t c¶ c¸ c cÆ p phÇ n tö d÷ liÖ u (cã thÓ lµ 2 vßng

lÆ p lång nhau).

Khi N lµ 1000 th× thêi gian ch¹ y lµ 1000000.

Khi N ®­îc nh© n ®«i th× thêi gian ch¹ y t¨ ng lª n gÊ p 4 lÇ n.

6. N3

T­¬ng tù, mét thuË t to¸ n mµ xö lý mét bé 3 cña c¸ c phÇ n tö d÷ liÖ u (cã

lÏ 3 vßng lÆ p lång nhau) cã thêi gian ch¹ y bË c 3 vµ còng chØ cã ý nghÜ a thùc tÕ

trong c¸ c bµ i to¸ n nhá.

Khi N lµ 100 th× thêi gian ch¹ y lµ 1.000.000.

Khi N ®­îc nh© n ®«i th× thêi gian ch¹ y t¨ ng lª n gÊ p 8 lÇ n.

7. 2n

Mét sè Ý t thuË t to¸ n cã thêi gian ch¹ y lòy thõa l¹ i thÝ ch hîp trong 1 sè

tr­êng hîp thùc tÕ , mÆ c dï c¸ c thuË t to¸ n nh­ thÕ lµ "sù Ð p buéc th« b¹ o" ®Ó gi¶ i

bµ i to¸ n.

Khi N lµ 20 th× thêi gian ch¹ y xÊ p xØ lµ 1.000.000

Khi N lµ gÊ p 2 th× thêi gian ch¹ y ®­îc n© ng lª n lòy thõa 2.

Thêi gian ch¹ y cña 1 ch­¬ng tr× nh cô thÓ ®«i khi lµ mét h» ng sè nh© n

víi c¸ c sè h¹ ng nãi trª n céng thª m mét sè h¹ ng nhá h¬n. C¸ c gi¸ trÞ cña h» ng sè

vµ c¸ c sè h¹ ng phô thuéc vµ o c¸ c kÕ t qu¶ cña sù ph© n tÝ ch vµ c¸c chi tiÕ t cµ i ®Æ t.

HÖ sè cña h» ng sè liª n quan tíi sè chØ thÞ bª n trong vßng lÆ p : ë 1 tÇ ng tïy ý cña

9

thiÕ t kÕ thuË t to¸n th× ph¶ i cÈ n thË n giíi h¹ n sè chØ thÞ nh­ thÕ . Víi N lín th× c¸c

h» ng sè ®ãng vai trß chñ chèt, víi N nhá th× c¸ c sè h¹ ng cïng ®ãng gãp vµ o vµ

sù so s¸ nh thuË t to¸ n sÏ khã kh¨ n h¬n. Ngoµ i nh÷ng hµ m võa nãi trª n còng cßn

cã 1 sè hµ m kh¸ c, vÝ dô nh­ 1 thuË t to¸ n víi N2

phÇ n tö d÷ liÖ u nhË p mµ cã thêi

gian ch¹ y lµ bË c 3 theo N th× sÏ ®­îc ph© n líp nh­ 1 thuË t to¸ n N3/2. Mét sè

thuË t to¸ n cã 2 giai ®o¹ n ph© n t¸ ch thµ nh c¸ c bµ i to¸ n con vµ cã thêi gian ch¹ y

xÊ p xØ víi Nlog2

N.

VI. c¸c c«ng thøc truy håi c¬ së :

PhÇ n lín c¸ c thuË t to¸ n ®Ò u dùa trª n viÖ c ph© n r∙ ®Ö qui mét bµ i to¸ n lín

thµ nh c¸ c bµ i to¸ n nhá h¬n, råi dïng c¸ c lêi gi¶ i cña c¸ c bµ i to¸ n nhá ®Ó gi¶ i bµ i

to¸ n ban ®Ç u. Thêi gian ch¹ y cña c¸ c thuË t to¸ n nh­ thÕ ®­îc x¸ c ®Þ nh bëi kÝ ch

th­íc vµ sè l­îng c¸ c bµ i to¸ n con vµ gi¸ ph¶ i tr¶ cña sù ph© n r∙ . Trong phÇ n

nµ y ta quan s¸ t c¸ c ph­¬ng ph¸ p c¬ së ®Ó ph© n tÝ ch c¸ c thuË t to¸ n nh­ thÕ vµ

tr× nh bµ y mét vµ i c«ng thøc chuÈ n th­êng ®­îc ¸ p dông trong viÖ c ph© n tÝ ch

nhiÒ u thuË t to¸ n.

TÝ nh chÊ t rÊ t tù nhiª n cña 1 ch­¬ng tr× nh ®Ö qui lµ thêi gian ch¹ y cho d÷

liÖ u nhË p cã kÝ ch th­íc N sÏ phô thuéc vµ o thêi gian ch¹ y cho c¸ c d÷ liÖ u nhË p

cã kÝ ch th­íc nhá h¬n : ®iÒ u nµ y ®­îc diÔ n dÞ ch thµ nh 1 c«ng thøc to¸ n häc gäi

lµ quan hÖ truy håi. C¸ c c«ng thøc nh­ thÕ m« t¶ chÝ nh x¸ c tÝ nh n¨ ng cña c¸ c

thuË t to¸ n t­¬ng øng, do ®ã ®Ó cã ®­îc thêi gian ch¹ y chóng ta ph¶ i gi¶ i c¸ c bµ i

to¸ n truy håi. B© y giê chóng ta chó ý vµ o c¸ c c«ng thøc chø kh«ng ph¶ i c¸ c

thuË t to¸ n.

C«ng thøc 1 :

C«ng thøc nµ y th­êng dïng cho c¸ c ch­¬ng tr× nh ®Ö qui mµ cã vßng lÆ p

duyÖ t qua d÷ liÖ u nhË p ®Ó bá bít 1 phÇ n tö.

Cn = Cn-1 + n, víi n >= 2 vµ C1 = 1

Chøng minh :

Cn kho¶ ng n2

/2. §Ó gi¶ i 1 c«ng thøc truy håi nh­ trª n, chóng ta lÇ n l­ît ¸ p

dông chÝ nh c«ng thøc ®ã nh­ sau :

Cn = Cn-1 + n

= Cn-2 + (n-1) + n

= ...

= C1 + 2 + ... + (n-2) + (n-1) + n

= 1 + 2 + ... + n

= n(n+1)/2

10

C«ng thøc 2 :

C«ng thøc nµ y dïng cho ch­¬ng tr× nh ®Ö qui mµ chia d÷ liÖ u nhË p thµ nh 2

phÇ n trong mçi b­íc.

Cn = Cn/2 + 1, víi n >= 2 vµ C1 = 0

Chøng minh :

Cn kho¶ ng logn. Ph­¬ng tr× nh nµ y v« nghÜ a trõ phi n ch½ n hay chóng ta gi¶

sö r» ng n/2 lµ phÐ p chia nguyª n : b© y giê chóng ta gi¶ sö r» ng n = 2m ®Ó cho

c«ng thøc lu«n lu«n cã nghÜ a. Chóng ta viÕ t nh­ sau :

1 2 2 C m = C m−1 +

2 2 = C m−2 +

3 2 = C m−3 +

= ......

= C m−m + m 2

= m = log n

C«ng thøc chÝ nh x¸ c cho n tæng qu¸ t th× phô thuéc vµ o biÓ u diÔ n nhÞ ph© n

cña n, nãi chung Cn kho¶ ng logn víi mäi n.

C«ng thøc 3 :

C«ng thøc nµ y dïng cho ch­¬ng tr× nh ®Ö qui mµ chia ®«i d÷ liÖ u nhË p

nh­ng cã thÓ kiÓ m tra mçi phÇ n tö cña d÷ liÖ u nhË p.

Cn = Cn/2 + n, víi n >= 2 vµ C1 = 0

Chøng minh :

Cn kho¶ ng 2n. T­¬ng tù trª n, c«ng thøc nµ y chÝ nh lµ tæng n + n/2 + n/4 + ...

(dÜ nhiª n ®iÒ u nµ y chØ chÝ nh x¸ c khi n lµ lòy thõa cña 2).

NÕ u d∙ y lµ v« h¹ n, th× ®© y lµ 1 chuçi h× nh häc ®¬n gi¶ n mµ ®­îc ­íc l­îng

chÝ nh x¸ c lµ 2n. Trong tr­êng hîp tæng qu¸ t lêi gi¶ i chÝ nh x¸ c phô thuéc vµ o

biÓ u diÔ n nhÞ ph© n cña n.

C«ng thøc 4 :

C«ng thøc nµ y dïng cho ch­¬ng tr× nh ®Ö qui mµ duyÖ t tuyÕ n tÝ nh xuyª n

qua d÷ liÖ u nhË p, tr­íc, trong, hay sau khi d÷ liÖ u nhË p ®­îc chia ®«i.

Cn = 2Cn/2 + n, víi n >= 2 vµ C1 = 0

Chøng minh :

Cn kho¶ ng nlogn. C«ng thøc nµ y ¸ p dông cho nhiÒ u thuË t to¸ n theo ph­¬ng

ph¸ p "chia ®Ó trÞ ".

11

2 2 2

1 m

C m = C m− +

1

2 2 1

1

2 2 = + −

−

m

m

m

C m C

1 1

2 2

2

2 = + + −

−

m

C m

m

C

m m

m m

= + −

−

2

2

= C + m = m 2

0

⇒ C m n n m

n = 2 = log

Lêi gi¶ i cho c«ng thøc nµ y rÊ t gièng nh­ trong c«ng thøc 2, nh­ng ph¶ i

chia 2 vÕ cña c«ng thøc cho 2n

trong b­íc thø hai.

C«ng thøc 5 :

C«ng thøc nµ y dïng cho ch­¬ng tr× nh ®Ö qui mµ t¸ ch d÷ liÖ u thµ nh 2 phÇ n.

Cn = 2Cn/2 + 1, víi n >= 2 vµ C1 = 0

Chøng minh :

Cn kho¶ ng 2n. Chøng minh gièng nh­ c«ng thøc 4.

C¸ c biÕ n d¹ ng cña nh÷ng c«ng thøc nµ y ch¼ ng h¹ n nh­ ®iÒ u kiÖ n kh¸ c nhau

hay c¸ c sè h¹ ng thª m vµ o kh¸ c nhau mét Ý t, cã thÓ ­íc l­îng b» ng c¸ ch dïng

còng mét kü thuË t nh­ trª n. MÆ c dï vË y, chóng ta còng nª n chó ý 1 quan hÖ truy

håi d­êng nh­ t­¬ng tù víi mét quan hÖ ®∙ biÕ t th× ®«i khi l¹ i khã gi¶ i h¬n rÊ t

nhiÒ u.

VII. gi¶i ph­¬ng tr× nh truy håi :

§Ó gi¶ i ph­¬ng tr× nh truy håi cã nhiÒ u c¸ ch gi¶ i kh¸ c nhau, ë ®© y chóng t«i

tr× nh bµ y c¸ ch gi¶ i ph­¬ng tr× nh truy håi b» ng c¸ ch truy vÒ ph­¬ng tr× nh ®Æ c

tr­ng. Chóng t«i dïng c¸ ch gi¶ i nµ y ®Ó viÕ t ch­¬ng tr× nh gi¶ i tù ®éng ph­¬ng

tr× nh truy håi.

a) Ta xÐ t ph­¬ng tr× nh truy håi thuÇ n nhÊ t tuyÕ n tÝ nh víi c¸ c hÖ sè kh«ng

®æi sau ®© y :

a0tn + a1tn-1 + ... + aktn-k = 0 (VII.1)

trong ®ã ti

(i=n, n-1,..., n-k) lµ c¸ c È n sè cÇ n t× m.

TuyÕ n tÝ nh v× c¸ c ti

chØ cã bË c nhÊ t, thuÇ n nhÊ t v× vÕ ph¶ i b» ng kh«ng vµ

c¸ c hÖ sè a0, a1,..., ak lµ kh«ng ®æi v× kh«ng phô thuéc vµ o n.

12

Sau khi gi¶ thiÕ t tn = xn

ta ®­a (VII.1) vÒ d¹ ng:

a0xn

+ a1xn-1

+...+ akxn-k = 0

hay xn-k(a0xk

+ a1xk-1

+...+ ak) = 0

Râ rµ ng x = 0 lµ nghiÖ m hiÓ n nhiª n, nh­ng ta quan t© m nghiÖ m ph­¬ng

tr× nh a0xk

+ a1xk-1

+...+ ak = 0 (VII.2) vµ ®© y chÝ nh lµ ph­¬ng tr× nh ®Æ c tr­ng bË c

k cña ph­¬ng tr× nh truy håi (VII.1)

Gi¶ sö r1, r2,..., rk lµ k nghiÖ m cña ph­¬ng tr× nh (VII.2) vµ chóng kh¸ c nhau

(cã thÓ phøc). DÔ dµ ng kiÓ m tra:

t c r

n

i

k

i n ∑ i =

= 1

Víi c1, c2,..., ck lµ c¸ c h» ng x¸ c ®Þ nh tõ k ®iÒ u kiÖ n ban ®Ç u.

VÝ dô 1 :

XÐ t ph­¬ng tr× nh truy håi:

t n − 3t n−1 − 4t n−2 = 0

§iÒ u kiÖ n ban ®Ç u : t0 = 1 ; t1 =1

Ph­¬ng tr× nh ®Æ c tr­ng t­¬ng øng cña nã lµ :

x2

- 3x - 4 = 0

cã nghiÖ m b» ng -1 vµ 4. VË y nghiÖ m tæng qu¸ t lµ :

1( 1) 2 (4) n n

t n c c = − +

Theo ®iÒ u kiÖ n ban ®Ç u (khi n =0 vµ n = 1) ta cã :

c1 + c2 = 1 = t0

- c1 + 4c2 =1

VË y c1 = 3/5, c2 = 2/5. Ta ®­îc tn = - [4n

- (-1)

n

] /5

VÝ dô 2 : (ph­¬ng tr× nh Fibonacci)

tn = tn-1 + tn-2 n ≥ 2

§iÒ u kiÖ n : t0 = 0, t1 = 1

ViÕ t l¹ i ph­¬ng tr× nh trª n :

tn - tn-1 - tn -2 = 0

Ph­¬ng tr× nh ®Æ c tr­ng t­¬ng øng :

x2

- x -1 = 0

13

NghiÖ m : r (1 5)/ 2 1 = + , r (1 5)/ 2 2 = −

NghiÖ m tæng qu¸ t : tn = c1r1

n + c2r2

n

Tõ ®iÒ u kiÖ n ban ®Ç u :

c1 + c2 = 0 (n = 0)

r1c1 + r2c2 = 1 (n =1)

Ta cã c 1/ 5 1 = ,

c 1/ 5 2 = −

VË y: tn = (r n r n )/ 5 1 − 2

Gi¶ sö c¸ c nghiÖ m ph­¬ng tr× nh ®Æ c tr­ng lµ kh«ng ph© n biÖ t, P(x) lµ 1 ®a

thøc.

P(x) = a0xk

+ a1xk-1

+ ... + ak

vµ r lµ nghiÖ m kÐ p.

Víi mçi r > k, ta xÐ t ®a thøc bË c n ®­îc x¸ c ®Þ nh nh­ sau :

h(x) = x [xn-k P(x)] = a0nxn

+ a1(n-1)xn-1

+ ... + ak(n-k)xn-k

§Æ t q(x) lµ ®a thøc tháa ®iÒ u kiÖ n

P(x) = (x-r)2

q(x)

Ta cã :

h(x) = x[(x-r)2

xn-k q(x)] = x[2(x-r)xn-k q(x) + (x-r)2

[xn-k q(x)]]

Râ rµ ng h(r) = 0, do ®ã

a0nrn

+ a1(n-1)xn-1

+ ... + ak(n-k) rn-k = 0

NghÜ a lµ tn = nrn còng lµ nghiÖ m cña (5.13). Tæng qu¸ t h¬n, nÕ u nghiÖ m r

trïng nhau m lÇ n (r béi m) th×

tn = rn

, tn = nrn

, tn = n2

r

n

,...., tn = nm-1

r

n

còng lµ c¸ c nghiÖ m cña (5.13). NghiÖ m tæng qu¸ t (nghiÖ m chung) lµ tæ hîp

tuyÕ n tÝ nh cña c¸ c nghiÖ m riª ng nµ y vµ nghiÖ m riª ng kh¸c cña ph­¬ng tr× nh ®Æ c

tr­ng. K h» ng ®­îc x¸ c ®Þ nh tõ c¸ c ®iÒ u kiÖ n ban ®Ç u.

VÝ dô 3 : XÐ t ph­¬ng tr× nh

tn = 5tn-1 - 8tn-2 + 4tn-3 n ≥ 3

víi c¸ c ®iÒ u kiÖ n t0 = 0, t1 = 1, t2 = 2

Ta viÕ t l¹ i ph­¬ng tr× nh:

tn - 5tn-1 + 8tn-2 - 4tn-3 = 0

vµ ph­¬ng tr× nh ®Æ c tr­ng t­¬ng øng lµ :

x3

- 5x2

+ 8x - 4 = 0

hay (x-1) (x-2)2

= 0

14

Ta cã c¸ c nghiÖ m 1 (cã béi 1), 2 (cã béi 2). VË y nghiÖ m tæng qu¸ t lµ :

tn = c11n

+ c22n + c3n2n

C¸ c ®iÒ u kiÖ n ban ®Ç u cho tr­íc lµ :

c1 + c2 = 0 khi n = 0

c1 + 2c2 + 2c3 = 1 khi n = 1

c1 + 4c2 + 8c3 = 2 khi n = 2

Tõ ®© y ta t× m ra c1 = -2, c2 = 2, c3 = -1/2. VË y tn = 2n+1

- n2n-1

- 2

b) Ph­¬ng tr× nh truy håi kh«ng thuÇ n nhÊ t:

Ta xÐ t ph­¬ng tr× nh cã d¹ ng sau :

a0tn + a1tn-1 + ... + aktn-k = bn

P(n) (VII.3)

Trong ®ã vÕ tr¸ i nh­ trong (VII.1), vÕ ph¶ i lµ bn

P(n) víi b lµ h» ng vµ P(n) lµ

®a thøc.

VÝ dô 4 :

tn - 2tn-1 = 3n

th× b = 3 vµ P(n) = 1 lµ ®a thøc bË c 0.

B» ng phÐ p biÕ n ®æi ®¬n gi¶ n ta cã thÓ chuyÓ n vÝ dô nµ y vÒ d¹ ng (VII.1) lµ

ph­¬ng tr× nh truy håi thuÇ n nhÊ t. Tr­íc hÕ t ta nh© n 2 vÕ cho 3 ta ®­îc :

3tn - 6tn-1 = 3n+1 (1)

Sau ®ã ta thay n ra n + 1 trong ph­¬ng tr× nh ban ®Ç u:

tn+1 - 2tn = 3n+1 (2)

Cuèi cïng, lÊ y (2) - (1) , ta thu ®­îc (cã cïng vÕ ph¶ i 3n+1

), ta ®­îc:

tn+1 - 5tn + 6tn-1 = 0

§Õ n ®© y ta cã thÓ gi¶ i ph­¬ng tr× nh ®∙ tr× nh bµ y ë môc a.

Ph­¬ng tr× nh ®Æ c tr­ng cña nã lµ :

x2

- 5x + 6 = 0

hay (x-2) (x-3) = 0

Trùc gi¸ c cho ta thÊ y r» ng thµ nh phÇ n (x-2) t­¬ng øng víi vÕ tr¸ i

ph­¬ng tr× nh ban ®Ç u; cßn (x-3) lµ biÓ u hiÖ n kÕ t qu¶ cña viÖ c biÕ n ®æi vµ trõ vÕ

ph¶ i.

VÝ dô 5 :

tn - 2tn-1 = (n+5)3n

15

Sù biÕ n ®æi cã phøc t¹ p nh­ sau :

- Nh© n 2 vÕ cho 9

- Thay n bëi n+2

- Thay n bëi n+1,sau ®ã nh© n cho -6

- Ta ®­îc kÕ t qu¶ :

9tn - 18tn-1 = (n + 5) 3n+2

tn+2 - 2tn+1 = (n + 7) 3n+2

-6tn+1 + 12tn = -6(n + 6) 3n+1

Céng 3 ph­¬ng tr× nh l¹ i ta ®­îc :

tn+2 - 8tn+1 + 21tn - 18tn-1 = 0

Ph­¬ng tr× nh ®Æ c tr­ng.

x2

- 8x2

+ 21x - 18 = 0 hay (x-2) (x-3)2

= 0

Ta l¹ i thÊ y (x-2) t­¬ng øng vÕ tr¸ i ph­¬ng tr× nh ban ®Ç u vµ (x-3)2

lµ kÕ t qu¶

cña sù biÕ n ®æi.

Nh­ vË y chóng ta cã thÓ nãi r» ng ®Ó gi¶ i ph­¬ng tr× nh truy håi kh«ng thuÇ n

nhÊ t cã d¹ ng (VII.3) ta chØ cÇ n gi¶ i ph­¬ng tr× nh ®Æ c tr­ng sau.

(a0xk

+ a1xk-1 + ... + ak) (x-b)d+1

= 0 (VII.4)

VÝ dô 6 : (bµ i to¸ n th¸ p Hµ Néi)

Ph­¬ng tr× nh truy håi cho bµ i to¸ n chuyÓ n n ®Ü a nµ y cã d¹ ng:

1 nÕ u n = 1

tn = { 2tn-1 + 1 nÕ u n > 1

hay tn = 2tn-1 + 1, n > 1 víi t0 = 0

Ta viÕ t l¹ i ph­¬ng tr× nh :

tn - 2tn-1 = 1

Vµ thÊ y nã cã d¹ ng (VII.3) víi b = 1, P(n) = 1 bË c 0

Ph­¬ng tr× nh ®Æ c tr­ng lµ (x-2) (x-1) = 0

VË y : tn =c11n

+ c22n

. Tõ t0 = 0 ®Ó t× m t1 ta viÕ t :

t1 = 2to + 1 = 1

VË y c1 + c2 = 0, n = 0

c1 + 2c2 = 1, n = 1

Suy ra c1 = -1, c2 = 1. VË y tn = 2n

-1

Ta nhË n thÊ y tõ tn = c11n

+ c22n

còng cã thÓ kÕ t luË n tn cã O(2n

).