Bài giảng Thiết kế và đánh giá thuật toán: Khái niệm tiệm cận - TS. Lê Nguyên Khôi

Bài giảng "Thiết kế và đánh giá thuật toán: Khái niệm tiệm cận" cung cấp cho người học các kiến thức: Độ tăng của hàm, ký hiệu tiệm cận (Ο- – big-Oh), ký hiệu tiệm cận (o- little-oh & - little-omega),... Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Thiết kế và đánh giá thuật toán: Khái niệm tiệm cận - TS. Lê Nguyên KhôiThiết Kế & Đánh Giá Thuật ToánKhái Niệm Tiệm CậnTS. Lê Nguyên KhôiTrường Đại Học Công Nghệ - ĐHQGHNNội DungKhái niệm tiệm cậnKý hiệu – big-Oh (của …) Ký hiệu – big-Omega (của…) Ký hiệu – Theta (của …)1Độ Tăng Của HàmVới là độ lớn dữ liệu đầu vào Tỷ lệ tăng trưởng (chính xác): + + + log + + Bậc tăng trưởng (xấp xỉ): + + => + => log + + =>bậc bậc bậc log 2Ký Hiệu Tiệm Cận (Ο- – big-Oh)- – big-Oh (chặn trên – upper bound):Ta nói rằng ∈ ( ) nếu tồn tại cáchằng số > 0, và > 0 sao cho:0 ≤ ≤ với mọi ≥ Ví dụ:2∈( )( = 1, = 2)Hàm khôngphải giá trị3Ο- – big-Oh – Khái Niệm Tập Hợp- – big-Oh (chặn trên – upper bound): = { : tồn tại các hằng số > 0,và > 0 sao cho:0 ≤ ≤ với mọi ≥ }Ví dụ: 2 ∈ ( )4