Giải thuật là gì ? - hocdauthau.com

0 Shares

Giải thuật là gì ?

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

Xuất phát từ quan điểm của cấu trúc dữ liệu, dưới đây chính là một số giải thuật quan trọng:

Bạn đang xem: Giải thuật chính là gì

Bạn đang đọc: Giải thuật là gì ?

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 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.Giải thuật Xóa: Giải thuật để xóa một phần tử đang tồn tại đến 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 chính 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 những bước.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 chính 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 những vấn đề tương 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.

phương pháp viết một giải thuật ?

Bạn đừng tìm, bởi vì sẽ chưa 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), … những bạn có thể 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 biện pháp để giải quyết vấn đề đó , sau đó chính là viết giải thuật.

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

Bạn theo dõi Thí dụ minh họa dưới đây để thấy rõ những bước , và phương pháp viết một giải thuật. Tất nhiên chính là Thí dụ dưới đây chính là khá đơn giản vì đây chỉ là Thí 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.

Bài toán: Thiết kế một giải thuật để cộng hai số , 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 những giá trị của a & b Bước 4: Cộng những 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

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 đầ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

Xem thêm: Chiến tranh ủy nhiệm , và giải pháp phòng, chống – Tạp chí Quốc phòng toàn dân

Trong khi thiết kế , phân tích những giải thuật, thường thì phương thức thứ hai đã được dùng để miêu tả một giải thuật. Phương Pháp thứ hai này giúp cho dễ dàng phân tích giải thuật khi đã bỏ qua những phần định nghĩa chưa cần thiết. 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 dùng , phương pháp tiến trình thực thi.

Tất nhiên, việc viết tên những bước chính là tùy ý.

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.

Giải thuật chính là gì

Do đó, một bài toán có thể cũng sẽ có nhiều lời giải. Vậy lời giải nào sẽ là thích hợp số 1 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 (Thí dụ: tốc độ vi xử lý, …) chính là hằng số , và không ảnh hưởng 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ì tốt nhất 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 cũng 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ề bản chất, độ phức tạp giải thuật chính là một hàm ước lượng (có thể chưa chính xác) số phép tính mà giải thuật cần làm (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ể chính là độ lớn của số trong bài toán kiểm tra số nguyên tố, …

Tham khảo thêm: Trưởng ban Tiếng Anh là gì: phương pháp viết, Thí dụ trong tiếng Anh.

Giả sử X chính là một giải thuật , và n là kích cỡ của dữ liệu đầu vào. Thời gian , lượng bộ nhớ đã được dùng bởi giải thuật X là hai nhân tố chính quyết định tốt nhất 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 dùng.

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

Độ 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 dùng là tổng của hai thành phần sau:

Phần cố định (giả sử gọi chính là C) là lượng bộ nhớ cần thiết để 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 đề). Thí 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ớ cần thiết bởi những biến, có kích cỡ phụ thuộc vào kích cỡ của vấn đề. Thí 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). chúng ta theo dõi Thí dụ đơn giản sau:

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 mọi người có ba biến A, B , C , 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 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 cần thiết đến 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ố những bước.

Thí 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ẽ chính là T(n) = c*n, trong đó c chính là thời gian để làm 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.

Loạt bài hướng dẫn Cấu trúc dữ liệu , giải thuật của chúng tôi dựa trên nguồn tài liệu của trang: Tutorialspoint

Tham khảo thêm: Slippage là gì vậy? Trượt giá , phương pháp tránh trượt giá trong forex – Admiral Markets