Chương 10 Phân tích thuật toán

1NHẬP MÔN LẬP TRÌNH CHƯƠNG 10 PHÂN TÍCH THUẬT TOÁN CTDL1- Nguyễn Hữu Thể 2 NỘI DUNG 1 Độ phức tạp của thuật toán2 Phương pháp tính độ phức tạp3 5 Đánh giá thời gian thực hiện thuật toán CTDL1- Nguyễn Hữu Thể 3 1. Phân tích thuật toán − Đánh giá chi phí và thời gian thực hiện thuật toán. − Thời gian tính toán của thuật toán => phụ thuộc kích thước đầu vào (size of input). − Nếu gọi n là kích thước dữ liệu đưa vào => thời gian thực hiện của một thuật toán có thể biểu diễn như một hàm của n: T(n). − Phần cứng máy tính, ngôn ngữ, chương trình dịch đều ảnh hưởng tới thời gian thực hiện. Ví dụ:
Nếu như thời gian thực hiện một thuật toán T1(n) = n2
Và thời gian thực hiện của một thuật toán khác T2(n) = 100n
=> Khi n đủ lớn, thời gian thực hiện của thuật toán T2 nhanh hơn thuật toán T1. CTDL1- Nguyễn Hữu Thể 4 2. Độ phức tạp của thuật toán − Cho một hàm T(n),
T(n) gọi là có độ phức tạp f(n) nếu tồn tại các hằng C • sao cho T(n) ≤ C*f(n)
Tức là T(n) có tỷ suất tăng là f(n) • kí hiệu: O(f(n)) (đọc là “ô của f(n)”). Chú ý: O(C.f(n))=O(f(n)) với C là hằng số.
Ðặc biệt: O(C)=O(1) CTDL1- Nguyễn Hữu Thể 5 2. Độ phức tạp của thuật toán − Bảng các cấp thời gian thực hiện thuật toán: − Các hàm như log2n, n, nlog2n, n2, n3 gọi là các hàm đa thức. − Giải thuật với thời gian thực hiện có cấp hàm đa thức thường chấp nhận được. − Các hàm như 2n, n!, nn được gọi là hàm mũ => tốc độ rất chậm. CTDL1- Nguyễn Hữu Thể 6 3. Phương pháp tính độ phức tạp − Phương pháp tính độ phức tạp (thời gian thực hiện) của:
Chương trình không gọi chương trình con.
Chương trình có gọi chương trình con không đệ quy.
Chương trình đệ quy − Hai qui tắc quan trọng:
Qui tắc cộng: Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2 • T1(n) = O(f(n)), • T2(n) = O(g(n)) • => thời gian thực hiện nối tiếp nhau là T(n) = O(max(f(n),g(n))).
Qui tắc nhân: Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1và P2 • T1(n) = O(f(n)), • T2(n) = O(g(n)) • => thời gian thực hiện là T(n) = O(f(n)*g(n)). CTDL1- Nguyễn Hữu Thể 7 3. Phương pháp tính độ phức tạp  Phân tích một chương trình không có chương trình con:
Thời gian thực hiện của mỗi lệnh gán, Read, Write là O(1)
Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng qui tắc cộng. • => thời gian thi hành một lệnh lâu nhất trong chuỗi các lệnh.
Thời gian thực hiện cấu trúc IF-ELSE: thời gian lớn nhất thực hiện lệnh sau IF hoặc sau ELSE và thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện là O(1).
Thời gian thực hiện vòng lặp: tổng (trên tất cả các lần lặp) thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp không đổi: • thời gian thực hiện vòng lặp = (số lần lặp) * (thời gian thực hiện thân vòng lặp). CTDL1- Nguyễn Hữu Thể 8 3. Phương pháp tính độ phức tạp Ví dụ: thủ tục sắp xếp “nổi bọt” − Trước hết, cả ba lệnh gán {4}, {5} và {6} đều tốn O(1) thời gian, so sánh a[j-1]> a[j] cũng tốn O(1) thời gian, do đó lệnh {3} tốn O(1) thời gian. − Vòng lặp {2} thực hiện (n-i) lần, mỗi lần O(1) => vòng lặp {2} tốn O((n-i).1) = O(n-i). − Vòng lặp {1} có i chạy từ 0 đến n-2 nên thời gian thực hiện của vòng lặp {1} và cũng là độ phức tạp của giải thuật là: void BubbleSort(int a[], int n) { int i,j,temp; /*1*/ for(i= 0; i<=n-2; i++) /*2*/ for(j=n-1; j>=i ; j--) /*3*/ if (a[j] < a[j-1]){ /*4*/ temp=a[j-1]; /*5*/ a[j-1] = a[j]; /*6*/ a[j] = temp; } } − Toàn bộ chương trình chỉ gồm:
một lệnh lặp {1},
lồng trong lệnh {1} là lệnh lặp {2}
lồng trong lệnh {2} là lệnh {3}
lồng trong lệnh {3} là 3 lệnh nối tiếp nhau {4}, {5} và {6}. − Chúng ta sẽ tiến hành tính độ phức tạp theo thứ tự từ trong ra. CTDL1- Nguyễn Hữu Thể 9 Bài tập: tính độ phức tạp void SelectionSort(int a[],int N ) { int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành for (int i=0; i<N-1 ; i++) { min = i; for(int j = i+1; j <N ; j++) if (a[j ] < a[min]) min = j; // ghi nhận vị trí phần tử hiện nhỏ nhất int temp=a[min]; a[min] = a[i]; a[i] = temp; } } 10