Phan tich Thuat toan 6

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (324.04 KB, 14 trang )

(1)<div class='page_container' data-page=1>

Á

Ố

Đ

ÁNH GIÁ M

Ộ

T S

Ố

THU

Ậ

T TOÁN THƠNG D

Ụ

NG

Phạm Thế Bảo
Khoa Tố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 tốn: cho trước
khóa k, có tồn tại j đểa[j].key bằng k hay khơng?

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

Nếu bỏelse:

</div>
(2)<div class='page_container' data-page=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 tốn s

ẽ

t

ă

ng hay gi

ả

m?

phép tốn s

ẽ

t

ă

ng hay gi

ả

m?

• Vi

ế

t l

ạ

i thu

ậ

t tốn:

i=1;

a[n+1].key=k;

while (a[i].key khác k) do

i = i+1;

endw

Phạm Th Bo

ã

Thu

t toỏn d

ng khi no?

i =n+1 ặkhụng tỡm thy

i=i0, vi 1i0n ặtỡm thy

ã

ỏnh giỏ ta c

á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 pilà 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 ) n i 1 và có trung bình n i( 1)

i i

q q p α α p i

= =

</div>
(3)<div class='page_container' data-page=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 pi

α+ =∑

• 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à:

1
i=

∑

(

1)

(1

)

n i

i

n

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

k

đượ

c ch

ọ

n ng

ẫ

u nhiên t

ừ

t

ậ

p h

ợ

p 1, 2, 2, 3, 3,

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+

( 3) 3

n
q

n n n

= + =

Ỉ

Xác su

ấ

t

để

k

∉

{key} là

Suy ra

( 3) 3

n n+ n+

2
( 1) ( 1)

i

i i

p

n n n n

= + =

</div>
(4)<div class='page_container' data-page=4>

Ỉ

S

ố

l

ầ

n so sánh khóa trung bình là:

2 (

1)

1

3 (

1)

n

i

n

⎛

⎞

⎛

i

⎞

=

+

+ −

⎜

⎟

⎜

⎟

+

⎝

+

⎠⎝

∑

+

⎠

3 (

1)

2(

1)

1

2 (

1)(2

1)

.

3 3 (

1)

6

2

9

7 3(

3)

i

n

n n

n

n n

n

n n

n

⎜

⎟

⎜

⎟

+

⎝

+

⎠⎝

+

⎠

+

=

+

=

+

∑

Phạm Thế Bảo

3(

n

+

3)

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..

i

p i n

n
= ∀ =
1 1

1

2

n n
i
i i

n

ip

i

n

+

=

∑

3. Gi

ả

s

ử

có phân b

ố

khóa nh

ư

1 1

2

i=

n

i=

1 2
3 2
1
2
...
2
...
2
n n
c
p c p

c
p
c
p −
= =
=
=

Phạm Thế Bảo

1 1

1
1

1 2 1

2 1 2

2
1
1
2 1
2
i

ta c o ù p

n
n
n n
k
i k
n

c c c

</div>
(5)<div class='page_container' data-page=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 n
i-1 i

ùt f( ) i

n n n

i i i

n

c i

ip i c

x x
− −

= = =
= =
⎡ − ⎤
⎛ ⎞
⎢ ⎥
⎜ ⎟

∑

1
2
( )
1
( 1) 1
(1 )

1
2

i 1 i

i=1 i=1

xet f(x)= ix x

với c được tính như trên

n n

n

i

x
nx n x

x
ip cf
+
=⎜ ⎟ = ⎢ ⎥
−
⎝ ⎠ ⎣ ⎦
− + +
=
−
⎛ ⎞
⇒ = ⎜ ⎟
⎝ ⎠

∑

Phạm Thế Bảo

1
1
2
2
2
2
1
1

khi n đủ lớn (n

i
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

ờ

ê

đ

ặ

• Do nh

ữ

ng ph

ầ

n t

ử

th

ườ

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

ơ

</div>
(6)<div class='page_container' data-page=6>

4. Xem xét m

ộ

t phân b

ố

khác nh

ư

1 2

...
3

c c

p p

c
p

= =

1 1

...

1
1

1 1

1 ... ( ln )

2
i

ta c o ù p

m a ø H

n

n n

n

i k

c
p

n

c c H

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

2 n

1 1

n n

n
i

i i n

H n n

ip 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]

–Tính m=[(l+r)/2]

–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

</div>
(7)<div class='page_container' data-page=7>

• Ví d

ụ

: xét n=6, m=(1+6)/2=3

–Nếu k∈{khóa} thì thuật tốn
dừng ởđâu?

Số lần lặp trung bình≈

[2,2]

[4,6]
3

6
4

2
1

[1,2]

[4,4] [6,6]

[1,6]

1 1 2 2 3 3 14

6 x

+

x

+

x

=

Phạm Thế Bảo

–Nếu k∉{khóa} thì thuật tố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

6
4

2
1

[1,2]

[4,4] [6,6]

[1,6]

b∈(a[1].key,a[2].key) c∈(a[2].key,a[3].key)
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 x

+

x

</div>
(8)<div class='page_container' data-page=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

8
2

[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 T1sao cho mỗi node
của t cóđúng hai con

Phạm Thế Bảo
[3,4]

9
6

[6,7] [9,10]

1
[1,1]

4 7 10

[4,4] [10,10]

</div>
(9)<div class='page_container' data-page=9>

• Thu

ậ

t ng

ữ

:

–Node trong (node trịn) của T=node của T=n

–Node ngồi (vng) của T=node bổ sung=N

–Độộdàiđườnggđiđến node x: l(x)=s( ) ố cạạnh từggố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

∑

( )
số node trong

I T

( )

l

∑

Trởlại ví dụ, 19/10 1.9

–Độdàiđườngđi ngịai = E(T) =

–Độdàiđườngđi ngịai trung bình =

Phạm Thế Bảo

{ }

( )

node ngồi

x

l x

∈

∑

( )

số node ngồ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đườngg đi ngịai trung bình = g g I T( ) 2+1+ n

Ví d

ụ

trên, có E(T)=

I(T)=

E(T)=I(T)+2x10

n+1

</div>
(10)<div class='page_container' data-page=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 vng y
• β=0 vàα=l(y)

{ } ( )

node tron

x I T

n n

α = ∈ = +

( ) ( )

2 2 I T 1 1 I T 1

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

α = = +

+ ( ) 4

2 2

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
…

</div>
(11)<div class='page_container' data-page=11>

Thuật toán:
j=2;

while (j≤n) do
i=j-1;
k=a[j].key;[j] y
r=a[j];

while ((i>0)&&(k<a[i].key)) do
a[i+1]=a[i];

i=i-1;
endw

a[i+1]=r;
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

–i có thểgiảm về0: (αj+1) so sánh sốhọc vàαjso sánh khóa

–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: hốn vịban đầu

</div>
(12)<div class='page_container' data-page=12>

• V

ậ

y

a Số phép gán sốhọc

số nghịch thế của

có số nghịch thế cuûa

n

j
j
n
j
j
α σ
α α σ
=
=
=
= ⇒ =
∑
∑
( )

1 (n 1) ⎡ n gán số hoc P(j)⎤ n 1

= + − +⎢∑ ⎥+ +

a. Số phép gán sốhọc

b. So sánh số học

( )

1 ( 1) 1

2 1 2 1

gan so hoïc P(j)

min=0
n(n-1)
số nghich thế của max=

2
n(n-1)
4
j
n
j
j
n n

n α n σ

=
=
+ +⎢ ⎥+ +
⎣ ⎦
⎧
⎪
⎪
⎪
= − + = − + ⎨
⎪

⎪
⎪⎩
∑
∑

(

)

1 2 1 số nghịch thế của

n
j
j

n α n σ

= +∑ + = − +

c. Sao chép khóa = n-1

Phạm Thế Bảo
2

j=

d. Sao chép mẫu tin

e. So sánh khóa:

( )

( 1) 1

2 2 2 2

chép mẫu tin P(j)

số nghịch thế củ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

(

)

1 1 số nghịch thế của

n
j
j
n
α σ
=
=

∑

+ = − +
⎛ ⎞ ⎛ ⎞

Phạm Thế Bảo

(

)

2 2
2
1

,
[ ] [ ]
1
n
j
j=2

a[1] là loại 1, loại 1 và 2 bù nhau
loại 1 loại 2

=
n n
j j
j j
n
j

a j a j

</div>
(13)<div class='page_container' data-page=13>

V

ậ

y s

y

ố

phép so sánh khóa là (s

p p

(

ố

ngh

g

ị

ch th

ế

c

ủ

a

σ

+(n- s

ố

ph

ầ

n t

ử

c

ự

c ti

ể

u bên trái))

(

1)

4

n

n n

TB

−

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

{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 Ỉhốnđổi

–j=n-1 chj ọọn idx=9 Ỉhóanđổi

</div>
(14)<div class='page_container' data-page=14>