Giáo trình cấu trúc dữ liệu và giải thuật

mydoc
mydoc(788 tài liệu)
(35 người theo dõi)
Lượt xem 311
17
Tải xuống 2,000₫
(Lịch sử tải xuống)
Số trang: 148 | Loại file: PDF
0

Gửi bình luận

Bình luận

Thông tin tài liệu

Ngày đăng: 16/08/2012, 14:59

Mô tả: Giáo trình cấu trúc dữ liệu và giải thuật ĐH Đà Lạt TRƯỜNG ĐẠI HỌC ĐÀ LẠT KHOA TOÁN - TIN HỌC Y  Z TRƯƠNG CHÍ TÍN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 (Giáo Trình) -- Lưu hành nội bộ -- Y Đà Lạt 2008 Z LỜI MỞ ĐẦU Giáo trình này nhằm cung cấp cho sinh viên các kiến thức căn bản về các cấu trúc dữ liệu cơ sở có cấu trúc tuyến tính tĩnh, động (danh sách liên kết), cấu trúc cây và các giải thuật cơ bản liên quan đến chúng như sắp xếp, tìm kiếm ở bộ nhớ trong, cũng như so sánh độ phức tạp của các giải thuật này. Để có thể nắm bắt các kiến thức trình bày học phần này, sinh viên cần nắm được các kiến thức về tin học đại cương, nhập môn lập trình. Ngôn ngữ lập trình được chọn để minh họa các kiến thức trên là C++. Các kiến thức này sẽ tạo điều kiện cho học viên tiếp tục dễ dàng nắm bắt các kiến thức các học phần tin học về sau như: cấu trúc dữ liệu và giải thuật nâng cao, phân tích và thiết kế giải thuật, đồ hoạ, hệ điều hành, trí tuệ nhân tạo, . Nội dung giáo trình gồm 4 chương: - Chương 1: Giới thiệu các khái niệm ban đầu về mối liên hệ mật thiết giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu, thiết kế và phân tích giải thuật, độ phức tạp giải thuật, . - Chương 2: Giới thiệu các phương pháp cơ bản về tìm kiếm và sắp xếp trong trên kiểu dữ liệu tuyến tính mảng. Thông qua đó, trình bày một số ý tưởng và kỹ thuật cơ bản nhằm cải tiến các giải thuật. - Chương 3: Trình bày kiểu dữ liệu con trỏ. Trên cơ sở đó, trình bày các kiểu dữ liệu động tuyến tính và có nhiều ứng dụng trong tin học là các kiểu danh sách liên kết khác nhau, ngăn xếp, hàng đợi, cũng như một số ứng dụng của chúng. - Chương 4: Giới thiệu một loại cấu trúc dữ liệu động khác là cây và các thao tác cơ bản trên cây nhị phân, cây nhị phân tìm kiếm, cây cân bằng AVL. Nhằm mục đích dành thời gian nhiều hơn cho sinh viên để làm các bài tập lớn, nên trong một số phần tác giả đã trình bày khá chi tiết các dạng cài đặt biến thể khác nhau cho các giải thuật. Các phần thứ yếu hoặc khá phức tạp sẽ được in cỡ chữ nhỏ dành cho sinh viên đọc thêm. Chắn chắn rằng trong giáo trình sẽ còn nhiều khiếm khuyết, tác giả mong muốn nhận được và rất biết ơn các ý kiến quí báu đóng góp của đồng nghiệp cũng như bạn đọc để giáo trình này có thể hoàn thiện hơn nữa về mặt nội dung cũng như hình thức trong lần tái bản sau. Đà lạt, 04/2008 Tác giả MỤC LỤC Chương I. GIỚI THIỆU CẤU TRÚC DỮ LIỆU, PHÂN TÍCH GIẢI THUẬT Trang I.1. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu I.1 I.1.1. Biểu diễn dữ liệu I.1 I.1.2. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu I.1 I.1.3. Các bước chính để giải một bài toán trên máy tính I.2 I.2. Thiết kế và phân tích giải thuật I.4 I.2.1. Thiết kế giải thuật theo phương pháp Top-Down I.4 I.2.2. Các chiến lược khác để thiết kế giải thuật I.5 I.2.3. Phân tích giải thuật và độ phức tạp của giải thuật I.5 I.2.4. Qui ước về ngôn ngữ mã giả I.9 Chương II. TÌM KIẾM VÀ SẮP XẾP TRONG II.1. Giới thiệu về sắp xếp và tìm kiếm II.1 II.1.1. Sắp xếp II.1 a. Định nghĩa sắp xếp II.1 b. Phân loại phương pháp sắp xếp II.1 c. Vài qui uớc về kiểu dữ liệu khi xét các giải thuật sắp xếp II.1 II.1.2. Tìm kiếm II.3 a. Định nghĩa phép tìm kiếm II.3 b. Phân loại các phương pháp tìm kiếm II.3 II.2. Phương pháp tìm kiếm trong II.3 II.2.1. Phương pháp tìm kiếm tuyến tính II.3 a. Dãy chưa được sắp II.3 b. Dãy đã được sắp II.5 II.2.2. Phương pháp tìm kiếm nhị phân II.6 II.3. Phương pháp sắp xếp trong II.7 II.3.1. Phương pháp sắp xếp chọn đơn giản II.8 II.3.2. Phương pháp sắp xếp chèn đơn giản II.9 II.3.3. Phương pháp sắp xếp đổi chỗ đơn giản II.10 II.3.4. Phương pháp sắp xếp đổi chỗ cải tiến (Shake Sort) II.12 II.3.5. Phương pháp sắp xếp chèn cải tiến (Shell Sort) II.14 II.3.6. Phương pháp sắp xếp phân hoạch (Quick Sort) II.16 II.3.7. Phương pháp sắp xếp trên cây có thứ tự (HeapSort) II.19 II.3.8. Phương pháp sắp xếp trộn (Merge Sort) II.25 II.3.9. Phương pháp sắp xếp dựa trên cơ số (Radix Sort) II.28 II.3.10. So sánh các phương pháp sắp xếp trong II.31 Trang Chương III. CẤU TRÚC DANH SÁCH LIÊN KẾT III.1. Giới thiệu đối tượng dữ liệu con trỏ III.1 III.1.1. So sánh cấu trúc dữ liệu tĩnh và cấu trúc dữ liệu động III.1 III.1.2. Kiểu dữ liệu con trỏ III.1 a. Định nghĩa III.1 b. Khai báo III.2 c. Các thao tác trên kiểu dữ liệu con trỏ III.3 III.1.3. Biến động III.4 a. Đặc trưng của biến động III.4 b. Truy xuất biến động III.4 c. Hai thao tác cơ bản trên biến động III.5 III.2. Danh sách liên kết (DSLK) III.7 III.2.1. Định nghĩa danh sách III.7 III.2.2. Các cách tổ chức danh sách III.7 III.3. DSLK đơn III.8 III.3.1. Tổ chức DSLK đơn, các thao tác cơ bản, tìm kiếm và sắp xếp trên kiểu DSLK đơn III.8 a. Tổ chức DSLK đơn (không có nút câm) III.8 b. Các thao tác cơ bản trên kiểu DSLK đơn III.9 c. Sắp xếp trên kiểu DSLK đơn: sắp xếp chèn, QuickSort, MergeSort, RadixSort III.17 III.3.2. Vài ứng dụng của DSLK đơn III.24 III.3.2.1. Ngăn xếp: định nghĩa, cài đặt, các phép toán cơ bản và ứng dụng của ngăn xếp III.24 III.3.2.2. Hàng đợi: định nghĩa, cài đặt, các phép toán cơ bản và ứng dụng của hàng đợi III.31 III.4. Một số kiểu DSLK khác III.34 III.4.1. DSLK đơn có nút câm III.34 III.4.2. DSLK vòng III.37 III.4.3. DSLK đối xứng III.38 a. Cấu trúc dữ liệu biểu diễn DSLK đối xứng III.39 b. Các thao tác cơ bản trên kiểu DSLK đối xứng III.39 c. Ứng dụng của DSLK đối xứng: hàng đợi hai đầu III.47 III.4.4. DS đa liên kết III.48 III.4.5. Một số ứng dụng khác của DSLK III.51 a. DS có thứ tự và DS tổ chức lại III.51 b. Biểu diễn tập hợp bằng DSLK III.53 c. Biểu diễn đa thức rời rạc bằng DSLK III.54 d. Biểu diễn ma trận thưa nhờ DSLK III.56 e. Sắp xếp tôpô III.57 Trang Chương IV. CẤU TRÚC CÂY IV.1. Định nghĩa và các khái niệm cơ bản IV.1 IV.1.1. Định nghĩa cây IV.1 IV.1.2. Các khái niệm khác IV.1 IV.2. Cây nhị phân IV.3 IV.2.1. Định nghĩa IV.3 IV.2.2. Vài tính chất của cây nhị phân IV.3 IV.2.3. Biểu diễn cây nhị phân IV.3 IV.2.4. Duyệt cây nhị phân IV.4 IV.2.5. Một cách biểu diễn khác của cây nhị phân IV.7 IV.2.6. Biểu diễn cây n - phân bằng cây nhị phân IV.8 IV.2.7. Xây dựng cây nhị phân cân bằng hoàn toàn IV.8 IV.3. Cây nhị phân tìm kiếm IV.9 IV.3.1. Định nghĩa cây nhị phân tìm kiếm IV.9 IV.3.2. Tìm kiếm một phần tử trên cây BST IV.10 IV.3.3. Chèn một phần tử vào cây BST, xây dựng cây BST IV.11 IV.3.4. Phương pháp sắp xếp bằng cây BST IV.13 IV.3.5. Xóa một phần tử khỏi cây BST, hủy cây nhị phân IV.13 IV.4. Cây nhị phân tìm kiếm cân bằng IV.16 IV.4.1. Định nghĩa IV.17 IV.4.2. Chiều cao của cây cân bằng IV.17 IV.4.3. Chỉ số cân bằng và việc cân bằng lại cây AVL IV.18 IV.4.4. Chèn một phần tử vào cây AVL IV.24 IV.4.5. Xóa một phần tử khỏi cây AVL IV.25 Bài tập. BT.1 Bài tập chương I BT.1 Bài tập chương II BT.4 Bài tập chương III BT.6 Bài tập chương IV BT.11 Tài liệu tham khảo Chương I GIỚI THIỆU CẤU TRÚC DỮ LIỆU VÀ PHÂN TÍCH GIẢI THUẬT I.1. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu I.1.1. Biểu diễn dữ liệu Một mục tiêu quan trọng của tin học là nhằm giải quyết tự động những bài toán trong thế giới thực bằng máy tính điện tử. Các thông tin về bài toán cần giải quyết trên máy tính luôn được mã hoá dưới dạng nhị phân. Các thông tin này gồm dữ liệu và các thao tác trên các dữ liệu đó. Việc biểu diễn dữ liệu ở dạng nhị phân rất bất tiện cho con người trong khi xử lý các bài toán, đặc biệt là các bài toán lớn và phức tạp. Chính vì lý do đó, các ngôn ngữ lập trình bậc cao đã cung cấp sẵn các cách biểu diễn dữ liệu trừu tượng đơn giản và có cấu trúc, nhằm giúp người lập trình không phải mất nhiều thời gian và công sức thực hiện thường xuyên lặp lại các thao tác sơ cấp nặng nề trên các kiểu dữ liệu nhị phân ở mức thấp. Tính trừu tượng của dữ liệu thể hiện ở chỗ nó không quá chú trọng đến những đặc điểm và ý nghĩa riêng của từng đối tượng cụ thể mà chỉ rút ra và phản ánh những tính chất chung nhất mà các đối tượng thuộc cùng một lớp có được. I.1.2. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu Dựa vào bản chất chung của từng nhóm dữ liệu, các đối tượng dữ liệu được phân thành các lớp. Mỗi lớp dữ liệu được thể hiện qua một kiểu dữ liệu. Một kiểu dữ liệu T là một tập hợp nào đó, mỗi phần tử của tập được gọi là một thể hiện của kiểu. Ta đã biết giải thuật (hay giải thuật) là một dãy câu lệnh rõ ràng, xác định một trình tự các thao tác trên một số đối tượng nào đó (input) sao cho sau một số hữu hạn bước thực hiện (chú ý đến tính khả thi về thời gian), ta đạt được kết quả (output) mong muốn. Giải thuật phản ánh các phép xử lý, còn đối tượng để xử lý bởi giải thuật chính là dữ liệu: dữ liệu (input) đưa vào, dữ liệu trung gian và kết qủa (output) cuối cùng. Đối với bất kỳ một lớp dữ liệu nào, nếu để ý kỹ, ta thấy trên đó luôn tồn tại những thao tác cơ bản mật thiết gắn liền với các đối tượng dữ liệu cùng kiểu đó. Khi cách biểu diễn dữ liệu thay đổi thì các thao tác gắn liền với chúng cũng thay đổi theo. Vì nếu không thì trong nhiều trường hợp việc xử lý sẽ gượng ép, thiếu tự Giới thiệu cấu trúc dữ liệu và phân tích giải thuật I.2 nhiên, khó hiểu, phức tạp khơng cần thiết và chương trình kém hiệu quả, lãng phí tài ngun trên máy tính (CPU và bộ nhớ). Chẳng hạn, đối với một chuỗi ký tự, ta có ít nhất hai cách biểu diễn chúng như được thể hiện trong ngơn ngữ lập trình Pascal và C. Với mỗi cách biểu diễn, ta sẽ có những cách xây dựng các thao tác tương ứng trên chúng khác nhau. Một ví dụ khác, sẽ thấy rõ hơn trong các chương tiếp theo, đối với một dãy các phần tử dữ liệu cùng loại, ta có thể lưu trữ chúng ít nhất bằng hai cách: lưu bằng mảng (tĩnh, động) hay lưu trữ bằng danh sách liên kết động. Khi đó, các thao tác cơ bản trên chúng như chèn, xóa, sắp xếp sẽ thực hiện theo những cách thức khác nhau và do đó có hiệu quả khác nhau. Do đó, khi nói đến một kiểu dữ liệu T, ta thường chú ý đến hai đặc trưng quan trọng và liên hệ mật thiết với nhau: - tập V các giá trị thuộc kiểu, đó là tập các giá trị hợp lệ mà đối tượng kiểu T có thể nhận và lưu trữ; - tập O các phép tốn (hay thao tác xử lý) xác định có thể thực hiện trên các đối tượng dữ liệu kiểu đó. Người ta thường viết: T = <V, O>. Trong một ngơn ngữ lập trình cấp cao cụ thể, người ta thường xây dựng sẵn một số kiểu dữ liệu đơn giản hay sơ cấp xác định, chẳng hạn với C++, ta có các kiểu dữ liệu: số (ngun, thực), ký tự, lơgic. Với kiểu số ngun, các phép tốn thường gặp là: các phép tốn số học +, -, *, / (chia ngun), % (mod, lấy phần dư) và các phép tốn so sánh như: ==, !=, ≥, ≤, >, <. Với kiểu số thực, các phép tốn thường gặp là: các phép tốn số học +, -, *, /, và các phép tốn so sánh như: ==, !=, ≥, ≤, >, <. Với kiểu lơgic, các phép tốn thường gặp là: ! (not), && (and), || (or). Với kiểu ký tự, các phép tốn thường gặp là: phép tốn ép kiểu và các phép tốn so sánh như: ==, !=, ≥, ≤, >, <, … Dựa trên các kiểu đơn giản đã có và các phương pháp xác định của ngơn ngữ lập trình qui định, ta có thể xây dựng nên các cấu trúc dữ liệu hay kiểu dữ liệu có cấu trúc phức tạp hơn nhằm phản ánh tốt hơn các loại dữ liệu phong phú và đa dạng trong thế giới thực. Chẳng hạn như: kiểu mảng, kiểu cấu trúc, kiểu hợp, kiểu file, … Một trong những phép tốn cơ bản trên các kiểu dữ liệu đó là: truy cập đến từng phần tử hay từng thành phần của đối tượng dữ liệu. I.1.3. Các bước chính để giải một bài tốn trên máy tính Để giải một bài tốn trên máy tính, ta thường trải qua các giai đoạn chính sau đây: Giới thiệu cấu trúc dữ liệu và phân tích giải thuật I.3 - Đặt bài tốn, phân tích, đặc tả và mơ hình hố bài tốn - Chọn cấu trúc dữ liệu để biểu diễn bài tốn và phát triển giải thuật (chọn kiểu dữ liệu) - Mã hóa chương trình - Thử nghiệm chương trình - Bảo trì chương trình. Hai giai đoạn đầu rất quan trọng, nó góp phần quyết định tính đúng đắn và hiệu quả của chương trình nhằm giải bài tốn. Vai trò của kiểu dữ liệu trong việc giải một bài tốn trên máy tính Khi đề cập đến một thao tác, cần phải xác định nó tác động lên loại đối tượng hay trên cấu trúc dữ liệu hoặc trong kiểu dữ liệu nào? Với mỗi mơ hình dữ liệu, có thể có nhiều cách cài đặt bởi các cấu trúc dữ liệu khác nhau. Trong mỗi cách cài đặt, có thể có một số phép tốn được thực hiện thuận lợi, nhưng một số phép tốn khác lại khơng thuận tiện. Khi đề cập đến một thao tác, cần phải xác định rõ nó tác động trên loại đối tượng hoặc kiểu dữ liệu nào? Khi cấu trúc dữ liệu thay đổi thì các giải thuật cơ bản tương ứng với nó cũng thay đổi theo. Vì vậy việc chọn cấu trúc dữ liệu nào để biểu diễn mơ hình sẽ phụ thuộc vào từng ứng dụng cụ thể. Để việc chọn cấu trúc dữ liệu biểu diễn bài tốn một cách phù hợp, cần chú ý đến những quan hệ giữa các đối tượng và thành phần dữ liệu với nhau; ngồi ra, ta còn cần phải lưu ý đến những phép tốn cơ bản nào sẽ được thực hiện thường xun trên các đối tượng dữ liệu đó. Chẳng hạn, đối với một dãy các đối tượng dữ liệu cùng loại, nếu số lượng các đối tượng này khơng q lớn (để có thể lưu ở bộ nhớ trong), biến động nhiều, hơn nữa các phép tốn thêm và hủy các đối tượng xảy ra rất thường xun thì ta nên chọn kiểu dữ liệu là danh sách liên kết động hơn là kiểu mảng tĩnh để lưu trữ dãy đối tượng này. Khi xây dựng các giải thuật nhằm giải quyết một bài tốn, ta phải dựa trên các u cầu cần xử lý để xem xét kỹ lưỡng, cũng như nên dựa trên các đặc trưng của bài tốn và tài ngun (tốc độ xử lý và khả năng lưu trữ của hệ thống máy tính) thực tế hiện có. Tóm lại, khi xây dựng các kiểu dữ liệu nhằm giải quyết một bài tốn cụ thể, ta nên để ý các tiêu chuẩn sau: - Phản ánh đúng thực tế: có dự trù đến khả năng biến đổi của dữ liệu trong chu trình sống của nó. Đây là tiêu chuẩn rất quan trọng nhằm quyết định tính đúng đắn của tồn bộ bài tốn. - Cấu trúc dữ liệu được xây dựng cần phù hợp với các thao tác trên đó (đặc biệt là các thao tác được sử dụng nhiều nhất). Khi đó, việc phát triển các giải thuật sẽ đơn giản, tự nhiên hơn và đạt hiệu quả cao về mặt tốc độ và bộ nhớ. Giới thiệu cấu trúc dữ liệu và phân tích giải thuật I.4 - Tiết kiệm tài ngun (tốc độ xử lý và dung lượng bộ nhớ): Đối với các giải thuật khơng q tầm thường, hai u cầu này thường mâu thuẫn nhau và khó đạt được tối ưu đồng thời. Tùy theo u cầu của bài tốn và tài ngun thực tế, ta nên chọn giải thuật cho phù hợp. I.2. Thiết kế và phân tích giải thuật I.2.1. Thiết kế giải thuật theo phương pháp Top-Down Các bài tốn giải được trên máy tính ngày càng đa dạng và phức tạp. Việc xây dựng mơ hình cùng với các giải thuật và cách cài đặt các chương trình giải chúng ngày càng có quy mơ lớn và phức tạp, thường đòi hỏi cơng sức đồng thời của cả một tập thể các nhóm phân tích - thiết kế viên cũng như các thảo chương viên. Mặt khác, việc thử nghiệm, sửa chữa, bổ sung, mở rộng, bảo trì các hệ chương trình lớn chiếm tỷ lệ thời gian đáng kể so với tổng thời gian xây dựng hệ chương trình. Để chương trình trở nên dễ hiểu, dễ kiểm tra, dễ bảo trì và dễ mở rộng hơn, đặc biệt là trong mơi trường làm việc theo nhóm, người ta thường áp dụng chiến thuật “chia để trị” bằng phương pháp thiết kế từ trên xuống (top-down design) hay thiết kế từ khái qt đến chi tiết. Đó là cách phân tích bài tốn, xuất phát từ dữ kiện và các mục tiêu đặt ra nhằm đưa ra các cơng việc chủ yếu (theo cấu trúc phân cấp, chưa vội sa đà vào tiểu tiết), rồi mới chia dần từng cơng việc lớn thành các cơng việc (module) chi tiết hơn; nếu các module này vẫn còn phức tạp ta lại chia tiếp chúng thành các module nhỏ hơn cho tới khi đạt đến các phần việc cơ bản mà ta đã biết cách giải quyết. Việc giải bài tốn lớn ban đầu qui về việc kết hợp những lời giải của các bài tốn con. Đó cũng là cơ sở của kỹ thuật lập trình có cấu trúc. Khi thiết kế từng module nên chú ý đến tính độc lập tương đối của chúng đối với các module khác. Phương pháp thiết kế này hỗ trợ đắc lực trong việc lập trình theo nhóm của cơng nghệ phần mềm. Khi đó, nhiều người có thể cùng chia xẻ giải quyết các vấn đề lớn mà khơng cần quan tâm tới chi tiết phần việc của người khác mà sau đó vẫn có thể nối kết các module nhỏ để cả bài tốn lớn được giải quyết. Q trình này làm cho việc tìm hiểu cũng như sửa lỗi, bổ sung, mở rộng chương trình trở nên dễ dàng và đơn giản hơn. Việc phân tích và thiết kế bài tốn lớn thành các bài tốn con thường chiếm thời gian lẫn cơng sức lớn hơn nhiều so với nhiệm vụ lập trình (coding). Giới thiệu cấu trúc dữ liệu và phân tích giải thuật I.5 I.2.2. Các chiến lược khác để thiết kế giải thuật Ngồi chiến lược chia để trị, người ta còn dùng các phương pháp thiết kế giải thuật sau: phương pháp tham lam, phương pháp qui hoạch động, phương pháp quay lui, phương pháp nhánh và cận. Phương pháp tham lam thường dùng để tìm nghiệm tối ưu trong một tập nghiệm chấp nhận được S nào đó được xây dựng theo một hàm chọn để bổ sung những phần tử vào S theo một cách thích hợp. Phương pháp qui hoạch động sử dụng kỹ thuật “đi từ dưới lên”: xuất phát từ nghiệm của những bài tốn con sơ cấp (được lưu giữ trong một bảng nhằm tránh mất cơng sức giải lại những bài tốn con này sẽ phát sinh khi cần giải những bài con lớn hơn sau này), ta xây dựng nghiệm của những bài tốn con lớn hơn và lưu tiếp vào bảng; cứ tiếp tục như vậy cho đến khi tìm được nghiệm của bài tốn lớn ban đầu từ bảng. Phương pháp quay lui thường dùng để tìm một hoặc tất cả nghiệm của bài tốn dưới dạng một vectơ nghiệm có thể chưa biết trước độ dài của nó và có thể được xác định dần trong q trình giải. Đây là một kỹ thuật rất quan trọng trong việc thiết kế giải thuật. Phương pháp nhánh và cận là một dạng cải tiến của phương pháp quay lui để tìm nghiệm tối ưu của bài tốn. Trong q trình từng bước mở rộng nghiệm từng phần để đạt đến nghiệm tối ưu của bài tốn (dưới dạng vectơ), nếu biết các nghiệm mở rộng đều có hàm giá lớn hơn giá của nghiệm tốt nhất ở thời điểm đó, thì ta khơng cần mở rộng nghiệm một phần theo nhánh này nữa và quay lui sang tìm nghiệm trên nhánh khác có triển vọng hơn. Các chiến lược này sẽ được nghiên cứu chi tiết trong các học phần tiếp theo. I.2.3. Phân tích giải thuật và độ phức tạp của giải thuật a. Các vấn đề cần lưu ý khi phân tích giải thuật - Tính đúng đắn của giải thuật: cần trả lời câu hỏi liệu giải thuật có thể hiện đúng lời giải của bài tốn hay khơng? Thơng thường người ta cài đặt giải thuật đó trên máy tính và thử nghiệm nó với một số bộ dữ liệu mẫu nào đó rồi so sánh kết quả thử nghiệm với kết quả được lấy từ những thơng tin và phương pháp khác mà ta đã biết chắc đúng. Nhưng cách thử này chỉ phát hiện được tính sai chứ chưa thể bảo đảm được tính đúng của giải thuật. Để chứng minh được tính đúng đắn của giải thuật nhiều khi đòi hỏi phải sử dụng các cơng cụ tốn học khá phức tạp, nhưng đây là một cơng việc khơng phải ln ln dễ dàng. - Tính đơn giản của giải thuật: thể hiện qua tính dễ hiểu, tự nhiên, dễ lập trình, dễ chỉnh lý. Thơng thường các giải thuật q đơn sơ chưa hẳn là cách tốt nhất và nó thường gây tổn phí thời gian và bộ nhớ khi thực hiện. Nhưng trên thực tế ta nên cân nhắc giữa tính đơn giản của giải thuật và thời gian lẫn cơng sức để xây dựng các giải thuật tinh tế, hiệu quả hơn nhưng chỉ sử dụng q ít lần với bộ dữ liệu q nhỏ với điều kiện thời gian hạn chế trong một mơi trường lập trình thực tế. - Tốc độ thực hiện và dung lượng bộ nhớ cần chiếm dụng của giải thuật: Thơng thường hiếm khi cả hai u cầu tối ưu về thời gian và bộ nhớ được thỏa mãn đồng thời. Các giải thuật khơng tầm thường nếu có tốc độ thực hiện cao thì . THIỆU CẤU TRÚC DỮ LIỆU, PHÂN TÍCH GIẢI THUẬT Trang I.1. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu I.1 I.1.1. Biểu diễn dữ liệu. Tài liệu tham khảo Chương I GIỚI THIỆU CẤU TRÚC DỮ LIỆU VÀ PHÂN TÍCH GIẢI THUẬT I.1. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu

— Xem thêm —

Xem thêm: Giáo trình cấu trúc dữ liệu và giải thuật, Giáo trình cấu trúc dữ liệu và giải thuật, Giáo trình cấu trúc dữ liệu và giải thuật

Lên đầu trang

Tài liệu liên quan

Từ khóa liên quan

Đăng ký

Generate time = 0.113039016724 s. Memory usage = 13.95 MB