1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Secció 3 - Més Còmode]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Harvard University]

3
00:00:05,070 --> 00:00:07,310
>> [Aquesta és CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Així que la primera pregunta és estranyament redactada.

5
00:00:12,700 --> 00:00:17,480
GDB li permet "depurar" un programa, sinó, més específicament, què farem?

6
00:00:17,480 --> 00:00:22,590
Vaig a respondre a això, i jo no sé què és exactament l'esperat,

7
00:00:22,590 --> 00:00:27,910
així que suposo que és una cosa al llarg de les línies de deixa pas a pas

8
00:00:27,910 --> 00:00:31,540
caminar a través del programa, interactuar-hi, les variables del canvi, fer totes aquestes coses -

9
00:00:31,540 --> 00:00:34,270
bàsicament completament controlar l'execució d'un programa

10
00:00:34,270 --> 00:00:38,410
i inspeccionar qualsevol part donada de l'execució del programa.

11
00:00:38,410 --> 00:00:43,030
Així que aquestes funcions li permeten depurar les coses.

12
00:00:43,030 --> 00:00:44,830
Bé.

13
00:00:44,830 --> 00:00:50,520
Per què la recerca binària que requereixen un arranjament poden ordenar?

14
00:00:50,520 --> 00:00:53,360
Qui vol respondre a això?

15
00:00:56,120 --> 00:01:00,070
[Estudiant] Perquè no funciona si no està ordenada. Sí >>. [Rialles]

16
00:01:00,070 --> 00:01:04,910
Si no està ordenat, llavors és impossible que dividir per la meitat

17
00:01:04,910 --> 00:01:07,850
i saber que tot a l'esquerra és menor i tot a la dreta

18
00:01:07,850 --> 00:01:10,490
és major que el valor mitjà.

19
00:01:10,490 --> 00:01:12,790
Així que ha de ser resolt.

20
00:01:12,790 --> 00:01:14,170
Bé.

21
00:01:14,170 --> 00:01:17,570
Per què és una espècie de bombolla a O del quadrat n?

22
00:01:17,570 --> 00:01:23,230
Hi ha algú que primer vol donar una molt ràpida visió general d'alt nivell de bombolla quin tipus és?

23
00:01:25,950 --> 00:01:33,020
[Estudiant] És, bàsicament, a través de cada element i comprovi els elements primers.

24
00:01:33,020 --> 00:01:37,150
Si estan fora d'on canviar, després de comprovar els elements pròxims i així successivament.

25
00:01:37,150 --> 00:01:40,770
En arribar a la final, llavors vostè sap que el major element es col · loca a l'extrem,

26
00:01:40,770 --> 00:01:42,750
de manera que ignorar aquell temps segueixes passant,

27
00:01:42,750 --> 00:01:48,490
i cada vegada que ha de comprovar un element menys fins que es faci cap canvi. Sí >>.

28
00:01:48,490 --> 00:01:58,470
Es diu tipus bombolla, perquè si li dóna la volta el conjunt del seu costat pel que és a dalt i cap a baix, vertical,

29
00:01:58,470 --> 00:02:03,100
a continuació, els valors grans s'enfonsen fins al fons i els valors petits es bombolla fins a dalt.

30
00:02:03,100 --> 00:02:05,210
Aquesta és la manera com va obtenir el seu nom.

31
00:02:05,210 --> 00:02:08,220
I sí, que acaba de passar.

32
00:02:08,220 --> 00:02:11,190
Segueixes anant a través de la matriu, canviant el valor més gran

33
00:02:11,190 --> 00:02:14,040
per obtenir els valors més grans per a la part inferior.

34
00:02:14,040 --> 00:02:17,500
>> Per què és O quadrat de n?

35
00:02:18,690 --> 00:02:24,620
En primer lloc, ¿algú vol dir això que és de O n al quadrat?

36
00:02:24,620 --> 00:02:28,760
[Estudiant] A causa que per a cada carrera es va n vegades.

37
00:02:28,760 --> 00:02:32,100
Només es pot estar segur que vostè ha pres l'element més gran fins al fons,

38
00:02:32,100 --> 00:02:35,230
llavors vostè ha de repetir això per a tanta elements. Sí >>.

39
00:02:35,230 --> 00:02:41,800
Així que tingui en compte el gran O significa i quins grans mitjans Omega.

40
00:02:41,800 --> 00:02:50,560
L'O gran és com el límit superior del lent que en realitat es pot executar.

41
00:02:50,560 --> 00:02:58,990
Així que dir que és de O n al quadrat, no és de O n o del que seria capaç d'executar

42
00:02:58,990 --> 00:03:02,640
en el temps lineal, però és O de n cubs

43
00:03:02,640 --> 00:03:06,390
perquè està limitada per O de n cubs.

44
00:03:06,390 --> 00:03:12,300
Si està acotat per O quadrat de n, llavors és fitada també per n en cubs.

45
00:03:12,300 --> 00:03:20,280
Per tant, és n al quadrat, i en el cas pitjor absolut que no pot fer millor que quadrada n,

46
00:03:20,280 --> 00:03:22,830
que és per això que és O de n al quadrat.

47
00:03:22,830 --> 00:03:31,200
Així que per veure les matemàtiques lleu en la manera com ve a ser n al quadrat,

48
00:03:31,200 --> 00:03:40,530
si tenim cinc coses a la nostra llista, per primera vegada com els swaps molts podríem potencialment necessiten per prendre

49
00:03:40,530 --> 00:03:47,170
per tal d'aconseguir-ho? Que en realitat només -

50
00:03:47,170 --> 00:03:52,040
Com swaps molts haurem de fer en la primera execució de l'ordenació de bombolla a través de la matriu?

51
00:03:52,040 --> 00:03:53,540
[Estudiant] n - 1. Sí >>.

52
00:03:53,540 --> 00:03:58,340
>> Si hi ha 5 elements, haurem de fer n - 1.

53
00:03:58,340 --> 00:04:01,100
Després, a la segona com swaps molts haurem de fer?

54
00:04:01,100 --> 00:04:03,440
[Estudiant] n - 2. Sí >>.

55
00:04:03,440 --> 00:04:11,640
I la tercera serà n - 3 i, a continuació per conveniència escriuré els dos últims

56
00:04:11,640 --> 00:04:15,270
com llavors haurem de fer 2 swaps i swaps 1.

57
00:04:15,270 --> 00:04:19,899
Suposo que l'últim pot o no pot necessitar realment a succeir.

58
00:04:19,899 --> 00:04:22,820
Es tracta d'un intercanvi? No.

59
00:04:22,820 --> 00:04:26,490
Així que aquestes són les quantitats totals de swaps o almenys comparacions que han de fer.

60
00:04:26,490 --> 00:04:29,910
Encara que no intercanvia, vostè encara necessita per comparar els valors.

61
00:04:29,910 --> 00:04:33,910
Així que hi ha n - 1 comparacions en la primera passada a través de la matriu.

62
00:04:33,910 --> 00:04:42,050
Si reorganitza aquestes coses, anem a realment fer sis coses per apilar les coses molt bé,

63
00:04:42,050 --> 00:04:44,790
i després vaig a fer 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Així que reorganitzar aquestes sumes, volem veure com moltes comparacions que fem

65
00:04:49,910 --> 00:04:52,700
en l'algorisme complet.

66
00:04:52,700 --> 00:04:56,550
Així que si portem a aquests nois per aquí,

67
00:04:56,550 --> 00:05:07,470
llavors estem sent només suma comparacions però molts no ho eren.

68
00:05:07,470 --> 00:05:13,280
Però si sumem aquests i sumem aquests i sumem aquests,

69
00:05:13,280 --> 00:05:18,130
que segueix sent el mateix problema. Acabem de resumir aquests grups en particular.

70
00:05:18,130 --> 00:05:22,400
>> Així que ara estem sumant els 3 n. No es tracta només de 3 n.

71
00:05:22,400 --> 00:05:27,650
Sempre serà n / 2 n de.

72
00:05:27,650 --> 00:05:29,430
Així que aquí passa que té 6.

73
00:05:29,430 --> 00:05:34,830
Si tinguéssim 10 coses, llavors podríem fer aquesta agrupació per a 5 parells diferents de coses

74
00:05:34,830 --> 00:05:37,180
i acabar amb n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Així que sempre obtindràs n / 2 n, i pel que aquest ho anem a apuntar a n al quadrat / 2.

76
00:05:45,840 --> 00:05:48,890
I així, tot i ser el factor de la mitjana, que passa a ser en

77
00:05:48,890 --> 00:05:54,190
pel fet que a través de cada iteració en la matriu es comparen menys 1

78
00:05:54,190 --> 00:05:58,040
així és com vam aconseguir el sobre 2, però segueix sent n al quadrat.

79
00:05:58,040 --> 00:06:01,650
No m'importa el factor constant de la meitat.

80
00:06:01,650 --> 00:06:07,760
Així que un munt de grans coses O com això es basa en un sol tipus de fer aquesta classe de matemàtiques,

81
00:06:07,760 --> 00:06:12,260
fent sumes aritmètiques i coses sèrie geomètrica,

82
00:06:12,260 --> 00:06:17,750
però la majoria d'ells en aquest curs són bastant senzills.

83
00:06:17,750 --> 00:06:19,290
Bé.

84
00:06:19,290 --> 00:06:24,430
Per què és l'ordenació per inserció en Omega de n? Què omega dir?

85
00:06:24,430 --> 00:06:27,730
[Dues estudiants que parlen alhora - inintel · ligible] >> Yeah.

86
00:06:27,730 --> 00:06:30,630
Omega es pot considerar com el límit inferior.

87
00:06:30,630 --> 00:06:36,550
>> Així que no importa què tan eficient és el seu algoritme d'ordenació per inserció és,

88
00:06:36,550 --> 00:06:41,810
independentment de la llista que es passa a dins, sempre cal comparar almenys n coses

89
00:06:41,810 --> 00:06:44,620
o ha de iterar núm coses.

90
00:06:44,620 --> 00:06:47,280
Per què és això?

91
00:06:47,280 --> 00:06:51,190
[Estudiant] Perquè si la llista ja està ordenat, i després a través de la primera iteració

92
00:06:51,190 --> 00:06:54,080
només es pot garantir la primera tasca és el menor,

93
00:06:54,080 --> 00:06:56,490
i la segona iteració només es poden garantir les dues primeres són

94
00:06:56,490 --> 00:07:00,010
perquè no saben que la resta de la llista està ordenada. Sí >>.

95
00:07:00,010 --> 00:07:08,910
Si vostè passa en una llista completament ordenats, si més no has d'anar a través de tots els elements

96
00:07:08,910 --> 00:07:12,180
per veure que res necessita ser mogut al voltant.

97
00:07:12,180 --> 00:07:14,720
Així que passant per sobre de la llista i dient oh, això ja està classificat,

98
00:07:14,720 --> 00:07:18,240
és impossible que vostè sàpiga que està ordenats fins que marqui cada element

99
00:07:18,240 --> 00:07:20,660
per veure que estan en l'ordre establert.

100
00:07:20,660 --> 00:07:25,290
Així que el límit inferior de l'ordenació per inserció és Omega de n.

101
00:07:25,290 --> 00:07:28,210
Què és el pitjor dels casos el temps de funcionament de tipus fusió,

102
00:07:28,210 --> 00:07:31,390
pitjor cas és O grans de nou?

103
00:07:31,390 --> 00:07:37,660
Així que en el pitjor dels casos, com ordenar fusió córrer?

104
00:07:42,170 --> 00:07:43,690
[Estudiant] N log n. Sí >>.

105
00:07:43,690 --> 00:07:49,990
Els més ràpids algorismes generals d'ordenació són n log n. No es pot fer millor.

106
00:07:51,930 --> 00:07:55,130
>> Hi ha casos especials, i si tenim temps avui - però probablement no veuran -

107
00:07:55,130 --> 00:07:59,330
vam poder veure un que ho faci millor que n log n.

108
00:07:59,330 --> 00:08:04,050
Però en el cas general, no es pot fer res millor que n log n.

109
00:08:04,050 --> 00:08:09,680
I combinar espècie passa a ser el que vostè ha de saber per a aquest curs que és n log n.

110
00:08:09,680 --> 00:08:13,260
I pel que en realitat serà l'aplicació d'aquest avui.

111
00:08:13,260 --> 00:08:18,070
I, finalment, en no més de tres frases, com funciona la selecció de classe?

112
00:08:18,070 --> 00:08:20,370
Algú vol contestar, i jo et conte les seves penes

113
00:08:20,370 --> 00:08:22,390
perquè si vostè es passa de 3 -

114
00:08:25,530 --> 00:08:28,330
Algú recorda tipus de selecció?

115
00:08:31,280 --> 00:08:37,809
Tipus de selecció és en general bastant fàcil de recordar només pel nom.

116
00:08:37,809 --> 00:08:45,350
Vostè acaba de recórrer l'array, trobar el que és el valor més gran o més petit -

117
00:08:45,350 --> 00:08:47,290
l'ordre que li toqui rentar polz

118
00:08:47,290 --> 00:08:50,750
Així que diguem que estem ordenar de menor a major.

119
00:08:50,750 --> 00:08:55,250
Vostè iterar sobre la matriu, a la recerca del que és l'element mínim,

120
00:08:55,250 --> 00:08:59,750
seleccioneu i, a continuació, només canviar el que està en el primer lloc.

121
00:08:59,750 --> 00:09:04,090
I després, en la segona passada a través de la matriu, busqui l'element mínim de nou,

122
00:09:04,090 --> 00:09:07,490
seleccioneu i, a continuació, intercanviar amb el que està en la segona posició.

123
00:09:07,490 --> 00:09:10,650
Així que només estem escollint i seleccionant els valors mínims

124
00:09:10,650 --> 00:09:16,050
i la seva inserció en la part frontal de la matriu fins que s'ordena.

125
00:09:19,210 --> 00:09:21,560
Les preguntes sobre això?

126
00:09:21,560 --> 00:09:25,710
>> Aquests inevitablement apareixen en els formularis que s'han d'emplenar quan vostè està presentant el conjunt de processadors.

127
00:09:29,010 --> 00:09:32,360
Aquests són, bàsicament, les respostes a ells.

128
00:09:32,360 --> 00:09:34,230
Bé, ara codificació problemes.

129
00:09:34,230 --> 00:09:40,140
Ja he enviat per correu electrònic - Ningú aconseguir que el correu electrònic? Bé.

130
00:09:40,140 --> 00:09:46,630
Ja he enviat per correu electrònic l'espai que utilitzarem,

131
00:09:46,630 --> 00:09:52,120
i si fas clic en el meu nom - així que crec que estaré al fons

132
00:09:52,120 --> 00:09:57,170
causa de la r cap enrere - però si fas clic en el meu nom veuràs dues revisions.

133
00:09:57,170 --> 00:10:02,650
Revisió 1 serà que ja copiar i enganxar el codi en els espais

134
00:10:02,650 --> 00:10:06,900
de manera que la recerca haurà de posar en pràctica.

135
00:10:06,900 --> 00:10:10,540
I Revisió 2 serà el tipus que posem en pràctica després d'això.

136
00:10:10,540 --> 00:10:15,770
Així que vostè pot fer clic en el meu Revisió 1 i treballar des d'allà.

137
00:10:17,350 --> 00:10:22,060
I ara volem implementar la recerca binària.

138
00:10:22,060 --> 00:10:26,470
>> Algú vol donar només un pseudocodi d'alt nivell explicació

139
00:10:26,470 --> 00:10:31,440
del que haurem de fer per a la recerca? Si.

140
00:10:31,440 --> 00:10:36,170
[Estudiant] Vostè acaba de prendre el centre de la matriu i veure si el que estàs buscant

141
00:10:36,170 --> 00:10:38,650
és menor que o més que això.

142
00:10:38,650 --> 00:10:41,080
I si és menys, vas a la part que és menys,

143
00:10:41,080 --> 00:10:44,750
i si és més, te'n vas a la mitjana que és més i repetir fins que vostè acaba d'aconseguir una cosa.

144
00:10:44,750 --> 00:10:46,570
[Bowden] Yeah.

145
00:10:46,570 --> 00:10:51,320
Tingueu en compte que la nostra matriu de nombres ja està ordenat,

146
00:10:51,320 --> 00:10:57,190
i pel que significa que podem prendre avantatge d'això i vam poder comprovar en primer lloc,

147
00:10:57,190 --> 00:11:00,390
bé, estic buscant el número 50.

148
00:11:00,390 --> 00:11:03,720
Perquè pugui entrar al centre.

149
00:11:03,720 --> 00:11:07,380
Mitjà és difícil de definir, quan és un nombre parell de coses,

150
00:11:07,380 --> 00:11:10,820
però diguem que sempre anem a truncar a la meitat.

151
00:11:10,820 --> 00:11:14,420
Així que aquí tenim 8 coses, de manera que la mitjana seria de 16.

152
00:11:14,420 --> 00:11:17,330
Estic buscant a 50, així que 50 és més gran que 16.

153
00:11:17,330 --> 00:11:21,310
Així que ara, bàsicament, pot tractar la meva matriu com aquests elements.

154
00:11:21,310 --> 00:11:23,450
Puc llençar tot a partir de 16 anys.

155
00:11:23,450 --> 00:11:27,440
Ara la meva matriu és només aquests 4 elements, i ho repeteixo.

156
00:11:27,440 --> 00:11:31,910
Així que vull trobar el mitjà més, que serà 42.

157
00:11:31,910 --> 00:11:34,730
42 és inferior a 50, pel que puc tirar aquests dos elements.

158
00:11:34,730 --> 00:11:36,890
Aquest és el meu arsenal restant.

159
00:11:36,890 --> 00:11:38,430
Vaig a trobar el mitjà de nou.

160
00:11:38,430 --> 00:11:42,100
Suposo que 50 era un mal exemple perquè sempre estava tirant coses a l'esquerra,

161
00:11:42,100 --> 00:11:48,280
però en la mateixa mesura, si estic buscant alguna cosa

162
00:11:48,280 --> 00:11:52,100
i és menor que l'element que estic mirant,

163
00:11:52,100 --> 00:11:55,080
llavors vaig a tirar tot a la dreta.

164
00:11:55,080 --> 00:11:58,150
Així que ara hem d'aplicar això.

165
00:11:58,150 --> 00:12:02,310
Recordeu que hem de passar de mida.

166
00:12:02,310 --> 00:12:06,730
No podem també han codificar mida.

167
00:12:06,730 --> 00:12:11,640
Així que si ens desfem que # defineix -

168
00:12:19,630 --> 00:12:21,430
Bé.

169
00:12:21,430 --> 00:12:27,180
Com puc esbrinar molt bé quin és la mida de la matriu de nombres en l'actualitat és?

170
00:12:27,180 --> 00:12:30,950
>> Quants elements hi ha a la matriu números?

171
00:12:30,950 --> 00:12:33,630
[Estudiants] Els nombres, parèntesis,. Longitud?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Això no existeix en C.

173
00:12:36,600 --> 00:12:38,580
Necessitat. Longitud.

174
00:12:38,580 --> 00:12:42,010
Les matrius no tenen propietats, de manera que no hi ha cap propietat de les matrius de longitud

175
00:12:42,010 --> 00:12:45,650
que només li donarà el temps que passa a ser.

176
00:12:48,180 --> 00:12:51,620
[Estudiant] Veure la quantitat de memòria que té i dividir per la quantitat - >> Yeah.

177
00:12:51,620 --> 00:12:55,810
Llavors, com podem saber quanta memòria té? >> [Estudiant] sizeof. >> Sí, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof és l'operador que tornarà la mida de la matriu de nombres.

179
00:13:01,680 --> 00:13:10,060
I això serà sencers però hi ha moltes vegades la mida d'un sencer

180
00:13:10,060 --> 00:13:14,050
ja que és la quantitat de memòria que realment prenent.

181
00:13:14,050 --> 00:13:17,630
Així que si voleu que el nombre de coses en la matriu,

182
00:13:17,630 --> 00:13:20,560
llavors vaig a voler dividir per la grandària d'un sencer.

183
00:13:22,820 --> 00:13:26,010
Bé. Així que em permet passar de mida aquí.

184
00:13:26,010 --> 00:13:29,430
Per què he de passar en grandària després de tot?

185
00:13:29,430 --> 00:13:38,570
Per què no puc fer aquí int size = sizeof (paller) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Per què no funciona?

187
00:13:41,490 --> 00:13:44,470
[Estudiant] No és una variable global.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack existeix i estem passant en números com paller,

189
00:13:51,540 --> 00:13:54,700
i això és una mena de presagi del que vindrà. Si.

190
00:13:54,700 --> 00:14:00,170
[Estudiant] Haystack és només la referència a la mateixa, de manera que tornaria el gran que és de referència.

191
00:14:00,170 --> 00:14:02,150
Si.

192
00:14:02,150 --> 00:14:09,000
Dubto que en la conferència que ha vist la pila encara realment, oi?

193
00:14:09,000 --> 00:14:11,270
Hem parlat sobre això.

194
00:14:11,270 --> 00:14:16,090
Així que la pila és on totes les variables s'han d'emmagatzemar.

195
00:14:16,090 --> 00:14:19,960
>> Qualsevol memòria que assignada per les variables locals va a la pila,

196
00:14:19,960 --> 00:14:24,790
i cada funció té el seu propi espai a la pila, el seu propi marc de pila és el que es diu.

197
00:14:24,790 --> 00:14:31,590
Així que té el seu principal marc de pila, i dins d'ella va a existir aquesta matriu nombres,

198
00:14:31,590 --> 00:14:34,270
i que serà de mida sizeof (nombres).

199
00:14:34,270 --> 00:14:38,180
Va a tenir la mida dels nombres dividit per la mida dels elements,

200
00:14:38,180 --> 00:14:42,010
sinó que totes les vides dins de marc de pila principal.

201
00:14:42,010 --> 00:14:45,190
Quan cridem a la recerca, recerca obté el seu propi marc de pila,

202
00:14:45,190 --> 00:14:48,840
seu propi espai per emmagatzemar totes les variables locals.

203
00:14:48,840 --> 00:14:56,420
Però aquests arguments - així paller no és una còpia d'aquesta matriu completa.

204
00:14:56,420 --> 00:15:00,990
No lliurem a tot el conjunt com una còpia en la recerca.

205
00:15:00,990 --> 00:15:04,030
Tot just passa una referència a la matriu.

206
00:15:04,030 --> 00:15:11,470
Així recerca pot accedir a aquests números a través d'aquesta referència.

207
00:15:11,470 --> 00:15:17,100
És encara l'accés a les coses que viuen a l'interior del marc de pila principal,

208
00:15:17,100 --> 00:15:22,990
però en el fons, quan arribem als punters, que ha de ser breu,

209
00:15:22,990 --> 00:15:24,980
això és el que els punters són.

210
00:15:24,980 --> 00:15:29,400
Els punters són només referències a les coses, i es pot utilitzar punters per accedir a les coses

211
00:15:29,400 --> 00:15:32,030
que es troben en els marcs de pila altres coses.

212
00:15:32,030 --> 00:15:37,660
Així que, encara que el nombre és local principal, encara pot accedir a través d'aquest punter.

213
00:15:37,660 --> 00:15:41,770
Però ja que és simplement un punter i és només una referència,

214
00:15:41,770 --> 00:15:45,040
sizeof (paller) només retorna la grandària de la mateixa referència.

215
00:15:45,040 --> 00:15:47,950
No torna la mida del que està assenyalant.

216
00:15:47,950 --> 00:15:51,110
No torna la mida real dels nombres.

217
00:15:51,110 --> 00:15:55,660
I perquè això no funcionarà com es desitja.

218
00:15:55,660 --> 00:15:57,320
>> Les preguntes sobre això?

219
00:15:57,320 --> 00:16:03,250
Els punters s'haurà anat en detall molt més sagnant en les setmanes per venir.

220
00:16:06,750 --> 00:16:13,740
I aquesta és la raó per un munt de coses que es veuen, la majoria de les coses o les coses d'ordre de recerca,

221
00:16:13,740 --> 00:16:16,990
són gairebé tots haurem de prendre la mida real de la matriu,

222
00:16:16,990 --> 00:16:20,440
perquè en C, no tenim idea del que la mida de la matriu és.

223
00:16:20,440 --> 00:16:22,720
Has de passar manualment polz

224
00:16:22,720 --> 00:16:27,190
I no es pot passar manualment a tota la matriu, ja que està de pas en la referència

225
00:16:27,190 --> 00:16:30,390
i no es pot obtenir la mida de la referència.

226
00:16:30,390 --> 00:16:32,300
Bé.

227
00:16:32,300 --> 00:16:38,160
Així que ara volem posar en pràctica el que s'ha explicat anteriorment.

228
00:16:38,160 --> 00:16:41,530
Pot treballar-hi durant un minut,

229
00:16:41,530 --> 00:16:45,250
i vostè no ha de preocupar d'aconseguir tot perfectament 100% de treball.

230
00:16:45,250 --> 00:16:51,410
Només ha d'escriure el pseudocodi mitjà de com crec que hauria de funcionar.

231
00:16:52,000 --> 00:16:53,630
Bé.

232
00:16:53,630 --> 00:16:56,350
No hi ha necessitat d'estar completament acabat amb això.

233
00:16:56,350 --> 00:17:02,380
Però, ¿algú se senti còmode amb el que tinc fins ara,

234
00:17:02,380 --> 00:17:05,599
com una cosa que podem treballar de forma conjunta?

235
00:17:05,599 --> 00:17:09,690
Algú vol ser voluntari? O escolliran aleatòriament.

236
00:17:12,680 --> 00:17:18,599
No ha de ser just per qualsevol mesura, sinó alguna cosa que pot modificar en un estat de treball.

237
00:17:18,599 --> 00:17:20,720
[Estudiant] Clar. >> Okay.

238
00:17:20,720 --> 00:17:27,220
Així es pot estalviar la revisió fent clic a la petita icona Guardar.

239
00:17:27,220 --> 00:17:29,950
Vostè és Ramya, oi? >> [Estudiant] Yeah. >> [Bowden] Bé.

240
00:17:29,950 --> 00:17:35,140
Així que ara puc veure la seva revisió i tothom pot aixecar la revisió.

241
00:17:35,140 --> 00:17:38,600
I aquí tenim - Està bé.

242
00:17:38,600 --> 00:17:43,160
Així va ser amb Ramya la solució recursiva, que és definitivament una solució vàlida.

243
00:17:43,160 --> 00:17:44,970
Hi ha dues maneres que vostè pot fer aquest problema.

244
00:17:44,970 --> 00:17:48,060
Vostè pot fer-ho iterativament o recursivament.

245
00:17:48,060 --> 00:17:53,860
La majoria dels problemes que trobi que es pot fer de forma recursiva també pot realitzar iterativament.

246
00:17:53,860 --> 00:17:58,510
Així que aquí ho hem fet de forma recursiva.

247
00:17:58,510 --> 00:18:03,730
>> Algú vol definir el que significa fer una funció recursiva?

248
00:18:07,210 --> 00:18:08,920
[Estudiant] Quan es té una funció pròpia anomenada

249
00:18:08,920 --> 00:18:13,470
i després trucar a si mateix fins que surti amb veritable i cert. Sí >>.

250
00:18:13,470 --> 00:18:17,680
Una funció recursiva és una funció que es diu a si mateixa.

251
00:18:17,680 --> 00:18:24,140
Hi ha tres coses importants que una funció recursiva ha de tenir.

252
00:18:24,140 --> 00:18:27,310
La primera és, òbviament, es diu a si mateixa.

253
00:18:27,310 --> 00:18:29,650
El segon és el cas base.

254
00:18:29,650 --> 00:18:33,390
Així que en algun punt la funció ha de deixar de cridar a si mateix,

255
00:18:33,390 --> 00:18:35,610
i això és el que el cas base és per.

256
00:18:35,610 --> 00:18:43,860
Així que aquí sabem que hem de deixar, hem de renunciar a la nostra recerca

257
00:18:43,860 --> 00:18:48,150
quan l'inici és igual a extrem - i anem a repassar el que això significa.

258
00:18:48,150 --> 00:18:52,130
Però, finalment, l'última cosa que és important per a les funcions recursives:

259
00:18:52,130 --> 00:18:59,250
les funcions d'alguna manera ha d'abordar la causa base.

260
00:18:59,250 --> 00:19:04,140
Igual que si vostè no està realment actualitzar res quan vostè fa la crida recursiva en segon lloc,

261
00:19:04,140 --> 00:19:07,880
si vostè està literalment a la crida a la funció de nou amb els mateixos arguments

262
00:19:07,880 --> 00:19:10,130
i no hi ha variables globals han canviat ni res,

263
00:19:10,130 --> 00:19:14,430
vostè mai arribarà al cas base, en aquest cas això és dolent.

264
00:19:14,430 --> 00:19:17,950
Serà una repetició infinita i un desbordament de pila.

265
00:19:17,950 --> 00:19:24,330
Però aquí veiem que l'actualització està passant des que s'inicia l'actualització + final / 2,

266
00:19:24,330 --> 00:19:28,180
estem actualitzant l'argument final aquí, estem actualitzant l'argument d'inici aquí.

267
00:19:28,180 --> 00:19:32,860
Així, en totes les trucades recursives estem actualitzant alguna cosa. Bé.

268
00:19:32,860 --> 00:19:38,110
Vols que ens guiarà a través de la seva solució? >> Clar.

269
00:19:38,110 --> 00:19:44,270
Estic usant SearchHelp de manera que cada vegada que faig aquesta crida de funció

270
00:19:44,270 --> 00:19:47,910
Tinc el principi d'on jo estic buscant en la matriu i la fi

271
00:19:47,910 --> 00:19:49,380
d'on jo estic buscant la matriu.

272
00:19:49,380 --> 00:19:55,330
>> A cada pas, on es diu que és l'element central, que és inici + final / 2,

273
00:19:55,330 --> 00:19:58,850
que és igual al que estem buscant?

274
00:19:58,850 --> 00:20:04,650
I si és així, llavors que el trobem, i suposo que es passa als nivells de recursivitat.

275
00:20:04,650 --> 00:20:12,540
I si això no és cert, llavors es comprova si el valor mitjà de la matriu és massa gran,

276
00:20:12,540 --> 00:20:19,320
en aquest cas ens fixem en la meitat esquerra de la matriu per va des del començament fins l'índex mitjà.

277
00:20:19,320 --> 00:20:22,710
I una altra cosa que fem la mitjana final.

278
00:20:22,710 --> 00:20:24,740
[Bowden] Bé.

279
00:20:24,740 --> 00:20:27,730
Això sembla bé.

280
00:20:27,730 --> 00:20:36,640
Està bé, així que un parell de coses, i de fet, això és una cosa molt alt nivell

281
00:20:36,640 --> 00:20:41,270
que vostè no haurà de saber per aquest curs, però és cert.

282
00:20:41,270 --> 00:20:46,080
Les funcions recursives, que sempre se sent que són un mal negoci

283
00:20:46,080 --> 00:20:51,160
perquè si es diu a si mateix de forma recursiva massa vegades, s'obté desbordament de pila

284
00:20:51,160 --> 00:20:54,990
ja que, com he dit abans, cada funció té el seu propi marc de pila.

285
00:20:54,990 --> 00:20:59,500
Així que cada crida de la funció recursiva obté el seu propi marc de pila.

286
00:20:59,500 --> 00:21:04,140
Així que si vostè fa 1.000 trucades recursives, s'obté 1.000 marcs de pila,

287
00:21:04,140 --> 00:21:08,390
i ràpidament el portarà a tenir marcs de pila massa coses i acaba de trencar.

288
00:21:08,390 --> 00:21:13,480
Per això és que les funcions recursives són generalment dolents.

289
00:21:13,480 --> 00:21:19,370
Però hi ha un subconjunt de les funcions recursives agradable anomenat cua de funcions recursives,

290
00:21:19,370 --> 00:21:26,120
i aquest passa a ser un exemple d'un en el que si el compilador nota això

291
00:21:26,120 --> 00:21:29,920
i ha de ser, crec - en Clang si se li passa la bandera-O2

292
00:21:29,920 --> 00:21:33,250
llavors es donarà compte d'això és la cua recursiva i fer les coses bé.

293
00:21:33,250 --> 00:21:40,050
>> Es tornarà a utilitzar el mateix marc de pila i una altra per a cada crida recursiva.

294
00:21:40,050 --> 00:21:47,010
I ja que estàs utilitzant el mateix marc de pila, vostè no ha de preocupar sobre

295
00:21:47,010 --> 00:21:51,690
mai apilar desbordant, i alhora, com vas dir abans,

296
00:21:51,690 --> 00:21:56,380
què, després que torni cert, llavors cal tornar tot el d'aquests marcs de pila

297
00:21:56,380 --> 00:22:01,740
i la crida del 10 al SearchHelp ha de tornar als dies 9, ha de tornar a la 8a.

298
00:22:01,740 --> 00:22:05,360
Així que no cal que passi quan les funcions són col recursiva.

299
00:22:05,360 --> 00:22:13,740
I així, el que fa que aquesta funció recursiva de cua és un avís de que per a qualsevol crida d'atenció a searchHelp

300
00:22:13,740 --> 00:22:18,470
la crida recursiva que està fent és el que està tornant.

301
00:22:18,470 --> 00:22:25,290
Així, a la primera crida a SearchHelp, que sigui immediatament tornar false,

302
00:22:25,290 --> 00:22:29,590
immediatament tornar true, o es fa una crida recursiva a SearchHelp

303
00:22:29,590 --> 00:22:33,810
on el que estem tornant és el que aquesta crida està tornant.

304
00:22:33,810 --> 00:22:51,560
I no podríem fer això si ho féssim alguna cosa com int x = SearchHelp, return x * 2,

305
00:22:51,560 --> 00:22:55,440
només alguns canvis a l'atzar.

306
00:22:55,440 --> 00:23:01,470
>> Així que ara aquesta crida recursiva, aquesta int x = SearchHelp crida recursiva,

307
00:23:01,470 --> 00:23:05,740
ja no és la cua recursiva, ja que en realitat ha de tornar

308
00:23:05,740 --> 00:23:10,400
de nou a un marc de pila anterior perquè aquesta trucada prèvia a la funció

309
00:23:10,400 --> 00:23:13,040
A continuació, pot fer alguna cosa amb el valor de retorn.

310
00:23:13,040 --> 00:23:22,190
Així que això no és la cua recursiva, però el que teníem abans és ben cua recursiva. Si.

311
00:23:22,190 --> 00:23:27,000
[Estudiant] No hauria el cas de la segona base es comprova en primer lloc

312
00:23:27,000 --> 00:23:30,640
perquè podria haver una situació en què quan se li passa l'argument

313
00:23:30,640 --> 00:23:35,770
ha començar = fi, sinó que són el valor de l'agulla.

314
00:23:35,770 --> 00:23:47,310
La pregunta va ser no podem córrer en el cas extrem és el valor d'agulla

315
00:23:47,310 --> 00:23:52,000
o començar = fi, apropiadament, iniciï final =

316
00:23:52,000 --> 00:23:59,480
i no s'han comprovat que determinat valor, però,

317
00:23:59,480 --> 00:24:03,910
a continuació, iniciar + final / 2 és només serà el mateix valor.

318
00:24:03,910 --> 00:24:07,890
Però ja hem tornat fals i que en realitat mai comprovat el valor.

319
00:24:07,890 --> 00:24:14,240
Així que almenys, en la primera convocatòria, si la mida és 0, llavors volem tornar false.

320
00:24:14,240 --> 00:24:17,710
Però si la mida és 1, llavors començament no acabarà igual,

321
00:24:17,710 --> 00:24:19,820
i anem a comprovar almenys l'únic element.

322
00:24:19,820 --> 00:24:26,750
Però crec que tens raó en que pot acabar en un cas en l'inici + final / 2,

323
00:24:26,750 --> 00:24:31,190
inici acaba sent la mateixa que inici + final / 2,

324
00:24:31,190 --> 00:24:35,350
però mai hem fet el check aquest element.

325
00:24:35,350 --> 00:24:44,740
>> Així que si busquem en primer lloc és un dels eixos del valor que estem buscant,

326
00:24:44,740 --> 00:24:47,110
llavors pot tornar immediatament veritat.

327
00:24:47,110 --> 00:24:50,740
Perquè si són iguals, llavors no hi ha raó per continuar

328
00:24:50,740 --> 00:24:58,440
ja que només anem a actualitzar a un cas en què ens trobem en una matriu d'un sol element.

329
00:24:58,440 --> 00:25:01,110
Si aquest element no és el que estem buscant,

330
00:25:01,110 --> 00:25:03,530
llavors tot el que està malament. Si.

331
00:25:03,530 --> 00:25:08,900
[Estudiant] El cas és que ja que la mida és més gran que el nombre d'elements en la matriu,

332
00:25:08,900 --> 00:25:13,070
ja hi ha un offset - >> Passa el mateix amb la mida -

333
00:25:13,070 --> 00:25:19,380
[Estudiant] Digues si la matriu era de mida 0, llavors el SearchHelp realment comprovar paller de 0

334
00:25:19,380 --> 00:25:21,490
a la primera trucada.

335
00:25:21,490 --> 00:25:25,300
La matriu té una mida 0, de manera que el 0 és - >> Yeah.

336
00:25:25,300 --> 00:25:30,750
Hi ha una altra cosa que - pot ser bo. Anem a pensar.

337
00:25:30,750 --> 00:25:40,120
Així que si la matriu amb 10 elements i el del mitjà que revisarem és l'índex de 5,

338
00:25:40,120 --> 00:25:45,700
pel que estem comprovant 5, i diguem que el valor és menor.

339
00:25:45,700 --> 00:25:50,720
Així que estem tirant tot a rodar a partir del 5 d'ara endavant.

340
00:25:50,720 --> 00:25:54,030
Així que comença a + final / 2 serà el nostre nou final,

341
00:25:54,030 --> 00:25:57,450
així que sí, que sempre estarà més enllà del final de la matriu.

342
00:25:57,450 --> 00:26:03,570
Si es tracta d'un cas si era parell o senar, llavors podríem comprovar, per exemple, 4,

343
00:26:03,570 --> 00:26:05,770
però encara estem desaprofitant -

344
00:26:05,770 --> 00:26:13,500
Així que sí, al final sempre estarà més enllà del final real de la matriu.

345
00:26:13,500 --> 00:26:18,350
De manera que els elements que ens estem centrant, final sempre serà el que després d'això.

346
00:26:18,350 --> 00:26:24,270
I així, si fa arrencada acaba mai igual, estem en una matriu de mida 0.

347
00:26:24,270 --> 00:26:35,600
>> L'altra cosa que estava pensant és que estem actualitzant el principi fins al final es va iniciar + / 2,

348
00:26:35,600 --> 00:26:44,020
de manera que aquest és el cas que estic tenint problemes amb, per on començar + final / 2

349
00:26:44,020 --> 00:26:46,820
és l'element que està comprovant.

350
00:26:46,820 --> 00:26:58,150
Anem a dir que vam tenir aquesta matriu de 10 elements. El que sigui.

351
00:26:58,150 --> 00:27:03,250
Així que comença a + final / 2 serà una cosa així com aquest,

352
00:27:03,250 --> 00:27:07,060
i si aquest no és el valor, diguem que voleu actualitzar.

353
00:27:07,060 --> 00:27:10,060
El valor és més gran, de manera que desitgi veure en aquesta meitat de la matriu.

354
00:27:10,060 --> 00:27:15,910
Llavors, ¿com estem actualitzant principi, estem actualitzant principi per ser ara aquest element.

355
00:27:15,910 --> 00:27:23,790
Però això encara pot funcionar, o si més no, pot fer start + final / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Estudiant] No cal que es comenci final + [inaudible] >> Si.

357
00:27:27,850 --> 00:27:33,240
Ja hem comprovat aquest element i sé que no és la que estem buscant.

358
00:27:33,240 --> 00:27:36,800
Així que no cal actualitzar principi per ser aquest element.

359
00:27:36,800 --> 00:27:39,560
Només podem saltar i actualitzar començar a ser aquest element.

360
00:27:39,560 --> 00:27:46,060
I hi ha mai un cas, direm, que això fos final,

361
00:27:46,060 --> 00:27:53,140
així llavors començar seria això, iniciï + final / 2 seria això,

362
00:27:53,140 --> 00:28:00,580
començar final + - Sí, crec que pot acabar en una recursió infinita.

363
00:28:00,580 --> 00:28:12,690
Anem a dir que és una matriu de mida 2 o una matriu de mida 1. Crec que això va a funcionar.

364
00:28:12,690 --> 00:28:19,490
Així en l'actualitat, és que inici i final element és 1 més enllà d'ella.

365
00:28:19,490 --> 00:28:24,110
De manera que l'element que anem a comprovar és aquest,

366
00:28:24,110 --> 00:28:29,400
i després, quan ens posem al dia d'inici, estem actualitzant principi per ser 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
que ens acabarà de nou amb arrencada sent aquest element.

368
00:28:33,160 --> 00:28:36,210
>> Així que estem comprovant l'element mateix una i una altra.

369
00:28:36,210 --> 00:28:43,310
Així que aquest és el cas en què cada crida recursiva en realitat ha d'actualitzar alguna cosa.

370
00:28:43,310 --> 00:28:48,370
Així que hem de fer start + final / 2 + 1, o si no hi ha un cas

371
00:28:48,370 --> 00:28:50,710
on no estem en realitat l'actualització inicial.

372
00:28:50,710 --> 00:28:53,820
Tothom veu això?

373
00:28:53,820 --> 00:28:56,310
Bé.

374
00:28:56,310 --> 00:29:03,860
Algú té alguna pregunta sobre aquesta solució o més comentaris?

375
00:29:05,220 --> 00:29:10,280
Bé. Algú té una solució iterativa que tots puguem mirar?

376
00:29:17,400 --> 00:29:20,940
Sabia que tots ho fan de forma recursiva?

377
00:29:20,940 --> 00:29:25,950
O també suposo que si ella es va obrir, llavors vostè podria tenir anul · lat el seu anterior.

378
00:29:25,950 --> 00:29:28,810
Es guarda automàticament? Jo no sóc positiu.

379
00:29:35,090 --> 00:29:39,130
Algú ha iteratiu?

380
00:29:39,130 --> 00:29:42,430
Podem caminar a través d'ella junts si no.

381
00:29:46,080 --> 00:29:48,100
La idea serà el mateix.

382
00:30:00,260 --> 00:30:02,830
Solució iterativa.

383
00:30:02,830 --> 00:30:07,140
Anem a voler fer bàsicament la mateixa idea

384
00:30:07,140 --> 00:30:16,530
on volem portar el compte del nou final de la matriu i el nou començament de la matriu

385
00:30:16,530 --> 00:30:18,510
i fer això una i altra vegada.

386
00:30:18,510 --> 00:30:22,430
I si el que estem fer el seguiment de com l'inici i el final mai es creuen,

387
00:30:22,430 --> 00:30:29,020
llavors nosaltres no el trobem i ens pot tornar false.

388
00:30:29,020 --> 00:30:37,540
Llavors, com puc fer això? Algú té suggeriments o codi perquè jo tiri cap amunt?

389
00:30:42,190 --> 00:30:47,450
[Estudiant] Fer un bucle while. Sí >>.

390
00:30:47,450 --> 00:30:49,450
Vostè va a voler fer un bucle.

391
00:30:49,450 --> 00:30:51,830
>> Vostè té un codi que podria tirar amunt, o el que se li va a suggerir?

392
00:30:51,830 --> 00:30:56,340
[Estudiant] Crec que sí. >> Està bé. Això fa les coses més fàcils. Quin era el seu nom?

393
00:30:56,340 --> 00:30:57,890
[Estudiant] Lucas.

394
00:31:00,140 --> 00:31:04,190
Revisió 1. Bé.

395
00:31:04,190 --> 00:31:13,200
Menor és el que anomenem començar abans.

396
00:31:13,200 --> 00:31:17,080
Fins no és exactament el que dèiem abans de final.

397
00:31:17,080 --> 00:31:22,750
En realitat, està ara al final de la matriu. És un element que hem de considerar.

398
00:31:22,750 --> 00:31:26,890
Així sota és 0, a dalt és la mida de la matriu - 1,

399
00:31:26,890 --> 00:31:34,780
i ara estem bucle, i la comprovació es -

400
00:31:34,780 --> 00:31:37,340
Suposo que es pot caminar a través d'ell.

401
00:31:37,340 --> 00:31:41,420
Quin va ser el seu pensament a través d'això? Camina amb nosaltres a través del seu codi.

402
00:31:41,420 --> 00:31:49,940
[Estudiant] Clar. Fixeu-vos en el valor paller al centre i comparar-la amb l'agulla.

403
00:31:49,940 --> 00:31:58,520
Així que si és més gran que la seva agulla, llavors vostè vol - Oh, en realitat, hauria de ser al revés.

404
00:31:58,520 --> 00:32:05,180
Vostè va a voler tirar la meitat dreta, de manera que si, que ha de ser el camí.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Així que això ha de ser menys? És això el que vas dir? >> [Estudiant] Yeah.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Bé. Menys.

407
00:32:10,390 --> 00:32:15,700
Així que si el que estem veient és més petit que el que volem,

408
00:32:15,700 --> 00:32:19,410
llavors sí, volem tirar la meitat esquerra,

409
00:32:19,410 --> 00:32:22,210
el que significa que estem actualitzant tot el que estem considerant

410
00:32:22,210 --> 00:32:26,610
movent sota a la dreta de la matriu.

411
00:32:26,610 --> 00:32:30,130
Això es veu bé.

412
00:32:30,130 --> 00:32:34,550
Crec que té el mateix problema que hem dit en l'anterior,

413
00:32:34,550 --> 00:32:49,760
on si baixa és 0 i fins és 1, llavors sota fins + / 2 s'establirà a ser el mateix una altra vegada.

414
00:32:49,760 --> 00:32:53,860
>> I fins i tot si aquest no és el cas, encara és més eficient si més no

415
00:32:53,860 --> 00:32:57,630
a tir de lluny l'element que acabem de veure que sabem que està malament.

416
00:32:57,630 --> 00:33:03,240
Així que sota + dalt / 2 + 1 - >> [estudiant] Això hauria de ser al contrari.

417
00:33:03,240 --> 00:33:05,900
[Bowden] O això hauria de ser - 1 i l'altre ha de ser + 1.

418
00:33:05,900 --> 00:33:09,580
[Estudiant] I ha d'haver un doble signe igual. >> [Bowden] Yeah.

419
00:33:09,580 --> 00:33:11,340
[Estudiant] Yeah.

420
00:33:14,540 --> 00:33:15,910
Bé.

421
00:33:15,910 --> 00:33:21,280
I, finalment, ara que tenim aquest 1 + - 1 cosa,

422
00:33:21,280 --> 00:33:31,520
és que - potser no és - és sempre possible baix per acabar amb un valor major de fins?

423
00:33:35,710 --> 00:33:40,320
Crec que l'única manera en què pot succeir - És possible? >> [Estudiant] No ho sé.

424
00:33:40,320 --> 00:33:45,220
Però si es posa truncada i després es fa menys que 1 i després - >> Yeah.

425
00:33:45,220 --> 00:33:47,480
[Estudiant] És, possiblement, arribar en mal estat.

426
00:33:49,700 --> 00:33:53,940
Crec que hauria de ser bo només perquè

427
00:33:53,940 --> 00:33:58,800
perquè acabi inferior haurien de ser igual, crec.

428
00:33:58,800 --> 00:34:03,070
Però si són iguals, llavors no hauria fet el bucle while per començar

429
00:34:03,070 --> 00:34:06,670
i ens hauria tornat el valor. Així que crec que estem bé ara.

430
00:34:06,670 --> 00:34:11,530
Observi que encara que aquest problema ja no és recursiu,

431
00:34:11,530 --> 00:34:17,400
el mateix tipus d'idees s'apliquen en què podem veure com això tan fàcilment es presta

432
00:34:17,400 --> 00:34:23,659
a una solució recursiva pel fet que estem només l'actualització dels índexs d'una i altra vegada,

433
00:34:23,659 --> 00:34:29,960
estem fent el problema més petit, ens estem centrant en un subconjunt de la matriu.

434
00:34:29,960 --> 00:34:40,860
[Estudiant] Si baixa és 0 i fins és 1, els dos estarien 0 + 1/2, que aniria a 0,

435
00:34:40,860 --> 00:34:44,429
i llavors un seria + 1, un seria - 1.

436
00:34:47,000 --> 00:34:50,870
[Estudiant] On estem comprovant la igualtat?

437
00:34:50,870 --> 00:34:55,100
Igual que si el medi és realment agulla?

438
00:34:55,100 --> 00:34:58,590
No estem actualment fent això? Oh!

439
00:35:00,610 --> 00:35:02,460
Si és -

440
00:35:05,340 --> 00:35:13,740
Sí No podem limitar-nos a fer la prova aquí perquè diguem que la primera meitat -

441
00:35:13,740 --> 00:35:16,430
[Estudiant] De fet, és com no llençar el enquadernat.

442
00:35:16,430 --> 00:35:20,220
Així que si vostè llança lluny el límit, vostè ha de comprovar primer o el que sigui.

443
00:35:20,220 --> 00:35:23,350
Ah. Si. >> [Estudiant] Yeah.

444
00:35:23,350 --> 00:35:29,650
Així que ara que hem tirat la que actualment mirat,

445
00:35:29,650 --> 00:35:33,260
el que significa que ara hem de tenir també

446
00:35:33,260 --> 00:35:44,810
if (paller [(baixa + fins) / 2] == agulla), llavors es pot tornar realitat.

447
00:35:44,810 --> 00:35:52,070
I si em poso més o simplement si, significa literalment la mateixa cosa

448
00:35:52,070 --> 00:35:57,110
perquè això hauria tornat realitat.

449
00:35:57,110 --> 00:36:01,450
Així que vaig a posar un altre si, però no importa.

450
00:36:01,450 --> 00:36:10,440
>> Així que si aquesta cosa, en cas contrari això, i això és una cosa comuna que faig

451
00:36:10,440 --> 00:36:14,340
on fins i tot si és el cas en què tot està bé aquí,

452
00:36:14,340 --> 00:36:22,780
com sota no pot ser mai superior a la pota, no és digne de raonament sobre si això és cert.

453
00:36:22,780 --> 00:36:28,010
Així que vostè pot també dir mentre baixa és menor o igual a

454
00:36:28,010 --> 00:36:30,720
o mentre baix és menor que

455
00:36:30,720 --> 00:36:35,300
pel que si és que alguna vegada passa igual o menor a deixar-la passar,

456
00:36:35,300 --> 00:36:40,130
llavors podem sortir d'aquest bucle.

457
00:36:41,410 --> 00:36:44,630
Preguntes, inquietuds, comentaris?

458
00:36:47,080 --> 00:36:49,270
Bé. Això es veu bé.

459
00:36:49,270 --> 00:36:52,230
Ara volem fer una espècie.

460
00:36:52,230 --> 00:37:04,030
Si anem a la meva segona revisió, veiem aquests mateixos nombres,

461
00:37:04,030 --> 00:37:07,550
però ara ja no estan en ordre.

462
00:37:07,550 --> 00:37:12,840
I volem implementar utilitzant qualsevol tipus algoritme en O de n log n.

463
00:37:12,840 --> 00:37:17,240
Llavors, què algorisme creus que hauríem d'aplicar aquí? >> [Estudiant] tipus de mescla.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Yeah. Combinar tipus és O (n log n), així que això és el que farem.

465
00:37:23,810 --> 00:37:26,680
I el problema serà bastant similar,

466
00:37:26,680 --> 00:37:31,920
on es presta fàcilment a una solució recursiva.

467
00:37:31,920 --> 00:37:35,580
També podem arribar a una solució iterativa si volem,

468
00:37:35,580 --> 00:37:42,540
però recursió serà més fàcil aquí i hem de fer recursivitat.

469
00:37:45,120 --> 00:37:49,530
Suposo que tindrem una caminada per tipus de mescla en primer lloc,

470
00:37:49,530 --> 00:37:54,280
encara que hi ha un vídeo preciós sobre tipus de combinació ja. [Rialles]

471
00:37:54,280 --> 00:37:59,780
Així merge sort hi ha - m'estic perdent gran part d'aquest treball.

472
00:37:59,780 --> 00:38:02,080
Oh, només hi ha una esquerra.

473
00:38:02,080 --> 00:38:03,630
Així es fusionen.

474
00:38:08,190 --> 00:38:12,470
Oh, 1, 3, 5.

475
00:38:26,090 --> 00:38:27,440
Bé.

476
00:38:29,910 --> 00:38:33,460
Merge pren dues matrius independents.

477
00:38:33,460 --> 00:38:36,780
Individualment aquestes dues matrius són dos ordenats.

478
00:38:36,780 --> 00:38:40,970
Així aquesta matriu, 1, 3, 5, ordenats. Aquesta matriu, 0, 2, 4, ordenats.

479
00:38:40,970 --> 00:38:46,710
Ara, què combinació ha de fer és combinar en una sola matriu que és al seu torn ordenats.

480
00:38:46,710 --> 00:38:57,130
Per això volem una matriu de mida 6 que tindrà aquests elements dins d'ella

481
00:38:57,130 --> 00:38:59,390
de manera ordenada.

482
00:38:59,390 --> 00:39:03,390
>> I així podem aprofitar el fet que aquests dos conjunts s'ordenen

483
00:39:03,390 --> 00:39:06,800
fer-ho en un temps lineal,

484
00:39:06,800 --> 00:39:13,510
sentit del temps lineal si aquesta matriu és x mida i aquesta és i mida,

485
00:39:13,510 --> 00:39:20,970
llavors l'algorisme total ha de ser O (x + i). Bé.

486
00:39:20,970 --> 00:39:23,150
Així suggeriments.

487
00:39:23,150 --> 00:39:26,030
[Estudiant] Podríem començar per l'esquerra?

488
00:39:26,030 --> 00:39:30,150
Així que vaig a posar el 0 a baix primer i després el 1 i després aquí estàs en el 2.

489
00:39:30,150 --> 00:39:33,320
Així que és com té una fitxa que es mou cap a la dreta. >> [Bowden] Yeah.

490
00:39:33,320 --> 00:39:41,070
Per a tots dos conjunts si només es centren en l'element més a l'esquerra.

491
00:39:41,070 --> 00:39:43,530
Com que tots dos conjunts s'ordenen, se sap que aquests dos elements

492
00:39:43,530 --> 00:39:46,920
són els elements més petits, ja sigui en matriu.

493
00:39:46,920 --> 00:39:53,500
Així que això significa que 1 dels 2 elements han de ser l'element més petit de la nostra gamma combinada.

494
00:39:53,500 --> 00:39:58,190
El que passa és que el més petit és el de la dreta aquest cop.

495
00:39:58,190 --> 00:40:02,580
Així que prenem 0, inserir-lo a l'esquerra, perquè 0 és menor que 1,

496
00:40:02,580 --> 00:40:08,210
així que 0, la inserida en la nostra posició, i després actualitzem aquesta

497
00:40:08,210 --> 00:40:12,070
a centrar ara en el primer element.

498
00:40:12,070 --> 00:40:14,570
I ara ho repetim.

499
00:40:14,570 --> 00:40:20,670
Així que ara comparem 2 i 1. 1 és més petita, així que anem a inserir 1.

500
00:40:20,670 --> 00:40:25,300
Actualitzem aquest punter per apuntar a aquest noi.

501
00:40:25,300 --> 00:40:33,160
Ara hem de fer-ho de nou, així que 2. Açò actualitzarà, comparar aquests 2, 3.

502
00:40:33,160 --> 00:40:37,770
Això actualitza, després 4 i 5.

503
00:40:37,770 --> 00:40:42,110
Així que és de mescla.

504
00:40:42,110 --> 00:40:49,010
>> Ha de ser bastant obvi que és el temps lineal ja que només ha d'anar a través de cada element d'una vegada.

505
00:40:49,010 --> 00:40:55,980
I aquest és el pas més important per a la implementació espècie de barreja està fent això.

506
00:40:55,980 --> 00:40:59,330
I no és tan difícil.

507
00:40:59,330 --> 00:41:15,020
Un parell de coses que preocupar és que anem a dir que ens fusió 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
En aquest cas, acaben en l'escenari en què aquest serà més petit,

509
00:41:30,930 --> 00:41:36,160
després actualitzem aquest punter, aquest serà més petits, actualitzar això,

510
00:41:36,160 --> 00:41:41,280
aquest és més petit, i ara vostè ha de reconèixer

511
00:41:41,280 --> 00:41:44,220
quan realment has quedat sense elements per comparar.

512
00:41:44,220 --> 00:41:49,400
Com que ja hem utilitzat aquest arsenal sencer,

513
00:41:49,400 --> 00:41:55,190
tot aquest conjunt ara s'acaba d'inserir en aquí.

514
00:41:55,190 --> 00:42:02,040
Així que si mai arribes a tenir al punt que un dels nostres arrays està totalment fusionat ja,

515
00:42:02,040 --> 00:42:06,510
llavors simplement prendre tots els elements de l'altra matriu i inserir-los al final de la matriu.

516
00:42:06,510 --> 00:42:13,630
Així que només es pot inserir 4, 5, 6. Bé.

517
00:42:13,630 --> 00:42:18,070
Això és una cosa a tenir en compte.

518
00:42:22,080 --> 00:42:26,120
Implementació que ha de ser el pas 1.

519
00:42:26,120 --> 00:42:32,600
Combinar ordenar després en base a això, és 2 passos, 2 passos ximples.

520
00:42:38,800 --> 00:42:42,090
Anem a donar a aquesta matriu.

521
00:42:57,920 --> 00:43:05,680
Així merge sort, el pas 1 és trencar la matriu recursivament en dues meitats.

522
00:43:05,680 --> 00:43:09,350
Així que dividir aquest conjunt en dues meitats.

523
00:43:09,350 --> 00:43:22,920
Ara tenim 4, 15, 16, 50 i 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
I ara ho fem de nou i ens separem aquests en dues meitats.

525
00:43:25,800 --> 00:43:27,530
Jo només vaig a fer en aquest costat.

526
00:43:27,530 --> 00:43:34,790
Així 4, 15 i 16, 50.

527
00:43:34,790 --> 00:43:37,440
Faríem el mateix aquí.

528
00:43:37,440 --> 00:43:40,340
I ara ho dividim per la meitat una altra vegada.

529
00:43:40,340 --> 00:43:51,080
I tenim 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Així que aquest és el nostre cas base.

531
00:43:53,170 --> 00:44:00,540
Quan les matrius són de grandària 1, llavors s'atura amb la divisió en dues meitats.

532
00:44:00,540 --> 00:44:03,190
>> Ara, què fem amb això?

533
00:44:03,190 --> 00:44:15,730
Acabem això també es divideixen en 8, 23, 42, i 108.

534
00:44:15,730 --> 00:44:24,000
Així que ara que estem en aquest moment, ara pas dos tipus de combinació és simplement la fusió de parells per les llistes.

535
00:44:24,000 --> 00:44:27,610
Així que volem fusionar aquests. Acabem de trucar a fusionar-se.

536
00:44:27,610 --> 00:44:31,410
Sabem fusió tornarà aquests en l'ordre establert.

537
00:44:31,410 --> 00:44:33,920
4, 15.

538
00:44:33,920 --> 00:44:41,440
Ara volem unir aquests, i que tornarà una llista amb els registres en ordre,

539
00:44:41,440 --> 00:44:44,160
16, 50.

540
00:44:44,160 --> 00:44:57,380
Ens fusionem aquells - que no puc escriure - 8, 23 i 42, 108.

541
00:44:57,380 --> 00:45:02,890
Així que tenim parells fusionats vegada.

542
00:45:02,890 --> 00:45:05,140
Ara només ens queda unir de nou.

543
00:45:05,140 --> 00:45:10,130
Tingueu en compte que cadascuna d'aquestes llistes s'ordenen per si mateixa,

544
00:45:10,130 --> 00:45:15,220
i llavors només pot combinar aquestes llistes per obtenir una llista de mida 4, que es classifica

545
00:45:15,220 --> 00:45:19,990
i fusionar aquestes dues llistes per obtenir una llista de mida 4, que està ordenada.

546
00:45:19,990 --> 00:45:25,710
I, finalment, podem fusionar aquests dos llistes de mida 4 per obtenir una llista de mides de 8, que està ordenada.

547
00:45:25,710 --> 00:45:34,030
Així que a veure que això és general n log n, ja vam veure que merge és lineal,

548
00:45:34,030 --> 00:45:40,390
així que quan ens enfrontem a la fusió d'aquests, així com el cost total de fusió

549
00:45:40,390 --> 00:45:43,410
per aquestes dues llistes és a 2 perquè -

550
00:45:43,410 --> 00:45:49,610
O bé, és de S n, n però aquí és només aquests dos elements, de manera que és 2.

551
00:45:49,610 --> 00:45:52,850
I aquests 2 serà 2 i aquests 2 serà 2 i aquests 2 serà 2,

552
00:45:52,850 --> 00:45:58,820
així que a través de totes les fusions que hem de fer, acabem fent núm.

553
00:45:58,820 --> 00:46:03,210
Igual que 2 + 2 + 2 + 2 és 8, que és N,

554
00:46:03,210 --> 00:46:08,060
de manera que el cost de la combinació d'aquest conjunt és n.

555
00:46:08,060 --> 00:46:10,810
I el mateix aquí.

556
00:46:10,810 --> 00:46:16,980
Anem a combinar aquests 2, llavors aquests 2, i de forma individual aquesta fusió es durà a quatre operacions,

557
00:46:16,980 --> 00:46:23,610
aquesta fusió es durà a quatre operacions, però un cop més, entre tots ells,

558
00:46:23,610 --> 00:46:29,030
acabem la fusió n les coses en conjunt, de manera que aquest pas pren núm.

559
00:46:29,030 --> 00:46:33,670
I així, cada nivell té n elements es van fusionar.

560
00:46:33,670 --> 00:46:36,110
>> I Quants nivells hi ha?

561
00:46:36,110 --> 00:46:40,160
A cada nivell, la nostra matriu creix en mida 2.

562
00:46:40,160 --> 00:46:44,590
Aquí les nostres matrius són de grandària 1, aquí són de mida 2, aquí són de grandària 4,

563
00:46:44,590 --> 00:46:46,470
i, finalment, són de mida 8.

564
00:46:46,470 --> 00:46:56,450
Així que ja que es duplica, hi haurà un total de log n d'aquests nivells.

565
00:46:56,450 --> 00:47:02,090
Així que amb log n nivells, cada nivell individual tenint núm total d'operacions,

566
00:47:02,090 --> 00:47:05,720
obtenim un log n n algorisme.

567
00:47:05,720 --> 00:47:07,790
Preguntes?

568
00:47:08,940 --> 00:47:13,320
La gent ja s'ha avançat en la forma d'aplicar això?

569
00:47:13,320 --> 00:47:18,260
Hi ha algú ja en un estat en el qual només pot aixecar el seu codi?

570
00:47:20,320 --> 00:47:22,260
Em pot donar un minut.

571
00:47:24,770 --> 00:47:27,470
Aquest serà més llarga.

572
00:47:27,470 --> 00:47:28,730
Recomano altament recurrents -

573
00:47:28,730 --> 00:47:30,510
No ha de fer recursivitat per fusió

574
00:47:30,510 --> 00:47:33,750
perquè per fer recursivitat per merge, hauràs de passar un munt de diferents mides.

575
00:47:33,750 --> 00:47:37,150
Es pot, però és molest.

576
00:47:37,150 --> 00:47:43,720
Però recursivitat per ordenar en si és bastant fàcil.

577
00:47:43,720 --> 00:47:49,190
Simplement truqui espècie literalment a la meitat esquerra, més o menys a la meitat dreta. Bé.

578
00:47:51,770 --> 00:47:54,860
Algú té alguna cosa que pugui aixecar ja?

579
00:47:54,860 --> 00:47:57,540
O si no vaig a donar un minut.

580
00:47:58,210 --> 00:47:59,900
Bé.

581
00:47:59,900 --> 00:48:02,970
Algú té alguna cosa que puguem treballar?

582
00:48:05,450 --> 00:48:09,680
Del que només haurem de treballar amb això i després expandir des d'allà.

583
00:48:09,680 --> 00:48:14,050
>> Qualsevol persona que tingui més d'això que jo puc aixecar?

584
00:48:14,050 --> 00:48:17,770
[Estudiant] Yeah. Vostè pot aixecar la meva. >> Està bé.

585
00:48:17,770 --> 00:48:19,730
Sí!

586
00:48:22,170 --> 00:48:25,280
[Estudiant] Hi havia un munt de condicions. >> Oh, dispara. Pot vostè -

587
00:48:25,280 --> 00:48:28,110
[Estudiant] He de guardar. Sí >>.

588
00:48:32,420 --> 00:48:35,730
Així ho vam fer fer la fusió per separat.

589
00:48:35,730 --> 00:48:38,570
Oh, però no és tan dolent.

590
00:48:39,790 --> 00:48:41,650
Bé.

591
00:48:41,650 --> 00:48:47,080
Així classe en si és simplement trucar mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Explica'ns què mergeSortHelp fa.

593
00:48:49,530 --> 00:48:55,700
[Estudiant] MergeSortHelp pràcticament fa els dos passos principals:

594
00:48:55,700 --> 00:49:01,270
que és classificar cada mitjà de la matriu i, a continuació per fusionar els dos.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Està bé, dóna'm un segon.

596
00:49:10,850 --> 00:49:13,210
Crec que això - >> [estudiant] Necessito -

597
00:49:17,100 --> 00:49:19,400
Si. M'estic perdent alguna cosa.

598
00:49:19,400 --> 00:49:23,100
En combinació, m'adono que he de crear una nova matriu

599
00:49:23,100 --> 00:49:26,530
perquè jo no podia fer-ho en el seu lloc. Sí >>. No es pot. Corregir.

600
00:49:26,530 --> 00:49:28,170
[Estudiant] Per tant, crear una nova matriu.

601
00:49:28,170 --> 00:49:31,510
Em vaig oblidar al final de fusionar-se per tornar a canviar.

602
00:49:31,510 --> 00:49:34,490
Bé. Necessitem una nova matriu.

603
00:49:34,490 --> 00:49:41,000
En tipus de mescla, això és gairebé sempre cert.

604
00:49:41,000 --> 00:49:44,340
Una part del cost d'un algorisme millor pel que fa a temps

605
00:49:44,340 --> 00:49:47,310
és gairebé sempre la necessitat d'usar la memòria una mica més.

606
00:49:47,310 --> 00:49:51,570
Així que aquí, no importa el que facis merge sort,

607
00:49:51,570 --> 00:49:54,780
que inevitablement hauria d'utilitzar una mica de memòria extra.

608
00:49:54,780 --> 00:49:58,240
Ell o ella va crear una nova matriu.

609
00:49:58,240 --> 00:50:03,400
I després diuen que al final només hem de copiar nova matriu a la matriu original.

610
00:50:03,400 --> 00:50:04,830
[Estudiant] Crec que sí, sí.

611
00:50:04,830 --> 00:50:08,210
No sé si això funciona en termes de comptatge per referència o el que sigui -

612
00:50:08,210 --> 00:50:11,650
Sí, va a treballar. >> [Estudiant] Bé.

613
00:50:20,620 --> 00:50:24,480
Ha intentat executar aquest? >> [Estudiant] No, encara no. >> Okay.

614
00:50:24,480 --> 00:50:28,880
Intenta executar, i després vaig a parlar d'això per un segon.

615
00:50:28,880 --> 00:50:35,200
[Estudiant] Necessito tenir tots els prototips de funcions i tot, però, no?

616
00:50:37,640 --> 00:50:40,840
Els prototips de funció. Oh, et refereixes a - si.

617
00:50:40,840 --> 00:50:43,040
Ordenar diu mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Així que per sort de cridar mergeSortHelp, mergeSortHelp han d'haver estat definit

619
00:50:47,390 --> 00:50:56,370
abans d'ordenar o només tenim el prototip. Només has de copiar i enganxar això.

620
00:50:56,370 --> 00:50:59,490
I de la mateixa manera, mergeSortHelp crida fusió,

621
00:50:59,490 --> 00:51:03,830
però fusió no s'ha definit encara, així que podem deixar saber mergeSortHelp

622
00:51:03,830 --> 00:51:08,700
que això és el que va a fusionar veurà així, i això és tot.

623
00:51:09,950 --> 00:51:15,730
Així mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Tenim un problema aquí on tenim cap cas base.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp és recursiu, de manera que qualsevol funció recursiva

626
00:51:38,110 --> 00:51:42,610
va a necessitar algun tipus de cas base per saber quan parar de forma recursiva es fa dir.

627
00:51:42,610 --> 00:51:45,590
Quin és el nostre cas base estarà aquí? Si.

628
00:51:45,590 --> 00:51:49,110
[Estudiant] Si la mida és 1? >> [Bowden] Sí

629
00:51:49,110 --> 00:51:56,220
Així que, com vam veure allà, ens vam aturar arrays divisió

630
00:51:56,220 --> 00:52:01,850
una vegada que arribem a matrius de mida 1, el que inevitablement s'estan ordenades.

631
00:52:01,850 --> 00:52:09,530
Així que si la mida és igual a 1, sabem que la sèrie ja està ordenat,

632
00:52:09,530 --> 00:52:12,970
de manera que només pot tornar.

633
00:52:12,970 --> 00:52:16,880
>> Tingueu en compte que és nul, de manera que no torna res especial, simplement tornar.

634
00:52:16,880 --> 00:52:19,580
Bé. Així que aquest és el nostre cas base.

635
00:52:19,580 --> 00:52:27,440
Suposo que el nostre cas base també podria ser si ens toca ser la fusió d'una matriu de mida 0,

636
00:52:27,440 --> 00:52:30,030
és probable que desitgi aturar en algun moment,

637
00:52:30,030 --> 00:52:33,610
de manera que només pot dir mida de menys de 2 o menys d'o igual a 1

638
00:52:33,610 --> 00:52:37,150
per tal que això funcionarà per a qualsevol matriu ara.

639
00:52:37,150 --> 00:52:38,870
Bé.

640
00:52:38,870 --> 00:52:42,740
Així que aquest és el nostre cas base.

641
00:52:42,740 --> 00:52:45,950
Ara, vols que ens guiarà a través de fusió?

642
00:52:45,950 --> 00:52:49,140
Què signifiquen tots aquests casos?

643
00:52:49,140 --> 00:52:54,480
Fins aquí, només estem fent la mateixa idea, la -

644
00:52:56,970 --> 00:53:02,470
[Estudiant] Necessito que em passa mida amb totes les trucades mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
He afegit una mida com a principal addicional i no hi és, com la mida / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, mida / 2, mida / 2. >> [Estudiant] Sí, i també en la funció anterior també.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Aquí? >> [Estudiant] Just mida. >> [Bowden] Oh. Mida, la mida? >> [Estudiant] Yeah.

648
00:53:21,320 --> 00:53:23,010
[Bowden] Bé.

649
00:53:23,010 --> 00:53:26,580
Deixa pensar per un segon.

650
00:53:26,580 --> 00:53:28,780
No ens trobem amb un problema?

651
00:53:28,780 --> 00:53:33,690
Sempre estem tractant l'esquerra com a 0. >> [Estudiant] No

652
00:53:33,690 --> 00:53:36,340
Això està malament també. Em sap greu. Ha de ser inici. Si.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Bé. M'agrada més.

654
00:53:39,230 --> 00:53:43,880
I final. Bé.

655
00:53:43,880 --> 00:53:47,200
Així que ara vols que ens guiarà a través de fusió? >> [Estudiant] Bé.

656
00:53:47,200 --> 00:53:52,150
Estic caminant a través d'aquesta nova matriu que he creat.

657
00:53:52,150 --> 00:53:57,420
La seva grandària és la mida de la porció de la matriu que volem ser ordenats

658
00:53:57,420 --> 00:54:03,460
i tractant de trobar l'element que he de posar en l'etapa de nova matriu.

659
00:54:03,460 --> 00:54:10,140
Així que per fer això, primer estic comprovant si la meitat esquerra de la matriu continua tenint elements més,

660
00:54:10,140 --> 00:54:14,260
i si no és així, llavors cal baixar a la condició de cosa, que només diu

661
00:54:14,260 --> 00:54:20,180
bé, ha d'estar en la matriu dreta, i posarem això en l'índex actual de newArray.

662
00:54:20,180 --> 00:54:27,620
>> I a continuació, en cas contrari, estic comprovant si el costat dret de la matriu també és acabat,

663
00:54:27,620 --> 00:54:30,630
en aquest cas només cal posar a l'esquerra.

664
00:54:30,630 --> 00:54:34,180
Això no podria ser en realitat necessari. No estic segur.

665
00:54:34,180 --> 00:54:40,970
Però de tota manera, els altres dos controls que els dos són més petites en l'esquerra o la dreta.

666
00:54:40,970 --> 00:54:49,770
I també en cada cas, estic incrementant qualsevol d'incrementar marcador de posició.

667
00:54:49,770 --> 00:54:52,040
[Bowden] Bé.

668
00:54:52,040 --> 00:54:53,840
Això es veu bé.

669
00:54:53,840 --> 00:54:58,800
Algú té algun comentari o inquietud o preguntes?

670
00:55:00,660 --> 00:55:07,720
Així que els quatre casos que hem de fer les coses en només ser - o sembla que cinc -

671
00:55:07,720 --> 00:55:13,100
però hem de tenir en compte si la matriu de l'esquerra s'ha quedat sense coses que hem d'unir,

672
00:55:13,100 --> 00:55:16,390
si la matriu de la dreta s'ha quedat sense coses que hem de fusionar -

673
00:55:16,390 --> 00:55:18,400
Estic apuntant a res.

674
00:55:18,400 --> 00:55:21,730
Així que si la matriu de l'esquerra s'ha quedat sense coses o la matriu de la dreta s'ha quedat sense coses.

675
00:55:21,730 --> 00:55:24,320
Es tracta de dos casos.

676
00:55:24,320 --> 00:55:30,920
També tenim el cas trivial que la cosa esquerra és menor que el correcte.

677
00:55:30,920 --> 00:55:33,910
Llavors volem triar el esquerre.

678
00:55:33,910 --> 00:55:37,630
Aquests són els casos.

679
00:55:37,630 --> 00:55:40,990
Així que això estava bé, així que això és tot.

680
00:55:40,990 --> 00:55:46,760
Matriu de l'esquerra. És 1, 2, 3. Bé. Així que sí, aquestes són les quatre coses que pot ser que vulgui fer.

681
00:55:50,350 --> 00:55:54,510
I no anem a anar a través d'una solució iterativa.

682
00:55:54,510 --> 00:55:55,980
Jo no recomanaria -

683
00:55:55,980 --> 00:56:03,070
Unir tipus és un exemple d'una funció que és alhora no cua recursiva,

684
00:56:03,070 --> 00:56:07,040
no és fàcil de fer cua recursiva,

685
00:56:07,040 --> 00:56:13,450
però també no és molt fàcil de fer iteratiu.

686
00:56:13,450 --> 00:56:16,910
Això és molt fàcil.

687
00:56:16,910 --> 00:56:19,170
Aquesta implementació del tipus de mescla,

688
00:56:19,170 --> 00:56:22,140
fusionar, no importa el que facis, has de construir combinació.

689
00:56:22,140 --> 00:56:29,170
>> Així fusionar tipus construït al cim de fusió recursiva és només aquestes tres línies.

690
00:56:29,170 --> 00:56:34,700
Iterativament, és més molest i més difícil de pensar.

691
00:56:34,700 --> 00:56:41,860
Però cal notar que no és recursiu cua des mergeSortHelp - quan es diu a si mateixa -

692
00:56:41,860 --> 00:56:46,590
que encara ha de fer les coses després d'aquesta crida recursiva.

693
00:56:46,590 --> 00:56:50,830
Així que aquest marc de pila ha de seguir existint fins i tot després de cridar a això.

694
00:56:50,830 --> 00:56:54,170
I després, quan es diu a això, el marc de pila ha de seguir existint

695
00:56:54,170 --> 00:56:57,780
perquè fins i tot després d'aquesta trucada, encara hem de combinar.

696
00:56:57,780 --> 00:57:01,920
I és trivial per fer aquesta cua recursiva.

697
00:57:04,070 --> 00:57:06,270
Preguntes?

698
00:57:08,300 --> 00:57:09,860
Està bé.

699
00:57:09,860 --> 00:57:13,400
Així que tornant a ordenar - oh, hi ha dues coses que vull mostrar. Bé.

700
00:57:13,400 --> 00:57:17,840
Tornant a la classe, farem això ràpidament.

701
00:57:17,840 --> 00:57:21,030
O cerca. Ordenar? Sort. Si.

702
00:57:21,030 --> 00:57:22,730
Tornant als començaments de l'espècie.

703
00:57:22,730 --> 00:57:29,870
Volem crear un algoritme que ordena la matriu mitjançant qualsevol algoritme

704
00:57:29,870 --> 00:57:33,660
a O de n.

705
00:57:33,660 --> 00:57:40,860
Llavors, com és això possible? Algú té alguna mena de -

706
00:57:40,860 --> 00:57:44,300
Em va donar a entendre abans de -

707
00:57:44,300 --> 00:57:48,300
Si estem a punt de millorar a partir de n log n a O de n,

708
00:57:48,300 --> 00:57:51,450
hem millorat el nostre algoritme quant a temps,

709
00:57:51,450 --> 00:57:55,250
el que significa que haurem de fer per compensar això?

710
00:57:55,250 --> 00:57:59,520
[Estudiant] Space. Sí >>. Estarem usant més espai.

711
00:57:59,520 --> 00:58:04,490
I ni tan sols només més espai, és exponencialment més espai.

712
00:58:04,490 --> 00:58:14,320
Així que crec que aquest tipus d'algorisme és una cosa pseudo polinomi pseudo -

713
00:58:14,320 --> 00:58:18,980
pseudo - No puc recordar. Pseudo alguna cosa.

714
00:58:18,980 --> 00:58:22,210
Però és perquè hem d'utilitzar tant espai

715
00:58:22,210 --> 00:58:28,610
que es pot aconseguir, però no realista.

716
00:58:28,610 --> 00:58:31,220
>> I com s'aconsegueix això?

717
00:58:31,220 --> 00:58:36,810
Podem aconseguir això si et garantim que qualsevol element particular de la matriu

718
00:58:36,810 --> 00:58:39,600
està per sota d'una certa mida.

719
00:58:42,070 --> 00:58:44,500
Així que anem a dir que la mida és de 200,

720
00:58:44,500 --> 00:58:48,130
qualsevol element d'una matriu es troba per sota de la mida 200.

721
00:58:48,130 --> 00:58:51,080
I això és realment molt realista.

722
00:58:51,080 --> 00:58:58,660
Vostè pot fàcilment tenir una matriu que ja saps tot el que conté

723
00:58:58,660 --> 00:59:00,570
serà menor que cert nombre.

724
00:59:00,570 --> 00:59:07,400
Igual que si vostè té algun vector absolutament massiu o alguna cosa

725
00:59:07,400 --> 00:59:11,810
però ja saps que tot estarà entre 0 i 5,

726
00:59:11,810 --> 00:59:14,790
llavors serà molt més ràpida de fer això.

727
00:59:14,790 --> 00:59:17,930
I la envoltant en qualsevol dels elements és 5,

728
00:59:17,930 --> 00:59:21,980
de manera que aquest límit, que és la quantitat de memòria que utilitzarà.

729
00:59:21,980 --> 00:59:26,300
Així que el límit és 200.

730
00:59:26,300 --> 00:59:32,960
En teoria no sempre és un salt des d'un nombre sencer només pot ser de fins a 4 milions de dòlars,

731
00:59:32,960 --> 00:59:40,600
però això és poc realista ja que llavors estaríem utilitzant l'espai

732
00:59:40,600 --> 00:59:44,400
l'ordre de 4 mil milions. Així que això és poc realista.

733
00:59:44,400 --> 00:59:47,060
Però aquí direm que el nostre límit és de 200.

734
00:59:47,060 --> 00:59:59,570
El truc per fer-ho en O de n és que fem una altra matriu anomenada càrrecs de mida OBLIGAT.

735
00:59:59,570 --> 01:00:10,470
Així que en realitat, es tracta d'un accés directe - Jo en realitat no sé si Clang fa això.

736
01:00:11,150 --> 01:00:15,330
Però en GCC com a mínim - Clang estic suposant que també ho fa -

737
01:00:15,330 --> 01:00:18,180
això només inicialitzar la matriu completa per ser 0.

738
01:00:18,180 --> 01:00:25,320
Així que si no vols fer això, llavors jo podria fer per separat for (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <BOUND, i + +) i compta amb [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Així que ara tot s'inicialitza a 0.

741
01:00:35,260 --> 01:00:39,570
Jo iterar sobre la meva matriu,

742
01:00:39,570 --> 01:00:51,920
i el que estic fent és que estic comptant el nombre de cada un - Baixem aquí.

743
01:00:51,920 --> 01:00:55,480
Tenim 4, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
El que estic comptant és el nombre d'ocurrències de cada un d'aquests elements.

745
01:01:00,010 --> 01:01:03,470
Anem a afegir un parell realment més aquí amb algunes repeticions.

746
01:01:03,470 --> 01:01:11,070
Per tant el valor que tenim aquí, el valor que serà matriu [i].

747
01:01:11,070 --> 01:01:14,850
Així val podria ser 4 o 8 o el que sigui.

748
01:01:14,850 --> 01:01:18,870
I ara que estic comptant quants d'aquest valor que he vist,

749
01:01:18,870 --> 01:01:21,230
així recomptes [val] + +;

750
01:01:21,230 --> 01:01:29,430
Un cop fet això, el recompte es veurà alguna cosa com 0001.

751
01:01:29,430 --> 01:01:42,190
Farem recompte de [valor] - SUBJECTE + 1.

752
01:01:42,190 --> 01:01:48,230
>> Ara això és només per explicar el fet que estem començant des de 0.

753
01:01:48,230 --> 01:01:50,850
Així que si 200 serà la nostra major nombre,

754
01:01:50,850 --> 01:01:54,720
llavors 0-200 és de 201 coses.

755
01:01:54,720 --> 01:02:01,540
Així que compte, es veurà com 00001, perquè tenim un 4.

756
01:02:01,540 --> 01:02:10,210
Llavors tindrem 0001 on tindrem un 1 en l'índex de 8 de comptatge.

757
01:02:10,210 --> 01:02:14,560
Tindrem un 2 al índex 23 de la compte.

758
01:02:14,560 --> 01:02:17,630
Tindrem un 2 al índex 42 del recompte.

759
01:02:17,630 --> 01:02:21,670
Així que podem utilitzar el compte.

760
01:02:34,270 --> 01:02:44,920
Així num_of_item = compte [i].

761
01:02:44,920 --> 01:02:52,540
I si és així num_of_item és 2, significa que desitja inserir 2 de la sèrie i

762
01:02:52,540 --> 01:02:55,290
en la nostra matriu ordenada.

763
01:02:55,290 --> 01:03:02,000
Així que hem de fer un seguiment del lluny que estem en la matriu.

764
01:03:02,000 --> 01:03:05,470
So = índex 0.

765
01:03:05,470 --> 01:03:09,910
Array - Vaig a escriure.

766
01:03:16,660 --> 01:03:18,020
Comptes -

767
01:03:19,990 --> 01:03:28,580
array [índex + +] = i;

768
01:03:28,580 --> 01:03:32,490
És això el que vols? Crec que això és el que vull.

769
01:03:35,100 --> 01:03:38,290
Sí, això es veu bé. Bé.

770
01:03:38,290 --> 01:03:43,050
Llavors, tothom entén el que el propòsit del meu compte és la matriu?

771
01:03:43,050 --> 01:03:48,140
S'explica el nombre d'ocurrències de cada un d'aquests nombres.

772
01:03:48,140 --> 01:03:51,780
Llavors estic iterar sobre aquesta matriu compte,

773
01:03:51,780 --> 01:03:57,190
i la posició i-èsima de la matriu dels recomptes

774
01:03:57,190 --> 01:04:01,930
és el nombre d'i és que hauria d'aparèixer en la meva matriu ordenada.

775
01:04:01,930 --> 01:04:06,840
És per això que els recomptes de 4 serà un

776
01:04:06,840 --> 01:04:11,840
i els recomptes de 8 serà 1, els recomptes de 23 serà 2.

777
01:04:11,840 --> 01:04:16,900
Així és com molts dels que voleu inserir en el meu matriu ordenada.

778
01:04:16,900 --> 01:04:19,200
Llavors m'acaba de fer això.

779
01:04:19,200 --> 01:04:28,960
Estic inserint num_of_item is en la meva matriu ordenada.

780
01:04:28,960 --> 01:04:31,670
>> Preguntes?

781
01:04:32,460 --> 01:04:43,100
I així, un cop més, aquest és el temps lineal, ja que estem només iterar sobre un cop i

782
01:04:43,100 --> 01:04:47,470
però també és lineal en el que aquest nombre passa a ser,

783
01:04:47,470 --> 01:04:50,730
pel que en gran mesura depèn del que el seu límit és.

784
01:04:50,730 --> 01:04:53,290
D'un salt de 200, que no és tan dolent.

785
01:04:53,290 --> 01:04:58,330
Si el límit serà 10.000, llavors això és una mica pitjor,

786
01:04:58,330 --> 01:05:01,360
però si el seu límit serà de 4 milions de dòlars, que és completament irreal

787
01:05:01,360 --> 01:05:07,720
i aquest acord es va a haver de ser de mida 4 mil milions, la qual cosa és poc realista.

788
01:05:07,720 --> 01:05:10,860
Així que això és tot. Preguntes?

789
01:05:10,860 --> 01:05:13,270
[Resposta dels estudiants inaudible] >> Okay.

790
01:05:13,270 --> 01:05:15,710
Em vaig adonar de res més quan estàvem passant.

791
01:05:17,980 --> 01:05:23,720
Crec que el problema estava en Lucas, i probablement cada un que hem vist.

792
01:05:23,720 --> 01:05:26,330
Em vaig oblidar del tot.

793
01:05:26,330 --> 01:05:31,040
L'únic que volia comentar és que quan vostè està tractant amb coses com índexs,

794
01:05:31,040 --> 01:05:38,320
vostè mai realment veure això quan vostè està escrivint un bucle for,

795
01:05:38,320 --> 01:05:41,120
però tècnicament, quan vostè està tractant amb aquests índexs,

796
01:05:41,120 --> 01:05:45,950
vostè ha gairebé sempre tracten amb nombres enters sense signe.

797
01:05:45,950 --> 01:05:53,850
La raó d'això és quan vostè està tractant amb enters amb signe,

798
01:05:53,850 --> 01:05:56,090
així que si vostè té 2 sencers amb signe i sumar-los

799
01:05:56,090 --> 01:06:00,640
i acaben massa gran, llavors vostè acaba amb un nombre negatiu.

800
01:06:00,640 --> 01:06:03,410
Així que això és el que és de desbordament de sencers.

801
01:06:03,410 --> 01:06:10,500
>> Si afegeixo 2000000000 i 1 mil milions, terme amb negatiu 1 mil milions.

802
01:06:10,500 --> 01:06:15,480
Així és com funciona en equips sencers.

803
01:06:15,480 --> 01:06:17,510
Així que el problema amb l'ús -

804
01:06:17,510 --> 01:06:23,500
Això està bé, excepte si baixa passa a ser de fins a 2 mil milions i passa a ser d'1 mil milions,

805
01:06:23,500 --> 01:06:27,120
llavors això serà negatiu 1000000000 i després anem a dividir això per 2

806
01:06:27,120 --> 01:06:29,730
i acabar amb negatiu 500 milions.

807
01:06:29,730 --> 01:06:33,760
Així que això és només un problema si li passa que es busca a través d'una matriu

808
01:06:33,760 --> 01:06:38,070
de milers de milions de coses.

809
01:06:38,070 --> 01:06:44,050
Però si baixa + fins que passa el desbordament, llavors això és un problema.

810
01:06:44,050 --> 01:06:47,750
Així que els fem sense signar, a continuació, 2 milions més de mil milions és de 3 milions de dòlars.

811
01:06:47,750 --> 01:06:51,960
3000000000 dividit per 2 és de 1,5 milions de dòlars.

812
01:06:51,960 --> 01:06:55,670
Així que tan aviat com estiguin sense signar, tot és perfecte.

813
01:06:55,670 --> 01:06:59,900
I això és també un problema quan vostè està escrivint el seu bucles for,

814
01:06:59,900 --> 01:07:03,940
i, de fet, és probable que ho faci de forma automàtica.

815
01:07:09,130 --> 01:07:12,330
En realitat, s'acaba de cridar a tu.

816
01:07:12,330 --> 01:07:21,610
Així que si aquest nombre és massa gran per ser just en un enter però cabria en un enter sense signe,

817
01:07:21,610 --> 01:07:24,970
va a cridar a tu, així que per això mai et arribes a tenir el problema.

818
01:07:29,150 --> 01:07:34,820
Es pot veure que l'índex mai serà negatiu,

819
01:07:34,820 --> 01:07:39,220
així que quan vostè està interactuant sobre una matriu,

820
01:07:39,220 --> 01:07:43,970
gairebé sempre es pot dir unsigned int i, però que en realitat no ha de fer-ho.

821
01:07:43,970 --> 01:07:47,110
Les coses van a funcionar més o menys igual de bé.

822
01:07:48,740 --> 01:07:50,090
Bé. [Xiuxiueja] Quina hora és?

823
01:07:50,090 --> 01:07:54,020
L'últim que volia mostrar - i jo només vaig a fer-ho molt ràpid.

824
01:07:54,020 --> 01:08:03,190
Saps com hem # defineix pel que pot definir # MAX com 5 o alguna cosa així?

825
01:08:03,190 --> 01:08:05,940
No fem MAX. # Defineix OBLIGAT 200. Això és el que vam fer abans.

826
01:08:05,940 --> 01:08:10,380
Això defineix una constant, que només serà copiat i enganxat

827
01:08:10,380 --> 01:08:13,010
on ens ha tocat escriure OBLIGAT.

828
01:08:13,010 --> 01:08:18,189
>> Així que en realitat pot fer més amb # defineix.

829
01:08:18,189 --> 01:08:21,170
Hem # pot definir funcions.

830
01:08:21,170 --> 01:08:23,410
No són realment funcions, però anomenarem funcions.

831
01:08:23,410 --> 01:08:36,000
Un exemple podria ser alguna cosa com MAX (x, i) es defineix com (x <i i:? X). Bé.

832
01:08:36,000 --> 01:08:40,660
Pel que s'ha d'acostumar a la sintaxi de l'operador ternari,

833
01:08:40,660 --> 01:08:49,029
però és x menor que i? Torneu a, o torni x.

834
01:08:49,029 --> 01:08:54,390
Així es pot veure que pot fer aquesta funció, per separat,

835
01:08:54,390 --> 01:09:01,399
i la funció podria ser com bool MAX té 2 arguments, torni aquest.

836
01:09:01,399 --> 01:09:08,340
Aquesta és una de les més comuns que veig fet així. Els anomenem macros.

837
01:09:08,340 --> 01:09:11,790
Aquesta és una macro.

838
01:09:11,790 --> 01:09:15,859
Això és només la sintaxi per a això.

839
01:09:15,859 --> 01:09:18,740
Vostè pot escriure una macro per fer el que vulguis.

840
01:09:18,740 --> 01:09:22,649
Es veuen amb freqüència per depurar macros printfs i aquestes coses.

841
01:09:22,649 --> 01:09:29,410
Així que un tipus de printf, hi ha constants especials al carrer com subratllen LÍNIA subratllat,

842
01:09:29,410 --> 01:09:31,710
2 subratlla LÍNIA subratllat,

843
01:09:31,710 --> 01:09:37,550
i també cal pensar dos guions FUNC. Això podria ser. Una cosa per l'estil.

844
01:09:37,550 --> 01:09:40,880
Aquestes coses es reemplaçarà amb el nom de la funció

845
01:09:40,880 --> 01:09:42,930
o el nombre de la línia que et trobis.

846
01:09:42,930 --> 01:09:48,630
Sovint, s'escriu printfs depuració que aquí em podria simplement escriure

847
01:09:48,630 --> 01:09:54,260
DEBUG i s'imprimirà el nombre de línia i la funció que em toca estar en

848
01:09:54,260 --> 01:09:57,020
que va trobar que la declaració DEBUG.

849
01:09:57,020 --> 01:09:59,550
I també es pot imprimir altres coses.

850
01:09:59,550 --> 01:10:05,990
Així que una cosa que has de tenir en compte és si se m'acut per definir # DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
alguna cosa així com 2 * i 2 * i x.

852
01:10:11,380 --> 01:10:14,310
Així que per raó, li toca fer molt d'això.

853
01:10:14,310 --> 01:10:16,650
Així que el converteixen en un macro.

854
01:10:16,650 --> 01:10:18,680
Això és realment trencat.

855
01:10:18,680 --> 01:10:23,050
Jo diria que és per fer alguna cosa com DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Llavors, quin ha de ser retornat?

857
01:10:28,840 --> 01:10:30,580
[Estudiant] 12.

858
01:10:30,580 --> 01:10:34,800
Sí, 12 han de ser retornats, i 12 es torna.

859
01:10:34,800 --> 01:10:43,350
3 és reemplaçat per x, 6 és reemplaçat per i, i tornem 2 * 6, que té 12 anys.

860
01:10:43,350 --> 01:10:47,710
Ara, què passa amb això? Quin ha de ser retornat?

861
01:10:47,710 --> 01:10:50,330
[Estudiant] 14. >> Idealment, 14.

862
01:10:50,330 --> 01:10:55,290
La qüestió és que la forma de hash defineix el treball, recordi que és una còpia literal i enganxar

863
01:10:55,290 --> 01:11:00,160
de gairebé tot, així que el que això serà interpretada com

864
01:11:00,160 --> 01:11:11,270
és 3 menys que 1 més 6, 2 vegades 1 més 6, 2 vegades 3.

865
01:11:11,270 --> 01:11:19,780
>> Així, per aquesta raó per la qual gairebé sempre envolten tot entre parèntesis.

866
01:11:22,180 --> 01:11:25,050
Qualsevol variable que gairebé sempre envolten a parèntesi.

867
01:11:25,050 --> 01:11:29,570
Hi ha casos en què no han de, com jo sé que no és necessari fer-ho aquí

868
01:11:29,570 --> 01:11:32,110
perquè menys és gairebé sempre només es treballarà,

869
01:11:32,110 --> 01:11:34,330
tot i que ni tan sols podria ser cert.

870
01:11:34,330 --> 01:11:41,870
Si hi ha alguna cosa ridícul com DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
llavors això quedarà substituït per 3 menys 1 és igual a igual a 2,

872
01:11:49,760 --> 01:11:53,460
i pel que també farà 3 menys que 1, és igual que 2,

873
01:11:53,460 --> 01:11:55,620
que no és el que volem.

874
01:11:55,620 --> 01:12:00,730
Així que per evitar qualsevol problema de prioritat d'operador,

875
01:12:00,730 --> 01:12:02,870
emboliqui sempre entre parèntesi.

876
01:12:03,290 --> 01:12:07,700
Bé. I això és tot, 5:30.

877
01:12:08,140 --> 01:12:12,470
Si vostè té alguna pregunta sobre el conjunt de processadors, contacteu amb nosaltres.

878
01:12:12,470 --> 01:12:18,010
Ha de ser divertit, i l'edició pirata informàtic també és molt més realista

879
01:12:18,010 --> 01:12:22,980
que l'edició pirata de la de l'any passat, així que esperem que molts de vostès ho intenti.

880
01:12:22,980 --> 01:12:26,460
L'any passat va ser molt aclaparador.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]