Đang chuẩn bị liên kết để tải về tài liệu:
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. nội dung chi tiết. | 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 GIỚI THIỆU PHÂN TÍCH THUẬT TOÁN Bùi Tiến Lên 01/01/2017 CuuDuongThanCong.com https://fb.com/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 CuuDuongThanCong.com Data structure & Algorithm https://fb.com/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 CuuDuongThanCong.com Data structure & Algorithm https://fb.com/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 CuuDuongThanCong.com Data structure & Algorithm https://fb.com/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 CuuDuongThanCong.com Data structure & Algorithm https://fb.com/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 CuuDuongThanCong.com Data structure & Algorithm https://fb.com/tailieudientucntt 6 Thời gian .