1
00:00:00,000 --> 00:00:02,892
>> [Mūzikas atskaņošanai]

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

3
00:00:05,347 --> 00:00:07,180
Doug LLOYD: Linear
meklēšana ir algoritms mums

4
00:00:07,180 --> 00:00:09,840
var izmantot, lai atrastu elements masīva.

5
00:00:09,840 --> 00:00:11,990
Algoritms atsaukšana
ir soli pa solim komplekts

6
00:00:11,990 --> 00:00:15,030
par norādījumiem, kā pabeigt uzdevumu.

7
00:00:15,030 --> 00:00:17,480
>> Lineārais meklēšana
algoritms darbojas šādi.

8
00:00:17,480 --> 00:00:22,200
Atkārtot pāri masīvs no kreisās uz
pa labi, skatoties uz noteiktu elementu.

9
00:00:22,200 --> 00:00:26,380
>> In pseudocode, kas ir vairāk
destilēts versiju šo teikumu,

10
00:00:26,380 --> 00:00:29,840
ja pirmais elements ir tas, ko
jūs meklējat, jūs varat pārtraukt.

11
00:00:29,840 --> 00:00:33,930
Pretējā gadījumā, pāriet uz nākamo elementu un
glabāt iet vairāk un vairāk, līdz atrodat

12
00:00:33,930 --> 00:00:36,389
elements, vai jums nav.

13
00:00:36,389 --> 00:00:38,680
Tātad, mēs varam izmantot lineāro
meklēšanas algoritmu, piemēram,

14
00:00:38,680 --> 00:00:42,330
atrast mērķlielumu
deviņi šajā masīvā.

15
00:00:42,330 --> 00:00:43,870
Nu mēs sākam sākumā.

16
00:00:43,870 --> 00:00:45,970
Ja tas ir tas, ko mēs esam
meklē, mēs varam apturēt.

17
00:00:45,970 --> 00:00:47,890
Tas nav, mēs nemeklējam 11.

18
00:00:47,890 --> 00:00:50,220
Tātad citādi, pāriet uz nākamo elementu.

19
00:00:50,220 --> 00:00:51,510
>> Tātad mēs skatāmies 23.

20
00:00:51,510 --> 00:00:52,730
Ir 23, ko mēs meklējam?

21
00:00:52,730 --> 00:00:55,614
Nu nē, tāpēc mēs pāriet uz nākamo
elements, un nākamā elements,

22
00:00:55,614 --> 00:00:57,780
un mēs turpinām iet cauri
šis process vairāk un vairāk

23
00:00:57,780 --> 00:01:01,030
un vairāk, kamēr mēs nolaisties
par situāciju, kā šis.

24
00:01:01,030 --> 00:01:03,910
>> Deviņi ir tas, ko mēs meklējam,
un šis elements no masīva

25
00:01:03,910 --> 00:01:05,787
ir, tā vērtība ir deviņi.

26
00:01:05,787 --> 00:01:08,120
Un tā mēs atradām to, ko mēs esam
meklē, un mēs varam apturēt.

27
00:01:08,120 --> 00:01:11,910
Lineārais meklēšanai ir
pabeigts veiksmīgi.

28
00:01:11,910 --> 00:01:15,370
>> Bet ko par to, ja mēs meklējam
elements, kas nav mūsu masīvā.

29
00:01:15,370 --> 00:01:17,040
Vai lineārs meklēšana joprojām strādā?

30
00:01:17,040 --> 00:01:17,540
Nu pārliecināts.

31
00:01:17,540 --> 00:01:19,947
Tāpēc mēs atkārtot šo procesu
sākot no pirmā elementa.

32
00:01:19,947 --> 00:01:21,780
Ja tas ir tas, ko mēs esam
meklē, mēs varam apturēt.

33
00:01:21,780 --> 00:01:22,800
Tas nav.

34
00:01:22,800 --> 00:01:25,020
Pretējā gadījumā mēs virzāmies uz nākamo elementu.

35
00:01:25,020 --> 00:01:29,050
>> Bet mēs varam saglabāt šo procesu atkārtojot,
Pārbaudot katru elementu, savukārt,

36
00:01:29,050 --> 00:01:31,720
cerot, ka mēs atrodam skaitli 50.

37
00:01:31,720 --> 00:01:33,750
Bet mēs nezinām, vai
mēs esam noskaidrojuši, skaitli 50

38
00:01:33,750 --> 00:01:38,290
vai arī, ja mēs neesam, kamēr mēs esam pastiprināts
pār katru elementu masīva.

39
00:01:38,290 --> 00:01:40,440
>> Tikai tad, kad mēs esam darījuši
kas un jānāk klajā īsu,

40
00:01:40,440 --> 00:01:43,040
mēs varam secināt, ka
50 neatrodas masīvs.

41
00:01:43,040 --> 00:01:46,410
Un tā lineārais meklēšana
algoritms, arī tas neizdevās, per se.

42
00:01:46,410 --> 00:01:49,181
Bet ne tādā nozīmē, ka tā
bija neveiksmīgs darot to, ko

43
00:01:49,181 --> 00:01:49,930
mēs lūdzām to darīt.

44
00:01:49,930 --> 00:01:52,390
>> Tas bija neveiksmīgs, jo
cik tas neatrada 50,

45
00:01:52,390 --> 00:01:54,070
bet 50 nebija masīvs.

46
00:01:54,070 --> 00:01:57,310
Bet mēs esam izsmeļoši meklētas
ar katru elementu

47
00:01:57,310 --> 00:02:00,550
un tā, kamēr mēs neatradām
kaut kas, lineārā meklēt vēl

48
00:02:00,550 --> 00:02:05,230
izdodas pat ja
elements nav masīvs.

49
00:02:05,230 --> 00:02:07,507
>> Tātad, kas ir sliktākais gadījums
scenārijs ar lineāro meklēšanu?

50
00:02:07,507 --> 00:02:09,590
Nu mums ir jāskatās caur
katru elements,

51
00:02:09,590 --> 00:02:14,590
nu tāpēc, ka mērķa elements
ir pēdējais elements masīva,

52
00:02:14,590 --> 00:02:18,510
vai elements mēs meklējam nav
faktiski pastāv masīvā vispār.

53
00:02:18,510 --> 00:02:19,760
Kāds ir labākais scenārijs?

54
00:02:19,760 --> 00:02:22,430
Nu mēs varētu atrast
elements nekavējoties.

55
00:02:22,430 --> 00:02:24,360
Un cik daudz elementi
mums tad ir jāmeklē

56
00:02:24,360 --> 00:02:26,859
pie labākajā gadījumā,
ja mēs meklējam to

57
00:02:26,859 --> 00:02:28,400
un mēs redzam to jau pašā sākumā?

58
00:02:28,400 --> 00:02:29,850
Mēs varam apturēt nekavējoties.

59
00:02:29,850 --> 00:02:32,984
>> Ko tas saka par
sarežģītība lineārā meklēt?

60
00:02:32,984 --> 00:02:35,650
Nu sliktākajā gadījumā, mums ir
apskatīt katru elementu.

61
00:02:35,650 --> 00:02:38,930
Un tā tas darbojas O
n, sliktākajā gadījumā.

62
00:02:38,930 --> 00:02:41,540
>> Labākajā gadījumā mēs esam gonna
uzreiz atrast elementu.

63
00:02:41,540 --> 00:02:44,750
Un tā sākas ar omega 1.

64
00:02:44,750 --> 00:02:45,780
>> Es esmu Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
Tas ir CS50.

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