Nghiên cứu Khoa học

Thuật toán và độ phức tạp thuật toán

  • 18/06/2021
  • Nghiên cứu Khoa học

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ố a0, a1, …, aN. 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ố a0, a1, …, aN

Bước 2:Minvalue = a0, i = 1

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

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

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

Algorithm Tìm giá trị nhỏ nhất của chuỗi số a có N phần tử

Input: N, a

Output: Minvalue

Method:

     Minvalue = a0

     i = 1

     while i < N do

          if ai < Minvalue

          then Minvalue = ai

          i = i + 1

          end if

     end while

     return Minvalue

 

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

Kí hiệu Big-O                 

Độ phức tạp loại:

O(1)

Hằng số

O(logn)

Logarit

O(n)

Tuyến tính

O(nlogn)

nlogn

O(n2)

Bình phương

O(n3)

Lập phương

O(2n)

Mũ

O(n!)

Giai thừa

 

Các tin khác

KHOA ĐIỆN - ĐIỆN TỬ ĐẠI HỌC DUY TÂN

Phòng 503 - K7/25 Quang Trung, Tp Đà Nẵng

(0236) 3827111(Ext 503)

Copyright © 2024 Đại học Duy Tân