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

2
00:00:10,950 --> 00:00:13,090
for utføring av din bestemt oppgave,

3
00:00:13,090 --> 00:00:16,110
men hva betyr det for en algoritme for å være rask eller effektiv?

4
00:00:16,110 --> 00:00:18,580
Vel, det er ikke snakk om en måling i sanntid,

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

6
00:00:20,500 --> 00:00:22,220
Dette er fordi maskinvare

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

8
00:00:24,260 --> 00:00:26,020
Mitt program kan kjøre saktere enn din,

9
00:00:26,020 --> 00:00:28,000
fordi jeg kjører den på en eldre datamaskin,

10
00:00:28,000 --> 00:00:30,110
eller fordi jeg tilfeldigvis skal spille et online dataspill

11
00:00:30,110 --> 00:00:32,670
på samme tid, som den samler min hukommelse,

12
00:00:32,670 --> 00:00:35,400
eller jeg kan kjøre mitt program gjennom forskjellig programvare

13
00:00:35,400 --> 00:00:37,550
som kommuniserer med maskinen annerledes på et lavt nivå.

14
00:00:37,550 --> 00:00:39,650
Det er som å sammenligne epler og appelsiner.

15
00:00:39,650 --> 00:00:41,940
Bare fordi min tregere datamaskin tar lengre tid

16
00:00:41,940 --> 00:00:43,410
enn din for å gi tilbake et svar

17
00:00:43,410 --> 00:00:45,510
betyr ikke at du har den mer effektiv algoritme.

18
00:00:45,510 --> 00:00:48,830
>> Så, siden vi ikke kan sammenlikne kjøretidsfiler av programmer

19
00:00:48,830 --> 00:00:50,140
i løpet av sekunder eller minutter,

20
00:00:50,140 --> 00:00:52,310
hvordan sammenligne vi to forskjellige algoritmer

21
00:00:52,310 --> 00:00:55,030
uavhengig av deres maskinvare eller programvare-miljøet?

22
00:00:55,030 --> 00:00:58,000
Å skape en mer enhetlig måte å måle algoritmisk effektivitet,

23
00:00:58,000 --> 00:01:00,360
dataforskere og matematikere har utviklet

24
00:01:00,360 --> 00:01:03,830
konsepter for måling den asymptotiske kompleksiteten av et program

25
00:01:03,830 --> 00:01:06,110
og en notasjon som kalles "Big Ohnotation '

26
00:01:06,110 --> 00:01:08,320
for å beskrive dette.

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

28
00:01:10,820 --> 00:01:13,390
kjører på i størrelsesorden g (x)

29
00:01:13,390 --> 00:01:15,140
hvis det eksisterer noen (x)-verdi, x ₀ og

30
00:01:15,140 --> 00:01:17,630
noen konstant, C, hvor

31
00:01:17,630 --> 00:01:19,340
f (x) er mindre enn eller lik

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

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

34
00:01:23,190 --> 00:01:25,290
>> Men ikke bli skremt vekk av den formelle definisjonen.

35
00:01:25,290 --> 00:01:28,020
Hva betyr dette egentlig betyr i mindre teoretisk?

36
00:01:28,020 --> 00:01:30,580
Vel, det er i utgangspunktet en måte å analysere

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

38
00:01:33,580 --> 00:01:37,170
Det er, som størrelsen på dataen øker mot uendelig,

39
00:01:37,170 --> 00:01:41,390
si, du sortere en rekke størrelse 1000 sammenlignet med en rekke størrelse 10.

40
00:01:41,390 --> 00:01:44,950
Hvordan vokse runtime på programmet?

41
00:01:44,950 --> 00:01:47,390
Tenk deg for eksempel telle antall tegn

42
00:01:47,390 --> 00:01:49,350
i en streng den enkleste måten

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

44
00:01:51,620 --> 00:01:54,790
bokstav for bokstav og tilsetning av 1 til en teller for hvert tegn.

45
00:01:55,700 --> 00:01:58,420
Denne algoritmen er sagt å kjøre i lineær tid

46
00:01:58,420 --> 00:02:00,460
med hensyn til det antall tegn,

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

48
00:02:02,670 --> 00:02:04,910
Kort sagt, det går i O (n).

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

50
00:02:07,290 --> 00:02:09,539
Vel, ved hjelp av denne tilnærmingen, krevde tid

51
00:02:09,539 --> 00:02:11,300
å traversere hele strengen

52
00:02:11,300 --> 00:02:13,920
er proporsjonal med antall tegn.

53
00:02:13,920 --> 00:02:16,480
Telle antall tegn i en 20-tegnstreng

54
00:02:16,480 --> 00:02:18,580
kommer til å ta dobbelt så lang tid som det tar

55
00:02:18,580 --> 00:02:20,330
å telle tegnene i en 10-tegns streng,

56
00:02:20,330 --> 00:02:23,000
fordi du må se på alle tegnene

57
00:02:23,000 --> 00:02:25,740
og hvert tegn tar like mye tid til å se på.

58
00:02:25,740 --> 00:02:28,050
Når du øker antall tegn,

59
00:02:28,050 --> 00:02:30,950
driftstiden vil øke lineært med input lengde.

60
00:02:30,950 --> 00:02:33,500
>> Nå forestille seg hvis du bestemmer deg for at lineær tid,

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

62
00:02:36,390 --> 00:02:38,750
Kanskje du lagrer store strenger,

63
00:02:38,750 --> 00:02:40,450
og du ikke har råd til den ekstra tiden det ville ta

64
00:02:40,450 --> 00:02:44,000
å traversere alle sine karakterer teller én etter én.

65
00:02:44,000 --> 00:02:46,650
Så bestemmer deg for å prøve noe annerledes.

66
00:02:46,650 --> 00:02:49,270
Hva om du ville skje med allerede lagre nummeret tegn

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

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

69
00:02:54,210 --> 00:02:57,800
før du selv lagret det aller første tegnet i strengen din?

70
00:02:57,800 --> 00:02:59,980
Deretter alt du måtte gjøre nå for å finne ut strengen lengde,

71
00:02:59,980 --> 00:03:02,570
er å sjekke hva verdien av variabelen er.

72
00:03:02,570 --> 00:03:05,530
Du ville ikke trenger å se på selve strengen i det hele tatt,

73
00:03:05,530 --> 00:03:08,160
og tilgang til verdien av en variabel som len regnes

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 dette? Vel, husk hva asymptotisk kompleksitet betyr.

77
00:03:17,110 --> 00:03:19,100
Hvordan får runtime endring som størrelsen

78
00:03:19,100 --> 00:03:21,400
av dataen vokser?

79
00:03:21,400 --> 00:03:24,630
>> Si du prøvde å få antall tegn i en større streng.

80
00:03:24,630 --> 00:03:26,960
Vel, ville det ingen rolle hvor stor du gjør streng,

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

82
00:03:28,690 --> 00:03:31,150
alt du måtte gjøre for å finne strengens lengde med denne tilnærmingen,

83
00:03:31,150 --> 00:03:33,790
er å lese ut verdien av variabelen 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 lengde, det vil si lengden av strengen du forsøker å finne,

86
00:03:38,200 --> 00:03:41,510
påvirker ikke i det hele tatt hvor raskt programmet kjører.

87
00:03:41,510 --> 00:03:44,550
Denne delen av programmet vil kjøre like fort på en en-tegnstreng

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

89
00:03:46,170 --> 00:03:49,140
og det er derfor dette programmet ville bli referert til som kjører i konstant tid

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

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

92
00:03:53,920 --> 00:03:55,710
Du tilbringe ekstra lagringsplass på datamaskinen

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

94
00:03:57,380 --> 00:03:59,270
og den ekstra tiden det tar deg

95
00:03:59,270 --> 00:04:01,490
å gjøre selve lagring av variabelen,

96
00:04:01,490 --> 00:04:03,390
men poenget står fortsatt,

97
00:04:03,390 --> 00:04:05,060
finne ut hvor lenge streng var

98
00:04:05,060 --> 00:04:07,600
ikke avhengig av lengden av strengen i det hele tatt.

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

100
00:04:10,720 --> 00:04:13,070
Dette absolutt ikke å bety

101
00:04:13,070 --> 00:04:15,610
at koden kjøres i trinn 1,

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

103
00:04:17,470 --> 00:04:20,019
hvis den ikke endrer med størrelsen av inngangene,

104
00:04:20,019 --> 00:04:23,420
det er fortsatt asymptotisk konstant som vi representerer som O (1).

105
00:04:23,420 --> 00:04:25,120
>> Som du kan sikkert gjette,

106
00:04:25,120 --> 00:04:27,940
er det mange forskjellige store O kjøretidsfiler å måle algoritmer med.

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

108
00:04:32,980 --> 00:04:35,910
Det er, som antall elementer (n) vokser,

109
00:04:35,910 --> 00:04:39,280
slutt O (n) ² algoritmer vil ta mer tid

110
00:04:39,280 --> 00:04:41,000
enn O (n) algoritmer å kjøre.

111
00:04:41,000 --> 00:04:43,960
Dette betyr ikke O (n) algoritmer alltid kjøre raskere

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

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

114
00:04:48,080 --> 00:04:50,180
Kanskje for liten input størrelser,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algoritmen kan faktisk jobbe raskere,

116
00:04:52,900 --> 00:04:55,450
men, til slutt, som input størrelsen øker

117
00:04:55,450 --> 00:04:58,760
mot uendelig, O (n) ² algoritme runtime

118
00:04:58,760 --> 00:05:02,000
vil til slutt overskygger runtime på O (n) algoritme.

119
00:05:02,000 --> 00:05:04,230
Akkurat som alle kvadratisk matematisk funksjon

120
00:05:04,230 --> 00:05:06,510
 vil til slutt gå forbi noen lineær funksjon,

121
00:05:06,510 --> 00:05:09,200
uansett hvor mye av et hode starte lineær funksjon starter med.

122
00:05:10,010 --> 00:05:12,000
Hvis du arbeider med store mengder data,

123
00:05:12,000 --> 00:05:15,510
algoritmer som kjører i O (n) ² tid kan virkelig ende opp bremse ned programmet,

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

125
00:05:17,770 --> 00:05:19,420
du sannsynligvis vil ikke engang merke til.

126
00:05:19,420 --> 00:05:21,280
>> En annen asymptotisk 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 som kjører dette raskt

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

130
00:05:29,060 --> 00:05:31,850
for å finne et element i et allerede sortert liste av elementer.

131
00:05:31,850 --> 00:05:33,400
>> Hvis du ikke vet hva binær søk gjør,

132
00:05:33,400 --> 00:05:35,170
Jeg skal forklare det for deg veldig raskt.

133
00:05:35,170 --> 00:05:37,020
La oss si at du leter etter nummer 3

134
00:05:37,020 --> 00:05:40,200
i denne rekke heltall.

135
00:05:40,200 --> 00:05:42,140
Den ser på midten element i matrisen

136
00:05:42,140 --> 00:05:46,830
og spør: "Er element jeg vil ha større enn, lik eller mindre enn dette?"

137
00:05:46,830 --> 00:05:49,150
Hvis det er lik, så flott. Du fant elementet, og du er ferdig.

138
00:05:49,150 --> 00:05:51,300
Hvis den er større, så vet du elementet

139
00:05:51,300 --> 00:05:53,440
må være på høyre side av tabellen,

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

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

142
00:05:57,690 --> 00:06:00,980
Denne prosessen blir så gjentatt med den mindre størrelse matrise

143
00:06:00,980 --> 00:06:02,870
inntil riktig elementet er funnet.

144
00:06:08,080 --> 00:06:11,670
>> Denne kraftige algoritmen kutter gitterstørrelse i to med hver operasjon.

145
00:06:11,670 --> 00:06:14,080
Så, for å finne et element i en sortert rekke størrelse 8,

146
00:06:14,080 --> 00:06:16,170
på de fleste (log ₂ 8),

147
00:06:16,170 --> 00:06:18,450
eller 3 av disse operasjonene,

148
00:06:18,450 --> 00:06:22,260
sjekke midten element, deretter kutte array i halvparten vil være nødvendig,

149
00:06:22,260 --> 00:06:25,670
mens en rekke størrelser som 16 tar (log ₂ 16),

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

151
00:06:27,480 --> 00:06:30,570
Det er bare en mer bruk for en doblet størrelse array.

152
00:06:30,570 --> 00:06:32,220
Dobling av størrelsen på matrisen

153
00:06:32,220 --> 00:06:35,160
øker runtime med kun 1 del av denne koden.

154
00:06:35,160 --> 00:06:37,770
Igjen, sjekke midt element i listen, og splitting.

155
00:06:37,770 --> 00:06:40,440
Så er det sagt å 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 sier,

158
00:06:44,270 --> 00:06:47,510
ikke dette avhenger av hvor i listen elementet du leter etter er?

159
00:06:47,510 --> 00:06:50,090
Hva om det første elementet du ser på skjer for å være den rette?

160
00:06:50,090 --> 00:06:52,040
Deretter tar det bare en operasjon,

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

162
00:06:54,310 --> 00:06:56,310
>> Vel, det er derfor dataforskere har flere ord

163
00:06:56,310 --> 00:06:58,770
for asymptotisk kompleksitet som reflekterer best-case

164
00:06:58,770 --> 00:07:01,050
og worst-case forestillinger av en algoritme.

165
00:07:01,050 --> 00:07:03,320
Mer riktig, øvre og nedre grenser

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

167
00:07:05,090 --> 00:07:07,660
I beste fall for binære søk, er vår element

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

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

170
00:07:11,770 --> 00:07:14,240
uansett hvor stor resten av tabellen er.

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

172
00:07:17,650 --> 00:07:19,930
Så, er denne algoritmen sagt å kjøre i Ω (1).

173
00:07:19,930 --> 00:07:21,990
I beste fall, finner den det elementet raskt,

174
00:07:21,990 --> 00:07:24,200
uansett hvor stor matrise er,

175
00:07:24,200 --> 00:07:26,050
men i verste fall,

176
00:07:26,050 --> 00:07:28,690
det må utføre (log n) split sjekker

177
00:07:28,690 --> 00:07:31,030
i matrisen for å finne den rette element.

178
00:07:31,030 --> 00:07:34,270
Worst-case øvre grense er referert til med den store "O" som du allerede vet.

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øk, derimot,

181
00:07:40,680 --> 00:07:43,220
der du går gjennom hvert element i matrisen

182
00:07:43,220 --> 00:07:45,170
å finne det du vil ha,

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

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

185
00:07:49,430 --> 00:07:51,930
Så det spiller ingen rolle hvor stor matrise er.

186
00:07:51,930 --> 00:07:54,840
I verste fall er det siste elementet i matrisen.

187
00:07:54,840 --> 00:07:58,560
Så må du gå gjennom alle n elementer i matrisen for å finne den,

188
00:07:58,560 --> 00:08:02,170
som om du var på utkikk etter en 3.

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

190
00:08:06,030 --> 00:08:09,330
fordi det er proporsjonal med antallet av elementer i matrisen.

191
00:08:10,800 --> 00:08:12,830
>> Enda et symbol som brukes er Θ.

192
00:08:12,830 --> 00:08:15,820
Dette kan brukes til å beskrive algoritmer hvor de beste og verste tilfeller

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

194
00:08:17,440 --> 00:08:20,390
Dette er tilfellet i streng-lengde algoritmer vi snakket om tidligere.

195
00:08:20,390 --> 00:08:22,780
Det vil si, hvis vi lagre den i en variabel før

196
00:08:22,780 --> 00:08:25,160
vi lagre strengen og få tilgang til den senere i konstant tid.

197
00:08:25,160 --> 00:08:27,920
Uansett hvilket nummer

198
00:08:27,920 --> 00:08:30,130
Vi lagrer i den variabelen, må vi se på det.

199
00:08:33,110 --> 00:08:35,110
Det beste fall er, ser vi på det

200
00:08:35,110 --> 00:08:37,120
og finne lengden på 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 verste tilfellet er,

203
00:08:41,059 --> 00:08:43,400
Vi ser på det og finne lengden av strengen.

204
00:08:43,400 --> 00:08:47,300
Slik, O (1) eller konstant tid i verste tilfelle.

205
00:08:47,300 --> 00:08:49,180
Så, siden den beste tilfelle og verste tilfellene er de samme,

206
00:08:49,180 --> 00:08:52,520
Dette kan sies å kjøre i Θ (1) gang.

207
00:08:54,550 --> 00:08:57,010
>> Oppsummert har vi gode måter å resonnere om koder effektivitet

208
00:08:57,010 --> 00:09:00,110
uten å vite noe om den virkelige verden tid de tar å kjøre,

209
00:09:00,110 --> 00:09:02,270
som påvirkes av mange ytre faktorer,

210
00:09:02,270 --> 00:09:04,190
inkludert ulike maskinvare, programvare,

211
00:09:04,190 --> 00:09:06,040
eller spesifikk av koden din.

212
00:09:06,040 --> 00:09:08,380
Også gir det oss å resonnere godt om hva som vil skje

213
00:09:08,380 --> 00:09:10,180
når størrelsen av inngangene øker.

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

215
00:09:12,490 --> 00:09:15,240
eller enda verre, en O (2 ⁿ) algoritme,

216
00:09:15,240 --> 00:09:17,170
en av de raskest voksende,

217
00:09:17,170 --> 00:09:19,140
vil du virkelig begynne å merke nedgangen

218
00:09:19,140 --> 00:09:21,220
når du begynner å arbeide med større mengder data.

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