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

Thiết Kế & Đánh Giá Thuật Toán<br /> Khái Niệm Tiệm Cận<br /> TS. Lê Nguyên Khôi<br /> Trường Đại Học Công Nghệ - ĐHQGHN<br /> <br /> Nội Dung<br />
<br /> <br /> Khái niệm tiệm cận<br /> Ký hiệu
– big-Oh (của …)<br />
Ký hiệu  – big-Omega (của…)<br />
Ký hiệu  – Theta (của …)<br />
<br /> <br /> 1<br /> <br /> Độ Tăng Của Hàm<br /> Với  là độ lớn dữ liệu đầu vào<br />
Tỷ lệ tăng trưởng (chính xác):<br />
<br /> <br />  +  + <br />
 + <br />
 log  +  + <br />
<br /> <br />
<br /> <br /> Bậc tăng trưởng (xấp xỉ):<br />  +  + <br /> =><br />
 + <br /> =><br />
 log  +  + =><br />
<br /> <br /> bậc <br /> bậc <br /> bậc  log <br /> 2<br /> <br /> Ký Hiệu Tiệm Cận (Ο- – big-Oh)<br />
<br /> <br />
- – big-Oh (chặn trên – upper bound):<br /> Ta nói rằng <br />  ∈
(  ) nếu tồn tại các<br /> hằng số > 0, và  > 0 sao cho:<br /> 0 ≤ <br />  ≤  <br /> với mọi  ≥ <br /> <br />
<br /> <br /> Ví dụ:<br /> <br /> <br /> 2<br /> <br /> ∈<br /> <br /> <br />
( )<br /> <br /> ( = 1,  = 2)<br /> <br /> Hàm không<br /> phải giá trị<br /> 3<br /> <br /> Ο- – big-Oh – Khái Niệm Tập Hợp<br />
<br /> <br />
- – big-Oh (chặn trên – upper bound):<br />
 <br /> <br />
<br /> <br /> = {<br />  : tồn tại các hằng số > 0,<br /> và  > 0 sao cho:<br /> 0 ≤ <br />  ≤  <br /> với mọi  ≥  }<br /> <br /> Ví dụ: 2 ∈
( )<br /> <br /> 4<br /> <br />