Bài giảng Orders of Growth

University of FloridaDept. of Computer & Information Science & EngineeringCOT 3100Applications of Discrete StructuresDr. Michael P. Frank Slides for a Course Based on the TextDiscrete Mathematics & Its Applications (5th Edition)by Kenneth H. Rosen Module #6:Cấp độ tăng - Orders of Growth Rosen 5th ed., §2.2 ~22 slides, ~1 lecture Cấp độ tăng (§1.8) Đối với các hàm số, ta thường cần phải biết độ đo thô xem hàm tăng nhanh như thế nào. Nếu f(x) tăng nhanh hơn g(x), thì f(x) luôn sẽ trở nên lớn hơn g(x) đối với những giá trị của x đủ lớn. Cấp độ tăng hữu ích trong công nghệ khi chỉ ra một thiết kế này tốt hơn thiết kế khác. Cấp độ tăng - Động lực (Motivation) Giả sử bạn thiết kế web site để xử lý số liệu của người sử dụng (như các bản ghi tài chính). Giả sử chương trình A trong CSDL dùng fA(n)=30n+8 microseconds để xử lý bất kỳ n bản ghi nào, trong khi đó chương trình B dùng fB(n)=n2+1 microseconds để xử lý n bản ghi. Bạn chọn chương trình nào, khi bạn muốn hỗ trợ một triệu khách hàng? Hình dung cấp độ tăng- Visualizing Orders of Growth Trên đồ thị, khibạn đi sang phải, hàm tăng nhanh hơn luôn nhấtđịnh sẽ trở nên lớn hơn hàm kia... fA(n)=30n+8 Increasing n  fB(n)=n2+1 Value of function  Khái niệm cấp độ tăngConcept of order of growth Ta nói fA(n)=30n+8 là (nhiều nhất) cấp n, hoặc O(n). Cái đó tối đa là VCL ngang cấp với n. fB(n)=n2+1 là cấp n2, hoặc O(n2). Cái đó tối đa là VCL ngang cấp n2. Bất cứ hàm nào mà cấp sát nhất của nó là O(n2) cũng sẽ tăng nhanh hơn mọi hàm cấp O(n). Sau này ta sẽ dùng Θ để biểu diễn chính xác cấp. Đối với số lớn người sử dụng, hàm cấp chính xác n2 sẽ dùng nhiều thời gian hơn hàm tuyến tính. Định nghĩa: O(g), tối đa cấp g G/s g là một hàm bất kỳ RR. ĐN “tối đa cấp g”, viết là O(g), là hàm: {f:RR | c,k: x>k: f(x)  cg(x)}. “Bắt đầu từ một k nào đó, hàm f bị chặn bởi hằng số c lần g (tức là, tỷ lệ với g).” “f là tối đa cấp g”, hoặc “f là O(g)”, hoặc “f=O(g)” tất cả đều có nghĩa là fO(g). Thông thường chữ “tối đa” bị bỏ qua. Các tham số trong định nghĩa Lưu ý f là O(g) khi tồn tạo bất kỳ giá trị c và k mà thoả mãn định nghĩa. Nhưng: Các giá trị c, k cụ thể mà làm cho khẳng định trên đúng không là duy nhất: mọi giá trị của c, k lớn hơn đều thỏa mãn. Ban không cần phải tìm các giá trị nhỏ nhất của c và k thỏa mãn. (Thực tế trong một số trường hợp sẽ không có giá trị nhỏ nhất!) However, you should prove that the values you choose do work. “Big-O” Proof Examples Show that 30n+8 is O(n). Show c,k: n>k: 30n+8  cn. Let c=31, k=8. Assume n>k=8. Thencn = 31n = 30n + n > 30n+8, so 30n+8 k: n2+1  cn2. Let c=2, k=1. Assume n>1. Then cn2 = 2n2 = n2+n2 > n2+1, or n2+10). Nó không phải nhỏ hơn 31nở mọi nơi. Nhưng nó nhỏ hơn 31n ở mọi nơibên phải n=8. Ví dụ Big-O example bằng đồ thị Increasing n  Value of function  n 30n+8 30n+8O(n) Các ghi chú có ích về Big O Big O, như một quan hệ có tính bắc cầu: fO(g)  gO(h)  fO(h) O không thay đổi khi nhân thừa số hằng số, lấy căn hoặc logarit... f (in (1)) & hằng số a,bR, với b0, af, f 1-b, và (logb f)a tất cả đều là O(f). Tổng các hàm:Nếu gO(f) và hO(f), thì g+hO(f). Thêm một số khẳng định về Big OMore Big-O facts c>0, O(cf)=O(f+c)=O(fc)=O(f) f1O(g1)  f2O(g2)  f1 f2 O(g1g2) f1+f2 O(g1+g2)  = O(max(g1,g2)) = O(g1) if g2O(g1) (Very useful!) Tiếp tục về cấp độ tăng (§1.8) Đối với mọi g:RR, “nhiều nhất cấp độ g”,O(g)  {f:RR | c,k x>k |f(x)|  |cg(x)|}. Thông thường, người ta xét các hàm dương và có thể bỏ qua dấu trị tuyệt đối. “fO(g)” thường được viết “f là O(g)”hoặc “f=O(g)”. Dạng sau cùng cho phép mở rộng định nghĩa tổng quát hơn... Các biểu thức về cấp độ tăngOrder-of-Growth Expressions “O(f)” thường được dùng như một số hạng trong một biểu thức theo nghĩa: “một hàm f nào đó mà fO(f)”. E.g.: “x2+O(x)” nghĩa là “x2 cộng một hàm nào đó mà là O(x)”. Về hình thức, ta có thể nghĩ về biểu thức bất kỳ như vậy là ký hiệu một tập hợp các hàm: x2+O(x) : {g | fO(x): g(x)= x2+f(x)} Các phưong trình về cấp độ tăngOrder of Growth Equations G/s E1 và E2 là các biểu thức cấp độ tăng tương ứng với các tập hàm S và T. Khi đó “phương trình” E1=E2 có nghĩa là fS, gT : f=ghoặc đơn giản ST. Ví dụ: x2 + O(x) = O(x2) nghĩa là fO(x): gO(x2): x2+f(x)=g(x) Một số điều có ích về Big OUseful Facts about Big O  f,g & constants a,bR, with b0, af = O(f); (e.g. 3x2 = O(x2)) f+O(f) = O(f); (e.g. x2+x = O(x2)) Also, if f=(1) (at least order 1), then: |f|1-b = O(f); (e.g. x1 = O(x)) (logb |f|)a = O(f). (e.g. log x = O(x)) g=O(fg) (e.g. x = O(x log x)) fg  O(g) (e.g. x log x  O(x)) a=O(f) (e.g. 3 = O(x)) Định nghĩa: (g), chính xác cấp g Nếu fO(g) và gO(f), thì ta nói “g và f là cùng cấp” hoặc “f là (chính xác) cấp g” và viết f(g). Định nghĩa khác tương đương:(g)  {f:RR |  c1c2k>0 x>k: |c1g(x)||f(x)||c2g(x)| } “Bắt đầu từ điểm k nào đó, f(x) kẹp giữa hai hàm tỷ lệ của g(x).” Các qui tắc cho  Đa số qui tắc giống O( ), ngoại trừ:  f,g>0 & constants a,bR, with b>0, af  (f), but  Same as with O. f  (fg) unless g=(1)  Unlike O.|f| 1-b  (f), and  Unlike with O. (logb |f|)c  (f).  Unlike with O. Các hàm trong hai trường hợp cuối được gọi là cấp nhỏ hơn chặt so với (f).  example Determine whether: Quick solution: Các quan hệ cấp độ khác Other Order-of-Growth Relations (g) = {f | gO(f)}“The functions that are at least order g.” o(g) = {f | c>0 k x>k : |f(x)| 0 k x>k : |cg(x)| 1. Khi đó các điều sau là đúng:1  log log n  log n ~ logk n  logk n   n1/k  n  n log n  nk  kn  n!  nn … Tóm tắt: cấp độ tăngReview: Orders of Growth (§1.8) Định nghĩa các tập cấp độ tăng, g:RR O(g) : {f |  c>0 k x>k |f(x)| 0 k x>k |f(x)| < |cg(x)|} (g) : {f | gO(f)} (g) : {f | go(f)} (g) : O(g)  (g) Ví dụ Sắp xếp cấp độ tăng sau theo thứ tự tăng dần: n2, n, log n, n log n, log log n, 2n, n!, n (log n)2 Cho tập o(n), O(n), (n), (n), (n). Xem các cấp độ tăng sau thuộc các tập nào: n sin n; n/sin n; 2n; n/3 + 100; 1000n + 50 n1/2; log n; n log n + n2; n/log n + n ; 2n + n9 ; n! Giải Log log n, log n, n log n, n, n (log n)2, n2, 2n, n! VD: nsin n  O(n), nhưng n.sin n  (n) n/sin n  O(n2), nhưng n/sin n  (n2) n/3 + 100   (n); 1000n + 50 n1/2  (n) n log n + n2  (n2); n/log n + n   (n) ; 2n + n9   (2n) Cho cặp hàm xét quan hệ Cho cặp hàm,chúng có quan hệ nào? ~ là quan hệ VCL tương đương