Giải thuật Kĩ thuật phân tích giải thuật

1.6.2.3.2 Hàm nhân
Một hàm f(n) được gọi là hàm nhân (multiplicative function) nếu f(m.n) = f(m).f(n)
với mọi số nguyên dương m và n.
k k
Ví dụ 1-13: Hàm f(n) = n là một hàm nhân, vì f(m.n) = (m.n) = m
k k
.n = f(m) f(n)
Tính nghiệm của phương trình tổng quát trong trường hợp d(n) là hàm nhân:
Nếu d(n) trong (I.1) là một hàm nhân thì theo tính chất của hàm nhân ta có
d(b
k-j
) = [d(b)]
k-j
và nghiệm riêng của (I.2) là
1 -
d(b)
a
1 -]
d(b)
a
[
k
(
‡”
1-k
0=j
j-kj
bda
)

k
, theo quy tắc
lấy độ phức tạp ta có nghiệm riêng là O(a
k log
) = O(n
b
a
). Như vậy nghiệm riêng và
nghiệm thuần nhất bằng nhau do đó T(n) là O(n
log
b
a
).
Trong trương hợp này ta thấy thời gian thực hiện chỉ phụ thuộc vào a, b mà không
phụ thuộc vào hàm tiến triển d(n). Vì vậy để cải tiến giải thuật ta cần giảm a hoặc
tăng b.
2 Trường hợp 2: a < d(b) thì trong công thức (I.3) ta có [d(b)]
k k
> a , theo quy tắc
lấy độ phức tạp ta cónghiệm riêng là O([d(b)]
k
) = O(n
log
b
d(b)
). Trong trường hợp này
nghiệm riêng lớn hơn nghiệm thuần nhất nên T(n) là O(n
log d(b)
).
b

n và a
k
= n
log
b
a
. Vậy nghiệm riêng là n
log
b
a
log
b
n và nghiệm
này lớn gấp log
b
n lần nghiệm thuần nhất. Do đó T(n) là O(n
log a
log n).
b b
Chú ý khi giải một phương trình đệ quy cụ thể, ta phải xem phương trình đó có
thuộc dạng phương trình tổng quát hay không. Nếu có thì phải xét xem hàm tiến
triển có phải là hàm nhân không. Nếu có thì ta xác định a, d(b) và dựa vào sự so
sánh giữa a và d(b) mà vận dụng một trong ba trường hợp nói trên.

Nguyễn Văn Linh Trang 14
Click to buy NOW!
P
D
F
-

o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-

Với phương trình thứ nhất, ta có d(n) = n => d(b) = b = 2 < a, áp dụng trường hợp 1
ta có T(n) = O(n
log
b
a log4
) = O(n ) = O(n
2
).
Với phương trình thứ hai, d(n) = n
2 2
=> d(b) = b = 4 = a, áp dụng trường hợp 3 ta có
T(n) = O(n
log
b
a log4 2
log
b
n) = O(n logn) = O(n logn).
3 3
=> d(b) = b
Với phương trình thứ 3, ta có d(n) = n
= 8 > a, áp dụng trường hợp 2,
ta có T(n) = O(n
log
b
d(b) log8 3
) = O(n ) = O(n ).
1.6.2.3.3 Các hàm tiến triển khác
Trong trường hợp hàm tiến triển không phải là một hàm nhân thì chúng ta không
thể áp dụng các công thức ứng với ba trường hợp nói trên mà chúng ta phải tính

‡”
)j-(k2k
‡”
1-k
0=j
2
)1+(
2
k
kk
k
= O(2 k
2
)
Theo giả thiết trong phương trình tổng quát thì n = b
k
nên k = log
b
n, ở đây do b = 2
nên 2
k
= n và k = logn, chúng ta có nghiệm riêng là O(nlog
2
n), nghiệm này lớn hơn
nghiệm thuần nhất do đó T(n) = O(nlog
2
n). Nguyễn Văn Linh Trang 15

a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.

7 Khi giải một phương trình đệ quy thuộc dạng phương trình tổng quát, nếu hàm
tiến triển d(n) là một hàm nhân thì vận dụng công thức nghiệm của môt trong ba
trường hợp để xác định nghiệm, còn nếu d(n) không phải là hàm nhân thì phải tính
trực tiếp nghiệm riêng và so sánh với nghiệm thuần nhất để chọn nghiệm.
BÀI TẬP CHƯƠNG 1
Bài 1: Tính thời gian thực hiện của các đoạn chương trình sau:
a) Tính tổng của các số
{1} Sum := 0;
{2} for i:=1 to n do begin
{3} readln(x);

{4} Sum := Sum + x;
end;
b) Tính tích hai ma trận vuông cấp n C = A*B:
{1} for i := 1 to n do
{2} for j := 1 to n do begin
{3} c[i,j] := 0;
{4} for k := 1 to n do
{5} c[i,j] := c[i,j] + a[i,k] * b[k,j];
end;
Bài 2: Giải các phương trình đệ quy sau với T(1) = 1 và
a) T(n) = 3T(n/2) + n
2
b) T(n) = 3T(n/2) + n

3
c) T(n) = 8T(n/2) + n

Bài 3: Giải các phương trình đệ quy sau với T(1) = 1 và
a) T(n) = 4T(n/3) + n

u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i
e
w
e
r

a) T(1) = 2 và T(n) = 2T(n-1) + 1 với n > 1
b) T(1) = 1 và T(n) = 2T(n-1) + n với n > 1
Bài 6: Cho một mảng n số nguyên được sắp thứ tự tăng. Viết hàm tìm một số
nguyên trong mảng đó theo phương pháp tìm kiếm nhị phân, nếu tìm thấy thì trả
về TRUE, ngược lại trả về FALSE.
Sử dụng hai kĩ thuật là đệ quy và vòng lặp. Với mỗi kĩ thuật hãy viết một hàm tìm
và tính thời gian thực hiện của hàm đó.
Bài 7: Tính thời gian thực hiện của giải thuật đệ quy giải bài toán Tháp Hà nội với n
tầng?
Bài 8: Xét công thức truy toán để tính số tổ hợp chập k của n như sau:
n<k<0nêu C+C
n=k hoac 0=knêu 1
=C
k
1-n
1-k
1-n
k
n

a) Viết một hàm đệ quy để tính số tổ hợp chập k của n.
b) Tính thời gian thực hiện của giải thuật nói trên.

Nguyễn Văn Linh Trang 17
Click to buy NOW!
P
D
F
-
X

m
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t

(Chapter 9).
Đinh Mạnh Tường. Cấu trúc dữ liệu & Thuật toán. Nhà xuất bản khoa học và kĩ
thuật. Hà nội-2001. (Chương 9).

Đỗ Xuân Lôi. Cấu trúc dữ liệu & Giải thuật. 1995. (Chương 9).
2.1.4 Nội dung cốt lõi
Trong chương này chúng ta sẽ nghiên cứu các vấn đề sau:
• Bài toán sắp xếp.
• Một số giải thuật sắp xếp đơn giản.
• QuickSort
• HeapSort
• BinSort
Nguyễn Văn Linh Trang
18
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i
e

n
g
e

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m