Timtailieu.net 
Phân tích tư tưởng của nhân dân qua đoạn thơ: Những người vợ nhớ chồng… Những cuộc đời đã hóa sông núi ta trong Đất nước của Nguyễn Khoa Điềm
3403
1
0
9 trang
Bài giảng Tìm kiếm (searching) do Lê Sỹ Vinh biên soạn sau đây sẽ trang bị cho các bạn những kiến thức về việc tìm kiếm trên danh sách và tìm kiếm trên văn bản. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về lĩnh vực này.
Nội dung trích xuất từ tài liệu:
Bài giảng Tìm kiếm (searching)Tìm ki m (searching)Lê S VinhB môn Khoa H c Máy Tính – Khoa CNTTi H c Công Ngh - HQGHNEmail: vinhbio@gmail.comCác v nTìm ki m trên danh sách:Có m t danh sách các i tư ng A, tìm xem m tvào danh sách này hay khôngVí d :– Tìm m t sinh viên– m t s i n tho i– Tìm 1 t trong t i n– Tìm 1 lo i hàng hóai tư ng X có thu cCác v nTìm ki m trên văn b n (text matching):Tim ki m s xu t hi n c a m t o n văn b n (1 t , 1 câu, 1 o n…)trong m t văn b n l n. o n văn b n có th xu t hi n chính xác ho cg n chính xác trong văn b n l n.Ví d––Search and replace in editorsSearch engine (yahoo, google…)Tìm ki m trên danh sáchInput:• Danh sách các i tư ng A = (a0,…,an)•i tư ng c n tìm XOutput:• i: v trí xu t hi n c a tư ng X trong A (i = -1 n u X không xu t hi n)Thu t toán: Duy t l n lư t trên danh sách A và so sánh xem X có trong danh sáchhay không. Nêu có tr l i v trí xu t hi n u tiên, n u không tr l i (-1)ph c t p: O(n)Tìm ki m trên danh sách ã ư c s p x pInput:• Danh sách các i tư ng ã ư c s p x p A = (a0,…,an) | ai ≤ ai+1•i tư ng c n tìm XOutput:i: v trí xu t hi n c a tư ng X trong A (i = -1 n u X không xu t hi n)Tìm ki1.2.3.m nh phân: So sánh X v i ph n tgi a danh sách , n uN u b ng → X n m v trí gi a danh sáchN u nh hơn, Tìm ki m X trên n a u c a danh sáchN u l n hơn, Tìm ki m X trên n a cu i c a danh sáchph c t p: O (log n)
