Hệ ký hiệu tiệm cận
Các ký hiệu mà ta dùng để mô tả thời gian thực hiện tiệm cận của một thuật toán được định nghĩa theo dạng các hàm có các lĩnh vực là tập hựp các số tựnhiên N = {0, 1, 2,…}. Các ký hiệu như vậy tỏ ra tiện dụng khi mô tả hàm thời gian thực hiện ca xấu nhất T(n),thường chỉ được
định nghĩa dựa trên các kích cỡ đầu vào sô” nguyên. Tuy nhiên, đôi lúc cũng tỏ ra tiện dụng khi lạm dụnghệ ký hiệu tiệm cận theo nhiều cách khác nhau. Ví dụ, có thể dễ dàng mở rộng hệ ký hiệu theo lĩnh vực các sô” thực hoặc, một cách khác, hạn chế theo một tập hợp con các số tự nhiên. Tuy nhiên, điều quan trọng là hiểu rõý nghĩa đích thực của hệ ký hiệu sao cho khi bị lạm dụng, nó không bịdùng sai.Đoạn này định nghĩa các ký hiệu tiệm cận căn bản và giới thiệu vài cách lạm dụng phổ biến.
Hệ ký hiệu 0
Chương 1 đã giới thiệu thời gian thực hiện trường hợp xâu nhất của phương pháp sắp xếp chèn là T(n)= 0(n2). Giờ đây ta định nghĩa ý nghĩa của hệ ký hiệu này. Với một hàm đã cho g(n),qua 0(g(n)) ta thể hiện tập hợp các hàm
<d(g(n)) = {J{n): ờ đó tồn tại các hằng dương cr crvà nữsao cho 0 <
c lg («) <fin) < c2g (n)với tấit cản > n{)}.
Một hàm jịn)thuộc về tập hợp 0(g(n)) nếu ở đó tồn tại các hằng dương Cj, và c2sao cho nó có thể “được kẹp” giữa c{ g(n)và c2g(n),với nđủ lớn. Mặc dù 0 (g(n))là một tập hợp, ta viết “f(n)= 0(£(/ĩ)) ” để nêu rõý[n)là một phần tử của 0 (g(n)Xhoặc “/(n) e0 (g(n)).”Thoạt tiên, kiểu lạm dụng đẵng thức để thể hiện sự thuộc về tập hợp này có vẻ như dễ gây lẫn lộn, song nó có các ưu điểm mà ta sẽ thây ở phần sau trong đoạn này.Với tất cả giá trịnvề bên phải của nữgiá trỊf(n)nằm tại hoặc bên trên Cjg(rt) và tại hoặc bên dưới c2g(n).Nói cách khác, với tất cản >nữhàm fin)bằng g(n)bên trong một thừa số bất biến. Ta nổi g(n)là một cận sát theo tiệm cận[asymptotically tight bound] cảãj{n).
Phần định nghĩa <2>(g(n))yêu cầu mọi phần tử của 0(£(n)) là không âm theo tiệm cận[asymptotically nonnegative], nghĩa \ầj{rì) đó không âm mỗi khi nđủ lớn. Kết quả là, chính hàm g(n)phải là không âm theo tiệm cận, bằng không tập hợp 0 (g(n))là trống. Do đó ta mặc nhận rằng mọi hàm được dùng trong hệ ký hiệu 0 sẽ không âm theo tiệm cận. Giả thiết này cũng áp dụng cho các ký hiệu tiệm cận khác được định nghĩa trong chương này.
Chương 1 đã giới thiệu một khái niệm không chính thức về hệ kỹ hiệu 0 mà chung quy là vứt bỏ các số hạng cấp thấp và bỏ qua hệ số đầu của số hạng cấp cao nhất. Hãy xác minh ngắn gọn trực giác này bằng cách dùng phần định nghĩa hình thức để chứng tỏ y n2- 3n= 0 {n2),Để thực hiện, phải xác định các hằng dương cr cvvà n0sao cho
c{n2<J n2 – 3n < c2n2
với tất cản > nữ Chia với n2 cho ra
c, ắ 2 * n – c2
Có thể tạo bất đẳng thức tay phải [right-hand inequality] để áp dụng cho bất kỳ giá trịn > 1 bằng cách chọn c2> 1/2. Cũng vậy, có thể tạo bất đẳng thức tay trái để cho bất kỳ giá trịn > 7 bằng cách chọn < 1/ 14. Như vậy, nhờ chọn cl = 1/14, c2 = 1/2, và n° = 7, ta có thể xác minh 1 n2- 3n = 0(/t2). Tất nhiên, vẫn có các chọn lựa khác cho các hằng, song điều quan trọng đó là việc tồn tại một khả năng chọn lựa nào đó.
Lưu ý, các hằng này tùy thuộc vào hàm \ n2 – 3n; một hàm khác thuộc về 0(n2) thường yêu cầu các hằng khác nhau.
Trong mỗi phần, giá trịn0 đã nêu là giá trị tối thiểu khả dĩ; các giá tộ lớn hơn cũng làm việc, (a) hệ ký hiệu 0 định cận một hàm nằm trong các thừa số bát biến. Ta viết jịri) – 0G?(*)) nếu ở đó tồn tại các hằng dương n0, cv và c2 sao cho về bên phải của nut giá tr\j{n) luôn nằm giữa Cịgírt) và c\g(n) kể luôn cả hai giá trị này. (b) hệ ký hiệu o cung câp một cận trên cho một hàm nằm trong một thừa số bất biến. Ta viết/(ri) = 0(#(/z)) nếu có các hằng dương nQ và c sao cho về bên phải của no, giá trỊýịri) luôn nằm tại hoặc bên dưới cg(n). (c) hệ ký hiệu £2 đưa ra một cận dưới cho một hàm nằm trong một thừa số bất biến. Ta viết f(n) =. Q(g(n)) nếu có các hằng dương no và c sao cho về bên phải của n0, giá trịf(n) luôn nằm tại hoặc bên trên cg(n).