Giải thuật là gì? Cách thiết kế giải thuật đơn giản, dễ hiểu

Giải thuật là một thuật ngữ cơ bản dành cho những ai muốn bước chân vào thế giới lập trình. Vậy thì giải thuật là gì, những cách thiết kế giải thuật đơn giản? Hãy tham khảo bài viết dưới đây nhé!

Giải thuật là gì?

I. Giải thuật là gì?

1. Khái niệm

Giải thuật (hay còn gọi là thuật toán – tiếng Anh là Algorithms) là một tập hợp hữu hạn các chỉ thị để được thực thi theo một thứ tự nào đó nhằm thu được kết quả mong muốn. 

Nói một cách ngắn gọn, giải thuật là tập hợp các bước, thao tác để giải quyết một vấn đề gì đó.

Giải thuật là tập hợp các thao tác để giải quyết vấn đề

Giả sử như bạn có một vấn đề cần giải quyết đó là biến gạo thành cơm để ăn (hay nói cách khác là nấu cơm), bạn sẽ phải thực hiện những bước sau đây:

• Lấy gạo – vo gạo – đong nước – đặt vào nồi – đậy nắp – cắm điện – bật nút – đợi cơm chín.

Giải thuật là độc lập với các ngôn ngữ lập trình, tức là một giải thuật có thể được triển khai trong nhiều ngôn ngữ lập trình khác nhau.

2. Những đặc trưng của giải thuật

Không phải tất cả các thủ tục đều được gọi là một giải thuật. Một giải thuật nên có các đặc điểm sau:

• Tính xác định: Giải thuật nên rõ ràng và không mơ hồ. Mỗi một giai đoạn (hay mỗi bước) nên rõ ràng và chỉ mang một mục đích nhất định.
• Dữ liệu đầu vào xác định: Một giải thuật nên có 0 hoặc nhiều hơn dữ liệu đầu vào đã xác định.
• Kết quả đầu ra: Một giải thuật nên có một hoặc nhiều dữ liệu đầu ra đã xác định, và nên kết nối với kiểu kết quả bạn mong muốn.
• Tính dừng: Các giải thuật phải kết thúc sau một số hữu hạn các bước.

Giải thuật dừng lại sau 1 số bước nhất định

• Tính hiệu quả: Một giải thuật nên là có thể thi hành được với các nguồn có sẵn, tức là có khả năng giải quyết hiệu quả vấn đề trong điều kiện thời gian và tài nguyên cho phép.
• Tính phổ biến: Một giải thuật có tính phổ biến nếu giải thuật này có thể giải quyết được một lớp các vấn đề tương tự.
• Độc lập: Một giải thuật nên có các chỉ thị độc lập với bất kỳ phần code lập trình nào.

3. Tầm quan trọng của giải thuật

Cấu trúc dữ liệu và giải thuật rất quan trọng trong lập trình, không riêng ngôn ngữ Java, PHP, Python.. tất cả ngôn ngữ lập trình khác điều cần cấu trúc dữ liệu và giải thuật.

Việc chuyển đổi ngôn ngữ lập trình không quá khó. Thứ quyết định và sẽ đi theo bạn là cấu trúc dữ liệu và giải thuật. Việc sở hữu một tư duy giải thuật sẽ giúp bạn hoàn thành tốt các công việc lập trình. 

II. Cách thiết kế giải thuật

1. Ngôn ngữ viết 

Thiết kế giải thuật bằng ngôn ngữ viết là liệt kê tuần tự các bước bằng ngôn ngữ tự nhiên để biểu diễn thuật toán. 

Ưu điểm: 

Đơn giản, không cần kiến thức về cách biểu diễn (mã giả, lưu đồ,…)

Nhược điểm:

• Dài dòng, không có cấu trúc.
• Đôi lúc khó hiểu và không biểu diễn được thuật toán.

Ví dụ: Dùng ngôn ngữ viết để tìm ra 3 số lớn nhất trong a, b, c

• Bước 1: Gán max = a.
• Bước 2: Nếu b > max thì gán max = b.
• Bước 3: Nếu c > max thì max chính là c.

2. Lưu đồ

Lưu đồ bao gồm: 

• Điểm bắt đầu và điểm kết thúc.
• Thao tác nhập/xuất dữ liệu.
• Thao tác xử lý.
• Điều khiển rẽ nhánh.
• Đường tiến trình.
• Chú thích.
• Ký hiệu kết nối cùng trang hay sang trang khác. 

Lưu đồ

Ưu điểm: 

Trực quan, dễ hình dung. 

Nhược điểm: 

Cồng kềnh nếu vấn đề xử lý quá phức tạp. 

3. Mã giả

Ngôn ngữ của mã giả khá giống ngôn ngữ lập trình. Nó thường dùng cấu trúc chuẩn hóa, chẳng hạn tựa Pascal, C. Nó cũng sử dụng các ký hiệu toán học, biến, hàm.

Một mã giả

Ưu điểm: 

Không cồng kềnh như lưu đồ khối

Nhược điểm:

Không trực quan bằng lưu đồ khối.

4. Ngôn ngữ lập trình

• Dùng ngôn ngữ máy tính (C, Pascal,…) để diễn tả thuật toán, cấu trúc dữ liệu thành câu lệnh.
• Dùng phương pháp tinh chế từng bước để chuyển hóa bài toán sang mã chương trình cụ thể.
• Để có kỹ năng lập trình đòi hỏi phải cần học tập và thực hành.

Viết “Hello world” bằng ngôn ngữ Java

III. Phân tích giải thuật (Miêu tả + hình ảnh)

1. Vì sao cần phản phân tích giải thuật

Trong khi giải một bài toán chúng ta có thể có một số giải thuật khác nhau, vấn đề là cần phải đánh giá các giải thuật đó để lựa chọn một giải thuật tốt nhất.

2. Phân tích lý thuyết

Có thể coi đây là phân tích chỉ dựa trên lý thuyết. Hiệu quả của giải thuật được đánh giá bằng việc giả sử rằng tất cả các yếu tố khác (ví dụ: tốc độ vi xử lý, …) là hằng số và không ảnh hưởng tới sự triển khai giải thuật.

3. Phân tích tiệm cận:

Việc phân tích giải thuật này được tiến hành sau khi đã tiến hành trên một ngôn ngữ lập trình nào đó.

Sau khi chạy và kiểm tra đo lường các thông số liên quan thì hiệu quả của giải thuật dựa trên các thông số như thời gian chạy, thời gian thực thi, lượng bộ nhớ cần dùng, …

IV. Độ phức tạp của giải thuật

1. Độ phức tạp của giải thuật là gì?

Độ phức tạp giải thuật là một hàm ước lượng (có thể không chính xác) số phép tính mà giải thuật cần thực hiện (từ đó dễ dàng suy ra thời gian thực hiện của giải thuật) đối với bộ dữ liệu đầu vào (Input) có kích thước n.

Trong đó, n có thể là số phần tử của mảng trong trường hợp bài toán sắp xếp hoặc tìm kiếm, hoặc có thể là độ lớn của số trong bài toán kiểm tra số nguyên tố, …

Giả sử X là một giải thuật và n là kích cỡ của dữ liệu đầu vào. Thời gian và lượng bộ nhớ được sử dụng bởi giải thuật X là hai nhân tố chính quyết định hiệu quả của giải thuật X:

• Nhân tố thời gian: Thời gian được đánh giá bằng việc tính số phép tính chính (chẳng hạn như các phép so sánh trong thuật toán sắp xếp).

Các phép so sánh trong thuật toán sắp xếp

• Nhân tố bộ nhớ: Lượng bộ nhớ được đánh giá bằng việc tính lượng bộ nhớ tối đa mà giải thuật cần sử dụng.

Độ phức tạp của một giải thuật (một hàm f(n)) cung cấp mối quan hệ giữa thời gian chạy và/hoặc lượng bộ nhớ cần được sử dụng bởi giải thuật.

2. Độ phức tạp bộ nhớ trong phân tích giải thuật (Space complexity)

Nhân tố bộ nhớ của một giải thuật biểu diễn lượng bộ nhớ mà một giải thuật cần dùng trong vòng đời của giải thuật. 

Lượng bộ nhớ (giả sử gọi là S(P)) mà một giải thuật cần sử dụng là tổng của hai thành phần sau:

• Phần cố định (giả sử gọi là C) là lượng bộ nhớ cần thiết để lưu giữ dữ liệu và các biến nào đó (phần này độc lập với kích cỡ của vấn đề). Ví dụ: các biến và các hằng đơn giản, …
• Phần biến đổi (giả sử gọi là SP(I)) là lượng bộ nhớ cần thiết bởi các biến, có kích cỡ phụ thuộc vào kích cỡ của vấn đề. Ví dụ: cấp phát bộ nhớ động, cấp phát bộ nhớ đệ qui, …

Từ trên, ta sẽ có S(P) = C + SP(I). Bạn theo dõi ví dụ đơn giản sau:

Ở đây chúng ta có ba biến A, B và C và một hằng số. Do đó: S(P) = 1+3.

Bây giờ, lượng bộ nhớ sẽ phụ thuộc vào kiểu dữ liệu của các biến và hằng đã cho và sẽ bằng tích của tổng trên với bộ nhớ cho kiểu dữ liệu tương ứng.

3. Độ phức tạp thời gian trong phân tích giải thuật (Time Complexity)

Nhân tố thời gian của một giải thuật biểu diễn lượng thời gian chạy cần thiết từ khi bắt đầu cho đến khi kết thúc một giải thuật. 

Thời gian yêu cầu có thể được biểu diễn bởi một hàm T(n), trong đó T(n) có thể được đánh giá như là số các bước.

Ví dụ, phép cộng hai số nguyên n-bit sẽ có n bước. Do đó, tổng thời gian tính toán sẽ là T(n) = c*n

Trong đó c là thời gian để thực hiện phép cộng hai bit. Ở đây, chúng ta xem xét hàm T(n) tăng tuyến tính khi kích cỡ dữ liệu đầu vào tăng lên.

Trên đây là khái niệm về giải thuật và cách thiết kế giải thuật đơn giản, dễ hiểu. Hi vọng bài viết này sẽ giúp ích cho bạn. Đừng quên chia sẻ bài viết nếu thấy hữu ích nhé!