Giáo trình giải thuật - phân tích giải thuật

* Tính đúng đắn của giải thuật có thể được chứng minh bằng công cụ toán học (sử dụng bộ test chỉ giúp phát hiện giải thuật sai)* Giải thuật dẫn đến chương trình được cài đặt dễ dàng (tiết kiệm thời gian viết mã lệnh)* Đối với chương trình cần xử lý dữ liệu lớn thì thời gian thực hiện là tiêu chí đặc biệt quan trọng.
Nội dung trích xuất từ tài liệu:
Giáo trình giải thuật - phân tích giải thuật 11/30/2010 Phân tích giải thuật GVGD: Trương Phước Hải Nội dung 1. Đánh giá giải thuật 2. Độ phức tạp của giải thuật 3. Quy tắc xác định độ phức tạp 4. Đánh giá các cấu trúc điều khiển 2 Đánh giá giải thuật Mỗi bài toán có thể có nhiều phương pháp (giải thuật) để giải quyết Đánh giá giải thuật là việc làm cần thiết để lựa chọn giải thuật tối ưu cho bài toán Giải thuật được đánh giá dựa trên các tiêu chí Tính đúng đắn  Tính đơn giản  Thời gian thực hiện  3 1 11/30/2010 Đánh giá giải thuật Tính đúng đắn của giải thuật có thể được chứng minh bằng công cụ toán học (sử dụng bộ test chỉ giúp phát hiện giải thuật sai) Giải thuật đơn giản dẫn đến chương trình được cài đặt dễ dàng (tiết kiệm thời gian viết mã lệnh) Đối với chương trình cần xử lý dữ liệu lớn thì thời gian thực thi là tiêu chí đặc biệt quan trọng 4 Đánh giá giải thuật Tính hiệu quả của giải thuật được đo lường dựa vào tốc độ thực thi khi được cài đặt trên máy tính Thời gian thực thi phụ thuộc Kích thước dữ liệu  Trạng thái dữ liệu  Tốc độc máy tính  Ngôn ngữ lập trình  5 Đánh giá giải thuật Thời gian thực thi được đánh giá dựa trên số thao tác sơ cấp mà giải thuật phải thực hiện Phép so sánh  Phép gán  Phép toán số học  Phép toán logic  Thời gian thực thi được biểu diễn tương đối bằng hàm T(N) với N là kích thước của dữ liệu đầu vào Thời gian thực thi là một hàm không âm T(N) ≥ 0, N ≥ 0  6 2 11/30/2010 Đánh giá giải thuật Xét ví dụ tính S = A[0] + A[1] + … + A[N-1] int S = 0; for (int i = 0; i < N; i++) S = S + A[i]; Thao tác chính để thực hiện tính S là phép cộng và phép  gán trong câu lệnh S = S + A[i] Số lần thực hiện thao tác S = S + A[i] bằng số lần thực thi  vòng lặp: N Vậy thời gian thực hiện đoạn chương trình T(N) = c*N,  trong đó c là một hằng số 7 Đánh giá giải thuật Xét đoạn chương trình sau int max = A[0][0]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (max < A[i][j]) max = A[i][j]; Thao tác chính của đoạn chương trình là so sánh và phép  gán Số phép so sánh bằng số lần lặp của 2 vòng lặp: N2  Số phép gán max = A[i][j] được thực hiện phụ thuộc vào  điều kiện if (max 11/30/2010 Độ phức tạp của giải thuật Thời gian thực thi T(N) không thể tính bằng thời gian đồng hồ nên không thể dựa vào số giây thực hiện để so sánh 2 giải thuật Ví dụ xét T1(N) = 100*N, T2(N) = N2 Khi N đủ lớn (N > 100) thì T1(N) < T2(N) => thời gian thực  hiện T1 ít hơn thời gian thực hiện T2 Ta nói thời gian thực hiện T1 tỉ lệ thuận với N và thời gian  thực hiện T2 tỉ lệ thuận với N2 Cách đánh giá thời gian thực hiện như trên gọi là đánh giá độ phức tạp của giải thuật 10 Độ phức tạp của giải thuật Xét giải thuật tổng quát với N là kích thước của bài toán, T(N) là thời gian thực thi với kích thước N f(N) được gọi là độ phức tạp của T(N) nếutồn tại các hằng  số dương c và N0 sao cho T(N) ≤ c*f(N) N ≥ N0 Kí hiệu độ phức tạp của giải thuật T(N) = O(f(N))  11 Độ phức tạp của giải thuật Ví dụ tính độ phức tạp của T(N) = (N + 1)2 Chọn c = 4, N0 = 1 ta có (N + 1)2 ≤ c*N2, N ≥ N0  Vậy độ phức tạp của hàm thời gian T(N) = O(N2)  Ví dụ tính độ phức tạp của T(N) = 3*N3 + 2*N2 Chọn c = 5, N0 = 1 ta có 3*N3 + 2*N2 ≤ c*N3, N ≥ N0  Vậy độ phức tạp của hàm thời gian T(N) = O(N3)  12 4 11/30/2010 Độ phức tạp của giải thuật Các trường hợp đánh giá độ phức tạp giải thuật Trường hợp tốt nhất: số thao tác sơ cấp ít nhất mà giải  thuật thực hiện trên các bộ dữ liệu c ...