tailieunhanh - Bài giảng Cấu trúc dữ liệu & giải thuật: Độ tăng của hàm

Bài giảng "Cấu trúc dữ liệu và giải thuật: Độ tăng của hàm" cung cấp cho người học các kiến thức về định nghĩa toán học của Big-O, ý nghĩa của Big-O, một số kết quả Big-O quan trọng, độ tăng của tổ hợp các hàm, . Mời các bạn cùng tham khảo. | 33 Big-O. Một số kết quả Big-O quan trọng. Cấu trúc dữ liệu và giải thuật - HCMUS 2016 34 Khái niệm Big-O lần đầu tiên được đưa ra bởi nhà toán học người Đức Paul Bachmann vào năm 1892. Big-O được trở nên phổ biến hơn nhờ nhà toán học Landau. Do vậy Big-O cũng còn được gọi là ký hiệu Landau hay Bachmann-Landau. Donald Knuth được xem là người đầu tiên truyền bá khái niệm Big-O trong tin học từ những năm 1970. Ông cũng là người đưa ra các khái niệm Big- Omega và Big-Theta. Cấu trúc dữ liệu và giải thuật - HCMUS 2016 https tailieudientucntt FIT-HCMUS 1 35 Cho f và g là hai hàm số từ tập các số nguyên hoặc số thực đến số thực. Ta nói f x là O g x nếu tồn tại hằng số C và k sao cho f x C g x với mọi x gt k Cấu trúc dữ liệu và giải thuật - HCMUS 2016 36 Cho f và g là hai hàm số từ tập các số nguyên hoặc số thực đến số thực. Ta nói f x là O g x nếu tồn tại hằng số C và k sao cho f x C g x với mọi x gt k Ví dụ hàm f x x2 3x 2 là O x2 . Thật vậy khi x gt 2 thì x lt x2 và 2 lt 2x2 Do đó x2 3x 2 lt 6x2. Nghĩa là ta chọn được C 6 và k 2. Cấu trúc dữ liệu và giải thuật - HCMUS 2016 https tailieudientucntt FIT-HCMUS 2 37 Big-O giúp xác định được mối quan hệ giữa f x và g x trong đó g x thường là hàm ta đã biết trước. Từ đó ta xác định được sự tăng trưởng của hàm f x cần khảo sát. C và k trong định nghĩa của khái niệm Big-O được gọi là bằng chứng của mối quan hệ f x là O g x . Cấu trúc dữ liệu và giải thuật - HCMUS 2016 38 Big-O phân hoạch được các hàm với các độ tăng khác nhau. Nếu có hai hàm f x và g x sao cho f x là O g x và g x là O f x thì ta nói hai hàm f x và g x đó là có cùng bậc. Ví dụ f x 7x2 là O x2 chọn k 0 C 7 . Do vậy 7x2 và x2 3x 2 và x2 là 3 hàm có cùng bậc. Cấu trúc dữ liệu và giải thuật - HCMUS 2016 https tailieudientucntt FIT-HCMUS 3 39 Lưu ý 7x2 cũng là O x3 nhưng x3 không là O 7x2 . Thật vậy Nếu x3 là O 7x2 thì ta phải tìm được C và k sao cho x3 C 7x2 x 7C với mọi x gt k. .