[MUSIC CHƠI] DOUG LLOYD: Linear tìm kiếm là một thuật toán chúng tôi có thể sử dụng để tìm một phần tử trong một mảng. Một thuật toán thu hồi là một tập hợp các bước theo các bước các hướng dẫn để hoàn thành một nhiệm vụ. 

Các tìm kiếm tuyến tính thuật toán hoạt động như sau. Lặp qua mảng từ trái sang bên phải, tìm kiếm một yếu tố quy định. 

Trong giả, đó là một nhiều hơn phiên bản cất của câu này, nếu các yếu tố đầu tiên là những gì bạn đang tìm kiếm, bạn có thể dừng lại. Nếu không, di chuyển đến phần tử tiếp theo và tiếp tục đi qua và hơn cho đến khi bạn tìm thấy phần tử, hoặc bạn không. Vì vậy, chúng ta có thể sử dụng tuyến tính thuật toán tìm kiếm, ví dụ, để tìm giá trị mục tiêu chín trong mảng này. Vâng, chúng tôi bắt đầu từ đầu. Nếu đó là những gì chúng tôi tìm kiếm, chúng ta có thể dừng lại. Nó không, chúng ta không tìm kiếm 11. Vì vậy, nếu không, di chuyển đến phần tử tiếp theo. 

Vì vậy, chúng ta nhìn vào 23. 23 điều chúng ta đang tìm kiếm? Cũng không có, vì vậy chúng tôi chuyển sang tiếp theo phần tử, và các phần tử tiếp theo, và chúng tôi tiếp tục đi qua quá trình này hơn và hơn và hơn, cho đến khi chúng tôi hạ cánh vào một tình huống như thế này. 

Chín là những gì chúng tôi đang tìm kiếm, và yếu tố này của mảng là, nó giá trị là chín. Và như vậy, chúng tôi tìm thấy những gì chúng tôi tìm kiếm, và chúng ta có thể dừng lại. Các tìm kiếm tuyến tính có hoàn thành, thành công. 

Nhưng những gì về nếu chúng tôi đang tìm kiếm một yếu tố mà không có trong mảng của chúng tôi. Sao tìm kiếm tuyến tính vẫn làm việc? Vâng chắc chắn. Vì vậy, chúng ta lặp lại quá trình này bắt đầu từ phần tử đầu tiên. Nếu đó là những gì chúng tôi tìm kiếm, chúng ta có thể dừng lại. Nó không phải. Nếu không, chúng tôi di chuyển đến phần tử tiếp theo. 

Nhưng chúng ta có thể tiếp tục lặp lại quá trình này, kiểm tra mỗi phần tử lần lượt, hy vọng rằng chúng ta tìm số 50. Nhưng chúng ta sẽ không biết nếu chúng tôi đã tìm thấy các số 50 hoặc nếu chúng ta không làm, cho đến khi chúng ta đã bước trên mỗi phần tử của mảng. 

Chỉ khi chúng tôi đã thực hiện đó và đi lên ngắn, chúng ta có thể kết luận rằng 50 không có trong mảng. Và do đó, tìm kiếm tuyến tính thuật toán, cũng không thành công, mỗi se. Nhưng không phải trong ý nghĩa rằng nó đã không thành công trong việc làm những gì chúng tôi hỏi nó làm. 

Nó đã không thành công trong khi nhiều khi nó không tìm thấy 50, nhưng 50 không phải là trong mảng. Nhưng chúng tôi đã triệt tìm kiếm qua mọi yếu tố duy nhất và như vậy, trong khi chúng tôi không tìm thấy bất cứ điều gì, tìm kiếm tuyến tính vẫn thành công ngay cả khi yếu tố không có trong mảng. 

Vì vậy, trường hợp xấu nhất là gì kịch bản với tìm kiếm tuyến tính? Vâng, chúng ta phải xem xét thông qua mỗi yếu tố duy nhất, hoặc vì các yếu tố mục tiêu là yếu tố cuối cùng của mảng, hoặc các yếu tố chúng tôi đang tìm kiếm không thực sự tồn tại trong mảng ở tất cả. Trường hợp kịch bản tốt nhất là gì? Vâng, chúng tôi có thể tìm thấy phần tử ngay. Và bao nhiêu yếu tố Chúng ta sau đó phải tìm ở trong trường hợp tốt nhất, nếu chúng ta đang tìm kiếm nó và chúng tôi tìm thấy nó ngay từ đầu? Chúng ta có thể dừng lại ngay lập tức. 

Điều này không nói về phức tạp của tìm kiếm tuyến tính? Cũng trong trường hợp xấu nhất, chúng tôi có nhìn vào từng yếu tố duy nhất. Và do đó, nó chạy trong O n, trong trường hợp xấu nhất. 

Trong trường hợp tốt nhất, chúng tôi đang gonna tìm phần tử ngay lập tức. Và như vậy chạy trong omega của 1. 

Tôi Doug Lloyd. Đây là CS50.