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

2
00:00:05,760 --> 00:00:08,900
>> Doug LLOYD: Entón, nós aprenden sobre CS50
unha variedade de clasificación e investigación

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

4
00:00:09,442 --> 00:00:11,400
E ás veces isto pode ser
un pouco complicado para manter

5
00:00:11,400 --> 00:00:14,161
ao tanto do que algoritmo fai o que.

6
00:00:14,161 --> 00:00:15,910
Temos realmente só
desnatado a superficie tamén,

7
00:00:15,910 --> 00:00:18,740
hai moitos outros investigación
e algoritmos de ordenación.

8
00:00:18,740 --> 00:00:21,780
Polo tanto, neste vídeo, imos
só levar uns minutos

9
00:00:21,780 --> 00:00:24,980
para tratar e destilar cada algoritmo
abaixo aos seus elementos centrais

10
00:00:24,980 --> 00:00:27,810
para que poida lembrar o máis
información importante sobre eles

11
00:00:27,810 --> 00:00:31,970
e ser capaz de articular a
diferenzas, se fose necesario.

12
00:00:31,970 --> 00:00:34,220
>> A primeira é a selección de clasificación.

13
00:00:34,220 --> 00:00:38,210
A idea básica por tras de selección tipo
é atopar o menor elemento sen clasificar

14
00:00:38,210 --> 00:00:42,890
nunha matriz e troca-lo co
primeiro elemento non ordenado dese array.

15
00:00:42,890 --> 00:00:46,620
Nós dixemos que o peor caso
tempo de execución que se n ao cadrado.

16
00:00:46,620 --> 00:00:50,060
E se queres lembrar por que razón, tomar
un ollar para o vídeo selección de clasificación.

17
00:00:50,060 --> 00:00:54,560
O tempo de execución do mellor caso
é tamén n ao cadrado.

18
00:00:54,560 --> 00:00:58,910
>> Bubble sort, a idea detrás diso
un é cambiar os pares adxacentes.

19
00:00:58,910 --> 00:01:01,730
Entón, esa é a clave que axuda
Teña en conta que a diferenza aquí.

20
00:01:01,730 --> 00:01:04,920
Selección tipo é, ata agora,
atopar o bubble smallest--

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

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

23
00:01:08,710 --> 00:01:12,530
están fóra de orde, o que efectivamente
Burbullas de elementos máis grandes para a dereita,

24
00:01:12,530 --> 00:01:17,060
e, á vez que tamén comeza
para mover elementos menores á esquerda.

25
00:01:17,060 --> 00:01:20,180
O peor caso de tempo caso de execución
de bubble sort é n ao cadrado.

26
00:01:20,180 --> 00:01:23,476
O tempo de execución do mellor caso
de bubble sort é n.

27
00:01:23,476 --> 00:01:25,350
Porque nesa situación
non actually--

28
00:01:25,350 --> 00:01:27,141
que quizais non sexa necesario
facer os swaps en todo.

29
00:01:27,141 --> 00:01:31,026
Nós só ten que facer unha
pasar por todos os elementos n.

30
00:01:31,026 --> 00:01:34,600
>> Na ordenación por inserción, o
idea básica aquí está cambiando.

31
00:01:34,600 --> 00:01:36,630
Esa é a palabra clave para a inserción de clasificación.

32
00:01:36,630 --> 00:01:39,630
Nós imos para a etapa a través dunha vez
a matriz de esquerda a dereita.

33
00:01:39,630 --> 00:01:41,670
E como nós facemos, nós somos
cambiará elementos

34
00:01:41,670 --> 00:01:46,260
vimos para dar lugar a
os menores que necesitan un lugar para caber

35
00:01:46,260 --> 00:01:48,080
de volta en que parte clasificada.

36
00:01:48,080 --> 00:01:51,600
Entón, nós construímos a matriz clasificada unha
elemento de cada vez, para a esquerda a dereita,

37
00:01:51,600 --> 00:01:54,740
e cambiamos cousas que facer o cuarto.

38
00:01:54,740 --> 00:01:58,650
O tempo de execución do peor caso de
ordenación por inserción é n ao cadrado.

39
00:01:58,650 --> 00:02:02,380
O mellor caso o tempo de execución é n.

40
00:02:02,380 --> 00:02:05,380
>> Mesturar sort-- a palabra chave
aquí é dividir e mesturar.

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

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- nós división lo
abaixo á metade, á metade, á metade,

43
00:02:13,790 --> 00:02:17,720
ata que teñamos baixo matriz
n dun elemento de matrices.

44
00:02:17,720 --> 00:02:19,470
Un conxunto de matrices n un elemento.

45
00:02:19,470 --> 00:02:22,640
Entón comezamos cunha
1000-elemento da matriz,

46
00:02:22,640 --> 00:02:26,550
e chegamos ao punto en que
1.000 matrices ten un único elemento.

47
00:02:26,550 --> 00:02:30,990
Entón comezamos a mesturar estas sub matrices
xuntos na orde correcta.

48
00:02:30,990 --> 00:02:34,860
Entón, tomamos dúas matrices dun elemento
e crear unha matriz de dous elementos.

49
00:02:34,860 --> 00:02:38,180
Tomamos dúas matrices de dous elementos
e crear unha matriz de catro elementos

50
00:02:38,180 --> 00:02:43,900
e así por diante e así por diante ata que teñamos
novamente reconstruída unha matriz elemento n.

51
00:02:43,900 --> 00:02:48,410
>> O tempo de execución do peor caso de
merge sort é n veces rexistro n.

52
00:02:48,410 --> 00:02:52,390
Temos n elementos, pero
este proceso de recombinación

53
00:02:52,390 --> 00:02:56,960
colle no rexistro n pasos para obter
de volta a un conxunto completo.

54
00:02:56,960 --> 00:03:01,160
O mellor caso o tempo de execución tamén é log n
N porque este proceso non realmente

55
00:03:01,160 --> 00:03:04,090
importan a matriz foi
clasificadas ou non para comezar.

56
00:03:04,090 --> 00:03:07,590
O proceso é o mesmo, non hai
ningunha forma de curtos circuítos cousas.

57
00:03:07,590 --> 00:03:11,610
Entón n log n, no peor caso,
n log n no mellor dos casos.

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

59
00:03:13,960 --> 00:03:16,230
Así, busca linear é sobre iteración.

60
00:03:16,230 --> 00:03:19,500
Continuar en toda a gama
xa que, a partir de esquerda a dereita,

61
00:03:19,500 --> 00:03:21,950
intentando atopar o número
que estamos a procurar.

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

63
00:03:24,550 --> 00:03:27,610
Pode levar a iteración
a través de cada elemento

64
00:03:27,610 --> 00:03:30,660
para atopar o elemento que estamos a buscar
para, tanto na última posición,

65
00:03:30,660 --> 00:03:31,630
ou non en todos.

66
00:03:31,630 --> 00:03:34,720
Pero non podemos confirmar que ata
nós miramos todo.

67
00:03:34,720 --> 00:03:36,730
son o mellor caso, atopamos inmediatamente.

68
00:03:36,730 --> 00:03:41,060
O tempo de execución do mellor caso
busca linear é omega de 1.

69
00:03:41,060 --> 00:03:43,689
>> Para rematar, non había investigación binaria,
que require gama variada.

70
00:03:43,689 --> 00:03:45,605
Lembre que é moi
consideración importante

71
00:03:45,605 --> 00:03:47,155
cando se traballa con pescuda binária.

72
00:03:47,155 --> 00:03:50,180
É unha condición previa para utilizar ele--
a matriz que está a buscar a través

73
00:03:50,180 --> 00:03:52,160
debe ser clasificado.

74
00:03:52,160 --> 00:03:54,500
Se non, a palabra chave
é dividir e conquistar.

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

76
00:03:58,310 --> 00:04:00,780
cada vez que a medida que avanzar a través.

77
00:04:00,780 --> 00:04:04,330
Debido a iso dividir e conquistar
e as cousas dividindo á metade visión,

78
00:04:04,330 --> 00:04:07,450
o tempo de execución do peor caso
de busca binaria é

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

80
00:04:11,730 --> 00:04:13,570
O mellor caso o tempo de execución aínda é un.

81
00:04:13,570 --> 00:04:17,010
>> Podemos atopalo inmediatamente a
primeira vez que facemos unha división, pero,

82
00:04:17,010 --> 00:04:19,339
de novo, lembre que
aínda busca binaria é

83
00:04:19,339 --> 00:04:24,030
substancialmente mellor que a investigación lineal
en virtude de ser log n contra n,

84
00:04:24,030 --> 00:04:27,110
pode ter que ir a través do traballo
de clasificar a matriz primeiro, que

85
00:04:27,110 --> 00:04:32,010
pode facelo menos eficaz en función
sobre o tamaño da iteración clasificados.

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

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