1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Du har säkert hört talas om en snabb eller effektiv algoritm

2
00:00:10,950 --> 00:00:13,090
för att utföra din uppgift,

3
00:00:13,090 --> 00:00:16,110
men vad betyder det för en algoritm för att vara snabb eller effektiv?

4
00:00:16,110 --> 00:00:18,580
Tja, det talar inte om en mätning i realtid,

5
00:00:18,580 --> 00:00:20,500
Liksom sekunder eller minuter.

6
00:00:20,500 --> 00:00:22,220
Detta beror på att maskinvara

7
00:00:22,220 --> 00:00:24,260
och programvara varierar kraftigt.

8
00:00:24,260 --> 00:00:26,020
Mitt program kan köra långsammare än din,

9
00:00:26,020 --> 00:00:28,000
eftersom jag kör det på en äldre dator,

10
00:00:28,000 --> 00:00:30,110
eller för att jag råkar vara spela ett online videospel

11
00:00:30,110 --> 00:00:32,670
Samtidigt, vilket hogging hela mitt minne,

12
00:00:32,670 --> 00:00:35,400
eller jag kanske köra mitt program genom olika programvaror

13
00:00:35,400 --> 00:00:37,550
som kommunicerar med maskinen olika vid en låg nivå.

14
00:00:37,550 --> 00:00:39,650
Det är som att jämföra äpplen och apelsiner.

15
00:00:39,650 --> 00:00:41,940
Bara för att min långsammare dator tar längre

16
00:00:41,940 --> 00:00:43,410
än din att ge tillbaka ett svar

17
00:00:43,410 --> 00:00:45,510
betyder inte att du har desto mer effektiv algoritm.

18
00:00:45,510 --> 00:00:48,830
>> Så, eftersom vi inte direkt kan jämföra drifttider av program

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

20
00:00:50,140 --> 00:00:52,310
Hur jämför vi 2 olika algoritmer

21
00:00:52,310 --> 00:00:55,030
oavsett hårdvara eller mjukvara miljö?

22
00:00:55,030 --> 00:00:58,000
För att skapa ett mer enhetligt sätt att mäta algoritmisk effektivitet,

23
00:00:58,000 --> 00:01:00,360
datavetare och matematiker har utarbetat

24
00:01:00,360 --> 00:01:03,830
koncept för att mäta det asymptotiska komplexiteten av ett program

25
00:01:03,830 --> 00:01:06,110
och en notation som kallas "Big Ohnotation"

26
00:01:06,110 --> 00:01:08,320
för att beskriva detta.

27
00:01:08,320 --> 00:01:10,820
Den formella definitionen är att en funktion f (x)

28
00:01:10,820 --> 00:01:13,390
körs i storleksordningen av g (x)

29
00:01:13,390 --> 00:01:15,140
om det finns någon (x) värde, x ₀ och

30
00:01:15,140 --> 00:01:17,630
någon konstant, C, för vilket

31
00:01:17,630 --> 00:01:19,340
f (x) är mindre än eller lika med

32
00:01:19,340 --> 00:01:21,230
att konstant gånger g (x)

33
00:01:21,230 --> 00:01:23,190
för alla x större än x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Men inte vara rädd bort av den formella definitionen.

35
00:01:25,290 --> 00:01:28,020
Vad innebär det egentligen i mindre teoretiskt?

36
00:01:28,020 --> 00:01:30,580
Tja, det är i grunden ett sätt att analysera

37
00:01:30,580 --> 00:01:33,580
hur snabbt ett programs körning växer asymptotiskt.

38
00:01:33,580 --> 00:01:37,170
Det är, som storleken på dina insatser ökar mot oändligheten,

39
00:01:37,170 --> 00:01:41,390
säger, du sorterar en rad storlek 1000 jämfört med en rad storlek 10.

40
00:01:41,390 --> 00:01:44,950
Hur växer runtime för ditt program?

41
00:01:44,950 --> 00:01:47,390
Tänk dig till exempel att räkna antalet tecken

42
00:01:47,390 --> 00:01:49,350
i en sträng det enklaste sättet

43
00:01:49,350 --> 00:01:51,620
 genom att gå igenom hela strängen

44
00:01:51,620 --> 00:01:54,790
bokstav för bokstav och tillsätta 1 till en räknare för varje tecken.

45
00:01:55,700 --> 00:01:58,420
Denna algoritm sägs gå i linjär tid

46
00:01:58,420 --> 00:02:00,460
med avseende på antalet tecken,

47
00:02:00,460 --> 00:02:02,670
"N" i strängen.

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

49
00:02:05,570 --> 00:02:07,290
Varför är det här?

50
00:02:07,290 --> 00:02:09,539
Nåväl, med denna metod, krävs tid

51
00:02:09,539 --> 00:02:11,300
att korsa hela strängen

52
00:02:11,300 --> 00:02:13,920
är proportionell mot antalet tecken.

53
00:02:13,920 --> 00:02:16,480
Räkna antalet tecken i en 20-teckensträng

54
00:02:16,480 --> 00:02:18,580
kommer att ta dubbelt så lång tid som det tar

55
00:02:18,580 --> 00:02:20,330
att räkna tecknen i en 10-teckensträng,

56
00:02:20,330 --> 00:02:23,000
eftersom du måste titta på alla tecken

57
00:02:23,000 --> 00:02:25,740
och varje tecken tar lika lång tid att titta på.

58
00:02:25,740 --> 00:02:28,050
När du ökar antalet tecken,

59
00:02:28,050 --> 00:02:30,950
körningen ökar linjärt med den ingående längd.

60
00:02:30,950 --> 00:02:33,500
>> Nu, tänk om du bestämmer att linjär tid,

61
00:02:33,500 --> 00:02:36,390
O (n), var helt enkelt inte snabb nog för dig?

62
00:02:36,390 --> 00:02:38,750
Kanske du lagra stora strängar,

63
00:02:38,750 --> 00:02:40,450
och du inte har råd den extra tid det skulle ta

64
00:02:40,450 --> 00:02:44,000
att korsa alla sina karaktärer räkna en-för-en.

65
00:02:44,000 --> 00:02:46,650
Så bestämmer dig att prova något annat.

66
00:02:46,650 --> 00:02:49,270
Vad händer om du skulle hända redan lagra antalet tecken

67
00:02:49,270 --> 00:02:52,690
i strängen, säger i en variabel som heter "Len"

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

69
00:02:54,210 --> 00:02:57,800
innan du lagras även den allra första tecknet i strängen?

70
00:02:57,800 --> 00:02:59,980
Sedan allt du måste göra nu för att ta reda på stränglängd,

71
00:02:59,980 --> 00:03:02,570
är kolla vad värdet på variabeln är.

72
00:03:02,570 --> 00:03:05,530
Du skulle inte behöva titta på strängen själv alls,

73
00:03:05,530 --> 00:03:08,160
och åtkomst till värdet för en variabel som len anses

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

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

76
00:03:13,070 --> 00:03:17,110
Varför är det här? Tja, kom ihåg vad asymptotisk komplexitet innebär.

77
00:03:17,110 --> 00:03:19,100
Hur runtime förändring som storleken

78
00:03:19,100 --> 00:03:21,400
av dina ingångar växer?

79
00:03:21,400 --> 00:03:24,630
>> Säg att du försökte få antalet tecken i en större sträng.

80
00:03:24,630 --> 00:03:26,960
Tja, det skulle ingen roll hur stor du gör strängen,

81
00:03:26,960 --> 00:03:28,690
även en miljon tecken,

82
00:03:28,690 --> 00:03:31,150
allt du skulle behöva göra för att hitta strängen längd med detta tillvägagångssätt,

83
00:03:31,150 --> 00:03:33,790
är att läsa ut värdet på variabeln len,

84
00:03:33,790 --> 00:03:35,440
som ni redan gjort.

85
00:03:35,440 --> 00:03:38,200
Ingången längd, dvs längden på strängen du försöker hitta,

86
00:03:38,200 --> 00:03:41,510
påverkar inte alls hur snabbt ditt program körs.

87
00:03:41,510 --> 00:03:44,550
Denna del av programmet skulle gå lika snabbt på en en-teckensträng

88
00:03:44,550 --> 00:03:46,170
och tusen-teckensträng,

89
00:03:46,170 --> 00:03:49,140
och det är därför detta program skulle kallas körs i konstant tid

90
00:03:49,140 --> 00:03:51,520
med avseende på ingående storlek.

91
00:03:51,520 --> 00:03:53,920
>> Naturligtvis finns det en nackdel.

92
00:03:53,920 --> 00:03:55,710
Du tillbringar extra minnesutrymme på datorn

93
00:03:55,710 --> 00:03:57,380
lagra variabeln

94
00:03:57,380 --> 00:03:59,270
och den extra tid det tar

95
00:03:59,270 --> 00:04:01,490
att göra själva lagringen av variabeln,

96
00:04:01,490 --> 00:04:03,390
men poängen står stilla,

97
00:04:03,390 --> 00:04:05,060
ta reda på hur lång tid din sträng var

98
00:04:05,060 --> 00:04:07,600
beror inte på längden av strängen alls.

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

100
00:04:10,720 --> 00:04:13,070
Detta absolut inte behöver betyda

101
00:04:13,070 --> 00:04:15,610
att koden körs i 1 steg,

102
00:04:15,610 --> 00:04:17,470
men oavsett hur många steg det är,

103
00:04:17,470 --> 00:04:20,019
om det inte förändras med storleken av insignalerna,

104
00:04:20,019 --> 00:04:23,420
det är fortfarande asymptotiskt konstant som vi representerar som O (1).

105
00:04:23,420 --> 00:04:25,120
>> Som ni säkert kan gissa,

106
00:04:25,120 --> 00:04:27,940
det finns många olika Big O drifttider för att mäta algoritmer med.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmer är asymptotiskt långsammare än O (n) algoritmer.

108
00:04:32,980 --> 00:04:35,910
Det är, eftersom antalet element (n) växer,

109
00:04:35,910 --> 00:04:39,280
småningom O (n) ² algoritmer tar längre tid

110
00:04:39,280 --> 00:04:41,000
än O (n) algoritmer för att köra.

111
00:04:41,000 --> 00:04:43,960
Detta betyder inte O (n) algoritmer alltid springa snabbare

112
00:04:43,960 --> 00:04:46,410
än O (n) ² algoritmer, även i samma miljö,

113
00:04:46,410 --> 00:04:48,080
på samma hårdvara.

114
00:04:48,080 --> 00:04:50,180
Kanske för små ingång storlekar,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algoritm kan faktiskt arbeta snabbare,

116
00:04:52,900 --> 00:04:55,450
men så småningom, som ingång storlek ökar

117
00:04:55,450 --> 00:04:58,760
mot oändligheten, O (n) ² algoritmens runtime

118
00:04:58,760 --> 00:05:02,000
kommer så småningom överskugga runtime av O (n) algoritm.

119
00:05:02,000 --> 00:05:04,230
Precis som alla kvadratisk matematisk funktion

120
00:05:04,230 --> 00:05:06,510
 kommer så småningom köra någon linjär funktion,

121
00:05:06,510 --> 00:05:09,200
oavsett hur mycket ett försprång den linjära funktionen börjar med.

122
00:05:10,010 --> 00:05:12,000
Om du arbetar med stora mängder data,

123
00:05:12,000 --> 00:05:15,510
algoritmer som körs i O (n) ² tid kan verkligen hamna saktar ner ditt program,

124
00:05:15,510 --> 00:05:17,770
men för små inmatade storlekar,

125
00:05:17,770 --> 00:05:19,420
du förmodligen inte ens märker.

126
00:05:19,420 --> 00:05:21,280
>> Annan asymptotiska komplexitet är,

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

128
00:05:24,420 --> 00:05:26,340
Ett exempel på en algoritm som kör detta snabbt

129
00:05:26,340 --> 00:05:29,060
är den klassiska binära sökalgoritm,

130
00:05:29,060 --> 00:05:31,850
för att finna ett element i en redan sorterade listan över element.

131
00:05:31,850 --> 00:05:33,400
>> Om du inte vet vad binär sökning gör,

132
00:05:33,400 --> 00:05:35,170
Jag ska förklara det för dig riktigt snabbt.

133
00:05:35,170 --> 00:05:37,020
Låt oss säga att du letar efter siffran 3

134
00:05:37,020 --> 00:05:40,200
i denna grupp av heltal.

135
00:05:40,200 --> 00:05:42,140
Det ser i mitten element i arrayen

136
00:05:42,140 --> 00:05:46,830
och frågar, "Är elementet jag vill ha mer än, lika med eller mindre än detta?"

137
00:05:46,830 --> 00:05:49,150
Om det är lika så bra. Du hittade elementet, och du är klar.

138
00:05:49,150 --> 00:05:51,300
Om det är större, då vet du att elementet

139
00:05:51,300 --> 00:05:53,440
måste vara i den högra sidan av gruppen,

140
00:05:53,440 --> 00:05:55,200
och du kan bara titta på det i framtiden,

141
00:05:55,200 --> 00:05:57,690
och om det är mindre, så du vet att det måste vara på vänster sida.

142
00:05:57,690 --> 00:06:00,980
Denna process upprepas sedan med den mindre storlek matris

143
00:06:00,980 --> 00:06:02,870
tills korrekt elementet hittas.

144
00:06:08,080 --> 00:06:11,670
>> Denna kraftfulla algoritm klipper matrisstorlek i halv med varje operation.

145
00:06:11,670 --> 00:06:14,080
Så, för att finna ett element i en sorterad array med storlek 8,

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

147
00:06:16,170 --> 00:06:18,450
eller 3 av dessa operationer,

148
00:06:18,450 --> 00:06:22,260
kontrollera mellersta elementet, sedan skära arrayen i halv kommer att krävas,

149
00:06:22,260 --> 00:06:25,670
medan en rad storlek 16 tar (log ₂ 16),

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

151
00:06:27,480 --> 00:06:30,570
Det är bara 1 mer drift under en dubbelt storlek array.

152
00:06:30,570 --> 00:06:32,220
En fördubbling av storleken på matrisen

153
00:06:32,220 --> 00:06:35,160
ökar runtime med endast 1 bit av denna kod.

154
00:06:35,160 --> 00:06:37,770
Återigen, kontrollera den mellersta delen av listan, sedan dela.

155
00:06:37,770 --> 00:06:40,440
Så är det sagt att arbeta 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 vänta, du säger,

158
00:06:44,270 --> 00:06:47,510
inte detta beror på var i listan elementet du letar efter är?

159
00:06:47,510 --> 00:06:50,090
Vad händer om det första elementet du tittar på råkar vara den rätta?

160
00:06:50,090 --> 00:06:52,040
Sedan tar det bara 1 operation,

161
00:06:52,040 --> 00:06:54,310
oavsett hur stor listan är.

162
00:06:54,310 --> 00:06:56,310
>> Tja, det är därför datavetare har fler villkor

163
00:06:56,310 --> 00:06:58,770
för asymptotisk komplexitet som speglar bästa fall

164
00:06:58,770 --> 00:07:01,050
och värsta föreställningar av en algoritm.

165
00:07:01,050 --> 00:07:03,320
Mer korrekt, de övre och nedre gränser

166
00:07:03,320 --> 00:07:05,090
på körningen.

167
00:07:05,090 --> 00:07:07,660
I bästa fall för binär sökning, är vår del

168
00:07:07,660 --> 00:07:09,330
rätt där i mitten,

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

170
00:07:11,770 --> 00:07:14,240
oavsett hur stor resten av matrisen är.

171
00:07:15,360 --> 00:07:17,650
Den symbol som används för detta är Ω.

172
00:07:17,650 --> 00:07:19,930
Så, denna algoritm sägs köra i Ω (1).

173
00:07:19,930 --> 00:07:21,990
I bästa fall, finner det elementet snabbt,

174
00:07:21,990 --> 00:07:24,200
oavsett hur stor gruppen är,

175
00:07:24,200 --> 00:07:26,050
men i värsta fall,

176
00:07:26,050 --> 00:07:28,690
det måste ha (log n) delade kontroller

177
00:07:28,690 --> 00:07:31,030
i matrisen för att hitta rätt element.

178
00:07:31,030 --> 00:07:34,270
Värsta övre gräns kallas med den stora "O" att du redan vet.

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

180
00:07:38,080 --> 00:07:40,680
>> En linjär sökning, däremot,

181
00:07:40,680 --> 00:07:43,220
där du går igenom varje element i arrayen

182
00:07:43,220 --> 00:07:45,170
att hitta det du vill,

183
00:07:45,170 --> 00:07:47,420
är i bästa Ω (1).

184
00:07:47,420 --> 00:07:49,430
Återigen det första elementet som du vill.

185
00:07:49,430 --> 00:07:51,930
Så det spelar ingen roll hur stor gruppen är.

186
00:07:51,930 --> 00:07:54,840
I värsta fall är det det sista elementet i arrayen.

187
00:07:54,840 --> 00:07:58,560
Så måste du gå igenom alla n element i arrayen att hitta den,

188
00:07:58,560 --> 00:08:02,170
som om du letade efter en 3.

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

190
00:08:06,030 --> 00:08:09,330
eftersom det är proportionellt mot antalet element i arrayen.

191
00:08:10,800 --> 00:08:12,830
>> En mer symbol som används är Θ.

192
00:08:12,830 --> 00:08:15,820
Detta kan användas för att beskriva algoritmer där de bästa och sämsta fall

193
00:08:15,820 --> 00:08:17,440
är desamma.

194
00:08:17,440 --> 00:08:20,390
Detta är fallet i strängen längd algoritmer vi talat om tidigare.

195
00:08:20,390 --> 00:08:22,780
Det är, om vi förvara den i en variabel innan

196
00:08:22,780 --> 00:08:25,160
Vi lagrar strängen och komma åt den senare konstant tid.

197
00:08:25,160 --> 00:08:27,920
Oavsett vilket nummer

198
00:08:27,920 --> 00:08:30,130
vi lagrar i den variabeln, vi måste titta på det.

199
00:08:33,110 --> 00:08:35,110
I bästa fall är, tittar vi på det

200
00:08:35,110 --> 00:08:37,120
och hitta längden på strängen.

201
00:08:37,120 --> 00:08:39,799
Så Ω (1) eller bästa fall konstant tid.

202
00:08:39,799 --> 00:08:41,059
Det värsta fallet är,

203
00:08:41,059 --> 00:08:43,400
vi tittar på det och hitta längden på strängen.

204
00:08:43,400 --> 00:08:47,300
Så, O (1) eller konstant tid i värsta fall.

205
00:08:47,300 --> 00:08:49,180
Så, eftersom det bästa fall och värsta fall är desamma,

206
00:08:49,180 --> 00:08:52,520
detta kan sägas att köras i Θ (1) tid.

207
00:08:54,550 --> 00:08:57,010
>> Sammanfattningsvis har vi goda möjligheter att resonera om koder effektivitet

208
00:08:57,010 --> 00:09:00,110
utan att veta något om den verkliga tid de tar att köra,

209
00:09:00,110 --> 00:09:02,270
som påverkas av många yttre faktorer,

210
00:09:02,270 --> 00:09:04,190
inklusive olika hårdvara, mjukvara,

211
00:09:04,190 --> 00:09:06,040
eller detaljerna i din kod.

212
00:09:06,040 --> 00:09:08,380
Dessutom ger det oss att resonera väl om vad som kommer att hända

213
00:09:08,380 --> 00:09:10,180
när storleken på ingångarna ökar.

214
00:09:10,180 --> 00:09:12,490
>> Om du kör i O (n) ² algoritm,

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

216
00:09:15,240 --> 00:09:17,170
en av de snabbast växande typerna,

217
00:09:17,170 --> 00:09:19,140
du verkligen börja märka avmattningen

218
00:09:19,140 --> 00:09:21,220
När du börjar arbeta med större datamängder.

219
00:09:21,220 --> 00:09:23,590
>> Det är asymptotisk komplexitet. Tack.