1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Abschnitt 3 - komfortabler]

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

3
00:00:05,070 --> 00:00:07,310
>> [Dies ist CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Die erste Frage ist seltsam formuliert.

5
00:00:12,700 --> 00:00:17,480
GDB können Sie "debuggen" ein Programm, aber, genauer gesagt, was macht es können Sie tun?

6
00:00:17,480 --> 00:00:22,590
Ich werde antworten, dass ein, und ich weiß nicht, was genau erwartet,

7
00:00:22,590 --> 00:00:27,910
so ich vermute, es ist etwas entlang der Linien von ihm können Sie Schritt für Schritt

8
00:00:27,910 --> 00:00:31,540
Spaziergang durch das Programm, mit ihm interagieren, Variablen zu ändern, all diese Dinge tun -

9
00:00:31,540 --> 00:00:34,270
grundsätzlich vollständig steuern die Ausführung eines Programms

10
00:00:34,270 --> 00:00:38,410
und überprüfen Sie beliebige Teil der Ausführung des Programms.

11
00:00:38,410 --> 00:00:43,030
Also diese Funktionen können Sie debuggen Dinge.

12
00:00:43,030 --> 00:00:44,830
Okay.

13
00:00:44,830 --> 00:00:50,520
Warum binäre Suche verlangen, dass ein Array sortiert werden?

14
00:00:50,520 --> 00:00:53,360
Wer will darauf antworten?

15
00:00:56,120 --> 00:01:00,070
[Schüler] Weil es nicht funktionieren, wenn es nicht sortiert ist. >> Ja. [Gelächter]

16
00:01:00,070 --> 00:01:04,910
Wenn es nicht sortiert ist, dann ist es unmöglich, sie in zwei Hälften geteilt

17
00:01:04,910 --> 00:01:07,850
und wissen, dass alles, was auf der linken Seite ist weniger und alles auf der rechten Seite

18
00:01:07,850 --> 00:01:10,490
größer ist als der mittlere Wert.

19
00:01:10,490 --> 00:01:12,790
So ist es sortiert werden muss.

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

21
00:01:14,170 --> 00:01:17,570
Warum ist Bubble Sort in O n squared?

22
00:01:17,570 --> 00:01:23,230
Hat jemand wollen zunächst einen sehr schnellen Überblick auf hoher Ebene von dem, was Bubble Sort geben?

23
00:01:25,950 --> 00:01:33,020
[Schüler] Sie haben grundsätzlich durch jedes Element gehen und prüfen Sie die ersten paar Elemente.

24
00:01:33,020 --> 00:01:37,150
Wenn sie aus dem Sie tauschen sie sind, dann überprüfen Sie die nächsten Elemente und so weiter.

25
00:01:37,150 --> 00:01:40,770
Wenn Sie das Ende erreichen, dann wissen Sie, dass das größte Element am Ende platziert wird,

26
00:01:40,770 --> 00:01:42,750
so dass Sie ignorieren, dass ein dann los durch zu halten,

27
00:01:42,750 --> 00:01:48,490
und jedes Mal, wenn Sie zu einem weniger Element zu überprüfen, bis Sie keine Änderungen vornehmen. >> Ja.

28
00:01:48,490 --> 00:01:58,470
Es heißt bubble sort, denn wenn Sie das Array-Flip auf die Seite, sodass es bis und ab, vertikal,

29
00:01:58,470 --> 00:02:03,100
dann die großen Werte werden auf den Boden sinken und die kleinen Werte Blase bis an die Spitze.

30
00:02:03,100 --> 00:02:05,210
So ist es zu seinem Namen kam.

31
00:02:05,210 --> 00:02:08,220
Und ja, man muss nur durchlaufen.

32
00:02:08,220 --> 00:02:11,190
Sie halten durch das Array gehen, tauschen den größeren Wert

33
00:02:11,190 --> 00:02:14,040
die größten Werte auf den Grund gehen.

34
00:02:14,040 --> 00:02:17,500
>> Warum ist es O n squared?

35
00:02:18,690 --> 00:02:24,620
Zuerst hat jemand sagen wollen, warum es O n Quadrat ist?

36
00:02:24,620 --> 00:02:28,760
[Schüler] Da für jeden Durchlauf es n-mal geht.

37
00:02:28,760 --> 00:02:32,100
Sie können nur sicher sein, dass Sie genommen haben das größte Element den ganzen Weg hinunter,

38
00:02:32,100 --> 00:02:35,230
dann müssen Sie, dass für so viele Elemente wiederholen. >> Ja.

39
00:02:35,230 --> 00:02:41,800
So im Hinterkopf behalten, was große O bedeutet und welche große Omega Mittel.

40
00:02:41,800 --> 00:02:50,560
The big O ist wie die oberen, wie langsam es tatsächlich laufen gebunden.

41
00:02:50,560 --> 00:02:58,990
So dass es entweder das durch O von n quadrierten, ist es nicht von n O oder aber es wäre in der Lage zu laufen

42
00:02:58,990 --> 00:03:02,640
in linearer Zeit, aber es ist von n O cubed

43
00:03:02,640 --> 00:03:06,390
weil sie von O n cubed begrenzt.

44
00:03:06,390 --> 00:03:12,300
Wenn es durch O n squared begrenzt ist, dann ist es auch n cubed begrenzt.

45
00:03:12,300 --> 00:03:20,280
So ist es n quadriert und in der absoluten schlimmsten Fall kann es nicht besser als n squared,

46
00:03:20,280 --> 00:03:22,830
weshalb es O von n Quadrat ist.

47
00:03:22,830 --> 00:03:31,200
So leichte Mathematik, wie es kommt, dass n Quadrat zu sehen,

48
00:03:31,200 --> 00:03:40,530
wenn wir fünf Dinge in unserer Liste haben, zum ersten Mal, wie viele Swaps könnten wir möglicherweise benötigen, um

49
00:03:40,530 --> 00:03:47,170
um sich das? Lasst uns eigentlich nur -

50
00:03:47,170 --> 00:03:52,040
Wie viele Swaps werden wir gehen zu müssen, in der ersten Auflage von bubble sort durch das Array zu machen?

51
00:03:52,040 --> 00:03:53,540
[Schüler] n - 1. >> Ja.

52
00:03:53,540 --> 00:03:58,340
>> Wenn es 5 Elemente sind, wir gehen zu müssen, machen n - 1.

53
00:03:58,340 --> 00:04:01,100
Dann auf dem zweiten ein, wie viele Swaps werden wir machen müssen?

54
00:04:01,100 --> 00:04:03,440
[Schüler] n - 2. >> Ja.

55
00:04:03,440 --> 00:04:11,640
Und die dritte wird n - 3, und dann für die Bequemlichkeit ich die letzten beiden schreib

56
00:04:11,640 --> 00:04:15,270
Als dann werden wir brauchen, um 2-Swaps und 1 swap machen.

57
00:04:15,270 --> 00:04:19,899
Ich denke, das letzte kann oder auch nicht wirklich brauchen, um passieren.

58
00:04:19,899 --> 00:04:22,820
Ist es ein Swap? Ich weiß nicht.

59
00:04:22,820 --> 00:04:26,490
So sind die Gesamtbeträge der Swaps oder zumindest Vergleiche die Sie machen müssen.

60
00:04:26,490 --> 00:04:29,910
Auch wenn Sie nicht tauschen kann, müssen Sie noch die Werte vergleichen.

61
00:04:29,910 --> 00:04:33,910
So gibt es n - 1 Vergleiche in dem ersten Lauf durch den Array.

62
00:04:33,910 --> 00:04:42,050
Wenn Sie diese Dinge neu zu ordnen, lasst uns tatsächlich machen es sechs Dinge so Dinge stapeln sich schön,

63
00:04:42,050 --> 00:04:44,790
und dann werde ich tun, 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Also einfach neu anordnen diese Summen wollen wir sehen, wie viele Vergleiche machen wir

65
00:04:49,910 --> 00:04:52,700
im gesamten Algorithmus.

66
00:04:52,700 --> 00:04:56,550
Also, wenn wir bringen diese Jungs hier unten,

67
00:04:56,550 --> 00:05:07,470
dann sind wir gerade noch Summierung jedoch viele Vergleiche dort waren.

68
00:05:07,470 --> 00:05:13,280
Aber wenn wir summieren diese und fassen wir diese und fassen wir diese,

69
00:05:13,280 --> 00:05:18,130
es ist immer noch das gleiche Problem. Wir fassen diese speziellen Gruppen.

70
00:05:18,130 --> 00:05:22,400
>> So jetzt sind wir Summierung 3 n der. Es ist nicht nur 3 n der.

71
00:05:22,400 --> 00:05:27,650
Es ist immer zu n / 2 n der sein.

72
00:05:27,650 --> 00:05:29,430
Also hier haben wir gerade 6 haben.

73
00:05:29,430 --> 00:05:34,830
Wenn wir 10 Dinge hatte, dann könnten wir diese Gruppierung für 5 verschiedene Paare von Dingen zu tun

74
00:05:34,830 --> 00:05:37,180
und am Ende mit n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Sie sind also immer zu n / 2 n die zu bekommen, und so ist dies werden wir es jot aus n squared / 2.

76
00:05:45,840 --> 00:05:48,890
Und obwohl es der Faktor der Hälfte, die zu kommen passiert

77
00:05:48,890 --> 00:05:54,190
wegen der Tatsache, dass durch jede Iteration über die Anordnung es 1 weniger vergleiche

78
00:05:54,190 --> 00:05:58,040
so das ist, wie wir das über 2 bekommen, aber es ist immer noch n Quadrat.

79
00:05:58,040 --> 00:06:01,650
Wir reden nicht über den konstanten Faktor von einer halben kümmern.

80
00:06:01,650 --> 00:06:07,760
So viele große O Sachen wie diese stützt sich auf nur eine Art, dies zu tun Art von Mathematik,

81
00:06:07,760 --> 00:06:12,260
Rechnen Summen und geometrischen Reihe stuff,

82
00:06:12,260 --> 00:06:17,750
aber die meisten von ihnen in diesem Kurs sind ziemlich eindeutig.

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

84
00:06:19,290 --> 00:06:24,430
Warum ist Insertion Sort in Omega der n? Was bedeutet omega bedeuten?

85
00:06:24,430 --> 00:06:27,730
[Zwei Studenten sprechen auf einmal - unverständlich] >> Ja.

86
00:06:27,730 --> 00:06:30,630
Omega Sie können als die untere Grenze zu denken.

87
00:06:30,630 --> 00:06:36,550
>> Also egal, wie effizient Ihre Insertion Sort-Algorithmus ist,

88
00:06:36,550 --> 00:06:41,810
unabhängig von der Liste, die im vergangen ist, es muss immer mindestens n Dinge zu vergleichen

89
00:06:41,810 --> 00:06:44,620
oder es muss über n Dinge durchlaufen.

90
00:06:44,620 --> 00:06:47,280
Warum ist das so?

91
00:06:47,280 --> 00:06:51,190
[Schüler] Denn wenn die Liste bereits sortiert ist, dann durch die erste Iteration

92
00:06:51,190 --> 00:06:54,080
Sie können nur garantieren, dass das erste Element, das wenigste ist,

93
00:06:54,080 --> 00:06:56,490
und die zweite Iteration können Sie garantieren nur die ersten beiden sind

94
00:06:56,490 --> 00:07:00,010
weil Sie nicht wissen, dass der Rest der Liste sortiert ist. >> Ja.

95
00:07:00,010 --> 00:07:08,910
Wenn Sie in einem komplett sortierte Liste, passieren zumindest müssen Sie gehen über alle Elemente

96
00:07:08,910 --> 00:07:12,180
zu sehen, dass nichts zu bewegt werden.

97
00:07:12,180 --> 00:07:14,720
So Überfahren der Liste und sagen oh, dies bereits sortiert ist,

98
00:07:14,720 --> 00:07:18,240
es ist unmöglich zu wissen, es sortiert ist, bis Sie jedes Element überprüfen

99
00:07:18,240 --> 00:07:20,660
um zu sehen, dass sie in sortierter Reihenfolge sind.

100
00:07:20,660 --> 00:07:25,290
So das untere am insertion sort gebunden ist Omega von n.

101
00:07:25,290 --> 00:07:28,210
Was ist der schlimmste Fall Laufzeit von Mergesort,

102
00:07:28,210 --> 00:07:31,390
worst case ist big O wieder?

103
00:07:31,390 --> 00:07:37,660
So im schlimmsten Fall, wie kommt Mergesort laufen?

104
00:07:42,170 --> 00:07:43,690
[Schüler] N log n. >> Ja.

105
00:07:43,690 --> 00:07:49,990
Die schnellsten allgemeinen Sortieralgorithmen sind n log n. Sie können es nicht besser.

106
00:07:51,930 --> 00:07:55,130
>> Es gibt spezielle Fälle, und wenn wir Zeit haben heute - aber wir werden wahrscheinlich willst nicht -

107
00:07:55,130 --> 00:07:59,330
konnten wir sehen ein, die besser als n log n tut.

108
00:07:59,330 --> 00:08:04,050
Aber im allgemeinen Fall, können Sie nicht besser als n log n.

109
00:08:04,050 --> 00:08:09,680
Und Mergesort passiert das, das Sie für diesen Kurs, n log n wissen sollte.

110
00:08:09,680 --> 00:08:13,260
Und so werden wir tatsächlich zur Umsetzung dieser heute.

111
00:08:13,260 --> 00:08:18,070
Und schließlich, in nicht mehr als drei Sätze, wie funktioniert Auswahl Art Arbeit?

112
00:08:18,070 --> 00:08:20,370
Hat jemand beantworten wollen, und ich werde Ihre Sätze zählen

113
00:08:20,370 --> 00:08:22,390
denn wenn Sie über 3 gehen -

114
00:08:25,530 --> 00:08:28,330
Erinnert sich noch jemand Auswahl Art?

115
00:08:31,280 --> 00:08:37,809
Selection Art ist in der Regel recht einfach, nur aus dem Namen zu erinnern.

116
00:08:37,809 --> 00:08:45,350
Sie haben über das Array durchlaufen, zu finden, was der größte Wert ist oder kleinsten -

117
00:08:45,350 --> 00:08:47,290
was um Sie Sortier in.

118
00:08:47,290 --> 00:08:50,750
Also lasst uns sagen, dass wir vom kleinsten bis zum größten Sortierung.

119
00:08:50,750 --> 00:08:55,250
Sie über das Array, auf der Suche nach was auch immer das kleinste Element ist,

120
00:08:55,250 --> 00:08:59,750
wählen Sie es aus, und dann einfach tauschen Sie ihn, was in den ersten Platz.

121
00:08:59,750 --> 00:09:04,090
Und dann auf dem zweiten Durchlauf über die Anordnung, für die minimale Element noch einmal anzusehen,

122
00:09:04,090 --> 00:09:07,490
wählen Sie es aus, und dann tauschen sie mit dem, was in der zweiten Position.

123
00:09:07,490 --> 00:09:10,650
So sind wir nur Auswahlchristentum die minimalen Werte

124
00:09:10,650 --> 00:09:16,050
und Einfügen von ihnen in die vor dem Array, bis sie sortiert ist.

125
00:09:19,210 --> 00:09:21,560
Fragen dazu?

126
00:09:21,560 --> 00:09:25,710
>> Diese unvermeidlich in den Formularen, die Sie ausfüllen müssen, wenn Sie die Einreichung des pset sind angezeigt.

127
00:09:29,010 --> 00:09:32,360
Das sind im Wesentlichen die Antworten auf diese.

128
00:09:32,360 --> 00:09:34,230
Okay, jetzt Codierung Probleme.

129
00:09:34,230 --> 00:09:40,140
I already sent sich über e-mail - Hat jemand nicht bekommen, dass E-Mail? Okay.

130
00:09:40,140 --> 00:09:46,630
I already sent out über E-Mail den Raum, dass wir gehen zu verwenden,

131
00:09:46,630 --> 00:09:52,120
und wenn Sie auf meinen Namen - ich denke, ich werde auf dem Boden sein

132
00:09:52,120 --> 00:09:57,170
wegen der hinten r - aber wenn Sie auf meinen Namen sehen Sie 2 Revisionen.

133
00:09:57,170 --> 00:10:02,650
Revision 1 wird ich schon kopiert und eingefügt werden Sie den Code in Spaces

134
00:10:02,650 --> 00:10:06,900
für die Suche, was Sie gehen zu müssen, zu implementieren.

135
00:10:06,900 --> 00:10:10,540
Und Revision 2 wird die Art, was wir nach, dass umzusetzen.

136
00:10:10,540 --> 00:10:15,770
So können Sie auf meiner Revision 1 klicken und arbeiten von dort aus.

137
00:10:17,350 --> 00:10:22,060
Und jetzt wollen wir binäre Suche zu implementieren.

138
00:10:22,060 --> 00:10:26,470
>> Hat jemand will geben nur einen Pseudo-High-Level-Erklärung

139
00:10:26,470 --> 00:10:31,440
von dem, was wir gehen zu müssen, für die Suche zu tun? Yeah.

140
00:10:31,440 --> 00:10:36,170
[Schüler] Sie einfach die Mitte des Arrays und sehen, ob was Sie suchen

141
00:10:36,170 --> 00:10:38,650
ist kleiner als die oder mehr.

142
00:10:38,650 --> 00:10:41,080
Und wenn es weniger ist, müssen Sie die Hälfte, die weniger ist zu gehen,

143
00:10:41,080 --> 00:10:44,750
und wenn es mehr ist, gehen Sie zu der Hälfte, die mehr ist und Sie das wiederholen, bis bekommst du nur eine Sache.

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

145
00:10:46,570 --> 00:10:51,320
Beachten Sie, dass unsere Zahlen Array bereits sortiert ist,

146
00:10:51,320 --> 00:10:57,190
und so, dass bedeutet, dass wir das auszunutzen und wir konnten zuerst überprüfen,

147
00:10:57,190 --> 00:11:00,390
Okay, ich bin für die Nummer 50 suchen.

148
00:11:00,390 --> 00:11:03,720
So kann ich in die Mitte gehen.

149
00:11:03,720 --> 00:11:07,380
Mittelschicht ist schwer zu definieren, wenn es eine gerade Anzahl von Dingen ist,

150
00:11:07,380 --> 00:11:10,820
aber lasst uns einfach sagen, dass wir immer in der Mitte abgeschnitten.

151
00:11:10,820 --> 00:11:14,420
Also hier haben wir 8 Dinge, so in der Mitte würde 16 sein.

152
00:11:14,420 --> 00:11:17,330
Ich bin für 50 suchen, so 50 ist größer als 16 ist.

153
00:11:17,330 --> 00:11:21,310
So jetzt kann ich im Grunde behandle meine Array dieser Elemente.

154
00:11:21,310 --> 00:11:23,450
Ich kann alles wegwerfen, was aus 16 vorbei.

155
00:11:23,450 --> 00:11:27,440
Jetzt ist mein Array ist gerade diese 4 Elemente, und ich wiederhole.

156
00:11:27,440 --> 00:11:31,910
Also habe ich die Mitte wieder finden wollen, ist das werde 42 sein.

157
00:11:31,910 --> 00:11:34,730
42 weniger als 50, so kann ich wegwerfen diese beiden Elemente.

158
00:11:34,730 --> 00:11:36,890
Dies ist meine restlichen Array.

159
00:11:36,890 --> 00:11:38,430
Ich werde in der Mitte wieder zu finden.

160
00:11:38,430 --> 00:11:42,100
Ich denke, 50 war ein schlechtes Beispiel, weil ich immer wegwerfen Dinge auf der linken Seite

161
00:11:42,100 --> 00:11:48,280
aber aus dem gleichen Maß, wenn ich mich für etwas

162
00:11:48,280 --> 00:11:52,100
und es ist weniger als das Element Ich suche derzeit an,

163
00:11:52,100 --> 00:11:55,080
dann werde ich alles wegwerfen, was auf der rechten Seite.

164
00:11:55,080 --> 00:11:58,150
So, jetzt müssen wir, dass zu implementieren.

165
00:11:58,150 --> 00:12:02,310
Beachten Sie, dass wir in der Größe übergeben müssen.

166
00:12:02,310 --> 00:12:06,730
Wir können auch nicht zu hart-Code Größe benötigen.

167
00:12:06,730 --> 00:12:11,640
Wenn wir also los, dass Sie # define -

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

169
00:12:21,430 --> 00:12:27,180
Wie kann ich schön herauszufinden, was die Größe der Zahlen-Arrays aktuell ist?

170
00:12:27,180 --> 00:12:30,950
>> Wie viele Elemente sind in den Zahlen-Array?

171
00:12:30,950 --> 00:12:33,630
[Schüler] Numbers, Konsolen,. Länge?

172
00:12:33,630 --> 00:12:36,600
[Bowden], dass nicht in C existiert

173
00:12:36,600 --> 00:12:38,580
Benötigen. Länge.

174
00:12:38,580 --> 00:12:42,010
Arrays haben keine Eigenschaften, so dass es keine length-Eigenschaft des Arrays

175
00:12:42,010 --> 00:12:45,650
das wird Ihnen nur wie lange es passiert zu sein.

176
00:12:48,180 --> 00:12:51,620
[Schüler] Sehen Sie, wie viel Speicher hat und dividieren, um wie viel - >> Ja.

177
00:12:51,620 --> 00:12:55,810
Wie können wir also sehen, wie viel Speicher sie hat? >> [Schüler] Sizeof. >> Ja, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof ist der Betreiber, die gehen, um die Größe der Zahlen Array zurück ist.

179
00:13:01,680 --> 00:13:10,060
Und das wird aber viele ganze Zahlen sein gibt es Zeiten, die Größe eines Integer

180
00:13:10,060 --> 00:13:14,050
denn das ist, wie viel Speicher es ist tatsächlich die Aufnahme.

181
00:13:14,050 --> 00:13:17,630
Also, wenn ich die Anzahl der Dinge im Array möchten,

182
00:13:17,630 --> 00:13:20,560
dann bin ich gehen zu wollen, die von der Größe eines Integer teilen.

183
00:13:22,820 --> 00:13:26,010
Okay. Also das lässt mich in die grösse hier passieren.

184
00:13:26,010 --> 00:13:29,430
Warum brauche ich in der Größe überhaupt passieren?

185
00:13:29,430 --> 00:13:38,570
Warum kann ich nicht einfach tun, hier int size = sizeof (Heuhaufen) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Warum funktioniert das nicht?

187
00:13:41,490 --> 00:13:44,470
[Schüler] Es ist nicht eine globale Variable.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack existiert und wir in Zahlen vorbei, wie Heuhaufen,

189
00:13:51,540 --> 00:13:54,700
und dies ist eine Art Vorahnung von dem, was noch kommen wird. Yeah.

190
00:13:54,700 --> 00:14:00,170
[Schüler] Haystack ist nur der Verweis darauf, so wäre das Ergebnis, wie groß, dass Referenz ist.

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

192
00:14:02,150 --> 00:14:09,000
Ich bezweifle, dass in der Vorlesung, dass Sie den Stapel noch nicht wirklich, richtig gesehen?

193
00:14:09,000 --> 00:14:11,270
Wir haben gerade darüber gesprochen.

194
00:14:11,270 --> 00:14:16,090
So der Stapel ist, wo alle Ihre Variablen gehen, um gespeichert werden.

195
00:14:16,090 --> 00:14:19,960
>> Jede Erinnerung, die für lokale Variablen zugeordnet ist im Stapel gehen,

196
00:14:19,960 --> 00:14:24,790
und jede Funktion bekommt seinen eigenen Platz auf dem Stack, ist seine eigene Stack-Frame, was es heißt.

197
00:14:24,790 --> 00:14:31,590
So Haupt hat seinen Stack-Frame und nach innen von ihm wird diesen Zahlen Array vorhanden,

198
00:14:31,590 --> 00:14:34,270
und es wird von der Größe sizeof (Zahlen) sein.

199
00:14:34,270 --> 00:14:38,180
Es wird auf die Größe der Zahlen nach der Größe der Elemente unterteilt haben,

200
00:14:38,180 --> 00:14:42,010
sondern dass alle Leben in Main Stack-Frame.

201
00:14:42,010 --> 00:14:45,190
Wenn wir suchen nennen, bekommt Suche eigene Stack-Frame,

202
00:14:45,190 --> 00:14:48,840
seinen eigenen Raum zu speichern alle ihre lokalen Variablen.

203
00:14:48,840 --> 00:14:56,420
Aber diese Argumente - so Heuhaufen ist nicht eine Kopie dieser gesamte Array.

204
00:14:56,420 --> 00:15:00,990
Wir glauben nicht an das gesamte Array als Kopie Suche übergeben.

205
00:15:00,990 --> 00:15:04,030
Es ist einfach eine Referenz auf dieses Array.

206
00:15:04,030 --> 00:15:11,470
So suchen können diese Zahlen durch diesen Verweis zugreifen.

207
00:15:11,470 --> 00:15:17,100
Es ist immer noch Zugriff auf die Dinge, die in der Haupt-Stack-Frame zu leben,

208
00:15:17,100 --> 00:15:22,990
aber im Grunde, wenn wir Hinweise erhalten, sollten die bald sein,

209
00:15:22,990 --> 00:15:24,980
dies ist, was Zeiger sind.

210
00:15:24,980 --> 00:15:29,400
Zeiger sind nur Verweise auf Dinge, und Sie können Zeiger zu verwenden, um die Dinge zugreifen

211
00:15:29,400 --> 00:15:32,030
, die in anderen Dingen 'Stack-Frames.

212
00:15:32,030 --> 00:15:37,660
Also auch wenn Zahlen ist lokal zu main, können wir immer noch darauf zugreifen über diesen Zeiger.

213
00:15:37,660 --> 00:15:41,770
Aber da es nur ein Zeiger und es ist nur eine Referenz,

214
00:15:41,770 --> 00:15:45,040
sizeof (Heuhaufen) gibt nur die Größe der Referenz selbst.

215
00:15:45,040 --> 00:15:47,950
Es gibt nicht die Größe der Sache, die es zu zeigen ist.

216
00:15:47,950 --> 00:15:51,110
Es gibt nicht die tatsächliche Größe der Zahlen.

217
00:15:51,110 --> 00:15:55,660
Und so ist dies nicht zur Arbeit zu gehen, wie wir es wollen.

218
00:15:55,660 --> 00:15:57,320
>> Fragen dazu?

219
00:15:57,320 --> 00:16:03,250
Pointers werden in deutlich mehr blutigen Details werden in Wochen weg zu kommen.

220
00:16:06,750 --> 00:16:13,740
Und das ist, warum viele Dinge, die Sie sehen, die meisten suchen Dinge oder sort Dinge,

221
00:16:13,740 --> 00:16:16,990
sie fast alle gehen zu müssen, um die tatsächliche Größe des Arrays zu nehmen,

222
00:16:16,990 --> 00:16:20,440
denn in C, wir haben keine Ahnung, was die Größe des Arrays ist.

223
00:16:20,440 --> 00:16:22,720
Sie müssen manuell weitergeben in.

224
00:16:22,720 --> 00:16:27,190
Und Sie können nicht manuell in das gesamte Array durchlaufen, da Sie nur auf der Durchreise sind in der Referenzwährung

225
00:16:27,190 --> 00:16:30,390
und es kann nicht die Größe aus der Referenz.

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

227
00:16:32,300 --> 00:16:38,160
So, jetzt wollen wir das umsetzen, was erklärt wurde, vor.

228
00:16:38,160 --> 00:16:41,530
Darauf können Sie sich für eine Minute zu arbeiten,

229
00:16:41,530 --> 00:16:45,250
und Sie müssen nicht darum, alles perfekt 100% arbeiten zu kümmern.

230
00:16:45,250 --> 00:16:51,410
Schreiben Sie einfach bis die Hälfte Pseudocode, wie Sie denken, es sollte funktionieren.

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

232
00:16:53,630 --> 00:16:56,350
Keine Notwendigkeit, komplett mit dies noch getan werden.

233
00:16:56,350 --> 00:17:02,380
Aber hat jemand wohl fühlen mit dem, was sie bisher,

234
00:17:02,380 --> 00:17:05,599
wie etwas können wir mit zusammen?

235
00:17:05,599 --> 00:17:09,690
Will jemand sich freiwillig? Oder ich werde nach dem Zufallsprinzip auswählen.

236
00:17:12,680 --> 00:17:18,599
Es muss nicht nach rechts durch eine Maßnahme, sondern etwas, das wir in einen funktionierenden Zustand zu ändern können.

237
00:17:18,599 --> 00:17:20,720
[Schüler] Sure. >> Okay.

238
00:17:20,720 --> 00:17:27,220
So können Sie die Revision durch Klick auf das kleine Symbol Speichern.

239
00:17:27,220 --> 00:17:29,950
Du bist Ramya, nicht wahr? >> [Schüler] Yeah. >> [Bowden] Okay.

240
00:17:29,950 --> 00:17:35,140
So jetzt kann ich sehen Sie Ihre Revision und jeder kann nach oben ziehen die Revision.

241
00:17:35,140 --> 00:17:38,600
Und hier haben wir - Okay.

242
00:17:38,600 --> 00:17:43,160
So Ramya ging mit der rekursive Lösung, das ist definitiv eine gültige Lösung.

243
00:17:43,160 --> 00:17:44,970
Es gibt zwei Möglichkeiten, wie Sie dieses Problem tun kann.

244
00:17:44,970 --> 00:17:48,060
Sie können es entweder iterativ oder rekursiv.

245
00:17:48,060 --> 00:17:53,860
Die meisten Probleme, die das kann rekursiv geschehen kann auch iterativ erfolgen.

246
00:17:53,860 --> 00:17:58,510
Also hier haben wir es geschafft rekursiv.

247
00:17:58,510 --> 00:18:03,730
>> Hat jemand wollen definieren, was es zu machen eine Funktion rekursiv bedeutet?

248
00:18:07,210 --> 00:18:08,920
[Schüler] Wenn Sie eine Funktion haben, nennt sich

249
00:18:08,920 --> 00:18:13,470
und rufen Sie dann selbst, bis es aus mit echten und wahren. >> Ja.

250
00:18:13,470 --> 00:18:17,680
Eine rekursive Funktion ist nur eine Funktion, die sich selbst aufruft.

251
00:18:17,680 --> 00:18:24,140
Es gibt drei große Dinge, die eine rekursive Funktion haben muss.

252
00:18:24,140 --> 00:18:27,310
Die erste ist offensichtlich, nennt es sich.

253
00:18:27,310 --> 00:18:29,650
Die zweite ist die Base-Case.

254
00:18:29,650 --> 00:18:33,390
So an einem gewissen Punkt die Funktion muss aufhören, sich selbst,

255
00:18:33,390 --> 00:18:35,610
und das ist, was die Base-Case ist für.

256
00:18:35,610 --> 00:18:43,860
Also hier wissen wir, dass wir aufhören sollten, sollten wir in unserer Suche

257
00:18:43,860 --> 00:18:48,150
bei Beginn Ende gleich - und wir gehen über das, was das bedeutet.

258
00:18:48,150 --> 00:18:52,130
Aber schließlich, die letzte Sache, die wichtig für rekursive Funktionen ist:

259
00:18:52,130 --> 00:18:59,250
Die Funktionen müssen irgendwie nähern sich dem Basisfall.

260
00:18:59,250 --> 00:19:04,140
Wie, wenn du nicht wirklich aktualisiert nichts, wenn Sie den zweiten rekursiven Aufruf zu machen,

261
00:19:04,140 --> 00:19:07,880
wenn Sie buchstäblich nur den Aufruf der Funktion wieder mit den gleichen Argumenten

262
00:19:07,880 --> 00:19:10,130
und keine globalen Variablen geändert haben oder so etwas,

263
00:19:10,130 --> 00:19:14,430
Sie erreichen nie die Base-Case, in welchem ​​Fall das ist schlecht.

264
00:19:14,430 --> 00:19:17,950
Es wird eine unendliche Rekursion und ein Stack-Überlauf sein.

265
00:19:17,950 --> 00:19:24,330
Aber hier sehen wir, dass das Update geschieht, da wir die Aktualisierung beginnen, werden + Ende / 2,

266
00:19:24,330 --> 00:19:28,180
wir aktualisieren das Ende Argument hier, wir aktualisieren die Start-Argument hier.

267
00:19:28,180 --> 00:19:32,860
So in allen rekursiven Aufrufen aktualisieren wir etwas. Okay.

268
00:19:32,860 --> 00:19:38,110
Wollen Sie uns durch Ihre Lösung gehen? >> Sure.

269
00:19:38,110 --> 00:19:44,270
Ich bin mit SearchHelp, so dass jedes Mal wenn ich diese Funktion Anruf

270
00:19:44,270 --> 00:19:47,910
Ich habe den Start, wo ich in dem Array suchen und das Ende

271
00:19:47,910 --> 00:19:49,380
wo ich freue mich auf das Array.

272
00:19:49,380 --> 00:19:55,330
>> Bei jedem Schritt, wo es zu sagen, es ist das mittlere Element, das Start ist + Ende / 2 ist,

273
00:19:55,330 --> 00:19:58,850
ist, dass gleich was wir suchen?

274
00:19:58,850 --> 00:20:04,650
Und wenn ja, dann fanden wir es, und ich denke, das wird sich die Ebenen der Rekursion übergeben.

275
00:20:04,650 --> 00:20:12,540
Und wenn das nicht wahr ist, dann werden wir prüfen, ob es mittleren Wert des Arrays zu groß ist,

276
00:20:12,540 --> 00:20:19,320
In diesem Fall betrachten wir die linke Hälfte des Feldes, indem Sie von Anfang bis Mitte index.

277
00:20:19,320 --> 00:20:22,710
Und sonst tun wir das Ende Hälfte.

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

279
00:20:24,740 --> 00:20:27,730
Das hört sich gut an.

280
00:20:27,730 --> 00:20:36,640
Okay, so ein paar Dinge, und tatsächlich ist dies ein sehr hohem Niveau, was

281
00:20:36,640 --> 00:20:41,270
dass Sie nie brauchen, um für diesen Kurs wissen, aber es ist wahr.

282
00:20:41,270 --> 00:20:46,080
Rekursive Funktionen, hört man immer, dass sie ein schlechtes Geschäft sind

283
00:20:46,080 --> 00:20:51,160
denn wenn man rekursiv nennen sich zu oft, erhalten Sie Stack-Überlauf

284
00:20:51,160 --> 00:20:54,990
denn, wie ich schon sagte, bekommt jeder Funktion eine eigene Stack-Frame.

285
00:20:54,990 --> 00:20:59,500
So dass jeder Aufruf der rekursiven Funktion bekommt seinen eigenen Stack-Frame.

286
00:20:59,500 --> 00:21:04,140
Also, wenn Sie 1.000 rekursive Anrufe tätigen, erhalten Sie 1.000 Stack-Frames,

287
00:21:04,140 --> 00:21:08,390
und schnell Sie zu viele Stack-Frames und die Dinge einfach zu brechen führen.

288
00:21:08,390 --> 00:21:13,480
Also das ist, warum rekursive Funktionen in der Regel schlecht sind.

289
00:21:13,480 --> 00:21:19,370
Aber es ist ein schöner Teil der rekursive Funktionen aufgerufen tail-rekursive Funktionen,

290
00:21:19,370 --> 00:21:26,120
und dies geschieht, ein Beispiel für eine, wo, wenn der Kompilierer bemerkt dies

291
00:21:26,120 --> 00:21:29,920
und es sollte, denke ich - in Clang wenn Sie weitergeben the-O2-Flag

292
00:21:29,920 --> 00:21:33,250
dann wird es bemerken, ist dies endrekursiv und die Dinge gut.

293
00:21:33,250 --> 00:21:40,050
>> Es wird Wiederverwendung der gleichen Stapelrahmen immer wieder für jeden rekursiven Aufruf.

294
00:21:40,050 --> 00:21:47,010
Und so, da Sie mit dem gleichen Stack-Frame sind, brauchen Sie keine Sorgen zu machen

295
00:21:47,010 --> 00:21:51,690
immer stapeln überfüllt, und zur gleichen Zeit, wie Sie vorhin sagten,

296
00:21:51,690 --> 00:21:56,380
wo, wenn Sie true zurückgeben, dann muss es zurück bis alle diese Stack-Frames

297
00:21:56,380 --> 00:22:01,740
und die 10. Aufruf SearchHelp muss dem neunten zurückzukehren, muss dem achten zurückzukehren.

298
00:22:01,740 --> 00:22:05,360
Also das muss nicht passieren, wenn Funktionen endrekursiv sind.

299
00:22:05,360 --> 00:22:13,740
Und so was macht diese Funktion endrekursiv ist bekannt, dass für einen bestimmten Aufruf SearchHelp

300
00:22:13,740 --> 00:22:18,470
der rekursive Aufruf, dass es macht, was es ist zurück.

301
00:22:18,470 --> 00:22:25,290
So in dem ersten Aufruf SearchHelp wir entweder sofort false zurück,

302
00:22:25,290 --> 00:22:29,590
sofort wieder wahr, oder wir machen eine rekursive Aufruf SearchHelp

303
00:22:29,590 --> 00:22:33,810
wo das, was wir wieder ist, was das Gespräch wird zurückkehren.

304
00:22:33,810 --> 00:22:51,560
Und wir konnten das nicht tun, wenn wir so etwas wie int x = SearchHelp, return x * 2 tat,

305
00:22:51,560 --> 00:22:55,440
nur einige zufällige Veränderung.

306
00:22:55,440 --> 00:23:01,470
>> So jetzt dieses rekursiven Aufruf, diese int x = SearchHelp rekursiven Aufruf,

307
00:23:01,470 --> 00:23:05,740
ist nicht mehr endrekursiv, weil es tatsächlich zur Rücksendung haben

308
00:23:05,740 --> 00:23:10,400
zurück zu einer früheren Stapelrahmen so dass diese vorherigen Aufruf der Funktion

309
00:23:10,400 --> 00:23:13,040
kann dann etwas mit dem Rückgabewert.

310
00:23:13,040 --> 00:23:22,190
Das ist also nicht endrekursiv, aber was wir vorher hatten ist schön endrekursiv. Yeah.

311
00:23:22,190 --> 00:23:27,000
[Schüler] Sollte nicht das zweite Base Case zunächst überprüft werden

312
00:23:27,000 --> 00:23:30,640
weil es könnte eine Situation sein, wo, wenn Sie es das Argument übergeben

313
00:23:30,640 --> 00:23:35,770
Sie start = Ende, aber sie sind die Nadel Wert.

314
00:23:35,770 --> 00:23:47,310
Die Frage wurde können wir nicht in die Falle laufen, wo Ende ist die Nadel-Wert

315
00:23:47,310 --> 00:23:52,000
oder starten = Ende, angemessen, start = Ende

316
00:23:52,000 --> 00:23:59,480
und Sie haben nicht wirklich, dass die besonderen Wert überprüft noch,

317
00:23:59,480 --> 00:24:03,910
dann starten + Ende / 2 ist gerade dabei, den gleichen Wert.

318
00:24:03,910 --> 00:24:07,890
Aber wir haben schon wieder falsch und wir eigentlich nie den Wert überprüft.

319
00:24:07,890 --> 00:24:14,240
So zumindest in dem ersten Aufruf, wenn die Größe 0 ist, dann wollen wir false zurück.

320
00:24:14,240 --> 00:24:17,710
Aber wenn Größe 1 ist, dann Start wird nicht gleich Ende

321
00:24:17,710 --> 00:24:19,820
und wir zumindest überprüfen die ein Element.

322
00:24:19,820 --> 00:24:26,750
Aber ich glaube, Sie haben Recht, dass wir am Ende in einem Fall, wo + Ende / 2 starten,

323
00:24:26,750 --> 00:24:31,190
Start landet das gleiche wie Start + Ende / 2,

324
00:24:31,190 --> 00:24:35,350
aber wir nie wirklich das Element überprüft.

325
00:24:35,350 --> 00:24:44,740
>> Also, wenn wir zuerst überprüfen, ist das mittlere Element der Wert, die wir suchen,

326
00:24:44,740 --> 00:24:47,110
dann können wir sofort wieder wahr.

327
00:24:47,110 --> 00:24:50,740
Else, wenn sie gleich sind, dann hat es keinen Sinn in der Weiterbildung

328
00:24:50,740 --> 00:24:58,440
da wir gerade dabei, in einem Fall, wo wir sind auf einer Single-Element-Array zu aktualisieren.

329
00:24:58,440 --> 00:25:01,110
Wenn das einzelne Element ist nicht das, was wir suchen,

330
00:25:01,110 --> 00:25:03,530
dann ist alles falsch. Yeah.

331
00:25:03,530 --> 00:25:08,900
[Schüler] Die Sache ist, dass, da Größe ist tatsächlich größer als die Anzahl der Elemente in dem Array,

332
00:25:08,900 --> 00:25:13,070
gibt es bereits ein Offset - >> So wird Größe -

333
00:25:13,070 --> 00:25:19,380
[Student] Sprich, wenn das Array war Größe 0, dann ist die SearchHelp tatsächlich überprüfen Heuhaufen 0

334
00:25:19,380 --> 00:25:21,490
beim ersten Anruf.

335
00:25:21,490 --> 00:25:25,300
Das Array hat die Größe 0, so dass die 0 ist - >> Ja.

336
00:25:25,300 --> 00:25:30,750
Es ist eine andere Sache, dass - es könnte gut sein. Lasst uns denken.

337
00:25:30,750 --> 00:25:40,120
Also, wenn das Array mit 10 Elementen und in der Mitte ein wir überprüfen, sind die Index-5,

338
00:25:40,120 --> 00:25:45,700
so dass wir die Überprüfung 5, und sagen wir, dass der Wert geringer ist.

339
00:25:45,700 --> 00:25:50,720
So wir werfen alles weg 5 weiter.

340
00:25:50,720 --> 00:25:54,030
So starten + Ende / 2 wird unsere neue Ende,

341
00:25:54,030 --> 00:25:57,450
so yeah, es ist immer zu über das Ende des Arrays bleiben.

342
00:25:57,450 --> 00:26:03,570
Wenn es eine Falle ist, wenn es gerade oder ungerade war, dann würden wir überprüfen, sagen, 4,

343
00:26:03,570 --> 00:26:05,770
aber wir sind immer noch wegwerfen -

344
00:26:05,770 --> 00:26:13,500
Also ja, ist das Ende immer zu über das eigentliche Ende des Arrays sein.

345
00:26:13,500 --> 00:26:18,350
So die Elemente konzentrieren wir uns auf, wird Ende immer zu der ein danach.

346
00:26:18,350 --> 00:26:24,270
Und so, wenn startet immer gleich Ende, wir sind in einem Array der Größe 0.

347
00:26:24,270 --> 00:26:35,600
>> Die andere Sache, die ich dachte, ist, dass wir die Aktualisierung Start zu Start + Ende / 2,

348
00:26:35,600 --> 00:26:44,020
so ist dies der Fall, dass ich Probleme mit, wo + Ende / 2 beginnen

349
00:26:44,020 --> 00:26:46,820
ist das Element, wir überprüfen.

350
00:26:46,820 --> 00:26:58,150
Sagen wir, wir hatten diese 10-Element-Array. Wie auch immer.

351
00:26:58,150 --> 00:27:03,250
So starten + Ende / 2 wird so etwas wie dieses sein,

352
00:27:03,250 --> 00:27:07,060
und wenn das nicht der Wert, sagen wir aktualisieren möchten.

353
00:27:07,060 --> 00:27:10,060
Der Wert ist größer, so wollen wir an dieser Hälfte des Array.

354
00:27:10,060 --> 00:27:15,910
So wie wir die Aktualisierung starten, wir aktualisieren Start nun dieses Element sein.

355
00:27:15,910 --> 00:27:23,790
Aber das kann noch arbeiten, oder zumindest, können Sie beginnen zu tun + Ende / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Schüler] Sie brauchen nicht zu + Ende beginnen [unverständlich] >> Ja.

357
00:27:27,850 --> 00:27:33,240
Wir haben bereits dieses Element geprüft und weiß, es ist nicht das, was wir suchen.

358
00:27:33,240 --> 00:27:36,800
So brauchen wir nicht, um den Start zu aktualisieren, um dieses Element zu sein.

359
00:27:36,800 --> 00:27:39,560
Wir können es gerade auslässt und zu aktualisieren beginnen dieses Element sein.

360
00:27:39,560 --> 00:27:46,060
Und gibt es überhaupt ein Fall, sagen wir mal, dass dieses Ende waren,

361
00:27:46,060 --> 00:27:53,140
so starten Sie dann wäre dies, starten + Ende / 2 wäre dies,

362
00:27:53,140 --> 00:28:00,580
Start + Ende - Ja, ich denke, es kann am Ende in Endlosschleife.

363
00:28:00,580 --> 00:28:12,690
Lassen Sie uns sagen, es ist nur ein Array der Größe 2 oder ein Array der Größe 1. Ich denke, das wird funktionieren.

364
00:28:12,690 --> 00:28:19,490
So aktuell ist Anfang dieses Element und am Ende ein dahinter ist.

365
00:28:19,490 --> 00:28:24,110
So das Element, dass wir gehen, um zu überprüfen ist dies ein,

366
00:28:24,110 --> 00:28:29,400
und dann, wenn wir Update starten, wir aktualisieren Start in 0 + 1/2 sein,

367
00:28:29,400 --> 00:28:33,160
was wird uns am Ende wieder mit Beginn ist dieses Element.

368
00:28:33,160 --> 00:28:36,210
>> Also werden wir prüfen das gleiche Element immer und immer wieder.

369
00:28:36,210 --> 00:28:43,310
So dies der Fall ist, wo jeder rekursive Aufruf tatsächlich aktualisieren muss etwas.

370
00:28:43,310 --> 00:28:48,370
Also müssen wir, um den Start + Ende / 2 + 1, sonst tun es ist ein Fall

371
00:28:48,370 --> 00:28:50,710
wo wir eigentlich nicht die Aktualisierung starten.

372
00:28:50,710 --> 00:28:53,820
Jeder sehen?

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

374
00:28:56,310 --> 00:29:03,860
Hat jemand Fragen zu dieser Lösung oder mehr Kommentare?

375
00:29:05,220 --> 00:29:10,280
Okay. Hat jemand eine iterative Lösung, dass wir alle sehen?

376
00:29:17,400 --> 00:29:20,940
Haben wir alle tun es rekursiv?

377
00:29:20,940 --> 00:29:25,950
Oder auch ich denke, wenn man ihr eröffnet, dann haben Sie vielleicht überschrieben Ihrer vorherigen.

378
00:29:25,950 --> 00:29:28,810
Ist es automatisch zu speichern? Ich bin nicht positiv.

379
00:29:35,090 --> 00:29:39,130
Hat jemand iterativen?

380
00:29:39,130 --> 00:29:42,430
Wir können durch sie gehen zusammen, wenn nicht.

381
00:29:46,080 --> 00:29:48,100
Die Idee wird die gleiche sein.

382
00:30:00,260 --> 00:30:02,830
Iterative Lösung.

383
00:30:02,830 --> 00:30:07,140
Wir gehen zu wollen, im Grunde tun die gleiche Idee

384
00:30:07,140 --> 00:30:16,530
wo wir wollen den Überblick über das neue Ende des Arrays und den Neubeginn des Arrays zu halten

385
00:30:16,530 --> 00:30:18,510
und das tun immer und immer wieder.

386
00:30:18,510 --> 00:30:22,430
Und wenn das, was wir als die Verfolgung von Anfang und Ende je kreuzen,

387
00:30:22,430 --> 00:30:29,020
dann haben wir es nicht finden, und wir können false zurück.

388
00:30:29,020 --> 00:30:37,540
Also, wie kann ich das tun? Wer noch Anregungen oder Code für mich nach oben zu ziehen?

389
00:30:42,190 --> 00:30:47,450
[Schüler] Führen Sie eine while-Schleife. >> Ja.

390
00:30:47,450 --> 00:30:49,450
Sie gehen zu wollen, um eine Schleife zu tun.

391
00:30:49,450 --> 00:30:51,830
>> Haben Sie Code konnte ich nach oben ziehen, oder was wolltest du vorschlagen?

392
00:30:51,830 --> 00:30:56,340
[Schüler] Ich denke schon. >> Alles klar. Das macht die Sache einfacher. Was war Ihr Name?

393
00:30:56,340 --> 00:30:57,890
[Schüler] Lucas.

394
00:31:00,140 --> 00:31:04,190
Revision 1. Okay.

395
00:31:04,190 --> 00:31:13,200
Niedrig ist, was wir beginnen, bevor genannt.

396
00:31:13,200 --> 00:31:17,080
Up ist nicht ganz das, was wir am Ende als zuvor.

397
00:31:17,080 --> 00:31:22,750
Eigentlich ist Ende nun innerhalb des Arrays. Es ist ein Element, das wir berücksichtigen sollten.

398
00:31:22,750 --> 00:31:26,890
So niedrig ist 0, bis die Größe des Arrays - 1,

399
00:31:26,890 --> 00:31:34,780
und jetzt sind wir eine Schleife, und wir werden prüfen -

400
00:31:34,780 --> 00:31:37,340
Ich denke, man kann durch sie hindurchgehen.

401
00:31:37,340 --> 00:31:41,420
Was war Ihr Denken durch das? Gehen Sie uns durch Ihren Code.

402
00:31:41,420 --> 00:31:49,940
[Schüler] Sure. Schauen Sie sich die Heuhaufen Wert in der Mitte und vergleichen Sie es mit Nadel.

403
00:31:49,940 --> 00:31:58,520
Also, wenn es größer als die Nadel ist, dann wollen Sie - oh, tatsächlich, das sollte rückwärts.

404
00:31:58,520 --> 00:32:05,180
Sie gehen zu wollen, werfen die rechte Hälfte, und so ja, das sollte der Weg sein.

405
00:32:05,180 --> 00:32:08,830
[Bowden] So sollte dies weniger? Ist das, was du gesagt hast? >> [Schüler] Yeah.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Okay. Weniger.

407
00:32:10,390 --> 00:32:15,700
Also, wenn das, was wir suchen, ist kleiner als das, was wir wollen,

408
00:32:15,700 --> 00:32:19,410
dann ja, wollen wir wegwerfen die linke Hälfte,

409
00:32:19,410 --> 00:32:22,210
was bedeutet, wir aktualisieren alles, was wir erwägen

410
00:32:22,210 --> 00:32:26,610
durch Bewegen günstig rechts von der Anordnung.

411
00:32:26,610 --> 00:32:30,130
Das sieht gut aus.

412
00:32:30,130 --> 00:32:34,550
Ich denke, es hat das gleiche Problem, dass wir auf dem vorherigen sagte

413
00:32:34,550 --> 00:32:49,760
wo, wenn niedrig ist 0 und bis 1 ist, dann low + up / 2 wird eingerichtet, um die gleiche Sache wieder.

414
00:32:49,760 --> 00:32:53,860
>> Und selbst wenn das nicht der Fall ist, ist es noch effizienter zumindest

415
00:32:53,860 --> 00:32:57,630
nur wegwerfen das Element wir sahen, an dem wir wissen, ist falsch.

416
00:32:57,630 --> 00:33:03,240
So low + up / 2 + 1 - >> [Schüler] Das sollte das anders sein.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Oder diese sollte - 1 und der andere sollte + 1 sein.

418
00:33:05,900 --> 00:33:09,580
[Schüler] Und es sollte eine doppelte sein Gleichheitszeichen. >> [Bowden] Yeah.

419
00:33:09,580 --> 00:33:11,340
[Schüler] Yeah.

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

421
00:33:15,910 --> 00:33:21,280
Und schließlich, jetzt, da wir dieses + 1 - 1 Sache,

422
00:33:21,280 --> 00:33:31,520
ist es - könnte es nicht sein - ist es überhaupt möglich für niedrige bis zum Ende mit einem Wert größer als up?

423
00:33:35,710 --> 00:33:40,320
Ich denke, der einzige Weg, die passieren können - Ist es möglich? >> [Schüler] Ich weiß es nicht.

424
00:33:40,320 --> 00:33:45,220
Aber wenn er abgeschnitten wird und dann bekommt minus dass 1 und dann - >> Ja.

425
00:33:45,220 --> 00:33:47,480
[Schüler] Es wäre möglicherweise durcheinander.

426
00:33:49,700 --> 00:33:53,940
Ich denke, es sollte gut sein, nur weil

427
00:33:53,940 --> 00:33:58,800
für sie enden bis unteren müssten sie gleich sein, denke ich.

428
00:33:58,800 --> 00:34:03,070
Aber wenn sie gleich sind, dann würden wir nicht die while-Schleife zu beginnen getan haben

429
00:34:03,070 --> 00:34:06,670
und wir würden den Wert zurückgekehrt. Also ich denke, wir sind jetzt gut.

430
00:34:06,670 --> 00:34:11,530
Beachten Sie, dass, obwohl dieses Problem ist nicht mehr rekursiv,

431
00:34:11,530 --> 00:34:17,400
die gleiche Art von Ideen gelten, wo wir sehen können, wie diese so leicht eignet sich

432
00:34:17,400 --> 00:34:23,659
eine rekursive Lösung durch die Tatsache, dass wir nur die Aktualisierung der Indizes immer und immer wieder,

433
00:34:23,659 --> 00:34:29,960
wir machen das Problem kleiner, sind wir auf eine Teilmenge des Arrays konzentrieren.

434
00:34:29,960 --> 00:34:40,860
[Schüler] Wenn niedrig ist 0 und bis 1 ist, würden sie beide 0 + 1/2, die auf 0 gehen würde,

435
00:34:40,860 --> 00:34:44,429
und dann würde + 1 sein, würde man - 1.

436
00:34:47,000 --> 00:34:50,870
[Student] Wo werden wir die Überprüfung Gleichheit?

437
00:34:50,870 --> 00:34:55,100
Wie, wenn die mittlere ist eigentlich Nadel?

438
00:34:55,100 --> 00:34:58,590
Wir sind nicht gerade tun? Oh!

439
00:35:00,610 --> 00:35:02,460
Wenn es ist -

440
00:35:05,340 --> 00:35:13,740
Ja. Wir können nicht einfach machen Sie den Test hier unten, weil wir die ersten mittleren sagen -

441
00:35:13,740 --> 00:35:16,430
[Schüler] Es ist eigentlich wie nicht wegwerfen gebunden.

442
00:35:16,430 --> 00:35:20,220
Also, wenn Sie entfernt das gebundene, müssen Sie es zuerst oder was auch immer.

443
00:35:20,220 --> 00:35:23,350
Ah. Yeah. >> [Schüler] Yeah.

444
00:35:23,350 --> 00:35:29,650
So, jetzt haben wir entfernt die, die wir derzeit sah geworfen,

445
00:35:29,650 --> 00:35:33,260
das heißt, wir müssen jetzt auch

446
00:35:33,260 --> 00:35:44,810
if (haystack [(low + up) / 2] == Nadel), dann können wir wieder wahr.

447
00:35:44,810 --> 00:35:52,070
Und ob ich sonst oder nur, wenn ausgedrückt, bedeutet es wörtlich dasselbe

448
00:35:52,070 --> 00:35:57,110
denn dies würde true zurückgegeben haben.

449
00:35:57,110 --> 00:36:01,450
Also werde ich andere zu stellen, wenn, aber es spielt keine Rolle.

450
00:36:01,450 --> 00:36:10,440
>> So else if diesem, sonst dieses, und das ist eine gemeinsame Sache, die ich tun

451
00:36:10,440 --> 00:36:14,340
wo auch wenn es der Fall, wo alles ist gut hier,

452
00:36:14,340 --> 00:36:22,780
wie niedrige nie sein kann größer als oben, ist es nicht wert Argumentation darüber, ob das wahr ist.

453
00:36:22,780 --> 00:36:28,010
So können Sie genauso gut sagen, während niedrig ist kleiner oder gleich

454
00:36:28,010 --> 00:36:30,720
oder während niedrig ist weniger als

455
00:36:30,720 --> 00:36:35,300
so dass, wenn sie jemals gleich oder niedriger sind passiert zu passieren,

456
00:36:35,300 --> 00:36:40,130
dann können wir brechen aus dieser Schleife.

457
00:36:41,410 --> 00:36:44,630
Fragen, Anliegen, Anregungen?

458
00:36:47,080 --> 00:36:49,270
Okay. Das sieht gut aus.

459
00:36:49,270 --> 00:36:52,230
Jetzt wollen wir dergleichen zu tun.

460
00:36:52,230 --> 00:37:04,030
Wenn wir zu meinem zweiten Revision gehen, sehen wir die gleichen Zahlen,

461
00:37:04,030 --> 00:37:07,550
aber jetzt sind sie nicht mehr in sortierter Reihenfolge.

462
00:37:07,550 --> 00:37:12,840
Und wir wollen sort Umsetzung mit einem beliebigen Algorithmus in O n log n.

463
00:37:12,840 --> 00:37:17,240
So, welcher Algorithmus denkst du, wir sollten hier zu implementieren? >> [Schüler] Merge sort.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Yeah. Mergesort ist O (n log n), so dass das, was wir tun werden.

465
00:37:23,810 --> 00:37:26,680
Und das Problem wird sich ziemlich ähnlich,

466
00:37:26,680 --> 00:37:31,920
wo es leicht eignet sich für eine rekursive Lösung.

467
00:37:31,920 --> 00:37:35,580
Wir können auch kommen mit einem iterativen Lösung, wenn wir wollen,

468
00:37:35,580 --> 00:37:42,540
aber Rekursion wird einfacher sein hier, und wir sollten Rekursion zu tun.

469
00:37:45,120 --> 00:37:49,530
Ich denke, wir werden durch Mergesort erste gehen,

470
00:37:49,530 --> 00:37:54,280
obwohl es eine schöne Video-on-Mergesort bereits. [Gelächter]

471
00:37:54,280 --> 00:37:59,780
So Mergesort gibt es - ich bin es leid verschwenden so viel von diesem Papier.

472
00:37:59,780 --> 00:38:02,080
Oh, es gibt nur eine links.

473
00:38:02,080 --> 00:38:03,630
So verschmelzen.

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

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

476
00:38:29,910 --> 00:38:33,460
Merge dauert zwei separate Arrays.

477
00:38:33,460 --> 00:38:36,780
Individuell diese beiden Arrays werden sowohl sortiert.

478
00:38:36,780 --> 00:38:40,970
So dieses Array, 1, 3, 5, sortiert. Dieses Array, 0, 2, 4, sortiert.

479
00:38:40,970 --> 00:38:46,710
Nun, was merge tun sollten, ist zu kombinieren sie zu einem einzigen Array, das sich von selbst geregelt ist.

480
00:38:46,710 --> 00:38:57,130
So wollen wir ein Array der Größe 6, die gehen, um diese Elemente im Inneren lassen will

481
00:38:57,130 --> 00:38:59,390
in sortierter Reihenfolge.

482
00:38:59,390 --> 00:39:03,390
>> Und so können wir die Tatsache zunutze, dass diese beiden Arrays sortiert nehmen

483
00:39:03,390 --> 00:39:06,800
dies in linearer Zeit zu tun,

484
00:39:06,800 --> 00:39:13,510
linearer Zeit Sinn, wenn diese Anordnung ist die Größe x, und dies ist die Größe y,

485
00:39:13,510 --> 00:39:20,970
dann ist der gesamte Algorithmus sollte O (x + y) sein. Okay.

486
00:39:20,970 --> 00:39:23,150
So Vorschläge.

487
00:39:23,150 --> 00:39:26,030
[Schüler] Könnten wir von links beginnen?

488
00:39:26,030 --> 00:39:30,150
So finden Sie die 0 zuerst hinunter und dann die 1 gesetzt und dann hier bist du an der 2.

489
00:39:30,150 --> 00:39:33,320
Also ist es eine Art, wie Sie eine Registerkarte, die nach rechts bewegt hat. >> [Bowden] Yeah.

490
00:39:33,320 --> 00:39:41,070
Für diese beiden Arrays wenn wir nur auf der äußersten linken Element fokussieren.

491
00:39:41,070 --> 00:39:43,530
Da beide Arrays sortiert sind, wissen wir, dass diese 2 Elemente

492
00:39:43,530 --> 00:39:46,920
sind die kleinsten Elemente in jedem Array.

493
00:39:46,920 --> 00:39:53,500
Das heißt also, dass 1 dieser 2 Elemente müssen das kleinste Element in unserer fusionierten Array sein.

494
00:39:53,500 --> 00:39:58,190
Es passiert einfach so, dass die kleinste der auf der rechten Seite dieser Zeit ist.

495
00:39:58,190 --> 00:40:02,580
Also nehmen wir 0, legen Sie sie auf der linken, da 0 kleiner als 1,

496
00:40:02,580 --> 00:40:08,210
so nehmen 0, legen Sie sie in unserer ersten Position, und dann aktualisieren wir diese

497
00:40:08,210 --> 00:40:12,070
Bisher auf dem ersten Element zu konzentrieren.

498
00:40:12,070 --> 00:40:14,570
Und jetzt haben wir wiederholen.

499
00:40:14,570 --> 00:40:20,670
So, jetzt vergleichen wir 2 und 1. 1 kleiner, so dass wir 1 einzufügen.

500
00:40:20,670 --> 00:40:25,300
Wir aktualisieren diese Zeiger auf diesen Kerl zu zeigen.

501
00:40:25,300 --> 00:40:33,160
Jetzt haben wir es wieder tun, so 2. Dies wird zu aktualisieren, zu vergleichen diese 2, 3.

502
00:40:33,160 --> 00:40:37,770
Diese Updates, dann 4 und 5.

503
00:40:37,770 --> 00:40:42,110
So das ist fusionieren.

504
00:40:42,110 --> 00:40:49,010
>> Es sollte ziemlich offensichtlich, dass es die lineare Zeit ist, da wir über jedes Element nur einmal gehen.

505
00:40:49,010 --> 00:40:55,980
Und das ist der größte Schritt zur Umsetzung Mergesort ist, dies zu tun.

506
00:40:55,980 --> 00:40:59,330
Und es ist nicht so schwer.

507
00:40:59,330 --> 00:41:15,020
Ein paar Dinge zu kümmern ist sagen wir, wir wurden Zusammenlegung 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
In diesem Fall werden wir am Ende in dem Fall, wenn diese eine werde kleiner sein wird,

509
00:41:30,930 --> 00:41:36,160
dann werden wir diesen Zeiger zu aktualisieren, dieser wird kleiner sein, aktualisieren Sie diese,

510
00:41:36,160 --> 00:41:41,280
dieses ist kleiner, und jetzt haben Sie zu erkennen,

511
00:41:41,280 --> 00:41:44,220
wenn man eigentlich laufen aus Elementen zu vergleichen mit.

512
00:41:44,220 --> 00:41:49,400
Da haben wir schon das gesamte Array verwendet,

513
00:41:49,400 --> 00:41:55,190
alles in diesem Array ist nun gerade in hier eingefügt.

514
00:41:55,190 --> 00:42:02,040
Also, wenn wir jemals in dem Punkt, wo einer unserer Arrays komplett zusammengeführt wird bereits ausgeführt,

515
00:42:02,040 --> 00:42:06,510
dann haben wir nur nehmen alle Elemente der anderen Anordnung und legen Sie sie in das Ende des Arrays.

516
00:42:06,510 --> 00:42:13,630
So können wir einfach legen Sie 4, 5, 6. Okay.

517
00:42:13,630 --> 00:42:18,070
Das ist eine Sache, die Sie achten sollten.

518
00:42:22,080 --> 00:42:26,120
Umsetzung das sollte Schritt 1 sein.

519
00:42:26,120 --> 00:42:32,600
Merge dann sortieren basierend auf, dass es 2 Stufen, 2 dumme Schritte.

520
00:42:38,800 --> 00:42:42,090
Lasst uns einfach geben diesem Array.

521
00:42:57,920 --> 00:43:05,680
So Mergesort ist Schritt 1 rekursiv zu brechen das Array in zwei Hälften.

522
00:43:05,680 --> 00:43:09,350
So unterteilt dieses Array in zwei Hälften.

523
00:43:09,350 --> 00:43:22,920
Wir haben jetzt 4, 15, 16, 50 und 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Und jetzt haben wir es wieder tun und wir teilen diese in zwei Hälften.

525
00:43:25,800 --> 00:43:27,530
Ich werde es einfach tun auf dieser Seite.

526
00:43:27,530 --> 00:43:34,790
Also 4, 15 und 16, 50.

527
00:43:34,790 --> 00:43:37,440
Wir würden die gleiche Sache immer tun.

528
00:43:37,440 --> 00:43:40,340
Und jetzt haben wir spaltete es in zwei Hälften wieder.

529
00:43:40,340 --> 00:43:51,080
Und wir haben 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Also das ist unsere Basis Fall.

531
00:43:53,170 --> 00:44:00,540
Nachdem die Arrays der Größe 1 sind, dann werden wir mit der Aufspaltung zu stoppen in zwei Hälften.

532
00:44:00,540 --> 00:44:03,190
>> Nun, was haben wir damit zu tun?

533
00:44:03,190 --> 00:44:15,730
Wir landen wird dies auch brechen in 8, 23, 42 und 108.

534
00:44:15,730 --> 00:44:24,000
So, jetzt, dass wir an diesem Punkt sind, jetzt Schritt zwei Mergesort ist nur Zusammenlegung Paaren zu den Listen.

535
00:44:24,000 --> 00:44:27,610
So wollen wir diese zusammenführen. Wir rufen zu verschmelzen.

536
00:44:27,610 --> 00:44:31,410
Wir wissen merge werden diese in sortierter Reihenfolge zurück.

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

538
00:44:33,920 --> 00:44:41,440
Jetzt wollen wir diese zusammenführen, und das wird eine Liste mit den in sortierter Reihenfolge zurück,

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

540
00:44:44,160 --> 00:44:57,380
Wir verschmelzen die - ich kann nicht schreiben - 8, 23 und 42, 108.

541
00:44:57,380 --> 00:45:02,890
So haben wir fusionierten Paaren einmal.

542
00:45:02,890 --> 00:45:05,140
Jetzt müssen wir nur wieder zusammenführen.

543
00:45:05,140 --> 00:45:10,130
Beachten Sie, dass jede dieser Listen sortiert ist an sich

544
00:45:10,130 --> 00:45:15,220
und dann können wir nur verschmelzen diese Listen, um eine Liste der Größe 4, sortiert zu bekommen

545
00:45:15,220 --> 00:45:19,990
und Zusammenführen dieser beiden Listen eine Liste der Größe 4, die sortiert erhalten.

546
00:45:19,990 --> 00:45:25,710
Und schließlich können wir mischen Sie die beiden Listen der Größe 4 zu einer Liste der Größe 8, sortiert zu bekommen.

547
00:45:25,710 --> 00:45:34,030
So zu sehen, dass diese allgemeine n log n ist, haben wir bereits gesehen, dass Merge-linear ist,

548
00:45:34,030 --> 00:45:40,390
so, wenn wir mit dem Zusammenführen dieser zu tun haben, so wie die Gesamtkosten der Zusammenführung

549
00:45:40,390 --> 00:45:43,410
für diese beiden Listen ist nur 2, weil -

550
00:45:43,410 --> 00:45:49,610
Oder gut, es ist O n, aber n ist hier nur diese 2 Elemente, so dass es 2.

551
00:45:49,610 --> 00:45:52,850
Und diese 2 2 sein und diese 2 2 sein und diese 2 2 sein,

552
00:45:52,850 --> 00:45:58,820
so über alle geht, dass wir tun müssen, landen wir tun, n.

553
00:45:58,820 --> 00:46:03,210
Wie 2 + 2 + 2 + 2 ist 8, das N ist,

554
00:46:03,210 --> 00:46:08,060
so dass die Kosten der Zusammenführung in dieser Reihe ist n.

555
00:46:08,060 --> 00:46:10,810
Und dann das Gleiche hier.

556
00:46:10,810 --> 00:46:16,980
Wir verschmelzen diese 2, dann diese 2 und individuell diese Zusammenführung wird vier Operationen zu nehmen,

557
00:46:16,980 --> 00:46:23,610
Diese Zusammenführung dauert vier Operationen, aber noch einmal, zwischen all diesen

558
00:46:23,610 --> 00:46:29,030
landen wir Verschmelzung n insgesamt Dinge, und so dass dieser Schritt erfolgt n.

559
00:46:29,030 --> 00:46:33,670
Und so jede Ebene hat n Elemente verschmolzen.

560
00:46:33,670 --> 00:46:36,110
>> Und wie viele gibt es?

561
00:46:36,110 --> 00:46:40,160
Auf jeder Ebene, wächst unser Angebot nach Größe 2.

562
00:46:40,160 --> 00:46:44,590
Hier unsere Arrays der Größe 1 sind, hier sind sie der Größe 2 sind, hier sind sie der Größe 4,

563
00:46:44,590 --> 00:46:46,470
und schließlich sind sie der Größe 8.

564
00:46:46,470 --> 00:46:56,450
Zumal es verdoppelt wird, wird es auch insgesamt log n dieser Ebenen liegen.

565
00:46:56,450 --> 00:47:02,090
Also mit log n Ebenen, wobei jede einzelne Ebene unter n insgesamt Operationen,

566
00:47:02,090 --> 00:47:05,720
bekommen wir eine n log n Algorithmus.

567
00:47:05,720 --> 00:47:07,790
Haben Sie Fragen?

568
00:47:08,940 --> 00:47:13,320
Haben Menschen, die bereits Fortschritte gemacht, wie dies zu implementieren?

569
00:47:13,320 --> 00:47:18,260
Ist jemand bereits in einem Zustand, wo ich nur ziehen kann ihren Code?

570
00:47:20,320 --> 00:47:22,260
Ich kann eine Minute.

571
00:47:24,770 --> 00:47:27,470
Dieser wird länger sein.

572
00:47:27,470 --> 00:47:28,730
Ich empfehle wiederkehren -

573
00:47:28,730 --> 00:47:30,510
Sie haben noch die Rekursion für Merge tun

574
00:47:30,510 --> 00:47:33,750
weil die Rekursion für Merge tun, sind Sie gehen zu müssen, eine Reihe von verschiedenen Größen passieren.

575
00:47:33,750 --> 00:47:37,150
Man kann, aber es ist ärgerlich.

576
00:47:37,150 --> 00:47:43,720
Aber Rekursion für sort selbst ist recht einfach.

577
00:47:43,720 --> 00:47:49,190
Sie haben buchstäblich nennen sort auf der linken Hälfte, sort auf der rechten Hälfte. Okay.

578
00:47:51,770 --> 00:47:54,860
Wer noch etwas, das ich ziehen kann noch?

579
00:47:54,860 --> 00:47:57,540
Oder ich gebe eine Minute.

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

581
00:47:59,900 --> 00:48:02,970
Wer noch etwas mit denen wir arbeiten können?

582
00:48:05,450 --> 00:48:09,680
Oder aber wir müssen einfach damit arbeiten und erweitern Sie dann von dort aus.

583
00:48:09,680 --> 00:48:14,050
>> Wer noch mehr als dies, dass ich nach oben ziehen?

584
00:48:14,050 --> 00:48:17,770
[Schüler] Yeah. Sie können Pull-up-Mine. >> Alles klar.

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

586
00:48:22,170 --> 00:48:25,280
[Schüler] Es gab eine Menge von Bedingungen. >> Oh, schießen. Können Sie -

587
00:48:25,280 --> 00:48:28,110
[Schüler] Ich habe sie zu retten. >> Ja.

588
00:48:32,420 --> 00:48:35,730
Also taten wir tun, die Zusammenführung getrennt.

589
00:48:35,730 --> 00:48:38,570
Oh, aber es ist nicht so schlimm.

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

591
00:48:41,650 --> 00:48:47,080
So sort ist selbst nur anrufen mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Erklären Sie uns, was mergeSortHelp tut.

593
00:48:49,530 --> 00:48:55,700
[Schüler] MergeSortHelp ziemlich viel kostet die beiden wichtigsten Schritte,

594
00:48:55,700 --> 00:49:01,270
das ist es, jede Hälfte des Arrays zu sortieren und dann für beide von ihnen zu verschmelzen.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Okay, so geben Sie mir eine Sekunde.

596
00:49:10,850 --> 00:49:13,210
Ich denke, das - >> [Schüler] Ich muss -

597
00:49:17,100 --> 00:49:19,400
Yeah. Ich bin etwas fehlt.

598
00:49:19,400 --> 00:49:23,100
In merge, merke ich, dass ich um ein neues Array erstellen müssen

599
00:49:23,100 --> 00:49:26,530
denn ich konnte es nicht an Ort und Stelle. >> Ja. Sie kann es nicht. Zu korrigieren.

600
00:49:26,530 --> 00:49:28,170
[Schüler] So erstelle ich ein neues Array.

601
00:49:28,170 --> 00:49:31,510
Ich habe am Ende verschmelzen zu re-ändern.

602
00:49:31,510 --> 00:49:34,490
Okay. Wir brauchen ein neues Array.

603
00:49:34,490 --> 00:49:41,000
In Mergesort ist dies fast immer der Fall.

604
00:49:41,000 --> 00:49:44,340
Teil der Kosten eines besseren Algorithmus zeitlich

605
00:49:44,340 --> 00:49:47,310
ist fast immer braucht ein bisschen mehr Speicher zu verwenden.

606
00:49:47,310 --> 00:49:51,570
Also hier verschmelzen, egal wie Sie sortieren,

607
00:49:51,570 --> 00:49:54,780
Sie würde unweigerlich müssen einige zusätzliche Speicher zu verwenden.

608
00:49:54,780 --> 00:49:58,240
Er oder sie erstellt ein neues Array.

609
00:49:58,240 --> 00:50:03,400
Und dann sagst du am Ende müssen wir nur noch neue Array in das ursprüngliche Array kopieren.

610
00:50:03,400 --> 00:50:04,830
[Schüler] Ich denke schon, ja.

611
00:50:04,830 --> 00:50:08,210
Ich weiß nicht, ob das funktioniert in Bezug auf das Zählen von Referenz-oder was auch immer -

612
00:50:08,210 --> 00:50:11,650
Ja, wird es funktionieren. >> [Schüler] Okay.

613
00:50:20,620 --> 00:50:24,480
Haben Sie versucht, läuft das? >> [Schüler] Nein, noch nicht. >> Okay.

614
00:50:24,480 --> 00:50:28,880
Versuchen Sie es, und dann werde ich darüber für eine Sekunde sprechen.

615
00:50:28,880 --> 00:50:35,200
[Schüler] Ich brauche, um alle Funktionsprototypen und alles haben, obwohl, nicht wahr?

616
00:50:37,640 --> 00:50:40,840
Die Funktionsprototypen. Oh, du meinst wie - Ja.

617
00:50:40,840 --> 00:50:43,040
Sortieren ruft mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Also, um für die Sortierung zu mergeSortHelp aufrufen, müssen mergeSortHelp entweder definiert haben

619
00:50:47,390 --> 00:50:56,370
vor sortieren oder brauchen wir nur den Prototypen. Kopieren Sie einfach und fügen Sie diese.

620
00:50:56,370 --> 00:50:59,490
Und ähnlich wird mergeSortHelp Aufruf verschmelzen,

621
00:50:59,490 --> 00:51:03,830
aber merge wurde noch nicht festgelegt, so können wir lass mergeSortHelp wissen

622
00:51:03,830 --> 00:51:08,700
, dass das ist, was zusammenführen wird aussehen, und das ist, dass.

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

624
00:51:22,770 --> 00:51:32,660
Wir haben ein Problem hier, wo wir keine Basis Fall haben.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp rekursiv ist, so dass jede rekursive Funktion

626
00:51:38,110 --> 00:51:42,610
wird irgendeine Art von base case müssen wissen, wann man aufhören rekursiven Aufruf selber.

627
00:51:42,610 --> 00:51:45,590
Was ist unsere Basis bei gehen, hier zu sein? Yeah.

628
00:51:45,590 --> 00:51:49,110
[Schüler] Wenn die Größe 1? >> [Bowden] Ja.

629
00:51:49,110 --> 00:51:56,220
So wie wir genau dort sahen, hielten wir Splitting-Arrays

630
00:51:56,220 --> 00:52:01,850
sobald wir in Arrays der Größe 1, die unweigerlich selbst sortiert werden.

631
00:52:01,850 --> 00:52:09,530
Also, wenn Größe gleich 1 ist, wissen wir das Array bereits sortiert ist,

632
00:52:09,530 --> 00:52:12,970
so können wir nur zurück.

633
00:52:12,970 --> 00:52:16,880
>> Beachten Sie, das ist nichtig, so dass wir nicht wieder etwas Besonderes, wir zurückkehren.

634
00:52:16,880 --> 00:52:19,580
Okay. Damit ist unser Basis-Szenario.

635
00:52:19,580 --> 00:52:27,440
Ich denke, unsere base case könnte auch sein, wenn wir sein Verschmelzung ein Array der Größe 0 passieren,

636
00:52:27,440 --> 00:52:30,030
Wir wollen wahrscheinlich irgendwann aufhören,

637
00:52:30,030 --> 00:52:33,610
So können wir einfach sagen Größe von weniger als 2 oder weniger als oder gleich 1 ist

638
00:52:33,610 --> 00:52:37,150
so dass dies auch bei jedem Array jetzt funktionieren.

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

640
00:52:38,870 --> 00:52:42,740
Damit ist unser Basis-Szenario.

641
00:52:42,740 --> 00:52:45,950
Jetzt wollen Sie uns durch Zusammenführung gehen?

642
00:52:45,950 --> 00:52:49,140
Was haben alle diese Fälle bedeuten?

643
00:52:49,140 --> 00:52:54,480
Hier oben, wir sind nur die gleiche Idee, die -

644
00:52:56,970 --> 00:53:02,470
[Schüler] Ich brauche zu vorbei Größe mit allen mergeSortHelp Anrufe.

645
00:53:02,470 --> 00:53:10,080
Ich fügte hinzu, groß wie eine zusätzliche primäre und es ist nicht da, wie Größe / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, Größe / 2, Größe / 2. >> [Schüler] Ja, und auch in der obigen Funktion als gut.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Hier? >> [Student] Just Größe. >> [Bowden] Oh. Größe, Größe? >> [Schüler] Yeah.

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

649
00:53:23,010 --> 00:53:26,580
Lassen Sie mich für eine Sekunde denken.

650
00:53:26,580 --> 00:53:28,780
Haben wir in ein Problem laufen?

651
00:53:28,780 --> 00:53:33,690
Wir sind immer auf der Behandlung der linken als 0. >> [Schüler] Nr.

652
00:53:33,690 --> 00:53:36,340
Das ist auch falsch. Entschuldigung. Es sollte Anfang sein. Yeah.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Okay. Ich mag, dass besser.

654
00:53:39,230 --> 00:53:43,880
Und Ende. Okay.

655
00:53:43,880 --> 00:53:47,200
So, jetzt wollen Sie uns durch Zusammenführung gehen? >> [Schüler] Okay.

656
00:53:47,200 --> 00:53:52,150
Ich bin nur zu Fuß durch dieses neue Array, das ich erstellt habe.

657
00:53:52,150 --> 00:53:57,420
Seine Größe ist die Größe des Teils des Arrays, die wir sortiert werden soll

658
00:53:57,420 --> 00:54:03,460
und zu versuchen, das Element, dass ich in das neue Array Schritt gesetzt zu finden.

659
00:54:03,460 --> 00:54:10,140
So zu tun, erste ich Prüfen, ob die linke Hälfte des Feldes weiterhin mehr Elemente haben,

660
00:54:10,140 --> 00:54:14,260
und wenn es das nicht tut, dann gehen Sie auf dieser else-Bedingung, die nur sagt

661
00:54:14,260 --> 00:54:20,180
okay, muss es in die richtige Array sein, und wir werden, dass in der aktuellen Index newArray setzen.

662
00:54:20,180 --> 00:54:27,620
>> Und dann nichts anderes, ich überprüfen, ob die rechte Seite des Arrays auch abgeschlossen ist,

663
00:54:27,620 --> 00:54:30,630
in welchem ​​Fall ich gerade auf der linken Seite.

664
00:54:30,630 --> 00:54:34,180
Das könnte eigentlich nicht notwendig sein. Ich bin nicht sicher.

665
00:54:34,180 --> 00:54:40,970
Aber trotzdem sind die beiden anderen, welche der beiden kleineren in der linken oder der rechten Seite.

666
00:54:40,970 --> 00:54:49,770
Und auch in jedem Fall bin ich Inkrementieren je nachdem Platzhalter I erhöhen.

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

668
00:54:52,040 --> 00:54:53,840
Das sieht gut aus.

669
00:54:53,840 --> 00:54:58,800
Hat jemand Anmerkungen oder Bedenken oder Fragen?

670
00:55:00,660 --> 00:55:07,720
So sind die vier Fälle, dass wir die Dinge in einfach nur mitbringen müssen - oder es sieht aus wie fünf -

671
00:55:07,720 --> 00:55:13,100
aber wir haben zu prüfen, ob die linke Array von Dingen, die wir brauchen, um Mischlauf,

672
00:55:13,100 --> 00:55:16,390
ob das Recht Array von Dingen, die wir brauchen, um Mischlauf -

673
00:55:16,390 --> 00:55:18,400
Ich freue mich auf nichts zeigt.

674
00:55:18,400 --> 00:55:21,730
Also, ob das linke Array aus der Dinge laufen oder das Recht Array aus der Dinge laufen.

675
00:55:21,730 --> 00:55:24,320
Das sind zwei Fälle.

676
00:55:24,320 --> 00:55:30,920
Wir benötigen auch die trivialen Fall, ob der linke was kleiner ist als der Richtige.

677
00:55:30,920 --> 00:55:33,910
Dann wollen wir die linke Sache wählen.

678
00:55:33,910 --> 00:55:37,630
Das sind die Fälle.

679
00:55:37,630 --> 00:55:40,990
Das war also richtig, so ist das also.

680
00:55:40,990 --> 00:55:46,760
Array gelassen. Es ist 1, 2, 3. Okay. Also ja, das sind die vier Dinge, die wir tun wollen könnte.

681
00:55:50,350 --> 00:55:54,510
Und wir werden nicht über eine iterative Lösung gehen.

682
00:55:54,510 --> 00:55:55,980
Ich würde nicht empfehlen -

683
00:55:55,980 --> 00:56:03,070
Mergesort ist ein Beispiel für eine Funktion, die beide nicht endrekursiv ist,

684
00:56:03,070 --> 00:56:07,040
es ist nicht leicht zu machen endrekursiv,

685
00:56:07,040 --> 00:56:13,450
sondern auch es ist nicht sehr einfach zu machen, iterativ.

686
00:56:13,450 --> 00:56:16,910
Dies ist sehr einfach.

687
00:56:16,910 --> 00:56:19,170
Diese Implementierung von Mergesort,

688
00:56:19,170 --> 00:56:22,140
verschmelzen, egal was du tust, wirst du merge bauen.

689
00:56:22,140 --> 00:56:29,170
>> So Mergesort auf der Oberseite des Merge gebaut rekursiv ist nur diese drei Linien.

690
00:56:29,170 --> 00:56:34,700
Iterativ, ist es lästig und schwierig zu denken.

691
00:56:34,700 --> 00:56:41,860
Aber beachten Sie, dass es nicht endrekursiv seit mergeSortHelp - wenn es selbst nennt -

692
00:56:41,860 --> 00:56:46,590
es muss noch die Dinge nach dieser rekursiven Aufruf kehrt zu tun.

693
00:56:46,590 --> 00:56:50,830
Also das Stack-Frame muss weiterhin auch nach dem Aufruf dieser existieren.

694
00:56:50,830 --> 00:56:54,170
Und dann, wenn Sie diese aufrufen, muss der Stack-Frame weiter bestehen

695
00:56:54,170 --> 00:56:57,780
denn auch nach diesem Anruf, müssen wir noch zu fusionieren.

696
00:56:57,780 --> 00:57:01,920
Und es ist nicht trivial, um diese endrekursiv.

697
00:57:04,070 --> 00:57:06,270
Haben Sie Fragen?

698
00:57:08,300 --> 00:57:09,860
Gut.

699
00:57:09,860 --> 00:57:13,400
So gehen zurück zu sortieren - oh, es gibt zwei Dinge, die ich zeigen wollen. Okay.

700
00:57:13,400 --> 00:57:17,840
Gehen wir zurück zu sortieren, werden wir dies schnell zu tun.

701
00:57:17,840 --> 00:57:21,030
Oder suchen. Sortieren? Sortieren. Yeah.

702
00:57:21,030 --> 00:57:22,730
Gehen wir zurück zu den Anfängen der sort.

703
00:57:22,730 --> 00:57:29,870
Wir wollen einen Algorithmus, der Art der Array mit einem beliebigen Algorithmus erstellen

704
00:57:29,870 --> 00:57:33,660
O in der n.

705
00:57:33,660 --> 00:57:40,860
Also, wie ist das möglich? Hat jemand eine Art von -

706
00:57:40,860 --> 00:57:44,300
Ich deutete vorher an -

707
00:57:44,300 --> 00:57:48,300
Wenn wir etwa von n log n bis O n zu verbessern,

708
00:57:48,300 --> 00:57:51,450
wir unseren Algorithmus zeitlich verbessert,

709
00:57:51,450 --> 00:57:55,250
was bedeutet, was sollen wir tun müssen, um Make-up für die damit?

710
00:57:55,250 --> 00:57:59,520
[Schüler] Space. >> Ja. Wir gehen zu sein mit mehr Platz.

711
00:57:59,520 --> 00:58:04,490
Und auch nicht nur mehr Platz, ist es exponentiell mehr Platz.

712
00:58:04,490 --> 00:58:14,320
Also ich denke, diese Art von Algorithmus ist pseudo etwas, pseudo Polynom -

713
00:58:14,320 --> 00:58:18,980
pseudo - ich kann mich nicht erinnern. Pseudo etwas.

714
00:58:18,980 --> 00:58:22,210
Aber es ist, weil wir so viel Platz benötigen

715
00:58:22,210 --> 00:58:28,610
dass dies erreichbar ist, jedoch nicht realistisch.

716
00:58:28,610 --> 00:58:31,220
>> Und wie wollen wir das erreichen?

717
00:58:31,220 --> 00:58:36,810
Wir erreichen dies, wenn wir garantieren, dass ein bestimmtes Element im Array

718
00:58:36,810 --> 00:58:39,600
unter einer bestimmten Größe.

719
00:58:42,070 --> 00:58:44,500
Also lasst uns einfach sagen, dass Größe 200,

720
00:58:44,500 --> 00:58:48,130
jedes Element in einer Anordnung unterhalb Größe 200.

721
00:58:48,130 --> 00:58:51,080
Und das ist eigentlich sehr realistisch.

722
00:58:51,080 --> 00:58:58,660
Sie können sehr leicht ein Array, dass Sie alles wissen, in sie

723
00:58:58,660 --> 00:59:00,570
wird auf weniger als eine bestimmte Anzahl.

724
00:59:00,570 --> 00:59:07,400
Wie, wenn Sie etwas absolut riesig vector oder so etwas haben

725
00:59:07,400 --> 00:59:11,810
aber du weißt alles wird zwischen 0 und 5 liegen,

726
00:59:11,810 --> 00:59:14,790
dann wird es zu deutlich schneller, dies zu tun.

727
00:59:14,790 --> 00:59:17,930
Und das gebundene auf einem der Elemente 5 ist,

728
00:59:17,930 --> 00:59:21,980
so dass diese gebundene, das heißt, wie viel Speicher du gehst zu verwenden.

729
00:59:21,980 --> 00:59:26,300
So ist die Grenze ist 200.

730
00:59:26,300 --> 00:59:32,960
In der Theorie gibt es immer ein gebundenes da eine ganze Zahl kann nur bis zu 4 Milliarden,

731
00:59:32,960 --> 00:59:40,600
aber das ist seitdem wir würden den Weltraum unrealistisch

732
00:59:40,600 --> 00:59:44,400
in der Größenordnung von 4 Milliarden Euro. Also das ist unrealistisch.

733
00:59:44,400 --> 00:59:47,060
Aber hier werden wir unsere gebundenen sagen, ist 200.

734
00:59:47,060 --> 00:59:59,570
Der Trick, um es zu tun in O von n ist, dass wir einen weiteren Array namens zählt der Größe GEBUNDEN.

735
00:59:59,570 --> 01:00:10,470
Also eigentlich ist dies eine Abkürzung für - ich eigentlich nicht weiß, ob Clang tut dies.

736
01:00:11,150 --> 01:00:15,330
Aber in GCC zumindest - ich bin davon Clang tut es auch -

737
01:00:15,330 --> 01:00:18,180
dies nur initialisiert das gesamte Array zu sein 0s.

738
01:00:18,180 --> 01:00:25,320
Also, wenn ich nicht will, das zu tun, dann könnte ich separat zu tun (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <BOUND; i + +) und zählt [i] = 0;

740
01:00:31,500 --> 01:00:35,260
So, jetzt ist alles auf 0 initialisiert.

741
01:00:35,260 --> 01:00:39,570
Ich über meine Array durchlaufen,

742
01:00:39,570 --> 01:00:51,920
und was ich mache ist, dass ich das Zählen der Anzahl der einzelnen - LET'S GO hier unten.

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

744
01:00:55,480 --> 01:01:00,010
Was ich zähle die Anzahl der Vorkommen jedes dieser Elemente.

745
01:01:00,010 --> 01:01:03,470
Lasst uns tatsächlich ein paar mehr hinzuzufügen hier mit einigen Wiederholungen.

746
01:01:03,470 --> 01:01:11,070
So wird der Wert wir hier haben, ist der Wert, werde Array [i].

747
01:01:11,070 --> 01:01:14,850
So val konnte 4 oder 8 oder was auch immer.

748
01:01:14,850 --> 01:01:18,870
Und jetzt bin ich zählen, wie viele dieser Wert ich gesehen habe,

749
01:01:18,870 --> 01:01:21,230
so zählt [val] + +;

750
01:01:21,230 --> 01:01:29,430
Nachdem dies geschehen ist, wird Zählungen werden etwas wie 0001 zu sehen.

751
01:01:29,430 --> 01:01:42,190
Lasst uns zählt [val] - Bound + 1.

752
01:01:42,190 --> 01:01:48,230
>> Nun, das ist nur für die Tatsache, dass wir von 0 beginnend ausmachen.

753
01:01:48,230 --> 01:01:50,850
Also, wenn 200 wird unsere größte Zahl sein,

754
01:01:50,850 --> 01:01:54,720
dann von 0 bis 200 ist 201 Sachen.

755
01:01:54,720 --> 01:02:01,540
So zählt, werde es wie 00.001 aussehen, weil wir eine 4 haben.

756
01:02:01,540 --> 01:02:10,210
Dann haben wir 0001, wo wir eine 1 in der 8. Index der Anzahl musst.

757
01:02:10,210 --> 01:02:14,560
Wir werden eine 2 in der 23. Index der Zählung haben.

758
01:02:14,560 --> 01:02:17,630
Wir werden eine 2 in der 42. Index der Zählung haben.

759
01:02:17,630 --> 01:02:21,670
So können wir zählen.

760
01:02:34,270 --> 01:02:44,920
So num_of_item = counts [i].

761
01:02:44,920 --> 01:02:52,540
Und so, wenn num_of_item 2 ist, dass heißt, wir wollen 2 von der Anzahl i einfügen

762
01:02:52,540 --> 01:02:55,290
in unsere sortierten Array.

763
01:02:55,290 --> 01:03:02,000
Also müssen wir verfolgen, wie weit sind wir in das Array zu halten.

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

765
01:03:05,470 --> 01:03:09,910
Array - Ich werde nur schreiben.

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

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

768
01:03:28,580 --> 01:03:32,490
Ist das, was ich will? Ich denke, dass ist es, was ich will.

769
01:03:35,100 --> 01:03:38,290
Ja, das sieht gut aus. Okay.

770
01:03:38,290 --> 01:03:43,050
So wird jeder verstehen, was der Zweck meiner zählt Array ist?

771
01:03:43,050 --> 01:03:48,140
Es wird das Zählen der Anzahl des Auftretens von jeder dieser Zahlen.

772
01:03:48,140 --> 01:03:51,780
Dann bin ich Iteration über die zählt Array

773
01:03:51,780 --> 01:03:57,190
und der i-ten Position in der Zählungen array

774
01:03:57,190 --> 01:04:01,930
die Anzahl von i ist, die in meinem sortierten Array erscheinen soll.

775
01:04:01,930 --> 01:04:06,840
Deshalb zählt der 4 wird 1 sein

776
01:04:06,840 --> 01:04:11,840
und zählt von 8 wird 1 sein wird Grafen von 23 werde 2 sein.

777
01:04:11,840 --> 01:04:16,900
Also das ist, wie viele von ihnen, dass ich in meiner sortierten Array einfügen möchten.

778
01:04:16,900 --> 01:04:19,200
Dann habe ich nur tun.

779
01:04:19,200 --> 01:04:28,960
Ich bin Einfügen num_of_item i ist in meinen sortierten Array.

780
01:04:28,960 --> 01:04:31,670
>> Haben Sie Fragen?

781
01:04:32,460 --> 01:04:43,100
Und so wieder, das ist die lineare Zeit, da wir gerade durchlaufen werden über dieses eine Mal,

782
01:04:43,100 --> 01:04:47,470
aber es ist auch in dem, was passiert, diese Anzahl um die linear,

783
01:04:47,470 --> 01:04:50,730
und so ist es hängt stark auf, was Ihre gebunden ist.

784
01:04:50,730 --> 01:04:53,290
Mit einem Satz von 200, das ist nicht so schlimm.

785
01:04:53,290 --> 01:04:58,330
Wenn Ihr gebundenen wird 10.000 sein, dann ist das ein wenig schlechter,

786
01:04:58,330 --> 01:05:01,360
aber wenn Ihr gebundenen wird auf 4 Milliarden, das ist völlig unrealistisch

787
01:05:01,360 --> 01:05:07,720
und das Array zu haben, um der Größe 4 Mrd., was unrealistisch ist.

788
01:05:07,720 --> 01:05:10,860
So basta. Haben Sie Fragen?

789
01:05:10,860 --> 01:05:13,270
[Unverständlich Student Response] >> Okay.

790
01:05:13,270 --> 01:05:15,710
Ich erkannte eine andere Sache, wenn wir durch gingen.

791
01:05:17,980 --> 01:05:23,720
Ich denke, das Problem war in Lucas 'und wahrscheinlich jeder einzelne wir gesehen haben.

792
01:05:23,720 --> 01:05:26,330
Ich habe ganz vergessen.

793
01:05:26,330 --> 01:05:31,040
Das einzige, was ich wollte zu kommentieren ist, dass wenn man mit Dingen wie Indizes zu tun haben,

794
01:05:31,040 --> 01:05:38,320
Sie nie wirklich sehen, wenn Sie schriftlich eine suchen Schleife

795
01:05:38,320 --> 01:05:41,120
aber technisch immer dann, wenn Sie mit diesen Indizes zu tun haben,

796
01:05:41,120 --> 01:05:45,950
Sie sollten so ziemlich immer mit Ganzzahlen umzugehen.

797
01:05:45,950 --> 01:05:53,850
Der Grund dafür ist, wenn Sie mit Ganzzahlen zu tun haben,

798
01:05:53,850 --> 01:05:56,090
so, wenn Sie 2 Ganzzahlen mit Vorzeichen und fügen Sie sie zusammen

799
01:05:56,090 --> 01:06:00,640
und sie zu groß zu beenden, dann am Ende mit einer negativen Zahl.

800
01:06:00,640 --> 01:06:03,410
Also das ist, was Integer-Überlauf ist.

801
01:06:03,410 --> 01:06:10,500
>> Wenn ich 2 Milliarden Euro und 1 Mrd. hinzuzufügen, habe ich am Ende mit negativen 1 Milliarde.

802
01:06:10,500 --> 01:06:15,480
Das ist, wie ganze Zahlen auf Computern zu arbeiten.

803
01:06:15,480 --> 01:06:17,510
Also das Problem bei der Verwendung -

804
01:06:17,510 --> 01:06:23,500
Das ist in Ordnung, außer, wenn niedrige passiert 2 Milliarden und bis zufällig 1 Milliarde,

805
01:06:23,500 --> 01:06:27,120
dann wird negativ sein 1 Mrd. und dann werden wir zu teilen, dass durch 2

806
01:06:27,120 --> 01:06:29,730
und am Ende mit negativen 500 Millionen Euro.

807
01:06:29,730 --> 01:06:33,760
So ist dies nur ein Problem, wenn Sie über ein Array zu suchen passieren

808
01:06:33,760 --> 01:06:38,070
Milliarden von Dingen.

809
01:06:38,070 --> 01:06:44,050
Aber wenn low + up passiert Überlauf, dann ist das ein Problem.

810
01:06:44,050 --> 01:06:47,750
Sobald wir sie unsigned machen, dann 2 Milliarden plus 1 Mrd. 3 Milliarden Euro.

811
01:06:47,750 --> 01:06:51,960
3 Milliarden geteilt durch 2 ist 1,5 Milliarden Euro.

812
01:06:51,960 --> 01:06:55,670
So, sobald sie unsigned bist, ist alles perfekt.

813
01:06:55,670 --> 01:06:59,900
Und damit ist auch ein Problem, wenn Sie Ihren sind für Schleifen,

814
01:06:59,900 --> 01:07:03,940
und tatsächlich, ist es wahrscheinlich tut es automatisch.

815
01:07:09,130 --> 01:07:12,330
Es wird eigentlich nur auf dich schreien.

816
01:07:12,330 --> 01:07:21,610
Also, wenn diese Zahl ist zu groß, um in nur einer Zahl sein, aber es wäre in einem unsigned integer passen,

817
01:07:21,610 --> 01:07:24,970
es wird dich anschreien, so das ist, warum Sie nie wirklich in das Thema laufen.

818
01:07:29,150 --> 01:07:34,820
Sie können sehen, dass ein Index wird nie negativ sein,

819
01:07:34,820 --> 01:07:39,220
und so, wenn Sie über ein Array durchlaufen,

820
01:07:39,220 --> 01:07:43,970
Sie können fast immer sagen, unsigned int i, aber nicht wirklich zu.

821
01:07:43,970 --> 01:07:47,110
Die Dinge werden sich ziemlich genau so gut funktionieren.

822
01:07:48,740 --> 01:07:50,090
Okay. [Flüstert] Wie spät ist es?

823
01:07:50,090 --> 01:07:54,020
Das letzte was ich wollte zeigen - und ich werde es einfach tun wirklich schnell.

824
01:07:54,020 --> 01:08:03,190
Du weißt, wie wir # define damit wir # definieren MAX als 5 oder so etwas?

825
01:08:03,190 --> 01:08:05,940
Lasst uns nicht MAX. # Define gebunden als 200. Das ist das, was wir vorher taten.

826
01:08:05,940 --> 01:08:10,380
Das definiert eine Konstante, die gerade dabei ist, kopiert und eingefügt werden

827
01:08:10,380 --> 01:08:13,010
wo immer wir zu schreiben GEBUNDEN.

828
01:08:13,010 --> 01:08:18,189
>> So können wir tatsächlich mehr mit # definiert.

829
01:08:18,189 --> 01:08:21,170
Wir können # define Funktionen.

830
01:08:21,170 --> 01:08:23,410
Sie sind nicht wirklich funktioniert, aber wir nennen sie Funktionen.

831
01:08:23,410 --> 01:08:36,000
Ein Beispiel wäre etwas wie MAX (x, y) wird als (?: X x <y y) definiert. Okay.

832
01:08:36,000 --> 01:08:40,660
So sollten Sie auf ternäre Operator Syntax zu gewöhnen,

833
01:08:40,660 --> 01:08:49,029
aber x kleiner als y? Zurück y, andernfalls kehren x.

834
01:08:49,029 --> 01:08:54,390
So können Sie sehen, können Sie diesen eine separate Funktion zu machen,

835
01:08:54,390 --> 01:09:01,399
und die Funktion könnte wie bool MAX dauert 2 Argumente, return this.

836
01:09:01,399 --> 01:09:08,340
Dies ist eines der gebräuchlichsten Ich sehe, wie dies getan. Wir nennen sie Makros.

837
01:09:08,340 --> 01:09:11,790
Dies ist ein Makro.

838
01:09:11,790 --> 01:09:15,859
Dies ist nur die Syntax für sie.

839
01:09:15,859 --> 01:09:18,740
Sie können ein Makro schreiben, zu tun, was Sie wollen.

840
01:09:18,740 --> 01:09:22,649
Sie sehen oft Makros für das Debuggen printfs and stuff.

841
01:09:22,649 --> 01:09:29,410
So eine Art von printf, gibt es spezielle Konstanten in C wie Unterstrich LINE unterstreichen,

842
01:09:29,410 --> 01:09:31,710
2 unterstreicht LINE unterstreichen,

843
01:09:31,710 --> 01:09:37,550
und es gibt auch ich glaube 2 unterstreicht FUNC. Das könnte es sein. So etwas Ähnliches.

844
01:09:37,550 --> 01:09:40,880
Diese Dinge werden mit dem Namen der Funktion ersetzt werden

845
01:09:40,880 --> 01:09:42,930
oder die Nummer der Zeile, die Sie sich gerade befinden.

846
01:09:42,930 --> 01:09:48,630
Häufig, schreiben Sie mit dem Debuggen printfs, dass hier unten habe ich dann einfach schreiben konnte

847
01:09:48,630 --> 01:09:54,260
DEBUG und es wird die Nummer der Zeile und Funktion, dass ich in sein passieren drucken

848
01:09:54,260 --> 01:09:57,020
dass sie diesen Debug-Anweisung angetroffen.

849
01:09:57,020 --> 01:09:59,550
Und Sie können auch ausdrucken andere Dinge.

850
01:09:59,550 --> 01:10:05,990
So ein Sache, die Sie achten sollten ist, wenn ich # define DOUBLE_MAX passieren

851
01:10:05,990 --> 01:10:11,380
so etwas wie 2 * y und 2 * x.

852
01:10:11,380 --> 01:10:14,310
Also für welchen Gründen auch immer, passieren Sie, dass eine Menge zu tun.

853
01:10:14,310 --> 01:10:16,650
So machen es zu einem Makro.

854
01:10:16,650 --> 01:10:18,680
Dies ist tatsächlich gebrochen.

855
01:10:18,680 --> 01:10:23,050
Ich würde es durch etwas wie DOUBLE_MAX (3, 6) nennen.

856
01:10:23,050 --> 01:10:27,530
Also, was soll zurückgegeben werden?

857
01:10:28,840 --> 01:10:30,580
[Schüler] 12.

858
01:10:30,580 --> 01:10:34,800
Ja, Sie sollten 12 zurückgeführt werden, und 12 zurückgegeben.

859
01:10:34,800 --> 01:10:43,350
3 wird für x ersetzt, wird 6 für y ersetzt, und wir kehren 2 * 6, die 12 ist.

860
01:10:43,350 --> 01:10:47,710
Nun was ist das? Was sollte zurückgegeben werden?

861
01:10:47,710 --> 01:10:50,330
[Schüler] 14. >> Idealfall 14.

862
01:10:50,330 --> 01:10:55,290
Das Problem ist, dass, wie Hash definiert Arbeit, denken Sie daran, es ist eine wörtliche Kopie und Paste

863
01:10:55,290 --> 01:11:00,160
der so ziemlich alles, so was, das wird so ausgelegt werden

864
01:11:00,160 --> 01:11:11,270
3 ist weniger als 1 plus 6, 2 mal 1 plus 6, 2 mal 3.

865
01:11:11,270 --> 01:11:19,780
>> So aus diesem Grund fast immer wickeln alles in Klammern.

866
01:11:22,180 --> 01:11:25,050
Jede Variable, die Sie fast immer in Klammern wickeln.

867
01:11:25,050 --> 01:11:29,570
Es gibt Fälle, wo man nicht haben, um, wie ich weiß, dass ich nicht brauchen, um das hier tun

868
01:11:29,570 --> 01:11:32,110
da weniger als ist so ziemlich immer nur zur Arbeit gehen,

869
01:11:32,110 --> 01:11:34,330
obwohl dies vielleicht nicht einmal wahr sein.

870
01:11:34,330 --> 01:11:41,870
Wenn es etwas lächerlich wie DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
dann ist das jetzt mit 3 weniger als 1 ersetzt zu bekommen ist gleich gleich 2,

872
01:11:49,760 --> 01:11:53,460
und so dann wird es zu tun 3 kleiner als 1, bedeutet das gleich 2,

873
01:11:53,460 --> 01:11:55,620
das ist nicht das, was wir wollen.

874
01:11:55,620 --> 01:12:00,730
Um also keine Operatorvorrang Probleme zu vermeiden,

875
01:12:00,730 --> 01:12:02,870
immer in Klammern zu wickeln.

876
01:12:03,290 --> 01:12:07,700
Okay. Und das ist alles, 5:30.

877
01:12:08,140 --> 01:12:12,470
Wenn Sie Fragen zum pset haben, lassen Sie es uns wissen.

878
01:12:12,470 --> 01:12:18,010
Es soll Spaß machen, und die Hacker-Edition ist auch viel realistischer

879
01:12:18,010 --> 01:12:22,980
als der Hacker-Ausgabe des vergangenen Jahres, so hoffen wir, dass viele von Ihnen es zu versuchen.

880
01:12:22,980 --> 01:12:26,460
Im vergangenen Jahr war sehr überwältigend.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]