tailieunhanh - Giáo trình Cấu trúc dữ liệu và thuật toán (Tái bản): Phần 2

Nối tiếp nội dung phần 1, phần 2 cuốn giáo trình "Cấu trúc dữ liệu và thuật toán" trình bày các nội dung: Phân tích thuật toán sắp xếp, các thuật toán tìm kiếm, các thuật toán tìm kiếm, quy hoạch động. | Chưưng 6 PHÂN TÍCH THUẬT TOÁN . K HÁ I N IỆM Mỗi thuật toán phải đảm bảo các tính chất - Các bước phải được xác định rõ ràng rành mạch từ bắt đầu đến kết thúc - Tổng quát xét được mọi khả năng mọi trường hợp của bài toán - Chi tiết trong từng khả năng từng trường hợp phải xác định được công thức tính toán hay dòng thông báo về kết quả xử lý - Dễ cài đặt chương trình máy tính - Hữu hạn thời gian thực hiện thuật toán chấp nhận được. Trong chương trước ta đã học các phương pháp trình bày thuật toán các dạng thuật toán cơ bản. Một bài toán có thể có nhiều cách giải khác nhau có thể có nhiều thuật toán khác nhau việc chọn thuật toán nào để viết chương trình cho máy tính đã được các chuyên gia tin học đề cập đến từ lâu và một lĩnh vực mới đã hình thành nghiên cứu và phân tích độ phức tạp độ hiệu quả của thuật toán. Ví dụ Xét một thuật toán điển hình Bài toán lim kiếm nhị phan. Cần xác định phẩn tử T có trong mảng được sắp X hay không. 0. Đưa vào T 1. Found .false. 2. Đầu 1 3. Cuối N 4. WHILE đầu b IF TX M THEN Đầu M l ELSE Found .true. ở đây X có thể là số có thể là xâu ký tự chữ xem mảng - array . Những vấn đề cần quan tâm khi xây dựng thuật toán Thuật toán phải đảm bảo được 5 tính chất như đã nêu ở đầu mục này Cách trình bày thuật toán phải giúp cho việc viết đúng chương trình Cách trình bày thuật toán phải giúp cho việc lựa chọn kỹ thuật lập trình để nâng cao hiệu suất của chương trình. . ĐỘ HIỆU QUẢ VÀ ĐỘ PHỨC TẠP CỦA THUẬT TOÁN . Các loại bài toán Độ phức tạp của thuật toán thường phụ thuộc vào từng loại bài toán cần giải quyết. Có bài toán có khối lượng xử lý thông tin rất lớn như bài toán thống k6 da số . có bài toán có ft thông lin ban đẩu nhuiig lại rất phức tạp về mặt toán học logic tính toán. Ta gọi chung các bài toán cần xử lý trên máy tính là công việc tính toán. Ta có thể phân chia các cống việc tính toán cần xử lý trên máy tính ra các lĩnh vực sau - Quản lý doanh nghiệp quản lý nhà nước - chính phủ và quản lý ở các cấp bộ ngành .