Hãy nêu tiêu chuẩn lựa chọn thuật toán?

Đáp án và lời giải chính xác cho câu hỏi: “Hãy nêu tiêu chuẩn lựa chọn thuật toán?” cùng với kiến thức mở rộng do Top lời giải tổng hợp, biên soạn về Tin học 10 là tài liệu học tập bổ ích dành cho thầy cô và các bạn học sinh tham khảo.

Hãy nêu tiêu chuẩn lựa chọn thuật toán? 

Tiêu chuẩn lựa chọn thuật toán

- Một bài toán có thể được biểu diễn bởi nhiều thuật toán, việc chọn lựa thuật toán thích hợp sẽ giúp cho quá trình viết chương trình đơn gián hom và máy tính thực hiện với thời gian nhanh hơri. Vi vậy, có ba tiêu chuẩn cơ bản lựa chọn thuật toán đó là:

+ Thuật toán có độ phúc tạp thời gian nhỏ nhất (thực hiện chương trình trong thời gian ngắn nhất);

+ Số lượng ô nhớ sử dụng it nhất;

+ Viết chương trình cho thuật toán dễ hiểu, đơn giản nhất.

Kiến thức tham khảo thêm về Thuật toán.

1. Các đặc điểm của thuật toán

- Rõ ràng(Unambiguous) – Thuật toán phải rõ ràng và rõ ràng. Mỗi bước (hoặc giai đoạn) của nó, và đầu vào / đầu ra của chúng phải rõ ràng và chỉ dẫn đến một ý nghĩa.

- Đầu vào(Input) – Một thuật toán phải có 0 hoặc nhiều đầu vào được xác định rõ.

- Đầu ra(Output) – Một thuật toán phải có 1 hoặc nhiều đầu ra được xác định rõ ràng và phải phù hợp với đầu ra mong muốn.

- Tính hữu hạn(Finiteness) – Thuật toán phải kết thúc sau một số bước hữu hạn.

- Tính khả thi(Feasibility) – Phải khả thi với các nguồn lực sẵn có(tài nguyên, thiết bị hiện có).

- Độc lập(Independent) – Một thuật toán nên có hướng dẫn từng bước, điều này phải độc lập với bất kỳ code lập trình nào.

2. Phương pháp đánh giá độ phức tạp của thuật toán

* Phương pháp đánh giá bằng lý thuyết

- Trong lập trình thi đấu, người ta sẽ đánh giá độ phức tạp thuật toán bằng phương pháp lý thuyết. Trong phương pháp này, ta quan tâm tới yêu tố kích thước của dữ liệu đầu vào, thông thường là một con số nn. Mối liên hệ giữa yếu tố này và số lượng các phép tính toán để tìm ra được kết quả của bài toán gọi là độ phức tạp thuật toán (chứ không phải thời gian cụ thể như 1, 2 hay 10 giây. Ta sử dụng hàm số T(n) để biểu diễn thời gian thực hiện của thuật toán với dữ liệu đầu vào kích thước là nn.

- Nếu một thuật toán có thời gian thực hiện là T(n) = O(f(n))thì ta nói thuật toán đó có thời gian thực hiện cấp f(n). Nói một cách dễ hiểu, T(n)sẽ biểu diễn số phép tính tối đa cần thực hiện trong thuật toán với một bộ dữ liệu cấp n chẳng hạn trong bài toán kiểm tra tính nguyên tố của số n nếu n là số nguyên tố thì thuật toán sẽ phải thực hiện nhiều lần thử nhất.

* Các quy tắc đánh giá thời gian thực hiện thuật toán

- Để đánh giá thời gian thực hiện thuật toán, ta xuất phát từ các lệnh đơn trong chương trình, rồi tới các câu lệnh có cấu trúc, các khối lệnh phức tạp hơn, sau đó hợp lại thành thời gian thực hiện cả chương trình. Cụ thể ta có các quy tắc:

+ Các lệnh đơn (lệnh khai báo, gán, nhập xuất dữ liệu, phép toán số học,...): Thời gian O(1).

+ Các khối lệnh: Giả sử một khối lệnh gồm các câu lệnh S_1, S_2,..., S_m có thời gian thực hiện lần lượt là O(f_1(n)), O(f_2(n),..., O(f_m(n)) thì thời gian thực hiện của cả khối lệnh là: O(max(f₁​(n),f₂​(n),...,f_m​(n))).

+ Câu lệnh rẽ nhánh: Ta có cú pháp lệnh rẽ nhánh là:

Giả sử thời gian thực hiện của câu lệnh 1 và câu lệnh 2 lần lượt là O(f₁​(n)) và O(f₂​(n)) thì thời gian thực hiện lệnh rẽ nhánh là: O(max(f₁​(n),f₂​(n))).

+ Câu lệnh lặp: Giả sử thời gian thực hiện phần thân của lệnh lặp là O(f(n))và số lần lặp tối đa của vòng lặp là g(n)thì thời gian thực hiện của cả vòng lặp là O(f(n).g(n)).Điều này áp dụng cho tất cả các vòng lặp for, while

+ Sau khi đánh giá được thời gian thực hiện của tất cả các câu lệnh trong chương trình, thời gian thực hiện của toàn bộ chương trình sẽ là thời gian thực hiện của câu lệnh có thời gian thực hiện lớn nhất.