Bài giảng Cơ sở lập trình nâng cao - Chương 1: Độ phức tạp của thuật toán - Tôn Quang Toại

CƠ SỞ LẬP TRÌNH NÂNG CAO 
Biên soạn: Ths.Tôn Quang Toại 
TonQuangToai@yahoo.com 
TPHCM, NĂM 2013 
TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC TP.HCM 
KHOA CÔNG NGHỆ THÔNG TIN 
Mục tiêu môn học 
Mục tiêu cần đạt được 
- Nắm vững một số phương pháp Thiết kế thuật toán để giải bài toán tin học 
- Nắm vững một số phương pháp Tối ưu hóa chương trình 
Nội dung môn học 
Chương 1: Độ phức tạp của thuật toán 
Chương 2: Ôn tập kỹ thuật xử lý File – Mảng – Xâu ký tự 
Chương 3: Lập trình Đệ quy 
Chương 4: Phương pháp Quay lui 
Chương 5: Phương pháp Nhánh cận 
Chương 6: Phương pháp Chia để trị 
Chương 7: Phương pháp Tham lam 
Chương 8: Phương pháp Quy hoạch động 
Chương 9: Phương pháp Hình học 
Chương 10: Tối ưu hóa chương trình 
Tài liệu tham khảo 
Books 
Vũ Đình Hòa, Đỗ Trung Kiên, “ Thuật toán và độ phức tạp của thuật toán ”, NXB ĐHSP, 2007 
Steven S. Skiena, “ The Algorithm Design Manual ”, Springer , 2008 
Art Lew, Holger Mauch, “ Dynamic Programming – A Computational Tool ”, Springer, 2007 
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “ Introduction to Algorithms ”, 2009 
Jon Bentley, “ Writing Efficient Programs ”, Prentice-Hall, 1982 
Jon Bentley, “ Programming Pearls ”, Addison Wesley, 2000 
ĐỘ PHỨC TẠP CỦA THUẬT TOÁN 
Chương 1 
Nội dung 
Độ phức tạp của thuật toán 
Ước lượng độ phức tạp của thuật toán 
ĐỘ PHỨC TẠP CỦA THUẬT TOÁN 
Thời gian thực hiện thuật toán 
Phân tích thuật toán: Phân tích thuật toán là xác định lượng tài nguyên cần thiết để thực thi thuật toán: 
Thời gian thực hiện thuật toán 
Bộ nhớ cần thực hiện thuật toán 
Tiêu chí thường được dùng để đánh giá thuật toán là thời gian thực hiện thuật toán . 
Thời gian thực hiện thuật toán 
Mục tiêu của phân tích thuật toán 
So sánh để chọn ra thuật toán nào chạy nhanh nhất 
Tìm những yếu điểm của thuật toán để Cải tiến thuật toán tốt hơn 
2 cách “đo” thời gian thực hiện của thuật toán 
Thời gian thực hiện thực tế 
Thời gian thực hiện lý thuyết (Phân tích thuật toán) 
Thời gian thực hiện thuật toán 
Thời gian thực hiện thực tế: Dựa trên thực tế khi chạy các thuật toán được tình bằng (mili second, second, minute, hour, day) 
Kết luận: Thuật toán nào nhanh, thuật toán nào chậm 
Thời gian thực hiện thuật toán 
Thời gian thực hiện thực tế phụ thuộc vào nhiều yếu tố: 
Dữ liệu vào: 
Kích thước dữ liệu 
Đặc điểm của dữ liệu 
Tốc độ của máy tính 
Ngôn ngữ lập trình 
Chương trình dịch cho ngôn ngữ lập trình 
Hệ điều hành để thực hiện chương trình 
Thời gian thực hiện thuật toán 
Thời gian thực hiện thực tế: Dựa trên thực tế khi chạy các thuật toán được viết trên: 
Cùng ngôn ngữ lập trình, cùng trình biên dịch 
Cùng hệ thống máy tính 
Cùng bộ dữ liệu vào chuẩn 
Kết luận: Thuật toán nào nhanh, thuật toán nào chậm 
Thời gian thực hiện thuật toán 
Thời gian thực hiện lý thuyết: Dựa vào 
Số phép toán cơ bản trong thuật toán sẽ được thực hiện bao nhiêu lần 
Kích thước dữ liệu vào 
Kết luận  + Thuật toán nào nhanh, thuật toán nào chậm + Tìm ra những nơi cần cải tiến thuật toán 
Thời gian thực hiện thuật toán 
Phép toán cơ bản: Một phép toán được gọi là cơ bản nếu thời gian thực hiện của nó bị chặn trên bởi một hằng số (chỉ phụ thuộc cách cài đặt được sử dụng – ngôn ngữ lập trình, máy tính, ). 
Ví dụ: 
+, -, *, / 
Các phép so sánh: >, =, <=, ==, != 
Phép gán: =, +=,  
Đọc file, ghi file 
cout, cin, printf, scanf 
Thời gian thực hiện thuật toán 
Định nghĩa [Thời gian thực hiện thuật toán]: Gọi T(n) là số phép toán cơ bản khi thực hiện thuật toán với kích thước dữ liệu vào n. T(n) được gọi là thời gian thực hiện thuật toán. 
Chú ý: Thuật toán có nhiều loại phép toán cơ bản nên chúng ta có thể thực hiện đánh theo một trong hay cách: 
Đánh giá thời gian chạy trên từng loại phép toán 
Tổng hợp các phép toán và gán trọng số cho từng phép toán 
Xem các phép toán là như nhau 
Thời gian thực hiện thuật toán 
Ví dụ: Tìm thời gian thực hiện của thuật toán 
// Thuật toán tính tổng S=a[0]+a[1]++a[n-1]{1} s = 0;{2} for (i=0; i<n; i++){3}	s = s + a[i]; 
Thời gian thực hiện thuật toán 
Ví dụ: Tìm thời gian thực hiện của thuật toán 
// Thuật toán tìm max{1} max = a[0];{2} for (i=1; i<n; i++){3}	 if (max < a[i]){4}	max=a[i]; 
Nhận xét: Số lần thực hiện của Câu lệnh {4} phụ thuộc vào biểu thức điều kiện trong câu lệnh {3} hay bộ dữ liệu input 
T(n)=...? 
Thời gian thực hiện thuật toán 
3 trường hợp đánh giá thời gian thực hiện thuật toán 
Trường hợp xấu nhất (worst case): T(n) là thời gian lớn nhất khi thực hiện thuật toán với mọi bộ dữ liệu kích thước n 
Trường hợp tốt nhất (best case): T(n) là thời gian ít nhất khi thực hiện thuật toán với mọi bộ dữ liệu kích thước n 
Trường hợp trung bình (average case): Dữ liệu tuân theo 1 phân bố xác suất nào đó. Giả sử P(input) là xác suất dữ liệu input xuất hiện, khi đó thời gian trung bình của thuật toán là 
Thời gian thực hiện thuật toán 
Ví dụ: Tìm thời gian thực hiện của thuật toán trong trường hợp xấu nhất 
// Thuật toán tìm max{1} max = a[0];{2} for (i=1; i<n; i++){3}	 if (max < a[i]){4}	max=a[i]; 
Độ phức tạp thuật toán 
Nhận xét: 
Việc đánh giá thời gian thực hiện thuật toán qua hàm T(n) như trên là quá chi tiết. Cho nên việc dùng T(n) để so sánh tính hiệu quả giữa các thuật toán sẽ gặp khó khăn. 
Để giải quyết khó khăn này Bachmann và Landau giới thiệu khái niệm hàm O (đọc là ô lớn) để xác định độ lớn của hàm T(n) 
Độ phức tạp thuật toán 
Định nghĩa [Độ phức tạp thuật toán]: 
Độ lớn của thời gian thuật toán T(n) được gọi là độ phức tạp thuật toán 
Giả sử f(n) là hàm xác định dương trên mọi n. Khi đó ta nói độ phức tạp của thuật toán có thời gian thực hiện T(n) là 
Hàm O (đọc là ô lớn): O(f(n)) nếu tồn tại các hằng số c và n 0 sao cho với mọi n≥n 0 ta có T(n) ≤c.f(n), hàm f(n) được gọi là giới hạn trên của hàm T(n) 
Độ phức tạp thuật toán 
Ví dụ: Nếu T(n)=n 3 +3n 2 +n+1 thì T(n)=O(n 3 ) 
Thật vậy, với mọi n≥1 ta có: 	T(n) = n 3 +3n 2 +n+1 ≤ n 3 +3n 3 +n 3 +n 3 =6n 3 
Vậy ta chọn n 0 =1, c=6 và f(n)=n 3 , ta có: T(n)≤c.f(n) 
Tóm lại: T(n)=O(n 3 ) 
Nhận xét: 
Có nhiều hàm f(n) làm chặn trên của T(n) 
Thông thường người ta chọn f(n) nhỏ nhất và đơn giản nhất có thể 
Một số dạng hàm kí hiệu độ phức tạp thuật toán 
Một số hàm f(n) thường dùng để kí hiệu độ phức tạp thuật toán 
log(n) 
n 
n.log(n) 
n 1.25 , n 2 , n 3 , n 4 , 
2 n 
n! 
Các quy tắc của độ phức tạp 
Quy tắc Hằng số : Nếu thuật toán T có độ phức tạp là T(n)=O(c 1 .f(n)) với c 1 là một hằng số dương thì có thể coi thuật toán T có độ phức tạp là O(f(n)) 
Chứng minh: 
Các quy tắc của độ phức tạp 
Quy tắc Cộng : Nếu thuật toán T gồm 2 phần liên tiếp T 1 và T 2 và 
Phần T 1 có độ phức tạp là T 1 (n)=O(f(n)) 
Phần T 2 có độ phức tạp là T 2 (n)=O(g(n)) 
Thì độ phức tạp thuật toán là: 	 T(n)=T 1 (n)+T 2 (n) = O(f(n)+g(n)) 
Chứng minh: 
Các quy tắc của độ phức tạp 
Quy tắc Max : Nếu thuật toán T có độ phức tạp là T(n)=O(f(n)+g(n)) thì có thể coi thuật toán T có độ phức tạp là 	T(n)=O(max(f(n), g(n))) 
Chứng minh: 
Các quy tắc của độ phức tạp 
Quy tắc Nhân : Nếu thuật toán T có độ phức tạp tính toán là T(n)=O(f(n)). Khi đó nếu thực hiện k(n) lần thuật toán T với k(n)=O(g(n)) thì độ phức tạp tính toán là 	O(f(n).g(n)) 
Chứng minh: 
Một số dạng hàm kí hiệu độ phức tạp thuật toán 
Tùy theo dạng hàm f(n), ta có các kí pháp sau: 
Nếu thuật toán có thời gian thực hiện không phụ thuộc vào kích thước dữ liệu thì ta nói thuật toán có độ phức tạp là một hằng số và được viết là O(1) 
Nếu thuật toán có thời gian thực hiện là log a f(n) thì độ phức tạp của thuật toán đó được viết là O(log f(n)) 
Nếu thuật toán có thời gian thực hiện là đa thức bậc k: P(n) thì độ phức tạp của thuật toán đó được viết là O(n k ) 
Một số dạng hàm kí hiệu độ phức tạp thuật toán 
Kí hiệu O-lớn 
Tên thường gọi 
O(1) 
Hằng 
O(log(n)) 
Logarit 
O(n) 
Tuyến tính 
O(n.log(n)) 
n.log(n) 
O(n 2 ), O(n 3 ),  
Bình phương, lập phương,  Đa thức 
O(2 n ), O(a n ) 
Mũ 
O(n!) 
Giai thừa 
ƯỚC LƯỢNG ĐỘ PHỨC TẠP CỦA THUẬT TOÁN 
Phân loại câu lệnh trong một ngôn ngữ lập trình 
Câu lệnh đơn thực hiện một thao tác 
Lệnh gán đơn giản (không chứa lời gọi hàm trong biểu thức) 
Đọc/ghi đơn giản 
Câu lệnh chuyển điều khiển đơn giản (break, goto, continue, return) 
Câu lệnh hợp thành : dãy các câu lệnh trong 1 khối 
Câu lệnh rẽ nhánh : if, switchcase 
Câu lệnh lặp : for, while, dowhile 
Đánh giá độ phức tạp của từng câu lệnh 
Độ phức tạp của lệnh đơn: Không phụ thuộc kích thước dữ liệu nên sẽ là O(1) 
Độ phức tạp của lệnh hợp thành: Tính theo quy tắc Cộng và quy tắc Max 
Độ phức tạp của lệnh rẽ nhánh đầy đủ: Tính theo quy tắc Max. Nếu thời gian thực hiện 2 thành phần là f(n), g(n) thì độ phức tạp O(max(f(n), g(n))) 
Độ phức tạp của lệnh lặp: Tính theo quy tắc nhân 
Một số ví dụ 
Ví dụ [for]: Tìm độ phức tạp của thuật toán 
// Thuật toán tính tổng S=a[0]+a[1]++a[n-1]{1} cout > n;{3} for (i=0; i> a[i]; 
{5} s = 0;{6} for (i=0; i<n; i++){7}	s = s + a[i]; 
Một số ví dụ 
Ví dụ [for lồng nhau]: Tìm độ phức tạp của thuật toán 
{1} s1 = 0;{2} for (i=0; i<n; i++){3}	s1=s1+a[i]; 
{4} s2 = 0;{5} for (i=0; i<n; i++) 
{6}	 for (j=0; j<n; j++) 
{7}	s2 = s2 + b[i][j]; 
Một số ví dụ 
Ví dụ [for lồng nhau]: Tìm độ phức tạp của thuật toán 
{1} s = 0;{2} for (i=0; i<n; i++) 
{3}	 for (j=0; j<i; j++) 
{4}	s = s + b[i][j]; 
Một số ví dụ 
Ví dụ [if]: Tìm độ phức tạp của thuật toán trong trường hợp xấu nhất 
// Thuật toán tìm max{1} max = a[0];{2} for (i=1; i<n; i++){3}	 if (max < a[i]){4}	max=a[i]; 
Một số ví dụ 
Ví dụ [if + return]: Tìm độ phức tạp của thuật toán trong trường hợp xấu nhất 
// Thuật toán tìm kiếm{1} vitri = -1;{2} for (i=0; i<n; i++){3}	 if (x == a[i])	{{4}	vitri = i;{5}	 return vitri;	}{6} return vitri; 
Một số ví dụ 
Ví dụ: Tìm độ phức tạp thuật toán Tính tổng ma trận 
i=0;s=0; while (i<=n){	j=1;	 while (j<=n)	{	s = s + a[i][j];	j++;	}	i++;} 
Một số ví dụ 
Ví dụ: 
smax=a[0];i=0; while (i smax)	s = smax;	j++;	}	i++;} 
HẾT CHƯƠNG 1