- Mục tiêu
- Đang so sánh
- Đã loại
- Đã tìm thấy
Tìm kiếm tuyến tính
Tìm kiếm tuyến tính là cách đơn giản nhất để tìm một giá trị: bắt đầu từ đầu và kiểm tra lần lượt từng giá trị cho đến khi thấy nó. Nó dùng được cho mọi danh sách, đã sắp xếp hay chưa. Chọn giá trị cần tìm, phát quá trình tìm kiếm hoặc đi từng phép so sánh, và xem chi phí phụ thuộc thế nào vào vị trí của giá trị, hay nó có trong danh sách hay không. Nhấn Phát để xem quá trình tìm kiếm, hoặc Bước và Lùi để đi từng phép so sánh. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Đường nét đứt đánh dấu giá trị cần tìm. Chọn giá trị đó, số cột, thứ tự ban đầu, hoặc tự nhập các số. Tắt Dừng khi khớp lần đầu để tìm mọi giá trị khớp. Khi bảng được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.
Cách nó hoạt động
- Chọn giá trị cần tìm, số cột và thứ tự ban đầu. Hoặc tự nhập các số.
- Nhấn Phát, hoặc dùng Bước và Lùi để đi từng phép so sánh. Kéo thanh trượt bước để nhảy đến bất kỳ đâu trong quá trình tìm kiếm.
- Tắt Dừng khi khớp lần đầu để kiểm tra mọi giá trị và tìm tất cả các giá trị khớp.
Cách tìm kiếm tuyến tính hoạt động
So sánh giá trị đầu tiên với giá trị cần tìm. Nếu bằng nhau thì xong. Nếu không, chuyển sang giá trị thứ hai, rồi thứ ba, và cứ thế. Nếu đến cuối danh sách mà không có giá trị nào khớp, giá trị cần tìm không có trong danh sách. Không cần chuẩn bị gì: danh sách không cần được sắp xếp.
Bao nhiêu phép so sánh
Giá trị ở vị trí k được tìm thấy sau k phép so sánh. Trường hợp tốt nhất là một phép so sánh, khi giá trị cần tìm đứng đầu. Trường hợp xấu nhất là n, khi nó đứng cuối hoặc không có, vì chỉ sau khi kiểm tra mọi giá trị mới chắc chắn được là nó không có. Trung bình, với giá trị có trong danh sách, cần khoảng (n + 1)/2. Với danh sách đã sắp xếp, tìm kiếm nhị phân tốt hơn nhiều: khoảng log₂ n phép so sánh, 6 thay vì tối đa 40 với 40 giá trị.
Câu hỏi thường gặp
Tìm kiếm tuyến tính hoạt động thế nào?
Nó kiểm tra từng giá trị của danh sách, từ đầu đến cuối, cho đến khi tìm thấy giá trị cần tìm hoặc hết giá trị. Nó còn được gọi là tìm kiếm tuần tự.
Độ phức tạp thời gian của tìm kiếm tuyến tính là bao nhiêu?
O(n): trong trường hợp xấu nhất, khi giá trị cần tìm đứng cuối hoặc không có, nó so sánh giá trị cần tìm với cả n giá trị. Trung bình, với giá trị có trong danh sách, cần khoảng (n + 1)/2 phép so sánh.
Khi nào nên dùng tìm kiếm tuyến tính?
Với danh sách ngắn, danh sách chưa sắp xếp và chỉ tìm một hai lần, và dữ liệu chỉ đọc được theo thứ tự, như một luồng dữ liệu. Sắp xếp trước để dùng tìm kiếm nhị phân chỉ đáng khi bạn tìm nhiều lần.
Vì sao giá trị không có lại tốn nhiều nhất?
Vì không có gì báo cho tìm kiếm tuyến tính dừng sớm. Chỉ có thể loại trừ khả năng khớp bằng cách kiểm tra mọi giá trị, nên giá trị không có trong danh sách luôn cần n phép so sánh.
Các số của tôi có bị gửi đi đâu không?
Không. Việc tìm kiếm chạy trong trình duyệt của bạn, và các cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Tới trình chỉnh sửa