Ký hiệu tiệm cận và phân tích Apriori

Trong việc thiết kế Thuật toán, phân tích độ phức tạp của một thuật toán là một khía cạnh thiết yếu. Chủ yếu, độ phức tạp của thuật toán quan tâm đến hiệu suất của nó, tốc độ hoạt động của nó nhanh hay chậm.

Độ phức tạp của một thuật toán mô tả hiệu quả của thuật toán về dung lượng bộ nhớ cần thiết để xử lý dữ liệu và thời gian xử lý.

Độ phức tạp của một thuật toán được phân tích theo hai khía cạnh: Time và Space.

Thời gian phức tạp

Đó là một hàm mô tả lượng thời gian cần thiết để chạy một thuật toán về kích thước của đầu vào. "Thời gian" có thể có nghĩa là số lần truy cập bộ nhớ được thực hiện, số lần so sánh giữa các số nguyên, số lần một số vòng lặp bên trong được thực hiện hoặc một số đơn vị tự nhiên khác liên quan đến lượng thời gian thực mà thuật toán sẽ sử dụng.

Không gian phức tạp

Đó là một hàm mô tả dung lượng bộ nhớ mà một thuật toán có về kích thước đầu vào cho thuật toán. Chúng ta thường nói về bộ nhớ "bổ sung" cần thiết, không tính bộ nhớ cần thiết để lưu trữ dữ liệu đầu vào. Một lần nữa, chúng tôi sử dụng các đơn vị tự nhiên (nhưng độ dài cố định) để đo điều này.

Sự phức tạp về không gian đôi khi bị bỏ qua vì không gian được sử dụng là tối thiểu và / hoặc hiển nhiên, tuy nhiên đôi khi nó trở thành một vấn đề quan trọng như thời gian.

Ký hiệu tiệm cận

Thời gian thực thi của một thuật toán phụ thuộc vào tập lệnh, tốc độ bộ xử lý, tốc độ I / O của đĩa, v.v. Do đó, chúng tôi ước tính hiệu quả của một thuật toán theo tiệm cận.

Hàm thời gian của một thuật toán được biểu diễn bằng T(n), Ở đâu n là kích thước đầu vào.

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

• O - Ồ lớn

• Ω - Omega lớn

• θ - Theta lớn

• o - Oh nhỏ

• ω - Tiểu omega

O: Đường giới hạn trên của tiệm cận

'O' (Big Oh) là ký hiệu được sử dụng phổ biến nhất. Một chức năngf(n) có thể được đại diện là thứ tự của g(n) đó là O(g(n)), nếu tồn tại một giá trị là số nguyên dương n như n₀ và một hằng số dương c như vậy -

$ f (n) \ leqslant cg (n) $ cho $ n> n_ {0} $ trong mọi trường hợp

Do đó, chức năng g(n) là giới hạn trên cho hàm f(n), như g(n) phát triển nhanh hơn f(n).

Thí dụ

Chúng ta hãy xem xét một hàm đã cho, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $

Xét $ g (n) = n ^ 3 $,

$ f (n) \ leqslant 5.g (n) $ cho tất cả các giá trị của $ n> 2 $

Do đó, sự phức tạp của f(n) có thể được biểu diễn dưới dạng $ O (g (n)) $, tức là $ O (n ^ 3) $

Ω: Giới hạn dưới tiệm cận

Ta nói rằng $ f (n) = \ Omega (g (n)) $ khi tồn tại hằng số c $ f (n) \ geqslant cg (n) $ đó cho tất cả giá trị đủ lớn của n. Đâynlà một số nguyên dương. Nó có nghĩa là chức năngg là giới hạn dưới cho hàm f; sau một giá trị nhất định củan, f sẽ không bao giờ đi xuống dưới g.

Thí dụ

Ta xét một hàm đã cho, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $.

Xét $ g (n) = n ^ 3 $, $ f (n) \ geqslant 4.g (n) $ với tất cả các giá trị của $ n> 0 $.

Do đó, sự phức tạp của f(n) có thể được biểu diễn dưới dạng $ \ Omega (g (n)) $, tức là $ \ Omega (n ^ 3) $

θ: Đường giới hạn chặt chẽ tiệm cận

Ta nói rằng $ f (n) = \ theta (g (n)) $ khi tồn tại hằng số c₁ và c₂ $ c_ {1} .g (n) \ leqslant f (n) \ leqslant c_ {2} .g (n) $ cho tất cả giá trị đủ lớn của n. Đâyn là một số nguyên dương.

Điều này có nghĩa là chức năng g là một ràng buộc chặt chẽ cho chức năng f.

Thí dụ

Chúng ta hãy xem xét một hàm đã cho, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $

Xét $ g (n) = n ^ 3 $, $ 4.g (n) \ leqslant f (n) \ leqslant 5.g (n) $ cho tất cả các giá trị lớn của n.

Do đó, sự phức tạp của f(n) có thể được biểu diễn dưới dạng $ \ theta (g (n)) $, tức là $ \ theta (n ^ 3) $.

O - Ký hiệu

Giới hạn trên của tiệm cận được cung cấp bởi O-notationcó thể có hoặc không có tiệm cận chặt chẽ. Giới hạn $ 2.n ^ 2 = O (n ^ 2) $ là tiệm cận chặt chẽ, nhưng giới hạn $ 2.n = O (n ^ 2) $ thì không.

Chúng tôi sử dụng o-notation để biểu thị một giới hạn trên không chặt chẽ về mặt tiệm cận.

Chúng tôi chính thức xác định o(g(n)) (little-oh of g of n) as the set f(n) = o(g(n)) cho bất kỳ hằng số dương nào $ c> 0 $ và tồn tại một giá trị $ n_ {0}> 0 $, sao cho $ 0 \ leqslant f (n) \ leqslant cg (n) $.

Một cách trực quan, trong o-notation, chức năng f(n) trở nên không đáng kể so với g(n) như ntiếp cận vô cực; đó là,

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = 0 $$

Thí dụ

Chúng ta hãy xét cùng một hàm, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $

Xét $ g (n) = n ^ {4} $,

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 4} \ right) = 0 $$

Do đó, sự phức tạp của f(n) có thể được biểu diễn dưới dạng $ o (g (n)) $, tức là $ o (n ^ 4) $.

ω - Kí hiệu

Chúng tôi sử dụng ω-notationđể biểu thị một giới hạn dưới không chặt chẽ về mặt tiệm cận. Tuy nhiên, về mặt hình thức, chúng tôi xác địnhω(g(n)) (little-omega of g of n) as the set f(n) = ω(g(n)) cho bất kỳ hằng số dương nào C > 0 và tồn tại một giá trị $ n_ {0}> 0 $, sao cho $ 0 \ leqslant cg (n) <f (n) $.

Ví dụ: $ \ frac {n ^ 2} {2} = \ omega (n) $, nhưng $ \ frac {n ^ 2} {2} \ neq \ omega (n ^ 2) $. Quan hệ $ f (n) = \ omega (g (n)) $ ngụ ý rằng giới hạn sau tồn tại

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = \ infty $$

Đó là, f(n) trở nên lớn tùy ý so với g(n) như n tiệm cận vô cùng.

Thí dụ

Chúng ta hãy xét cùng một hàm, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $

Xét $ g (n) = n ^ 2 $,

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 2} \ right) = \ infty $$

Do đó, sự phức tạp của f(n) có thể được biểu diễn dưới dạng $ o (g (n)) $, tức là $ \ omega (n ^ 2) $.

Phân tích Apriori và Apostiari

Phân tích Apriori có nghĩa là, phân tích được thực hiện trước khi chạy nó trên một hệ thống cụ thể. Phân tích này là một giai đoạn mà một hàm được xác định bằng cách sử dụng một số mô hình lý thuyết. Do đó, chúng tôi xác định độ phức tạp về thời gian và không gian của một thuật toán bằng cách chỉ xem xét thuật toán thay vì chạy nó trên một hệ thống cụ thể với bộ nhớ, bộ xử lý và trình biên dịch khác.

Phân tích Apostiari của một thuật toán có nghĩa là chúng tôi chỉ thực hiện phân tích một thuật toán sau khi chạy nó trên một hệ thống. Nó phụ thuộc trực tiếp vào hệ thống và thay đổi từ hệ thống này sang hệ thống khác.

Trong một ngành, chúng tôi không thể thực hiện phân tích Apostiari vì phần mềm này thường được tạo cho người dùng ẩn danh, phần mềm này chạy trên một hệ thống khác với những hệ thống hiện có trong ngành.

Trong Apriori, đó là lý do mà chúng tôi sử dụng các ký hiệu tiệm cận để xác định độ phức tạp của thời gian và không gian khi chúng thay đổi từ máy tính này sang máy tính khác; tuy nhiên, về mặt tiệm cận chúng giống nhau.