Mục tiêu-sau khi học chương này, sinh viên cần phải trả lời được các câu hỏi sau: tại sao cần phân tích đánh giá giải thuật. tiêu chuẩn nào để đánh giá một giải thuật là tốt | Generated by Foxit PDF Creator Foxit Software http For evaluation only. Chương II Độ phức tạp tinh toán và tinh hiệu quả của thuật toán TỐNG QUAN . Mục tiêu Sau khi học chương này sinh viên cần phải trả lời được các câu hôi sau Tại sao cần phân tích đánh giá giải thuật Tiêu chuẩn nào đổ đánh giá một giài thuật là tốt Phương pháp đánh giá như the nào đánh giá chương trình không gọi chương trình con đánh giá một chương trinh có gọi các chương trinh con không đệ quy và đánh giá chương trình đệ quy . Generated by Foxit PDF Creator Foxit Software http For evaluation only. . Kiến thức cơ bản cần thiết Các kiến thức cơ bản cẩn thiết để học chương này bao gồm Kiến thức toán học Công thức tính tổng n số tự nhiên đầu tiên công thức tính tồng n số hạng đầu tiên cùa một cấp số nhân phương pháp chứng minh quỵ nạp và các kiến thức liên quan đến logarit biến đổi logarit tính chất đồng biến của hàm số logarit . Kĩ thuật lập trình và lập trình đệ quy. . Nội dung cót lõi Trong chương này chúng ta sẽ nghiên cứu các vấn đề sau Sự cần thiết phải phân tích các giải thuật. Thời gian thực hiện của chương trình. Tỳ suất tăng và độ phức tạp của giải thuật. Tính thời gian thực hiện cùa chương trình. Phân tích các chương trinh đệ quỵ. Generated by Foxit PDF Creator Foxit Software http For evaluation only. . Sự CÁN THIỀT PHẢỈ PHÂN TÍCH THUÁ T TOÁN Trong khi giải một bài toán chúng ta có thổ có một số giải thuật khác nhau vấn đồ lả cần phải đánh giá các giải thuật đó đổ lựa chọn một giải thuật tốt nhất . Thông thường thì ta sẽ căn cứ vảo các tiêu chuẩn sau 1. ìiải thuật đúng đắn. 2. ìiải thuật đon giản. 3. ìiải thuật 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 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ụ 2-1 Chương trình tính tống của n số có thời gian thực .
