intTypePromotion=1
ADSENSE

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

67
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ủ đề:
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. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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] 
  8. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2