TĂNG TRƯỞNG CỦA HÀM VÀ PHÂN TÍCH THUẬT TOÁN
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 (1.45 MB, 52 trang )
BÁO CÁO TIỂU LUẬN
TĂNG TRƯỞNG CỦA HÀM
VÀ PHÂN TÍCH THUẬT TOÁN
Giáo viên hướng dẫn: TS. Hoàng Quang
Thực hiện: Hồ Thủy Sơn
Nguyễn Hữu Lương
Hồ Thị Thu Thủy
Nguyễn Thị Phương Ngọc
Lê Thị Thanh Châu
Huế, tháng 10 năm 2014
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
Intel Confidential
Intel Confidential
NỘI DUNG TRÌNH BÀY
Tăng trưởng của hàm và phân tích thuật toán
1
!"
2
3
#$%!"&"'
4
#()
5
)*%+"!,"
Intel Confidential
Intel Confidential
Tăng trưởng hàm và phân tích thuật toán
Identit
y
/0&123)4&
Đầu vào: Cho một dãy n số (a1, a2…an)
Đầu ra: Phép hoán vị (a1’, a2’,….an’)
thỏa mãn a1’<=a2’<=an’
Ví dụ: Cho mảng A với dãy số chưa được sắp xếp A = <5, 2, 4,
6, 1, 3> và tiến hành xây dựng mã giả để viết thuật toán sắp xếp
chèn theo thứ tự tăng dần và kết quả sẽ là A = <1, 2, 3, 4, 5, 6>
Intel Confidential
Intel Confidential
/0&123)4&
- Đầu tiên ta xem chỉ số j như là con bài
hiện tại đang ở trên tay. Cho vòng lặp For
chạy bởi j nó sẽ chia mảng A thành 2
đoạn A[1 j - 1] đây là đoạn cần được
sắp xếp và A[j + 1 n] là số con bài còn
lại ở trên bàn chưa được đưa vào.
- Chỉ số j dời từ trái sang phải qua mảng. Với mỗi lần lặp của
vòng lặp For thành phần A[j] được lấy ra khỏi mảng. Sau đó bắt
đầu tại vị trí j-1, các thành phần liên tiếp được dời về bên phải
một vị trí cho đến khi tìm thấy vị trí đúng đắn cho A[j] tại điểm mà
nó được chèn vào.
Intel Confidential
Intel Confidential
Identit
y
/0&123)4&
Sử dụng mã giả để viết thuật tóan
INSERTION-SORT(A)
1 for j ← 2 to length[A]
2 do m ← A[j] {m là khóa }
3 ► Chèn A[j] vào chuỗi có sắp xếp A[1 i - 1].
4 i ← j - 1
5 while i > 0 and A[i] > m
6 do A[i + 1] ← A[i]
7 i ← i - 1
8 A[i + 1] ← m
Các bước minh họa giải thuật
Intel Confidential
Intel Confidential
Identit
y
/0&123)4&
Thủ tục sắp xếp chèn bằng ngôn ngữ Pascal:
Procedure Insertion_Sort;
Begin
For j:=2 to n do
Begin
m:= A[j]; i: =j-1;
while m<A[i] and i> 0do
begin
A[i+1]:=A[i];
i:=i-1;
end;
A[i+1]:=m;
End;
End;
Intel Confidential
Intel Confidential
Identit
y
/0&123)4&
Cách sử dụng những mã giả
1- Thụt đầu dòng để nêu rỏ cấu trúc khối.
2- Cấu trúc vòng lặp while, for, và repeat và những cấu trúc có điều
kiện như if, then, và else được thể hiện giống nhau như trong pascal.
3- Ký tự "►" để ghi chú hoặc giải thích một đoạn lệnh.
4- Phép gán nhiều biến cho 1 giá trị nào đó như: i ← j ← e tức là cả 2
biến i và j là có giá trị e nó nên được xem là tương đương như là phép
gán j ← e theo sau phép gán i ← j.
5- Biến (như là i, j, và key) là biến cục bộ trong thủ tục đã cho trên.
Chúng ta không nên sử dụng biến toàn cục với những mục đích không rỏ
Intel Confidential
Intel Confidential
Identit
y
/0&123)4&
Cách sử dụng những mã giả
6- Các thành phần mảng được truy cập bằng cách đặt tả tên mảng theo
sau là chỉ số trong các dấu ngoặc vuông. Ví dụ A[i] nêu rỏ thành phần
thứ i trong mảng A.
7- Dữ liệu phức hợp thường được tổ chức thành các đối tượng bao hàm các
thuộc tính hoặc các trường. Để truy cập 1 trường cụ thể ta dùng tên trường
theo sau là tên đối tượng của nó trong các dấu ngoặc vuông.
Ví dụ ta xem 1 mảng như 1 đối tượng có thuộc tính length nêu rỏ số lượng
thành phần mà nó chứa. Để đặt tả số lượng thành phần trong mảng A ta viết
Length[A].
8 – Việc cấp phát bộ nhớ sẽ được hiểu ngầm
Intel Confidential
Intel Confidential
PHẦN 3 THIT K THUÂT TON
Intel Confidential
Intel Confidential
&"56$“)(789:”;<;=(;>=9
!"#$%
%&%'(
)*+(,-.(
/0 *
Intel Confidential
Intel Confidential
?";@""56$“;<;=(;>=9”
<*A(
Intel Confidential
Intel Confidential
THU T TOAN MERGE-SORTÂ
•
!"#$$%&
•
'()*%
•
+,-./"0%&1+2
•
3 !"#$$-&
•
4 !"#$-0'$%&
•
5"#$$-$%&
10 2. $3%&%45&6
Intel Confidential
Intel Confidential
Th tuc con Mergeu
•
"#$$-$%&
•
''6-0'
•
++6%-
•
37%,8,8%%89:';;
'0'<8
:';;+0'<
•
4)=%(6'='
•
5=9:(<6#:0(
'<
•
>)=%?6'=+
•
@=:?<6#:-0?<
•
A9:'0'<6B
•
C:+0'<6B
•
'D(6'
•
''?6'
•
'+)=%E6=%
•
'3=()9:(<F:?<
•
'4,#:E<6
9:(<
•
'5(6(0'
•
'>,G,#:E<6:?<
•
'@?6?0'
Intel Confidential
Intel Confidential
Bưc 0:
MS( 2,5,4,5,9)
Bưc 1
MS(2,5,4,5,9)
MS(2,5,4)
MS(5,9)
V d minh ha
Intel Confidential
Intel Confidential
Bưc 2
MS(2,5,4,5,9)
MS(2,5,4) MS(5,9)
MS(2,5) MS(4)
MS(5)
MS(9)
Intel Confidential
Intel Confidential
Bưc 3
MS(2,5,4,5,9)
MS(2,5,4) MS(5,9)
MS(2,5) MS(4)
MS(5)
MS(9)
MS(2) MS(5)
Intel Confidential
Intel Confidential
BCDCBC“(789:”
7'8!92(
:$,&;H-(<I&
=(,>?
",92(:@?
(1)
( )
( / ) ( ) ( )
if n c
T n
aT n b D n C n otherwise
Θ <=
=
+ +
Intel Confidential
Intel Confidential
2.3.3 Phân tich thu t toan Merge sortâ
JKLGMH7(8N%OIN
GP7QR7%(7=
P=
Hay
Intel Confidential
Intel Confidential
PHẦN 4: HỆ KÝ HIỆU TIỆM CẬN
Tăng trưởng hàm và phân tích thuật toán
Identit
y
Cc ký hiệu dSng để mô tả thời gian thực hiện
tiệm cận của một thuật ton được định nghĩa
dưới dạng cc hm, m miền của những hm đT
l tập hợp cc số tự nhiên N={1,2,3U.}.
NT thường định nghĩa trên kch thước dữ liệu
vo l số nguyên (integer).
Tuy nhiên, ký hiệu dễ dng mở rộng trên miền l
tập số thực hoặc giới hạn của tập hợp con cc
số tự nhiên.
Intel Confidential
Intel Confidential
Hệ ký hiệu tiệm cận (tt)
•
Phần ny trVnh by cc hệ ký hiệu sau:
1.Ký hiệu Θ
2.Ký hiệu O
3.Ký hiệu Ω
4.Ký hiệu o
5.Ký hiệu ω
Tăng trưởng hàm và phân tích thuật toán
Intel Confidential
Intel Confidential
Tăng trưởng hàm và phân tích thuật toán
Identit
y
1. Hệ ký hiệu Θ
•
Định nghĩa: Với một hm đã cho g(n), qua Θg(n) ta
thể hiện tập hợp cc hm
))(()( ngnf Θ∈
Bởi vì Θ (g(n)) là một tập hợp nên ta có thể viết
Hoặc
))(()( ngnf Θ=
≥∀≤≤≤∃=Θ
0
),(
2
)()(
1
0,
0
,
2
,
1
:)())(( nnngcnfngcnccnfng
Intel Confidential
Intel Confidential
Tăng trưởng hàm và phân tích thuật toán
Identit
y
1. Hệ ký hiệu Θ (tt)
•
Với tất cả các giá trị từ n đến
bên phải n
0
, giá trị của f(n) >= c
1
g(n )
và f(n)<= c
2
g(n).
•
Nói cách khác, với mọi n>n
0
,
hàm f(n) bằng g(n) với một hằng số
nào đó.
•
Ta nói rằng, g(n) là một tiệm cận
ràng buộc chặt chẽ (asymptotically
tight bound) của f(n).
Intel Confidential
Intel Confidential
1. Hệ ký hiệu Θ (tt)
•
Định nghĩa của Θ(g(n)) yêu cầu mọi phần tử
))(()( ngnf Θ∈
Tăng trưởng hàm và phân tích thuật toán
Identit
y
phải là tiệm cận không âm.
Do vậy, bản thân hàm g(n) phải là tiệm cận không âm,
hoặc ngược lại tập Θ(g(n)) là rỗng.
Giả sử rằng tất cả các hàm được sử dụng trong vòng
ký hiệu Θ, và các ký hiệu tiếp theo là tiệm không âm.
•
Ta có thể sử dụng định nghĩa để chỉ ra rằng
)(32/1
22
nnn Θ=−
bằng cách chọn c
1
= 1/14, c
2
=1/2, và n
0
= 7
Intel Confidential
Intel Confidential
1. Hệ ký hiệu Θ (tt)
Tăng trưởng hàm và phân tích thuật toán
Identit
y
.
Tổng quát hơn, xét hàm bậc hai bất kỳ
cbnannf ++=
2
)(
Với a,b,c là hằng số và a>0
Ta sẽ lấy c
1
=a/4, c
2
=7a/4 và
))/(,/max(*2
0
acabn =
NTi chung, đối với bất kỳ đa thức
∑
=
=
d
i
i
i
nanp
0
)(
Với a
i
là hằng số và a
d
>0, chúng ta có
)()(
d
nnp Θ=
Vì một hằng bất kỳ là đa thức bậc 0, nên ta có thể
biễu diễn hàm liên tục bất kỳ là Θ(n
0
), hoặc Θ(1).
Intel Confidential
Intel Confidential
2. H ký hi u Oệ ệ
Tăng trưởng hàm và phân tích thuật toán
Identit
y
•
Cc ký hiệu Θ l ký hiệu tiệm cận giới
hạn của một hm chặn trên v chặn
dưới. Khi chỉ cT một tiệm cận chặn trên
(asymptotic higher bound), chWng ta sử
dụng ký hiệu O.
•
Đ/n: Với một hm đã cho g(n), ta định
nghĩa:
•
O(g(n)) = {f(n): tồn tại hằng số dương c
v n
0
sao cho 0 ≤ f (n) ≤ cg(n), với mọi
n>n
0
}.
