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. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Giáo trình Cấu trúc dữ liệu và thuật toán (Tái bản): Phần 2 Chưưng 6 PHÂN TÍCH THUẬT TOÁN 6.1. 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[1..N] 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[1..N] 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 6.1 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. 6.2. ĐỘ HIỆU QUẢ VÀ ĐỘ PHỨC TẠP CỦA THUẬT TOÁN 6.2.1. 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 thuộc chính phủ, quản lý nhà nước ở cấp tỉnh và các sở thuộc tỉnh, quản lý tài chính - kế toán - ngân hàng, quản lý tư pháp, quản lý tòa án, quản lý giáo dục đào tạo. - Khoa học kỹ thuật thuần tuý. 154 - Lĩnh vực khoa học cơ bản. - Trong cơ khí, kiến trúc, xây dụng nhà, xây dựng cầu, đường, thuỷ lợi, giao thông, nông nghiệp v.v... - Thuần tuý tin học: dịch vụ tra cứu thông tin trên mạng, thư tín điện tử, thương mại điện từ v.v... - Lĩnh vực trò chơi, dạy học, du lịch, dịch vụ công cộng v.v... 6.2.2. Xác định độ hiệu quả, độ phức tạp của th u ậ t toán Các cấu trúc dữ liệu có thể được cài đặt trong bộ nhớ máy tính theo nhiều cách khác nhau, mỗi cách đòi hỏi phải dùng số lượng bộ nhớ và thời gian tính toán nhất định. Cách nào mà sử dụng ít bộ nhớ nhất và thời gian tính toán ít nhất thì nó là hiệu quả nhất. Người ta chỉ quan tâm đến thời gian tính toán. Yếu tố quan trọng nhất ảnh hường đến thời gian tính toán là khối lượng thông tin đầu vào và kỹ thuật lập trình được sử dụng. Ký hiệu t là thời gian thực hiện của thuật toán, khi đó t là một hàm số phụ thuộc vào số lượng đầu vào n, nên ta viết là T(n). Khái niệm độ phức tạp của thuật toán được hiểu theo ý nghĩa là độ lớn của T(n), được kỷ hiệu bâng chữ 0 (đọc là ô lớn) như sau: giả sử n là sô' nguyên dương, T (n) và f(n ) là các hàm thực không ám, khi đó T(n) = 0(f(n )) nếu và chỉ nếu tổn tại các hằng dương c và nn sao cho T(n) n0. Theo định nghĩa trên, hàm f(n) là cận trên của T(n). Thuật toán có thời gian thực hiện T(n) = 0(f(n))- ta nói rằng nó có thời gian thực hiện cấp f(n). Trong lý thuyết phần tích thuật toán, người ta đã đưa ra một số cấp thời gian chuẩn thực hiện thuật toán như sau: 0 (1 ) - thời gian thực hiện bị chặn bởi 1 hằng số; O(logn) - thời gian thực hiện theo logarit O(nlogn) - thời gian thực hiện theo nlogn 0 (n ) - thời gian thực hiện tuyến tính 0 (n 2) - thời gian thực hiện bình phương 0 (2 ) - thời gian thực hiện là số mũ 155 Với các chỉ tiêu trên đây, ta đã có một độ đo để đánh giá, SO sánh thuật toán nào tốt hơn thuật toán nào khi giải quyết một bài toán. 6.2.3. Quy tắc đánh giá thời gian thực hiện thuật toán Quy tắc tổng: nếu Tj(n) = 0 (f|(n )) và T2(n) = 0 ( f 2(n)) thì T,(n) + T\(n) = 0(m ax(f|(n), fi(n)) Thật vậy: vì Tị(n) = 0 (f|(n )) nên 3 c h n, sao cho T ,(n) < C |f|(n)) với V n > n 1; T2(n) = 0 ( f 2(n)) nên 3 c2, n2 sao cho T2(n) < c2f2(n)) với V n > n2, Đặt n0 = max(ri|, n2), khi đó với V n > n0 ta có: T,(n) + T2(n) < (C| + c2)max(f|(n), f2(n)) Có thể nói một cách tổng quát như sau: khi một bài toán được chia thành nhiểu bài toán con thì độ đo cấp độ thời gian thực hiện thuật toán sẽ lấy theo cấp độ lốn nhất trong các cấp độ thành phần. 6.2.4. Đ ánh giá thời gian thực hiện các câu lệnh Pascal Để đánh giá thời gian thực hiện một chương trình, ta phải biết được từng câu lệnh thực hiện bao nhiêu lần. Tuỳ theo loại lộnh, ta có các chỉ tiêu đánh giá như sau: 1. Lệnh gán, lệnh read, write, goto có thòi gian thực hiên là 0 ( 1); 2. Lệnh phức hợp để trong cặp begin... end được đánh giá theo quy tắc tổng ở trên; 3. Lệnh IF T H E N SI ELSE S2, thời gian thực hiên là: 0(m ax(f,(n), f2(n)) trong đó f|(n), f2(n) là cận trên của thời gian thực hiện lệnh SI, S2. 4. Lệnh CASE được đánh giá như lệnh IF. 5. Lệnh lập (repeat...until, while..do. fo ...