tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Bùi Tiến Lên

Mục tiêu của bài giảng là giúp sinh viên hiểu được sự cần thiết về phân tích thuật toán, nắm được các tiêu chuẩn để đánh giá một giải thuật, hiểu được các khái niệm về độ phức tạp thuật toán. | GIỚI THIỆU PHÂN TÍCH THUẬT TOÁN Bùi Tiến Lên 01 01 2017 https tailieudientucntt Phân tích thuật toán Mục tiêu I Hiểu được sự cần thiết về phân tích thuật toán I Nắm được các tiêu chuẩn để đánh giá một giải thuật I Hiểu được các khái niệm về độ phức tạp thuật toán Spring 2017 Data structure amp Algorithm https tailieudientucntt 2 Phân tích thuật toán cont. Để làm gì I Cùng một vấn đề có thể giải quyết bằng nhiều giải thuật khác nhau I Lựa chọn một giải thuật tốt nhất trong các giải thuật cho một bài toán I Cải tiến giải thuật để có một giải thuật tốt hơn Spring 2017 Data structure amp Algorithm https tailieudientucntt 3 Phân tích thuật toán cont. Các tiêu chí đánh giá thuật toán I Một thuật toán được xem là đúng nếu I Tính đúng đắn Thuật toán phải chạy đúng I Tính hữu hạn Thuật toán phải dừng sau một số bước hữu hạn I Một thuật toán được xem là tốt nếu I Bộ nhớ Sử dụng ít bộ nhớ liên quan đến cấu trúc dữ liệu I Thời gian Thực hiện nhanh Spring 2017 Data structure amp Algorithm https tailieudientucntt 4 Thời gian thực hiện chương trình I Các yếu tố ảnh hưởng đến thời gian thực hiện chương trình I Cấu hình máy tính tốc độ CPU kích thước bộ nhớ. I Ngôn ngữ lập trình I Cấu trúc dữ liệu I Cài đặt chi tiết I . Spring 2017 Data structure amp Algorithm https tailieudientucntt 5 Thời gian thực hiện chương trình cont. Định nghĩa 1 I Thời gian thực hiện hay chi phí thực hiện hay độ phức tạp chương trình là 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 hay độ lớn của dữ liệu vào Spring 2017 Data structure amp Algorithm https tailieudientucntt 6 Thời gian thực hiện chương trình cont. Lưu ý I Thời gian thực hiện chương trình là một hàm không âm T n 0 n 0. I Đơn vị của T n không phải là đơn vị thời gian vật lý như giờ phút giây . mà được đo bởi số các lệnh cơ bản basic operations được thực .