6/12/141 /XX MÔN: C U TRÚC D LI UẤ Ữ Ệ GV: NGUY N XUÂN VINHỄ
Đ PH C T PỘ Ứ Ạ
(Complexity)
Nguy n Xuân Vinhễ
nguyenxuanvinh@hcmuaf.edu.
vn
C U TRÚC D LI UẤ Ữ Ệ
DATA STRUCTURES
[214331]
6/12/142 /XX MÔN: C U TRÚC D LI UẤ Ữ Ệ GV: NGUY N XUÂN VINHỄ
Khái ni mệ
•Thu t toán (ậAlgorithm) là m t dãy h u h n các b c có th th c ộ ữ ạ ướ ể ự
thi đ c mà theo đó ta đ t đ c l i gi i c a bài toán.ượ ạ ượ ờ ả ủ
•T ừAlgorithm b t ngu n t nhà toán h c R p ắ ồ ừ ọ Ả ậ Al-Khwārizmī
•Thu t toán gi i ph ng trình b c 2, thu t toán tìm s l n nh t ậ ả ươ ậ ậ ố ớ ấ
trong dãy s , thu t toán s p x p…ố ậ ắ ế
6/12/143 /XX MÔN: C U TRÚC D LI UẤ Ữ Ệ GV: NGUY N XUÂN VINHỄ
Ví dụ
•Mô t gi i thu t tìm ph n t l n nh t trong dãy h u h n các ả ả ậ ầ ử ớ ấ ữ ạ
ph n tầ ử
–B1: Đ t giá tr c c đ i t m th i (max) là ph n t đ u tiên c a ặ ị ự ạ ạ ờ ầ ử ầ ủ
dãy
–B2: N u s k ti p l n h n max thì gán giá tr max = s đóế ố ế ế ớ ơ ị ố
–B3: L p l i b c 2 n u còn ph n t trong dãyặ ạ ướ ế ầ ử
–B4: D ng khi không còn ph n t trong dãy, s max lúc này là ừ ầ ử ố
ph n t l n nh t c a dãyầ ử ớ ấ ủ
6/12/144 /XX MÔN: C U TRÚC D LI UẤ Ữ Ệ GV: NGUY N XUÂN VINHỄ
Dữ liệu nhập (input) Dữ liệu xuất (output)
Dãy thao tác
Khái ni mệ
6/12/145 /XX MÔN: C U TRÚC D LI UẤ Ữ Ệ GV: NGUY N XUÂN VINHỄ
Các tính ch t c b n c a thu t toánấ ơ ả ủ ậ
•Tính xác đ nh (rõ ràng, xác đ nh).ị ị
•Tính h u h n (d ng).ữ ạ ừ
•Tính đúng đ n.ắ
•Tính t ng quát: ph i áp d ng đ c cho 1 h các v n đổ ả ụ ượ ọ ấ ề
•Đ u vàoầ
•Đ u raầ