Giải (?) Câu hỏi mục II Câu hỏi 3 Bài 19. Bài toán tìm kiếm (trang 89) – SGK Tin học 11 Kết nối tri thức. Gợi ý: Tra cứu trên internet, sách, báo, …kết hợp kiến thức thực tế của bản thân để trả lời câu hỏi.
Câu hỏi/Đề bài:
Khi nào thì tìm kiếm tuần tự sẽ cần nhiều bước nhất? Cho ví dụ.
Hướng dẫn:
Tra cứu trên internet, sách, báo,…kết hợp kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải:
Thuật toán tìm kiếm tuần tự sẽ cần nhiều bước nhất khi phải duyệt qua toàn bộ dãy số để tìm kiếm phần tử cần tìm, tức là phần tử đó nằm ở cuối dãy hoặc không có trong dãy. Đây là trường hợp xấu nhất của thuật toán tìm kiếm tuần tự.
Ví dụ: Giả sử chúng ta cần tìm phần tử có giá trị là 100 trong dãy A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Phần tử này không có trong dãy, và thuật toán tìm kiếm tuần tự sẽ phải duyệt qua toàn bộ dãy 10 phần tử để xác nhận rằng phần tử này không có trong dãy.
Vậy, trong trường hợp xấu nhất, số lần duyệt cần thực hiện là đúng bằng số phần tử trong dãy. Trong ví dụ trên, số lần duyệt cần thực hiện là 10 lần để tìm kiếm phần tử không có trong dãy.