Đang chuẩn bị liên kết để tải về tài liệu:
PHÂN TÍCH CÁC GIẢI THUẬT TÌM KIẾM

Bắt đầu từ phần tử đầu tiên của danh sách, so sánh lần lượt từng phần tử của danh sách với giá trị X cần tìm. Nếu có phần tử bằng X thì trả về vị trí tìm thấy, thuật toán dừng lại (thành công). Giải thuật tìm kiếm tuần tự, nhị phân trên danh sách liên kết. | PHÂN TÍCH CÁC GIẢI THUẬT TÌM KIẾM Nội dung Giải thuật tìm kiếm tuần tự, nhị phân trên danh sách liên kết Phân tích các thao tác trên cây tìm kiếm nhị phân Phân tích các kỹ thuật băm Phân tích một vài giải thuật so trùng chuỗi 2. Tìm tuyến tính (Linear Seach) Ý tưởng: Bắt đầu từ phần tử đầu tiên của danh sách, so sánh lần lượt từng phần tử của danh sách với giá trị X cần tìm Nếu có phần tử bằng X thì trả về vị trí tìm thấy, thuật toán dừng lại (thành công) Nếu đến cuối danh sách mà không có phần tử nào bằng X, thuật toán dừng lại (không thành công) Tìm tuyến tính (Linear Seach) 5 Khóa tìm 7 13 5 21 6 2 8 15 0 1 2 3 4 5 6 7 Vị trí = 2 Tìm thành công Số lần so sánh: 3 9 7 13 5 21 6 2 8 15 0 1 2 3 4 5 6 7 Không tìm thấy Số lần so sánh: 8 Khóa tìm 2. Tìm tuyến tính (Linear Seach) Tìm tuyến tính (Linear Seach) int LSearch(int list[], int n, int key) { int find= -1; for (int i=0; i int . | PHÂN TÍCH CÁC GIẢI THUẬT TÌM KIẾM Nội dung Giải thuật tìm kiếm tuần tự, nhị phân trên danh sách liên kết Phân tích các thao tác trên cây tìm kiếm nhị phân Phân tích các kỹ thuật băm Phân tích một vài giải thuật so trùng chuỗi 2. Tìm tuyến tính (Linear Seach) Ý tưởng: Bắt đầu từ phần tử đầu tiên của danh sách, so sánh lần lượt từng phần tử của danh sách với giá trị X cần tìm Nếu có phần tử bằng X thì trả về vị trí tìm thấy, thuật toán dừng lại (thành công) Nếu đến cuối danh sách mà không có phần tử nào bằng X, thuật toán dừng lại (không thành công) Tìm tuyến tính (Linear Seach) 5 Khóa tìm 7 13 5 21 6 2 8 15 0 1 2 3 4 5 6 7 Vị trí = 2 Tìm thành công Số lần so sánh: 3 9 7 13 5 21 6 2 8 15 0 1 2 3 4 5 6 7 Không tìm thấy Số lần so sánh: 8 Khóa tìm 2. Tìm tuyến tính (Linear Seach) Tìm tuyến tính (Linear Seach) int LSearch(int list[], int n, int key) { int find= -1; for (int i=0; i int LinearSearch(int a[], int N, int key) { int i=0; while ((i Giảm bớt một phép so sánh trong vòng lặp 2. Tìm tuyến tính (Linear Seach) Phân tích, đánh giá thuật toán Vậy giải thuật tìm tuyến tính có độ phức tạp tính toán cấp n: T(n) = O(n) Giải thuật tìm tuyến tính không phụ thuộc vào thứ tự của các phần tử mảng, do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy số bất kỳ. Trường hợp Số lần so sánh Giải thích Tốt .