1
00:00:00,000 --> 00:00:05,830

2
00:00:05,830 --> 00:00:07,910
>> Na gut, so, Berechnungskomplexität.

3
00:00:07,910 --> 00:00:10,430
Nur ein bisschen eine Warnung
Bevor wir uns in zu far--

4
00:00:10,430 --> 00:00:13,070
Diese werden wahrscheinlich unter sein
Die Mathematik-schwere Dinge

5
00:00:13,070 --> 00:00:14,200
wir über in CS50 sprechen.

6
00:00:14,200 --> 00:00:16,950
Hoffentlich wird es nicht zu überwältigend sein
und wir werden versuchen, und führen Sie

7
00:00:16,950 --> 00:00:19,200
durch den Prozess, aber
nur ein bisschen eine faire Warnung.

8
00:00:19,200 --> 00:00:21,282
Es ist ein bisschen
Mathe hier beteiligt.

9
00:00:21,282 --> 00:00:23,990
Na gut, so, damit
Verwendung unserer Rechenressourcen

10
00:00:23,990 --> 00:00:28,170
in der realen world-- es wirklich
wichtig, um Algorithmen zu verstehen

11
00:00:28,170 --> 00:00:30,750
und wie sie Prozessdaten.

12
00:00:30,750 --> 00:00:32,810
Wenn wir eine wirklich
effizienten Algorithmus, wir

13
00:00:32,810 --> 00:00:36,292
kann die Menge an Ressourcen zu minimieren
wir zur Verfügung haben, damit umzugehen.

14
00:00:36,292 --> 00:00:38,750
Wenn wir einen Algorithmus,
wird eine Menge Arbeit

15
00:00:38,750 --> 00:00:41,210
um wirklich zu verarbeiten ein
große Menge von Daten, ist es

16
00:00:41,210 --> 00:00:44,030
gehen, um mehr erforderlich
und mehr Ressourcen, die

17
00:00:44,030 --> 00:00:47,980
ist Geld, RAM, all solche Sachen.

18
00:00:47,980 --> 00:00:52,090
>> Also, in der Lage, eine Analyse
Algorithmus mit diesem Werkzeug-Set,

19
00:00:52,090 --> 00:00:56,110
Grundsätzlich fordert die question--
wie funktioniert dieser Algorithmus Skala

20
00:00:56,110 --> 00:00:59,020
wie wir mehr und mehr Daten um sich werfen?

21
00:00:59,020 --> 00:01:02,220
In CS50, die Menge der Daten sind wir
Arbeiten mit ist ziemlich klein.

22
00:01:02,220 --> 00:01:05,140
Im Allgemeinen werden unsere Programme gehen
um in einer zweiten oder less-- laufen

23
00:01:05,140 --> 00:01:07,830
wahrscheinlich viel weniger
besonders früh.

24
00:01:07,830 --> 00:01:12,250
>> Aber zu einer Firma, die Angebote zu denken
Hunderte von Millionen von Kunden.

25
00:01:12,250 --> 00:01:14,970
Und sie brauchen, um zu verarbeiten
dass Kundendaten.

26
00:01:14,970 --> 00:01:18,260
Als die Anzahl der Kunden, die sie
haben wird größer und größer,

27
00:01:18,260 --> 00:01:21,230
es wird erforderlich
mehr und mehr Ressourcen.

28
00:01:21,230 --> 00:01:22,926
Wie viele Ressourcen?

29
00:01:22,926 --> 00:01:25,050
Nun, das hängt davon ab, wie
analysieren wir den Algorithmus,

30
00:01:25,050 --> 00:01:28,097
mit Hilfe der Tools in dieser Toolbox.

31
00:01:28,097 --> 00:01:31,180
Wenn wir von der Komplexität der zu sprechen
ein algorithm-- was manchmal werden Sie

32
00:01:31,180 --> 00:01:34,040
hören es an der Zeit bezeichnet
Komplexität und Speicherkomplexität

33
00:01:34,040 --> 00:01:36,190
aber wir sind gerade dabei
zu rufen complexity--

34
00:01:36,190 --> 00:01:38,770
wir sind in der Regel reden
das Worst-Case-Szenario.

35
00:01:38,770 --> 00:01:42,640
Angesichts der absolute worst Haufen
Daten, die wir auf sie zu werfen,

36
00:01:42,640 --> 00:01:46,440
wie wird dieser Algorithmus würde
verarbeiten oder sich mit diesen Daten?

37
00:01:46,440 --> 00:01:51,450
Wir das Worst-Case-rufen in der Regel
Laufzeit eines Algorithmus big-O.

38
00:01:51,450 --> 00:01:56,770
So könnte ein Algorithmus zu sagen
laufen in O n oder O n quadriert.

39
00:01:56,770 --> 00:01:59,110
Und mehr über das, was
diejenigen bedeuten, in einem zweiten.

40
00:01:59,110 --> 00:02:01,620
>> Manchmal aber geht uns
über das Best-Case-Szenario.

41
00:02:01,620 --> 00:02:05,400
Wenn die Daten alles, was wir wollten
es zu sein und es war absolut perfekt

42
00:02:05,400 --> 00:02:09,630
und wir senden diesen perfekten
Set von Daten über unser Algorithmus.

43
00:02:09,630 --> 00:02:11,470
Wie wäre es in dieser Situation umgehen?

44
00:02:11,470 --> 00:02:15,050
Wir beziehen uns manchmal, dass als
Big-Omega, so im Gegensatz zu Big-O,

45
00:02:15,050 --> 00:02:16,530
Wir haben big-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega für den besten Fall.

47
00:02:18,880 --> 00:02:21,319
Big-O für den Fall der Fälle.

48
00:02:21,319 --> 00:02:23,860
Im Allgemeinen, wenn wir sprechen
Die Komplexität eines Algorithmus,

49
00:02:23,860 --> 00:02:26,370
wir über das reden
Worst-Case-Szenario.

50
00:02:26,370 --> 00:02:28,100
So sollte man das im Hinterkopf.

51
00:02:28,100 --> 00:02:31,510
>> Und in dieser Klasse, wir sind in der Regel gehen
um die strengen Analyse beiseite zu lassen.

52
00:02:31,510 --> 00:02:35,350
Es gibt Wissenschaften und Felder
um diese Art von Sachen gewidmet.

53
00:02:35,350 --> 00:02:37,610
Wenn wir über die Gründe sprechen
durch Algorithmen,

54
00:02:37,610 --> 00:02:41,822
was wir Stück für Stück für viele zu tun
Algorithmen, wir sprechen in der Klasse.

55
00:02:41,822 --> 00:02:44,780
Wir sind wirklich nur darüber zu reden
Argumentation durch sie mit gesundem Menschenverstand,

56
00:02:44,780 --> 00:02:47,070
nicht mit Formeln, oder Beweise,
oder so etwas.

57
00:02:47,070 --> 00:02:51,600
Also keine Sorge, wir werden nicht
sich in einen großen Math-Klasse.

58
00:02:51,600 --> 00:02:55,920
>> Also sagte ich: wir über die Komplexität Pflege
weil sie die Frage, wie verlangt

59
00:02:55,920 --> 00:03:00,160
haben unsere Algorithmen umgehen größer und
wobei größere Datenmengen auf sie geworfen.

60
00:03:00,160 --> 00:03:01,960
Nun, was ist ein Datensatz?

61
00:03:01,960 --> 00:03:03,910
Was habe ich meine, wenn ich das gesagt?

62
00:03:03,910 --> 00:03:07,600
Es bedeutet, was auch immer das macht
Sinn im Kontext, um ehrlich zu sein.

63
00:03:07,600 --> 00:03:11,160
Wenn wir einen Algorithmus, der
Prozesse Strings-- wir wahrscheinlich

64
00:03:11,160 --> 00:03:13,440
reden über die Größe der Zeichenfolge.

65
00:03:13,440 --> 00:03:15,190
Das ist die Daten-Satz--
Die Größe, die Anzahl

66
00:03:15,190 --> 00:03:17,050
von Zeichen, aus denen sich die Schnur.

67
00:03:17,050 --> 00:03:20,090
Wenn wir über ein Gespräch
Algorithmus, der Dateien verarbeitet,

68
00:03:20,090 --> 00:03:23,930
könnten wir darüber, wie sprechen
viele Kilobytes umfassen diese Datei.

69
00:03:23,930 --> 00:03:25,710
Und das ist der Datensatz.

70
00:03:25,710 --> 00:03:28,870
Wenn wir über einen Algorithmus im Gespräch
daß Griffe Arrays allgemeiner

71
00:03:28,870 --> 00:03:31,510
wie Sortieralgorithmen
oder Suchalgorithmen,

72
00:03:31,510 --> 00:03:36,690
Wir sind wahrscheinlich über die Anzahl Gespräche
Elemente, die ein Array umfassen.

73
00:03:36,690 --> 00:03:39,272
>> Jetzt können wir ein zu messen
algorithm-- insbesondere

74
00:03:39,272 --> 00:03:40,980
wenn ich sage, wir können
messen einen Algorithmus, I

75
00:03:40,980 --> 00:03:43,840
bedeuten, können wir messen, wie
viele Ressourcen nimmt es.

76
00:03:43,840 --> 00:03:48,990
Ob diese Ressourcen sind, wie viele
Byte RAM-- oder Megabyte RAM

77
00:03:48,990 --> 00:03:49,790
es verwendet.

78
00:03:49,790 --> 00:03:52,320
Oder wie viel Zeit es braucht, um laufen.

79
00:03:52,320 --> 00:03:56,200
Und wir können diesen Aufruf
zu messen, beliebig, f n.

80
00:03:56,200 --> 00:03:59,420
Wobei n die Anzahl von
Elemente in der Datenmenge.

81
00:03:59,420 --> 00:04:02,640
Und f n ist, wie viele Jährigen.

82
00:04:02,640 --> 00:04:07,530
Wie viele Einheiten von Ressourcen funktioniert
sie erfordern, um diese Daten zu verarbeiten.

83
00:04:07,530 --> 00:04:10,030
>> Nun, wir eigentlich egal
über das, was f n ist genau.

84
00:04:10,030 --> 00:04:13,700
In der Tat, sehr selten will-- wir
wird sicherlich nie in dieser class-- I

85
00:04:13,700 --> 00:04:18,709
tauchen Sie ein in jeder wirklich tief
Analyse, was f von n ist.

86
00:04:18,709 --> 00:04:23,510
Wir sind gerade dabei, über das, was f sprechen
n ungefähr oder was es dazu neigt.

87
00:04:23,510 --> 00:04:27,600
Und die Tendenz eines Algorithmus ist
von seinem höchsten Reihenfolge tige diktiert.

88
00:04:27,600 --> 00:04:29,440
Und wir können sehen, was ich
damit meine, indem sie

89
00:04:29,440 --> 00:04:31,910
einen Blick auf ein konkreteres Beispiel.

90
00:04:31,910 --> 00:04:34,620
>> Also lassen Sie uns sagen, dass wir
drei verschiedene Algorithmen.

91
00:04:34,620 --> 00:04:39,350
Von denen die erste dauert n
in Würfel geschnitten, einige Einheiten der Ressourcen

92
00:04:39,350 --> 00:04:42,880
um einen Datensatz der Größe n zu verarbeiten.

93
00:04:42,880 --> 00:04:47,000
Wir haben einen zweiten Algorithmus, der findet
n hoch drei plus n quadriert Ressourcen

94
00:04:47,000 --> 00:04:49,350
um einen Datensatz der Größe n zu verarbeiten.

95
00:04:49,350 --> 00:04:52,030
Und wir haben ein Drittel
Algorithmus, der in--, dass läuft

96
00:04:52,030 --> 00:04:58,300
nimmt n gewürfelt minus 8n Quadrat
plus 20 n Einheiten von Ressourcen

97
00:04:58,300 --> 00:05:02,370
einen Algorithmus zu verarbeiten,
mit Datensatz der Größe n.

98
00:05:02,370 --> 00:05:05,594
>> Jetzt wieder, wir wirklich nicht gehen,
in diesem Detailgrad zu erhalten.

99
00:05:05,594 --> 00:05:08,260
Ich bin wirklich nur noch diese bis
hier als Illustration eines Punktes

100
00:05:08,260 --> 00:05:10,176
daß ich werde sein
was in einer zweiten, der

101
00:05:10,176 --> 00:05:12,980
ist, dass wir nur wirklich interessieren
über die Tendenz der Dinge

102
00:05:12,980 --> 00:05:14,870
da die Datenmengen immer größer.

103
00:05:14,870 --> 00:05:18,220
Also, wenn die Datenmenge ist klein, es gibt
eigentlich ein ziemlich großer Unterschied

104
00:05:18,220 --> 00:05:19,870
in dieser Algorithmen.

105
00:05:19,870 --> 00:05:23,000
Der dritte Algorithmus gibt
dauert 13 mal länger,

106
00:05:23,000 --> 00:05:27,980
13-fache der Menge an Ressourcen,
zu laufen, bezogen auf die erste.

107
00:05:27,980 --> 00:05:31,659
>> Wenn Sie unsere Datensatz Größe 10, die
ist größer, aber nicht unbedingt riesig,

108
00:05:31,659 --> 00:05:33,950
können wir sehen, dass es
eigentlich ein bisschen von einem Unterschied.

109
00:05:33,950 --> 00:05:36,620
Der dritte Algorithmus
wird effizienter.

110
00:05:36,620 --> 00:05:40,120
Es geht darum, tatsächlich 40% -
oder 60% effizienter.

111
00:05:40,120 --> 00:05:41,580
Es dauert 40% der Menge an Zeit.

112
00:05:41,580 --> 00:05:45,250
Es kann run-- es dauern kann
400 Einheiten von Ressourcen

113
00:05:45,250 --> 00:05:47,570
um einen Datensatz der Größe 10 zu verarbeiten.

114
00:05:47,570 --> 00:05:49,410
Während die erste
Algorithmus hingegen

115
00:05:49,410 --> 00:05:54,520
nimmt 1.000 Einheiten von Ressourcen
um einen Datensatz der Größe 10 zu verarbeiten.

116
00:05:54,520 --> 00:05:57,240
Aber schauen Sie, was passiert, als
unsere Zahlen noch größer.

117
00:05:57,240 --> 00:05:59,500
>> Nun wird die Differenz
zwischen diesen Algorithmen

118
00:05:59,500 --> 00:06:01,420
beginnen, etwas weniger deutlich.

119
00:06:01,420 --> 00:06:04,560
Und die Tatsache, dass es
niedrigerer Ordnung terms-- oder besser gesagt,

120
00:06:04,560 --> 00:06:09,390
Begriffe mit niedrigeren exponents--
starten irrelevant zu werden.

121
00:06:09,390 --> 00:06:12,290
Wenn ein Datensatz ist von der Größe
1000 und der erste Algorithmus

122
00:06:12,290 --> 00:06:14,170
läuft in eine Milliarde Schritte.

123
00:06:14,170 --> 00:06:17,880
Und der zweite Algorithmus läuft in
eine Milliarde und eine Million Schritte.

124
00:06:17,880 --> 00:06:20,870
Und der dritte Algorithmus läuft
in knapp einer Milliarde Schritte.

125
00:06:20,870 --> 00:06:22,620
Es ist so ziemlich eine Milliarde Schritte.

126
00:06:22,620 --> 00:06:25,640
Diese Terme niedrigerer Ordnung zu starten
um wirklich irrelevant werden.

127
00:06:25,640 --> 00:06:27,390
Und nur um wirklich
hammer haupt die point--

128
00:06:27,390 --> 00:06:31,240
Wenn der Dateneingang der Größe A
million-- alle drei von ihnen ziemlich viel

129
00:06:31,240 --> 00:06:34,960
nehmen Sie eine quintillion-- wenn
meine Mathe ist correct-- Schritte

130
00:06:34,960 --> 00:06:37,260
mit einem Dateneingang zu verarbeiten
der Größe einer Million.

131
00:06:37,260 --> 00:06:38,250
Das ist eine Menge von Schritten.

132
00:06:38,250 --> 00:06:42,092
Und die Tatsache, dass einer von ihnen könnte
nehmen Sie ein paar 100.000 oder ein paar 100

133
00:06:42,092 --> 00:06:44,650
Millionen noch weniger, wenn
wir über eine Reihe sprechen

134
00:06:44,650 --> 00:06:46,990
dass big-- es irgendwie irrelevant ist.

135
00:06:46,990 --> 00:06:50,006
Sie alle sind in der Regel übernehmen
ca. n in Würfel geschnitten,

136
00:06:50,006 --> 00:06:52,380
und so haben wir eigentlich beziehen würde
Für alle diese Algorithmen

137
00:06:52,380 --> 00:06:59,520
als in der Größenordnung von n
gewürfelt oder Big-O von n gewürfelt.

138
00:06:59,520 --> 00:07:03,220
>> Hier ist eine Liste von einigen der mehr
gemeinsame Komplexitätsklassen

139
00:07:03,220 --> 00:07:05,820
dass wir stoßen in
Algorithmen, in der Regel.

140
00:07:05,820 --> 00:07:07,970
Und auch speziell in CS50.

141
00:07:07,970 --> 00:07:11,410
Diese werden aus bestellt
in der Regel am schnellsten an der Spitze,

142
00:07:11,410 --> 00:07:13,940
allgemein langsamsten an der Unterseite.

143
00:07:13,940 --> 00:07:16,920
So konstante Zeit-Algorithmen sind in der Regel
die am schnellsten zu sein, unabhängig davon,

144
00:07:16,920 --> 00:07:19,110
von der Größe des
Dateneingabe Sie übergeben in.

145
00:07:19,110 --> 00:07:23,760
Sie einem Arbeitsgang erfolgen immer oder
eine Einheit von Ressourcen, zu beschäftigen.

146
00:07:23,760 --> 00:07:25,730
Es kann 2 sein, könnte es
3 sein, könnte es vier sein.

147
00:07:25,730 --> 00:07:26,910
Aber es ist eine konstante Zahl.

148
00:07:26,910 --> 00:07:28,400
Sie ändert sich nicht.

149
00:07:28,400 --> 00:07:31,390
>> Logarithmischen Zeitalgorithmen
sind etwas besser.

150
00:07:31,390 --> 00:07:33,950
Und ein wirklich gutes Beispiel dafür,
einen logarithmischen Algorithmus

151
00:07:33,950 --> 00:07:37,420
Sie haben sicherlich inzwischen gesehen, ist die
Auseinanderreißen des Telefonbuchs

152
00:07:37,420 --> 00:07:39,480
Mike Smith im Telefonbuch zu finden.

153
00:07:39,480 --> 00:07:40,980
Wir schneiden das Problem in zwei Hälften.

154
00:07:40,980 --> 00:07:43,580
Und so, n größer wird
und größer und larger--

155
00:07:43,580 --> 00:07:47,290
in der Tat, jedes Mal wenn Sie verdoppeln
n, dauert es nur noch ein Schritt.

156
00:07:47,290 --> 00:07:49,770
Also das ist viel besser
als, sagen wir, die lineare Zeit.

157
00:07:49,770 --> 00:07:53,030
Das ist, wenn Sie n verdoppeln, es
nimmt die doppelte Anzahl von Schritten.

158
00:07:53,030 --> 00:07:55,980
Wenn Sie n verdreifachen, dauert es
Verdreifachung der Anzahl der Schritte.

159
00:07:55,980 --> 00:07:58,580
Einen Schritt pro Einheit.

160
00:07:58,580 --> 00:08:01,790
>> Dann wird es ein wenig more--
etwas weniger von dort super.

161
00:08:01,790 --> 00:08:06,622
Sie haben lineare rhythmische Zeit, manchmal
genannt log lineare Zeit oder einfach nur n log n.

162
00:08:06,622 --> 00:08:08,330
Und wir werden ein Beispiel
eines Algorithmus,

163
00:08:08,330 --> 00:08:13,370
läuft in n log n, die noch besser ist,
als quadratische Zeit-- n quadriert.

164
00:08:13,370 --> 00:08:17,320
Oder polynomialer Zeit, n zwei
beliebige Zahl größer als zwei ist.

165
00:08:17,320 --> 00:08:20,810
Oder exponentieller Zeit, die
Noch C bis worse-- der n.

166
00:08:20,810 --> 00:08:24,670
So angehoben einige konstante Anzahl
die Leistung der Größe der Eingabe.

167
00:08:24,670 --> 00:08:28,990
Also, wenn es 1,000-- wenn die
Dateneingabe der Größe 1000,

168
00:08:28,990 --> 00:08:31,310
sie zur Preis 1000. Macht zu übernehmen C.

169
00:08:31,310 --> 00:08:33,559
Es ist viel schlimmer als Polynomialzeit.

170
00:08:33,559 --> 00:08:35,030
>> Factorial Es ist noch schlimmer.

171
00:08:35,030 --> 00:08:37,760
Und in der Tat, es gibt wirklich tun
existieren unendliche Zeit-Algorithmen,

172
00:08:37,760 --> 00:08:43,740
wie beispielsweise so genannte dumme sort-- deren
Aufgabe ist es, nach dem Zufallsprinzip Shuffle ein Array

173
00:08:43,740 --> 00:08:45,490
und dann überprüfen Sie,
ob es sortiert.

174
00:08:45,490 --> 00:08:47,589
Und wenn es nicht, nach dem Zufallsprinzip
mische das Array wieder

175
00:08:47,589 --> 00:08:49,130
und überprüfen Sie, ob es sortiert.

176
00:08:49,130 --> 00:08:51,671
Und wie Sie wahrscheinlich imagine-- können
Sie können eine Situation vorstellen,

177
00:08:51,671 --> 00:08:55,200
wobei im schlimmsten Fall, dass Wille
nie wirklich mit dem Array zu starten.

178
00:08:55,200 --> 00:08:57,150
Das Algorithmus würde ewig laufen.

179
00:08:57,150 --> 00:08:59,349
Und damit wäre ein
unendliche Zeit-Algorithmus.

180
00:08:59,349 --> 00:09:01,890
Hoffentlich werden Sie nicht zu schreiben
jede Fakultät oder unendliche Zeit

181
00:09:01,890 --> 00:09:04,510
Algorithmen in CS50.

182
00:09:04,510 --> 00:09:09,150
>> Also, lassen Sie uns ein wenig mehr
Beton Blick auf einige einfachere

183
00:09:09,150 --> 00:09:11,154
Komplexitätsklassen.

184
00:09:11,154 --> 00:09:13,070
So haben wir eine example--
oder zwei Beispiele hier--

185
00:09:13,070 --> 00:09:15,590
der konstante Zeitalgorithmen,
die immer nehmen

186
00:09:15,590 --> 00:09:17,980
eine einzige Operation in der Worst-Case.

187
00:09:17,980 --> 00:09:20,050
So die erste example--
wir eine Funktion haben

188
00:09:20,050 --> 00:09:23,952
genannt 4 für Sie, die
nimmt ein Array der Größe 1.000.

189
00:09:23,952 --> 00:09:25,660
Aber dann offenbar
nicht wirklich aussehen

190
00:09:25,660 --> 00:09:29,000
bei es-- nicht wirklich, was ist
innen von ihm, dieses Arrays.

191
00:09:29,000 --> 00:09:30,820
Immer nur liefert vier.

192
00:09:30,820 --> 00:09:32,940
So, dass Algorithmus
trotz der Tatsache, daß es

193
00:09:32,940 --> 00:09:35,840
nimmt 1000 Elemente nicht
nichts mit ihnen.

194
00:09:35,840 --> 00:09:36,590
Nur gibt vier.

195
00:09:36,590 --> 00:09:38,240
Es ist immer ein Schritt.

196
00:09:38,240 --> 00:09:41,600
>> In der Tat, fügen Sie 2 nums-- die
wir zuvor als well-- gesehen haben

197
00:09:41,600 --> 00:09:43,680
gerade verarbeitet zwei ganzen Zahlen.

198
00:09:43,680 --> 00:09:44,692
Es ist nicht ein Schritt.

199
00:09:44,692 --> 00:09:45,900
Es ist eigentlich ein paar Schritte.

200
00:09:45,900 --> 00:09:50,780
Sie erhalten ein, erhalten Sie b, Sie sie hinzufügen
zusammen, und du Ausgabe der Ergebnisse.

201
00:09:50,780 --> 00:09:53,270
So ist es 84 Stufen.

202
00:09:53,270 --> 00:09:55,510
Aber es ist immer konstant,
unabhängig von a oder b.

203
00:09:55,510 --> 00:09:59,240
Du musst ein, bekommen b, fügen
sie zusammen, das Ergebnis auszugeben.

204
00:09:59,240 --> 00:10:02,900
Also das ist eine konstante Zeit-Algorithmus.

205
00:10:02,900 --> 00:10:05,170
>> Hier ist ein Beispiel für ein
linearen Zeit algorithm--

206
00:10:05,170 --> 00:10:08,740
ein Algorithmus, der gets-- das braucht
einen zusätzlichen Schritt, gegebenenfalls,

207
00:10:08,740 --> 00:10:10,740
wie Ihr Eingangs wächst um 1.

208
00:10:10,740 --> 00:10:14,190
Also, sagen wir, wir suchen
die Nummer 5 innerhalb eines Arrays.

209
00:10:14,190 --> 00:10:16,774
Vielleicht haben Sie eine Situation, wo haben
Sie ziemlich früh zu finden.

210
00:10:16,774 --> 00:10:18,606
Aber Sie haben auch könnte
eine Situation, wo es

211
00:10:18,606 --> 00:10:20,450
könnte das letzte Element des Arrays.

212
00:10:20,450 --> 00:10:23,780
In einer Anordnung von der Größe 5, wenn
wir sind für die Zahl 5 suchen.

213
00:10:23,780 --> 00:10:25,930
Es würde 5 Stufen.

214
00:10:25,930 --> 00:10:29,180
Und in der Tat, sich vorstellen, dass es
5 nicht überall in diesem Array.

215
00:10:29,180 --> 00:10:32,820
Wir haben immer noch tatsächlich haben, zu betrachten
Jedes einzelne Element des Arrays

216
00:10:32,820 --> 00:10:35,550
um zu bestimmen,
ob oder ob nicht 5 ist da.

217
00:10:35,550 --> 00:10:39,840
>> Also im ungünstigsten Fall, der das ist
das Element in dem Array letzten

218
00:10:39,840 --> 00:10:41,700
oder überhaupt nicht existieren.

219
00:10:41,700 --> 00:10:44,690
Wir haben immer noch zu sehen
alle der n Elemente.

220
00:10:44,690 --> 00:10:47,120
Und so dieser Algorithmus
läuft in linearer Zeit.

221
00:10:47,120 --> 00:10:50,340
Sie können das bestätigen
Extrapolation ein wenig mit den Worten:

222
00:10:50,340 --> 00:10:53,080
wenn wir eine 6-Element-Array und
wurden wir für die Zahl 5 suchen,

223
00:10:53,080 --> 00:10:54,890
sie treffen könnte, 6 Stufen.

224
00:10:54,890 --> 00:10:57,620
Wenn wir eine 7-Elementanordnung und
wir sind für die Zahl 5 suchen.

225
00:10:57,620 --> 00:10:59,160
Es könnte dauern 7 Schritten.

226
00:10:59,160 --> 00:11:02,920
Da wir ein weiteres Element hinzuzufügen, um unsere
Array, dauert es noch ein Schritt.

227
00:11:02,920 --> 00:11:06,750
Das ist ein linearer Algorithmus
im ungünstigsten Fall.

228
00:11:06,750 --> 00:11:08,270
>> Paar kurze Fragen für Sie.

229
00:11:08,270 --> 00:11:11,170
Was ist der runtime-- was ist
das Worst-Case-Laufzeit

230
00:11:11,170 --> 00:11:13,700
dieses bestimmten Code-Snippet?

231
00:11:13,700 --> 00:11:17,420
So habe ich eine 4-Schleife, die hier läuft
von j gleich 0 ist, den ganzen Weg bis zum m.

232
00:11:17,420 --> 00:11:21,980
Und was ich hier sehen, ist, dass die
Rumpf der Schleife läuft in konstanter Zeit.

233
00:11:21,980 --> 00:11:24,730
So mit der Terminologie,
wir haben bereits about-- was gesprochen

234
00:11:24,730 --> 00:11:29,390
würde im schlimmsten Fall sein,
Laufzeit dieses Algorithmus?

235
00:11:29,390 --> 00:11:31,050
Nehmen Sie eine Sekunde.

236
00:11:31,050 --> 00:11:34,270
Der innere Teil der Schleife
läuft in konstanter Zeit.

237
00:11:34,270 --> 00:11:37,510
Und der äußere Teil der
Schleife wird sich m-mal ausgeführt.

238
00:11:37,510 --> 00:11:40,260
Also, was ist das Worst-Case-Laufzeit hier?

239
00:11:40,260 --> 00:11:43,210
Haben Sie Big-O von m erraten?

240
00:11:43,210 --> 00:11:44,686
Sie würden Recht haben.

241
00:11:44,686 --> 00:11:46,230
>> Wie wäre es mit einem anderen?

242
00:11:46,230 --> 00:11:48,590
Dieses Mal haben wir ein
Schleife innerhalb einer Schleife.

243
00:11:48,590 --> 00:11:50,905
Wir haben eine äußere Schleife
das läuft von null auf p.

244
00:11:50,905 --> 00:11:54,630
Und wir haben eine innere Schleife, die läuft
von Null auf P, und im Inneren davon,

245
00:11:54,630 --> 00:11:57,890
Ich behaupte, dass der Körper die
Schleife läuft in konstanter Zeit.

246
00:11:57,890 --> 00:12:02,330
Also, was ist das Worst-Case-Laufzeit
dieses bestimmten Code-Snippet?

247
00:12:02,330 --> 00:12:06,140
Nun, wieder haben wir ein
äußere Schleife, die p-mal ausgeführt wird.

248
00:12:06,140 --> 00:12:09,660
Und jeder Iteration Zeit--
dieser Schleife statt.

249
00:12:09,660 --> 00:12:13,170
Wir haben eine innere Schleife
dass auch läuft p Zeiten.

250
00:12:13,170 --> 00:12:16,900
Und dann im Inneren der, dass, gibt es das
Konstante Zeit-- kleine Ausschnitt gibt.

251
00:12:16,900 --> 00:12:19,890
>> Wenn wir also eine äußere Schleife,
läuft p-mal innerhalb von denen ist

252
00:12:19,890 --> 00:12:22,880
eine innere Schleife,
läuft p times-- was

253
00:12:22,880 --> 00:12:26,480
das Worst-Case-Laufzeit
dieser Code-Snippet?

254
00:12:26,480 --> 00:12:30,730
Haben Sie big-O p denke Quadrat?

255
00:12:30,730 --> 00:12:31,690
>> Ich bin Doug Lloyd.

256
00:12:31,690 --> 00:12:33,880
Dies ist CS50.

257
00:12:33,880 --> 00:12:35,622