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

Bài giảng Phân tích và thiết kế thuật toán: Đánh giá một số thuật toán thông dụng - Phạm Thế Bảo

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:14

Báo xấu

104
lượt xem 8
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 toán này trình bày về đánh giá một số thuật toán thông dụng. Nội dung chính của bài giảng gồm có: Tìm kiếm tuần tự, xem xét phân bố khóa, tìm kiếm nhị phân, sắp xếp chè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 toán: Đánh giá một số thuật toán thông dụng - Phạm Thế Bảo

28/03/2008 ĐÁNH Á GIÁ Ố Á MỘT SỐ THUẬT TOÁN THÔNG DỤNG Phạm Thế Bảo Khoa Toán – Tin học Trường Đại học Khoa học Tự nhiên Tp.HCM Tìm kiếm tuần tự • Xét một mảng các phần tử a[1], a[2], …, a[n]. Phần tử a[i] có khóa tìm kiếm là a[i].key, bài toán: cho trước khóa k, có tồn tại j để a[j].key bằng k hay không? i=1; found=false; while((i≤n)&&(not found)) do if(a[i].key bằng k) then found=true;; ế bỏ else: Nếu else 1. Thuật toán còn đúng không? 2. Có tăng phép đếm (gán)? i=i+1; endif endw Phạm Thế Bảo 1
28/03/2008 • Ta cần phân biệt: Phép toán số học: so sánh, gán Phép toán trên khóa: sao chép, so sánh • Nếu ta thêm một phần tử a[n+1].key=k thì số phép toán sẽ tăng hay giảm? • Viết lại thuật toán: i=1; a[n+1].key=k; while (a[i].key khác k) do i = i+1; endw Phạm Thế Bảo • Thuật toán dừng khi nào? – i =n+1 Æ không tìm thấy – i=i0, với 1≤i0≤n Æ tìm thấy giá ta cần tính α: • Để đánh giá, – Tìm không thấy: k∉{a[i].key/i=1..n}Æ α=n, gọi q là xác suất tìm không thấy. – Tìm thấy sẽ có xác suất là (1-q) – Đặt pi là xác suất để a[i].key bằng k ế a[k].key khác a[l].key nếu – Giả thiết ế k≠l – Nếu a[i].key bằng n k thì α=i-1 ??? n – Vậy q + (1 − q)∑ pi = 1 vaø coù α trung bình = α = ∑ pi (i − 1) i =1 i =1 Phạm Thế Bảo 2
28/03/2008 • Khi tìm thấy số lượng so sánh khóa: 1 – Tối thiểu = – Tối đa = n n – Trungg bình = α + 1 = ∑ pi i=1 • Số lần so sánh khóa trung bình cho cả hai trường hợp tìm thấy và không tìm thấy là: n (n + 1)q + (1 − q )∑ ipi i =1 Phạm Thế Bảo Xem xét phân bố khóa 1. Giả sử a[i].key=i k được đ chọn h ngẫu ẫ nhiên hiê từ tập tậ hợp h 1, 1 22, 22, 3, 3 3, 3 3, …, i, i, …, i, …, n, …, n, n+1, n+2, …, 2n i lần n lần n(n + 3) Tổng số khả năng có thể là:(1+2+…+n)+n= 2 n 2 Æ Xác suất để k∉{key} là q = n(n + 3) = n + 3 2 i 2i Suy ra pi = = n(n + 1) n(n + 1) 2 Phạm Thế Bảo 3
28/03/2008 Æ Số lần so sánh khóa trung bình là: 2 ⎛ 2 ⎞⎛ n 2i ⎞ = (n + 1) + ⎜1− ⎟⎜ ∑ i ⎟ n + 3 ⎝ n + 3 ⎠ ⎝ i =1 n(n + 1) ⎠ 2(n + 1) n + 1 2 n(n + 1)(2n + 1) = + . . n+3 n + 3 n(n + 1) 6 2n 2 + 9n + 7 = 3(n + 3) Phạm Thế Bảo 1 2. Giả sử dữ liệu phân bố đều Æ pi = , ∀i = 1..n n – Số lần so sánh khóa trung bình khi tìm thấy: 1 n n n +1 ∑i =1 ipi = ∑ i = n i =1 2 3. Giả sử có phân c bố khóa như sau: p1 = c p2 = 2 c p3 = 2 ... 2 c ... pn = 2 n −1 n ⎛ 1⎞ 1− ⎜ ⎟ ⎡ ⎛ 1⎞ ⎤ n ⎝ 2⎠ n n 1 ta c o ù ∑ pi = 1 = c∑ k −1 = c 1 = 2 c ⎢1 − ⎜ ⎟ ⎥ ⎝ 2 ⎠ ⎥⎦ i =1 k =1 2 1− ⎣⎢ 2 1 ⇒ c = ⎡ ⎛ 1⎞ ⎤ n 2 ⎢1 − ⎜ ⎟ ⎥ ⎣⎢ ⎝ 2 ⎠ ⎥⎦ Phạm Thế Bảo 4
28/03/2008 • Số lần so sánh khóa trung bình khi tìm thấy: n n n c i ∑ ipi = ∑ i i =1 i =1 2 i −1 = c ∑ i =1 2 i −1 ' ' n ⎛ n ⎞ ⎡ x((1 − x n ) ⎤ xetùt f( ) ∑ iix = ⎜ ∑ x i ⎟ = ⎢ f(x)= ii-1 1 ⎥ i=1 ⎝ i=1 ⎠ ⎣ 1 − x ⎦ nx n +1 − (n + 1) x n + 1 = (1 − x) 2 n ⎛1⎞ ⇒ ∑ ipi = cf ⎜ ⎟ vôùi c ñöôïc tính nhö treân i =1 ⎝ 2⎠ n+2 n 2− n ⇒ ∑ ipi = 2 ⇒ khi n ñuû lôùn (n → ∞ ) ⇒ 2 1 i =1 1− n 2 Phạm Thế Bảo • Nếu thuật tóan phân bố như trên thì độ phức tạp của thuật toán là hằng (nhỏ). • Do D nhữnghữ phần hầ tử ử thường h ờ ê được xuyên đ ặ gặp nhất được sắp ở đầu, những phần tử ở đầu có xác suất gặp cao hơn các phần tử càng về sau, tỷ lệ này giảm dần rất nhanh theo hệ số 2. Ví dụ: ứng dụng trong tổ chức dữ liệu của hệ cơ sở dữ liệu Oracle Phạm Thế Bảo 5
28/03/2008 4. Xem xét một phân bố khác như sau: c c p1 = p2 = 1 2 c p3 = ... 3 c ... pn = n n n 1 ta c o ù i=1 ∑ pi = 1 = c∑ k =1 k = cH n 1 1 m aø H n = 1 + + ... + = O ( ln n ) 2 n • Lúc đó số phép so sánh khóa trung bình trong trường hợp tìm thấy là 1 n n Hn n n ∑ ip = ∑ i i =1 i i =1 i = ≈ H n ln n Phạm Thế Bảo Tìm kiếm nhị phân • Cho mảng n phần tử thỏa a[1].key
28/03/2008 [1,6] • Ví dụ: xét n=6, m=(1+6)/2=3 3 [4,6] [1,2] – Nếu k∈{khóa} thì thuật toán 1 5 dừng ở đâu? [2,2] [4,4] [6,6] Số lần lặp trung bình ≈ 2 4 6 1x1 + 2 x 2 + 3 x3 14 = 6 6 Phạm Thế Bảo [1,6] – Nếu k∉ {khóa} thì thuật toán 3 dừng ở đâu? [1,2] [4,6] Số lần lặp trung bình ≈ 1 [2,2] 5 [6,6] [4,4] a∈(-∞,a[1].key) 6 b∈(a[1].key,a[2].key) c∈(a[2].key,a[3].key) a 2 4 d∈(a[3].key,a[4].key) e∈(a[4].key,a[5].key) b c d e f g f∈(a[5].key,a[6].key) g∈(a[5].key,+ ∞) 1x 2 + 6 x3 20 = 7 7 Phạm Thế Bảo 7
28/03/2008 Thuật toán: l=1; r=n; idx=-1; while (l≤r) do m=[l+r]/2; if(a[m].key==k) then idx=m; l=r+1; else if(if(a[m].key
28/03/2008 • Thuật ngữ: – Node trong (node tròn) của T=node của T=n – Node ngoài (vuông) của T=node bổ sung=N – Độ ộ dài đườngg đi đến node x: l(x)=số ( ) ạ từ g cạnh gốc đến x. ∑trong} l(x)=I(T) – Độ dài đường đi trong cây T= x∈{node Trở lại ví dụ trên, độ dài = 0x1+2x1+4x2+3x3=19 I (T ) – Độ dài đường đi trung bình đến mỗi node= soá node trong ∑ Trở lại ví dụ, dụ =19/10=1 19/10 1.99 l ( x) – Độ dài đường đi ngòai = E(T) = x∈{ node ngoaøi} E (T ) – Độ dài đường đi ngòai trung bình = soá node ngoaøi Phạm Thế Bảo • Mệnh đề: a. Số node ngoài = số node trong +1, N=n+1 b. E(T)=I(T)+2n I (T ) + 2n ộ dài đường c. Độ g đi ngòai g trung g bình = n+1 +1 Ví dụ trên, có E(T)= I(T)= E(T)=I(T)+2x10 E(T) I(T)+2x10 Phạm Thế Bảo 9
28/03/2008 • Nhận xét: – Khi tìm thấy: dừng ở node tròn x • β=1 và α=l(x)+1 ∑ [l ( x) + 1] x∈{node d tron t ø } I (T ) • α= = +1 n n ⎡ I (T ) ⎤ I (T ) • Số phép so sánh khóa TB= 2α − β = 2 ⎢ + 1⎥ − 1 = +1 ⎣ n ⎦ n – Khi không tìm thấy: dừng ở node vuông y • β=0 và α=l(y) E (T ) I (T ) + 2n • α = N = n +1 ⎡ I (T ) + 4n ⎤ • Số phép so sánh khóa TB= 2α − β = 2 ⎢ ⎣ n + 1 ⎥⎦ Phạm Thế Bảo Sắp xếp chèn • Có n phần tử a[1], …, a[n], ý tưởng: – n=1 hiển nhiên a[1] được sắp – Giả sử có k phần tử đầu a[1].key≤… ≤ a[k].key được sắp, ta phải tìm cách chèn a[k+1] vào đúng vị trí. Ví dụ: n=7, có mảng: 10 2 7 9 6 1 5 Lần 1 chèn 2 trước 10 Lần 2 chèn 7 giữa 2 và 10 … Phạm Thế Bảo 10
28/03/2008 Thuật toán: j=2; while (j≤n) do i=j-1; k=a[j].key; [j] y r=a[j]; while ((i>0)&&(k
28/03/2008 n • Vậy ∑ α j =1 j = soá nghòch theá cuûa σ n coù α1 = 0 ⇒ ∑ α j = soá nghòch theá cuûa σ j=2 ⎡ n ⎤ a Số phép gán số học = 1 + (n − 1) + ⎢⎣∑ ( gan a. gaùn soá hocc P(j) ) ⎥ + n + 1 so hoï ⎦ j=2 ⎧ ⎪ min=0 ⎪ n ⎪ n(n-1) = 2n − 1 + ∑ α j = 2n − 1 + soá nghich theá cuûa σ ⎨ max= j=2 ⎪ 2 ⎪ n(n-1) ⎪⎩ 4 b. So sánh số học = n + ∑ (α ) n j + 1 = 2n − 1 + soá nghòch theá cuûa σ j 2 j= c. Sao chép khóa = n-1 Phạm Thế Bảo ⎡ n ⎤ d. Sao chép mẫu tin = ( n − 1) + ⎢ ∑ ( cheùp maãu tin P(j) ) ⎥ + n − 1 ⎣ j=2 ⎦ n = 2n − 2 + ∑ α j = 2n − 2 + soá nghòch theá cuûa σ j=2 e. So sánh khóa: ( ) n • Không tối ưu = ∑ α j + 1 = n − 1 + soá nghòch theá cuûa σ j=2 • Có tối ưu: – a[j] là cực tiểu so với bên trái: i có thể giảm về 0 – Ngược lại i không giảm về 0 ⎛ ⎞ ⎛ n ⎞ ( ) n ⎜ ∑α j ⎟ ⎜ ∑ α j + 1 ⎟ = ⎜ j=2 ⎟ + ⎜ j=2 ⎟ , a[1] laø loaïi 1, loaïi 1 vaø 2 buø nhau ⎜ a[ j ] loaïi 1⎟ ⎜ a[ j ] loaïi 2 ⎟ ⎝ ⎠ ⎝ ⎠ n n =∑ α j + ∑ 1 j=2 j=2 Phạm Thế Bảo 12
28/03/2008 ậy số pphép Vậy g ị thế của p so sánh khóa là ((số nghịch σ +(n- số phần tử cực tiểu bên trái)) n(n − 1) ⇒ TB = + n − Hn 4 Phạm Thế Bảo Sắp xếp chọn • Ý tưởng: xét j=n, …, 2 chọn max trong {a[1] key a[2].key, {a[1].key, a[2] key …, a[j].key} idx đổi a[j] key} tại idx, chỗ a[j] và a[idx]. ví dụ: 10 2 7 9 6 1 5 – j=n chọn idx=1 Æ hoán đổi ọ idx=9 Æ hóan đổi – jj=n-1 chọn –… Phạm Thế Bảo 13
28/03/2008 Thuật toán: j=n; while (j≥2) do idx=1; i=2; while (i≤j) do if(a[i].key>a[idx].key) then idx=i; endif i=i+1; endw a[j] ÅÆ a[idx]; j=j-1; endw Phạm Thế Bảo • Đoạn P(j) là tìm khóa lớn nhất trong tập j phần tử. Ước lượng tổng chi phí trung bình của αj như sau: n ∑p j =1 j = (n + 1) H n − n Phạm Thế Bảo 14

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.