Ký thiệu O lớn và khái niệm độ phức tạp của thuật toán

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
Nội dung trích xuất từ tài liệu:
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 f f g nếu tồn tại M > 0 và n0 ∈ Ν sao cho f (n) ≤ M . g (n) , ∀n ≥ n0 2. Lưu ý: f  Ý nghĩa bị chặn khi n đủ lớn g  Cũng có thể xem M ∈ Ν , nhiều khi cũng không cần thiết n0 ∈ N  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,+ ∞ ) ⊂ R 3. Ký hiệu Với mọi hàm g, ta định nghĩa O(g) = { f / f f g } Ví dụ 1: 1 g(n) = n2 2000 f1(n) = n f2(n) = 3n2 Ta có { f 1 f g } bởi vì: f 1 (n) ≤ 1. g (n) , ∀n ≥ 2000 Hay vì f1 (n) ≤ 2000. g (n) , ∀n ≥ 1 Như vậy: f1 ∈ O( g ) Tương tự: f 2 ∈ O( g ) 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) 1 Nhận xét:  Ký hiệu thường dùng f = O(g) khi muốn nói f ∈ O(g ) (đôi khi dấu = lại gây hiểu nhầm)  Không dùng cách ghi O(g) = n 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 = Θg khi  f = O( g )   g = O( f ) 1 Ví dụ n2 = Θ( n2 ) 2000 • Mệnh đề f ( x) o Nếu Lim = L thì f = O(g) x →∞ g ( x )  Nếu L = 0 thì g ≠ O( f )  Nếu L ≠ 0 thì f = Θ(g ) 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 k +1 Hiển nhiên f (n) ≤ n + ... + n = n k k Như vậy f = O(nk+1) Chưa biết f = Θ(n k +1 ) (hay nk+1 = O(f)) Bỏ bớt phân nửa: 2 2 2 k n  n n nn f ( n) ≥     + ... + n k ≥     + ... +     =    2   2   2  f(n)     2 2 2 2 2   22 2  2  22 n 2 lan  II. Cách tính O lớn trong đoạn chương trình cụ thể: Nhận xét: • O(cf(n)) = O(f(n)) • O(c) = O(1) 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) 2 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ặp4. Ví dụ: void Bubble (int a[], int n) { int i, j, temp; {1} for (i=1; i ...