1
Đ PH C T P Ộ Ứ Ạ
C A THU T TOÁNỦ Ậ
Ch ng 1ươ
2
N i dungộ
§Đ ph c t p c a thu t toán ộ ứ ạ ủ ậ
§c l ng đ ph c t p c a thu t toánƯớ ượ ộ ứ ạ ủ ậ
3
Đ PH C T P C A THU T TOÁN Ộ Ứ Ạ Ủ Ậ
4
Th i gian th c hi n thu t toánờ ự ệ ậ
§Phân tích thu t toán: Phân tích thu t toán là ậ ậ
xác đ nh l ng ị ượ tài nguyên c n thi t đ th c thi ầ ế ể ự
thu t toán:ậ
•Th i gian ờth c hi n thu t toán ự ệ ậ
•B nh ộ ớ c n th c hi n thu t toán ầ ự ệ ậ
§Tiêu chí th ng đ c dùng đ đánh giá thu t ườ ượ ể ậ
toán là th i gian th c hi n thu t toánờ ự ệ ậ .
5
Th i gian th c hi n thu t toán ờ ự ệ ậ
§M c tiêu c a phân tích thu t toán ụ ủ ậ
•So sánh đ ch n ra thu t toán nào ch y ể ọ ậ ạ
nhanh nh t ấ
•Tìm nh ng y u đi m c a thu t toán đ C i ữ ế ể ủ ậ ể ả
ti n thu t toán t t h nế ậ ố ơ
§2 cách “đo” th i gian th c hi n c a thu t toánờ ự ệ ủ ậ
•Th i gian th c hi n th c tờ ự ệ ự ế
•Th i gian th c hi n lý thuy t (Phân tích thu t ờ ự ệ ế ậ
toán)