Tài liệu tham khảo Ký thiệu " O lớn " và khái niệm độ phức tạp của thuật toán | Chủ đề 2: Ký hiệu “ O lớn” và khái niệm độ phức tạp của thuật toán --- --- I. Khái niệm cơ sở: 1. Định nghĩa “O lớn”: Cho 2 hàm f , g : R Ta nói nếu tồn tại M > 0 và sao cho 2. Lưu ý: Ý nghĩa bị chặn khi n đủ lớn Cũng có thể xem , nhiều khi cũng không cần thiết Thông thường về mặt áp dụng thì f , g xác định trên khoảng liên tục (a,+ ) 3. Ký hiệu Với mọi hàm g, ta định nghĩa O(g) = Ví dụ 1: g(n) = f1(n) = n f2(n) = 3n2 Ta có bởi vì: Hay vì Như vậy: Tương tự: Ví dụ 2: g(n) = (n+1)2 f1(n) = n2 (chọn M =4 , n0 = 1) Ví dụ 3: g(n) = 3n3 + 2n2 f1(n) = n3 (chọn M =5 , n0 = 0) 4. Định nghĩa độ phức tạp thuật toán: Gọi f là độ phức tạp của g, ký hiệu f = khi Ví dụ n2 = Mệnh đề o Nếu thì f = O(g) Nếu L = 0 thì g Nếu L thì f = 5. Kỷ thuật “Bỏ bớt phân nửa” : Kỷ thuật thông dụng thường dùng trong khoa học máy tính Ví dụ: f(n) = 1k+2k+3k+ +nk Hiển nhiên Như vậy f = O(nk+1) Chưa biết f = (hay nk+1 = O(f)) Bỏ bớt phân nửa: f(n) II. Cách tính O lớn trong đoạn chương trình cụ thể: 1. Qui tắc cộng: Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2; và T1(n)=O(f(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))) 2. Qui tắc nhân: Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1và P2 và T1(n) = O(f(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)) 3. Qui tắc tổng quát: a. Phép gán, cin, cout : O(1) b. Các chuỗi lệnh tuần tự : Qui tắc cộng c. Cấu trúc if : thời gian lớn nhất giữa các lệnh sau THEN và sau ELSE d. Cấu trúc swich/case : thời gian lớn nhất trong các trường hợp case và default (nếu có) e. Cấu trúc lặp : i. 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 ii. Nếu thời gian thực hiện thân vòng lặp không đổi => tích của số lần lặp với thời gian thực hiện thân vòng lặp 4. Ví dụ: void Bubble (int a[], int n) { int i, j, temp; {1} for (i=1; ia[j]) { {4} temp:=a[j-1]; {5} a[j-1]:=a[j]; {6} a[j]:=temp; } } Cả ba lệnh đổi chỗ {4} {5} {6} tốn O(1) thời gian, do đó lệnh {3} tốn O(1). Vòng lặp {2} thực hiện (n-i) lần, mỗi lần O(1) do đó vòng lặp {2} tốn O((n-i).1)=O(n-i). Vòng lặp {1} lặp (n-1) lần vậy độ phức tạp của giải thuật là:
