T
thienvamai
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
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.
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 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.Đá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.
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.
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.
3.Ký hiệu O (Big – O)
Hàm số độ phức tạp của thuật toán, ta hay kí hiệu là O(g(n)), g(n) ở đây thông thường là hàm đa thức, hàm logarit (thường là cơ số 2), hàm mũ hoặc giai thừa. Hàm mũ và giai thừa thường ít gặp vì tăng quá nhanh khi n lớn. Trong các bài toán thực tế, ta không cần biết chính xác giá trị của hàm số này mà chỉ cần biết một ước lượng chấp nhận được của nó.
Nếu g(n) là một hàm đa thức [TEX]{n}^{3} + {n}^{2} + n + 1[/TEX], khi ta coi n đủ lớn thì[TEX]{n}^{2} + n + 1[/TEX] sẽ nhỏ hơn [TEX]{n}^{3}[/TEX] rất nhiều, do đó ước lượng cho g(n) chỉ còn là [TEX]{n}^{3} [/TEX], hay nói cách khác nếu số bước lớn nhất bạn phải thực hiện tính toán bị phụ thuộc vào [TEX]{n}^{3} [/TEX] thì tức là độ phức tạp của thuật toán bạn chọn là cỡ O([TEX]{n}^{3}[/TEX]) - từ "cỡ" ở đây ý là O([TEX]{n}^{3}[/TEX]) là một ước lượng tốt cho lượng hàm độ phức tạp
Các độ phức tạp thường gặp đối với các thuật toán thông thường gồm có:
Độ phức tạp hằng số, O(1). Số phép tính/thời gian chạy/dung lượng bộ nhớ không phụ thuộc vào độ lớn đầu vào. Chẳng hạn như các thao tác hệ thống: đóng, mở file.
Độ phức tạp tuyến tính, O(n). Số phép tính/thời gian chạy/dung lượng bộ nhớ có xu hướng tỉ lệ thuận với độ lớn đầu vào. Chẳng hạn như tính tổng các phần tử của một mảng một chiều.
Độ phức tạp đa thức, O(P(n)), với P là đa thức bậc cao (từ 2 trở lên). Chẳng hạn như các thao tác tính toán với mảng nhiều chiều (tính định thức ma trận).
Độ phức tạp logarit, O(log n) (chú ý: bậc của nó thấp hơn so với O(n)) . Chẳng hạn thuật toán Euclid để tìm ước số chung lớn nhất.
Độ phức tạp hàm mũ, O(2^n). Trường hợp này bất lợi nhất và sẽ rất phi thực tế nếu thực hiện thuật toán với độ phức tạp này.
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:
4. Cách xác định thời gian thực hiện một thuật giải:
a.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; và T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của đoạn hai chương trình đó nối tiếp nhau là T(n)=O(max(f(n),g(n)))
Lệnh gán x:=15 tốn một hằng thời gian hay O(1), Lệnh đọc dữ liệu READ(x) tốn một hằng thời gian hay O(1). Vậy thời gian thực hiện cả hai lệnh trên nối tiếp nhau là O(max(1,1))=O(1)
b.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 và T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện của đoạn hai đoạn chương trình đó lồng nhau là T(n) = O(f(n).g(n))
c.Qui tắc tổng quát để phân tích một chương trình
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. Như vậy thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi lệnh.
Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau THEN 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 là 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ì thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp.
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.
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 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.Đá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.
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.
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.
3.Ký hiệu O (Big – O)
Hàm số độ phức tạp của thuật toán, ta hay kí hiệu là O(g(n)), g(n) ở đây thông thường là hàm đa thức, hàm logarit (thường là cơ số 2), hàm mũ hoặc giai thừa. Hàm mũ và giai thừa thường ít gặp vì tăng quá nhanh khi n lớn. Trong các bài toán thực tế, ta không cần biết chính xác giá trị của hàm số này mà chỉ cần biết một ước lượng chấp nhận được của nó.
Nếu g(n) là một hàm đa thức [TEX]{n}^{3} + {n}^{2} + n + 1[/TEX], khi ta coi n đủ lớn thì[TEX]{n}^{2} + n + 1[/TEX] sẽ nhỏ hơn [TEX]{n}^{3}[/TEX] rất nhiều, do đó ước lượng cho g(n) chỉ còn là [TEX]{n}^{3} [/TEX], hay nói cách khác nếu số bước lớn nhất bạn phải thực hiện tính toán bị phụ thuộc vào [TEX]{n}^{3} [/TEX] thì tức là độ phức tạp của thuật toán bạn chọn là cỡ O([TEX]{n}^{3}[/TEX]) - từ "cỡ" ở đây ý là O([TEX]{n}^{3}[/TEX]) là một ước lượng tốt cho lượng hàm độ phức tạp
Các độ phức tạp thường gặp đối với các thuật toán thông thường gồm có:
Độ phức tạp hằng số, O(1). Số phép tính/thời gian chạy/dung lượng bộ nhớ không phụ thuộc vào độ lớn đầu vào. Chẳng hạn như các thao tác hệ thống: đóng, mở file.
Độ phức tạp tuyến tính, O(n). Số phép tính/thời gian chạy/dung lượng bộ nhớ có xu hướng tỉ lệ thuận với độ lớn đầu vào. Chẳng hạn như tính tổng các phần tử của một mảng một chiều.
Độ phức tạp đa thức, O(P(n)), với P là đa thức bậc cao (từ 2 trở lên). Chẳng hạn như các thao tác tính toán với mảng nhiều chiều (tính định thức ma trận).
Độ phức tạp logarit, O(log n) (chú ý: bậc của nó thấp hơn so với O(n)) . Chẳng hạn thuật toán Euclid để tìm ước số chung lớn nhất.
Độ phức tạp hàm mũ, O(2^n). Trường hợp này bất lợi nhất và sẽ rất phi thực tế nếu thực hiện thuật toán với độ phức tạp này.
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:
4. Cách xác định thời gian thực hiện một thuật giải:
a.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; và T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của đoạn hai chương trình đó nối tiếp nhau là T(n)=O(max(f(n),g(n)))
Lệnh gán x:=15 tốn một hằng thời gian hay O(1), Lệnh đọc dữ liệu READ(x) tốn một hằng thời gian hay O(1). Vậy thời gian thực hiện cả hai lệnh trên nối tiếp nhau là O(max(1,1))=O(1)
b.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 và T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện của đoạn hai đoạn chương trình đó lồng nhau là T(n) = O(f(n).g(n))
c.Qui tắc tổng quát để phân tích một chương trình
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. Như vậy thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi lệnh.
Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau THEN 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 là 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ì thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp.