Trả lời nhanh
Thuật toán tìm kiếm tuần tự cần nhiều bước nhất (trường hợp xấu nhất) khi giá trị cần tìm nằm ở vị trí cuối cùng của dãy hoặc không có trong dãy. Khi đó thuật toán phải so sánh lần lượt với cả n phần tử, tức là n bước so sánh. Ví dụ: tìm 5 hoặc 8 trong dãy [7, 3, 9, 1, 5] đều mất 5 lần so sánh.
Nhắc lại cách hoạt động của tìm kiếm tuần tự
Tìm kiếm tuần tự (còn gọi là tìm kiếm tuyến tính) duyệt dãy từ phần tử đầu tiên. Mỗi bước, ta so sánh phần tử đang xét với giá trị cần tìm x. Nếu bằng nhau thì dừng và báo vị trí; nếu duyệt hết dãy mà không thấy thì báo “không tìm thấy”.
Vì dãy không cần sắp xếp trước nên thuật toán rất dễ cài đặt, nhưng số bước phụ thuộc hoàn toàn vào vị trí của x.
def tim_tuan_tu(a, x):
for i in range(len(a)):
if a[i] == x:
return i # tìm thấy tại vị trí i
return -1 # duyệt hết, không có xKhi nào cần nhiều bước nhất?
Gọi n là số phần tử của dãy. Có hai tình huống khiến thuật toán phải làm đủ n lần so sánh:
- x nằm ở vị trí cuối cùng của dãy: n − 1 phần tử đầu đều “sai”, đến phần tử thứ n mới khớp.
- x không có trong dãy: thuật toán phải kiểm tra từng phần tử rồi mới kết luận được là không có.
Lý do: thuật toán không có thông tin nào để bỏ qua phần tử nào, nên chỉ dừng sớm khi gặp đúng x. Nếu x ở cuối hoặc vắng mặt, không có “lối tắt” nào cả.
Ví dụ minh hoạ
Cho dãy a = [7, 3, 9, 1, 5] (n = 5).
| Giá trị cần tìm | Vị trí trong dãy | Số lần so sánh | Trường hợp |
|---|---|---|---|
| 7 | Đầu dãy (1) | 1 | Tốt nhất |
| 9 | Vị trí 3 | 3 | Trung bình |
| 5 | Cuối dãy (5) | 5 | Xấu nhất |
| 8 | Không có | 5 | Xấu nhất |
Với x = 8, ta lần lượt so 8 với 7, 3, 9, 1, 5 – đều không bằng – rồi mới kết luận không có. Tổng cộng 5 lần so sánh, bằng đúng độ dài dãy.
So sánh ba trường hợp
- Tốt nhất: x ở đầu dãy → 1 lần so sánh.
- Xấu nhất: x ở cuối hoặc không có → n lần so sánh.
- Trung bình: nếu x chắc chắn có và có thể ở vị trí nào cũng như nhau, số lần so sánh trung bình là (n + 1)/2. Với n = 5 là (1+2+3+4+5)/5 = 3.
Vì số bước tăng tỉ lệ thuận với n nên người ta nói độ phức tạp thời gian của tìm kiếm tuần tự là O(n) trong trường hợp xấu nhất.
Lỗi sai thường gặp
- Nghĩ rằng “không tìm thấy” thì dừng sớm. Thực ra phải duyệt hết dãy mới chắc chắn là không có (với dãy chưa sắp xếp).
- Nhầm “xấu nhất” là x ở giữa dãy. Giữa dãy chỉ mất khoảng n/2 bước.
- Quên rằng trường hợp xấu nhất có hai kiểu: x ở cuối và x vắng mặt.
Mẹo nhớ
Hãy hình dung bạn tìm một quyển sách trong chồng sách mà chỉ lật từ trên xuống. Quyển sách nằm dưới cùng, hoặc không có trong chồng, thì bạn đều phải lật hết cả chồng.
Bài luyện tập
- Dãy [4, 8, 15, 16, 23, 42] (n = 6). Tìm x = 42, x = 15 và x = 10 mất bao nhiêu lần so sánh?
Đáp án: x = 42 mất 6 lần (cuối dãy); x = 15 mất 3 lần; x = 10 mất 6 lần (không có trong dãy). - Một dãy có 1000 phần tử. Trường hợp xấu nhất cần bao nhiêu lần so sánh? Trường hợp tốt nhất?
Đáp án: xấu nhất 1000 lần; tốt nhất 1 lần. - Nếu dãy đã sắp xếp tăng dần và ta dừng ngay khi gặp phần tử lớn hơn x, trường hợp xấu nhất có còn là n bước không?
Đáp án: Có. Khi x lớn hơn mọi phần tử (hoặc nằm ở cuối), ta vẫn phải duyệt đủ n phần tử, nên trường hợp xấu nhất không đổi, chỉ một số trường hợp “không có” được dừng sớm hơn.
Câu hỏi thường gặp
Tìm kiếm tuần tự cần bao nhiêu bước trong trường hợp xấu nhất?
Cần n lần so sánh, với n là số phần tử của dãy. Điều này xảy ra khi giá trị cần tìm ở cuối dãy hoặc không có trong dãy.
Trường hợp tốt nhất của tìm kiếm tuần tự là gì?
Là khi giá trị cần tìm đứng ngay đầu dãy, thuật toán chỉ cần 1 lần so sánh rồi dừng.
Số lần so sánh trung bình của tìm kiếm tuần tự là bao nhiêu?
Nếu giá trị cần tìm chắc chắn có trong dãy và có khả năng ở mọi vị trí như nhau thì trung bình khoảng (n + 1)/2 lần so sánh.
Dãy đã sắp xếp có giúp tìm kiếm tuần tự nhanh hơn không?
Có thể dừng sớm khi gặp phần tử lớn hơn x, nhưng trường hợp xấu nhất vẫn là n bước nên độ phức tạp vẫn là O(n).