1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Vi verŝajne aŭdis homojn paroli pri rapida aŭ kompetenta algoritmo

2
00:00:10,950 --> 00:00:13,090
por ekzekuti vian apartan taskon,

3
00:00:13,090 --> 00:00:16,110
sed kion ekzakte signifas por algoritmo por esti rapida aŭ efika?

4
00:00:16,110 --> 00:00:18,580
Nu, ĝi ne parolas pri mezurado en reala tempo,

5
00:00:18,580 --> 00:00:20,500
kiel duaj aŭ minutoj.

6
00:00:20,500 --> 00:00:22,220
Ĉi tiu estas ĉar komputilaj aparataro

7
00:00:22,220 --> 00:00:24,260
kaj programaro varias draste.

8
00:00:24,260 --> 00:00:26,020
Mia programo povus kuri pli malrapida ol via,

9
00:00:26,020 --> 00:00:28,000
ĉar mi kurante ĝin sur malnovan komputilon,

10
00:00:28,000 --> 00:00:30,110
aŭ ĉar mi hazarde esti ludante interreta videoludo

11
00:00:30,110 --> 00:00:32,670
samtempe, kiu prenu al vi la tutan mia memoro,

12
00:00:32,670 --> 00:00:35,400
aŭ mi povus kuri mia programo por malsamaj programaro

13
00:00:35,400 --> 00:00:37,550
kiu komunikas kun la maŝino malsame je malalta nivelo.

14
00:00:37,550 --> 00:00:39,650
Estas kiel kompari pomojn kaj oranĝoj.

15
00:00:39,650 --> 00:00:41,940
Nur ĉar mia malrapida komputilo prenas plu

16
00:00:41,940 --> 00:00:43,410
ol la viaj redoni respondon

17
00:00:43,410 --> 00:00:45,510
ne signifas ke ili havas la pli kompetenta algoritmo.

18
00:00:45,510 --> 00:00:48,830
>> Do, cxar ne eblas rekte komparas la runtimes de programoj

19
00:00:48,830 --> 00:00:50,140
en duaj aŭ minutoj,

20
00:00:50,140 --> 00:00:52,310
kiel ni komparu 2 malsamaj algoritmoj

21
00:00:52,310 --> 00:00:55,030
sendepende de ilia aparataro aŭ programaro medio?

22
00:00:55,030 --> 00:00:58,000
Krei pli unuforma maniero de mezuri algoritma efikeco,

23
00:00:58,000 --> 00:01:00,360
komputilo sciencistoj kaj matematikistoj elpensis

24
00:01:00,360 --> 00:01:03,830
konceptoj por mezuri la asimptota komplekseco de programo

25
00:01:03,830 --> 00:01:06,110
kaj skribmaniero nomata 'Big Ohnotation'

26
00:01:06,110 --> 00:01:08,320
por priskribi ĉi.

27
00:01:08,320 --> 00:01:10,820
La formala difino estas tiu funkcio f (x)

28
00:01:10,820 --> 00:01:13,390
funkcias en la ordo de g (x)

29
00:01:13,390 --> 00:01:15,140
se tie ekzistas iu (x) valoro, x ₀ kaj

30
00:01:15,140 --> 00:01:17,630
iu konstanto, C, por kiu

31
00:01:17,630 --> 00:01:19,340
f (x) estas malpli ol aŭ egala al

32
00:01:19,340 --> 00:01:21,230
ke konstantan fojoj g (x)

33
00:01:21,230 --> 00:01:23,190
por ĉiuj x pli granda ol x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Sed ne havi timon for de la formala difino.

35
00:01:25,290 --> 00:01:28,020
Kion tio vere signifas en malpli teoriaj terminoj?

36
00:01:28,020 --> 00:01:30,580
Nu, estas esence formo de analizi

37
00:01:30,580 --> 00:01:33,580
kiel rapide programon de ekzekuto kreskas asimptote.

38
00:01:33,580 --> 00:01:37,170
Tio estas, al la grandeco de via enigoj pliigas al malfinio,

39
00:01:37,170 --> 00:01:41,390
diru vi ordigi tabelo de amplekso 1000 kompare kun tabelo de amplekso 10.

40
00:01:41,390 --> 00:01:44,950
Kiel la runtime de via programo kreski?

41
00:01:44,950 --> 00:01:47,390
Ekzemple, imagu rakonti la nombro da karakteroj

42
00:01:47,390 --> 00:01:49,350
en linio la plej simpla maniero

43
00:01:49,350 --> 00:01:51,620
 marŝante tra la tuta ĉeno

44
00:01:51,620 --> 00:01:54,790
letero-de-leteron kaj aldonante 1 al nombrilo por ĉiu signo.

45
00:01:55,700 --> 00:01:58,420
Ĉi tiu algoritmo estas dirita por kuri en lineara tempo

46
00:01:58,420 --> 00:02:00,460
rilate al la nombro da karakteroj,

47
00:02:00,460 --> 00:02:02,670
'N' en la kordo.

48
00:02:02,670 --> 00:02:04,910
Unuvorte, ĝi kuras en O (n).

49
00:02:05,570 --> 00:02:07,290
Kial tio estas?

50
00:02:07,290 --> 00:02:09,539
Nu, uzante tiun koncepton, la tempo bezonata

51
00:02:09,539 --> 00:02:11,300
tra la tuta ĉeno

52
00:02:11,300 --> 00:02:13,920
estas proporcia al la nombro de signoj.

53
00:02:13,920 --> 00:02:16,480
Rakontante la nombro da karakteroj en 20-karaktero ŝnuroj

54
00:02:16,480 --> 00:02:18,580
tuj prenos duoble longe kiel ĝi prenas

55
00:02:18,580 --> 00:02:20,330
por rakonti la gravuloj en 10-karaktero ŝnuroj,

56
00:02:20,330 --> 00:02:23,000
ĉar vi devas rigardi ĉiujn karakterojn

57
00:02:23,000 --> 00:02:25,740
kaj ĉiu karaktero portas la saman kvanton de tempo por rigardi.

58
00:02:25,740 --> 00:02:28,050
Kiel vi pliigos la nombron de karakteroj,

59
00:02:28,050 --> 00:02:30,950
la runtime pliigos lineare kun la eniro longa.

60
00:02:30,950 --> 00:02:33,500
>> Nun, imagu se vi decidas ke lineara tempo,

61
00:02:33,500 --> 00:02:36,390
O (n), simple ne estis sufiĉe rapide por vi?

62
00:02:36,390 --> 00:02:38,750
Eble vi stoki grandan kordoj,

63
00:02:38,750 --> 00:02:40,450
kaj vi ne povas pagi la ekstra tempo necesus

64
00:02:40,450 --> 00:02:44,000
tra ĉiuj liaj karakteroj rakonti unu-por-unu.

65
00:02:44,000 --> 00:02:46,650
Do, vi decidas provi ion malsaman.

66
00:02:46,650 --> 00:02:49,270
Kio se okazus al la jam konservi nombron de karakteroj

67
00:02:49,270 --> 00:02:52,690
en la ĉeno, ni diru, en variablo nomita 'len:

68
00:02:52,690 --> 00:02:54,210
frue en la programo,

69
00:02:54,210 --> 00:02:57,800
antaŭ vi eĉ stoki la unua gravulo en via ĉeno?

70
00:02:57,800 --> 00:02:59,980
Tiam, ĉiuj vi devus fari nun por eltrovi la kordo longo,

71
00:02:59,980 --> 00:03:02,570
estas kontroli kion la valoro de la variablo estas.

72
00:03:02,570 --> 00:03:05,530
Vi ne devus rigardi la kordo mem tute ne,

73
00:03:05,530 --> 00:03:08,160
kaj aliru la valoro de variablo kiel len konsideras

74
00:03:08,160 --> 00:03:11,100
an asimptote konstanta tempo operacio,

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

76
00:03:13,070 --> 00:03:17,110
Kial tio estas? Nu, memoru kion asimptota komplekseco signifas.

77
00:03:17,110 --> 00:03:19,100
Kiel funkcias la runtime ŝanĝon kiel la grandeco

78
00:03:19,100 --> 00:03:21,400
de via enigoj kreskas?

79
00:03:21,400 --> 00:03:24,630
>> Diru vi volis ricevi la nombro da karakteroj en pli grandan ĉenon.

80
00:03:24,630 --> 00:03:26,960
Nu, ne gravas kiom granda vi fari la ĉeno,

81
00:03:26,960 --> 00:03:28,690
eĉ miliono signojn longa,

82
00:03:28,690 --> 00:03:31,150
ĉiuj vi devus fari, por trovi la kordoj de longa kun ĉi alproksimiĝo,

83
00:03:31,150 --> 00:03:33,790
estas legi ekster la valoro de la variablo len,

84
00:03:33,790 --> 00:03:35,440
kion vi jam faris.

85
00:03:35,440 --> 00:03:38,200
La eniro longo, tio estas, la longo de la kordo vi provas trovi,

86
00:03:38,200 --> 00:03:41,510
ne afekti tute kiel rapide via programo kuras.

87
00:03:41,510 --> 00:03:44,550
Ĉi tiu parto de via programo kurus egale rapide en unu-karaktero ŝnuroj

88
00:03:44,550 --> 00:03:46,170
kaj mil-karaktero ŝnuroj,

89
00:03:46,170 --> 00:03:49,140
kaj tial tiu programo devus esti referita al kiel kurante en konstanta tempo

90
00:03:49,140 --> 00:03:51,520
kun respekto al la eniro grandeco.

91
00:03:51,520 --> 00:03:53,920
>> Kompreneble, ekzistas malavantaĝo.

92
00:03:53,920 --> 00:03:55,710
Vi elspezos ekstra memoro spaco sur via komputilo

93
00:03:55,710 --> 00:03:57,380
stoki la variablo

94
00:03:57,380 --> 00:03:59,270
kaj la ekstra tempo prenas vin

95
00:03:59,270 --> 00:04:01,490
fari la efektiva stokado de la variablo,

96
00:04:01,490 --> 00:04:03,390
sed la punkto ankoraŭ staras,

97
00:04:03,390 --> 00:04:05,060
eltrovi kiom longe viajn kordoj estis

98
00:04:05,060 --> 00:04:07,600
ne dependas de la longo de la kordo ajn.

99
00:04:07,600 --> 00:04:10,720
Do, ĝi kuras en O (1) aŭ konstanta tempo.

100
00:04:10,720 --> 00:04:13,070
Tiu certe ne devas signifi

101
00:04:13,070 --> 00:04:15,610
ke via kodo kuras en 1 paŝo,

102
00:04:15,610 --> 00:04:17,470
sed ne gravas kiom da paŝoj estas,

103
00:04:17,470 --> 00:04:20,019
se ĝi ne ŝanĝi kun la grandeco de la enigoj,

104
00:04:20,019 --> 00:04:23,420
ĝi estas ankoraŭ asimptote konstanta kiu ni reprezentas kiel O (1).

105
00:04:23,420 --> 00:04:25,120
>> Kiel vi povas verŝajne diveni,

106
00:04:25,120 --> 00:04:27,940
ekzistas multaj malsamaj granda a runtimes mezuri algoritmoj kun.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmoj estas asimptote pli malrapida ol O (n) algoritmoj.

108
00:04:32,980 --> 00:04:35,910
Tio estas, kiel la nombro de elementoj (n) kreskas,

109
00:04:35,910 --> 00:04:39,280
eventuale O (n) ² algoritmoj prenos pli da tempo

110
00:04:39,280 --> 00:04:41,000
ol O (n) algoritmoj por kuri.

111
00:04:41,000 --> 00:04:43,960
Tio ne signifas, O (n) algoritmoj ĉiam kuras pli rapide

112
00:04:43,960 --> 00:04:46,410
ol O (n) ² algoritmoj, eĉ en la sama medio,

113
00:04:46,410 --> 00:04:48,080
en la sama aparataro.

114
00:04:48,080 --> 00:04:50,180
Eble por malgrandaj enigo grandecoj,

115
00:04:50,180 --> 00:04:52,900
 la O (n) ² algoritmo povus reale labori rapide,

116
00:04:52,900 --> 00:04:55,450
sed, eventuale, kiel la enigo grandeco pliigas

117
00:04:55,450 --> 00:04:58,760
al malfinio, la O (n) ² algoritmo de ekzekuto

118
00:04:58,760 --> 00:05:02,000
eventuale eclipsar la runtime de la O (n) algoritmo.

119
00:05:02,000 --> 00:05:04,230
Same kiel iu kvadrata matematika funkcio

120
00:05:04,230 --> 00:05:06,510
 eventuale atingos ajnan lineara funkcio,

121
00:05:06,510 --> 00:05:09,200
kiom ajn en kapo komenci la lineara funkcio dividu kun.

122
00:05:10,010 --> 00:05:12,000
Se vi laboras kun grandaj kvantoj de datumoj,

123
00:05:12,000 --> 00:05:15,510
algoritmoj kiuj kuras en O (n) ² tempo povas vere fini ralentizando vian programon,

124
00:05:15,510 --> 00:05:17,770
sed por malgranda enigo grandecoj,

125
00:05:17,770 --> 00:05:19,420
vi probable eĉ ne rimarkos.

126
00:05:19,420 --> 00:05:21,280
>> Alia asimptota komplekseco estas,

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

128
00:05:24,420 --> 00:05:26,340
Ekzemplo de algoritmo kiu kuras ĉi rapide

129
00:05:26,340 --> 00:05:29,060
estas la klasika duuma serĉo algoritmo,

130
00:05:29,060 --> 00:05:31,850
por trovi elementon en jam-ordo listo de eroj.

131
00:05:31,850 --> 00:05:33,400
>> Se vi ne scias, kion duuma serĉo faras,

132
00:05:33,400 --> 00:05:35,170
Mi klarigas ĝin por vi vere rapide.

133
00:05:35,170 --> 00:05:37,020
Diru vi serĉas la numero 3

134
00:05:37,020 --> 00:05:40,200
en ĉi tiu tabelo de entjeroj.

135
00:05:40,200 --> 00:05:42,140
Ĝi rigardas la mezo ero de la tabelo

136
00:05:42,140 --> 00:05:46,830
kaj demando: "Ĉu la elemento Mi volas pli granda ol, egala al, aŭ malpli ol tio?"

137
00:05:46,830 --> 00:05:49,150
Se estas egalaj, tiam granda. Vi trovis la elementon, kaj vi faris.

138
00:05:49,150 --> 00:05:51,300
Se estas pli granda, tiam vi scias la elemento

139
00:05:51,300 --> 00:05:53,440
devas esti en la dekstra flanko de la tabelo,

140
00:05:53,440 --> 00:05:55,200
kaj vi nur povas rigardi, ke en la estonteco,

141
00:05:55,200 --> 00:05:57,690
kaj se ĝi estas pli malgranda, tiam vi scias ke ĝi devas esti en la maldekstra flanko.

142
00:05:57,690 --> 00:06:00,980
Ĉi tiu procezo estas tiam ripetis kun la plej malgranda-grandeco tabelo

143
00:06:00,980 --> 00:06:02,870
ĝis la korekta elemento estas trovita.

144
00:06:08,080 --> 00:06:11,670
>> Tiu potenca algoritmo tranĉas la tabelo grandeco en duono kun ĉiu operacio.

145
00:06:11,670 --> 00:06:14,080
Do, por trovi elementon en ordo tabelo de amplekso 8,

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

147
00:06:16,170 --> 00:06:18,450
aŭ 3 el tiuj operacioj,

148
00:06:18,450 --> 00:06:22,260
kontrolanta la mezo elemento, tiam tranĉi la tabelo en duono estos bezonata,

149
00:06:22,260 --> 00:06:25,670
dum tabelo de amplekso 16 prenas (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
aŭ 4 operacioj.

151
00:06:27,480 --> 00:06:30,570
Tio estas nur 1 pli operacio por duobliĝis-grandeco tabelo.

152
00:06:30,570 --> 00:06:32,220
Duobligante la grandeco de la tabelo

153
00:06:32,220 --> 00:06:35,160
pliigas la runtime de nur 1 pecon de ĉi tiu kodo.

154
00:06:35,160 --> 00:06:37,770
Denove, kontrolanta la mezo ero de la listo, tiam forkiĝanta.

155
00:06:37,770 --> 00:06:40,440
Do, ĝi estas dirita al operacii en logaritma tempo,

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

157
00:06:42,440 --> 00:06:44,270
Sed atendu, vi diras,

158
00:06:44,270 --> 00:06:47,510
Ne ĉi dependas kie en la listo la elemento vi serĉas estas?

159
00:06:47,510 --> 00:06:50,090
Kio se la unua elemento vi rigardas hazarde estas la ĝuste?

160
00:06:50,090 --> 00:06:52,040
Tiam, ĝi nur prenas 1 operacio,

161
00:06:52,040 --> 00:06:54,310
kiel ajn granda la listo estas.

162
00:06:54,310 --> 00:06:56,310
>> Nu, jen kial komputilo sciencistoj havas pli terminoj

163
00:06:56,310 --> 00:06:58,770
por asimptota komplekseco kiu reflektas la plej kazo

164
00:06:58,770 --> 00:07:01,050
kaj plej malbona-kazo agadoj de algoritmo.

165
00:07:01,050 --> 00:07:03,320
Pli ĝuste, la supra kaj subaj baroj

166
00:07:03,320 --> 00:07:05,090
en la tempo de ekzekuto.

167
00:07:05,090 --> 00:07:07,660
En la plej bona kazo por duuma serĉo, nia ero estas

168
00:07:07,660 --> 00:07:09,330
Dekstre en la mezo,

169
00:07:09,330 --> 00:07:11,770
kaj vi akiris ĝin en konstanta tempo,

170
00:07:11,770 --> 00:07:14,240
kiel ajn granda la resto de la tabelo estas.

171
00:07:15,360 --> 00:07:17,650
La simbolo uzita por tiu ĉi estas Ω.

172
00:07:17,650 --> 00:07:19,930
Do, ĉi tiu algoritmo estas dirita al kuri en Ω (1).

173
00:07:19,930 --> 00:07:21,990
En la plej bona kazo, ĝi trovas la elemento rapide,

174
00:07:21,990 --> 00:07:24,200
kiel ajn granda la tabelo estas,

175
00:07:24,200 --> 00:07:26,050
sed en la plej malbona kazo,

176
00:07:26,050 --> 00:07:28,690
ĝi devas plenumi (log n) divido ĉekojn

177
00:07:28,690 --> 00:07:31,030
de la tabelo por trovi la dekstra elemento.

178
00:07:31,030 --> 00:07:34,270
Plej malbona-kazo superaj baroj estas raportita kun la granda "O", kiun vi jam konas.

179
00:07:34,270 --> 00:07:38,080
Do, ĝi estas O (log n), sed Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Lineara serĉo, per kontrasto,

181
00:07:40,680 --> 00:07:43,220
en kiuj vi trairu ĉiu ero de la tabelo

182
00:07:43,220 --> 00:07:45,170
trovi kiun vi volas,

183
00:07:45,170 --> 00:07:47,420
Estas en la plej bona Ω (1).

184
00:07:47,420 --> 00:07:49,430
Denove, la unua elemento vi volas.

185
00:07:49,430 --> 00:07:51,930
Do, ne gravas kiom granda la tabelo estas.

186
00:07:51,930 --> 00:07:54,840
En la plej malbona kazo, ĝi estas la lasta elemento en la tabelo.

187
00:07:54,840 --> 00:07:58,560
Do, vi devas marŝi tra ĉiuj n elementoj en la tabelo por trovi ĝin,

188
00:07:58,560 --> 00:08:02,170
kiel se vi serĉis 3.

189
00:08:04,320 --> 00:08:06,030
Do, ĝi kuras en O (n) tempo

190
00:08:06,030 --> 00:08:09,330
ĉar ĝi estas proporcia al la nombro de eroj en la tabelo.

191
00:08:10,800 --> 00:08:12,830
>> Unu pli simbolo uzita estas Θ.

192
00:08:12,830 --> 00:08:15,820
Ĉi tiu povas esti uzita por priskribi algoritmojn, kie la plej bona kaj plej malbonaj kazoj

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

194
00:08:17,440 --> 00:08:20,390
Tiu estas la kazo en la kordo-longo algoritmoj ni parolis pri pli frua.

195
00:08:20,390 --> 00:08:22,780
Tio estas, se ni konservas ĝin en variablo antaux

196
00:08:22,780 --> 00:08:25,160
ni stoki la kordo kaj konsenti ĝin poste en konstanta tempo.

197
00:08:25,160 --> 00:08:27,920
Ne gravas kion nombro

198
00:08:27,920 --> 00:08:30,130
ni stokante en tiu variablo, ni devos rigardi ĝin.

199
00:08:33,110 --> 00:08:35,110
La plej bona okazo estas, ni rigardu ĝin

200
00:08:35,110 --> 00:08:37,120
kaj trovi la longo de la kordo.

201
00:08:37,120 --> 00:08:39,799
Do Ω (1) aŭ pli kazo konstanta tempo.

202
00:08:39,799 --> 00:08:41,059
La plej malbona kazo estas,

203
00:08:41,059 --> 00:08:43,400
ni rigardas ĝin kaj trovi la longeco de la kordo.

204
00:08:43,400 --> 00:08:47,300
Do, O (1) aŭ konstanta tempo en plej malbona kazo.

205
00:08:47,300 --> 00:08:49,180
Do, ekde la plej bona kazo kaj plej malbonaj kazoj estas la sama,

206
00:08:49,180 --> 00:08:52,520
tiu povas diri kuri en Θ (1) tempo.

207
00:08:54,550 --> 00:08:57,010
>> Resume, ni havas bonajn manierojn kialo pri kodoj efikeco

208
00:08:57,010 --> 00:09:00,110
sen scii ion pri la reala mondo tempo prenas kuri,

209
00:09:00,110 --> 00:09:02,270
kio estas influata de multaj ekster faktoroj,

210
00:09:02,270 --> 00:09:04,190
inkludante diferencanta aparataro, programaro,

211
00:09:04,190 --> 00:09:06,040
aŭ la specifaj detaloj de via kodo.

212
00:09:06,040 --> 00:09:08,380
Ankaŭ, ĝi permesas al ni elpensus bone pri kio okazos

213
00:09:08,380 --> 00:09:10,180
kiam la grandeco de la enigoj pliigas.

214
00:09:10,180 --> 00:09:12,490
>> Se vi kuras en O (n) ² algoritmo,

215
00:09:12,490 --> 00:09:15,240
aŭ malbona, oni ho (2 ⁿ) algoritmo,

216
00:09:15,240 --> 00:09:17,170
unu el la plej rapide kreskanta tipoj,

217
00:09:17,170 --> 00:09:19,140
vi vere komencas rimarki la malrapidiĝo

218
00:09:19,140 --> 00:09:21,220
kiam vi komencos labori kun grandaj kvantoj de datumoj.

219
00:09:21,220 --> 00:09:23,590
>> Tio estas asimptota komplekseco. Dankon.