YOMEDIA
Ký thiệu " O lớn " và khái niệm độ phức tạp của thuật toán
Chia sẻ: Đinh Hùng Vũ
| Ngày:
| Loại File: DOC
| Số trang:3
443
lượt xem
94
download
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
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
AMBIENT/
Chủ đề:
Nội dung Text: 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 nn
f ( n) ≥ + ... + n k ≥ + ... + =
2 2 2
f(n) 2 2 2 2 2 22
2 2
22
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ặp
4. Ví dụ:
void Bubble (int a[], int n)
{
int i, j, temp;
{1} for (i=1; i
Thêm tài liệu vào bộ sưu tập có sẵn:
Báo xấu
LAVA
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
Đang xử lý...
Thêm vào BST
Báo xấu
