ĐẠI HỌC SƯ PHẠM HÀ NỘI

NGUYỄN CHÍ TRUNG
NGUYỄN THỊ THU THỦY
PHÂN TÍCH THIẾT KẾ THUẬT TOÁN VÀ
ĐÁNH GIÁ ĐỘ PHỨC TẠP GIẢI THUẬT
HÀ NỘI 2010
Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 2
MỤC LỤC
TÀI LIỆU THAM KHẢO 4
Chương 1. CÁC KHÁI NIỆM CƠ BẢN 5
1. Thuật toán (giải thuật, thuật giải) 5
1.1. Định nghĩa 5
1.2. Các đặc trưng của thuật toán 5
2. Phân tích thuật toán 5
2.1. Tại sao phải phân tích thuật toán 10
2.2. Thời gian thực hiện thuật toán 11
2.3. Khái niệm độ ph1độ phức tạp thuật toán 15
3.1. Qui tắc hằng số 15
3.2. Qui tắc cộng 16
3.3. Qui tắc lấy max 16
3.4. Qui tắc nhân 17
3. Các kỹ thuật đánh giá độ phức tạp thuật toán 17
3.1. Câu lệnh đơn 17
3.2. Câu lệnh hợp thành 17
3.3. Câu lệnh lặp với số lần lặp biết trước for-do 18
3.4. Câu lệnh rẽ nhánh if 19


3
3.2. Trở lại bài toán mảng con trọng số lớn nhất 51
3.3. Xâu con chung dài nhất 52
3.4. Bài toán cái túi 55
3.5. Nhân ma trận 57
BÀI TẬP CHƯƠNG 3 62
Chương 4. THUẬT TOÁN THAM LAM 64
1. Giới thiệu thuật toán tham lam 64
1.1. Đặc điểm của thuật toán tham lam 64
1.2. Sơ đồ chung của thuật toán tham lam 65
1.3. Chứng minh thuật toán đúng 65
2. Một số ví dụ minh họa 66
2.1. Bài toán tập các đoạn thẳng không giao nhau 66
2.2. Tìm hiểu các thuật toán tham lam đối với bài toán cái túi 69
2.3. Bài toán người du lịch (TSP - Travelling Salesman Problem) 70
2.4. Bài toán mã hóa Huffman 71
BÀI TẬP CHƯƠNG 4 75
Chương 5. CÁC THUẬT TOÁN ĐỒ THỊ CƠ BẢN 77
1. Các khái niệm cơ bản 77
1.1. Đồ thị 77
1.2. Các khái niệm 77
2. Các phương pháp biểu diễn đồ thị 78
1.1. Biểu diễn đồ thị bằng ma trận kề 78
1.2. Biểu diễn đồ thị bằng danh sách cạnh 78
1.3. Biểu diễn đồ thị bằng danh sách kề 79
1.4. Biểu diễn đồ thị bằng danh sách liên thuộc 81
3. Thuật toán tìm kiếm theo chiều rộng 81
3.1. Nguyên tắc tô màu 81
2.2. Breadth – First Tree 81

Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 5
Chương 1. CÁC KHÁI NIỆM CƠ BẢN
1. Thuật toán (giải thuật, thuật giải)
1.1. Định nghĩa
Một thuật toán là một danh sách từng bước các chỉ dẫn để giải quyết cho một bài toán cụ thể.
1

Ở góc độ lập trình, thuật toán còn được gọi là thuật giải hay giải thuật, là một danh sách các
thao tác (câu lệnh) theo đó máy tính thực hiện để sau một số hữu hạn bước, từ input là dữ liệu
vào của bài toán, sẽ thu được output là dữ liệu ra cần tìm của bài toán.
1.2. Các tính chất cơ bản của thuật toán
1.2.1. Tính dừng
Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác.
Ví dụ: thuật toán sau đây vi phạm tính dừng
Bước 1: S Å 0; i Å 0;
Bước 2: i Å i + 1;
Bước 3: S Å S + i*i;
Bước 4: Quay về bước 2;
Bước 5: Đưa ra S và kết thúc thuật toán
Thuật toán được sửa lại để nó có tính dừng (trở thành thuật toán tính tổng các bình phương của n
số tự nhiên đầu tiên) như sau:
Bước 1: Nhập N;
Bước 2: S Å 0; i Å 0;
Bước 3: Nếu i ≥ N thì chuyển đến Bước 7;
Bước 4: i Å i + 1;
Bước 5: S Å S + i*i;
Bước 6: Quay về bước 3;

Bước 3: S Å (1/3)π.a.b
2
Bước 4: Đưa ra S và kết thúc thuật toán;
Ví dụ khác: thuật toán ”Tìm số hạng Fibonacci thứ N” dưới đây vi phạm tính xác định
Bước 1: Nhập số dương N
Bước 2: Nếu N ≤ 2 thì c Å 1, kết thúc thuật toán
Bước 3: a Å 1; b Å 1; k Å 2;
Bước 4: Nếu k = N thì đưa ra c và kết thúc thuật toán,
Bước 5: k Å k + 1; Thực hiện bước 6 hoặc bước 7 sau đây:
Bước 6: c Å
a + b; a Å b; b Å c; Quay về bước 4;
Bước 7: c Å a + b;
Bước 8: a Å b; b Å c; Quay về bước 4;
Sửa lại:
Bước 1: Nhập số dương N
Bước 2: Nếu N ≤ 2 thì c Å 1, đưa ra c và kết thúc thuật toán
Bước 3: a Å 1; b Å 1; k Å 2;
Bước 4: Nếu k = N thì đưa ra c và kết thúc thuật toán,
Bước 5: k Å k + 1;
Bước 6: c Å a + b; a Å b; b Å c; Quay về bướ
c 4;
1.2.3. Tính đúng đắn
Một thuật toán phải đảm bảo cho ra Output luôn đúng đối với mọi dữ liệu vào của Input.
Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 7
Ta định nghĩa một bộ dữ liệu vào đầy đủ là nó bao phủ hết (cover all the cases) tất cả các trường
hợp cần xem xét.
Ví dụ, để giải phương trình bậc 2: ax

Ví dụ thay vì xây dựng thuật toán và viết chương trình giải các phương trình:
1) 5x
2
+ 12x - 1 = 0
2) 2x
2
-6x +2 = 0
3) 7x + 100 = 0
4) -50x
2
+112x - 11 = 0
Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 8
Người ta tiến hành xây dựng thuật toán và viết chương trình giải phương trình:
ax
2
+ bx + c = 0 với mọi số thực a, b, c cho trước.
1.3. Các tính quan trọng của thuật toán
Các tính chất này liên quan đến việc nhấn mạnh ưu điểm của "thuật toán tin học" là có thể giao
cho máy tính thực hiện. Một "thuật toán toán học" thuần túy có thể “rất đẹp” nhưng chưa chắc
đã cài đặt dễ dàng trên máy tính, và nếu cài đặt được thì thuật toán đó chưa chắc ổn định và khả
thi. Nói ở góc
độ tương tự, hai tính chất sau đây thể hiện sự khác biệt giữa toán lí thuyết và toán
tính.
- Toán lí thuyết quan tâm đến các vấn đề định tính của bài toán: tồn tại, duy nhất, tính chất
nghiệm của các bài toán.
- Toán tính quan tâm đến xây dựng phương pháp, thuật toán để để tìm nghiệm bài toán trên máy
tính.

thời gian để thực hiện khối lượng tính toán trên là giờ = năm. Một thời
gian lớn vô cùng! Và như vậy, thuật toán dựa vào công thức Cramer là hoàn toàn không khả thi
cho dù máy tính có tăng tốc độ lên gấp hàng nghìn, hàng vạn lần.
20
10*7073.9≈Q
9
10*2.6965
5
10*0782.3
Ở trên ta mới chỉ xét việc giải một hệ cỡ 20, mà thực tế khoa học và công nghệ đòi hỏi phải giải
các hệ phương trình đại số tuyến tính cỡ hàng vạn, hàng triệu hoặc hơn thế nữa. Vì thế, cần phải
Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 9
nghiên cứu đề xuất các phương pháp hiệu quả để có thể giải được các hệ thống phương trình cỡ
lớn.
1.3.2. Tính ổn định
Một thuật toán gọi là ổn định nếu sai số tính toán (do máy tính làm tròn số) không bị khuếch đại
trong quá trình tính.
Ví dụ (tính ổn định). Giả sử cần tính tích phân
)1(
1
1
0
≥=
−
∫
ndxexI
xn

)1(
1
0
11
1
0
1
≈=−==
−−
∫
e
xedxexI
xx

Như vậy, để tính
ta thu được công thức truy hồi tính được In về mặt lý thuyết:
n
I
.3679.0
,2,1
1
1
=
≥−=
−
I
nnII
nn

Về mặt thực tế tính trên máy tính không cho kết quả mong muốn khi n lớn. Cụ thể là tính trên

Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 10
Hiện tượng kết quả tính toán nêu trên là sự không ổn định của thuật toán: sai số ban đầu khi
tính
n
I
3679.0
1
1
≈=
e
I
đã bị khuyếch đại trong quá trình tính. Cụ thể như sau: Thay vì tính chính
xác
e
I
1
1
=
ta tính xấp xỉ của nó là
δ
+=
11
~
II , trong đó
δ
là sai số. Giả sử các tính toán tiếp theo
không mắc phải sai số. Với n = 2 ta được

δ
có bé thì khi n đủ lớn, sai số vẫn
đủ lớn và ta không thể nhận được giá trị chấp nhận được là gần đúng cho
.
n
I
2. Phân tích thuật toán
2.1. Tại sao phải phân tích thuật toán
Xét một thuật toán nhân 2 số phức
z
1
= a + bi; z
2
= c + di
z = z
1
* z
2
= (ac – bd) + (ad + bc)i
Khi tiến hành thuật toán: máy tính thực hiện 4 phép nhân và 3 phép cộng (ở đây là phép cộng đại
số, nghĩa là phép trừ được xem là cộng với số âm).
Giả sử phép nhân thực hiện mất 1 giây, phép cộng thực hiện mất 0.01 giây, phép gán thực hiện
mất 0.005 giây. Khi đó phép nhân hai số phức trên thực hiện mất 4*1 + 3*0.01 + 0.005 = 4.035
giây. Để giảm thời gian tính toán, ta có thể giảm phép nhân nhờ các tính toán sau đây:
ac - bd và ad + bc = (a + b)*(c + d) - ac - bd
Do đó nếu đặt p := ac; q := bd; Thì z := (p - q) + ((a +b)*(c+d) - p - q)i
Khi đó việc tính z g
ồm 3 phép nhân, 6 phép cộng và 3 phép gán; mất khoảng thời gian là 3*1 +
6*0.01 + 3*0.005 = 3.075 giây, giảm được 4.04 - 3.09 = 0.96 giây.
Ví dụ trên cho thấy một bài toán có thể tồn tại nhiều thuật toán để giải, do đó cần lựa chọn thuật

1.
Lời gọi thủ tục như read, write, và lời gọi hàm như sqr, sqrt,
2.
Câu lệnh gán
3.
Phép tính số học (+, -, *, /)
4.
Phép toán logic và phép toán so sánh
Chú ý: Ở đây ta không xem xét thời gian thực hiện đối với các câu lệnh điều khiển (rẽ nhánh if-
then, case-of, lặp for-do, while-do, và repeat-until) vì chúng không được xem là các phép tính cơ
bản. Việc bỏ qua các câu lệnh điều khiển mặc dù không cho kết quả chính xác về thời gian tính
(khác nhau một cơ số lần giá trị của n, với n là kích thước dữ liệu vào), nhưng thường không ảnh
hưởng đến độ phức tạp cần đánh giá. Vài trườ
ng hợp, câu lệnh rẽ nhánh khi kiểm tra điều kiện
được quan tâm và thời gian của việc kiểm tra điều kiện này được tính là một hằng số nào đó.
Một cách tổng quát, nếu mục đích là tính thời gian thực hiện thuật toán thì nên xem xét đầy đủ cả
các câu lệnh điều khiển, nếu mục đích là đánh giá độ phức tạp thuật toán thì có thể bỏ qua các
câu lệnh điề
u khiển.
Ví dụ 1.1 Tính trung bình cộng của n số nhập từ bàn phím
Số lần thực hiện
1. write(‘n = ‘); 1
2. readln(n); 1
3. T := 0; 1
for i := 1 to n do begin
Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 12
4. write(‘x = ‘); n

then
3. found := true;
else
4. i := i + 1;
if found then
5. writeln(‘vi tri ‘,i)
else
6. writeln(‘khong tim thay’);

1 lần
Phân tích và đánh giá: Mỗi câu lệnh 1, 2 luôn thực hiện 1 lần. Một trong hai lệnh 5 hoặc 6 thực
hiện một lần. Vậy thời gian thực hiện thuật toán luôn có dạng T(n) = 3 + k, trong đó k là số lần
thực hiện các câu lệnh 3 và 4. Khi đó ta có thể tạm thời không cần xem xét các câu lệnh 1, 2, 5, 6
nữa mà chỉ cần xem xét các câu lệnh 3 và 4.
Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 13
Thời gian tính tốt nhất khi x = a
1
: Câu lệnh 3 thực hiện một lần, câu lệnh 4 thực hiện không lần,
do đó k = 1 và :
T(n) = 3 + 1
Thời gian tính tồi nhất xảy ra khi không có x trong dãy (không tìm thấy). Câu lệnh 3 thực hiện
không lần, câu lệnh 4 thực hiện n lần. Do đó k = n và
T(n) = 3 + n
Thời gian tính trung bình được tính như sau:
Nếu x = a
1
: T(n) = 3 + 1 (lệnh 3 một lần; lệnh 4 không lần)

n
nn
n
n
nn
n
nT

Phân tích thuật toán theo nghĩa hẹp ở đây là xác định T(n) trong trường hợp xấu nhất. Phân tích
thuật toán theo nghĩa rộng là việc lựa chọn thuật toán tốt: tốn ít bộ nhớ, và có thời gian tính
trong trường hợp xấu nhất là chấp nhận được (tức là thỏa mãn tính khả thi).
Một số vấn đề đặt ra: Khi phân tích thuật toán, người ta ít khi quan tâm đến tính chính xác của
hàm thời gian tính mà thường quan tâm đến độ tăng của hàm này.
Ví dụ 1.3 Đánh giá hàm thời gian khi n tăng
Xét hàm thời gian T(n) = 60n
2
+ 9n + 19. Khi n tăng rất lớn thì T(n) ≈ 60n
2
Giả sử T(n) được tính bằng giây, khi đó hàm T(n) trên đây tính bằng phút có dạng:
T = n
2
+ 0,15n + 0,316.
Khi n tăng rất lớn thì T(n) ≈ n
2
.
Khi đó ta nói rằng T(n) có thời gian tính tương đương với hàm n
2
, hay T(n) là VCL (vô cùng
lớn) cùng bậc với n
2

n
C
ng
nf
1
)(
)(
lim

•
Ta viết f(n) =
Ω
(g(n)) và nói f(n) có bậc ít nhất là g(n) nếu tồn tại hằng số dương C
2
và
số nguyên dương N
2
sao cho
f(n) ≥ C
2
.g(n) với
∀
n ≥ N
2
Theo cách viết giới hạn, điều này nghĩa là:
∞=
∞→
)(
)(
lim

2
+ 9n + 1 ≤ 60n
2
+ 9n
2
+ n
2
= 70n
2
với ∀ n ≥ 1
Chọn C
1
= 70, g(n) = n
2
, N
1
= 1 Æ T(n) ≤ C
1
.g(n) hay T(n) = O(n
2
)
2) Tính Ω(.)
Ta có 60n
2
≤ 60n
2
+ 9n + 1 với ∀ n ≥ 1
Chọn C
2
= 60 , N

3
) bậc 3
7 O(n
k
) đa thức
Chấp nhận được
8 O(a
n
) hàm mũ
9 O(n!) giai thừa
Không chấp
nhận được
Ví dụ 1.5 Dùng kí hiệu
θ
đánh giá tốc độ tăng của hàm
a)

222
)1(
)(
2
nnnn
nf +=
+
=

Chọn C

2
.g(n) Æ f(n) = Ω(n
2
)
Do đó f(n) = θ(n
2
).
b)
1
2
1
1
1
)(
2
+
+−=
+
+
=
n
n
n
n
nf

Ta có
1
1
2

Nếu một thuật toán T có thời gian thực hiện T(n) = O(C.f(n)) với C là hằng số dương thì có thể
coi thuật toán T có độ phức tạp tính toán là O(f(n)).
Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 16
Chứng minh: Vì T(n) = O(C.f(n)) nên tồn tại số dương C
1
và số nguyên N
1
sao cho T(n) ≤
C.C
1
.f(n) với ∀ n ≥ N
1
. Khi đó chọn C
2
= C.C
1
thì T(n) ≤ C
2
.f(n) với ∀ n ≥ N
1
, hay T(n) =
O(f(n)).
3.2. Qui tắc cộng
Giả sử một thuật toán T gồm hai phần liên tiếp T
1
và T
2

= O(g(n)) nên tồn tại hằng số dương C
2
và số nguyên N
2
sao cho
T
2
(n) ≤ C
2
.g(n) với ∀ n ≥ N
2
. Chọn C
0
= max(C
1
, C
2
) và N
0
= max(N
1
, N
2
) thì với ∀ n ≥ N
0
ta
có: T(n) = T
1
(n) + T
2

.max(f(n), g(n)). Do đó T(n) =
O(max(f(n), g(n))).
Chú ý: Qui tắc max rất hay được sử dụng. Với qui tắc này:
•
Nếu T(n) là một đa thức thì có thể khẳng định các toán hạng bậc thấp là không quan
trọng, có thể bỏ qua khi đánh giá độ phức tạp thuật toán.
•
Trong một đoạn chương trình, câu lệnh được thực hiện nhiều nhất (được gọi là câu lệnh
đặc trưng
) sẽ được sử dụng để đánh giá độ phức tạp thuật toán của đoạn chương trình đó,
mà không cần quan tâm đến các câu lệnh khác (điều này không đúng nếu tính thời gian
thực hiện thuật toán cho toàn bộ đoạn chương trình). Câu lệnh đặc trưng thường là câu
lệnh đơn nằm trong một vòng lặp ở mức sâu nhất. Việc đánh giá độ phức tạp thuật toán
s
ử dụng câu lệnh đặc trưng sẽ được dùng đến từ phần áp dụng của chương 3, hiện tại
không dùng đến để rèn luyện việc phân tích thuật toán.
Ví dụ 1.6. Minh họa qui tắc max
a)
T(n) = 3n + 4 (Trong Ví dụ 1.1). Ta có T(n) = 3n + 4n
0
Æ T(n) = O(n).
Vậy thuật toán tính giá trị trung bình có độ phức tạp tuyến tính.
b)
)1(2
69
)(
2
+
++
=

nT

)()( nOnT =→

Vậy thuật toán tìm kiếm tuần tự có độ phức tạp tuyến tính.
c) T(n) = 60n
2
+ 9n + 9 (Trong Ví dụ 1.3). Ta có T(n) = O(n
2
)
Vì chọn N
0
= 9 và C
0
= 70 thì với ∀ n ≥ N
0
ta có 60n
2
+ 9n + 9 ≤ 60n
2
+ 9n
2
+ n
2
= 70n
2
. Do đó
T(n) ≤ C
0
.n

0
= max(N
k
, N
r
) và C
0
= C
k
.C
r
thì với ∀ n ≥ N
0
ta có: k(n).T(n) ≤ C
0
.f(n).g(n) hay
độ phức tạp tính toán của quá trình lặp là T(n) = O(f(n).g(n)).
4. Các kỹ thuật đánh giá độ phức tạp thuật toán
4.1. Câu lệnh đơn
Câu lệnh đơn là câu lệnh thực hiện một thao tác, ví dụ câu lệnh gán đơn giản (không chứa lời gọi
hàm trong biểu thức), câu lệnh vào/ra đơn giản, câu lệnh chuyển điều khiển đơn giản như break,
goto, continue, return.
Thời gian thực hiện một câu lệnh đơn không phụ thuộc vào kích thước dữ liệu nên sẽ là O(1).
Nói cách khác, các câu lệnh đơn có thời gian tính bị chặn bởi hàm số O(1) (hay O(c)). Ví dụ mỗi
câu lệ
nh sau đều có thời gian thực hiện là O(1): readln; writeln; readln(x); writeln(k);
4.2. Câu lệnh hợp thành
Thời gian thực hiện một câu lệnh hợp thành sẽ được tính theo qui tắc cộng và qui tắc max.
Ví dụ 1.7 Minh họa qui tắc cộng
if n > 1 then begin

là:
tnnT .)( =

Ví dụ 1.9. Đánh giá thời gian tính của vòng lặp khi P(i) là hằng số
for i := 1 to n do begin
1. write(‘x = ‘);
2. readln(x);
3. S := S + x;
end;
⎪
⎪
⎭
⎪
⎪
⎬
⎫
P(i)
T(P(i)) = 3. Do đó T(n) = n.3 Æ T(n) = O(n)
Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 19
Trường hợp 2: Thời gian thực hiện của P(i) phụ thuộc vào i, nghĩa là T(P(i)) = t(i). Khi đó thời
gian thực hiện câu lệnh lặp “for i” với i lần lượt nhận giá trị từ 1 đến n là T(n) = t(1) + t(2) + …
+ t(n), hay ta có:
∑
=
=
n
i

nOnT
nn
nn
nininT
ii
P
T
n
i
n
i
=→
+=
+
+=+=+=→
+=
∑∑
==

3.4. Câu lệnh rẽ nhánh if
Giả sử thời gian thực hiện hai câu lệnh thành phần của câu lệnh if dạng đủ là f(n) và g(n). Khi đó
thời gian thực hiện câu lệnh if sẽ được tính theo qui tắc max, tức là sẽ bằng
O(max(f(n), g(n)).
Thời gian kiểm tra điều kiện thường là hằng số, tức là O(1).
Ví dụ 1.11. Minh họa thời gian tính của câu lệnh rẽ nhánh
if n < 1 then
1. writeln(‘hay nhap so nguyen duong’) 1 lần
else
for i :=1 to n do
2. write(i : 5);

P(i)
gồm 4
câu lệnh
cơ bản
end;
Phân tích, đánh giá: P(i) gồm 4 câu lệnh cơ bản 3, 4, 5, và 6
-
i = n/2
0
Æ P(i) thực hiện lần thứ nhất
-
i = n/2
1
Æ P(i) thựchiện lần thứ hai
-
i = n/2
2
Æ P(i) thựchiện lần thứ ba
-
…
-
i = n/2
k-1
Æ P(i) thực hiện lần thứ k
Nếu đây là lần thực hiện cuối cùng thì n/2
k-1
= 1 Ù n = 2
k-1
Ù k = log
2
21
2. S := 0; l lần
while i > 0 do begin
3. for j := 1 to i do
4. write(j:5);
5. writeln;
6. i := i div 2;

)(iP
⎪
⎭
⎪
⎬
⎫
end;
Phân tích, đánh giá: P(i) gồm hai câu lệnh cơ bản 5 và 6, và một câu lệnh cơ bản 4 thực hiện i
lần.
-
Lần 1: i = n/2
0
Æ thực hiện n + 2 câu lệnh cơ bản
-
Lần 2: i = n/2
1
Æ thực hiện n/2 + 2 câu lệnh cơ bản
-
Lần 3 i = n/2
2

2log22
)
2
1

2
1
2
1
1(22)(
−
−
−++=
−
−
+++=
++++++=
k
k
k
n
nn
nn
nknT

Do đó T(n) ≤ 2n + 2log
2
n + 4 ≤ 2n + 2n + 4n = 8n (vì khi n tăng thì log
2
n ≤ log

3. p := p * x/i;
4. s := s + p;
⎭
⎬
⎫
P(i)
end;
b) T(n) = 2 + 2*n Æ T(n) = O(n)
Bài toán 1.2 Thuật toán tìm kiếm tuần tự
Cho dãy gồm n phần tử a
1
, a
2
, , a
n
. Hãy đưa ra vị trí của phần tử đầu tiên bằng phần tử đứng
ngay trước đó trong dãy.
a) Thiết kế giải thuật
b) Đánh giá độ phức tạp
Giải
Ví dụ 6, 7, 3, 4, 9, 8, 1, 5, 2, 5, 4, 3 Đáp số là vị trí 7
a)
1, 2 i := 2; found := false; 1 lần
while (i<=n) and not found do
3. if a[i] = a[i-1] then found := true
4. else i := i + 1;
⎭
⎬
⎫
P(i)

⎭
⎪
⎪
⎬
⎫
P(i)
end;
8. if found then write(‘Tim thay o vi tri ‘, k)
9. else write(‘khong co x trong day’);
1 lần

Trong trường hợp xấu nhất, không có x trong dãy, ta cần tính số lần thực hiện khối lệnh P(i)
trong thân vòng lặp, gồm 2 lệnh cơ bản. Vì mỗi lần đi qua vòng lặp độ dài của dãy giảm đi một
nửa, nên sau vòng lặp thứ k độ dài của dãy còn là n/2
k
.
Vòng lặp kết thúc tại lần thứ k mà độ dài
còn lại của dãy là n/2
k

= 1 hay k = log
2
n. Khi đó:
T(n) = 4 + 2k = 4 + 2log
2
n ≤ log
2
n + 2log
2
n với ∀ n ≥ N

P(i)
if (k<>i) then begin
5. a[k] := a[i]; n-1 lần
6. a[i] := min; end; end;
n-1 lần

Xét thuật toán trong trường hợp tồi nhất: dãy (a) đã được sắp xếp không tăng. Ta cần đánh giá
được số lần thực hiện hai câu lệnh cơ bản 3 và 4, do đó tính được thời gian P(i) để thực hiện các
câu lệnh for j phụ thuộc vào i.
Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 24
- i = 1: hai câu lệnh 3 và 4 thực hiện n - 1 lần
-
i = 2: hai câu lệnh 3 và 4 thực hiện n - 2 lần
-
…
-
i = n-1: hai câu lệnh 3 và 4 thực hiện n- (n-1) = 1 lần
Vậy T(P(i)) = 1 + 2 + … + (n-2) + (n-1) = n(n-1)/2 (ta đặt bằng p)
Do đó T(n) = 4(n-1) + n(n-1)/2 = (1/2)n
2
+ (7/2)n - 4.
Vậy T(n) = O(n
2
).
Thuật toán sắp xếp chọn trực tiếp cải tiến (tối ưu hơn)
for i :=1 to n-1 do begin
(* chọn phần tử nhỏ nhất trong dãy a[i] đến a[n]*)

t toán đệ qui.
Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 25
Ví dụ về hình ảnh đệ qui: giả sử cần xác định một cái túi: Cần lấy một cái túi mà nó đựng trong
một cái túi thứ hai mà cái túi thứ hai này là một cái túi mà nó đựng trong một cái túi thứ ba, cái
túi thứ ba là một cái túi mà nó đựng trong cái túi thứ tư, Tuy nhiên quá trình các cái túi chứa
trong nhau ấy không thể vô hạn, đến một cái túi thứ n hữu hạn nào đó thì nó không đựng trong
một cái túi nào nữa. Cái túi thứ n này gọi là cái túi “neo”, các cái túi còn lại gọi là các cái túi
được xác định một cách đệ qui.
Trong toán học, ta gặ
p rất nhiều định nghĩa đệ qui mà thường là các công thức để tính giá trị cho
một hàm số nào đó có thể tính được bằng qui nạp toán học (hay công thức truy hồi).
Ví dụ 1.15 Định nghĩa đệ qui hàm tính n!
Ta có thể định nghĩa f(n) = n! như sau:
⎩
⎨
⎧
>−
=
=
0)1(.
01
)(
nifnfn
nif
nf
Như vậy bài toán T tính f(n) được giải dựa vào bài toán T’ tính f(n-1) có dạng giống như T. Bài
toán T’ tính f(n-1) lại được giải dựa vào bài toán T” tính f(n-2) có dạng giống như T’ (hoặc như