Phân tích tiệm cận

Phân tích tiệm cận của một thuật toán đề cập đến việc xác định giới hạn / khung toán học của hiệu suất thời gian chạy của nó. Sử dụng phân tích tiệm cận, chúng tôi rất có thể kết luận trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất của một thuật toán.

Phân tích tiệm cận bị ràng buộc đầu vào tức là, nếu không có đầu vào cho thuật toán, nó được kết luận là hoạt động trong một thời gian không đổi. Khác với "đầu vào", tất cả các yếu tố khác được coi là hằng số.

Phân tích tiệm cận đề cập đến việc tính toán thời gian chạy của bất kỳ hoạt động nào trong các đơn vị tính toán toán học. Ví dụ, thời gian chạy của một hoạt động được tính là f (n) và có thể đối với hoạt động khác, nó được tính là g (n ² ). Điều này có nghĩa là thời gian chạy hoạt động đầu tiên sẽ tăng tuyến tính với mức tăng n và thời gian chạy của hoạt động thứ hai sẽ tăng theo cấp số nhân khi n tăng. Tương tự, thời gian chạy của cả hai thao tác sẽ gần như nhau nếu n nhỏ đáng kể.

Thông thường, thời gian mà thuật toán yêu cầu thuộc ba loại -

1. Trường hợp tốt nhất - Thời gian tối thiểu cần thiết để thực hiện chương trình.
2. Trường hợp trung bình - Thời gian trung bình cần thiết để thực hiện chương trình.
3. Trường hợp xấu nhất - Thời gian tối đa cần thiết để thực hiện chương trình.

Ký hiệu tiệm cận

Sau đây là các ký hiệu tiệm cận thường được sử dụng để tính độ phức tạp thời gian chạy của thuật toán.

1. Ký hiệu
2. Ký hiệu
3. Ký hiệu

Ký hiệu Big Oh,

Ký hiệu (n) là cách chính thức để thể hiện giới hạn trên của thời gian chạy thuật toán. Nó đo độ phức tạp của thời gian trong trường hợp xấu nhất hoặc thời gian dài nhất mà thuật toán có thể mất để hoàn thành.

Ví dụ: đối với hàm f (n)

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }

Ký hiệu Omega,

Ký hiệu (n) là cách chính thức để biểu thị giới hạn dưới của thời gian chạy của thuật toán. Nó đo độ phức tạp thời gian trường hợp tốt nhất hoặc lượng thời gian tốt nhất mà thuật toán có thể mất để hoàn thành.

Ví dụ: đối với hàm f (n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }

Ký hiệu Theta,

Ký hiệu (n) là cách chính thức để thể hiện cả giới hạn dưới và giới hạn trên của thời gian chạy thuật toán. Nó được trình bày như sau -

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }

Ký hiệu tiệm cận thường gặp

Sau đây là danh sách một số ký hiệu tiệm cận phổ biến -

Được cập nhật: 17 tháng 4 lúc 17:04:28 | Lượt xem: 547