1
00:00:00,000 --> 00:00:02,892
>> [MUSIC JOC]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Linear
căutare este o noi algoritm

4
00:00:07,180 --> 00:00:09,840
se poate utiliza pentru a găsi un element într-o matrice.

5
00:00:09,840 --> 00:00:11,990
Un algoritm rechemare
este un set de pas-cu-pas

6
00:00:11,990 --> 00:00:15,030
de instrucțiuni pentru finalizarea unei sarcini.

7
00:00:15,030 --> 00:00:17,480
>> Căutare liniară
Algoritmul funcționează după cum urmează.

8
00:00:17,480 --> 00:00:22,200
Repeta peste matrice de la stânga la
dreapta, în căutarea unui element specificat.

9
00:00:22,200 --> 00:00:26,380
>> În pseudocod, care este o mai
versiunea distilată a acestei propoziții,

10
00:00:26,380 --> 00:00:29,840
În cazul în care primul element este ceea ce
sunteți în căutarea pentru, vă puteți opri.

11
00:00:29,840 --> 00:00:33,930
În caz contrar, trece la elementul următor și
mergi peste si peste până când veți găsi

12
00:00:33,930 --> 00:00:36,389
elementul, sau nu.

13
00:00:36,389 --> 00:00:38,680
Deci, putem folosi liniar
algoritm de căutare, de exemplu,

14
00:00:38,680 --> 00:00:42,330
pentru a găsi valoarea țintă
nouă în această matrice.

15
00:00:42,330 --> 00:00:43,870
Ei bine, vom începe de la început.

16
00:00:43,870 --> 00:00:45,970
Dacă e ceea ce suntem
cauta, ne putem opri.

17
00:00:45,970 --> 00:00:47,890
Nu e, nu suntem în căutarea pentru 11.

18
00:00:47,890 --> 00:00:50,220
Deci în caz contrar, trece la elementul următor.

19
00:00:50,220 --> 00:00:51,510
>> Deci, ne uităm la 23.

20
00:00:51,510 --> 00:00:52,730
Este de 23 ceea ce căutăm?

21
00:00:52,730 --> 00:00:55,614
Ei bine, nu, asa ca am trece la următoarea
element și elementul următor,

22
00:00:55,614 --> 00:00:57,780
și păstrăm trece prin
acest proces de peste si peste

23
00:00:57,780 --> 00:01:01,030
și peste, până când vom ateriza
pe o situatie ca asta.

24
00:01:01,030 --> 00:01:03,910
>> Nouă este ceea ce căutați,
și acest element de matrice

25
00:01:03,910 --> 00:01:05,787
este, o valoare este de aceasta nouă.

26
00:01:05,787 --> 00:01:08,120
Și așa am găsit ceea ce suntem
cauta, si ne putem opri.

27
00:01:08,120 --> 00:01:11,910
Căutare liniară are
finalizat, cu succes.

28
00:01:11,910 --> 00:01:15,370
>> Dar ceea ce despre dacă căutăm
un element care nu este în oferta noastră.

29
00:01:15,370 --> 00:01:17,040
Are căutare liniară încă mai funcționează?

30
00:01:17,040 --> 00:01:17,540
Bine sigur.

31
00:01:17,540 --> 00:01:19,947
Așa că am repeta acest proces
începând de la primul element.

32
00:01:19,947 --> 00:01:21,780
Dacă e ceea ce suntem
cauta, ne putem opri.

33
00:01:21,780 --> 00:01:22,800
Nu e.

34
00:01:22,800 --> 00:01:25,020
În caz contrar, vom trece la elementul următor.

35
00:01:25,020 --> 00:01:29,050
>> Dar putem repeta acest proces,
examinarea fiecărui element, la rândul său,

36
00:01:29,050 --> 00:01:31,720
în speranța că vom găsi numărul 50.

37
00:01:31,720 --> 00:01:33,750
Dar nu vom ști dacă
am găsit numărul 50

38
00:01:33,750 --> 00:01:38,290
sau dacă nu am făcut-o, până când am pășit noi
peste fiecare element unic de matrice.

39
00:01:38,290 --> 00:01:40,440
>> Doar o singură dată am făcut
că și să vină scurt,

40
00:01:40,440 --> 00:01:43,040
putem concluziona că
50 nu este în matrice.

41
00:01:43,040 --> 00:01:46,410
Și astfel de căutare liniară
algoritm, bine nu a reușit, în sine.

42
00:01:46,410 --> 00:01:49,181
Dar nu în sensul că
nu a avut succes în a face ceea ce

43
00:01:49,181 --> 00:01:49,930
am cerut să facă.

44
00:01:49,930 --> 00:01:52,390
>> Acesta a avut succes în ca
de mult ca nu a găsit 50,

45
00:01:52,390 --> 00:01:54,070
dar 50 nu a fost în matrice.

46
00:01:54,070 --> 00:01:57,310
Dar am căutat în mod exhaustiv
prin fiecare singur element

47
00:01:57,310 --> 00:02:00,550
și așa, în timp ce nu am găsit
nimic, căutare liniară încă

48
00:02:00,550 --> 00:02:05,230
reușește, chiar dacă
Element nu este în matrice.

49
00:02:05,230 --> 00:02:07,507
>> Deci, ce este cel mai rău caz
scenariu cu căutare liniară?

50
00:02:07,507 --> 00:02:09,590
Ei bine, trebuie sa ne uitam prin
fiecare singur element,

51
00:02:09,590 --> 00:02:14,590
fie din cauză că elementul țintă
este ultimul element de matrice,

52
00:02:14,590 --> 00:02:18,510
sau elementul căutăm nu
există de fapt în matrice, la toate.

53
00:02:18,510 --> 00:02:19,760
Care este cel mai bun caz?

54
00:02:19,760 --> 00:02:22,430
Ei bine, am putea găsi
elementul imediat.

55
00:02:22,430 --> 00:02:24,360
Și cât de multe elemente
avem apoi să se uite

56
00:02:24,360 --> 00:02:26,859
la în cel mai bun caz,
dacă suntem în căutarea pentru el

57
00:02:26,859 --> 00:02:28,400
și îl găsim la bun început?

58
00:02:28,400 --> 00:02:29,850
Ne putem opri imediat.

59
00:02:29,850 --> 00:02:32,984
>> Ce înseamnă acest spune despre
complexitatea căutare liniară?

60
00:02:32,984 --> 00:02:35,650
Ei bine, în cel mai rău caz, ne-am
să se uite la fiecare singur element.

61
00:02:35,650 --> 00:02:38,930
Și așa se execută în O de
n, în cel mai rău caz.

62
00:02:38,930 --> 00:02:41,540
>> În cel mai bun caz, vom
găsi imediat elementul.

63
00:02:41,540 --> 00:02:44,750
Și astfel se execută în omega de 1.

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

65
00:02:45,780 --> 00:02:48,020
Acest lucru este CS50.

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