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,. . | Bài giảng Cấu trúc dữ liệu và giải thuật: Độ tăng của hàm - Văn Chí Nam, Nguyễn Thị Hồng Nhung, Đặng Nguyễn Đức Tiến 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 ©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 > 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 > k • Ví dụ, hàm f(x) = x2 + 3x + 2 là O(x2). Thật vậy, khi x > 2 thì x < x2 và 2 < 2x2 Do đó x2 + 3x + 2 < 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 ©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ó .
