Giới thiệu
Độ tăng hàm
Big-O
Tính chất
Big-Theta
Tính chất
Little-o
Độ phức tạp
Xấu nhất
Trung bình
Tính đúng đắn
Điều kiện
Lặp
Ví dụ
Tóm tắt
1/35Tổ toán đại học FPT
05/03/14
Chương 2.2, 2.3 Kenneth H. Rosen
Xuân 2008
Đại học FPT
Discrete Mathematics I
độ phức tạp & tính
đúng đắn
complexity & correctness
độ phức tạp & tính
đúng đắn
complexity & correctness
Thuật toán
Algorithm
Thuật toán
Algorithm

•
Trường hợp trung bình
•
Tính đúng đắn thuật toán
Giới thiệu
Độ tăng hàm
Big-O
Tính chất
Big-Theta
Tính chất
Little-o
Độ phức tạp
Xấu nhất
Trung bình
Tính đúng đắn
Điều kiện
Lặp
Ví dụ
Tóm tắt
3/35Tổ toán đại học FPT
05/03/14
Thuật toán BIG-O
Algorithm BIG-O
Định nghĩa Definition
Định nghĩa Definition
Cho f(x) và g(x) là hai hàm số từ tập các số nguyên
hoặc số thực đến tập các số thực. Ta nói f(x) là O(g(x))
hoặc f(x) là big-O của g(x) hay f(x) ∈ O(g(x)) nếu tồn tại
hai hằng số C và k sao cho
|f(x)| ≤ C|g(x)| với mọi x ≥ k.

Ví dụ Example
Chứng minh f(n) = 30n + 8 là big-O của g(n) = n.
Ta cần chứng minh ∃c,k: ∀n > k: 30n + 8 ≤ cn.
Lấy c = 31, k = 8. Khi đó
với n > k = 8,
cn = 31n = 30n + n > 30n+8
n>k=8 →
n
30n+8
cn =
31n
30n+8 ∈O(n)
Giá trị cụ thể của c và k
gọi là bằng chứng. Ta có
thể tìm nhiều bằng chứng.
Chẳng hạn:
c = 32, k = 9
Big-O
Giới thiệu
Độ tăng hàm
Big-O
Tính chất
Big-Theta
Tính chất
Little-o
Độ phức tạp
Xấu nhất
Trung bình
Tính đúng đắn
Điều kiện

40
50
60
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5
n
1
log(n)
n^2
2^n
n!
Big-O
Giới thiệu
Độ tăng hàm
Big-O
Tính chất
Big-Theta
Tính chất
Little-o
Độ phức tạp
Xấu nhất
Trung bình
Tính đúng đắn
Điều kiện
Lặp
Ví dụ
Tóm tắt
6/35Tổ toán đại học FPT
05/03/14
Thuật toán BIG-O
Algorithm BIG-O

, (log
b
f)
a
∈ O(f) với mọi a, b ∈ R và b ≥ 0.
•
f
1
∈O(g
1
) ∧ f
2
∈O(g
2
) → f
1
f
2
∈ O(g
1
g
2
)
•
f
1
∈O(g
1
) ∧ f
2

x
n
+ a
n -1
x
n -1
+ …+ a
1
x + a
0
∈ O(x
n
) (a
0
, a
1
, …, a
n
là
các số thực)
•
f ∈ O(g) ∧ g ∈ O(h) → f ∈ O(h)
•
af, f
1-b
, (log
b
f)
a
∈ O(f) với mọi a, b ∈ R và b ≥ 0.

2
∈ O(g
1
+g
2
)
•
O(g
1
+g
2
) = O(max(g
1
,g
2
)) = O(g
1
) nếu g
2
∈O(g
1
)
Tính chất
Giới thiệu
Độ tăng hàm
Big-O
Tính chất
Big-Theta
Tính chất
Little-o

n
i
2
+
2
=
2
nn
∈ O(n
2
)
hoặc ∈ n
2
/2 + O(n)
Bài tập: Chứng minh
)(log)( 1+=
1
=
∑
1=
On
i
nf
n
i
Tính chất
Giới thiệu
Độ tăng hàm
Big-O
Tính chất

, C
2
, k > 0
sao cho
C
1
|g(x)| ≤ |f(x)| ≤ C
2
|g(x)| với mọi x ≥ k.
Cho f(x) và g(x) là hai hàm số từ tập các số nguyên hoặc
số thực đến tập các số thực. Ta nói
•
f(x) là Ω(g(x)) hoặc f(x) là big-Omega của g(x) nếu tồn
tại hai hằng số C > 0 và k sao cho
|f(x)| ≥ C|g(x)| với mọi x ≥ k.
•
f(x) là Θ(g(x)) hoặc f(x) là big-Theta của g(x) nếu f ∈
O(g) và f ∈ Ω(g) tức là tồn tại các hằng số C
1
, C
2
, k > 0
sao cho
C
1
|g(x)| ≤ |f(x)| ≤ C
2
|g(x)| với mọi x ≥ k.
g ∈ O(f)
f và g cùng bậc

x
n -1
+ …+ a
1
x + a
0
∈ Θ(x
n
) (ở đây a
0
, a
1
, …,
a
n
là các số thực và a
n
≠ 0)
•
f ∈ Θ(g) ∧ g ∈ Θ(h) → f ∈ Θ(h)
•
af ∈ Θ(f) với mọi a ≠ 0
•
f
1
∈ Θ(g
1
) ∧ f
2
∈ Θ(g

1
+g
2
) = Θ(max(g
1
,g
2
)) = Θ(g
1
) nếu g
2
∈O(g
1
)
•
a
n
x
n
+ a
n -1
x
n -1
+ …+ a
1
x + a
0
∈ Θ(x
n
) (ở đây a

)
•
f
1
∈ Θ(g
1
) ∧ f
2
∈ Θ(g
2
) → f
1
+ f
2
∈ Θ(g
1
+g
2
)
•
Θ(g
1
+g
2
) = Θ(max(g
1
,g
2
)) = Θ(g
1

f(n) = log(1) + log(2) + …+ log(n) g(n) = nlog(n)
f (n) ≤ g(n) ∀ n ≥ 1
⇒ f (n) ∈ O(g(n))
2f(n) = log(1) + log(2) + …+ log(n)
+ log(n) + log(n-1) +…+ log(1)
= log(1.n) + log(2(n-1)) + … + log(n.1)
≥ g(n) ∀ n ≥ 1
⇒ f (n) ∈ Ω(g(n))
Vậy f (n) ∈ Θ(g(n))
Tính chất
Giới thiệu
Độ tăng hàm
Big-O
Tính chất
Big-Theta
Tính chất
Little-o
Độ phức tạp
Xấu nhất
Trung bình
Tính đúng đắn
Điều kiện
Lặp
Ví dụ
Tóm tắt
11/35Tổ toán đại học FPT
05/03/14
Thuật toán BIG-
THETA Algorithm BIG-
THETA

x
)| < |
)| < |
cg
cg
(
(
x
x
)|
)|
•
f(x) là ω(g(x)) hoặc f có bậc cao hơn thật sự g nếu
∀
∀
c
c
>0
>0
∃
∃
k
k∀
∀
x>k
x>k
: |

k
k∀
∀
x>k
x>k
: |
: |
f
f
(
(
x
x
)| < |
)| < |
cg
cg
(
(
x
x
)|
)|
•
f(x) là ω(g(x)) hoặc f có bậc cao hơn thật sự g nếu
∀
∀

)|
)|
Little-o
Giới thiệu
Độ tăng hàm
Big-O
Tính chất
Big-Theta
Tính chất
Little-o
Độ phức tạp
Xấu nhất
Trung bình
Tính đúng đắn
Điều kiện
Lặp
Ví dụ
Tóm tắt
12/35Tổ toán đại học FPT
05/03/14
Định lí Theorem
Định lí Theorem
Mối quan hệ về độ tăng của hàm được mô tả như sau

Mối quan hệ về độ tăng của hàm được mô tả như sau

Thuật toán BIG-
THETA Algorithm BIG-
THETA
Ω( f )

Định lí Theorem
Định lí Theorem
Cho f(x) và g(x) là hai hàm số từ tập các số nguyên
hoặc số thực đến tập các số thực. Khi đó
•
Nếu lim
x→∞
g(x)/f(x) = 0 thì g ∈ o(f).
•
Nếu lim
x→∞
g(x)/f(x) = ∞ thì g ∈ ω(f).
•
Nếu lim
x→∞
g(x)/f(x) = A khác 0 thì g ∈ Θ(f). Nếu A = 1
thì ta nói g(x) tiệm cận f(x).
Cho f(x) và g(x) là hai hàm số từ tập các số nguyên
hoặc số thực đến tập các số thực. Khi đó
•
Nếu lim
x→∞
g(x)/f(x) = 0 thì g ∈ o(f).
•
Nếu lim
x→∞
g(x)/f(x) = ∞ thì g ∈ ω(f).
•
Nếu lim
x→∞

như: phép so sánh, cộng, trừ, nhân, chia, …
•
Độ phức tạp không gian: dung lượng bộ nhớ cần sử
dụng để thực hiện thuật toán.
Độ phức tạp của thuật toán mô tả mức độ khó khăn khi
thực hiện thuật toán, gồm hai loại:
•
Độ phức tạp thời gian: thời gian cần thiết để thực hiện
được thuật toán với kích thước đầu vào xác định, được
biểu diễn qua số phép toán được dùng bởi thuật toán
như: phép so sánh, cộng, trừ, nhân, chia, …
•
Độ phức tạp không gian: dung lượng bộ nhớ cần sử
dụng để thực hiện thuật toán.
Khi có một thuật toán chúng ta sẽ quan tâm đến
•
Tính đúng đắn: kết quả chính xác không?
•
Độ phức tạp: thuật toán có hiệu quả không?
sẽ học hôm nay
Độ phức tạp
Giới thiệu
Độ tăng hàm
Big-O
Tính chất
Big-Theta
Tính chất
Little-o
Độ phức tạp
Xấu nhất

Big-O
Tính chất
Big-Theta
Tính chất
Little-o
Độ phức tạp
Xấu nhất
Trung bình
Tính đúng đắn
Điều kiện
Lặp
Ví dụ
Tóm tắt
16/35Tổ toán đại học FPT
05/03/14
Thuật toán ĐỘ PHỨC TẠP
Algorithm COMPLEXITY
Ví dụ Example
LN là giá trị lớn nhất
trong {a
1
, a
2
, …, a
n
}
i ≤ n
đúng
sai
LN: = a

Tính chất
Big-Theta
Tính chất
Little-o
Độ phức tạp
Xấu nhất
Trung bình
Tính đúng đắn
Điều kiện
Lặp
Ví dụ
Tóm tắt
17/35Tổ toán đại học FPT
05/03/14
Thuật toán ĐỘ PHỨC TẠP
Algorithm COMPLEXITY
Định nghĩa Definition
Định nghĩa Definition
Một thuật toán với kích thước đầu vào n gọi là có
•
độ phức tạp hằng nếu có dạng O(1)
•
độ phức tạp logarit nếu có dạng O(log n)
•
độ phức tạp tuyến tính nếu có dạng O(n)
•
độ phức tạp đa thức nếu có dạng O(n
a
), a ≥ 1
•

Big-Theta
Tính chất
Little-o
Độ phức tạp
Xấu nhất
Trung bình
Tính đúng đắn
Điều kiện
Lặp
Ví dụ
Tóm tắt
18/35Tổ toán đại học FPT
05/03/14
Thuật toán ĐỘ PHỨC TẠP
Algorithm COMPLEXITY
Định nghĩa Definition
Định nghĩa Definition
•
Độ phức tạp trong trường hợp xấu nhất là độ phức tạp
tính trong trường hợp phải dùng tối đa các phép toán để
giải bài toán theo thuật toán đang xét, ứng với một số đầu
vào nào đó có kích thước xác định.
•
Độ phức tạp trong trường hợp trung bình là độ phức tạp
tính số trung bình các phép toán để giải bài toán trên toàn
bộ các giá trị đầu vào có kích thước xác định.
•
Những bài toán giải được bằng một thuật toán có độ
phức tạp đa thức trong trường hợp xấu nhất gọi là bài
toán dễ dử lí, nếu không gọi là bài toán không dễ xử lí.

Tóm tắt
19/35Tổ toán đại học FPT
05/03/14
Thuật toán ĐỘ PHỨC TẠP
Algorithm COMPLEXITY
Ví dụ Example
Mô tả độ phức tạp thời gian của thuật toán tìm kiếm
tuyến tính sau, dựa trên số phép so sánh?
procedure TìmTT(x ∈ Z; a
1
, a
2
,…, a
n
∈ Z phân biệt)
i : = 1
while (i ≤ n and x ≠ a
i
)
if i ≤ n then vị trí: = i
i : = i + 1
else vị trí: = 0
Độ phức tạp
Giới thiệu
Độ tăng hàm
Big-O
Tính chất
Big-Theta
Tính chất
Little-o

vị trí: = 0
nếu x = a
i
có i vòng lặp
mỗi vòng lặp có 2 phép so
sánh i ≤ n và x ≠ a
i

Trường hợp x ≠ a
i
∀i có 2n + 1 + 1= 2n + 2 phép so sánh
nếu x ≠ a
i
∀i có n vòng lặp
và 1 phép so sánh để thoát
ra khỏi vòng lặp
một phép so sánh
ngoài vòng lặp
Trường hợp x = a
i
có 2i + 1 phép so sánh
Xấu nhất
Giới thiệu
Độ tăng hàm
Big-O
Tính chất
Big-Theta
Tính chất
Little-o
Độ phức tạp

Độ phức tạp
Xấu nhất
Trung bình
Tính đúng đắn
Điều kiện
Lặp
Ví dụ
Tóm tắt
22/35Tổ toán đại học FPT
05/03/14
Ví dụ Example
Xác định độ phức tạp của thuật toán tìm kiếm nhị phân
dựa trên số phép so sánh
Thuật toán ĐỘ PHỨC TẠP
Algorithm COMPLEXITY
procedure TìmNP(x ∈ Z; a
1
, a
2
,…, a
n
∈ Z tăng dần)
i : = 1
while (i < j)
if x = a
i
then vị trí: = i
begin
else vị trí: = 0
j : = n

, …, a
n
: nguyên tăng dần
i: = 1; j: = n
i < j
đúng
sai
vị trí: = i
x > a
m

j: = m
đúng
sai
vị trí: = 0
m: = (i + j)/2
i: = m + 1
x = a
i

đúng
sai
mỗi vòng lặp có 2 phép so
sánh i < j và x > a
m

sau mỗi vòng, kích thước danh
sách giảm đi cỡ một nửa
⇒ có không quá log
2

đắn của thuật toán gồm hai phần:
•
Chứng tỏ rằng nếu thuật toán kết thúc thì nó cho ra kết
quả đúng, tức là xác lập tính đúng đắn bộ phận.
•
Chứng tỏ thuật toán kết thúc.
Một thuật toán gọi là đúng đắn nếu với mọi đầu vào
khả dĩ, nó cho đầu ra đúng. Việc chứng minh tính đúng
đắn của thuật toán gồm hai phần:
•
Chứng tỏ rằng nếu thuật toán kết thúc thì nó cho ra kết
quả đúng, tức là xác lập tính đúng đắn bộ phận.
•
Chứng tỏ thuật toán kết thúc.
Tính đúng đắn
Giới thiệu
Độ tăng hàm
Big-O
Tính chất
Big-Theta
Tính chất
Little-o
Độ phức tạp
Xấu nhất
Trung bình
Tính đúng đắn
Điều kiện
Lặp
Ví dụ
Tóm tắt

ta nói chương trình S đúng đắn bộ phận với khẳng
định đầu p và khẳng định cuối q.
Tính đúng đắn