1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Du har sikkert hørt folk tale om en hurtig eller effektiv algoritme

2
00:00:10,950 --> 00:00:13,090
for at gennemføre netop din opgave,

3
00:00:13,090 --> 00:00:16,110
men hvad betyder det for en algoritme til at være hurtig eller effektiv?

4
00:00:16,110 --> 00:00:18,580
Tja, det er ikke tale om en måling i realtid,

5
00:00:18,580 --> 00:00:20,500
lignende sekunder eller minutter.

6
00:00:20,500 --> 00:00:22,220
Dette skyldes computerhardware

7
00:00:22,220 --> 00:00:24,260
og software varierer drastisk.

8
00:00:24,260 --> 00:00:26,020
Mit program kan køre langsommere end dit,

9
00:00:26,020 --> 00:00:28,000
fordi jeg kører det på en ældre computer,

10
00:00:28,000 --> 00:00:30,110
eller fordi jeg tilfældigvis skal spille en online video game

11
00:00:30,110 --> 00:00:32,670
på samme tid, som er hogging al min hukommelse,

12
00:00:32,670 --> 00:00:35,400
eller jeg kan køre mit program gennem forskellige software

13
00:00:35,400 --> 00:00:37,550
som kommunikerer med maskinen forskelligt på et lavt niveau.

14
00:00:37,550 --> 00:00:39,650
Det er som at sammenligne æbler og appelsiner.

15
00:00:39,650 --> 00:00:41,940
Bare fordi min langsommere computer tager længere tid

16
00:00:41,940 --> 00:00:43,410
end din at give tilbage et svar

17
00:00:43,410 --> 00:00:45,510
betyder ikke, du har, jo mere effektiv algoritme.

18
00:00:45,510 --> 00:00:48,830
>> Så da vi ikke direkte kan sammenligne de runtime af programmer

19
00:00:48,830 --> 00:00:50,140
i sekunder eller minutter,

20
00:00:50,140 --> 00:00:52,310
hvordan kan vi sammenligne 2 forskellige algoritmer

21
00:00:52,310 --> 00:00:55,030
uanset deres hardware eller software miljø?

22
00:00:55,030 --> 00:00:58,000
At skabe et mere ensartet måde at måle algoritmisk effektivitet,

23
00:00:58,000 --> 00:01:00,360
dataloger og matematikere har udtænkt

24
00:01:00,360 --> 00:01:03,830
koncepter til måling af asymptotiske kompleksitet et program

25
00:01:03,830 --> 00:01:06,110
og en notation kaldet 'Big Ohnotation'

26
00:01:06,110 --> 00:01:08,320
til beskrivelse af dette.

27
00:01:08,320 --> 00:01:10,820
Den formelle definition er, at en funktion f (x)

28
00:01:10,820 --> 00:01:13,390
kører i størrelsesordenen g (x)

29
00:01:13,390 --> 00:01:15,140
Hvis der findes en (x) værdi, x ₀ og

30
00:01:15,140 --> 00:01:17,630
eller anden konstant, C, for hvilke

31
00:01:17,630 --> 00:01:19,340
f (x) er mindre end eller lig med

32
00:01:19,340 --> 00:01:21,230
at konstant gange g (x)

33
00:01:21,230 --> 00:01:23,190
for alle x større end x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Men du skal ikke blive skræmt væk af den formelle definition.

35
00:01:25,290 --> 00:01:28,020
Hvad betyder dette egentlig betyder i mindre teoretiske termer?

36
00:01:28,020 --> 00:01:30,580
Tja, det er dybest set en måde at analysere

37
00:01:30,580 --> 00:01:33,580
hvor hurtigt et program runtime vokser asymptotisk.

38
00:01:33,580 --> 00:01:37,170
Det er, som størrelsen på dine input øges mod uendeligheden,

39
00:01:37,170 --> 00:01:41,390
sige, du sortering et array af størrelse 1000 i forhold til et array af størrelse 10.

40
00:01:41,390 --> 00:01:44,950
Hvordan runtime af dit program vokse?

41
00:01:44,950 --> 00:01:47,390
For eksempel forestille sig at tælle antallet af tegn

42
00:01:47,390 --> 00:01:49,350
i en snor den simpleste måde

43
00:01:49,350 --> 00:01:51,620
 ved at gå gennem hele strengen

44
00:01:51,620 --> 00:01:54,790
brev-by-brev og lægge 1 til en tæller for hver karakter.

45
00:01:55,700 --> 00:01:58,420
Denne algoritme siges at køre i lineær tid

46
00:01:58,420 --> 00:02:00,460
med hensyn til antallet af tegn,

47
00:02:00,460 --> 00:02:02,670
'N' i strengen.

48
00:02:02,670 --> 00:02:04,910
Kort sagt, kører det i O (n).

49
00:02:05,570 --> 00:02:07,290
Hvorfor er det?

50
00:02:07,290 --> 00:02:09,539
Nå, ved hjælp af denne metode, den nødvendige tid

51
00:02:09,539 --> 00:02:11,300
at krydse hele strengen

52
00:02:11,300 --> 00:02:13,920
er proportional med det antal tegn.

53
00:02:13,920 --> 00:02:16,480
Tælle antallet af tegn i en 20-tegnstreng

54
00:02:16,480 --> 00:02:18,580
vil tage dobbelt så lang som det tager

55
00:02:18,580 --> 00:02:20,330
at tælle tegnene i en 10-tegnstreng,

56
00:02:20,330 --> 00:02:23,000
fordi du er nødt til at se på alle tegn

57
00:02:23,000 --> 00:02:25,740
og hver karakter tager den samme mængde tid til at se på.

58
00:02:25,740 --> 00:02:28,050
Når du øger antallet af tegn,

59
00:02:28,050 --> 00:02:30,950
runtime vil øges lineært med input længde.

60
00:02:30,950 --> 00:02:33,500
>> Nu, tænk hvis du beslutter dig for at lineær tid,

61
00:02:33,500 --> 00:02:36,390
O (n), var bare ikke hurtig nok for dig?

62
00:02:36,390 --> 00:02:38,750
Måske er du gemme enorme strenge,

63
00:02:38,750 --> 00:02:40,450
og du kan ikke råd til den ekstra tid, det ville tage

64
00:02:40,450 --> 00:02:44,000
at krydse alle deres karakterer tæller én efter én.

65
00:02:44,000 --> 00:02:46,650
Så du beslutter dig for at prøve noget andet.

66
00:02:46,650 --> 00:02:49,270
Hvad hvis du ville der ske med allerede gemme antallet af tegn

67
00:02:49,270 --> 00:02:52,690
i strengen, siger, i en variabel kaldet 'len'

68
00:02:52,690 --> 00:02:54,210
tidligt i programmet,

69
00:02:54,210 --> 00:02:57,800
før du selv gemt det allerførste tegn i din streng?

70
00:02:57,800 --> 00:02:59,980
Så alt hvad du nødt til at gøre nu for at finde ud af strengen længde,

71
00:02:59,980 --> 00:03:02,570
er kontrollere, hvad værdien af ​​variablen er.

72
00:03:02,570 --> 00:03:05,530
Du ville ikke have til at se på selve strengen på alle,

73
00:03:05,530 --> 00:03:08,160
og adgang til værdien af ​​en variabel ligesom len anses

74
00:03:08,160 --> 00:03:11,100
en asymptotisk konstant tid drift,

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

76
00:03:13,070 --> 00:03:17,110
Hvorfor er det? Nå, huske, hvad asymptotisk kompleksitet betyder.

77
00:03:17,110 --> 00:03:19,100
Hvordan runtime ændring som den størrelse

78
00:03:19,100 --> 00:03:21,400
af dine input vokser?

79
00:03:21,400 --> 00:03:24,630
>> Sig, at du forsøgte at få antallet af tegn i en større streng.

80
00:03:24,630 --> 00:03:26,960
Nå, ville det ikke ligegyldigt hvor stor du gør strengen,

81
00:03:26,960 --> 00:03:28,690
selv en million tegn,

82
00:03:28,690 --> 00:03:31,150
alt hvad du nødt til at gøre for at finde strengen længde med denne tilgang,

83
00:03:31,150 --> 00:03:33,790
at læse værdien af ​​den variable len,

84
00:03:33,790 --> 00:03:35,440
som du allerede har gjort.

85
00:03:35,440 --> 00:03:38,200
Input længde, det vil sige længden af ​​strengen man prøver at finde,

86
00:03:38,200 --> 00:03:41,510
påvirker ikke på alle, hvor hurtigt dit program kører.

87
00:03:41,510 --> 00:03:44,550
Denne del af dit program ville køre lige så hurtigt på en en-tegnstreng

88
00:03:44,550 --> 00:03:46,170
og tusind-tegnstreng,

89
00:03:46,170 --> 00:03:49,140
og det er derfor dette program vil blive omtalt som kører i konstant tid

90
00:03:49,140 --> 00:03:51,520
med hensyn til input-størrelse.

91
00:03:51,520 --> 00:03:53,920
>> Selvfølgelig er der en ulempe.

92
00:03:53,920 --> 00:03:55,710
Du tilbringer ekstra hukommelse på din computer

93
00:03:55,710 --> 00:03:57,380
lagring af variable

94
00:03:57,380 --> 00:03:59,270
og den ekstra tid det tager dig

95
00:03:59,270 --> 00:04:01,490
at gøre det egentlige lagring af variable,

96
00:04:01,490 --> 00:04:03,390
men pointen stadig står,

97
00:04:03,390 --> 00:04:05,060
finde ud af, hvor længe din streng var

98
00:04:05,060 --> 00:04:07,600
ikke afhænger af længden af ​​strengen overhovedet.

99
00:04:07,600 --> 00:04:10,720
Så det kører i O (1) eller konstant tid.

100
00:04:10,720 --> 00:04:13,070
Det betyder bestemt ikke at betyde

101
00:04:13,070 --> 00:04:15,610
at din kode kører i 1 trin,

102
00:04:15,610 --> 00:04:17,470
men uanset hvor mange skridt det er,

103
00:04:17,470 --> 00:04:20,019
hvis det ikke ændres med størrelsen af ​​de input,

104
00:04:20,019 --> 00:04:23,420
det er stadig asymptotisk konstant, som vi repræsenterer som O (1).

105
00:04:23,420 --> 00:04:25,120
>> Som du sikkert kan gætte,

106
00:04:25,120 --> 00:04:27,940
der er mange forskellige store O funktionstider at måle algoritmer med.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmer er asymptotisk langsommere end O (n) algoritmer.

108
00:04:32,980 --> 00:04:35,910
Det vil sige, idet antallet af elementer (n) vokser,

109
00:04:35,910 --> 00:04:39,280
til sidst O (n) ² algoritmer vil tage længere tid

110
00:04:39,280 --> 00:04:41,000
end O (n) algoritmer til at køre.

111
00:04:41,000 --> 00:04:43,960
Det betyder ikke O (n) algoritmer altid køre hurtigere

112
00:04:43,960 --> 00:04:46,410
end O (n) ² algoritmer, selv i det samme miljø

113
00:04:46,410 --> 00:04:48,080
på den samme hardware.

114
00:04:48,080 --> 00:04:50,180
Måske til små input størrelser,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algoritme kan faktisk arbejde hurtigere,

116
00:04:52,900 --> 00:04:55,450
men i sidste ende, som input størrelse stiger

117
00:04:55,450 --> 00:04:58,760
mod uendeligheden, O (n) ² algoritmen runtime

118
00:04:58,760 --> 00:05:02,000
i sidste ende vil overskygge den runtime af O (n) algoritme.

119
00:05:02,000 --> 00:05:04,230
Ligesom enhver kvadratisk matematisk funktion

120
00:05:04,230 --> 00:05:06,510
 sidste ende vil overtage en lineær funktion,

121
00:05:06,510 --> 00:05:09,200
uanset hvor meget af et forspring den lineære funktion starter med.

122
00:05:10,010 --> 00:05:12,000
Hvis du arbejder med store mængder data,

123
00:05:12,000 --> 00:05:15,510
algoritmer, der kører i O (n) ² tid virkelig kan ende med at bremse dit program,

124
00:05:15,510 --> 00:05:17,770
men for små input størrelser,

125
00:05:17,770 --> 00:05:19,420
De vil sandsynligvis ikke engang mærke til det.

126
00:05:19,420 --> 00:05:21,280
>> En anden asymptotiske kompleksitet er,

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

128
00:05:24,420 --> 00:05:26,340
Et eksempel på en algoritme, der kører denne hurtigt

129
00:05:26,340 --> 00:05:29,060
er den klassiske binære søgealgoritme,

130
00:05:29,060 --> 00:05:31,850
for at finde et element i en allerede sorteret liste over bestanddele.

131
00:05:31,850 --> 00:05:33,400
>> Hvis du ikke ved, hvad binær søgning gør,

132
00:05:33,400 --> 00:05:35,170
Jeg vil forklare det for dig virkelig hurtigt.

133
00:05:35,170 --> 00:05:37,020
Lad os sige, du leder efter tallet 3

134
00:05:37,020 --> 00:05:40,200
i denne række af heltal.

135
00:05:40,200 --> 00:05:42,140
Det ser på den midterste element i arrayet

136
00:05:42,140 --> 00:05:46,830
og spørger: "Er det element jeg ønsker større end, lig med eller mindre end dette?"

137
00:05:46,830 --> 00:05:49,150
Hvis det er lige, så stor. Du fandt det element, og du er færdig.

138
00:05:49,150 --> 00:05:51,300
Hvis det er større, så du kender element

139
00:05:51,300 --> 00:05:53,440
skal være i højre side af opstillingen,

140
00:05:53,440 --> 00:05:55,200
og du kan kun se på det i fremtiden,

141
00:05:55,200 --> 00:05:57,690
og hvis det er mindre, så du ved, det må være i venstre side.

142
00:05:57,690 --> 00:06:00,980
Denne proces gentages derefter med den mindre størrelse matrix

143
00:06:00,980 --> 00:06:02,870
indtil det korrekte element er fundet.

144
00:06:08,080 --> 00:06:11,670
>> Denne kraftfulde algoritme skærer array-størrelse i halve med hver operation.

145
00:06:11,670 --> 00:06:14,080
Så for at finde et element i en sorteret array af størrelse 8,

146
00:06:14,080 --> 00:06:16,170
højst (log ₂ 8),

147
00:06:16,170 --> 00:06:18,450
eller 3 af disse transaktioner,

148
00:06:18,450 --> 00:06:22,260
kontrollere den midterste element, så skære arrayet i halvdelen vil være påkrævet,

149
00:06:22,260 --> 00:06:25,670
henviser til et array af størrelse 16 tager (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
eller 4 operationer.

151
00:06:27,480 --> 00:06:30,570
Det er kun 1 mere operation for en dobbelt-størrelse array.

152
00:06:30,570 --> 00:06:32,220
Fordobling af størrelsen af ​​grupperingen

153
00:06:32,220 --> 00:06:35,160
øger runtime ved kun 1 bid af denne kode.

154
00:06:35,160 --> 00:06:37,770
Igen, kontrol den midterste element i listen, så opdelingen.

155
00:06:37,770 --> 00:06:40,440
Så er det sagt at operere i logaritmisk tid,

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

157
00:06:42,440 --> 00:06:44,270
Men vent, du siger,

158
00:06:44,270 --> 00:06:47,510
ikke dette afhænger af, hvor på listen det element, du leder efter, er?

159
00:06:47,510 --> 00:06:50,090
Hvad hvis det første element, du ser på sker for at være den rigtige?

160
00:06:50,090 --> 00:06:52,040
Så det tager kun 1 operation,

161
00:06:52,040 --> 00:06:54,310
uanset hvor stor listen er.

162
00:06:54,310 --> 00:06:56,310
>> Nå, det er derfor dataloger har flere vilkår

163
00:06:56,310 --> 00:06:58,770
for asymptotiske kompleksitet, der afspejler den bedst tænkelige

164
00:06:58,770 --> 00:07:01,050
og værst tænkelige præstationer af en algoritme.

165
00:07:01,050 --> 00:07:03,320
Mere korrekt, de øvre og nedre grænser

166
00:07:03,320 --> 00:07:05,090
på runtime.

167
00:07:05,090 --> 00:07:07,660
I bedste fald for binær søgning, er vores element

168
00:07:07,660 --> 00:07:09,330
lige der i midten,

169
00:07:09,330 --> 00:07:11,770
og du får det i konstant tid,

170
00:07:11,770 --> 00:07:14,240
uanset hvor stor resten af ​​arrayet er.

171
00:07:15,360 --> 00:07:17,650
Symbolet anvendes til dette er Ω.

172
00:07:17,650 --> 00:07:19,930
Så bliver denne algoritme siges at køre i Ω (1).

173
00:07:19,930 --> 00:07:21,990
I bedste fald finder det elementet hurtigt,

174
00:07:21,990 --> 00:07:24,200
uanset hvor stor array er,

175
00:07:24,200 --> 00:07:26,050
men i værste fald,

176
00:07:26,050 --> 00:07:28,690
den skal udføre (log n) delte checks

177
00:07:28,690 --> 00:07:31,030
af arrayet at finde den rigtige element.

178
00:07:31,030 --> 00:07:34,270
Worst-case øvre grænser benævnes med det store "O", som du allerede kender.

179
00:07:34,270 --> 00:07:38,080
Så det er O (log n), men Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> En lineær søgning derimod

181
00:07:40,680 --> 00:07:43,220
hvor man går gennem alle elementer i arrayet

182
00:07:43,220 --> 00:07:45,170
at finde det, du ønsker,

183
00:07:45,170 --> 00:07:47,420
er i bedste Ω (1).

184
00:07:47,420 --> 00:07:49,430
Igen det første element, du ønsker.

185
00:07:49,430 --> 00:07:51,930
Så er det ligegyldigt, hvor stor array er.

186
00:07:51,930 --> 00:07:54,840
I værste fald er det det sidste element i array.

187
00:07:54,840 --> 00:07:58,560
Så du er nødt til at gå gennem alle n elementer i arrayet for at finde det,

188
00:07:58,560 --> 00:08:02,170
ligesom hvis du var på udkig efter en 3.

189
00:08:04,320 --> 00:08:06,030
Så det kører i O (n) tid

190
00:08:06,030 --> 00:08:09,330
fordi det er proportional med antallet af elementer i array.

191
00:08:10,800 --> 00:08:12,830
>> En mere anvendte symbol er Θ.

192
00:08:12,830 --> 00:08:15,820
Dette kan bruges til at beskrive algoritmer, hvor de bedste og værste tilfælde

193
00:08:15,820 --> 00:08:17,440
er de samme.

194
00:08:17,440 --> 00:08:20,390
Dette er tilfældet i streng-længde algoritmer, vi talte om tidligere.

195
00:08:20,390 --> 00:08:22,780
Det vil sige, hvis vi gemme det i en variabel, før

196
00:08:22,780 --> 00:08:25,160
vi opbevarer strengen og få adgang til det senere i konstant tid.

197
00:08:25,160 --> 00:08:27,920
Ligegyldigt hvad nummer

198
00:08:27,920 --> 00:08:30,130
vi lagring i denne variabel, vil vi nødt til at se på det.

199
00:08:33,110 --> 00:08:35,110
Den bedste fald er, at vi ser på det

200
00:08:35,110 --> 00:08:37,120
og finde længden af ​​strengen.

201
00:08:37,120 --> 00:08:39,799
Så Ω (1) eller best-case konstant tid.

202
00:08:39,799 --> 00:08:41,059
Det værste tilfælde er,

203
00:08:41,059 --> 00:08:43,400
vi ser på det, og finde længden af ​​strengen.

204
00:08:43,400 --> 00:08:47,300
Så, O (1) eller konstant tid i værste fald.

205
00:08:47,300 --> 00:08:49,180
Så da bedste fald og værste tilfælde er de samme,

206
00:08:49,180 --> 00:08:52,520
Dette kan siges at køre i Θ (1) tid.

207
00:08:54,550 --> 00:08:57,010
>> Sammenfattende har vi gode måder at ræsonnere om koder effektivitet

208
00:08:57,010 --> 00:09:00,110
uden at vide noget om den virkelige verden tid de tager at køre,

209
00:09:00,110 --> 00:09:02,270
der er påvirket af mange eksterne faktorer,

210
00:09:02,270 --> 00:09:04,190
herunder forskellige hardware, software,

211
00:09:04,190 --> 00:09:06,040
eller detaljerne i din kode.

212
00:09:06,040 --> 00:09:08,380
Også, det giver os mulighed for at ræsonnere sig om, hvad der vil ske

213
00:09:08,380 --> 00:09:10,180
når størrelsen af ​​input stiger.

214
00:09:10,180 --> 00:09:12,490
>> Hvis du kører i O (n) ² algoritme,

215
00:09:12,490 --> 00:09:15,240
eller værre, en O (2 ⁿ) algoritme,

216
00:09:15,240 --> 00:09:17,170
en af ​​de hurtigst voksende typer,

217
00:09:17,170 --> 00:09:19,140
vil du virkelig begynde at lægge mærke afmatningen

218
00:09:19,140 --> 00:09:21,220
når du begynder at arbejde med større mængder af data.

219
00:09:21,220 --> 00:09:23,590
>> Det er asymptotisk kompleksitet. Tak.