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: Linear
pesquisa é um algoritmo que

4
00:00:07,180 --> 00:00:09,840
pode usar para encontrar um elemento em uma matriz.

5
00:00:09,840 --> 00:00:11,990
Uma recordação algoritmo
é um conjunto passo-a-passo

6
00:00:11,990 --> 00:00:15,030
de instruções para completar uma tarefa.

7
00:00:15,030 --> 00:00:17,480
>> A pesquisa linear
algoritmo funciona da seguinte maneira.

8
00:00:17,480 --> 00:00:22,200
Iterar através da matriz da esquerda para a
direita, à procura de um elemento especificado.

9
00:00:22,200 --> 00:00:26,380
>> Em pseudocódigo, que é uma forma mais
versão destilada desta frase,

10
00:00:26,380 --> 00:00:29,840
Se o primeiro elemento de que é
você está procurando, você pode parar.

11
00:00:29,840 --> 00:00:33,930
Caso contrário, passar para o próximo elemento e
manter indo mais e mais até que você encontre

12
00:00:33,930 --> 00:00:36,389
o elemento, ou você não faz.

13
00:00:36,389 --> 00:00:38,680
Assim, podemos usar o linear
algoritmo de busca, por exemplo,

14
00:00:38,680 --> 00:00:42,330
para encontrar o valor alvo
nove nessa matriz.

15
00:00:42,330 --> 00:00:43,870
Bem vamos começar pelo começo.

16
00:00:43,870 --> 00:00:45,970
Se é o que nós somos
procurando, nós podemos parar.

17
00:00:45,970 --> 00:00:47,890
Não é, não estamos procurando 11.

18
00:00:47,890 --> 00:00:50,220
Assim, caso contrário, passar para o próximo elemento.

19
00:00:50,220 --> 00:00:51,510
>> Então olhamos para 23.

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

21
00:00:52,730 --> 00:00:55,614
Bem, não, por isso, passar para a próxima
elemento eo elemento seguinte,

22
00:00:55,614 --> 00:00:57,780
e continuamos a atravessar
este processo mais e mais

23
00:00:57,780 --> 00:01:01,030
e mais, até que pousar
em uma situação como esta.

24
00:01:01,030 --> 00:01:03,910
>> Nove é o que estamos procurando,
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 assim nós encontramos o que nós somos
procurando, e nós podemos parar.

27
00:01:08,120 --> 00:01:11,910
A pesquisa linear tem
concluído, com sucesso.

28
00:01:11,910 --> 00:01:15,370
>> Mas o que dizer se estamos procurando
um elemento que não está em nossa matriz.

29
00:01:15,370 --> 00:01:17,040
Será que busca linear ainda funciona?

30
00:01:17,040 --> 00:01:17,540
Bem certeza.

31
00:01:17,540 --> 00:01:19,947
Então, nós repetimos este processo
começando no primeiro elemento.

32
00:01:19,947 --> 00:01:21,780
Se é o que nós somos
procurando, nós podemos parar.

33
00:01:21,780 --> 00:01:22,800
Não é.

34
00:01:22,800 --> 00:01:25,020
Caso contrário, nós nos movemos para o próximo elemento.

35
00:01:25,020 --> 00:01:29,050
>> Mas podemos continuar a repetir esse processo,
examina cada elemento, por sua vez,

36
00:01:29,050 --> 00:01:31,720
na esperança de que nós encontramos o número 50.

37
00:01:31,720 --> 00:01:33,750
Mas nós não saberemos se
nós encontramos o número 50

38
00:01:33,750 --> 00:01:38,290
ou se nós não o fez, até que nós já pisou
sobre cada elemento da matriz.

39
00:01:38,290 --> 00:01:40,440
>> Apenas uma vez que fizemos
isso e vir acima do short,

40
00:01:40,440 --> 00:01:43,040
podemos concluir que
50 não se encontra na matriz.

41
00:01:43,040 --> 00:01:46,410
E assim a busca linear
algoritmo, bem ele falhou, per se.

42
00:01:46,410 --> 00:01:49,181
Mas não no sentido de que ele
não teve sucesso em fazer o que

43
00:01:49,181 --> 00:01:49,930
pedimos que ele faça.

44
00:01:49,930 --> 00:01:52,390
>> Ele teve sucesso em como
tanto como ele não encontrou 50,

45
00:01:52,390 --> 00:01:54,070
mas 50 não estava na matriz.

46
00:01:54,070 --> 00:01:57,310
Mas temos exaustivamente pesquisados
através de cada elemento

47
00:01:57,310 --> 00:02:00,550
e assim, enquanto não encontramos
qualquer coisa, pesquisa linear ainda

48
00:02:00,550 --> 00:02:05,230
sucede mesmo que a
elemento não está na matriz.

49
00:02:05,230 --> 00:02:07,507
>> Então, qual é o pior caso
cenário com busca linear?

50
00:02:07,507 --> 00:02:09,590
Bem, temos de olhar através de
cada elemento,

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

52
00:02:14,590 --> 00:02:18,510
ou o elemento que estamos procurando não
realmente existem na matriz em tudo.

53
00:02:18,510 --> 00:02:19,760
Qual é o melhor cenário?

54
00:02:19,760 --> 00:02:22,430
Bem que poderíamos encontrar o
elemento imediatamente.

55
00:02:22,430 --> 00:02:24,360
E quantos elementos
nós então temos que olhar

56
00:02:24,360 --> 00:02:26,859
na na melhor das hipóteses,
se nós estamos olhando para ele

57
00:02:26,859 --> 00:02:28,400
e nós encontrá-lo logo no início?

58
00:02:28,400 --> 00:02:29,850
Nós podemos parar imediatamente.

59
00:02:29,850 --> 00:02:32,984
>> O que isso diz sobre a
complexidade da busca linear?

60
00:02:32,984 --> 00:02:35,650
Bem, no pior caso, temos
olhar para cada elemento.

61
00:02:35,650 --> 00:02:38,930
E assim ele é executado em O de
N, no pior dos casos.

62
00:02:38,930 --> 00:02:41,540
>> Na melhor das hipóteses, nós vamos
encontrar o elemento imediatamente.

63
00:02:41,540 --> 00:02:44,750
E assim é executado em omega de 1.

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

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

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