Giải thích
Quảng cáo
3 câu trả lời 135
1) Tìm kiếm tuần tự (Linear Search)
Cách làm:
Duyệt lần lượt từ phần tử đầu đến cuối, gặp đúng thì dừng.
Yêu cầu dữ liệu:
Không cần sắp xếp danh sách.
Tốc độ:
Trường hợp xấu nhất phải xem hết nnn phần tử → O(n) (chậm khi danh sách lớn).
Ưu điểm:
Dễ hiểu, dễ viết.
Dùng được cho mọi danh sách (kể cả chưa sắp xếp).
Nhược điểm:
Danh sách càng dài càng chậm.
2) Tìm kiếm nhị phân (Binary Search)
Cách làm:
So sánh với phần tử ở giữa:
Nếu cần tìm nhỏ hơn → tìm nửa bên trái
Nếu lớn hơn → tìm nửa bên phải
Lặp lại đến khi tìm thấy hoặc hết khoảng.
Yêu cầu dữ liệu:
Danh sách phải được sắp xếp (tăng/giảm).
Tốc độ:
Mỗi lần loại bỏ một nửa danh sách → O(log n) (rất nhanh khi danh sách lớn).
Ưu điểm:
Nhanh hơn tuần tự rất nhiều với dữ liệu lớn.
Nhược điểm:
Bắt buộc dữ liệu phải sắp xếp.
Khó hiểu hơn một chút so với tuần tự.
Bảng so sánh nhanh
Tiêu chí
Tìm kiếm tuần tự
Tìm kiếm nhị phân
Cần sắp xếp dữ liệu?
Không
Có
Cách tìm
Duyệt từng phần tử
Chia đôi liên tục
Tốc độ
O(n)
O(log n)
Khi dùng tốt nhất
Danh sách nhỏ / chưa sắp xếp
Danh sách lớn / đã sắp xếp
- Tìm kiếm nhị phân: chia đôi dãy dữ liệu để tìm. Bắt buộc dữ liệu đã sắp xếp nhưng nhanh hơn nhiều.
Kết luận: Tìm kiếm tuần tự đơn giản nhưng kém hiệu quả; tìm kiếm nhị phân nhanh và hiệu quả hơn khi dữ liệu đã được sắp xếp.
- Tìm kiếm nhị phân: chia đôi dãy dữ liệu để tìm. Bắt buộc dữ liệu đã sắp xếp nhưng nhanh hơn nhiều.
Kết luận: Tìm kiếm tuần tự đơn giản nhưng kém hiệu quả; tìm kiếm nhị phân nhanh và hiệu quả hơn khi dữ liệu đã được sắp xếp.
Quảng cáo
Bạn cần hỏi gì?
Câu hỏi hot cùng chủ đề
-
Đã trả lời bởi chuyên gia
61558 -
Đã trả lời bởi chuyên gia
32993 -
Hỏi từ APP VIETJACK
Đã trả lời bởi chuyên gia
25231 -
Đã trả lời bởi chuyên gia
23788
