1
00:00:00,000 --> 00:00:02,892
>> [REPRODUCCIÓ DE MÚSICA]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Lineal
recerca és un algoritme que

4
00:00:07,180 --> 00:00:09,840
pot utilitzar per trobar un element en una matriu.

5
00:00:09,840 --> 00:00:11,990
Un record algoritme
és un conjunt pas a pas

6
00:00:11,990 --> 00:00:15,030
d'instruccions per completar una tasca.

7
00:00:15,030 --> 00:00:17,480
>> Hi lineal
algoritme funciona de la següent manera.

8
00:00:17,480 --> 00:00:22,200
Iterar a través de la matriu d'esquerra a
dreta, a la recerca d'un element especificat.

9
00:00:22,200 --> 00:00:26,380
>> En pseudocodi, que és un més
versió destil·lada d'aquesta frase,

10
00:00:26,380 --> 00:00:29,840
si el primer element és el
que vostè està buscant, pot aturar.

11
00:00:29,840 --> 00:00:33,930
Altrament, passar al següent element i
seguir endavant i una altra fins que trobi

12
00:00:33,930 --> 00:00:36,389
l'element, o no ho fas.

13
00:00:36,389 --> 00:00:38,680
Així que podem fer servir el lineal
algoritme de recerca, per exemple,

14
00:00:38,680 --> 00:00:42,330
per trobar el valor objectiu
09:00 en aquesta matriu.

15
00:00:42,330 --> 00:00:43,870
Bé comencem pel principi.

16
00:00:43,870 --> 00:00:45,970
Si és el que estem
buscant, podem aturar.

17
00:00:45,970 --> 00:00:47,890
No és, no estem buscant 11.

18
00:00:47,890 --> 00:00:50,220
Així que en cas contrari, passar al següent element.

19
00:00:50,220 --> 00:00:51,510
>> Així que ens fixem en el 23.

20
00:00:51,510 --> 00:00:52,730
És de 23 que estem buscant?

21
00:00:52,730 --> 00:00:55,614
Doncs no, així que vam passar a la següent
element, i el següent element,

22
00:00:55,614 --> 00:00:57,780
i seguim passant per
aquest procés una i altra

23
00:00:57,780 --> 00:01:01,030
i una altra, fins que aterrem
en una situació com aquesta.

24
00:01:01,030 --> 00:01:03,910
>> Nou és el que estem buscant,
i aquest element de la matriu

25
00:01:03,910 --> 00:01:05,787
és a dir, el seu valor és de nou.

26
00:01:05,787 --> 00:01:08,120
I així ens trobem el que estem
buscant, i podem aturar.

27
00:01:08,120 --> 00:01:11,910
Hi lineal té
completat, amb èxit.

28
00:01:11,910 --> 00:01:15,370
>> Però què passa si estem buscant
un element que no està en la nostra matriu.

29
00:01:15,370 --> 00:01:17,040
Té encara treballen cerca lineal?

30
00:01:17,040 --> 00:01:17,540
Bé segur.

31
00:01:17,540 --> 00:01:19,947
Així que repetim aquest procés
començant en el primer element.

32
00:01:19,947 --> 00:01:21,780
Si és el que estem
buscant, podem aturar.

33
00:01:21,780 --> 00:01:22,800
No és.

34
00:01:22,800 --> 00:01:25,020
Altrament, ens movem al següent element.

35
00:01:25,020 --> 00:01:29,050
>> Però podem seguir repetint aquest procés,
examinar cada element, al seu torn,

36
00:01:29,050 --> 00:01:31,720
l'esperança que ens trobem amb el número 50.

37
00:01:31,720 --> 00:01:33,750
Però no sabrem si
hem trobat el número 50

38
00:01:33,750 --> 00:01:38,290
o si no ho féssim, fins que hàgim entrem
sobre cada element de la matriu.

39
00:01:38,290 --> 00:01:40,440
>> Només una vegada que hem fet
això i es queden curts,

40
00:01:40,440 --> 00:01:43,040
podem concloure que
50 no està a la matriu.

41
00:01:43,040 --> 00:01:46,410
I pel que la recerca lineal
algoritme, així que no, per se.

42
00:01:46,410 --> 00:01:49,181
Però no en el sentit que
no va tenir èxit en fer el que

43
00:01:49,181 --> 00:01:49,930
demanem que faci.

44
00:01:49,930 --> 00:01:52,390
>> Es va tenir èxit en el
molt més, ja que no es va trobar 50,

45
00:01:52,390 --> 00:01:54,070
però 50 no estava en l'array.

46
00:01:54,070 --> 00:01:57,310
Però hem buscat exhaustivament
a través de cada element

47
00:01:57,310 --> 00:02:00,550
i així, mentre que no trobem
res, cerca lineal encara

48
00:02:00,550 --> 00:02:05,230
té èxit encara que la
element no està en la matriu.

49
00:02:05,230 --> 00:02:07,507
>> Quin és el pitjor dels casos
escenari amb recerca lineal?

50
00:02:07,507 --> 00:02:09,590
Bé, hem de mirar a través de
cada element,

51
00:02:09,590 --> 00:02:14,590
ja sigui perquè l'element de destinació
és l'últim element de la matriu,

52
00:02:14,590 --> 00:02:18,510
o l'element que estem buscant no
en realitat existeix en la matriu en absolut.

53
00:02:18,510 --> 00:02:19,760
Quin és el millor dels casos?

54
00:02:19,760 --> 00:02:22,430
Bé podríem trobar la
element immediatament.

55
00:02:22,430 --> 00:02:24,360
I quants elements
Com podem llavors hem de mirar

56
00:02:24,360 --> 00:02:26,859
en en el millor cas,
si estem a la recerca d'ella

57
00:02:26,859 --> 00:02:28,400
i ens trobem en el començament?

58
00:02:28,400 --> 00:02:29,850
Podem parar immediatament.

59
00:02:29,850 --> 00:02:32,984
>> Què diu això sobre la
complexitat de cerca lineal?

60
00:02:32,984 --> 00:02:35,650
Bé, en el pitjor dels casos, tenim
per mirar a cada element.

61
00:02:35,650 --> 00:02:38,930
I el que s'executa en O de
n, en el pitjor dels casos.

62
00:02:38,930 --> 00:02:41,540
>> En el millor dels casos, anem a
trobar l'element immediatament.

63
00:02:41,540 --> 00:02:44,750
I així funciona en omega d'1.

64
00:02:44,750 --> 00:02:45,780
>> Sóc Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
Això és CS50.

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