Kỹ thuật phân tích giải thuật
K thu t phân tích gi i thu tỹ ậ ả ậ
Trong bài vi t này chúng ta s nghiên c u nh ng v n đ sau:ế ẽ ứ ữ ấ ề
S c n thi t ph i phân tích các gi i thu tự ầ ế ả ả ậ
Th i gian th c hi n ch ng trìnhờ ự ệ ươ
T su t tăng và đ ph c t p c a gi i thu tỷ ấ ộ ứ ạ ủ ả ậ
Tính th i gian th c hi n ch ng trìnhờ ự ệ ươ
1. S c n thi t ph i phân tích các gi i thu tự ầ ế ả ả ậ
Trong khi gi i m t bài toán chúng ta có th có m t s gi i thu t khác nhau, ả ộ ể ộ ố ả ậ
v n đ là c n ph i đánh giá các gi i thu t đó đ l a ch n m t gi i thu t ấ ề ầ ả ả ậ ể ự ọ ộ ả ậ
t t nh t. Thông th ng thì ta s căn c vào các tiêu chu n sau:ố ấ ườ ẽ ứ ẩ
1. Gi i thu t đúng đ nả ậ ắ
2. Gi i thu t đ n gi nả ậ ơ ả
3. Gi i thu t th c hi n nhanhả ậ ự ệ
V i yêu c u (1), đ ki m tra tính đúng đ n c a gi i thu t chúng ta có th ớ ầ ể ể ắ ủ ả ậ ể
cài đ t gi i thu t đó và cho th c hi n trên máy v i m t s b d li u m u ặ ả ậ ự ệ ớ ộ ố ộ ữ ệ ẫ
r i l y k t qu thu đ c so sánh v i k t qu đã bi t. Th c ra thì cách làm ồ ấ ế ả ượ ớ ế ả ế ự
này không ch c ch n b i vì có th gi i thu t đúng v i t t c các b d ắ ắ ở ể ả ậ ớ ấ ả ộ ữ
li u chúng ta đã th nh ng l i sai v i m t b d li u nào đó. V l i cách ệ ử ư ạ ớ ộ ộ ữ ệ ả ạ
làm này ch phát hi n ra gi i thu t sai ch ch a ch ng minh đ c là nó ỉ ệ ả ậ ứ ư ứ ượ
đúng. Tính đúng đ n c a gi i thu t c n ph i đ c ch ng minh b ng toán ắ ủ ả ậ ầ ả ượ ứ ằ
h c. T t nhiên đi u này không đ n gi n và do v y chúng ta s không đ ọ ấ ề ơ ả ậ ẽ ề
c p đ n đây.ậ ế ở
Khi chúng ta vi t m t ch ng trình đ s d ng m t vài l n thì yêu c u (2) ế ộ ươ ể ử ụ ộ ầ ầ
là quan tr ng nh t. Chúng ta c n m t gi i thu t d vi t ch ng trình đ ọ ấ ầ ộ ả ậ ễ ế ươ ể
nhanh chóng có đ c k t qu , th i gian th c hi n ch ng trình không ượ ế ả ờ ự ệ ươ
đ c đ cao vì dù sao thì ch ng trình đó cũng ch s d ng m t vài l nượ ề ươ ỉ ử ụ ộ ầ
Tuy nhiên khi m t ch ng trình đ c s d ng nhi u l n thì thì yêu c u ộ ươ ượ ử ụ ề ầ ầ
ti ït ki m th i gian th c hi n ch ng trình l i r t quan tr ng đ c bi t đ i ế ệ ờ ự ệ ươ ạ ấ ọ ặ ệ ố
v i nh ng ch ng trình mà khi th c hi n c n d li u nh p l n do đó yêu ớ ữ ươ ự ệ ầ ữ ệ ậ ớ
c u (3) s đ c xem xét m t cách k càng. Ta g i nó là hi u qu th i gian ầ ẽ ượ ộ ỹ ọ ệ ả ờ
th c hi n c a gi i thu t.ự ệ ủ ả ậ
2. Th i gian th c hi n c a gi i thu tờ ự ệ ủ ả ậ
Th i gian th c hi n c a gi i thu t đ c xem xét các khía c nh sau:ờ ự ệ ủ ả ậ ượ ở ạ
Th i gian th c hi n ch ng trìnhờ ự ệ ươ
Đ n v đo th i gian th c hi nơ ị ờ ự ệ
Th i gian th c hi n trong tr ng h p x u nh tờ ự ệ ườ ợ ấ ấ
M t ph ng pháp đ xác đ nh hi u qu th i gian th c hi n c a m t gi i ộ ươ ể ị ệ ả ờ ự ệ ủ ộ ả
thu t là l p trình nó và đo l ng th i gian th c hi n c a ho t đ ng trên ậ ậ ườ ờ ự ệ ủ ạ ộ
m t máy tính xác đ nh đ i v i t p h p đ c ch n l c các d li u vào.ộ ị ố ớ ậ ợ ượ ọ ọ ữ ệ
Th i gian th c hi n không ch ph thu c vào gi i thu t mà còn ph thu c ờ ự ệ ỉ ụ ộ ả ậ ụ ộ
váo t p các ch th c a máy tính, ch t l ng c a máy tính và k x o c a ậ ỉ ị ủ ấ ượ ủ ỹ ả ủ
ng i l p trình. S thi hành cũng có th đi u ch nh đ th c hi n t t trên ườ ậ ự ể ề ỉ ể ự ệ ố
t p đ c bi t các d li u vào đ c ch n. Đ v t qua các tr ng i này, các ậ ặ ệ ữ ệ ượ ọ ể ượ ở ạ
nhà khoa h c máy tính đã ch p nh n tính ph c t p c a th i gian đ c ti p ọ ấ ậ ứ ạ ủ ớ ượ ế
c n nh m t s đo l ng c b n s th c thi c a gi i thu t. Thu t ng ậ ư ộ ự ườ ơ ả ự ự ủ ả ậ ậ ữ
tính hi u qu s đ c p đ n s đo l ng này và đ c bi t đ i v i s ph c ệ ả ẽ ề ậ ế ự ườ ặ ệ ố ớ ự ứ
t p th i gian trong tr ng h p x u nh t.ạ ờ ườ ợ ấ ấ
2.1 Th i gian th c hi n ch ng trìnhờ ự ệ ươ
Th i gian th c hi n m t ch ng trình là m t hàm c a kích th c d li u ờ ự ệ ộ ươ ộ ủ ướ ữ ệ
vào, ký hi uệ T(n)T(n) trong đó nn là kích th c (đ l n) c a d li u vào.ướ ộ ớ ủ ữ ệ
Ví d :ụ Ch ng trình tính t ng c aươ ổ ủ nn s có th i gian th c hi n làố ờ ự ệ T(n) =
cnT(n)=cn trong đó cc là m t h ng s .ộ ằ ố
2.2 Đ n v đo th i gian th c hi nơ ị ờ ự ệ
Đ n v c aơ ị ủ T(n)T(n) không ph i là đ n v đo th i gian bình th ng nh ả ơ ị ờ ườ ư
gi , phút giây… mà th ng đ c xác đ nh b i s các l nh đ c th c hi n ờ ườ ượ ị ở ố ệ ượ ự ệ
trong m t máy tính lý t ng.ộ ưở
Ví d :ụ Khi ta nói th i gian th c hi n c a m t ch ng trình làờ ự ệ ủ ộ ươ T(n) =
cnT(n)=cn thì có nghĩa là ch ng trình y c nươ ấ ầ cncn ch th th c thi.ỉịự
2.3 Th i gian th c hi n trong tr ng h p x u nh tờ ự ệ ườ ợ ấ ấ
Nói chung thì th i gian th c hi n ch ng trình không ch ph thu c vào ờ ự ệ ươ ỉ ụ ộ
kích th c mà còn ph thu c vào tính ch t c a d li u vào. Nghĩa là d ướ ụ ộ ấ ủ ữ ệ ữ
li u vào có cùng kích th c nh ng th i gian th c hi n ch ng trình có th ệ ướ ư ờ ự ệ ươ ể
khác nhau. Ch ng h n ch ng trình s p x p dãy s nguyên tăng d n, khi taẳ ạ ươ ắ ế ố ầ
cho vào dãy có th t thì th i gian th c hi n khác v i khi ta cho vào dãy ứ ự ờ ự ệ ớ
ch a có th t , ho c khi ta cho vào m t dãy đã có th t tăng thì th i gian ư ứ ự ặ ộ ứ ự ờ
th c hi n cũng khác so v i khi ta cho vào m t dãy đã có th t gi m.ự ệ ớ ộ ứ ự ả
Vì v y th ng ta coiậ ườ T(n)T(n) là th i gian th c hi n ch ng trình trong ờ ự ệ ươ
tr ng h p x u nh t trên d li u vào có kích th ócườ ợ ấ ấ ữ ệ ư nn, t c là:ứ T(n)T(n) là
th i gian l n nh t đ th c hi n ch ng trình đ i v i m i d li u vào có ờ ớ ấ ể ự ệ ươ ố ớ ọ ữ ệ
cùng kích th cướ nn.
3. T su t tăng và đ ph c t p c a gi i thu tỷ ấ ộ ứ ạ ủ ả ậ
3.1 T su t tăngỷ ấ
Ta nói r ng hàm không âmằ T(n)T(n) có t su t tăngỷ ấ (growth rate)
(growthrate) f(n)f(n) n u t n t i các h ng sế ồ ạ ằ ố cc và n_0n0 sao cho T(n) ≤
f(n)T(n)≤f(n) v i m iớ ọ n ≥ n_0n≥n0.
Ta có th ch ng minh đ c r ng “Cho m t hàm không âmể ứ ượ ằ ộ T(n)T(n) b t kỳ, ấ
ta luôn tìm đ c t su t tăngượ ỷ ấ f(n)f(n) c a nó”.ủ
Ví d :ụ Gi sả ử T(0) = 1T(0)=1 , T(1) = 4T(1)=4 và t ng quátổ T(n) =
(n+1)^2T(n)=(n+1)2. Đ tặ n_0 = 1n0=1 và c = 4c=4 thì v i m iớ ọ n ≥
1n≥1 chúng ta d dàng ch ng minh r ngễ ứ ằ T(n) = (n+1)^2 ≤
4n^2T(n)=(n+1)2≤4n2 v i m iớ ọ n ≥ 1n≥1, t c là t su t tăng ứ ỷ ấ
c aủ T(n)T(n) là n^2n2.
3.2 Khái ni m đ ph c t p c a gi i thu tệ ộ ứ ạ ủ ả ậ
Gi s ta có hai gi i thu tả ử ả ậ P_1P1 và P_2P2 v i th i gian th c hi n t ng ớ ờ ự ệ ươ
ng làứ T_1(n) = 100n^2T1(n)=100n2 (v i t su t tăng làớ ỷ ấ n^2n2) và T_2(n) =
5n^3T2(n)=5n3 (v i t su t tăng làớ ỷ ấ n^3n3).
Gi i thu t nào s th c hi n nhanh h n?ả ậ ẽ ự ệ ơ
Câu tr l i ph thu c vào kích th c d li u vào. V iả ờ ụ ộ ướ ữ ệ ớ n <
20n<20 thì P_2P2 s nhanh h nẽ ơ P_1P1 (T_2<T_1)(T2<T1), do h s c a ệ ố ủ
5n^3n3 nh h n h s c a 100n^2n2ỏ ơ ệ ố ủ (5<100)(5<100). Nh ng khiư n >
20n>20 thì ng c l i do s mũ c a 100n^2n2ươ ạ ố ủ nh h n s mũ c a ỏ ơ ố ủ
5n^3n3 (2<3)(2<3). đây chúng ta ch nên quan tâm đ n tr ng Ở ỉ ế ườ
h pợ n>20n>20 vì khi n<20n<20 thì th i gian th c hi n c a ờ ự ệ ủ
cả P_1P1 và P_2P2 đ u không l n và s khác bi t gi aề ớ ự ệ ữ T_1T1và T_2T2 là
không đáng k ..ể
Nh v y m t cách h p lý là ta xét t su t tăng c a hàm th i gian th c hi nư ậ ộ ợ ỷ ấ ủ ờ ự ệ
ch ng trình thay vì xét chính b n thân th i gian th c hi nươ ả ờ ự ệ
Cho m t hàmộ T(n)T(n), T(n)T(n) g i là có đ ph c t pọ ộ ứ ạ f(n)f(n) n u t n t i ế ồ ạ
các h ngằ cc, N_0N0 sao cho T(n) ≤ cf(n)T(n)≤cf(n) v i m iớ ọ n ≥
N_0n≥N0 ( t c làứ T(n)T(n) có t su t tăng làỷ ấ f(n)f(n) ) và kí
hi uệ T(n)T(n) là O(f(n))O(f(n)) (đ c là “ô c aọ ủ f(n)f(n)”)
Nói cách khác đ ph c t p tính toán c a gi i thu t là m t hàm ch n ộ ứ ạ ủ ả ậ ộ ặ
trên c a hàm th i gianủ ờ . Vì h ng nhân tằ ử cc trong hàm ch n trên không có ặ
ý nghĩa nên ta có th b qua vì v y hàm th hi n đ ph c t p có các d ng ể ỏ ậ ể ệ ộ ứ ạ ạ
th ng g p sau:ườ ặ log2nlog2n, nn, nlog2nnlog2n, n^2n2, n^3n3, n!
n!, n^nnn.
Ba hàm cu i cùng ta g i là d ng hàm mũ, các hàm khác g i là hàm đa th c. ố ọ ạ ọ ứ
M t gi i thu t mà th i gian th c hi n có đ ph c t p là m t hàm đa th c ộ ả ậ ờ ự ệ ộ ứ ạ ộ ứ
thì ch p nh n đ c, t c là có th cài đ t đ th c hi n, còn các gi i thu t ấ ậ ượ ứ ể ặ ể ự ệ ả ậ
có đ ph c t p hàm mũ thì ph i tìm cách c i ti n gi i thu t.ộ ứ ạ ả ả ế ả ậ
Khi nói đ n đ ph c t p c a gi i thu t là ta mu n nói đ n hi u qu c a ế ộ ứ ạ ủ ả ậ ố ế ệ ả ủ
th i gian th c hi n c a ch ng trình nên ta có th xem vi c xác đ nh th i ờ ự ệ ủ ươ ể ệ ị ờ
gian th c hiên c a ch ng trình chính làự ủ ươ xác đ nh đ ph c t p c a gi i ị ộ ứ ạ ủ ả
thu tậ.
4. Cách tính đ ph c t p c a thu t toánộ ứ ạ ủ ậ
Cách tính đ ph c t p c a m t gi i thu t b t kỳ là m t v n đ không đ n ộ ứ ạ ủ ộ ả ậ ấ ộ ấ ề ơ
gi n. Tuy nhiên ta có th tuân theo m t s nguyên t c sau:ả ể ộ ố ắ
4.1 Qui t c c ngắ ộ
N uế T_1(n)T1(n) và T_2(n)T2(n) là th i gian th c hi n c a hai đo n ờ ự ệ ủ ạ
ch ng trìnhươ P_1P1 và P_2P2; và T_1(n)=O(f(n))T1
(n)=O(f(n)), T_2(n)=O(g(n)T2(n)=O(g(n) thì th i gian th c hi n c a đo n ờ ự ệ ủ ạ
hai ch ng trình đó n i ti p nhau ươ ố ế
là T(n)=O(max(f(n),g(n)))T(n)=O(max(f(n),g(n)))
Ví d :ụ L nh gánệ x:=15x:=15 t n m t h ng th i gian hayố ộ ằ ờ O(1)O(1), L nh ệ
đ c d li uọ ữ ệ READ(x)READ(x) t n m t h ng th i gian hayố ộ ằ ờ O(1)O(1), V y ậ
th i gian th c hi n c hai l nh trên n i ti p nhau ờ ự ệ ả ệ ố ế
là O(max(1,1))=O(1)O(max(1,1))=O(1)
4.2 Qui t c nhânắ
N uế T_1(n)T1(n) và T_2(n)T2(n) là th i gian th c hi n c a hai đo n ờ ự ệ ủ ạ
ch ng trìnhươ P_1P1 và P_2P2 và T_1(n) = O(f(n))T1(n)=O(f(n)), T_2(n) =
O(g(n)T2(n)=O(g(n) thì th i gian th c hi n c a đo n hai đo n ch ng ờ ự ệ ủ ạ ạ ươ
trình đó l ng nhau làồ T(n) = O(f(n).g(n))T(n)=O(f(n).g(n))
4.3 Qui t c t ng quát đ phân tích m t ch ng trìnhắ ổ ể ộ ươ
Th i gian th c hi n c a m i l nh ờ ự ệ ủ ỗ ệ
gán, READREAD, WRITEWRITE là O(1)O(1)
Th i gian th c hi n c a m t chu i tu n t các l nh đ c xác đ nh ờ ự ệ ủ ộ ỗ ầ ự ệ ượ ị
b ng qui t c c ng. Nh v y th i gian này là th i gian thi hành m t ằ ắ ộ ư ậ ờ ờ ộ
l nh nào đó lâu nh t trong chu i l nhệ ấ ỗ ệ
Th i gian th c hi n c u trúc IF là th i gian l n nh t th c hi n l nh ờ ự ệ ấ ờ ớ ấ ự ệ ệ
sau THENTHEN ho c sauặ ELSEELSE và th i gian ki m tra đi u ờ ể ề
ki n. Th ng th i gian ki m tra đi u ki n làệ ườ ờ ể ề ệ O(1)O(1).
Th i gian th c hi n vòng l p là t ng (trên t t c các l n l p) th i ờ ự ệ ặ ổ ấ ả ầ ặ ờ
gian th c hi n thân vòng l p. N u th i gian th c hi n than vòng l p ự ệ ặ ế ờ ự ệ ặ
không đ i thì th i gian th c hi n vòng l p là tích c a s l n l p v i ổ ờ ự ệ ặ ủ ố ầ ặ ớ
th i gian th c hi n thân vòng l p.ờ ự ệ ặ
có thể bạn quan tâm
Nghiên cứu, đánh giá các giải thuật đối sánh chuỗi. Trên cơ sở đó lựa...
25
1.075
555
Thạc sĩ cao học
25
(New)
Tìm hiểu về kỹ thuật Radio over Fiber- Kết hợp kĩ thuật Radio over Fib...
80
1.390
561
Kỹ thuật
80
(New)
Luận văn thạc sỹ kỹ thuật: Tổng quan phân tích các giải pháp nâng cao...
196
884
291
Thạc sĩ cao học
196
(New)
Khái niệm phân tập và kỹ thuật phân tập đa người dùng, kỹ thuật OFDM,...
62
819
599
Kỹ thuật
62
(New)
Kỹ thuật giải thuật trong lập trình và ứng dụng
0
760
317
Lập trình
(New)
Phân tích giá trị nội dung và nghệ thuật của người lái đò sông đà
9
843
318
Giáo án, bài giảng lớp 12
9
(New)
Đồ án: Nghiên cứu, phân tích về kỹ thuật OFDM và hệ thống MIMO
43
867
328
Kỹ thuật
43
(New)
Tìm hiểu về thuật toán và thuật giải
97
2.151
442
Cơ sở dữ liệu
97
(New)
thông tin tài liệu
Trong bài viết này chúng ta sẽ nghiên cứu những vấn đề sau:
• Sự cần thiết phải phân tích các giải thuật
• Thời gian thực hiện chương trình
• Tỷ suất tăng và độ phức tạp của giải thuật
• Tính thời gian thực hiện chương trình
Mở rộng để xem thêm
từ khóa liên quan
tài liệu mới trong mục này
tài liệu hot trong mục này
tài liệu giúp tôi
Nếu bạn không tìm thấy tài liệu mình cần có thể gửi yêu cầu ở đây để chúng tôi tìm giúp bạn!
xem nhiều trong tuần
Giáo trình Quản trị học của Đại học kinh tế quốc dân
Mẫu slide chủ đề âm nhạc
Tâm lý xã hội VÀ Hệ tư tưởng
Tham khảo 12 bài tập nguyên lý thống kê có lời giải
4 đề thi học sinh giỏi Toán lớp 2, có đáp án kèm theo
Các hiệu ứng HTML cho trang web
yêu cầu tài liệu
Giúp bạn tìm tài liệu chưa có
×
