Bài giảng Thiết kế và đánh giá thuật toán - 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