Trình bày các phương pháp đệ quy và độ phức tạp tương ứng
|
Khi bạn lập trình bạn có từng suy nghĩ rằng tại sao lại có những chương trình chạy nhanh mà lại có những chương trình cùng chức năng đó lại chạy chậm và ngốn tài nguyên máy tính của bạn nhiều hơn. Bạn cố gắng tìm cách cài tiến các thuật giải của mình để chương trình chạy nhanh hơn, vậy nó nhanh đến cỡ nào. Bài viết này sẽ trang bị cho bạn một số kiến thức để đánh giá độ phức tạp thuật toán của bạn…. 1. Tính hiệu quả của thuật giải: Để giải quyết một vấn đề thường có nhiều cách. Để giải một bài toán, có thể có nhiều cách khác nhau. Cần phải lựa chọn cách “tốt nhất” theo một nghĩa nào đó. Thế nào là một thuật giải “tốt”. Có thể nêu hai tiêu chuẩn sau: - Đơn giản, dễ hiểu, dễ lập trình. (1) - Cho lời giải nhanh, dùng ít tài nguyên máy tính. (2) Thật không may là thường không thể đảm bảo đồng thời cả 2 tiêu chuẩn đó. Phải tùy theo trường hợp mà áp dụng tiêu chuẩn thứ nhất hay thứ 2. - Nếu chỉ dùng thuật giải cho một vài lần thì tiêu chuẩn 1 quan trọng hơn tiêu chuẩn thứ 2. - Trái lại, nếu đây là một bài toán rất phổ biến, thuật giải sẽ còn được dùng nhiều lần thì tiêu chuẩn 2 quan trọng hơn tiêu chuẩn 1. Mục đích của việc nghiên cứu cấu trúc dữ liệu và giải thuật chính là để xây dựng các chương trình hiệu quả. Tiêu chuẩn 2 chính là tính hiệu quả của thuật giải. Một thuật giải được gọi là hiệu quả nếu nó tiết kiệm được không gian và thời gian. Tiết kiệm không gian là chiếm dụng ít bộ nhớ trong thời gian thực hiện. Tiết kiệm thời gian là chạy nhanh. Tiêu chuẩn thời gian thực hiện nhanh là quan trọng hàng đầu. Đánh giá độ phức tạp của thuật giải là đánh giá thời gian thực hiện nó. Bài toán không không phải là bài toán chưa có lời giải mà là bài toán mà việc giải nó mất một khoảng thời gian quá dài, đến mức không chấp nhận được. 2. Tại sao thuật giải cần phải có tính hiệu quả: Máy tính ngày nay có tốc độ lên tới hàng trăm triệu phép tính trên một giây. Liệu việc cải tiến thuật giải để giảm bớt đi một số phép tính toán có ý nghĩa gì không? Ví dụ sau đây cho thấy tầm quan trọng của một thuật giải hiệu quả. Xét bài toán tính định thức cấp n. Giả sử M = aij là ma trận vuông n x m. Cần tính định thức det(M). a. Thuật toán đệ quy: - Nếu n = 1 thí det(M) = a11 . - Trái lại, n > 1 sử dụng công thức khải triển theo định thức hàng để đưa về định thức cấp thấp hơn. (Ở đây chúng ta sẽ không đề cập đến cách tính toán như thế nào trong ví dụ này). Giải thuật này sẽ cần đến n.(n-1).(n-2)… 1 = n! phép tính nhân. Mà n! là một số rất lớn ngay khi cả n là không lớn lắm. Sẽ cần đến hàng triệu năm để tính một định thức cấp 100. Rõ ràng là không thể chấp nhận một thuật toán như thế. b. Thuật toán sử dụng Gauss-Jordan: - Đưa ma trận về dạng đường chéo. - Tính định thức bằng tích các phần tử trên đường chéo. Dùng thuật toán này tính định thức cấp n chỉ cần n3 phép tính. Chỉ cần không quá 1 giây để tính định thức cấp 100 trong. –> Trong ví dụ trên, sự chênh lệch về số phép toán cần thực hiện của 2 thuật giải là rất lớn, nên lựa chọn là hiển nhiên. Tuy nhiên, ngay cả trong trường hợp việc cải tiến hiệu quả chỉ tiết kiệm được một số ít phép toán, nhưng thuật giải được sử dụng hàng triệu lần thì lợi ích mang lại cũng được nhân lên hàng triệu lần, con số đó không phải là nhỏ. 3. Đánh giá thời gian thực hiện thuật giải: a. Tính độc lập: Thế nào là một thuật giải nhanh. Có thể lập chương trình, chạy máy rồi bấm giờ. Tuy nhiên tốc độ thực hiện một chương trình phụ thuộc vào ngôn ngữ lập trình, chương trình dịch, hệ điều hành, phần cứng của máy… Mặt khác, phải lập trình mới đo được thời gian thực hiện của thuật giải. Cần đánh giá thời thực hiện sao cho: - Không phụ thuộc máy, ngôn ngữ lập trình, chương trình biên dịch. - Không cần phải triển khai chương trình thực hiện thuật giải. - Chỉ dựa vào bản thân thuật giải. Trong ví dụ ở phần 2, ta đã tính thời gian thực hiện thuật giải tính định thức bằng số phép tính cần tiến hành. Đây chính là cách làm đáp ứng nhu cầu trên. b. Các phép toán sơ cấp: Trước hết ta cần thống nhất những thao tác nào được coi là một phép tính. Đây là khái niện phép toán sơ cấp. Các phép toán sơ cấp là những phép toán mà thời gian thực hiện nó đủ ngắn, hay nói đúng hơn là không vượt quá một hằng số nào đó. Các phép toán sau đây có thể coi là sơ cấp: - Các phép tính số học. - Các phép tính logic. - Các phép chuyển chỗ, gán… c. Kích thước dữ liệu đầu vào: Cho một thuật giải ta hoàn toàn ước lượng được tổng số các phép toán sơ cấp cần thiết để thực hiện thuật giải đó. Một điều hiển nhiên là tổng số phép toán sơ cấp để giải một bài toán phụ thuộc vào kích thước của bài toán. Dùng cùng một thuật toán, tính một định thức cấp 5 rõ ràng cần ít phép tính hơn định thức cấp 10. Tổng số mục dữ liệu đầu vào là đặc trưng cho kích thước của bài toán. Người ta thường dùng một số nguyên dương n để thể hiện kích thước này. Như vậy, một thuật giải T áp dụng để giải bài toán có kích thước n sẽ cần một tổng số T(n) các phép toán sơ cấp. T(n) là một hàm của tham số n. Hàm số T(n) là đặc trưng cho hiệu quả của thuật giải T. 4. Tính trạng dữ liệu đầu vào: Không chỉ có số lượng dữ liệu đầu vào quyết định thời gian thực hiện giải thuật mà tình trạng dữ liệu cũng ảnh hưởng đến việc thuật giải thực hiện nhanh hay chậm. Xét bài toán sắp xếp một dãy số. Rõ ràng là nếu dãy đã có sẵn thứ tự mong muốn hoặc gần thư thế thì công việc phải làm ít hơn trường hợp một dãy bất kỳ. Hoặc bài toán tìm kiếm tuần tự trong một dãy số cho sẵn như tìm vị trí của phần tử k trong mảng a[0, 1, n-1] (nếu k tồn tại trong mảng a). int SequentialSearch(int a[], int n, int k) { for(int i = 0; i < n; i++ ) { if( k == a[i]) return i; // i la vi tri cua k trong mang a[] } return -1; } - Trường hợp mới bắt đầu tìm kiếm gặp ngay phần từ k thì đây là trường hợp tốt nhất (best case) C(n) = 1. - Trường hợp tìm kiếm mà không có k trong mảng hay k nằm ở cuối mảng thì đây là trường hợp xấu nhất, phải duyệt qua tất cả các phần tử của mảng a[] (worst case). C(n) = n. - Trường hợp trung bình C(n) = C(n)trung bình = 0, 5. p(n + 1) + n(1 – p). ** Tùy theo tình trạng dữ liệu đầu vào mà ta có các trường hợp: - Thuận lợi nhất C(n) là nhỏ nhất, ta ký hiệu là Cmin (best case). - Bất lợi nhất C(n) là lớn nhất, ta ký hiệu là Cmax (worst case). - Ngẫu nhiên T(n) là trung bình, ta ký hiệu là Taver (average case). –> Hợp lý nhất là dùng ước lượng thời gian thực hiện trung bình Taver để so sánh đánh giá thuật giải. Nếu tính thời gian thực hiện trung bình quá khó khăn, có theer đánh giá căn cứ vào trường hợp xấu nhất, tức là dùng Tmax. Thậm chí, nhiều bài toán thời gian thực đòi hỏi thời gian trả lời phải không vượt quá một giới hạn cho trước nào đó. Trong trường hợp này, chỉ có thể dùng ước lượng trong trường hợp xấu nhất, nghĩa là Tmax mà thôi. 5. Ký hiệu O (Big – O) và các vô cùng lớn: a. Tốc độ tăng: Giả sử để giải cùng một bài toán có hai giải thuật giải T1 , T2 với thời gian thực hiện tương ứng là:
Ở đây C1, C2 là các hằng số. Thế thì khi n đủ lớn chắc chắn T2(n) sẽ lớn hơn T1(n), dù rằng C1 Có lớn hơn C2 nhiều lần. Tôi nói đến điều này để chúng ta thấy rằng trong lĩnh vực các vô cùng lớn các hằng số không quan trọng. Độ lớn phụ thuộc chủ yếu vào tốc độ tăng của T(n) khi n tăng. Ký hiệu O lớn được đặt ra nhằm mục đích loại bỏ các thành phần không quan trọng, làm rõ tốc độ tăng nói trên. b. Ký hiệu O lớn (Big-O) - Định nghĩa: Giả sử f(n), g(n) là 2 hàm số không âm, đồng biến theo n. Ta nói “f(n) là O lớn của g(n)” và viết: f(n) = O(g(n)). khi và chỉ khi tồn tại hằng số C để f(n) <= C.g(n) kể từ n >= n0 nào đó. Ta nói f(n) có cấp lớn không vượt quá g(n) (dễ hiểu là f(n) có tăng tới đâu đi nữa cũng không thể vượt quá tốc độ tăng của g(n)). Ví dụ: f(n) = 2(n*n) + 3n + 5.
với mọi n >= 1. Ta viết f(n) = O(n2) Viết T(n) = O(g(n)) nghĩa là tốc ọộ tăng của T(n) khi tiến đến vô cùng không vượt quá tốc độ tăng của g(n). Khi n lớn, g(n) cho ta hình dung được mức lớn của T(n).g(n) là “thước đo” độ lớn của T(n). Các thuộc tính của big-O c. Các đơn vị đo tốc độ tăng Người ta thường cố gắng ước lượng g(n) sao cho sát với T(n) nhất và có dạng đơn giản nhất để dễ hình dung.
Bảng trên cung cấp các “thước đo” thời gian thực hiện giải thuật giải hay dùng nhất và tên gọi thông thường của chúng. Trong các đánh giá về thời gian thực hiện thuật giải, chủ yếu sẽ dùng các hàm logarit cơ số 2. Do đó, để đơn giản ta viết log n thay cho logarit cơ số 2 của n. Các logarit cơ số khác sẽ được chỉ rõ. - T(n) = O(1): thời gian thực hiện giải thuật không quá một hằng số nào đó, không phụ thuộc vào n. Ta nói thuật giải có thời gian hằng số. - T(n) = O(n): ta nói thuật giải có tốc độ tăng tuyến tính. - T(n) = O(2n): ta nói thuật toán có độ tăng theo hàm mũ. Bảng so sánh dưới đây giúp chúng ta dễ hình dung độ lớn của các mức thời gian thực hiện thuật giải nói trên:
Rõ ràng là khi thời gian thực hiện thuật giải tăng với tốc độ hàm mũ thì độ lớn tăng rất nhanh. Những bài toán mà chưa tìm được thuật giải với thời gian dưới cấp hàm mũ, nghĩa là từ thời gian đa thức thức trở xuống, sẽ được xếp vào loại bài toán khó. 6. Big- Omega (Ω) và Big-Theta (Θ) Tương tự như với bậc big-O, nếu như tìm được các hằng số C,k1,k2 đều dương và không phụ thuộc vào n, sao cho với n đủ lớn, các hàm R(n),f(n) và h(n) đều dương và thì ta nói thuật toán có độ phức tạp cỡ lớn hơn Ω(n), và đúng bằng cỡ Θ(h(n)). Như vậy nếu xét một cách chặt chẽ, kí hiệu Θ mới biểu thị độ phức tạp của thuật toán một cách chặt chẽ. Do đó 2 ký hiệu thường được sử dụng trong đánh giá độ phức tạp của thuật toán là Big-O và Big Theta. Nhưng chúng ta thường sử dụng Big-O hơn. 7. Cách xác định thời gian thực hiện một thuật giải: a. Quy tắc tổng
Ví dụ: Thuật giải gồm 2 thủ tục kế nhau P = { P1, P2 }
b. Tính thời gian thực hiện của các câu lệnh trong ngôn ngữ lập trình: Dưới đây là thể hiện trình bày, ta quy ước gọi f(n), fi(n) là thời gian thực hiện câu lệnh S, Si tương ứng. - Câu lệnh đơn: các câu lệnh đơn như gán, đọc, viết, so sánh,… có thời gian thực hiện là O(1) - Lệnh ghép: S = S1 = S2, …, = Sp; tính thời gian thực hiện theo quy tắc tổng. - Lệnh rẽ nhánh: if <điều kiện> S1; else S2; tính thời gian thực hiện là O( max { f1(n), f2(n) }). - Lệnh lựa chọn: case tính thời gian tương tự như if. - Lệnh vòng lặp: While< điều kiện> { S } ; tính thời gian thực hiện là (số lần lặp) * f(n) - Vòng lặp for tương tự như while. Ví dụ: Tính ex ex = 1 + ( x/1!) + (x*x/2!) + (x*x*x/ 3!) + … + (xn /n!) Thuật giải 1: double SumDevideFactorial(int n) { double S = 1; double p = 1; for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { p = p*x/ j; S += p; } } return S; } Vòng for bên trong có số phép toán bằng i. Tổng số phép toán T(n) = 1 + 2+ … + n = (n( n –1 ))/ 2 = O(n2) Thuật Giải 2
double SumDevideFactorial(int n) { double S = 1; double p = 1; for(int i = 0; i < n; i++) { p = p*x/ i; S += p; } return S; } Tổng số phép toán T(n) = O(n). Như vậy giải thuật 2 tối ưu hơn giải thuật 1. |
