Đánh giá độ phức tạp thuật toán – Phần I

Đánh giá độ phức tạp thuật toán – Phần I

Đối với một bài toán đặt ra, có thể có nhiều thuật toán để giải quyết bài toán đó. Có những thuật toán chạy nhanh, tốn ít tài nguyên của máy tính mà vẫn cho ra kết quả đúng, trong khi các thuật toán khác lại không được như vậy. Bài viết này cung cấp cho bạn một số kiến thức cơ bản nhất để đánh gia độ phức tạp của một thuật toán.

Đánh giá độ phức tạp thuật toán là đánh giá lượng tài nguyên các loại mà thuật toán đòi hỏi sử dụng. Có hai loại tài nguyên quan trọng là thời gian và bộ nhớ. Ta sẽ tập trung vào phân tích thời gian thực hiện thuật toán, tiêu chuẩn để đánh giá hiệu lực của thuật toán hay đề cập tới.

Rõ ràng, thời gian thực hiện của thuật toán phụ thuộc vào dữ liệu đầu vào. Vì vậy, ta sẽ đánh giá thời gian bởi một hàm của độ dài dữ liệu vào.

Các loại thời gian tính mà ta sẽ quan tâm đến:

  • Thời gian tính tốt nhất: thời gian tối thiểu cần thiết để thực hiện thuật toán với mọi bộ dữ liệu đầu vào kích thước
  • Thời gian tính trung bình: thời gian trung bình cần thiết để thực hiện thuật toán trên tập hữu hạn dữ liệu đầu vào kích thước
  • Thời gian tính tốt nhất: thời gian nhiều nhất cần thiết để thực hiện thuật toán với mọi bộ dữ liệu đầu vào kích thước

Các khái niệm về tiệm cận

Ký hiệu

Đối với hàm g(n), ký hiệu (g(n)) là tập các hàm f(n)


theta
Ý nghĩa hình học của

Ta viết hay
Ví dụ: Cần chỉ ra 7n^2 – 2n = (n^2), tức là ta cần tìm các hệ số c1, c2, n0 thỏa mãn định nghĩa trên. Dễ thấy c1 = 1, c2 = 10, n0 = 1 thỏa mãn:

n^2 <= 7n^2 - 2n <= 10n^2 với mọi n >= 1

Ký hiệu O

Đối với hàm g(n), ký hiệu O(g(n)) là tập các hàm

bigO
Ý nghĩa hình học của O

Ví dụ: Dễ thấy 7n^2 – 2n = O(n^2) với c = 1, n = 1

Ký hiệu

Đối với hàm g(n), ký hiệu (g(n)) là tập các hàm

omega
Ý nghĩa hình học của

Ví dụ: Dễ thấy 7n^2 – 2n = (n^2) với c = 10, n = 1

Liên hệ giữa , O

f(n) = g(n)) f(n) = O(g(n))f(n) = (g(n)) tức là (g(n)) = O(g(n)) (g(n))

Cách nói về thời gian tính

  • “Thời gian tính là O(f(n))“: Hiểu là thời gian tính trong trường hợp tồi nhất được xác định bởi
    một hàm nào đó thuộc O(f(n))
  • “Thời gian tính là (f(n))“: Hiểu là thời gian tính trong trường hợp tốt nhất được xác định bởi một hàm nào đó thuộc (f(n))

(còn tiếp)

Khi trích dẫn bài viết từ tek.eten.vn, xin vui lòng ghi rõ nguồn. Chúng tôi sẽ rất cảm ơn bạn!