1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Ön valószínűleg hallott az emberek beszélnek a gyors és hatékony algoritmus

2
00:00:10,950 --> 00:00:13,090
végrehajtására az adott feladat,

3
00:00:13,090 --> 00:00:16,110
de hogy pontosan mit jelent ez egy olyan algoritmust, hogy gyors vagy hatékony?

4
00:00:16,110 --> 00:00:18,580
Nos, ez nem beszél a mérés valós időben,

5
00:00:18,580 --> 00:00:20,500
mint a másodperc vagy perc.

6
00:00:20,500 --> 00:00:22,220
Ez azért van, mert számítógépes hardver

7
00:00:22,220 --> 00:00:24,260
és a szoftver változik drasztikusan.

8
00:00:24,260 --> 00:00:26,020
A program esetleg lassabban futnak, mint a tiéd,

9
00:00:26,020 --> 00:00:28,000
mert én fut egy régebbi számítógép,

10
00:00:28,000 --> 00:00:30,110
vagy azért, mert megtörténhet, hogy játszik egy online videojáték

11
00:00:30,110 --> 00:00:32,670
ugyanakkor, amely domborító All My memória,

12
00:00:32,670 --> 00:00:35,400
vagy talán fut a programom a különböző szoftverek

13
00:00:35,400 --> 00:00:37,550
, amely összeköttetésben van a készülék különböző alacsony szinten.

14
00:00:37,550 --> 00:00:39,650
Ez olyan, mint összehasonlítása alma és a narancs.

15
00:00:39,650 --> 00:00:41,940
Csak azért, mert a lassabb számítógépen hosszabb időt vesz igénybe

16
00:00:41,940 --> 00:00:43,410
, mint a tiéd, hogy adja vissza a választ

17
00:00:43,410 --> 00:00:45,510
nem jelenti azt, hogy a hatékonyabb algoritmust.

18
00:00:45,510 --> 00:00:48,830
>> Szóval, mivel nem tudjuk közvetlenül összehasonlítani a Runtimes programok

19
00:00:48,830 --> 00:00:50,140
másodpercben vagy percben,

20
00:00:50,140 --> 00:00:52,310
hogyan hasonlítsa össze 2 különböző algoritmusok

21
00:00:52,310 --> 00:00:55,030
függetlenül attól, hogy hardver vagy szoftver környezetben?

22
00:00:55,030 --> 00:00:58,000
Ahhoz, hogy hozzon létre egy egységes módon mérésének algoritmikus hatékonyság,

23
00:00:58,000 --> 00:01:00,360
számítógép tudósok és matematikusok kidolgozott

24
00:01:00,360 --> 00:01:03,830
koncepciók mérésére aszimptotikus bonyolultsága program

25
00:01:03,830 --> 00:01:06,110
és a jelölés az úgynevezett "Big Ohnotation"

26
00:01:06,110 --> 00:01:08,320
leírására ezt.

27
00:01:08,320 --> 00:01:10,820
A hivatalos meghatározás szerint a függvény f (x)

28
00:01:10,820 --> 00:01:13,390
fut a sorrendben g (x)

29
00:01:13,390 --> 00:01:15,140
ha létezik valami (x) érték, x ₀ és

30
00:01:15,140 --> 00:01:17,630
bizonyos konstans, C, amelyek

31
00:01:17,630 --> 00:01:19,340
f (x) kisebb vagy egyenlő, mint

32
00:01:19,340 --> 00:01:21,230
hogy állandó szor g (x)

33
00:01:21,230 --> 00:01:23,190
minden x-nél nagyobb x ₀.

34
00:01:23,190 --> 00:01:25,290
>> De ne félj elérhető a hivatalos meghatározás.

35
00:01:25,290 --> 00:01:28,020
Mit jelent ez valójában azt jelenti, a kevésbé elméleti szempontból?

36
00:01:28,020 --> 00:01:30,580
Nos, ez alapvetően egy módja elemzése

37
00:01:30,580 --> 00:01:33,580
milyen gyors a program futásidejű nő aszimptotikusan.

38
00:01:33,580 --> 00:01:37,170
Azaz, mivel a méret a bemenetek felé növekszik végtelen,

39
00:01:37,170 --> 00:01:41,390
azt mondják, te válogatás tömb mérete 1000 képest egy sor 10-es méret.

40
00:01:41,390 --> 00:01:44,950
Hogyan futási a programunk nő?

41
00:01:44,950 --> 00:01:47,390
Képzeljük el például, számítva a karakterek száma

42
00:01:47,390 --> 00:01:49,350
egy string a legegyszerűbb módon

43
00:01:49,350 --> 00:01:51,620
 gyalog az egész szöveg

44
00:01:51,620 --> 00:01:54,790
levél-by-levél és hogy 1 a számláló minden egyes karakter.

45
00:01:55,700 --> 00:01:58,420
Ez az algoritmus azt mondta, hogy fut a lineáris időben

46
00:01:58,420 --> 00:02:00,460
tekintetében a karakterek száma,

47
00:02:00,460 --> 00:02:02,670
'N' a string.

48
00:02:02,670 --> 00:02:04,910
Röviden, ez fut O (n).

49
00:02:05,570 --> 00:02:07,290
Miért van ez?

50
00:02:07,290 --> 00:02:09,539
Nos, ezt a módszert, a szükséges időt

51
00:02:09,539 --> 00:02:11,300
áthalad a teljes szöveg

52
00:02:11,300 --> 00:02:13,920
arányos a karakterek számát.

53
00:02:13,920 --> 00:02:16,480
Számlálása a karakterek száma a 20-karakterlánc

54
00:02:16,480 --> 00:02:18,580
fog tartani az kétszer mivel addig, amíg

55
00:02:18,580 --> 00:02:20,330
számolni a karaktereket a 10-karakterlánc,

56
00:02:20,330 --> 00:02:23,000
mert meg kell nézni az összes karakter

57
00:02:23,000 --> 00:02:25,740
és minden karakter úgy ugyanannyi időt, hogy nézd meg.

58
00:02:25,740 --> 00:02:28,050
Ahogy növeli a karakterek száma,

59
00:02:28,050 --> 00:02:30,950
a futásidejű növeli lineárisan a bemenet hosszát.

60
00:02:30,950 --> 00:02:33,500
>> Most képzeld el, ha úgy dönt, hogy a lineáris idő,

61
00:02:33,500 --> 00:02:36,390
O (n), csak nem volt elég gyors az Ön számára?

62
00:02:36,390 --> 00:02:38,750
Talán tárolására hatalmas húrok,

63
00:02:38,750 --> 00:02:40,450
, és nem engedheti meg magának az extra időt venne

64
00:02:40,450 --> 00:02:44,000
áthalad minden a karakter számít egy-az-egy.

65
00:02:44,000 --> 00:02:46,650
Szóval, úgy dönt, hogy megpróbál valami mást.

66
00:02:46,650 --> 00:02:49,270
Mi lenne, ha történne már tárolni a karakterek száma

67
00:02:49,270 --> 00:02:52,690
A húr, mondjuk, egy változó úgynevezett "len"

68
00:02:52,690 --> 00:02:54,210
korai szakaszában a program,

69
00:02:54,210 --> 00:02:57,800
mielőtt még tárolja a legelső karakter a szöveg?

70
00:02:57,800 --> 00:02:59,980
Aztán csak annyit kéne tenni most, hogy megtudja, a húr hossza,

71
00:02:59,980 --> 00:03:02,570
van ellenőrizni, hogy milyen az értéke a változó.

72
00:03:02,570 --> 00:03:05,530
Ugye nem kell nézni a string maga egyáltalán,

73
00:03:05,530 --> 00:03:08,160
és nyissa meg a változó értékét, mint a len tekinthető

74
00:03:08,160 --> 00:03:11,100
egy aszimptotikusan konstans idejű működés,

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

76
00:03:13,070 --> 00:03:17,110
Miért van ez? Nos, emlékszem, milyen aszimptotikus komplexitás jelent.

77
00:03:17,110 --> 00:03:19,100
Hogyan működik a futási változás a méret

78
00:03:19,100 --> 00:03:21,400
a bemenetek nő?

79
00:03:21,400 --> 00:03:24,630
>> Mondja el, hogy akarták, hogy a karakterek száma egy nagyobb string.

80
00:03:24,630 --> 00:03:26,960
Nos, ez nem számít, milyen nagy legyenek a húr,

81
00:03:26,960 --> 00:03:28,690
még egy millió karakter hosszú,

82
00:03:28,690 --> 00:03:31,150
csak annyit kéne tennie, hogy megtalálja a string hosszának ezzel a megközelítéssel,

83
00:03:31,150 --> 00:03:33,790
hogy felolvassa az érték a változó len,

84
00:03:33,790 --> 00:03:35,440
amit már elért.

85
00:03:35,440 --> 00:03:38,200
A bemeneti hossz, azaz a string hossza akarsz találni,

86
00:03:38,200 --> 00:03:41,510
nem érinti egyáltalán milyen gyors a program fut.

87
00:03:41,510 --> 00:03:44,550
Ez a része a program fut egyformán gyors egy karakterlánc

88
00:03:44,550 --> 00:03:46,170
és ezer-karakterlánc,

89
00:03:46,170 --> 00:03:49,140
és ez az, amiért ezt a programot a továbbiakban mint fut konstans id

90
00:03:49,140 --> 00:03:51,520
tekintetében a bemeneti méret.

91
00:03:51,520 --> 00:03:53,920
>> Persze, van egy hátránya.

92
00:03:53,920 --> 00:03:55,710
Töltesz extra memóriát a számítógépen

93
00:03:55,710 --> 00:03:57,380
tárolására a változó

94
00:03:57,380 --> 00:03:59,270
és az extra időt, akkor

95
00:03:59,270 --> 00:04:01,490
tenni a tényleges tárolása változó,

96
00:04:01,490 --> 00:04:03,390
de a lényeg még mindig fennáll,

97
00:04:03,390 --> 00:04:05,060
kideríteni, milyen hosszú a karakterlánc

98
00:04:05,060 --> 00:04:07,600
nem függ a hossza a húr egyáltalán.

99
00:04:07,600 --> 00:04:10,720
Szóval, ez fut O (1) vagy konstans időt.

100
00:04:10,720 --> 00:04:13,070
Ez természetesen nem jelenti

101
00:04:13,070 --> 00:04:15,610
hogy a kód fut 1 lépés,

102
00:04:15,610 --> 00:04:17,470
de nem számít, hogy hány lépés van,

103
00:04:17,470 --> 00:04:20,019
ha nem változik a mérete a bemenet,

104
00:04:20,019 --> 00:04:23,420
ez még mindig aszimptotikusan konstans, amely az általunk képviselt, mint O (1).

105
00:04:23,420 --> 00:04:25,120
>> Mint tudod talán kitalálni,

106
00:04:25,120 --> 00:04:27,940
sok különböző nagy O Runtimes mérésére algoritmusok.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmusok aszimptotikusan lassabb, mint O (n) algoritmusok.

108
00:04:32,980 --> 00:04:35,910
Azaz, mivel az elemek száma (n) nő,

109
00:04:35,910 --> 00:04:39,280
végül O (n) ² algoritmusok több időre lesz szükség

110
00:04:39,280 --> 00:04:41,000
mint O (n) algoritmusok futtatására.

111
00:04:41,000 --> 00:04:43,960
Ez nem azt jelenti, O (n) algoritmusok mindig fut gyorsabban

112
00:04:43,960 --> 00:04:46,410
mint O (n) ² algoritmusok, még ugyanabban a környezetben,

113
00:04:46,410 --> 00:04:48,080
ugyanazon a hardveren.

114
00:04:48,080 --> 00:04:50,180
Lehet, hogy a kis méretű input,

115
00:04:50,180 --> 00:04:52,900
 az O (n) ² algoritmus meglehet ténylegesen munkát gyorsabban,

116
00:04:52,900 --> 00:04:55,450
de, végül, mivel a bemeneti méret növekszik

117
00:04:55,450 --> 00:04:58,760
felé végtelen, az O (n) ² algoritmus a futási

118
00:04:58,760 --> 00:05:02,000
végül oltja a futásidejű az O (n) algoritmus.

119
00:05:02,000 --> 00:05:04,230
Mint minden kvadratikus matematikai függvény

120
00:05:04,230 --> 00:05:06,510
 végül előzni minden lineáris függvény,

121
00:05:06,510 --> 00:05:09,200
nem számít, hogy mennyi egy fej kezdeni a lineáris függvény indul.

122
00:05:10,010 --> 00:05:12,000
Ha dolgozik a nagy mennyiségű adat,

123
00:05:12,000 --> 00:05:15,510
algoritmusok futnak O (n) ² idő tényleg végén lassul a program,

124
00:05:15,510 --> 00:05:17,770
de a kis méretű input,

125
00:05:17,770 --> 00:05:19,420
akkor valószínűleg észre sem.

126
00:05:19,420 --> 00:05:21,280
>> További aszimptotikus összetettség,

127
00:05:21,280 --> 00:05:24,420
logaritmikus idő, O (log n).

128
00:05:24,420 --> 00:05:26,340
Egy példa egy algoritmus, hogy fut ilyen gyorsan

129
00:05:26,340 --> 00:05:29,060
a klasszikus bináris keresés algoritmus,

130
00:05:29,060 --> 00:05:31,850
megállapításának egyik eleme, egy már rendezett lista elemeit.

131
00:05:31,850 --> 00:05:33,400
>> Ha nem tudja, mi a bináris keresést tesz,

132
00:05:33,400 --> 00:05:35,170
Majd elmondom neked nagyon gyorsan.

133
00:05:35,170 --> 00:05:37,020
Tegyük fel, hogy keres a 3-as szám

134
00:05:37,020 --> 00:05:40,200
e tömb egészek.

135
00:05:40,200 --> 00:05:42,140
Úgy tűnik, a középső elem a tömb

136
00:05:42,140 --> 00:05:46,830
és megkérdezi: "Van az elemet szeretnék nagyobb, egyenlő vagy kisebb, mint ez?"

137
00:05:46,830 --> 00:05:49,150
Ha ez egyforma, akkor nagyszerű. Megtalálta az elem, és kész.

138
00:05:49,150 --> 00:05:51,300
Ha ez nagyobb, akkor tudja az elemet

139
00:05:51,300 --> 00:05:53,440
kell lennie a jobb oldalon a tömb,

140
00:05:53,440 --> 00:05:55,200
és akkor csak nézd meg, hogy a jövőben,

141
00:05:55,200 --> 00:05:57,690
és ha ez kisebb, akkor tudod, hogy kell, hogy legyen a bal oldalon.

142
00:05:57,690 --> 00:06:00,980
Ez a folyamat azután megismételjük a kisebb méretű tömb

143
00:06:00,980 --> 00:06:02,870
amíg a helyes elem található.

144
00:06:08,080 --> 00:06:11,670
>> Ez a nagy teljesítményű algoritmus csökkenti a tömb mérete fél minden művelet.

145
00:06:11,670 --> 00:06:14,080
Tehát találni egy eleme a rendezett tömb mérete 8,

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

147
00:06:16,170 --> 00:06:18,450
vagy 3 E műveletek,

148
00:06:18,450 --> 00:06:22,260
ellenőrzése a középső elem, akkor a vágás a tömb ketté lesz szükség,

149
00:06:22,260 --> 00:06:25,670
mivel a tömb mérete 16 előnyben (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
vagy 4 műveletek.

151
00:06:27,480 --> 00:06:30,570
Ez csak 1 további művelet kétszeres méretű tömb.

152
00:06:30,570 --> 00:06:32,220
Megkettőzése a méret a tömb

153
00:06:32,220 --> 00:06:35,160
növeli a futási csak 1 darab ezt a kódot.

154
00:06:35,160 --> 00:06:37,770
Ismét ellenőrzése középső eleme a listából, majd felosztása.

155
00:06:37,770 --> 00:06:40,440
Szóval, azt mondják, hogy működik logaritmikus időben,

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

157
00:06:42,440 --> 00:06:44,270
De várjunk csak, azt mondod,

158
00:06:44,270 --> 00:06:47,510
nem ez attól függ, a listában az elem, amit keresett?

159
00:06:47,510 --> 00:06:50,090
Mi van, ha az első elem nézel történik, hogy az igazit?

160
00:06:50,090 --> 00:06:52,040
Aztán, csak úgy 1 működését,

161
00:06:52,040 --> 00:06:54,310
nem számít, milyen nagy a lista.

162
00:06:54,310 --> 00:06:56,310
>> Nos, ezért számítógépes szakemberek több szempontból

163
00:06:56,310 --> 00:06:58,770
az aszimptotikus komplexitás, melyek tükrözik a legjobb eset

164
00:06:58,770 --> 00:07:01,050
és a legrosszabb teljesítményt az algoritmus.

165
00:07:01,050 --> 00:07:03,320
További megfelelően, a felső és alsó határ

166
00:07:03,320 --> 00:07:05,090
A futás közben.

167
00:07:05,090 --> 00:07:07,660
A legjobb esetben a bináris keresés, a mi elem

168
00:07:07,660 --> 00:07:09,330
ott a közepén,

169
00:07:09,330 --> 00:07:11,770
és megkapod azt a konstans időben,

170
00:07:11,770 --> 00:07:14,240
nem számít, milyen nagy a többi tömb.

171
00:07:15,360 --> 00:07:17,650
A szimbólum erre a célra használt Ω.

172
00:07:17,650 --> 00:07:19,930
Szóval, ez az algoritmus azt mondta, hogy fut Ω (1).

173
00:07:19,930 --> 00:07:21,990
A legjobb esetben azt állapítja meg, az elem gyorsan,

174
00:07:21,990 --> 00:07:24,200
nem számít, milyen nagy a tömb,

175
00:07:24,200 --> 00:07:26,050
de a legrosszabb esetben,

176
00:07:26,050 --> 00:07:28,690
azt elvégezni (log n) osztott ellenőrzések

177
00:07:28,690 --> 00:07:31,030
a tömb, hogy megtalálja a megfelelő elemet.

178
00:07:31,030 --> 00:07:34,270
Worst-case felső határt említi a nagy "O", hogy már tudod.

179
00:07:34,270 --> 00:07:38,080
Szóval, ez O (log n), de Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> A lineáris keresés, ezzel szemben,

181
00:07:40,680 --> 00:07:43,220
területén, ahol Ön séta minden elemét a tömb

182
00:07:43,220 --> 00:07:45,170
hogy megtalálja a kívánt,

183
00:07:45,170 --> 00:07:47,420
a legjobb esetben Ω (1).

184
00:07:47,420 --> 00:07:49,430
Ismét az első elem akarsz.

185
00:07:49,430 --> 00:07:51,930
Szóval, nem számít, milyen nagy a tömb.

186
00:07:51,930 --> 00:07:54,840
A legrosszabb esetben, ez az utolsó elem a tömbben.

187
00:07:54,840 --> 00:07:58,560
Szóval, meg kell járni az összes n elem a tömbben, hogy megtalálja azt,

188
00:07:58,560 --> 00:08:02,170
szeretném, ha kerestek a 3.

189
00:08:04,320 --> 00:08:06,030
Szóval, ez fut O (n) idő

190
00:08:06,030 --> 00:08:09,330
mert ez arányos az elemek száma a tömbben.

191
00:08:10,800 --> 00:08:12,830
>> Még egy jel használt Θ.

192
00:08:12,830 --> 00:08:15,820
Ezt felhasználhatjuk leírására algoritmusok ahol a legjobb és legrosszabb esetben

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

194
00:08:17,440 --> 00:08:20,390
Ez a helyzet a string-length algoritmusok beszéltünk korábban.

195
00:08:20,390 --> 00:08:22,780
Azaz, ha tárolja változó előtt

196
00:08:22,780 --> 00:08:25,160
tároljuk a húr és a hozzáférést később állandó időben.

197
00:08:25,160 --> 00:08:27,920
Nem számít, milyen szám

198
00:08:27,920 --> 00:08:30,130
vagyunk tárolja, hogy változó, akkor meg kell nézni.

199
00:08:33,110 --> 00:08:35,110
A legjobb eset az, hogy nézd meg

200
00:08:35,110 --> 00:08:37,120
és keresse meg a hosszát a húr.

201
00:08:37,120 --> 00:08:39,799
Szóval Ω (1) vagy legjobb esetben konstans idő.

202
00:08:39,799 --> 00:08:41,059
A legrosszabb eset az,

203
00:08:41,059 --> 00:08:43,400
nézzük, és megtalálni a hossza a húr.

204
00:08:43,400 --> 00:08:47,300
Szóval, O (1) vagy konstans idő legrosszabb esetben.

205
00:08:47,300 --> 00:08:49,180
Így, mivel a legjobb és legrosszabb esetek az ugyanaz,

206
00:08:49,180 --> 00:08:52,520
ezt lehet mondani, hogy futtatni Θ (1) idő.

207
00:08:54,550 --> 00:08:57,010
>> Összefoglalva, van jó módja, hogy ok kódokról hatékonyság

208
00:08:57,010 --> 00:09:00,110
ismerete nélkül semmit a valós idejű vesznek futtatni,

209
00:09:00,110 --> 00:09:02,270
által érintett sok külső tényezők,

210
00:09:02,270 --> 00:09:04,190
beleértve a különböző hardver, szoftver,

211
00:09:04,190 --> 00:09:06,040
vagy a sajátosságait a kódot.

212
00:09:06,040 --> 00:09:08,380
Azt is lehetővé teszi számunkra, hogy érvelni is arról, hogy mi fog történni

213
00:09:08,380 --> 00:09:10,180
, ha a méret a bemenetek növekszik.

214
00:09:10,180 --> 00:09:12,490
>> Ha fut O (n) ² algoritmus,

215
00:09:12,490 --> 00:09:15,240
vagy ami még rosszabb, egy O (2 ⁿ) algoritmus,

216
00:09:15,240 --> 00:09:17,170
az egyik leggyorsabban növekvő típusokat,

217
00:09:17,170 --> 00:09:19,140
akkor tényleg elkezdi észrevenni a lassulás

218
00:09:19,140 --> 00:09:21,220
ha elkezd dolgozni nagyobb mennyiségű adat.

219
00:09:21,220 --> 00:09:23,590
>> Ez aszimptotikus komplexitás. Kösz.