Giới thiệu thuật toán

TS. Phạm Văn Cảnh

1
Thuật toán và độ phức tạp của thuật toán

Phạm Văn Cảnh 2

 Thuật toán
Thuật toán (còn gọi là giải thuật):
▪ Là một tập hợp hữu hạn của các chỉ thị hay phương
cách được định nghĩa rõ ràng;
▪ Để hoàn tất một số sự việc từ một trạng thái ban đầu
cho trước.

Ví dụ: giải phương trình bậc nhất P(x): ax + b = c

Nếu a = 0
b = c thì P(x) có nghiệm bất kì
b ≠ c thì P(c) vô nghiệm
Nếu a ≠ 0
P(x) có duy nhất một nghiệm x = (c - b)/a

Phạm Văn Cảnh 3

 Các đặc trưng của thuật toán

▪ Đầu vào, ra;

▪ Tính chính xác;
▪ Tính rõ ràng;
▪ Tính khách quan;
▪ Tính phổ dụng;
▪ Tính hữu hạn.

Phạm Văn Cảnh 4

 Biểu diễn thuật toán

▪ Phương pháp liệt kê

• Sử dụng ngôn ngữ tự nhiên để liệt kê từng bước;
▪ Ví dụ: Giải phương trình a𝑥 2 + 𝑏𝑥 + 𝑐 = 0 (a≠ 0).
Bước 1: Nhập a, b,c;
Bước 2: Kiểm tra a≠ 0? Nếu a=0 quay lại bước 1;
Bước 3: Tính ∆= 𝑏 2 − 4ac;
Bước 4: Nếu ∆< 0: phương trình vô nghiệm;
−𝑏
Bước 5: Nếu ∆= 0: 𝑥1 = 𝑥2 =
2𝑎
−𝑏− ∆ −𝑏+ ∆
Bước 6: Nếu ∆> 0: 𝑥1 = ; 𝑥2 =
2𝑎 2𝑎
Bước 7: Thông báo các nghiệm
Bước 8: Kết thức thuật toán
Phạm Văn Cảnh 5
 Biểu diễn thuật toán

▪ Sơ đồ khối (lưu đồ khối):

• Sử dụng các khối để biểu diễn các bước của thuật toán

Phạm Văn Cảnh 6

 Sơ đồ khối

▪ Khối thao tác

• Biểu diễn bằng hình chữ nhật;
• Ghi các câu lệnh cần thực hiện trong trong khối;
• Có thể viết chung nhiều lệnh trong khối

Khối thao tác;

Phạm Văn Cảnh 7

 Sơ đồ khối

▪ Khối điều kiện

• Biểu diễn bằng hình thoi;
• Ghi điều kiện trong quá trình tính toán.

Khối
Điều kiện

Phạm Văn Cảnh 8

 Sơ đồ khối

▪ Khối bắt đầu, kết thúc:

• Biểu diễn bằng hình elip
• Thể hiện bắt đầu hoặc kết thúc thuật toán;

Khối bắt đầu,

kết thúc

Phạm Văn Cảnh 9

 Sơ đồ khối

▪ Cung
• Biểu diễn bằng đoạn thẳng có hướng;
• Biểu diễn đường đi, chiều của thuật toán.

Cung

Phạm Văn Cảnh 10

 Sơ đồ khối
▪ Ví dụ:
▪ Sơ đồ khối giải
phương trình bậc
hai

Phạm Văn Cảnh 11

 Một số thuật toán thường gặp

▪ Thuật toán đệ quy (recurse algorithm)

▪ Thuật toán quy hoạch động (Dynamic
programming).
▪ Thuật toán phân tán (Distributed algorithm).
▪ Thuật toán song song (Parallel alrorithm).
▪ Thuật toán gần đúng
• Thuật toán Heuristic (Heuristic algorithm)
• Thuật toán xấp xỉ (Approximation algorithm)
• Thuật toán tiến hóa (Evolution algorithm)
• Etc..

Phạm Văn Cảnh 12

 Độ phức tạp của thuật toán

▪ Các yếu tố đánh giá tính hiệu quả của thuật toán:
• Số phép tính mà thuật toán đó thực hiện.
• Lượng bộ nhớ đã dùng

Thời gian thực hiện thuật toán

→ Độ phức tạp của thuật toán

Phạm Văn Cảnh 13

 Độ phức tạp của thuật toán

▪ Thời gian chạy thuật toán:

• Phụ thuộc vào kích cỡ dữ liệu đầu vào (gọi là n);
→ Có thể đánh giá theo một hàm T(n).
T(n)= Số lượng phép toán sơ cấp cần phải thực hiện (số
học, logic, so sánh).

Trong thực tế không thể tính toán chính xác hàm T(n) mà
chỉ có thể tìm ra một ước lượng đủ tốt, theo
▪ Cận trên: O(n): O-lớn (big-O);
▪ Cận dưới: Ω(𝑛) (Ô-mê-ga);
▪ Trung bình : Θ(𝑛) (Thê-ta).

Phạm Văn Cảnh 14

 Hàm O(.)

▪ Mục đích ước lượng:

• Lấy chặn trên số phép toán cần dùng.
▪ Ta nói T(n) là một O(f(n)) nếu, tồn tại một số
dương C>0 và 𝑛0 sao cho:
T(n)≤C.f(n),với mọi n≥ 𝑛0 .
▪ Ý nghĩa: Số phép toán cần thực hiện trong trường
hợp xấu nhất.

▪ Ví dụ: Cho T(n)=5𝑛3 + 2𝑛2 + 13𝑛 + 6.

Ta có: T(n)≤ 5𝑛3 +2𝑛3 +13𝑛3 +6𝑛3 ≤ 26𝑛3 .
→T(n)=O(𝑛3 ) (C=26).

Phạm Văn Cảnh 15

 Hàm O(.)

▪ Độ phức tạp hằng số: O(1)

• Số phép tính không phụ thuộc vào dữ liệu đầu vào.
▪ Độ phức tạp tuyến tính: O(n)
• Số phép tính tỷ lệ thuận với dữ liệu đầu vào.
▪ Độ phức tạp đa thức: O(P(n))
• Trong đó P(n) là đa thức bậc hai trở lên
▪ Độ phức tạp logarit: O(logn)
▪ Độ phức tạp hàm mũ: O(2𝑛 )

Phạm Văn Cảnh 16

So sánh một số độ phức tạp theo O

Phạm Văn Cảnh 17

 Hàm Θ(.)

▪ Mục đích ước lượng:

• Lấy chặn giữa số phép toán cần dùng.
▪ Ta nói T(n) là một Θ(f(n)) nếu, tồn tại hai số 𝐶1 , 𝐶2
và 𝑛0 sao cho:
𝐶1 .f(n) ≤ T(n)≤ 𝐶2 .f(n), với mọi n≥ 𝑛0 .
▪ Ý nghĩa: Số phép toán cần thực hiện trong trường
hợp trung bình.

▪ Ví dụ: Cho T(n)=5𝑛3 + 2𝑛2

Ta có: 5𝑛3 ≤T(n)≤ 5𝑛3 +2𝑛3 ≤ 7𝑛3 ,
→T(n)= Θ(𝑛3 ) (𝐶1 =5, 𝐶2 =7).

Phạm Văn Cảnh 18

 Hàm Ω(.)

▪ Mục đích ước lượng:

• Lấy chặn dưới số phép toán cần dùng.
▪ Ta nói T(n) là một Ω(f(n)) nếu, tồn tại một số
dương C>0 và 𝑛0 sao cho:
T(n)≥C.f(n), với mọi n≥ 𝑛0 .
▪ Ý nghĩa: Số phép toán cần thực hiện trong trường
hợp tốt nhất.

▪ Ví dụ: Cho T(n)=5𝑛3 + 2𝑛2 + 13𝑛 + 6.

Ta có: T(n)≥ 5𝑛3
→T(n)= Ω(𝑛3 ) (C=5).

Phạm Văn Cảnh 19

So sánh O, Ω và Θ

Phạm Văn Cảnh 20

 Chú ý

▪ Đánh giá T(n) có thể cùng theo một hàm theo

O(.); Ω, Θ.
• Ví dụ: T(n)=5𝑛3 + 2𝑛2 + 13𝑛 + 6. là O(𝑛3 ); Ω(𝑛3 ), Θ(𝑛3 ).
▪ Nếu dữ liệu đầu vào có nhiều chiều→ các hàm
O(.); Ω, Θ đánh giá theo các chiều đó.
• Ví dụ: đối với đồ hị G có m cạnh và n đỉnh, thuật toán
duyệt theo chiều sâu là O(m+n).

Phạm Văn Cảnh 21

 Các quy tắc xác định độ phức tạp

▪ Quy tắc lấy cực đại (max)

T(n)=O(f(n)+g(n))=O(max{f(n),g(n)}).
▪ Quy tắc cộng:
Nếu 𝑇1 =O(f(n)); 𝑇2 =O(g(n)) thì 𝑇1 (n)+ 𝑇2 (n)=O(f(n)+g(n))
▪ Quy tắc nhân:
Nếu 𝑇1 (n)=O(f(n)) và f(n) = O(g(n)) thì độ phức tạp sẽ là
O(g(n).f(n))

Phạm Văn Cảnh 22

 Một số tính chất

▪ Hệ quả: Θ(f(n))⊂O(f(n))
▪ Định lý:
Nếu T(n)=Θ(f(n))⟺ T(n)=Ω(f(n)) và T(n)=𝑂(f(n)).
▪ Chuyển đổi:

Phạm Văn Cảnh 23

 Bài tập

1. Chứng minh rằng Θ(f(n)+g(n))=max{f(n),g(n)}

2. Chứng minh rằng với mọi số thực a,b (b>0) thì:
(𝑛 + 𝑎)𝑏 = Θ(𝑛𝑏 )

Phạm Văn Cảnh 24