Bài giảng Phân tích và thiết kế thuật giải: Bài 1 - TS. Ngô Quốc Việt

Chia sẻ: You Can | Ngày: | Loại File: PDF | Số trang:43

Thêm vào BST

Báo xấu

83
lượt xem 13
download

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

Bài giảng Phân tích và thiết kế thuật giải - Bài 1 trình bày về độ phức tạp của giải thuật. Các nội dung chính trong bài giảng này gồm có: Các ví dụ về thuật giải như thuật giải tìm tuyến tính, tìm nhị phân; xác định độ phức tạp; định nghĩa O “lớn”; một số tính chất của O lớn;... Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Phân tích và thiết kế thuật giải: Bài 1 - TS. Ngô Quốc Việt

PHÂN TÍCH THIẾT KẾ THUẬT GIẢI ĐỘ PHỨC TẠP CỦA GIẢI THUẬT NGÔ QUỐC VIỆT 2014
Nội dung 1. Giới thiệu 2. Xác định độ phức tạp 3. Bài tập 4. Hỏi đáp. Ngô Quốc Việt 2
Ví dụ: thuật giải tìm tuyến tính linear_search(x: integer; a1, a2, …, an: integers) i := 1 while (i  n and x  ai) i := i + 1 Ngô Quốc Việt if i  n then location := i else location := 0 location = vị trí tìm thấy x, hoặc bằng zero nếu không tìm thấy 3
Ví dụ: tìm nhị phân Tìm nhị phân ký tự ‘j’ Khoảng tìm Ngô Quốc Việt a c d f g h j l m o p r s u v x z Phần tử giữa 4
Ví dụ: tìm nhị phân Tìm nhị phân ký tự ‘j’ Khoảng tìm Ngô Quốc Việt a c d f g h j l m o p r s u v x z Phần tử giữa 5
Ví dụ: tìm nhị phân Tìm nhị phân ký tự ‘j’ search interval Ngô Quốc Việt a c d f g h j l m o p r s u v x z center element 6
Ví dụ: tìm nhị phân Tìm nhị phân ký tự ‘j’ Khoảng tìm Ngô Quốc Việt a c d f g h j l m o p r s u v x z Phần tử giữa 7
Ví dụ: tìm nhị phân Tìm nhị phân ký tự ‘j’ Khoảng tìm Ngô Quốc Việt a c d f g h j l m o p r s u v x z Phần tử giữa OK 8
Tìm nhị phân-thuật giải procedure binary_search(int x, int a1, a2, …, an) i = 1 // i is left endpoint of search interval j = n // j is right endpoint of search interval while (i < j) begin m = (i + j)/2 Ngô Quốc Việt if x > am ) i = m + 1 else j = m end if x == ai then location = i else location = 0 Độ phức tạp tìm nhị phân: 𝑶 𝒍𝒐𝒈𝒏 ≪ 𝒏. Hướng dẫn: cần chia n cho 2 bao nhiêu lần để có được mảng 1 phần tử. 𝑛 1 = 𝑘 ⇒ 𝑘 = 𝑙𝑜𝑔2 𝑛 2 9
Độ phức tạp • Hai ví dụ về tìm kiếm trên có số lần lặp khác nhau. • Thuật giải A cần chạy 5000𝑛 lần (vd: lệnh so sánh), trong khi B là 1.1 𝑛 lần. Ngô Quốc Việt • Với 𝑛 = 10, B hiệu quả hơn A, khi 𝑛 = 1000, A cần 5.000.000 lần chạy, nhưng B cần 2.5. 1041 lần • Số lần thực hiện với 𝑛 input được gọi là độ phức tạp thuật giải  được biểu diễn hàm T(n). 10
Giới thiệu • Yêu cầu cần phải có thuật giải chính xác và nhanh  cần có tiêu chuẩn đánh giá. • Một yếu tố quan trọng nhất ảnh hưởng đến tốc độ là kích thước dữ liệu cần xử lý. Nếu n là kích thước đầu vào  cần tìm hàm T(n) thể hiện độ Ngô Quốc Việt phức tạp. Hàm T(n) gọi là độ phức tạp của giải thuật. • Các yếu tố khác như: phần cứng, ngôn ngữ lập trình, v.v.. được bỏ qua khi xét độ phức tạp. 11
Định nghĩa O “lớn” • Định nghĩa: 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, n0 sao cho 𝑇(𝑛) ≤ 𝐶𝑓(𝑛) với mọi n ≥ n0 (tức là T(n) có tỷ suất tăng là f(n)) và kí hiệu T(n) là 𝑂(𝑓(𝑛)) (đọc là “ô của f(n)”). Ngô Quốc Việt • Ví dụ: 𝑇(𝑛) = (𝑛 + 1)2 có tỷ suất tăng là 𝑛2 nên 𝑇(𝑛) = (𝑛 + 1)2 là 𝑂(𝑛2). • Chú ý: 𝑂(𝐶. 𝑓(𝑛)) = 𝑂(𝑓(𝑛)) với C là hằng số. Ðặc biệt 𝑂(𝐶) = 𝑂(1). 12
O lớn • Ý tưởng của big-O là tìm cận trên của độ tăng trưởng của hàm 𝑓(𝑛) khi n đủ lớn. • Cận trên xác định bởi hàm 𝑔(𝑛) đơn giản hơn 𝑓(𝑛). Ngô Quốc Việt • Xác định được hằng C sao cho 𝑓(𝑛)  𝐶𝑔(𝑛) khi 𝑛 > 𝑘. • Mục tiêu là tìm cận trên nhỏ nhất 𝑔(𝑛) sao cho 𝑓(𝑛)  𝐶𝑔(𝑛) khi 𝑛 > 𝑘 13
O lớn Cho 𝑓 𝑛 = 𝑛2 + 2𝑛 + 1. Chứng minh 𝑓(𝑛) là 𝑂 𝑛2 𝑛2 + 2𝑛 + 1 ≤ 4𝑛2 . Chọn 𝑘 = 1, 𝐶 = 4, 𝑓 𝑛 ≤ 4. 𝑛2 , ∀𝑛 ≥ 1 Ngô Quốc Việt ⇒ 𝑓(𝑛) là 𝑂 𝑛2 14
Các tính chất O “lớn” • Định lý: Cho đa thức d f (n)   ai ni i 0 với ai hằng số, ad > 0, thì Ngô Quốc Việt T ( n)  O ( n d ) 15
Một số tính chất của O lớn QUI TẮC Ngô Quốc Việt Quy tắc tổng: Quy tắc nhân: Thời gian thực hiện của Thời gian thực hiện đoạn hai chương trình nối của đoạn hai đoạn tiếp nhau là chương trình lồng nhau là: 𝑻(𝒏) = 𝑶(max(𝒇(𝒏), 𝒈(𝒏))) 𝑻(𝒏) = 𝑶(𝒇(𝒏). 𝒈(𝒏)) 16
Quy tắc tổng • Độ phức tạp chương trình P1 là: 𝑂(𝑓(𝑛)). • Độ phức tạp chương trình P2 là: 𝑂(𝑔(𝑛)). • Thời gian thực hiện tuần tự P1, P2 là: 𝑂(max(𝑓(𝑛), 𝑔(𝑛))). • Chứng minh: Ngô Quốc Việt 𝑇1(𝑛) = 𝑂(𝑓(𝑛)) nên  𝑛1, 𝑐1 sao cho 𝑇1(𝑛) < 𝑐1. 𝑓(𝑛) ∀ 𝑛 > 𝑛1. 𝑇2(𝑛) = 𝑂(𝑔(𝑛)) nên  𝑛2, 𝑐2 sao cho 𝑇2(𝑛) < 𝑐2. 𝑔(𝑛) ∀𝑛 > 𝑛2. Chọn 𝑛0 = max(𝑛1, 𝑛2); 𝑐 = max(𝑐1, 𝑐2) =>  𝑛 > 𝑛0 𝑇1(𝑛) + 𝑇2(𝑛)
Quy tắc nhân • Độ phức tạp chương trình P là: 𝑂(𝑓(𝑛)). • Nếu thực hiện P 𝑘(𝑛) lần, với 𝑘(𝑛) = 𝑂(𝑔(𝑛)), thì độ phức tạp là: 𝑂(𝑓(𝑛). 𝑔(𝑛)). • Chứng minh: Ngô Quốc Việt Thời gian thực hiện 𝑘(𝑛) lần P sẽ là 𝑘(𝑛). 𝑇 (𝑛), theo đn:  𝑛𝑘, 𝑐𝑘 > 0 sao cho 𝑘(𝑛) < 𝑐𝑘. 𝑔(𝑛) ∀𝑛 > 𝑛𝑘  𝑛𝑇, 𝑐𝑇 > 0 sao cho T 𝑛 < 𝑐𝑇. 𝑓 𝑛 ∀𝑛 > 𝑛𝑇 Vậy:  𝑛 >= max(𝑛𝑘, 𝑛𝑇) , ta có 𝑘(𝑛). 𝑇(𝑛)
Một số tính chất O lớn Ngô Quốc Việt 19
Một số hàm độ phức tạp phổ biến n logn nlogn n2 n3 2n 1 0 0 1 1 2 2 1 2 4 8 4 Ngô Quốc Việt 3 2 8 16 64 16 8 3 24 64 512 256 16 4 64 256 4096 65536 32 5 160 1024 32768 2147483648 20