Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Phân tích thiết kế thuật toán: Chương 1 - Nguyễn Văn Linh

Bài giảng "Phân tích thiết kế thuật toán - Chương 1: Kỹ thuật phân tích thuật toán" cung cấp các kiến thức giúp người đọc có thể" Hiểu được sự cần thiết phải phân tích đánh giá giải thuật, biết các tiêu chuẩn để đánh giá một giải thuật, hiểu khái niệm độ phức tạp của giải thuật, vận dụng được phương pháp thành lập phương trình đệ quy,. . | CHƯƠNG 1: KỸ THUẬT PHÂN TÍCH THUẬT TOÁN Nguyễn Văn Linh Khoa Công nghệ Thông tin & Truyền thông ĐẠI HỌC CẦN THƠ nvlinh@cit.ctu.edu.vn Nguyễn Văn Linh MỤC TIÊU Sau khi hoàn tất bài học này bạn cần: Hiểu được sự cần thiết phải phân tích đánh giá giải thuật. Biết các tiêu chuẩn để đánh giá một giải thuật. Hiểu khái niệm độ phức tạp của giải thuật. Vận dụng được các quy tắc để tính độ phức tạp của chương trình không gọi chương trình con, độ phức tạp của một chương trình có gọi các chương trình con không đệ quy. Vận dụng được phương pháp thành lập phương trình đệ quy. Vận dụng được các phương pháp giải phương trình đệ quy Sự cần thiết phải phân tích, đánh giá giải thuật Cần phải phân tích, đánh giá giải thuật để: Lựa chọn một giải thuật tốt nhất trong các giải thuật để cài đặt chương trình giải quyết bài toán đặt ra. Cải tiến giải thuật hiện có để được một giải thuật tốt hơn. Tiêu chuẩn đánh giá một giải thuật là tốt Một giải thuật được xem là tốt nếu nó đạt các tiêu chuẩn sau: Thực hiện đúng. Tốn ít bộ nhớ. Thực hiện nhanh. Trong khuôn khổ môn học này, chúng ta chỉ quan tâm đến tiêu chuẩn thực hiện nhanh. Thời gian thực hiện của chương trình Thời gian thực hiện một chương trình là một hàm của kích thước dữ liệu vào, ký hiệu T(n) trong đó n là kích thước (độ lớn) của dữ liệu vào. Ví dụ : Chương trình tính tổng của n số có thời gian thực hiện là T(n) = cn trong đó c là một hằng số. Thời gian thực hiện chương trình là một hàm không âm, tức là T(n) 0 n 0. Ðơn vị đo thời gian thực hiện Ðơn vị của T(n) không phải là đơn vị đo thời gian bình thường như giờ, phút giây. mà thường được xác định bởi số các lệnh được thực hiện trong một máy tính lý tưởng. Ví dụ: Khi ta nói thời gian thực hiện của một chương trình là T(n) = Cn thì có nghĩa là chương trình ấy cần Cn chỉ thị thực thi. Thời gian thực hiện trong trường hợp xấu nhất Nói chung thì thời gian thực hiện chương trình không chỉ phụ thuộc vào kích thước mà còn phụ thuộc vào tính chất của dữ liệu vào. Vì vậy thường | CHƯƠNG 1: KỸ THUẬT PHÂN TÍCH THUẬT TOÁN Nguyễn Văn Linh Khoa Công nghệ Thông tin & Truyền thông ĐẠI HỌC CẦN THƠ nvlinh@cit.ctu.edu.vn Nguyễn Văn Linh MỤC TIÊU Sau khi hoàn tất bài học này bạn cần: Hiểu được sự cần thiết phải phân tích đánh giá giải thuật. Biết các tiêu chuẩn để đánh giá một giải thuật. Hiểu khái niệm độ phức tạp của giải thuật. Vận dụng được các quy tắc để tính độ phức tạp của chương trình không gọi chương trình con, độ phức tạp của một chương trình có gọi các chương trình con không đệ quy. Vận dụng được phương pháp thành lập phương trình đệ quy. Vận dụng được các phương pháp giải phương trình đệ quy Sự cần thiết phải phân tích, đánh giá giải thuật Cần phải phân tích, đánh giá giải thuật để: Lựa chọn một giải thuật tốt nhất trong các giải thuật để cài đặt chương trình giải quyết bài toán đặt ra. Cải tiến giải thuật hiện có để được một giải thuật tốt hơn. Tiêu chuẩn đánh giá một giải thuật là tốt Một giải thuật được xem là tốt nếu nó đạt các tiêu chuẩn sau: Thực hiện