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 Cấu trúc dữ liệu và giải thuật: Giải thuật tìm kiếm trình bày các nội dung sau: Còn gọi là tuyến tính – Linear search, danh sách chưa sắp xếp hoặc đã sắp xếp, thời gian tỉ lệ với n (số phần tử), độ phức tạp O(n),...
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Giải thuật tìm kiếm - TS. Ngô Hữu DũngTRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINHCấu trúc dữ liệu và giải thuậtGiải thuật tìm kiếmTS. Ngô Hữu DũngTìm kiếm – SearchingTìm kiếm tuần tự - Sequential searchTìm kiếm nhị phân – Binary search2Còn gọi là tuyến tính – Linear searchDanh sách chưa sắp xếp hoặc đã sắp xếpThời gian tỉ lệ với n (số phần tử)Độ phức tạp O(n)Danh sách đã sắp xếpThời gian tỉ lệ với log2 nĐộ phức tạp O(log n)Cấu trúc dữ liệu và giải thuật - Tìm kiếmSequential searchDuyệt danh sách từ đầu đến cuối3Dừng khi tìm thấy hoặc kết thúc danh sáchNếu tìm thấy: Trả về kết quả tìm thấy True hoặc vị trí được tìm thấy hoặc thông báoNếu không tìm thấy: Trả về kết quả không tìm thấy False hoặc một giá trị như -1 hoặc thông báoCấu trúc dữ liệu và giải thuật - Tìm kiếmSequential search – Vòng lặpTrả về vị trí khi tìm thấy Trả về -1 khi không tìm thấyLưu ý: Các code chỉ mang tính minh hoạ cho giải thuật Có nhiều cách diễn đạt và cải tiến thuật toán1. int linearSearch(int a[], int n, int x)2. {3.int i;4.for(i=0; i
