Bài giảng C căn bản - Chương 5: Thuật toán và độ phức tạp của thuật toán

Chương 5  Thuật toán và độ phức tạp của thuật toán 
2 
5.1. Tổng quan về thuật toán 
Thuật toán là một dãy các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết một vấn đề. 
Thuật toán tìm ước số chung lớn nhất của hai số nguyên. 
	Input: m, n nguyên dương. 
	Output: g, ước chung lớn nhất của m và n. 
	Bước 1: tìm r, phần dư của phép chia m cho n. 
	Bước 2: 	Nếu r = 0 thì g := n và dừng thuật toán. 
	Ngược lại, (r 0) m := n; n := r; 
	Quay lại bước 1. 
3 
5.2. Các đặc trưng của thuật toán. 
Input. Là các giá trị cần đưa vào (có thể là rỗng) khi cần thực hiện thuật toán 
Output. Là các giá trị có quan hệ hoàn toàn xác định với các dữ liệu vào và là kết quả của sự thực hiện thuật toán 
Tính xác định. Mỗi bước của thuật toán cần phải được mô tả một cách chính xác. 
Tính khả thi. Các phép toán trong các bước của thuật toán phải đủ đơn giản . 
Tính dừng. Thuật toán phải dừng sau hữu hạn bước ứng với mọi bộ dữ liệu thõa mãn điều kiện của dữ liệu vào. 
4 
5.3. Đặc tả thuật toán  
Đặc tả thuật toán cần chỉ ra các đặc điểm sau : 
	1. Các đối tượng và phương tiện của thuật toán cần sử dụng (nhập). 
	2. Điều kiện ràng buộc (nếu có) trên các đối tượng và phương tiện đó. 
	3. Các sản phẩm ,kết quả (xuất). 
	4. Các yêu cầu trên sản phẩm, kết quả. Thường xuất hiện dưới dạng quan hệ giữa kết quả và các đối tượng, phương tiện sử dụng. 
5 
5.3. Các vấn đề liên quan đến thuật toán. 
Thiết kế thuật toán: Tức là làm thế nào để tìm ra một thuật toán cho một bài toán đặt ra 
Tính đúng đắn của thuật toán: Ta cần phải chứng minh thuật toán làm ra phải cho một kết quả đúng với mọi dữ liệu vào hợp lệ. 
Phân tích thuật toán: Tức là việc đánh giá độ phức tạp của một thuật toán. 
6 
5.4. Độ phức tạp của thuật toán 
Độ phức tạp của thuật toán: là lượng thời gian và bộ nhớ cần thiết để thực hiện thuật toán. Chúng ta sẽ quan tâm đến: 
Thời gian tối thiểu để thực hiện. 
Thời gian tối đa để thực hiện thuật toán. 
Thời gian trung bình khi thực hiện thuật toán. 
7 
5.4. Độ phức tạp của thuật toán 
Tính hiệu quả: Thông thường ta dựa vào hai tiêu chuẩn sau: 
Thuật toán đơn giản, dễ hiểu, dễ cài đặt. 
Thuật toán sử dụng tiết kiệm nhất các nguồn tài nguyên của máy tính và chạy nhanh nhất có thể được: 
Dung lượng không gian nhớ cần thiết để lưu trữ các dữ liệu vào, các kết quả tính toán trung gian và các kết quả của thuật toán. 
Thời gian cần thiết để thực hiện thuật toán. (thời gian chạy) 
8 
5.4. Độ phức tạp của thuật toán 
Có hai cách để đánh giá thời gian thực hiện của một thuật toán: 
Phương pháp thử nghiệm: 
Các dữ liệu vào. 
Chương trình dịch. 
Tốc độ thực hiện của các phép toán của máy tính. 
Phương pháp lý thuyết: cỡ dữ liệu vào . 
9 
5.4. Độ phức tạp của thuật toán 
Bài toán tháp Hà Nội. 
	Ta tính số lần thực hiện việc chuyển đĩa từ cọc này sang cọc khác (không đặt đĩa to lên đĩa nhỏ) để chuyển từ cọc A sang cọc B. Gọi số đó là F(n), ta có: 
	F(1) = 1; 
	F(n) = 2F(n-1) + 1; với n > 1 
	Một cách quy nạp, ta có F(n) = 2n-1. 
	Với n = 64 ta có F(n) = 2 64 – 1 lần chuyển, giả sử mỗi lần chuyển là 1 giây, vậy ta có 5*10 11 năm thực hiện 
10 
5.4. Độ phức tạp của thuật toán 
11 
5.5. Quy tắc đánh giá thời gian thuật toán 
Qui tắc tổng. Nếu T1(n) = O(f1(n)) và T2(n) = O(f2(n)) thì T1(n) + T2(n) = O(max{f1(n),f2(n)}) 
Thời gian thực hiện lệnh đơn: gán (không chưa lời gọi hàm), đọc, viết, goto là O(1). 
Thời gian thực hiện câu lênh phức. được xác định qua các câu lệnh thành phần. 
Lệnh if. Ví dụ	if E then S1 else S2. Và giả sử thời gian thực hiện các lện S1 và S2 là O(f1(n)) và O(f2(n)). Khi đó thời gian thực hiện lệnh if là O(max{f1(n),f2(n)}). 
12 
5.5. Quy tắc đánh giá thời gian thuật toán 
Lệnh case. Được đánh giá như lệnh if. 
Lệnh while. 
	Ví dụ: while E do S. Giả sử thời gian thực hiện của lệnh S là O(f(n)). Và giả sử g(n) là số tối đa lần thực hiện lệnh S. Thì khi đó thời gian thực hiện lệnh while là: O(f(n))g(n). 
Lệnh repeat. Được đánh giá như lệnh while. 
Lệnh for. Được đánh giá như lệnh repeat, while. 
13