intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

thiết kế và đánh giá thuật toán - trần tuấn minh -2

Chia sẻ: Muay Thai | Ngày: | Loại File: PDF | Số trang:16

Thêm vào BST
Báo xấu
106
lượt xem 14
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phân tích thuật toán Khi xây dựng được thuật toán để giải bài toán thì có hằng loạt vấn đề được đặt ra để phân tích. Thường là các vấn đề sau : - Yêu cầu về tính đúng đắn của thuật toán, thuật toán có cho lời giải đúng của bài toán hay không ? - Tính đơn giản của thuật toán. Thường ta mong muốn có được một thuật toán đơn giản, dễ hiểu, dễ lập trình. Đặc biệt là những thuật toán chỉ dùng một vài lần ta cần coi trọng tính chất này, vì công sức và...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: thiết kế và đánh giá thuật toán - trần tuấn minh -2

  1. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 17 - IV. Phaân tích thuaät toaùn Khi xaây döïng ñöôïc thuaät toaùn ñeå giaûi baøi toaùn thì coù haèng loaït vaán ñeà ñöôïc ñaët ra ñeå phaân tích. Thöôøng laø caùc vaán ñeà sau : - Yeâu caàu veà tính ñuùng ñaén cuûa thuaät toaùn, thuaät toaùn coù cho lôøi giaûi ñuùng cuûa baøi toaùn hay khoâng ? - Tính ñôn giaûn cuûa thuaät toaùn. Thöôøng ta mong muoán coù ñöôïc moät thuaät toaùn ñôn giaûn, deã hieåu, deã laäp trình. Ñaëc bieät laø nhöõng thuaät toaùn chæ duøng moät vaøi laàn ta caàn coi troïng tính chaát naøy, vì coâng söùc vaø thôøi gian boû ra ñeå xaây döïng thuaät toaùn thöôøng lôùn hôn raát nhieàu so vôùi thôøi gian thöïc hieän noù. - Yeâu caàu veà khoâng gian : thuaät toaùn ñöôïc xaây döïng coù phuø hôïp vôùi boä nhôù cuûa maùy tính hay khoâng ? - Yeâu caàu veà thôøi gian : Thôøi gian chaïy cuûa thuaät toaùn coù nhanh khoâng ? Moät baøi toaùn thöôøng coù nhieàu thuaät toaùn ñeå giaûi, cho neân yeâu caàu moät thuaät toaùn daãn nhanh ñeán keát quaû laø moät ñoøi hoûi ñöông nhieân. ....... Trong phaàn naøy ta quan taâm chuû yeáu ñeán toác ñoä cuûa thuaät toaùn. Ta cuõng löu yù raèng thôøi gian chaïy cuûa thuaät toaùn vaø dung löôïng boä nhôù nhieàu khi khoâng caân ñoái ñöôïc ñeå coù moät giaûi phaùp troïn veïn. Chaúng haïn, thuaät toaùn saép xeáp noäi seõ coù thôøi gian chaïy nhanh hôn vì döõ lieäu ñöôïc löu tröû trong boä nhôù trong, vaø do ñoù khoâng phuø hôïp trong tröôøng hôïp kích thöôùc döõ lieäu lôùn. Ngöôïc laïi, caùc thuaät toaùn saép xeáp ngoaøi phuø hôïp vôùi kích thöôùc döõ lieäu lôùn vì döõ lieäu ñöôïc löu tröû chính ôû caùc thieát bò ngoaøi, nhöng khi ñoù toác ñoä laïi chaäm hôn. 1. Caùc böôùc trong quaù trình phaân tích ñaùnh giaù thôøi gian chaïy cuûa thuaät toaùn - Böôùc ñaàu tieân trong vieäc phaân tích thôøi gian chaïy cuûa thuaät toaùn laø quan taâm ñeán kích thöôùc döõ lieäu, seõ ñöôïc duøng nhö döõ lieäu nhaäp cuûa thuaät toaùn vaø quyeát Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn
  2. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 18 - ñònh phaân tích naøo laø thích hôïp. Ta coù theå xem thôøi gian chaïy cuûa thuaät toaùn laø moät haøm theo kích thöôùc cuûa döõ lieäu nhaäp. Neáu goïi n laø kích thöôùc cuûa döõ lieäu nhaäp thì thôøi gian thöïc hieän T cuûa thuaät toaùn ñöôïc bieåu dieãn nhö moät haøm theo n, kyù hieäu laø : T(n). - Böôùc thöù hai trong vieäc phaân tích ñaùnh giaù thôøi gian chaïy cuûa moät thuaät toaùn laø nhaân ra caùc thao taùc tröøu töôïng cuûa thuaät toaùn ñeå taùch bieät söï phaân tích vaø söï caøi ñaët. Bôûi vì ta bieát raèng toác ñoä xöû lyù cuûa maùy tính vaø caùc boä dòch cuûa caùc ngoân ngöõ laäp trình caáp cao ñeàu aûnh höôûng ñeán thôøi gian chaïy cuûa thuaät toaùn, nhöng nhöõng yeáu toá naøy aûnh höôûng khoâng ñoàng ñeàu vôùi caùc loïai maùy treân ñoù caøi ñaët thuaät toaùn, vì vaäy khoâng theå döïa vaøo chuùng ñeå ñaùnh giaù thôøi gian chaïy cuûa thuaät toaùn. Chaúng haïn ta taùch bieät söï xem xeùt coù bao nhieâu pheùp toaùn so saùnh trong moät thuaät toaùn saép xeáp khoûi söï xaùc ñònh caàn bao nhieâu micro giaây chaïy treân moät maùy tính cuï theå. Yeáu toá thöù nhaát döôïc xaùc ñònh bôûi tính chaát cuûa thuaät toaùn, coøn yeùu toá thöù hai ñöôïc xaùc ñònh bôûi tính naêng cuûa maùy tính. Ñieàu naøy cho ta thaáy raèng T(n) khoâng theå ñöôïc bieåu dieãn baèng giaây, phuùt...ñöôïc; caùch toát hôn laø bieåu dieãn theo soá caùc chæ thò trong thuaät toaùn. Ví duï : Xeùt : for(i = 1; i < n; i++) (1) for(j = 1; j < n; j++) (2) Kyù hieäu : T(n) laø thôøi gian thöïc hieän caâu leänh (2) : 1 1 2 3 ……. . . n-1 (2) n n n n T (n) = n 4 4n = (n − 1)n 1 2+ +L 3 ) ( n −1) la n - Böôùc thöù ba trong vieäc phaân tích ñaùnh giaù thôøi gian chaïy cuûa moät thuaät toaùn laø söï phaân tích veà maët toaùn hoïc vôùi muïc ñích tìm ra caùc giaù trò trung bình vaø tröôøng hôïp xaáu nhaát cho moãi ñaïi löôïng cô baûn. Chaúng haïn, khi saép xeáp moät daõy caùc phaàn töû, thôøi gian chaïy cuûa thuaät toaùn hieån nhieân coøn phuï thuoäc vaøo tính chaát cuûa döõ lieäu nhaäp nhö : * Daõy coù thöù töï thuaän. * Daõy coù thöù töï ngöôïc. * Caùc soá haïng cuûa daõy coù thöù töï ngaãu nhieân. 2. Caùc kyù hieäu tieäm caän a) Kyù hieäu O lôùn (big – oh) : Ñònh nghóa : Cho haøm f : N* ⎯⎯→ N* . Ta ñònh nghóa : O(f(n)) = {t : N* ⎯⎯→ N* | ∃ c∈ R+ , ∃n0 ∈ N, ∀ n ≥ n0 , t(n) ≤ cf(n)} O(f(n)) goïi laø caáp cuûa f(n). Vôùi t : N* ⎯⎯→ N* t(n) ∈ O(f(n)) ⇔ ∃ c∈ R+ , ∃n0 ∈ N, ∀ n ≥ n0 , t(n) ≤ cf(n) . Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn
  3. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 19 - Nhaän xeùt : a) t(n) ∈ O(t(n)) b) t(n) ∈ O(f(n)) ⇒ ∃ c∈ R+ , ∀ n ∈ N , t(n) ≤ cf(n) . Caùc tính chaát : Tính chaát 1 : Vôùi moïi haøm f : N* ⎯⎯→ N* : ⎧• f (n) 2 ∈ O(n 2 ) ⎪ f ( n) ∈ O ( n) ⇒ ⎨ ⎪• 2 f ( n) ∈ O(2 n ) ⎩ Tính chaát 2: a) f(n) ∈ O(g(n)) vaø g(n) ∈ O(h(n)) ⇒ f(n) ∈ O(h(n)). b) g(n) ∈ O(h(n)) ⇒ O(g(n)) ⊆ O(h(n)). Tính chaát 3: a) O(f(n)) = O(g(n)) ⇔ g(n) ∈ O(f(n)) vaø f(n) ∈ O(g(n)). b) O(f(n)) ⊂ O(g(n)) ⇔ f(n) ∈ O(g(n)) vaø g(n) ∉ O(f(n)). Tính chaát 4: f ( n) a) lim = c ≠ 0 ⇔ O(f(n)) = O(g(n)) n→∞ g ( n) f ( n) b) lim = 0 ⇒ O(f(n)) ⊂ O(g(n)) = O(g(n)± f(n)) n→∞ g ( n) Ví duï : - Haøm f(n) = 2n5 + 3n3 + 6n2 + 2 coù caáp O(n5 ) vì : 2n 5 + 3n 3 + 6n 2 + 2 = 2 ≠ 0. lim n5 n→∞ - Haøm f(n) = 2n laø O(n! ) vì : 2n = 0. lim n→∞ n ! - Haøm 2n+1 ∈ O(2n ) . b) Kyù hieäu Ω : Kyù hieäu naøy duøng ñeå chæ chaën döôùi cuûa thôøi gian chaïy cuûa thuaät toaùn Ta ñònh nghóa : Ω (f(n)) = {t : N ⎯⎯→ N* | ∃ c∈ R+ , ∃n0 ∈ N, ∀ n ≥ n0 , t(n) ≥ cf(n)} Tính chaát 6: Cho f, g : N ⎯⎯→ N* , Ta coù : f(n) ∈ O(g(n)) ⇔ g(n) ∈ Ω (f(n)). c) Kyù hieäu θ : Ñònh nghóa : θ(f(n)) = O(f(n)) ∩ Ω (f(n)). Tính chaát 7: f(n) ∈ θ (g(n)) ⇔ ∃ c,d∈ R+ , ∃n0 ∈ N, ∀ n ≥ n0 , cg(n) ≤ f(n) ≤ dg(n) . 3. Moät soá lôùp caùc thuaät toaùn Haàu heát caùc thuaät toaùn ñöôïc giôùi thieäu trong giaùo trình naøy tieäm caän tôùi moät trong caùc haøm sau : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn
  4. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 20 - (1) 1 : Neáu taát caû caùc chæ thò cuûa chöông trình ñeàu ñöôïc thöïc hieän chæ moät vaøi laàn vaø ta noùi thôøi gian chaïy cuûa noù laø haèng soá. (2) Logn : Khi thôøi gian chaïy cuûa chöông trình laø Logarit. Thôøi gian chaïy thuoäc loaïi naøy xuaát hieän trong caùc chöông trình maø giaûi 1 baøi toùan lôùn baèng caùch chuyeån noù thaønh 1 baøi toaùn nhoû hôn, baèng caùch caét boû kích thöôùc moät haèng soá naøo ñoù. Cô soá Logarit coù theå laøm thay ñoåi haèng soá ñoù nhöng khoâng nhieàu. (3) n : Khi thôøi gian chaïy cuûa chöông trình laø tuyeán tính. (4) nLogn : Thôøi gian chaïy thuoäc loaïi naøy xuaát hieän trong caùc chöông trình maø giaûi 1 baøi toaùn lôùn baèng caùch chuyeån noù thaønh caùc baøi toaùn nhoû hôn, keù ñeán giaûi quyeát chuùng 1 caùch ñoäc laäp, sau ñoù toå hôïp caùc lôøi giaûi. (5) n2 : Thôøi gian chaïy cuûa thuaät toaùn laø baäc 2, thöôøng laø xöû lyù caùc caëp phaàn töû döõ lieäu (coù theå laø 2 voøng laëp loàng nhau). Tröôøng hôïp naøy chæ coù yù nghóa thöïc teá khi baøi toaùn nhoû. (6) n3 : Moät thuaät toaùn xöû lyù boä ba caùc phaàn töû döõ lieäu (coù theå laø 3 voøng laëp loàng nhau) coù thôøi gian chaïy baäc 3. Tröôøng hôïp naøy chæ coù yù nghóa thöïc teá khi baøi toaùn nhoû. (7) . 2n : Sau ñaây laø caùc giaù trò xaáp xæ cuûa caùc haøm treân : n2 n3 2n n \ Haøm n lg n Nlgn 1 1 0 0 1 1 2 2 2 1 2 4 8 4 4 n 2 8 16 64 16 8 8 3 24 64 512 256 16 16 4 64 256 4096 65536 32 32 5 160 1024 32768 2.147.483.648 Deã thaáy raèng : O(1) ⊂ O(lg n) ⊂ O(n) ⊂ O(nlgn) ⊂ O(n2 ) ⊂ O(n3 ) ⊂ O(2n ). Caùc haøm loaïi : 2n, n!, nn thöôøng ñöôïc goïi laø caùc haøm loaïi muõ. thuaät toaùn vôùi thôøi gian chaïy coù caáp haøm loaïi muõ thì toác ñoä raát chaäm. Caùc haøm loaïi : n3, n2, nLog2 n, n, Log2 n thöôøng ñöôïc goïi laø caùc haøm loaïi ña thöùc. Thuaät toaùn vôùi thôøi gian chaïy coù caáp haøm ña thöùc thöôøng chaáp nhaän ñöôïc. Ghi chuù : Caùc haèng soá bò boû qua trong bieåu thöùc ñaùnh giaù ñoä phöùc taïp cuûa thuaät toaùn coù theå coù yù nghóa quan troïng trong öùng duïng cuï theå. Giaû söû thuaät toaùn 1 ñoøi hoûi thôøi gian laø C1n, coøn thuaät toaùn 2 ñoøi hoûi thôøi gian laø C2n2. Dó nhieân laø vôùi n ñuû lôùn thì thuaät toaùn 1 nhanh hôn thuaät toaùn 2. Nhöng vôùi n nhoû thì coù theå thuaät toaùn 1 nhanh hôn thuaät toaùn 2. Chaúng haïn, vôùi C1 = 200, C2 = 10, vaø vôùi n = 5, thì thuaät toaùn 1 ñoøi hoûi thôøi gian 1000, trong khi ñoù thuaät toaùn 2 chæ coù 250. Ví duï : Thuaät toaùn Choïn tröïc tieáp (Straight Selection) : SSS Saép xeáp taêng daàn daõy caùc khoùa : x[1],x[2],. . .,x[n]. YÙ töôûng : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn
  5. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 21 - - Böôùc i choïn phaàn töû nhoû nhaát cuûa daõy x[i],x[i+1],. . .,x[n], ñoåi choã phaàn töû nhoû nhaát naøy cho x[i]. - Laëp thao taùc naøy vôùi i = 1..n-1. Thuaät toaùn : 1 for (i =1;i
  6. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 22 - baøi toaùn con vaø giaù phaûi traû cuûa söï phaân raõ. Neân caùc thuaät toaùn ñeä qui coù thôøi gian chaïy phuï thuoäc vaøo thôøi gian chaïy cho caùc döõ lieäu nhaäp coù kích thöôùc nhoû hôn, ñieàu naøy ñöôïc dieãn dòch thaønh moät coâng thöùc toaùn hoïc goïi laø coâng thöùc truy hoài. Do ñoù, ñeå tính ñoä phöùc taïp cuûa thuaät toaùn, ta thöôøng phaûi giaûi caùc phöông trình truy hoài. Coù nhieàu caùch giaûi, ta nghieân cöùu caùc caùch thöôøng duøng sau. A. Phöông phaùp thay theá : Döïa vaøo daïng truy hoài cuûa phöông trình ñeå tính ñoä phöùc taïp cuûa thuaät toaùn döïc vaøo caùc kích thuôùc döõ lieäu nhoû hôn. Moät soá coâng thöùc thöôøng gaëp sau ñaây ñöôïc giaûi baèng phöông phaùp thay theá : Coâng thöùc 1: ⎧T + N ; N ≥ 2 TN = ⎨ N −1 ⎩1; N = 1 Coâng thöùc naøy thöôøng duøng cho caùc chöông trình ñeä qui maø coù voøng laëp duyeät qua döõ lieäu nhaäp ñeå boû bôùt 1 phaàn töû . TN = TN-1 + N = TN-2 + (N-1) +N = TN-23+ +(N-2) + (N-1) +N = . . . = 1+2+ . . . +N N ( N + 1) = . 2 Coâng thöùc 2: ⎧T N + 1; N ≥ 2 ⎪ TN = ⎨ 2 ⎪0; N = 1 ⎩ Coâng thöùc naøy thöôøng duøng cho caùc thuaät toaùn ñeä qui maø taïi moãi böôùc chia döõ lieäu nhaäp thaønh 2 phaàn . Giaû söû N = 2n , coù : T n = T n − 1 + 1 = T n − 2 + 2 = L = n. 2 2 2 Suy ra : TN = log2 N . Coâng thöùc 3: ⎧T N + N ; N ≥ 2 ⎪ TN = ⎨ 2 ⎪0; N = 1 ⎩ Coâng thöùc naøy thöôøng duøng cho caùc thuaät toaùn ñeä qui maø taïi moãi böôùc thöïc hieän, chia ñoâi döõ lieäu nhaäp nhöng coù kieåm tra moãi phaàn töû cuûa döõ lieäu nhaäp. NNN TN = N + ++ L ≅ 2N. 248 Coâng thöùc 4: ⎧2T N + 1; N ≥ 2 ⎪ TN = ⎨ 2 ⎪0; N = 1 ⎩ Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn
  7. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 23 - Coâng thöùc naøy thöôøng duøng cho caùc thuaät toaùn theo phöông phaùp chia ñeå trò. T2n = 2T2n −1 + 2 n T2n T2n −1 T2n − 2 = +1 = +1+1 = L = n 2n − 1 2n − 2 2n ⇒ T2n = n 2 n ⇒ TN = NLog 2 N B. Duøng phöông trình ñaëc tröng ñeå giaûi phöông trình truy hoài : B1) Phöông trình truy hoài tuyeán tính thuaàn nhaát vôùi caùc heä soá khoâng ñoåi : Xeùt phöông trình daïng : (1) a0 t n + a1 t n−1 + L + a k t n−k = 0 Trong ñoá caùc t i , i = n, n − 1,L , n − k laø caùc aån soá. Ñaët tn = Xn , ta ñöa (1) veà daïng : X n−k (a0 X k + a1 X k −1 + L + a k −1 X + a k ) = 0 (2) ⎡ X n−k = 0 ⇔⎢ ⎢a0 X k + a1 X k −1 + L + a k −1 X + a k = 0 ⎣ X = 0 hieån nhieân laø nghieäm cuûa (2), nhöng ta quan taâm ñeán nghieäm cuûa phöông trình : (3) p ( X ) = a 0 X k + a 1 X k −1 + L + a k −1 X + a k = 0 Phöông trình (3) goïi laø phöông trình ñaëc tröng baäc k cuûa phöông trình truy hoài (1) . TH1 : Taát caû caùc nghieäm cuûa (3 ) ñeàu laø nghieäm ñôn. Giaû söû raèng X 1 , X 2 ,L , X k laø caùc nghieäm ñôn cuûa (3), thì ta coù theå kieåm tra k ñöôïc t n = ∑ ci X in , vôùi c1, c2, …, ck laø caùc haèng xaùc ñònh töø k ñieàu kieän ban ñaàu i =1 laø nghieäm cuûa (3). TH2 : Phöông trình (3 ) coù nghieäm boäi. - Giaû söû u laø nghieäm keùp cuûa (3). Vôùi n > k, xeùt ña thöùc p baäc n : q ( X ) = a 0 nX n + a 1 (n − 1) X n −1 + L + a k ( n − k ) X n − k = X ( X n − k p ( X ))' Vì u laø nghieäm keùp cuûa (3), neân toàn taïi ña thöùc r thoûa : p( X ) = ( X − u ) 2 r ( X ) Khi ñoù : q ( X ) = X [ X n − k ( X − u ) 2 r ( X )]' = 0 Do ñoù : a 0 nu n + a 1 ( n − 1)u n −1 + L + a k (n − k )u n − k = 0 Töùc laø : tn = nun cuõng laø nghieäm cuûa (1). Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn
  8. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 24 - - Toång quaùt, neáu u laø nghieäm boäi m cuûa (3) thì : tn = u , nun, n2un, . . ., nm-1un cuõng laø nghieäm cuûa (1) n Khi ñoù toå hôïp tuyeán tính cuûa caùc nghieäm naøy vaø caùc nghieäm khaùc cuûa phöông trình ñaëc tröng (3) seõ laø nghieäm cuûa (1). Ví duï 1 : ⎧T (n) − 6T (n − 1) + 8T (n − 2) = 0 ⎪ ⎨T (0) = 1 ⎪T (1) = 2 ⎩ Xeùt phöông trình : T ( n) − 6T ( n − 1) + 8T ( n − 2) = 0 Ñaët : Xn = T(n) Ta coù : X n − 6 X n−1 + 8 X n−2 = 0 Phöông trình ñaëc tröng : X 2 − 6 X + 8 = 0 Coù caùc nghieäm : X1 = 2, X2 = 4 Vaäy : T (n) = c1 X 1 + c2 X 2 n n Do : 0 0 T (0) = 1 ⇒ c1 X 1 + c2 X 2 = 1 ⇒ c1 + c2 = 1 T (1) = 2 ⇒ c1 X 1 + c 2 X 2 = 2 ⇒ 2c1 + 4c2 = 2 ⎧c1 + c 2 = 1 Vaäy coù : ⇒ c1 = 1, c2 = 0. ⎨ ⎩2c1 + 4c 2 = 2 Ví duï 2 : ⎧5T (n − 1) − 8T (n − 2) + 4T (n − 3); n ≥ 3 ⎪0; n = 0 ⎪ T ( n) = ⎨ ⎪1; n = 1 ⎪2; n = 2 ⎩ Ta coù phöông trình : T ( n) − 5T ( n − 1) + 8T ( n − 2) − 4T ( n − 3) = 0 Phöông trình ñaëc tröng töông öùng laø : X 3 − 5X 2 + 8X − 4 = 0 ⇔ ( X − 1)( X − 2) 2 = 0 Vaäy ta coù caùc nghieäm cuûa phöông trình ñaëc tröng : 1 (ñôn), 2 (keùp) Neân nghieäm chung laø : T ( n) = c11n + c 2 2 n + c3 n 2 n Döïa vaøo caùc ñieàu kieän ñaàu, ta coù : ⎧c1 + c 2 = 0 ⎪ ⎨c1 + 2c 2 + 2c3 = 1 ⎪c + 4c + 8c = 2 ⎩1 2 3 1 Suy ra : c1 = −2; c 2 = 2; c3 = − 2 Vaäy : n +1 n −1 T ( n) = 2 − n 2 − 2 Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn
  9. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 25 - B2) Phöông trình truy hoài tuyeán tính khoâng thuaàn nhaát vôùi caùc heä soá khoâng ñoåi : Phöông trình daïng : a 0 t n + a 1 t n −1 + L + a k t n − k = b n p (n) Vôùi b laø haèng soá, p laø ña thöùc baäc d theo n. Bieán ñoåi veà daïng thuaàn nhaát. Ví duï : t n − 2t n −1 = 3 n ⎡(2) : t n +1 − 2t n = 3 n +1 ; Ta coù : ⎢ ⎢(3) : 3t n − 6t n −1 = 3 ; do nhaân 2 veá cuûa (1) cho 3 n +1 ⎣ Laáy (2) – (3), ñöôïc daïng thuaàn nhaát : t n +1 − 5t n + 6t n −1 = 0 5. Caùc pheùp toaùn treân caùc kyù hieäu tieäm caän a) Pheùp toaùn coäng : θ( f(n)) + θ (g(n)) = Max(θ( f(n)) , θ (g(n)) Nhaän xeùt : - θ( f(n)) + θ (g(n)) = θ( f(n) + g(n)) = θ (Max(f(n),g(n)) - Ñaëc bieät , Neáu c laø haèng soá , thì : θ( cf(n)) = θ( f(n)) b) Pheùp toaùn nhaân : θ(f(n))θ (g(n)) = θ(f(n)g(n)) Ñaëc bieät : θ( f(n)2 ) = (θ(f(n))2 c) Pheùp toaùn tích cöïc : Ñoù laø leänh trong thuaät toaùn maø thôøi gian thöïc hieän noù khoâng ít hôn thôøi gian thöïc hieän caùc leänh khaùc. Khi ñaùnh giaù thôøi gian thöïc hieän cuûa thuaät toaùn, ta chæ caàn quan taâm ñeán caùc böôùc thöïc hieän cuûa pheùp toaùn naøy. Ví duï : Saép taêng daàn caùc phaàn töø cuûa daõy soá x. Duøng thuaät toaùn cheøn tröïc tieáp SIS (straight insertion Sort): YÙ töôûng : ÔÛ böôùc i , giaû söû daõy : x[1],..., x[i] ñaõ coù thöù töï. Tìm vò trí thích hôïp cuûa phaàn töû x[i+1] ñeå cheøn noù vaøo daõy x[1],..., x[i], keát quaû laø ta coù daõy x[1],..., x[i+1] coù thöù töï. Thöïc hieän thao taùc treân vôùi i = 1,2,,..., n-1. Thuaät toaùn : for (i =1; i
  10. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 26 - j = j-1; Chuaån bò cho a tieán tieáp veà traùi } a ≥ x[j] x[j+1] = a; Cheøn x[i+1] vaøo vò trí thích hôïp - laø sau x[j]. } Coù theå xem pheùp toaùn tích cöïc ôû ñaây laø : a< x[j]; Trong tröôøng hôïp xaáu nhaát, töông öùng daõy giaûm daàn. Soá laàn thöïc hieän cuûa pheùp toaùn naøy laø : n(n + 1) 2+⋅⋅⋅+n= −1 . 2 Vaäy : T(n) ∈ θ (n2). Trong tröôøng hôïp toát nhaát, töông öùng daõy taêng daàn.Soá laàn thöïc hieän cuûa pheùp toaùn naøy laø : n - 1 Vaäy : T(n) ∈ θ (n). 6. Phaân tích tröôøng hôïp trung bình Ta bieát raèng thôøi gian thöïc hieän thuaät toaùn khoâng phaûi chæ phuï thuoäc vaøo kích thöôùc döõ lieäu maø coøn phuï thuoäc vaøo tình traïng döõ lieäu nhaäp nöõa. Chaúng haïn, khi xeáp taêng daàn moät daõy caùc soá nguyeân, thì caùc soá ñaõ coù saün thöù töï taêng daàn, hoaëc ngöôïc laïi, hoaëc ngaãu nhieân. Phaàn treân ta ñaõ xeùt trong nhöõng khaû naêng toát nhaát hoaëc xaáu nhaát cuûa thuaät toaùn . Baây giôø ta phaân tích trong tröôøng hôïp ngaãu nhieân, töùc laø ñaùnh giaù ñoä phöùc taïp trung bình thôøi gian thöïc hieän thuaät toaùn . Vieäc ñaùnh giaù trung bình thöôøng khoù vaø phöùc taïp ñoøi hoûi nhöõng coâng cuï toaùn hoïc tinh vi, hôn nöõa vieäc tính trung bình coù theå coù nhieàu caùch quan nieäm khaùc nhau.ÔÛ ñaây, vieäc ñaùnh giaù ñoä phöùc taïp thuaät toaùn trong tröôøng hôïp trung bình ta döïa treân cô sôû lyù thuyeát xaùc suaát ( rôøi raïc ) . Ví duï : Xeùt thuaät toaùn cheøn tröïc tieáp . Xeùt böôùc thöù i cuûa voøng laëp. Danh saùch coù i phaàn töû ñaõ ñöôïc saép. Phaàn töû x[i+1] coù theå cheøn vaøo i-1 khe giöõa caùc x[j], j ∈ {1, i} vaø theâm 2 vò trí ñaàu cuoái nöõa (Cheøn tröôùc x[1] vaø cheøn sau x[i] ), toång coäng laø coù i+1 vò trí coù theå cheøn x[i+1]. Giaû söû khaû naêng cuûa moãi vò trí ñöôïc x[i+1] cheøn vaøo laø ñoàng ñeàu. Töùc laø xaùc 1 suaát cuûa moãi vò trí ñöôïc x[i+1] cheøn vaøo laø . i +1 Goïi Xi laø bieán ngaãu nhieân chæ soá löôïng caùc pheùp toaùn so saùnh caàn thieát ñeå x[i+1] cheøn vaøo vò trí thích hôïp cuûa noù trong moãi böôùc. Ta coù : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn
  11. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 27 - X1 X2 Xi Vò trí i+1 i 3 2 1 (Töø phaûi sang traùi) Xi I i ... 3 2 1 p ... 1 1 1 1 1 i +1 i +1 i +1 i +1 i +1 1 1 1 1 i E( X i ) = 1 +2 +3 +L+ i ⋅ + i +1 i +1 i +1 i +1 i +1 1 = (1 + 2 + L + (i − 1) + i + i ) i +1 1 i (i + 1) i = ⋅ + i +1 i +1 2 i i =+ 2 i +1 Neáu goïi Y laø bieán ngaãu nhieân xaùc ñònh bôûi toång caùc so saùnh trong saép xeáp thì : X1 + X2 + ⋅ ⋅ ⋅ +Xn-1 Y = Ta coù : n −1 n −1 n −1 1 n −1 n −1 1 i i ∑2 + ∑ i + 1 2 i=1 i =1 i + 1) ∑ E( X i ) = = ∑ i + ∑ (1 − E(Y) = i =1 i =1 i =1 1 n(n − 1) 1 n +n−∑ = ⋅ 2 2 i =1 i n 2 3n = + − Hn 4 4 1 n Trong ñoù : H n = ∑ ≤ lgn + 1 ; ( Hn laø soá Harmonic baäc n .) i =1 i Neân giaù trò trung bình cuûa caùc pheùp toaùn so saùnh trong thuaät toaùn töông n2 , Vaäy ñoä phöùc taïp trung bình cuûa thuaät toaùn laø θ (n2 ). ñöông vôùi 4 V. Toái öu thuaät toaùn Tieán trình toång quaùt cuûa vieäc taïo ra caùc söûa ñoåi ngaøy caøng tieán boä hôn cho moät thuaät toaùn ñeå sinh ra moät phieân baûn khaùc chaïy nhanh hôn ñöôïc goïi laø toái öu thuaät toaùn. Khi toái öu moät thuaät toaùn ta thöôøng döïa vaøo moät nguyeân lyù, ñoù laø nguyeân lyù Profile : “ Tìm ñieåm maát thôøi gian nhieàu nhaát cuûa thuaät toaùn “. Moät soá kyõ thuaät sau thöôøng duøng ñeå toái öu thuaät toaùn : 1. Kyõ thuaät toái öu caùc voøng laëp Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn
  12. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 28 - Ñaây laø ñieåm quan taâm ñaàu tieân khi caûi tieán thuaät toaùn, vì voøng laëp laø caâu leänh thöôøng laøm taêng ñoä phöùc taïp cuûa thuaät toaùn. Vieäc caûi tieán taäp trung vaøo : - Coá gaéng giaûm caùc voøng laëp loàng nhau. - Taêng soá leänh thöïc hieän trong moät böôùc laëp ñeå giaûm soá löôïng caùc böôùc laëp. - Taùch caùc leänh khoâng phuï thuoäc vaøo chæ soá laëp ra khoûi voøng laëp. ... Ví duï 1: Xeùt thuaät toaùn tính giaù trò cuûa ex theo coâng thöùc gaàn ñuùng : x2 xi xn ∑ i! = 1+ x + +L+ +L 2! n! i ≥0 Thuaät toaùn 1 :{ Tính töøng soá haïng roài coäng laïi.} Input x,n xi n Ouput S = ∑ . i =1 i! Moâ taû : S = 1; for( i = 1; i
  13. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 29 - p = 1; for( i = 1; i
  14. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 30 - c[ii][j] = 0; c[ii][jj] = 0; k = 1; while (k < n) { kk = k+1; c[i][j] = c[i][j] + a[i][k]*b[k][j] + a[i][kk]*b[kk][j]; c[i][jj] = c[i][jj]+a[i][k]*b[k][jj] + a[i][kk]*b[kk][jj]; c[ii][j] = c[ii][j]+a[ii][k]*b[k][j] + a[ii][kk]*b[kk][j]; c[ii][jj] = c[ii][jj]+a[ii][k]*b[k][jj] + a[ii][kk]*b[kk][jj]; k = k+2; } j = j + 2; } i = i + 2; } } Giaû thieát n chaün vì ta duøng böôùc nhaûy 2 2. Toái öu vieäc reõ nhaùnh - Ñoái vôùi bieåu thöùc logic keát hôïp baèng pheùp toaùn &&, neân vieát theo thöù töï xaùc suaát sai giaûm daàn : A1 && A2 &&... && An Xaùc suaát sai cuûa caùc Ai giaûm daàn . - Ñoái vôùi bieåu thöùc logic keát hôïp baèng pheùp toaùn ||, neân vieát theo thöù töï xaùc suaát ñuùng giaûm daàn : A1 || A2 ||... || An Xaùc suaát ñuùng cuûa caùc Ai giaûm daàn : ... BAØI TAÄP Baøi 1 : Xaùc ñònh ñoä phöùc taïp cuûa caùc thuaät toaùn sau : r = m%n; gt (n) ≡ while(r) if (n == 0 || n == 1) { return 1; m = n; else n = r; return (n * gt(n-1)) ; r = m%n; } return n Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn
  15. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 31 - Fibo(n) ≡ Fib(n) ≡ i = 1; j = 0; if ( n < 2 ) for( k =1 → n) return 2; { else j = i + j; return Fib(n-1)+Fib(n-2); i = j – i; } return j; Baøi 2 : Tính ñoä phöùc taïp cuûa caùc thuaät toaùn sau trong tröôøng hôïp toát nhaát, xaáu nhaát : for (i = 1; i
  16. Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 32 - ⎧T (n) − 3T (n − 1)48T (n − 2) = 0, n > 1 ⎪ 1. ⎨T (0) = 1 ⎪T (1) = 2 ⎩ ⎧ n ⎪T (n) = n + 4T ( ), n > 1 2. ⎨ 2 ⎪T (1) = 1 ⎩ ⎧T (n) = T (n − 1) + T (n − 2), n > 1 ⎪ 3. ⎨T (0) = 1 ⎪T (1) = 1 ⎩ ⎧T (n) = 2T (n − 1) + 1; n > 1 ⎪ 4. ⎨T (0) = 0 ⎪T (1) = 1 ⎩ Baøi 5 : Caûi tieán thuaät toaùn cheøn tröïc tieáp baèng caùch : Duøng phöông phaùp tìm kieám nhò phaân ñeå xaùc ñònh vò trí caàn cheøn cuûa ai trong daõy con ñaõ coù thöù töï a1,…, ai-1 . Thuaät toaùn caûi tieán goïi laø cheøn nhò phaân. Haõy thieát keá, caøi ñaët vaø ñaùnh giaù ñoä phöùc taïp thôøi gian cuûa thuaät toaùn. Baøi 6 : Tìm caùc ví duï veà caùc thuaät toaùn maø khi caûi tieán ( baèng caùch naøo ñoù ), soá laàn thöïc hieän cuûa thuaät toaùn giaûm ñaùng keå ( veà ñoä phöùc taïp tieäm caän, hoaëc veà tæ leä ...) Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2