Cấu trúc dữ liệu - 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 đối với 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 ta 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. Ngoài "đầu vào", tất cả các yếu tố khác được coi là không đổi.

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. 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 sự gia tăngn và thời gian chạy của hoạt động thứ hai sẽ tăng lên theo cấp số nhân khi ntăng. Tương tự, thời gian chạy của cả hai hoạt động sẽ gần như nhau nếun là nhỏ đáng kể.

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

Best Case - Thời gian tối thiểu cần thiết để thực hiện chương trình.
Average Case - Thời gian trung bình cần thiết để thực hiện chương trình.
Worst Case - 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 một thuật toán.

Ο Kí hiệu
Ký hiệu Ω
θ Kí hiệu

Ký hiệu Big Oh, Ο

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

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

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

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 thuật toán. Nó đo lường độ phức tạp thời gian của trường hợp tốt nhất hoặc khoảng thời gian tốt nhất mà một thuật toán có thể có để hoàn thành.

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

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

Ký hiệu Theta, θ

Kí hiệu θ (n) là cách chính thức để biểu thị 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 biểu diễn như sau:

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

Ký hiệu tiệm cận phổ biến

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

không thay đổi	-	Ο (1)
lôgarit	-	Ο (log n)
tuyến tính	-	Ο (n)
n log n	-	Ο (n log n)
bậc hai	-	Ο (n ² )
khối	-	Ο (n ³ )
đa thức	-	n ^{Ο (1)}
số mũ	-	2 ^{Ο (n)}