1
00:00:00,000 --> 00:00:02,892
>> [MÜZİK OYUN]

2
00:00:02,892 --> 00:00:05,347

3
00:00:05,347 --> 00:00:07,180
Doug LLOYD: Doğrusal
Arama bir algoritma biziz

4
00:00:07,180 --> 00:00:09,840
Bir dizide bir eleman bulmak için kullanabilirsiniz.

5
00:00:09,840 --> 00:00:11,990
Bir algoritma hatırlama
Bir adım-adım seti

6
00:00:11,990 --> 00:00:15,030
Bir görevi tamamlamak için talimatları.

7
00:00:15,030 --> 00:00:17,480
>> Doğrusal arama
aşağıdaki gibi algoritma çalışır.

8
00:00:17,480 --> 00:00:22,200
Soldan dizi boyunca yineleme
Doğru, belirli bir öğe için arıyor.

9
00:00:22,200 --> 00:00:26,380
>> Pseudocode, içinde hangi daha
Bu cümlenin distile versiyonu,

10
00:00:26,380 --> 00:00:29,840
İlk unsurdur ne olur
sen durdurabilirsiniz arıyoruz.

11
00:00:29,840 --> 00:00:33,930
Aksi takdirde, bir sonraki öğeye geçmek ve
Eğer bulana kadar tekrar tekrar devam

12
00:00:33,930 --> 00:00:36,389
eleman, ya da yoktur.

13
00:00:36,389 --> 00:00:38,680
Bu yüzden doğrusal kullanabilirsiniz
araştırma algoritması, örneğin,

14
00:00:38,680 --> 00:00:42,330
Hedef değeri bulmak için
Bu dizide dokuz.

15
00:00:42,330 --> 00:00:43,870
Peki biz başında başlayacak.

16
00:00:43,870 --> 00:00:45,970
Biz konum buysa
arıyor, biz durdurabiliriz.

17
00:00:45,970 --> 00:00:47,890
Bu, biz 11 aramıyoruz değil.

18
00:00:47,890 --> 00:00:50,220
Yani aksi halde, bir sonraki öğeye geçmek.

19
00:00:50,220 --> 00:00:51,510
>> Yani biz 23 bakmak.

20
00:00:51,510 --> 00:00:52,730
Biz aradığınızı 23 mi?

21
00:00:52,730 --> 00:00:55,614
Hayır Eh, bu yüzden bir sonraki geçmek
elemanı ve bir sonraki elemanının

22
00:00:55,614 --> 00:00:57,780
ve biz aracılığıyla devam
ve üzerinde bu işlem

23
00:00:57,780 --> 00:01:01,030
ve üzeri kadar biz arazi
Böyle bir durumla ilgili.

24
00:01:01,030 --> 00:01:03,910
>> Dokuz, biz ne arıyorsanız
ve dizinin bu eleman

25
00:01:03,910 --> 00:01:05,787
ise, 's değeri dokuz.

26
00:01:05,787 --> 00:01:08,120
Ve bu yüzden biz ne konum bulundu
arıyor ve biz durdurabiliriz.

27
00:01:08,120 --> 00:01:11,910
Doğrusal arama var
başarıyla tamamlandı.

28
00:01:11,910 --> 00:01:15,370
>> Ama biz için ne arıyorsanız hakkında
Bizim dizide değil bir unsur.

29
00:01:15,370 --> 00:01:17,040
Doğrusal arama hala çalışıyor mu?

30
00:01:17,040 --> 00:01:17,540
İyi emin olun.

31
00:01:17,540 --> 00:01:19,947
Yani biz bu işlemi tekrarlayın
İlk elemanın başlayan.

32
00:01:19,947 --> 00:01:21,780
Biz konum buysa
arıyor, biz durdurabiliriz.

33
00:01:21,780 --> 00:01:22,800
Bu değil.

34
00:01:22,800 --> 00:01:25,020
Aksi takdirde, bir sonraki öğeye geçmek.

35
00:01:25,020 --> 00:01:29,050
>> Ama biz, bu işlemi tekrar devam edebilirsiniz
sırayla her elemanı inceleyerek,

36
00:01:29,050 --> 00:01:31,720
Biz sayı 50 bulmak umuduyla.

37
00:01:31,720 --> 00:01:33,750
Ama eğer bilmiyor
Biz sayı 50 bulduk

38
00:01:33,750 --> 00:01:38,290
we did not ya da eğer biz istifa ettik kadar
Dizinin her elemanı üzerinde.

39
00:01:38,290 --> 00:01:40,440
>> Sadece biz yaptık bir kere
Bu ve kısa gelip

40
00:01:40,440 --> 00:01:43,040
biz sonucuna varabiliriz
50 dizisi değildir.

41
00:01:43,040 --> 00:01:46,410
Ve böylece lineer arama
algoritma, başarısız kuyu, haddi zatında.

42
00:01:46,410 --> 00:01:49,181
Ama anlamda öyle
yaparken başarısız ne

43
00:01:49,181 --> 00:01:49,930
Yapmamız bunu istedi.

44
00:01:49,930 --> 00:01:52,390
>> O kadar başarısız oldu
o 50 bulamadık kadar,

45
00:01:52,390 --> 00:01:54,070
ancak 50 dizide değildi.

46
00:01:54,070 --> 00:01:57,310
Ama biz exhaustively aramış
her elemanı ile

47
00:01:57,310 --> 00:02:00,550
ve bu nedenle, ederken bulamadık
şey, doğrusal arama hala

48
00:02:00,550 --> 00:02:05,230
başarılı olsa bile
elemanı dizisinde değildir.

49
00:02:05,230 --> 00:02:07,507
>> Peki kötü durumda bulunuyor
Doğrusal arama ile senaryo?

50
00:02:07,507 --> 00:02:09,590
Peki biz bakmak zorunda
her eleman,

51
00:02:09,590 --> 00:02:14,590
ya çünkü hedef elemanı
dizinin son elemanı olduğunu

52
00:02:14,590 --> 00:02:18,510
ya da biz arıyoruz eleman yok
Aslında tüm dizide var.

53
00:02:18,510 --> 00:02:19,760
En iyi senaryo nedir?

54
00:02:19,760 --> 00:02:22,430
Peki biz bulabiliriz
Hemen elemanı.

55
00:02:22,430 --> 00:02:24,360
Ve kaç unsurlar
biz sonra bakmak zorunda

56
00:02:24,360 --> 00:02:26,859
En iyi durumda, en,
biz bunun için arıyorsanız

57
00:02:26,859 --> 00:02:28,400
ve biz çok başında bulabilirsiniz?

58
00:02:28,400 --> 00:02:29,850
Biz hemen durdurabilirsiniz.

59
00:02:29,850 --> 00:02:32,984
>> Bu konuda ne diyor
Lineer arama karmaşıklığı?

60
00:02:32,984 --> 00:02:35,650
Peki en kötü durumda, biz
her elemana bakmak için.

61
00:02:35,650 --> 00:02:38,930
Ve böylece bir O çalışır
n, en kötü durumda.

62
00:02:38,930 --> 00:02:41,540
>> En iyi durumda, seni
Hemen elemanı bulmak.

63
00:02:41,540 --> 00:02:44,750
Ve böylece 1 omega çalışır.

64
00:02:44,750 --> 00:02:45,780
>> Ben Doug Lloyd değilim.

65
00:02:45,780 --> 00:02:48,020
Bu CS50 olduğunu.

66
00:02:48,020 --> 00:02:49,876