TAILIEUCHUNG - 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ũng

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),. | TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH 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ũng Tìm kiếm – Searching Tìm kiếm tuần tự - Sequential search Tìm kiếm nhị phân – Binary search 2 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) Danh sách đã sắp xếp Thờ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ếm Sequential search Duyệt danh sách từ đầu đến cuối 3 Dừng khi tìm thấy hoặc kết thúc danh sách Nế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áo Nế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áo Cấu trúc dữ liệu và giải thuật - Tìm kiếm Sequential search – Vòng lặp Trả về vị trí khi tìm thấy Trả về -1 khi không tìm thấy Lư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án 1. int linearSearch(int a[], int n, int x) 2. { 3. int i; 4. for(i=0; i

• Cơ sở dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu
• Giải thuật tìm kiếm
• Cách đo thời gian
• Tìm kiếm tuần tự
• Tìm kiếm nhị phân
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• tài liệu Cấu trúc dữ liệu và giải thuật
• giáo trình Cấu trúc dữ liệu và giải thuật
• bài tập Cấu trúc dữ liệu và giải thuật
• Ngôn ngữ diễn đạt giải thuật
• Thiết kế và phân tích giải thuật
• Giải thuật đệ quy
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu cơ bản
• Kiểu dữ liệu trừu tượng
• Tổng quan về giải thuật
• Kiểu dữ liệu
• Các tiêu chuẩn đánh giá dữ liệu
• Cách diễn đạt giải thuật
• Phân tích giải thuật
• phân tích thiết kế
• thiết kế hướng đối tượng
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm