1
00:00:00,000 --> 00:00:02,892
>> [Música tocando]

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

3
00:00:05,347 --> 00:00:07,180
Doug LLOYD: Lineal
investigación é un algoritmo que

4
00:00:07,180 --> 00:00:09,840
pode usar para atopar un elemento nunha matriz.

5
00:00:09,840 --> 00:00:11,990
Un recordo algoritmo
é un conxunto paso a paso

6
00:00:11,990 --> 00:00:15,030
de instrucións para completar unha tarefa.

7
00:00:15,030 --> 00:00:17,480
>> A investigación lineal
algoritmo funciona do seguinte xeito.

8
00:00:17,480 --> 00:00:22,200
Iterado través da matriz de esquerda a
dereita, á procura dun elemento especificado.

9
00:00:22,200 --> 00:00:26,380
>> En pseudocódigo, que é unha forma máis
versión destilada desta frase,

10
00:00:26,380 --> 00:00:29,840
O primeiro elemento que é
está a buscar, pode parar.

11
00:00:29,840 --> 00:00:33,930
Se non, pasar ao seguinte elemento e
manter indo máis e máis ata que atope

12
00:00:33,930 --> 00:00:36,389
o elemento, ou non fai.

13
00:00:36,389 --> 00:00:38,680
Así, podemos usar o lineal
algoritmo de procura, por exemplo,

14
00:00:38,680 --> 00:00:42,330
para atopar o valor obxectivo
nove nesa matriz.

15
00:00:42,330 --> 00:00:43,870
Ben imos comezar polo comezo.

16
00:00:43,870 --> 00:00:45,970
Se é o que somos
buscar, podemos parar.

17
00:00:45,970 --> 00:00:47,890
Non é, non estamos a buscar 11.

18
00:00:47,890 --> 00:00:50,220
Así, se non, pasar ao seguinte elemento.

19
00:00:50,220 --> 00:00:51,510
>> Entón miramos para 23.

20
00:00:51,510 --> 00:00:52,730
23 é o que estamos a buscar?

21
00:00:52,730 --> 00:00:55,614
Ben, non, por iso, pasar á seguinte
elemento eo elemento seguinte,

22
00:00:55,614 --> 00:00:57,780
e seguimos a atravesar
este proceso máis e máis

23
00:00:57,780 --> 00:01:01,030
e máis, ata que pousar
nunha situación como esta.

24
00:01:01,030 --> 00:01:03,910
>> Nove é o que estamos a buscar,
e este elemento da matriz

25
00:01:03,910 --> 00:01:05,787
é, de valor é nove.

26
00:01:05,787 --> 00:01:08,120
E así atopamos o que somos
buscar, e podemos parar.

27
00:01:08,120 --> 00:01:11,910
A investigación lineal ten
Feito con éxito.

28
00:01:11,910 --> 00:01:15,370
>> Pero o que dicir se estamos a buscar
un elemento que non está na nosa matriz.

29
00:01:15,370 --> 00:01:17,040
Será que busca lineal aínda funciona?

30
00:01:17,040 --> 00:01:17,540
Ben seguro.

31
00:01:17,540 --> 00:01:19,947
Entón, nós repetimos este proceso
comezando o primeiro elemento.

32
00:01:19,947 --> 00:01:21,780
Se é o que somos
buscar, podemos parar.

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

34
00:01:22,800 --> 00:01:25,020
Se non, nós nos movemos no seguinte elemento.

35
00:01:25,020 --> 00:01:29,050
>> Pero podemos seguir a repetir ese proceso,
examina cada elemento, á súa vez,

36
00:01:29,050 --> 00:01:31,720
coa esperanza de que atopamos o número 50.

37
00:01:31,720 --> 00:01:33,750
Pero nós non saberemos se
atopamos o número 50

38
00:01:33,750 --> 00:01:38,290
ou se non o fixo, ata que xa pisou
sobre cada elemento da matriz.

39
00:01:38,290 --> 00:01:40,440
>> Só unha vez que fixemos
iso e vir enriba do short,

40
00:01:40,440 --> 00:01:43,040
podemos concluír que
50, non figura na matriz.

41
00:01:43,040 --> 00:01:46,410
E así a procura lineal
algoritmo, así el fallou, per se.

42
00:01:46,410 --> 00:01:49,181
Pero non no sentido de que
non tivo éxito en facer o que

43
00:01:49,181 --> 00:01:49,930
pedimos que faga.

44
00:01:49,930 --> 00:01:52,390
>> Tivo éxito en como
tanto como el non atopou 50,

45
00:01:52,390 --> 00:01:54,070
pero 50 non estaba na matriz.

46
00:01:54,070 --> 00:01:57,310
Pero temos extensa investigados
a través de cada elemento

47
00:01:57,310 --> 00:02:00,550
e así, mentres non atopamos
algo, procura lineal aínda

48
00:02:00,550 --> 00:02:05,230
sucede aínda que a
elemento non está na matriz.

49
00:02:05,230 --> 00:02:07,507
>> Entón, cal é o peor caso
escenario con procura lineal?

50
00:02:07,507 --> 00:02:09,590
Ben, temos que mirar a través
cada elemento,

51
00:02:09,590 --> 00:02:14,590
ben porque o elemento obxecto
é o último elemento da matriz,

52
00:02:14,590 --> 00:02:18,510
ou o elemento que estamos a buscar non
realmente existen na matriz en todo.

53
00:02:18,510 --> 00:02:19,760
Cal é o mellor escenario?

54
00:02:19,760 --> 00:02:22,430
Ben que poderíamos atopar o
elemento inmediatamente.

55
00:02:22,430 --> 00:02:24,360
E cantos elementos
nós entón temos que mirar

56
00:02:24,360 --> 00:02:26,859
na no mellor dos casos,
se nós estamos mirando para el

57
00:02:26,859 --> 00:02:28,400
e nós atopalo ao comezo?

58
00:02:28,400 --> 00:02:29,850
Podemos deixar inmediatamente.

59
00:02:29,850 --> 00:02:32,984
>> O que isto di sobre a
complexidade da busca lineal?

60
00:02:32,984 --> 00:02:35,650
Ben, no peor caso, temos
ollar para cada elemento.

61
00:02:35,650 --> 00:02:38,930
E así é executado no de
N, no peor dos casos.

62
00:02:38,930 --> 00:02:41,540
>> No mellor dos casos, nós imos
atopar o elemento inmediatamente.

63
00:02:41,540 --> 00:02:44,750
E así é executado en omega de 1.

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

65
00:02:45,780 --> 00:02:48,020
Este é CS50.

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