1
00:00:00,000 --> 00:00:02,892
>> [Musiikkia]

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

3
00:00:05,347 --> 00:00:07,180
DOUG Lloyd: Lineaarinen
haku on algoritmi me

4
00:00:07,180 --> 00:00:09,840
voi käyttää löytää elementti array.

5
00:00:09,840 --> 00:00:11,990
Algoritmi Recall
on askel-askeleelta sarja

6
00:00:11,990 --> 00:00:15,030
ohjeisto valmiiksi tehtävän.

7
00:00:15,030 --> 00:00:17,480
>> Lineaarinen haku
Algoritmi toimii seuraavasti.

8
00:00:17,480 --> 00:00:22,200
Kerrata rivin poikki vasemmalta
oikea, etsivät tietyn elementin.

9
00:00:22,200 --> 00:00:26,380
>> Pseudokoodilla, joka on enemmän
tislattua versio tämän lauseen,

10
00:00:26,380 --> 00:00:29,840
jos ensimmäinen elementti on mitä
etsit, voit lopettaa.

11
00:00:29,840 --> 00:00:33,930
Muuten, siirtyä seuraavaan elementtiin ja
jatkaa yhä kunnes löydät

12
00:00:33,930 --> 00:00:36,389
elementti, tai et.

13
00:00:36,389 --> 00:00:38,680
Joten voimme käyttää lineaarinen
hakualgoritmi, esimerkiksi,

14
00:00:38,680 --> 00:00:42,330
löytää tavoitearvo
yhdeksän tässä array.

15
00:00:42,330 --> 00:00:43,870
No me aloittaa alusta.

16
00:00:43,870 --> 00:00:45,970
Jos se mitä olemme
etsivät, voimme lopettaa.

17
00:00:45,970 --> 00:00:47,890
Se ei ole, emme ole etsimässä 11.

18
00:00:47,890 --> 00:00:50,220
Niin muuten, siirry seuraavaan elementtiin.

19
00:00:50,220 --> 00:00:51,510
>> Joten katsomme 23.

20
00:00:51,510 --> 00:00:52,730
On 23, mitä etsimme?

21
00:00:52,730 --> 00:00:55,614
No ei, joten siirrymme seuraavaan
elementti, ja seuraava osa,

22
00:00:55,614 --> 00:00:57,780
ja pidämme läpi
tämä prosessi uudestaan ​​ja uudestaan

23
00:00:57,780 --> 00:01:01,030
ja yli, kunnes laskeudumme
on tällainen tilanne.

24
00:01:01,030 --> 00:01:03,910
>> Yhdeksän on mitä etsimme,
ja tämä alkio

25
00:01:03,910 --> 00:01:05,787
on, se arvo on yhdeksän.

26
00:01:05,787 --> 00:01:08,120
Ja niin löysimme mitä olemme
etsivät, ja voimme lopettaa.

27
00:01:08,120 --> 00:01:11,910
Lineaarinen haku on
suoritettu onnistuneesti.

28
00:01:11,910 --> 00:01:15,370
>> Mutta entä jos me etsimme
elementti, joka ei ole meidän array.

29
00:01:15,370 --> 00:01:17,040
Onko lineaarinen haku silti toimia?

30
00:01:17,040 --> 00:01:17,540
Hyvin varma.

31
00:01:17,540 --> 00:01:19,947
Joten me toista tämä prosessi
alkaen ensimmäinen elementti.

32
00:01:19,947 --> 00:01:21,780
Jos se mitä olemme
etsivät, voimme lopettaa.

33
00:01:21,780 --> 00:01:22,800
Ei ole.

34
00:01:22,800 --> 00:01:25,020
Muuten, siirrymme seuraavaan elementtiin.

35
00:01:25,020 --> 00:01:29,050
>> Mutta voimme pitää toistaa tätä prosessia,
tutkii jokaisen elementin puolestaan

36
00:01:29,050 --> 00:01:31,720
toivoen, että löydämme numero 50.

37
00:01:31,720 --> 00:01:33,750
Mutta emme tiedä,
olemme löytäneet numero 50

38
00:01:33,750 --> 00:01:38,290
tai jos emme, ennen kuin olemme astui
yli jokainen alkio.

39
00:01:38,290 --> 00:01:40,440
>> Vasta kun olemme tehneet
että ja keksiä lyhyt,

40
00:01:40,440 --> 00:01:43,040
voimme päätellä, että
50 ei ole jono.

41
00:01:43,040 --> 00:01:46,410
Ja niin lineaarinen haku
algoritmi, hyvin se epäonnistui, sinänsä.

42
00:01:46,410 --> 00:01:49,181
Mutta ei siinä mielessä, että se
ei onnistunut tekemään mitä

43
00:01:49,181 --> 00:01:49,930
pyysimme sitä tekemään.

44
00:01:49,930 --> 00:01:52,390
>> Se ei onnistunut, koska
paljon kuin se ei löytänyt 50,

45
00:01:52,390 --> 00:01:54,070
mutta 50 ei ollut jono.

46
00:01:54,070 --> 00:01:57,310
Mutta olemme tyhjentävästi etsinyt
läpi jokaisen elementin

47
00:01:57,310 --> 00:02:00,550
ja niin, vaikka emme löytäneet
mitään, lineaarinen haku yhä

48
00:02:00,550 --> 00:02:05,230
onnistuu vaikka
elementti ei ole jono.

49
00:02:05,230 --> 00:02:07,507
>> Niin mitä pahimmassa tapauksessa
skenaario, jossa lineaarinen haku?

50
00:02:07,507 --> 00:02:09,590
No meidän täytyy käydä läpi
jokainen elementti,

51
00:02:09,590 --> 00:02:14,590
joko siksi kohdistuselementti
on viimeinen osa array,

52
00:02:14,590 --> 00:02:18,510
tai elementti etsimme ei
todella olemassa joukko lainkaan.

53
00:02:18,510 --> 00:02:19,760
Mikä on parhaassa tapauksessa?

54
00:02:19,760 --> 00:02:22,430
No voisimme löytää
elementti välittömästi.

55
00:02:22,430 --> 00:02:24,360
Ja kuinka monta elementtiä
meillä sitten on tarkasteltava

56
00:02:24,360 --> 00:02:26,859
klo parhaassa tapauksessa,
jos etsimme sitä

57
00:02:26,859 --> 00:02:28,400
ja pidämme aivan alussa?

58
00:02:28,400 --> 00:02:29,850
Voimme lopettaa välittömästi.

59
00:02:29,850 --> 00:02:32,984
>> Mitä tämä sanottavaa
monimutkaisuus lineaarinen haku?

60
00:02:32,984 --> 00:02:35,650
Hyvin pahimmassa tapauksessa olemme
katsomaan jokaisen elementin.

61
00:02:35,650 --> 00:02:38,930
Ja niin se toimii O
n, pahimmassa tapauksessa.

62
00:02:38,930 --> 00:02:41,540
>> Parhaassa tapauksessa aiomme
löytää elementti välittömästi.

63
00:02:41,540 --> 00:02:44,750
Ja niin toimii omega 1.

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

65
00:02:45,780 --> 00:02:48,020
Tämä on CS50.

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