PHẦN 3


THUẬT TOÁN
CHƯƠNG 15
PHÂN TÍCH THUẬT TOÁN


Với một vấn đề đặt ra có thể có nhiều thuật toán giải, chẳng hạn người ta đã tìm ra rất nhiều thuật toán sắp xếp một mảng dữ liệu (chúng ta sẽ nghiên cứu các thuật toán sắp xếp này trong chương 17). Trong các trường hợp như thế, khi cần sử dụng thuật toán người ta thường chọn thuật toán có thời gian thực hiện ít hơn các thuật toán khác. Mặt khác, khi bạn đưa ra một thuật toán để giải quyết một vấn đề thì một câu hỏi đặt ra là thuật toán đó có ý nghĩa thực tế không? Nếu thuật toán đó có thời gian thực hiện quá lớn chẳng hạn hàng năm, hàng thế kỷ thì đương nhiên không thể áp dụng thuật toán này trong thực tế. Như vậy chúng ta cần đánh giá thời gian thực hiện thuật toán. Phân tích thuật toán, đánh giá thời gian chạy của thuật toán là một lĩnh vực nghiên cứu quan trong của khoa học máy tính. Trong chương này, chúng ta sẽ nghiên cứu phương pháp đánh giá thời gian chạy của thuật toán bằng cách sử dụng ký hiệu ô lớn, và chỉ ra cách đánh gía thời gian chạy thuật toán bằng ký hiệu ô lớn. Trước khi đi tới mục tiêu trên, chúng ta sẽ thảo luận ngắn gọn một số vấn đề liên quan đến thuật toán và tính hiệu quả của thuật toán.
15.1 THUẬT TOÁN VÀ CÁC VẤN ĐỀ LIÊN QUAN
Thuật toán được hiểu là sự đặc tả chính xác một dãy các bước có thể thực hiện được một cách máy móc để giải quyết một vấn đề. Cần nhấn mạnh rằng, mỗi thuật toán có một dữ liệu vào (Input) và một dữ liệu ra (Output); khi thực hiện thuật toán (thực hiện các bước đã mô tả), thuật toán cần cho ra các dữ liệu ra tương ứng với các dữ liệu vào.
Biểu diễn thuật toán. Để đảm bảo tính chính xác, chỉ có thể hiểu một cách duy nhất, thụât toán cần được mô tả trong một ngôn ngữ lập trình thành một chương trình (hoặc một hàm, một thủ tục), tức là thuật toán cần được mô tả dưới dạng mã (code). Tuy nhiên, khi trình bày một thuật toán để cho ngắn gọn nhưng vẫn đảm bảo đủ chính xác, người ta thường biểu diễn thuật toán dưới dạng giả mã (pseudo code). Trong cách biểu diễn này, người ta sử dụng các câu lệnh trong một ngôn ngữ lập trình (pascal hoặc C++) và cả các ký hiệu toán học, các mệnh đề trong ngôn ngữ tự nhiên (tiếng Anh hoặc tiếng Việt chẳng hạn). Tất cả các thuật toán được đưa ra trong sách này đều được trình bày theo cách này. Trong một số trường hợp, để người đọc hiểu được ý tưởng khái quát của thuật toán, người ta có thể biểu diễn thuật toán dưới dạng sơ đồ (thường được gọi là sơ đồ khối).
Tính đúng đắn (correctness) của thuật toán. Đòi hỏi truớc hết đối với thuật toán là nó phải đúng đắn, tức là khi thực hiện nó phải cho ra các dữ liệu mà ta mong muốn tương ứng với các dữ liệu vào. Chẳng hạn nếu thuật toán được thiết kế để tìm ước chung lớn nhất của 2 số nguyên dương, thì khi đưa vào 2 số nguyên dương (dữ liệu vào) và thực hiện thuật toán phải cho ra một số nguyên dương (dữ liệu ra) là ước chung lớn nhất của 2 số nguyên đó. Chứng minh một cách chặt chẽ (bằng toán học) tính đúng đắn của thuật toán là một công việc rất khó khăn. Tuy nhiên đối với phần lớn các thuật toán được trình bày trong sách này, chúng ta có thể thấy (bằng cách lập luận không hoàn toàn chặt chẽ) các thuật toán đó là đúng đắn, và do đó chúng ta không đưa ra chứng minh chặt chẽ bằng toán học.
Một tính chất quan trong khác của thuật toán là tính hiệu quả (efficiency), chúng ta sẽ thảo luận về tính hiệu quả của thuật toán trong mục tiếp theo.
Đến đây chúng ta có thể đặt câu hỏi: có phải đối với bất kỳ vấn đề nào cũng có thuật toán giải (có thể tìm ra lời giải bằng thuật toán)? câu trả lời là không. Người ta đã phát hiện ra một số vấn đề không thể đưa ra thuật toán để giải quyết nó. Các vấn đề đó được gọi là các vấn đề không giải được bằng thuật toán.
15.2 TÍNH HIỆU QUẢ CỦA THUẬT TOÁN
Người ta thường xem xét thuật toán, lựa chọn thuật toán để áp dụng dựa vào các tiêu chí sau:
Thuật toán đơn giản, dễ hiểu.
Thuật toán dễ cài đặt (dễ viết chương trình)
Thuật toán cần ít bộ nhớ
Thuật toán chạy nhanh
Khi cài đặt thuật toán chỉ để sử dụng một số ít lần, người ta thường lựa chọn thuật toán theo tiêu chí 1 và 2. Tuy nhiên, có những thuật toán được sử dụng rất nhiều lần, trong nhiều chương