ƯỚC LƯỢNG
ĐỘ PHỨC TẠP THỜI GIAN (BIG O)
CỦA THUẬT TOÁN
Khoa Công nghệ thông tin
Trường Đại học Ngoại ngữ - Tin học TP.HCM (HUFLIT)
2
Review
•4 thành phần của bài toán
•Mô tả ngữ cảnh
•Mô tả input
•Mô tả output
•Các ví dụ
•Quy trình giải bài toán
•Đọc bài toán vài lần, gạch dưới những từ quan trọng
•Giải bài toán trên giấy, giải các ví dụ
•Tinh chỉnh lời giải
•Viết mã giả, dự kiến các hàm, các lớp
•Cài đặt chương trình: cài đặt từng bước của mã giả
•Kiểm tra/kiểm thử với những dữ liệu khác nhau, chạy từng bước để phát
hiện lỗi
•Các biểu diễn dữ liệu cơ bản
•Vô hướng
•Danh sách
•Bảng
•Dạng khác (Tree, Graph, …)
3
Nội dung
•Thời gian chạy của thuật toán
•Khái niệm Big O
•Quy tắc tính Big O
•Một số Big O thông dụng
THỜI GIAN CHẠY
CỦA THUẬT TOÁN
5
Tại sao cần biết thời gian chạy của thuật toán
•Trong thiết kế thuật toán
•Định hướng thiết kế: từ input size + time limited →định hướng cần phải
thiết kế thuật toán có phức tạp bao nhiêu →dùng phương pháp gì
•Đánh giá thuật toán có thể chạy trong thời gian cho phép không (trước
khi tiến hành cài đặt)
•Xác định những điểm yếu trong thuật toán để cải tiến
•Trong sử dụng thuật toán
•Trước khi sử dụng một thuật toán trong thư viện, cần biết thuật toán có
thời gian chạy bao nhiêu
•Trong so sánh các thuật toán
•Là thước đo các thuật toán cùng giải quyết một bài toán