Giống như hệ ký hiệu ocung cấp một cận trên tiệm cận trên một hàm, hệ ký hiệu Q cung cấp một cận dưới tiệm cận[asymptotic lower bound]. Với một hàm đã cho g(n), bằng Q(g(/ĩ)) ta thể hiện tập hợp các hàm
Q(g(rt)) = ỈẨn):ở đó tồn tại các hằng dương c và nữ sao cho 0 <cgịn) < fịn) với tất cản > n0\ .
Hình 2. 1 (c) có nêu trực giác đàng sau hệ ký hiệu Q. Với tất cả giá trịn về bên phải của /20, giá trị của f{n) nằm tại hoặc bên trên gịn).
Từ các định nghĩa về các hộ ký hiệu tiệm cận mà ta đã gặp cho đến giờ, ta có thể dễ dàng chứng minh định lý quan trọng dưới đây (xem Bài tập 2.1-5).
Định lý 2.1
Với hai hàm bất kỳf(n) và g(n),f(n) = Q(g(n)) nếu và chỉ nếu/(n) = Oig(n)) và/(rt) = Í2(g(^)).
Để lấy ví dụ về cách ứng dụng định lý này, chứng minh của chúng ta rằng an2 + bn+ c – o (rr) với bất kỳ hằng a, b, và c, ở đó a > 0, cũng lập tức hàm ý rằng an2 + bn+ c – Q(/r ) và an2 + bn + c = 0(n2). Trong thực tế, thay vì dùng Định lý2.1 để có các cận trôn và dưới tiệm cận từ các cận sát tiệm cận, như đà làm trong ví dụ này, ta thường dùng nó để chứng minh các cận sát tiệm cận từ các cận trên và dưới tiệm cận.
Do hệ ký hiệu Í2 mô tả một cận dưới, khi ta dùng nó để định cận thời gian thực hiện trường hợp tốt nhất của một thuật toán, ta cũng ngụý định cận thời gian thực hiện của thuật toán trên các đầu vào tùy ý. Ví dụ, thời gian thực hiện trường hợp tốt nhất của sấp xếp chèn là Q(n), hàm ý rằng thời gian thực hiện của sắp xếp chèn là Q(rc).
Như vậy, thời gian thực hiện của sắp xếp chèn rơi giữa Q(rt) và ơ(n2)y bởi nó rơi tại bất kỳ đâu giữa một hàm tuyến tính của n và một hàm bậc hai của n. Hơn nữa, theo tiệm cận, các cận này càng sát càng tốt: ví dụ, thời gian thực hiện của sấp xếp chèn không phải là £}(rt2), bởi tiến trình sắp xếp chèn chạy trong thời gian 0(«) khi đầu vào được sắp xếp sẩn. Tuy nhiên, không phải là mâu thuẫn khi ta nói rằng thời gian thực hiện ca xấu nhất của sắp xếp chèn là Q(n2), bởi ở đó tồn tại một đầu vào khiến thuật toán chấp nhận thời gian £2(«2). Khi nói thời gian thực hiện (không có bổ từ) của một thuật toán là Q(g(«)), ta ngụýbất kể đã chọn đầu vào cụ thể có kích cỡ n nào cho mỗi giá trị của n, thời gian thực hiện trên tập hợp các đầu vào đó ít nhất cũng là một hằng nhân g(n\ với n đủ lớn.
Hệ ký hiệu tiệm cận trong các phương trình
Ta đã thấy cách dùng hệ ký hiệu tiệm cận trong các công thức toán học. Ví dụ, trong khi giới thiệu hệ ký hiệu o, ta đã viết “ n = 0{n2).” Ta cũng có thể viết 2n2 + 3n + 1 = 2n2+ 0(/z). Làm sao để diễn dịch các công thức như vậy?
Khi hệ ký hiệu tiệm cận đứng một mình bên phía phái của một phương trình, như trong n =ỡ(n2), ta đã định nghĩa sấn dấu bằng để ám chỉ thuộc về tập hợp: n e 0(n2). Tuy nhiên, nói chung, khi hệ ký hiệu tiệm cận xuất hiện trong một công thức, ta diễn dịch nó dưới dạng thay cho một hàm nặc danh [anonymous function] nào đó mà ta không quan tâm đến tên. Ví dụ, công thức 2n2 + 3n + 1 = 2n2 + 0(rt) có nghĩa là 2n2 + 3n + 1 = 2n2 + /(/ĩ), ở đó J{n) là một hàm nào đó trong tập hợp 0(rt). Trong trường hợp này,J{n) = 3n + 1, mà quả thật nằm trong 0(n).
Dùng hệ ký hiệu tiệm cận theo cách này có thể giúp loại bỏ chi tiết không cần thiết và khả năng gây bừa bộn trong một phương trình. Ví dụ, trong Chương 1 ta đã diễn tả thời gian thực hiện ca xấu nhất của sắp xếp trộn dưới dạng phép truy toán
T(n) = 2T(nỉ2) + e(n).
Nếu ta chỉ quan tâm đến cách ứng xử tiệm cận của 7Ỵtt), chẳng có ý nghĩa gì khi đặc tả chính xác tất cả sô” hạng câ”p thấp; chúng được hiểu ngầm là nằm trong hàm nặc danh do số hạng 0(n) thể hiện.
Sô” lượng hàm nặc danh trong một biểu thức được hiểu ngầm là bằng sô” lần xuâ”t hiện của hệ ký hiệu tiệm cận. Ví dụ, trong biểu thức
±0(i\
i=\
chỉ có độc một hàm nặc danh (một hàm của í). Do đó, kiểu diễn tả này không giống như ớ(l) + 0(2) + ỡ(n), không thực sự có một kiểu diễn dịch không lỗi.
