TAILIEUCHUNG - 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 | 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à:

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.