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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Així que en CS50 vam aprendre sobre
una varietat de classificació i recerca

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

4
00:00:09,442 --> 00:00:11,400
I de vegades pot ser
una mica difícil de mantenir

5
00:00:11,400 --> 00:00:14,161
la pista del algoritme fa què.

6
00:00:14,161 --> 00:00:15,910
Tenim realment només
fregat la superfície també,

7
00:00:15,910 --> 00:00:18,740
hi ha moltes altres cerca
i algoritmes d'ordenació.

8
00:00:18,740 --> 00:00:21,780
Així que en aquest vídeo anem a
simplement prendre un parell de minuts

9
00:00:21,780 --> 00:00:24,980
per intentar destil·lar cada algoritme
fins en els seus elements bàsics

10
00:00:24,980 --> 00:00:27,810
perquè pugui recordar més
informació important sobre ells

11
00:00:27,810 --> 00:00:31,970
i ser capaç d'articular el
diferències, si cal.

12
00:00:31,970 --> 00:00:34,220
>> La primera és l'ordenació per selecció.

13
00:00:34,220 --> 00:00:38,210
La idea bàsica d'ordenació per selecció
es troba l'element més petit sense classificar

14
00:00:38,210 --> 00:00:42,890
en una matriu i canviar amb el
primer element sense classificar d'aquesta matriu.

15
00:00:42,890 --> 00:00:46,620
Hem dit que el pitjor dels casos
temps d'execució que es n al quadrat.

16
00:00:46,620 --> 00:00:50,060
I si vols recordar per què, pren
un cop d'ull al vídeo ordenació per selecció.

17
00:00:50,060 --> 00:00:54,560
El temps d'execució millor dels casos
També està n al quadrat.

18
00:00:54,560 --> 00:00:58,910
>> Bombolla espècie, la idea darrere d'aquesta
un és per intercanviar parells adjacents.

19
00:00:58,910 --> 00:01:01,730
Així que aquesta és la clau que l'ajuda
recordar la diferència aquí.

20
00:01:01,730 --> 00:01:04,920
Selecció espècie, és a dir, fins al moment,
trobar la bombolla smallest--

21
00:01:04,920 --> 00:01:06,790
és un gènere intercanviar parells adjacents.

22
00:01:06,790 --> 00:01:08,710
Vam intercanviar parells adjacents
d'elements si

23
00:01:08,710 --> 00:01:12,530
estan fora de servei, el que efectivament
bombolles elements més grans a la dreta,

24
00:01:12,530 --> 00:01:17,060
i, al mateix temps, també comença
per moure elements més petits a l'esquerra.

25
00:01:17,060 --> 00:01:20,180
El pitjor dels casos el temps d'execució cas
d'ordenament de bombolla està n al quadrat.

26
00:01:20,180 --> 00:01:23,476
El temps d'execució millor dels casos
d'ordenament de bombolla és n.

27
00:01:23,476 --> 00:01:25,350
Perquè en aquesta situació
no actually--

28
00:01:25,350 --> 00:01:27,141
pot ser que no hagi de
fer els bescanvis en absolut.

29
00:01:27,141 --> 00:01:31,026
Només hem de fer-ne un
passar a través de tots els elements n.

30
00:01:31,026 --> 00:01:34,600
>> En l'ordenació per inserció, la
idea bàsica que aquí s'està desplaçant.

31
00:01:34,600 --> 00:01:36,630
Aquesta és la paraula clau per l'ordenació per inserció.

32
00:01:36,630 --> 00:01:39,630
Anem a entrar una vegada a través
la matriu d'esquerra a dreta.

33
00:01:39,630 --> 00:01:41,670
I mentre ho fem, estem
canviarà els elements

34
00:01:41,670 --> 00:01:46,260
ja hem vist per fer espai per
més petits que necessiten per encaixar en algun lloc

35
00:01:46,260 --> 00:01:48,080
de tornada a aquesta porció ordenats.

36
00:01:48,080 --> 00:01:51,600
Així construïm la matriu ordenada d'un
element a la vegada, d'esquerra a dreta,

37
00:01:51,600 --> 00:01:54,740
i canviem les coses per fer espai.

38
00:01:54,740 --> 00:01:58,650
El temps d'execució del pitjor cas de
ordenació per inserció està n al quadrat.

39
00:01:58,650 --> 00:02:02,380
El temps millor dels casos de gestió és n.

40
00:02:02,380 --> 00:02:05,380
>> Combinar sort-- la paraula clau
aquí és dividir i combinar.

41
00:02:05,380 --> 00:02:08,949
Dividim la gamma, ja sigui
és de sis elements, vuit elements,

42
00:02:08,949 --> 00:02:13,790
10000 elements-- ho dividim
pel mig, pel mig, pel mig,

43
00:02:13,790 --> 00:02:17,720
fins que tinguem sota array
de n conjunts d'elements d'un.

44
00:02:17,720 --> 00:02:19,470
Un conjunt de n 1 conjunts d'elements.

45
00:02:19,470 --> 00:02:22,640
Així que vam començar amb un sol
1000-element de la matriu,

46
00:02:22,640 --> 00:02:26,550
i arribem al punt en què
té 1.000 matrius d'un element.

47
00:02:26,550 --> 00:02:30,990
Llavors vam començar a combinar aquestes matrius sub
de nou junts en l'ordre correcte.

48
00:02:30,990 --> 00:02:34,860
Així que prenem dos conjunts d'un sol element
i crear una matriu de dos elements.

49
00:02:34,860 --> 00:02:38,180
Prenem dues matrius de dos elements
i crear una matriu de quatre elements

50
00:02:38,180 --> 00:02:43,900
i així successivament i així successivament fins que haguem
novament reconstruït una matriu n element.

51
00:02:43,900 --> 00:02:48,410
>> El temps d'execució del pitjor cas de
fusionen espècie és n vegades log n.

52
00:02:48,410 --> 00:02:52,390
Tenim n elements, però
aquest procés recombinació

53
00:02:52,390 --> 00:02:56,960
pren log n passos per arribar
còpia d'un arsenal complet.

54
00:02:56,960 --> 00:03:01,160
El millor dels casos el temps d'execució és també n log
n perquè aquest procés en realitat no

55
00:03:01,160 --> 00:03:04,090
importa si la matriu era
ordenats o no, per començar.

56
00:03:04,090 --> 00:03:07,590
El procés és el mateix, no hi ha
no hi ha manera de coses de curtcircuit.

57
00:03:07,590 --> 00:03:11,610
Així n log n en el pitjor dels casos,
n log n en el millor dels casos.

58
00:03:11,610 --> 00:03:13,960
>> Parlem de dos
buscar algoritmes.

59
00:03:13,960 --> 00:03:16,230
Així que la recerca lineal és sobre la iteració.

60
00:03:16,230 --> 00:03:19,500
Procedim a través de la matriu
una vegada, d'esquerra a dreta,

61
00:03:19,500 --> 00:03:21,950
tractant de trobar el nombre
que estem buscant.

62
00:03:21,950 --> 00:03:24,550
El temps en el pitjor cas és executar gran O de n.

63
00:03:24,550 --> 00:03:27,610
Ens podria prendre la iteració
a través de cada element

64
00:03:27,610 --> 00:03:30,660
per trobar l'element que estem buscant
per, ja sigui en l'última posició,

65
00:03:30,660 --> 00:03:31,630
o res en absolut.

66
00:03:31,630 --> 00:03:34,720
Però no podem confirmar que fins
hem vist tot.

67
00:03:34,720 --> 00:03:36,730
sóc el millor dels casos, ens trobem immediatament.

68
00:03:36,730 --> 00:03:41,060
El temps d'execució millor dels casos de
cerca lineal és l'omega d'1.

69
00:03:41,060 --> 00:03:43,689
>> Finalment, va haver de recerca binària,
que requereix gamma variada.

70
00:03:43,689 --> 00:03:45,605
Recordeu que és una molt
consideració important

71
00:03:45,605 --> 00:03:47,155
quan es treballa amb recerca binària.

72
00:03:47,155 --> 00:03:50,180
És un requisit previ per a l'ús de it--
la matriu que està mirant a través de

73
00:03:50,180 --> 00:03:52,160
han de ser ordenats.

74
00:03:52,160 --> 00:03:54,500
Altrament, la paraula clau
és divideix i venceràs.

75
00:03:54,500 --> 00:03:58,310
Dividir la matriu en la meitat i
eliminar la meitat dels elements

76
00:03:58,310 --> 00:04:00,780
cada vegada que a mesura que avanci a través.

77
00:04:00,780 --> 00:04:04,330
A causa d'això divideix i venceràs
i les coses de divisió en mig enfocament,

78
00:04:04,330 --> 00:04:07,450
el temps d'execució del pitjor cas
de recerca binària és

79
00:04:07,450 --> 00:04:11,730
log n, que és substancialment
millor que la recerca lineal n.

80
00:04:11,730 --> 00:04:13,570
El temps millor dels casos de gestió segueix sent un.

81
00:04:13,570 --> 00:04:17,010
>> Podríem trobar immediatament el
primera vegada que fem una divisió, però,

82
00:04:17,010 --> 00:04:19,339
de nou, recordar que
tot i que la recerca binària és

83
00:04:19,339 --> 00:04:24,030
substancialment millor que la recerca lineal
en virtut de ser log n enfront de n,

84
00:04:24,030 --> 00:04:27,110
és possible que hagi de passar per la feina
d'ordenar la matriu primera, que

85
00:04:27,110 --> 00:04:32,010
podria fer que sigui menys eficaç depenent
en la mida de la iteració ordenats.

86
00:04:32,010 --> 00:04:35,250
>> Sóc Doug Lloyd, això és CS50.

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