Độ phức tạp thời gian tìm kiếm tuyến tính DSA
Xem trang này để biết giải thích chung về độ phức tạp của thời gian.
Độ phức tạp thời gian tìm kiếm tuyến tính
Để có giải thích chung về độ phức tạp của thời gian, hãy truy cập trang này .
Để được giải thích kỹ lưỡng và chi tiết hơn về độ phức tạp về thời gian Sắp xếp chèn, hãy truy cập trang này .
Tìm kiếm tuyến tính so sánh từng giá trị với giá trị mà nó đang tìm kiếm. Nếu tìm thấy giá trị, chỉ mục sẽ được trả về và nếu không tìm thấy -1 sẽ được trả về.
Để tìm độ phức tạp về thời gian cho Tìm kiếm tuyến tính, hãy xem liệu chúng ta có thể tìm ra cần bao nhiêu thao tác so sánh để tìm một giá trị trong một mảng có các giá trị \(n\) hay không.
Kịch bản Trường hợp Tốt nhất là nếu giá trị chúng ta đang tìm kiếm là giá trị đầu tiên trong mảng. Trong trường hợp như vậy chỉ cần một lần so sánh và độ phức tạp về thời gian là \(O(1)\).
Trường hợp xấu nhất là nếu toàn bộ mảng được xem qua mà không tìm thấy giá trị đích. Trong trường hợp như vậy, tất cả các giá trị trong mảng được so sánh với giá trị đích và độ phức tạp về thời gian là \(O(n)\).
Kịch bản trường hợp trung bình không dễ xác định. Khả năng tìm thấy giá trị mục tiêu là gì? Điều đó phụ thuộc vào các giá trị trong mảng phải không? Nhưng nếu chúng ta giả định rằng chính xác một trong các giá trị trong mảng bằng giá trị đích và vị trí của giá trị đó có thể ở bất kỳ đâu thì thời gian trung bình cần thiết cho Tìm kiếm tuyến tính là một nửa thời gian cần thiết trong trường hợp xấu nhất .
Độ phức tạp về thời gian của Tìm kiếm tuyến tính là \(O(n)\).
Nếu chúng ta rút ra lượng thời gian Tìm kiếm tuyến tính cần để tìm một giá trị trong một mảng các giá trị \(n\), chúng ta sẽ có được biểu đồ này:
Mô phỏng tìm kiếm tuyến tính
Chạy mô phỏng cho số lượng giá trị khác nhau trong một mảng và xem cần bao nhiêu phép so sánh để Tìm kiếm tuyến tính để tìm một giá trị trong một mảng các giá trị \(n\):
{{ this.userX }}
Hoạt động: {{ hoạt động }}
Không tìm thấy!
Như bạn có thể thấy khi chạy mô phỏng Tìm kiếm tuyến tính, việc tìm kiếm yêu cầu ít so sánh nếu giá trị được tìm thấy nhanh, nhưng nếu không tìm thấy giá trị mà chúng ta đang tìm kiếm thì số lần so sánh tối đa sẽ được thực hiện.
