Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 2: Khái niệm tiệm cận - Lê Nguyên Khôi

BubbleSort (-) 1 for . ← 1 to -. 1234 − 1 do 2 for 9 ← -. 1234 downto . + 1 do 3 if - 9 < -[9 − 1] 4 exchange - 9 with -[9 − 1] Sắp Xếp Nổi Bọt – Phân Tích  Trường hợp xấu nhất: :  = ; (9) < => ∈ ()  Trường hợp trung bình: :  = ; (9) < => ∈ ()

pdf19 trang | Chia sẻ: thucuc2301 | Lượt xem: 502 | Lượt tải: 0download
Bạn đang xem nội dung tài liệu Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 2: Khái niệm tiệm cận - Lê Nguyên Khôi, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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ỉ):   +  + => bậc    +  => bậc    log  +  + => 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) 3 Hàm không phải giá trị Ο- – 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 Ký Hiệu Tiệm Cận (- – big-Omega)  Ký hiệu - là ký hiệu chặn trên. Không có ý nghĩa khi nói  tăng ít nhất ()  - – big-Omega (chặn dưới – lower bound):    = {  : tồn tại các hằng số > 0, và  > 0 sao cho: 0 ≤   ≤  với mọi  ≥ }  Ví dụ:  ∈ (log ) ( = 1,  = 16) 5 Ký Hiệu Tiệm Cận (- little-oh & - little-omega)  Ký hiệu - và - tương tự ≤ và ≥  Ký hiệu - và - tương tự > và < "   = {  : tồn tại các hằng số > 0, và  > 0 sao cho: 0 ≤  <   với mọi  ≥ }  Ví dụ: 2 ∈ () ( = 2/ ) 6 Ký Hiệu Tiệm Cận (- little-oh & - little-omega)  Ký hiệu - và - tương tự ≤ và ≥  Ký hiệu - và - tương tự > và <   = {  : tồn tại các hằng số > 0, và  > 0 sao cho: 0 ≤   <  với mọi  ≥ }  Ví dụ:  ∈  log  ( = 1 + 1/ ) 7 Ký Hiệu Tiệm Cận (- – Theta)  Ký hiệu - (chặn chặt – tight bound):    = {  : tồn tại các hằng số $ > 0,  > 0, và  > 0 sao cho: 0 ≤ $() ≤ () ≤ () với mọi  ≥ }    =    ∩     Ví dụ: $   − 2 ∈ () 8 Bậc Của Tiệm Cận  Xác định bậc của tiệm cận bằng việc giải bất phương trình tìm ' và   Cách khác:  Bỏ các bậc thấp (bậc tăng chậm);  Bỏ các hệ số là hằng  Ví dụ: 3 + 90– 5 + 6046 ∈ () 9 Bậc Của Tiệm Cận – Ví Dụ  Chứng minh  ∈    trong đó:  = 13  − 50   =   Cần tìm các hằng số $ > 0,  > 0, và  > 0 sao cho: 0 ≤ $() ≤ () ≤ () 10 Bậc Của Tiệm Cận  Nếu nói “Thời gian chạy của thuật toán ít nhất là ()” có đúng hay không?  Không có ý nghĩa do - – big- là chặn trên 11 Sắp Xếp Chèn – Mã Giả InsertionSort (-) 1 for . ← 2 to -. 1234 do 2 526 ← -[.] 3 9 ← . − 1 4 while 9 > 0 and - 9 > 526 do 5 - 9 + 1 ← -[9] 6 9 ← 9 − 1 7 - 9 + 1 ← 526 12 Sắp Xếp Chèn – Phân Tích  Trường hợp xấu nhất: :  =;(9) < => ∈ ()  Trường hợp trung bình: :  =;(9/2) < => ∈ () 13 Sắp Xếp Lựa Chọn – Mã Giả SelectionSort (-) 1 for . ← 1 to -. 1234 − 1 do 2 ?@112?3 ← . 3 for 9 ← . + 1 to -. 1234 do 4 if - 9 < -[?@112?3] 5 ?@112?3 ← 9 6 exchange - . with -[?@112?3] 14 Sắp Xếp Lựa Chọn – Phân Tích  Trường hợp xấu nhất: :  =;(9) < => ∈ ()  Trường hợp trung bình: :  =;(9) < => ∈ () 15 Sắp Xếp Nổi Bọt – Mã Giả BubbleSort (-) 1 for . ← 1 to -. 1234 − 1 do 2 for 9 ← -. 1234 downto . + 1 do 3 if - 9 < -[9 − 1] 4 exchange - 9 with -[9 − 1] 16 Sắp Xếp Nổi Bọt – Phân Tích  Trường hợp xấu nhất: :  =;(9) < => ∈ ()  Trường hợp trung bình: :  =;(9) < => ∈ () 17 Bài Tập Bài tập trong sách: Exercise 3.1-1 tr.52 Exercise 3.1-4 tr.53 Exercise 3.1-8 tr.53 18

Các file đính kèm theo tài liệu này:

  • pdfthiet_ke_danh_gia_thuat_toanbaigiang02_tiemcan_4036_2032089.pdf