1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Então, nós aprendemos sobre CS50
uma variedade de classificação e pesquisa

3
00:00:08,900 --> 00:00:09,442
algoritmos.

4
00:00:09,442 --> 00:00:11,400
E às vezes isso pode ser
um pouco complicado para manter

5
00:00:11,400 --> 00:00:14,161
a par do que algoritmo faz o quê.

6
00:00:14,161 --> 00:00:15,910
Nós temos realmente apenas
desnatado a superfície também,

7
00:00:15,910 --> 00:00:18,740
existem muitos outros pesquisa
e algoritmos de ordenação.

8
00:00:18,740 --> 00:00:21,780
Portanto, neste vídeo, vamos
apenas levar alguns minutos

9
00:00:21,780 --> 00:00:24,980
para tentar e destilar cada algoritmo
para baixo a seus elementos centrais

10
00:00:24,980 --> 00:00:27,810
para que você possa lembrar o mais
informações importantes sobre eles

11
00:00:27,810 --> 00:00:31,970
e ser capaz de articular a
diferenças, se necessário.

12
00:00:31,970 --> 00:00:34,220
>> O primeiro é a seleção de classificação.

13
00:00:34,220 --> 00:00:38,210
A idéia básica por trás de seleção tipo
é encontrar o menor elemento não triados

14
00:00:38,210 --> 00:00:42,890
em uma matriz e trocá-lo com o
primeiro elemento não ordenado desse array.

15
00:00:42,890 --> 00:00:46,620
Nós dissemos que o pior caso
tempo de execução do que foi n ao quadrado.

16
00:00:46,620 --> 00:00:50,060
E se você quiser recordar por que razão, tomar
um olhar para o vídeo selecção de classificação.

17
00:00:50,060 --> 00:00:54,560
O tempo de execução do melhor caso
é também n ao quadrado.

18
00:00:54,560 --> 00:00:58,910
>> Bubble sort, a idéia por trás disso
um é trocar os pares adjacentes.

19
00:00:58,910 --> 00:01:01,730
Então, essa é a chave que ajuda você
lembre-se a diferença aqui.

20
00:01:01,730 --> 00:01:04,920
Seleção tipo é, até agora,
encontrar o bubble smallest--

21
00:01:04,920 --> 00:01:06,790
Sort é trocar os pares adjacentes.

22
00:01:06,790 --> 00:01:08,710
Nós trocar pares adjacentes
de elementos se

23
00:01:08,710 --> 00:01:12,530
estão fora de ordem, o que efetivamente
Bolhas de elementos maiores para a direita,

24
00:01:12,530 --> 00:01:17,060
e, ao mesmo tempo que também começa
para mover elementos menores para a esquerda.

25
00:01:17,060 --> 00:01:20,180
O pior caso de tempo caso de execução
de bubble sort é n ao quadrado.

26
00:01:20,180 --> 00:01:23,476
O tempo de execução do melhor caso
de bubble sort é n.

27
00:01:23,476 --> 00:01:25,350
Porque nessa situação
nós não actually--

28
00:01:25,350 --> 00:01:27,141
que talvez não seja necessário
fazer quaisquer swaps em tudo.

29
00:01:27,141 --> 00:01:31,026
Nós só tem de fazer uma
passar por todos os elementos n.

30
00:01:31,026 --> 00:01:34,600
>> Na ordenação por inserção, o
idéia básica aqui está mudando.

31
00:01:34,600 --> 00:01:36,630
Essa é a palavra-chave para a inserção de classificação.

32
00:01:36,630 --> 00:01:39,630
Nós vamos para a etapa através de uma vez
a matriz da esquerda para a direita.

33
00:01:39,630 --> 00:01:41,670
E como nós fazemos, nós somos
vai mudar elementos

34
00:01:41,670 --> 00:01:46,260
já vimos para dar lugar a
os menores que necessitam de um lugar para caber

35
00:01:46,260 --> 00:01:48,080
de volta em que parcela classificada.

36
00:01:48,080 --> 00:01:51,600
Então, nós construímos a matriz classificada uma
elemento de cada vez, para a esquerda para a direita,

37
00:01:51,600 --> 00:01:54,740
e mudamos coisas para fazer o quarto.

38
00:01:54,740 --> 00:01:58,650
O tempo de execução do pior caso de
ordenação por inserção é n ao quadrado.

39
00:01:58,650 --> 00:02:02,380
O melhor caso o tempo de execução é n.

40
00:02:02,380 --> 00:02:05,380
>> Mesclar sort-- a palavra-chave
aqui é dividir e mesclar.

41
00:02:05,380 --> 00:02:08,949
Podemos dividir o conjunto completo, se
é seis elementos, oito elementos,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- nós dividi-lo
para baixo pela metade, pela metade, pela metade,

43
00:02:13,790 --> 00:02:17,720
até que tenhamos sob matriz
n de um elemento de matrizes.

44
00:02:17,720 --> 00:02:19,470
Um conjunto de matrizes n um elemento.

45
00:02:19,470 --> 00:02:22,640
Então começamos com uma
1000-elemento da matriz,

46
00:02:22,640 --> 00:02:26,550
e chegarmos ao ponto em que
1.000 matrizes tem um único elemento.

47
00:02:26,550 --> 00:02:30,990
Então começamos a mesclar essas sub matrizes
juntos novamente na ordem correta.

48
00:02:30,990 --> 00:02:34,860
Então, tomamos duas matrizes de um elemento
e criar uma matriz de dois elementos.

49
00:02:34,860 --> 00:02:38,180
Tomamos duas matrizes de dois elementos
e criar uma matriz de quatro elementos

50
00:02:38,180 --> 00:02:43,900
e assim por diante e assim por diante até que tenhamos
novamente reconstruída uma matriz elemento n.

51
00:02:43,900 --> 00:02:48,410
>> O tempo de execução do pior caso de
merge sort é n vezes log n.

52
00:02:48,410 --> 00:02:52,390
Temos n elementos, mas
este processo de recombinação

53
00:02:52,390 --> 00:02:56,960
pega no registo n passos para obter
de volta para um conjunto completo.

54
00:02:56,960 --> 00:03:01,160
O melhor caso o tempo de execução também é log n
N porque este processo não realmente

55
00:03:01,160 --> 00:03:04,090
importam se a matriz foi
classificadas ou não para começar.

56
00:03:04,090 --> 00:03:07,590
O processo é o mesmo, não há
nenhuma maneira de curtos circuitos coisas.

57
00:03:07,590 --> 00:03:11,610
Então n log n, no pior caso,
n log n na melhor das hipóteses.

58
00:03:11,610 --> 00:03:13,960
>> Falamos sobre dois
busca algoritmos.

59
00:03:13,960 --> 00:03:16,230
Assim, busca linear é sobre iteração.

60
00:03:16,230 --> 00:03:19,500
Prosseguimos em toda a gama
uma vez que, a partir da esquerda para a direita,

61
00:03:19,500 --> 00:03:21,950
tentando encontrar o número
que estamos procurando.

62
00:03:21,950 --> 00:03:24,550
O tempo de pior caso executar é grande O de n.

63
00:03:24,550 --> 00:03:27,610
Ele pode nos levar a iteração
através de cada elemento

64
00:03:27,610 --> 00:03:30,660
para encontrar o elemento que estamos procurando
para, quer na última posição,

65
00:03:30,660 --> 00:03:31,630
ou não em todos.

66
00:03:31,630 --> 00:03:34,720
Mas não podemos confirmar que até
nós olhamos tudo.

67
00:03:34,720 --> 00:03:36,730
sou o melhor caso, encontramos imediatamente.

68
00:03:36,730 --> 00:03:41,060
O tempo de execução do melhor caso de
busca linear é omega de 1.

69
00:03:41,060 --> 00:03:43,689
>> Por último, não havia pesquisa binária,
que requer gama variada.

70
00:03:43,689 --> 00:03:45,605
Lembre-se que é muito
consideração importante

71
00:03:45,605 --> 00:03:47,155
quando se trabalha com pesquisa binária.

72
00:03:47,155 --> 00:03:50,180
É um pré-requisito para utilizar ele--
a matriz que você está procurando através

73
00:03:50,180 --> 00:03:52,160
deve ser classificado.

74
00:03:52,160 --> 00:03:54,500
Caso contrário, a palavra-chave
é dividir e conquistar.

75
00:03:54,500 --> 00:03:58,310
Dividir a matriz em metade e
eliminar metade dos elementos

76
00:03:58,310 --> 00:04:00,780
cada vez que à medida que avançar através.

77
00:04:00,780 --> 00:04:04,330
Devido a isso dividir e conquistar
e as coisas dividindo pela metade abordagem,

78
00:04:04,330 --> 00:04:07,450
o tempo de execução do pior caso
de busca binária é

79
00:04:07,450 --> 00:04:11,730
log n, que é substancialmente
melhor do que de busca linear n.

80
00:04:11,730 --> 00:04:13,570
O melhor caso o tempo de execução ainda é um.

81
00:04:13,570 --> 00:04:17,010
>> Podemos encontrá-lo imediatamente a
primeira vez que fazemos uma divisão, mas,

82
00:04:17,010 --> 00:04:19,339
novamente, lembre-se que
embora busca binária é

83
00:04:19,339 --> 00:04:24,030
substancialmente melhor do que a pesquisa linear
em virtude de ser log n contra n,

84
00:04:24,030 --> 00:04:27,110
você pode ter que ir através do trabalho
de classificar a matriz primeiro, que

85
00:04:27,110 --> 00:04:32,010
pode torná-lo menos eficaz, dependendo
sobre o tamanho da iteração classificados.

86
00:04:32,010 --> 00:04:35,250
>> Eu sou Doug Lloyd, este é CS50.

87
00:04:35,250 --> 00:04:36,757