1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Jūs droši vien esat dzirdējis cilvēkus runājam par ātru vai efektīva algoritma

2
00:00:10,950 --> 00:00:13,090
izpildei jūsu konkrēto uzdevumu,

3
00:00:13,090 --> 00:00:16,110
bet ko tieši tas nozīmē algoritmu, lai būtu ātri un efektīvi?

4
00:00:16,110 --> 00:00:18,580
Nu, tas nav runā par mērījumiem reālā laikā,

5
00:00:18,580 --> 00:00:20,500
piemēram sekundēs vai minūtēs.

6
00:00:20,500 --> 00:00:22,220
Tas ir tāpēc, datoru aparatūru

7
00:00:22,220 --> 00:00:24,260
un programmatūras krasi atšķiras.

8
00:00:24,260 --> 00:00:26,020
Mana programma varētu darboties lēnāk nekā jums,

9
00:00:26,020 --> 00:00:28,000
jo es skrienu to vecāku datoru,

10
00:00:28,000 --> 00:00:30,110
vai tāpēc es gadās būt spēlējot tiešsaistes video spēli

11
00:00:30,110 --> 00:00:32,670
tajā pašā laikā, kas ir hogging visu manu atmiņu,

12
00:00:32,670 --> 00:00:35,400
vai es varētu darboties savu programmu cauri dažādu programmatūru

13
00:00:35,400 --> 00:00:37,550
kas sazinās ar mašīnu savādāk zemā līmenī.

14
00:00:37,550 --> 00:00:39,650
Tas ir tāpat kā salīdzināt ābolus ar apelsīniem.

15
00:00:39,650 --> 00:00:41,940
Tikai tāpēc, ka mans lēnāka datora aizņem ilgāku

16
00:00:41,940 --> 00:00:43,410
kā jums dot atpakaļ atbildi

17
00:00:43,410 --> 00:00:45,510
nenozīmē, ka jums ir daudz efektīvāku algoritmu.

18
00:00:45,510 --> 00:00:48,830
>> Tātad, jo mēs nevaram tieši salīdzināt runtimes, programmu

19
00:00:48,830 --> 00:00:50,140
sekundēs vai minūtēs,

20
00:00:50,140 --> 00:00:52,310
kā mēs salīdzināt 2 dažādus algoritmus

21
00:00:52,310 --> 00:00:55,030
neatkarīgi no viņu aparatūras vai programmatūras vidē?

22
00:00:55,030 --> 00:00:58,000
Lai radītu vienotu iespējams izmērīt algoritmiskās efektivitāti,

23
00:00:58,000 --> 00:01:00,360
datorzinātnieku un matemātiķi ir izstrādājušas

24
00:01:00,360 --> 00:01:03,830
koncepcijas mērīšanas asimptotiskās sarežģītību programmas

25
00:01:03,830 --> 00:01:06,110
un pieraksta sauc par "Big Ohnotation"

26
00:01:06,110 --> 00:01:08,320
lai aprakstītu to.

27
00:01:08,320 --> 00:01:10,820
Formālā definīcija ir funkcija f (x)

28
00:01:10,820 --> 00:01:13,390
iet par kārtību g (x)

29
00:01:13,390 --> 00:01:15,140
ja pastāv zināma (x) vērtība, x ₀ un

30
00:01:15,140 --> 00:01:17,630
daži konstante, C, par kuru

31
00:01:17,630 --> 00:01:19,340
f (x) ir mazāks vai vienāds ar

32
00:01:19,340 --> 00:01:21,230
ka nemainīga reizes g (x)

33
00:01:21,230 --> 00:01:23,190
visiem x lielāks nekā x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Bet vai nav bail prom ar formālās definīcijas.

35
00:01:25,290 --> 00:01:28,020
Ko tas patiesībā nozīmē mazāk teorētisko izteiksmē?

36
00:01:28,020 --> 00:01:30,580
Nu, tas būtībā veids analizējot

37
00:01:30,580 --> 00:01:33,580
cik ātri programma ir izpildlaika aug asimptotiski.

38
00:01:33,580 --> 00:01:37,170
Tas ir, jo no jūsu izejvielu izmērs palielinās virzienā bezgalībai,

39
00:01:37,170 --> 00:01:41,390
teiksim, jūs šķirošanas masīvs 1000 izmēra, salīdzinot ar masīvu 10 izmēra.

40
00:01:41,390 --> 00:01:44,950
Kā jūsu programmā izpildlaika augt?

41
00:01:44,950 --> 00:01:47,390
Piemēram, iedomājieties skaitīšana rakstzīmju

42
00:01:47,390 --> 00:01:49,350
virknē visvienkāršākais veids

43
00:01:49,350 --> 00:01:51,620
 ejot cauri visai string

44
00:01:51,620 --> 00:01:54,790
burtu pa vēstuli un pievienojot 1 līdz counter katram raksturs.

45
00:01:55,700 --> 00:01:58,420
Šis algoritms ir teikt palaist lineārā laika

46
00:01:58,420 --> 00:02:00,460
attiecībā uz zīmju skaitu,

47
00:02:00,460 --> 00:02:02,670
"N" virknē.

48
00:02:02,670 --> 00:02:04,910
Īsi sakot, tas darbojas O (n).

49
00:02:05,570 --> 00:02:07,290
Kāpēc tas tā ir?

50
00:02:07,290 --> 00:02:09,539
Nu, izmantojot šo pieeju, laiks, kas nepieciešams

51
00:02:09,539 --> 00:02:11,300
lai šķērsotu virtenei

52
00:02:11,300 --> 00:02:13,920
ir proporcionāls rakstzīmju skaitu.

53
00:02:13,920 --> 00:02:16,480
Saskaitot rakstzīmēm 20 rakstzīmju virkne

54
00:02:16,480 --> 00:02:18,580
gatavojas veikt divreiz tik ilgi, cik tas nepieciešams

55
00:02:18,580 --> 00:02:20,330
saskaitīt rakstzīmes 10 rakstzīmju virknes,

56
00:02:20,330 --> 00:02:23,000
jo jums ir apskatīt visas rakstzīmes

57
00:02:23,000 --> 00:02:25,740
un katrs simbols aizņem tikpat daudz laika, lai apskatīt.

58
00:02:25,740 --> 00:02:28,050
Kā jūs palielināt zīmju skaitu,

59
00:02:28,050 --> 00:02:30,950
izpildlaika palielinās lineāri ar ievades garuma.

60
00:02:30,950 --> 00:02:33,500
>> Tagad iedomājieties, ja jūs nolemjat, ka lineārā laika,

61
00:02:33,500 --> 00:02:36,390
O (N), vienkārši nav pietiekami ātri, lai jūs?

62
00:02:36,390 --> 00:02:38,750
Varbūt jūs uzglabātu milzīgu stīgas,

63
00:02:38,750 --> 00:02:40,450
un jūs nevarat atļauties papildu laiku, kas būtu nepieciešams

64
00:02:40,450 --> 00:02:44,000
lai šķērsotu visu to īpašību skaitīšanas vienu pa vienam.

65
00:02:44,000 --> 00:02:46,650
Tātad, esat nolēmis izmēģināt kaut ko atšķiras.

66
00:02:46,650 --> 00:02:49,270
Ko darīt, ja jūs varētu notikt jau glabāt zīmju skaitu

67
00:02:49,270 --> 00:02:52,690
virknē, teiksim, jo ​​mainīgo sauc "len"

68
00:02:52,690 --> 00:02:54,210
agri programmā,

69
00:02:54,210 --> 00:02:57,800
Pirms jūs pat glabājas ļoti pirmo rakstzīmi jūsu virknes?

70
00:02:57,800 --> 00:02:59,980
Tad viss jūs ir jādara tagad, lai uzzinātu stīgu garumu,

71
00:02:59,980 --> 00:03:02,570
ir jāpārbauda, ​​kāda ir mainīgā vērtība ir.

72
00:03:02,570 --> 00:03:05,530
Jums nebūtu jāskatās uz virkni pati vispār,

73
00:03:05,530 --> 00:03:08,160
un piekļūstot mainīgā vērtību, piemēram, len tiek uzskatīta

74
00:03:08,160 --> 00:03:11,100
asimptotiski nemainīgs laika darbību,

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

76
00:03:13,070 --> 00:03:17,110
Kāpēc tas tā ir? Nu, atceros, ko asimptotiskais sarežģītība nozīmē.

77
00:03:17,110 --> 00:03:19,100
Kā runtime izmaiņas, jo izmērs

78
00:03:19,100 --> 00:03:21,400
no jūsu ieejas aug?

79
00:03:21,400 --> 00:03:24,630
>> Say jūs mēģināt iegūt rakstzīmju skaitu lielāku virknē.

80
00:03:24,630 --> 00:03:26,960
Nu, tas nav svarīgi, cik liels jūs veicat virkni,

81
00:03:26,960 --> 00:03:28,690
pat miljons rakstzīmēm,

82
00:03:28,690 --> 00:03:31,150
visi jūs jādara, lai atrastu string garuma ar šo pieeju,

83
00:03:31,150 --> 00:03:33,790
ir nolasīt vērtību mainīgā len,

84
00:03:33,790 --> 00:03:35,440
kas jums jau veikti.

85
00:03:35,440 --> 00:03:38,200
Ieejas garums, tas ir, garums string jūs mēģināt atrast,

86
00:03:38,200 --> 00:03:41,510
neietekmē vispār, cik ātri jūsu programma darbojas.

87
00:03:41,510 --> 00:03:44,550
Šī jūsu programmas daļa varētu darboties tikpat strauji uz vienu rakstzīmju virkne

88
00:03:44,550 --> 00:03:46,170
un tūkstoš rakstzīmju virkne,

89
00:03:46,170 --> 00:03:49,140
un tāpēc šī programma būtu minēta kā darbojas pastāvīgu laiku

90
00:03:49,140 --> 00:03:51,520
attiecībā uz ieejas lielumu.

91
00:03:51,520 --> 00:03:53,920
>> Protams, tur ir trūkums.

92
00:03:53,920 --> 00:03:55,710
Jūs tērēt papildus atmiņas vietu datorā

93
00:03:55,710 --> 00:03:57,380
uzglabājot mainīgo

94
00:03:57,380 --> 00:03:59,270
un papildu laiks, kas jūs aizvedīs

95
00:03:59,270 --> 00:04:01,490
darīt faktisko uzglabāšanu mainīgo,

96
00:04:01,490 --> 00:04:03,390
bet punkts joprojām stāv,

97
00:04:03,390 --> 00:04:05,060
uzzināt, cik ilgi jūsu string bija

98
00:04:05,060 --> 00:04:07,600
nav atkarīga no garuma virknes vispār.

99
00:04:07,600 --> 00:04:10,720
Tātad, tas darbojas O (1) vai pastāvīgu laiku.

100
00:04:10,720 --> 00:04:13,070
Tas noteikti nav jāsaprot

101
00:04:13,070 --> 00:04:15,610
ka jūsu kods darbojas 1 solis,

102
00:04:15,610 --> 00:04:17,470
bet nav svarīgi, cik daudz soļus tas ir,

103
00:04:17,470 --> 00:04:20,019
ja tas nemaina ar izmēru ieguldījumiem,

104
00:04:20,019 --> 00:04:23,420
tas joprojām asimptotiski konstante, ko mēs pārstāvam, O (1).

105
00:04:23,420 --> 00:04:25,120
>> Kā jūs varat droši uzminēt,

106
00:04:25,120 --> 00:04:27,940
ir daudz dažādu Big O runtimes lai izmērītu algoritmus ar.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmi ir asimptotiski lēnāks nekā O (N) algoritmiem.

108
00:04:32,980 --> 00:04:35,910
Tas ir, kā to elementu skaits (n) aug,

109
00:04:35,910 --> 00:04:39,280
beidzot O (n) ² algoritmi vēl būs nepieciešams laiks

110
00:04:39,280 --> 00:04:41,000
kā O (n) algoritmus, lai palaistu.

111
00:04:41,000 --> 00:04:43,960
Tas nenozīmē, O (n) algoritmi vienmēr darboties ātrāk

112
00:04:43,960 --> 00:04:46,410
kā O (n) ² algoritmus, pat tajā pašā vidē,

113
00:04:46,410 --> 00:04:48,080
tajā pašā aparatūru.

114
00:04:48,080 --> 00:04:50,180
Varbūt mazajiem ieejas izmēriem,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algoritms tiešām strādāt ātrāk,

116
00:04:52,900 --> 00:04:55,450
bet, galu galā, kā ieejas lielumu palielina

117
00:04:55,450 --> 00:04:58,760
pret bezgalību, O (n) ² algoritms ir izpildlaika

118
00:04:58,760 --> 00:05:02,000
beidzot aizēnot runtime par O (n) algoritms.

119
00:05:02,000 --> 00:05:04,230
Tāpat kā jebkuru kvadrātvienādojums matemātisko funkciju

120
00:05:04,230 --> 00:05:06,510
 beidzot apsteigs jebkuru lineāro funkciju,

121
00:05:06,510 --> 00:05:09,200
Nav svarīgi, cik daudz no galvas sāk lineāru funkciju sākas ar.

122
00:05:10,010 --> 00:05:12,000
Ja jūs strādājat ar lielu datu apjomu,

123
00:05:12,000 --> 00:05:15,510
algoritmi, kas darbosies O (n) ² laiku tiešām var beigties palēninot savu programmu,

124
00:05:15,510 --> 00:05:17,770
bet mazajiem ieejas izmēriem,

125
00:05:17,770 --> 00:05:19,420
Jūs, iespējams, pat nepamanīsiet.

126
00:05:19,420 --> 00:05:21,280
>> Vēl asimptotiskās sarežģītība ir,

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

128
00:05:24,420 --> 00:05:26,340
Piemērs algoritmu, kas vada šo ātri

129
00:05:26,340 --> 00:05:29,060
ir klasisks bināro meklēšanas algoritmu,

130
00:05:29,060 --> 00:05:31,850
lai atrastu elements jau tā-sakārtoti sarakstā elementu.

131
00:05:31,850 --> 00:05:33,400
>> Ja jūs nezināt, ko binārā meklēšana dara,

132
00:05:33,400 --> 00:05:35,170
Es paskaidrošu to you tiešām ātri.

133
00:05:35,170 --> 00:05:37,020
Pieņemsim, ka jūs meklējat skaits 3

134
00:05:37,020 --> 00:05:40,200
Šajā masīvs integers.

135
00:05:40,200 --> 00:05:42,140
Tas izskatās pēc vidējā elementu masīva

136
00:05:42,140 --> 00:05:46,830
un jautā: "Vai elements es gribu lielāka, vienāda vai mazāka par šo?"

137
00:05:46,830 --> 00:05:49,150
Ja tas ir vienāds, tad lieliski. Jūs atrast elementu, un jūs darīts.

138
00:05:49,150 --> 00:05:51,300
Ja tas ir lielāks, tad jūs zināt elements

139
00:05:51,300 --> 00:05:53,440
ir būt pareizajā pusē masīva,

140
00:05:53,440 --> 00:05:55,200
un jūs varat tikai apskatīt, ka nākotnē,

141
00:05:55,200 --> 00:05:57,690
un, ja tas ir mazāks, tad jūs zināt, tas ir jābūt kreisajā pusē.

142
00:05:57,690 --> 00:06:00,980
Šis process tiek atkārtots ar mazāku izmēra masīvs

143
00:06:00,980 --> 00:06:02,870
līdz pareizu elements ir atrasts.

144
00:06:08,080 --> 00:06:11,670
>> Šī jaudīga algoritms samazina masīva izmēru pusē ar katru darbību.

145
00:06:11,670 --> 00:06:14,080
Tātad, lai atrastu elementu sakārtoti masīvs 8 izmēra,

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

147
00:06:16,170 --> 00:06:18,450
vai 3 no šīm operācijām,

148
00:06:18,450 --> 00:06:22,260
Pārbaudot vidējo elementu, tad griešanas masīvs pusē būs nepieciešama,

149
00:06:22,260 --> 00:06:25,670
tā 16 izmēra masīvs aizņem (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
vai 4 operācijas.

151
00:06:27,480 --> 00:06:30,570
Tas ir tikai vēl 1 operācija uz dubultojies izmēra masīvs.

152
00:06:30,570 --> 00:06:32,220
Divkāršojot masīva

153
00:06:32,220 --> 00:06:35,160
palielina izpildlaika tikai 1 rieciens šo kodu.

154
00:06:35,160 --> 00:06:37,770
Atkal, pārbaudot vidējo elementu sarakstu, tad sadalīšana.

155
00:06:37,770 --> 00:06:40,440
Tātad, tas teica darboties logaritmiskajā laikā,

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

157
00:06:42,440 --> 00:06:44,270
Bet pagaidiet, jūs sakāt,

158
00:06:44,270 --> 00:06:47,510
nav tas atkarīgs no tā, kurā sarakstā elements jūs meklējat ir?

159
00:06:47,510 --> 00:06:50,090
Ko darīt, ja pirmais elements paskatās notiek, ir pareizais?

160
00:06:50,090 --> 00:06:52,040
Tad, tas aizņem tikai 1 darbību,

161
00:06:52,040 --> 00:06:54,310
Nav svarīgi, cik liels šis saraksts ir.

162
00:06:54,310 --> 00:06:56,310
>> Nu, tāpēc datorzinātnieku ir vairāk termini

163
00:06:56,310 --> 00:06:58,770
par asimptotiskās sarežģītību, kas atspoguļo labāko-lietu

164
00:06:58,770 --> 00:07:01,050
un sliktākajā gadījumā izrādes algoritmu.

165
00:07:01,050 --> 00:07:03,320
Vairāk pareizi, augšējā un apakšējā robeža

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

167
00:07:05,090 --> 00:07:07,660
Labākajā gadījumā par bināro meklēšanu, mūsu elements ir

168
00:07:07,660 --> 00:07:09,330
turpat vidū,

169
00:07:09,330 --> 00:07:11,770
un jūs saņemsiet to pastāvīgu laiku,

170
00:07:11,770 --> 00:07:14,240
Nav svarīgi, cik liels ir masīva pārējais ir.

171
00:07:15,360 --> 00:07:17,650
Simbols, ko izmanto tas ir Ω.

172
00:07:17,650 --> 00:07:19,930
Tātad, šis algoritms ir teikt palaist Ω (1).

173
00:07:19,930 --> 00:07:21,990
Labākajā gadījumā, tas atrod elements ātri,

174
00:07:21,990 --> 00:07:24,200
Nav svarīgi, cik liels masīvs ir,

175
00:07:24,200 --> 00:07:26,050
bet sliktākajā gadījumā,

176
00:07:26,050 --> 00:07:28,690
tai jāpilda (log n) split pārbaudes

177
00:07:28,690 --> 00:07:31,030
masīva lai atrastu pareizo elementu.

178
00:07:31,030 --> 00:07:34,270
Sliktākajā gadījumā augšējās robežas ir minēti ar lielo "O" ka jūs jau zināt.

179
00:07:34,270 --> 00:07:38,080
Tātad, tas ir O (log n), bet Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Lineāra meklēt, gluži pretēji,

181
00:07:40,680 --> 00:07:43,220
kurā jums staigāt pa katru elementu masīva

182
00:07:43,220 --> 00:07:45,170
lai atrastu vienu vēlaties,

183
00:07:45,170 --> 00:07:47,420
labākajā Ω (1).

184
00:07:47,420 --> 00:07:49,430
Atkal, pirmais elements jūs vēlaties.

185
00:07:49,430 --> 00:07:51,930
Tātad, tas nav svarīgi, cik liels masīvs ir.

186
00:07:51,930 --> 00:07:54,840
Sliktākajā gadījumā, tas ir pēdējais elements masīva.

187
00:07:54,840 --> 00:07:58,560
Tātad, jums ir staigāt pa visiem n elementu masīvu, lai atrastu to,

188
00:07:58,560 --> 00:08:02,170
piemēram, ja jūs meklējat 3.

189
00:08:04,320 --> 00:08:06,030
Tātad, tas darbojas O (n) laikā

190
00:08:06,030 --> 00:08:09,330
jo tas ir proporcionāls skaits elementu masīvā.

191
00:08:10,800 --> 00:08:12,830
>> Vēl viens lietots simbols ir Θ.

192
00:08:12,830 --> 00:08:15,820
To var izmantot, lai aprakstītu algoritmu, kur vislabāk un sliktākajā gadījumā

193
00:08:15,820 --> 00:08:17,440
ir vienādi.

194
00:08:17,440 --> 00:08:20,390
Tas ir gadījums, kas virknes garuma algoritmu mēs runājām par agrāk.

195
00:08:20,390 --> 00:08:22,780
Tas ir, ja mēs to uzglabā mainīgā pirms

196
00:08:22,780 --> 00:08:25,160
mēs saglabājam stīgu un tai piekļūt vēlāk pastāvīgu laiku.

197
00:08:25,160 --> 00:08:27,920
Nav svarīgi, ko skaits

198
00:08:27,920 --> 00:08:30,130
mēs esam uzglabājot šajā mainīgo, mums būs jāskatās uz to.

199
00:08:33,110 --> 00:08:35,110
Labākais lieta ir, mēs skatāmies uz to

200
00:08:35,110 --> 00:08:37,120
un atrast garumu virknes.

201
00:08:37,120 --> 00:08:39,799
Tātad Ω (1) vai labākajā gadījumā nemainīgs laika.

202
00:08:39,799 --> 00:08:41,059
Sliktākajā gadījumā ir,

203
00:08:41,059 --> 00:08:43,400
mēs skatāmies uz to un atrast garumu virknes.

204
00:08:43,400 --> 00:08:47,300
Tātad, O (1) vai pastāvīgs laiks sliktākajā gadījumā.

205
00:08:47,300 --> 00:08:49,180
Tātad, jo labākajā gadījumā un sliktākajā gadījumā, ir tas pats,

206
00:08:49,180 --> 00:08:52,520
to var teikt darboties Θ (1) laikā.

207
00:08:54,550 --> 00:08:57,010
>> Rezumējot, mums ir labas iespējas, lai tādēļ par kodiem efektivitāti

208
00:08:57,010 --> 00:09:00,110
nezinot neko par reālās pasaules laika tās veic, lai palaistu,

209
00:09:00,110 --> 00:09:02,270
kas ietekmē daudz ārējo faktoru,

210
00:09:02,270 --> 00:09:04,190
tostarp atšķiras aparatūras, programmatūras,

211
00:09:04,190 --> 00:09:06,040
vai specifiku jūsu kodu.

212
00:09:06,040 --> 00:09:08,380
Arī tas ļauj mums pamatojusi arī par to, kas notiks

213
00:09:08,380 --> 00:09:10,180
ja lielumu ievadē palielinās.

214
00:09:10,180 --> 00:09:12,490
>> Ja jūs darbojas O (n) ² algoritmu,

215
00:09:12,490 --> 00:09:15,240
vai vēl ļaunāk, O (2 ⁿ) algoritms,

216
00:09:15,240 --> 00:09:17,170
viena no visstraujāk augošajām veidi,

217
00:09:17,170 --> 00:09:19,140
jūs tiešām sāk pamanīt palēninājumu

218
00:09:19,140 --> 00:09:21,220
kad jūs sākat strādāt ar lielāku datu apjomu.

219
00:09:21,220 --> 00:09:23,590
>> Tas ir asimptotiskā sarežģītību. Paldies.