Tham khảo tài liệu 'bài 6 growthorders', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | University of Florida Dept. of Computer & Information Science & Engineering COT 3100 Applications of Discrete Structures Dr. Michael P. Frank Slides for a Course Based on the Text Discrete Mathematics & Its Applications (5th Edition) by Kenneth H. Rosen 1/8/01 A word about organization: Since different courses have different lengths of lecture periods, and different instructors go at different paces, rather than dividing the material up into fixed-length lectures, we will divide it up into “modules” which correspond to major topic areas and will generally take 1-3 lectures to cover. Within modules, we have smaller “topics”. Within topics are individual slides. Module #6: Cấp độ tăng - Orders of Growth Rosen 5th ed., § ~22 slides, ~1 lecture 1/8/01 Cấp độ tăng (§) Đố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 . | University of Florida Dept. of Computer & Information Science & Engineering COT 3100 Applications of Discrete Structures Dr. Michael P. Frank Slides for a Course Based on the Text Discrete Mathematics & Its Applications (5th Edition) by Kenneth H. Rosen 1/8/01 A word about organization: Since different courses have different lengths of lecture periods, and different instructors go at different paces, rather than dividing the material up into fixed-length lectures, we will divide it up into “modules” which correspond to major topic areas and will generally take 1-3 lectures to cover. Within modules, we have smaller “topics”. Within topics are individual slides. Module #6: Cấp độ tăng - Orders of Growth Rosen 5th ed., § ~22 slides, ~1 lecture 1/8/01 Cấp độ tăng (§) Đố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. 1/8/01 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? A 1/8/01 Hình dung cấp độ tăng - Visualizing Orders of Growth Trên đồ thị, khi bạ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 1/8/01 Khái niệm cấp độ tăng Concept 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 Θ
