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
gf 
nếu tồn tại M > 0 và
Ν∈
0
n
sao cho
0
,)(.)( nnngMnf ≥∀≤
2. Lưu ý :
 Ý nghĩa
g
f
bị chặn khi n đủ lớn
 Cũng có thể xem
Ν∈
M
, nhiều khi cũng không cần thiết
Nn ∈
0
 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,
+
∞

1
≥∀≤ nngnf
Như vậy:
)(
1
gOf ∈
Tương tự:
)(
2
gOf ∈
Ví dụ 2:
g(n) = (n+1)
2
f
1
(n) = n
2
(chọn M =4 , n
0
= 1)
Ví dụ 3:
g(n) = 3n
3
+ 2n
2
f
1
(n) = n
3
(chọn M =5 , n

Lim
x
=
∞→
)(
)(
thì f = O(g)
 Nếu L = 0 thì g
)( fO≠
 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) = 1
k
+2
k
+3
k
+…+n
k
Hiển nhiên
1
)(
+
=++≤
kkk
nnnnf














++














≥++


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
Nhận xét:
 Ký hiệu thường dùng f = O(g) khi muốn nói
)(gOf ∈
(đôi
khi dấu = lại gây hiểu nhầm)
 Không dùng cách ghi O(g) = n
Nhận xét:
• O(cf(n)) = O(f(n))
• O(c) = 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ụ :