›

Thiết Kế và Đánh Giá Thuật Toán Khái Niệm Tiệm Cận - Lê Nguyên Khôi

pdf 19 trang huongle 5620
Download
Bạn đang xem tài liệu "Thiết Kế và Đánh Giá Thuật Toán Khái Niệm Tiệm Cận - Lê Nguyên Khôi", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfthiet_ke_va_danh_gia_thuat_toan_khai_niem_tiem_can_le_nguyen.pdf

Nội dung text: Thiết Kế và Đánh Giá Thuật Toán Khái Niệm Tiệm Cận - Lê Nguyên Khôi

  1. ế ế ậ ệ ệ ậ ườ ạ ọ ệ
  2. ộ  Khái ni m ti m cn  Ký hi u – big-Oh (ca )  Ký hi u – big-Omega (ca )  Ký hi u – Theta (ca ) 1
  3. ộ ủa  Vi là ln d li u u vào  T l tng tr ư ng (chính xác):  + +  +  log++  Bc tng tr ư ng (xp x):  + + => bc  + => bc  log++ => bc log 2
  4. ệ ệ ậ Ο-  - – big-Oh (ch n trên – upper bound): Ta nói rng ∈ ( ) nu tn ti các hng s > 0, và > 0 sao cho: 0 ≤ ≤ vi mi ≥  Ví d: 2 ∈ ( ) ( = 1, = 2) Hàm không ph ải giá tr ị 3
  5. Ο- ệ ậ ợ  - – big-Oh (ch n trên – upper bound): = { : tn t i các hng s > 0, và > 0 sao cho: 0 ≤ ≤ vi m i ≥ }  Ví d: 2 ∈ () 4
  6. ệ ệ ậ - a  Ký hi u - là ký hi u ch n trên. Không có ý ngh a khi nói tng ít nh t ()  - – big-Omega (ch n dư i – lower bound): = { : tn ti các hng s > 0, và > 0 sao cho: 0 ≤ ≤ vi m i ≥ }  Ví d: ∈ (log ) ( = 1, = 16 ) 5
  7. ệ ệ ậ a  Ký hi u - và - tư ng t ≤ và ≥  Ký hi u - và - tư ng t > và 0, và > 0 sao cho: 0 ≤ < vi m i ≥ }  Ví d: 2 ∈ ( ) ( = 2/) 6
  8. ệ ệ ậ a  Ký hi u - và - tư ng t ≤ và ≥  Ký hi u - và - tư ng t > và 0, và > 0 sao cho: 0 ≤ < vi m i ≥ }  Ví d: ∈ log ( = 1 + 1/) 7
  9. ệ ệ ậ - a  Ký hi u - (ch n ch t – tight bound): = { : tn ti các hng s > 0, > 0, và > 0 sao cho: 0 ≤ () ≤ () ≤ () vi m i ≥ } = ∩  Ví d: − ∈ ( ) 8
  10. ậ ủa ệ ậ  Xác nh bc ca ti m cn bng vi c gi i bt ph ư ng trình tìm và  Cách khác:  B các bc th p (bc tng ch m);  B các h s là hng  Ví d: 3 + 90– + 6046 ∈ () 9
  11. ậ ủa ệ ậ ụ  Ch ng minh ∈ trong ó: 1 = − 3 =  Cn tìm các h ng s > , > , và > sao cho: ≤ () ≤ () ≤ () 10
  12. ậ ủa ệ ậ  Nu nói “Th i gian ch y ca 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
  13. ắ ế ả InsertionSort () 1 for to do ← 2 . 2 ← [] 3 ← − 1 4 while > 0 and > do 5 + 1 ← [] 6 ← − 1 7 +1 ← 12
  14. ắ ế  Tr ư ng hp xu nh t: = () ∈ ()  Tr ư ng hp trung bình: = (/2) ∈ ( ) 13
  15. ắ ế ựa ọ ả SelectionSort () 1 for to do ← 1 . − 1 2 ← 3 for to do ← + 1 . 4 if < [] 5 ← 6 exchange with [] 14
  16. ắ ế ựa ọ  Tr ư ng hp xu nh t: = () ∈ ()  Tr ư ng hp trung bình: = () ∈ () 15
  17. ắ ế ổ ọ ả BubbleSort () 1 for to do ← 1 . − 1 2 for downto do ← . + 1 3 if < [ − 1] 4 exchange with [ − 1] 16
  18. ắ ế ổ ọ  Tr ư ng hp xu nh t: = () ∈ ()  Tr ư ng hp trung bình: = () ∈ () 17
  19. ậ 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