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

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à...
Nội dung trích xuất từ tài liệu:
thiết kế và đánh giá thuật toán - trần tuấn minh -2 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 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 ...