1
00:00:00,000 --> 00:00:00,488

2
00:00:00,488 --> 00:00:10,800
>> [Musik spielt]

3
00:00:10,800 --> 00:00:13,500
DAVID MALAN: Alles klar.

4
00:00:13,500 --> 00:00:14,670
Alles klar, willkommen zurück.

5
00:00:14,670 --> 00:00:18,120
Also das ist Woche 4, der Anfang
davon bereits.

6
00:00:18,120 --> 00:00:21,320
Und Sie werden sich erinnern, dass letzte Woche, haben wir
codieren beiseite für nur ein wenig

7
00:00:21,320 --> 00:00:24,240
und wir kamen ins Gespräch ein wenig mehr
High-Level, über Dinge wie

8
00:00:24,240 --> 00:00:28,130
Such-und Sortierfunktionen, die zwar
etwas einfachen Ideen sind

9
00:00:28,130 --> 00:00:31,840
Vertreter einer Klasse von Problemen
Sie werden beginnen, besonders lösen

10
00:00:31,840 --> 00:00:34,820
wie Sie anfangen, darüber nachzudenken Finale
Projekte und interessante Lösungen, die Sie

11
00:00:34,820 --> 00:00:36,760
könnte zu Problemen der realen Welt haben.

12
00:00:36,760 --> 00:00:39,490
Jetzt bubble sort war eine der einfachsten
solche Algorithmen, und es

13
00:00:39,490 --> 00:00:42,900
arbeitete, indem er diese kleinen Zahlen
in einer Liste oder eines Arrays Art

14
00:00:42,900 --> 00:00:46,530
Blase ihren Weg bis an die Spitze, und die
große Zahlen bewegen ihren Weg nach unten, um

15
00:00:46,530 --> 00:00:47,930
das Ende dieser Liste.

16
00:00:47,930 --> 00:00:50,650
>> Und daran erinnern, dass wir visualisieren
Bubble-Sort ein wenig

17
00:00:50,650 --> 00:00:52,310
etwas wie dieses.

18
00:00:52,310 --> 00:00:53,640
Also lassen Sie mich gehen Sie vor und klicken Sie auf Start.

19
00:00:53,640 --> 00:00:55,350
Ich habe bubble sort vorausgewählt.

20
00:00:55,350 --> 00:00:58,920
Und wenn Sie sich erinnern, dass der größere blau
Linien stellen große Zahlen, kleine

21
00:00:58,920 --> 00:01:03,300
blauen Linien stellen kleine Zahlen, wie
wir gehen durch diese wieder und wieder und

22
00:01:03,300 --> 00:01:07,680
wieder, den Vergleich von zwei Stangen nebeneinander
andere in rot, wir gehen an den Swap-

23
00:01:07,680 --> 00:01:11,010
größte und die kleinste, wenn
sie sind nicht in Ordnung.

24
00:01:11,010 --> 00:01:14,150
>> So wird dies gehen und gehen und gehen
auf, und du wirst sehen, dass die größere

25
00:01:14,150 --> 00:01:16,700
Elemente sind, die ihren Weg auf die
rechts, und die kleineren Elemente

26
00:01:16,700 --> 00:01:17,900
die ihren Weg auf der linken Seite.

27
00:01:17,900 --> 00:01:21,380
Aber wir begannen zu quantifizieren
die Effizienz, die

28
00:01:21,380 --> 00:01:22,970
Qualität dieses Algorithmus.

29
00:01:22,970 --> 00:01:25,200
Und wir sagten, dass im schlimmsten
Fall hat dieser Algorithmus

30
00:01:25,200 --> 00:01:27,940
etwa, wie viele Schritte?

31
00:01:27,940 --> 00:01:28,980
>> So n Quadrat.

32
00:01:28,980 --> 00:01:30,402
Und was war n?

33
00:01:30,402 --> 00:01:31,650
>> ZUSCHAUER: Anzahl der Elemente.

34
00:01:31,650 --> 00:01:32,790
>> DAVID MALAN: So war das n
Anzahl der Elemente.

35
00:01:32,790 --> 00:01:33,730
Und so werden wir dies oft zu tun.

36
00:01:33,730 --> 00:01:36,650
Jedes Mal, wenn wir wollen, um die Größe zu sprechen
einer Störung oder der Größe eines

37
00:01:36,650 --> 00:01:39,140
oder dass der Betrag der Zeit, die
zur Ausgabe produzieren, werden wir nur

38
00:01:39,140 --> 00:01:41,610
generalisierte whatever
Der Eingang ist als n.

39
00:01:41,610 --> 00:01:45,970
Also zurück in Woche 0, Seiten die Zahl
im Telefonbuch war n.

40
00:01:45,970 --> 00:01:47,550
Die Zahl der Studierenden
im Zimmer war n.

41
00:01:47,550 --> 00:01:49,630
So auch hier, wir sind nach
dass Muster.

42
00:01:49,630 --> 00:01:52,800
>> Jetzt n squared ist nicht besonders
schnell, also versuchten wir es besser zu machen.

43
00:01:52,800 --> 00:01:55,970
Und so sahen wir uns an ein paar
andere Algorithmen, unter denen

44
00:01:55,970 --> 00:01:57,690
Auswahl Art waren.

45
00:01:57,690 --> 00:01:59,180
So Auswahl Art war
ein wenig anders.

46
00:01:59,180 --> 00:02:03,130
Es war fast einfacher, ich wage zu sagen,
wobei ich begann zu Beginn des

47
00:02:03,130 --> 00:02:06,740
Liste unserer Freiwilligen und ich wieder
und wieder und wieder ging durch

48
00:02:06,740 --> 00:02:10,060
die Liste, Herausreißen der kleinste
Element zu einem Zeitpunkt und setzen ihn oder

49
00:02:10,060 --> 00:02:13,040
sie am Anfang der Liste.

50
00:02:13,040 --> 00:02:16,410
>> Aber auch dies, wenn wir begonnen zu denken,
durch die Mathematik und größer

51
00:02:16,410 --> 00:02:19,860
Bild, dachte darüber nach, wie oft
Ich war hin und her und wieder zurück

52
00:02:19,860 --> 00:02:24,090
und her, wobei wir im schlimmsten Fall,
Auswahl Art war auch was?

53
00:02:24,090 --> 00:02:24,960
n straffte.

54
00:02:24,960 --> 00:02:27,490
Jetzt in der realen Welt, könnte es
tatsächlich geringfügig schneller.

55
00:02:27,490 --> 00:02:30,620
Weil wieder, habe ich nicht zu halten
Backtracking ich einmal sortiert hatte die

56
00:02:30,620 --> 00:02:31,880
kleinsten Elemente.

57
00:02:31,880 --> 00:02:35,090
Aber wenn wir darüber nachdenken, sehr große n, und
wenn Sie irgendwie tun sich die Mathematik als

58
00:02:35,090 --> 00:02:39,170
Ich habe auf dem Brett, mit dem n squared
minus etwas, alles andere

59
00:02:39,170 --> 00:02:41,850
neben dem n Quadrat, einmal n
wird wirklich groß, nicht

60
00:02:41,850 --> 00:02:42,850
wirklich so viel aus.

61
00:02:42,850 --> 00:02:45,470
So wie Informatiker, wir sortieren
ein Auge zudrücken, um den kleineren

62
00:02:45,470 --> 00:02:49,220
Faktoren und Fokus nur auf den Faktor in
ein Ausdruck, der gehen, dass ist

63
00:02:49,220 --> 00:02:50,330
der größte Unterschied.

64
00:02:50,330 --> 00:02:52,840
>> Nun, schließlich haben wir uns
bei insertion sort.

65
00:02:52,840 --> 00:02:56,620
Und das war im Geiste, aber
anstatt zu gehen durch iterativ und

66
00:02:56,620 --> 00:03:01,250
Wählen Sie das kleinste Element ein zu einer
Zeit, ich stattdessen nahm die Hand, dass ich

67
00:03:01,250 --> 00:03:04,070
behandelt wurde, und ich beschloss, alle
Recht, du gehörst hier.

68
00:03:04,070 --> 00:03:06,160
Dann zog ich auf das nächste Element
und beschlossen, dass er oder

69
00:03:06,160 --> 00:03:07,470
sie gehörte hier.

70
00:03:07,470 --> 00:03:08,810
Und dann zog ich weiter und weiter.

71
00:03:08,810 --> 00:03:11,780
Und ich könnte an, auf dem Weg,
verschieben diese Jungs um

72
00:03:11,780 --> 00:03:13,030
Platz machen für sie.

73
00:03:13,030 --> 00:03:16,880
Das war also eine Art der geistigen Umkehr
von Selection Sort, dass wir

74
00:03:16,880 --> 00:03:18,630
genannt insertion sort.

75
00:03:18,630 --> 00:03:20,810
>> Also diese Themen auftreten
in der realen Welt.

76
00:03:20,810 --> 00:03:23,640
Gerade vor ein paar Jahren, wenn eine bestimmte
Senator zum Präsidenten läuft,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, die zum Zeitpunkt der CEO von
Google, tatsächlich die Möglichkeit hatte

78
00:03:27,160 --> 00:03:28,040
um ihn zu interviewen.

79
00:03:28,040 --> 00:03:32,010
Und wir dachten, wir würden dieses YouTube teilen
Clip für Sie hier, wenn wir drehen konnte

80
00:03:32,010 --> 00:03:32,950
das Volumen.

81
00:03:32,950 --> 00:03:39,360
>> [VIDEO PLAYBACK]

82
00:03:39,360 --> 00:03:44,620
>> -Nun, Senator, sind Sie hier bei Google,
und Ich mag an der Präsidentschaft denken

83
00:03:44,620 --> 00:03:46,042
wie ein Vorstellungsgespräch.

84
00:03:46,042 --> 00:03:47,770
>> [Gelächter]

85
00:03:47,770 --> 00:03:50,800
>> -Jetzt ist es schwer zu bekommen
ein Job als Präsident.

86
00:03:50,800 --> 00:03:52,480
Und du durchmachst
die Strapazen jetzt.

87
00:03:52,480 --> 00:03:54,330
Es ist auch schwer, einen Job bei Google zu bekommen.

88
00:03:54,330 --> 00:03:59,610
Wir haben Fragen und wir bitten
unsere Kandidaten Fragen.

89
00:03:59,610 --> 00:04:02,250
Und dieser ist von Larry Schwimmer.

90
00:04:02,250 --> 00:04:05,325
>> [Gelächter]

91
00:04:05,325 --> 00:04:06,400
-Ihr Jungs denken, ich bin verrückt?

92
00:04:06,400 --> 00:04:08,750
Es ist hier genau richtig.

93
00:04:08,750 --> 00:04:12,110
Was ist der effizienteste Weg, um
sortieren eine Million zwei-Bit-Integer?

94
00:04:12,110 --> 00:04:15,810
>> [Gelächter]

95
00:04:15,810 --> 00:04:18,260
>> -Nun, äh -

96
00:04:18,260 --> 00:04:19,029
>> -Tut mir leid.

97
00:04:19,029 --> 00:04:19,745
Vielleicht sollten wir -

98
00:04:19,745 --> 00:04:21,000
>> -Nein, nein, nein, nein, nein.

99
00:04:21,000 --> 00:04:21,470
>> -Das ist nicht ein -

100
00:04:21,470 --> 00:04:22,185
OK.

101
00:04:22,185 --> 00:04:25,328
>> -Ich denke, die Art Blase würde
sein der falsche Weg zu gehen.

102
00:04:25,328 --> 00:04:26,792
>> [Gelächter]

103
00:04:26,792 --> 00:04:28,510
>> [Jubel und Applaus]

104
00:04:28,510 --> 00:04:31,211
>> -Komm, der ihm sagte, dieses?

105
00:04:31,211 --> 00:04:32,155
OK.

106
00:04:32,155 --> 00:04:33,350
>> [END VIDEO PLAYBACK]

107
00:04:33,350 --> 00:04:35,070
>> DAVID MALAN: So dort haben Sie es.

108
00:04:35,070 --> 00:04:39,600
Also fingen wir an, diese läuft quantifizieren
Zeiten, sozusagen, mit etwas

109
00:04:39,600 --> 00:04:43,480
genannt asymptotischen Notation, die ist
nur mit Bezug auf unsere Art des Drehens

110
00:04:43,480 --> 00:04:47,420
ein Auge zudrücken, um diese kleineren Faktoren und
nur Blick auf die Laufzeit,

111
00:04:47,420 --> 00:04:51,250
die Leistung der Algorithmen,
als n wird wirklich groß über die Zeit.

112
00:04:51,250 --> 00:04:55,110
Und so stellten wir große O. und Big O
vertreten etwas, dass wir dachten,

113
00:04:55,110 --> 00:04:57,000
der als Obergrenze.

114
00:04:57,000 --> 00:04:59,570
Und tatsächlich, Barry, können wir senken
als das Mikrofon ein wenig?

115
00:04:59,570 --> 00:05:01,040
>> Wir dachten, dies ist eine obere Schranke.

116
00:05:01,040 --> 00:05:04,710
So groß O von n Quadrat bedeutet, dass in
schlimmsten Fall etwas

117
00:05:04,710 --> 00:05:07,780
Auswahl sortieren würde
n squared Schritte.

118
00:05:07,780 --> 00:05:10,310
Oder so etwas wie Insertion Sort
würde n squared Schritte.

119
00:05:10,310 --> 00:05:15,150
Nun zu etwas wie Insertion
Art, was war der schlimmste Fall?

120
00:05:15,150 --> 00:05:18,200
Da ein Array ist, ist, was das Schlimmste
mögliches Szenario, dass Sie vielleicht finden

121
00:05:18,200 --> 00:05:20,650
sich konfrontiert mit?

122
00:05:20,650 --> 00:05:21,860
>> Es ist völlig nach hinten, nicht wahr?

123
00:05:21,860 --> 00:05:24,530
Denn wenn es ganz nach hinten,
Sie haben eine ganze Menge Arbeit zu tun.

124
00:05:24,530 --> 00:05:26,420
Denn wenn du ganz nach hinten,
Sie gehen, um die zu finden

125
00:05:26,420 --> 00:05:28,840
größte Element ist hier, obwohl
es gehört dort unten.

126
00:05:28,840 --> 00:05:31,140
So wirst du sagen, alles in Ordnung, bei
dieser Moment in der Zeit, du gehörst hier

127
00:05:31,140 --> 00:05:32,310
so dass Sie in Ruhe lassen.

128
00:05:32,310 --> 00:05:35,425
>> Dann merkt man, oh, verdammt, ich muss
verschieben Sie diese etwas kleinere Element

129
00:05:35,425 --> 00:05:36,470
links von Ihnen.

130
00:05:36,470 --> 00:05:38,770
Dann muss ich das wieder tun
und immer wieder.

131
00:05:38,770 --> 00:05:41,410
Und wenn ich hin und her ging, Sie
würde irgendwie das Gefühl, die Leistung der

132
00:05:41,410 --> 00:05:45,540
dass Algorithmus, weil ständig bin ich
schlurfenden alle anderen in der

133
00:05:45,540 --> 00:05:46,510
Array, um Platz für sie zu machen.

134
00:05:46,510 --> 00:05:47,750
Also das ist der schlimmste Fall.

135
00:05:47,750 --> 00:05:48,570
>> Im Gegensatz dazu -

136
00:05:48,570 --> 00:05:50,320
und dies war ein Cliffhanger letzten Mal -

137
00:05:50,320 --> 00:05:54,065
wir sagten, dass insertion sort
war ein Omega von was?

138
00:05:54,065 --> 00:05:57,530
Was ist das Best-Case-Lauf
Zeitpunkt der Einführung Art?

139
00:05:57,530 --> 00:05:58,520
Also es ist eigentlich n.

140
00:05:58,520 --> 00:06:00,980
Das war der Rohling, dass wir links
auf dem Brett letzten Zeit.

141
00:06:00,980 --> 00:06:03,160
>> Und es ist der Omega n denn warum?

142
00:06:03,160 --> 00:06:06,630
Nun, in den besten Fall, was ist
Insertion Sort gehen zu übergeben?

143
00:06:06,630 --> 00:06:09,830
Nun, eine Liste, die vollständig geordnet ist
Bereits minimale Arbeit zu tun.

144
00:06:09,830 --> 00:06:12,460
Aber was ist ordentlich über Insertion Sort
ist, weil es hier startet und

145
00:06:12,460 --> 00:06:15,340
entscheidet, oh, du bist die Nummer
ein, du gehörst hier.

146
00:06:15,340 --> 00:06:16,970
Oh, was für ein Glück.

147
00:06:16,970 --> 00:06:17,740
>> Du bist die Nummer zwei.

148
00:06:17,740 --> 00:06:19,030
Sie gehören hierher.

149
00:06:19,030 --> 00:06:21,010
Nummer drei, noch besser,
Sie gehören hierher.

150
00:06:21,010 --> 00:06:25,210
Sobald es an das Ende der
Liste pro Insertion Sort ist Pseudocode

151
00:06:25,210 --> 00:06:28,010
dass wir durch verbal
letzten Mal, hat es getan.

152
00:06:28,010 --> 00:06:32,790
Aber Auswahl Art dagegen
gehalten zu tun, was?

153
00:06:32,790 --> 00:06:35,260
>> In Gang gehalten durch die Liste
wieder und wieder und wieder.

154
00:06:35,260 --> 00:06:39,160
Da der Schlüssel Einblick gab es nur
sobald Sie sah den ganzen Weg bis die

155
00:06:39,160 --> 00:06:42,500
Ende der Liste können Sie sicher sein,
dass das Element, das Sie ausgewählt war

156
00:06:42,500 --> 00:06:45,560
Tat das derzeit kleinste Element.

157
00:06:45,560 --> 00:06:48,920
Also diese unterschiedlichen mentalen Modelle Ende
up was einige sehr realen Welt

158
00:06:48,920 --> 00:06:53,130
Unterschiede für uns, sowie diese
theoretischen asymptotischen Unterschiede.

159
00:06:53,130 --> 00:06:56,910
>> Also nur zur Erinnerung, dann big O von n
Quadrat, haben wir ein paar solcher gesehen

160
00:06:56,910 --> 00:06:58,350
Algorithmen so weit.

161
00:06:58,350 --> 00:06:59,580
Big O von n?

162
00:06:59,580 --> 00:07:02,870
Was ist ein Algorithmus, der konnte
gesagt werden, um große O von n sein?

163
00:07:02,870 --> 00:07:06,930
Im schlimmsten Fall kommt es
eine lineare Reihe von Schritten.

164
00:07:06,930 --> 00:07:07,810
>> OK, lineare Suche.

165
00:07:07,810 --> 00:07:10,470
Und im schlimmsten Fall, wo ist die
Element Sie bei der Suche

166
00:07:10,470 --> 00:07:12,950
Anwenden einer linearen Suche?

167
00:07:12,950 --> 00:07:14,680
>> OK, im schlimmsten Fall,
es ist gar nicht da.

168
00:07:14,680 --> 00:07:17,000
Oder in der zweiten schlimmsten Fall ist es
ganz am Ende, das ist

169
00:07:17,000 --> 00:07:18,880
plus oder minus ein einstufiges Unterschied.

170
00:07:18,880 --> 00:07:21,180
So dass am Ende des Tages,
können wir sagen, es ist linear.

171
00:07:21,180 --> 00:07:23,910
Big O von n würde lineare Suche zu sein,
denn im schlimmsten Fall die

172
00:07:23,910 --> 00:07:26,610
Element ist gar nicht da, oder es ist
ganz am Ende.

173
00:07:26,610 --> 00:07:29,370
>> Nun, groß O von log n.

174
00:07:29,370 --> 00:07:32,760
Wir haben nicht im Detail reden
, aber wir haben dies gesehen.

175
00:07:32,760 --> 00:07:36,840
Was läuft im sogenannten logarithmischen
Zeit, im schlimmsten Fall?

176
00:07:36,840 --> 00:07:38,500
>> Ja, so binäre Suche.

177
00:07:38,500 --> 00:07:42,930
Und binäre Suche im schlimmsten Fall
vielleicht das Element irgendwo in haben

178
00:07:42,930 --> 00:07:45,640
der Mitte oder irgendwo
innerhalb des Arrays.

179
00:07:45,640 --> 00:07:48,040
Aber Sie finden es nur, wenn Sie
teilen Sie die Liste in der Hälfte, in

180
00:07:48,040 --> 00:07:48,940
Hälfte, in der Mitte, in zwei Hälften.

181
00:07:48,940 --> 00:07:50,200
Und dann voila, es ist da.

182
00:07:50,200 --> 00:07:52,500
Oder auch, worst case,
es ist gar nicht da.

183
00:07:52,500 --> 00:07:56,770
Aber Sie wissen nicht, dass es nicht da ist
bis Sie irgendwie erreichen, dass im vergangenen

184
00:07:56,770 --> 00:08:00,470
untersten Elemente durch Halbierung
und halbieren und halbieren.

185
00:08:00,470 --> 00:08:01,400
>> Big O von 1.

186
00:08:01,400 --> 00:08:03,540
So konnten wir große O 2, O 3 groß.

187
00:08:03,540 --> 00:08:06,260
Immer, wenn Sie wollen einfach nur eine konstante Anzahl,
wir einfach nur vereinfachen sortieren

188
00:08:06,260 --> 00:08:07,280
so groß, dass O von 1.

189
00:08:07,280 --> 00:08:10,440
Obwohl, wenn realistisch, dauert es
2 oder sogar 100 Schritte, wenn es eine

190
00:08:10,440 --> 00:08:13,680
konstante Anzahl von Schritten,
wir nur sagen big O von 1.

191
00:08:13,680 --> 00:08:15,930
Was ist ein Algorithmus, der ist
in großen O von 1?

192
00:08:15,930 --> 00:08:18,350
>> ZUSCHAUER: Finden Sie die Länge
einer Variablen.

193
00:08:18,350 --> 00:08:21,090
>> DAVID MALAN: Suche nach dem
Länge einer Variable?

194
00:08:21,090 --> 00:08:23,870
>> ZUSCHAUER: Nein, die Länge
wenn es bereits sortiert.

195
00:08:23,870 --> 00:08:24,160
>> DAVID MALAN: Good.

196
00:08:24,160 --> 00:08:27,850
OK, so finden die Länge von etwas
wenn die Länge dieser etwas, wie

197
00:08:27,850 --> 00:08:30,020
ein Array ist, wird in einer Variablen gespeichert.

198
00:08:30,020 --> 00:08:33,380
Da kann man gerade gelesen das variable,
oder drucken Sie die Variable oder

199
00:08:33,380 --> 00:08:34,960
nur allgemein diese Variable zugreifen.

200
00:08:34,960 --> 00:08:37,299
Und voila, die konstante Zeit in Anspruch nimmt.

201
00:08:37,299 --> 00:08:38,909
>> Im Gegensatz dazu, denken Sie zurück zu kratzen.

202
00:08:38,909 --> 00:08:42,460
Denken Sie zurück an die erste Woche des C,
Aufruf nur printf und Drucken

203
00:08:42,460 --> 00:08:46,240
etwas auf dem Bildschirm ist wohl
konstante Zeit, denn es dauert nur

204
00:08:46,240 --> 00:08:50,880
einige der CPU-Zyklen zu zeigen
dass der Text auf dem Bildschirm.

205
00:08:50,880 --> 00:08:52,720
Oder warten - geht das?

206
00:08:52,720 --> 00:08:56,430
Wie sonst könnten wir modellieren die
Leistung von printf?

207
00:08:56,430 --> 00:09:00,420
Würde jemand gerne einverstanden, dass
vielleicht ist es nicht wirklich konstante Zeit?

208
00:09:00,420 --> 00:09:03,600
In welchem ​​Sinne könnte printf läuft
Zeit, etwas tatsächlich ausdrucken String auf

209
00:09:03,600 --> 00:09:05,580
der Bildschirm, etwas zu sein
andere als konstant.

210
00:09:05,580 --> 00:09:07,860
>> ZUSCHAUER: [unverständlich].

211
00:09:07,860 --> 00:09:08,230
>> DAVID MALAN: Yeah.

212
00:09:08,230 --> 00:09:09,300
Es hängt also von unserer Perspektive.

213
00:09:09,300 --> 00:09:13,390
Wenn wir tatsächlich denken, der Eingang zum
printf als die Saite, und

214
00:09:13,390 --> 00:09:16,380
Daher messen wir die Größe, dass
Eingang durch seine Länge - so nennen wir

215
00:09:16,380 --> 00:09:17,780
dass Länge n sowie -

216
00:09:17,780 --> 00:09:21,990
wohl, printf ist selbst groß O von n
denn es geht um Sie n Schritte

217
00:09:21,990 --> 00:09:24,750
ausdrucken jedem dieser n
Zeichen, wahrscheinlich.

218
00:09:24,750 --> 00:09:27,730
Wenigstens soweit wir annehmen,
dass vielleicht ist es mit einer for-Schleife

219
00:09:27,730 --> 00:09:28,560
unter der Haube.

220
00:09:28,560 --> 00:09:30,860
>> Aber wir müssten sich das an
Code, um sie besser verstehen.

221
00:09:30,860 --> 00:09:33,650
Und in der Tat, wenn man Jungs starten
Analyse der eigenen Algorithmen, werden Sie

222
00:09:33,650 --> 00:09:34,900
buchstäblich genau das zu tun.

223
00:09:34,900 --> 00:09:37,765
Sortieren der Augapfel Ihren Code und denken
über - alles in Ordnung, habe ich diese Schleife

224
00:09:37,765 --> 00:09:41,870
hier oder ich habe eine verschachtelte Schleifen hier
das wird n mal n Dinge zu tun,

225
00:09:41,870 --> 00:09:46,050
und Sie können von Grund sortieren Sie Ihren Weg
durch den Code, auch wenn es

226
00:09:46,050 --> 00:09:47,980
Pseudocode und nicht eigentliche Code.

227
00:09:47,980 --> 00:09:49,730
>> Und was ist mit der omega n squared?

228
00:09:49,730 --> 00:09:53,582
Was war ein Algorithmus, der in der besten
Fall dauerte noch n squared Schritte?

229
00:09:53,582 --> 00:09:54,014
Ja?

230
00:09:54,014 --> 00:09:54,880
>> ZUSCHAUER: [unverständlich].

231
00:09:54,880 --> 00:09:55,900
>> DAVID MALAN: Also Auswahl sortieren.

232
00:09:55,900 --> 00:09:59,150
Da in diesem Problem wirklich reduziert
der Tatsache, dass wieder, ich weiß nicht,

233
00:09:59,150 --> 00:10:02,600
Ich habe die aktuelle kleinsten bis gefunden
Ich habe alle verdammt Elemente überprüft.

234
00:10:02,600 --> 00:10:08,050
So Omega von, sagen wir, n, wir
kam gerade mit einem.

235
00:10:08,050 --> 00:10:09,300
Insertion sort.

236
00:10:09,300 --> 00:10:12,370
Wenn die Liste zufällig sortiert werden
bereits, im besten Fall müssen wir nur

237
00:10:12,370 --> 00:10:15,090
zu einem Durchgang zu machen,
An welchem ​​Punkt sind wir sicher.

238
00:10:15,090 --> 00:10:17,890
Und dann könnte man sagen,
linear zu sein, das ist sicher.

239
00:10:17,890 --> 00:10:20,570
>> Was über Omega von 1?

240
00:10:20,570 --> 00:10:23,790
Was im besten Fall könnte dauern
eine konstante Anzahl von Schritten?

241
00:10:23,790 --> 00:10:27,220
So lineare Suche, wenn Sie einfach Glück
und das Element Sie suchen

242
00:10:27,220 --> 00:10:31,000
am Anfang der Liste rechts,
wenn es das ist, wo Sie beginnen Ihr sind

243
00:10:31,000 --> 00:10:33,070
lineare Durchlaufen dieser Liste.

244
00:10:33,070 --> 00:10:35,180
>> Und dies gilt für eine
Reihe von Dingen.

245
00:10:35,180 --> 00:10:37,660
Zum Beispiel werden auch binäre
Suche ist Omega von 1.

246
00:10:37,660 --> 00:10:40,310
Denn was ist, wenn man wirklich verdammt
Glück und Klatschenkleks in der Mitte des

247
00:10:40,310 --> 00:10:42,950
Ihr Array ist die Anzahl
Sie suchen?

248
00:10:42,950 --> 00:10:45,730
So kann man mit etwas Glück gibt es, wie gut.

249
00:10:45,730 --> 00:10:49,190
>> Dieses schließlich Omega n log n.

250
00:10:49,190 --> 00:10:52,573
So n log n, haben wir nicht wirklich
reden noch nicht, aber -

251
00:10:52,573 --> 00:10:53,300
>> ZUSCHAUER: Merge sort?

252
00:10:53,300 --> 00:10:53,960
>> DAVID MALAN: Merge sort.

253
00:10:53,960 --> 00:10:56,920
Das war der Cliffhanger der letzten Zeit,
wo wir vorgeschlagen, und wir zeigten

254
00:10:56,920 --> 00:10:58,600
visuell, dass es Algorithmen.

255
00:10:58,600 --> 00:11:02,470
Und verschmelzen Art nur eine solche
Algorithmus, der grundsätzlich schneller ist

256
00:11:02,470 --> 00:11:03,450
als einige dieser anderen Jungs.

257
00:11:03,450 --> 00:11:07,800
Tatsächlich verschmelzen kurz ist nicht nur in der
besten Fall n log n, im schlimmsten

258
00:11:07,800 --> 00:11:09,460
Fall n log n.

259
00:11:09,460 --> 00:11:14,540
Und wenn Sie über diese Koinzidenz
Omega und große O ist die gleiche Sache?

260
00:11:14,540 --> 00:11:17,310
Wir können tatsächlich beschreiben, wie das, was ist
Theta genannt, obwohl es ein

261
00:11:17,310 --> 00:11:18,220
etwas weniger häufig.

262
00:11:18,220 --> 00:11:21,730
Aber das bedeutet nur, dass die beiden Grenzen,
in diesem Fall sind die gleichen.

263
00:11:21,730 --> 00:11:25,770
>> Also Mergesort, was hat das
wirklich einkochen, um für uns?

264
00:11:25,770 --> 00:11:27,000
Nun, erinnern an die Motivation.

265
00:11:27,000 --> 00:11:30,340
Lassen Sie mich hochziehen andere Animation,
wir nicht endlich Zeit zu suchen.

266
00:11:30,340 --> 00:11:33,390
Dieser eine, gleiche Idee, aber
es ist ein wenig größer.

267
00:11:33,390 --> 00:11:36,160
Und ich werde weitermachen und darauf hinweisen,
ersten - wir haben Insertion Sort auf

268
00:11:36,160 --> 00:11:39,410
oben links, dann Auswahl sortieren
Bubble-Sort, ein paar andere Sorten -

269
00:11:39,410 --> 00:11:42,670
Shell und schnell -, dass wir nicht gesprochen
über und Heap und Mergesort.

270
00:11:42,670 --> 00:11:47,090
>> So zumindest versuchen, Ihre Augen auf konzentrieren
die ersten drei auf der linken Seite und dann

271
00:11:47,090 --> 00:11:49,120
Mergesort wenn ich auf
diese grünen Pfeil.

272
00:11:49,120 --> 00:11:51,900
Aber ich lasse sie alle laufen, nur um
geben Ihnen ein Gefühl für die Vielfalt der

273
00:11:51,900 --> 00:11:53,980
Algorithmen, die in der Welt existieren.

274
00:11:53,980 --> 00:11:56,180
Ich werde diesen Lauf lassen
nur für ein paar Sekunden.

275
00:11:56,180 --> 00:11:59,640
Und wenn Sie sich Ihre Augen - Pick ein
Algorithmus darauf konzentrieren nur für ein

276
00:11:59,640 --> 00:12:02,970
Sekunden - Sie beginnen zu sehen, die
Muster, dass es die Umsetzung.

277
00:12:02,970 --> 00:12:04,530
>> Merge sort, bemerken, ist getan.

278
00:12:04,530 --> 00:12:06,430
Heap sort, schnelle Art, Schale -

279
00:12:06,430 --> 00:12:09,480
so scheint es, haben wir die drei
schlimmsten Algorithmen letzte Woche.

280
00:12:09,480 --> 00:12:12,960
Aber das ist gut, dass wir hier sind, um
Blick auf Merge sort, ist das einer der

281
00:12:12,960 --> 00:12:16,500
die leichteren, ist zu sehen, auch
obwohl es vermutlich verbiegen Ihre Meinung

282
00:12:16,500 --> 00:12:17,490
nur ein kleines bisschen.

283
00:12:17,490 --> 00:12:21,130
Hier können wir sehen, wie viel
Auswahl sortieren saugt.

284
00:12:21,130 --> 00:12:24,600
>> Aber auf der anderen Seite, ist es
einfach zu implementieren.

285
00:12:24,600 --> 00:12:28,160
Und vielleicht für P Set 3, das ist einer der
Sie wählten Algorithmen zu implementieren

286
00:12:28,160 --> 00:12:28,960
für die Standard Edition.

287
00:12:28,960 --> 00:12:30,970
Vollkommen in Ordnung, vollkommen richtig.

288
00:12:30,970 --> 00:12:35,210
>> Aber noch einmal, wie n groß wird, wenn Sie
wählen, um einen schnelleren Algorithmus zu implementieren

289
00:12:35,210 --> 00:12:39,020
mag Mergesort, stehen die Chancen in größeren und
größere Eingänge, ist Ihr Code nur

290
00:12:39,020 --> 00:12:39,800
gehen, um schneller zu laufen.

291
00:12:39,800 --> 00:12:41,090
Ihre Website wird funktionieren besser.

292
00:12:41,090 --> 00:12:42,650
Ihre Nutzer sich glücklicher zu sein.

293
00:12:42,650 --> 00:12:45,280
Und so sind diese Effekte
der tatsächlich geben

294
00:12:45,280 --> 00:12:47,350
uns einige tiefer gedacht.

295
00:12:47,350 --> 00:12:49,990
>> Werfen wir also einen Blick auf, was zu verschmelzen
Art ist eigentlich alles über.

296
00:12:49,990 --> 00:12:52,992
Das Coole daran ist, dass fusionieren
Art ist genau dies.

297
00:12:52,992 --> 00:12:56,300
Dies ist wiederum das, was wir als
Pseudocode Pseudocode Wesen

298
00:12:56,300 --> 00:12:57,720
Englisch-ähnliche Syntax.

299
00:12:57,720 --> 00:12:59,890
Und der Einfachheit
Art faszinierend.

300
00:12:59,890 --> 00:13:02,840
>> So bei der Eingabe von n Elementen - so dass
bedeutet nur, hier ist ein Array.

301
00:13:02,840 --> 00:13:04,000
Es ist n Dinge in ihm bekam.

302
00:13:04,000 --> 00:13:05,370
Das ist alles, was wir sagen, es sind.

303
00:13:05,370 --> 00:13:07,560
>> Ist n kleiner als 2, zurückzukehren.

304
00:13:07,560 --> 00:13:08,640
Also das ist nur der Fall trivial.

305
00:13:08,640 --> 00:13:12,580
Wenn n kleiner als 2 ist, dann ist es offensichtlich
1 oder 0 ist, in welchem ​​Fall die Sache

306
00:13:12,580 --> 00:13:14,780
bereits sortiert oder nicht vorhanden,
so einfach zurück.

307
00:13:14,780 --> 00:13:15,900
Es gibt nichts zu tun.

308
00:13:15,900 --> 00:13:18,360
Also das ist ein einfacher Fall zu abzupfen.

309
00:13:18,360 --> 00:13:20,110
>> Else, haben wir drei Schritte.

310
00:13:20,110 --> 00:13:23,650
Sortieren Sie die linke Hälfte der Elemente, sortiert
die rechte Hälfte der Elemente,

311
00:13:23,650 --> 00:13:26,650
und dann verschmelzen die sortierten Hälften.

312
00:13:26,650 --> 00:13:29,400
Interessant dabei ist, dass
Ich bin eine Art punting, nicht wahr?

313
00:13:29,400 --> 00:13:32,300
Es ist eine Art kreisförmige Definition
diesem Algorithmus.

314
00:13:32,300 --> 00:13:35,986
In welchem ​​Sinn ist dieser Algorithmus die
Definition kreisförmigen?

315
00:13:35,986 --> 00:13:37,850
>> ZUSCHAUER: [unverständlich].

316
00:13:37,850 --> 00:13:41,670
>> DAVID MALAN: Yeah, mein Sortieralgorithmus,
zwei seiner Schritte sind "sort

317
00:13:41,670 --> 00:13:44,640
etwas. "Und damit die bettelt
Frage, na ja, was soll ich verwenden

318
00:13:44,640 --> 00:13:46,460
die linke Hälfte sortieren
und die rechte Hälfte?

319
00:13:46,460 --> 00:13:49,600
Und das Schöne dabei ist, dass, obwohl
wieder, das ist die knifflige

320
00:13:49,600 --> 00:13:54,030
Teil potenziell, können Sie gleich
Algorithmus, um die linke Hälfte zu sortieren.

321
00:13:54,030 --> 00:13:54,700
>> Aber warten Sie eine Minute.

322
00:13:54,700 --> 00:13:57,070
Wenn man dir sagt, um die Art
linke Hälfte, was sind die beiden

323
00:13:57,070 --> 00:13:58,240
Schritte gehen, um der nächste sein?

324
00:13:58,240 --> 00:14:00,550
Wir sortieren die linke Hälfte des
linke Hälfte und die rechte

325
00:14:00,550 --> 00:14:01,420
Hälfte der linken Hälfte.

326
00:14:01,420 --> 00:14:04,430
Verdammt, wie sortiere ich die beiden
Hälften oder Viertel, jetzt?

327
00:14:04,430 --> 00:14:05,260
>> Aber das ist OK.

328
00:14:05,260 --> 00:14:07,830
Wir haben einen Sortieralgorithmus hier.

329
00:14:07,830 --> 00:14:10,660
Und obwohl Sie vielleicht an Sorgen
erste dieser Art ist von einer unendlichen

330
00:14:10,660 --> 00:14:12,780
Schleife, es ist ein Zyklus, der ist nie
zu Ende gehen - es wird gehen

331
00:14:12,780 --> 00:14:15,770
endet, wenn was passiert?

332
00:14:15,770 --> 00:14:16,970
Wenn n kleiner als 2 ist.

333
00:14:16,970 --> 00:14:19,180
Die schließlich passieren wird,
denn wenn Sie zu halten und die Halbierung

334
00:14:19,180 --> 00:14:23,020
Halbierung halbieren diese Hälften, sicherlich
schließlich wirst du enden

335
00:14:23,020 --> 00:14:25,350
mit nur 1 oder 0 Elemente.

336
00:14:25,350 --> 00:14:28,500
An welchem ​​Punkt, dieser Algorithmus
sagt Sie fertig sind.

337
00:14:28,500 --> 00:14:31,020
>> Also die wirkliche Magie in dieser
Algorithmus scheint in sein

338
00:14:31,020 --> 00:14:33,470
dass letzte Schritt, Zusammenführen.

339
00:14:33,470 --> 00:14:37,190
Diese einfache Idee nur die Zusammenlegung zweier
Dinge, das ist, was letztlich gehen

340
00:14:37,190 --> 00:14:40,920
uns zu erlauben, eine Reihe von sortieren,
sagen wir mal, acht Elementen.

341
00:14:40,920 --> 00:14:44,410
Also ich habe acht weitere Stress-Bälle bis
hier acht Stück Papier, und ein

342
00:14:44,410 --> 00:14:45,500
Google Glass -

343
00:14:45,500 --> 00:14:46,140
denen ich zu halten.

344
00:14:46,140 --> 00:14:46,960
>> [Gelächter]

345
00:14:46,960 --> 00:14:48,970
>> DAVID MALAN: Wenn wir nehmen acht
Freiwillige, und lasst uns sehen, ob wir

346
00:14:48,970 --> 00:14:51,430
spielen diese aus, so.

347
00:14:51,430 --> 00:14:52,500
Wow, OK.

348
00:14:52,500 --> 00:14:53,565
Informatik wird immer Spaß.

349
00:14:53,565 --> 00:14:54,320
In Ordnung.

350
00:14:54,320 --> 00:14:57,770
So wie sie Ihnen etwa drei,
größten Hand gibt.

351
00:14:57,770 --> 00:14:58,580
Vier in den Rücken.

352
00:14:58,580 --> 00:15:02,220
Und wie machen wir Sie
drei in dieser Reihe?

353
00:15:02,220 --> 00:15:03,390
Und vier in der Front.

354
00:15:03,390 --> 00:15:04,920
So können Sie acht, come on up.

355
00:15:04,920 --> 00:15:12,060
>> [Gelächter]

356
00:15:12,060 --> 00:15:13,450
>> DAVID MALAN: Ich bin eigentlich
nicht sicher, was es ist.

357
00:15:13,450 --> 00:15:14,810
Ist es die Stress-Bälle?

358
00:15:14,810 --> 00:15:16,510
Die Schreibtischlampen?

359
00:15:16,510 --> 00:15:18,650
Das Material?

360
00:15:18,650 --> 00:15:19,680
Das Internet?

361
00:15:19,680 --> 00:15:20,160
>> OK.

362
00:15:20,160 --> 00:15:21,310
So kommen auf bis.

363
00:15:21,310 --> 00:15:22,310
Wer möchte -

364
00:15:22,310 --> 00:15:23,570
immer wieder auftauchen.

365
00:15:23,570 --> 00:15:24,240
Mal sehen.

366
00:15:24,240 --> 00:15:26,460
Und das bringt Sie in Lage -

367
00:15:26,460 --> 00:15:27,940
Sie sind in einer Lage.

368
00:15:27,940 --> 00:15:28,670
Uh-oh, warten Sie eine Minute.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - oh, gut.

370
00:15:30,760 --> 00:15:31,310
Alles klar, wir sind gut.

371
00:15:31,310 --> 00:15:35,130
Alles klar, so dass jeder einen Sitz haben,
aber nicht auf der Google Glass.

372
00:15:35,130 --> 00:15:36,475
Lassen Sie mich in die Warteschlange bis diese.

373
00:15:36,475 --> 00:15:37,115
Wie ist dein Name?

374
00:15:37,115 --> 00:15:37,440
>> MICHELLE: Michelle.

375
00:15:37,440 --> 00:15:38,090
>> DAVID MALAN: Michelle?

376
00:15:38,090 --> 00:15:42,000
Okay, erhalten Sie aussehen
Der Aussenseiter, wenn es das ist OK.

377
00:15:42,000 --> 00:15:44,625
Nun, ich auch tun, denke ich,
nur für einen Augenblick.

378
00:15:44,625 --> 00:15:45,875
Alles klar, Standby.

379
00:15:45,875 --> 00:15:48,510

380
00:15:48,510 --> 00:15:50,950
Wir haben versucht, sich mit einem
Use-Case für Google Glass, und wir

381
00:15:50,950 --> 00:15:53,750
dachte, es würde Spaß machen, genau das zu tun
dies, wenn die Leute auf der Bühne sind.

382
00:15:53,750 --> 00:15:57,120
Wir erfassen die Welt
aus ihrer Perspektive.

383
00:15:57,120 --> 00:15:58,410
In Ordnung.

384
00:15:58,410 --> 00:15:59,830
Nicht wahrscheinlich das, was Google gedacht.

385
00:15:59,830 --> 00:16:02,260
Gut, wenn Sie nichts dagegen haben das Tragen
diese für die nächsten umständlich Minuten

386
00:16:02,260 --> 00:16:03,150
das wäre wunderbar.

387
00:16:03,150 --> 00:16:08,620
>> Na gut, so haben wir hier eine Reihe von
Elemente, und das Array nach der

388
00:16:08,620 --> 00:16:11,480
Stücke von Papier in diese Leute '
Hände, ist derzeit unsortiert.

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE: Oh, das ist so komisch.

390
00:16:12,050 --> 00:16:12,810
>> DAVID MALAN: Es ist ziemlich zufällig.

391
00:16:12,810 --> 00:16:15,760
Und in einem Moment, werden wir versuchen,
zu implementieren Mergesort zusammen

392
00:16:15,760 --> 00:16:17,950
und sehen, wo die wichtigste Erkenntnis ist.

393
00:16:17,950 --> 00:16:21,970
Und der Trick mit Merge sort ist
etwas, dass wir nicht noch angenommen.

394
00:16:21,970 --> 00:16:24,030
Tatsächlich brauchen wir einige
zusätzlichen Platz.

395
00:16:24,030 --> 00:16:26,650
Also, was ist los als besonders
Interessant dabei ist, dass diese

396
00:16:26,650 --> 00:16:29,270
Kerle werden sich ein wenig zu bewegen
bit, weil ich gehe davon aus, dass

397
00:16:29,270 --> 00:16:31,880
gibt es eine zusätzliche Anordnung von Raum,
sagen, direkt hinter ihnen.

398
00:16:31,880 --> 00:16:34,570
>> Also, wenn sie sind hinter ihren Stuhl,
Das ist die sekundäre Array.

399
00:16:34,570 --> 00:16:36,960
Wenn sie hier sind sitzen, das ist
das primäre Array.

400
00:16:36,960 --> 00:16:40,170
Aber das ist eine Ressource, die wir haben
nicht so weit mit Blase genutzt

401
00:16:40,170 --> 00:16:42,040
Art, mit Auswahl sortieren
mit Insertion Sort.

402
00:16:42,040 --> 00:16:44,600
Daran erinnern, letzte Woche, jeder nur
Art schlurfte im Ort.

403
00:16:44,600 --> 00:16:46,840
Sie habe keinerlei zusätzlichen Speicher.

404
00:16:46,840 --> 00:16:49,310
Wir haben Platz für Menschen, die von
Menschen bewegen sich um.

405
00:16:49,310 --> 00:16:50,580
>> Dies ist also eine wichtige Erkenntnis, auch.

406
00:16:50,580 --> 00:16:53,410
Es ist das Trade-off, in der Regel in
Informatik, der Ressourcen.

407
00:16:53,410 --> 00:16:55,800
Wenn Sie möchten, zu beschleunigen, etwas
wie die Zeit, du bist zu gehen

408
00:16:55,800 --> 00:16:56,900
haben, einen Preis zu zahlen.

409
00:16:56,900 --> 00:17:00,750
Und einer von diesen Preisen ist sehr oft
Raum, die Größe des Speichers oder harten

410
00:17:00,750 --> 00:17:01,700
Speicherplatz, den Sie verwenden.

411
00:17:01,700 --> 00:17:03,640
Oder, ehrlich gesagt, die Menge
der Programmierer Zeit.

412
00:17:03,640 --> 00:17:06,700
Wie viel Zeit es dauert, der Mensch,
tatsächlich umzusetzen etwas mehr

413
00:17:06,700 --> 00:17:07,829
komplizierten Algorithmus.

414
00:17:07,829 --> 00:17:09,760
Aber für heute, den Trade-off
ist Zeit und Raum.

415
00:17:09,760 --> 00:17:11,930
>> Also, wenn euch könnte nur halten Sie Ihre
Zahlen, so dass wir sehen können, dass Sie

416
00:17:11,930 --> 00:17:15,839
tatsächlich passende 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
Excellent.

418
00:17:16,599 --> 00:17:19,520
Also werde ich versuchen, zu orchestrieren
Dinge können, wenn euch nur

419
00:17:19,520 --> 00:17:21,800
folge meinem Blei hier.

420
00:17:21,800 --> 00:17:26,650
>> So werde ich zu implementieren, zunächst die
ersten Schritt des Pseudocode, das ist

421
00:17:26,650 --> 00:17:29,440
am Eingang von n Elementen, wenn n
weniger als 2, dann zurückzukehren.

422
00:17:29,440 --> 00:17:31,370
Natürlich bedeutet das nicht,
gelten, so dass wir weiterziehen.

423
00:17:31,370 --> 00:17:33,340
So sortieren Sie die linke Hälfte der Elemente.

424
00:17:33,340 --> 00:17:36,220
Also das heißt, ich werde meinen Fokus
Aufmerksamkeit für einen Moment auf diese

425
00:17:36,220 --> 00:17:37,310
vier Jungs hier.

426
00:17:37,310 --> 00:17:39,774
Alles klar, was ich als nächstes tun?

427
00:17:39,774 --> 00:17:40,570
>> ZUSCHAUER: Sortieren Sie die linke Hälfte.

428
00:17:40,570 --> 00:17:42,780
>> DAVID MALAN: So jetzt habe ich zu sortieren
die linke Hälfte von diesen Jungs.

429
00:17:42,780 --> 00:17:45,580
Weil wieder, um sich dem annehmen
Ziel ist es, die linke Hälfte sortieren.

430
00:17:45,580 --> 00:17:46,440
Wie machst du das?

431
00:17:46,440 --> 00:17:49,140
Folgen Sie einfach den Anweisungen, auch
obwohl wir es wieder tun.

432
00:17:49,140 --> 00:17:50,160
So sortieren Sie die linke Hälfte.

433
00:17:50,160 --> 00:17:52,030
Jetzt bin ich ordnen diese beiden Jungs.

434
00:17:52,030 --> 00:17:53,563
Was kommt als nächstes?

435
00:17:53,563 --> 00:17:54,510
>> ZUSCHAUER: Sortieren Sie die linke Hälfte.

436
00:17:54,510 --> 00:17:55,460
>> DAVID MALAN: Sortieren Sie die linke Hälfte.

437
00:17:55,460 --> 00:18:00,680
So, jetzt diese, dieser Platz hier,
ist eine Liste der Größe 1.

438
00:18:00,680 --> 00:18:01,365
Und was ist Ihr Name?

439
00:18:01,365 --> 00:18:02,390
>> PRINCESS DAISY: Princess Daisy.

440
00:18:02,390 --> 00:18:03,690
>> DAVID MALAN: Princess Daisy ist hier.

441
00:18:03,690 --> 00:18:07,470
Und so ist sie bereits sortiert, weil
die Liste ist von Größe 1.

442
00:18:07,470 --> 00:18:09,490
Was muss ich als nächstes tun?

443
00:18:09,490 --> 00:18:13,680
OK, zurück, weil diese Liste ist der
Größe 1, die weniger als 2 ist.

444
00:18:13,680 --> 00:18:14,320
Was ist dann der nächste Schritt?

445
00:18:14,320 --> 00:18:17,490
Und jetzt müssen Sie Art
Backtrack in deinem Geist.

446
00:18:17,490 --> 00:18:19,340
>> Sortieren Sie die rechte Hälfte, das ist -

447
00:18:19,340 --> 00:18:19,570
was ist Ihr Name?

448
00:18:19,570 --> 00:18:20,220
>> LINDA: Linda.

449
00:18:20,220 --> 00:18:20,980
>> DAVID MALAN: Linda.

450
00:18:20,980 --> 00:18:23,210
Und was machen wir jetzt, dass
haben wir eine Liste der Größe 1?

451
00:18:23,210 --> 00:18:24,440
>> ZUSCHAUER: Return.

452
00:18:24,440 --> 00:18:24,760
>> DAVID MALAN: Vorsichtig.

453
00:18:24,760 --> 00:18:29,540
Wir kehren erste, und jetzt das dritte
Schritt - und wenn ich irgendwie zeigen sie durch

454
00:18:29,540 --> 00:18:33,490
umarmt die beiden Sitze jetzt, jetzt habe ich
müssen diese beiden Elemente zu verschmelzen.

455
00:18:33,490 --> 00:18:35,530
So, jetzt leider die Elemente
sind nicht in Ordnung.

456
00:18:35,530 --> 00:18:39,920
Aber das ist, wo die Verschmelzung Prozess
beginnt sich zu überzeugend.

457
00:18:39,920 --> 00:18:42,410
>> Also, wenn euch könnte sich für nur
Einen Moment, ich werde Sie brauchen, in ein

458
00:18:42,410 --> 00:18:44,170
Moment, um hinter den Stuhl fort.

459
00:18:44,170 --> 00:18:46,480
Und wenn Linda, weil 2
kleiner als 4 ist, warum nicht

460
00:18:46,480 --> 00:18:48,130
Sie kommen um zuerst?

461
00:18:48,130 --> 00:18:48,690
Bleiben Sie dort.

462
00:18:48,690 --> 00:18:50,520
So Linda, kommen Sie um die erste.

463
00:18:50,520 --> 00:18:53,820
>> Jetzt in der Realität, wenn es nur ein Array
wir konnten nur bewegen sie in Echtzeit

464
00:18:53,820 --> 00:18:55,360
aus diesem Stuhl an diese Stelle.

465
00:18:55,360 --> 00:18:57,770
So vorstellen, dass einige konstante nahm
Anzahl der Schritte 1.

466
00:18:57,770 --> 00:18:58,480
Und jetzt -

467
00:18:58,480 --> 00:19:01,490
aber wir müssen Sie setzen in
die erste Stelle hier.

468
00:19:01,490 --> 00:19:03,930
>> Und jetzt, wenn Sie könnten um zu kommen,
sowie, wir gehen zu

469
00:19:03,930 --> 00:19:06,300
sein in Position zwei.

470
00:19:06,300 --> 00:19:09,120
Und obwohl dies fühlt sich an wie es ist
Einnahme einer Weile, was ist schön jetzt

471
00:19:09,120 --> 00:19:14,710
dass die linke Hälfte der
linke Hälfte ist nun sortiert.

472
00:19:14,710 --> 00:19:18,010
Also, was war der nächste Schritt, wenn wir jetzt
zurückspulen weiter in der Geschichte?

473
00:19:18,010 --> 00:19:18,980
>> ZUSCHAUER: Rechte Hälfte.

474
00:19:18,980 --> 00:19:19,900
>> DAVID MALAN: Sortieren Sie die rechte Hälfte.

475
00:19:19,900 --> 00:19:21,320
Also Jungs haben, dies zu tun, wie gut.

476
00:19:21,320 --> 00:19:23,510
Also, wenn Sie aufstehen konnte
nur für einen Augenblick?

477
00:19:23,510 --> 00:19:25,192
Und was ist Ihr Name?

478
00:19:25,192 --> 00:19:25,540
>> Jess: Jess.

479
00:19:25,540 --> 00:19:25,870
>> DAVID MALAN: Jess.

480
00:19:25,870 --> 00:19:29,720
OK, so Jess ist nun die linke
Hälfte der rechten Hälfte.

481
00:19:29,720 --> 00:19:31,400
Und so ist eine Liste der Größe 1.

482
00:19:31,400 --> 00:19:32,380
Sie ist offensichtlich sortiert.

483
00:19:32,380 --> 00:19:33,070
Und noch mal Ihr Name?

484
00:19:33,070 --> 00:19:33,630
>> MICHELLE: Michelle.

485
00:19:33,630 --> 00:19:35,340
>> DAVID MALAN: Michelle ist offensichtlich
eine Liste der Größe 1.

486
00:19:35,340 --> 00:19:36,050
Sie ist bereits sortiert.

487
00:19:36,050 --> 00:19:38,690
So, jetzt die Magie passiert,
die Verschmelzung Prozess.

488
00:19:38,690 --> 00:19:39,790
Also wer wird zuerst kommen?

489
00:19:39,790 --> 00:19:41,560
Offensichtlich Michelle.

490
00:19:41,560 --> 00:19:43,280
Also, wenn Sie kommen könnten um zurück.

491
00:19:43,280 --> 00:19:47,090
Der Raum, den wir zur Verfügung haben für sie jetzt
befindet sich direkt hinter diesem Stuhl hier.

492
00:19:47,090 --> 00:19:51,580
Und jetzt, wenn Sie könnten wieder als gut,
wir jetzt haben, klar zu sein, zwei

493
00:19:51,580 --> 00:19:53,810
Hälften, die jeweils eine Größe von 2 -

494
00:19:53,810 --> 00:19:57,090
und nur zur Darstellung willen, wenn Sie
könnte ein wenig von einem Raum zu machen -

495
00:19:57,090 --> 00:19:59,780
eine linke Hälfte hier, eine
rechte Hälfte hier.

496
00:19:59,780 --> 00:20:01,160
>> Spulen Sie weiter in der Geschichte.

497
00:20:01,160 --> 00:20:02,270
Welche Schritt geht es weiter?

498
00:20:02,270 --> 00:20:03,030
>> ZUSCHAUER: Zusammenführen.

499
00:20:03,030 --> 00:20:04,160
>> DAVID MALAN: So, jetzt haben wir zu fusionieren.

500
00:20:04,160 --> 00:20:07,490
So OK, so jetzt, Gott sei Dank, wir
nur bis vier Stühlen befreit.

501
00:20:07,490 --> 00:20:11,480
Deshalb haben wir doppelt so viel Speicher, aber
können wir Flip-flopping geben zwischen

502
00:20:11,480 --> 00:20:12,330
die beiden Arrays.

503
00:20:12,330 --> 00:20:14,190
So ist die Zahl an erster Stelle?

504
00:20:14,190 --> 00:20:14,850
Also Michelle, offensichtlich.

505
00:20:14,850 --> 00:20:16,680
So etwa kommen und
Ihren Sitz hier.

506
00:20:16,680 --> 00:20:19,120
Und dann die Nummer 2 ist offensichtlich
nächsten, so kommen Sie hier.

507
00:20:19,120 --> 00:20:21,520
Nummer 4, Nummer 6.

508
00:20:21,520 --> 00:20:23,390
Und wieder, obwohl es ein
wenig zu Fuß beteiligt,

509
00:20:23,390 --> 00:20:26,010
wirklich, könnten diese sofort passieren,
indem man -

510
00:20:26,010 --> 00:20:26,880
OK, gut gespielt.

511
00:20:26,880 --> 00:20:28,350
>> [Gelächter]

512
00:20:28,350 --> 00:20:29,680
>> DAVID MALAN: Und jetzt sind wir
in ziemlich guter Form.

513
00:20:29,680 --> 00:20:34,910
Die linke Hälfte des gesamten
Eingangs wurde nun sortiert.

514
00:20:34,910 --> 00:20:37,370
Alles klar, so dass diese Jungs hatten
Der Vorteil my -

515
00:20:37,370 --> 00:20:40,340
wie kam es am Ende all die Mädchen auf die
links und all die Jungs auf der rechten Seite?

516
00:20:40,340 --> 00:20:42,450
>> OK, so Jungs nun zuwenden.

517
00:20:42,450 --> 00:20:44,680
Also werde ich nicht gehen Sie durch
diese Schritte.

518
00:20:44,680 --> 00:20:46,550
Wir werden sehen, ob wir erneut kann
das gleiche Pseudocode.

519
00:20:46,550 --> 00:20:50,050
Wenn Sie möchten, gehen Sie vor und aufstehen,
und euch, lassen Sie mich Ihnen das Mikrofon.

520
00:20:50,050 --> 00:20:52,990
Sehen Sie, wenn Sie sich nicht replizieren, was
Wir haben einfach hier auf die

521
00:20:52,990 --> 00:20:53,880
andere Ende der Liste.

522
00:20:53,880 --> 00:20:59,530
Wer braucht zuerst zu sprechen,
basierend auf dem Algorithmus?

523
00:20:59,530 --> 00:21:03,210
So erklären, was Sie tun, bevor
Sie machen alle Bewegungen Fuß.

524
00:21:03,210 --> 00:21:05,930
>> Sprecher 1: Alles klar, also seit
Ich bin der linken Hälfte des

525
00:21:05,930 --> 00:21:07,790
linke Hälfte, kehre ich.

526
00:21:07,790 --> 00:21:08,730
Right?

527
00:21:08,730 --> 00:21:09,250
>> DAVID MALAN: Good.

528
00:21:09,250 --> 00:21:10,350
>> Sprecher 1: Und dann -

529
00:21:10,350 --> 00:21:11,800
>> DAVID MALAN: Wer macht
das Mikrofon weiter gehen?

530
00:21:11,800 --> 00:21:12,920
>> Sprecher 1: Nächste Nummer.

531
00:21:12,920 --> 00:21:14,720
>> Sprecher 2: Also ich bin die rechte Hälfte
der linken Hälfte der

532
00:21:14,720 --> 00:21:17,830
linke Hälfte, und ich zurück.

533
00:21:17,830 --> 00:21:18,050
>> DAVID MALAN: Good.

534
00:21:18,050 --> 00:21:18,550
Sie kehren.

535
00:21:18,550 --> 00:21:21,855
So jetzt, was ist der nächste für Sie zwei?

536
00:21:21,855 --> 00:21:23,740
>> Sprecher 2: Wir wollen sehen, wer kleiner.

537
00:21:23,740 --> 00:21:24,200
>> DAVID MALAN: Genau.

538
00:21:24,200 --> 00:21:24,940
Wir wollen fusionieren.

539
00:21:24,940 --> 00:21:27,590
Der Raum, den wir gehen, um zu verwenden, um zu verschmelzen sind
Sie in, obwohl sie sind

540
00:21:27,590 --> 00:21:30,250
offensichtlich bereits sortiert, wir gehen
um den gleichen Algorithmus befolgen.

541
00:21:30,250 --> 00:21:31,560
Also, wer geht in erster zurück?

542
00:21:31,560 --> 00:21:35,720
Also 3 und dann 7.

543
00:21:35,720 --> 00:21:38,570
Und jetzt geht das Mikrofon
zu diesen Jungs, OK?

544
00:21:38,570 --> 00:21:43,590
>> SPEAKER 3: Also ich bin die rechte Hälfte des
linke und meine n kleiner als

545
00:21:43,590 --> 00:21:45,048
1, so dass ich werde einfach passieren -

546
00:21:45,048 --> 00:21:46,380
>> DAVID MALAN: Good.

547
00:21:46,380 --> 00:21:49,450
>> SPEAKER 4: Ich bin die rechte Hälfte des
rechten Hälfte der rechten Hälfte, und ich bin

548
00:21:49,450 --> 00:21:51,740
auch eine Person, also bin ich
gehen, um zurückzukehren.

549
00:21:51,740 --> 00:21:52,990
So, jetzt haben wir zusammengeführt.

550
00:21:52,990 --> 00:21:55,140

551
00:21:55,140 --> 00:21:56,150
>> SPEAKER 3: So gehen wir zurück.

552
00:21:56,150 --> 00:21:57,160
>> DAVID MALAN: Also in den Rücken gehen.

553
00:21:57,160 --> 00:21:59,200
Also 5 geht, dann 8.

554
00:21:59,200 --> 00:22:01,240
Und nun Publikum, das ist die
Schritt müssen wir jetzt zurückspulen

555
00:22:01,240 --> 00:22:02,200
hinten, um in unseren Köpfen?

556
00:22:02,200 --> 00:22:02,940
>> ZUSCHAUER: Zusammenführen.

557
00:22:02,940 --> 00:22:07,270
>> DAVID MALAN: Zusammenführen von linken und rechten Hälfte
die Hälfte der ursprünglichen linken Hälfte.

558
00:22:07,270 --> 00:22:08,840
So, jetzt -

559
00:22:08,840 --> 00:22:10,520
und gerade dies deutlich zu machen,
machen ein wenig Raum

560
00:22:10,520 --> 00:22:11,690
zwischen Ihnen beiden Jungs.

561
00:22:11,690 --> 00:22:13,800
Also das ist jetzt die beiden Listen,
links und rechts.

562
00:22:13,800 --> 00:22:18,320
So, wie wir jetzt fusionieren euch in
die vordere Sitzreihe wieder?

563
00:22:18,320 --> 00:22:19,600
>> 3 beginnt.

564
00:22:19,600 --> 00:22:20,850
Dann 5, offensichtlich.

565
00:22:20,850 --> 00:22:23,110

566
00:22:23,110 --> 00:22:27,330
Dann 7, 8 und jetzt.

567
00:22:27,330 --> 00:22:28,710
OK, und jetzt sind wir?

568
00:22:28,710 --> 00:22:29,650
>> ZUSCHAUER: Nicht getan.

569
00:22:29,650 --> 00:22:32,440
>> DAVID MALAN: Nicht getan, denn
offensichtlich gibt es einen Schritt übrig.

570
00:22:32,440 --> 00:22:35,720
Aber noch einmal, der Grund warum ich bin mit dieser
Jargon wie "Rewind in your mind,"

571
00:22:35,720 --> 00:22:37,160
es ist, weil das ist wirklich
was passiert.

572
00:22:37,160 --> 00:22:39,610
Wir durch alle diese Schritte gehen,
aber wir sind eine Art Pause für ein

573
00:22:39,610 --> 00:22:42,480
Moment, tauchen tiefer in die
Algorithmus, einen Moment innehalten,

574
00:22:42,480 --> 00:22:45,840
Tauchen tiefer in den Algorithmus und
jetzt müssen wir der Rücklauf in unserem sortieren

575
00:22:45,840 --> 00:22:49,430
Köpfe und rückgängig all dieser Schichten
dass wir irgendwie auf Eis gelegt.

576
00:22:49,430 --> 00:22:51,790
>> So, jetzt haben wir zwei Listen der Größe 4.

577
00:22:51,790 --> 00:22:54,790
Wenn euch aufstehen konnte ein letztes Mal
und machen ein wenig Platz hier, um

578
00:22:54,790 --> 00:22:57,230
deutlich machen, dass diese die Linke
die Hälfte des ursprünglichen, die

579
00:22:57,230 --> 00:22:58,620
rechte Hälfte der ursprünglichen.

580
00:22:58,620 --> 00:23:01,060
Wer ist die erste Zahl, die wir
brauchen, um in den Rücken ziehen?

581
00:23:01,060 --> 00:23:01,870
Michelle, natürlich.

582
00:23:01,870 --> 00:23:03,230
>> Also haben wir Michelle hier.

583
00:23:03,230 --> 00:23:05,080
Und wer hat die Nummer 2?

584
00:23:05,080 --> 00:23:06,440
Nummer 2 kommt auf der Rückseite als auch.

585
00:23:06,440 --> 00:23:07,800
Nummer 3?

586
00:23:07,800 --> 00:23:08,510
Excellent.

587
00:23:08,510 --> 00:23:16,570
Number 4, Nr. 5, Nr. 6,
Nummer 7 und Nummer 8.

588
00:23:16,570 --> 00:23:18,850
>> OK, so fühlte es sich wie eine Menge
von Schritten, das ist sicher.

589
00:23:18,850 --> 00:23:22,390
Aber jetzt wollen wir sehen, ob wir nicht bestätigen können,
Art intuitiv, dass diese

590
00:23:22,390 --> 00:23:26,190
Algorithmus grundlegend, zumal
n wird wirklich groß ist, wie wir gesehen haben

591
00:23:26,190 --> 00:23:29,170
mit den Animationen ist
grundsätzlich schneller.

592
00:23:29,170 --> 00:23:33,400
Also ich behaupte, diesen Algorithmus im schlimmsten
Fall und auch im besten Fall

593
00:23:33,400 --> 00:23:36,160
ist groß O von n mal n log.

594
00:23:36,160 --> 00:23:39,160
Das heißt, es ist ein Aspekt dieser
Algorithmus, der n Schritte unternimmt, aber

595
00:23:39,160 --> 00:23:43,110
gibt es einen anderen Aspekt irgendwo in
dass Iteration, dass Looping, dass

596
00:23:43,110 --> 00:23:44,410
nimmt log n Schritte.

597
00:23:44,410 --> 00:23:49,154
Können wir unsere Finger auf das, was die
zwei Zahlen sich beziehen?

598
00:23:49,154 --> 00:23:51,320
Nun, wo -

599
00:23:51,320 --> 00:23:54,160
wo ist das Mikrofon zu gehen?

600
00:23:54,160 --> 00:23:58,660
>> Sprecher 1: Würde die sich n sein
Brechen Sie uns in zwei -

601
00:23:58,660 --> 00:23:59,630
Division durch zwei, im Wesentlichen.

602
00:23:59,630 --> 00:24:00,120
>> DAVID MALAN: Genau.

603
00:24:00,120 --> 00:24:03,000
Jedes Mal, wenn wir sehen, in jedem Algorithmus so
Bis jetzt hat es schon dieses Muster von

604
00:24:03,000 --> 00:24:04,200
Teilen, teilen, teilen.

605
00:24:04,200 --> 00:24:05,700
Und es ist in der Regel reduziert
etwas, das ist

606
00:24:05,700 --> 00:24:07,100
logarithmisch, log Basis 2.

607
00:24:07,100 --> 00:24:10,180
Aber es könnte wirklich alles sein,
aber einloggen Basis 2.

608
00:24:10,180 --> 00:24:11,330
>> Nun, was über die n?

609
00:24:11,330 --> 00:24:14,550
Ich kann sehen, dass wir freundlich von Ihnen geteilt
Jungs - unterteilt Sie, eingeteilt Sie,

610
00:24:14,550 --> 00:24:15,910
Sie unterteilt, unterteilt man.

611
00:24:15,910 --> 00:24:18,760
Woher kommt das Ende kommen?

612
00:24:18,760 --> 00:24:19,810
>> So ist es die Verschmelzung.

613
00:24:19,810 --> 00:24:20,610
Weil darüber nachdenken.

614
00:24:20,610 --> 00:24:25,420
Beim Zusammenführen acht Personen zusammen,
wobei die Hälfte von denen ein Satz von vier

615
00:24:25,420 --> 00:24:27,770
und die andere Hälfte ein weiteres
Satz von vier, wie Sie gehen

616
00:24:27,770 --> 00:24:28,820
über das Tun der Verschmelzung?

617
00:24:28,820 --> 00:24:30,830
Nun, habt ihr es
ziemlich intuitiv.

618
00:24:30,830 --> 00:24:34,140
>> Aber wenn ich es täte stattdessen ein wenig mehr
methodisch, könnte ich an hingewiesen haben

619
00:24:34,140 --> 00:24:38,090
die linke Person zum ersten Mal mit meinem linken
Hand, zeigte auf der linken Person

620
00:24:38,090 --> 00:24:42,080
dieser Hälfte mit meiner rechten Hand, und
nur danach ging durch die

621
00:24:42,080 --> 00:24:46,990
Liste zeigt auf die kleinste Element
jedes Mal, bewegte meine Finger über und

622
00:24:46,990 --> 00:24:48,970
über, wie er in der Liste benötigt.

623
00:24:48,970 --> 00:24:51,890
Aber was ist Schlüssel zu dieser Verschmelzung
Prozess ist, vergleiche ich diese Paare

624
00:24:51,890 --> 00:24:53,460
der Elemente.

625
00:24:53,460 --> 00:24:57,270
Von der rechten Hälfte und der linken
Hälfte, ich bin nicht einmal Backtracking.

626
00:24:57,270 --> 00:25:00,570
>> Also die Zusammenführung selbst nimmt
nicht mehr als n Schritte.

627
00:25:00,570 --> 00:25:03,250
Und wie oft hatte ich
zu, dass Zusammenführen tun?

628
00:25:03,250 --> 00:25:07,150
Nun, nicht mehr als n, und wir
sah, dass mit der endgültigen Zusammenführung.

629
00:25:07,150 --> 00:25:13,120
Und so, wenn Sie etwas tun, was kommt
einloggen n Schritte n mal, oder umgekehrt,

630
00:25:13,120 --> 00:25:15,210
es geht um uns mal n log n.

631
00:25:15,210 --> 00:25:16,310
>> Und warum ist das besser?

632
00:25:16,310 --> 00:25:19,600
Nun, wenn wir schon wissen, dass log
n ist besser als n - richtig?

633
00:25:19,600 --> 00:25:22,590
Wir sahen in binäre Suche, das Telefonbuch
Beispielsweise war definitiv log n

634
00:25:22,590 --> 00:25:23,760
besser als linear.

635
00:25:23,760 --> 00:25:28,420
Das heißt also, mal n log n ist
definitiv besser als n mal einen anderen

636
00:25:28,420 --> 00:25:30,390
n, n AKA Quadrat.

637
00:25:30,390 --> 00:25:32,400
Und das ist, was wir letztlich fühlen.

638
00:25:32,400 --> 00:25:34,928
>> So großen Applaus, wenn
wir könnten, für diese Jungs.

639
00:25:34,928 --> 00:25:38,920
>> [Applaus]

640
00:25:38,920 --> 00:25:41,550
>> DAVID MALAN: Und Ihre Abschiedsgeschenke -
Sie halten die Zahlen,

641
00:25:41,550 --> 00:25:44,010
wenn Sie möchten.

642
00:25:44,010 --> 00:25:45,620
Und dein Abschiedsgeschenk, wie üblich.

643
00:25:45,620 --> 00:25:47,290
Oh, und wir schicken Ihnen
das Filmmaterial, Michelle.

644
00:25:47,290 --> 00:25:48,343
Vielen Dank.

645
00:25:48,343 --> 00:25:49,250
In Ordnung.

646
00:25:49,250 --> 00:25:50,400
Helfen Sie sich selbst mit einem Stress-Ball.

647
00:25:50,400 --> 00:25:54,110
>> Und lassen Sie mich nach oben ziehen, in der Zwischenzeit
unser Freund Rob Bowden zu bieten

648
00:25:54,110 --> 00:25:59,520
etwas andere Perspektive auf das,
da kann man über diese denken

649
00:25:59,520 --> 00:26:01,280
Schritte geschieht in einem etwas
anders.

650
00:26:01,280 --> 00:26:04,750
In der Tat, das Set-up für das, was Rob geht um
um uns zu zeigen, dass wir davon ausgegangen,

651
00:26:04,750 --> 00:26:09,030
bereits getan die Aufteilung der
große Liste in acht kleinen Listen

652
00:26:09,030 --> 00:26:10,570
jeder Größe 1.

653
00:26:10,570 --> 00:26:13,350
>> So ändern wir den Pseudocode ein
wenig, nur um von sich bei der sortieren

654
00:26:13,350 --> 00:26:15,320
Kern Vorstellung davon, wie die Zusammenführung funktioniert.

655
00:26:15,320 --> 00:26:17,600
Aber die Laufzeit, welche
er ist etwa zu tun ist immer noch

656
00:26:17,600 --> 00:26:19,110
gehen, um die gleichen sein.

657
00:26:19,110 --> 00:26:23,540
Und wieder ist das Set-up ist hier, dass er
begonnen mit acht Listen der Größe 1.

658
00:26:23,540 --> 00:26:27,730
Sie haben also den Teil, wo er ist vermisst
tatsächlich getan der log n, log n, log n

659
00:26:27,730 --> 00:26:31,205
Aufteilen des Eingangssignals.

660
00:26:31,205 --> 00:26:32,120
>> [VIDEO PLAYBACK]

661
00:26:32,120 --> 00:26:33,615
>> -Das ist es für einen Schritt.

662
00:26:33,615 --> 00:26:38,270
Für Schritt zwei, wiederholt
verschmelze Paare von Listen.

663
00:26:38,270 --> 00:26:39,210
>> DAVID MALAN: Hm.

664
00:26:39,210 --> 00:26:41,270
Nur Audio kommt
aus meinem Computer.

665
00:26:41,270 --> 00:26:42,520
Lassen Sie uns noch einmal versuchen.

666
00:26:42,520 --> 00:26:45,330

667
00:26:45,330 --> 00:26:48,310
>> -Just beliebig wählen, welche -
jetzt haben wir vier Listen.

668
00:26:48,310 --> 00:26:51,590

669
00:26:51,590 --> 00:26:52,120
Lernen vor.

670
00:26:52,120 --> 00:26:53,040
>> DAVID MALAN: Dort gehen wir.

671
00:26:53,040 --> 00:27:00,510
>> Merging-108 und 15 landen wir
mit der Liste 15, 108.

672
00:27:00,510 --> 00:27:07,170
Zusammenführen von 50 und 4, wir
am Ende mit 4, 50.

673
00:27:07,170 --> 00:27:12,990
Zusammenführen von 8 und 42, wir
am Ende mit 8, 42.

674
00:27:12,990 --> 00:27:19,970
Und Zusammenführen 23 und 16, wir
am Ende mit 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Nun sind alle unsere Listen sind der Größe 2.

676
00:27:23,270 --> 00:27:26,690
Beachten Sie, dass jede der
vier Listen sortiert ist.

677
00:27:26,690 --> 00:27:29,450
So können wir anfangen Verschmelzung
Paare von Listen wieder.

678
00:27:29,450 --> 00:27:38,420
Zusammenführen von 15 und 108 und 4 und 50, wir
nehmen Sie zuerst die 4, dann die 15, dann

679
00:27:38,420 --> 00:27:41,500
die 50, dann die 108.

680
00:27:41,500 --> 00:27:50,610
Zusammenführen von 8, 42 und 16, 23, wir zunächst
die 8, dann die 16, dann die 23,

681
00:27:50,610 --> 00:27:52,700
dann ist die 42.

682
00:27:52,700 --> 00:27:57,600
>> So, jetzt haben wir nur zwei Listen der Größe
4, von denen jede sortiert.

683
00:27:57,600 --> 00:28:01,170
So, jetzt haben wir verschmelzen diese beiden Listen.

684
00:28:01,170 --> 00:28:11,835
Erstens haben wir die 4 nehmen, dann nehmen wir die
8, dann nehmen wir die 15, dann 16, dann

685
00:28:11,835 --> 00:28:19,456
23, dann 42, dann 50, dann 108.

686
00:28:19,456 --> 00:28:19,872
>> [END VIDEO PLAYBACK]

687
00:28:19,872 --> 00:28:23,430
>> DAVID MALAN: Wieder Ankündigung, er nie
berührt einen bestimmten Tasse mehr als einmal

688
00:28:23,430 --> 00:28:24,860
nach dem Vorrücken darüber hinaus.

689
00:28:24,860 --> 00:28:26,200
Also ist er nie wiederholen.

690
00:28:26,200 --> 00:28:29,850
Also ist er immer in Bewegung zur Seite,
und das ist, wo wir unsere n einsehen.

691
00:28:29,850 --> 00:28:33,290
>> Warum lassen Sie nicht mich hochzuziehen eine Animation
dass wir früher gesehen, aber dieses Mal

692
00:28:33,290 --> 00:28:35,110
sich nur auf Merge sort.

693
00:28:35,110 --> 00:28:38,030
Lassen Sie mich gehen Sie vor und vergrößern
Auf diesem hier.

694
00:28:38,030 --> 00:28:42,530
Zunächst lassen Sie mich wählen einen zufälligen Eingang,
vergrößern dies, und Sie können von zu sehen sortieren

695
00:28:42,530 --> 00:28:46,600
was wir für selbstverständlich hielt, früher,
Mergesort tatsächlich tut.

696
00:28:46,600 --> 00:28:50,330
>> So bemerken, dass Sie diese Hälften erhalten oder
diese Viertel oder Achtel der diese

697
00:28:50,330 --> 00:28:53,140
Problem, dass alle von einer plötzlichen
beginnen, gut in Form zu nehmen.

698
00:28:53,140 --> 00:28:57,070
Und dann endlich, sehen Sie auf
ganz am Ende, dass bam,

699
00:28:57,070 --> 00:28:58,860
alles zusammengeführt.

700
00:28:58,860 --> 00:29:01,690
>> So sind nur drei verschiedene
nimmt auf der gleichen Idee.

701
00:29:01,690 --> 00:29:05,980
Aber die wichtigste Erkenntnis, wie divide
und in der ersten Klasse zu erobern,

702
00:29:05,980 --> 00:29:10,640
war, dass wir irgendwie teilen beschlossen
das Problem in etwas Großes, in

703
00:29:10,640 --> 00:29:14,760
etwas Art identisch im Geiste,
aber kleiner und kleiner

704
00:29:14,760 --> 00:29:15,660
und kleiner.

705
00:29:15,660 --> 00:29:18,420
>> Nun noch eine unterhaltsame Art und Weise zu denken sortieren
über diese, obwohl es nicht

706
00:29:18,420 --> 00:29:20,520
gehen, um Ihnen die gleiche intuitive
Verständnis ist

707
00:29:20,520 --> 00:29:21,640
Die folgende Animation.

708
00:29:21,640 --> 00:29:25,400
Also das ist ein Video jemand zusammen
dass damit verbundenen unterschiedlichen

709
00:29:25,400 --> 00:29:29,970
Klänge mit den verschiedenen Operationen
Insertion Sort, Merge für Art und

710
00:29:29,970 --> 00:29:31,150
ein paar andere.

711
00:29:31,150 --> 00:29:32,330
So in einem Moment, werde ich spielen getroffen.

712
00:29:32,330 --> 00:29:33,600
Es geht darum, eine Minute lang.

713
00:29:33,600 --> 00:29:37,410
Und auch wenn man noch die
Muster geschieht, dieser Zeit können Sie

714
00:29:37,410 --> 00:29:41,420
auch hören, wie diese Algorithmen sind
Durchführen anders und mit

715
00:29:41,420 --> 00:29:43,950
etwas verschiedenen Mustern.

716
00:29:43,950 --> 00:29:45,830
>> Dies ist Insertion Sort.

717
00:29:45,830 --> 00:29:50,400
>> [TÖNE SPIELT]

718
00:29:50,400 --> 00:29:52,400
>> DAVID MALAN: Es wird wieder versuchen
um jedes Element einfügen

719
00:29:52,400 --> 00:29:52,900
in, wo es hingehört.

720
00:29:52,900 --> 00:29:54,628
Dies ist bubble sort.

721
00:29:54,628 --> 00:30:10,097
>> [TÖNE SPIELT]

722
00:30:10,097 --> 00:30:13,630
>> DAVID MALAN: Und Sie können von Gefühl sortieren
wie relativ wenig Arbeit es tut

723
00:30:13,630 --> 00:30:15,834
auf jedem Schritt.

724
00:30:15,834 --> 00:30:20,470
Dies ist, was Langeweile klingt.

725
00:30:20,470 --> 00:30:21,472
>> [TÖNE SPIELT]

726
00:30:21,472 --> 00:30:25,222
>> DAVID MALAN: Dies ist Selection Sort,
wo wir wählen Sie das Element wollen wir durch

727
00:30:25,222 --> 00:30:28,845
Durchlaufen wieder und wieder und wieder
und legt es am Anfang.

728
00:30:28,845 --> 00:30:37,674
>> [TÖNE SPIELT]

729
00:30:37,674 --> 00:30:43,970
>> DAVID MALAN: Dies ist Mergesort, die
Sie kann wirklich beginnen zu fühlen.

730
00:30:43,970 --> 00:30:51,810
>> [TÖNE SPIELT]

731
00:30:51,810 --> 00:30:54,770
>> [Gelächter]

732
00:30:54,770 --> 00:30:58,395
>> DAVID MALAN: Etwas namens gnome
Art, die wir nicht geschaut haben.

733
00:30:58,395 --> 00:31:13,630
>> [TÖNE SPIELT]

734
00:31:13,630 --> 00:31:17,910
>> DAVID MALAN: So lassen Sie mich sehen, jetzt,
abgelenkt, wie Sie hoffentlich durch die

735
00:31:17,910 --> 00:31:21,110
Musik, wenn ich ein wenig rutschen
etwas Mathe hier.

736
00:31:21,110 --> 00:31:24,850
Also gibt es eine vierte Möglichkeit, dass wir
darüber nachzudenken, was es bedeutet, diese

737
00:31:24,850 --> 00:31:29,210
Funktionen schneller als diejenigen sein
dass wir noch nie gesehen.

738
00:31:29,210 --> 00:31:32,470
Und wenn Sie auf dem Golfplatz aus
ein Mathematik-Hintergrund, Sie

739
00:31:32,470 --> 00:31:36,030
tatsächlich vielleicht schon wissen, dass Sie
kann eine Laufzeit über diese Technik zu schlagen -

740
00:31:36,030 --> 00:31:40,400
nämlich Rekursion eine Funktion
das nennt sich irgendwie.

741
00:31:40,400 --> 00:31:44,780
>> Und wieder daran erinnern, dass Merge sort
Pseudocode war in dem Sinne, rekursiv

742
00:31:44,780 --> 00:31:48,460
dass eine Zusammenführung Art der Schritte
war zu sortieren nennen -

743
00:31:48,460 --> 00:31:49,740
das heißt, sich.

744
00:31:49,740 --> 00:31:52,480
Aber zum Glück, weil wir immer
Aufruf sortieren oder Mergesort,

745
00:31:52,480 --> 00:31:55,880
Insbesondere für ein kleiner
und kleinere Liste, wir schließlich

746
00:31:55,880 --> 00:32:00,005
Talsohle dank dem, was wir nennen
eine Basis Fall die hart codierte Fall, dass

747
00:32:00,005 --> 00:32:04,270
sagte, wenn die Liste ist klein, weniger als 2
in diesem Fall nur sofort zurück.

748
00:32:04,270 --> 00:32:07,550
Wenn wir nicht haben, dass spezielle Fall der
Algorithmus würde nie Talsohle,

749
00:32:07,550 --> 00:32:11,010
und Sie würden in der Tat in eine bekommen
Endlosschleife wirklich immer.

750
00:32:11,010 --> 00:32:14,330
>> Aber nehmen wir an, dass wir jetzt stellen wollte
einige Zahlen dazu, wieder mit n

751
00:32:14,330 --> 00:32:15,660
wenn die Größe des Eingangs.

752
00:32:15,660 --> 00:32:18,680
Und ich wollte Sie fragen, was ist
die gesamte Zeit beteiligt

753
00:32:18,680 --> 00:32:19,800
Mergevorgang Art?

754
00:32:19,800 --> 00:32:22,960
Oder allgemeiner, was ist
die Kosten für die es in der Zeit?

755
00:32:22,960 --> 00:32:24,730
>> Nun, es ist ziemlich einfach, dass zu messen.

756
00:32:24,730 --> 00:32:29,010
Wenn n kleiner als 2 ist, involviert die Zeit
Sortierung in n Elemente,

757
00:32:29,010 --> 00:32:30,480
wenn n 2 ist, 0 ist.

758
00:32:30,480 --> 00:32:31,410
Weil wir gerade zurück.

759
00:32:31,410 --> 00:32:32,510
Es gibt keine Arbeit getan werden.

760
00:32:32,510 --> 00:32:35,660
Nun wohl, vielleicht ist es einen Schritt oder zwei
Schritte, um herauszufinden, die Menge der

761
00:32:35,660 --> 00:32:38,420
arbeiten, aber es ist nahe genug, um 0, dass
Ich werde einfach sagen, keine Arbeit

762
00:32:38,420 --> 00:32:40,940
erforderlich, wenn die Liste ist so klein
zu uninteressant.

763
00:32:40,940 --> 00:32:42,580
>> Aber dieser Fall ist interessant.

764
00:32:42,580 --> 00:32:47,320
Die rekursive Fall war der Zweig der
der Pseudocode, anderes sagte, sortieren

765
00:32:47,320 --> 00:32:52,000
die linke Hälfte, sortieren das Recht
Hälfte, verschmelzen die beiden Hälften.

766
00:32:52,000 --> 00:32:55,530
Nun, warum tut dies Ausdruck
stellen, dass die Kosten?

767
00:32:55,530 --> 00:32:58,690
Nun, T von n bedeutet nur die
Zeit, um n Elemente zu sortieren.

768
00:32:58,690 --> 00:33:03,070
Und dann auf der rechten Seite des
Gleichheitszeichen gibt, teilte die T von n

769
00:33:03,070 --> 00:33:06,600
von 2 ist auf die Kosten, was bezogen?

770
00:33:06,600 --> 00:33:07,570
Sortieren der linken Hälfte.

771
00:33:07,570 --> 00:33:10,990
Die andere T von n geteilt durch 2 ist
vermutlich mit Bezug auf die Kosten für

772
00:33:10,990 --> 00:33:12,390
sortieren die rechte Hälfte.

773
00:33:12,390 --> 00:33:14,590
>> Und dann die plus n?

774
00:33:14,590 --> 00:33:15,420
Ist die Verschmelzung.

775
00:33:15,420 --> 00:33:19,120
Denn wenn Sie haben zwei Listen, eine der
Größe n mehr als 2 und eine andere Größe n

776
00:33:19,120 --> 00:33:22,580
über 2, müssen Sie im Wesentlichen berühren
jedes dieser Elemente, so wie Rob

777
00:33:22,580 --> 00:33:24,990
berührt jede der Schalen, und nur
wie wir bereits an jedem der

778
00:33:24,990 --> 00:33:26,310
Freiwillige auf der Bühne.

779
00:33:26,310 --> 00:33:28,790
So n ist der Aufwand der Zusammenführung.

780
00:33:28,790 --> 00:33:31,780
>> Jetzt leider diese Formel
ist auch selbst rekursiv.

781
00:33:31,780 --> 00:33:36,390
Also, wenn die Frage gestellt, wenn n, sagen wir,
16, wenn es 16 Leute auf der Bühne

782
00:33:36,390 --> 00:33:40,670
oder 16 Tassen in dem Video, wie viele insgesamt
Schritte braucht es, um sie zu sortieren

783
00:33:40,670 --> 00:33:41,550
mit Merge sort?

784
00:33:41,550 --> 00:33:45,790
Es ist eigentlich nicht eine offensichtliche Antwort,
denn jetzt haben Sie von sortieren

785
00:33:45,790 --> 00:33:48,500
rekursiv beantworten diese Formel.

786
00:33:48,500 --> 00:33:51,190
>> Aber das ist OK, weil mich schlagen
was wir tun, die folgenden.

787
00:33:51,190 --> 00:33:56,670
Der Zeitaufwand, um 16 Personen zu sortieren oder
16 Tassen wird vertreten sein

788
00:33:56,670 --> 00:33:58,020
allgemein als T von 16 Jahren.

789
00:33:58,020 --> 00:34:01,400
Aber das entspricht nach unserer
vorherige Formel, 2-fache der Menge

790
00:34:01,400 --> 00:34:04,780
Zeit, die es braucht, um zu sortieren
8 Tassen plus 16.

791
00:34:04,780 --> 00:34:08,590
Und wieder ist die Zeit plus 16 zu verschmelzen,
und die zwei Zeiten T von 8 ist die

792
00:34:08,590 --> 00:34:10,790
Zeit, um linke Hälfte und rechte Hälfte sortieren.

793
00:34:10,790 --> 00:34:11,989
>> Aber auch dies ist nicht genug.

794
00:34:11,989 --> 00:34:13,210
Wir müssen in tiefer tauchen.

795
00:34:13,210 --> 00:34:16,409
Das heißt, wir müssen die Antwort
Frage, was ist T von 8?

796
00:34:16,409 --> 00:34:19,610
Nun T von 8 ist nur 2
Zeiten T von 4 und 8.

797
00:34:19,610 --> 00:34:20,520
Nun, was ist T von 4?

798
00:34:20,520 --> 00:34:23,780
T 4 ist nur 2 mal T von 2 plus 4.

799
00:34:23,780 --> 00:34:25,489
Nun, was ist T von 2?

800
00:34:25,489 --> 00:34:29,030
T 2 ist nur 2 mal T von 1 plus 2 sein.

801
00:34:29,030 --> 00:34:31,940
>> Und wieder sind wir irgendwie immer
stecken in diesem Zyklus.

802
00:34:31,940 --> 00:34:34,790
Aber es ist darüber zu treffen, dass
sogenannte Base-Case.

803
00:34:34,790 --> 00:34:37,310
Denn was ist T von 1, haben wir behaupten?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
So, jetzt endlich können wir rückwärts arbeiten.

806
00:34:39,730 --> 00:34:44,290
>> Wenn T von 1 0 ist, kann ich jetzt gehen zurück bis eine
Die Linie die diesen Kerl hier, und ich kann

807
00:34:44,290 --> 00:34:46,330
Stecker in 0 für T 1.

808
00:34:46,330 --> 00:34:51,770
Das heißt also, es gleich 2 mal Null,
anders als 0, plus 2 bekannt.

809
00:34:51,770 --> 00:34:53,739
Und damit ganze Ausdruck 2 ist.

810
00:34:53,739 --> 00:34:58,740
>> Nun, wenn ich den T 2, dessen Antwort
2 ist, stecken Sie es in der mittleren Linie, T

811
00:34:58,740 --> 00:35:02,740
von 4, das gibt mir 2 mal
2 plus 4, 8 so.

812
00:35:02,740 --> 00:35:07,080
Wenn ich dann stecken in 8 zum vorherigen
Linie, das gibt mir 2 mal 8, 16.

813
00:35:07,080 --> 00:35:12,470
Und wenn wir dann weiter, dass mit dem
24, indem in 16, bekommen wir endlich ein

814
00:35:12,470 --> 00:35:13,820
Wert von 64.

815
00:35:13,820 --> 00:35:18,480
>> Nun, an und für sich eine Art spricht
nichts der n-Notation, die

816
00:35:18,480 --> 00:35:20,700
big O, das Omega, dass wir
worden reden.

817
00:35:20,700 --> 00:35:24,890
Aber es stellt sich heraus, dass 64 tatsächlich
16, die Größe des Eingangssignals,

818
00:35:24,890 --> 00:35:27,110
einloggen Basis 2 von 16 Jahren.

819
00:35:27,110 --> 00:35:30,200
Und wenn dies ist ein wenig ungewohnt, nur
denken Sie zurück, und es wird wieder kommen

820
00:35:30,200 --> 00:35:30,700
Sie schließlich.

821
00:35:30,700 --> 00:35:33,775
Wenn dies Logbase 2, es ist wie 2
angehoben, um das, was gibt Ihnen 16?

822
00:35:33,775 --> 00:35:36,380
Oh, das ist 4, so ist es 16 mal 4.

823
00:35:36,380 --> 00:35:39,380
>> Und wieder ist es keine große Sache, wenn diese
ist eine Art verschwommene Erinnerung jetzt.

824
00:35:39,380 --> 00:35:43,720
Aber jetzt, auf den Glauben nehmen
dass 16 log 16 64.

825
00:35:43,720 --> 00:35:46,590
Und so in der Tat, mit diesem einfachen Vernunft
, überprüfen wir bestätigt haben -

826
00:35:46,590 --> 00:35:48,250
aber nicht bewiesen formal -

827
00:35:48,250 --> 00:35:52,800
dass die Laufzeit von Merge
Art ist in der Tat n n einloggen.

828
00:35:52,800 --> 00:35:53,790
>> Also nicht schlecht.

829
00:35:53,790 --> 00:35:57,260
Es ist definitiv besser als die
Algorithmen, die wir bisher gesehen haben, und

830
00:35:57,260 --> 00:36:00,710
es ist, weil wir genutzt haben, ein,
eine Technik namens Rekursion.

831
00:36:00,710 --> 00:36:03,880
Aber viel interessanter als das, dass
Begriff der Teilung und Eroberung.

832
00:36:03,880 --> 00:36:07,460
Auch wirklich Woche 0 Zeug, dass
auch jetzt wird in einer wiederkehrenden

833
00:36:07,460 --> 00:36:08,740
mehr überzeugende Art und Weise.

834
00:36:08,740 --> 00:36:11,750
>> Nun wird ein Spaß wenig Übung, wenn Sie
nie getan - und Sie wahrscheinlich

835
00:36:11,750 --> 00:36:14,660
wäre nicht zu haben, denn irgendwie normale
Leute nicht denken, dies zu tun.

836
00:36:14,660 --> 00:36:20,650
Aber wenn ich gehe zu google.com und wenn
Ich möchte etwas erfahren

837
00:36:20,650 --> 00:36:22,356
Rekursion, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Gelächter]

840
00:36:29,058 --> 00:36:32,030
[Mehr Gelächter]

841
00:36:32,030 --> 00:36:33,385
DAVID MALAN: Bad Witz langsam ausbreitet.

842
00:36:33,385 --> 00:36:34,450
[Gelächter]

843
00:36:34,450 --> 00:36:36,970
DAVID MALAN: Nur für den Fall, es ist da.

844
00:36:36,970 --> 00:36:38,710
Ich wusste nicht buchstabieren es falsch,
und es ist der Witz.

845
00:36:38,710 --> 00:36:40,810
In Ordnung.

846
00:36:40,810 --> 00:36:42,950
Erklären Sie es den Menschen neben dir, wenn
Es hat nicht ganz geklickt nur noch.

847
00:36:42,950 --> 00:36:47,650
Aber Rekursion, allgemein bezeichnet
der Prozess einer Funktion, Aufrufen

848
00:36:47,650 --> 00:36:51,430
selbst, oder allgemeiner, eine Teilung
Problem in etwas, das kann

849
00:36:51,430 --> 00:36:56,220
stückweise durch Lösen identisch gelöst
Vertreter Probleme.

850
00:36:56,220 --> 00:36:58,400
>> Nun, lasst Wechselräder
nur für einen Augenblick.

851
00:36:58,400 --> 00:37:00,840
Wir möchten auf bestimmte Cliffhanger enden,
also lasst uns beginnen, um

852
00:37:00,840 --> 00:37:05,870
die Bühne, für einige Minuten,
auf eine sehr einfache Idee -

853
00:37:05,870 --> 00:37:07,620
dass der Vertauschung zweier Elemente, nicht wahr?

854
00:37:07,620 --> 00:37:10,040
All diese Algorithmen, die wir waren
reden über die letzten paar

855
00:37:10,040 --> 00:37:12,420
Vorträge beinhalten einige
Art von Austausch.

856
00:37:12,420 --> 00:37:14,630
Heute wurde es von ihnen immer sichtbar
aus ihrem Sessel und

857
00:37:14,630 --> 00:37:18,570
herumlaufen, aber im Code, würden wir
nehmen Sie einfach ein Element aus einem Array

858
00:37:18,570 --> 00:37:20,370
und plop es in eine andere.

859
00:37:20,370 --> 00:37:21,880
>> So, wie wir dabei vorgehen?

860
00:37:21,880 --> 00:37:24,850
Nun, lasst mich weitermachen und schreiben
ein schnelles Programm hier.

861
00:37:24,850 --> 00:37:31,600
Ich werde weitermachen und tun
diese wie folgt.

862
00:37:31,600 --> 00:37:33,910
Nennen wir diese -

863
00:37:33,910 --> 00:37:38,070
Was wollen wir, dieses zu nennen?

864
00:37:38,070 --> 00:37:38,650
>> Eigentlich nicht.

865
00:37:38,650 --> 00:37:39,420
Lassen Sie mich zurückzuspulen.

866
00:37:39,420 --> 00:37:41,220
Ich möchte nicht, das zu tun
Cliffhanger noch.

867
00:37:41,220 --> 00:37:42,270
Es wird den Spaß verderben.

868
00:37:42,270 --> 00:37:43,600
Lassen Sie uns diese statt.

869
00:37:43,600 --> 00:37:47,430
>> Angenommen, dass ich ein wenig schreiben wollen
Programm und das umfasst heute diese

870
00:37:47,430 --> 00:37:48,700
Idee der Rekursion.

871
00:37:48,700 --> 00:37:50,370
Ich irgendwie bekam vor mir da.

872
00:37:50,370 --> 00:37:51,420
Ich werde folgendes tun.

873
00:37:51,420 --> 00:38:00,220
>> Erstens gehören eine schnelle Standard-io.h,
sowie eine Include von cs50.h.

874
00:38:00,220 --> 00:38:03,200
Und dann werde ich weitermachen
und erklären int main nichtig

875
00:38:03,200 --> 00:38:04,360
in der üblichen Weise.

876
00:38:04,360 --> 00:38:07,920
Ich erkannte, ich habe die Datei falsch benannt, so
lassen Sie mich einfach ein. c Erweiterung hier so

877
00:38:07,920 --> 00:38:09,510
dass wir es richtig zu kompilieren.

878
00:38:09,510 --> 00:38:10,970
Starten Sie diese Funktion ausschalten.

879
00:38:10,970 --> 00:38:13,290
>> Und die Funktion, die ich schreiben möchte, ganz
Einfach ausgedrückt, ist derjenige, der fragt,

880
00:38:13,290 --> 00:38:16,210
Benutzer für eine Reihe und dann summiert sich
alle Zahlen zwischen dem

881
00:38:16,210 --> 00:38:19,920
Anzahl und, sagen wir, 0.

882
00:38:19,920 --> 00:38:22,510
Also zuerst werde ich weitermachen
und erklären, int n.

883
00:38:22,510 --> 00:38:24,760
Dann kopiere ich einige Code, dass
wir haben für eine Weile benutzt.

884
00:38:24,760 --> 00:38:26,660
Während etwas wahr ist.

885
00:38:26,660 --> 00:38:28,000
Ich komme zurück auf das in einem Moment.

886
00:38:28,000 --> 00:38:29,010
>> Was will ich tun?

887
00:38:29,010 --> 00:38:33,460
Ich möchte sagen, printf positive
integer bitte.

888
00:38:33,460 --> 00:38:36,130
Und dann bin ich zu gehen
sagen n bekommt bekommen int.

889
00:38:36,130 --> 00:38:38,800
Also noch einmal, einige Textvorschlag Code
dass wir vor verwendet.

890
00:38:38,800 --> 00:38:40,810
Und ich werde, dies zu tun
während n kleiner als 1 ist.

891
00:38:40,810 --> 00:38:44,120
So wird dies zu gewährleisten, dass der Benutzer
gibt mir eine positive ganze Zahl ist.

892
00:38:44,120 --> 00:38:45,490
>> Und jetzt werde ich folgendes tun.

893
00:38:45,490 --> 00:38:51,020
Ich möchte hinzufügen, bis alle Zahlen
zwischen 1 und und n oder 0 ist und n,

894
00:38:51,020 --> 00:38:52,570
äquivalent zu bekommen die Gesamtsumme.

895
00:38:52,570 --> 00:38:55,100
Die große Sigma-Symbol
Sie erinnern sich vielleicht an.

896
00:38:55,100 --> 00:38:59,050
Also werde ich dies durch erste Berufung zu tun
eine Funktion aufgerufen sigma,

897
00:38:59,050 --> 00:39:06,030
Übergabe in n, und dann bin ich zu gehen
printf sagen, die Antwort ist recht.

898
00:39:06,030 --> 00:39:08,180
>> Also kurz gesagt, ich bekomme und
int von dem Benutzer.

899
00:39:08,180 --> 00:39:09,280
Ich stelle sicher, es ist positiv.

900
00:39:09,280 --> 00:39:12,700
Ich erkläre, eine Variable namens Antwort
Typ int und speichern es in die Rückkehr

901
00:39:12,700 --> 00:39:15,610
Wert von sigma, übergibt n als Eingabe.

902
00:39:15,610 --> 00:39:17,060
Und dann drucke ich diese Antwort.

903
00:39:17,060 --> 00:39:19,550
>> Leider, obwohl sigma klingt
wie etwas, das in sein könnten

904
00:39:19,550 --> 00:39:24,040
die math.h Datei, seine Erklärung,
es ist eigentlich nicht.

905
00:39:24,040 --> 00:39:24,690
Also das ist OK.

906
00:39:24,690 --> 00:39:26,170
Ich kann das selbst implementieren.

907
00:39:26,170 --> 00:39:29,160
Ich werde eine Funktion namens implementieren
sigma, und es geht um eine nehmen

908
00:39:29,160 --> 00:39:29,900
Parameter -

909
00:39:29,900 --> 00:39:32,100
wir nennen es einfach m, nur
so ist es anders.

910
00:39:32,100 --> 00:39:35,910
Und dann hier, werde ich sagen,
gut, wenn m kleiner als 1 ist - dies ist ein

911
00:39:35,910 --> 00:39:38,180
sehr uninteressant Programm.

912
00:39:38,180 --> 00:39:41,700
Also werde ich weitermachen und
sofort 0 zurück.

913
00:39:41,700 --> 00:39:45,920
Es macht einfach keinen Sinn, addieren Sie alle
Die Zahlen zwischen 1 und m, wenn m

914
00:39:45,920 --> 00:39:48,470
selbst 0 oder negativ ist.

915
00:39:48,470 --> 00:39:50,900
>> Und dann werde ich weitermachen
und tun dies sehr iterativ.

916
00:39:50,900 --> 00:39:53,090
Ich werde diese Art der alten Schule zu tun,
und ich werde weitermachen

917
00:39:53,090 --> 00:39:57,150
und sagen, dass ich zu gehen
deklarieren eine Summe 0 sein.

918
00:39:57,150 --> 00:39:59,630
Dann werde ich zu haben
eine for-Schleife von int -

919
00:39:59,630 --> 00:40:02,820
und lass es mich tun, um unser Spiel
Verteilung Code, so dass Sie eine Kopie

920
00:40:02,820 --> 00:40:07,500
zu Hause. int i bekommt 1 auf bis zu
i kleiner oder gleich m ist.

921
00:40:07,500 --> 00:40:09,430
i plus plus.

922
00:40:09,430 --> 00:40:11,430
Und dann innerhalb dieser for-Schleife -

923
00:40:11,430 --> 00:40:12,440
wir sind fast da -

924
00:40:12,440 --> 00:40:15,810
Summe bekommt Summe plus 1.

925
00:40:15,810 --> 00:40:17,670
Und dann werde ich die Summe zurück.

926
00:40:17,670 --> 00:40:19,420
>> Also tat ich dies schnell,
ganz zugegebenermaßen.

927
00:40:19,420 --> 00:40:22,775
Aber nochmals, die Hauptfunktion ziemlich
unkompliziert, basierte auf Code, den wir haben

928
00:40:22,775 --> 00:40:23,190
geschrieben so weit.

929
00:40:23,190 --> 00:40:25,610
Verwendet die Dual-Schleife, um eine positive bekommen
int von dem Benutzer.

930
00:40:25,610 --> 00:40:29,870
Ich habe dann passieren, dass int auf eine neue Funktion
genannt sigma, ruft sie, wieder n.

931
00:40:29,870 --> 00:40:33,100
Und ich speichern den Rückgabewert, die Antwort
von der Blackbox derzeit

932
00:40:33,100 --> 00:40:35,460
bekannt als sigma, in einer variablen
genannt Antwort.

933
00:40:35,460 --> 00:40:36,580
Dann habe ich ausdrucken.

934
00:40:36,580 --> 00:40:39,090
>> Wenn wir nun die Geschichte weiter,
wie ist Sigma umgesetzt?

935
00:40:39,090 --> 00:40:40,840
Ich schlage vor, wie folgt zu implementieren.

936
00:40:40,840 --> 00:40:43,560
Zuerst ein wenig Fehlerprüfung
um sicherzustellen, dass der Benutzer nicht ist

937
00:40:43,560 --> 00:40:46,480
Messing mit mir und Weitergabe in
einige negativ oder 0-Wert.

938
00:40:46,480 --> 00:40:49,710
Dann erkläre ich eine Variable namens
Zusammenfassend und auf 0 setzen.

939
00:40:49,710 --> 00:40:55,910
>> Und jetzt habe ich beginnen sich zu bewegen von i gleich
1 den ganzen Weg bis einschließlich m,

940
00:40:55,910 --> 00:41:00,130
denn ich will alles umfassen
Zahlen von eins bis m, inklusive.

941
00:41:00,130 --> 00:41:04,350
Und innerhalb dieser for-Schleife, ich habe gerade zu tun
Summe bekommt, was es jetzt ist, zuzüglich der

942
00:41:04,350 --> 00:41:08,900
Wert von i.

943
00:41:08,900 --> 00:41:10,370
Zuzüglich des Wertes der i.

944
00:41:10,370 --> 00:41:14,090
>> Nebenbei, wenn Sie noch nicht gesehen
vor, es gibt einige syntaktische Zucker

945
00:41:14,090 --> 00:41:14,870
für diese Leitung.

946
00:41:14,870 --> 00:41:21,120
Ich kann umschreiben dies als Plus gleich i,
nur um mich retten ein paar Tastenanschläge

947
00:41:21,120 --> 00:41:22,570
und sehen ein bisschen kühler.

948
00:41:22,570 --> 00:41:23,140
Aber das ist alles.

949
00:41:23,140 --> 00:41:24,660
Es ist funktionell dasselbe.

950
00:41:24,660 --> 00:41:26,710
>> Leider ist dieser Kodex
noch nicht zu kompilieren.

951
00:41:26,710 --> 00:41:31,600
Wenn ich make ausführe sigma 0, wie am
Ich werde bei Get schrie?

952
00:41:31,600 --> 00:41:33,473
Was es wird nicht dabei?

953
00:41:33,473 --> 00:41:35,740
>> ZUSCHAUER: [unverständlich].

954
00:41:35,740 --> 00:41:37,800
>> DAVID MALAN: Yeah, ich habe nicht erklären
die Funktion up top, right?

955
00:41:37,800 --> 00:41:40,590
C ist ziemlich blöd, dass es nur
macht, was Sie sagen, zu tun, und Sie

956
00:41:40,590 --> 00:41:41,880
haben, um es in dieser Reihenfolge zu tun.

957
00:41:41,880 --> 00:41:45,910
Und so, wenn ich hier eingeben schlagen, werde ich
erhalten eine Warnung über Sigma impliziten

958
00:41:45,910 --> 00:41:46,860
Erklärung.

959
00:41:46,860 --> 00:41:48,120
>> Oh, kein Problem.

960
00:41:48,120 --> 00:41:50,370
Ich kann gehen bis an die Spitze, und ich kann
sagen, alles in Ordnung, warten Sie eine Minute.

961
00:41:50,370 --> 00:41:54,240
Sigma ist eine Funktion, kehrt
ein int und erwartet ein

962
00:41:54,240 --> 00:41:56,620
int als Eingabe Semikolon.

963
00:41:56,620 --> 00:41:59,550
Oder ich könnte die ganze Funktion setzen
über Haupt-, aber im Allgemeinen würde ich

964
00:41:59,550 --> 00:42:02,260
raten, dass, weil es
schön, um immer über Haupt an der Spitze so

965
00:42:02,260 --> 00:42:06,310
Sie können eintauchen und wissen, was ein
Programms durch das Lesen wichtigsten ersten tun.

966
00:42:06,310 --> 00:42:07,930
>> So, jetzt lassen Sie mich klar auf den Bildschirm.

967
00:42:07,930 --> 00:42:09,330
Remake sigma 0.

968
00:42:09,330 --> 00:42:10,340
Alles scheint zu überprüfen.

969
00:42:10,340 --> 00:42:11,970
Lassen Sie mich laufen sigma 0.

970
00:42:11,970 --> 00:42:12,770
Positive unter.

971
00:42:12,770 --> 00:42:15,580
Ich gebe es die Anzahl
3 es einfach zu halten.

972
00:42:15,580 --> 00:42:18,710
Also das sollte mir 3
zzgl. 2 plus 1, also 6.

973
00:42:18,710 --> 00:42:20,750
Geben Sie, und zwar bekomme ich 6.

974
00:42:20,750 --> 00:42:21,820
>> Ich kann etwas tun, größer -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Gerade als Tangente, werde ich tun
etwas Lächerliches wie eine wirklich große

977
00:42:27,690 --> 00:42:30,375
Anzahl, Oh, die tatsächlich geklappt -

978
00:42:30,375 --> 00:42:31,600
eh, ich glaube nicht, das ist richtig.

979
00:42:31,600 --> 00:42:32,810
Mal sehen.

980
00:42:32,810 --> 00:42:34,060
Lasst uns wirklich damit herum.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Das ist ein Problem.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Was ist da los?

985
00:42:44,970 --> 00:42:46,050
Der Code ist nicht so schlimm.

986
00:42:46,050 --> 00:42:48,470
Es ist immer noch linear.

987
00:42:48,470 --> 00:42:50,810
Pfeifen ist eine gute Wirkung, though.

988
00:42:50,810 --> 00:42:52,060
Was ist da los?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Nicht sicher, ob ich es hörte.

991
00:42:55,620 --> 00:42:57,620
So stellt sich heraus - und
dies ist als ein beiseite.

992
00:42:57,620 --> 00:42:59,400
Dies ist nicht der Kern der
Idee der Rekursion.

993
00:42:59,400 --> 00:43:02,480
Es stellt sich heraus, weil ich versuche, mich
stellen so eine große Zahl, die meisten

994
00:43:02,480 --> 00:43:06,980
wahrscheinlich ist es falsch interpretiert
durch C als nicht positive Zahl ist,

995
00:43:06,980 --> 00:43:09,980
aber negative Zahl ist.

996
00:43:09,980 --> 00:43:12,690
>> Wir haben nicht darüber gesprochen, aber es
stellt sich heraus, es gibt negative Zahlen

997
00:43:12,690 --> 00:43:14,210
in der Welt zusätzlich
auf positive Zahlen.

998
00:43:14,210 --> 00:43:16,290
Und die Mittel, mit denen Sie
negativen Zahlen darstellen

999
00:43:16,290 --> 00:43:19,530
im Wesentlichen ist, verwenden Sie einen
spezielles Bit, um anzuzeigen,

1000
00:43:19,530 --> 00:43:20,400
positiv in negativ.

1001
00:43:20,400 --> 00:43:22,950
Es ist ein wenig komplizierter als das,
aber das ist die Grundidee.

1002
00:43:22,950 --> 00:43:26,740
>> Also leider, wenn C ist verwirrend einer
dieser Bits als eigentlich bedeutet,

1003
00:43:26,740 --> 00:43:30,790
oh, das ist eine negative Zahl, meine Schleife
hier, zum Beispiel, ist eigentlich nie

1004
00:43:30,790 --> 00:43:31,740
gehen, um zu beenden.

1005
00:43:31,740 --> 00:43:33,850
Also, wenn ich tatsächlich etwas Druck
wieder und wieder, würden wir

1006
00:43:33,850 --> 00:43:34,650
sehen eine ganze Menge.

1007
00:43:34,650 --> 00:43:36,220
Aber auch dies ist neben dem Punkt.

1008
00:43:36,220 --> 00:43:38,590
Das ist wirklich nur eine Art
intellektuelle Neugier, dass wir kommen

1009
00:43:38,590 --> 00:43:39,550
zurück, um schließlich.

1010
00:43:39,550 --> 00:43:43,400
Aber jetzt, ist dies eine richtige
Umsetzung, wenn wir annehmen, dass die

1011
00:43:43,400 --> 00:43:45,970
Benutzer stellen ints
die passen in ints.

1012
00:43:45,970 --> 00:43:49,370
>> Aber ich behaupte, dass dieser Code, ehrlich gesagt,
könnte so viel einfacher durchgeführt werden.

1013
00:43:49,370 --> 00:43:54,060
Wenn das Ziel bei der Hand ist, um eine Zahl zu
wie m und summieren sich alle der

1014
00:43:54,060 --> 00:43:59,510
Zahlen zwischen ihr und 1, oder umgekehrt
zwischen 1 und es behaupte ich,

1015
00:43:59,510 --> 00:44:03,380
dass ich ausleihen kann diese Idee, dass fusionieren
Art hatte, die nahm ein Problem

1016
00:44:03,380 --> 00:44:05,660
dieser Größe und Dividieren es
in etwas kleiner.

1017
00:44:05,660 --> 00:44:09,875
Vielleicht nicht die Hälfte, aber auch kleinere, aber
repräsentativ gleich.

1018
00:44:09,875 --> 00:44:12,130
Gleiche Idee, aber ein kleineres Problem.

1019
00:44:12,130 --> 00:44:15,470
>> Also ich bin eigentlich - lassen Sie mich diese Datei speichern
eine andere Versionsnummer.

1020
00:44:15,470 --> 00:44:17,670
Wir nennen diese Version
1 statt 0.

1021
00:44:17,670 --> 00:44:20,790
Und ich behaupte, dass ich eigentlich
reimplementieren dies in dieser Art von

1022
00:44:20,790 --> 00:44:22,160
irreen Weg.

1023
00:44:22,160 --> 00:44:23,710
>> Ich werde ein Teil davon allein zu lassen.

1024
00:44:23,710 --> 00:44:27,710
Ich werde sagen, wenn m kleiner
als oder gleich 0 -

1025
00:44:27,710 --> 00:44:29,280
Ich werde einfach ein wenig sein
mehr anal diesmal

1026
00:44:29,280 --> 00:44:30,520
mit meinem Fehlerprüfung -

1027
00:44:30,520 --> 00:44:33,190
Ich werde weitermachen und 0 zurück.

1028
00:44:33,190 --> 00:44:34,490
Das ist beliebig.

1029
00:44:34,490 --> 00:44:37,500
Ich bin einfach nur entscheiden, wenn der Benutzer
gibt mir eine negative Zahl, ich bin

1030
00:44:37,500 --> 00:44:41,490
Rückkehr 0, und sie sollten gelesen
die Dokumentation näher.

1031
00:44:41,490 --> 00:44:42,170
>> Else -

1032
00:44:42,170 --> 00:44:44,070
bemerken, was ich tun werde.

1033
00:44:44,070 --> 00:44:49,260
Else Ich werde m plus zurückkehren -

1034
00:44:49,260 --> 00:44:51,010
was ist der Sigma-m?

1035
00:44:51,010 --> 00:44:56,710
Nun, sigma von m plus m minus 1,
zzgl. m minus 2 plus minus 3 m.

1036
00:44:56,710 --> 00:44:58,030
Ich will nicht, all das heraus zu schreiben.

1037
00:44:58,030 --> 00:44:59,120
Warum ich nicht einfach Kahn?

1038
00:44:59,120 --> 00:45:05,080
Rekursiv nenne mich mit einem leicht
kleineres Problem, Semikolon,

1039
00:45:05,080 --> 00:45:06,840
und nennen es einen Tag?

1040
00:45:06,840 --> 00:45:07,040
>> Right?

1041
00:45:07,040 --> 00:45:10,980
Nun, auch hier könnte man glauben, oder sich Sorgen
dass dies eine Endlosschleife, dass ich

1042
00:45:10,980 --> 00:45:15,450
induzieren, wobei ich bin der Umsetzung
sigma sigma von Berufung.

1043
00:45:15,450 --> 00:45:20,342
Aber das ist völlig in Ordnung, weil ich
Gedanken voraus, die eine zusätzliche Linien?

1044
00:45:20,342 --> 00:45:22,600
>> ZUSCHAUER: [unverständlich].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID MALAN: 23 bis 26, die
ist mein wenn Bedingung.

1046
00:45:25,430 --> 00:45:28,390
Denn was ist schön, über die
Subtraktion hier, weil ich halten

1047
00:45:28,390 --> 00:45:31,180
Übergabe sigma kleinere Probleme, kleinere
Probleme, kleiner - es ist nicht

1048
00:45:31,180 --> 00:45:31,870
halb so groß.

1049
00:45:31,870 --> 00:45:34,380
Es ist nur ein kleiner Schritt Baby,
aber das ist OK.

1050
00:45:34,380 --> 00:45:38,050
Denn schließlich werden wir arbeiten
unseren Weg bis zu 1 oder 0 ist.

1051
00:45:38,050 --> 00:45:41,630
Und wenn wir 0 schlagen, ist sigma nicht
gehen, um sich nicht mehr aufrufen.

1052
00:45:41,630 --> 00:45:43,590
Es wird sofort 0 zurück.

1053
00:45:43,590 --> 00:45:47,960
>> Also der Effekt, wenn Sie diese Art von Wind
sich in Ihrem Geist, ist es m plus hinzufügen

1054
00:45:47,960 --> 00:45:52,740
m minus 1 plus minus 2 m sowie m minus
3 plus Punkt, Punkt, Punkt, m minus

1055
00:45:52,740 --> 00:45:57,820
m, schließlich geben Sie 0 und die
Effekt ist letztlich alle hinzufügen

1056
00:45:57,820 --> 00:45:59,070
diese Dinge zusammen.

1057
00:45:59,070 --> 00:46:02,380
So haben wir nicht, mit Rekursion
löste das Problem, dass wir

1058
00:46:02,380 --> 00:46:03,470
konnte nicht vor zu lösen.

1059
00:46:03,470 --> 00:46:06,840
Tatsächlich Version 0 von dieser, und jedes
Problem bisher war lösbar

1060
00:46:06,840 --> 00:46:09,980
mit nur mit for-Schleifen oder während
Schleifen oder ähnliche Konstrukte.

1061
00:46:09,980 --> 00:46:13,150
>> Aber Rekursion, ich wage zu behaupten, gibt uns
eine andere Art des Denkens über

1062
00:46:13,150 --> 00:46:17,010
Probleme, wobei, wenn wir können eine
Problem, teilen Sie es von etwas

1063
00:46:17,010 --> 00:46:22,340
etwas groß in etwas etwas
kleiner, behaupte ich, dass wir es lösen können

1064
00:46:22,340 --> 00:46:26,040
vielleicht ein wenig mehr elegant in Bezug
des Entwurfs, mit weniger Code,

1065
00:46:26,040 --> 00:46:30,980
und vielleicht sogar Probleme zu lösen, das wäre
schwieriger sein, als wir werden schließlich

1066
00:46:30,980 --> 00:46:33,280
sehen, die Lösung rein iterativ.

1067
00:46:33,280 --> 00:46:35,980
>> Aber der Cliffhanger, dass ich
wollen uns verlassen auf war.

1068
00:46:35,980 --> 00:46:40,720
Lassen Sie mich gehen Sie vor und öffnen
bis eine Datei aus -

1069
00:46:40,720 --> 00:46:44,300
tatsächlich, lass mich gehen und
tun dies wirklich schnell.

1070
00:46:44,300 --> 00:46:46,875
Lassen Sie mich gehen Sie vor und schlagen
der folgende.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Unter heutigen Code ist diese Datei hier.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Dieser hier, NOSWAP.

1075
00:47:03,050 --> 00:47:06,260
>> Also das ist ein dummes kleines Programm, dass
Ich peitschte, dass Ansprüche zu tun

1076
00:47:06,260 --> 00:47:06,940
der folgende.

1077
00:47:06,940 --> 00:47:10,140
In main, es zuerst erklärt ein
int namens x und ordnet sie

1078
00:47:10,140 --> 00:47:11,100
der Wert von 1.

1079
00:47:11,100 --> 00:47:13,520
Dann erklärt sie ein int y und
weist sie den Wert 2.

1080
00:47:13,520 --> 00:47:15,310
Dann druckt, was x und y.

1081
00:47:15,310 --> 00:47:17,781
Dann sagt er, Tauschen, Punkt Punkt Punkt.

1082
00:47:17,781 --> 00:47:21,670
>> Dann behauptet, sein Aufruf einer Funktion
Swap genannt, vorbei in x und

1083
00:47:21,670 --> 00:47:24,290
y, die Idee davon, dass hoffentlich
x und y kommen wieder

1084
00:47:24,290 --> 00:47:25,620
anders, im Gegenteil.

1085
00:47:25,620 --> 00:47:27,110
Dann behaupten vertauscht!

1086
00:47:27,110 --> 00:47:28,420
mit einem Ausrufezeichen.

1087
00:47:28,420 --> 00:47:30,190
Dann druckt x und y.

1088
00:47:30,190 --> 00:47:33,480
>> Aber es stellt sich heraus, dass dies sehr
einfache Demonstration unten

1089
00:47:33,480 --> 00:47:35,570
hier ist wirklich buggy.

1090
00:47:35,570 --> 00:47:38,870
Auch wenn ich über die Vereinbarkeit eines temporären
variabel und vorübergehend in ein Putting

1091
00:47:38,870 --> 00:47:42,010
es, dann bin ich Umwidmung
a der Wert von b -

1092
00:47:42,010 --> 00:47:45,080
das fühlt sich vernünftig, weil ich
Gespeicherte eine Kopie in ein Temp.

1093
00:47:45,080 --> 00:47:48,410
Dann aktualisiere ich b gleich
Was auch immer in Temp.

1094
00:47:48,410 --> 00:47:51,610
Diese Art von Shell Spiel bewegen ein
in b und b in eine durch diese

1095
00:47:51,610 --> 00:47:54,360
Mitte-Mann namens Temp fühlt
durchaus sinnvoll.

1096
00:47:54,360 --> 00:47:57,270
>> Aber ich behaupten, dass, wenn ich das laufen
Code, wie ich jetzt tun -

1097
00:47:57,270 --> 00:47:59,490
lassen Sie mich gehen Sie vor und fügen Sie ihn hier.

1098
00:47:59,490 --> 00:48:01,995
Ich rufe diese noswap.c.

1099
00:48:01,995 --> 00:48:05,630
Und wie der Name schon sagt, ist dies nicht
gehen, um eine richtige Programm sein.

1100
00:48:05,630 --> 00:48:09,460
Machen NOSWAP. / No Swap.

1101
00:48:09,460 --> 00:48:12,110
x 1 ist, y 2, Tauschen, getauscht.

1102
00:48:12,110 --> 00:48:14,220
x 1 ist, y 2.

1103
00:48:14,220 --> 00:48:16,920
Dies ist grundsätzlich falsch, auch
obwohl dies scheint perfekt

1104
00:48:16,920 --> 00:48:17,730
mir vernünftig.

1105
00:48:17,730 --> 00:48:21,330
Und es gibt einen Grund, aber wir sind nicht
gehen, um die Ursache nur noch offenbaren.

1106
00:48:21,330 --> 00:48:24,610
>> Denn nun ist die zweite Cliffhanger ich wollte
Ihnen überlassen ist, eine

1107
00:48:24,610 --> 00:48:27,120
Ankündigung von Arten auf Gutscheincodes.

1108
00:48:27,120 --> 00:48:31,590
Unser Innovation mit späten Tage in diesem Jahr
provoziert eine nicht-triviale Zahl

1109
00:48:31,590 --> 00:48:33,830
von Fragen, die war
nicht unsere Absicht.

1110
00:48:33,830 --> 00:48:36,590
Die Absicht dieser Gutscheincodes
wobei wenn du Teil des Problems

1111
00:48:36,590 --> 00:48:39,850
gesetzt früh, damit immer einen zusätzlichen Tag,
war wirklich zu helfen, euch zu helfen

1112
00:48:39,850 --> 00:48:42,420
Sie beginnen früh, sortieren
der durch incentivizing Sie.

1113
00:48:42,420 --> 00:48:44,880
Hilft uns verteilen Last auf
Bürozeiten besser, so dass

1114
00:48:44,880 --> 00:48:45,740
Es ist eine Art Win-Win.

1115
00:48:45,740 --> 00:48:48,860
>> Leider denke ich, meine Anweisungen
sind bisher nicht auf dem neuesten Stand, sehr klar, so

1116
00:48:48,860 --> 00:48:52,230
Ich ging zurück an diesem Wochenende und aktualisiert
die Spezifikation in größer, mutiger Text

1117
00:48:52,230 --> 00:48:53,600
erklären Kugeln wie diese.

1118
00:48:53,600 --> 00:48:56,900
Und nur um es öffentlich zu sagen, durch
Standardmäßig Problem Sets sind aufgrund Donnerstag

1119
00:48:56,900 --> 00:48:58,400
am Mittag, nach der Lehrplan.

1120
00:48:58,400 --> 00:49:02,030
Wenn Sie früh beginnen, Finishing Teil
das Problem bis Mittwoch um 12:00 Uhr eingestellt

1121
00:49:02,030 --> 00:49:05,170
PM, der Teil, der einen Coupon betrifft
Code, ist die Idee, dass man verlängern

1122
00:49:05,170 --> 00:49:07,710
Ihre Frist für die
P gesetzt, bis Montag.

1123
00:49:07,710 --> 00:49:10,890
Das heißt, etwas abseits einer winzigen Teil des P
gesetzt relativ zu dem, was in der Regel ist die

1124
00:49:10,890 --> 00:49:13,200
größeres Problem, und Sie kaufen
sich einen zusätzlichen Tag.

1125
00:49:13,200 --> 00:49:15,190
Auch hier wird es Ihnen zu denken
das Problem gesetzt, bekommt man zu

1126
00:49:15,190 --> 00:49:16,380
Bürozeiten früher.

1127
00:49:16,380 --> 00:49:20,670
Aber der Gutscheincode Problem ist immer noch
erforderlich, auch wenn Sie nicht eintragen.

1128
00:49:20,670 --> 00:49:23,340
>> Aber mehr zwingend ist dies.

1129
00:49:23,340 --> 00:49:26,520
(Bühnenflüstern) Und die Leute verlassen
Anfang sind gonna es bereuen.

1130
00:49:26,520 --> 00:49:28,620
Wie sind die Leute auf dem Balkon.

1131
00:49:28,620 --> 00:49:32,510
Ich im Voraus, um den Leuten zu entschuldigen auf
der Balkon aus Gründen, die sein

1132
00:49:32,510 --> 00:49:33,920
klar in nur einem Augenblick.

1133
00:49:33,920 --> 00:49:37,050
>> Also wir haben das Glück, eine haben
CS50 ehemaliger Leiter Lehre Fellows

1134
00:49:37,050 --> 00:49:39,302
eine Firma namens dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Sie haben sehr großzügig gespendet ein
Gutschein-Code für diese hier viel Platz,

1136
00:49:45,500 --> 00:49:48,180
was aus der
üblichen 2 Gigabyte.

1137
00:49:48,180 --> 00:49:51,740
Also, was ich dachte, wir würden auf dies zu tun
letzte Anmerkung ist zu tun ein bisschen wie ein Werbegeschenk,

1138
00:49:51,740 --> 00:49:55,380
wobei in nur einem Augenblick werden wir enthüllen,
der Gewinner und wer hat einen Gutschein

1139
00:49:55,380 --> 00:49:57,980
Code, den Sie dann in ihre gehen
Website, geben Sie ihn in, und voila, erhalten eine

1140
00:49:57,980 --> 00:50:01,370
ganze Menge mehr Platz für Ihre Dropbox
Gerät und für Ihre persönlichen Dateien.

1141
00:50:01,370 --> 00:50:05,690
>> Und zuerst, wer würde gerne teilnehmen
in dieser Zeichnung?

1142
00:50:05,690 --> 00:50:09,630
OK, jetzt, da macht es noch mehr Spaß.

1143
00:50:09,630 --> 00:50:14,010
Die Person, die diese 25-Gigabyte erhält
Gutschein-Code - was bei weitem nicht

1144
00:50:14,010 --> 00:50:16,150
zwingender als der spät
Tage jetzt vielleicht -

1145
00:50:16,150 --> 00:50:20,620
ist derjenige, der auf der Oberseite sitzt ein
Sitzkissen unter denen es

1146
00:50:20,620 --> 00:50:21,620
dass Gutscheincode.

1147
00:50:21,620 --> 00:50:23,480
Sie können jetzt unter aussehen
Ihre Sitzkissen.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [VIDEO PLAYBACK]

1150
00:50:29,680 --> 00:50:31,620
>> -Eins, zwei, drei.

1151
00:50:31,620 --> 00:50:35,015
>> [SCREAMING]

1152
00:50:35,015 --> 00:50:35,985
>> -Sie erhalten ein Auto!

1153
00:50:35,985 --> 00:50:36,670
Sie erhalten ein Auto!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID MALAN: Wir werden sehen
Sie am Mittwoch.

1155
00:50:37,970 --> 00:50:38,904
>> -Sie erhalten ein Auto!

1156
00:50:38,904 --> 00:50:39,371
Sie erhalten ein Auto!

1157
00:50:39,371 --> 00:50:40,305
Sie erhalten ein Auto!

1158
00:50:40,305 --> 00:50:41,706
Sie erhalten ein Auto!

1159
00:50:41,706 --> 00:50:43,107
Sie erhalten ein Auto!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID MALAN: Balkon Leute kommen
hier unten an der Vorderseite,

1161
00:50:45,530 --> 00:50:46,866
wo wir Extras.

1162
00:50:46,866 --> 00:50:50,282
>> -Jeder bekommt ein Auto!

1163
00:50:50,282 --> 00:50:52,234
Jeder bekommt ein Auto!

1164
00:50:52,234 --> 00:50:52,722
>> [END VIDEO PLAYBACK]

1165
00:50:52,722 --> 00:50:54,590
>> SPRECHER: Bei der nächsten CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> SPEAKER 5: Oh mein Gott Güte Güte Güte
Güte Güte Güte Güte Güte Güte -

1167
00:51:00,374 --> 00:51:02,106
>> [Ukulele gespielt]