Bài giảng Cấu trúc dữ liệu giải thuật: Kỹ thuật phân tích giải thuật

Bài giảng Cấu trúc dữ liệu giải thuật: Kỹ thuật phân tích giải thuật nêu lên nguyên nhân cần phải phân tích giải thuật, tiêu chuẩn đánh giá giải thuật, phương pháp đánh giá. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về vấn đề này.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu giải thuật: Kỹ thuật phân tích giải thuậtKỹ thuật phân tích giải thuậtPhạm Nguyên Khang, Đỗ Thanh NghịKhoa CNTT – Đại học Cần Thơ{pnkhang,dtnghi}@cit.ctu.edu.vn2Nội dung••••Tại sao cần phải phân tích giải thuật ?Tiêu chuẩn đánh giá giải thuậtPhương pháp đánh giáBài tập3Sự cần thiết phải phân tích giải thuật• Đánh giá giải thuật–Tính đúng đắn●●––Chạy trên dữ liệu thửChứng minh lý thuyết (bằng toán học chẳng hạn)Tính đơn giảnTính nhanh chóng (thời gian thực thi)●●Quan trọng khi chương trình được thực thi nhiều lầnHiệu quả thời gian thực thi4Thời gian thực hiện của chương trình• Đo thời gian thực hiện chương trình––––Lập trình và đo thời gian thực hiệnPhụ thuộc vào tập lệnh của máy tínhKỹ năng của người lập trìnhDữ liệu đầu vàoTính độ phức tạp thời gian thực hiện của giảithuật = độ đo sự thực thi của giải thuật5Thời gian thực hiện của chương trình• Đo thời gian thực hiện:––––Hàm T(n) ≥ 0, với n là kích thước (độ lớn) củađầu vàoVí dụ: T(n) = 3nĐơn vị tính: số lệnh cơ bản, số chỉ thị, …Thời gian thực hiện trong các trường hợp: tốtnhất, xấu nhất, trung bìnhSo sánh T1(n) và T2(n)