©FIT-HCMUS 1
Cấu trúc dữ liệu và giải thuật - HCMUS 2016
33
Big-O.
Một số kết quả Big-O quan trọng.
Cấu trúc dữ liệu và giải thuật - HCMUS 2016
34
Khái niệm Big-O lần đầu tiên được đưa ra bởi nhà
toán học người Đức Paul Bachmann vào năm
1892.
Big-O được trở nên phổ biến hơn nhờ nhà toán học
Landau. Do vậy, Big-O cũng còn được gọi là ký
hiệu Landau, hay Bachmann-Landau.
Donald Knuth được xem là người đầu tiên truyền
bá khái niệm Big-O trong tin học từ những năm
1970. Ông cũng là người đưa ra các khái niệm Big-
Omega và Big-Theta.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
©FIT-HCMUS 2
Cấu trúc dữ liệu và giải thuật - HCMUS 2016
35
Cho f và g là hai hàm số từ tập các số nguyên
hoặc số thực đến số thực. Ta nói f(x) là O(g(x))
nếu tồn tại hằng số Cvà ksao cho:
|f(x)| ≤ C |g(x)| với mọi x > k
Cấu trúc dữ liệu và giải thuật - HCMUS 2016
36
Cho f và g là hai hàm số từ tập các số nguyên
hoặc số thực đến số thực. Ta nói f(x) là O(g(x))
nếu tồn tại hằng số Cvà ksao cho:
|f(x)| ≤ C |g(x)| với mọi x > k
• Ví dụ, hàm f(x) = x2+ 3x + 2 là O(x2).
Thật vậy, khi x > 2 thì x < x2và 2 < 2x2
Do đó x2+ 3x + 2 < 6x2.
Nghĩa là ta chọn được C = 6 và k = 2.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
©FIT-HCMUS 3
Cấu trúc dữ liệu và giải thuật - HCMUS 2016
37
Big-O giúp xác định được mối quan hệ giữa
f(x) và g(x), trong đó g(x) thường là hàm ta đã
biết trước. Từ đó ta xác định được sự tăng
trưởng của hàm f(x) cần khảo sát.
Cvà ktrong định nghĩa của khái niệm Big-O
được gọi là bằng chứng của mối quan hệ f(x)
là O(g(x)).
Cấu trúc dữ liệu và giải thuật - HCMUS 2016
38
Big-O phân hoạch được các hàm với các độ
tăng khác nhau. Nếu có hai hàm f(x) và g(x) sao
cho f(x) là O(g(x)) và g(x) là O(f(x)) thì ta nói hai
hàm f(x) và g(x) đó là có cùng bậc.
Ví dụ: f(x) 7x2là O(x2) (chọn k = 0, C = 7).
Do vậy 7x2và x2+ 3x + 2, và x2là 3 hàm có
cùng bậc.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
©FIT-HCMUS 4
Cấu trúc dữ liệu và giải thuật - HCMUS 2016
39
Lưu ý: 7x2cũng là O(x3) nhưng x3không là
O(7x2).
Thật vậy: Nếu x3là O(7x2) thì ta phải tìm được C
và k sao cho
|x3| ≤ C|7x2|
x ≤ 7C với mọi x > k.
Điều này không thể xảy ra vì không thể tìm
được k và C nào như vậy.
Do vậy, trong quan hệ f(x) là O(g(x)), hàm g(x)
thường được chọn là nhỏ nhất có thể.
Cấu trúc dữ liệu và giải thuật - HCMUS 2016
40
1. Hàm đa thức:
f(x) = anxn+ an-1xn-1 + … + a1x + a0
Khi đó f(x) là O(xn).
CuuDuongThanCong.com https://fb.com/tailieudientucntt
©FIT-HCMUS 5
Cấu trúc dữ liệu và giải thuật - HCMUS 2016
41
Nếu f(x) là O(g(x)) thì c.f(x) là O(g(x)) với c là
hằng số.
Cho f1(x) là O(g1(x)) và f2(x) là O(g2(x)).
Khi đó:
Quy tắc tổng:
(f1(x)+f2(x)) là O(max(|g1(x)|, |g2(x)|))
Quy tắc nhân:
(f1(x) * f2(x)) là O(g1(x) * g2(x)).
Cấu trúc dữ liệu và giải thuật - HCMUS 2016
42
CuuDuongThanCong.com https://fb.com/tailieudientucntt