Các qui tắc đánh giá thời gian thực hiện thuật toán potx - Pdf 16

Sau đây là qui tắc cần thiết về ô lớn để đánh giá thời gian thực hiện thuật toán.
Qui tắc tổng : Nếu T
1
(n)=O(f
1
(n)) và T
2
(n) = O(f
2
(n)) thì
T
1
(n) + T
2
(n) = O(max (f
1
(n) , f
2
(n))).
Thật vậy , vì T
1
(n) , T
2
(n) lần lượt là ô lớn của f
1
(n) và f
2
(n) tương ứng do đó tồn tại hằng số c
1
,
c

1
(n) + T
2
(n) ≤ (c
1
+ c
2
) max (f
1
(n), f
2
(n)).
Qui tắc này thường được áp dụng như sau .Giả sử thuật toán của ta được phân thành ba phần tuần tự .
Phần một có thời gian thực hiện T
1
(n) được đánh giá là O(1), phần hai có thời gian thực hiện là T
2
(n) và có
thời gian đánh gía là O(n
2
), phần ba có thời gian thực hiện T
3
(n) có thời gian đánh giá là O(n) .Khi đó thời
gian thực hiện thuật toán là T(n) = T
1
(n) + T
2
(n) + T
3
(n) là O(n

(n))).
4. Nếu S1,S2, ,Sn là các câu lệnh , E là biểu thức có kiểu thứ tự đếm được, và v1,v2, , vn là các giá
trị có cùng kiểu với E thì :
Case E of
v1: S1 ;
v2: S2 ;

vn : Sn;;
end;
là các lệnh.
Lệnh này được gọi là lệnh case.
Đánh giá thời gian thực hiện lệnh case như lệnh if
5. Nếu S là các câu lệnh và E là biểu thức logíc thì
While E do S
Là câu lệnh. Lệnh này được gọi là lệnh while.
Thời gian thực hiện lệnh while được đánh giá : Giả sử thời gian thực hiện lệnh S (thân của lệnh while) là
O(f(n)). Giả sử g(n) là số tối đa các lần thực hiện lệnh S , khi thực hiện lệnh while .Khi đó thời gian thực
hiện lệnh while là O(f(n)g(n)).
Nếu S1, S2, , Sn là các câu lệnh , E là biểu thức logíc thì
Repeat S1, S2, , Sn until E
Là câu lệnh. Lệnh này được gọi là lệnh repeat.
Giả sử , thời gian thực hiện khối begin S1, S2,…Sn end; là O(f(n)). Giả sử g(n) là số tối đa các lần lặp. Khi
đó thời gian thực hiện lệnh repeat là O(f(n),g(n)).
Với S là câu lệnh và E1,E2 là biểu thức cùng một kiểu thứ tự đếm được thì
For i:= E1 to E2 do S là câu lệnh ,và
for i:= E2 downto E1 do S là câu lệnh.
Các câu lệnh này được gọi là lệnh for .
Thời gian thực hiện lệnh for được đánh giá tương tự như thời gian thực hiện lệnh while và lệnh repeat.



Nhờ tải bản gốc

Tài liệu, ebook tham khảo khác

Music ♫

Copyright: Tài liệu đại học © DMCA.com Protection Status