[MÜZİK OYUN] Doug LLOYD: Doğrusal Arama bir algoritma biziz Bir dizide bir eleman bulmak için kullanabilirsiniz. Bir algoritma hatırlama Bir adım-adım seti Bir görevi tamamlamak için talimatları. 

Doğrusal arama aşağıdaki gibi algoritma çalışır. Soldan dizi boyunca yineleme Doğru, belirli bir öğe için arıyor. 

Pseudocode, içinde hangi daha Bu cümlenin distile versiyonu, İlk unsurdur ne olur sen durdurabilirsiniz arıyoruz. Aksi takdirde, bir sonraki öğeye geçmek ve Eğer bulana kadar tekrar tekrar devam eleman, ya da yoktur. Bu yüzden doğrusal kullanabilirsiniz araştırma algoritması, örneğin, Hedef değeri bulmak için Bu dizide dokuz. Peki biz başında başlayacak. Biz konum buysa arıyor, biz durdurabiliriz. Bu, biz 11 aramıyoruz değil. Yani aksi halde, bir sonraki öğeye geçmek. 

Yani biz 23 bakmak. Biz aradığınızı 23 mi? Hayır Eh, bu yüzden bir sonraki geçmek elemanı ve bir sonraki elemanının ve biz aracılığıyla devam ve üzerinde bu işlem ve üzeri kadar biz arazi Böyle bir durumla ilgili. 

Dokuz, biz ne arıyorsanız ve dizinin bu eleman ise, 's değeri dokuz. Ve bu yüzden biz ne konum bulundu arıyor ve biz durdurabiliriz. Doğrusal arama var başarıyla tamamlandı. 

Ama biz için ne arıyorsanız hakkında Bizim dizide değil bir unsur. Doğrusal arama hala çalışıyor mu? İyi emin olun. Yani biz bu işlemi tekrarlayın İlk elemanın başlayan. Biz konum buysa arıyor, biz durdurabiliriz. Bu değil. Aksi takdirde, bir sonraki öğeye geçmek. 

Ama biz, bu işlemi tekrar devam edebilirsiniz sırayla her elemanı inceleyerek, Biz sayı 50 bulmak umuduyla. Ama eğer bilmiyor Biz sayı 50 bulduk we did not ya da eğer biz istifa ettik kadar Dizinin her elemanı üzerinde. 

Sadece biz yaptık bir kere Bu ve kısa gelip biz sonucuna varabiliriz 50 dizisi değildir. Ve böylece lineer arama algoritma, başarısız kuyu, haddi zatında. Ama anlamda öyle yaparken başarısız ne Yapmamız bunu istedi. 

O kadar başarısız oldu o 50 bulamadık kadar, ancak 50 dizide değildi. Ama biz exhaustively aramış her elemanı ile ve bu nedenle, ederken bulamadık şey, doğrusal arama hala başarılı olsa bile elemanı dizisinde değildir. 

Peki kötü durumda bulunuyor Doğrusal arama ile senaryo? Peki biz bakmak zorunda her eleman, ya çünkü hedef elemanı dizinin son elemanı olduğunu ya da biz arıyoruz eleman yok Aslında tüm dizide var. En iyi senaryo nedir? Peki biz bulabiliriz Hemen elemanı. Ve kaç unsurlar biz sonra bakmak zorunda En iyi durumda, en, biz bunun için arıyorsanız ve biz çok başında bulabilirsiniz? Biz hemen durdurabilirsiniz. 

Bu konuda ne diyor Lineer arama karmaşıklığı? Peki en kötü durumda, biz her elemana bakmak için. Ve böylece bir O çalışır n, en kötü durumda. 

En iyi durumda, seni Hemen elemanı bulmak. Ve böylece 1 omega çalışır. 

Ben Doug Lloyd değilim. Bu CS50 olduğunu.