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),. nội dung chi tiết. | Thiết Kế & Đánh Giá Thuật Toán Khái Niệm Tiệm Cận TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung Khái niệm tiệm cận Ký 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àm Vớ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 2 Ký 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ác hằng số > 0, và > 0 sao cho: 0 ≤ ≤ với mọi ≥ Ví dụ: 2 ∈ ( ) ( = 1, = 2) Hàm không phả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 ∈ ( .
