Giới thiệu giáo trình ” Giáo Trình Cấu Trúc Dữ Liệu Và Giải Thuật “
1.4. GIẢI THUẬT – PHÂN TÍCH VÀ ĐÁNH GIÁ GIẢI THUẬT
1.4.1. Giải thuật
Giải thuật (algorithm) là một trong những khái niệm quan trọng nhất trong tin học. Giải thuật chỉ ra một quy trình để thực hiện một công việc. Một trong những giải thuật nổi tiếng nhất, có từ thời cổ Hy Lạp là giải thuật Euclid, tìm ước số chung lớn nhất của hai số nguyên. Có thể mô tả giải thuật này như sau:
Giải thuật Euclid
Vào: m, n nguyên dương
Ra: d, ước chung lớn nhất của m và n.
Phương pháp
Bước 1: Tìm r, phần dư của phép chia m cho n
Bước 2: Nếu r = 0, thì d – n (gán giá trị của n cho d) và dừng lại
Ngược lại, thì m← n, n – r và quay lại bước 1
1.4.1.1. Khái niệm
Giải thuật là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết vấn đề đặt ra.
1.4.1.2. Đặc trưng của giải thuật
Để hiểu đầy đủ ý nghĩa của giải thuật, chúng ta nêu ra 5 đặc trưng của nó:
i) Bộ dữ liệu vào: Mỗi giải thuật cần có một số lượng dữ liệu vào. Đó là các giá trị cần đưa vào khi giải thuật bắt đầu làm việc. Các dữ liệu này cần được lấy từ các tập hợp giá trị cụ thể nào đó. Chẳng hạn, trong giải thuật Euclid trên, m và n là các dữ liệu vào lấy từ tập các số nguyên dương.
ii) Dữ liệu ra: Mỗi giải thuật cần có một hoặc nhiều dữ liệu ra. Đó là các giá trị có quan hệ hoàn toàn xác định với các dữ liệu vào và là kết quả của sự thực hiện giải thuật. Trong giải thuật Euclid có một dữ liệu ra, đó là d, khi thực hiện đến bước 2 và phải dừng lại (trường hợp r = 0), giá trị của d là ước chung lớn nhất của m và n.
iii) Tính xác định: Mỗi bước của giải thuật cần phải được mô tả một các chính xác, chỉ có một cách hiều duy nhất. Đây là một đòi hỏi rất quan trọng. Bởi vì, nếu một bước có thể hiểu theo nhiều cách khác nhau, thì cùng một dữ liệu vào, những người thực hiện giải thuật khác nhau có thể dẫn đến các kết quả khác nhau. Để đảm bảo được tính xác định giải thuật cần phải được mô tả trong các ngôn ngữ lập trình. Trong các ngôn ngữ này, các mệnh đề được tạo thành theo quy tắc cú pháp nghiêm ngặt và chỉ có một ý nghĩa duy nhất.
iv) Tính khả thi: Tất cả các phép toán có mặt trong các bước của giải thuật phải đủ đơn giản. Điều này có nghĩa là, người lập trình có thể thực hiện chỉ bằng giấy trắng và bút trong khoảng thời gian hữu hạn. Chẳng hạn, với giải thuật Euclid, ta chỉ cần thực hiện các phép chia số nguyên, các phép gán và phép so sánh để biết được r = 0 hay r = 0.
v) Tính dừng: Với mọi bộ dữ liệu vào thoả mãn các điều kiện của dữ liệu vào, giải thuật phải dừng lại sau một số hữu hạn các bước thực hiện. Chẳng hạn, giải thuật Euclid thoả mãn điều kiện này. Bởi vì, khi thực hiện bước 1 thì giá trị của r nhỏ hơn n, nếu r ≠ 0 thì giá trị của n ở bước 2 là giá trị của r ở bước trước, ta có n > r = n₁> r = n2 > r2… Dãy số nguyên dương giảm dần cần phải kết thúc ở 0, do đó sau một số bước nào đó giá trị của r phải bằng 0, giải thuật dừng.
1.4.2. Biểu diễn giải thuật
Có nhiều phương pháp biểu diễn giải thuật. Có thể biểu diễn giải thuật bằng danh sách các bước, các bước được diễn đạt bằng ngôn ngữ tự nhiên và các ký hiệu toán học. Có thể biểu diễn bằng sơ đồ khối. Tuy nhiên, như đã trình bày, để đảm bảo tính xác định của giải thuật thì nên biểu diễn nó bằng ngôn ngữ lập trình.
1.4.3. Phân tích giải thuật
Giả sử đối với một bài toán nào đó chúng ta có một số giải thuật giải. Một câu hỏi đặt ra là, chúng ta cần chọn giải thuật nào trong số giải thuật đã có để giải bài toán một cách hiệu quả nhất. Sau đây ta phân tích giải thuật và đánh giá độ phức tạp tính toán của nó.
1.4.3.1. Tính hiệu quả của giải thuật
Khi giải quyết một vấn đề, chúng ta cần chọn trong số các giải thuật, một giải thuật mà chúng ta cho là tốt nhất. Vậy ta cần lựa chọn giải thuật dựa trên cơ sở nào? Thông thường ta dựa trên hai tiêu chuẩn sau đây:
1. Giải thuật đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình).
2. Giải thuật sử dụng tiết kiệm nhất nguồn tài nguyên của máy tính và đặc biệt, chạy nhanh nhất có thể được.
Khi ta viết một chương trình chỉ để sử dụng một số ít lần và chi phí cho thời gian viết chương trình vượt xa chi phí cho việc chạy chương trình thì tiêu chuẩn (1) là quan trọng nhất. Nhưng có trường hợp ta cần viết các chương trình để sử dụng nhiều lần, cho nhiều người sử dụng, khi đó giá của thời gian chạy chương trình sẽ vượt xa giá viết nó. Chẳng hạn, các hàm sắp xếp, tìm kiếm được sử dụng rất nhiều lần, bởi rất nhiều người trong các bài toán khác nhau. Trong trường hợp này ta cần dựa trên tiêu chuẩn (2). Ta sẽ cài đặt giải thuật có thể rất phức tạp, miễn là chương trình nhận được chạy nhanh hơn các giải thuật khác.
Tiêu chuẩn (2) được xem là tính hiệu quả của giải thuật. Tính hiệu quả của giải thuật bao gồm hai nhân tố cơ bản:
Dung lượng nhớ cần thiết để lưu giữ các dữ liệu vào, các kết quả tính toán trung gian và các kết quả của giải thuật.
– Thời gian cần thiết để thực hiện giải thuật (ta gọi là thời gian chạy chương trình, thời gian này không phụ thuộc vào các yếu tố vật lý của máy tính như tốc độ xử lý của máy tính, ngôn ngữ viết chương trình,…).
Chúng ta sẽ chỉ quan tâm đến thời gian thực hiện giải thuật. Vì vậy khi nói đến đánh giá độ phức tạp của giải thuật, có nghĩa là ta nói đến đánh giá thời gian thực hiện. Một giải thuật có hiệu quả được xem là giải thuật có thời gian chạy ít hơn các giải thuật khác.
