1.1 Khái niệm thuật toán

Như đã trình bày ở trên, mỗi thuật toán là một máy Turing. Cụ thể hơn, thuật toán: là 1 dãy hữu hạn các thao tác được sắp xếp theo 1 trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm, sau hữu hạn bước.

Các đặc điểm chính của thuật toán:

- Tính dừng: thuật toán phải kết thúc sau 1 số hữu hạn lần thực hiện các thao tác.

- Tính xác định: sau khi thực hiện 1 thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng 1 thao tác xác định để được thực hiện tiếp theo.

- Tính đúng đắn: sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm. Ở mỗi bước trong thuật toán, các thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng. Nói cách khác, trong cùng một điều kiện, hai bộ xử lý cùng thực hiện cùng một thuật toán phải cho cùng một kết quả như nhau. Thuật toán cần được mô tả trong các ngôn ngữ lập trình, với các mệnh đề được tạo theo các qui tắc cú pháp nghiêm ngặt và chỉ có một nghĩa duy nhất.

1.2 Biểu diễn thuật toán

 Người ta đã đề xuất nhiều cách để biểu diễn thuật toán, cụ thể như sau:

- Biểu diễn bằng cách liệt kê theo bước

- Biểu diễn bằng lưu đồ

- Biểu diễn bằng ngôn ngữ cấu trúc

Bài toán: Cho một số tự nhiên nguyên dương N và một dãy số a₀, a₁, …, a_N. Hãy biểu diễn thuật toán tìm giá trị nhỏ nhất của dãy số đó.

• Biểu diễn bằng cách liệt kê theo bước

Bước 1:Nhập vào N và dãy số a₀, a₁, …, a_N

Bước 2:Minvalue = a₀, i = 1

Bước 3:If i > N then return Minvalue

Bước 4:If a_i < Minvalue then Minvalue ß a_i

Bước 5:i = i+1

Bước 6:Goto bước 3

• Biểu diễn bằng ngôn ngữ cấu trúc

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

Một bài toán có nhiều cách giải. Đểso sánhcác cáchgiải với nhau, ta có thể dựa vào độ phức tạp của thuật toán[4]-[6].

Độ phức tạp của thuật toán có thể chia làm hai loại:

• Độ phức tạp không gian (M): Số ô nhớ cần thiết để có thể triển khaithực hiện thuật toán.
• Độ phức tạp thời gian (T): Thời gian cần thiết để thực hiện xongcác bước các bước của thuật toán, cho ra kết quả.

Khi xét đến độ phức tạp thuật toán, chúng ta chú ý các điều sau đây:

Trong trường hợp giả thiết sử dụng hết RAM để thực hiện thuật toán, chúng ta chỉ cần quan tâm đến độ phức tạp thời gian (T) để đánh giá thuật toán. 

• Khi xét Big-O, ta luôn xét với chiều dài dữ liệu đầu vào n là 1 số vô cùng lớn, do đó có thế coi n là +∞.
• Các bước thực thi không phụ thuộc vào giá trị đầu vào(ví dụ: phép tính toán, gán, so sánh,...) có độ phức tạp hằng số(O(1)).
• Tổng các hằng số là 1 hằng số.
• Tích của 1 số dương với +∞ cũng là +∞, tổng của 1 số với +∞ cũng là+∞.

Bảng 1 cung cấp thời gian thực hiện thuật toán được sử dụng phổ biến nhất và tên gọi của chúng

Bảng 1. Bảng sắp xếp độ phức tạp thuật toán theo thứ tự tăng dần của hàm thời gian thực hiện