Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 7: Tìm kiếm

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 7: Tìm kiếm

1. Quản lý danh sách có thứ tự Thừa hưởng từ List và Hiệu chỉnh (override) lại các phương thức insert, replace: Đảm bảo là danh sách kết quả vẫn còn thứ tự. Thiết kế thêm (overload) phương thức insert mới không cần tham số position. class Ordered_list: public List { public: Error_code insert (const Record &data); }; 11 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
2. Thêm vào danh sách có thứ tự - Giải thuật Algorithm Insert Input: x là giá trị cần thêm vào Output: danh sách đã thêm x vào và vẫn có thứ tự // Đi tìm vị trí position mà khóa của x nằm giữa khóa của các phần từ // tại vị trí position – 1 và position. 1. for position = 0 to size 1.1. list_data = phần tử tại vị trí position 1.2. if x nhỏ hơn hoặc bằng list_data 1.2.1. thêm vào tại vị trí này 1.2.2. ngừng lại End Insert 12 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
3. Thêm vào danh sách có thứ tự - Mã C++ Error_code Ordered_list :: insert(const Record &data) /* Post: If the Ordered_list is not full, the function succeeds: The Record data is inserted into the list, following the last entry of the list with a strictly lesser key (or in the rst list position if no list element has a lesser key). Else: the function fails with the diagnostic Error_code overflow. */ { int s = size( ); int position; for (position = 0; position :: insert(position, data); } 13 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
4. Thêm vào danh sách (viết đè) - Giải thuật Algorithm Insert_overridden Input: position là vị trí cần thêm vào, x là giá trị cần thêm vào Output: danh sách đã thêm x vào và vẫn có thứ tự // Kiểm tra xem có thỏa mãn mà khóa của x nằm giữa khóa của // các phần từ tại vị trí position – 1 và position. 1. if position > 0 1.1. list_data = phần tử tại vị trí position -1 1.2. if x nhỏ hơn list_data 1.2.1. có lỗi 2. if position < count 2.1. list_data = phần tử tại vị trí position 2.2. if x lớn hơn list_data 2.2.1. có lỗi 3. Thêm vào tại vị trí này End Insert_overridden 14 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
5. Tìm nhị phân (binary search) Ý tưởng: So sánh khóa cần tìm với phần tử giữa. Nếu nó nhỏ hơn thì tìm bên trái danh sách. Ngược lại tìm bên phải danh sách. Lặp lại động tác này. Cần 2 chỉ mục top và bottom để giới hạn đoạn tìm kiếm trên danh sách. Khóa cần tìm nếu có chỉ nằm trong đoạn này. 15 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
6. Tìm nhị phân – Cách 2 position = 3 10 Khóa cần tìm khôngnhỏlớnbằng hơnhơn bằng Target key 0 1 2 3 4 5 6 7 8 9 2 5 8 10 12 13 15 18 21 24 bottom middle top return success Số lần so sánh: 7 16 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
7. Tìm nhị phân – Giải thuật 2 Algorithm Binary_search2 Input: target là khóa cần tìm, bottom và top là giới hạn danh sách Output: position là vị trí nếu tìm thấy 1. if bottom > top 1.1. return not_present 2. if bottom <= top 2.1. list_data = phần tử tại vị trí mid = (bottom + top)/2 2.2. if x == list_data 2.2.1. position = mid 2.2.2. return success 2.3. if x < list_data 2.3.1. call Binary_search2 với đoạn bên trái (bottom, mid-1) 2.4. else 2.4.1. call Binary_search2 với đoạn bên phải (mid+1, top) End Binary_search2 17 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
8. Tìm nhị phân 2 – Mã C++ Error_code recursive_binary_2(const Ordered_list &the list, const Key &target, int bottom, int top, int &position) { Record data; if (bottom <= top) { int mid = (bottom + top)/2; the_list.retrieve(mid, data); if (data == target) { position = mid; return success; } else if (data < target) return recursive_binary_2(the list, target, mid + 1, top, position); else return recursive_binary_2(the list, target, bottom, mid − 1, position); } else return not_present; } 18 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
9. Tìm nhị phân – Cách 1 position = 3 10 Target key Khóa cần tìm nhỏlớnbằng hơnhơn hoặc bằng 0 1 2 3 4 5 6 7 8 9 2 5 8 10 12 13 15 18 21 24 bottom middle top return success Số lần so sánh: 4 19 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
10. Tìm nhị phân – Giải thuật 1 Algorithm Binary_search1 Input: target là khóa cần tìm, bottom và top là giới hạn danh sách Output: position là vị trí nếu tìm thấy 1. if bottom == top 1.1. if x == phần tử tại vị trí bottom 1.1.1. position = bottom 1.1.2. return success 2. if bottom > top 2.1. return not_present 3. if bottom < top 3.1. if x < phần tử tại vị trí mid = (bottom + top)/2 3.1.1. call Binary_search1 với đoạn bên trái (bottom, mid-1) 3.2. else 3.2.1. call Binary_search1 với đoạn bên phải (mid, top) End Binary_search1 20 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
11. Tìm nhị phân 1 – Mã C++ Error_code recursive_binary_1(const Ordered_list &the_list, const Key &target, int bottom, int top, int &position) { Record data; if (bottom < top) { // List has more than one entry. the_list.retrieve((bottom + top)/2, data); if (data < target) return recursive_binary_1(the list, target, mid + 1, top, position); else // Reduce to bottom half of list. return recursive_binary_1(the list, target, bottom, mid, position); } else if (top < bottom) return not_present; // List is empty. else { position = bottom; the_list.retrieve(bottom, data); if (data == target) return success; else return not_present; } } 21 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
12. Cây so sánh của giải thuật 1 22 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
13. Cây so sánh của giải thuật 2 23 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
14. Tìm nhị phân – Đánh giá 24 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
15. So sánh trong trường hợp trung bình các giải thuật 25 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
16. Đánh giá độ phức tạp của giải thuật So sánh với các hàm cơ bản: g(n) = 1 Constant function g(n) = log n Logarithmic function g(n) = n Linear function g(n) = n2 Quadratic function g(n) = n3 Cubic function g(n) = 2n Exponential function 26 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
17. Độ phức tạp tính bằng tiệm cận 27 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
18. Độ tăng của các hàm chung 28 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm
19. Ký hiệu Big-O f(n) Bậc của f so với g limn->∞ (f(n)/g(n) o(g(n)) < : nhỏ hơn hẳn 0 O(g(n)) ≤ : nhỏ hơn hoặc bằng a Θ(g(n)) = : bằng a ≠ 0 Ω(g(n)) ≥ : lớn hơn hoặc bằng a ≠ 0 hoặc là ∞ Thứ tự tăng dần về độ lớn: O(1) O(lg n) O(n) O(n lg n) O(n2) O(n3) O(2n) 29 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 7. Tìm kiếm