Algorithm Là Gì – định Nghĩa, Ví Dụ, Giải Thích

Giải thuật là gì ?

Giải thuật Algorithms (hay còn gọi là thuật toán) là một tập hợp hữu hạn những chỉ thị sẽ được thực thi theo một thứ tự nào đó để thu được kết quả mong muốn. Nói tóm lại thì giải thuật là độc lập với những 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.

Bài Viết: Algorithm là gì

Xuất phát từ quan điểm của cấu trúc dữ liệu, dưới đây là 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 Sắp xếp: Giải thuật để sắp xếp những phần tử theo thứ tự nào đó.

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 Update: Giải thuật để update (hay update) một phần tử đã tồn tại trong một cấu trúc dữ liệu.

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.

Đặc điểm của giải thuật

Không phải tất cả những thủ tục có thể được gọi là một giải thuật. Một giải thuật nên có những đặ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: Những giải thuật phải kết thúc sau một số hữu hạn công đoạn.

Tính hiệu quả: Một giải thuật nên là có thể thi hành được với những nguồn có sẵn, tức là có khả năng giải quyết hiệu quả vấn đề trong tình huống thời gian và tài nguyên được phép.

Tính phổ cập: Một giải thuật có tính phổ cập nếu giải thuật này có thể giải quyết được một lớp những vấn đề tương tự.

Xem Ngay:  Real Là Gì - Real Trong Tiếng Tiếng Việt

Độc lập: Một giải thuật nên có những chỉ thị độc lập với bất kỳ phần code lập trình nào.

Cách thức viết một giải thuật ?

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

Chúng ta viết những giải thuật theo phương pháp thức là theo từng bước một. 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. Từ việc định vị vấn đề, chúng ta sẽ thiết kế ra giải pháp để giải quyết vấn đề đó và sau đó là viết giải thuật.

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

Bạn theo dõi ví dụ minh họa dưới đây để thấy rõ công đoạn và phương pháp viết một giải thuật. Tất nhiên là ví dụ dưới đây là khá đơn giản vì đây chỉ là ví dụ minh họa mở đầu cho phương pháp viết giải thuật thôi, nên mình nghĩ càng đơn giản sẽ càng tốt.

Xem Ngay: Wattpad Là Gì – đọc Truyện Pr Là Gì

Bài toán: Thiết kế một giải thuật để cộng hai số và hiển thị kết quả.

Bước 1: Bắt đầuBước 2: Khai báo ba số a, b & cBước 3: Định nghĩa những giá trị của a & bBước 4: Cộng những giá trị của a & bBước 5: Lưu trữ kết quả của Bước 4 vào biến cBước 6: In biến cBước 7: Kết thúc
Những giải thuật nói cho lập trình viên phương pháp để 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 đầuBước 2: Lấy giá trị của a & bBước 3: c ← a + bBước 4: Hiển thị cBước 5: Kết thúc
Trong khi thiết kế và phân tích những giải thuật, thường thì phương thức thứ hai được sử dụng để miêu tả một giải thuật. Cách thức thứ hai này giúp dễ dàng phân tích giải thuật khi đã bỏ qua những phần định nghĩa không thiết yếu. Nhìn vào phương pháp thứ hai này, người ta có thể biết những phép tính nào đang được sử dụng và phương pháp tiến trình thực thi.

Tất nhiên, việc viết tên công đoạn là tùy ý.

Xem Ngay:  Velocity Là Gì - Chuyển động Riêng

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 đó. Một bài toán có thể được giải theo nhiều phương pháp khác nhau.

*

Do đó, một bài toán có thể sẽ có nhiều lời giải. Vậy lời giải nào sẽ là thích hợp nhất cho bài toán đó. Mời bạn tiếp tục theo dõi.

Phân tích giải thuật

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

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ả những yếu tố khác (ví dụ: vận tốc vi xử lý, …) là hằng số và không liên quan tới sự triển khai giải thuật.

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 những thông số liên quan thì hiệu quả của giải thuật dựa trên những 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 giải thuật (Algorithm Complexity)

Về thực chất, độ phức tạp giải thuật là một hàm ước lượng (có thể không đúng đắn) 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) nếu 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à độ to 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 yếu 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ư những 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)) tán thành mối quan hệ giữa thời gian chạy và/hoặc lượng bộ nhớ cần phải được sử dụng bởi giải thuật.

Xem Ngay:  Biến Quan Sát Là Gì

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

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ớ thiết yếu để lưu giữ dữ liệu và những biến nào đó (phần này độc lập với kích cỡ của vấn đề). Ví dụ: những biến và những hằng đơn giản, …

Phần biến đổi (giả sử gọi là SP(I)) là lượng bộ nhớ thiết yếu bởi những 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:

Output:

Giải thuật: tìm tổng hai số A, BStep 1 – Bắt đầuStep 2 – C ← A + B + 10Step 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.

Ngày này, lượng bộ nhớ sẽ phụ thuộc vào kiểu dữ liệu của những 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 (Time Complexity) trong phân tích giải thuật

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 thiết yếu 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ông đoạn.

Xem Ngay: Viettel Pay Là Gì – Viettelpay Là Gì

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.

Thể Loại: Chia sẻ Kiến Thức Cộng Đồng

Bài Viết: Algorithm Là Gì – định Nghĩa, Ví Dụ, Giải Thích

Thể Loại: LÀ GÌ

Nguồn Blog là gì: https://hethongbokhoe.com Algorithm Là Gì – định Nghĩa, Ví Dụ, Giải Thích

Leave a Reply