1
00:00:00,000 --> 00:00:03,332
>> [RIPRODUZIONE DI BRANI MUSICALI]

2
00:00:03,332 --> 00:00:06,490
>> ANDI PENG: Benvenuti a settimana 3 della sezione.

3
00:00:06,490 --> 00:00:09,550
Grazie, ragazzi, per tutti provenienti
per questo ora di inizio prima di oggi.

4
00:00:09,550 --> 00:00:11,466
Abbiamo una bella, piccolo
intimo gruppo di oggi.

5
00:00:11,466 --> 00:00:14,570
Quindi speriamo ci arriveremo
finitura, forse, presto,

6
00:00:14,570 --> 00:00:15,780
un po 'presto oggi.

7
00:00:15,780 --> 00:00:22,057
Così in fretta, solo alcuni
annunci per l'ordine del giorno di oggi.

8
00:00:22,057 --> 00:00:23,890
Prima di iniziare, siamo
intenzione di andare poco più

9
00:00:23,890 --> 00:00:28,910
alcune brevi problemi logistici, pset
domande, debriefing, cose del genere.

10
00:00:28,910 --> 00:00:30,250
E poi ci immergeremo in pieno.

11
00:00:30,250 --> 00:00:34,710
Useremo un debugger GDB chiamato a
iniziare a sfatare il nostro codice, che David

12
00:00:34,710 --> 00:00:36,550
ha spiegato in conferenza, l'altro giorno.

13
00:00:36,550 --> 00:00:39,420
Andremo oltre i quattro tipi di sorta.

14
00:00:39,420 --> 00:00:42,310
Andremo su di loro abbastanza rapidamente
dato che sono piuttosto intenso.

15
00:00:42,310 --> 00:00:45,710
Ma sapere che tutte le diapositive e
il codice sorgente è sempre on-line.

16
00:00:45,710 --> 00:00:50,810
Quindi sentitevi liberi, a vostro esame, a
tornare indietro e dare un'occhiata a questo.

17
00:00:50,810 --> 00:00:53,930
>> Andremo attraverso
Notazione asintotica, che

18
00:00:53,930 --> 00:00:55,944
è solo un modo elegante
di dire "runtime"

19
00:00:55,944 --> 00:00:58,360
dove abbiamo la grande O, che
David ha spiegato in conferenza.

20
00:00:58,360 --> 00:01:01,550
E abbiamo anche Omega, che
è il runtime limite inferiore.

21
00:01:01,550 --> 00:01:06,450
E parleremo un po 'di più
in profondità per quanto riguarda come quelli di lavoro.

22
00:01:06,450 --> 00:01:10,160
E, infine, supereremo ricerca binaria,
perché un sacco di voi che hanno già

23
00:01:10,160 --> 00:01:15,190
guardò i tuoi pset sapere che probabilmente
questa è una domanda che è nel vostro pset.

24
00:01:15,190 --> 00:01:17,470
Così sarete tutti contenti
che copriamo questo oggi.

25
00:01:17,470 --> 00:01:20,610
>> E, infine, secondo la vostra
sezione di feedback, in realtà ho

26
00:01:20,610 --> 00:01:23,000
lasciato circa 15 minuti a
Alla fine di andare poco più

27
00:01:23,000 --> 00:01:27,730
logistica di pset3, tutte le domande,
forse un po 'di guida, se si vuole,

28
00:01:27,730 --> 00:01:28,990
prima di iniziare la programmazione.

29
00:01:28,990 --> 00:01:30,890
Quindi cerchiamo di ottenere attraverso
il materiale abbastanza rapidamente.

30
00:01:30,890 --> 00:01:33,880
E poi possiamo passare un po 'di tempo
prendere più domande per il pset.

31
00:01:33,880 --> 00:01:35,230
OK.

32
00:01:35,230 --> 00:01:39,570
>> Rapidamente, in modo solo alcuni
annunci prima di iniziare oggi.

33
00:01:39,570 --> 00:01:45,410
In primo luogo, non esitare a fare
attraverso due delle vostre pset.

34
00:01:45,410 --> 00:01:49,432
Ho preso uno sguardo al your-- sì, LET'S
ottenere un applauso per quello.

35
00:01:49,432 --> 00:01:51,140
In realtà, ero davvero,
veramente colpito.

36
00:01:51,140 --> 00:01:55,800
Ho classificato il primo pset per voi ragazzi
la scorsa settimana e voi ragazzi hanno fatto incredibile.

37
00:01:55,800 --> 00:01:58,290
>> Stile era sul punto
oltre un paio di osservazioni.

38
00:01:58,290 --> 00:02:00,660
Assicurati di essere sempre
commentando il codice.

39
00:02:00,660 --> 00:02:03,040
Ma i tuoi pset erano sul punto.

40
00:02:03,040 --> 00:02:05,549
E continuate così.

41
00:02:05,549 --> 00:02:08,090
Ed è un bene per il selezionatore a
vedere che voi ragazzi stanno mettendo

42
00:02:08,090 --> 00:02:10,704
in tanto sforzo nel tuo stile
ed il vostro disegno nel codice

43
00:02:10,704 --> 00:02:12,120
che vorremmo per voi a vedere.

44
00:02:12,120 --> 00:02:16,450
Così sto passando lungo la mia gratitudine
per il resto dei TA.

45
00:02:16,450 --> 00:02:19,210
>> Tuttavia esistono
alcune domande debriefing

46
00:02:19,210 --> 00:02:22,010
Voglio solo andare oltre che
renderebbe la mia vita sia

47
00:02:22,010 --> 00:02:24,900
e un sacco di altra
TA 'vive un po' più facile.

48
00:02:24,900 --> 00:02:28,220
In primo luogo, ho notato questo
passato week-- quanti di voi

49
00:02:28,220 --> 00:02:32,301
sono stati in esecuzione su check50
il codice prima di inviare?

50
00:02:32,301 --> 00:02:32,800
OK.

51
00:02:32,800 --> 00:02:36,690
Quindi tutti dovrebbero fare check50,
perchè-- un secret-- abbiamo effettivamente

52
00:02:36,690 --> 00:02:41,540
eseguire check50 come parte della nostra correttezza
script per testare il codice.

53
00:02:41,540 --> 00:02:45,480
Così, se il codice non riesce
check50, con ogni probabilità,

54
00:02:45,480 --> 00:02:47,570
sta probabilmente andando a
fallire il nostro check pure.

55
00:02:47,570 --> 00:02:49,320
A volte voi ragazzi
avere le risposte giuste.

56
00:02:49,320 --> 00:02:52,200
Come, in avida, alcuni dei
si hanno i numeri giusti,

57
00:02:52,200 --> 00:02:53,960
basta stampare alcune cose in più.

58
00:02:53,960 --> 00:02:55,940
E quella roba in più
in realtà non supera il controllo,

59
00:02:55,940 --> 00:02:58,440
perché il computer non
davvero sapere cosa sta cercando.

60
00:02:58,440 --> 00:03:00,981
E così sarà solo scorrere,
vedere che l'output non lo fa

61
00:03:00,981 --> 00:03:03,810
abbiniamo quello che ci aspettiamo la risposta
di essere, e segnare è sbagliato.

62
00:03:03,810 --> 00:03:06,560
>> E so che è successo in
alcuni dei vostri casi questa settimana.

63
00:03:06,560 --> 00:03:09,870
Così sono andato indietro e manualmente
declassato il codice di tutti.

64
00:03:09,870 --> 00:03:12,780
In futuro, però,
per favore, assicurati

65
00:03:12,780 --> 00:03:14,570
che si sta eseguendo
controlla 50 sul vostro codice.

66
00:03:14,570 --> 00:03:17,970
Perché è una specie di dolore per la TA
di dover tornare indietro e manualmente declassamento

67
00:03:17,970 --> 00:03:21,197
ogni singolo pset per ogni
singolo, istanza poco perso.

68
00:03:21,197 --> 00:03:22,530
Quindi non ho preso fuori qualsiasi punti.

69
00:03:22,530 --> 00:03:25,210
Penso che mi sono tolto forse
uno o due per la progettazione.

70
00:03:25,210 --> 00:03:27,710
In futuro, però, se
siete in mancanza check50,

71
00:03:27,710 --> 00:03:31,330
saranno presi punti
off per correttezza.

72
00:03:31,330 --> 00:03:35,020
>> Inoltre, sono pset
dovuto venerdì a mezzogiorno.

73
00:03:35,020 --> 00:03:38,990
Penso che ci sia un sette minuti
periodo di grazia tardi che vi diamo.

74
00:03:38,990 --> 00:03:42,434
Per il tempo di Harvard, avere il permesso di
sette minuti di ritardo a tutto.

75
00:03:42,434 --> 00:03:44,350
Così qui a Yale, faremo
aderire a quello.

76
00:03:44,350 --> 00:03:47,910
Ma più o meno, a 00:07,
se il vostro pset non è in,

77
00:03:47,910 --> 00:03:49,720
che sta per essere contrassegnato come ritardo.

78
00:03:49,720 --> 00:03:53,160
E così mentre è segnato
più tardi, il TA-- io sono

79
00:03:53,160 --> 00:03:54,870
ancora in corso di essere la classificazione vostri pset.

80
00:03:54,870 --> 00:03:56,760
Così ci si può comunque vedere apparire un grado.

81
00:03:56,760 --> 00:03:58,820
Tuttavia, so che a
la fine del semestre,

82
00:03:58,820 --> 00:04:02,270
tutti i pset fine saranno solo
azzerato automaticamente dal computer.

83
00:04:02,270 --> 00:04:04,490
>> Facciamo questo per due ragioni.

84
00:04:04,490 --> 00:04:09,220
Uno, a volte otteniamo
scusato, come le scuse di Dean,

85
00:04:09,220 --> 00:04:10,762
più tardi che io non so ancora.

86
00:04:10,762 --> 00:04:13,761
Così ci piace per assicurarsi che stiamo classificazione
tutto solo nel caso in cui, come, io sono

87
00:04:13,761 --> 00:04:15,080
manca la scusa di un decano.

88
00:04:15,080 --> 00:04:17,000
E in secondo luogo, di tenere
mente, è ancora possibile

89
00:04:17,000 --> 00:04:19,370
escludere un pset che
ha punti di ambito completi.

90
00:04:19,370 --> 00:04:21,430
E così ci piace grado
tutti i pset solo

91
00:04:21,430 --> 00:04:24,730
fare in modo che l'ambito di
lì e li sta cercando.

92
00:04:24,730 --> 00:04:29,150
Quindi, anche se è tardi, ci si può comunque
ottenere credito per i punti di ambito, penso.

93
00:04:29,150 --> 00:04:33,730
>> Quindi morale della storia è, fare
che i pset sono in tempo.

94
00:04:33,730 --> 00:04:38,350
E se non sono in su-tempo,
sanno che non è grande.

95
00:04:38,350 --> 00:04:41,678
Sì, prima di passare, qualcuno ha
Per qualsiasi domanda riguardante il feedback pset?

96
00:04:41,678 --> 00:04:42,178
Già.

97
00:04:42,178 --> 00:04:43,630
>> PUBBLICO: Hai detto che
può cadere uno dei pset?

98
00:04:43,630 --> 00:04:44,296
>> ANDI PENG: Sì.

99
00:04:44,296 --> 00:04:47,050
Quindi c'è nove pset globale
nel corso del semestre.

100
00:04:47,050 --> 00:04:50,610
E se avete portata
points-- così ambito è solo,

101
00:04:50,610 --> 00:04:53,567
più o meno, stai tentando il
problema, stai mettendo nel tempo,

102
00:04:53,567 --> 00:04:56,150
stai mostrando che hai
dimostrato di aver letto le specifiche.

103
00:04:56,150 --> 00:04:57,191
Che è praticamente portata.

104
00:04:57,191 --> 00:04:59,370
E se si sta adempiendo
punti di ambito, abbiamo

105
00:04:59,370 --> 00:05:03,360
può cadere il più basso
uno su pieno scopo.

106
00:05:03,360 --> 00:05:06,790
Ecco, questo è in vostro vantaggio per
completare e provare ogni pset.

107
00:05:06,790 --> 00:05:10,320
>> Anche se nessuno dei upload--
loro lavoro, li caricare.

108
00:05:10,320 --> 00:05:13,711
E poi ci si spera in grado di
darvi alcuni di questi punti indietro.

109
00:05:13,711 --> 00:05:14,210
Cool.

110
00:05:14,210 --> 00:05:16,780
Altre domande?

111
00:05:16,780 --> 00:05:17,840
Grande.

112
00:05:17,840 --> 00:05:21,960
>> In secondo luogo, ufficio hours-- alcuni
note rapide circa l'orario di ufficio.

113
00:05:21,960 --> 00:05:24,300
Quindi, prima, arrivato all'inizio della settimana.

114
00:05:24,300 --> 00:05:26,909
Nessuno è mai al
orario di ufficio il lunedì.

115
00:05:26,909 --> 00:05:28,700
Christabel è venuto a
orario di ufficio la notte scorsa.

116
00:05:28,700 --> 00:05:29,691
Sì, Christabel.

117
00:05:29,691 --> 00:05:32,190
E quello che abbiamo dovuto presso l'ufficio
ore la scorsa notte, Christabel?

118
00:05:32,190 --> 00:05:33,020
>> PUBBLICO: Abbiamo avuto il gelato.

119
00:05:33,020 --> 00:05:36,160
>> ANDI PENG: Così che è di destra, abbiamo avuto
gelato al orario di ufficio la scorsa notte.

120
00:05:36,160 --> 00:05:39,390
Mentre non posso promettere che
avremo gelato a orario d'ufficio

121
00:05:39,390 --> 00:05:43,230
ogni settimana, quello che posso promettere
è che ci sarà un significativo

122
00:05:43,230 --> 00:05:45,380
meglio studente al rapporto TA.

123
00:05:45,380 --> 00:05:47,650
Come legit, è come 00:57.

124
00:05:47,650 --> 00:05:50,350
Considerando che, per contrasto che con
Giovedi, hai circa 150

125
00:05:50,350 --> 00:05:52,830
davvero sottolineato i bambini e non gelato.

126
00:05:52,830 --> 00:05:55,360
E non è solo produttivo per chiunque.

127
00:05:55,360 --> 00:05:58,730
Quindi morale della storia è, venire presto
per l'orario di ufficio e le cose buone

128
00:05:58,730 --> 00:06:00,310
accadrà.

129
00:06:00,310 --> 00:06:02,110
>> Inoltre, vengono preparati a fare domande.

130
00:06:02,110 --> 00:06:03,200
Sai?

131
00:06:03,200 --> 00:06:05,420
Indipendentemente da ciò che le agenzie di viaggi, io
pensare, sono state dicendo,

132
00:06:05,420 --> 00:06:10,710
siamo stati sempre un paio di studenti
che vengono in il Giovedi a, come, 10:50

133
00:06:10,710 --> 00:06:15,100
Non avendo letto le specifiche
essendo come me aiutare, aiutami.

134
00:06:15,100 --> 00:06:18,200
Sfortunatamente a quel punto, c'è
non molto che possiamo fare per aiutarvi.

135
00:06:18,200 --> 00:06:19,590
Quindi, ti aspettiamo presto nella settimana.

136
00:06:19,590 --> 00:06:22,040
Venite presto a orari di ufficio.

137
00:06:22,040 --> 00:06:23,350
Siate preparati a fare domande.

138
00:06:23,350 --> 00:06:25,310
Assicurarsi che si, come
uno studente, sono dove

139
00:06:25,310 --> 00:06:27,620
è necessario essere in modo che il
TA in grado di guidarvi lungo,

140
00:06:27,620 --> 00:06:32,850
Che è ciò che l'orario d'ufficio
dovrebbe essere assegnato per.

141
00:06:32,850 --> 00:06:37,380
>> In secondo luogo, quindi so professori
vuole sorprenderci con i test.

142
00:06:37,380 --> 00:06:39,439
Avevo un professore di quelli
come, yo, tra l'altro,

143
00:06:39,439 --> 00:06:41,230
ricordare che midterm
avete Lunedi prossimo.

144
00:06:41,230 --> 00:06:42,855
Sì, io non conoscevo quella di medio termine.

145
00:06:42,855 --> 00:06:45,630
Quindi ho intenzione di essere che TA
che si ricorda tutto quello quiz

146
00:06:45,630 --> 00:06:47,270
0-- perché, si sa, siamo CS.

147
00:06:47,270 --> 00:06:50,730
Ora che abbiamo gli array fatto, si ottiene
perché è quiz 0, non quiz 1, eh?

148
00:06:50,730 --> 00:06:51,320
OK.

149
00:06:51,320 --> 00:06:52,490
Oh, ho avuto qualche risatina su quello.

150
00:06:52,490 --> 00:06:53,120
OK.

151
00:06:53,120 --> 00:06:59,710
>> Così quiz 0 sarà del 14 ottobre se
sei nella sezione Lunedi-Mercoledì

152
00:06:59,710 --> 00:07:02,920
e il 15 ottobre, se siete in
la sezione Martedì-Giovedi.

153
00:07:02,920 --> 00:07:05,630
Ciò non vale per
quelli di voi a Harvard

154
00:07:05,630 --> 00:07:10,350
who-- Penso che sarete tutti
prendere i vostri quiz il 14.

155
00:07:10,350 --> 00:07:13,560
>> Quindi sì, la prossima settimana, se
David, in conferenza, va,

156
00:07:13,560 --> 00:07:15,747
sì, così a tale proposito
quiz la prossima settimana, a tutti voi

157
00:07:15,747 --> 00:07:17,580
non sarà scioccato perché
siete venuti alla sezione

158
00:07:17,580 --> 00:07:19,664
e sapete che il vostro
quiz 0 è in due settimane.

159
00:07:19,664 --> 00:07:21,580
E avremo recensione
sessioni e tutto.

160
00:07:21,580 --> 00:07:26,360
Quindi nessuna preoccupazione circa
essere spaventato per quello.

161
00:07:26,360 --> 00:07:29,890
Tutte le domande before-- tutte le domande
a tutti i problemi logistici per quanto riguarda,

162
00:07:29,890 --> 00:07:32,591
di classificazione, le ore d'ufficio, sezioni?

163
00:07:32,591 --> 00:07:33,090
Già.

164
00:07:33,090 --> 00:07:35,100
>> AUDIENCE: Così il quiz è
sta per essere durante la lezione?

165
00:07:35,100 --> 00:07:35,766
>> ANDI PENG: Sì.

166
00:07:35,766 --> 00:07:39,460
Così il quiz, credo, è 60
minuti assegnati in quella fascia oraria

167
00:07:39,460 --> 00:07:42,240
che ti basta prendere
in aula.

168
00:07:42,240 --> 00:07:44,810
Quindi non c'è bisogno di venire a
su, come, un caso 07:00.

169
00:07:44,810 --> 00:07:46,140
Va tutto bene.

170
00:07:46,140 --> 00:07:47,100
Già.

171
00:07:47,100 --> 00:07:50,060
Cool.

172
00:07:50,060 --> 00:07:50,840
>> Tutto ok.

173
00:07:50,840 --> 00:07:54,330
Quindi stiamo andando a
introdurre un concetto a voi

174
00:07:54,330 --> 00:08:00,760
questa settimana che David ha già tipo
di toccato in conferenza la scorsa settimana.

175
00:08:00,760 --> 00:08:02,010
Si chiama GDB.

176
00:08:02,010 --> 00:08:05,570
E quanti di voi, mentre in
il corso di scrivere i pset,

177
00:08:05,570 --> 00:08:09,981
hanno notato un grande pulsante che dice
"Debug" sulla parte superiore del vostro IDE?

178
00:08:09,981 --> 00:08:10,480
OK.

179
00:08:10,480 --> 00:08:13,770
Così ora ci realmente arrivare a dissotterrare
il mistero di ciò che realmente pulsante

180
00:08:13,770 --> 00:08:14,270
fa.

181
00:08:14,270 --> 00:08:16,790
E vi garantisco, è un
bella, bella cosa.

182
00:08:16,790 --> 00:08:20,740
>> Quindi, fino ad ora, penso
c'è stato due cose

183
00:08:20,740 --> 00:08:23,320
gli studenti sono stati in genere
fare durante il debug pset.

184
00:08:23,320 --> 00:08:27,635
Uno, o aggiungere a
printf () - così ogni poche righe,

185
00:08:27,635 --> 00:08:29,760
aggiungono in un printf () -
oh, che cosa è questa variabile?

186
00:08:29,760 --> 00:08:32,551
Oh, che cosa è questa variabile now--
e tipo di vedere la progressione

187
00:08:32,551 --> 00:08:33,940
del codice durante l'esecuzione.

188
00:08:33,940 --> 00:08:37,030
O il secondo metodo bambini fanno è
che hanno appena scrivono il tutto

189
00:08:37,030 --> 00:08:38,610
e poi andare così alla fine.

190
00:08:38,610 --> 00:08:39,970
Speriamo che funziona.

191
00:08:39,970 --> 00:08:44,851
Ti garantisco, GDB è meglio
di entrambi i metodi.

192
00:08:44,851 --> 00:08:45,350
Già.

193
00:08:45,350 --> 00:08:46,980
Quindi questo sarà il tuo nuovo migliore amico.

194
00:08:46,980 --> 00:08:51,780
Perché è una bella cosa
che visivamente visualizza sia

195
00:08:51,780 --> 00:08:54,850
ciò che il codice sta facendo
in un punto specifico

196
00:08:54,850 --> 00:08:57,486
così come quello che tutti i tuoi
variabili stanno portando,

197
00:08:57,486 --> 00:08:59,610
come quello che i loro valori sono,
a quel punto specifico.

198
00:08:59,610 --> 00:09:02,670
E in questo modo, si può veramente
impostare punti di interruzione nel codice.

199
00:09:02,670 --> 00:09:04,350
È possibile scorrere riga per riga.

200
00:09:04,350 --> 00:09:07,324
E GDB sarà solo avere per
voi, visualizzato per voi,

201
00:09:07,324 --> 00:09:09,490
quello che tutte le variabili
sono, cosa fanno,

202
00:09:09,490 --> 00:09:10,656
cosa sta succedendo nel codice.

203
00:09:10,656 --> 00:09:13,240
E in tal modo, è
così molto più facile vedere

204
00:09:13,240 --> 00:09:17,120
cosa sta succedendo invece di printf-ing
o scrivere i vostri dichiarazioni.

205
00:09:17,120 --> 00:09:19,160
>> Quindi faremo un esempio di questo più avanti.

206
00:09:19,160 --> 00:09:20,660
Quindi, questo sembra un po 'astratto.

207
00:09:20,660 --> 00:09:23,490
Non preoccuparti, faremo esempi.

208
00:09:23,490 --> 00:09:29,170
E così in sostanza, i tre più grandi,
funzioni più utilizzate di cui ha bisogno in GDB

209
00:09:29,170 --> 00:09:32,500
sono il passo successivo e oltre,
e Step in bottoni.

210
00:09:32,500 --> 00:09:34,860
Io vado a testa oltre
lì, in realtà, in questo momento.

211
00:09:34,860 --> 00:09:40,930
>> Quindi voi ragazzi tutto può vedere che
o forse dovrei ingrandire un po '?

212
00:09:40,930 --> 00:09:43,220

213
00:09:43,220 --> 00:09:44,470
Nella parte posteriore, si può vedere che?

214
00:09:44,470 --> 00:09:45,730
Dovrei ingrandire?

215
00:09:45,730 --> 00:09:46,480
Solo un po?

216
00:09:46,480 --> 00:09:49,390
Ok bello.

217
00:09:49,390 --> 00:09:50,280
Ci siamo.

218
00:09:50,280 --> 00:09:50,960
OK.

219
00:09:50,960 --> 00:09:57,000
>> Così ho, qui, la mia
implementazione per avidi.

220
00:09:57,000 --> 00:10:01,430
E mentre molti di voi ragazzi ha scritto
avidi ciclo while form-- che

221
00:10:01,430 --> 00:10:04,890
è un modo perfettamente accettabile fare
it-- un altro modo per farlo è quello di semplicemente

222
00:10:04,890 --> 00:10:06,280
suddividere nel modulo.

223
00:10:06,280 --> 00:10:09,290
Perché allora si può avere la
valore e quindi hanno il tuo resto.

224
00:10:09,290 --> 00:10:11,150
E allora si può solo
aggiungere tutto insieme.

225
00:10:11,150 --> 00:10:13,390
Fa la logica di quello che sto facendo
qui dare un senso a tutti,

226
00:10:13,390 --> 00:10:14,117
prima di cominciare?

227
00:10:14,117 --> 00:10:16,760

228
00:10:16,760 --> 00:10:17,980
Tipo?

229
00:10:17,980 --> 00:10:18,710
Cool.

230
00:10:18,710 --> 00:10:19,210
Grande.

231
00:10:19,210 --> 00:10:21,290
E 'un pezzo sexy
di codice, direi.

232
00:10:21,290 --> 00:10:23,502
Come ho detto, David, a
lezione, dopo un po ',

233
00:10:23,502 --> 00:10:25,960
sarete tutti iniziare a vedere il codice
come qualcosa che è bello.

234
00:10:25,960 --> 00:10:29,950
E a volte quando si vede bella
codice, è una sensazione meravigliosa.

235
00:10:29,950 --> 00:10:35,410
>> Quindi tuttavia, mentre questo codice è molto
bello, non funziona correttamente.

236
00:10:35,410 --> 00:10:37,750
Così corriamo check50 su questo.

237
00:10:37,750 --> 00:10:39,440
Controllare 50 20-- oop.

238
00:10:39,440 --> 00:10:43,221

239
00:10:43,221 --> 00:10:43,720
2?

240
00:10:43,720 --> 00:10:44,990
È che PSet2?

241
00:10:44,990 --> 00:10:46,870
Già.

242
00:10:46,870 --> 00:10:47,520
Oh, pset1.

243
00:10:47,520 --> 00:10:50,970

244
00:10:50,970 --> 00:10:52,890
OK.

245
00:10:52,890 --> 00:10:53,900
Così corriamo check50.

246
00:10:53,900 --> 00:11:01,550

247
00:11:01,550 --> 00:11:07,170
>> E come voi potete vedere qui,
è mancato un paio di casi.

248
00:11:07,170 --> 00:11:10,165
E per alcuni di voi, nel
corso di fare i vostri insiemi di problemi,

249
00:11:10,165 --> 00:11:11,110
siete come, ah, perché non è vero funziona.

250
00:11:11,110 --> 00:11:13,318
Perché è lavorando da
valori, ma non per gli altri?

251
00:11:13,318 --> 00:11:17,760
Beh, GDB sta per aiutarti a capire
il motivo per cui gli ingressi non funzionavano.

252
00:11:17,760 --> 00:11:18,320
>> OK.

253
00:11:18,320 --> 00:11:21,640
Vediamo quindi, uno dei
controlli Stavo venendo a mancare in check50

254
00:11:21,640 --> 00:11:24,920
era il valore di ingresso di 0,41.

255
00:11:24,920 --> 00:11:27,830
Quindi la risposta corretta che
si dovrebbe essere sempre è un 4.

256
00:11:27,830 --> 00:11:33,090
Invece quello che sto stampando
è il 3-n, che non è corretto.

257
00:11:33,090 --> 00:11:36,190
Così facciamo solo eseguire questa operazione manualmente, semplicemente
assicurarsi che check50 sta funzionando.

258
00:11:36,190 --> 00:11:36,940
Facciamo ./greedy.

259
00:11:36,940 --> 00:11:40,130

260
00:11:40,130 --> 00:11:43,340
Oops, devo fare avido.

261
00:11:43,340 --> 00:11:43,840
Ci siamo.

262
00:11:43,840 --> 00:11:44,381
Ora ./greedy.

263
00:11:44,381 --> 00:11:46,950

264
00:11:46,950 --> 00:11:47,670
>> Quanto è dovuto?

265
00:11:47,670 --> 00:11:49,550
Facciamo 0.41.

266
00:11:49,550 --> 00:11:52,590
E sì, vediamo qui
che è l'output di 3

267
00:11:52,590 --> 00:11:55,160
quando la risposta corretta,
infatti, dovrebbe essere 4.

268
00:11:55,160 --> 00:12:01,460
Quindi cerchiamo di entrare GDB e vedere come noi
può andare sulla risoluzione di questo problema.

269
00:12:01,460 --> 00:12:03,992
>> Quindi il primo passo in
debug sempre il codice

270
00:12:03,992 --> 00:12:05,950
è quello di impostare un punto di interruzione,
o un punto in cui si

271
00:12:05,950 --> 00:12:09,079
desidera che il computer o il
debugger per iniziare a guardare.

272
00:12:09,079 --> 00:12:11,120
Quindi, se non si ha realmente
sapere che cosa il vostro problema è,

273
00:12:11,120 --> 00:12:14,670
Di solito, la cosa tipica vogliamo
fare è impostare il nostro punto di interruzione alla principale.

274
00:12:14,670 --> 00:12:18,520
Quindi, se voi potete vedere questo
pulsante rosso proprio lì,

275
00:12:18,520 --> 00:12:22,860
sì, quello era soltanto un me
breakpoint per la funzione principale.

276
00:12:22,860 --> 00:12:24,130
Clicco che.

277
00:12:24,130 --> 00:12:26,130
>> E poi posso andare al mio pulsante Debug.

278
00:12:26,130 --> 00:12:27,036
Mi ha colpito quel pulsante.

279
00:12:27,036 --> 00:12:31,710

280
00:12:31,710 --> 00:12:36,555
Permettetemi di zoom indietro se posso.

281
00:12:36,555 --> 00:12:38,020
Ci siamo.

282
00:12:38,020 --> 00:12:40,730
Così abbiamo, qui, un pannello sulla destra.

283
00:12:40,730 --> 00:12:43,680
Mi dispiace, ragazzi nella parte posteriore, si
non si può davvero vedere molto bene.

284
00:12:43,680 --> 00:12:49,090
Ma in sostanza, tutte
questo pannello di destra sta facendo

285
00:12:49,090 --> 00:12:53,130
è tenere traccia sia della evidenziata
linea, che è la linea di codice

286
00:12:53,130 --> 00:12:56,640
che il computer è in esecuzione,
così come tutte le variabili

287
00:12:56,640 --> 00:12:57,600
qui sotto.

288
00:12:57,600 --> 00:13:00,487
>> Così hai centesimi, monete, n,
tutti dichiarati a cose diverse

289
00:13:00,487 --> 00:13:01,070
a questo punto.

290
00:13:01,070 --> 00:13:04,850
Nessun problema, perché non hanno in realtà
li inizializzato a tutte le variabili ancora.

291
00:13:04,850 --> 00:13:07,200
Quindi nel tuo computer, il
calcolatore è appena visto,

292
00:13:07,200 --> 00:13:14,376
oh, 32767 è stata l'ultima funzione utilizzata
di quello spazio di memoria nel mio computer.

293
00:13:14,376 --> 00:13:16,000
E così che è dove centesimi attualmente è.

294
00:13:16,000 --> 00:13:19,360
Ma no che una volta che si esegue il codice,
dovrebbe diventare inizializzato.

295
00:13:19,360 --> 00:13:24,110
>> Quindi cerchiamo di passare attraverso, riga per
la linea, che cosa sta succedendo qui.

296
00:13:24,110 --> 00:13:25,350
OK.

297
00:13:25,350 --> 00:13:29,400
Così qui sono i tre
pulsanti che ho appena spiegato.

298
00:13:29,400 --> 00:13:34,090
Hai la riproduzione, o la funzione Run,
pulsante, si ha il passaggio sopra il pulsante,

299
00:13:34,090 --> 00:13:36,600
e hai anche il passo in tasto.

300
00:13:36,600 --> 00:13:41,260
E essenzialmente, tutti e tre
loro solo passare attraverso il codice

301
00:13:41,260 --> 00:13:42,690
e fare cose diverse.

302
00:13:42,690 --> 00:13:45,680
>> Così tipicamente, quando si è il debug,
noi non vogliamo solo colpire Play,

303
00:13:45,680 --> 00:13:47,930
perché Play appena eseguito
il codice per la fine di esso.

304
00:13:47,930 --> 00:13:49,070
E poi non sarà effettivamente
sapere che cosa il vostro problema

305
00:13:49,070 --> 00:13:51,432
è se non si imposta più punti di interruzione.

306
00:13:51,432 --> 00:13:53,890
Se si imposta più punti di interruzione,
lo farà solo automaticamente

307
00:13:53,890 --> 00:13:56,030
correre da un punto di interruzione,
al successivo, a quello successivo.

308
00:13:56,030 --> 00:13:58,030
Ma in questo caso abbiamo
solo che uno, perché noi

309
00:13:58,030 --> 00:13:59,970
voglia di lavorare il nostro modo
dall'alto verso il basso.

310
00:13:59,970 --> 00:14:04,830
Così stiamo andando a ignorare quel pulsante
in questo momento per fini del presente programma.

311
00:14:04,830 --> 00:14:08,230
>> Quindi il passo sopra funzione appena
passi oltre ogni singola riga

312
00:14:08,230 --> 00:14:11,510
e ti dice cosa
il computer sta facendo.

313
00:14:11,510 --> 00:14:14,630
Il passo in funzione va
nella funzione reale

314
00:14:14,630 --> 00:14:16,000
che è sulla linea di codice.

315
00:14:16,000 --> 00:14:19,070
Così, per esempio, come printf (),
che è una funzione, giusto?

316
00:14:19,070 --> 00:14:21,980
Se volessi fisicamente passo
nella funzione printf (),

317
00:14:21,980 --> 00:14:25,610
Vorrei davvero andare nel pezzo di
codice in cui printf () è stato scritto e vedere

318
00:14:25,610 --> 00:14:26,730
cosa sta succedendo li.

319
00:14:26,730 --> 00:14:29,924
>> Ma di solito, si assume che
il codice che vi diamo funziona.

320
00:14:29,924 --> 00:14:31,340
Non ci assumiamo la printf () sta lavorando.

321
00:14:31,340 --> 00:14:33,170
Partiamo dal presupposto che GetInt () sta lavorando.

322
00:14:33,170 --> 00:14:35,170
Quindi non c'è bisogno di
passo in tali funzioni.

323
00:14:35,170 --> 00:14:37,170
Ma se c'è funzioni
scritta da voi

324
00:14:37,170 --> 00:14:39,060
che si desidera controllare
cosa sta succedendo,

325
00:14:39,060 --> 00:14:41,200
si vorrebbe fare un passo
in tale funzione.

326
00:14:41,200 --> 00:14:43,940
>> Così adesso stiamo solo andando
per scavalcare questo pezzo di codice.

327
00:14:43,940 --> 00:14:44,485
Quindi cerchiamo di vedere.

328
00:14:44,485 --> 00:14:46,547
Oh, stampa, "Oh hai, come
cambia molto è dovuto? "

329
00:14:46,547 --> 00:14:47,130
Non ci interessa.

330
00:14:47,130 --> 00:14:49,830
Sappiamo che sta funzionando,
così facciamo un passo su di esso.

331
00:14:49,830 --> 00:14:53,290
>> Così n, che è il nostro galleggiante che
Abbiamo initialized-- o declared--

332
00:14:53,290 --> 00:14:56,810
nella parte superiore, ora siamo
pari a quella di getFloat ().

333
00:14:56,810 --> 00:14:57,810
Quindi facciamo un passo su quella.

334
00:14:57,810 --> 00:14:59,580
E vediamo al
fondo qui, il programma

335
00:14:59,580 --> 00:15:03,360
mi sta spingendo per introdurre un valore.

336
00:15:03,360 --> 00:15:08,580
Ingresso di modo da lasciare il valore che vogliamo
testare qui, che è 0,41.

337
00:15:08,580 --> 00:15:09,160
Grande.

338
00:15:09,160 --> 00:15:12,780
>> Così ora n-- voi ragazzi vedere
qui, al bottom-- è

339
00:15:12,780 --> 00:15:15,140
stored-- perché noi
non hanno ancora arrotondati, è

340
00:15:15,140 --> 00:15:19,540
memorizzati in questo gigante come
float che è 0,4099999996,

341
00:15:19,540 --> 00:15:22,550
che è abbastanza vicino al nostro
scopi, in questo momento, a 0,41.

342
00:15:22,550 --> 00:15:26,090
E poi si vedrà più avanti, come noi
proseguire scavalcando il programma,

343
00:15:26,090 --> 00:15:29,850
dopo qui, n è diventato
arrotondato e centesimi è diventato 41.

344
00:15:29,850 --> 00:15:30,350
Grande.

345
00:15:30,350 --> 00:15:32,230
Così sappiamo che il lavoro del nostro arrotondamento.

346
00:15:32,230 --> 00:15:34,700
Sappiamo che abbiamo il
corretto numero di centesimi,

347
00:15:34,700 --> 00:15:36,990
così sappiamo che questo è
non è davvero il problema.

348
00:15:36,990 --> 00:15:40,050
>> Così continuiamo passo
in questo programma.

349
00:15:40,050 --> 00:15:40,900
Siamo andate qui.

350
00:15:40,900 --> 00:15:46,139
E così dopo questa riga di codice, abbiamo
dovrebbe sapere quanti trimestri abbiamo.

351
00:15:46,139 --> 00:15:46,680
Facciamo un passo sopra.

352
00:15:46,680 --> 00:15:52,040
E vedi che facciamo, infatti, abbiamo una
quarto perché abbiamo sottratto 25

353
00:15:52,040 --> 00:15:53,790
dal nostro valore iniziale di 41.

354
00:15:53,790 --> 00:15:55,890
E abbiamo 16 a sinistra per i nostri centesimi.

355
00:15:55,890 --> 00:15:58,830
>> Fa capire a tutti come
il programma è un passo attraverso

356
00:15:58,830 --> 00:16:02,980
e perché centesimi è ormai diventato 16
e perché, ora, le monete è diventato uno?

357
00:16:02,980 --> 00:16:04,610
Sta seguendo tutti questa logica?

358
00:16:04,610 --> 00:16:05,110
Cool.

359
00:16:05,110 --> 00:16:07,860
Così come di questo punto, la
funzionamento del programma, giusto?

360
00:16:07,860 --> 00:16:09,797
Sappiamo che sta facendo esattamente
quello che noi vogliamo.

361
00:16:09,797 --> 00:16:11,880
E non abbiamo fatto in realtà
avere per stampare, oh, che

362
00:16:11,880 --> 00:16:14,430
è centesimi a questo punto,
ciò è monete a questo punto.

363
00:16:14,430 --> 00:16:17,170
>> Continuiamo passando attraverso il programma.

364
00:16:17,170 --> 00:16:18,100
Scavalcare.

365
00:16:18,100 --> 00:16:18,620
Cool.

366
00:16:18,620 --> 00:16:19,700
Andiamo su monetine.

367
00:16:19,700 --> 00:16:20,200
Grande.

368
00:16:20,200 --> 00:16:22,367
Vediamo che ci sono voluti
off $ 0,10 per un centesimo.

369
00:16:22,367 --> 00:16:23,450
E ora abbiamo due monete.

370
00:16:23,450 --> 00:16:25,260
È corretto.

371
00:16:25,260 --> 00:16:31,555
>> Andiamo oltre centesimi e vediamo
che abbiamo lasciato sopra centesimi.

372
00:16:31,555 --> 00:16:32,680
Hmm, questo è strano.

373
00:16:32,680 --> 00:16:37,540
Quassù al programma, ho dovuto
di aver sottratto i miei soldini.

374
00:16:37,540 --> 00:16:39,400
Forse semplicemente non ero
facendo questo diritto linea.

375
00:16:39,400 --> 00:16:42,190
E ahimè, si può vedere
qui, perché sappiamo

376
00:16:42,190 --> 00:16:44,360
che stiamo intensificando
attraverso le linee 32 e 33,

377
00:16:44,360 --> 00:16:50,560
è lì che il nostro programma
impropriamente avevano variabili corrono.

378
00:16:50,560 --> 00:16:55,136
Così possiamo guardare e vedere, oh,
Sto sottraendo centesimi qui,

379
00:16:55,136 --> 00:16:57,010
ma io non sono in realtà
aggiungendo al mio valore della moneta.

380
00:16:57,010 --> 00:16:57,860
Sto aggiungendo di centesimi.

381
00:16:57,860 --> 00:17:00,234
E io non voglio aggiungere a
centesimi, voglio aggiungere alle monete.

382
00:17:00,234 --> 00:17:05,420
Quindi, se cambiamo che a monete,
abbiamo un programma di lavoro.

383
00:17:05,420 --> 00:17:06,730
Posso correre check50.

384
00:17:06,730 --> 00:17:11,063
Si può solo uscire dal GDB destra
qui e quindi eseguire nuovamente check50.

385
00:17:11,063 --> 00:17:11,938
Potrei farlo.

386
00:17:11,938 --> 00:17:14,822

387
00:17:14,822 --> 00:17:18,480
Devo fare avido.

388
00:17:18,480 --> 00:17:19,940
0.41.

389
00:17:19,940 --> 00:17:22,819
E qui, è la stampa
la risposta giusta.

390
00:17:22,819 --> 00:17:26,569
>> Così come voi potete vedere, GDB
è uno strumento davvero potente

391
00:17:26,569 --> 00:17:29,940
per quando abbiamo così tanto codice
in corso e così tante variabili

392
00:17:29,940 --> 00:17:32,510
che è difficile per noi, come
un essere umano, per tenere traccia di.

393
00:17:32,510 --> 00:17:35,360
Il computer, in GDB
debugger, ha la capacità

394
00:17:35,360 --> 00:17:37,020
per tenere traccia di tutto ciò.

395
00:17:37,020 --> 00:17:40,480
Lo so, in Visionaire, voi ragazzi probabilmente
potrebbe aver colpito alcuni difetti di segmentazione

396
00:17:40,480 --> 00:17:43,150
perché si stesse eseguendo
fuori dai limiti della propria matrice.

397
00:17:43,150 --> 00:17:46,510
Nell'esempio di Cesare, che è
esattamente quello che ho implementato qui.

398
00:17:46,510 --> 00:17:50,060
>> Così ho dimenticato di verificare la presenza di
cosa accadrebbe se io

399
00:17:50,060 --> 00:17:52,510
non ha avuto due argomenti della riga di comando.

400
00:17:52,510 --> 00:17:53,880
Solo che non ho messo in quella di controllo.

401
00:17:53,880 --> 00:17:57,380
E così, se corro Debug-- ho impostato
il mio punto di interruzione per proprio lì.

402
00:17:57,380 --> 00:17:58,055
Corro Debug.

403
00:17:58,055 --> 00:18:15,880

404
00:18:15,880 --> 00:18:16,550
>> OK.

405
00:18:16,550 --> 00:18:17,050
Già.

406
00:18:17,050 --> 00:18:20,350
Quindi, in realtà, avrebbe dovuto GDB
a me hanno detto lì

407
00:18:20,350 --> 00:18:22,300
è stato un errore di segmentazione lì.

408
00:18:22,300 --> 00:18:24,883
Non so che cosa stava succedendo
proprio lì, ma quando ho eseguito,

409
00:18:24,883 --> 00:18:25,590
stava funzionando.

410
00:18:25,590 --> 00:18:29,410
Quando si esegue righe di codice tramite e
GDB potrebbe semplicemente smettere improvvisamente su di voi,

411
00:18:29,410 --> 00:18:31,540
salire e guardare ciò che l'errore è rosso.

412
00:18:31,540 --> 00:18:33,930
E ti dirò, hey,
aveva un errore di segmentazione,

413
00:18:33,930 --> 00:18:38,550
il che significa che si è tentato di accedere
spazio in una matrice che non esisteva.

414
00:18:38,550 --> 00:18:39,050
Già.

415
00:18:39,050 --> 00:18:43,280
>> Così nel prossimo problema
set di questa settimana, ragazzi

416
00:18:43,280 --> 00:18:45,600
probabilmente hanno un sacco di
variabili galleggianti intorno.

417
00:18:45,600 --> 00:18:48,560
Lei non sta andando ad essere sicuro di quello che
vogliono dire a un certo punto.

418
00:18:48,560 --> 00:18:53,560
Così GDB sarà davvero aiutare a capire
che cosa sono tutti pari

419
00:18:53,560 --> 00:18:55,940
ed essere in grado di vedere che visivamente.

420
00:18:55,940 --> 00:19:01,995
C'è qualcuno confuso su come
niente di tutto questo stava funzionando?

421
00:19:01,995 --> 00:19:02,495
Cool.

422
00:19:02,495 --> 00:19:10,121

423
00:19:10,121 --> 00:19:10,620
Tutto ok.

424
00:19:10,620 --> 00:19:14,260
Così, dopo che, siamo
andando a tuffarsi a destra

425
00:19:14,260 --> 00:19:17,562
in quattro diversi
tipi di genere per questa settimana.

426
00:19:17,562 --> 00:19:19,520
Quanti di voi, prima
di tutto, prima di iniziare,

427
00:19:19,520 --> 00:19:23,020
hanno letto l'intera specifica per pset3?

428
00:19:23,020 --> 00:19:23,824
OK.

429
00:19:23,824 --> 00:19:24,740
Sono orgoglioso di voi ragazzi.

430
00:19:24,740 --> 00:19:29,110
Questo è come la metà della classe, che
è molto più che l'ultima volta.

431
00:19:29,110 --> 00:19:33,950
>> Ecco, questo è grande, perché quando
si parla di contenuti

432
00:19:33,950 --> 00:19:36,170
in lecture-- o dispiaciuto,
in section-- Mi piace

433
00:19:36,170 --> 00:19:38,210
mettere in relazione un sacco di che
torna a ciò che il pset è

434
00:19:38,210 --> 00:19:40,210
e come si desidera
implementare che nel tuo pset.

435
00:19:40,210 --> 00:19:42,400
Quindi, se si arriva con
leggere le specifiche, sarà

436
00:19:42,400 --> 00:19:45,510
molto più facile per voi capire
che cosa sto parlando quando dico,

437
00:19:45,510 --> 00:19:48,720
Oh, hey, questo potrebbe essere davvero un
buon posto per implementare questo tipo.

438
00:19:48,720 --> 00:19:52,870
Così quelli di voi che hanno letto il
spec sapere che, come parte della vostra pset,

439
00:19:52,870 --> 00:19:54,900
si sta andando ad avere per
scrivere un tipo di ordinamento.

440
00:19:54,900 --> 00:19:58,670
Quindi questo può essere molto utile
per molti di voi oggi.

441
00:19:58,670 --> 00:20:01,760
>> Quindi inizieremo con,
essenzialmente, il tipo più semplice

442
00:20:01,760 --> 00:20:04,580
della specie, la selezione tipo.

443
00:20:04,580 --> 00:20:06,800
L'algoritmo tipico per
come ci piacerebbe andare su questo

444
00:20:06,800 --> 00:20:10,460
è-- Davide ha attraversato questi tutti in
lezione, quindi mi muovo in fretta lungo

445
00:20:10,460 --> 00:20:13,900
qui-- è essenzialmente, è
hanno una serie di valori.

446
00:20:13,900 --> 00:20:17,170
E poi si trova il
piccolo valore indifferenziati

447
00:20:17,170 --> 00:20:20,200
e di scambiare tale valore con
il primo valore non ordinato.

448
00:20:20,200 --> 00:20:22,700
E poi basta continuare a ripetere
con il resto della vostra lista.

449
00:20:22,700 --> 00:20:25,740
>> Ed ecco una spiegazione visiva
di come dovrebbe funzionare.

450
00:20:25,740 --> 00:20:30,460
Così, per esempio, se dovessimo iniziare
con una serie di cinque elementi, indice

451
00:20:30,460 --> 00:20:35,910
0 a 4, con 3, 5, 2, 6, e 4 valori
collocato nel array-- così in questo momento,

452
00:20:35,910 --> 00:20:38,530
stiamo solo andando ad assumere
che sono tutti indifferenziati

453
00:20:38,530 --> 00:20:41,130
perché non abbiamo provato altrimenti.

454
00:20:41,130 --> 00:20:44,130
>> Quindi, come una sorta di selezione sarebbe
lavoro è che sarebbe prima

455
00:20:44,130 --> 00:20:46,800
percorrere la totalità
dell'array indifferenziati.

456
00:20:46,800 --> 00:20:49,120
Sarebbe scegliere il valore più piccolo.

457
00:20:49,120 --> 00:20:51,750
In questo caso, 3, destra
ora, è il più piccolo.

458
00:20:51,750 --> 00:20:52,680
Si arriva a 5.

459
00:20:52,680 --> 00:20:55,620
No, 5 non è maggiore than--
o mi dispiace, non è meno than-- 3.

460
00:20:55,620 --> 00:20:57,779
Quindi il valore minimo è ancora 3.

461
00:20:57,779 --> 00:20:58,695
E poi si arriva a 2.

462
00:20:58,695 --> 00:21:00,990
Il computer vede, oh, 2 è inferiore a 3.

463
00:21:00,990 --> 00:21:02,750
2 deve ora il valore minimo.

464
00:21:02,750 --> 00:21:06,630
E così 2 swap con quel primo valore.

465
00:21:06,630 --> 00:21:10,702
>> Così, dopo un solo passaggio, noi davvero vediamo
che il 2 e il 3 sono scambiati.

466
00:21:10,702 --> 00:21:13,910
E stiamo solo andando a continuare a fare
questo nuovo con il resto della matrice.

467
00:21:13,910 --> 00:21:17,660
Quindi stiamo andando a correre solo attraverso
gli ultimi quattro indici dell'array.

468
00:21:17,660 --> 00:21:20,670
Vedremo che 3 è
il valore minimo successiva.

469
00:21:20,670 --> 00:21:23,240
Quindi stiamo andando a scambiare che con 4.

470
00:21:23,240 --> 00:21:26,900
E poi stiamo solo andando a tenere
che attraversa fino a quando, alla fine,

471
00:21:26,900 --> 00:21:33,730
arrivare a un array ordinato in cui
2, 3, 4, 5, e 6 sono tutti ordinati.

472
00:21:33,730 --> 00:21:37,530
Fa capire a tutti la logica
di come funziona un ordinamento per selezione?

473
00:21:37,530 --> 00:21:39,669
>> Devi solo qualche tipo
di un valore minimo.

474
00:21:39,669 --> 00:21:41,210
Stai tenere traccia di quello che è.

475
00:21:41,210 --> 00:21:45,170
E ogni volta a trovarlo, si scambia esso
con il primo valore della array--

476
00:21:45,170 --> 00:21:48,740
o, non il primo value--
il valore successivo nella matrice.

477
00:21:48,740 --> 00:21:50,150
Cool.

478
00:21:50,150 --> 00:21:55,460
>> Così come voi ragazzi tipo di
visto da un breve scorcio,

479
00:21:55,460 --> 00:21:58,450
stiamo andando a pseudocodice questo fuori.

480
00:21:58,450 --> 00:22:02,510
Quindi, se voi ragazzi nella parte posteriore vogliamo
formare un gruppo, tutti a un tavolo

481
00:22:02,510 --> 00:22:06,170
può formare un piccolo compagno, io vado
per darvi ragazzi come tre minuti

482
00:22:06,170 --> 00:22:08,190
di parlare solo attraverso
la logica, in inglese,

483
00:22:08,190 --> 00:22:14,161
di come potremmo essere in grado di implementare
pseudocodice a scrivere una selezione sorta.

484
00:22:14,161 --> 00:22:14,910
E c'è caramelle.

485
00:22:14,910 --> 00:22:16,118
Si prega di venire e ottenere caramelle.

486
00:22:16,118 --> 00:22:19,520
Se siete alla schiena e si desidera
caramelle, posso buttare caramelle a voi.

487
00:22:19,520 --> 00:22:22,850
In realtà, fare fresco you--.

488
00:22:22,850 --> 00:22:23,552
Oh scusa.

489
00:22:23,552 --> 00:22:26,751

490
00:22:26,751 --> 00:22:27,250
OK.

491
00:22:27,250 --> 00:25:23,880

492
00:25:23,880 --> 00:25:27,140
>> Quindi, se vogliamo, come
una classe, pseudocodice write

493
00:25:27,140 --> 00:25:30,466
per come si potrebbe affrontare
questo problema, ritiene appena libera.

494
00:25:30,466 --> 00:25:32,340
Mi limiterò a andare in giro e,
in ordine, chieda gruppi

495
00:25:32,340 --> 00:25:35,065
per la successiva riga di
quello che dobbiamo fare.

496
00:25:35,065 --> 00:25:37,840
Quindi, se voi volete iniziare
off, qual è la prima cosa

497
00:25:37,840 --> 00:25:40,600
a fare quando si sta cercando di
implementare un modo per risolvere questo programma

498
00:25:40,600 --> 00:25:43,480
per ordinare selettivamente una lista?

499
00:25:43,480 --> 00:25:46,349
Diciamo solo assumere noi
hanno una serie, va bene?

500
00:25:46,349 --> 00:25:49,088
>> PUBBLICO: Si desidera creare un po '
sorta di [incomprensibile] che sei

501
00:25:49,088 --> 00:25:50,420
che attraversa tutta l'array.

502
00:25:50,420 --> 00:25:51,128
>> ANDI PENG: Giusto.

503
00:25:51,128 --> 00:25:54,100
Così si sta andando a voler iterare
attraverso ogni spazio, giusto?

504
00:25:54,100 --> 00:26:05,490
Cosi grande.

505
00:26:05,490 --> 00:26:08,600
Se voi volete darmi la
prossimo line-- sì, nella parte posteriore.

506
00:26:08,600 --> 00:26:11,414

507
00:26:11,414 --> 00:26:13,290
>> PUBBLICO: Dateci
tutto per i più piccoli.

508
00:26:13,290 --> 00:26:14,248
>> ANDI PENG: Ci andiamo.

509
00:26:14,248 --> 00:26:17,438
Quindi vogliamo andare attraverso e controllare
vedere ciò che il valore minimo è, giusto?

510
00:26:17,438 --> 00:26:22,110

511
00:26:22,110 --> 00:26:24,840
Io vado per abbreviare quello a "min."

512
00:26:24,840 --> 00:26:27,658
Che cosa voi ragazzi volete fare dopo
hai trovato il valore minimo?

513
00:26:27,658 --> 00:26:28,533
>> PUBBLICO: [incomprensibile]

514
00:26:28,533 --> 00:26:29,942

515
00:26:29,942 --> 00:26:33,150
ANDI PENG: Quindi stai andando a voler
passare con il primo di tale matrice,

516
00:26:33,150 --> 00:26:33,650
destra?

517
00:26:33,650 --> 00:26:45,120

518
00:26:45,120 --> 00:26:46,850
Questo è l'inizio, ho intenzione di dire.

519
00:26:46,850 --> 00:26:47,220
Tutto ok.

520
00:26:47,220 --> 00:26:50,386
Quindi, ora che hai scambiato il primo
uno, che cosa vuoi fare dopo?

521
00:26:50,386 --> 00:26:54,840
Così ora sappiamo che questa qui
deve essere il valore più piccolo, giusto?

522
00:26:54,840 --> 00:26:58,310
Allora avete un riposo aggiuntivo
della matrice che è indifferenziati.

523
00:26:58,310 --> 00:27:01,569
Allora, cosa si vuole fare qui, se
ragazzi vogliono darmi la prossima linea?

524
00:27:01,569 --> 00:27:04,610
PUBBLICO: Allora volete iterare
attraverso il resto della matrice.

525
00:27:04,610 --> 00:27:05,276
ANDI PENG: Sì.

526
00:27:05,276 --> 00:27:09,857
E così ciò che scorrendo
tipo di implicano probabilmente avremo bisogno?

527
00:27:09,857 --> 00:27:10,440
Che tipo di--

528
00:27:10,440 --> 00:27:12,057
>> PUBBLICO: Oh, una variabile aggiuntiva?

529
00:27:12,057 --> 00:27:13,890
ANDI PENG: Probabilmente
un'altra per il ciclo, giusto?

530
00:27:13,890 --> 00:27:28,914
Quindi stiamo probabilmente andando a voler
per scorrere through-- grande.

531
00:27:28,914 --> 00:27:31,830
E poi avete intenzione di tornare indietro e
probabilmente controllare di nuovo il minimo,

532
00:27:31,830 --> 00:27:32,100
destra?

533
00:27:32,100 --> 00:27:34,975
E si sta andando a continuare a ripetere
questo, perché i loop solo andando

534
00:27:34,975 --> 00:27:36,010
continuare a correre, giusto?

535
00:27:36,010 --> 00:27:39,190
>> Così come voi potete vedere, abbiamo
solo avere un pseudocodice generale

536
00:27:39,190 --> 00:27:41,480
di come vogliamo questo programma per guardare.

537
00:27:41,480 --> 00:27:46,646
Questo iterate qui, quello che facciamo noi
in genere bisogno di scrivere nel nostro codice

538
00:27:46,646 --> 00:27:49,270
se vogliamo iterare un
array, che tipo di struttura?

539
00:27:49,270 --> 00:27:51,030
Credo che Christabel
già detto prima.

540
00:27:51,030 --> 00:27:51,500
>> PUBBLICO: Un ciclo for.

541
00:27:51,500 --> 00:27:52,160
>> ANDI PENG: Un ciclo for?

542
00:27:52,160 --> 00:27:52,770
Di preciso.

543
00:27:52,770 --> 00:27:56,060
Quindi questo è probabilmente
Sarà un ciclo for.

544
00:27:56,060 --> 00:27:59,240
Che cosa è un assegno qui andando a implicare?

545
00:27:59,240 --> 00:28:02,536
In genere, se si desidera controllare
se qualcosa è qualcosa else--

546
00:28:02,536 --> 00:28:03,270
>> PUBBLICO: se.

547
00:28:03,270 --> 00:28:06,790
>> ANDI PENG: Un caso, giusto?

548
00:28:06,790 --> 00:28:10,790
E poi lo swap qui, ce la faremo
andare oltre tardi, perché David

549
00:28:10,790 --> 00:28:12,770
passato attraverso che in conferenza pure.

550
00:28:12,770 --> 00:28:14,580
E poi il secondo iterata implies--

551
00:28:14,580 --> 00:28:15,120
>> PUBBLICO: Un altro ciclo for.

552
00:28:15,120 --> 00:28:16,745
>> ANDI PENG: --another per il ciclo, esattamente.

553
00:28:16,745 --> 00:28:19,870

554
00:28:19,870 --> 00:28:22,000
Quindi, se stiamo cercando
in questo correttamente, abbiamo

555
00:28:22,000 --> 00:28:24,680
può vedere che siamo probabilmente
andando ad avere bisogno di un ciclo for nidificato

556
00:28:24,680 --> 00:28:28,330
con un'istruzione condizionale in là
e quindi un pezzo reale del codice che è

557
00:28:28,330 --> 00:28:31,360
andando a scambiare i valori.

558
00:28:31,360 --> 00:28:35,980
Così ho appena generalmente scritto
un codice pseudocodice qui.

559
00:28:35,980 --> 00:28:38,910
E poi stiamo effettivamente andando
fisicamente, come classe,

560
00:28:38,910 --> 00:28:40,700
cercare di attuare questo oggi.

561
00:28:40,700 --> 00:28:42,486
Torniamo in questo IDE.

562
00:28:42,486 --> 00:28:49,243

563
00:28:49,243 --> 00:28:50,230
>> Uh Oh.

564
00:28:50,230 --> 00:28:51,754
Perché è che not-- c'è.

565
00:28:51,754 --> 00:28:52,253
OK.

566
00:28:52,253 --> 00:28:55,834

567
00:28:55,834 --> 00:28:57,500
Siamo spiacenti, vorrei provare a ingrandire un po 'di più.

568
00:28:57,500 --> 00:28:59,310
Ci siamo.

569
00:28:59,310 --> 00:29:05,060
Tutto quello che sto facendo qui è che ho creato
un programma chiamato "selezione / sort.c."

570
00:29:05,060 --> 00:29:10,860
Ho creato una serie di nove
valori, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
Attualmente, come si può
vedono, non sono ordinati.

572
00:29:14,370 --> 00:29:17,880
n sta per essere il numero che
ti dice la quantità di valori

573
00:29:17,880 --> 00:29:18,920
avete nel vostro allineamento.

574
00:29:18,920 --> 00:29:20,670
In questo caso, abbiamo nove valori.

575
00:29:20,670 --> 00:29:23,760
E ho appena ricevuto un ciclo for qui
che stampa l'array non ordinato.

576
00:29:23,760 --> 00:29:28,370
>> E alla fine, ho anche una per
ciclo che stampa appena fuori di nuovo.

577
00:29:28,370 --> 00:29:32,070
Quindi teoricamente, se questo programma
funzioni correttamente, alla fine,

578
00:29:32,070 --> 00:29:35,670
si dovrebbe vedere un stampate per il ciclo
in cui 1, 2, 3, 4, 5, 6, 7, 8,

579
00:29:35,670 --> 00:29:39,310
9 sono tutti in modo corretto.

580
00:29:39,310 --> 00:29:43,410
>> Così abbiamo il nostro pseudocodice qui.

581
00:29:43,410 --> 00:29:46,090
Qualcuno vuole a-- Sono solo
intenzione di andare a chiedere per volunteers--

582
00:29:46,090 --> 00:29:49,540
dirmi esattamente che cosa digitare se
vogliamo, prima, basta scorrere

583
00:29:49,540 --> 00:29:52,840
attraverso l'inizio di questo array?

584
00:29:52,840 --> 00:29:55,204
Qual è la linea di codice che sono
Probabilmente avrà bisogno di qui?

585
00:29:55,204 --> 00:29:56,990
>> PUBBLICO: [incomprensibile]

586
00:29:56,990 --> 00:29:59,010
>> ANDI PENG: Sì, si sentono
gratis a-- dispiace,

587
00:29:59,010 --> 00:30:02,318
non c'è bisogno di stare up-- tatto
libero di alzare la voce un po '.

588
00:30:02,318 --> 00:30:08,190
>> Destinatari: per int i è uguale a 0--

589
00:30:08,190 --> 00:30:10,690
>> ANDI PENG: Sì, bene.

590
00:30:10,690 --> 00:30:15,220
>> PUBBLICO: i è minore lunghezza dell'array.

591
00:30:15,220 --> 00:30:19,630
>> ANDI PENG: Quindi tenete a
mente qui, perché noi

592
00:30:19,630 --> 00:30:23,060
non hanno una funzione che
ci dice la lunghezza di un array,

593
00:30:23,060 --> 00:30:25,790
abbiamo già una
valore che memorizza tale.

594
00:30:25,790 --> 00:30:27,920
Destra?

595
00:30:27,920 --> 00:30:31,010
Un'altra cosa da tenere
in mind-- in un array

596
00:30:31,010 --> 00:30:33,940
di nove valori, quali sono gli indici?

597
00:30:33,940 --> 00:30:38,720
Diciamo solo che questa matrice è 0-3.

598
00:30:38,720 --> 00:30:41,500
Si vede che l'ultima
indice è in realtà 3.

599
00:30:41,500 --> 00:30:45,530
Non è 4, anche se non c'è
quattro valori nella matrice.

600
00:30:45,530 --> 00:30:49,866
>> Così qui, dobbiamo essere molto attenti
di ciò nostra condizione per la lunghezza

601
00:30:49,866 --> 00:30:50,490
sarà.

602
00:30:50,490 --> 00:30:51,948
>> PUBBLICO: Non sarebbe n meno 1?

603
00:30:51,948 --> 00:30:54,440
ANDI PENG: Sta andando
n meno 1, esattamente.

604
00:30:54,440 --> 00:30:57,379
Ha senso, perché
è n meno 1, tutti?

605
00:30:57,379 --> 00:30:58,920
È perché gli array sono zero indicizzati.

606
00:30:58,920 --> 00:31:02,010
Essi partono da 0 e correre fino a n meno 1.

607
00:31:02,010 --> 00:31:03,210
Sì, è un po 'complicato.

608
00:31:03,210 --> 00:31:03,730
OK.

609
00:31:03,730 --> 00:31:05,929
E poi--

610
00:31:05,929 --> 00:31:08,054
PUBBLICO: Isnt'1 che
già curato, però,

611
00:31:08,054 --> 00:31:11,400
semplicemente non dicendo "inferiore o
uguale a "e basta dire" meno? "

612
00:31:11,400 --> 00:31:13,108
>> ANDI PENG: Questo è un
davvero bella domanda.

613
00:31:13,108 --> 00:31:13,630
Allora sì.

614
00:31:13,630 --> 00:31:17,410
Ma anche, il modo in cui siamo
l'attuazione del diritto di controllo,

615
00:31:17,410 --> 00:31:19,120
è necessario confrontare due valori.

616
00:31:19,120 --> 00:31:21,009
Così si vuole realmente
lasciare la "a" vuoto.

617
00:31:21,009 --> 00:31:23,050
Perché se si confronta
questo, non hai intenzione

618
00:31:23,050 --> 00:31:25,530
avere nulla dopo
da confrontare con, giusto?

619
00:31:25,530 --> 00:31:27,460
Già.

620
00:31:27,460 --> 00:31:29,297
Così i ++.

621
00:31:29,297 --> 00:31:30,380
Aggiungiamo i nostri parentesi.

622
00:31:30,380 --> 00:31:30,880
Ops.

623
00:31:30,880 --> 00:31:33,950

624
00:31:33,950 --> 00:31:34,710
Grande.

625
00:31:34,710 --> 00:31:39,117
Così abbiamo l'inizio
del nostro ciclo esterno.

626
00:31:39,117 --> 00:31:41,450
Così ora probabilmente vogliamo
creare una variabile per mantenere

627
00:31:41,450 --> 00:31:43,085
traccia del valore minimo, giusto?

628
00:31:43,085 --> 00:31:45,751
Qualcuno ha voglia di darmi il
riga di codice che potrebbe farlo?

629
00:31:45,751 --> 00:31:48,700

630
00:31:48,700 --> 00:31:53,570
Che cosa abbiamo bisogno se vogliamo
a voler conservare qualcosa?

631
00:31:53,570 --> 00:31:55,047
>> Destra.

632
00:31:55,047 --> 00:31:57,630
Forse un nome migliore per questo
avrebbe essere-- "temp" totalmente works--

633
00:31:57,630 --> 00:32:00,655
forse più giustamente intitolato sarebbe,
se vogliamo che il più piccolo value--

634
00:32:00,655 --> 00:32:01,624
>> PUBBLICO: min.

635
00:32:01,624 --> 00:32:02,790
ANDI PENG: min, ci andiamo.

636
00:32:02,790 --> 00:32:05,230
min sarebbe buono.

637
00:32:05,230 --> 00:32:08,340
Ed ecco, che cosa fare noi
vuole inizializzare a?

638
00:32:08,340 --> 00:32:09,620
Questo è un po 'complicato.

639
00:32:09,620 --> 00:32:13,580
Perché in questo momento al
inizio di questa matrice,

640
00:32:13,580 --> 00:32:15,730
non hai guardato nulla, giusto?

641
00:32:15,730 --> 00:32:19,200
Così che cosa, automaticamente, se
siamo solo su i è uguale a 0,

642
00:32:19,200 --> 00:32:22,302
cosa vogliamo inizializzare
il nostro primo valore minimo?

643
00:32:22,302 --> 00:32:22,802
PUBBLICO: i.

644
00:32:22,802 --> 00:32:24,790
ANDI PENG: i, esattamente.

645
00:32:24,790 --> 00:32:27,040
Christabel, perché vogliamo
inizializzare per i?

646
00:32:27,040 --> 00:32:28,510
>> PUBBLICO: Perché, beh,
stiamo iniziando con 0.

647
00:32:28,510 --> 00:32:31,660
Quindi perché non abbiamo nulla da confrontare
a, minimo finirà per essere 0.

648
00:32:31,660 --> 00:32:32,451
>> ANDI PENG: Esattamente.

649
00:32:32,451 --> 00:32:34,400
Quindi lei è esattamente giusto.

650
00:32:34,400 --> 00:32:36,780
Perché non abbiamo in realtà
visto ancora nulla,

651
00:32:36,780 --> 00:32:38,680
non sappiamo qual è il nostro valore minimo è.

652
00:32:38,680 --> 00:32:41,960
Vogliamo inizializzare solo che
i, che, attualmente, è proprio qui.

653
00:32:41,960 --> 00:32:44,750
E mentre continuiamo a
spostare verso il basso questa matrice,

654
00:32:44,750 --> 00:32:48,122
vedremo che, con ogni
passaggio aggiuntivo, i incrementi.

655
00:32:48,122 --> 00:32:49,830
E così a quel punto,
i è probabilmente andando

656
00:32:49,830 --> 00:32:52,329
a voler essere il minimo,
perché sta andando essere quello

657
00:32:52,329 --> 00:32:54,520
è l'inizio della matrice indifferenziati.

658
00:32:54,520 --> 00:32:55,270
Cool.

659
00:32:55,270 --> 00:32:58,720
>> Così ora vogliamo aggiungere
un ciclo for qui che è

660
00:32:58,720 --> 00:33:03,225
andando a scorrere l'
indifferenziati, o il resto di questo array.

661
00:33:03,225 --> 00:33:05,808
Qualcuno ha voglia di darmi una
riga di codice che potrebbe farlo?

662
00:33:05,808 --> 00:33:08,870

663
00:33:08,870 --> 00:33:11,330
Hint-- ciò che abbiamo bisogno qui?

664
00:33:11,330 --> 00:33:17,320

665
00:33:17,320 --> 00:33:18,820
Che cosa sta per andare in questo ciclo for?

666
00:33:18,820 --> 00:33:19,465
Già.

667
00:33:19,465 --> 00:33:21,590
PUBBLICO: Quindi ci piacerebbe
un intero diverso,

668
00:33:21,590 --> 00:33:25,080
perché stiamo correndo per il resto
della matrice anziché i, quindi forse

669
00:33:25,080 --> 00:33:25,760
j.

670
00:33:25,760 --> 00:33:27,301
>> ANDI PENG: Si, j suona bene a me.

671
00:33:27,301 --> 00:33:27,850
Uguale?

672
00:33:27,850 --> 00:33:33,930
>> PUBBLICO: Quindi sarebbe i più 1, perché
si sta iniziando al valore successivo.

673
00:33:33,930 --> 00:33:40,395
E poi al end-- modo nuovo, j è
meno di n meno 1, quindi j ++.

674
00:33:40,395 --> 00:33:41,103
ANDI PENG: Grande.

675
00:33:41,103 --> 00:33:48,510

676
00:33:48,510 --> 00:33:52,750
>> E poi qui, stiamo andando a voler
controllare per vedere se la nostra condizione è soddisfatta,

677
00:33:52,750 --> 00:33:53,250
destra?

678
00:33:53,250 --> 00:33:55,740
Perché si vuole
modificare il valore minimo

679
00:33:55,740 --> 00:33:58,700
se in realtà è più piccolo di quello che
si sta confrontando a, giusto?

680
00:33:58,700 --> 00:34:01,146
Allora, cosa stiamo andando a voler qui?

681
00:34:01,146 --> 00:34:04,160

682
00:34:04,160 --> 00:34:04,897
Controllare per vedere.

683
00:34:04,897 --> 00:34:06,730
Che tipo di istruzione
siamo probabilmente stiamo andando

684
00:34:06,730 --> 00:34:08,389
ti vuole utilizzare se noi
consiglia di controllare qualcosa?

685
00:34:08,389 --> 00:34:09,360
>> PUBBLICO: Un if.

686
00:34:09,360 --> 00:34:10,485
>> ANDI PENG: An if.

687
00:34:10,485 --> 00:34:13,155
Così se: e quello che sta per essere
la condizione che si vuole all'interno

688
00:34:13,155 --> 00:34:13,988
della nostra istruzione if?

689
00:34:13,988 --> 00:34:18,255

690
00:34:18,255 --> 00:34:22,960
>> Pubblico: Se il valore di j
è inferiore al valore di i--

691
00:34:22,960 --> 00:34:24,600
>> ANDI PENG: Esattamente.

692
00:34:24,600 --> 00:34:27,480
Così se: quindi questa matrice si chiama "allineamento".

693
00:34:27,480 --> 00:34:27,980
Grande.

694
00:34:27,980 --> 00:34:30,465
Quindi, se array-- cosa è stato?

695
00:34:30,465 --> 00:34:31,090
Dire ancora una volta che.

696
00:34:31,090 --> 00:34:39,590
>> PUBBLICO: Se array j è minore di
matrice-i, allora avremmo cambiato la min.

697
00:34:39,590 --> 00:34:41,590
Così il minimo sarebbe j.

698
00:34:41,590 --> 00:34:44,590

699
00:34:44,590 --> 00:34:47,249
>> ANDI PENG: Ha senso?

700
00:34:47,249 --> 00:34:48,670
OK.

701
00:34:48,670 --> 00:34:52,929
E ora qui, in realtà
desidera implementare lo scambio, giusto?

702
00:34:52,929 --> 00:34:58,285
Quindi ricorda, in conferenza, che David, quando
stava cercando di scambiare the-- quello che era

703
00:34:58,285 --> 00:34:59,996
succo d'arancia e it-- milk--

704
00:34:59,996 --> 00:35:01,150
>> PUBBLICO: Che era indecente.

705
00:35:01,150 --> 00:35:02,816
>> ANDI PENG: Sì, che era piuttosto disgustoso.

706
00:35:02,816 --> 00:35:05,310
Ma è stato un buon
concetto di tempo dimostrando.

707
00:35:05,310 --> 00:35:08,430
Quindi, pensare dei vostri valori qui.

708
00:35:08,430 --> 00:35:10,794
Hai una matrice
di min, una serie di i,

709
00:35:10,794 --> 00:35:12,460
o quello che stavamo cercando di scambiare qui.

710
00:35:12,460 --> 00:35:15,310
E probabilmente non si possono versare in
l'altro allo stesso tempo, giusto?

711
00:35:15,310 --> 00:35:17,180
Allora, cosa stiamo andando
per necessità di creare qui

712
00:35:17,180 --> 00:35:19,126
al fine di scambiare correttamente i valori?

713
00:35:19,126 --> 00:35:19,820
>> PUBBLICO: Una variabile temporanea.

714
00:35:19,820 --> 00:35:21,370
>> ANDI PENG: Una variabile temporanea.

715
00:35:21,370 --> 00:35:22,570
Allora, facciamo int Temp.

716
00:35:22,570 --> 00:35:25,681
Vedere, questo sarebbe una migliore
tempo a-- whoa, che cosa è stato?

717
00:35:25,681 --> 00:35:26,180
OK.

718
00:35:26,180 --> 00:35:29,800
Quindi questo sarebbe stato una migliore
il tempo di assegnare un nome al "temp." variabile

719
00:35:29,800 --> 00:35:30,730
Allora, facciamo int Temp.

720
00:35:30,730 --> 00:35:32,563
Che cosa stiamo andando a
set temperatura pari a qui?

721
00:35:32,563 --> 00:35:34,752

722
00:35:34,752 --> 00:35:35,335
PUBBLICO: Min?

723
00:35:35,335 --> 00:35:38,508

724
00:35:38,508 --> 00:35:39,716
ANDI PENG: E 'un po' complicato.

725
00:35:39,716 --> 00:35:43,110

726
00:35:43,110 --> 00:35:44,880
In realtà non importa, alla fine.

727
00:35:44,880 --> 00:35:47,690
Non importa quello che
fine si sceglie di scambiare in

728
00:35:47,690 --> 00:35:50,862
a patto che si sta facendo in modo che sei
tenere traccia di ciò che si sta scambiando.

729
00:35:50,862 --> 00:35:52,250
>> PUBBLICO: Potrebbe essere di matrice-i.

730
00:35:52,250 --> 00:35:53,666
>> ANDI PENG: Sì, facciamo matrice-i.

731
00:35:53,666 --> 00:35:55,950

732
00:35:55,950 --> 00:35:59,305
E allora qual è la riga successiva
di codice vogliamo avere qui?

733
00:35:59,305 --> 00:36:00,680
PUBBLICO: array-i è uguale a matrice-j.

734
00:36:00,680 --> 00:36:07,154

735
00:36:07,154 --> 00:36:08,070
ANDI PENG: E infine?

736
00:36:08,070 --> 00:36:12,070
PUBBLICO: array-j è uguale matrice-i.

737
00:36:12,070 --> 00:36:14,525
Pubblico: O array j uguali
array temp-- o, temperatura.

738
00:36:14,525 --> 00:36:17,135

739
00:36:17,135 --> 00:36:19,430
>> ANDI PENG: OK.

740
00:36:19,430 --> 00:36:21,510
Così corriamo questo e vedere
se si tratta di andare a lavorare.

741
00:36:21,510 --> 00:36:37,520

742
00:36:37,520 --> 00:36:39,335
Dove è che accadendo?

743
00:36:39,335 --> 00:36:40,210
Oh, questo è un problema.

744
00:36:40,210 --> 00:36:44,320
Vediamo, sulla linea 40, siamo
cercando di utilizzare array j?

745
00:36:44,320 --> 00:36:47,022
Ma da dove viene j esistere solo in?

746
00:36:47,022 --> 00:36:48,402
>> AUDIENCE: Nel ciclo for.

747
00:36:48,402 --> 00:36:49,110
ANDI PENG: Giusto.

748
00:36:49,110 --> 00:36:51,730
Allora, cosa stiamo andando ad avere bisogno di fare?

749
00:36:51,730 --> 00:36:53,170
>> PUBBLICO: Definire fuori the--

750
00:36:53,170 --> 00:36:57,777

751
00:36:57,777 --> 00:37:00,610
PUBBLICO: Sì, credo che avete
per usare un'altra istruzione if, giusto?

752
00:37:00,610 --> 00:37:05,230
Così come, se il minimum--
tutto bene, fammi pensare.

753
00:37:05,230 --> 00:37:08,170

754
00:37:08,170 --> 00:37:09,990
>> ANDI Peng: Ragazzi, provare
a dare un'occhiata di Let

755
00:37:09,990 --> 00:37:11,270
vediamo, ciò che è qualcosa che possiamo fare qui?

756
00:37:11,270 --> 00:37:11,811
>> PUBBLICO: OK.

757
00:37:11,811 --> 00:37:15,900
Quindi, se il minimo non è uguale
j-- quindi se il minimo è I-- ancora

758
00:37:15,900 --> 00:37:17,570
allora non avremmo da scambiare.

759
00:37:17,570 --> 00:37:22,450

760
00:37:22,450 --> 00:37:24,712
>> ANDI PENG: Fa che la parità io?

761
00:37:24,712 --> 00:37:25,920
Cosa vuoi dire qui?

762
00:37:25,920 --> 00:37:30,494
>> PUBBLICO O sì, se il
minima non è uguale i, sì.

763
00:37:30,494 --> 00:37:39,627

764
00:37:39,627 --> 00:37:40,210
ANDI PENG: OK.

765
00:37:40,210 --> 00:37:42,040
Bene che risolve, specie di, i nostri problemi.

766
00:37:42,040 --> 00:37:47,265
Ma questo ancora non risolve il
problema di cosa succede se j-- dal j

767
00:37:47,265 --> 00:37:49,890
non esiste al di fuori di esso, cosa
cosa ci vuoi fare?

768
00:37:49,890 --> 00:37:50,698
Dichiarare fuori?

769
00:37:50,698 --> 00:37:59,410

770
00:37:59,410 --> 00:38:02,730
Proviamo l'esecuzione di questo.

771
00:38:02,730 --> 00:38:04,435
Uh Oh.

772
00:38:04,435 --> 00:38:06,200
Il nostro ordinamento non funziona.

773
00:38:06,200 --> 00:38:10,060
>> Come potete vedere, la nostra iniziale
matrice aveva quei valori.

774
00:38:10,060 --> 00:38:14,800
E poi dovrebbe avere
stato in 1, 2, 3, 4, 5, 6, 7, 8, 9.

775
00:38:14,800 --> 00:38:15,530
La sua non funziona.

776
00:38:15,530 --> 00:38:16,030
Ahh.

777
00:38:16,030 --> 00:38:17,184
Cosa facciamo?

778
00:38:17,184 --> 00:38:17,850
PUBBLICO: Debug.

779
00:38:17,850 --> 00:38:21,787

780
00:38:21,787 --> 00:38:23,370
ANDI PENG: Va bene, siamo in grado di provare che.

781
00:38:23,370 --> 00:38:25,030
Siamo in grado di eseguire il debug.

782
00:38:25,030 --> 00:38:26,042
Zoom indietro un po '.

783
00:38:26,042 --> 00:38:31,177

784
00:38:31,177 --> 00:38:33,656
Fissiamo il nostro punto di interruzione.

785
00:38:33,656 --> 00:38:37,280
Andiamo like-- OK.

786
00:38:37,280 --> 00:38:40,444
>> Quindi perché già sappiamo che
queste linee, da 15 a 22,

787
00:38:40,444 --> 00:38:43,610
sono working-- perché tutto quello che sto facendo è
solo scorrendo e printing--

788
00:38:43,610 --> 00:38:45,406
Posso andare avanti e saltare quella.

789
00:38:45,406 --> 00:38:47,280
Partiamo alla riga 25.

790
00:38:47,280 --> 00:38:48,712
Oop, mi permetta di ottenere liberarsi di questo.

791
00:38:48,712 --> 00:38:51,598

792
00:38:51,598 --> 00:38:54,057
>> AUDIENCE: Quindi il punto di interruzione
dove ha inizio il debug?

793
00:38:54,057 --> 00:38:54,890
ANDI PENG: o si ferma.

794
00:38:54,890 --> 00:38:55,670
PUBBLICO: o si arresta.

795
00:38:55,670 --> 00:38:55,930
ANDI PENG: Sì.

796
00:38:55,930 --> 00:38:58,640
È possibile impostare più punti di interruzione e
si può semplicemente passare da uno all'altro.

797
00:38:58,640 --> 00:39:01,590
Ma in questo caso non lo sappiamo
dove l'errore sta accadendo.

798
00:39:01,590 --> 00:39:03,780
Quindi vogliamo solo
iniziare dall'alto verso il basso.

799
00:39:03,780 --> 00:39:05,020
Yep.

800
00:39:05,020 --> 00:39:05,550
OK.

801
00:39:05,550 --> 00:39:08,460
>> Così questa linea qui, siamo in grado di intervenire.

802
00:39:08,460 --> 00:39:11,499
Potete vedere qui sotto,
abbiamo un array.

803
00:39:11,499 --> 00:39:13,290
Questi sono i valori
che sono nella matrice.

804
00:39:13,290 --> 00:39:16,360
Vedete che, come indice di 0,
corrisponde al value-- oh,

805
00:39:16,360 --> 00:39:17,526
Io vado a cercare per ingrandire.

806
00:39:17,526 --> 00:39:20,650
Ci dispiace, è davvero difficile
a see-- a indice di matrice 0,

807
00:39:20,650 --> 00:39:24,090
abbiamo un valore di 4 e
allora così via e così via.

808
00:39:24,090 --> 00:39:25,670
Abbiamo le nostre variabili locali.

809
00:39:25,670 --> 00:39:28,570
In questo momento i è uguale a
0, che noi vogliamo che sia.

810
00:39:28,570 --> 00:39:31,540

811
00:39:31,540 --> 00:39:33,690
>> E così teniamo passando attraverso.

812
00:39:33,690 --> 00:39:36,850
Il nostro minimo è uguale a 0,
che anche noi vogliamo che sia.

813
00:39:36,850 --> 00:39:39,470

814
00:39:39,470 --> 00:39:45,560
E allora entriamo nostra seconda per
cappio, se di matrice-j è minore di matrice-i,

815
00:39:45,560 --> 00:39:46,380
che non era.

816
00:39:46,380 --> 00:39:48,130
Così hai visto come
che saltati su questo?

817
00:39:48,130 --> 00:39:52,430
>> PUBBLICO: Quindi, qualora il caso
minimo, tutto che-- non dovrebbe che

818
00:39:52,430 --> 00:39:55,424
essere dentro il primo ciclo for?

819
00:39:55,424 --> 00:39:57,340
ANDI PENG: No, perché
si vuole ancora provare.

820
00:39:57,340 --> 00:40:00,329
Vuoi fare un confronto ogni
tempo, anche dopo aver eseguito attraverso di essa.

821
00:40:00,329 --> 00:40:02,620
Non si vuole solo per farlo
al primo passante.

822
00:40:02,620 --> 00:40:05,240
Si vuole farlo con
ogni passaggio di nuovo supplementare.

823
00:40:05,240 --> 00:40:07,198
Così si vuole verificare la presenza di
la sua condizione all'interno.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Quindi stiamo solo andando a
continuare a correre attraverso qui.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Ti do un suggerimento ragazzi.

828
00:40:18,420 --> 00:40:23,910
Essa ha a che fare con il fatto che quando
si sta controllando la vostra condizione,

829
00:40:23,910 --> 00:40:26,600
non stai controllando
per l'indice corretto.

830
00:40:26,600 --> 00:40:32,510
Così adesso si sta controllando per
indice di campo di j è minore di matrice

831
00:40:32,510 --> 00:40:33,970
indice i.

832
00:40:33,970 --> 00:40:36,580
Ma che cosa stai facendo su a
l'inizio del ciclo for?

833
00:40:36,580 --> 00:40:38,260
Non stai impostando j pari a I?

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Sì, così possiamo realmente
uscire dal debugger qui.

836
00:40:45,415 --> 00:40:47,040
Quindi, diamo uno sguardo al nostro pseudocodice.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
For-- stiamo andando a
partono i è uguale a 0.

839
00:40:52,580 --> 00:40:54,760
Stiamo per andare fino a n meno 1.

840
00:40:54,760 --> 00:40:58,040
Controlliamo, abbiamo dovuto questo diritto?

841
00:40:58,040 --> 00:40:59,580
Sì, quello era giusto.

842
00:40:59,580 --> 00:41:02,080
>> Allora dentro qui, siamo
andando a creare un valore minimo

843
00:41:02,080 --> 00:41:03,630
e impostare che pari a i.

844
00:41:03,630 --> 00:41:04,950
L'abbiamo fatto?

845
00:41:04,950 --> 00:41:06,270
Sì, lo ha fatto.

846
00:41:06,270 --> 00:41:10,430
Ora nel nostro interiore ciclo for, siamo
andando a fare i j è uguale a n 1 meno.

847
00:41:10,430 --> 00:41:11,950
L'abbiamo fatto?

848
00:41:11,950 --> 00:41:15,540
In effetti, abbiamo fatto.

849
00:41:15,540 --> 00:41:19,922
>> Allora però, che cosa stiamo confrontando qui?

850
00:41:19,922 --> 00:41:20,925
>> PUBBLICO: j più 1.

851
00:41:20,925 --> 00:41:21,716
ANDI PENG: Esattamente.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
E poi si sta andando a voler impostare
il vostro minimo pari a j + 1 pure.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Così ho passato che molto velocemente.

856
00:41:32,640 --> 00:41:36,190
Voi ragazzi capiate
perché è j + 1?

857
00:41:36,190 --> 00:41:36,890
OK.

858
00:41:36,890 --> 00:41:40,700
>> Quindi nel tuo array, in
il vostro primo passaggio,

859
00:41:40,700 --> 00:41:44,850
il vostro ciclo for, per int
i è uguale a 0, diciamo solo

860
00:41:44,850 --> 00:41:46,740
assumere questo non è stato ancora cambiata.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
Abbiamo una vasta gamma di, completamente,
solo quattro elementi non ordinati, giusto?

863
00:41:56,760 --> 00:42:00,760
Quindi vogliamo inizializzare i uguale a 0.

864
00:42:00,760 --> 00:42:03,650
E mi sta per solo
correre attraverso questo ciclo.

865
00:42:03,650 --> 00:42:08,560
E così nel primo passaggio, stiamo andando
per inizializzare una variabile chiamata "min"

866
00:42:08,560 --> 00:42:11,245
che è uguale anche io, perché
non abbiamo un valore minimo.

867
00:42:11,245 --> 00:42:12,870
Ecco, questo è attualmente pari a 0 pure.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
E poi stiamo per passare attraverso.

870
00:42:17,640 --> 00:42:19,270
E vogliamo scorrere di nuovo.

871
00:42:19,270 --> 00:42:22,900
Ora che abbiamo trovato ciò che il nostro minimo
è, vogliamo iterare

872
00:42:22,900 --> 00:42:25,190
di nuovo per vedere se è il confronto, giusto?

873
00:42:25,190 --> 00:42:40,440
Così j, qui, sta andando
alla parità di i, che è 0.

874
00:42:40,440 --> 00:42:46,320
E poi se matrice j più i, che
è quello che è eccessivo seguente, come meno

875
00:42:46,320 --> 00:42:49,270
di quello che la tua corrente minima
valore, che si desidera scambiare.

876
00:42:49,270 --> 00:42:56,850
>> Così facciamo solo dire che abbiamo
ottenuto, come, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
In questo momento, i è uguale a
0 e j è uguale a 0.

878
00:43:01,610 --> 00:43:05,210
E questo è il nostro valore minimo.

879
00:43:05,210 --> 00:43:09,950
Se array j più i-- quindi se quello
che è dopo quello che stiamo guardando

880
00:43:09,950 --> 00:43:13,450
è maggiore di quella precedente,
sta andando a diventare il minimo.

881
00:43:13,450 --> 00:43:18,120
>> Quindi, qui vediamo che 5
non è inferiore a quello.

882
00:43:18,120 --> 00:43:19,730
Così sta andando non essere 5.

883
00:43:19,730 --> 00:43:23,580
Vediamo che 1 è inferiore a 2, giusto?

884
00:43:23,580 --> 00:43:32,970
Così ora sappiamo che il nostro minimo è
sarà il valore di indice a 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
Sì?

886
00:43:34,030 --> 00:43:39,170
E poi quando si arriva qui,
è possibile scambiare i valori corretti.

887
00:43:39,170 --> 00:43:42,610
>> Così, quando stavate solo avere la j
prima, non stavate guardando quello

888
00:43:42,610 --> 00:43:43,260
dopo ciò.

889
00:43:43,260 --> 00:43:44,520
Stavi guardando
lo stesso valore, che

890
00:43:44,520 --> 00:43:46,290
è perché semplicemente non stava facendo nulla.

891
00:43:46,290 --> 00:43:49,721
Questo fa senso a tutti,
perché abbiamo bisogno che più 1 lì?

892
00:43:49,721 --> 00:43:50,220
OK.

893
00:43:50,220 --> 00:43:53,345
Ora facciamo solo attraversano per renderlo
che il resto del codice è corretto.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
Perché è quella accadendo?

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Ah, è il minimo qui.

898
00:44:16,364 --> 00:44:17,780
Stavamo confrontando il valore errato.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
Oh no.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> Oh sì, qui siamo stati
scambiando i valori errati pure.

903
00:44:33,482 --> 00:44:34,940
Perché stavamo guardando i e j.

904
00:44:34,940 --> 00:44:36,440
Questi sono quelli che stavano controllando.

905
00:44:36,440 --> 00:44:39,160
Noi in realtà vogliamo scambiare la
minimo, la corrente minima,

906
00:44:39,160 --> 00:44:40,550
con qualunque quella esterna è.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
E come voi potete vedere giù
qui, abbiamo un array ordinato.

909
00:45:05,402 --> 00:45:07,110
E 'appena avuto a che fare con
il fatto che quando

910
00:45:07,110 --> 00:45:09,350
ci siamo registrati il
valori stavamo confrontando,

911
00:45:09,350 --> 00:45:11,226
noi non stavamo guardando i giusti valori.

912
00:45:11,226 --> 00:45:13,850
Stavamo cercando allo stesso
qui, in realtà non lo scambio di esso.

913
00:45:13,850 --> 00:45:17,135
Bisogna guardare quello vicino
ad esso e quindi è possibile scambiare.

914
00:45:17,135 --> 00:45:19,260
Ed è quello che era una sorta di
intercettazioni nostro codice prima.

915
00:45:19,260 --> 00:45:22,460
E quello che ho fatto qui è tutto
il debugger avrebbe potuto fare per voi

916
00:45:22,460 --> 00:45:23,810
Ho appena fatto sul
bordo, perché è più facile

917
00:45:23,810 --> 00:45:26,320
per vedere piuttosto che cercare
per ingrandire il debugger.

918
00:45:26,320 --> 00:45:29,391
Questo fa senso a tutti?

919
00:45:29,391 --> 00:45:29,890
Cool.

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> Tutto ok.

922
00:45:35,410 --> 00:45:41,070
Siamo in grado di passare a parlare
Notazione asintotica, che

923
00:45:41,070 --> 00:45:44,580
è solo un modo elegante per dire la
tempi di esecuzione di tutti questi tipi.

924
00:45:44,580 --> 00:45:47,650
Quindi so Davide, in conferenza,
toccato runtime.

925
00:45:47,650 --> 00:45:52,124
E andò per tutta la formula
di come calcolare i tempi di esecuzione.

926
00:45:52,124 --> 00:45:53,040
Nessuna preoccupazione circa che.

927
00:45:53,040 --> 00:45:54,660
Se siete veramente curiosi
su come funziona,

928
00:45:54,660 --> 00:45:55,810
sentitevi liberi di parlare con me dopo la sezione.

929
00:45:55,810 --> 00:45:57,560
Siamo in grado di camminare attraverso
le formule insieme.

930
00:45:57,560 --> 00:46:00,689
Ma tutti voi ragazzi avete veramente
sapere è che n quadrato oltre 2

931
00:46:00,689 --> 00:46:01,980
è la stessa cosa di n quadrato.

932
00:46:01,980 --> 00:46:04,710
Poiché il numero maggiore,
l'esponente, cresce più.

933
00:46:04,710 --> 00:46:06,590
E così per i nostri scopi,
tutto ci preoccupiamo

934
00:46:06,590 --> 00:46:09,470
è che il numero gigante che sta crescendo.

935
00:46:09,470 --> 00:46:13,340
>> Allora, qual è il caso migliore
tempo di esecuzione dell'ordinamento per selezione?

936
00:46:13,340 --> 00:46:15,830
Se avete intenzione di avere
per scorrere una lista

937
00:46:15,830 --> 00:46:18,712
e poi scorrere
il resto di tale elenco,

938
00:46:18,712 --> 00:46:20,420
quante volte sono
hai intenzione di probabilmente,

939
00:46:20,420 --> 00:46:24,612
nel peggiore case-- nel
caso migliore, sorry-- percorrere?

940
00:46:24,612 --> 00:46:27,070
Forse la domanda migliore è
di chiedere, qual è il caso peggiore

941
00:46:27,070 --> 00:46:28,153
tempo di esecuzione dell'ordinamento per selezione.

942
00:46:28,153 --> 00:46:29,366
PUBBLICO: n al quadrato.

943
00:46:29,366 --> 00:46:30,740
ANDI PENG: E 'n al quadrato, destra.

944
00:46:30,740 --> 00:46:36,986
Quindi, un modo semplice per pensare a questo è come,
ogni volta che si hanno due cicli for nidificati,

945
00:46:36,986 --> 00:46:38,110
che sta per essere n quadrato.

946
00:46:38,110 --> 00:46:40,386
Perché non solo si sono
che attraversa una volta,

947
00:46:40,386 --> 00:46:42,260
si deve andare indietro
intorno e correre attraverso di essa

948
00:46:42,260 --> 00:46:44,980
nuovamente all'interno per ogni valore.

949
00:46:44,980 --> 00:46:48,640
Quindi, in questo caso, si sta eseguendo n
n volte quadrato, che è-- mi dispiace,

950
00:46:48,640 --> 00:46:50,505
n volte n, che è uguale al quadrato n.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> Ed è sorta anche un po '
unica nel senso

953
00:46:56,360 --> 00:46:59,774
che non importa se questi
I valori sono già in ordine.

954
00:46:59,774 --> 00:47:01,440
E 'ancora in corso a correre attraverso comunque.

955
00:47:01,440 --> 00:47:03,872
Diciamo solo che questo è stato di 1, 2, 3, 4.

956
00:47:03,872 --> 00:47:07,080
Indipendentemente dal fatto che o non era in
ordine, ancora sarebbe correva attraverso

957
00:47:07,080 --> 00:47:08,620
e ancora controllato il valore minimo.

958
00:47:08,620 --> 00:47:10,100
Avrebbe fatto il
stesso numero di controlli

959
00:47:10,100 --> 00:47:12,780
ogni volta, anche se
in realtà non toccare nulla.

960
00:47:12,780 --> 00:47:16,940
>> Quindi, in questo caso, i migliori e peggiori
tempi di esecuzione sono in realtà equivalenti.

961
00:47:16,940 --> 00:47:19,160
Così il runtime previsto
di ordinamento per selezione,

962
00:47:19,160 --> 00:47:23,790
che noi chiamiamo con il simbolo
di theta, theta, in questo caso,

963
00:47:23,790 --> 00:47:24,790
sarebbe anche n quadrato.

964
00:47:24,790 --> 00:47:26,480
Tutti e tre di questi sarebbero n quadrato.

965
00:47:26,480 --> 00:47:29,653
È tutto chiaro il motivo
il runtime è n quadrato?

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> Tutto ok.

968
00:47:33,980 --> 00:47:39,120
Così sto solo andando a correre velocemente
per il resto delle specie.

969
00:47:39,120 --> 00:47:41,137
L'algoritmo per
bolla sort-- ricordo,

970
00:47:41,137 --> 00:47:43,220
questo è stato il primo
Davide passò in conferenza.

971
00:47:43,220 --> 00:47:46,000
In sostanza, fate un passo
attraverso l'intera lista

972
00:47:46,000 --> 00:47:48,950
e tu hai appena swap--
confrontare due alla volta.

973
00:47:48,950 --> 00:47:51,350
E se uno è più grande,
quanto basta scambiarli.

974
00:47:51,350 --> 00:47:53,590
Quindi, se questi sono maggiori, si potrebbe scambiare.

975
00:47:53,590 --> 00:47:56,180
Ho ufficiale proprio qui.

976
00:47:56,180 --> 00:47:59,100
>> Così facciamo solo dire hai avuto 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Faresti confronta il 8 ed un 6.

978
00:48:00,571 --> 00:48:01,570
Avresti bisogno di scambiarle.

979
00:48:01,570 --> 00:48:02,610
Si potrebbe confrontare l'8 e 4.

980
00:48:02,610 --> 00:48:03,609
Avresti bisogno di scambiarle.

981
00:48:03,609 --> 00:48:07,000
Se si deve scambiare l'8 e
il 2, cambiare loro.

982
00:48:07,000 --> 00:48:10,760
Quindi, in un senso, si può vedere,
svolto su un lungo periodo di tempo,

983
00:48:10,760 --> 00:48:13,730
come i valori tipo di bolla per
le estremità, che è per questo che lo chiamano

984
00:48:13,730 --> 00:48:15,320
bubble sort.

985
00:48:15,320 --> 00:48:19,950
>> Ci sarebbe solo correre attraverso di nuovo su
il nostro secondo passaggio, e il nostro terzo passaggio,

986
00:48:19,950 --> 00:48:21,150
e il nostro quarto passaggio.

987
00:48:21,150 --> 00:48:25,820
In sostanza, bubble sort corre solo
fino a quando non apportare più swap.

988
00:48:25,820 --> 00:48:31,109
In questo senso, questo è solo
pseudocodice generale per esso.

989
00:48:31,109 --> 00:48:32,650
Nessun problema, questi saranno on-line tutti.

990
00:48:32,650 --> 00:48:34,990
Non abbiamo di andare effettivamente su questo.

991
00:48:34,990 --> 00:48:38,134
>> Abbiamo appena inizializzato un contatore
variabile che parte da 0.

992
00:48:38,134 --> 00:48:39,800
E noi scorrere l'intero array.

993
00:48:39,800 --> 00:48:43,420
E se un valore è-- se questo
valore è maggiore di tale valore,

994
00:48:43,420 --> 00:48:44,610
si sta andando a scambiarle.

995
00:48:44,610 --> 00:48:46,860
E poi sei solo
intenzione di andare avanti.

996
00:48:46,860 --> 00:48:47,970
E si sta andando a contare.

997
00:48:47,970 --> 00:48:50,845
E hai intenzione di continuare a fare
questo mentre il contatore è maggiore

998
00:48:50,845 --> 00:48:53,345
a 0, il che significa che
ogni volta che si deve scambiare,

999
00:48:53,345 --> 00:48:55,220
si sa che si vuole andare
indietro e prova di nuovo.

1000
00:48:55,220 --> 00:48:59,510
Si desidera mantenere il controllo finché non si sa
che non c'è bisogno di scambiare più.

1001
00:48:59,510 --> 00:49:05,570
>> Ma quali sono i migliori e peggiori
caso Runtime da bubble sort?

1002
00:49:05,570 --> 00:49:09,300
E hint-- questo è in realtà diverso
dalla selezione specie nel senso

1003
00:49:09,300 --> 00:49:11,810
che queste due risposte non sono gli stessi.

1004
00:49:11,810 --> 00:49:14,709
Pensate a cosa sarebbe successo in
un caso se è stato già risolto.

1005
00:49:14,709 --> 00:49:16,500
E pensare a ciò che
cosa accadrebbe se fosse

1006
00:49:16,500 --> 00:49:18,372
nel caso in cui non è stato risolto.

1007
00:49:18,372 --> 00:49:20,580
E si può sorta di eseguire
attraverso il motivo che sta succedendo.

1008
00:49:20,580 --> 00:49:22,954
Ti darò ragazzi, come, 30
secondi per pensarci.

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> OK.

1011
00:49:53,540 --> 00:49:57,462
Qualcuno ha una supposizione a ciò che il
caso peggiore runtime di bubble sort è?

1012
00:49:57,462 --> 00:49:57,962
Già.

1013
00:49:57,962 --> 00:50:07,810
>> PUBBLICO: Sarebbe, come, n volte
n meno 1 o qualcosa del genere?

1014
00:50:07,810 --> 00:50:10,650
Come, ogni volta che viene eseguito,
è proprio, come, uno scambio meno

1015
00:50:10,650 --> 00:50:10,960
che qualunque cosa fosse.

1016
00:50:10,960 --> 00:50:12,668
>> ANDI PENG: Sì, così
sei completamente a destra.

1017
00:50:12,668 --> 00:50:15,940
E questo è un caso in cui la vostra
risposta era in realtà più complessa

1018
00:50:15,940 --> 00:50:17,240
di quello che dobbiamo dare.

1019
00:50:17,240 --> 00:50:19,772
Così sta andando a run-- Sono
andando a cancellare tutto questo qui.

1020
00:50:19,772 --> 00:50:20,480
Sono tutti buoni?

1021
00:50:20,480 --> 00:50:21,869
Posso cancellare questo?

1022
00:50:21,869 --> 00:50:22,368
OK.

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
Stai andando a correre attraverso n
volte la prima volta, giusto?

1025
00:50:30,320 --> 00:50:33,200
E che stanno andando a correre attraverso
n meno 1 per la seconda volta, giusto?

1026
00:50:33,200 --> 00:50:37,130
E poi si sta andando a mantenere
andare, il mio n 2, eccetera.

1027
00:50:37,130 --> 00:50:40,210
David ha fatto questo in una conferenza, dove,
se si aggiungono tutti quei valori,

1028
00:50:40,210 --> 00:50:48,080
si ottiene qualcosa che è like-- yeah--
su 2, che sostanzialmente si riduce solo

1029
00:50:48,080 --> 00:50:49,784
fino a n quadrato.

1030
00:50:49,784 --> 00:50:51,700
Stai andando a ottenere un
frazione strano in là.

1031
00:50:51,700 --> 00:50:53,892
E così è sufficiente sapere che
il n quadrato sempre

1032
00:50:53,892 --> 00:50:55,350
ha la precedenza sulla frazione.

1033
00:50:55,350 --> 00:50:58,450
E così in questo caso, la peggiore
runtime sarebbe n al quadrato.

1034
00:50:58,450 --> 00:51:00,210
Se era in decrescente
ordine, pensare, voi

1035
00:51:00,210 --> 00:51:02,530
devono fare uno swap ogni singola volta.

1036
00:51:02,530 --> 00:51:05,170
>> Quale sarebbe, potenzialmente,
il miglior tempo di esecuzione caso?

1037
00:51:05,170 --> 00:51:08,580
Diciamo solo che, se la lista era già
in ordine, quale sarebbe il runtime essere?

1038
00:51:08,580 --> 00:51:09,565
>> PUBBLICO: n.

1039
00:51:09,565 --> 00:51:10,690
ANDI PENG: E 'n, esattamente.

1040
00:51:10,690 --> 00:51:11,600
E perché è n?

1041
00:51:11,600 --> 00:51:13,850
PUBBLICO: Perché hai appena
devono controllare ogni volta.

1042
00:51:13,850 --> 00:51:14,770
ANDI PENG: Esattamente.

1043
00:51:14,770 --> 00:51:17,150
Così nel miglior runtime possibile,
se questa lista era già

1044
00:51:17,150 --> 00:51:20,270
sorted-- diciamo 1, 2, 3, 4-- voi
sarebbe solo passare attraverso, si potrebbe verificare,

1045
00:51:20,270 --> 00:51:21,720
si dovrebbe vedere, oh, tutti pan.

1046
00:51:21,720 --> 00:51:22,636
Non ho avuto da scambiare.

1047
00:51:22,636 --> 00:51:23,370
Ho finito.

1048
00:51:23,370 --> 00:51:26,500
Quindi, in questo caso, è solo n
o il numero di passi che solo

1049
00:51:26,500 --> 00:51:29,870
dovuto controllare nel primo elenco.

1050
00:51:29,870 --> 00:51:33,990
>> E dopo, ora ha colpito
insertion sort, dove

1051
00:51:33,990 --> 00:51:39,260
l'algoritmo è essenzialmente divide
in una porzione ordinato e non ordinato.

1052
00:51:39,260 --> 00:51:42,810
E poi uno per uno,
i valori sono sottoposti a cernita

1053
00:51:42,810 --> 00:51:46,880
inserito nella loro appropriata
posizioni nella all'inizio della lista.

1054
00:51:46,880 --> 00:51:52,120
>> Così, per esempio, abbiamo un
elenco di 3, 5, 2, 6, 4 di nuovo.

1055
00:51:52,120 --> 00:51:54,750
Sappiamo che è attualmente
indifferenziati perché abbiamo solo

1056
00:51:54,750 --> 00:51:57,030
iniziato a guardarla.

1057
00:51:57,030 --> 00:52:00,610
Diamo un'occhiata e sappiamo che
il primo valore viene ordinato, giusto?

1058
00:52:00,610 --> 00:52:04,190
Se stai cercando solo in una serie di
formato uno, sai che è ordinato.

1059
00:52:04,190 --> 00:52:08,230
>> Allora sappiamo che la
altre quattro sono indifferenziati.

1060
00:52:08,230 --> 00:52:10,980
Andiamo attraverso e vediamo che il valore.

1061
00:52:10,980 --> 00:52:11,730
Torniamo indietro.

1062
00:52:11,730 --> 00:52:13,130
Vedere quel valore di 5?

1063
00:52:13,130 --> 00:52:14,110
Diamo un'occhiata a questo.

1064
00:52:14,110 --> 00:52:15,204
Confrontiamo a 3.

1065
00:52:15,204 --> 00:52:17,870
Sappiamo che è più grande di
3, quindi sappiamo che questo è risolto.

1066
00:52:17,870 --> 00:52:22,940
Così ora sappiamo che i primi due
vengono ordinati e gli ultimi tre non lo sono.

1067
00:52:22,940 --> 00:52:24,270
>> Diamo un'occhiata alle 2.

1068
00:52:24,270 --> 00:52:25,720
Per prima cosa controlliamo con 5.

1069
00:52:25,720 --> 00:52:26,700
È meno di 5?

1070
00:52:26,700 --> 00:52:27,240
Non è.

1071
00:52:27,240 --> 00:52:29,510
Quindi dobbiamo continuare a guardare verso il basso.

1072
00:52:29,510 --> 00:52:30,940
Poi si controlla 2 fuori 3.

1073
00:52:30,940 --> 00:52:31,850
E 'meno?

1074
00:52:31,850 --> 00:52:32,350
No.

1075
00:52:32,350 --> 00:52:35,430
Quindi conoscere un 2 deve essere inserito
nella parte anteriore e 3 e 5

1076
00:52:35,430 --> 00:52:38,200
entrambi devono essere spinto fuori.

1077
00:52:38,200 --> 00:52:42,190
Farlo di nuovo con 6 e 4.

1078
00:52:42,190 --> 00:52:48,962
E abbiamo appena mantenere il controllo in sostanza,
dove abbiamo appena controlliamo, controllare, controllare.

1079
00:52:48,962 --> 00:52:51,170
E fino a quando è nel giusto
posizione, abbiamo tipo solo

1080
00:52:51,170 --> 00:52:54,890
inserirla nella giusta posizione,
che è dove il nome di provenienza.

1081
00:52:54,890 --> 00:52:59,830
>> Ecco, questo è solo l'algoritmo,
pseudocodice di per sé, un po ',

1082
00:52:59,830 --> 00:53:04,990
su come avremmo implementare
un insertion sort.

1083
00:53:04,990 --> 00:53:05,954
Pseudocodice è qui.

1084
00:53:05,954 --> 00:53:06,620
E 'tutto on-line.

1085
00:53:06,620 --> 00:53:10,720
Nessun problema se voi ragazzi siete
cercando di copiare questo giù.

1086
00:53:10,720 --> 00:53:14,500
Così ancora una volta, la stessa cosa interrogo
sarebbe la migliore e peggiori tempi di esecuzione

1087
00:53:14,500 --> 00:53:16,120
per insertion sort?

1088
00:53:16,120 --> 00:53:17,750
E 'molto simile all'ultima domanda.

1089
00:53:17,750 --> 00:53:20,479
Ti darò ragazzi, come, 30
secondi per pensare a questo.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> OK Qualcuno ha voglia di
dammi il runtime peggiore?

1092
00:53:50,071 --> 00:53:50,570
Già.

1093
00:53:50,570 --> 00:53:51,490
>> PUBBLICO: n al quadrato.

1094
00:53:51,490 --> 00:53:52,573
>> ANDI PENG: E 'n al quadrato.

1095
00:53:52,573 --> 00:53:53,730
E perché è n quadrato?

1096
00:53:53,730 --> 00:53:57,562
>> PUBBLICO: Perché in
ordine inverso, si ha

1097
00:53:57,562 --> 00:54:02,619
passare attraverso n volte n, che è--

1098
00:54:02,619 --> 00:54:03,660
ANDI PENG: Sì, esattamente.

1099
00:54:03,660 --> 00:54:06,610
Così stessa cosa come nel bubble sort.

1100
00:54:06,610 --> 00:54:08,720
Se questa lista è in
ordine decrescente, sei

1101
00:54:08,720 --> 00:54:11,240
andando a controllare la prima volta.

1102
00:54:11,240 --> 00:54:13,470
E poi con ogni
valore aggiunto, sei

1103
00:54:13,470 --> 00:54:16,390
andando ad avere per verificare il rispetto
ogni singolo valore, giusto?

1104
00:54:16,390 --> 00:54:20,290
E così tutto, si sta andando a fare
una volte n passa un altro n passano, che

1105
00:54:20,290 --> 00:54:21,750
è n quadrato.

1106
00:54:21,750 --> 00:54:22,860
Che cosa circa il caso migliore?

1107
00:54:22,860 --> 00:54:24,360
Già.

1108
00:54:24,360 --> 00:54:28,840
>> Pubblico: n meno 1, perché la
prima è già quadrato.

1109
00:54:28,840 --> 00:54:30,270
>> ANDI PENG: Quindi, chiudere.

1110
00:54:30,270 --> 00:54:31,850
La risposta è in realtà n.

1111
00:54:31,850 --> 00:54:37,189
Perché mentre il primo è
ordinato, non può che actually--

1112
00:54:37,189 --> 00:54:38,980
siamo appena stati fortunati, in
questo esempio, che 2

1113
00:54:38,980 --> 00:54:40,930
è capitato di essere il numero più piccolo.

1114
00:54:40,930 --> 00:54:43,680
Ma non sarà sempre così.

1115
00:54:43,680 --> 00:54:48,040
Se 2 è già ordinati all'inizio
ma si guarda e c'è un 1 qui,

1116
00:54:48,040 --> 00:54:49,144
il 1 sta per urtarla.

1117
00:54:49,144 --> 00:54:51,060
E sta andando a finire
per essere urtato comunque.

1118
00:54:51,060 --> 00:54:56,250
>> Così nel migliore dei casi,
in realtà è solo andare a essere n.

1119
00:54:56,250 --> 00:54:59,090
Se si dispone di 1, 2, 3,
4, 5, 6, 7, 8, sei

1120
00:54:59,090 --> 00:55:00,940
andando a correre attraverso
che tutta la lista una volta

1121
00:55:00,940 --> 00:55:03,430
per controllare per vedere se va tutto bene.

1122
00:55:03,430 --> 00:55:07,390
E 'chiaro a tutti a correre
tempi di selezione come pure?

1123
00:55:07,390 --> 00:55:09,960
So che sto passando
questi veramente veloce.

1124
00:55:09,960 --> 00:55:13,330
Ma basta sapere che se si conosce la
concetti generali, si dovrebbe essere buona.

1125
00:55:13,330 --> 00:55:16,070
OK.

1126
00:55:16,070 --> 00:55:19,790
Quindi mi limiterò a darvi ragazzi forse, come,
un minuto per parlare con i vostri vicini

1127
00:55:19,790 --> 00:55:21,890
su quelle che sono solo alcuni
delle differenze principali

1128
00:55:21,890 --> 00:55:23,540
tra questi tipi di sorta.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
Andremo oltre che presto.

1131
00:56:25,570 --> 00:56:26,444
PUBBLICO: Oh, OK.

1132
00:56:26,444 --> 00:56:27,320
ANDI PENG: Sì.

1133
00:56:27,320 --> 00:56:28,380
OK.

1134
00:56:28,380 --> 00:56:33,420
Fresco, cerchiamo di riconvocare come classe.

1135
00:56:33,420 --> 00:56:34,330
OK.

1136
00:56:34,330 --> 00:56:37,579
Quindi questa è stata una specie di
domanda a risposta aperta, nel senso

1137
00:56:37,579 --> 00:56:39,120
che c'è un sacco di risposte.

1138
00:56:39,120 --> 00:56:40,746
E andremo su alcuni di loro brevemente.

1139
00:56:40,746 --> 00:56:43,411
Volevo solo farti ragazzi
pensando a quello differenziato

1140
00:56:43,411 --> 00:56:44,530
tutti e tre i tipi di sorta.

1141
00:56:44,530 --> 00:56:47,440
E ho sentito, anche, un grande
interrogo ciò che merge sort fare?

1142
00:56:47,440 --> 00:56:50,110
Grande questione, perché è
quello che stiamo coprendo prossimo.

1143
00:56:50,110 --> 00:56:52,850
>> Così merge sort è il
un tipo che funziona

1144
00:56:52,850 --> 00:56:56,100
in modo molto diverso dagli altri tipi.

1145
00:56:56,100 --> 00:56:58,180
Come voi potete see--
fece Davide che demo

1146
00:56:58,180 --> 00:57:01,130
dove ha avuto tutto il fresco
rumori di vedere come unire

1147
00:57:01,130 --> 00:57:04,010
specie corse, come infinitamente
più veloce rispetto agli altri due tipi?

1148
00:57:04,010 --> 00:57:04,510
OK.

1149
00:57:04,510 --> 00:57:07,580
Ecco, questo è perché merge
sorta implementa che divide

1150
00:57:07,580 --> 00:57:11,020
e conquistare il concetto che abbiamo
parlato molto in conferenza.

1151
00:57:11,020 --> 00:57:14,550
In questo senso che ci piace lavorare
più intelligente, non di più, quando si divide

1152
00:57:14,550 --> 00:57:18,120
e conquistare i problemi, e romperli
giù, e poi metterli insieme,

1153
00:57:18,120 --> 00:57:19,930
buone cose accadono sempre.

1154
00:57:19,930 --> 00:57:21,960
>> Quindi il modo che si fondono
lavori sorta essenzialmente

1155
00:57:21,960 --> 00:57:24,660
è che divide un
matrice indifferenziati a metà.

1156
00:57:24,660 --> 00:57:26,500
E poi è ottenuto due metà di array.

1157
00:57:26,500 --> 00:57:28,220
E ordina solo quei due metà.

1158
00:57:28,220 --> 00:57:31,750
Si continua a dividere a metà, in
mezzo, a metà fino a quando tutto è ordinato

1159
00:57:31,750 --> 00:57:33,680
e quindi in modo ricorsivo
mette tutto insieme.

1160
00:57:33,680 --> 00:57:36,550
>> Ecco, questo è davvero astratto.

1161
00:57:36,550 --> 00:57:38,750
Quindi questo è solo un po 'di pseudocodice.

1162
00:57:38,750 --> 00:57:41,040
Questo fa senso in
il modo in cui è in esecuzione?

1163
00:57:41,040 --> 00:57:43,870
Quindi diciamo solo che si dispone di un
array di n elementi, giusto?

1164
00:57:43,870 --> 00:57:45,450
Se n è inferiore a 2, si può tornare.

1165
00:57:45,450 --> 00:57:49,040
Perché sai che se c'è
solo una cosa, deve essere ordinata.

1166
00:57:49,040 --> 00:57:52,600
Altrimenti, si ordina la metà sinistra,
e poi si ordina la metà di destra,

1167
00:57:52,600 --> 00:57:54,140
e poi si uniscono.

1168
00:57:54,140 --> 00:57:56,979
>> Così, mentre che sembra davvero semplice,
in realtà, a pensarci è

1169
00:57:56,979 --> 00:58:00,270
piuttosto difficile. Perché tu sei come,
Beh, questo è tipo di esecuzione su se stessa.

1170
00:58:00,270 --> 00:58:00,769
Destra?

1171
00:58:00,769 --> 00:58:02,430
E 'in esecuzione su se stessa.

1172
00:58:02,430 --> 00:58:05,479
Quindi, in questo senso, David toccato
su ricorsione in classe.

1173
00:58:05,479 --> 00:58:07,270
E questo è un concetto
parleremo di più.

1174
00:58:07,270 --> 00:58:11,430
E 'questo che, queste due linee
qui, in realtà è solo il programma

1175
00:58:11,430 --> 00:58:13,860
dicendogli di correre stesso
con ingresso differente.

1176
00:58:13,860 --> 00:58:17,230
Quindi, piuttosto che correre con sé
l'insieme di n elementi,

1177
00:58:17,230 --> 00:58:20,530
è possibile abbattere in la
metà sinistra e la metà destra

1178
00:58:20,530 --> 00:58:22,680
e quindi eseguirlo di nuovo.

1179
00:58:22,680 --> 00:58:26,050
>> E poi vedremo visivamente,
perché io sono uno studente visivo.

1180
00:58:26,050 --> 00:58:27,270
Funziona meglio per me.

1181
00:58:27,270 --> 00:58:29,890
Così vedremo un esempio visivo qui.

1182
00:58:29,890 --> 00:58:36,237
>> Diciamo che abbiamo un array, sei
elementi, 3, 5, 2, 6, 4, 1, non filtrate.

1183
00:58:36,237 --> 00:58:37,820
Va bene, c'è molto in questa pagina.

1184
00:58:37,820 --> 00:58:43,179
Quindi, se voi potete guardare il
primo passo qui, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
è possibile dividere a metà.

1186
00:58:44,220 --> 00:58:45,976
Hai 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
Voi sapete che queste si aren't--
Non so se sono ordinati o no,

1188
00:58:48,850 --> 00:58:52,517
in modo da mantenere la rottura giù, in mezzo,
a metà, a metà, fino alla fine,

1189
00:58:52,517 --> 00:58:53,600
si dispone di un solo elemento.

1190
00:58:53,600 --> 00:58:56,790
E un elemento è sempre ordinato, giusto?

1191
00:58:56,790 --> 00:59:01,560
>> Così sappiamo che il 3, 5, 2, 4, 6,
1, da soli, sono ordinati.

1192
00:59:01,560 --> 00:59:05,870
E ora siamo in grado di rimetterli insieme.

1193
00:59:05,870 --> 00:59:07,510
Così sappiamo il 3, 5.

1194
00:59:07,510 --> 00:59:08,510
Abbiamo messo insieme quelli.

1195
00:59:08,510 --> 00:59:09,617
Sappiamo che è ordinato.

1196
00:59:09,617 --> 00:59:10,450
I 2 è ancora lì.

1197
00:59:10,450 --> 00:59:11,830
Siamo in grado di mettere il 4 e il 6 insieme.

1198
00:59:11,830 --> 00:59:13,996
Sappiamo che questo è risolto,
così abbiamo messo che, insieme.

1199
00:59:13,996 --> 00:59:14,940
E il 1 c'è.

1200
00:59:14,940 --> 00:59:18,720
>> E poi basta guardare
queste due metà proprio qui.

1201
00:59:18,720 --> 00:59:21,300
Avete il 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Si può solo confrontare la
inizio di tutto.

1203
00:59:23,465 --> 00:59:26,340
Perché si sa che questo è ordinato
e si sa che questo è risolto.

1204
00:59:26,340 --> 00:59:29,360
Allora non c'è nemmeno bisogno di
confrontare il 5, basta confrontare il 3.

1205
00:59:29,360 --> 00:59:32,070
E il 2 è inferiore a 3, così
sai 2 deve andare alla fine.

1206
00:59:32,070 --> 00:59:33,120
>> Stessa cosa là.

1207
00:59:33,120 --> 00:59:34,740
Il 1 deve andare qui.

1208
00:59:34,740 --> 00:59:37,330
E poi quando si va a mettere
questi due valori,

1209
00:59:37,330 --> 00:59:39,950
si sa che questo è ordinato e
si sa che quello è ordinato.

1210
00:59:39,950 --> 00:59:43,240
Allora l'1 e il
2, la 1 è inferiore a 2.

1211
00:59:43,240 --> 00:59:45,570
Che ti dice che il 1
dovrebbe andare alla fine di questo

1212
00:59:45,570 --> 00:59:47,480
senza nemmeno guardare 3 o 5.

1213
00:59:47,480 --> 00:59:50,100
E poi il 4, si può solo
controllare, va bene qui.

1214
00:59:50,100 --> 00:59:51,480
Non c'è bisogno di guardare il 5.

1215
00:59:51,480 --> 00:59:52,570
Stessa cosa con il 6.

1216
00:59:52,570 --> 00:59:55,860
Voi sapete che il 6-- solo
non ha bisogno di essere guardato.

1217
00:59:55,860 --> 00:59:57,870
>> E così in questo modo, sei
solo risparmiando

1218
00:59:57,870 --> 00:59:59,526
un sacco di passi quando si sta confrontando.

1219
00:59:59,526 --> 01:00:02,150
Non c'è bisogno di confrontare ogni
elemento contro altri elementi.

1220
01:00:02,150 --> 01:00:05,230
Basta confrontare contro quelli
che è necessario confrontare contro.

1221
01:00:05,230 --> 01:00:06,870
Ecco, questo è tipo di un concetto astratto.

1222
01:00:06,870 --> 01:00:10,540
Non preoccuparti se non è
piuttosto si colpendo a destra ancora.

1223
01:00:10,540 --> 01:00:14,740
Ma in generale, questo è
come un merge sort funziona.

1224
01:00:14,740 --> 01:00:17,750
Domande, domande veloci,
prima di passare?

1225
01:00:17,750 --> 01:00:18,550
Già.

1226
01:00:18,550 --> 01:00:22,230
>> PUBBLICO: Quindi lei ha detto che si prende
1, e quindi il 4 e il 6

1227
01:00:22,230 --> 01:00:23,860
e metterli in.

1228
01:00:23,860 --> 01:00:26,800
Quindi non sono those-- non sono
si guardarli

1229
01:00:26,800 --> 01:00:28,544
come elementi separati, non come l'intero?

1230
01:00:28,544 --> 01:00:29,210
ANDI PENG: Sì.

1231
01:00:29,210 --> 01:00:32,020
Allora, cosa sta succedendo
è che è fondamentalmente

1232
01:00:32,020 --> 01:00:33,650
stanno creando una nuova matrice di zecca.

1233
01:00:33,650 --> 01:00:36,690
Così si sa che, qui, ho
due array di dimensioni 3, giusto?

1234
01:00:36,690 --> 01:00:39,600
Così si sa che il mio array ordinato
deve avere sei elementi.

1235
01:00:39,600 --> 01:00:42,270
Quindi basta creare un
nuova quantità di memoria.

1236
01:00:42,270 --> 01:00:44,270
Quindi sei un po 'come
sperperare della memoria,

1237
01:00:44,270 --> 01:00:46,186
ma questo non ha importanza
perché è così piccolo.

1238
01:00:46,186 --> 01:00:48,590
Quindi si guarda al 1
e si guarda al 2.

1239
01:00:48,590 --> 01:00:50,770
E si sa che la 1 è inferiore a 2.

1240
01:00:50,770 --> 01:00:53,840
Così si sa che uno dovrebbe andare a
l'inizio di tutte quelle.

1241
01:00:53,840 --> 01:00:55,850
>> Non c'è nemmeno bisogno di
guardare il 3 e il 5.

1242
01:00:55,850 --> 01:00:57,400
Allora sai 1 va là.

1243
01:00:57,400 --> 01:00:59,300
Poi è fondamentalmente recidere la 1.

1244
01:00:59,300 --> 01:01:00,370
E ', come, morto per noi.

1245
01:01:00,370 --> 01:01:03,690
Poi dobbiamo solo 2,
3, 5, e quindi 4 e 6.

1246
01:01:03,690 --> 01:01:06,270
E poi si sa che, si
confrontare il 4 e 2,

1247
01:01:06,270 --> 01:01:07,560
oh, il 2 dovrebbe andare in là.

1248
01:01:07,560 --> 01:01:09,685
Così si plop il 2 verso il basso, si chop off.

1249
01:01:09,685 --> 01:01:12,060
Allora avete appena il 3
e il 5 in 4 e 6.

1250
01:01:12,060 --> 01:01:14,650
E basta tenere tagliare fuori
fino a quando li metti nella matrice.

1251
01:01:14,650 --> 01:01:17,110
>> PUBBLICO: Quindi sei sempre solo
confrontando il [incomprensibile]?

1252
01:01:17,110 --> 01:01:17,710
>> ANDI PENG: Esattamente.

1253
01:01:17,710 --> 01:01:19,590
Quindi, in questo senso, si è
solo il confronto, in sostanza,

1254
01:01:19,590 --> 01:01:21,240
un numero contro l'altro numero.

1255
01:01:21,240 --> 01:01:22,990
E perché non si sa
che è ordinato, è

1256
01:01:22,990 --> 01:01:24,350
non c'è bisogno di guardare attraverso
tutti i numeri.

1257
01:01:24,350 --> 01:01:25,870
Basta guardare il primo.

1258
01:01:25,870 --> 01:01:27,582
E allora si può solo plop
giù, perché non si sa

1259
01:01:27,582 --> 01:01:29,640
essi appartengono dove devono appartenere.

1260
01:01:29,640 --> 01:01:31,030
Già.

1261
01:01:31,030 --> 01:01:32,920
Bella domanda.

1262
01:01:32,920 --> 01:01:35,290
>> E poi se qualcuno di voi
sono un po 'ambizioso,

1263
01:01:35,290 --> 01:01:38,660
sentitevi liberi di guardare a questo codice.

1264
01:01:38,660 --> 01:01:40,680
Questo è in realtà la
realizzazione fisica

1265
01:01:40,680 --> 01:01:42,150
di come avremmo scrivere merge sort.

1266
01:01:42,150 --> 01:01:44,070
E si può vedere, è molto breve.

1267
01:01:44,070 --> 01:01:46,310
Ma le idee dietro
esso sono piuttosto complessi.

1268
01:01:46,310 --> 01:01:50,865
Quindi, se avete voglia di disegnare questo fuori
nel vostro lavoro stasera, non esitate a.

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> OK.

1271
01:01:54,740 --> 01:01:58,070
Davide è andato anche su questo in conferenza.

1272
01:01:58,070 --> 01:02:00,660
Quali sono i migliori caso
tempi di esecuzione, peggiori tempi di esecuzione,

1273
01:02:00,660 --> 01:02:05,680
e i tempi di esecuzione previsti di merge sort?

1274
01:02:05,680 --> 01:02:07,260
Un paio di secondi per pensare.

1275
01:02:07,260 --> 01:02:11,198
Questo è abbastanza duro, ma tipo di
intuitivo se ci pensate.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
Tutto ok.

1278
01:02:23,054 --> 01:02:25,269
>> AUDIENCE: E 'il caso peggiore n log n?

1279
01:02:25,269 --> 01:02:26,060
ANDI PENG: Esattamente.

1280
01:02:26,060 --> 01:02:29,380
E perché è n log n.

1281
01:02:29,380 --> 01:02:32,230
>> PUBBLICO: Non è perché
diventa esponenzialmente più veloce,

1282
01:02:32,230 --> 01:02:35,390
quindi è come una funzione di tale
invece di essere semplicemente n

1283
01:02:35,390 --> 01:02:37,529
quadrato o qualcosa del genere?

1284
01:02:37,529 --> 01:02:38,320
ANDI PENG: Esattamente.

1285
01:02:38,320 --> 01:02:40,750
Quindi la ragione per cui la
runtime su questo è log n

1286
01:02:40,750 --> 01:02:44,310
n è quello che si sono perchè--
facendo in tutti questi passaggi?

1287
01:02:44,310 --> 01:02:46,190
Stai solo tagliare a metà, giusto?

1288
01:02:46,190 --> 01:02:48,750
E così, quando stiamo facendo la
log, tutto quello che sta facendo

1289
01:02:48,750 --> 01:02:53,150
è dividere un problema a metà,
a metà, a metà, in più metà.

1290
01:02:53,150 --> 01:02:56,430
E in questo senso, si può tipo
di eliminare il modello lineare

1291
01:02:56,430 --> 01:02:57,510
che abbiamo usato.

1292
01:02:57,510 --> 01:03:00,254
Perché quando si taglia
cose in mezzo, si tratta di un registro.

1293
01:03:00,254 --> 01:03:02,420
Questo è solo il matematico
modo di rappresentarlo.

1294
01:03:02,420 --> 01:03:06,310
>> E poi finalmente, alla fine, si è
solo fare un ultimo passaggio attraverso

1295
01:03:06,310 --> 01:03:07,930
a mettere tutti in ordine, giusto?

1296
01:03:07,930 --> 01:03:10,330
E così, se devi solo
controllare una cosa, che è n.

1297
01:03:10,330 --> 01:03:13,420
E così sei tipo di
moltiplicando i due insieme.

1298
01:03:13,420 --> 01:03:17,660
Quindi è come se hai quella finale
verificare la presenza di n per quaggiù con un log di n

1299
01:03:17,660 --> 01:03:18,390
quassù.

1300
01:03:18,390 --> 01:03:21,060
E se si moltiplicano
loro, questo è n log n.

1301
01:03:21,060 --> 01:03:26,100
>> E così il caso migliore e peggiore
caso e atteso sono tutti n log n.

1302
01:03:26,100 --> 01:03:27,943
E 'anche come un altro tipo.

1303
01:03:27,943 --> 01:03:30,090
E 'come ordinamento per selezione
nel senso che

1304
01:03:30,090 --> 01:03:32,131
non importa che cosa il vostro
elenco è, è solo andare

1305
01:03:32,131 --> 01:03:34,801
per fare la stessa cosa ogni volta.

1306
01:03:34,801 --> 01:03:35,300
OK.

1307
01:03:35,300 --> 01:03:39,950
Così come voi potete vedere, anche se
il genere che siamo passati through-- n

1308
01:03:39,950 --> 01:03:41,660
squadrato, non è molto efficiente.

1309
01:03:41,660 --> 01:03:47,060
E anche questo registro n n è
non il più efficiente.

1310
01:03:47,060 --> 01:03:49,720
Se voi siete curiosi,
c'è meccanismi di ordinamento

1311
01:03:49,720 --> 01:03:54,310
che sono così efficienti che siano
quasi sostanzialmente piatto nel runtime.

1312
01:03:54,310 --> 01:03:55,420
>> Hai qualche log n di.

1313
01:03:55,420 --> 01:03:58,190
Hai qualche log log n di.

1314
01:03:58,190 --> 01:04:00,330
Noi non tocchiamo su di loro
in questa classe in questo momento.

1315
01:04:00,330 --> 01:04:02,663
Ma se voi siete curiosi,
sentitevi liberi di Google, che cosa è

1316
01:04:02,663 --> 01:04:04,392
i meccanismi di ordinamento più efficienti.

1317
01:04:04,392 --> 01:04:06,350
Non lo so, ci sono
alcuni tra quelli veramente divertenti,

1318
01:04:06,350 --> 01:04:09,860
like-- c'è qualche davvero
quelli divertenti che le persone fanno.

1319
01:04:09,860 --> 01:04:12,210
E ti chiedi come
mai pensato.

1320
01:04:12,210 --> 01:04:15,730
Così Google, se avete un po 'di ricambio
tempo, su, quali sono alcuni modi divertenti

1321
01:04:15,730 --> 01:04:17,730
che people-- nonché
efficienti persone ways--

1322
01:04:17,730 --> 01:04:20,371
sono stati in grado di attuare i tipi.

1323
01:04:20,371 --> 01:04:20,870
OK.

1324
01:04:20,870 --> 01:04:22,880
Ed ecco un po grafico a portata di mano.

1325
01:04:22,880 --> 01:04:26,850
So tutto di te, prima che quiz 0,
sarà nella vostra camera probabilmente cercando

1326
01:04:26,850 --> 01:04:27,960
di memorizzare quello.

1327
01:04:27,960 --> 01:04:30,940
Ecco, questo è bello in là per voi ragazzi.

1328
01:04:30,940 --> 01:04:37,120
Basta non dimenticare la logica che made--
perché quei numeri si verificavano.

1329
01:04:37,120 --> 01:04:39,870
Se stai sempre perso, basta fare
Assicuratevi di sapere quali sono i tipi sono.

1330
01:04:39,870 --> 01:04:40,820
E si può correre attraverso
loro nella vostra mente

1331
01:04:40,820 --> 01:04:42,903
di capire perché quelli
le risposte sono quelle risposte.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> Tutto ok.

1334
01:04:47,600 --> 01:04:49,680
Quindi stiamo andando a spostare
on, infine, per la ricerca.

1335
01:04:49,680 --> 01:04:51,638
Perché, come quelli di voi
che hanno letto il pset,

1336
01:04:51,638 --> 01:04:55,175
la ricerca è anche parte di
Il problema di questa settimana pone.

1337
01:04:55,175 --> 01:04:57,300
Ti verrà chiesto di implementare
due tipi di ricerca.

1338
01:04:57,300 --> 01:05:00,070
Uno è una ricerca lineare e
uno è una ricerca binaria.

1339
01:05:00,070 --> 01:05:01,760
>> Così la ricerca lineare è abbastanza facile.

1340
01:05:01,760 --> 01:05:04,070
Hai voglia di cercare elemento
di una lista per vedere se si ottiene.

1341
01:05:04,070 --> 01:05:05,444
Devi solo scorrere.

1342
01:05:05,444 --> 01:05:08,170
E se è uguale a qualcosa,
si può solo tornare, giusto?

1343
01:05:08,170 --> 01:05:10,890
Ma quello che noi siamo più
interessato a parlare

1344
01:05:10,890 --> 01:05:14,550
è ricerca binaria, a destra, che è la
dividere e conquistare il meccanismo che

1345
01:05:14,550 --> 01:05:18,190
David stava dimostrando a lezione.

1346
01:05:18,190 --> 01:05:20,810
>> Ricordate l'esempio rubrica telefonica
che continua a portare in su,

1347
01:05:20,810 --> 01:05:23,960
quello che tipo di fatica
un po 'in questo anno passato,

1348
01:05:23,960 --> 01:05:27,530
dove si divide il problema a metà,
a metà, a metà, ancora e ancora,

1349
01:05:27,530 --> 01:05:30,730
fino a trovare quello che stai cercando?

1350
01:05:30,730 --> 01:05:33,727
E tu hai il
tempo di esecuzione anche di questo.

1351
01:05:33,727 --> 01:05:35,810
E si può vedere, è
molto più efficienti

1352
01:05:35,810 --> 01:05:39,080
rispetto a qualsiasi altro tipo di ricerca.

1353
01:05:39,080 --> 01:05:41,880
>> Quindi il modo che saremmo andati su
l'attuazione di una ricerca binaria

1354
01:05:41,880 --> 01:05:46,510
è, se avessimo un array,
indice 0 a 6, sette elementi,

1355
01:05:46,510 --> 01:05:49,790
possiamo guardare al centro, a destra- sopra
scusate, se la nostra domanda first--

1356
01:05:49,790 --> 01:05:53,840
se vogliamo porre la domanda di, fa
l'array contiene l'elemento 7,

1357
01:05:53,840 --> 01:05:56,840
ovviamente, essendo esseri umani, e avendo
come una serie di piccole, è facile per noi

1358
01:05:56,840 --> 01:05:58,210
dire di sì.

1359
01:05:58,210 --> 01:06:05,750
Ma il modo per implementare un binario
ricerca sarebbe di guardare al centro.

1360
01:06:05,750 --> 01:06:08,020
>> Sappiamo che l'indice 3 è
mezzo, perché

1361
01:06:08,020 --> 01:06:09,270
che ci sono sette elementi.

1362
01:06:09,270 --> 01:06:10,670
Cosa 7 diviso 2?

1363
01:06:10,670 --> 01:06:12,850
Si può recidere quel qualcosa in più 1.

1364
01:06:12,850 --> 01:06:14,850
Hai 3 nel mezzo.

1365
01:06:14,850 --> 01:06:17,590
Così è array di 3 pari a 7?

1366
01:06:17,590 --> 01:06:18,900
Non è, giusto?

1367
01:06:18,900 --> 01:06:21,050
Ma possiamo fare un paio di controlli.

1368
01:06:21,050 --> 01:06:25,380
È serie di 3 o inferiore a 7
è matrice di 3 superiore a 7?

1369
01:06:25,380 --> 01:06:27,240
>> E sappiamo che è meno di 7.

1370
01:06:27,240 --> 01:06:30,259
Quindi sappiamo che, oh, si deve
non essere nella metà sinistra.

1371
01:06:30,259 --> 01:06:32,300
Sappiamo che deve essere
nella metà destra, giusto?

1372
01:06:32,300 --> 01:06:34,662
Così possiamo solo recidere la metà della matrice.

1373
01:06:34,662 --> 01:06:36,370
Non hanno nemmeno bisogno di
guardare più.

1374
01:06:36,370 --> 01:06:38,711
Perché sappiamo che
metà del nostro problem--

1375
01:06:38,711 --> 01:06:41,210
sappiamo che la risposta è in
la metà destra del nostro problema.

1376
01:06:41,210 --> 01:06:42,580
Quindi ci limitiamo a guardare adesso.

1377
01:06:42,580 --> 01:06:44,860
>> Ora diamo un'occhiata al
metà di ciò che resta.

1378
01:06:44,860 --> 01:06:46,880
Tale indice 5.

1379
01:06:46,880 --> 01:06:50,200
Facciamo di nuovo lo stesso controllo
e vediamo che è più piccolo.

1380
01:06:50,200 --> 01:06:52,050
Quindi guardiamo a sinistra di quello.

1381
01:06:52,050 --> 01:06:53,430
E poi vediamo che il check.

1382
01:06:53,430 --> 01:06:57,600
È il valore della matrice di
Indice 4 pari al 7?

1383
01:06:57,600 --> 01:06:58,260
Esso è.

1384
01:06:58,260 --> 01:07:03,580
Così possiamo tornare vero, perché
abbiamo trovato il valore della nostra lista.

1385
01:07:03,580 --> 01:07:06,738
Fa il modo in cui ho passato
che ha senso per tutti?

1386
01:07:06,738 --> 01:07:08,760
OK.

1387
01:07:08,760 --> 01:07:11,670
Ti darò ragazzi forse, come,
tre, quattro minuti per capire

1388
01:07:11,670 --> 01:07:13,270
come pseudocodice questo.

1389
01:07:13,270 --> 01:07:18,070
>> Quindi immagino ti ho chiesto di scrivere un
funzione chiamata di ricerca () che ha restituito

1390
01:07:18,070 --> 01:07:20,640
un valore, un valore booleano,
questo era vero o false-- come,

1391
01:07:20,640 --> 01:07:22,970
vero se avete trovato il
valore, falso se non l'avete fatto.

1392
01:07:22,970 --> 01:07:25,230
E allora tu eri
passato nel valore

1393
01:07:25,230 --> 01:07:28,410
erano alla ricerca di valori, che in
è il array-- oh, ho sicuramente messo

1394
01:07:28,410 --> 01:07:29,410
che nel posto sbagliato.

1395
01:07:29,410 --> 01:07:29,580
OK.

1396
01:07:29,580 --> 01:07:31,829
In ogni modo, che dovrebbe avere
stato a destra dei valori.

1397
01:07:31,829 --> 01:07:36,280
E poi int n è il numero
di elementi di tale matrice.

1398
01:07:36,280 --> 01:07:39,430
Come si va a provare
a pseudocodice che problema?

1399
01:07:39,430 --> 01:07:41,630
Ti darò ragazzi come
tre minuti per farlo.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
No, penso che ci sia only--
sì, ce n'è uno proprio qui.

1402
01:08:02,595 --> 01:08:03,261
PUBBLICO: Posso?

1403
01:08:03,261 --> 01:08:04,388
ANDI PENG: Sì, lo avete ottenuto.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
È che il lavoro?

1406
01:08:11,050 --> 01:08:12,290
Ok bello.

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> OK.

1409
01:10:44,720 --> 01:10:47,630
Tutti i ragazzi di destra, noi siamo
andando a frenare in.

1410
01:10:47,630 --> 01:10:49,730
OK.

1411
01:10:49,730 --> 01:10:54,020
Quindi assumiamo noi abbiamo questa bella
poco array con n valori in esso.

1412
01:10:54,020 --> 01:10:55,170
Non ho fatto disegnare le linee.

1413
01:10:55,170 --> 01:10:58,649
Ma come potremmo fare per
cercando di scrivere questo?

1414
01:10:58,649 --> 01:11:00,440
Qualcuno ha voglia di
dammi la prima linea?

1415
01:11:00,440 --> 01:11:02,814
Se volete darmi la
prima linea di questo pseudocodice.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> PUBBLICO: [incomprensibile]

1418
01:11:08,430 --> 01:11:10,138
PUBBLICO: Che ci si vuole
iterare through--

1419
01:11:10,138 --> 01:11:11,094
PUBBLICO: Solo un altro per il ciclo?

1420
01:11:11,094 --> 01:11:11,760
PUBBLICO: --per.

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> ANDI PENG: Quindi questo è un po 'complicato.

1423
01:11:17,780 --> 01:11:23,130
Pensate about-- vuoi
continuare a correre questo ciclo

1424
01:11:23,130 --> 01:11:27,950
più e più volte fino a quando?

1425
01:11:27,950 --> 01:11:30,819
>> AUDIENCE: Fino a quando il [incomprensibile]
valore è uguale a quel valore.

1426
01:11:30,819 --> 01:11:31,610
ANDI PENG: Esattamente.

1427
01:11:31,610 --> 01:11:33,900
Così si può in realtà solo write--
possiamo anche semplificare più.

1428
01:11:33,900 --> 01:11:35,630
Possiamo solo fare un ciclo while, giusto?

1429
01:11:35,630 --> 01:11:39,380
Così si può solo avere loop--
sappiamo che è un po '.

1430
01:11:39,380 --> 01:11:42,850
Ma per ora, sto andando
per dire "loop" - con che cosa?

1431
01:11:42,850 --> 01:11:46,640
Loop until-- ciò che è
la nostra condizione finale?

1432
01:11:46,640 --> 01:11:47,510
Credo di aver sentito.

1433
01:11:47,510 --> 01:11:48,530
Ho sentito qualcuno dire che.

1434
01:11:48,530 --> 01:11:51,255
>> Pubblico: Valori equivale a metà.

1435
01:11:51,255 --> 01:11:52,255
ANDI PENG: Dillo ancora.

1436
01:11:52,255 --> 01:11:54,470
PUBBLICO O, fino a quando la
valore che si sta cercando

1437
01:11:54,470 --> 01:11:58,470
per è uguale al valore medio.

1438
01:11:58,470 --> 01:12:00,280
>> ANDI PENG: Che cosa se non è lì dentro?

1439
01:12:00,280 --> 01:12:03,113
Che cosa succede se il valore che si sta cercando
perché non è in realtà in questo array?

1440
01:12:03,113 --> 01:12:05,890
PUBBLICO: Si ritorna 1.

1441
01:12:05,890 --> 01:12:08,850
>> ANDI PENG: Ma cosa vogliamo
ciclo finché se abbiamo una condizione?

1442
01:12:08,850 --> 01:12:09,350
Già.

1443
01:12:09,350 --> 01:12:11,239
>> PUBBLICO: Fino a quando non c'è un solo valore?

1444
01:12:11,239 --> 01:12:13,530
ANDI PENG: è possibile ciclo
until-- in modo da sapere che sei

1445
01:12:13,530 --> 01:12:15,714
avrà un valore massimo, giusto?

1446
01:12:15,714 --> 01:12:18,130
E si sa che si sta andando
avere un valore minimo, giusto?

1447
01:12:18,130 --> 01:12:20,379
Perché anche, questo è qualcosa
Ho dimenticato di dire prima,

1448
01:12:20,379 --> 01:12:22,640
che qualcosa che è
critico su ricerca binaria

1449
01:12:22,640 --> 01:12:24,182
è che l'array è già ordinato.

1450
01:12:24,182 --> 01:12:26,973
Perché non c'è modo di fare
questo se sono valori solo casuali.

1451
01:12:26,973 --> 01:12:29,190
Non sai se uno è
maggiore dell'altro, giusto?

1452
01:12:29,190 --> 01:12:32,720
>> Così sapete che il vostro max e
i tuoi minuti sono qui, giusto?

1453
01:12:32,720 --> 01:12:35,590
Se avete intenzione di essere regolare
il tuo massimo nei tuoi minuti e le mid--

1454
01:12:35,590 --> 01:12:38,470
facciamo solo assumere la tua
valore medio è qui-- giusto

1455
01:12:38,470 --> 01:12:43,910
si sta andando a fondo
ciclo fino a quando il minimo è

1456
01:12:43,910 --> 01:12:47,510
più o meno come il tuo massimo, a destra, o
se il vostro max non è lo stesso del vostro min.

1457
01:12:47,510 --> 01:12:48,040
Destra?

1458
01:12:48,040 --> 01:12:51,340
Perché quando ciò accade, si sa che
hai finalmente colpito lo stesso valore.

1459
01:12:51,340 --> 01:12:59,135
Così si vuole fino a quando il ciclo min
è inferiore o uguale a-- oops,

1460
01:12:59,135 --> 01:13:01,510
non meno di o uguale a,
l'altro modo around-- max è.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> Fatto che ha senso?

1463
01:13:16,160 --> 01:13:18,810
Ho preso un paio di tentativi per ottenere tale diritto.

1464
01:13:18,810 --> 01:13:21,869
Ma fino a quando il ciclo valore massimo
è essenzialmente quasi meno

1465
01:13:21,869 --> 01:13:23,410
o uguale al minimo, giusto?

1466
01:13:23,410 --> 01:13:25,201
Questo è quando si sa
che hai convergenti.

1467
01:13:25,201 --> 01:13:29,290
PUBBLICO: Quando sarebbe il vostro massimo
valore sia inferiore al minimo?

1468
01:13:29,290 --> 01:13:31,040
ANDI PENG: Se si mantiene
adattandolo, che

1469
01:13:31,040 --> 01:13:32,380
è quello che stiamo andando
di fare in questo.

1470
01:13:32,380 --> 01:13:33,460
Questo fa senso?

1471
01:13:33,460 --> 01:13:35,750
Minima e massima sono solo
interi che siamo probabilmente

1472
01:13:35,750 --> 01:13:39,260
andando a voler creare a mantenere
traccia di dove stiamo cercando.

1473
01:13:39,260 --> 01:13:41,790
Perché esiste la matrice
indipendentemente da quello che stiamo facendo.

1474
01:13:41,790 --> 01:13:45,030
Come, non siamo in realtà fisicamente
tagliando l'array, giusto?

1475
01:13:45,030 --> 01:13:47,261
Stiamo solo regolando
dove stiamo cercando.

1476
01:13:47,261 --> 01:13:48,136
Questo fa senso?

1477
01:13:48,136 --> 01:13:48,472
>> PUBBLICO: Sì.

1478
01:13:48,472 --> 01:13:49,110
>> ANDI PENG: OK.

1479
01:13:49,110 --> 01:13:57,090
Quindi, se questa è la condizione per il nostro ciclo,
cosa vogliamo all'interno di questo ciclo?

1480
01:13:57,090 --> 01:13:58,700
Che cosa abbiamo intenzione di mancare di fare?

1481
01:13:58,700 --> 01:14:02,390
Quindi in questo momento, abbiamo
max e min, a destra,

1482
01:14:02,390 --> 01:14:04,962
probabilmente creato qui da qualche parte.

1483
01:14:04,962 --> 01:14:07,170
Stiamo andando a voler probabilmente
per trovare una via di mezzo, giusto?

1484
01:14:07,170 --> 01:14:08,450
Come facciamo a essere
in grado di trovare il mezzo?

1485
01:14:08,450 --> 01:14:09,491
Qual è il mathematical--

1486
01:14:09,491 --> 01:14:11,079
PUBBLICO: Max Plus min diviso per 2.

1487
01:14:11,079 --> 01:14:11,870
ANDI PENG: Esattamente.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
Questo fa senso?

1490
01:14:21,620 --> 01:14:25,780
E voi ragazzi vedo perché noi
non solo use-- perché abbiamo fatto questo

1491
01:14:25,780 --> 01:14:27,850
invece di fare solo n diviso 2?

1492
01:14:27,850 --> 01:14:30,310
È perché n è un valore
che sta andando a rimanere lo stesso.

1493
01:14:30,310 --> 01:14:30,979
Destra?

1494
01:14:30,979 --> 01:14:34,020
Ma, come registriamo il nostro minimo e
valori massimi, che stanno andando a cambiare.

1495
01:14:34,020 --> 01:14:36,040
E di conseguenza, il nostro mezzo
sta per cambiare.

1496
01:14:36,040 --> 01:14:37,873
Ecco perché vogliamo
per fare questo qui.

1497
01:14:37,873 --> 01:14:38,510
OK.

1498
01:14:38,510 --> 01:14:41,600
>> E poi, ora che
abbiamo trovato our-- sì.

1499
01:14:41,600 --> 01:14:44,270
>> PUBBLICO: Solo un rapido interrogo
quando si dice min e max,

1500
01:14:44,270 --> 01:14:46,410
stiamo assumendo che
è già ordinato?

1501
01:14:46,410 --> 01:14:48,400
>> ANDI PENG: Sì, che in realtà è un
precondizione per una ricerca binaria,

1502
01:14:48,400 --> 01:14:49,816
che dovete sapere è ordinato.

1503
01:14:49,816 --> 01:14:53,660
È per questo tipo, si scrive nella tua
problema posto davanti la ricerca binaria.

1504
01:14:53,660 --> 01:14:55,910
OK.

1505
01:14:55,910 --> 01:14:58,876
Quindi, ora che sappiamo dove il nostro punto centrale
è, che cosa vuoi fare qui?

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> PUBBLICO: Vogliamo confrontare
che all'altra.

1508
01:15:04,319 --> 01:15:05,110
ANDI PENG: Esattamente.

1509
01:15:05,110 --> 01:15:12,280
Quindi si sta andando a confrontare
metà di valore, giusto?

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
E che cosa fa che raccontano
noi quando confrontiamo?

1512
01:15:18,670 --> 01:15:22,226
Che cosa vogliamo fare dopo?

1513
01:15:22,226 --> 01:15:25,389
>> AUDIENCE: Se il valore è più grande
che la metà, vogliamo tagliare fuori.

1514
01:15:25,389 --> 01:15:26,180
ANDI PENG: Esattamente.

1515
01:15:26,180 --> 01:15:33,940
Quindi, se il valore è maggiore
che la metà, siamo

1516
01:15:33,940 --> 01:15:36,550
intenzione di voler cambiare questi
Maxes minimo e, giusto?

1517
01:15:36,550 --> 01:15:38,980
Che cosa vogliamo cambiare?

1518
01:15:38,980 --> 01:15:42,145
Quindi, se conosciamo il valore è da qualche parte
nel sito, cosa dobbiamo cambiare?

1519
01:15:42,145 --> 01:15:44,758
Noi vogliamo cambiare il nostro
minima per essere a metà, giusto?

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
E poi il resto, se è in questo
mezzo, che cosa vogliamo cambiare?

1522
01:15:54,292 --> 01:15:55,306
>> PUBBLICO: Il tuo massimo.

1523
01:15:55,306 --> 01:15:55,972
ANDI PENG: Sì.

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
E poi si sta solo andando
per mantenere looping, giusto?

1526
01:16:04,680 --> 01:16:08,920
Perché ora, dopo una iterazione
attraverso, hai un max qui.

1527
01:16:08,920 --> 01:16:10,760
E poi si può ricalcolare un mid.

1528
01:16:10,760 --> 01:16:11,990
E poi si può confrontare.

1529
01:16:11,990 --> 01:16:14,766
E si sta andando a andare avanti
fino a quando i minuti e le Maxes

1530
01:16:14,766 --> 01:16:15,890
hanno sostanzialmente convergenti.

1531
01:16:15,890 --> 01:16:17,890
E questo è quando si sa che
hai colpito alla fine di esso.

1532
01:16:17,890 --> 01:16:20,280
E neanche lo avete trovato
non si dispone a quel punto.

1533
01:16:20,280 --> 01:16:23,170
>> Questo senso per tutti?

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
OK.

1536
01:16:26,770 --> 01:16:27,900
Questo è abbastanza importante,
perché avrete

1537
01:16:27,900 --> 01:16:29,760
scrivere questo nel codice stasera.

1538
01:16:29,760 --> 01:16:32,660
Ma voi ragazzi avete un buon
senso di ciò che si dovrebbe fare,

1539
01:16:32,660 --> 01:16:34,051
che è buono.

1540
01:16:34,051 --> 01:16:34,550
OK.

1541
01:16:34,550 --> 01:16:38,840
Quindi abbiamo circa sette
minuti dalla fine sezione.

1542
01:16:38,840 --> 01:16:43,170
Quindi stiamo andando a parlare di
questo pset che faremo.

1543
01:16:43,170 --> 01:16:46,410
Così il pset è diviso in due metà.

1544
01:16:46,410 --> 01:16:50,230
Il primo tempo coinvolge
attuazione di un ritrovamento

1545
01:16:50,230 --> 01:16:54,210
in cui si scrive una ricerca lineare, un
ricerca binaria, e un algoritmo di ordinamento.

1546
01:16:54,210 --> 01:16:56,690
>> Quindi questa è la prima
tempo in un pset dove

1547
01:16:56,690 --> 01:17:00,050
saremo dando ragazzi ciò che è chiamato
codice di distribuzione, che è il codice

1548
01:17:00,050 --> 01:17:02,740
che abbiamo pre-scritta,
ma appena lasciato alcuni pezzi off

1549
01:17:02,740 --> 01:17:04,635
per finire di scrivere.

1550
01:17:04,635 --> 01:17:07,510
Quindi ragazzi, quando si guarda a questo
codice, si potrebbe ottenere davvero spaventato.

1551
01:17:07,510 --> 01:17:08,630
Se sei proprio come, ahh, ho
non so cosa che sta facendo,

1552
01:17:08,630 --> 01:17:11,670
Non lo so, come, che sembra
così complicato, ahh, rilassatevi.

1553
01:17:11,670 --> 01:17:12,170
Va bene.

1554
01:17:12,170 --> 01:17:12,930
Leggere le specifiche.

1555
01:17:12,930 --> 01:17:16,920
Le specifiche vi spiegherà esattamente
ciò che tutti questi programmi stanno facendo.

1556
01:17:16,920 --> 01:17:20,560
>> Ad esempio, è un programma generate.c
che verrà con il vostro pset.

1557
01:17:20,560 --> 01:17:24,060
In realtà non è necessario toccare, ma
si dovrebbe capire che cosa sta facendo.

1558
01:17:24,060 --> 01:17:28,550
E generate.c, tutto ciò che sta facendo è
o generazione di numeri casuali

1559
01:17:28,550 --> 01:17:32,400
oppure si può dare un seme, come un
numero predisposto che ci vuole,

1560
01:17:32,400 --> 01:17:34,140
e genera più numeri.

1561
01:17:34,140 --> 01:17:37,170
Quindi non c'è un modo specifico per
implementare generate.c in cui

1562
01:17:37,170 --> 01:17:42,760
si può solo fare un po 'di numeri
per testare le vostre altri metodi su.

1563
01:17:42,760 --> 01:17:45,900
>> Quindi, se si voleva, per
esempio, testare la vostra scoperta,

1564
01:17:45,900 --> 01:17:48,970
si vorrebbe eseguire generate.c,
generare un po 'di numeri,

1565
01:17:48,970 --> 01:17:50,880
e quindi eseguire la funzione aiutanti.

1566
01:17:50,880 --> 01:17:53,930
La vostra funzione aiutanti è dove sei
in realtà la scrittura di codice fisicamente.

1567
01:17:53,930 --> 01:17:59,330
E pensate di aiutanti come un file di libreria
stai scrivendo che ritrovamento sta chiamando.

1568
01:17:59,330 --> 01:18:02,950
E così all'interno helpers.c, ti
fare ricerca e l'ordinamento.

1569
01:18:02,950 --> 01:18:06,500
>> E poi si sta andando a essenzialmente
basta metterli tutti insieme.

1570
01:18:06,500 --> 01:18:10,350
Le specifiche vi dirà come
mettere che nella riga di comando.

1571
01:18:10,350 --> 01:18:14,880
E voi sarete in grado di verificare se
Non la tua specie e di ricerca stanno lavorando.

1572
01:18:14,880 --> 01:18:15,870
Cool.

1573
01:18:15,870 --> 01:18:18,720
Qualcuno ha già iniziato e
problemi incontrati o domande

1574
01:18:18,720 --> 01:18:20,520
hanno ora con questo?

1575
01:18:20,520 --> 01:18:21,020
OK.

1576
01:18:21,020 --> 01:18:21,476
>> PUBBLICO: Aspetta.

1577
01:18:21,476 --> 01:18:21,932
Ho una domanda.

1578
01:18:21,932 --> 01:18:22,844
>> ANDI PENG: Sì.

1579
01:18:22,844 --> 01:18:28,390
>> PUBBLICO: Così ho iniziato a fare
la ricerca lineare in helpers.c

1580
01:18:28,390 --> 01:18:29,670
e non era davvero lavorando.

1581
01:18:29,670 --> 01:18:34,590
Ma poi, ho scoperto che abbiamo appena
necessario eliminare e fare ricerca binaria.

1582
01:18:34,590 --> 01:18:36,991
Quindi cosa importa se non funziona?

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> ANDI PENG: Breve risposta è no.

1585
01:18:41,510 --> 01:18:42,642
Ma dal momento che siamo not--

1586
01:18:42,642 --> 01:18:44,350
PUBBLICO: Ma nessuno di
in realtà il controllo.

1587
01:18:44,350 --> 01:18:46,058
ANDI PENG: Non siamo mai
andando a vedere che.

1588
01:18:46,058 --> 01:18:49,590
Ma probabilmente si vuole fare
sicuro che la ricerca sta lavorando.

1589
01:18:49,590 --> 01:18:51,700
Perché se il vostro lineari
ricerca non funziona,

1590
01:18:51,700 --> 01:18:54,410
allora è probabile che il vostro binario
ricerca non è andare a lavorare pure.

1591
01:18:54,410 --> 01:18:56,646
Perché hai simile
logica in entrambi.

1592
01:18:56,646 --> 01:18:58,020
E no, non ha molta importanza.

1593
01:18:58,020 --> 01:19:01,300
Così gli unici si piega
in genere sono e ricerca binaria.

1594
01:19:01,300 --> 01:19:02,490
Già.

1595
01:19:02,490 --> 01:19:06,610
>> E inoltre, molti bambini erano
cercare di compilare helpers.c.

1596
01:19:06,610 --> 01:19:09,550
Non sta effettivamente permesso
per fare questo, perché helpers.c

1597
01:19:09,550 --> 01:19:11,200
non ha una funzione principale.

1598
01:19:11,200 --> 01:19:13,550
E così si dovrebbe solo
essere in realtà la compilazione

1599
01:19:13,550 --> 01:19:18,670
generare e trovare, perché trovare le chiamate
helpers.c e le funzioni all'interno di esso.

1600
01:19:18,670 --> 01:19:20,790
In modo che rende il debugging
un dolore nel culo.

1601
01:19:20,790 --> 01:19:22,422
Ma questo è ciò che dobbiamo fare.

1602
01:19:22,422 --> 01:19:23,880
PUBBLICO: Devi solo fare tutto, giusto?

1603
01:19:23,880 --> 01:19:27,290
ANDI PENG: Si può solo
fare tutti così, sì.

1604
01:19:27,290 --> 01:19:28,060
OK.

1605
01:19:28,060 --> 01:19:32,570
In modo che sia in termini di ciò
il pset sta chiedendo a tutti voi di fare.

1606
01:19:32,570 --> 01:19:35,160
Se avete qualsiasi domanda,
a chiedere a me dopo la sezione.

1607
01:19:35,160 --> 01:19:37,580
Sarò qui per, come, a 20 minuti.

1608
01:19:37,580 --> 01:19:40,500
>> E sì, i pset di
non è affatto male.

1609
01:19:40,500 --> 01:19:41,680
Voi ragazzi dovreste essere OK.

1610
01:19:41,680 --> 01:19:43,250
Questi, basta seguire le linee guida.

1611
01:19:43,250 --> 01:19:47,840
Genere di avere un senso di, logicamente, cosa
dovrebbe accadere e non avrete problemi.

1612
01:19:47,840 --> 01:19:48,690
Non essere troppo spaventato.

1613
01:19:48,690 --> 01:19:50,220
Ci sono un sacco di codice
già lì scritta.

1614
01:19:50,220 --> 01:19:53,011
Non essere troppo spaventati se non lo fai
capire che cosa tutto questo significhi.

1615
01:19:53,011 --> 01:19:54,749
Se si tratta di un sacco, è totalmente bene.

1616
01:19:54,749 --> 01:19:55,790
E vieni a orari di ufficio.

1617
01:19:55,790 --> 01:19:57,520
Ti aiuteremo a dare un'occhiata.

1618
01:19:57,520 --> 01:20:00,810
>> AUDIENCE: Con l'extra
funzioni, cosa guardiamo quelli sopra?

1619
01:20:00,810 --> 01:20:03,417
>> ANDI PENG: Sì, quelli sono nel codice.

1620
01:20:03,417 --> 01:20:05,750
Nel gioco del 15, la metà di
è già scritto per voi.

1621
01:20:05,750 --> 01:20:09,310
Quindi queste funzioni sono
già nel codice.

1622
01:20:09,310 --> 01:20:12,020
Yep.

1623
01:20:12,020 --> 01:20:12,520
Tutto ok.

1624
01:20:12,520 --> 01:20:14,000
Beh, buona fortuna.

1625
01:20:14,000 --> 01:20:15,180
E 'un giorno disgustoso.

1626
01:20:15,180 --> 01:20:19,370
Quindi spero che voi ragazzi non si sentono troppo
male di stare dentro e codifica.

1627
01:20:19,370 --> 01:20:22,133