3.khai niem do phuc tap, vi du
3.Trình bày khái niệm độ phức tạp của giải thuật và phương pháp đánh giá độ phức tạp bằng ký pháp chữ O lớn ? Cho ví dụ minh hoạ ?
Người ta quy ước T(n) với n là số lần thực hiện 1 phép tính để đánh giá độ phức tạp của 1 giải thuật nào đó.
Độ phức tạp của giải thuật A quy ước là T(n) có kí pháp bởi chữ O lớn
T(n) = O(n)
Nếu lim (n>>vô cùng) của T(n)/n = hằng số
Cho giải thuật A1, A2 với độ phức tạp lần lượt là:
T1(n)= O(g)
T2(n)= O(f)
+ Độ phức tạp của giải thuật A= A1+A2 được hiểu theo nghĩa lần lượt thực hiện tuần tự hết giải thuật A1 đến giải thuật A2 thì độ phức tạp của giải thuật A là :
T(n) = O( max{g,f})
+độ phức tạp cả giải thuật A với A=A1xA2 hiểu theo nghĩa quá trình thực hiện theo sơ đồ lặp thì độ phức tạp of giải thuật A
T(n)= O(f.g)
1 số thước đo độ phức tạp :
+ Hằng : O(C)
+Logarit : O(logan)
+Tuyến tính: O(n)
+n.logn: O(n.logan)
+đa thức : O(n^k)
+Lũy thừa : O(a^n)
+giai thừa : n!
VD: Xác định độ phức tạp của giải thuật tính gt tb của 1 dãy số không âm a1,a2…an
Phép toán số lần thực hiện
1.Đọc n 1
2.Đặt i=1 1
3. S=S+a[i] n
4. i:=i+1 n
5. i<=n n
6. tb=S/n 1
7.In tb 1
Tổng 3n+4
Suy ra độ phức tạp của giải thuật A : T(n)= 3n+4
T(n)= O(n)
Bạn đang đọc truyện trên: Truyen2U.Pro