Bài giảng Phân tích và thiết kế thuật toán - Phạm Thế Bảo - Chương 6: Đánh giá một số thuật toán thông dụng

28/03/2008
1
Á Á ỐĐ NH GI MỘT S 
THUẬT TOÁN THÔNG DỤNG
Phạm Thế Bảo
Khoa Toán – Tin học 
Trường Đại học Khoa học Tự nhiên Tp.HCM
Tìm kiếm tuần tự
• Xét một mảng các phần tử a[1], a[2], …, a[n]. Phần tử
a[i] có khóa tìm kiếm là a[i].key, bài toán: cho trước
khóa k, có tồn tại j để a[j].key bằng k hay không?
i=1;
found=false;
while((i≤n)&&(not found)) do
if(a[i].key bằng k) then
found=true;
ế
else
i=i+1;
endif
endw
Phạm Thế Bảo
N u bỏ else:
1. Thuật toán còn đúng không?
2. Có tăng phép đếm (gán)?
28/03/2008
2
• Ta cần phân biệt:
™ Phép toán số học: so sánh, gán
™ Phép toán trên khóa: sao chép, so sánh
• Nếu ta thêm một phần tử a[n+1].key=k thì số
phép toán sẽ tăng hay giảm?
• Viết lại thuật toán:
i=1;
a[n+1].key=k;
while (a[i].key khác k) do 
i = i+1;
endw
Phạm Thế Bảo
• Thuật toán dừng khi nào?
– i =n+1 Æ không tìm thấy
– i=i0, với 1≤i0≤n Æ tìm thấy
• Để đánh giá ta cần tính α:, 
– Tìm không thấy: k∉{a[i].key/i=1..n}Æ α=n, gọi q
là xác suất tìm không thấy.
– Tìm thấy sẽ có xác suất là (1-q)
– Đặt pi là xác suất để a[i].key bằng k
ế ế– Giả thi t a[k].key khác a[l].key n u k≠l
– Nếu a[i].key bằng k thì α=i-1 ???
– Vậy
Phạm Thế Bảo
1 1
(1 ) 1 ( 1)trung bình vaø coù 
n n
i i
i i
q q p p iα α
= =
+ − = = = −∑ ∑
28/03/2008
3
• Khi tìm thấy số lượng so sánh khóa:
– Tối thiểu =
– Tối đa =
– Trung bình =
1
n
1
n
ipα + = ∑
• Số lần so sánh khóa trung bình cho cả hai
trường hợp tìm thấy và không tìm thấy là:
1i=
1
( 1) (1 )
n
i
i
n q q ip
=
+ + − ∑
Phạm Thế Bảo
Xem xét phân bố khóa
1. Giả sử a[i].key=i
k đ h ẫ hiê từ tậ h 1 2 2 3 3 ược c ọn ng u n n p ợp , , , , , 
3, …, i, i, …, i, …, n, …, n, n+1, n+2, …, 2n
Tổng số khả năng có thể là:(1+2+…+n)+n=
Æ Xác suất để k∉{key} là
i lần n lần
( 3)
2
n n +
2
( 3) 3
nq n n n
= =+ + 
Suy ra
Phạm Thế Bảo
2
2
( 1) ( 1)
2
i
i ip n n n n
= =+ +
28/03/2008
4
Æ Số lần so sánh khóa trung bình là:
2 2 2( 1) 1
3 3 ( 1)
n in i
⎛ ⎞⎛ ⎞= + + − ⎜ ⎟⎜ ⎟+ + +⎝ ⎠⎝ ⎠∑1
2
2( 1) 1 2 ( 1)(2 1). .
3 3 ( 1) 6
2 9 7
3( 3)
in n n n
n n n n n
n n n n
n n
=
+ + + += ++ + +
+ += +
Phạm Thế Bảo
n
2. Giả sử dữ liệu phân bố đềuÆ
– Số lần so sánh khóa trung bình khi tìm thấy:
1 , 1..ip i nn
= ∀ =
1 1
1 1
2
n n
i
i i
nip i
n
+= =∑ ∑
3. Giả sử có phân bố khóa như sau:
= =
1 2
3 2
1
2
...
2
...
2n n
cp c p
cp
cp −
= =
=
=
Phạm Thế Bảo
1
1 1
11
1 121 2 112 21
2
1
12 1
2
ita c o ù p
n
nn n
k
i k
n
c c c
c
−
= =
⎛ ⎞− ⎜ ⎟ ⎡ ⎤⎛ ⎞⎝ ⎠= = = = −⎢ ⎥⎜ ⎟⎝ ⎠⎢ ⎥⎣ ⎦−
⇒ = ⎡ ⎤⎛ ⎞−⎢ ⎥⎜ ⎟⎝ ⎠⎢ ⎥⎣ ⎦
∑ ∑
28/03/2008
5
• Số lần so sánh khóa trung bình khi tìm thấy:
1 1
1 1 1
''
2 2
(1 )n ni-1 iùt f( ) i
n n n
i i i
i i i
n
c iip i c
x x
− −
= = =
= =
⎡ ⎤−⎛ ⎞ ⎢ ⎥⎜ ⎟
∑ ∑ ∑
∑ ∑
1
2
1
( 1) 1
(1 )
1
2
i=1 i=1
xe x = x x
 vôùi c ñöôïc tính nhö treân
n n
n
i
x
nx n x
x
ip cf
+
= = −⎝ ⎠ ⎣ ⎦
− + += −
⎛ ⎞⇒ = ⎜ ⎟⎝ ⎠∑
Phạm Thế Bảo
1
1
22
2
11
2
 khi n ñuû lôùn (n
i
n n
i
i
n
n
ip
=
=
+−
⇒ = ⇒ →
−
∑ ) 2∞ ⇒
• Nếu thuật tóan phân bố như trên thì độ phức
tạp của thuật toán là hằng (nhỏ).
D hữ hầ ử h ờ ê đ ặ• o n ng p n t t ư ng xuy n ược g p
nhất được sắp ở đầu, những phần tử ở đầu có
xác suất gặp cao hơn các phần tử càng về sau,
tỷ lệ này giảm dần rất nhanh theo hệ số 2.
Ví dụ: ứng dụng trong tổ chức dữ liệu của hệ cơ
sở dữ liệu Oracle
Phạm Thế Bảo
28/03/2008
6
4. Xem xét một phân bố khác như sau:
1 2
3
1 2
. . .
3
c cp p
cp
= =
=
1 1
. . .
11
1 11 .. . ( ln )
2
i
n
ta c o ù p
m a ø H
n
n n
n
i k
cp
n
c cH
k
O n
n
= =
=
= = =
= + + + =
∑ ∑
• Lúc đó số phép so sánh khóa trung bình trong
trường hợp tìm thấy là
Phạm Thế Bảo
1 1
1
ln
n n
n
i
i i n
H n nip i
i H n= =
= = ≈∑ ∑
Tìm kiếm nhị phân
• Cho mảng n phần tử thỏa a[1].key<…<a[n].key
• Tổng quát, ta sẽ xét từ a[l] đến a[r], với l≤r:
Tí h [(l+ )/2]– n m= r
– Nếu a[m].key bằng k Æ dừng
– Nếu a[m].key nhỏ hơn k, quá trình tìm kiếm lặp lại
cho bên phải, nghĩa là l=m+1
– Nếu a[m].key lớn hơn k, quá trình tìm kiếm lặp lại
cho bên trái, nghĩa là r=m-1
• Thay vì tính như trên, ta tính
m=(a[l].key+a[r].key)/2 Æ chuyện gì?
Phạm Thế Bảo
28/03/2008
7
• Ví dụ: xét n=6, m=(1+6)/2=3
– Nếu k∈{khóa} thì thuật toán
dừng ở đâu?
Số lần lặp trung bình ≈
[2,2]
[4,6]
3
5
642
1
[1,2]
[4,4] [6,6]
[1,6]
1 1 2 2 3 3 14
6 6
x x x+ + =
Phạm Thế Bảo
– Nếu k∉ {khóa} thì thuật toán
dừng ở đâu?
Số lần lặp trung bình ≈
a∈(-∞,a[1].key)
b∈(a[1].key,a[2].key) c∈(a[2].key,a[3].key)
[2,2]
[4,6]
3
5
642
1
a
[1,2]
[4,4] [6,6]
[1,6]
d∈(a[3].key,a[4].key) e∈(a[4].key,a[5].key)
f∈(a[5].key,a[6].key) g∈(a[5].key,+ ∞) b c d e f g
1 2 6 3 20
7 7
x x+ =
Phạm Thế Bảo
28/03/2008
8
Thuật toán:
l=1;
r=n;
idx=-1;
while (l≤r) do
m=[l+r]/2;
if(a[m].key==k) then
idx=m;
l=r+1;
else
if(if(a[m].key<k) then
l=m+1;
else
r=m-1;
endif
endif
endw
Phạm Thế Bảo
• β=1 khi k∈{khóa} và β=0 khi k∉{khóa} 
• Có 2α-β so sánh khóa
• Ta nhận thấy: 1≤ α ≤log2n
• Ước lượng chính xác giá trị trung bình của α:
Ta nhận thấy có thể biểu diễn theo cây, với định nghĩa quy nạp cho cây: với
đoạn [l,r] cây có gốc là m=[(l+r)/2] và cây con trái được xây dựng với đọan
[l,m-1] và cây con phải được xây dựng với đọan [m+1,r].
Ví dụ: n=10
[3 4]
[6,10]
5
82
[1,4]
[6 7] [9,10][1 1]
Với mỗi cây T, ta xây dựng cây
mở rộng T1 sao cho mỗi node 
của t có đúng hai con
Phạm Thế Bảo
,
963
,
1
,
4 7 10
[4,4] [10,10][7,7]
28/03/2008
9
• Thuật ngữ:
– Node trong (node tròn) của T=node của T=n
– Node ngoài (vuông) của T=node bổ sung=N
– Độ dài đường đi đến node x: l(x)=số cạnh từ gốc
đến x.
– Độ dài đường đi trong cây T=
Trở lại ví dụ trên, độ dài = 0x1+2x1+4x2+3x3=19
– Độ dài đường đi trung bình đến mỗi node=
Trở lại ví dụ =19/10=1 9
{ } trong
l(x)=I(T)
x node∈
∑
( )
soá node trong
I T
( )l∑, .
– Độ dài đường đi ngòai = E(T) = 
– Độ dài đường đi ngòai trung bình =
Phạm Thế Bảo
{ }node ngoaøix
x
∈
( )
soá node ngoaøi
E T
• Mệnh đề:
a. Số node ngoài = số node trong +1, N=n+1
b. E(T)=I(T)+2n
c. Độ dài đường đi ngòai trung bình = 
( ) 2
+1
I T n+
Ví dụ trên, có E(T)=
I(T)=
E(T)=I(T)+2x10
n
Phạm Thế Bảo
28/03/2008
10
• Nhận xét:
– Khi tìm thấy: dừng ở node tròn x
• β=1 và α=l(x)+1
[ ]
{ }
( ) 1
( )d t ø
l x
I T
+∑
•
• Số phép so sánh khóa TB= 
– Khi không tìm thấy: dừng ở node vuông y
• β=0 và α=l(y)
1no e ronx
n n
α ∈= = +
( ) ( )2 2 1 1 1I T I T
n n
α β ⎡ ⎤− = + − = +⎢ ⎥⎣ ⎦
•
• Số phép so sánh khóa TB= 
Phạm Thế Bảo
( ) ( ) 2
1
E T I T n
N n
α += = + ( ) 42 2
1
I T n
n
α β +⎡ ⎤− = ⎢ ⎥+⎣ ⎦
Sắp xếp chèn
• Có n phần tử a[1], …, a[n], ý tưởng:
– n=1 hiển nhiên a[1] được sắp
– Giả sử có k phần tử đầu a[1].key≤… ≤ a[k].key
được sắp, ta phải tìm cách chèn a[k+1] vào đúng vị
trí.
Ví dụ: n=7, có mảng: 10 2 7 9 6 1 5
Lần 1 chèn 2 trước 10
Lần 2 chèn 7 giữa 2 và 10
…
Phạm Thế Bảo
28/03/2008
11
Thuật toán:
j=2;
while (j≤n) do
i=j-1;
k=a[j].key;
r=a[j];
while ((i>0)&&(k<a[i].key)) do
a[i+1]=a[i];
i=i-1;
endw
a[i+1]=r;
j=j+1;
endw
Phạm Thế Bảo
• Xét P(j) có hai trường hợp:
– Không tối ưu hóa biểu thức: (αj+1) so sánh số học
và (αj+1) so sánh khóa.
– Tối ưu:
i có thể giảm về 0: (α +1) so sánh số học và α so sánh khóa– j j 
– i không thể giảm về 0: (αj+1) so sánh số học và (αj+1)so sánh
khóa
– Mục tiêu là xác định αj:
• Nhận xét mảnh có cấu trúc như sau:
σcur = Khóa tăng aj
• Gọi σ=a1a2… an : hoán vị ban đầu
• αj = số phần tử bên trái aj trong σcur mà lớn hơn aj
= số phần tử bên trái aj trong σ mà lớn hơn aj
Phạm Thế Bảo
28/03/2008
12
• Vậy
a Số phép gán số học
1
2
01
 soá nghòch theá cuûa 
coù soá nghòch theá cuûa 
n
j
j
n
j
j
α σ
α α σ
=
=
=
= ⇒ =
∑
∑
( )1 ( 1) 1gaùn soá hoc P(j)nn n⎡ ⎤= + − + + +⎢ ⎥∑.
b. So sánh số học
2
2
2 1 2 1
 ï 
min=0
n(n-1)soá nghich theá cuûa max=
2
n(n-1)
4
j
n
j
j
n nα σ
=
=
⎣ ⎦
⎧⎪⎪⎪= − + = − + ⎨⎪⎪⎪⎩
∑
( )
2
1 2 1 soá nghòch theá cuûa 
n
j
j
n nα σ= + + = − +∑
c. Sao chép khóa = n-1
Phạm Thế Bảo
=
d. Sao chép mẫu tin
e. So sánh khóa:
( )
2
2
( 1) 1
2 2 2 2
cheùp maãu tin P(j)
soá nghòch theá cuûa 
n
j
n
j
j
n n
n nα σ
=
=
⎡ ⎤= − + + −⎢ ⎥⎣ ⎦
= − + = − +
∑
∑
n
• Không tối ưu
• Có tối ưu:
– a[j] là cực tiểu so với bên trái: i có thể giảm về 0
– Ngược lại i không giảm về 0
( )
2
1 1 soá nghòch theá cuûa j
j
nα σ
=
= + = − +∑
⎛ ⎞ ⎛ ⎞
Phạm Thế Bảo
( )
2 2
2
1
,
[ ] [ ]
1
n
j
j=2
a[1] laø loaïi 1, loaïi 1 vaø 2 buø nhau
 loaïi 1 loaïi 2
=
n n
j j
j j
n
j
a j a j
α α
α
= =
=
+⎜ ⎟ ⎜ ⎟= +⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠
+
∑ ∑
∑ ∑
28/03/2008
13
Vậy số phép so sánh khóa là (số nghịch thế của
σ +(n- số phần tử cực tiểu bên trái))
( 1)
4 n
n nTB n H−⇒ = + −
Phạm Thế Bảo
Sắp xếp chọn
• Ý tưởng: xét j=n, …, 2 chọn max trong
{a[1] key a[2] key a[j] key} tại idx đổi. , . , …, . , 
chỗ a[j] và a[idx].
ví dụ: 10 2 7 9 6 1 5
– j=n chọn idx=1 Æ hoán đổi
– j=n-1 chọn idx=9 Æ hóan đổi
– …
Phạm Thế Bảo
28/03/2008
14
Thuật toán:
j=n;
while (j≥2) do
idx=1;
i=2;
while (i≤j) do
if(a[i].key>a[idx].key) then
idx=i;
endif
i=i+1;
endw
a[j] ÅÆ a[idx];
j=j-1;
endw
Phạm Thế Bảo
• Đoạn P(j) là tìm khóa lớn nhất trong tập j phần
tử. Ước lượng tổng chi phí trung bình của αj
như sau:
( 1)
n
jp n H n= + −∑
Phạm Thế Bảo
1
n
j=