TAILIEUCHUNG - 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 họ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,. Mời các bạn tham khảo. | 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@ 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

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.