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

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