1
Phân tích & Thiết kế Giải
thuật nâng cao
Advanced Algorithm Analysis and Design
PGS. TS. TRẦN CAO ĐỆ
Đại Học Cần Thơ
2014
Bài giảng cho Thạc sĩ Ngành
HTTT
2
Phần 1:
KT phân tích và thiết kế giải thuật
PGS. TS. TRẦN CAO ĐỆ
Đại Học Cần Thơ
2014
3
Chương 1:
KỸ THUẬT PHÂN TÍCH GIẢI THUẬT
PGS. TS. TRẦN CAO ĐỆ
Đại Học Cần Thơ
2014
4
Thuật toán

Giải thuật / Thuật toán (algorithm)
–
Xuất phát từ nhà toán học Arập Al-Khowarizmi (khoảng năm 825).
–
Giải thuật là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các
phép toán, hoặc hành động cần thực hiện để cho ta lời giải của bài toán.


thực hiện.

Tính khả thi: Các phép toán có mặt trong thuật toán phải đủ đơn giản, có thể thực hiện được trong
một lượng thời gian hữu hạn (có thể thực hiện bởi con người với giấy, bút trong một khoảng thời
gian hữu hạn).

Tính tổng quát: phải áp dụng được cho một lớp bài toán.
6
Vấn đề giải được & không giải được

Một bài toán:
–
Có một hoặc nhiều thuật toán giải.

Giải được  Lựa chọn thuật toán
–
Không tồn tại thuật toán để giải

gọi là vấn đề không giải được (bằng thuật toán).

Vd:
–
KHÔNG CÓ Thuật toán chắc thắng cho người thứ hai của
cờ ca rô.
–
KHÔNG CÓ Thuật toán xem một máy Turing có dừng lại
sau n bước hay không.
7
Vấn đề chứng minh thuật toán


có input chạy chậm
–
Không khả thi

Chỉ thực hiện được trên
một số input

Không chỉ ra được sự biến
thiên của thời gian theo độ
dài input

Tiếp cận 2: theo số phép toán
cơ bản mà chương trình phải
thực hiện
–
Phép toán cơ bản

Số phép +,-,*,/,=;

Số chỉ thị cơ bản của máy
tính)
–
Độc lập tốc độ máy
–
Vẫn phụ thuộc vào đặc tính
của input

Trường hợp xấu nhất

Trường hợp tốt nhất

f(n) ∈ Θ(g(n))

Kí hiệu O: tiệm cận trên
O(g(n)) = {f(n)/ ∃c,n
0
>0: ∀n>n
0
,
0 ≤ f(n) ≤ cg(n) }
Ta viết: f(n)= O(g(n)) thay cho
f(n) ∈ O(g(n))

Kí hiệu Ω: tiệm cận dưới
Ω (g(n)) = {f(n)/ ∃c,n
0
>0:
∀n>n
0
, 0 ≤ cg(n) ≤ f(n)}
Ta viết: f(n)= Ω (g(n)) thay cho
f(n) ∈ Ω (g(n))
10
Ví dụ

f(n)= 3n
3
+ 2n
2

f(n)= Θ(n

Hàm đa thức
P(n)=O(n
d
)

Hàm giai thừa
Xấp xỉ Stirling
log(n!) = Θ (nlogn)
13
Tính chất của các tiệm cận

Phản xạ
f(n) = Θ(f(n))
f(n) = Ω(f(n)
f(n) = O(f(n)

Đối xứng
f(n)= Θ(g(n)) ⇔ g(n)= Θ(f(n)

Bắc cầu
f(n) = Θ(g(n)) ∧ g(n) = Θ(h(n)) ⇒ f(n)= Θ(h(n))
f(n) = Ω(g(n)) ∧ g(n) = Ω(h(n)) ⇒ f(n)= Ω(h(n))
f(n) = O(g(n)) ∧ g(n) = O(h(n)) ⇒ f(n)= O(h(n))
14
Ký hiệu O() của f(x) Độ phức thời gian
O(1)
O(logn)
O(n)
O(nlogn)
O(n

a[i]:=random(1000);
For i:=1 to n-1 do
for j:=i+1 to n do
if (a[i]>a[j]) then
swap(a[i],a[j]);

Giải thuật đệ qui
–
Thiết lập công thức truy hồi
T(n) = aT(n/b) + c(n)
-
Giải công thức truy hồi
(phương trình đệ qui)

Ví dụ: tính độ phức tạp của
quicksort
–
T(1)=1
–
T(n)=2T(n/2)+n
–
Giải ra T(n)=O(nlogn)
Phương trình hồi quy

T(1)=1

T(n) = aT(n/b) + d(n), n>1

Phương pháp giải
–

n/2
i-1
+…+4n/2+n (bước i)
= 4
k
T(n/2
k
) + 4
k-1
n/2
k-1
+…+4n/2+n (bước k)
= 4
k
+ 4
k-1
n/2
k-1
+…+4n/2+n
= 4
k
+ n (2
k-1
+…2+1)= n
2
+ n(2
k
-1) = n
2
+ n(n-1)

riêng
Nếu d là hàm nhân, tức là d(m*n) = d(m)*d(n)
Thì ta có thể giải được nghiệm riêng dễ dàng
∑
j=0
k-1
a
j
d(b
k-j
) = d(b)
k
∑
j=0
k-1
(a/d(b))
j
= (a
k
-d(b)
k
)/(a/d(b)-1)

Lời giải với d(n) là hàm nhân

Nếu a>d(b): T(n)=O(n
log
b
a
)

Cho T(n) = a · T(n/b) +
f(n), với n nguyên dương,
a ≥ 0 và b > 1 là các hằng
số; f(n) là hàm tiệm cận
không âm của n

Lời giải

Nếu f(n) = O(n
log
b
a− ε
) , với
ε là hằng số dương thì T(n)
= Θ(n
log
b
a
).

f(n) = Θ(n
log
b
a
log
k
n), với
k≥0 thì T(n) =
Θ(n
log

 T(n) = Θ(n
2
).

T(n) = 4T(n/2) + n
2
–
a =4, b= 2 n⇒
log
b
a
=n
2
; f(n) = n
2
.
–
f(n) = Θ(n
2
lg
0
n), tức là k = 0.
T(n) = Θ(n
2
lgn).
22
Ví dụ

T(n) = 4T(n/2) + n
3

a
=n
2
;
–
f(n) = n
2
/lgn.
Lời giải tổng quát không thể áp dụng vì sao?
Với mọi ε> 0, n
ε
>

lgn !
23
Tài liệu tham khảo

R. Sedgewick, Algorithms in Java, Addision-Wesley, 2004.
Chapter 1.

Aho, A. V. , J. E. Hopcroft, J. D. Ullman. Data Structure and
Algorihtms, 1983.

Kenneth H. Rosen, Discrete Mathematics and its applications,
4
th
edition, McGraw-Hill, 2000.

R. Sedgewick, Algorithms , 1987.
24