zunia.vn

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

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài giảng Cấu trúc dữ liệu và giải thuật: Phân tích thuật toán

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

Báo xấu

93
lượt xem 2
download

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

Chương này trang bị cho người học những kiến thức về phân tích thuật toán. Các nội dung chính trong chương này gồm có: Phân tích thuật toán; mô hình RAM; tốt nhất, tồi nhất, trung bình; ký hiệu O‐lớn; tốc độ tăng và tính thống trị; phân tích tiệm cận; một số tính chất của phân tích 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 Cấu trúc dữ liệu và giải thuật: Phân tích thuật toán

1/10/2011 REVIEW • Bài toán: Cho một tập các số nguyên S = {s1, s2, . . . , sn}, và một giá trị đích T. Tìm một tập con của S sao cho tổng các số trong tập con đó đúng bằng T. Ví dụ, Tồn tại một tập con trong S = {1, 2, 5, 9, 10} mà tổng là PHÂN TÍCH T = 22 nhưng lại không tồn tại với T = 23. THUẬT TOÁN Tìm phản ví dụ cho các thuật toán sau REVIEW NÔI DUNG • (a) Lần lượt chọn các phần tử trong S theo thứ tự từ trái qua • Phân tích thuật toán phải nếu chúng phù hợp (thuật toán first‐fit). • Mô hình RAM • Tốt nhất, tồi nhất, trung bình • (b) Lần lượt chọn các phần tử trong S theo thứ tự từ nhỏ đến • Ký hiệu O‐lớn lớn (thuật toán best‐fit). • Phân tích tiệm cận • Tốc độ tăng và tính thống trị • (c) Lần lượt chọn các phần tử trong S theo thứ tự từ lớn nhất • Một số tính chất của phân tích O‐lớn đến nhỏ nhất. 1
1/10/2011 PHÂN TÍCH THUẬT TOÁN? PHÂN TÍCH THUẬT TOÁN? Bài toán: tìm phần tử lớn nhất thứ k • Đánh giá hiệu quả của thuật toán mà không cần cài đặt. • Đầu vào: Dãy số gồm n số nguyên , , . . , , và số nguyên k • 2 mô hình : (0
1/10/2011 TỐT NHẤT, TỒI NHẤT VÀ TRUNG BÌNH KÝ HIÊU O LỚN • Độ phức tạp trong trường hợp tồi nhất (worst‐case complexity): • Khó xác định chính xác các hàm đánh giá độ phức tạp trong Là số lượng bước lớn nhất thuật toán cần thực hiện với bất cứ trường hợp tốt nhất, tồi nhất, trung bình đầu vào kích thước n nào. • Có rất nhiều điểm lồi: thời gian thực hiện biến đổi trong một số trường • Độ phức tạp trong trường hợp tốt nhất (best‐case complexity): hợp đầu vào đặc biệt. VD tìm kiếm nhị phân nếu đầu vào 2 1 Là số lượng bước nhỏ nhất thuật toán cần thực hiện với bất cứ • Để chính xác thì cần phân tích rất tỉ mỉ. đầu vào kích thước n nào. 120 12.4 43 9 • Độ phức tạp trong trường hợp trung bình (average‐case • Ký hiệu O lớn: đơn giản phân tích, bỏ qua những thành phần complexity): Là số lượng bước trung bình thuật toán cần thực mà không ảnh hưởng đến khi so sánh các thuật toán hiện trên tất cả các trường hợp đầu vào kích thước n. Trong phân tích O lớn 2 và 3 5 là tương đương • Mỗi độ phức tạp là một hàm của thời gian và kích thước đầu vào • Các ký hiệu tiệm cận , , dùng để phân tích độ phức tạp 120 12.4 43 9 trong thực tế PHÂN TÍCH TIÊM CẬN Cận trên, cận dưới để đánh giá cho độ phức tạp của hàm Định nghĩa O lớn chính thức: • : nghĩa là . là giới hạn trên của . Do vậy tồn tại hằng số sao cho . luôn đúng với mọi • Ω : nghĩa là . là giới hạn dưới của . Do vậy tồn tại hằng số sao cho . luôn đúng với mọi • Θ : nghĩa là . là giới hạn trên, và . là giới hạn dưới của . Do vậy tồn tại hằng số và sao cho . và . luôn đúng với mọi . Nói cách khác là giới hạn chặt của Với , , là các hằng số dương không phụ thuộc vào , và 0 Ο lớn Ω lớn Θ lớn 3
1/10/2011 KÝ HIÊU O LỚN OMEGA LỚN Ví dụ • vì chọn 1.5 thì 1.5 2 4 5 khi 50 • vì chọn 2 thì 2 2 4 5 • vì với bất kỳ giá trị thì • vì chọn 1 thì 2 4 5 khi c 2 4 5 khi đủ lớn ( 100 nếu 1, 1 10/ nếu 1) • vì với bất kỳ hằng số c nào thì • vì với bất kỳ hằng số c nào thì 2 4 5 khi 2 4 5 khi 5 THETA LỚN VÍ DỤ • vì cả Ο, Ω đều đúng Khẳng định sau đúng hay sai? Tại sao ? • vì chỉ Ο đúng •2 Θ 2 • vì chỉ Ω đúng •3 Θ 3 Để chứng minh Θ thì cần chỉ ra • Ο • Ο • Ω 4
1/10/2011 TỐC ĐÔ TĂNG VÀ QUAN TỐC ĐÔ TĂNG VÀ QUAN HÊ THỐNG TRỊ HÊ THỐNG TRỊ • O lớn nhóm các hàm thành các lớp hàm. 4 và 100.3 3 là thuộc lớp hàm Θ • Tốc độ tăng của một số hàm • Hai hàm , thuộc hai lớp khác nhau có quan hệ theo các ký hiệu thông dụng tiệm cận Ω, Ο khác nhau • Các lớp hàm thông dụng: • Hàm hằng 1. Thời gian thực hiện là hằng số VD hàm tính tổng 2 số • Hàm loga . VD tìm kiếm nhị phân • Hàm tuyến tính . VD Tìm giá trị lớn nhất trong dãy số • Hàm siêu tuyến tính . VD QuickSort, MergeSort • Hàm bậc hai . VD Sắp xếp nổi bọt (bubble sort ) • Hàm bậc ba . • Hàm mũ , là hằng số >1. • Hàm giai thừa ! TỐC ĐÔ TĂNG VÀ QUAN HÊ THỐNG TRỊ CÁC PHÉP TÍNH VỚI O LỚN • Quan hệ thống trị: • Cộng hai hàm !≫ ≫ ≫ ≫ log ≫ ≫ log ≫ 1 •Ο Ο → Ο max , • Giới hạn và quan hệ thống trị của các hàm •Ω Ω → Ω max , • thống trị nếu lim 0 → •Θ Θ → Θ max , VD. • Nhân hàm không thống trị 3 5 vì lim 3 → . •Ο ⋅ →Ο thống trị vì lim 0 → •Ω ⋅ →Ω !≫ ≫ ≫ ≫ ≫ log ≫ ≫ ≫ log •Θ ⋅ →Θ ≫ log ≫ log /loglog ≫ loglog ≫ 1 là một hằng số dương bất kỳ 5
1/10/2011 CÁC PHÉP TÍNH VỚI O LỚN MỘT SỐ TÍNH CHẤT • Nhân hai hàm Tính truyền ứng – transitivity • Nếu Ο và Ο thì Ο •Ο ∗Ο →Ο ∗ • Nếu Ω và Ω thì Ω •Ω ∗Ω →Ω ∗ • Nếu Θ và Θ thì Θ •Θ ∗Θ →Θ ∗ Tính đối xứng – symmetry • Θ khi và chỉ khi Θ Tính đối xứng chuyển vị ‐ transpose symmetry • Ο khi và chỉ khi Ω MỘT SỐ TÍNH CHẤT MỘT SỐ VÍ DỤ Chứng minh Thuật toán sắp xếp lựa chọn – Selection Sort Nếu Ο và Ο thì Ο selection_sort(int s[], int n) { Ta có int i,j; /* counters */ • Ο tức là với int min; /* index of minimum */ for (i=0; i
1/10/2011 MỘT SỐ VÍ DỤ MỘT SỐ VÍ DỤ • Lệnh được lặp lại nhiều nhất chính là lệnh if • Phân tích chi tiết hơn • 0 lệnh if lặp 2 lần (từ 1 tới n‐1) Phân tích trong trường hợp tồi nhất • 1 lệnh if lặp 3 lần (từ 2 tới n‐1) • Vòng lặp ngoài lặp n lần (từ 0 tới n‐1) … • 2 lệnh if lặp 1 lần (từ n‐1 tới n‐1) • Vòng lặp trong lặp n lần ứng với mỗi lần lặp của vòng ngoài • 1 lệnh if lặp 0 lần • Số lần lặp của if sẽ là • Vậy số lượng bước (thời gian) cần thực hiện trong trường 2 3 ⋯ 1 0 2 1 /2 hợp tồi nhất là →Ο • Vậy Θ MỘT SỐ VÍ DỤ MỘT SỐ VÍ DỤ • Sắp xếp chèn – Insertion Sort • Phân tích trong trường hợp tồi nhất for (i=1; i0) && (s[j]
1/10/2011 Môt số công thức hay dùng • ∑ 1 1 • ∑ 1 2 .. • ∑ 1 .. ∑ ∑ • ∑ 1 2 3 .. • .. với 1 • ∑ nếu 1 • ∑ 2 .. 8

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.