zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

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

Chia sẻ: Đặng Duy Nhật | Ngày: | Loại File: PDF | Số trang:0

Báo xấu

209
lượt xem 90
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

* 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ùng cấp Trường hợp xấu nhất: số thao tác sơ cấp nhiều nhất mà  giải thuật thực hiện trên các bộ dữ liệu cùng cấp Trường hợp trung bình: số thao tác trung bình cộng mà giải  thuật thực hiện trên các bộ dữ liệu cùng cấp  Việc tính toán hàm thời gian trong trường hợp trung bình khá khó khăn nên độ phức tạp được đánh giá trong trường hợp xấu nhất 13 Độ phức tạp của giải thuật  Ví dụ: xét đoạn chương trình sau for (int i = 0; i < n - 1; i++) for (int j = i + 1; j < n; j++) if (A[i] > A[j]) { int t = A[i]; A[i] = A[j]; A[j] = t; }  Các thao tác sơ cấp: phép so sánh, phép gán 14 Độ phức tạp của giải thuật  Phân tích phép so sánh if (A[i] > A[j]) Luôn được thực hiện trong vòng lặp  Số phép so sánh (N – 1) + (N – 2) + … + 1 = N*(N – 1)/2  Độ phức tạp theo phép so sánh của đoạn chương trình là  T(N) = O(N2) 15 5
11/30/2010 Độ phức tạp của giải thuật  Phân tích phép gán Việc thực hiện phụ thuộc điều kiện if (A[i] > A[j])  Trường hợp xấu nhất: điều kiện A[i] > A[j] luôn đúng, số  phép gán 3*((N – 1) + (N – 2) + … + 1) = 3*N*(N – 1)/2 Trường hợp tốt nhất: điều kiện A[i] > A[j] luôn sai, số phép  gán bằng 0 Độ phức tạp theo phép gán trong trường hợp xấu nhất của  đoạn chương trình là T(N) = O(N2) 16 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 17 Quy tắc xác định độ phức tạp  Việc xác định độ phức tạp của một giải thuật theo hàm thời gian có thể là vô cùng phức tạp.  Tuy nhiên một số hàm thời gian có thể xác định độ phức tạp theo một số quy tắc đơn giản sau Quy tắc bỏ hằng số  Quy tắc lấy max  Quy tắc cộng  Quy tắc nhân  18 6
11/30/2010 Quy tắc xác định độ phức tạp  Quy tắc bỏ hằng số Nếu đoạn chương trình P có thời gian thực hiện  T(N) = O(k*f(N)) với k là một hằng số dương thì độ phức tạp T(N) = O(f(N)) 19 Quy tắc xác định độ phức tạp  Quy tắc lấy max Nếu đoạn chương trình có thời gian thực hiện  T(N) = O(f(N), g(N)) thì độ phức tạp là O(max{f(N), g(N)}) 20 Quy tắc xác định độ phức tạp  Quy tắc tổng Nếu đoạn chương trình thực hiện 2 công việc T1 và T2 với  thời gian thực hiện T1(N) = O(f(N)) và T2(N) = O(g(N)) thì T1(N) + T2(N) = O(f(N) + g(N)) Đoạn lệnh P1 có độ phức tạp f(N), đoạn lệnh P2 có độ phức  tạp g(N). Nếu thực hiện P1 rồi sau đó thực hiện P2 thì độ phức tạp của cả chương trình là f(N) + g(N) 21 7
11/30/2010 Quy tắc xác định độ phức tạp  Quy tắc nhân Đoạn chương trình P có thời gian thực hiện T(N) = O(f(N)).  Nếu thực hiện P trong thời gian K(N) với K(N) = O(g(N)) thì độ phức tạp sẽ là O(g(N)* f(N)) 22 Quy tắc xác định độ phức tạp  Một số tính chất của biểu thức độ phức tạp P(N) là đa thức bậc k thì O(P(N)) = O(Nk)  f(N) > 0 N, logaf(N) = logab*logbf(N) => O(logaf(N)) =  O(logbf(N)). Độ phức tạp của giải thuật cấp logarit của f(N) là O(logf(N)) Độ phức tạp là hàm hằng, kí hiệu O(1)  Giải thuật có độ phức tạp cấp 2N, N!, NN là giải thuật có độ  phức tạp hàm mũ log2N < N < N.log2N < N2 < N3 < 2N < N! < NN với N lớn  23 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 24 8
11/30/2010 Đánh giá các cấu trúc điều khiển  Lệnh gán =  Thời gian của thao tác bằng thời gian thực hiện biểu thức  vd: d = sqrt(b*b – 4*a*c): phụ thuộc hàm sqrt a = sin(x): phụ thuộc hàm sin 25 Đánh giá các cấu trúc điều khiển  Lệnh rẽ nhánh if (điều kiện) //thời gian thực hiện T1(N) Lệnh 1; //thời gian thực hiện T2(N) else Lệnh 2; //thời gian thực hiện T3(N) Thời gian thực hiện  T(N) = T1(N) + max(T2(N), T3(N)) 26 Đánh giá các cấu trúc điều khiển  Lệnh vòng lặp: while (điều kiện) //thời gian thực hiện T0(N) câu lệnh; //thời gian thực hiện Ti(N) Thời gian thực hiện:  X(N): số lần lặp Ti(N): thời gian thực hiện ở lần thứ i T0(N): điều kiện lặp Trong trường hợp vòng lặp không xác định được số lần lặp  thì ta phải xét số lần lặp trong trường hợp xấu nhất 27 9
11/30/2010 Bài tập  Cách 1 int GiaiThua(int N) { int P = 1; for (int i = 1; i
11/30/2010 Bài tập  Cách 1 double Sum(int N) { double S = 0; for (int i = 1; i

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.