Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 1: Các khái niệm cơ bản - Nguyễn Khánh Phương

ớc nó trong dãy a0, a1, , an-1 với mọi số nguyên n n0 , n0 là số nguyên không âm Một dãy số được gọi là một lời giải của công thức đệ quy nếu các thành phần trong dãy số đó thỏa mãn công thức đệ quy. Ví dụ: Xét công thức đệ quy an = 2an-1 – an-2 với n = 2, 3, 4, • Dãy số an=3n là lời giải của công thức đệ quy đã cho? Với n 2 ta có: 2an-1 – an-2 = 2(3(n – 1)) – 3(n – 2) = 3n = an Do đó, dãy số an=3n là lời giải của công thức đệ quy đã cho • Dãy số an=5 cũng là lời giải của công thức đệ quy này? Với n 2 ta có: 2an-1 – an-2 = 2 5 - 5 = 5 = an Do đó, dãy an=5 cũng là lời giải của công thức đệ quy đã cho Cùng 1 công thức đệquy có thể có nhiều lời giải.  Tại sao ??? Dãy số an=n+1?? Một công thức đệ quy không có các giá trị đầu (các điều kiện đầu).  Có thể có (thường có) nhiều lời giải Ví dụ: an = 2an-1 – an-2 với n = 2, 3, 4,... Công thức đệ quy này có các lời giải: • an=5 • an=3n • an=n+1 Nếu cả công thức đệ quy và các điều kiện đầu đều được xác định, thì dãy số lời giải của công thức đệ quy sẽ được xác định duy nhất. Ví dụ: an = 2an-1 – an-2 với n = 2, 3, 4,.. với a0=0; a1 = 3 Dãy số an=5 không phải là lời giải Dãy số an=3n là lời giải duy nhất Công thức đệ quy là công thức cho phép tính giá trị của các đại lượng theo từng bước, dựa vào các giá trị tính ở các bước trước và một số giá trị đầu. 1.6. Giải công thức đệ quy 1.6. Giải công thức đệ quy Ta hiểu việc giải công thức đệ qui là việc tìm công thức dưới dạng hiện cho số hạng tổng quát của dãy số thoả mãn công thức đệ qui đã cho. Ví dụ: Cho công thức đệ quy: an = 2an-1 – an-2 với n = 2, 3, 4, a0=0; a1 = 3 Công thức dạng hiện của công thức đệ quy trên là dãy số an=3n an=3n được gọi là nghiệm (lời giải) của công thức đệ quy trên • Chưa có phương pháp giải mọi công thức đệ quy. • Xét một số phương pháp giải: – Phương trình đặc trưng giải Công thức đệ quy tuyến tính thuần nhất hệ số hằng (sẽ viết tắt là CTĐQ TTTNHSH) – Phương pháp thế xuôi – Phương pháp thế ngược – Cây đệ quy 125 1.6. Giải công thức đệ quy: Phương pháp Phương trình đặc trưng Định nghĩa. Công thức đệ qui tuyến tính thuần nhất hệ số hằng bậc k là công thức đệ qui sau an = c1an−1 + + ckan−k trong đó ci là các hằng số, và ck ≠ 0. Giải thích: • Tuyến tính: vế phải là tổng của các số hạng trước số hạng an trong dãy số với các hệ số (c1, c2, ..,ck) là hằng số (không phải là hàm phụ thuộc vào n) • Thuần nhất: vế phải không có thêm số hạng nào khác với các số hạng aj của dãy • Bậc k: vế phải có số hạng thứ (n-k) của dãy Dãy số thoả mãn công thức đã cho là xác định duy nhất nếu đòi hỏi nó thoả mãn k điều kiện đầu: a0 = C0, a1 = C1, ..., ak-1 = Ck-1, trong đó C0, C1, ..., Ck-1 là các hằng số. Ví dụ 1: an = 2an-1 – an-2 với n = 2, 3, 4,... Công thức đệ quy này có một số lời giải như sau: • an=5 an=3n an=n+1 Ví dụ 2: an = 2an-1 – an-2 với n = 2, 3, 4, và các điều kiện đầu: a0=0; a1 = 3  Dãy an=5 không là lời giải của công thức đệ quy đã cho  Dãy an=3n là lời giảicủa công thức đệ quy đã cho 126 • Ví dụ1: Đâu là CTĐQ TTTNHSH 1) an = 4an-1 +2nan-3 2) hn = 2hn-1 + 1 3) bn = 5bn-2 + 2(bn-3) 2 4) qn = 3 qn-6 + qn-8 127 Công thức đệ quy tuyến tính thuần nhất hệ số hằng 128 Ví dụ 2: • Công thức đệ quy Pn = (1.05)Pn-1 Là công thức đệ quy tuyến tính thuần nhất hệ số hằng bậc 1. • Công thức đệ quy fn = fn-1 + fn-2 Là công thức đệ quy tuyến tính thuần nhất hệ số hằng bậc 2. • Công thức đệ quy an = an-5 Là công thức đệ quy tuyến tính thuần nhất hệ số hằng bậc 5. CTĐQ TTTNHSH bậc k NGUYỄN KHÁNH PHƢƠNG Bộ môn KHMT – ĐHBK HN Giải CTĐQ TTTNHSH • Ta sẽ tìm nghiệm dưới dạng an = r n, trong đó r là hằng số. • Dãy số {an = r n } thoả mãn CTĐQ đã cho an = c1an−1 + + ckan−k nếu r thoả mãn phương trình: rn = c1r n−1 + + ckr n−k, hay rk − c1r k−1 − − ck = 0 phương trình đặc trưng, còn nghiệm của nó sẽ được gọi là nghiệm đặc trưng của CTĐQ TTTNHSH. • Ta có thể sử dụng nghiệm đặc trưng để thu được công thức cho dãy số. (chuyển vế và × với rk−n) 129 Giải CTĐQ TTTNHSH Xét công thức đệ quy tuyến tính thuần nhất hệ số hằng bậc 2: an = c1an−1 + c2an−2 Định lý 1. Cho c1, c2 là các hằng số thực. Giả sử phương trình r2 - c1 r - c2 = 0 có 2 nghiệm phân biệt r1 và r2. Khi đó dãy số {an} là nghiệm của công thức đệ quy an = c1 an-1 + c2 an-2 khi và chỉ khi an = 1(r1) n + 2(r2) n (1) n = 0, 1, ..., trong đó 1 , 2 là các hằng số. 130 Giải CTĐQ TTTNHSH • Chứng minh. Trước hết ta chứng minh rằng nếu r1 và r2 là hai nghiệm phân biệt của phương trình đặc trưng, và 1 , 2 là các hằng số, thì dãy số {an} xác định bởi công thức (1) là nghiệm của công thức đệ quy đã cho • Thực vậy, do r1 và r2 là nghiệm đặc trưng nên r1 2 = c1 r1 + c2 , r2 2 = c1 r2 + c2 131 Giải CTĐQ TTTNHSH • Từ đó suy ra c1 an-1 + c2 an-2 = c1 ( 1 r1 n-1 + 2 r2 n-1) + c2 ( 1 r1 n-2 + 2 r2 n-2) = 1 r1 n-2(c1 r1 + c2) + 2 r2 n-2(c1 r2 + c2) = 1 r1 n-2 r1 2 + 2 r2 n-2 r2 2 = 1 r1 n + 2 r2 n = an . 132 Giải CTĐQ TTTNHSH • Bây giờ ta sẽ chỉ ra rằng nghiệm {an} của công thức đệ quy an = c1 an-1 + c2 an-2 luôn có dạng (1) với 1, 2 nào đó. • Thực vậy, giả sử {an} là nghiệm của công thức đệ quy đã cho với điều kiện đầu a0 = C0 , a1 = C1, (2) • Ta chỉ ra rằng có thể tìm được các số 1 , 2 để cho (1) là nghiệm của hệ thức với điều kiện đầu này 133 Giải CTĐQ TTTNHSH • Ta có a0 = C0 = 1 + 2 , a1 = C1 = 1r1 + 2r2. • Hệ phương trình tuyến tính phụ thuộc hai ẩn 1, 2 này có định thức là r2 - r1 0 (do r1 r2) có nghiệm duy nhất 1 = (C1 - C0r2 )/(r1 - r2), 2 = (C0 r1 - C1 )/(r1 - r2). • Với những giá trị của 1 , 2 vừa tìm được, dãy {an} xác định theo (1) là nghiệm của hệ thức đã cho với điều kiện đầu (2). Do hệ thức đã cho cùng với điều kiện đầu (2) xác định duy nhất một dãy số, nên nghiệm của hệ thức được cho bởi công thức (1). Định lý được chứng minh 134 Giải CTĐQ TTTNHSH Ví dụ 1: Tìm lời giải cho công thức đệ quy an = an-1 + 2an-2 với a0 = 2 và a1 = 7 ? • Giải: Phương trình đặc trưng của công thức đệ quy là r2 – r – 2 = 0. Có 2 nghiệm phân biệt r1 = 2 và r2 = -1. Do đó, dãy {an} là lời giải của công thức đệ quy khi và chỉ khi: an = 12 n + 2(-1) n với giá trị nào đó của 1 và 2. Cho biểu thức an = 12 n + 2(-1) n và các điều kiện đầu a0 = 2 và a1 = 7, ta có a0 = 2 = 1 + 2 a1 = 7 = 1 2 + 2 (-1) Giả hệ phương trình này ta có: 1 = 3 và 2 = -1. Do đó, lời giải của công thức đệ quy với ddieuf kiện đầu đã cho là dãy {an} với an = 3 2 n – (-1)n 135 Giải CTĐQ TTTNHSH Ví dụ 2: Tìm lời giải cho công thức đệ quy (dãy Fibonacci) Fn = Fn-1 + Fn-2, n 2, F0 = 0, F1 = 1 Giả: Phương trình đặc trưng của công thức đệ quy r2 – r – 1 = 0. Có 2 nghiệm phân biệt là 136 Leonardo Fibonacci 1170-1250 Trường hợp nghiệm kép Định lý 2: Cho c1, c2 là các hằng số thực, c2 0. Giả sử phương trình r2 - c1 r - c2 = 0 có nghiệm kép r0. Khi đó dãy số {an } là nghiệm của công thức đệ qui an = c1 an-1 + c2 an-2 khi và chỉ khi n = 0, 1, ..., trong đó 1 , 2 là các hằng số. a r n r n n n 1 0 2 0 137NGUYỄN KHÁNH PHƢƠNG Bộ môn KHMT – ĐHBK HN Ví dụ 3 Tìm nghiệm cho công thức đệ quy an = 6 an-1 - 9 an-2 với điều kiện đầu a0 = 1 và a1 = 6. Giải: Phương trình đặc trưng: r2 - 6 r + 9 = 0 có nghiệm kép r = 3. Do đó nghiệm của hệ thức có dạng: an = 1 3 n + 2 n 3 n. Để tìm 1, 2 , sử dụng điều kiện đầu ta có a0 = 1 = 1 , a1 = 6 = 1 . 3 + 2 .1. 3 Giải hệ này ta tìm được 1 = 1 và 2 = 1. Từ đó nghiệm của hệ thức đã cho là: an = 3 n + n 3n . CTĐQ: an = c1an−1 + + ckan−k Phương trình đặc trưng: rk − c1r k−1 − − ck = 0 138 Trường hợp tổng quát Định lý 3. Cho c1, c2, ..., ck là các số thực, ck 0. Giả sử phương trình đặc trưng: rk - c1 r k-1 - c2 r k-2 - . . . - ck = 0 có k nghiệm phân biệt r1, r2, ..., rk . Khi đó dãy số {an} là nghiệm của công thức: an = c1 an-1 + c2 an-2 +...+ ck an-k, khi và chỉ khi an = 1 r1 n + 2 r2 n + . . . + k rk n với n = 0, 1, 2,..., trong đó 1, 2, ..., k là các hằng số 139 Ví dụ 4 Tìm nghiệm của công thức đệ quy an = 6 an-1 - 11 an-2 + 6 an-3 với điều kiện đầu a0 = 2, a1 = 5, a2 = 15. Giải: Phương trình đặc trưng r3 - 6 r2 + 11 r - 6 = 0 có 3 nghiệm r1 = 1, r2 = 2, r3 = 3. Vì vậy, nghiệm có dạng an = 1 1 n + 2 2 n + 3 3 n. CTĐQ: an = c1an−1 + + ckan−k Phương trình đặc trưng: rk − c1r k−1 − − ck = 0 140 Ví dụ 4 Sử dụng các điều kiện đầu ta có hệ phương trình sau đây để xác định các hằng số 1, 2, 3: a0 = 2 = 1 + 2 + 3 a1 = 5 = 1 + 2.2 + 3.3 a2 = 15 = 1 + 2.4 + 3.9. Giải hệ phương trình trên ta thu được 1 = 1, 2 = -1 vµ 3 = 2. Vậy nghiệm của công thức đã cho là an = 1 - 2 n + 2. 3n 141 Trường hợp tổng quát k i inin aca 1 0 1 k i ik i k rcr t i n i m j j jin rna i 1 1 0 , 142 Ví dụ 5 Giải công thức đệ qui: cn = – 4cn-1 + 3cn-2 + 18cn-3 , n 3, c0 = 1; c1 = 2; c2 = 13. Giải: Phương trình đặc trưng r3 + 4r2 – 3r – 18 = (r – 2)(r + 3)2 = 0 Vậy nghiệm tổng quát của công thức: 143 1.6. Giải công thức đệ quy: Các phương pháp khác • Trên thực tế, khi phân tích độ phức tạp của một thuật toán nào đó nhờ sử dụng công thức đệ quy tuyến tính, thì công thức đệ quy ít khi có bậc lớn hơn 2. • Do đó, ta cũng có thể sử dụng hai phương pháp sau đây để giải công thức đệ quy – Thay thế quay lui: xuất phát từ công thức đã cho, ta thế lần lượt lùi về các số hạng phía trước của công thức đệ quy – Cây đệ quy: biểu diễn công thức đệ quy bởi một cây đệ quy. Xuất phát từ công thức đệ quy đã cho, ta biểu diễn các số hạng đệ quy có kích thước dữ liệu đầu vào lớn ở mức A nào đó trên cây bởi các dữ liệu đầu vào nhỏ hơn ở mức A+1 của vây, và tính các số hạng không đệ quy. Cuối cùng, tính tổng tất cả các số hạng không đệ quy ở tất cả các mức của cây. 1.6. Giải công thức đệ quy: Phương pháp 2: Thay thế quay lui Ví dụ 1: Giải công thức đệ quy T(n)= T(n-1) + 2n với T(1) = 5 Giải: Ta tiến hành thay thế lần lượt các số hạng của công thức đệ quy bằng cách lùi lại các số hạng phía trước: T(n) = T(n-1) + 2n = T((n-1) -1) + 2(n-1) + 2n = T(n-2) + 2 (n-1) + 2n = T((n-2)-1) + 2(n-2) + 2(n-1) + 2n = T(n-3) +2(n-2) + 2(n-1) + 2n 1.6. Giải công thức đệ quy: Phương pháp 2: Thay thế quay lui 1.6. Giải công thức đệ quy: Phương pháp 2: Thay thế quay lui Ví dụ 2: Giải công thức đệ quy T(n)= T(n/2) + c với T(1) = 2, và c là hằng số T(n) = T(n/2) + c thay thế T(n/2) = T(n/4) + c + c thay thế T(n/4) = T(n/8) + c + c + c = T(n/23) + 3c = = T(n/2k) + kc T(n) = T(n/2logn) + clogn “chọn k = logn” = T(n/n) + clogn = T(1) + clogn = 2 +clogn Ví dụ 3 Hàm tính giai thừa Xét thuật toán đệ quy tính n! NGUYỄN KHÁNH PHƢƠNG Bộ môn KHMT – ĐHBK HN Bao nhiêu lần hàm Factorial được gọi khi chúng ta thực hiện lệnh Factorial(n); ? • Khi n = 1, hàm Factorial được gọi 1 lần T(1) = 1 • Khi n > 1: – Gọi hàm Factorial 1 lần, – Cộng với số lần gọi trong lệnh đệ quy Factorial(n − 1)  T(n-1) Do đó ta có công thức đệ quy: T(1) = 1 T(n) = 1 + T(n − 1), n >1 Factorial(n); Tìm công thức dạng hiện tính T(n) với mọi giá trị của n T(n) = 1 + T(n-1) Ví dụ 3 1.6. Giải công thức đệ quy: Phương pháp 2: Thay thế quay lui T(n) = T(n − 1) + 1, n >1 = [T(n-2) +1] + 1 [có 2 số “1”] =[[T(n-3)+1]+1]+1 [có 3 số “1”] =. = T(n – (n-1)) + (n-1) [có n-1 số “1”] = T(1) + (n-1) = 1 + (n-1) = n Factorial(n); Có bao nhiêu phép nhân M(n) được thực thi khi thực hiện hàm Factorial? • Khi n = 1 không phép nhân nào được thực hiện M(1) = 0 • Khi n > 1: – Ta thực hiện 1 lần phép nhân. – Cộng với số lần thực hiện phép nhân trong lệnh gọi đệ quy Factorial(n − 1) M(n-1) Do đó ta có công thức đệ quy: M(0) = 0; M(1) = 0 M(n) = 1 + M(n − 1), n >1 Ví dụ 4 1.6. Giải công thức đệ quy: Phương pháp 2: Thay thế quay lui VÝ dô 5. (Bµi to¸n th¸p Hµ néi). Trß ch¬i th¸p Hµ néi ®ư-îc trình bµy như- sau: “Cã 3 cäc a, b, c. Trªn cäc a cã mét chång gåm n c¸i ®Üa ®ư-êng kÝnh gi¶m dÇn tõ d-ưíi lªn trªn. CÇn ph¶i chuyÓn chång ®Üa tõ cäc a sang cäc c tu©n thñ qui t¾c: 1. Mỗi lần chỉ chuyển 1 đĩa 2. Chỉ được xếp đĩa có đường kính nhỏ hơn lên trên đĩa có đường kính lớn hơn. Trong qu¸ trình chuyÓn ®-ưîc phÐp dïng cäc b lµm cäc trung gian. Bµi to¸n ®Æt ra lµ: Tìm công thức đệ qui cho hn là sè lÇn di chuyÓn ®Üa Ýt nhÊt cÇn thùc hiÖn ®Ó hoàn thành nhiÖm vô ®Æt ra trong trß ch¬i th¸p Hµ néi. Cọc a Cọc c Cọc b 152 Tower of Hanoi: n=5 Cọc a Cọc c Cọc b 153 1. Mỗi lần chỉ chuyển 1 đĩa 2. Chỉ được xếp đĩa có đường kính nhỏ hơn lên trên đĩa có đường kính lớn hơn Bài toán: chuyển n đĩa từ cọc a sang cọc c sử dụng cọc b làm trung gian Cần tìm hn là sè lÇn di chuyÓn ®Üa Ýt nhÊt cÇn thùc hiÖn Cọc a Cọc c Cọc b (1) ChuyÓn n-1 ®Üa tõ cäc a ®Õn cäc b sö dông cäc c lµm trung gian. (2) ChuyÓn 1 ®Üa (®Üa víi ®-ưêng kÝnh lín nhÊt) tõ cäc a ®Õn cäc c. (3) ChuyÓn n-1 ®Üa tõ cäc b ®Õn cäc c (sö dông cäc a lµm trung gian). Bài toán kích thước n-1 Số lần di chuyển = hn-1 Bài toán kích thước n-1 Số lần di chuyển = hn-1  Số lần di chuyển = 1 hn = 2hn-1 + 1, n ≥ 2. ViÖc di chuyÓn ®Üa gåm 3 bư-íc: 154 Tower of Hanoi: n=5 Cọc a Cọc c Cọc b (1) ChuyÓn n-1 ®Üa tõ cäc a ®Õn cäc b sö dông cäc c lµm trung gian. (2) ChuyÓn 1 ®Üa (®Üa víi ®-ưêng kÝnh lín nhÊt) tõ cäc a ®Õn cäc c. (3) ChuyÓn n-1 ®Üa tõ cäc b ®Õn cäc c (sö dông cäc a lµm trung gian). Bài toán kích thước n-1 Số lần di chuyển = hn-1 Bài toán kích thước n-1 Số lần di chuyển = hn-1  Số lần di chuyển = 1 155 1.6. Giải công thức đệ quy: Phương pháp 2: Thay thế quay lui Ta có thể tìm được công thức trực tiếp cho hn bằng phương pháp thế quay lui: hn = 2 hn−1 + 1 = 2 (2 hn−2 + 1) + 1 = 2 2 hn−2 + 2 + 1 = 22(2 hn−3 + 1) + 2 + 1 = 2 3 hn−3 + 2 2 + 2 + 1 = 2n−1 h1 + 2 n−2 + + 2 + 1 = 2n−1 + 2n−2 + + 2 + 1 (do h1 = 1) = 2n − 1 156 1.6. Giải công thức đệ quy: Phương pháp 3: Cây đệ quy • Để giải công thức đệ quy bằng phương pháp này: ta sẽ vẽ cây đệ quy mô tả công thức đã cho • Mỗi nút của cây tương ứng với 1 hàm dữ liệu đầu vào. Càng đi xuống phía dưới cây, kích thước dữ liệu đầu vào càng giảm. • Mức cuối cùng của cây tương ứng với kích thước dữ liệu đầu vào nhỏ nhất Ví dụ 1: Thuật toán đệ quy giải bài toán dãy con lớn nhất 158 O(n) O(n) T(n/2) T(n/2) T(n) = 2T(n/2)+O(n) Giải bằng phương pháp cây đệ quy, ta sẽ thu được:  T(n) = O(nlogn) Ví dụ 1: Giải công thức đệ quy: T(n) = 2T(n/2) + n, T(1) = 4 • Giá trị hàm T(n) bằng tổng các giá trị tại tất cả các mức: • Vì mức cuối (sâu nhất) log2n có giá trị = 4n, ta có n*4 1.6. Giải công thức đệ quy: Phương pháp 3: Cây đệ quy • Ví dụ 2: Giải công thức đệ quy T(n) = T(n/ ) + f(n), T( ) = c Ví dụ 2: Giải công thức đệ quy T(n) = T(n/ ) + f(n), T( ) = c Iteration 0 1 2 . . i . log n TT(n) T(n/ ) T(n/ ) T(n/ ) T(n/ 2) T(n/ 2) T(n/ 2) T(n/ 2) Cost f(n) f(n/ ) 2f(n/ 2) . . i f(n/ i) . • Giá trị của hàm bằng tổng các giá trị trên tất cả các mức của cây: 162 NGUYỄN KHÁNH PHƢƠNG Bộ môn KHMT – ĐHBK HN Đầu vào: Mảng S gồm n phần tử: S[0],,S[n-1] đã sắp xếp theo thứ tự tăng dần; Giá trị key. Đầu ra: chỉ số của phần tử có giá trị key nếu có; -1 nếu key không xuất hiện trong mảng S int binsearch(int low, int high, int S[], int key) { if (low <= high) { mid = (low + high) / 2; if (S[mid]==key) return mid; else if (key < S[mid]) return binsearch(low, mid-1, S, key); else return binsearch(mid+1, high, S, key); } else return -1; } Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy 163 821 3 4 65 7 109 11 12 14130 641413 25 33 5143 53 8472 93 95 97966 lo hi int binsearch(int low, int high, int S[], int key) { if (low <= high) { mid = (low + high) / 2; if (S[mid]==key) return mid; else if (key < S[mid]) return binsearch(low, mid-1, S, key); else return binsearch(mid+1, high, S, key); } else return -1; } key=33 Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy 164 821 3 4 65 7 109 11 12 14130 641413 25 33 5143 53 8472 93 95 97966 lo himid int binsearch(int low, int high, int S[], int key) { if (low <= high) { mid = (low + high) / 2; if (S[mid]==key) return mid; else if (key < S[mid]) return binsearch(low, mid-1, S, key); else return binsearch(mid+1, high, S, key); } else return -1; } key=33 Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy 165 821 3 4 65 7 109 11 12 14130 641413 25 33 5143 53 8472 93 95 97966 lo hi int binsearch(int low, int high, int S[], int key) { if (low <= high) { mid = (low + high) / 2; if (S[mid]==key) return mid; else if (key < S[mid]) return binsearch(low, mid-1, S, key); else return binsearch(mid+1, high, S, key); } else return -1; } key=33 Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy 166 821 3 4 65 7 109 11 12 14130 641413 25 33 5143 53 8472 93 95 97966 lo mid hi int binsearch(int low, int high, int S[], int key) { if (low <= high) { mid = (low + high) / 2; if (S[mid]==key) return mid; else if (key < S[mid]) return binsearch(low, mid-1, S, key); else return binsearch(mid+1, high, S, key); } else return -1; } key=33 Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy 167 821 3 4 65 7 109 11 12 14130 641413 25 33 5143 53 8472 93 95 97966 lo hi int binsearch(int low, int high, int S[], int key) { if (low <= high) { mid = (low + high) / 2; if (S[mid]==key) return mid; else if (key < S[mid]) return binsearch(low, mid-1, S, key); else return binsearch(mid+1, high, S, key); } else return -1; } key=33 Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy 168 821 3 4 65 7 109 11 12 14130 641413 25 33 5143 53 8472 93 95 97966 lo himid int binsearch(int low, int high, int S[], int key) { if (low <= high) { mid = (low + high) / 2; if (S[mid]==key) return mid; else if (key < S[mid]) return binsearch(low, mid-1, S, key); else return binsearch(mid+1, high, S, key); } else return -1; } key=33 Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy 169 821 3 4 65 7 109 11 12 14130 641413 25 33 5143 53 8472 93 95 97966 lo hi int binsearch(int low, int high, int S[], int key) { if (low <= high) { mid = (low + high) / 2; if (S[mid]==key) return mid; else if (key < S[mid]) return binsearch(low, mid-1, S, key); else return binsearch(mid+1, high, S, key); } else return -1; } key=33 Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy 170 821 3 4 65 7 109 11 12 14130 641413 25 33 5143 53 8472 93 95 97966 lo hi mid int binsearch(int low, int high, int S[], int key) { if (low <= high) { mid = (low + high) / 2; if (S[mid]==key) return mid; else if (key < S[mid]) return binsearch(low, mid-1, S, key); else return binsearch(mid+1, high, S, key); } else return -1; } key=33 Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy 171 821 3 4 65 7 109 11 12 14130 641413 25 33 5143 53 8472 93 95 97966 lo hi mid int binsearch(int low, int high, int S[], int key) { if (low <= high) { mid = (low + high) / 2; if (S[mid]==key) return mid; else if (key < S[mid]) return binsearch(low, mid-1, S, key); else return binsearch(mid+1, high, S, key); } else return -1; } key=33 key=31?? Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy 172 Đầu vào: Mảng S gồm n phần tử: S[0],,S[n-1] đã sắp xếp theo thứ tự tăng dần; Giá trị key. Đầu ra: chỉ số của phần tử có giá trị key nếu có; -1 nếu key không xuất hiện trong mảng S int binsearch(int low, int high, int S[], int key) { if (low <= high) { mid = (low + high) / 2; if (S[mid]==key) return mid; else if (key < S[mid]) return binsearch(low, mid-1, S, key); else return binsearch(mid+1, high, S, key); } else return -1; }  binsearch(0, n-1, S, key); Có bao nhiêu lần hàm binsearch được gọi trong trường hợp tồi nhất ? Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy 173 int binsearch(int low, int high, int S[], int key) { if (low <= high) { mid = (low + high) / 2; if (S[mid]==key) return mid; else if (key < S[mid]) return binsearch(low, mid-1, S, key); else return binsearch(mid+1, high, S, key); } else return -1; } • T(0) = 1 • T(1) = 2 • T(2) = T(1) + 1 = 3 • T(4) = T(2) + 1 = 4 • T(8) = T(4) + 1 = 4 + 1 = 5 • T(n) = T(n/2) + 1 Công thức đệ quy: T(n) = T(n/2) + 1 T(0) = 1 T(1) = 2 Gọi T(n): số lần hàm binsearch được gọi trong trường hợp tồi nhất khi mảng S có n phần tử  binsearch(0, n-1, S, key);  binsearch(0, -1, S, key);  T(0) = ?  T(1) = ?  binsearch(0, 0, S, key);  binsearch(0, -1, S, key);  binsearch(1, 0, S, key); Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy Bài tập: Hãy giải công thức đệ quy này