1
22 August 2012
1
Toán rời rạc (1b):
ĐỘ PHỨC TẠP CỦA
THUẬT TOÁN
Ths. Hoàng ThThanh Hà
Khoa Thng kê –Tin hc
Trưng Đi hc Kinh t
Đi hcĐà Nng
22 August 2012
2
N
ộ
i
dung
1. Giới thiệu
2. Định nghĩa
3. Đánh giá thuật toán
2
22 August 2012
3
Giới thiệu
Các thuật toán đượcđánh giá qua 2 chỉtiêu:
–Thời gian: là sốthao tác mà thuật toán thực hiện tương ứng
với kích thước nhập n
–Không gian: là kích thước bộnhớmà thuật toán sửdụng
Ví dụ1: Xét thuật toán tìm sốlớn nhất trong dãy n số
a
1
, a
2
, ..., a
n
.
–Nếu coi mỗi lần so sánh hai sốcủa thuật toán đòi hỏi một
đơn vịthời gian (giây chẳng hạn) thì thời gian thực hiện
thuật toán trong trường hợp xấu nhất là n-1 giây.
–Với dãy 64 số, thời gian thực hiện thuật toán nhiều lắm là 63
giây.
22 August 2012
4
Giới thiệu
Ví dụ2: Thuật toán vềtrò chơi “Tháp Hà Nội”: có ba cọc A, B,
C và 64 cái đĩa, các đĩa có đường kính đôi một khác nhau.
Nguyên tắcđặtđĩa vào cọc là: mỗiđĩa chỉ được chồng lên đĩa
lớn hơn nó. Ban đầu, cả64 đĩađượcđặt chồng lên nhau ởcột
A; hai cột B, C trống. Vấnđề là phải chuyển cả64 đĩađó sang
cột C, lấy cột B làm trung gian, mỗi lần chỉ được di chuyển một
đĩa.
–Gọi Sn là sốlần chuyểnđĩađể chơi xong trò chơi với n đĩa
–Nếu n=1 thì rõ ràng là S
1
=1
–Nếu n>1 thì trước hết chuyển n-1 đĩa bên trên sang cọc B. Sốlần chuyển
n-1 đĩa là S
n-1
. Sau đó ta chuyểnđĩa thứn từcọc A sang cọc C. Cuối cùng,
ta chuyển n-1 đĩa từcọc B sang cọc C (sốlần chuyển là S
n-1
).
–=> sốlần chuyển n đĩa từA sang C là: S
n
=S
n-1
+1+S
n+1
=2S
n-
1
+1=2(2S
n+2
+1)+1=2.2S
n-2
-+2+1=.....=2n-1S
1
+2n-2+...+2+1=2
n
−
−−
−1.
3
22 August 2012
5
Giới thiệu
Thuật toán vềtrò chơi “Tháp Hà Nội” đòi hỏi
2
64
−
−−
−1 lần chuyểnđĩa (xấp xỉ18,4 tỉtỉlần). Nếu
mỗi lần chuyểnđĩa mất 1 giây thì thời gian thực
hiện thuật toán xấp xỉ585 tỉnăm!
Thuật toán trong ví dụ1 có độ phức tạp là n-1
và là một thuật toán hữu hiệu (hay thuật toán
nhanh)
Thuật toán trong ví dụ2 có độ phức tạp là 2
n
−
−−
−1
và đó là một thuật toán không hữu hiệu (hay
thuật toán chậm)
22 August 2012
6
Định nghĩa
Định nghĩa 1: Ta nói hàm f(n) có độ phức tạp
thấp hơn hay bằng hàm g(n) nếu tồn tại hằng số
C>0 và một sốtựnhiên n
0
sao cho:
f(n) ≤
≤≤
≤C. g(n) với∀
∀∀
∀n≥
≥≥
≥n
0
–Ta viết f(n)=O(g(n)) và nói f(n) thoảmãn quan hệ
big-O (hay O lớn) đối với g(n)
–Theo định nghĩa này, hàm g(n) là một hàm đơn giản
nhất có thể được, đại diện cho “sựbiến thiên” của
f(n)
4
22 August 2012
7
Định nghĩa
Ví dụ3: Hàm f(n)= n(n+3)/2 là hàm bậc hai và
hàm bậc hai đơn giản nhất là n
2
. Ta có:
–f(n)= n(n+3)/2 =O(n
2
) vì n(n+3)/2 ≤
≤≤
≤n
2
với mọi n≥
≥≥
≥3
(C=1, n
0
=3).
2
)3(
+
nn
22 August 2012
8
Định nghĩa
Định nghĩa 2: Nếu một thuật toán có độ phức
tạp là f(n) với f(n)=O(g(n)) thì ta cũng nói thuật
toán f(n) có độ phức tạp O(g(n))
–g(n) thường là hàm đơn thức
Ví dụ: f(n)=n
2
+7n, g(n) =n
2
–Ta có f(n)= O(g(n)), ta nói f(n) có độ phức tạp là
O(n
2
)
2
)3(
+
nn
5
22 August 2012
9
Đánh giá thuật toán
Quy ước:
–Lệnh gán, lệnh ghi có độ phức tạp là O(1)
–Lệnh vào ra có độ phức tạp là O(1)
–Lệnh If … else có độ phức tạp là max của 2 nhánh
–Lệnh lặp là sốlần lặp nhân với sốthao tác ởmỗi
bước
–Quy tắc cộng: O(f+g) = max{O(f) + O(g)}
–Quy tắc nhân O(f.g) = O(f). O(g)
2
)3(
+
nn
22 August 2012
10
Đánh giá thuật toán
Ví dụ: thuật toán tìm kiếm tuyến tính giá trị
x
trên mảng A gồm n phần tử.
–Trường hợp tốt nhất: x nằmđầu danh sách, thì độ
phức tạp là bằng O(1)
–Trường hợp xấu nhất: x nằm cuối danh sách hoặc
không tồn tại trong A, thì độ phức tạp là bằng O(n)
2
)3(
+
nn