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

pdf
Số trang Bài giảng Cấu trúc dữ liệu & giải thuật: Độ tăng của hàm 17 Cỡ tệp Bài giảng Cấu trúc dữ liệu & giải thuật: Độ tăng của hàm 2 MB Lượt tải Bài giảng Cấu trúc dữ liệu & giải thuật: Độ tăng của hàm 0 Lượt đọc Bài giảng Cấu trúc dữ liệu & giải thuật: Độ tăng của hàm 17
Đánh giá Bài giảng Cấu trúc dữ liệu & giải thuật: Độ tăng của hàm
4.2 ( 15 lượt)
Nhấn vào bên dưới để tải tài liệu
Đang xem trước 10 trên tổng 17 trang, để tải xuống xem đầy đủ hãy nhấn vào bên trên
Chủ đề liên quan

Nội dung

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 BigOmega và Big-Theta. Cấu trúc dữ liệu và giải thuật - HCMUS 2016 CuuDuongThanCong.com ©FIT-HCMUS https://fb.com/tailieudientucntt 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 CuuDuongThanCong.com ©FIT-HCMUS https://fb.com/tailieudientucntt 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 CuuDuongThanCong.com ©FIT-HCMUS https://fb.com/tailieudientucntt 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 > k. Điều này không thể xảy ra vì không thể tìm được k và C nào như vậy. Do vậy, trong quan hệ f(x) là O(g(x)), hàm g(x) thường được chọn là nhỏ nhất có thể. Cấu trúc dữ liệu và giải thuật - HCMUS 2016 40 1. Hàm đa thức: f(x) = anxn + an-1xn-1 + … + a1x + a0 Khi đó f(x) là O(xn). Cấu trúc dữ liệu và giải thuật - HCMUS 2016 CuuDuongThanCong.com ©FIT-HCMUS https://fb.com/tailieudientucntt 4 41  Nếu f(x) là O(g(x)) thì c.f(x) là O(g(x)) với c là hằng số. Cho f1(x) là O(g1(x)) và f2(x) là O(g2(x)). Khi đó:  tắc tổng: (f1(x)+f2(x)) là O(max(|g1(x)|, |g2(x)|))  Quy tắc nhân: (f1(x) * f2(x)) là O(g1(x) * g2(x)).  Quy Cấu trúc dữ liệu và giải thuật - HCMUS 2016 42 Cấu trúc dữ liệu và giải thuật - HCMUS 2016 CuuDuongThanCong.com ©FIT-HCMUS https://fb.com/tailieudientucntt 5 43 Cấu trúc dữ liệu và giải thuật - HCMUS 2016 44    Nói như sau là không chính xác: f(x) = O(g(x)) Nói như dưới đây lại càng không chính xác: f(x) > O(g(x)) Chỉ sử dụng như sau: f(x) là O(g(x)), hoặc f(x) với bậc g(x). Cấu trúc dữ liệu và giải thuật - HCMUS 2016 CuuDuongThanCong.com ©FIT-HCMUS https://fb.com/tailieudientucntt 6 45 Cấu trúc dữ liệu Giải thuật Chương trình Cấu trúc dữ liệu và giải thuật - HCMUS 2016 46      Tốc độ thực thi. Tính chính xác. Đơn giản, dễ hiểu, dễ bảo trì. Mức phổ dụng … Cấu trúc dữ liệu và giải thuật - HCMUS 2016 CuuDuongThanCong.com ©FIT-HCMUS https://fb.com/tailieudientucntt 7 47  Thời gian giải quyết một bài toán phụ thuộc vào nhiều yếu tố:  Tốc độ thực thi của máy tính (phần cứng lẫn phần mềm).  Tài nguyên (ví dụ: bộ nhớ).  Thuật toán.  Làm thế nào đánh giá được thời gian thực thi hiệu quả? Cấu trúc dữ liệu và giải thuật - HCMUS 2016 48  Đánh giá thời gian thực hiện dựa trên những phép toán quan trọng như:  Phép so sánh  Phép gán   Đánh giá bằng cách tính số lượng các phép toán quan trọng theo độ lớn của dữ liệu. Từ đó, thời gian thực hiện của một thuật toán có thể được đánh giá theo một hàm phụ thuộc vào độ lớn đầu vào. Cấu trúc dữ liệu và giải thuật - HCMUS 2016 CuuDuongThanCong.com ©FIT-HCMUS https://fb.com/tailieudientucntt 8 49     Bước 1. Gán tổng = 0. Gán i = 0. Bước 2.  Tăng i thêm 1 đơn vị.  Gán Tổng = Tổng + i Bước 3. So sánh i với 10  Nếu i < 10, quay lại bước 2.  Ngược lại, nếu i ≥ 10, dừng thuật toán. Số phép gán của thuật toán là bao nhiêu? Số phép so sánh là bao nhiêu?  Gán: g(n) = 2n + 2, So sánh: s(n) = n Cấu trúc dữ liệu và giải thuật - HCMUS 2016 50 Độ phức tạp của các thuật toán không đổi Khi nào thuật toán cho lời giải thỏa đáng? Phải luôn cho đáp số đúng. Phải hiệu quả (độ phức tạp tính toán) Trường hợp xấu nhất Độ phức tạp thời gian Trường hợp trung bình Độ phức tạp không gian Trường hợp tốt nhất Cấu trúc dữ liệu và giải thuật - HCMUS 2016 CuuDuongThanCong.com ©FIT-HCMUS https://fb.com/tailieudientucntt 9 51  Thuật toán:  B1. Đặt giá trị cực đại tạm thời bằng số nguyên đầu tiên trong dãy.  B2. So sánh số nguyên tiếp sau với giá trị cực đại tạm thời. Nếu nó lớn hơn giá trị cực đại tạm thời thì đặt cực đại tạm thời bằng số nguyên đó.  B3. Lặp lại B2 nếu còn các số nguyên trong dãy.  B4. Dừng khi không còn số nguyên nào nữa trong dãy. Cực đại tạm thời chính là số nguyên lớn nhất của dãy. Cấu trúc dữ liệu và giải thuật - HCMUS 2016 52     Vì phép sơ cấp sử dụng trong thuật toán là phép so sánh, nên phép so sánh được dùng làm thước đo độ phức tạp. Tại mỗi số hạng, ta thực hiện 2 phép so sánh, 1 phép xem đã hết dãy hay chưa và 1 phép so với cực đại tạm thời. Vì hai phép so sánh được dùng từ số hạng thứ 2 đến n, và thêm 1 phép so sánh nữa để ra khỏi vòng lặp, nên ta có chính xác 2(n-1) + 1 = 2n – 1 phép so sánh. Do vậy, độ phức tạp của thuật toán là O(n). Cấu trúc dữ liệu và giải thuật - HCMUS 2016 CuuDuongThanCong.com ©FIT-HCMUS https://fb.com/tailieudientucntt 10
This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.