1
00:00:00,000 --> 00:00:11,904
>> [RIPRODUZIONE DI BRANI MUSICALI]

2
00:00:11,904 --> 00:00:12,910
>> IL PROFESSORE: Va bene.

3
00:00:12,910 --> 00:00:16,730
Questo è CS50 e questo è
la fine della terza settimana.

4
00:00:16,730 --> 00:00:20,230
Quindi siamo qui oggi, non in Sanders
Teatro, invece di Weidner Biblioteca.

5
00:00:20,230 --> 00:00:23,170
All'interno di cui è uno studio
conosciuta come Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
o diciamo Studio H, o sono
noi say-- se ti è piaciuto quello scherzo,

7
00:00:28,310 --> 00:00:30,540
in realtà è da
compagno di classe, Mark, in linea,

8
00:00:30,540 --> 00:00:32,420
che ha suggerito il più via Twitter.

9
00:00:32,420 --> 00:00:34,270
Ora, ciò che è cool
essere qui in uno studio

10
00:00:34,270 --> 00:00:38,410
è che sono circondato da questi verde
pareti, uno schermo verde o chromakey,

11
00:00:38,410 --> 00:00:43,290
per così dire, il che significa che CS50 di
team di produzione, a mia insaputa

12
00:00:43,290 --> 00:00:47,380
in questo momento, potrebbe essere messa
più mi in qualsiasi parte del mondo,

13
00:00:47,380 --> 00:00:48,660
nel bene e nel male.

14
00:00:48,660 --> 00:00:51,800
>> Ora quello che ci aspetta, impostare problema
due è nelle vostre mani per questa settimana,

15
00:00:51,800 --> 00:00:53,830
ma con il problema set
tre la prossima settimana,

16
00:00:53,830 --> 00:00:56,600
sarete sfidati con
la cosiddetta partita a 15,

17
00:00:56,600 --> 00:00:58,960
un vecchio partito favore che
si potrebbe ricordare che riceve

18
00:00:58,960 --> 00:01:02,030
come un bambino che ha un sacco
di numeri che possono scorrere su, giù,

19
00:01:02,030 --> 00:01:05,790
a destra ea sinistra, e c'è un divario
all'interno del puzzle, in cui si

20
00:01:05,790 --> 00:01:07,840
può effettivamente fare scorrere i pezzi del puzzle.

21
00:01:07,840 --> 00:01:11,150
In definitiva si riceve questo
Puzzle in qualche ordine casuale semi,

22
00:01:11,150 --> 00:01:12,940
e l'obiettivo è quello
risolverlo, dall'alto in basso,

23
00:01:12,940 --> 00:01:16,310
da sinistra a destra, da una
tutta la strada fino a 15.

24
00:01:16,310 --> 00:01:19,360
>> Sfortunatamente, l'implementazione
avrete a portata di mano

25
00:01:19,360 --> 00:01:21,590
sta per essere software
basato, non fisicamente.

26
00:01:21,590 --> 00:01:25,280
Si sta effettivamente andando ad avere per scrivere
codice con il quale uno studente o un utente può

27
00:01:25,280 --> 00:01:26,760
giocare il gioco del 15.

28
00:01:26,760 --> 00:01:29,030
Ed infatti, nel l'hacker
edizione del gioco del 15,

29
00:01:29,030 --> 00:01:32,155
sarai una sfida per l'attuazione,
Non solo la riproduzione di questa vecchia scuola

30
00:01:32,155 --> 00:01:35,010
gioco, ma piuttosto la soluzione
di esso, attuare modalità di Dio,

31
00:01:35,010 --> 00:01:38,280
per così dire, che in realtà
risolve il puzzle per l'umano,

32
00:01:38,280 --> 00:01:41,080
fornendo loro suggerimento,
dopo suggerimento, dopo suggerimento.

33
00:01:41,080 --> 00:01:42,280
Quindi più che la prossima settimana.

34
00:01:42,280 --> 00:01:43,720
Ma questo è quello che ci aspetta.

35
00:01:43,720 --> 00:01:47,610
>> Per ora ricordare che all'inizio di questa settimana
abbiamo avuto questo colpo di scena, se si vuole,

36
00:01:47,610 --> 00:01:52,560
per cui la migliore che stavamo facendo la cernita
saggio è stato un limite superiore di grande o di n

37
00:01:52,560 --> 00:01:53,210
quadrato.

38
00:01:53,210 --> 00:01:56,520
In altre parole, bubble sort,
selection sort, insertion sort,

39
00:01:56,520 --> 00:01:59,120
tutti loro, mentre differente
nella loro attuazione,

40
00:01:59,120 --> 00:02:03,480
devoluto in una n quadrato esecuzione
tempo nel caso peggiore.

41
00:02:03,480 --> 00:02:06,010
E generalmente si assume che
il caso peggiore per l'ordinamento

42
00:02:06,010 --> 00:02:08,814
è uno che gli ingressi
sono completamente all'indietro.

43
00:02:08,814 --> 00:02:11,980
E in effetti, ci sono voluti parecchi passi
per attuare ciascuna di tali algoritmi.

44
00:02:11,980 --> 00:02:15,110
>> Ora, alla fine della classe
richiamo, abbiamo confrontato bubble sort

45
00:02:15,110 --> 00:02:19,390
contro la selezione sorta contro un altro
che abbiamo chiamato merge sort, al momento,

46
00:02:19,390 --> 00:02:22,120
e propongo che sta prendendo
vantaggio di una lezione di settimana

47
00:02:22,120 --> 00:02:24,060
pari a zero, divide et impera.

48
00:02:24,060 --> 00:02:28,810
E in qualche modo raggiungere un qualche tipo di
logaritmico tempo di esecuzione in ultima analisi,

49
00:02:28,810 --> 00:02:31,024
invece di qualcosa
questo è puramente quadratica.

50
00:02:31,024 --> 00:02:33,440
E non è del tutto logaritmica,
è un po 'più di questo.

51
00:02:33,440 --> 00:02:36,520
Ma se vi ricordate dalla classe,
era molto più velocemente.

52
00:02:36,520 --> 00:02:38,210
Diamo uno sguardo a dove avevamo lasciato.

53
00:02:38,210 --> 00:02:41,880

54
00:02:41,880 --> 00:02:45,370
>> Bubble sort contro selezione
specie contro merge sort.

55
00:02:45,370 --> 00:02:47,700
Ora sono tutti in esecuzione, in
teoria, allo stesso tempo.

56
00:02:47,700 --> 00:02:50,510
La CPU gira alla stessa velocità.

57
00:02:50,510 --> 00:02:54,990
Ma si può sentire che noia questo
sta molto rapidamente sta per diventare,

58
00:02:54,990 --> 00:02:58,790
e quanto velocemente, quando iniettiamo
un po 'di algoritmi settimana Zero,

59
00:02:58,790 --> 00:03:00,080
possiamo accelerare le cose.

60
00:03:00,080 --> 00:03:01,630
>> Così sorta marchio sembra incredibile.

61
00:03:01,630 --> 00:03:05,220
Come possiamo sfruttare essa, al fine
Per ordinare i numeri più rapidamente.

62
00:03:05,220 --> 00:03:07,140
Beh pensiamo indietro
a un ingrediente che

63
00:03:07,140 --> 00:03:10,380
avevano nel settimana zero, cioè di
alla ricerca di qualcuno in una rubrica telefonica,

64
00:03:10,380 --> 00:03:12,380
e ricordare che la
pseudocodice che abbiamo proposto,

65
00:03:12,380 --> 00:03:14,560
attraverso il quale possiamo trovare
uno come Mike Smith,

66
00:03:14,560 --> 00:03:16,310
sembrava un po 'qualcosa di simile.

67
00:03:16,310 --> 00:03:20,820
>> Ora date un'occhiata in particolare
alla linea 7 e 8, e 10 e 11,

68
00:03:20,820 --> 00:03:25,240
che inducono quel ciclo, per cui abbiamo mantenuto
tornando alla linea 3 ancora, e ancora,

69
00:03:25,240 --> 00:03:26,520
e ancora.

70
00:03:26,520 --> 00:03:31,790
Ma si scopre che siamo in grado di visualizzare
questo algoritmo, qui in pseudocodice,

71
00:03:31,790 --> 00:03:33,620
un po 'di più olistico.

72
00:03:33,620 --> 00:03:35,960
In realtà, quello che sto cercando
a qui sullo schermo,

73
00:03:35,960 --> 00:03:41,180
è un algoritmo per la ricerca di
Mike Smith tra un insieme di pagine.

74
00:03:41,180 --> 00:03:45,520
E in effetti, si potrebbe semplificare questo
algoritmo in quelle linee 7 e 8,

75
00:03:45,520 --> 00:03:49,860
e 10 e 11 per dire solo questo,
che ho presentato qui in giallo.

76
00:03:49,860 --> 00:03:52,210
In altre parole, se Mike
Smith è in precedenza nel libro,

77
00:03:52,210 --> 00:03:55,004
non abbiamo bisogno di specificare passo
passo ora come andare a trovare.

78
00:03:55,004 --> 00:03:56,920
Non abbiamo specificare
per tornare alla linea 3,

79
00:03:56,920 --> 00:03:58,960
perché non solo, invece,
per esempio, più in generale,

80
00:03:58,960 --> 00:04:01,500
cercare Mike nel
la metà sinistra del libro.

81
00:04:01,500 --> 00:04:03,960
>> Al contrario, se è Mike
in realtà più avanti nel libro,

82
00:04:03,960 --> 00:04:07,540
perché non solo citiamo ricerca unquote
per Mike nella metà destra del libro.

83
00:04:07,540 --> 00:04:11,030
In altre parole, perché non facciamo solo
sorta di punt a noi stessi dicendo,

84
00:04:11,030 --> 00:04:13,130
cercare Mike in questo
sottoinsieme del libro,

85
00:04:13,130 --> 00:04:16,279
e lasciare al nostro attuale
algoritmo per dirci

86
00:04:16,279 --> 00:04:18,750
come cercare Mike in
che la metà sinistra del libro.

87
00:04:18,750 --> 00:04:20,750
In altre parole, il nostro
algoritmo funziona se è

88
00:04:20,750 --> 00:04:24,670
una rubrica di questo spessore, di questa
spessore, o qualsiasi spessore di sorta.

89
00:04:24,670 --> 00:04:27,826
In modo che possiamo in modo ricorsivo
definire questo algoritmo.

90
00:04:27,826 --> 00:04:29,950
In altre parole, sulla
schermo qui, è un algoritmo

91
00:04:29,950 --> 00:04:33,130
per la ricerca di Mike Smith
tra le pagine di un libro di telefono.

92
00:04:33,130 --> 00:04:37,410
Quindi, in linea 7 e 10, diamo
solo dire esattamente questo.

93
00:04:37,410 --> 00:04:40,250
E io uso questo termine un momento
fa, e anzi, la ricorsione

94
00:04:40,250 --> 00:04:42,450
è la parola d'ordine, per ora,
ed è questo processo

95
00:04:42,450 --> 00:04:47,210
di fare qualcosa di ciclico da qualche modo
utilizzando il codice che hai già,

96
00:04:47,210 --> 00:04:49,722
e chiamarlo di nuovo,
e ancora, e ancora.

97
00:04:49,722 --> 00:04:51,930
Ora che sta per essere importante
che noi in qualche modo inferiore

98
00:04:51,930 --> 00:04:53,821
fuori, e non farlo infinitamente lungo.

99
00:04:53,821 --> 00:04:56,070
In caso contrario, stiamo andando a
hanno infatti un ciclo infinito.

100
00:04:56,070 --> 00:04:59,810
Ma vediamo se siamo in grado di prendere in prestito questa idea
di una ricorsione, facendo qualcosa di nuovo

101
00:04:59,810 --> 00:05:03,600
e ancora e ancora, per risolvere
il problema di ordinamento tramite merge

102
00:05:03,600 --> 00:05:05,900
sorta, tanto più efficiente.

103
00:05:05,900 --> 00:05:06,970
>> Quindi io do merge sort.

104
00:05:06,970 --> 00:05:07,920
Diamo un'occhiata.

105
00:05:07,920 --> 00:05:10,850
Così qui è pseudocodice, con
che potremmo implementare l'ordinamento,

106
00:05:10,850 --> 00:05:12,640
usando questo algoritmo chiamato merge sort.

107
00:05:12,640 --> 00:05:13,880
Ed è semplicemente questo.

108
00:05:13,880 --> 00:05:15,940
Su ingresso di n elementi,
in altre parole, se siete

109
00:05:15,940 --> 00:05:18,830
dato n elementi e numeri e
lettere o qualunque sia l'ingresso è,

110
00:05:18,830 --> 00:05:22,430
se sei dato n elementi, se
n è inferiore a 2, solo ritorno.

111
00:05:22,430 --> 00:05:22,930
Destra?

112
00:05:22,930 --> 00:05:26,430
Perché se n è minore di 2, che
significa che la mia lista di elementi

113
00:05:26,430 --> 00:05:30,446
o è di dimensione 0 o 1, e
in entrambi i casi banali,

114
00:05:30,446 --> 00:05:31,570
la lista è già ordinato.

115
00:05:31,570 --> 00:05:32,810
Se non esiste un elenco, è ordinato.

116
00:05:32,810 --> 00:05:35,185
E se c'è una lista di lunghezza
1, è ovviamente risolto.

117
00:05:35,185 --> 00:05:38,280
Quindi l'algoritmo deve solo
davvero fare qualcosa di interessante,

118
00:05:38,280 --> 00:05:40,870
se abbiamo due o più
Elementi dato a noi.

119
00:05:40,870 --> 00:05:42,440
Quindi diamo un'occhiata alla magia allora.

120
00:05:42,440 --> 00:05:47,500
Altrimenti ordinare la metà sinistra degli elementi,
quindi ordinare la metà destra di elementi,

121
00:05:47,500 --> 00:05:49,640
quindi unire le due metà ordinati.

122
00:05:49,640 --> 00:05:52,440
E che una specie di rompicapo
qui, è che io non faccio davvero

123
00:05:52,440 --> 00:05:56,190
sembrano avervi detto
nulla appena ancora, giusto?

124
00:05:56,190 --> 00:05:59,560
Tutto quello che ho detto è, data una lista di
n elementi, ordinare la metà sinistra,

125
00:05:59,560 --> 00:06:01,800
poi la metà destra, poi
unire le due metà ordinati,

126
00:06:01,800 --> 00:06:03,840
ma dove è la salsa segreto reale?

127
00:06:03,840 --> 00:06:05,260
Dov'è l'algoritmo?

128
00:06:05,260 --> 00:06:09,150
Beh, si scopre che quelle due righe
prima, la metà sinistra sorta di elementi,

129
00:06:09,150 --> 00:06:13,970
e specie metà destra di elementi,
sono chiamate ricorsive, per così dire.

130
00:06:13,970 --> 00:06:16,120
>> Dopo tutto, in questo
punto nel tempo, devo

131
00:06:16,120 --> 00:06:18,950
un algoritmo con cui
ordinare un sacco di elementi?

132
00:06:18,950 --> 00:06:19,450
Sì.

133
00:06:19,450 --> 00:06:20,620
E 'proprio qui.

134
00:06:20,620 --> 00:06:25,180
E 'proprio qui sullo schermo, e
modo da poter utilizzare la stessa serie di passaggi

135
00:06:25,180 --> 00:06:28,500
per ordinare la metà sinistra,
come posso la metà destra.

136
00:06:28,500 --> 00:06:30,420
E in effetti, ancora, e ancora.

137
00:06:30,420 --> 00:06:34,210
Quindi un modo o nell'altro, e faremo presto
vedere questo, la magia di merge sort

138
00:06:34,210 --> 00:06:37,967
è incorporato in quella finale
linea, fondendo le due metà ordinate.

139
00:06:37,967 --> 00:06:39,300
E questo sembra abbastanza intuitivo.

140
00:06:39,300 --> 00:06:41,050
Si prende due metà, e tu,
in qualche modo, si fondono insieme,

141
00:06:41,050 --> 00:06:43,260
e vedremo questo
concretamente in un attimo.

142
00:06:43,260 --> 00:06:45,080
>> Ma questo è un algoritmo completo.

143
00:06:45,080 --> 00:06:46,640
E vediamo esattamente perché.

144
00:06:46,640 --> 00:06:50,912
Beh, supponiamo che ci è dato questi stessi
otto elementi qui sullo schermo, uno

145
00:06:50,912 --> 00:06:53,120
attraverso otto, ma sono
in ordine apparentemente casuale.

146
00:06:53,120 --> 00:06:55,320
E l'obiettivo è a portata di mano
per ordinare questi elementi.

147
00:06:55,320 --> 00:06:58,280
Beh, come posso fare per
farlo utilizzando, di nuovo,

148
00:06:58,280 --> 00:07:00,407
merge sort, di cui al presente pseudocodice?

149
00:07:00,407 --> 00:07:02,740
E ancora, radicato in questo
la tua mente, solo per un momento.

150
00:07:02,740 --> 00:07:05,270
Il primo caso è abbastanza
banale, se è inferiore a 2,

151
00:07:05,270 --> 00:07:07,060
solo ritorno, non c'è lavoro da fare.

152
00:07:07,060 --> 00:07:09,290
Quindi, in realtà c'è solo tre
misure per tenere davvero in mente.

153
00:07:09,290 --> 00:07:11,081
Ancora una volta, e di nuovo, io sono
andando a voler avere

154
00:07:11,081 --> 00:07:13,980
per ordinare la metà sinistra,
ordinare la metà destra,

155
00:07:13,980 --> 00:07:15,890
e poi una volta loro
due metà sono ordinati,

156
00:07:15,890 --> 00:07:18,710
Voglio fondersi insieme
in una lista ordinata.

157
00:07:18,710 --> 00:07:19,940
Modo da tenere a mente.

158
00:07:19,940 --> 00:07:21,310
>> Quindi, ecco la lista originale.

159
00:07:21,310 --> 00:07:23,510
Cerchiamo di trattare questo come un
array, come abbiamo iniziato a

160
00:07:23,510 --> 00:07:25,800
in seconda settimana, che è un
blocco contiguo di memoria.

161
00:07:25,800 --> 00:07:28,480
In questo caso, contenente otto
numeri, back to back to back.

162
00:07:28,480 --> 00:07:30,700
E diciamo ora riferimento merge sort.

163
00:07:30,700 --> 00:07:33,300
Così Prima di tutto voglio ordinare
la metà sinistra di questo elenco,

164
00:07:33,300 --> 00:07:37,370
e facciamo, quindi,
concentrarsi su 4, 8, 6, e 2.

165
00:07:37,370 --> 00:07:41,000
>> Ora, come posso fare per
l'ordinamento di un elenco di dimensioni 4?

166
00:07:41,000 --> 00:07:45,990
Beh devo prendere in considerazione ora
classificare sinistra della metà sinistra.

167
00:07:45,990 --> 00:07:47,720
Ancora una volta, facciamo riavvolgere solo per un momento.

168
00:07:47,720 --> 00:07:51,010
Se il pseudocodice è questo,
e mi sono dato otto elementi,

169
00:07:51,010 --> 00:07:53,230
8 è ovviamente maggiore
o uguale a 2.

170
00:07:53,230 --> 00:07:54,980
Quindi, con il primo caso non si applica.

171
00:07:54,980 --> 00:07:58,120
Quindi, per ordinare otto elementi, in primo luogo ho
ordinare la metà sinistra di elementi,

172
00:07:58,120 --> 00:08:01,930
poi a ordinare la metà destra, poi mi fondo
le due metà ordinate, ciascuno di dimensioni 4.

173
00:08:01,930 --> 00:08:02,470
OK.

174
00:08:02,470 --> 00:08:07,480
>> Ma se hai appena detto a me, ordinare la
metà di sinistra, che ora è di dimensioni 4,

175
00:08:07,480 --> 00:08:09,350
Come faccio a ordinare la metà di sinistra?

176
00:08:09,350 --> 00:08:11,430
Beh, se ho un
ingresso di quattro elementi,

177
00:08:11,430 --> 00:08:14,590
Io Ordina sinistra
due, poi il diritto a due,

178
00:08:14,590 --> 00:08:16,210
e poi io li fondono insieme.

179
00:08:16,210 --> 00:08:18,700
Quindi, di nuovo, diventa un po '
di un rompicapo gioco qui,

180
00:08:18,700 --> 00:08:21,450
perché, specie di, devono
ricordare dove siete nella storia,

181
00:08:21,450 --> 00:08:23,620
ma alla fine della giornata,
dato un qualsiasi numero di elementi,

182
00:08:23,620 --> 00:08:25,620
si desidera prima di ordinare la
metà sinistra, poi la metà destra,

183
00:08:25,620 --> 00:08:26,661
poi unirle insieme.

184
00:08:26,661 --> 00:08:28,630
Cominciamo a fare esattamente questo.

185
00:08:28,630 --> 00:08:30,170
Ecco l'ingresso di otto elementi.

186
00:08:30,170 --> 00:08:31,910
Ora stiamo guardando la metà sinistra qui.

187
00:08:31,910 --> 00:08:33,720
Come faccio a ordinare quattro elementi?

188
00:08:33,720 --> 00:08:35,610
Beh, ho ordinare la metà di sinistra.

189
00:08:35,610 --> 00:08:37,720
Ora come faccio a ordinare la metà di sinistra?

190
00:08:37,720 --> 00:08:39,419
Beh mi è stata data da due elementi.

191
00:08:39,419 --> 00:08:41,240
Quindi cerchiamo di ordinare questi due elementi.

192
00:08:41,240 --> 00:08:44,540
2 è maggiore o
pari a 2, ovviamente.

193
00:08:44,540 --> 00:08:46,170
In modo che primo caso non si applica.

194
00:08:46,170 --> 00:08:49,010
>> Così ora ho ordinare sinistra
metà di questi due elementi.

195
00:08:49,010 --> 00:08:50,870
La metà sinistra, naturalmente, è solo 4.

196
00:08:50,870 --> 00:08:54,020
Allora, come faccio a ordinare un elenco di un elemento?

197
00:08:54,020 --> 00:08:57,960
Bene, ora, quella speciale caso base
up superiore, per così dire, si applica.

198
00:08:57,960 --> 00:09:01,470
1 è inferiore a 2, e la mia
lista è infatti di dimensioni 1.

199
00:09:01,470 --> 00:09:02,747
Così ho appena ritorno.

200
00:09:02,747 --> 00:09:03,580
Io non faccio nulla.

201
00:09:03,580 --> 00:09:06,770
E infatti, guardare a ciò che ho
fatto, 4 è già ordinato.

202
00:09:06,770 --> 00:09:09,220
Come se fossi già
parzialmente successo qui.

203
00:09:09,220 --> 00:09:11,750
>> Ora che sembra un po 'stupido
di rivendicare, ma è vero.

204
00:09:11,750 --> 00:09:13,700
4 è un elenco di dimensioni 1.

205
00:09:13,700 --> 00:09:15,090
E 'già ordinato.

206
00:09:15,090 --> 00:09:16,270
Questa è la metà di sinistra.

207
00:09:16,270 --> 00:09:18,010
Ora io a ordinare la metà destra.

208
00:09:18,010 --> 00:09:22,310
Mio ingresso è un elemento, 8
allo stesso modo, già ordinati.

209
00:09:22,310 --> 00:09:25,170
Stupido, troppo, ma ancora una volta,
questo principio di base

210
00:09:25,170 --> 00:09:28,310
sta per permetterci di costruire ora
in cima a questa con successo.

211
00:09:28,310 --> 00:09:32,260
4 ordinati, 8 è ordinato, ora
che cosa era che ultimo passo?

212
00:09:32,260 --> 00:09:35,330
Quindi la terza e ultima fase, qualsiasi
ora si sta ordinare una lista, richiamo,

213
00:09:35,330 --> 00:09:38,310
è stato quello di unire le due metà,
sinistra e destra.

214
00:09:38,310 --> 00:09:39,900
Quindi cerchiamo di fare esattamente questo.

215
00:09:39,900 --> 00:09:41,940
My metà sinistra è, ovviamente, 4.

216
00:09:41,940 --> 00:09:43,310
La mia metà destra è 8.

217
00:09:43,310 --> 00:09:44,100
>> Quindi cerchiamo di fare questo.

218
00:09:44,100 --> 00:09:46,410
Per prima cosa ho intenzione di stanziare
memoria aggiuntiva,

219
00:09:46,410 --> 00:09:48,680
che io rappresento qui,
come solo una matrice secondaria,

220
00:09:48,680 --> 00:09:49,660
che è abbastanza grande da contenere questo.

221
00:09:49,660 --> 00:09:52,243
Ma si può immaginare che si estende
quel rettangolo tutta la lunghezza,

222
00:09:52,243 --> 00:09:53,290
se abbiamo bisogno di più in seguito.

223
00:09:53,290 --> 00:09:58,440
Come faccio a prendere 4 e 8, e unire
questi due elenchi di dimensioni 1 insieme?

224
00:09:58,440 --> 00:10:00,270
Anche in questo caso, piuttosto semplice.

225
00:10:00,270 --> 00:10:03,300
4 viene prima, poi arriva 8.

226
00:10:03,300 --> 00:10:07,130
Perché se voglio ordinare la
metà sinistra, poi la metà destra,

227
00:10:07,130 --> 00:10:09,900
e quindi unire queste due metà
insieme, in modo ordinato,

228
00:10:09,900 --> 00:10:11,940
4 viene prima, poi arriva 8.

229
00:10:11,940 --> 00:10:15,810
>> Quindi ci sembra di fare progressi, anche
se non ho fatto alcun lavoro effettivo.

230
00:10:15,810 --> 00:10:17,800
Ma ricordate dove siamo nella storia.

231
00:10:17,800 --> 00:10:19,360
Abbiamo preso in origine otto elementi.

232
00:10:19,360 --> 00:10:21,480
Abbiamo risolto la metà di sinistra, che è 4.

233
00:10:21,480 --> 00:10:24,450
Poi abbiamo ordinato la metà sinistra
della metà sinistra, che era 2.

234
00:10:24,450 --> 00:10:25,270
E qui andiamo.

235
00:10:25,270 --> 00:10:26,920
Abbiamo finito con quel passo.

236
00:10:26,920 --> 00:10:29,930
>> Quindi, se abbiamo risolto il
lasciato metà del 2, ora siamo

237
00:10:29,930 --> 00:10:32,130
deve ordinare la metà destra 2.

238
00:10:32,130 --> 00:10:35,710
Quindi la metà destra 2 è
questi due valori qui, 6 e 2.

239
00:10:35,710 --> 00:10:40,620
Quindi cerchiamo di prendere ora un input di dimensione
2, e ordinare la metà sinistra, e poi

240
00:10:40,620 --> 00:10:42,610
la metà destra, e poi
unirle insieme.

241
00:10:42,610 --> 00:10:45,722
Bene come si ordina un elenco di dimensioni
1, contenente solo il numero 6?

242
00:10:45,722 --> 00:10:46,430
Ho già fatto.

243
00:10:46,430 --> 00:10:48,680
Tale elenco di dimensioni 1 è ordinato.

244
00:10:48,680 --> 00:10:52,140
>> Come faccio a ordinare un altro elenco di
formato 1, il cosiddetto metà destra.

245
00:10:52,140 --> 00:10:54,690
Beh, troppo, è già ordinato.

246
00:10:54,690 --> 00:10:56,190
Il numero 2 è solo.

247
00:10:56,190 --> 00:11:00,160
Così ora ho due metà, a sinistra e
a destra, ho bisogno di fondersi insieme.

248
00:11:00,160 --> 00:11:01,800
Lasciatemi mi dò qualche spazio in più.

249
00:11:01,800 --> 00:11:05,580
E mettere 2 in là,
poi 6 in là, così

250
00:11:05,580 --> 00:11:10,740
l'ordinamento tale elenco, a destra ea sinistra,
e la fusione insieme, in ultima analisi.

251
00:11:10,740 --> 00:11:12,160
Quindi sono in forma leggermente migliore.

252
00:11:12,160 --> 00:11:16,250
Non ho finito, perché chiaramente 4, 8, 2,
6 non è l'ordinamento finale che voglio.

253
00:11:16,250 --> 00:11:20,640
Ma ora ho due liste di dimensioni 2, che
hanno entrambi, rispettivamente stati ordinati.

254
00:11:20,640 --> 00:11:24,580
Così ora se si riavvolge nella vostra mente di
occhio, dove ha fatto che ci lascia?

255
00:11:24,580 --> 00:11:28,520
Ho iniziato con otto elementi, poi ho
whittled giù alla metà sinistra di 4,

256
00:11:28,520 --> 00:11:31,386
poi la metà sinistra di 2, e
poi la metà destra di 2,

257
00:11:31,386 --> 00:11:34,510
Ho finito, dunque, l'ordinamento sinistra
mezzo di 2, e la metà destra di 2,

258
00:11:34,510 --> 00:11:37,800
quindi qual è il terzo e ultimo passo qui?

259
00:11:37,800 --> 00:11:41,290
Devo fondersi insieme
due elenchi di dimensioni 2.

260
00:11:41,290 --> 00:11:42,040
Quindi cerchiamo di andare avanti.

261
00:11:42,040 --> 00:11:43,940
E sullo schermo qui, dare
me qualche memoria aggiuntiva,

262
00:11:43,940 --> 00:11:47,170
se tecnicamente, notato che ho
ha ottenuto un sacco di spazio vuoto sulla parte superiore

263
00:11:47,170 --> 00:11:47,670
Là.

264
00:11:47,670 --> 00:11:50,044
Se voglio essere particolarmente
spazio efficiente saggio,

265
00:11:50,044 --> 00:11:52,960
Potrei iniziare a muoversi gli elementi
avanti e indietro, sopra e sotto.

266
00:11:52,960 --> 00:11:55,460
Ma solo per chiarezza visiva,
Ho intenzione di mettere giù in basso,

267
00:11:55,460 --> 00:11:56,800
per mantenere le cose belle e pulite.

268
00:11:56,800 --> 00:11:58,150
>> Così ho due elenchi di dimensioni 2.

269
00:11:58,150 --> 00:11:59,770
Il primo elenco è dotato di 4 e 8.

270
00:11:59,770 --> 00:12:01,500
La seconda lista ha 2 e 6.

271
00:12:01,500 --> 00:12:03,950
Cerchiamo di unire quelli
insieme in modo ordinato.

272
00:12:03,950 --> 00:12:09,910
2, ovviamente, viene prima,
poi 4, poi 6, poi 8.

273
00:12:09,910 --> 00:12:12,560
E ora ci sembra di essere sempre
da qualche parte interessante.

274
00:12:12,560 --> 00:12:15,720
Metà Ora ho risolto del
lista, e per coincidenza, è

275
00:12:15,720 --> 00:12:18,650
tutti i numeri pari, ma che
è, infatti, solo una coincidenza.

276
00:12:18,650 --> 00:12:22,220
Ed ora ho ordinato la sinistra
mezzo, in modo che sia 2, 4, 6, e 8.

277
00:12:22,220 --> 00:12:23,430
Niente è fuori uso.

278
00:12:23,430 --> 00:12:24,620
Che si sente come il progresso.

279
00:12:24,620 --> 00:12:26,650
>> Ora ci si sente come ho
state parlando per sempre ora,

280
00:12:26,650 --> 00:12:29,850
così quello che resta da vedere se questo
algoritmo è, infatti, più efficiente.

281
00:12:29,850 --> 00:12:31,766
Ma stiamo attraversando
super metodicamente.

282
00:12:31,766 --> 00:12:34,060
Un computer, naturalmente,
farebbe così.

283
00:12:34,060 --> 00:12:34,840
Allora, dove siamo?

284
00:12:34,840 --> 00:12:36,180
Abbiamo iniziato con otto elementi.

285
00:12:36,180 --> 00:12:37,840
Ho risolto la metà sinistra del 4.

286
00:12:37,840 --> 00:12:39,290
Mi sembra di essere fatto con questo.

287
00:12:39,290 --> 00:12:42,535
Così ora il passo successivo è quello di
ordinare la metà destra della 4.

288
00:12:42,535 --> 00:12:44,410
E questa parte possiamo andare
attraverso un po 'più

289
00:12:44,410 --> 00:12:47,140
rapidamente, anche se sei
benvenuto per riavvolgere o mettere in pausa, semplicemente

290
00:12:47,140 --> 00:12:49,910
pensare attraverso di essa a
proprio ritmo, ma cosa

291
00:12:49,910 --> 00:12:53,290
che abbiamo ora è l'occasione per
fare la stessa algoritmo su quattro

292
00:12:53,290 --> 00:12:54,380
numeri diversi.

293
00:12:54,380 --> 00:12:57,740
>> Quindi cerchiamo di andare avanti, e concentrarsi su
la metà destra, che siamo qui.

294
00:12:57,740 --> 00:13:01,260
La metà sinistra di tale
metà destra, e ora il

295
00:13:01,260 --> 00:13:04,560
metà sinistra della sinistra
metà di quella metà destra,

296
00:13:04,560 --> 00:13:08,030
e come faccio a ordinare un elenco di dimensioni
1 contenente solo il numero 1?

297
00:13:08,030 --> 00:13:09,030
È già fatto.

298
00:13:09,030 --> 00:13:11,830
Come posso fare lo stesso per la lista
di dimensioni 1 contenente solo 7?

299
00:13:11,830 --> 00:13:12,840
È già fatto.

300
00:13:12,840 --> 00:13:16,790
Fase tre per questo mezzo poi
è quello di unire questi due elementi

301
00:13:16,790 --> 00:13:20,889
in un nuovo elenco di dimensioni 2, 1 e 7.

302
00:13:20,889 --> 00:13:23,180
Non sembrano aver fatto tutto
che molto lavoro interessante.

303
00:13:23,180 --> 00:13:24,346
Vediamo cosa succede dopo.

304
00:13:24,346 --> 00:13:29,210
Ho appena risolto la metà sinistra del
a destra la metà del mio ingresso originale.

305
00:13:29,210 --> 00:13:32,360
Ora cerchiamo di ordinare il giusto
mezzo, che contiene 5 e 3.

306
00:13:32,360 --> 00:13:35,740
Diamo ancora un'occhiata a sinistra
mezzo, ordinato, metà di destra, ordinato,

307
00:13:35,740 --> 00:13:39,120
e unire quei due insieme,
in qualche spazio aggiuntivo,

308
00:13:39,120 --> 00:13:41,670
3 viene prima, poi arriva 5.

309
00:13:41,670 --> 00:13:46,190
E così ora, abbiamo ordinato il
metà sinistra della metà destra

310
00:13:46,190 --> 00:13:49,420
del problema originale, e
la metà destra della metà destra

311
00:13:49,420 --> 00:13:50,800
del problema originale.

312
00:13:50,800 --> 00:13:52,480
Qual è il terzo e ultimo passo?

313
00:13:52,480 --> 00:13:54,854
Beh di fondere queste due metà insieme.

314
00:13:54,854 --> 00:13:57,020
Così mi permetta di ottenere un po 'di me stesso
spazio in più, ma, ancora una volta, io

315
00:13:57,020 --> 00:13:58,699
potrebbe essere utilizzando lo spazio sulla parte superiore di ricambio.

316
00:13:58,699 --> 00:14:00,490
Ma stiamo andando a tenere
semplice visivamente.

317
00:14:00,490 --> 00:14:07,070
Permettetemi di fondere in ora 1, e
poi 3, e poi 5 e quindi 7.

318
00:14:07,070 --> 00:14:10,740
In tal modo lasciandomi ora con il
metà destra del problema originale

319
00:14:10,740 --> 00:14:12,840
che è perfettamente ordinato.

320
00:14:12,840 --> 00:14:13,662
>> Allora, cosa rimane?

321
00:14:13,662 --> 00:14:16,120
Mi sento come se continuo a dire il
cose stesse di nuovo, e di nuovo,

322
00:14:16,120 --> 00:14:18,700
ma questo è riflettente del
fatto che stiamo utilizzando la ricorsione.

323
00:14:18,700 --> 00:14:21,050
Il processo di utilizzo di un
algoritmo ancora, e ancora,

324
00:14:21,050 --> 00:14:23,940
su piccoli sottoinsiemi di
il problema originale.

325
00:14:23,940 --> 00:14:27,580
Così ora ho un sinistro ordinato
metà del problema originale.

326
00:14:27,580 --> 00:14:30,847
Ho una mezza ordinato destra
del problema originale.

327
00:14:30,847 --> 00:14:32,180
Qual è il terzo e ultimo passo?

328
00:14:32,180 --> 00:14:33,590
Oh, è la fusione.

329
00:14:33,590 --> 00:14:34,480
Allora, facciamo così.

330
00:14:34,480 --> 00:14:36,420
Facciamo un po 'di destinare aggiuntivo
memoria, ma il mio dio, noi

331
00:14:36,420 --> 00:14:37,503
potrebbe mettere ovunque ora.

332
00:14:37,503 --> 00:14:40,356
Abbiamo così tanto spazio a disposizione
a noi, ma noi terremo le cose semplici.

333
00:14:40,356 --> 00:14:42,730
Invece di andare avanti e
avanti con la nostra memoria originale,

334
00:14:42,730 --> 00:14:44,480
facciamo solo fare
visivamente giù qui sotto,

335
00:14:44,480 --> 00:14:47,240
per finire la fusione
metà sinistra e la metà destra.

336
00:14:47,240 --> 00:14:49,279
>> Quindi attraverso la fusione, che cosa devo fare?

337
00:14:49,279 --> 00:14:50,820
Voglio prendere gli elementi in ordine.

338
00:14:50,820 --> 00:14:53,230
Così guardando la metà sinistra,
Vedo il primo numero è 2.

339
00:14:53,230 --> 00:14:55,230
Guardo la metà destra,
Vedo il primo numero

340
00:14:55,230 --> 00:14:58,290
è 1, quindi ovviamente che
numero Voglio cogliere fuori,

341
00:14:58,290 --> 00:15:00,430
e mettere al primo posto nella mia lista finale?

342
00:15:00,430 --> 00:15:01,449
Naturalmente, 1.

343
00:15:01,449 --> 00:15:02,990
Ora voglio fare la stessa domanda.

344
00:15:02,990 --> 00:15:05,040
Sulla metà sinistra, ho
ancora ottenuto il numero 2.

345
00:15:05,040 --> 00:15:07,490
Sulla metà destra,
Ho il numero 3.

346
00:15:07,490 --> 00:15:08,930
Quale voglio scegliere?

347
00:15:08,930 --> 00:15:11,760
Naturalmente, il numero 2 e
ora notare i candidati

348
00:15:11,760 --> 00:15:13,620
4 sono a sinistra, 3 a destra.

349
00:15:13,620 --> 00:15:15,020
Diamo, naturalmente, scegliere 3.

350
00:15:15,020 --> 00:15:18,020
Ora i candidati sono 4 su
sinistra, 5 a destra.

351
00:15:18,020 --> 00:15:19,460
Noi, naturalmente, scegliere 4.

352
00:15:19,460 --> 00:15:21,240
6 a sinistra, a destra 5.

353
00:15:21,240 --> 00:15:22,730
Noi, naturalmente, scegliere 5.

354
00:15:22,730 --> 00:15:25,020
6 sulla sinistra, 7 sulla destra.

355
00:15:25,020 --> 00:15:29,320
Scegliamo 6, e poi noi
scegliete 7, e quindi scegliamo 8.

356
00:15:29,320 --> 00:15:30,100
Voila.

357
00:15:30,100 --> 00:15:34,370
>> Così un enorme numero di parole successiva, abbiamo
hanno ordinato questo elenco di otto elementi

358
00:15:34,370 --> 00:15:38,450
in un elenco di uno a otto,
che è in aumento ad ogni passo,

359
00:15:38,450 --> 00:15:40,850
ma quanto tempo ha fatto
ci vuole noi a farlo.

360
00:15:40,850 --> 00:15:43,190
Beh, io ho deliberatamente
cose disposte Pittoricamente

361
00:15:43,190 --> 00:15:46,330
qui, in modo che possiamo tipo di
vedere o apprezzare la divisione

362
00:15:46,330 --> 00:15:49,060
a conquistare che sta succedendo.

363
00:15:49,060 --> 00:15:52,830
>> Infatti, se si guarda indietro alla veglia funebre,
Ho lasciato tutte queste linee tratteggiate

364
00:15:52,830 --> 00:15:55,660
in segnaposti, è possibile,
tipo di vedere, in ordine inverso,

365
00:15:55,660 --> 00:15:58,800
se è sorta di guardare indietro a
la storia ora, la mia lista originale

366
00:15:58,800 --> 00:16:00,250
è, ovviamente, di dimensioni 8.

367
00:16:00,250 --> 00:16:03,480
E poi in precedenza, sono stato
si tratta di due elenchi di dimensioni 4,

368
00:16:03,480 --> 00:16:08,400
e poi quattro liste di dimensioni 2,
e poi otto liste di dimensioni 1.

369
00:16:08,400 --> 00:16:10,151
>> Così che cosa fa questo,
tipo di, vi ricorderà?

370
00:16:10,151 --> 00:16:11,858
Ebbene, infatti, qualsiasi
gli algoritmi ABBIAMO

371
00:16:11,858 --> 00:16:14,430
guardato finora dove siamo
dividere, e si dividono, e dividere,

372
00:16:14,430 --> 00:16:19,500
continuare ad avere le cose di nuovo, e
di nuovo, in questa idea generale.

373
00:16:19,500 --> 00:16:23,100
E quindi c'è qualcosa
logaritmica succedendo qui.

374
00:16:23,100 --> 00:16:26,790
E non è del tutto log n, ma
c'è una componente logaritmica

375
00:16:26,790 --> 00:16:28,280
a quello che abbiamo appena fatto.

376
00:16:28,280 --> 00:16:31,570
>> Consideriamo ora come che in realtà è.

377
00:16:31,570 --> 00:16:34,481
Così accedere di n, ancora una volta è stato
un grande tempo di esecuzione,

378
00:16:34,481 --> 00:16:36,980
quando abbiamo fatto qualcosa di simile
ricerca binaria, come noi ora chiamiamo,

379
00:16:36,980 --> 00:16:40,090
la strategia divide et impera
via che abbiamo trovato Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Ora tecnicamente.

381
00:16:41,020 --> 00:16:43,640
Ecco logaritmo in base 2 di n, anche
anche se nella maggior parte delle classi di matematica,

382
00:16:43,640 --> 00:16:45,770
10 è di solito la base che si assume.

383
00:16:45,770 --> 00:16:48,940
Ma gli scienziati informatici quasi sempre
pensare e parlare in termini di base 2,

384
00:16:48,940 --> 00:16:52,569
quindi generalmente solo dire di registro
n, invece di logaritmo in base 2 di n,

385
00:16:52,569 --> 00:16:55,110
ma sono esattamente uno e il
stesso nel mondo di calcolatore

386
00:16:55,110 --> 00:16:57,234
la scienza, e come una digressione,
c'è un fattore costante

387
00:16:57,234 --> 00:17:01,070
differenza tra i due, quindi è
Moot comunque, per motivi formali.

388
00:17:01,070 --> 00:17:04,520
>> Ma per ora, ciò che ci preoccupa
circa è questo esempio.

389
00:17:04,520 --> 00:17:08,520
Quindi cerchiamo di non dimostrare con l'esempio, ma a
utilizzare almeno un esempio dei numeri

390
00:17:08,520 --> 00:17:10,730
a portata di mano come un controllo di integrità, se si vuole.

391
00:17:10,730 --> 00:17:14,510
Così in precedenza la formula era logaritmo in base
2 di n, ma ciò è n in questo caso.

392
00:17:14,510 --> 00:17:18,526
Ho avuto i numeri n originali, o 8
del numero originale appositamente.

393
00:17:18,526 --> 00:17:20,359
Ora è stato un po '
mentre, ma sono abbastanza

394
00:17:20,359 --> 00:17:25,300
Assicurarsi che logaritmo in base 2
del valore 8 è 3,

395
00:17:25,300 --> 00:17:29,630
e in effetti, cosa c'è di bello di questo è
3 che è esattamente il numero di volte

396
00:17:29,630 --> 00:17:33,320
che è possibile dividere un lista
di nuovo, e ancora di lunghezza 8,

397
00:17:33,320 --> 00:17:36,160
e ancora, fino a quando si è lasciato
con liste di appena formato 1.

398
00:17:36,160 --> 00:17:36,660
Destra?

399
00:17:36,660 --> 00:17:40,790
8 va a 4, va a 2,
va a 1, e questo è

400
00:17:40,790 --> 00:17:43,470
riflettente esattamente questo
immagine abbiamo avuto solo un momento fa.

401
00:17:43,470 --> 00:17:47,160
Quindi un po 'di buon senso controllare da dove
il logaritmo è effettivamente coinvolto.

402
00:17:47,160 --> 00:17:50,180
>> Così ora, che altro è coinvolto qui? n.

403
00:17:50,180 --> 00:17:53,440
Così notare che ogni
volta ho diviso la lista,

404
00:17:53,440 --> 00:17:58,260
anche se in ordine inverso nella storia
qui, stavo ancora facendo cose n.

405
00:17:58,260 --> 00:18:02,320
Questo passo ha richiesto che la fusione
Tocco ognuno dei numeri,

406
00:18:02,320 --> 00:18:05,060
per farlo scorrere in
la sua posizione appropriata.

407
00:18:05,060 --> 00:18:10,760
Quindi, anche se l'altezza di questo
diagramma è di dimensioni del registro n di n o 3,

408
00:18:10,760 --> 00:18:13,860
specificamente, in altre parole,
Ho fatto tre divisioni qui.

409
00:18:13,860 --> 00:18:18,800
Quanto lavoro ho fatto orizzontalmente
lungo questo grafico ogni volta?

410
00:18:18,800 --> 00:18:21,110
>> Beh, ho fatto n passi di
lavorare, perché se ho

411
00:18:21,110 --> 00:18:24,080
ottenuto quattro elementi e quattro elementi,
e ho bisogno di fondersi insieme.

412
00:18:24,080 --> 00:18:26,040
Ho bisogno di passare attraverso
questi quattro e questi quattro,

413
00:18:26,040 --> 00:18:28,123
in ultima analisi, per unirle
torna in otto elementi.

414
00:18:28,123 --> 00:18:32,182
Se al contrario ho otto dita
qui, che non lo faccio, e otto

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- Se ho
ottenuto quattro dita qui,

416
00:18:34,390 --> 00:18:37,380
che faccio, quattro dita
qui, che faccio,

417
00:18:37,380 --> 00:18:40,590
poi è la stessa
esempio di prima, se lo faccio

418
00:18:40,590 --> 00:18:44,010
hanno otto dita anche se in
totale, che posso, di tipo, fare.

419
00:18:44,010 --> 00:18:47,950
Posso esattamente fare qui,
allora posso certamente

420
00:18:47,950 --> 00:18:50,370
unire tutti questi elenchi
di dimensioni 1 insieme.

421
00:18:50,370 --> 00:18:54,050
Ma certamente devo guardare
ad ogni elemento esattamente una volta.

422
00:18:54,050 --> 00:18:59,640
Quindi l'altezza di questo processo è log n,
la larghezza di questo processo, per così dire,

423
00:18:59,640 --> 00:19:02,490
è n, per cui ciò che ci sembra
di avere, in ultima analisi, è

424
00:19:02,490 --> 00:19:06,470
un tempo di esecuzione di dimensione n volte log n.

425
00:19:06,470 --> 00:19:08,977
>> In altre parole, abbiamo diviso
l'elenco, registro n volte,

426
00:19:08,977 --> 00:19:11,810
ma ogni volta che abbiamo fatto, abbiamo avuto
toccare ognuno degli elementi

427
00:19:11,810 --> 00:19:13,560
al fine di unire i loro
tutti insieme, che

428
00:19:13,560 --> 00:19:18,120
fu n per passo, in modo da avere n volte il log n,
o come un informatico direbbe,

429
00:19:18,120 --> 00:19:20,380
asintoticamente, che
sarebbe la parola grossa

430
00:19:20,380 --> 00:19:22,810
per descrivere la tomaia
vincolato su un tempo di esecuzione,

431
00:19:22,810 --> 00:19:28,010
ci sono in esecuzione in una grande o
di log n tempo, per così dire.

432
00:19:28,010 --> 00:19:31,510
>> Ora, questo è significativo, perché
ricordano quello che i tempi di esecuzione sono stati

433
00:19:31,510 --> 00:19:34,120
con bubble sort, e la selezione
ordinare e insertion sort,

434
00:19:34,120 --> 00:19:38,200
e anche un paio di altri che esistono,
n quadrato era dove eravamo.

435
00:19:38,200 --> 00:19:39,990
E si può, un po ', questa qui.

436
00:19:39,990 --> 00:19:45,720
Se n è ovviamente quadrato n volte
n, ma qui abbiamo n volte log N,

437
00:19:45,720 --> 00:19:48,770
e sappiamo già da settimana
zero, cioè log n, logaritmico,

438
00:19:48,770 --> 00:19:50,550
è meglio di qualcosa lineare.

439
00:19:50,550 --> 00:19:52,930
Dopo tutto, ricordare l'immagine
con il rosso e il giallo

440
00:19:52,930 --> 00:19:56,500
e le linee verdi che abbiamo disegnato, il
Linea logaritmica verde era molto più basso.

441
00:19:56,500 --> 00:20:00,920
E quindi, molto meglio e più velocemente
che le linee gialle e rosse diritte,

442
00:20:00,920 --> 00:20:05,900
n volte il log-n è, infatti, una migliore
di n volte n o n squadrato.

443
00:20:05,900 --> 00:20:09,110
>> Quindi ci sembra di avere
identificato un algoritmo di unione

444
00:20:09,110 --> 00:20:11,870
tipo che viene eseguito in tanto
tempo più veloce, e in effetti,

445
00:20:11,870 --> 00:20:16,560
è per questo che, all'inizio di questa settimana, quando
abbiamo visto che gara tra bolla

446
00:20:16,560 --> 00:20:20,750
sort, selection sort, e unire
Ordina, merge sort davvero, davvero vinto.

447
00:20:20,750 --> 00:20:23,660
E in effetti, non abbiamo neanche aspettare
per bubble sort e ordinamento per selezione

448
00:20:23,660 --> 00:20:24,790
finire.

449
00:20:24,790 --> 00:20:27,410
>> Ora diamo un altro passaggio
a questo, da un po 'più

450
00:20:27,410 --> 00:20:31,030
punto di vista formale, proprio in
caso, questo risuona meglio

451
00:20:31,030 --> 00:20:33,380
quella discussione livello superiore.

452
00:20:33,380 --> 00:20:34,880
Quindi, ecco di nuovo l'algoritmo.

453
00:20:34,880 --> 00:20:36,770
Proviamo a chiederci,
ciò che il tempo di esecuzione

454
00:20:36,770 --> 00:20:39,287
è di questo algoritmi varie fasi?

455
00:20:39,287 --> 00:20:41,620
Dividiamo in primo
caso e il secondo caso.

456
00:20:41,620 --> 00:20:46,280
L'IF e l'altro nel caso in cui,
Se n è inferiore a 2, appena di ritorno.

457
00:20:46,280 --> 00:20:47,580
Si sente come costante di tempo.

458
00:20:47,580 --> 00:20:50,970
E ', specie di, come due fasi,
Se n è inferiore a 2, per poi tornare.

459
00:20:50,970 --> 00:20:54,580
Ma come abbiamo detto il Lunedi,
costante di tempo, o grande o di 1,

460
00:20:54,580 --> 00:20:57,130
possono essere due, tre passi
passi, anche 1.000 gradini.

461
00:20:57,130 --> 00:20:59,870
Ciò che conta è che è
un numero costante di passi.

462
00:20:59,870 --> 00:21:03,240
Così il giallo evidenziato pseudocodice
qui corre in, che chiameremo,

463
00:21:03,240 --> 00:21:04,490
costante di tempo.

464
00:21:04,490 --> 00:21:06,780
Quindi più formalmente, e
stiamo andando a-- questo

465
00:21:06,780 --> 00:21:09,910
sarà la misura in cui
formalizzare questo diritto now-- T di n,

466
00:21:09,910 --> 00:21:15,030
il tempo di esecuzione di un problema
che prende n quarantina come input,

467
00:21:15,030 --> 00:21:19,150
equivale grosso o di uno,
Se N è inferiore a 2.

468
00:21:19,150 --> 00:21:20,640
Quindi è subordinata tale.

469
00:21:20,640 --> 00:21:24,150
Quindi, per essere chiaro, se n è inferiore a
2, abbiamo una lista molto breve, quindi

470
00:21:24,150 --> 00:21:29,151
il tempo di esecuzione, T di n, dove n è
1 o 0, in questo caso molto specifico,

471
00:21:29,151 --> 00:21:30,650
è solo sarà tempo costante.

472
00:21:30,650 --> 00:21:32,691
Sta andando a prendere uno
passo, due passi, qualunque cosa.

473
00:21:32,691 --> 00:21:33,950
Si tratta di un numero fisso di passaggi.

474
00:21:33,950 --> 00:21:38,840
>> Così la parte succosa deve essere sicuramente in
l'altro caso in pseudocodice.

475
00:21:38,840 --> 00:21:40,220
Il caso ELSE.

476
00:21:40,220 --> 00:21:44,870
Ordina metà sinistra di elementi, tipo giusto
la metà di elementi, si fondono metà ordinati.

477
00:21:44,870 --> 00:21:46,800
Quanto dura ciascuno di questi passi prendere?

478
00:21:46,800 --> 00:21:49,780
Ebbene, se il funzionamento
tempo per ordinare n elementi

479
00:21:49,780 --> 00:21:53,010
è, chiamiamolo molto
genericamente, T di n,

480
00:21:53,010 --> 00:21:55,500
allora l'ordinamento sinistra
metà degli elementi

481
00:21:55,500 --> 00:21:59,720
è, un po ', come dire,
T di n diviso 2,

482
00:21:59,720 --> 00:22:03,000
e similmente classificare la metà destra
di elementi è, un po ', come dire,

483
00:22:03,000 --> 00:22:06,974
T di n diviso 2, e poi
fondendo le due metà ordinati.

484
00:22:06,974 --> 00:22:08,890
Beh, se ho un po '
numero di elementi qui,

485
00:22:08,890 --> 00:22:11,230
come quattro, e qualche numero
di elementi qui, come quattro,

486
00:22:11,230 --> 00:22:14,650
e devo unire ciascuno di questi quattro
in, e ciascuno di questi quattro, uno

487
00:22:14,650 --> 00:22:17,160
dopo l'altra, in modo che
in ultima analisi, ho otto elementi.

488
00:22:17,160 --> 00:22:20,230
Ci si sente come questo è grande o di n passi?

489
00:22:20,230 --> 00:22:23,500
Se ho n dita e ciascuno di
li deve essere fusi in luogo,

490
00:22:23,500 --> 00:22:25,270
che è come un altro n passi.

491
00:22:25,270 --> 00:22:27,360
>> Così infatti formulaically,
possiamo esprimere questo,

492
00:22:27,360 --> 00:22:29,960
anche se un po spaventosamente in un primo momento
sguardo, ma è qualcosa

493
00:22:29,960 --> 00:22:31,600
che cattura esattamente questa logica.

494
00:22:31,600 --> 00:22:35,710
Il tempo di esecuzione, T di n, n IF
è maggiore o uguale a 2.

495
00:22:35,710 --> 00:22:42,500
In questo caso, il caso ELSE, è T di n
diviso 2, oltre a T di N diviso 2,

496
00:22:42,500 --> 00:22:45,320
più grande o di n, un po '
Numero lineare di passi,

497
00:22:45,320 --> 00:22:51,630
forse esattamente n, forse 2 volte
n, ma è grosso modo, ordine di n.

498
00:22:51,630 --> 00:22:54,060
In modo che, anche, è come possiamo
esprimere questo formulaically.

499
00:22:54,060 --> 00:22:56,809
Ora non si sa questo meno
avete registrato nella vostra mente,

500
00:22:56,809 --> 00:22:58,710
o cercarlo nella
indietro di un libro di testo, che

501
00:22:58,710 --> 00:23:00,501
potrebbe avere un po '
cheat sheet, alla fine,

502
00:23:00,501 --> 00:23:03,940
ma questa è, in effetti, andando
ci danno una grande o di n log n,

503
00:23:03,940 --> 00:23:06,620
perché la ricorrenza che
che vedete qui sullo schermo,

504
00:23:06,620 --> 00:23:09,550
se effettivamente fatto fuori, con
un numero infinito di esempi,

505
00:23:09,550 --> 00:23:13,000
o avete fatto formulaically, si farebbe
vedere che questo, perché questa formula

506
00:23:13,000 --> 00:23:17,100
si è ricorsivo, con t
n sopra qualcosa sulla destra,

507
00:23:17,100 --> 00:23:21,680
e t di n sopra sulla sinistra, questo può
effettivamente essere espressa, in ultima analisi,

508
00:23:21,680 --> 00:23:24,339
grande andare log n n.

509
00:23:24,339 --> 00:23:26,130
Se non convinto, che è
bene per ora, solo

510
00:23:26,130 --> 00:23:28,960
prendere sulla fede, quella che è, in effetti,
cosa che porta alla recidiva,

511
00:23:28,960 --> 00:23:31,780
ma questo è solo un po 'più di un
approccio matematico a guardare

512
00:23:31,780 --> 00:23:36,520
al tempo di esecuzione di merge sort
in base alla sua pseudocodice solo.

513
00:23:36,520 --> 00:23:39,030
>> Ora diamo un po 'di
sfiato da tutto questo,

514
00:23:39,030 --> 00:23:41,710
e dare un'occhiata a un
certo ex senatore, che

515
00:23:41,710 --> 00:23:44,260
potrebbe apparire un po 'familiare,
che si sedette con Google Eric

516
00:23:44,260 --> 00:23:48,410
Schmidt, qualche tempo fa, per un colloquio
sul palco, di fronte a un sacco

517
00:23:48,410 --> 00:23:53,710
di persone, parlare in ultima analisi su
un argomento, che è abbastanza ormai familiare.

518
00:23:53,710 --> 00:23:54,575
Diamo un'occhiata.

519
00:23:54,575 --> 00:24:01,020

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: ora senatore,
tu sei qui a Google,

521
00:24:03,890 --> 00:24:09,490
e mi piace pensare al
presidenza come un colloquio di lavoro.

522
00:24:09,490 --> 00:24:11,712
Ora è difficile trovare un lavoro come presidente.

523
00:24:11,712 --> 00:24:12,670
Il presidente Obama: Giusto.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: E tu sei
intenzione di fare [incomprensibile] ora.

525
00:24:13,940 --> 00:24:15,523
E 'anche difficile ottenere un lavoro presso Google.

526
00:24:15,523 --> 00:24:17,700
Il presidente Obama: Giusto.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Abbiamo domande,
e chiediamo ai nostri candidati domande,

528
00:24:21,330 --> 00:24:24,310
e questo è da Larry Schwimmer.

529
00:24:24,310 --> 00:24:25,890
>> PRESIDENTE OBAMA: OK.

530
00:24:25,890 --> 00:24:27,005
>> Eric Schmidt: Che cosa?

531
00:24:27,005 --> 00:24:28,130
Voi ragazzi che io stia scherzando?

532
00:24:28,130 --> 00:24:30,590
E 'proprio qui.

533
00:24:30,590 --> 00:24:33,490
Qual è il modo più efficace per
ordinare un milione di numeri interi a 32 bit?

534
00:24:33,490 --> 00:24:37,560

535
00:24:37,560 --> 00:24:38,979
>> PRESIDENTE OBAMA: Well--

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: A volte,
forse mi dispiace, maybe--

537
00:24:41,020 --> 00:24:42,750
Il presidente Obama: No, no,
no, no, no, io think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: Che non è it--

539
00:24:43,240 --> 00:24:45,430
PRESIDENTE OBAMA: I
pensare, credo che la bolla

540
00:24:45,430 --> 00:24:46,875
specie sarebbe il modo sbagliato di procedere.

541
00:24:46,875 --> 00:24:49,619

542
00:24:49,619 --> 00:24:50,535
Eric Schmidt: Andiamo.

543
00:24:50,535 --> 00:24:52,200
Chi lo ha detto questo?

544
00:24:52,200 --> 00:24:54,020
OK.

545
00:24:54,020 --> 00:24:55,590
Non ho l'informatica on--

546
00:24:55,590 --> 00:24:58,986
>> PRESIDENTE OBAMA: ABBIAMO
ottenuto nostre spie in là.

547
00:24:58,986 --> 00:24:59,860
IL PROFESSORE: Va bene.

548
00:24:59,860 --> 00:25:03,370
Lasciamo dietro di noi ora il
mondo teorico di algoritmi

549
00:25:03,370 --> 00:25:06,520
nell'analisi asintotica
dello stesso, e tornare a alcuni argomenti

550
00:25:06,520 --> 00:25:09,940
dalla settimana zero e uno, e inizio
per rimuovere alcune ruote di formazione,

551
00:25:09,940 --> 00:25:10,450
se vuoi.

552
00:25:10,450 --> 00:25:13,241
In modo che si capisce davvero
in ultima analisi, da zero, ciò che è

553
00:25:13,241 --> 00:25:16,805
succedendo sotto il cofano, quando si
scrivere, compilare, ed eseguire programmi.

554
00:25:16,805 --> 00:25:19,680
Ricordiamo in particolare, che questo era
il primo programma C abbiamo guardato,

555
00:25:19,680 --> 00:25:22,840
una canonica semplice programma,
di sorta, relativamente parlando,

556
00:25:22,840 --> 00:25:24,620
in cui, stampa, Ciao Mondo.

557
00:25:24,620 --> 00:25:27,610
E ricordo che ho detto, il processo
che il codice sorgente passa attraverso

558
00:25:27,610 --> 00:25:28,430
è esattamente questo.

559
00:25:28,430 --> 00:25:31,180
Prendete il vostro codice sorgente, passa
attraverso un compilatore, come Clang,

560
00:25:31,180 --> 00:25:34,650
e viene fuori codice oggetto, che
potrebbe apparire come questo, zero e uno

561
00:25:34,650 --> 00:25:37,880
che la CPU del computer, centrale
unità di elaborazione o il cervello,

562
00:25:37,880 --> 00:25:39,760
in ultima analisi, capisce.

563
00:25:39,760 --> 00:25:42,460
>> Si scopre che questo è un
po 'di una semplificazione eccessiva,

564
00:25:42,460 --> 00:25:44,480
che siamo ora in una
grado di prendere in giro a parte

565
00:25:44,480 --> 00:25:46,720
per capire che cosa è veramente stato
succedendo sotto il cofano

566
00:25:46,720 --> 00:25:48,600
ogni volta che si esegue
Clang, o più in generale,

567
00:25:48,600 --> 00:25:53,040
ogni volta che si effettua un programma,
utilizzando Marca e CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
In particolare, cose del genere
questa sarà subito generato,

569
00:25:56,760 --> 00:25:58,684
quando si compila il programma.

570
00:25:58,684 --> 00:26:00,600
In altre parole, quando si
prendere il codice sorgente

571
00:26:00,600 --> 00:26:04,390
e compilarlo, ciò che è prima
essendo uscita dal Clang

572
00:26:04,390 --> 00:26:06,370
è qualcosa di noto come codice assembly.

573
00:26:06,370 --> 00:26:08,990
E infatti, sembra esattamente come questo.

574
00:26:08,990 --> 00:26:11,170
>> Ho eseguito un comando al
linea di comando in precedenza.

575
00:26:11,170 --> 00:26:16,260
Ciao.c Clang precipitare capitale s,
e questo ha creato un file

576
00:26:16,260 --> 00:26:19,490
per me chiamati hello.s,
all'interno del quale erano esattamente

577
00:26:19,490 --> 00:26:22,290
questi contenuti, e un po 'più
sopra e poco più sotto,

578
00:26:22,290 --> 00:26:25,080
ma ho messo il più succosi
informazioni qui sullo schermo.

579
00:26:25,080 --> 00:26:29,190
E se si guarda da vicino, vedrete
almeno alcune parole chiave familiare.

580
00:26:29,190 --> 00:26:31,330
Abbiamo principale in alto.

581
00:26:31,330 --> 00:26:35,140
Abbiamo printf nel mezzo.

582
00:26:35,140 --> 00:26:38,670
E abbiamo anche ciao mondo
backslash n tra virgolette sottostanti.

583
00:26:38,670 --> 00:26:42,450
>> E tutto il resto qui
è istruzioni molto basso livello

584
00:26:42,450 --> 00:26:45,500
che la CPU del computer capisce.

585
00:26:45,500 --> 00:26:50,090
Istruzioni della CPU che si muovono memoria
intorno, che le stringhe di carico dalla memoria,

586
00:26:50,090 --> 00:26:52,750
e in ultima analisi, la stampa
le cose sullo schermo.

587
00:26:52,750 --> 00:26:56,780
Ora, cosa succede se dopo
questo codice assembly viene generato?

588
00:26:56,780 --> 00:26:59,964
In ultima analisi, si fa, infatti,
ancora generare codice oggetto.

589
00:26:59,964 --> 00:27:02,630
Ma i passi che hanno veramente
sta succedendo sotto il cofano

590
00:27:02,630 --> 00:27:04,180
guardare un po 'più simile a questo.

591
00:27:04,180 --> 00:27:08,390
Il codice sorgente diviene codice assembly,
che poi diviene codice oggetto,

592
00:27:08,390 --> 00:27:11,930
e le parole chiave qui è che,
quando si compila il codice sorgente,

593
00:27:11,930 --> 00:27:16,300
viene fuori codice assembly, e poi
quando si assemblano il codice assembly,

594
00:27:16,300 --> 00:27:17,800
viene fuori codice oggetto.

595
00:27:17,800 --> 00:27:20,360
>> Ora Clang è super sofisticato,
come un sacco di compilatori,

596
00:27:20,360 --> 00:27:23,151
e lo fa tutti questi passaggi
insieme, e non necessariamente

597
00:27:23,151 --> 00:27:25,360
Uscita qualsiasi intermedio
i file che si può anche vedere.

598
00:27:25,360 --> 00:27:28,400
Compila solo le cose,
che è il termine generale che

599
00:27:28,400 --> 00:27:30,000
descrive l'intero processo.

600
00:27:30,000 --> 00:27:32,000
Ma se si vuole veramente
essere particolare, c'è

601
00:27:32,000 --> 00:27:34,330
molto più in corso anche lì.

602
00:27:34,330 --> 00:27:38,860
>> Ma consideriamo anche ora che anche
che super semplice programma, hello.c,

603
00:27:38,860 --> 00:27:40,540
detta funzione.

604
00:27:40,540 --> 00:27:41,870
Si chiama printf.

605
00:27:41,870 --> 00:27:46,900
Ma non ho scritto printf, infatti,
che viene fornito con c, per così dire.

606
00:27:46,900 --> 00:27:51,139
E 'un richiamo funzione che è
dichiarato in io.h standard, che

607
00:27:51,139 --> 00:27:53,180
è un file di intestazione, che
è un argomento che sarà in realtà

608
00:27:53,180 --> 00:27:55,780
immergersi più in profondità in breve tempo.

609
00:27:55,780 --> 00:27:58,000
Ma un file di intestazione è
tipicamente accompagnato

610
00:27:58,000 --> 00:28:02,920
da un file di codice, file di codice sorgente, in modo
molto simile esiste io.h. norma

611
00:28:02,920 --> 00:28:05,930
>> Qualche tempo fa, qualcuno,
o qualcuno, ha anche scritto

612
00:28:05,930 --> 00:28:11,040
un file chiamato io.c standard in
che le definizioni attuali,

613
00:28:11,040 --> 00:28:15,220
o implementazioni di printf,
e mazzi di altre funzioni,

614
00:28:15,220 --> 00:28:16,870
sono effettivamente scritti.

615
00:28:16,870 --> 00:28:22,140
Quindi, dato che, se si considera che ha
qui a sinistra, ciao.c, che quando

616
00:28:22,140 --> 00:28:26,250
compilato, ci dà hello.s, anche se
Clang non si preoccupa di risparmio in un posto

617
00:28:26,250 --> 00:28:31,360
possiamo vedere, e che codice assembly
viene assemblato in hello.o, che

618
00:28:31,360 --> 00:28:34,630
è, infatti, il nome di default
data ogni volta che si compila fonte

619
00:28:34,630 --> 00:28:39,350
codificare in codice oggetto, ma non sono
abbastanza pronto per eseguirlo ancora,

620
00:28:39,350 --> 00:28:41,460
perché un altro passo
deve accadere, e ha

621
00:28:41,460 --> 00:28:44,440
sta accadendo per il passato poche
settimane, forse a tua insaputa.

622
00:28:44,440 --> 00:28:47,290
>> In particolare da qualche parte
in CS50 IDE, e questo,

623
00:28:47,290 --> 00:28:49,870
troppo, sarà un po 'di un
semplificazione per un momento,

624
00:28:49,870 --> 00:28:54,670
vi è, o era un tempo,
un file chiamato io.c standard

625
00:28:54,670 --> 00:28:58,440
che qualcuno compilato in
io.s standard o l'equivalente,

626
00:28:58,440 --> 00:29:02,010
che qualcuno poi assemblati
in io.o di serie,

627
00:29:02,010 --> 00:29:04,600
o risulta in un
lima leggermente diverso

628
00:29:04,600 --> 00:29:07,220
formato che può avere un diverso
file di estensione del tutto,

629
00:29:07,220 --> 00:29:11,720
ma in teoria e concettualmente, esattamente
tali passaggi dovevano accadere in qualche forma.

630
00:29:11,720 --> 00:29:14,060
Vale a dire, che ora
quando sto scrivendo un programma,

631
00:29:14,060 --> 00:29:17,870
hello.c, che dice basta, ciao mondo,
e sto utilizzando il codice di qualcun altro

632
00:29:17,870 --> 00:29:22,480
come printf, che una volta era su un
tempo, in un file chiamato io.c standard

633
00:29:22,480 --> 00:29:26,390
quindi in qualche modo devo prendere il mio
codice oggetto, i miei e quelli, zero

634
00:29:26,390 --> 00:29:29,260
e l'oggetto di quella persona
codice, o zero e uno,

635
00:29:29,260 --> 00:29:34,970
e in qualche modo collegarli insieme in
un file finale, chiamato ciao, che

636
00:29:34,970 --> 00:29:38,070
ha tutti gli zeri e
quelli di mia funzione principale,

637
00:29:38,070 --> 00:29:40,830
e tutti gli zeri
e quelli per printf.

638
00:29:40,830 --> 00:29:44,900
>> E in effetti, che l'ultimo processo è
chiamato, collegando il vostro codice oggetto.

639
00:29:44,900 --> 00:29:47,490
L'uscita di cui
è un file eseguibile.

640
00:29:47,490 --> 00:29:49,780
Quindi, in tutta onestà, al
fine della giornata, niente

641
00:29:49,780 --> 00:29:52,660
è cambiato da una settimana, quando abbiamo
prima ha iniziato la compilazione di programmi.

642
00:29:52,660 --> 00:29:55,200
Infatti, tutto questo è stato
accade sotto il cofano,

643
00:29:55,200 --> 00:29:57,241
ma ora siamo in una posizione
dove possiamo realmente

644
00:29:57,241 --> 00:29:58,794
tease oltre questi vari passaggi.

645
00:29:58,794 --> 00:30:00,710
E infatti, alla fine
del giorno, siamo ancora

646
00:30:00,710 --> 00:30:04,480
sinistra con zero e uno, che
è in realtà un grande segue ora

647
00:30:04,480 --> 00:30:08,620
a un'altra capacità di C, che
non abbiamo dovuto sfruttare più probabile

648
00:30:08,620 --> 00:30:11,250
fino ad oggi, noto come operatori bit a bit.

649
00:30:11,250 --> 00:30:15,220
In altre parole, finora, in qualsiasi momento abbiamo
affrontato con i dati in C o variabili in C,

650
00:30:15,220 --> 00:30:17,660
abbiamo avuto le cose come
caratteri e carri allegorici e ins

651
00:30:17,660 --> 00:30:21,990
e anela e doppie e simili, ma
tutti questi sono almeno otto bit.

652
00:30:21,990 --> 00:30:25,550
Non abbiamo mai potuto ancora
manipolare i singoli bit,

653
00:30:25,550 --> 00:30:28,970
anche se un singolo bit, abbiamo
so, può rappresentare uno 0 e un 1.

654
00:30:28,970 --> 00:30:32,640
Ora si scopre che in C, è
possono ottenere l'accesso ai singoli bit,

655
00:30:32,640 --> 00:30:35,530
se si conosce la sintassi,
con cui arrivare a loro.

656
00:30:35,530 --> 00:30:38,010
>> Quindi, diamo uno sguardo
a operatori bit a bit.

657
00:30:38,010 --> 00:30:41,700
Quindi, nella foto qui sono alcuni simboli che
abbiamo, una sorta di, una sorta di, visto prima.

658
00:30:41,700 --> 00:30:45,580
Vedo una e commerciale, un verticale
bar, e alcuni altri, nonché,

659
00:30:45,580 --> 00:30:49,430
e ricordare che commerciale e commerciale
è qualcosa che abbiamo visto prima.

660
00:30:49,430 --> 00:30:54,060
L'operatore logico AND, dove si ha
due insieme, o l'OR logico

661
00:30:54,060 --> 00:30:56,300
operatore, dove si
avere due barre verticali.

662
00:30:56,300 --> 00:31:00,550
Operatori bit a bit, di cui parleremo
vedere operare su pezzi individualmente,

663
00:31:00,550 --> 00:31:03,810
basta usare un singolo commerciale, un
barra verticale singolo, il simbolo di inserimento

664
00:31:03,810 --> 00:31:06,620
viene dopo, il piccolo
tilde, e poi a sinistra

665
00:31:06,620 --> 00:31:08,990
staffa sinistra staffa o
Staffa destra parentesi destra.

666
00:31:08,990 --> 00:31:10,770
Ognuno di questi hanno significati diversi.

667
00:31:10,770 --> 00:31:11,950
>> In realtà, diamo uno sguardo.

668
00:31:11,950 --> 00:31:16,560
Andiamo oggi vecchia scuola, e l'uso
un touch screen da ieri,

669
00:31:16,560 --> 00:31:18,002
conosciuto come un bordo bianco.

670
00:31:18,002 --> 00:31:19,710
E questa scheda bianca
sta per permetterci

671
00:31:19,710 --> 00:31:27,360
per esprimere alcuni simboli abbastanza semplici,
o meglio alcune formule abbastanza semplici,

672
00:31:27,360 --> 00:31:29,560
che possiamo quindi in ultima analisi
leva, al fine

673
00:31:29,560 --> 00:31:33,230
per accedere ai singoli
bit all'interno di un programma C.

674
00:31:33,230 --> 00:31:34,480
In altre parole, cerchiamo di fare questo.

675
00:31:34,480 --> 00:31:37,080
Parliamo prima per un
momento su e commerciale,

676
00:31:37,080 --> 00:31:39,560
che è l'operatore AND bit a bit.

677
00:31:39,560 --> 00:31:42,130
In altre parole, si tratta
un operatore che permette

678
00:31:42,130 --> 00:31:45,930
me avere una variabile sinistra
tipicamente, e una variabile a destra,

679
00:31:45,930 --> 00:31:50,640
o un valore individuale, che se E
insieme, mi dà un risultato finale.

680
00:31:50,640 --> 00:31:51,560
Così che cosa voglio dire?

681
00:31:51,560 --> 00:31:54,840
Se in un programma, si dispone di una variabile
che memorizza uno di questi valori,

682
00:31:54,840 --> 00:31:58,000
o teniamolo semplice, e basta
scrivere zero e uno individuale,

683
00:31:58,000 --> 00:32:00,940
Ecco come funziona l'operatore commerciale.

684
00:32:00,940 --> 00:32:06,400
0 0 e commerciale sta per uguale a 0.

685
00:32:06,400 --> 00:32:07,210
Ora perché?

686
00:32:07,210 --> 00:32:09,291
>> E 'molto simile a
Espressioni booleane,

687
00:32:09,291 --> 00:32:10,540
che abbiamo discusso finora.

688
00:32:10,540 --> 00:32:15,800
Se si pensa che, dopo tutto, la 0 è
falso, 0 è falso, falso e falso

689
00:32:15,800 --> 00:32:18,720
è, come abbiamo discusso
logicamente, anche falso.

690
00:32:18,720 --> 00:32:20,270
Così otteniamo 0 anche qui.

691
00:32:20,270 --> 00:32:24,390
Se si prende 0 e commerciale
1, bene che, anche,

692
00:32:24,390 --> 00:32:29,890
sta per essere 0, perché per questo
espressione di sinistra sia vero o 1,

693
00:32:29,890 --> 00:32:32,360
che avrebbe bisogno di essere vero e vero.

694
00:32:32,360 --> 00:32:36,320
Ma qui abbiamo falso
e vero, o 0 e 1.

695
00:32:36,320 --> 00:32:42,000
Ora di nuovo, se abbiamo 1 e commerciale
0, che, anche, sta per essere 0,

696
00:32:42,000 --> 00:32:47,240
e se abbiamo 1 e commerciale 1,
finalmente abbiamo un 1 bit.

697
00:32:47,240 --> 00:32:50,340
Quindi, in altre parole, non stiamo facendo
qualcosa di interessante con questo operatore

698
00:32:50,340 --> 00:32:51,850
appena ancora, questo operatore commerciale.

699
00:32:51,850 --> 00:32:53,780
E 'l'operatore AND bit a bit.

700
00:32:53,780 --> 00:32:57,290
Ma questi sono gli ingredienti
attraverso il quale si può fare

701
00:32:57,290 --> 00:32:59,240
cose interessanti, come vedremo presto.

702
00:32:59,240 --> 00:33:02,790
>> Ora diamo un'occhiata a solo il singolo
barra verticale sopra qui a destra.

703
00:33:02,790 --> 00:33:06,710
Se ho un po 'e io 0
O con il bit per bit

704
00:33:06,710 --> 00:33:11,030
OR operatore, un altro po '0,
che sta per darmi 0.

705
00:33:11,030 --> 00:33:17,540
Se prendo un po '0 e OR con
un 1 po ', poi ho intenzione di ottenere 1.

706
00:33:17,540 --> 00:33:19,830
Ed infatti, solo per
chiarezza, lasciami andare indietro,

707
00:33:19,830 --> 00:33:23,380
in modo che le mie barre verticali
non vengono scambiati per 1 di.

708
00:33:23,380 --> 00:33:26,560
Permettetemi di riscrivere tutti
il mio 1 è un po 'di più

709
00:33:26,560 --> 00:33:32,700
chiaramente, così che noi vediamo il prossimo, se io
hanno un 1 o 0, che sta per essere un 1,

710
00:33:32,700 --> 00:33:39,060
e se ho un 1 o 1 che,
Anche, sta per essere un 1.

711
00:33:39,060 --> 00:33:42,900
Così si può vedere logicamente che l'OR
operatore si comporta in modo molto diverso.

712
00:33:42,900 --> 00:33:48,070
Questo mi dà 0 O 0 0 mi dà, ma
ogni altra combinazione mi dà 1.

713
00:33:48,070 --> 00:33:52,480
Finché ho un 1 nel
formula, il risultato sarà 1.

714
00:33:52,480 --> 00:33:55,580
>> In contrasto con AND
operatore, la e commerciale,

715
00:33:55,580 --> 00:34:00,940
solo se ho due 1 nella
equazione, posso effettivamente ottenere un 1 fuori.

716
00:34:00,940 --> 00:34:02,850
Ora c'è un pochi altri
operatori.

717
00:34:02,850 --> 00:34:04,810
Uno di loro è un po 'più complicato.

718
00:34:04,810 --> 00:34:07,980
Quindi lasciami andare avanti e cancelli
questo per liberare un po 'di spazio.

719
00:34:07,980 --> 00:34:13,020

720
00:34:13,020 --> 00:34:16,460
E diamo uno sguardo al
simbolo di inserimento, solo per un momento.

721
00:34:16,460 --> 00:34:18,210
Questo è tipicamente un
carattere è possibile digitare

722
00:34:18,210 --> 00:34:21,420
sulla Maiusc detenzione tastiera e
allora uno dei numeri in cima vostro Uniti

723
00:34:21,420 --> 00:34:22,250
tastiera.

724
00:34:22,250 --> 00:34:26,190
>> Quindi questo è l'esclusiva
Operatore OR, OR esclusivo.

725
00:34:26,190 --> 00:34:27,790
Così abbiamo appena visto l'operatore OR.

726
00:34:27,790 --> 00:34:29,348
Questo è l'esclusivo operatore OR.

727
00:34:29,348 --> 00:34:30,639
Qual è realmente la differenza?

728
00:34:30,639 --> 00:34:34,570
Beh diciamo basta guardare la formula,
e usare questo come ingredienti in definitiva.

729
00:34:34,570 --> 00:34:37,690
0 XOR 0.

730
00:34:37,690 --> 00:34:39,650
Io vado a dire è sempre 0.

731
00:34:39,650 --> 00:34:41,400
Questa è la definizione di XOR.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 sarà 1.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 sta per essere 1,
e 1 XOR 1 sta per essere?

734
00:34:58,810 --> 00:34:59,890
Sbagliato?

735
00:34:59,890 --> 00:35:00,520
O destra?

736
00:35:00,520 --> 00:35:01,860
Non lo so.

737
00:35:01,860 --> 00:35:02,810
0.

738
00:35:02,810 --> 00:35:04,700
Ora che cosa sta succedendo qui?

739
00:35:04,700 --> 00:35:06,630
Beh, pensare al
il nome di questo operatore.

740
00:35:06,630 --> 00:35:09,980
OR esclusivo, così come la
nome, tipo di, suggerisce,

741
00:35:09,980 --> 00:35:13,940
la risposta è solo andare a essere
un 1 se gli ingressi sono esclusivi,

742
00:35:13,940 --> 00:35:15,560
esclusivamente diverso.

743
00:35:15,560 --> 00:35:18,170
Così qui gli ingressi sono il
stesso, quindi l'uscita è 0.

744
00:35:18,170 --> 00:35:20,700
Qui gli ingressi sono il
stesso, quindi l'uscita è 0.

745
00:35:20,700 --> 00:35:25,640
Qui ci sono le uscite sono diverse,
sono esclusivi, e quindi l'uscita è 1.

746
00:35:25,640 --> 00:35:28,190
Quindi è molto simile a
E, è molto simile,

747
00:35:28,190 --> 00:35:32,760
o meglio, è molto simile a
O, ma solo in modo esclusivo.

748
00:35:32,760 --> 00:35:36,210
Questo non è un 1,
perché abbiamo due di 1,

749
00:35:36,210 --> 00:35:38,621
e non esclusivamente, solo uno di loro.

750
00:35:38,621 --> 00:35:39,120
Tutto ok.

751
00:35:39,120 --> 00:35:40,080
E gli altri?

752
00:35:40,080 --> 00:35:44,220
Beh, la tilde, nel frattempo, è
davvero bello e semplice, per fortuna.

753
00:35:44,220 --> 00:35:46,410
E questo è un unario
operatore, il che significa

754
00:35:46,410 --> 00:35:50,400
è applicato ad un solo ingresso,
un operando, per così dire.

755
00:35:50,400 --> 00:35:51,800
Non a sinistra e destra.

756
00:35:51,800 --> 00:35:56,050
In altre parole, se si prende di tilde
0, la risposta sarà l'opposto.

757
00:35:56,050 --> 00:35:59,710
E se si prende tilde di 1, il
risposta ci sarà l'opposto.

758
00:35:59,710 --> 00:36:02,570
Così l'operatore tilde è
un modo di negare un po ',

759
00:36:02,570 --> 00:36:06,000
o capovolgere un po 'da
0 a 1, o da 1 a 0.

760
00:36:06,000 --> 00:36:09,820
>> E che ci lascia finalmente
con solo due operatori finali,

761
00:36:09,820 --> 00:36:13,840
il cosiddetto spostamento a sinistra, e la
cosiddetto operatore di spostamento a destra.

762
00:36:13,840 --> 00:36:16,620
Diamo un'occhiata a come quelli di lavoro.

763
00:36:16,620 --> 00:36:20,780
L'operatore spostamento a sinistra, scritta
con due parentesi angolari del genere,

764
00:36:20,780 --> 00:36:22,110
il seguente.

765
00:36:22,110 --> 00:36:27,390
Se il mio ingresso, o il mio operando, a sinistra
operatore di spostamento è semplicemente un 1.

766
00:36:27,390 --> 00:36:33,750
E io allora dico il computer per
spostamento a sinistra che 1, dico sette posti,

767
00:36:33,750 --> 00:36:37,150
il risultato è come se io
prendere quel 1, e spostarla

768
00:36:37,150 --> 00:36:40,160
sette piazzole su al
sinistra, e per impostazione predefinita,

769
00:36:40,160 --> 00:36:42,270
stiamo andando a supporre che
lo spazio a destra

770
00:36:42,270 --> 00:36:44,080
sta per essere riempito con gli zeri.

771
00:36:44,080 --> 00:36:50,316
In altre parole, uno spostamento a sinistra 7 sta andando
per darmi quel 1, seguito da 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 zeri.

773
00:36:54,060 --> 00:36:57,380
Quindi, in un certo senso, ti permette di
prendere un numero piccolo come 1,

774
00:36:57,380 --> 00:37:00,740
e chiaramente fare molto
molto, molto più grande in questo modo,

775
00:37:00,740 --> 00:37:06,460
ma realmente stiamo andando a vedere
approcci più intelligenti per lo

776
00:37:06,460 --> 00:37:08,080
invece, pure,

777
00:37:08,080 --> 00:37:08,720
>> Tutto ok.

778
00:37:08,720 --> 00:37:10,060
Questo è tutto per tre settimane.

779
00:37:10,060 --> 00:37:11,400
Ci vediamo la prossima volta.

780
00:37:11,400 --> 00:37:12,770
Questo è stato CS50.

781
00:37:12,770 --> 00:37:17,270

782
00:37:17,270 --> 00:37:22,243
>> [RIPRODUZIONE DI BRANI MUSICALI]

783
00:37:22,243 --> 00:37:25,766
>> SPEAKER 1: E 'stato presso lo snack
bar a mangiare un hot fudge sundae.

784
00:37:25,766 --> 00:37:28,090
Ha avuto tutto il suo viso.

785
00:37:28,090 --> 00:37:30,506
Indossa che il cioccolato come una barba

786
00:37:30,506 --> 00:37:31,756
SPEAKER 2: Che cosa stai facendo?

787
00:37:31,756 --> 00:37:32,422
SPEAKER 3: Hmmm?

788
00:37:32,422 --> 00:37:33,500
Che cosa?

789
00:37:33,500 --> 00:37:36,800
>> SPEAKER 2: hai appena double dip?

790
00:37:36,800 --> 00:37:38,585
È doppio immersi chip.

791
00:37:38,585 --> 00:37:39,460
SPEAKER 3: Mi scusi.

792
00:37:39,460 --> 00:37:44,440
SPEAKER 2: immersi il chip, è
ha preso un morso, e hai immerso di nuovo.

793
00:37:44,440 --> 00:37:44,940
SPEAKER 3:

794
00:37:44,940 --> 00:37:48,440
SPEAKER 2: Ecco come mettere
destra bocca tutto in tuffo.

795
00:37:48,440 --> 00:37:52,400
La prossima volta che si prende un chip,
basta immergerlo una volta, e alla fine di esso.

796
00:37:52,400 --> 00:37:53,890
>> SPEAKER 3: Sai una cosa, Dan?

797
00:37:53,890 --> 00:37:58,006
Immergete il modo in cui si desidera immergersi.

798
00:37:58,006 --> 00:38:01,900
Mi tuffo il modo in cui voglio immergere.

799
00:38:01,900 --> 00:38:03,194