Python - Các loại thuật toán

Hiệu quả và độ chính xác của các thuật toán phải được phân tích để so sánh chúng và chọn một thuật toán cụ thể cho các tình huống nhất định. Quá trình thực hiện phân tích này được gọi là phân tích tiệm cận. 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 bằng 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 một hoạt động khác, nó được tính là g (n2). Đ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ăng của 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 hoạt động sẽ gần như nhau nếu n nhỏ hơn đá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:

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.
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.
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 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)}