Ý tưởng chính của phân tích tiệm cận là có một thước đo hiệu quả của các thuật toán không phụ thuộc vào các hằng số dành riêng cho máy và không yêu cầu các thuật toán phải được thực hiện và thời gian thực hiện của các chương trình để so sánh. Ký hiệu tiệm cận là công cụ toán học để biểu thị độ phức tạp về thời gian của các thuật toán để phân tích tiệm cận. 3 ký hiệu tiệm cận sau đây hầu hết được sử dụng để biểu thị độ phức tạp về thời gian của các thuật toán.
1) Θ Kí hiệu: Kí hiệu theta giới hạn một hàm từ trên xuống dưới, vì vậy nó xác định hành vi tiệm cận chính xác.
Một cách đơn giản để lấy ký hiệu Theta của một biểu thức là bỏ các số hạng bậc thấp và bỏ qua các hằng số đứng đầu. Ví dụ, hãy xem xét biểu thức sau.
3n 3 + 6n 2 + 6000 = Θ (n 3
Bỏ các số hạng thấp hơn luôn ổn vì sẽ luôn có một số (n) sau đó Θ (n 3 ) có giá trị lớn hơn Θ (n 2 ) bất kể là hằng số bị liên lụy.
Đối với một hàm g (n) đã cho, chúng ta ký hiệu Θ (g (n)) là tập hợp các hàm sau đây.
Θ (g (n)) = {f (n): tồn tại các hằng số dương c1, c2 và n0 như vậy
rằng 0 <= c1 * g (n) <= f (n) <= c2 * g (n) với mọi n> = n0}Định nghĩa trên có nghĩa là, nếu f (n) là giá trị của g (n), thì giá trị f (n) luôn nằm giữa c1 * g (n) và c2 * g (n) đối với các giá trị lớn của n (n> = n0). Định nghĩa của theta cũng yêu cầu f (n) phải không âm đối với các giá trị của n lớn hơn n0.
2) Ký hiệu Big O: Ký hiệu Big O xác định giới hạn trên của một thuật toán, nó chỉ giới hạn một hàm từ phía trên. Ví dụ, hãy xem xét trường hợp Sắp xếp chèn. Nó cần thời gian tuyến tính trong trường hợp tốt nhất và thời gian bậc hai trong trường hợp xấu nhất. Chúng ta có thể nói một cách an toàn rằng độ phức tạp về thời gian của sắp xếp Chèn là O (n ^ 2). Lưu ý rằng O (n ^ 2) cũng bao hàm thời gian tuyến tính.
Nếu chúng ta sử dụng ký hiệu Θ để biểu thị độ phức tạp thời gian của Sắp xếp chèn, chúng ta phải sử dụng hai câu lệnh cho trường hợp tốt nhất và xấu nhất:
1. Độ phức tạp thời gian trong trường hợp xấu nhất của Sắp xếp chèn là Θ (n ^ 2).
2. Độ phức tạp thời gian theo trường hợp tốt nhất của Sắp xếp chèn là Θ (n).
Ký hiệu Big O rất hữu ích khi chúng ta chỉ có giới hạn trên về độ phức tạp về thời gian của một thuật toán. Nhiều khi chúng ta dễ dàng tìm thấy giới hạn trên chỉ bằng cách nhìn vào thuật toán.
O (g (n)) = {f (n): tồn tại các hằng số dương c và
n0 sao cho 0 <= f (n) <= c * g (n) cho
tất cả n> = n0}
3) Kí hiệu Ω: Cũng giống như kí hiệu Big O cung cấp một đường tiệm cận trên của một hàm, kí hiệu Ω cung cấp một đường tiệm cận dưới.
Ω Ký hiệu có thể hữu ích khi chúng ta có giới hạn thấp hơn về độ phức tạp về thời gian của một thuật toán. Như đã thảo luận trong bài trước, hiệu suất trường hợp tốt nhất của một thuật toán thường không hữu ích , ký hiệu Omega là ký hiệu được sử dụng ít nhất trong cả ba.
Đối với một hàm g (n) đã cho, chúng ta ký hiệu là Ω (g (n)) tập các hàm.
Ω (g (n)) = {f (n): tồn tại các hằng số dương c và
n0 sao cho 0 <= c * g (n) <= f (n) cho
tất cả n> = n0}.Chúng ta hãy xem xét cùng một ví dụ sắp xếp Chèn ở đây. Độ phức tạp thời gian của Sắp xếp chèn có thể được viết là Ω (n), nhưng nó không phải là thông tin hữu ích về sắp xếp chèn, vì chúng ta thường quan tâm đến trường hợp xấu nhất và đôi khi trong trường hợp trung bình.
Các thuộc tính của các ký hiệu tiệm cận:
Như chúng ta đã đi qua định nghĩa của ba ký hiệu này, bây giờ chúng ta hãy thảo luận về một số thuộc tính quan trọng của các ký hiệu đó.
1. Thuộc tính chung:
Nếu f (n) là O (g (n)) thì a * f (n) cũng là O (g (n)); trong đó a là một hằng số.
Ví dụ: f (n) = 2n² + 5 là O (n²)
thì 7 * f (n) = 7 (2n² + 5) = 14n² + 35 cũng là O (n²).
Tương tự, tính chất này thỏa mãn cho cả ký hiệu Θ và Ω.
Ta có thể nói
Nếu f (n) là Θ (g (n)) thì a * f (n) cũng là Θ (g (n)); trong đó a là một hằng số.
Nếu f (n) là Ω (g (n)) thì a * f (n) cũng là Ω (g (n)); trong đó a là một hằng số.
2. Thuộc tính bắc cầu:
Nếu f (n) là O (g (n)) và g (n) là O (h (n)) thì f (n) = O (h (n)).
Ví dụ: nếu f (n) = n, g (n) = n² và h (n) = n³
n là O (n²) và n² là O (n³)
thì n là O (n³)
Tương tự, tính chất này thỏa mãn cho cả ký hiệu Θ và Ω.
Ta có thể nói
Nếu f (n) là Θ (g (n)) và g (n) là Θ (h (n)) thì f (n) = Θ (h (n)).
Nếu f (n) là Ω (g (n)) và g (n) là Ω (h (n)) thì f (n) = Ω (h (n))
3. Thuộc tính phản xạ :
Tính chất phản xạ luôn dễ hiểu sau tính chất bắc cầu.
Nếu f (n) là cho trước thì f (n) là O (f (n)). Vì GIÁ TRỊ TỐI ĐA CỦA f (n) sẽ là f (n) TỰ DO!
Do đó x = f (n) và y = O (f (n) luôn ràng buộc chúng trong quan hệ phản xạ.
Ví dụ: f (n) = n²; O (n²) tức là O (f (n))
Tương tự, tính chất này thỏa mãn cho cả ký hiệu Θ và Ω.
Chúng ta có thể nói về điều đó:
Nếu f (n) là cho trước thì f (n) là Θ (f (n)).
Nếu f (n) là cho trước thì f (n) là Ω (f (n)).
4. Tính chất đối xứng:
Nếu f (n) là Θ (g (n)) thì g (n) là Θ (f (n)).
Ví dụ: f (n) = n² và g (n) = n²
thì f (n) = Θ (n²) và g (n) = Θ (n²)
Thuộc tính này chỉ đáp ứng cho ký hiệu Θ.
5. Tính chất đối xứng Transpose:
Nếu f (n) là O (g (n)) thì g (n) là Ω (f (n)).
Ví dụ: f (n) = n, g (n) = n²
thì n là O (n²) và n² là Ω (n)
Tính chất này chỉ thỏa mãn đối với ký hiệu O và Ω .
6. Một số thuộc tính khác:
1.) Nếu f (n) = O (g (n)) và f (n) = Ω (g (n)) thì f (n) = Θ (g (n))
2.) Nếu f (n) = O (g (n)) và d (n) = O (e (n))
thì f (n) + d (n) = O (max (g (n), e (n)))
Ví dụ: f (n) = n tức là O (n)
d (n) = n² tức là O (n²)
thì f (n) + d (n) = n + n² tức là O (n²)
3.) Nếu f (n) = O (g (n)) và d (n) = O (e (n))
thì f (n) * d (n) = O (g (n) * e (n ))
Ví dụ: f (n) = n tức là O (n)
d (n) = n² tức là O (n²)
thì f (n) * d (n) = n * n² = n³ tức là O (n³)
_______________________________________________________________________________
Bài tập:
Mệnh đề nào sau đây là hợp lệ?
1. Độ phức tạp thời gian của QuickSort là Θ (n ^ 2)
2. Độ phức tạp thời gian của QuickSort là O (n ^ 2)
3. Với hai hàm f (n) và g (n) bất kỳ, ta có f (n) = Θ (g (n)) nếu và chỉ khi f (n) = O (g (n)) và f (n) = Ω (g (n)).
4. Độ phức tạp thời gian của tất cả các thuật toán máy tính có thể được viết là Ω (1)
Đăng nhận xét