Khái niệm giải thuật là gì ?

Tên tiếng Anh của giải thuật Algorithms, bên cạnh đó còn có tên là thuật toán. Là một tập hợp hữu hạn các chỉ thị để việc thực thi diễn ra theo một thứ tự nào đó cùng với đó để thu được kết quả theo yêu cầu người sử dụng. Bên cạnh đó, thì giải thuật là độc lập với các ngôn ngữ lập trình, có nghĩa 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.

Tìm hiểu một số giải thuật quan trọng

  • Giải thuật Tìm kiếm: Giải thuật để tìm kiếm một phần tử trong một cấu trúc dữ liệu.
  • Giải thuật Chèn: Giải thuật để chèn phần từ vào trong một cấu trúc dữ liệu.
  • Giải thuật Sắp xếp: Giải thuật để sắp xếp các phần tử theo thứ tự nào đó.
  • Giải thuật Xóa: Giải thuật để xóa một phần tử đang tồn tại từ một cấu trúc dữ liệu.
  • Giải thuật Cập nhật: Giải thuật để cập nhật (hay update) một phần tử đã tồn tại trong một cấu trúc dữ liệu.

Đặc điểm của giải thuật là gì?

Đặc điểm đặc trưng của một giải thuật:

  • 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.
  • 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.
  • 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ự.
  • 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.
  • 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.
  • 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.
  • Độ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.

Tất tần tật cách viết một giải thuật ?

Tiêu chuẩn của một giải thuật, bạn đừng tìm, bởi vì sẽ không có bất kỳ quy định nào cho trước để viết các thuật toán cả. Trên thực tế các ngôn ngữ lập trình đều có các vòng lặp (do, while, for) và các lệnh điều khiển luồng (if-else), … Với các lệnh này, bạn có thể sử dụng để viết một giải thuật

Vấn đề viết giải thuật là một tiến trình và được thực thi sau khi bạn đã định vị rõ ràng vấn đề cần giải quyết. Chính vì vậy, để viết các giải thuật theo cách thức là theo từng bước một. Đầu tiên từ việc định vị vấn đề, tiếp theo đó chúng ta sẽ thiết kế ra những giải pháp để giải quyết vấn đề đó và cuối cùng là hoàn thành việc viết giải thuật.

Ví dụ viết giải thuật

Các ví dụ dưới đây là khá đơn giản vì đây chỉ là ví dụ minh họa mở đầu cơ bản cho cách viết giải thuật thôi, chính vì vậy mình nghĩ càng đơn giản sẽ càng tốt hơn cho giải thuật của mình. Cùng theo dõi bạn nhé

Bài toán: Thực hiện trừ hai số hiển thị ra kết quả

Bước 1: Bắt đầu
Bước 2: Khai báo kiểu dữ liệu ba số x, y & z 
Bước 3: Định nghĩa các giá trị của x & y
Bước 4: Trừ các giá trị của x & y
Bước 5: Lưu trữ kết quả của Bước 4 vào biến z
Bước 6: Print biến z
Bước 7: Kết thúc

Cách khác thể hiện bài toán

Bước 1: Bắt đầu
Bước 2: Lấy giá trị của x & y
Bước 3: z ← x - y
Bước 4: Hiển thị z
Bước 5: Kết thúc

Phương thức thứ hai được sử dụng để miêu tả một giải thuật, trong khi thiết kế và phân tích các giải thuật. Nhìn vào cách thứ hai này, người ta có thể biết các phép tính nào đang được sử dụng và cách tiến trình thực thi. Cách thứ hai này giúp dễ dàng phân tích giải thuật khi đã bỏ qua các phần định nghĩa không cần thiết. Một bài toán có thể được giải theo nhiều cách khác nhau. Chúng ta viết một giải thuật để tìm giải pháp để xử lý một bài toán nào đó.

Chi tiết giải thuật là gì? Cùng nhau phân tích

Kết quả của một giải thuật thực tế có thể được phân tích dựa trên 2 góc độ: trước khi phân tích và sau khi phân tích.

  • Phân tích tiệm cận: 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, lượng bộ nhớ cần dùng, thời gian thực thi,… 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 đó.
  • Phân tích lý thuyết: Kết 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. Có thể coi đây là phân tích chỉ dựa trên lý thuyết.

Độ phức tạp giải thuật (Algorithm Complexity)

Trên thực tế, độ 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ùng với bộ dữ liệu đầu vào (Input) có kích thước n 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). Chi tiết hơn, n có thể là số phần tử của mảng trong trường hợp bài toán tìm kiếm và sắp xếp, hoặc có thể là độ lớn của số trong bài toán kiểm tra các số nguyên tố tự nhiên,…

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

  • 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.
  • 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).

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

Độ phức tạp bộ nhớ (Space complexity) trong phân tích giải thuật là gì?

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 chính là  nhân tố bộ nhớ của một giải thuật. Bên cạnh đó, 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 đây:

  • 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ớ đệ qui, cấp phát bộ nhớ động,…
  • 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 hằng đơn giản và các biến.

Một ví dụ đơn giản:

Giải thuật: tìm tổng hai số X, Y
Bước 1 -  Bắt đầu
Bước 2 -  Z ← X + Y + 10
Bước 3 -  Kết thúc

Trên thực tế, ở đây chúng ta có ba biến X, Y và Z và một hằng số. Cho nên: S(P) = 1+3.

Bây giờ, 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 và lượng bộ nhớ sẽ phụ thuộc vào kiểu dữ liệu của các biến.

Độ phức tạp thời gian (Time Complexity) trong phân tích 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. 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.

Cụ thể một phép cộng hai số nguyên n-bit sẽ có n bước thực hiện. Cho nên, 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 2 bit. Ngoài ra, bạn có thể xem xét hàm T(n) tăng tuyến tính khi sự tăng lên của kích cỡ dữ liệu input.

Với bài viết ngày hôm nay, Zephyrfalcon đã cung cấp cho bạn câu trả lời cho câu hỏi “Giải thuật là gì? Cách viết một giải thuật”. Hy vọng sẽ giúp bạn hiểu rõ hơn và áp dụng thành công giải thuật trong công việc của bạn.