Search Algorithm

Trong hầu hết các hệ lưu trữ, quản lý dữ liệu, thao tác tìm kiếm thường được thực hiện nhất để khai thác thông tin. Các câu hỏi thường gặp sẽ xoay quanh các giải thuật tìm kiếm trên số như Tìm kiếm tuyến tính, Tìm kiếm nhị phân và các giải thuật chuyên dụng trên chuỗi như DFA, KMP.

---

Câu hỏi: Nêu ý tưởng của tìm kiếm tuyến tính

Trả lời: Duyệt lần lượt từng phần tử của mảng, nếu trùng thì Dừng. Ngược lại: tiếp tục duyệt

Câu hỏi: Số phép so sánh của tìm kiếm tuyến tính

Trả lời: Trường hợp tốt nhất: số lần so sánh là 1 Trường hợp xấu nhất: số lần so sánh là: n + 1 Trường hợp trung bình: số lần so sánh là (n+1)/2

Câu hỏi: Điều kiện cần của thuật toán Tìm kiếm nhị phân là gì?

Trả lời: Mảng cần tìm kiếm đã được sắp thứ tự.

Câu hỏi: Nêu ý tưởng của tìm kiếm nhị phân

Trả lời: - Chọn một mốc so sánh: thường là phần tử nằm giữa - Nếu giá trị cần tìm nhỏ hơn giá trị nằm giữa: Tìm tiếp từ đầu đến trước giá trị nằm giữa - Nếu giá trị cần tìm lớn hơn giá trị nằm giữa: Tìm tiếp từ giá trị nằm giữa + 1 đến cuối mảng - Nếu bằng giá trị nằm giữa: Kết luận đã tìm thấy

Câu hỏi: Độ phức tạp trung bình của giải thuật tìm kiếm nhị phân.

Trả lời: Độ phức tạp trung bình là O(logn)

Câu hỏi: Nêu cách thực hiện thuật toán DFA (Knuth–Morris–Pratt)

Trả lời: Gọi m là số kí tự trong chuỗi P cần tìm. Σ là tập hợp bảng chữ cái (các kí tự dùng để tạo nên chuỗi). Ta cần tìm vị trí xuất hiện của chuỗi P trong T. B1: Xây dựng bảng DFA - Khởi tạo mảng 2 chiều có m + 1 dòng và số cột bằng số lượng bảng chữ cái dfs[m + 1][|Σ|] = {0}; - Xây dựng DFA Duyệt qua các trạng thái của DFA: cho q chạy từ 0..m Xét từng chữ cái a ∈ Σ: Cho k = trạng thái sau q hoặc là trạng thái cuối nếu q = m Kiểm tra k chữ cái đầu của P có là hậu tố của q chữ cái đầu của P sau khi ghép thêm a không. Nếu như không bằng thì đó không phải là trạng thái tiếp theo cần đến. Nên ta giảm k xuống một đơn vị rồi tiếp tục kiểm tra. Cuối cùng: gán dfa[q][a] = k;

B2: Tiến hành tìm kiếm - Cho biến q = 0 - Duyệt lần lượt qua các chữ cái của chuỗi T - Gán q = dfa[q][T[i]]; // Kiểm tra trạng thái tiếp theo từ trạng thái q nếu gắn thêm kí tự T[i] Nếu q = m thì kết luận vị trí xuất hiện là: i - m + 1

Câu hỏi: Tìm hiểu giải thuật KMP

Trả lời: Xem link Tham khảo