Tài liệu tham khảo về Các qui tắc đánh giá thời gian thực hiện thuật toán | 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 T1(n)=O(f1(n)) và T2(n) = O(f2(n)) thì T1(n) + T2(n) = O(max (f1(n) , f2(n))). Thật vậy , vì T1(n) , T2(n) lần lượt là ô lớn của f1(n) và f2(n) tương ứng do đó tồn tại hằng số c1 , c2 ,n1 ,n2 sao cho T1 (n) ≤ c1f1(n) ,T2(n) ≤ c2f2(n) với mọi n ≥ n1 , mọi n≥n2. Đặt n0 = max (n1,n2) . Khi đó, với mọi n ≥ n0 ta có bất đẳng thức sau: T1(n) + T2(n) ≤ (c1 + c2) max (f1(n), f2(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 T1(n) được đánh giá là O(1), phần hai có thời gian thực hiện là T2(n) và có thời gian đánh gía là O(n2), phần ba có thời gian thực hiện T3(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) = T1(n) + T2(n) + T3(n) là O(n2) ,vì n2 = max(1, n2, n). Trong sách báo quốc tế các sách báo thường được trình bày dưới dạng các thủ tục hoặc hàm trong ngôn ngữ tựa Pascal. Để đánh giá thời gian thực hiện thuật toán ta cần biết cách đánh giá thời gian thực hiện các câu lệnh trong Pascal, các câu lệnh trong Pascal được định nghĩa đệ qui như sau: 1. Các phép gán ,đọc , viết , goto là câu lệnh .Các lệnh này được gọi là các lệnh đơn . Thời gian thực hiện các lệnh đơn là O(1). 2. Nếu S1 , S2 , . ,Sn là câu lệnh thì begin S1, S2, ,Sn end là câu lệnh. Lệnh này được gọi là lệnh hợp thành (hoặc khối). Thời gian thực hiện lệnh hợp thành được xác định bởi luật tổng . 3. Nếu S1 ,S2 là các câu lệnh và E là biểu thức logíc thì : If E then S1 else S2 Và if E then S1 là câu lệnh. Các lệnh này được gọi là lệnh if. Đánh giá thời gian thực hiện các lệnh if : Giả sử thời gian thực hiện các lệnh S1,S2, là O(f1(n)) và O(f2(n)) tương ứng .Khi đó thời gian thực hiện lệnh if là : O(max(f1(n),f2(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.
