TAILIEUCHUNG - 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. .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Bài giảng Cấu trúc dữ liệu
• Độ tăng của tổ hợp các hàm
• Độ tăng của hàm
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp