Bài giảng Phân tích và thiết kế thuật toán - Phạm Thế Bảo - Chương 2: Đánh giá bằng công cụ toán học cơ bản

27/03/2008
1
Á Á Ằ ÔĐ NH GI B NG C NG CỤ 
TOÁN HỌC CƠ BẢN
Phạm Thế Bảo
Khoa Toán – Tin học 
Trường Đại học Khoa học Tự nhiên Tp.HCM
Đánh giá bằng công cụ toán học sơ cấp
1. Phương pháp chung:
Phân tích trực tiếp đoạn mã và sử dụng các kỹ
h ật u t:
• Phép đếm
• Tính tổng hữu hạn
• Xét dấu hàm
• …
Phé t á hủ ế t á đ ã là hé
Xác định số phép toán chủ yếu
p o n c y u rong c c oạn m p p
gán và so sánh.
Phương pháp này không giải quyết được tất cả
các trường hợp.
Phạm Thế Bảo
27/03/2008
2
• Ví dụ 1:
s = 0
i = 1
while i≤n do
j i = n -
while j≥1 do
s = s + 1
j = j - 1 
endw
i = i + 1
endw
Khảo sát độ phức tạp trên số phép gán và so sánh
trong thuật toán.
Phạm Thế Bảo
s = 0
i = 1
while i≤n do
j = n - i
while j≥1 do
s = s + 1
? phép gán
? phép so sánh
? phép gán
P(i) ? phép gán
? phép so sánh
j = j - 1 
endw
i = i + 1
endw
? phép gán
? phép gán
n
iSoá pheùp gaùn = 2 + n+ Gaùn(P ) +n
⎡ ⎤⎢ ⎥⎣ ⎦∑
Phạm Thế Bảo
i=1
2 2( 1)2 2 2 2 ( )
2
n nn n n O n−= + + = + + =
27/03/2008
3
Số phép so sánh = ? (Bài tập 1)
• Ví dụ 2:
sum = 0
i = 1
while i≤n do
j = n‐i*i
while j ≤ i*i do
sum=sum + i*j
j=j+1
endw
i=i+1
Pi
Phạm Thế Bảo
endw
n
i
i=1
Soá pheùp gaùn = 2 + n+ Gaùn(P ) +n⎡ ⎤⎢ ⎥⎣ ⎦∑
1 1
2 2 ( 2 ) 2 2 2
n n
i i
i i
n nα α
= =
= + + = + +∑ ∑
Nếu thay dòng lệnh j=n-i*i bằng dòng lệnh j=1 thì αi = i2
Vòng lặp Pi chỉ thực hiện khi n-i2 ≤ i2 ⇔ i2 ≥ n/2
2 2
0
2
( ) 1
2
2
i
2
Töø ñaây suy ra :
 neáu i
 neáu i
n
ni n i
α
⎧ <⎪⎪= ⎨⎪ − − + ≥⎪⎩
Bài tập 2: Hãy viết chương trình
thử nghiệm để đếm số phép gán
và so sánh của đoạn chương trình
ví dụ 2, để kiểm tra lại lý thuyết.
Phạm Thế Bảo
2 2
2 2
(2 1) 2 ( 1)( 1)
2
n
i
i=1
Nhö vaäy:
n n
n ni i
ni n i n nα
⎡ ⎤ ⎡ ⎤= =⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥
⎡ ⎤= − + = − − + −⎢ ⎥⎢ ⎥∑ ∑ ∑
27/03/2008
4
• Ví dụ 3: Xét thuật toán tìm phần tử max của mảng một
chiều có n phần tử.
max = A[0]; 
i=1;
while i<n do Số phép so sánh = ?
Số phép gán = ?if max< A[i] then 
max = A[i];
endif
i=i+1;
endw
0
(
?
1
)
 toái thieåu khi A[0] laø max 
 toái ña khi A ñöôïc saép xeáp
 taêng 
hay max naèm ôû cuoái
Trung bình: duøng coâng cuï toaùn
n
nα
⎧⎪ −⎪= ⎨⎪⎪⎩
Phạm Thế Bảo
Độ phức tạp f(n) = a(2n-1) + b[n+1+ α(n)]
Thời gian cho 01 so sánh
Thời gian cho 01 phép gán
Ta có:
a(2n-1) + b(n+1) ≤ f(n) ≤ a(2n-1) + b(2n)
Tuyến tính Tuyến tính
Phạm Thế Bảo
f(n)∼O(n)
27/03/2008
5
Phân loại sơ bộ các đoạn mã
1. Những tính toán lặp
– Tùy tình huống
2. Các loại tính toán lặp
– Số lần lặp xác định tường minh: được thể hiện rõ
ràng trong đoạn mã. Có thể tính toán bằng một
công thức xác định.
Ví dụ: Tổng n số nguyên.
Số lần lặp không tường minh: biến sẽ ngẫu nhiên– 
phụ thuộc vào dữ liệu đầu vào và phân bố.
Ví dụ: Tìm số lớn nhất.
Phạm Thế Bảo
• Ví dụ 4: Xét đoạn mã.
i=1;
res=0;
while i≤n do
j=1;
k=1;
while j ≤ i do
res=res+i*j;
k=k+2;
j=j+k;
endw
i=i+1;
Pi
Phạm Thế Bảo
endw
27/03/2008
6
• Vòng lặp while ngòai cùng: số lần lặp 
tường minh: n lần .
• Vòng lặp while bên trong: số lần lặp 
không xác định. Cách giải quyết:
Gọi α là số lần lặp của vòng while này (quy– i 
ước tính độc lập).
– Việc xác định số phép gán, so sánh trong 
đoạn mã sẽ quy về tính theo αi
T thấ j là tổ ới á ố là 1 3 5
1
i 
n
i
α
=
∑
• a y ng v c c s , , , ... 
Nên là các số chính phương. 
– ⇒ αi là số phần tử của {r/ r≥1 & r2 ≤i}.
– ⇒ αi = 
Phạm Thế Bảo
i⎢ ⎥⎣ ⎦
• Ví dụ 5: Xét đoạn mã tương tự ví dụ 4.
i=1;
res=0;
s=0; // số thực
while i≤n do
j=1;
s=s+1/i;
while j ≤ s do
res=res+i*j;
j=j+1;
endw
i=i+1;
Pi
Phạm Thế Bảo
endw
Lúc này αi  = ⎣Hi⎦
1 1 11 ...
2 3 i
vôùi , H laø soá ñieàu hoøaiH i
= + + + +
27/03/2008
7
• Ví dụ 6: xét đoạn mã
Đoạn chương trình dừng khi nào?
i=0;
A[n]=x;
while A[i] ≠ x do
i=i+1;
endw
Đoạn chương trình dừng trong các trường hợp sau:
• i=n ⇔ x ≠ A[i], ∀i∈ {0,1, …, n‐1}
• i<n ⇔ ∃ i0 ∈ {0,1, …, n‐1} sao cho x=A[i0] và
x ≠ A[j], ∀j<i0
Vậy số lần lặp không xác định tường minh, 
nhưng lại tường minh cho một mảng dữ liệu cụ thể
Phạm Thế Bảo
3. Vấn đề rẽ nhánh:
– Rẽ nhánh tất định:
• Cân bằng cách nhánh
• Độ lệch các nhánh rẽ tính được
• Không phụ thuộc dữ liệu nhập
– Rẽ nhánh phụ thuộc phân bố dữ liệu:
• Phải tính toán theo xác suất phân bố của dữ liệu
Phạm Thế Bảo
27/03/2008
8
• Ví dụ 7: Tìm số lớn nhất trong mảng một
chiều.
i=1;
max=A[0];
A[n] ;=x
while i<n do
if max<A[i] then 
max=A[i];
endif
i=i+1;
endw
Phạm Thế Bảo
Biến αn là biến ngẫu nhiên lấy các giá trị
Rời rạc {0, 1, 2, ..., n-1}
• Ví dụ 8:
s=0;
i=1;
while i≤n do
j=1;
while j≤i2 do
s=s+i*j;
j=j+1;
endw
i=i+1;
Phạm Thế Bảo
endw
27/03/2008
9
s=0;
i=1;
while i≤n do
j=1;
while j≤i2 do
s=s+i*j;
j=j+1;
endw
i=i+1;
endw
Pi
2
1
1 ( 1)
n
so saùnh
i=1
soá pheùp so saùnh = n+1+ P(i)
( 1)(2 1)
n
i
n i
=
= + + +∑ ∑
Phạm Thế Bảo
n n+ n+ = 2n+1+
6 ∼ n3
?
n
so saùnh
i=1
soá pheùp gaùn = 2n+2+ P(i) =∑
• Ví dụ 9:
count=0;
i=n;
while i>0 do 
count=count + i%2;
i=i/2;
endw
So sánh = α +1
Gán = 2 +2α
Cầ ớ l
Phạm Thế Bảo
n ư c ượng α
2Coù (n) log nα ≈
27/03/2008
10
Ví dụ: có n=25 Æ số lần lặp?
= số chữ số trong biểu diễn nhị phân của n.
n=25=1x24 + 1x23 + 0x22 + 0x21 + 1x20
n=bk bk-1 ... b1 b0 với bi = {0,1}
α = k+1
Phạm Thế Bảo
• Ví dụ 10:
sum=0;
i=1;
while i≤n do
j=i;
while j>0 do
sum=sum + 1;
j=j/2;
endw
i=i + 1;
endw
Pi lặp 
n lần
1 ( ( ) 1) 2 1 ( )
n
So saùnh = n+1 + P
n n
n i n iα α= + + + = + +∑ ∑ ∑
Phạm Thế Bảo
1 1
i
i=1
i i= =
Xác định α(i)? Bài tập 3
Gán = ? Bài tập 4
27/03/2008
11
• Ví dụ 11:
max=A[0];
i=1;
count=0;
while i≤n do
if (max<A[i]) 
max =A[i];
else 
count=count +1;
endif
i = i+1;
endw
Pi lặp?
Phạm Thế Bảo
Gán = ? 
So sánh =? Bài tập 5
• Ví dụ 12:
i=1;
c_d =0;
c_a =0;
c z =0;
So sánh = ?
Gán = ?
_
while i≤n do
if (A[i]>0) 
c_d =c_d+1;
else 
if(A[i]<0)
c_a=c_a+1;
else
+1
Pi lặp?
Phạm Thế Bảo
c_z=c_z ;
endif
endif
i = i+1;
endw
27/03/2008
12
Nếu viết lại Pi ta có:
if(A[i]>0)
c_d=c_d+1;
else
if(A[i]<0)
c_a=c_a+1;
endif
if(A[i]==0)
c_z=c_z+1;
endif
endif
Gán =?
So sánh =?
Phạm Thế Bảo
Nếu viết lại Pi ta có:
if(A[i]>0)
c_d=c_d+1;
endif
if(A[i]<0)
c_a=c_a+1;
endif
if(A[i]==0)
c_z=c_z+1;
endif
Gán =?
So sánh =?
Phạm Thế Bảo
3 so sánh
1 gán
27/03/2008
13
• Ví dụ 13:
found = false;
i =1;
sum=0;
while i≤n do
if((!found)&&(A[i]==X))
idx_f=i;
found=true;
endif
sum=sum+A[i];
i=i+1;
endw
Phạm Thế Bảo
• Khi x ∈ {A[i] / i=1..n}
– Gán = 5 + 2n
– So sánh =2n + α +1
• Khi x ∉ {A[i] / i=1..n}
– Gán = 3 + 2n
– So sánh =3n +1
Phạm Thế Bảo
27/03/2008
14
• Ví dụ 14:
i =1;
count=0;
while i≤n do
x=2m‐i;
y=i‐m;
if (x>0)
if(y>0)
count=count+1;
endif
endif
i=i+1;
endw
Phạm Thế Bảo
• Nhận xét:
‰ x = x(i) =2m-i
‰ y = y(i) =i-m
‰ Số lần α = |{i / x(i)>0}| 
Số lần β = |{i / x(i)>0 và y(i)>0}|
i
x(i) + + + ‐
1 m 2m
0
Phạm Thế Bảo
y(i) ‐ ‐ + +0
27/03/2008
15
• Nếu n≥2m
– α = 2m-1
– β = m-1
– Gán = 2+3n+ β = 3n+m+1 ≤ 3n + +1 ≈ O(n)n 
– So sánh = 2n+ α+1=2n+2m ≤ 2n+n ≈ O(n)
• Nếu n<2m
– α = n
– β =
2
0 nếu n ≤m
ế
– So sánh = 2n+ 1+ α = 3n ≈ O(n)
– Gán = 3n+ β+2 = 
n-m n u m<n<2m
3n+2 nếu n ≤m
4n+2-m nếu m<n<2m
≈ O(n)
Phạm Thế Bảo
• Ví dụ 15: xét đoạn mã.
i=1;
count=0;
s=0;
while i ≤ n do
x=n-2*i;
y=n-3*i;
if x>0 then
j=1;
while j ≤x do
if y>0 then 
count=count+1;
s=s+i*j;
Phạm Thế Bảo
endif
j=j+1;
endw
endif
i=i+1;
endw
27/03/2008
16
Phạm Thế Bảo
Đánh giá bằng thực nghiệm
• Chèn thêm lệnh đếm trong đoạn mã
ể• Phát sinh dữ liệu đ thực thi đoạn mã
• Ghi xuống file (dạng văn bản)
• Dùng Excel vẽ đồ thị tính phương sai, độ lệch 
chuNn Æ ước lượng độ phức tạp.
Phạm Thế Bảo
27/03/2008
17
Ví dụ: Thuật toán tìm giá trị lớn nhất
max = A[0];
i=1;
while i<n do
if(max<A[i])
max=A[i];
endif
endw
1. Cài đặt hàm 
i t fi dM (i t i t []){n n ax n n, n a
...
}
Phạm Thế Bảo
2. Cài đặt đếm
int evaluateFindMax(int n, int a[], long &gan, long &sosanh){
int max=a[0];
int i=1;
gan=2;
sosanh=0;
while(i<n){
sosanh+=2;
if(max<a[i]){
max=a[i];
gan++;
}
i++;
gan++;
}
sosanh++;
return max;
}
Phạm Thế Bảo
27/03/2008
18
3. Phát sinh dữ liệu
void generateData(int n, int *a){
// dùng hàm random hay rank hoặc kết hợp nhiều // hàm, hay tự 
viết (sách)
}
4 Chạy thử nghiệm và ghi dữ liệu. 
#define N MAX 50
#define N LOOP 200
int a[N MAX];
void runData(char *name){
FILE *fp = fopen(name,”wt”);
if(fp==N ULL){
printf(“Can not open to write file!!!”);
return;
}
Phạm Thế Bảo
int n=1;
while(n<N LOOP){
long gan=0;
long sosanh=0;
generateData(N MAX,a);
evaluteFindMax(N MAX a gan sosanh);, , ,
fprintf(fp,”%d\t%e\t%e\n”,n,gan,sosanh);
n++;
}
fclose(fp);
}
Hay viết lại đoạn while theo cách tính trung bình cho NLOOP 
lần chạy cho mảng có số phần tử thay đổi từ 1 đến 
NMAX.
Phạm Thế Bảo
27/03/2008
19
while(n≤N MAX){
long gan, tgan=0;
long sosanh, tsosanh=0;
for (int i=0; i<N LOOP; i++){
gan=sosanh=0;
generateData(N MAX,a);
evaluteFindMax(N MAX,a,gan,sosanh);
tgan+=gan;
tsosanh+=sosanh;
}
double tbgan=(double)tgan/N LOOP;
double tbsosanh=(double)tsosanh/N LOOP;
fprintf(fp,”%d \t %f \t %f\n”,n,tbgan,tbsosanh);
n++;
}
Phạm Thế Bảo
Chú ý
• Phân biệt rõ ràng: phép gán, so sánh khóa, sao 
hé N ti á hc p m u n, so s n
– Ví dụ khi so sánh khóa là chuỗi k ký tự thì?
– Sao chép một record sinh viên?
– Phép hoán đổi 2 phần tử swap(a[i],a[j]):
• Chỉ là 2 số nguyên Æ 3 phép gán
• 2 phần tử bất kỳ?
Phạm Thế Bảo