tailieunhanh - Chương 4: Kỹ thuật phân tích giải thuật

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 trình đệ quy | Collected by The Wall 11 10 2005 1. Mục tiêu 2. Kiến thức cơ bản cần có đe học chương này 3. Tài liệu tham khảo có liên quan đến chương 4. Nội dung - Sự cần thiết phải phân tích giải thuật. - Thời gian thực hiện của giải thuật. - Tỷ suất tăng và độ phức tạp của giải thuật. - Cách tính độ phức tạp. - Phân tích các chương trình đệ quy. 5. Vấn đề nghiên cứu của trang kế tiếp 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 trình đệ quy. Sự CẦN THIẾT PHẢI PHÂN TÍCH GIẢI THUẬT 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. - Giải thuật đúng đắn. 2. - Giải thuật đơn giản. 3. - Giải thuật thực hiện nhanh. Với yêu cầu 1 để kiểm tra tính đúng đắn của giải thuật chúng ta có thể cài đặt giải thuật đó và cho thực hiện trên máy với một số bộ dữ liệu mẫu rồi lấy kết quả thu được so sánh với kết quả đã biết. Thực ra thì cách làm này không chắc chắn bởi vì có thể giải thuật đúng với tất cả các bộ dữ liệu chúng ta đã thử nhưng lại sai với một bộ dữ liệu nào đó. Vả lại cách làm này chỉ phát hiện ra giải thuật sai chứ chưa chứng minh được là nó đúng. Tính đúng đắn của giải thuật cần phải được chứng minh bằng toán học. Tất nhiên điều này không đơn giản và do vậy chúng ta sẽ không đề cập đen ở đây. Khi chúng ta viết một chương trình để sử dụng một vài lần thì yêu cầu 2 là quan trọng nhất. Chúng ta cần một giải thuật dễ viết chương trình để nhanh chóng có được kết qủa thời gian thực hiện chương trình không được đề cao vì dù sao thì chương trình đó cũng chỉ sử dụng một vài lần mà thôi. Tuy nhiên khi một chương trình được sử dụng nhiều lần thì thì yêu cầu tiếỉt kiệm thời gian Giáo trình môn Phân tích Giải .