Linear Search Visualization with Animations

Mô phỏng thuật toán Linear Search

Mô phỏng

Giải thích

Linear Search (Tìm kiếm tuần tự) là thuật toán tìm kiếm đơn giản nhất. Nó kiểm tra mỗi phần tử của mảng một cách tuần tự cho đến khi tìm thấy phần tử mong muốn hoặc duyệt qua toàn bộ mảng.

Đang xét

Đã kiểm tra

Phần tử tìm thấy

def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i  # tìm thấy
    return -1  # không tìm thấy
            

Nhật ký thực thi:

Giải thích thuật toán Linear Search

Linear Search là thuật toán tìm kiếm đơn giản nhất trong khoa học máy tính. Thuật toán này duyệt qua từng phần tử của mảng một cách tuần tự để tìm kiếm giá trị cần tìm.

Nguyên lý hoạt động:

Bắt đầu từ phần tử đầu tiên của mảng (i = 0)
So sánh giá trị cần tìm với phần tử hiện tại
Nếu khớp, trả về vị trí hiện tại và kết thúc
Nếu không khớp, chuyển đến phần tử tiếp theo (i++)
Lặp lại bước 2-4 cho đến khi tìm thấy hoặc hết mảng
Nếu đã kiểm tra hết mảng mà không tìm thấy, trả về -1

def linear_search(arr, x): for i in range(len(arr)): # Duyệt qua từng phần tử if arr[i] == x: # So sánh với giá trị cần tìm return i # Trả về vị trí nếu tìm thấy return -1 # Trả về -1 nếu không tìm thấy

Độ phức tạp:

Độ phức tạp thời gian: O(n) - trong trường hợp xấu nhất, cần kiểm tra tất cả n phần tử của mảng
Độ phức tạp không gian: O(1) - chỉ sử dụng một số lượng biến cố định

Ưu điểm và nhược điểm:

Ưu điểm:

Đơn giản, dễ hiểu và dễ triển khai
Không yêu cầu mảng phải được sắp xếp
Hiệu quả với mảng nhỏ hoặc danh sách liên kết
Không cần bất kỳ điều kiện tiên quyết nào về dữ liệu

Nhược điểm:

Không hiệu quả với mảng lớn
Chậm hơn nhiều so với các thuật toán tìm kiếm khác như Binary Search (với mảng đã sắp xếp)
Độ phức tạp thời gian tuyến tính O(n) không tối ưu cho dữ liệu lớn

So sánh với Binary Search:

Tiêu chí	Linear Search	Binary Search
Độ phức tạp thời gian	O(n)	O(log n)
Yêu cầu mảng sắp xếp	Không	Có
Triển khai	Đơn giản	Phức tạp hơn
Hiệu quả với dữ liệu lớn	Không	Có

Ứng dụng:

Tìm kiếm trong mảng nhỏ hoặc danh sách liên kết
Khi mảng không được sắp xếp và chi phí sắp xếp cao hơn lợi ích của việc tìm kiếm nhanh
Khi cần tìm kiếm tất cả các phần tử thỏa mãn điều kiện (không chỉ phần tử đầu tiên)
Khi các phần tử được truy cập ngẫu nhiên tốn kém (như trong danh sách liên kết)

Trang chủ Thuật toán

Thuật toán tìm kiếm tuần tự