Phân tích các thuật toán (Analysis of Algorithms) Phân tích thuật toán Thuật toán là một qui trình thực hiện từng bước, từng bước giải quyết một vấn đề trong một khoảng thời | 5/13/2020 11:03:58 PM Phân tích thuật toán Bài 4. Phân tích các thuật toán (Analysis of Algorithms) 5/13/2020 11:03:58 PM Phân tích thuật toán Thuật toán là một qui trình thực hiện từng bước, từng bước giải quyết một vấn đề trong một khoảng thời gian hữu hạn. 5/13/2020 11:03:58 PM Phân tích thuật toán Các khía cạnh cần phân tích Bộ nhớ (Space) Xác định tổng dung lượng bộ nhớ cần thiết để lưu trữ toàn bộ dữ liệu đầu vào, trung gian và kết quả đầu ra. Ví dụ: Sắp xếp một dãy n phần tử. Bộ nhớ cần cho bài toán là: Bộ nhớ lưu biến n, lưu n phần tử của dãy, lưu các biến i, j, tg (nếu là thuật toán Bubble Sort) Thời gian chạy của thuật toán (Running time) 5/13/2020 11:03:58 PM Phân tích thuật toán Thời gian chạy (Running time) Hầu hết các thuật toán thực hiện biến đổi các đối tượng đầu vào thành các đối tượng đầu ra Thời gian chạy của thuật được đặc trưng bởi kích thước của dữ liệu đầu vào Chúng ta thường đi đánh giá thời gian chạy của thuật toán trong 3 trường hợp: xấu nhất, . | 5/14/2020 12:40:36 AM Phân tích thuật toán Bài 4. Phân tích các thuật toán (Analysis of Algorithms) 5/14/2020 12:40:36 AM Phân tích thuật toán Thuật toán là một qui trình thực hiện từng bước, từng bước giải quyết một vấn đề trong một khoảng thời gian hữu hạn. 5/14/2020 12:40:36 AM Phân tích thuật toán Các khía cạnh cần phân tích Bộ nhớ (Space) Xác định tổng dung lượng bộ nhớ cần thiết để lưu trữ toàn bộ dữ liệu đầu vào, trung gian và kết quả đầu ra. Ví dụ: Sắp xếp một dãy n phần tử. Bộ nhớ cần cho bài toán là: Bộ nhớ lưu biến n, lưu n phần tử của dãy, lưu các biến i, j, tg (nếu là thuật toán Bubble Sort) Thời gian chạy của thuật toán (Running time) 5/14/2020 12:40:36 AM Phân tích thuật toán Thời gian chạy (Running time) Hầu hết các thuật toán thực hiện biến đổi các đối tượng đầu vào thành các đối tượng đầu ra Thời gian chạy của thuật được đặc trưng bởi kích thước của dữ liệu đầu vào Chúng ta thường đi đánh giá thời gian chạy của thuật toán trong 3 trường hợp: xấu nhất, trung bình và tốt nhất. Thời gian chạy trung bình của thuật toán thường rất khó xác định Chung ta tập chung vào phân tích thời gian chạy trong trường hợp xấu nhất (do dễ phân tích) 5/14/2020 12:40:36 AM Phân tích thuật toán Phương pháp đánh giá Phương pháp thực nghiệm Phương pháp phân tích lý thuyết 5/14/2020 12:40:36 AM Phân tích thuật toán Phương pháp thực nghiệm Các bước thực hiện: Viết một chương trình thể hiện thuật toán Chạy chương trình với các bộ dữ liệu đầu vào có kích thước khác nhau và tổng hợp lại. Sử dụng một hàm như một đồng hồ để lấy chính xác thời gian chạy của thuật toán. Vẽ đồ thị biểu diễn kết quả 5/14/2020 12:40:36 AM Phân tích thuật toán Hạn chế của phương pháp thực nghiệm Cần phải cài đặt thuật toán bằng một ngôn ngữ lập trình, nhưng một số thuật toán việc cài đặt là khó. Kết quả thu được không thể biểu thị cho những bộ dữ liệu đầu vào chưa được thực nghiệm Để so sánh giữa hai thuật toán ta cần cài đặt trên các máy có cấu hình giống nhau cả về phần cứng/
