Khái niệm cơ bản về thuật toán trong cấu trúc dữ liệu & giải thuật

Thuật toán là một quy trình từng bước, xác định một tập các hướng dẫn sẽ được thực hiện theo một thứ tự nhất định để có được đầu ra mong muốn. Các thuật toán thường được tạo ra độc lập với các ngôn ngữ cơ bản, tức là một thuật toán có thể được thực hiện bằng nhiều ngôn ngữ lập trình.

Từ quan điểm cấu trúc dữ liệu, sau đây là một số loại thuật toán quan trọng

  • Tìm kiếm - Thuật toán để tìm kiếm một mục trong cấu trúc dữ liệu.
  • Sắp xếp - Thuật toán để sắp xếp các mục theo một thứ tự nhất định.
  • Thêm - Thuật toán để thêm mục trong cấu trúc dữ liệu.
  • Cập nhật - Thuật toán để cập nhật một mục hiện có trong cấu trúc dữ liệu.
  • Xóa - Thuật toán để xóa một mục hiện có khỏi cấu trúc dữ liệu.

Đặc điểm của một thuật toán

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

  • Tính xác định - Thuật toán phải rõ ràng và không mơ hồ. Mỗi bước của nó (hoặc các giai đoạn) và đầu vào / đầu ra của chúng phải rõ ràng và chỉ mang một mục đích nhất định
  • Đầu vào - Một thuật toán nên có 0 hoặc nhiều đầu vào được xác định rõ.
  • Đầu ra - Một thuật toán nên có 1 hoặc nhiều đầu ra được xác định rõ và phải phù hợp với đầu ra mong muốn.
  • Tính hữu hạn - Thuật toán phải kết thúc sau một số bước hữu hạn.
  • Tính khả thi - Nên khả thi với các nguồn lực sẵn có.
  • Độc lập - Một thuật toán nên có các hướng dẫn từng bước, độc lập với bất kỳ code lập trình nào.

Làm thế nào để viết một thuật toán?

Không có tiêu chuẩn được xác định rõ để viết thuật toán. Thay vào đó, nó là vấn đề và phụ thuộc tài nguyên. Các thuật toán không bao giờ được viết để hỗ trợ một mã lập trình cụ thể.

Như chúng ta đã biết, các ngôn ngữ lập trình đều có các vòng lặp (do, for, while) và các lệnh điều khiển luồng (if-else) v.v. Những cấu trúc phổ biến này có thể được sử dụng để viết một thuật toán.

Chúng ta viết các thuật toán theo cách từng bước, nhưng không phải lúc nào cũng như vậy. Viết thuật toán là một quá trình và được thực hiện sau khi xác định rõ ràng được vấn đề mà mình cần giải quyết. Đó là, chúng ta nên xác định rõ vấn đề mà chúng ta đang thiết kế một giải pháp.

Thí dụ

Hãy thử học viết thuật toán bằng cách sử dụng một ví dụ.

Vấn đề - Thiết kế một thuật toán để cộng hai số và hiển thị kết quả.

Bước 1: Bắt đầu
Bước 2: Khai báo ba số a, b & c
Bước 3: Định nghĩa các giá trị của a & b
Bước 4: Cộng các giá trị của a & b
Bước 5: Lưu trữ kết quả của Bước 4 vào biến c
Bước 6: In biến c
Bước 7: Kết thúc

Các giải thuật nói cho lập trình viên cách để viết code. Ngoài ra, bạn cũng có thể viết một giải thuật cho bài toán trên như sau:

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

Trong thiết kế và phân tích các thuật toán, thông thường phương pháp thứ hai được sử dụng để mô tả một thuật toán. Cách này giúp nhà phân tích dễ dàng phân tích thuật toán bỏ qua tất cả các định nghĩa không cần thiết. Anh ta có thể quan sát những hoạt động đang được sử dụng và quá trình đang diễn ra như thế nào.

Viết số bước , là tùy chọn.

Chúng tôi thiết kế một thuật toán để có được một giải pháp cho một vấn đề nhất định. Một vấn đề có thể được giải quyết theo nhiều cách.

một vấn đề nhiều giải pháp

Do đó, nhiều thuật toán giải pháp có thể được bắt nguồn cho một vấn đề nhất định. Bước tiếp theo là phân tích các thuật toán giải pháp được đề xuất đó và thực hiện giải pháp phù hợp nhất.

Phân tích thuật toán

Hiệu quả của một thuật toán có thể được phân tích ở hai giai đoạn khác nhau, trước khi thực hiện và sau khi thực hiện.

  • Phân tích lý thuyết - Đây là phân tích lý thuyết về thuật toán. Hiệu quả của một thuật toán được đo bằng cách giả sử rằng tất cả các yếu tố khác, ví dụ, tốc độ của bộ xử lý, là không đổi và không ảnh hưởng đến việc thực thi giải thuật.
  • Phân tích tiệm cận - Đây là một phân tích thực nghiệm của một thuật toán. Thuật toán đã chọn được thực hiện bằng một ngôn ngữ lập trình bất kỳ. 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, …

Chương này chúng ta sẽ tìm hiểu phân tích lý thuyết. Còn phân tích tiệm cận chúng ta sẽ cùng tìm hiểu ở chương tiếp theo.

Độ phức tạp thuật toán

Giả sử X là một thuật toán và n là kích thước của dữ liệu đầu vào, thời gian và không gian được sử dụng bởi thuật toán X là hai yếu tố chính, quyết định hiệu quả của X.

  • Yếu tố thời gian - Thời gian được đo bằng cách đếm số lượng các thao tác chính (như so sánh trong thuật toán sắp xếp).
  • Yếu tố bộ nhớ - Bộ nhớ được đo bằng cách đếm không gian bộ nhớ tối đa theo yêu cầu của thuật toán.

Độ phức tạp của thuật toán f (n) cho thời gian chạy và / hoặc không gian lưu trữ được yêu cầu bởi thuật toán theo n là kích thước của dữ liệu đầu vào.

Dung lượng sử dụng bộ nhớ (Space Complexity) trong phân tích thuật toán

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

Dưới đây là một ví dụ đơn giản

Giải thuật: tìm tổng hai số A, B

Step 1 -  Bắt đầu

Step 2 -  C ← A + B + 10

Step 3 -  Kết thúc

Ở đâ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.

Độ phức tạp thời gian của thuật toán biểu thị lượng thời gian mà thuật toán yêu cầu để chạy đến khi hoàn thành. Yêu cầu về thời gian có thể được định nghĩa là hàm số T (n), trong đó T (n) có thể được đo là số bước, miễn là mỗi bước tiêu tốn thời gian không đổi.

Ví dụ, việc thêm hai số nguyên n bit có n bước. Do đó, tổng thời gian tính toán là T (n) = c*n, trong đó c là thời gian thực hiện để cộng hai bit. Ở đây, chúng tôi quan sát thấy T (n) tăng trưởng tuyến tính khi kích thước đầu vào tăng.

- Hiếu Kiều -