1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] U hebt waarschijnlijk gehoord mensen praten over een snelle of efficiënt algoritme

2
00:00:10,950 --> 00:00:13,090
voor het uitvoeren van uw specifieke taak,

3
00:00:13,090 --> 00:00:16,110
maar wat precies betekent het voor een algoritme om snel en efficiënt?

4
00:00:16,110 --> 00:00:18,580
Nou, het is niet over een meting in real-time,

5
00:00:18,580 --> 00:00:20,500
zoals seconden of minuten.

6
00:00:20,500 --> 00:00:22,220
Dit komt doordat computer hardware

7
00:00:22,220 --> 00:00:24,260
en software variëren sterk.

8
00:00:24,260 --> 00:00:26,020
Mijn programma zou kunnen lopen langzamer dan die van jou,

9
00:00:26,020 --> 00:00:28,000
want ik ben het runnen van het op een oudere computer,

10
00:00:28,000 --> 00:00:30,110
of omdat ik toevallig te spelen van een online video game

11
00:00:30,110 --> 00:00:32,670
tegelijkertijd wordt die Noteer alle mijn geheugen,

12
00:00:32,670 --> 00:00:35,400
of ik zou kunnen lopen mijn programma door middel van verschillende software

13
00:00:35,400 --> 00:00:37,550
die communiceert met de machine anders op een laag niveau.

14
00:00:37,550 --> 00:00:39,650
Het is als het vergelijken van appels met peren.

15
00:00:39,650 --> 00:00:41,940
Gewoon omdat mijn langzamere computer duurt langer

16
00:00:41,940 --> 00:00:43,410
dan de jouwe terug te geven een antwoord

17
00:00:43,410 --> 00:00:45,510
betekent niet dat je hebt hoe meer efficiënt algoritme.

18
00:00:45,510 --> 00:00:48,830
>> Dus, omdat we niet direct vergelijken met de looptijden van de programma's

19
00:00:48,830 --> 00:00:50,140
in seconden of minuten,

20
00:00:50,140 --> 00:00:52,310
hoe kunnen we vergelijken 2 verschillende algoritmen

21
00:00:52,310 --> 00:00:55,030
ongeacht hun hardware-of software-omgeving?

22
00:00:55,030 --> 00:00:58,000
Om een ​​meer uniforme manier van meten algoritmische efficiëntie te creëren,

23
00:00:58,000 --> 00:01:00,360
informatici en wiskundigen hebben bedacht

24
00:01:00,360 --> 00:01:03,830
concepten voor het meten van de asymptotische complexiteit van een programma

25
00:01:03,830 --> 00:01:06,110
en een notatie genaamd 'Big Ohnotation'

26
00:01:06,110 --> 00:01:08,320
voor het beschrijven deze.

27
00:01:08,320 --> 00:01:10,820
De formele definitie is dat een functie f (x)

28
00:01:10,820 --> 00:01:13,390
uitgevoerd in de orde van g (x)

29
00:01:13,390 --> 00:01:15,140
dan als er een paar (x) waarde, x ₀ en

30
00:01:15,140 --> 00:01:17,630
een constante, C, waarbij

31
00:01:17,630 --> 00:01:19,340
f (x) kleiner dan of gelijk aan

32
00:01:19,340 --> 00:01:21,230
constante maal dat g (x)

33
00:01:21,230 --> 00:01:23,190
voor alle x groter is dan x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Maar laat u niet afschrikken door de formele definitie.

35
00:01:25,290 --> 00:01:28,020
Wat betekent dit eigenlijk in minder theoretische termen?

36
00:01:28,020 --> 00:01:30,580
Nou, het is in feite een manier van het analyseren van

37
00:01:30,580 --> 00:01:33,580
hoe snel een programma runtime asymptotisch groeit.

38
00:01:33,580 --> 00:01:37,170
Dat is, zoals de grootte van uw input verhoogt naar oneindigheid,

39
00:01:37,170 --> 00:01:41,390
zeggen, je sorteren een array van grootte 1000 vergeleken met een array van grootte 10.

40
00:01:41,390 --> 00:01:44,950
Hoe verhoudt de looptijd van uw programma te laten groeien?

41
00:01:44,950 --> 00:01:47,390
Stel bijvoorbeeld het tellen van het aantal tekens

42
00:01:47,390 --> 00:01:49,350
in een string de eenvoudigste manier

43
00:01:49,350 --> 00:01:51,620
 door een wandeling door de hele reeks

44
00:01:51,620 --> 00:01:54,790
letter-voor-letter en het toevoegen van 1 tot en met een teller voor elk karakter.

45
00:01:55,700 --> 00:01:58,420
Dit algoritme wordt gezegd om te draaien in lineaire tijd

46
00:01:58,420 --> 00:02:00,460
met betrekking tot het aantal tekens,

47
00:02:00,460 --> 00:02:02,670
'N' in de tekenreeks.

48
00:02:02,670 --> 00:02:04,910
Kortom, het loopt in O (n).

49
00:02:05,570 --> 00:02:07,290
Hoe komt dat?

50
00:02:07,290 --> 00:02:09,539
Nou, met behulp van deze aanpak, de tijd die nodig is

51
00:02:09,539 --> 00:02:11,300
om de gehele tekenreeks doorkruisen

52
00:02:11,300 --> 00:02:13,920
evenredig is met het aantal tekens.

53
00:02:13,920 --> 00:02:16,480
Tellen van het aantal tekens in een 20-tekenreeks

54
00:02:16,480 --> 00:02:18,580
gaat twee keer zo lang als nodig is

55
00:02:18,580 --> 00:02:20,330
om de tekens te tellen in een 10-tekenreeks,

56
00:02:20,330 --> 00:02:23,000
want je moet kijken naar alle tekens

57
00:02:23,000 --> 00:02:25,740
en elk teken is dezelfde hoeveelheid tijd te zien.

58
00:02:25,740 --> 00:02:28,050
Als u het aantal tekens,

59
00:02:28,050 --> 00:02:30,950
de runtime zal lineair toeneemt met de ingang lengte.

60
00:02:30,950 --> 00:02:33,500
>> Nu, stel je voor dat je besluit dat lineaire tijd,

61
00:02:33,500 --> 00:02:36,390
O (n), was gewoon niet snel genoeg voor jou?

62
00:02:36,390 --> 00:02:38,750
Misschien bent u het opslaan van grote strijkers,

63
00:02:38,750 --> 00:02:40,450
en je kunt niet veroorloven de extra tijd die het zou kosten

64
00:02:40,450 --> 00:02:44,000
al hun tekens tellen een voor een passeren.

65
00:02:44,000 --> 00:02:46,650
Dus, je besluit om iets anders te proberen.

66
00:02:46,650 --> 00:02:49,270
Wat als je zou er gebeuren met al slaan het aantal tekens

67
00:02:49,270 --> 00:02:52,690
in de string, bijvoorbeeld in een variabele met de naam 'len,'

68
00:02:52,690 --> 00:02:54,210
vroeg in het programma,

69
00:02:54,210 --> 00:02:57,800
voordat je zelfs opgeslagen het eerste teken in je string?

70
00:02:57,800 --> 00:02:59,980
Dan, alles wat je zou nu moeten doen om uit te vinden de lengte van het touw,

71
00:02:59,980 --> 00:03:02,570
is na te gaan wat de waarde van de variabele is.

72
00:03:02,570 --> 00:03:05,530
Je zou het niet moeten kijken naar de string zelf helemaal niet,

73
00:03:05,530 --> 00:03:08,160
en toegang tot de waarde van een variabele zoals len beschouwd

74
00:03:08,160 --> 00:03:11,100
een asymptotisch constante tijd operatie,

75
00:03:11,100 --> 00:03:13,070
of O (1).

76
00:03:13,070 --> 00:03:17,110
Hoe komt dat? Nou, onthoud wat asymptotische complexiteit betekent.

77
00:03:17,110 --> 00:03:19,100
Hoe werkt de runtime verandering als de grootte

78
00:03:19,100 --> 00:03:21,400
van uw ingangen groeit?

79
00:03:21,400 --> 00:03:24,630
>> Zeg dat je probeerde het aantal tekens in een grotere reeks te krijgen.

80
00:03:24,630 --> 00:03:26,960
Nou, het zou niet uit hoe groot je de snaar te maken,

81
00:03:26,960 --> 00:03:28,690
zelfs een miljoen tekens lang zijn,

82
00:03:28,690 --> 00:03:31,150
alles wat je zou moeten doen om de snaar lengte met deze aanpak te vinden,

83
00:03:31,150 --> 00:03:33,790
is het uitlezen van de waarde van de variabele len,

84
00:03:33,790 --> 00:03:35,440
die je al gemaakt.

85
00:03:35,440 --> 00:03:38,200
De input lengte is, dat de lengte van de tekenreeks u probeert te vinden,

86
00:03:38,200 --> 00:03:41,510
heeft geen invloed op helemaal hoe snel je programma draait.

87
00:03:41,510 --> 00:03:44,550
Dit deel van uw programma zou even snel draaien op een one-tekenreeks

88
00:03:44,550 --> 00:03:46,170
en duizend-tekenreeks,

89
00:03:46,170 --> 00:03:49,140
en dat is waarom dit programma zou worden aangeduid als lopen in constante tijd

90
00:03:49,140 --> 00:03:51,520
met betrekking tot de input-maat.

91
00:03:51,520 --> 00:03:53,920
>> Natuurlijk, er is een nadeel.

92
00:03:53,920 --> 00:03:55,710
U besteedt extra geheugenruimte op uw computer

93
00:03:55,710 --> 00:03:57,380
opslaan van de variabele

94
00:03:57,380 --> 00:03:59,270
en de extra tijd die je nodig hebt

95
00:03:59,270 --> 00:04:01,490
de feitelijke opslag van de variabele do,

96
00:04:01,490 --> 00:04:03,390
maar het punt staat stil,

97
00:04:03,390 --> 00:04:05,060
het vinden van hoe lang uw snaar was

98
00:04:05,060 --> 00:04:07,600
niet af van de lengte van de tekenreeks helemaal.

99
00:04:07,600 --> 00:04:10,720
Dus, het loopt in O (1) of constante tijd.

100
00:04:10,720 --> 00:04:13,070
Dit hoeft zeker niet te betekenen

101
00:04:13,070 --> 00:04:15,610
dat uw code wordt uitgevoerd in 1 stap,

102
00:04:15,610 --> 00:04:17,470
maar maakt niet uit hoeveel stappen het is,

103
00:04:17,470 --> 00:04:20,019
indien niet verandert met de grootte van de ingangen,

104
00:04:20,019 --> 00:04:23,420
het is nog steeds asymptotisch constante die wij vertegenwoordigen als O (1).

105
00:04:23,420 --> 00:04:25,120
>> Zoals je waarschijnlijk wel kunt raden,

106
00:04:25,120 --> 00:04:27,940
er zijn veel verschillende grote O runtimes om algoritmen te meten met.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmen asymptotisch langzamer dan O (n) algoritmen.

108
00:04:32,980 --> 00:04:35,910
Dat is, zoals het aantal elementen (n) groeit,

109
00:04:35,910 --> 00:04:39,280
uiteindelijk O (n) ² algoritmes kost meer tijd

110
00:04:39,280 --> 00:04:41,000
dan O (n) algoritmen uit te voeren.

111
00:04:41,000 --> 00:04:43,960
Dit betekent niet dat O (n) algoritme altijd sneller lopen

112
00:04:43,960 --> 00:04:46,410
dan O (n) ² algoritmen, zelfs in dezelfde omgeving,

113
00:04:46,410 --> 00:04:48,080
op dezelfde hardware.

114
00:04:48,080 --> 00:04:50,180
Misschien voor kleine ingang maten,

115
00:04:50,180 --> 00:04:52,900
 de O (n) ² algoritme misschien wel sneller werken,

116
00:04:52,900 --> 00:04:55,450
maar, uiteindelijk, als de input grootte toenemen

117
00:04:55,450 --> 00:04:58,760
naar het oneindige, de O (n) ² algoritme runtime

118
00:04:58,760 --> 00:05:02,000
zal uiteindelijk overschaduwen de looptijd van de O (n) algoritme.

119
00:05:02,000 --> 00:05:04,230
Net als elke kwadratische wiskundige functie

120
00:05:04,230 --> 00:05:06,510
 zal uiteindelijk inhalen elke lineaire functie,

121
00:05:06,510 --> 00:05:09,200
maakt niet uit hoe veel van een voorsprong de lineaire functie begint met.

122
00:05:10,010 --> 00:05:12,000
Als u werkt met grote hoeveelheden gegevens,

123
00:05:12,000 --> 00:05:15,510
algoritmen die worden uitgevoerd in O (n) ² tijd kan echt uiteindelijk vertragen van uw programma,

124
00:05:15,510 --> 00:05:17,770
maar voor kleine ingang maten,

125
00:05:17,770 --> 00:05:19,420
zal je waarschijnlijk niet eens merken.

126
00:05:19,420 --> 00:05:21,280
>> Een asymptotische complexiteit,

127
00:05:21,280 --> 00:05:24,420
logaritmische tijd, O (log n).

128
00:05:24,420 --> 00:05:26,340
Een voorbeeld van een algoritme dat deze verloopt snel

129
00:05:26,340 --> 00:05:29,060
is de klassieke binaire zoekalgoritme,

130
00:05:29,060 --> 00:05:31,850
voor het vinden van een element in een reeds gesorteerde lijst van elementen.

131
00:05:31,850 --> 00:05:33,400
>> Als je niet weet wat binary search doet,

132
00:05:33,400 --> 00:05:35,170
Ik leg het voor u heel snel.

133
00:05:35,170 --> 00:05:37,020
Laten we zeggen dat je op zoek bent naar het getal 3

134
00:05:37,020 --> 00:05:40,200
in deze array van integers.

135
00:05:40,200 --> 00:05:42,140
Het ziet er in het midden element van de array

136
00:05:42,140 --> 00:05:46,830
en vraagt: "Is het element wil ik groter dan, gelijk aan of kleiner is dan dit?"

137
00:05:46,830 --> 00:05:49,150
Als het gelijk, dan groot. Je vond het element, en je bent klaar.

138
00:05:49,150 --> 00:05:51,300
Als het groter is, dan weet je het element

139
00:05:51,300 --> 00:05:53,440
moet in de rechterzijde van de array,

140
00:05:53,440 --> 00:05:55,200
en je kunt alleen kijken naar dat in de toekomst,

141
00:05:55,200 --> 00:05:57,690
en als het kleiner is, dan weet je het moet aan de linkerkant.

142
00:05:57,690 --> 00:06:00,980
Dit proces wordt vervolgens herhaald met de kleinere grootte matrix

143
00:06:00,980 --> 00:06:02,870
totdat de juiste element wordt gevonden.

144
00:06:08,080 --> 00:06:11,670
>> Deze krachtige algoritme snijdt de array size in de helft na elke handeling.

145
00:06:11,670 --> 00:06:14,080
Dus, om een ​​element te vinden in een gesorteerde array van maat 8,

146
00:06:14,080 --> 00:06:16,170
bij de meeste (log ₂ 8),

147
00:06:16,170 --> 00:06:18,450
of 3 van deze operaties,

148
00:06:18,450 --> 00:06:22,260
controleren van de middelste element, dan snijden de array in half is vereist,

149
00:06:22,260 --> 00:06:25,670
terwijl een array van grootte 16 heeft (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
of 4 operaties.

151
00:06:27,480 --> 00:06:30,570
Dat is slechts 1 meer bediening voor een dubbele-size array.

152
00:06:30,570 --> 00:06:32,220
Verdubbeling van de array

153
00:06:32,220 --> 00:06:35,160
verhoogt de looptijd met slechts 1 stuk van deze code.

154
00:06:35,160 --> 00:06:37,770
Nogmaals, het controleren van de middelste element van de lijst, dan splitsen.

155
00:06:37,770 --> 00:06:40,440
Dus, het is gezegd om te werken in logaritmische tijd,

156
00:06:40,440 --> 00:06:42,440
O (log n).

157
00:06:42,440 --> 00:06:44,270
Maar wacht, u zegt,

158
00:06:44,270 --> 00:06:47,510
niet dit is afhankelijk van waar in de lijst het element dat u zoekt is?

159
00:06:47,510 --> 00:06:50,090
Wat als het eerste element je kijkt naar toevallig ook de juiste?

160
00:06:50,090 --> 00:06:52,040
Dan, het duurt maar 1 operatie,

161
00:06:52,040 --> 00:06:54,310
maakt niet uit hoe groot de lijst is.

162
00:06:54,310 --> 00:06:56,310
>> Nou, dat is waarom informatici hebben meer termen

163
00:06:56,310 --> 00:06:58,770
voor asymptotische complexiteit die het best-case weerspiegelen

164
00:06:58,770 --> 00:07:01,050
en worst-case prestaties van een algoritme.

165
00:07:01,050 --> 00:07:03,320
Beter gezegd, de boven-en ondergrenzen

166
00:07:03,320 --> 00:07:05,090
op de runtime.

167
00:07:05,090 --> 00:07:07,660
In het beste geval voor binaire zoeken, ons element is

168
00:07:07,660 --> 00:07:09,330
daar in het midden,

169
00:07:09,330 --> 00:07:11,770
en je krijgt het in constante tijd,

170
00:07:11,770 --> 00:07:14,240
ongeacht hoe groot de rest van de matrix.

171
00:07:15,360 --> 00:07:17,650
Het symbool voor dit Ω.

172
00:07:17,650 --> 00:07:19,930
Dus, is dit algoritme gezegd om te draaien in Ω (1).

173
00:07:19,930 --> 00:07:21,990
In het beste geval, het vindt het element snel,

174
00:07:21,990 --> 00:07:24,200
maakt niet uit hoe groot de array,

175
00:07:24,200 --> 00:07:26,050
maar in het ergste geval,

176
00:07:26,050 --> 00:07:28,690
het heeft uit te voeren (log n) split controles

177
00:07:28,690 --> 00:07:31,030
van de matrix om de juiste element vinden.

178
00:07:31,030 --> 00:07:34,270
Worst-case bovengrenzen worden aangeduid met de grote "O" die je al kent.

179
00:07:34,270 --> 00:07:38,080
Dus, het is O (log n), maar Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Een lineair zoeken daarentegen

181
00:07:40,680 --> 00:07:43,220
in waarin je door elk element van de array

182
00:07:43,220 --> 00:07:45,170
aan degene die je wilt vinden,

183
00:07:45,170 --> 00:07:47,420
is best Ω (1).

184
00:07:47,420 --> 00:07:49,430
Nogmaals, het eerste element dat u wilt.

185
00:07:49,430 --> 00:07:51,930
Het maakt dus niet uit hoe groot de array is.

186
00:07:51,930 --> 00:07:54,840
In het ergste geval, het is het laatste element in de array.

187
00:07:54,840 --> 00:07:58,560
Dus, je moet je door alle n elementen in de array om het te vinden,

188
00:07:58,560 --> 00:08:02,170
graag als je op zoek naar een 3.

189
00:08:04,320 --> 00:08:06,030
Dus, het loopt in O (n) tijd

190
00:08:06,030 --> 00:08:09,330
omdat het evenredig aan het aantal elementen in de array.

191
00:08:10,800 --> 00:08:12,830
>> Een meer gebruikt symbool Θ.

192
00:08:12,830 --> 00:08:15,820
Dit kan worden gebruikt om algoritmen waar de beste en slechtste geval beschrijven

193
00:08:15,820 --> 00:08:17,440
dezelfde.

194
00:08:17,440 --> 00:08:20,390
Dit is het geval in de string-length algoritmen hebben we het eerder over had.

195
00:08:20,390 --> 00:08:22,780
Dat wil zeggen, als we het op te slaan in een variabele voor

196
00:08:22,780 --> 00:08:25,160
slaan we de string en de toegang later in constante tijd.

197
00:08:25,160 --> 00:08:27,920
Het maakt niet uit welk nummer

198
00:08:27,920 --> 00:08:30,130
we opslaan in de variabele, zullen we moeten kijken.

199
00:08:33,110 --> 00:08:35,110
Het beste geval is, kijken we naar het

200
00:08:35,110 --> 00:08:37,120
en vind de lengte van de tekenreeks.

201
00:08:37,120 --> 00:08:39,799
Dus Ω (1) of best-case constante tijd.

202
00:08:39,799 --> 00:08:41,059
Het ergste geval is,

203
00:08:41,059 --> 00:08:43,400
we kijken ernaar en vind de lengte van de string.

204
00:08:43,400 --> 00:08:47,300
Dus, O (1) of constante tijd in het ergste geval.

205
00:08:47,300 --> 00:08:49,180
Dus, aangezien de beste en slechtste geval gevallen hetzelfde,

206
00:08:49,180 --> 00:08:52,520
Dit kan worden gezegd om te draaien in Θ (1) tijd.

207
00:08:54,550 --> 00:08:57,010
>> Kortom, we hebben goede manieren om te redeneren over codes efficiëntie

208
00:08:57,010 --> 00:09:00,110
zonder iets te weten over de echte wereld tijd die zij nemen om te draaien,

209
00:09:00,110 --> 00:09:02,270
die wordt beïnvloed door vele factoren van buitenaf,

210
00:09:02,270 --> 00:09:04,190
waaronder verschillende hardware, software,

211
00:09:04,190 --> 00:09:06,040
of de specifieke kenmerken van uw code.

212
00:09:06,040 --> 00:09:08,380
Ook is het ons in staat stelt om goed te redeneren over wat er zal gebeuren

213
00:09:08,380 --> 00:09:10,180
wanneer de omvang van de ingangen toeneemt.

214
00:09:10,180 --> 00:09:12,490
>> Als u gebruik maakt van O (n) ² algoritme,

215
00:09:12,490 --> 00:09:15,240
of erger nog, een O (2 ⁿ) algoritme,

216
00:09:15,240 --> 00:09:17,170
een van de snelst groeiende types,

217
00:09:17,170 --> 00:09:19,140
je zult echt beginnen aan de vertraging merken

218
00:09:19,140 --> 00:09:21,220
wanneer u begint te werken met grotere hoeveelheden data.

219
00:09:21,220 --> 00:09:23,590
>> Dat is asymptotische complexiteit. Bedankt.