1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Jūs tikriausiai girdėjote, žmonės kalba apie greitai ar efektyvus algoritmas

2
00:00:10,950 --> 00:00:13,090
vykdyti savo konkrečią užduotį,

3
00:00:13,090 --> 00:00:16,110
Bet ką tiksliai tai reiškia algoritmą, greitai ir efektyviau?

4
00:00:16,110 --> 00:00:18,580
Na, tai kalbame ne apie matavimo realiu laiku,

5
00:00:18,580 --> 00:00:20,500
kaip sekundėmis arba minutėmis.

6
00:00:20,500 --> 00:00:22,220
Tai yra todėl, kad kompiuterinės įrangos

7
00:00:22,220 --> 00:00:24,260
ir programinės įrangos labai drastiškai.

8
00:00:24,260 --> 00:00:26,020
Mano programa gali veikti lėčiau, nei tavo,

9
00:00:26,020 --> 00:00:28,000
nes aš jį rodyti senesnius kompiuterius,

10
00:00:28,000 --> 00:00:30,110
arba dėl to, kad aš atsitikti, kad bus žaisti interneto vaizdo žaidimą

11
00:00:30,110 --> 00:00:32,670
tuo pačiu metu, kuris Žuvo visą mano atmintį,

12
00:00:32,670 --> 00:00:35,400
ar aš mano programa gali būti vykdoma naudojant įvairias programinės įrangos

13
00:00:35,400 --> 00:00:37,550
skirtingai bendrauja su mašina žemo lygio.

14
00:00:37,550 --> 00:00:39,650
Tai kaip lyginti obuolius ir apelsinus.

15
00:00:39,650 --> 00:00:41,940
Tiesiog, nes mano lėtesnis kompiuteris užtrunka ilgiau

16
00:00:41,940 --> 00:00:43,410
kaip tavo duoti atsakymą

17
00:00:43,410 --> 00:00:45,510
nereiškia, turite efektyvesnis algoritmas.

18
00:00:45,510 --> 00:00:48,830
>> Taip, nes mes negali tiesiogiai palyginti programų Runtimes

19
00:00:48,830 --> 00:00:50,140
sekundžių ar minučių,

20
00:00:50,140 --> 00:00:52,310
kaip mes lyginti 2 skirtingus algoritmus

21
00:00:52,310 --> 00:00:55,030
nepriklausomai nuo jų įrangos ar programinės įrangos aplinką?

22
00:00:55,030 --> 00:00:58,000
Norėdami sukurti vienodą matavimo algoritmų efektyvumą,

23
00:00:58,000 --> 00:01:00,360
kompiuterių mokslininkai ir matematikai, sukūrė

24
00:01:00,360 --> 00:01:03,830
koncepcijos matavimo asimptotinio programos sudėtingumą

25
00:01:03,830 --> 00:01:06,110
ir žymėjimą, vadinamą "Big Ohnotation"

26
00:01:06,110 --> 00:01:08,320
aprašyti tai.

27
00:01:08,320 --> 00:01:10,820
Formalus apibrėžimas yra tas, kad funkcija f (x)

28
00:01:10,820 --> 00:01:13,390
veikia g tvarka (x)

29
00:01:13,390 --> 00:01:15,140
jei egzistuoja šiek tiek (x) vertę, x ₀ ir

30
00:01:15,140 --> 00:01:17,630
kai konstanta, C, kuris

31
00:01:17,630 --> 00:01:19,340
f (x) yra mažesnis arba lygus

32
00:01:19,340 --> 00:01:21,230
kad nuolatinis kartus g (x)

33
00:01:21,230 --> 00:01:23,190
su visais x didesnis nei X ₀.

34
00:01:23,190 --> 00:01:25,290
>> Tačiau nereikia būti nubaidyta formalaus apibrėžimo.

35
00:01:25,290 --> 00:01:28,020
Ką tai iš tikrųjų reiškia mažiau teoriniu aspektu?

36
00:01:28,020 --> 00:01:30,580
Na, tai iš esmės būdas analizuoti

37
00:01:30,580 --> 00:01:33,580
kaip greitai programos Runtime auga asimptotiškai.

38
00:01:33,580 --> 00:01:37,170
Tai reiškia, kad, kaip savo sąnaudas dydis didėja link begalybės,

39
00:01:37,170 --> 00:01:41,390
sako, jūs rūšiavimas dydžio 1000 masyvas, masyvo dydis 10.

40
00:01:41,390 --> 00:01:44,950
Kaip savo programą Runtime augti?

41
00:01:44,950 --> 00:01:47,390
Pavyzdžiui, įsivaizduokite, skaičiavimas simbolių skaičių

42
00:01:47,390 --> 00:01:49,350
į eilutę paprasčiausias būdas

43
00:01:49,350 --> 00:01:51,620
 vaikščioti per visą eilutę

44
00:01:51,620 --> 00:01:54,790
laiškas raidžių ir kiekvieno požymio skaitiklis pridedant 1.

45
00:01:55,700 --> 00:01:58,420
Šis algoritmas yra sakoma, kad paleisti eilutėmis

46
00:01:58,420 --> 00:02:00,460
dėl ženklų skaičiaus,

47
00:02:00,460 --> 00:02:02,670
"N" į eilutę.

48
00:02:02,670 --> 00:02:04,910
Trumpai tariant, jis veikia O (n).

49
00:02:05,570 --> 00:02:07,290
Kodėl taip yra?

50
00:02:07,290 --> 00:02:09,539
Na, naudojant šį metodą, laikas, reikalingas

51
00:02:09,539 --> 00:02:11,300
feed visą eilutę

52
00:02:11,300 --> 00:02:13,920
yra proporcingas simbolių skaičių.

53
00:02:13,920 --> 00:02:16,480
Skaičiavimo simbolių skaičių 20 simbolių ilgio eilutę

54
00:02:16,480 --> 00:02:18,580
ketina imtis dvigubai ilgiau, nes joje

55
00:02:18,580 --> 00:02:20,330
suskaičiuoti simbolių 10 simbolių ilgio eilutę,

56
00:02:20,330 --> 00:02:23,000
nes jūs turite pažvelgti į visų simbolių

57
00:02:23,000 --> 00:02:25,740
ir kiekvienas personažas mano laikas pažvelgti į tą pačią sumą.

58
00:02:25,740 --> 00:02:28,050
Kaip jums padidinti simbolių skaičių,

59
00:02:28,050 --> 00:02:30,950
Runtime didėja linijiniu būdu su įėjimo ilgio.

60
00:02:30,950 --> 00:02:33,500
>> Dabar įsivaizduokite, jei jums nuspręsti, kad linijinis laiko,

61
00:02:33,500 --> 00:02:36,390
O (n), tiesiog nebuvo pakankamai greitai jums?

62
00:02:36,390 --> 00:02:38,750
Gal jūs saugoti didžiulius eilutes,

63
00:02:38,750 --> 00:02:40,450
ir jūs negalite sau leisti papildomo laiko, kad būtų priimti

64
00:02:40,450 --> 00:02:44,000
feed visus savo simbolių, skaičiuojant po vieną.

65
00:02:44,000 --> 00:02:46,650
Taigi, jūs nuspręsite išbandyti kažką kita.

66
00:02:46,650 --> 00:02:49,270
Ką daryti, jei nutiktų jau saugoti simbolių skaičių

67
00:02:49,270 --> 00:02:52,690
į eilutę, tarkim, į kintamąjį vadinamą "ilg"

68
00:02:52,690 --> 00:02:54,210
anksti programos,

69
00:02:54,210 --> 00:02:57,800
prieš jus net saugomi pirmųjų savo eilutę simbolį?

70
00:02:57,800 --> 00:02:59,980
Tada visi jūs turite padaryti dabar sužinoti eilutės ilgis,

71
00:02:59,980 --> 00:03:02,570
yra patikrinti, kokia kintamojo reikšmė yra.

72
00:03:02,570 --> 00:03:05,530
Jūs neturite pažvelgti į eilutę, ne visi,

73
00:03:05,530 --> 00:03:08,160
ir prie kintamojo vertę kaip len

74
00:03:08,160 --> 00:03:11,100
asimptotiškai nuolatinio laiko operacija,

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

76
00:03:13,070 --> 00:03:17,110
Kodėl taip yra? Na, prisiminkite, ką asimptotinė sudėtingumo.

77
00:03:17,110 --> 00:03:19,100
Kaip Runtime dydžio pasikeitimas,

78
00:03:19,100 --> 00:03:21,400
iš savo sąnaudas auga?

79
00:03:21,400 --> 00:03:24,630
>> Pasakyti bandėte gauti didesnį eilutės simbolių skaičių.

80
00:03:24,630 --> 00:03:26,960
Na, tai nesvarbu kiek daug jums padaryti eilutę,

81
00:03:26,960 --> 00:03:28,690
net milijonų ženklai ilgai,

82
00:03:28,690 --> 00:03:31,150
visi jūs turite padaryti, kad surastumėte styginių ilgio su šio požiūrio,

83
00:03:31,150 --> 00:03:33,790
skaityti kintamojo len vertę,

84
00:03:33,790 --> 00:03:35,440
kuri jau padaryta.

85
00:03:35,440 --> 00:03:38,200
Įvesties ilgis, tai yra, eilutę, kurį bandote rasti ilgis,

86
00:03:38,200 --> 00:03:41,510
neturi įtakos, kaip greitai jūsų programa veikia.

87
00:03:41,510 --> 00:03:44,550
Tai savo programos dalis veikia vienodai greitai vieną simbolių ilgio eilutę

88
00:03:44,550 --> 00:03:46,170
ir tūkstančių simbolių eilutė,

89
00:03:46,170 --> 00:03:49,140
ir tai, kodėl ši programa būtų minima kaip veikia nuolat

90
00:03:49,140 --> 00:03:51,520
atsižvelgiant į įėjimo dydžio.

91
00:03:51,520 --> 00:03:53,920
>> Žinoma, nėra trūkumas.

92
00:03:53,920 --> 00:03:55,710
Jums praleisti daugiau atminties jūsų kompiuteryje

93
00:03:55,710 --> 00:03:57,380
saugoti kintamąjį

94
00:03:57,380 --> 00:03:59,270
papildomo laiko, pateksite

95
00:03:59,270 --> 00:04:01,490
padaryti faktinio saugojimo kintamojo,

96
00:04:01,490 --> 00:04:03,390
bet esmė vis dar stovi,

97
00:04:03,390 --> 00:04:05,060
išsiaiškinti, kaip ilgai jūsų eilutė

98
00:04:05,060 --> 00:04:07,600
nepriklauso nuo ilgio eilutę, ne visi.

99
00:04:07,600 --> 00:04:10,720
Taigi, ji veikia O (1) arba pastovaus laiko.

100
00:04:10,720 --> 00:04:13,070
Tai, žinoma, nebūtinai turi reikšti

101
00:04:13,070 --> 00:04:15,610
kad jūsų kodas veikia 1 žingsnio,

102
00:04:15,610 --> 00:04:17,470
bet nesvarbu, kiek žingsnių jis yra,

103
00:04:17,470 --> 00:04:20,019
jei jis neturi pakeisti sąnaudų dydžio,

104
00:04:20,019 --> 00:04:23,420
jis vis dar yra asimptotiškai pastovus, kurią mes atstovaujame kaip O (1).

105
00:04:23,420 --> 00:04:25,120
>> Kaip jums greičiausiai gali atspėti,

106
00:04:25,120 --> 00:04:27,940
yra daug skirtingų Big O katilas matuoti algoritmai.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmai yra asimptotiškai lėčiau nei O (n) algoritmų.

108
00:04:32,980 --> 00:04:35,910
Tai yra, kaip elementų skaičius (n) auga,

109
00:04:35,910 --> 00:04:39,280
galiausiai O (n) ² algoritmai bus daugiau laiko

110
00:04:39,280 --> 00:04:41,000
nei O (n) algoritmai paleisti.

111
00:04:41,000 --> 00:04:43,960
Tai nereiškia, kad O (n) algoritmai visada paleisti greičiau

112
00:04:43,960 --> 00:04:46,410
nei O (n) ² algoritmų, net toje pačioje aplinkoje,

113
00:04:46,410 --> 00:04:48,080
tame pačiame kompiuteryje.

114
00:04:48,080 --> 00:04:50,180
Gal mažų sąnaudų dydžio,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algoritmas iš tiesų gali dirbti greičiau,

116
00:04:52,900 --> 00:04:55,450
bet, galų gale, įvesties dydis didina

117
00:04:55,450 --> 00:04:58,760
link begalybės, O (n) ² algoritmo veikimo laikas

118
00:04:58,760 --> 00:05:02,000
galų gale užtemimas Runtime O (n) algoritmas.

119
00:05:02,000 --> 00:05:04,230
Tiesiog kaip ir bet kvadratin matematinė funkcija

120
00:05:04,230 --> 00:05:06,510
 galų gale aplenkti bet kurios tiesinės funkcijos,

121
00:05:06,510 --> 00:05:09,200
nesvarbu, kiek galvos pradėti Tiesinės funkcijos prasideda nuo.

122
00:05:10,010 --> 00:05:12,000
Jei dirbate su dideliais duomenų kiekiais,

123
00:05:12,000 --> 00:05:15,510
algoritmai, kurie veikia O (n) ² laikas tikrai gali baigtis lėtėja savo programą,

124
00:05:15,510 --> 00:05:17,770
bet mažų dydžių įvesties,

125
00:05:17,770 --> 00:05:19,420
tikriausiai net nepastebi.

126
00:05:19,420 --> 00:05:21,280
>> Kitas asimptotinė sudėtingumas yra,

127
00:05:21,280 --> 00:05:24,420
logaritminė laikas, O (log n).

128
00:05:24,420 --> 00:05:26,340
Algoritmą, kuris veikia tai greitai pavyzdys

129
00:05:26,340 --> 00:05:29,060
yra klasikinis dvejetainis paieškos algoritmas,

130
00:05:29,060 --> 00:05:31,850
rasti elementą jau surūšiuoti elementų sąrašo.

131
00:05:31,850 --> 00:05:33,400
>> Jei jūs neturite žinoti, dvejetainis paieškos,

132
00:05:33,400 --> 00:05:35,170
Aš paaiškinti jums tikrai greitai.

133
00:05:35,170 --> 00:05:37,020
Tarkime, kad jūs ieškote skaičiumi 3

134
00:05:37,020 --> 00:05:40,200
šiame sveikųjų skaičių masyvas.

135
00:05:40,200 --> 00:05:42,140
Jis žiūri į vidurinės masyvo elementu

136
00:05:42,140 --> 00:05:46,830
ir klausia: "Ar elementas Noriu didesnis nei, lygus arba mažesnis nei šis?"

137
00:05:46,830 --> 00:05:49,150
Jei tai vienodos, tai puikus. Jums rasti elementą, ir baigsite.

138
00:05:49,150 --> 00:05:51,300
Jei jis didesnis, tuomet jūs žinote, elementas

139
00:05:51,300 --> 00:05:53,440
turi būti dešinėje pusėje masyvo,

140
00:05:53,440 --> 00:05:55,200
ir jūs galite tik pažvelgti į ateitį,

141
00:05:55,200 --> 00:05:57,690
ir jei jis mažesnis, tuomet jūs žinote, jis turi būti kairėje pusėje.

142
00:05:57,690 --> 00:06:00,980
Šis procesas kartojamas su mažesnio dydžio masyvas

143
00:06:00,980 --> 00:06:02,870
iki teisingas elementas nerasta.

144
00:06:08,080 --> 00:06:11,670
>> Šis galingas algoritmas sumažina masyvo dydį per pusę kiekvienos operacijos.

145
00:06:11,670 --> 00:06:14,080
Taigi, rasti elementą rūšiuotas masyvo dydis 8,

146
00:06:14,080 --> 00:06:16,170
ne daugiau kaip (prisijungti ₂ 8),

147
00:06:16,170 --> 00:06:18,450
3 iš šių operacijų arba

148
00:06:18,450 --> 00:06:22,260
vidurinįjį elementą patikrinti, tada pjovimo masyvo pusę bus reikalaujama,

149
00:06:22,260 --> 00:06:25,670
o dydis 16 masyvas užima (log ₂ 16)

150
00:06:25,670 --> 00:06:27,480
arba 4 operacijas.

151
00:06:27,480 --> 00:06:30,570
Tai tik 1 daugiau operacija dvigubai dydžio masyvą.

152
00:06:30,570 --> 00:06:32,220
Padvigubinti masyvo dydį

153
00:06:32,220 --> 00:06:35,160
padidina Runtime tik 1 riekė šio kodekso.

154
00:06:35,160 --> 00:06:37,770
Vėlgi, tikrinant viduryje sąrašo elementą, tada padalijimas.

155
00:06:37,770 --> 00:06:40,440
Taigi, tai sakė veikti logaritminis metu,

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

157
00:06:42,440 --> 00:06:44,270
Bet palaukit, jūs sakote,

158
00:06:44,270 --> 00:06:47,510
ne tai priklauso nuo to, kur sąraše elementas jūs ieškote?

159
00:06:47,510 --> 00:06:50,090
Ką daryti, jeigu pirmasis elementas pažvelgti būna, kad teisingas?

160
00:06:50,090 --> 00:06:52,040
Tada, tai trunka tik 1 operaciją

161
00:06:52,040 --> 00:06:54,310
nesvarbu, kaip didelis sąrašas.

162
00:06:54,310 --> 00:06:56,310
>> Na, tai kodėl kompiuterių mokslininkai turi daugiau terminų

163
00:06:56,310 --> 00:06:58,770
asimptotinio sudėtingumo, kuri atspindi geriausiu atveju

164
00:06:58,770 --> 00:07:01,050
ir blogiausią algoritmą spektakliai.

165
00:07:01,050 --> 00:07:03,320
Tiksliau, viršutinė ir apatinė ribos

166
00:07:03,320 --> 00:07:05,090
Runtime.

167
00:07:05,090 --> 00:07:07,660
Geriausiu atveju dvejetainis paieškos elementas yra

168
00:07:07,660 --> 00:07:09,330
teisę ten per vidurį,

169
00:07:09,330 --> 00:07:11,770
ir jūs gaunate jį nuolat,

170
00:07:11,770 --> 00:07:14,240
nesvarbu, kaip didelis likusi masyvo.

171
00:07:15,360 --> 00:07:17,650
Tai simbolis, naudojamas Ω.

172
00:07:17,650 --> 00:07:19,930
Taigi, šis algoritmas yra sakoma, kad paleisti Ω (1).

173
00:07:19,930 --> 00:07:21,990
Geriausiu atveju, ji nustato elementą greitai,

174
00:07:21,990 --> 00:07:24,200
nesvarbu, kaip didelis masyvas,

175
00:07:24,200 --> 00:07:26,050
bet blogiausiu atveju,

176
00:07:26,050 --> 00:07:28,690
turi atlikti (log n) padalinti patikrinimus

177
00:07:28,690 --> 00:07:31,030
masyvo rasti tinkamą elementą.

178
00:07:31,030 --> 00:07:34,270
Blogiausiu atveju viršutinės ribos yra nurodytos su dideliu "O", kad jūs jau žinote.

179
00:07:34,270 --> 00:07:38,080
Taigi, tai O (log n), o Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Linijinis paieška, priešingai,

181
00:07:40,680 --> 00:07:43,220
, kuriame jūs vaikščioti per kiekvienas masyvo elementas

182
00:07:43,220 --> 00:07:45,170
rasti vieną norite,

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

184
00:07:47,420 --> 00:07:49,430
Vėlgi, pirmasis elementas norite.

185
00:07:49,430 --> 00:07:51,930
Taigi, nesvarbu, kaip didelis masyvas.

186
00:07:51,930 --> 00:07:54,840
Blogiausiu atveju, tai paskutinis masyvo elementas.

187
00:07:54,840 --> 00:07:58,560
Taigi, jūs turite pereiti per visų n elementų masyvo jį rasti,

188
00:07:58,560 --> 00:08:02,170
patinka, jei jūs ieškote už 3.

189
00:08:04,320 --> 00:08:06,030
Taigi, ji veikia O (n) laiko

190
00:08:06,030 --> 00:08:09,330
, nes jis proporcingas masyvo elementų skaičius.

191
00:08:10,800 --> 00:08:12,830
>> Dar vienas simbolis, naudojamas Θ.

192
00:08:12,830 --> 00:08:15,820
Tai gali būti naudojama aprašyti algoritmai, kur atskiram geriausius ir blogiausius atvejus

193
00:08:15,820 --> 00:08:17,440
yra tas pats.

194
00:08:17,440 --> 00:08:20,390
Tai string ilgio algoritmų, mes kalbėjome apie anksčiau atveju.

195
00:08:20,390 --> 00:08:22,780
Tai yra, jei mes saugome jį į kintamąjį prieš

196
00:08:22,780 --> 00:08:25,160
mes saugome eilutę ir vėliau pasiekti nuolat.

197
00:08:25,160 --> 00:08:27,920
Nesvarbu, kokiu numeriu

198
00:08:27,920 --> 00:08:30,130
mes saugoti toje kintamojo, mes turime pažvelgti į ją.

199
00:08:33,110 --> 00:08:35,110
Geriausiu atveju, mes žiūrime į jį

200
00:08:35,110 --> 00:08:37,120
ir rasti eilutės ilgį.

201
00:08:37,120 --> 00:08:39,799
Taigi Ω (1) arba geriausiu atveju nuolatinio laiko.

202
00:08:39,799 --> 00:08:41,059
Blogiausiu atveju,

203
00:08:41,059 --> 00:08:43,400
mes žiūrime į ją ir rasti eilutės ilgį.

204
00:08:43,400 --> 00:08:47,300
Taigi, O (1) arba nuolatinio laiko blogiausiu atveju.

205
00:08:47,300 --> 00:08:49,180
Taip, nes geriausiu atveju ir blogiausiu atveju yra tas pats,

206
00:08:49,180 --> 00:08:52,520
tai galima teigti, paleisti Θ (1) metu.

207
00:08:54,550 --> 00:08:57,010
>> Apibendrinant galima pasakyti, mes turime gerų būdų, samprotauti apie kodus efektyvumo

208
00:08:57,010 --> 00:09:00,110
nežinant nieko apie realaus pasaulio laiką, jos imasi vykdyti,

209
00:09:00,110 --> 00:09:02,270
, kuris veikia daug išorinių veiksnių,

210
00:09:02,270 --> 00:09:04,190
įskaitant skiriasi įrangos, programinės įrangos,

211
00:09:04,190 --> 00:09:06,040
arba savo kodą specifika.

212
00:09:06,040 --> 00:09:08,380
Be to, ji leidžia samprotauti ir apie tai, kas nutiks

213
00:09:08,380 --> 00:09:10,180
kai įėjimai didėja dydis.

214
00:09:10,180 --> 00:09:12,490
>> Jei vykdote O (n) ² algoritmas,

215
00:09:12,490 --> 00:09:15,240
arba, dar blogiau, O (2 ⁿ) algoritmas,

216
00:09:15,240 --> 00:09:17,170
viena iš sparčiausiai augančių rūšių,

217
00:09:17,170 --> 00:09:19,140
jūs tikrai pradėsite pastebėti sulėtėjimą

218
00:09:19,140 --> 00:09:21,220
kai pradėsite dirbti su didesniais duomenų kiekiais.

219
00:09:21,220 --> 00:09:23,590
>> Štai asimptotinė sudėtingumas. Ačiū.