Bài giảng Cấu trúc dữ liệu - Chương 11: Độ phức tạp (Complexity) trình bày về khái niệm thuật toán, các tính chất cơ bản của thuật toán, độ phức tạp của thuật toán, độ phức tạp về không gian, độ phức tạp về thời gian,..
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu: Chương 11 - Nguyễn Xuân Vinh
- GV: NGUYỄN XUÂN VINH
CẤU TRÚC DỮ LIỆU
DATA STRUCTURES
[214331]
ĐỘ PHỨC TẠP
MÔN: CẤU TRÚC DỮ LIỆU
(Complexity)
Nguyễn Xuân Vinh
nguyenxuanvinh@hcmuaf.edu.
6/12/14
vn
/XX
1
- GV: NGUYỄN XUÂN VINH
Khái niệm
•
Thuật toán (Algorithm) là một dãy hữu hạn các bước có thể thực
thi được mà theo đó ta đạt được lời giải của bài toán.
•
Từ Algorithm bắt nguồn từ nhà toán học Ả Rập Al-Khwārizmī
•
Thuật toán giải phương trình bậc 2, thuật toán tìm số lớn nhất
trong dãy số, thuật toán sắp xếp…
MÔN: CẤU TRÚC DỮ LIỆU
6/12/14
/XX
2
- GV: NGUYỄN XUÂN VINH
Ví dụ
•
Mô tả giải thuật tìm phần tử lớn nhất trong dãy hữu hạn các
phần tử
–
B1: Đặt giá trị cực đại tạm thời (max) là phần tử đầu tiên của
dãy
–
B2: Nếu số kế tiếp lớn hơn max thì gán giá trị max = số đó
MÔN: CẤU TRÚC DỮ LIỆU
–
B3: Lặp lại bước 2 nếu còn phần tử trong dãy
–
B4: Dừng khi không còn phần tử trong dãy, số max lúc này là
phần tử lớn nhất của dãy
6/12/14
/XX
3
- GV: NGUYỄN XUÂN VINH
Khái niệm
MÔN: CẤU TRÚC DỮ LIỆU
Dữ liệu nhập (input) Dữ liệu xuất (output)
Dãy thao tác
6/12/14
/XX
4
- GV: NGUYỄN XUÂN VINH
Các tính chất cơ bản của thuật toán
•
Tính xác định (rõ ràng, xác định).
•
Tính hữu hạn (dừng).
•
Tính đúng đắn.
•
Tính tổng quát: phải áp dụng được cho 1 họ các vấn đề
•
Đầu vào
MÔN: CẤU TRÚC DỮ LIỆU
•
Đầu ra
6/12/14
/XX
5
- GV: NGUYỄN XUÂN VINH
Độ phức tạp của thuật toán
MÔN: CẤU TRÚC DỮ LIỆU
Thời gian (số thao tác)
Độ phức tạp
Dữ liệu nhập của thuật toán
Không gian
6/12/14
/XX
6
- GV: NGUYỄN XUÂN VINH
Độ phức tạp của thuật toán
•
Thời gian mà máy tính khi thực hiện một thuật toán phụ thuộc
vào:
–
Bản thân thuật toán đó.
–
Máy tính đang thực thi thuật toán.
Đánh giá hiệu quả của một thuật toán có thể:
MÔN: CẤU TRÚC DỮ LIỆU
•
–
Xét số các phép tính phải thực hiện khi thực hiện thuật toán
này.
6/12/14
/XX
7
- GV: NGUYỄN XUÂN VINH
Độ phức tạp của thuật toán
•
Độ phức tạp về không gian
•
Độ phức tạp về thời gian
•
Độ phức tạp về giải thuật
MÔN: CẤU TRÚC DỮ LIỆU
6/12/14
/XX
8
- GV: NGUYỄN XUÂN VINH
Độ phức tạp về không gian
•
Chiếm tài nguyên của máy
–
Bộ nhớ
–
Sử dụng CPU
–
Băng thông
MÔN: CẤU TRÚC DỮ LIỆU
–
…
•
VD: heap sort nếu dùng heap mà không dùng arraytốn bộ nhớ
6/12/14
/XX
9
- GV: NGUYỄN XUÂN VINH
Độ phức tạp về thời gian
•
Tính hiệu quả của thuật toán được tính bằng phương pháp thực
nghiệm thông qua các bộ dữ liệu thử
–
Phụ thuộc vào ngôn ngữ lập trình
–
Trình độ, kỹ năng của người viết
Phần cứng máy tính dùng để thử nghiệm
MÔN: CẤU TRÚC DỮ LIỆU
–
–
Sự phức tạp của việc xây dựng một bộ dữ liệu thử
6/12/14
/XX
10
- GV: NGUYỄN XUÂN VINH
Độ phức tạp về giải thuật
•
Mang tính hình thức
•
Phép đo độc lập với máy tính, ngôn ngữ lập trình, người lập trình
hay những tiểu tiết: tăng giảm, chỉ số vòng lặp, sự khởi gán,…
•
Thời gian thực thi của giải thuật sẽ tăng theo kích thước dữ liệu,
thời gian này sẽ tỷ lệ các thao tác cơ sở
MÔN: CẤU TRÚC DỮ LIỆU
•
Độ phức tạp thuật toán là một hàm phụ thuộc đầu vào
6/12/14
/XX
11
- GV: NGUYỄN XUÂN VINH
Độ phức tạp của thuật toán
•
Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ
của bài toán, tức là độ lớn của đầu vào.
•
Trong thực tiễn, chỉ cần biết một ước lượng đủ tốt của chúng.
•
Để ước lượng độ phức tạp của một thuật toán ta thường dùng
khái niệm big-O
MÔN: CẤU TRÚC DỮ LIỆU
6/12/14
/XX
12
- GV: NGUYỄN XUÂN VINH
Những thao tác cơ sở
•
Là các phép toán tham gia trực tiếp vào quá trình xử lý
•
Ví dụ
–
Phép so sánh
–
Phép chuyển dời
MÔN: CẤU TRÚC DỮ LIỆU
–
Phép toán số học,..
•
Trong các giải thuật sắp xếp thì các phép toán cơ sở là so sánh và
chuyển dời
6/12/14
/XX
13
- GV: NGUYỄN XUÂN VINH
Độ phức tạp của thuật toán (tt)
Thời gian (số thao tác)
Thuật toán 1
MÔN: CẤU TRÚC DỮ LIỆU
Thuật toán 2
Thuật toán 3
6/12/14
/XX
Dữ liệu nhập
14
- GV: NGUYỄN XUÂN VINH
Độ phức tạp của thuật toán (tt)
•
Thời gian tối thiểu (trường hợp tốt nhất).
•
Thời gian tối đại (trường hợp xấu nhất).
•
Thời gian trung bình.
•
Ta thường dùng các ký hiệu sau để mô tả cho độ phức tạp thuật
toán
MÔN: CẤU TRÚC DỮ LIỆU
–
Bậc big-O: chặn trên, trường hợp tốt nhất
–
Bậc big-Ω: chặn dưới, trường hợp xấu nhất
–
Bậc Θ (bậc Theta): chặn 2 đầu, trung bình
6/12/14
/XX
15
- GV: NGUYỄN XUÂN VINH
Ký hiệu O
•
Cho f, g là 2 hàm thực xác định trong N. Khi đó ta viết
f(n) = O(g(n))
Nếu C>0, kN, nN, n≥k |f(n)| ≤ C.|g(n)|
MÔN: CẤU TRÚC DỮ LIỆU
Với n là độ lớn đầu vào:
–
Bài toán giai thừa: n là số cần tính giai thừa
–
Bài toán sai phân: n là số chữ số có nghĩa cần đạt được
–
Các phép tính trên ma trận: n là số hàng hoặc số cột của ma
trận
6/12/14
/XX
16
- GV: NGUYỄN XUÂN VINH
Ký hiệu O (tt)
•
3n = O(15n) do n > 0, 3n 115n.
•
15n = O(3n) do n > 0, 15n 53n.
•
3n và 15n đều = O(n)?
•
n2 = O(n3) do n > 1, n2 < n3.
•
f(n) = log(n!), g(n) = n.log(n). Ta có:
MÔN: CẤU TRÚC DỮ LIỆU
n! = 1.2.....n n.n.....n = nn
log(n!) log(nn) = n.log(n)
log(n!) = O(n.log(n)) (f(n) = O(g(n))
6/12/14
/XX
17
- GV: NGUYỄN XUÂN VINH
Ký hiệu O (tt)
•
f(n) = n2 + 100n + 100 = O(n2)?
•
f(n) = n2 + 200n + 150 = O(n2)?
•
f(n) = n3 + 10n + 12 = O(n3)?
MÔN: CẤU TRÚC DỮ LIỆU
6/12/14
/XX
18
- GV: NGUYỄN XUÂN VINH
Định lý 1
Nếu f(n) là một đa thức bậc k theo n:
f(n) = aknk + ak-1nk-1 + . . . + a1n + a0, với ak ≠ 0,
thì ta có f(n) = O(nk).
MÔN: CẤU TRÚC DỮ LIỆU
6/12/14
/XX
19
- GV: NGUYỄN XUÂN VINH
Thí dụ
n
n (n + 1)
∑ k=
2
= O( n 2 )
MÔN: CẤU TRÚC DỮ LIỆU
k =1
n
∑ k 2 = 12 + 2 2 + ... + n 2 ≤ n 2 + 2 + ... n 2 = n 3
k =1
n +
n
n
⇒ ∑k 2
= O( n )
3
6/12/14
k =1
/XX
20
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
