1
00:00:00,000 --> 00:00:05,830

2
00:00:05,830 --> 00:00:07,910
>> Haki wote, hivyo, kuhesabu utata.

3
00:00:07,910 --> 00:00:10,430
Kidogo tu ya onyo
kabla ya sisi kupiga mbizi katika pia far--

4
00:00:10,430 --> 00:00:13,070
hii pengine utasikia kuwa miongoni mwa
mambo ya hesabu-nzito

5
00:00:13,070 --> 00:00:14,200
tunazungumzia kuhusu katika CS50.

6
00:00:14,200 --> 00:00:16,950
Nadhani itakuwa si kuwa pia balaa
na tutaweza kujaribu na kuongoza wewe

7
00:00:16,950 --> 00:00:19,200
kupitia mchakato, lakini
kidogo tu ya onyo haki.

8
00:00:19,200 --> 00:00:21,282
Kuna kidogo
ya hisabati kushiriki hapa.

9
00:00:21,282 --> 00:00:23,990
Haki wote, hivyo ili kufanya
matumizi ya rasilimali zetu Computational

10
00:00:23,990 --> 00:00:28,170
katika world-- halisi ni kweli
muhimu kuelewa algorithms

11
00:00:28,170 --> 00:00:30,750
na jinsi mchakato wa data.

12
00:00:30,750 --> 00:00:32,810
Kama tuna kweli
algorithm ufanisi, sisi

13
00:00:32,810 --> 00:00:36,292
unaweza kupunguza kiasi cha rasilimali
tuna inapatikana kwa kukabiliana nayo.

14
00:00:36,292 --> 00:00:38,750
Kama tuna algorithm kwamba
ni kwenda kuchukua mengi ya kazi

15
00:00:38,750 --> 00:00:41,210
na mchakato wa kweli
kuweka kubwa ya data, ni

16
00:00:41,210 --> 00:00:44,030
kwenda zinahitaji zaidi
na rasilimali zaidi, ambayo

17
00:00:44,030 --> 00:00:47,980
ni fedha, RAM, kwamba aina zote za mambo ya ajabu.

18
00:00:47,980 --> 00:00:52,090
>> Hivyo, kuwa na uwezo wa kuchambua
algorithm kutumia seti chombo hiki,

19
00:00:52,090 --> 00:00:56,110
kimsingi, anauliza question--
jinsi gani hii algorithm wadogo

20
00:00:56,110 --> 00:00:59,020
kama sisi kutupa data zaidi na zaidi katika hilo?

21
00:00:59,020 --> 00:01:02,220
Katika CS50, kiasi cha data tuko
kufanya kazi na ni pretty ndogo.

22
00:01:02,220 --> 00:01:05,140
Kwa ujumla, mipango yetu ni kwenda
kuendesha katika pili au less--

23
00:01:05,140 --> 00:01:07,830
pengine mengi chini
hasa mapema.

24
00:01:07,830 --> 00:01:12,250
>> Lakini fikiria kampuni hiyo mikataba
na mamia ya mamilioni ya wateja.

25
00:01:12,250 --> 00:01:14,970
Na wanahitaji mchakato
kwamba data kwa wateja.

26
00:01:14,970 --> 00:01:18,260
Kama idadi ya wateja wao
na anapata kubwa na kubwa zaidi,

27
00:01:18,260 --> 00:01:21,230
itakuja kuhitaji
zaidi na zaidi na rasilimali.

28
00:01:21,230 --> 00:01:22,926
Jinsi wengi zaidi rasilimali?

29
00:01:22,926 --> 00:01:25,050
Naam, hiyo inategemea jinsi
sisi kuchambua algorithm,

30
00:01:25,050 --> 00:01:28,097
kutumia zana katika sanduku la vifaa hii.

31
00:01:28,097 --> 00:01:31,180
Tunapozungumzia kuhusu utata wa
algorithm ambayo wakati mwingine utasikia

32
00:01:31,180 --> 00:01:34,040
kusikia inajulikana kama wakati
utata au nafasi utata

33
00:01:34,040 --> 00:01:36,190
lakini tunakwenda tu
kuwaita complexity--

34
00:01:36,190 --> 00:01:38,770
sisi ni ujumla kuzungumza juu ya
mbaya zaidi kesi.

35
00:01:38,770 --> 00:01:42,640
Kutokana na mbaya kabisa rundo la
data kwamba tunaweza kutupa saa hiyo,

36
00:01:42,640 --> 00:01:46,440
jinsi ni algorithm hii kwenda
mchakato au kukabiliana na takwimu ambazo?

37
00:01:46,440 --> 00:01:51,450
Sisi kwa ujumla kuwaita mbaya zaidi kesi
Runtime ya algorithm big-O.

38
00:01:51,450 --> 00:01:56,770
Hivyo algorithm inaweza kuwa alisema
kukimbia katika O ya n au O ya n squared.

39
00:01:56,770 --> 00:01:59,110
Na zaidi juu ya nini
wale maana katika pili.

40
00:01:59,110 --> 00:02:01,620
>> Wakati mwingine, ingawa, sisi kufanya huduma
kuhusu bora kesi.

41
00:02:01,620 --> 00:02:05,400
Kama data ni kila kitu tulitaka
kuwa ni na ilikuwa kamilifu kabisa

42
00:02:05,400 --> 00:02:09,630
na tulikuwa kutuma hii kamili
seti ya data kwa njia ya kompyuta yetu.

43
00:02:09,630 --> 00:02:11,470
Jinsi gani ni kushughulikia katika hali hiyo?

44
00:02:11,470 --> 00:02:15,050
Sisi wakati mwingine kutaja kwamba kama
big-Omega, hivyo tofauti na big-O,

45
00:02:15,050 --> 00:02:16,530
tuna big-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega kwa bora kesi.

47
00:02:18,880 --> 00:02:21,319
Big-O kwa hali mbaya zaidi kesi.

48
00:02:21,319 --> 00:02:23,860
Kwa ujumla, wakati sisi majadiliano juu
utata wa algorithm,

49
00:02:23,860 --> 00:02:26,370
tunazungumzia
mbaya zaidi kesi.

50
00:02:26,370 --> 00:02:28,100
Hivyo kuendelea kuwa katika akili.

51
00:02:28,100 --> 00:02:31,510
>> Na katika darasa hili, tuko kwa ujumla kwenda
kuondoka uchambuzi ukali kando.

52
00:02:31,510 --> 00:02:35,350
Kuna sayansi na mashamba
kujitoa kwa aina hii ya mambo.

53
00:02:35,350 --> 00:02:37,610
Tunapozungumzia kuhusu hoja
kupitia algorithms,

54
00:02:37,610 --> 00:02:41,822
ambayo tutaweza kufanya kipande-by-kipande kwa wengi
algorithms tunazungumzia kuhusu darasani.

55
00:02:41,822 --> 00:02:44,780
Sisi ni kweli tu kuzungumza juu ya
hoja kwa njia hiyo kwa akili ya kawaida,

56
00:02:44,780 --> 00:02:47,070
si kwa kanuni, au hoja,
au kitu kama hicho.

57
00:02:47,070 --> 00:02:51,600
Hivyo msiwe na wasiwasi, Hatutaki kuwa
kugeuka katika hesabu kubwa darasani.

58
00:02:51,600 --> 00:02:55,920
>> Kwa hiyo mimi nikasema sisi huduma ya juu utata
kwa sababu anauliza swali, jinsi

59
00:02:55,920 --> 00:03:00,160
Je, algorithms wetu kushughulikia kubwa na
seti kubwa data kutupwa saa yao.

60
00:03:00,160 --> 00:03:01,960
Naam, ni nini seti data?

61
00:03:01,960 --> 00:03:03,910
Je, I mean wakati mimi alisema kuwa?

62
00:03:03,910 --> 00:03:07,600
Ina maana chochote hufanya wengi
maana katika mazingira, kuwa waaminifu.

63
00:03:07,600 --> 00:03:11,160
Kama tuna algorithm,
Taratibu Strings-- tuko pengine

64
00:03:11,160 --> 00:03:13,440
kuzungumza juu ya ukubwa wa kamba.

65
00:03:13,440 --> 00:03:15,190
Hiyo ni takwimu set--
ukubwa, idadi

66
00:03:15,190 --> 00:03:17,050
ya wahusika kwamba kufanya juu ya kamba.

67
00:03:17,050 --> 00:03:20,090
Kama tunazungumzia
algorithm kwamba michakato mafaili,

68
00:03:20,090 --> 00:03:23,930
tupate kuzungumza kuhusu jinsi
kilobytes wengi wanaunda faili hilo.

69
00:03:23,930 --> 00:03:25,710
Na hiyo ndiyo kuweka data.

70
00:03:25,710 --> 00:03:28,870
Kama tunazungumzia juu ya algorithm
ambacho kinafanya arrays kwa ujumla zaidi,

71
00:03:28,870 --> 00:03:31,510
kama vile kuchagua algorithms
au kutafuta algorithms,

72
00:03:31,510 --> 00:03:36,690
sisi ni pengine kuzungumza juu idadi
ya mambo ambayo wanaunda safu.

73
00:03:36,690 --> 00:03:39,272
>> Sasa, tunaweza kupima
algorithm hasa,

74
00:03:39,272 --> 00:03:40,980
wakati mimi kusema tunaweza
kupima algorithm, mimi

75
00:03:40,980 --> 00:03:43,840
maana tunaweza kupima jinsi
rasilimali nyingi inachukua up.

76
00:03:43,840 --> 00:03:48,990
Kama rasilimali hizo ni, jinsi wengi
ka wa RAM-- au megabaiti ya RAM

77
00:03:48,990 --> 00:03:49,790
anatumia.

78
00:03:49,790 --> 00:03:52,320
Au ni kiasi gani wakati inachukua kukimbia.

79
00:03:52,320 --> 00:03:56,200
Na tunaweza kuwaita hii
kupima, kiholela, f ya n.

80
00:03:56,200 --> 00:03:59,420
Ambapo n ni idadi ya
mambo katika kuweka data.

81
00:03:59,420 --> 00:04:02,640
Na f ya n ni somethings wangapi.

82
00:04:02,640 --> 00:04:07,530
Jinsi vitengo ya rasilimali nyingi anafanya
ni zinahitaji mchakato wa data hiyo.

83
00:04:07,530 --> 00:04:10,030
>> Sasa, sisi kweli hawana huduma
kuhusu nini f la n ni sawa kabisa.

84
00:04:10,030 --> 00:04:13,700
Kwa kweli, sisi mara chache sana will--
hakika kamwe katika hili mimi class--

85
00:04:13,700 --> 00:04:18,709
mbizi katika yoyote kwa kweli kina
Uchambuzi wa nini f la n ni.

86
00:04:18,709 --> 00:04:23,510
Sisi ni kwenda tu kuzungumza kuhusu nini f ya
n ni takriban au nini inaelekea.

87
00:04:23,510 --> 00:04:27,600
Na tabia ya algorithm ni
dictated na utaratibu wake wa juu mrefu.

88
00:04:27,600 --> 00:04:29,440
Na tunaweza kuona nini mimi
maana na kwamba kwa kuchukua

89
00:04:29,440 --> 00:04:31,910
a tuangalie mfano thabiti zaidi.

90
00:04:31,910 --> 00:04:34,620
>> Basi hebu kusema kwamba tuna
algorithms tatu tofauti.

91
00:04:34,620 --> 00:04:39,350
Kwanza ambayo inachukua n
cubed, baadhi ya vitengo ya rasilimali

92
00:04:39,350 --> 00:04:42,880
na mchakato wa kuweka data ya ukubwa n.

93
00:04:42,880 --> 00:04:47,000
Tuna algorithm pili kwamba inachukua
n cubed pamoja na rasilimali n squared

94
00:04:47,000 --> 00:04:49,350
na mchakato wa kuweka data ya ukubwa n.

95
00:04:49,350 --> 00:04:52,030
Na tuna tatu
algorithm kwamba anaendesha in-- kwamba

96
00:04:52,030 --> 00:04:58,300
unachukua n cubed bala 8n mraba
pamoja na 20 n vitengo ya rasilimali

97
00:04:58,300 --> 00:05:02,370
na mchakato algorithm
na data seti ya ukubwa n.

98
00:05:02,370 --> 00:05:05,594
>> Sasa tena, sisi kweli si kwenda
kupata katika ngazi hii ya kina.

99
00:05:05,594 --> 00:05:08,260
Mimi nina kweli tu na hizi up
hapa kama mfano wa hatua

100
00:05:08,260 --> 00:05:10,176
kwamba mimi nina kwenda kuwa
kufanya katika pili, ambayo

101
00:05:10,176 --> 00:05:12,980
ni kwamba sisi tu kweli huduma
kuhusu tabia ya mambo

102
00:05:12,980 --> 00:05:14,870
kama data seti kupata kubwa.

103
00:05:14,870 --> 00:05:18,220
Hivyo kama seti data ni ndogo, kuna
kweli tofauti pretty kubwa

104
00:05:18,220 --> 00:05:19,870
katika algorithms haya.

105
00:05:19,870 --> 00:05:23,000
Algorithm tatu kulikuwa
inachukua mara 13 tena,

106
00:05:23,000 --> 00:05:27,980
Mara 13 kiasi cha rasilimali
kuendesha jamaa na moja ya kwanza.

107
00:05:27,980 --> 00:05:31,659
>> Kama kuweka wetu data ni ukubwa 10, ambayo
ni kubwa, lakini si lazima kubwa,

108
00:05:31,659 --> 00:05:33,950
tunaweza kuona kwamba kuna
kweli kidogo ya tofauti.

109
00:05:33,950 --> 00:05:36,620
Algorithm tatu
inakuwa ufanisi zaidi.

110
00:05:36,620 --> 00:05:40,120
Ni kuhusu kweli 40% -
au 60% ufanisi zaidi.

111
00:05:40,120 --> 00:05:41,580
Inachukua 40% ya kiasi cha muda.

112
00:05:41,580 --> 00:05:45,250
Ni inaweza run-- inaweza kuchukua
Vitengo 400 wa rasilimali

113
00:05:45,250 --> 00:05:47,570
na mchakato wa kuweka data ya ukubwa 10.

114
00:05:47,570 --> 00:05:49,410
Wakati kwanza
algorithm, kwa kulinganisha,

115
00:05:49,410 --> 00:05:54,520
inachukua vitengo 1,000 ya rasilimali
na mchakato wa kuweka data ya ukubwa 10.

116
00:05:54,520 --> 00:05:57,240
Lakini angalia nini kinatokea kama
idadi yetu kupata hata kubwa.

117
00:05:57,240 --> 00:05:59,500
>> Sasa, tofauti
kati ya algorithms haya

118
00:05:59,500 --> 00:06:01,420
kuanza kuwa kidogo kidogo dhahiri.

119
00:06:01,420 --> 00:06:04,560
Na ukweli kwamba kuna
ili kupunguza terms-- au tuseme,

120
00:06:04,560 --> 00:06:09,390
masharti na chini exponents--
kuanza kuwa lisilo na maana.

121
00:06:09,390 --> 00:06:12,290
Kama kuweka data ni wa kawaida
1,000 na algorithm kwanza

122
00:06:12,290 --> 00:06:14,170
anaendesha katika bilioni hatua.

123
00:06:14,170 --> 00:06:17,880
Na algorithm pili anaendesha katika
bilioni na milioni hatua.

124
00:06:17,880 --> 00:06:20,870
Na algorithm tatu anaendesha
katika aibu tu ya bilioni hatua.

125
00:06:20,870 --> 00:06:22,620
Ni pretty much bilioni hatua.

126
00:06:22,620 --> 00:06:25,640
Wale suala ili kupunguza kuanza
kuwa kweli lisilo.

127
00:06:25,640 --> 00:06:27,390
Na tu kwa kweli
nyundo nyumbani point--

128
00:06:27,390 --> 00:06:31,240
kama pembejeo data ni wa kawaida a
million-- zote tatu wa haya pretty much

129
00:06:31,240 --> 00:06:34,960
kuchukua quintillion-- moja ikiwa
math yangu ni hatua correct--

130
00:06:34,960 --> 00:06:37,260
na mchakato wa pembejeo data
ukubwa milioni.

131
00:06:37,260 --> 00:06:38,250
Kwamba mengi ya hatua.

132
00:06:38,250 --> 00:06:42,092
Na ukweli kwamba mmoja wao wapate
kuchukua michache 100,000 au wanandoa 100

133
00:06:42,092 --> 00:06:44,650
milioni hata kidogo wakati
tunazungumzia idadi

134
00:06:44,650 --> 00:06:46,990
kwamba big-- ni aina ya lisilo na maana.

135
00:06:46,990 --> 00:06:50,006
Wote huwa na kuchukua
takriban n cubed,

136
00:06:50,006 --> 00:06:52,380
na hivyo sisi ingekuwa kweli rejea
kwa wote wa algorithms hizi

137
00:06:52,380 --> 00:06:59,520
kuwa juu ya utaratibu wa n
cubed au kubwa-O ya n cubed.

138
00:06:59,520 --> 00:07:03,220
>> Hapa ni orodha ya baadhi ya zaidi
kawaida madarasa Computational utata

139
00:07:03,220 --> 00:07:05,820
kwamba tutaweza kukutana katika
algorithms, kwa ujumla.

140
00:07:05,820 --> 00:07:07,970
Na pia hasa katika CS50.

141
00:07:07,970 --> 00:07:11,410
Hizi ni amri kutoka
ujumla kwa kasi juu,

142
00:07:11,410 --> 00:07:13,940
kwa ujumla madogo zaidi chini.

143
00:07:13,940 --> 00:07:16,920
Hivyo algorithms wakati mara kwa mara huwa
kuwa kasi, bila kujali

144
00:07:16,920 --> 00:07:19,110
ukubwa wa
pembejeo data kupita katika.

145
00:07:19,110 --> 00:07:23,760
Wao daima kuchukua operesheni moja au
kitengo moja ya rasilimali ya kushughulikia.

146
00:07:23,760 --> 00:07:25,730
Ni inaweza kuwa 2, inaweza
kuwa 3, inaweza kuwa 4.

147
00:07:25,730 --> 00:07:26,910
Lakini ni idadi ya mara kwa mara.

148
00:07:26,910 --> 00:07:28,400
Ni haina kutofautiana.

149
00:07:28,400 --> 00:07:31,390
>> Logarithmic algorithms wakati
ni kidogo bora.

150
00:07:31,390 --> 00:07:33,950
Na mfano mzuri wa
logarithmic wakati algorithm

151
00:07:33,950 --> 00:07:37,420
umefanya hakika kuonekana na sasa ni
akamtikisatikisa peke yao ya kitabu cha simu

152
00:07:37,420 --> 00:07:39,480
kupata Mike Smith katika kitabu cha simu.

153
00:07:39,480 --> 00:07:40,980
Sisi kupunguza tatizo katika nusu.

154
00:07:40,980 --> 00:07:43,580
Na hivyo kama n anapata kubwa
na kubwa na larger--

155
00:07:43,580 --> 00:07:47,290
kwa kweli, kila wakati mara mbili
n, tu inachukua hatua moja zaidi.

156
00:07:47,290 --> 00:07:49,770
Hivyo hiyo ni mengi zaidi
kuliko kusema, wakati linear.

157
00:07:49,770 --> 00:07:53,030
Ambayo ni kama mara mbili n, ni
inachukua mara mbili ya idadi ya hatua.

158
00:07:53,030 --> 00:07:55,980
Kama mara tatu n, inachukua
mara tatu idadi ya hatua.

159
00:07:55,980 --> 00:07:58,580
Hatua moja kwa kila kitengo.

160
00:07:58,580 --> 00:08:01,790
>> Kisha mambo kupata kidogo more--
kidogo kidogo kubwa kutoka huko.

161
00:08:01,790 --> 00:08:06,622
Una linear wakati utungo, wakati mwingine
aitwaye gogo wakati linear au tu n logi n.

162
00:08:06,622 --> 00:08:08,330
Na tutaweza mfano
ya algorithm kwamba

163
00:08:08,330 --> 00:08:13,370
anaendesha katika n logi n, ambayo bado ni bora
kuliko quadratic time-- n squared.

164
00:08:13,370 --> 00:08:17,320
Au wakati polynomial, n wawili
idadi yoyote kubwa kuliko hizo mbili.

165
00:08:17,320 --> 00:08:20,810
Au kielelezo wakati, ambayo
ni hata worse-- C kwa n.

166
00:08:20,810 --> 00:08:24,670
Hivyo baadhi ya idadi ya mara kwa mara kufufuka kwa
nguvu ya ukubwa wa pembejeo.

167
00:08:24,670 --> 00:08:28,990
Hivyo kama kuna 1,000-- kama
pembejeo data ni wa kawaida 1,000,

168
00:08:28,990 --> 00:08:31,310
itachukua C madarakani 1000.

169
00:08:31,310 --> 00:08:33,559
Ni mengi zaidi kuliko wakati polynomial.

170
00:08:33,559 --> 00:08:35,030
>> Muda factorial ni mbaya zaidi.

171
00:08:35,030 --> 00:08:37,760
Na kwa kweli, kuna kweli kufanya
kuwepo usio algorithms muda,

172
00:08:37,760 --> 00:08:43,740
kama vile, kinachojulikana kijinga sort-- ambao
kazi ni kwa nasibu shuffle safu

173
00:08:43,740 --> 00:08:45,490
na kisha kuangalia kuona
kama ni yamepangwa.

174
00:08:45,490 --> 00:08:47,589
Na kama siyo, nasibu
changa safu tena

175
00:08:47,589 --> 00:08:49,130
na kuangalia kuona kama ni yamepangwa.

176
00:08:49,130 --> 00:08:51,671
Na kama pengine unaweza imagine--
unaweza kufikiria hali

177
00:08:51,671 --> 00:08:55,200
ambapo katika hali mbaya zaidi kesi, kwamba mapenzi
kamwe kweli kuanza na safu.

178
00:08:55,200 --> 00:08:57,150
Algorithm kwamba ingekuwa kukimbia milele.

179
00:08:57,150 --> 00:08:59,349
Na hivyo kwamba itakuwa
usio wakati algorithm.

180
00:08:59,349 --> 00:09:01,890
Hopefully huwezi kuwa kuandika
wakati wowote factorial au usio

181
00:09:01,890 --> 00:09:04,510
algorithms katika CS50.

182
00:09:04,510 --> 00:09:09,150
>> Hivyo, hebu kuchukua kidogo zaidi
kuangalia saruji katika baadhi rahisi

183
00:09:09,150 --> 00:09:11,154
Computational utata madarasa.

184
00:09:11,154 --> 00:09:13,070
Hivyo tuna example--
mifano moja au mbili here--

185
00:09:13,070 --> 00:09:15,590
ya mara kwa mara algorithms muda,
ambayo daima kuchukua

186
00:09:15,590 --> 00:09:17,980
operesheni moja katika kesi mbaya.

187
00:09:17,980 --> 00:09:20,050
Hivyo example-- kwanza
tuna kazi

188
00:09:20,050 --> 00:09:23,952
aitwaye 4 kwa ajili yenu, ambayo
inachukua safu ya ukubwa 1,000.

189
00:09:23,952 --> 00:09:25,660
Lakini basi inaonekana
haina kweli kuangalia

190
00:09:25,660 --> 00:09:29,000
katika it-- kweli haina huduma nini
ndani yake, ya kwamba safu.

191
00:09:29,000 --> 00:09:30,820
Daima tu anarudi nne.

192
00:09:30,820 --> 00:09:32,940
Hivyo, kwamba algorithm,
licha ya ukweli kwamba

193
00:09:32,940 --> 00:09:35,840
inachukua mambo 1,000 haina
kufanya kitu chochote pamoja nao.

194
00:09:35,840 --> 00:09:36,590
Tu anarudi nne.

195
00:09:36,590 --> 00:09:38,240
Ni siku zote hatua moja.

196
00:09:38,240 --> 00:09:41,600
>> Kwa kweli, kuongeza 2 nums-- ambayo
tumeona kabla kama well--

197
00:09:41,600 --> 00:09:43,680
michakato tu integers mbili.

198
00:09:43,680 --> 00:09:44,692
Siyo hatua moja.

199
00:09:44,692 --> 00:09:45,900
Ni kweli hatua kadhaa.

200
00:09:45,900 --> 00:09:50,780
Kupata, kupata b, wewe kuongeza yao
pamoja, na wewe pato matokeo.

201
00:09:50,780 --> 00:09:53,270
Hivyo ni hatua 84.

202
00:09:53,270 --> 00:09:55,510
Lakini mara nyingi ni mara kwa mara,
bila kujali au b.

203
00:09:55,510 --> 00:09:59,240
Una kupata, kupata b, kuongeza
nao pamoja, pato matokeo.

204
00:09:59,240 --> 00:10:02,900
Hivyo hiyo ni mara kwa mara wakati algorithm.

205
00:10:02,900 --> 00:10:05,170
>> Hapa ni mfano wa
linear wakati algorithm

206
00:10:05,170 --> 00:10:08,740
algorithm kwamba gets-- kwamba inachukua
hatua moja zaidi, pengine,

207
00:10:08,740 --> 00:10:10,740
kama mchango wako kukua na 1.

208
00:10:10,740 --> 00:10:14,190
Hivyo, hebu sema sisi ni kuangalia kwa
namba 5 ndani ya safu.

209
00:10:14,190 --> 00:10:16,774
Unaweza kuwa na hali ambapo
unaweza kuipata haki mapema.

210
00:10:16,774 --> 00:10:18,606
Lakini unaweza pia kuwa
Hali ambako

211
00:10:18,606 --> 00:10:20,450
inaweza kuwa kipengele mwisho wa safu.

212
00:10:20,450 --> 00:10:23,780
Katika safu ya ukubwa 5, ikiwa
sisi ni kuangalia kwa namba 5.

213
00:10:23,780 --> 00:10:25,930
Itachukua hatua 5.

214
00:10:25,930 --> 00:10:29,180
Na kwa kweli, kufikiria kwamba kuna
si 5 popote katika safu hii.

215
00:10:29,180 --> 00:10:32,820
Sisi bado kweli kuwa na kuangalia
kila kipengele moja ya safu

216
00:10:32,820 --> 00:10:35,550
ili kujua
iwapo au 5 ni huko.

217
00:10:35,550 --> 00:10:39,840
>> Hivyo katika hali mbaya zaidi kesi, ambayo ni kuwa
kipengele ni ya mwisho katika safu

218
00:10:39,840 --> 00:10:41,700
au haipo kabisa.

219
00:10:41,700 --> 00:10:44,690
Bado tuna kuangalia
wote wa mambo n.

220
00:10:44,690 --> 00:10:47,120
Na hivyo algorithm hii
anaendesha katika muda linear.

221
00:10:47,120 --> 00:10:50,340
Unaweza kuthibitisha kwamba kwa
extrapolating kidogo kwa kusema,

222
00:10:50,340 --> 00:10:53,080
kama tulikuwa na 6-kipengele safu na
tulikuwa kuangalia kwa namba 5,

223
00:10:53,080 --> 00:10:54,890
inaweza kuchukua hatua 6.

224
00:10:54,890 --> 00:10:57,620
Kama tuna 7-kipengele safu na
sisi ni kuangalia kwa namba 5.

225
00:10:57,620 --> 00:10:59,160
Inaweza kuchukua 7 hatua.

226
00:10:59,160 --> 00:11:02,920
Kama sisi kuongeza moja zaidi kipengele kwa wetu
safu, inachukua hatua moja zaidi.

227
00:11:02,920 --> 00:11:06,750
Hiyo ni algorithm linear
katika hali mbaya zaidi kesi.

228
00:11:06,750 --> 00:11:08,270
>> Wanandoa maswali ya haraka kwa ajili yenu.

229
00:11:08,270 --> 00:11:11,170
Nini runtime-- nini
mbaya zaidi kesi Runtime

230
00:11:11,170 --> 00:11:13,700
ya snippet hii hasa wa kanuni?

231
00:11:13,700 --> 00:11:17,420
Hivyo nina 4 kitanzi hapa kwamba anaendesha
kutoka j sawa na 0, njia yote hadi m.

232
00:11:17,420 --> 00:11:21,980
Na nini mimi nina kuona hapa, ni kwamba
mwili wa kitanzi anaendesha katika muda wa mara kwa mara.

233
00:11:21,980 --> 00:11:24,730
Hivyo kwa kutumia istilahi kwamba
tumekuwa tayari kuongelea about-- nini

234
00:11:24,730 --> 00:11:29,390
itakuwa mbaya zaidi kesi
Runtime ya algorithm hii?

235
00:11:29,390 --> 00:11:31,050
Kuchukua pili.

236
00:11:31,050 --> 00:11:34,270
Sehemu ya ndani ya kitanzi
anaendesha katika muda wa mara kwa mara.

237
00:11:34,270 --> 00:11:37,510
Na sehemu ya nje ya
kitanzi ni kwenda kukimbia m nyakati.

238
00:11:37,510 --> 00:11:40,260
Basi nini mbaya zaidi kesi Runtime hapa?

239
00:11:40,260 --> 00:11:43,210
Je, nadhani big-O wa m?

240
00:11:43,210 --> 00:11:44,686
Ningependa kuwa na haki.

241
00:11:44,686 --> 00:11:46,230
>> Vipi kuhusu mtu mwingine?

242
00:11:46,230 --> 00:11:48,590
Wakati huu tuna
kitanzi ndani ya kitanzi.

243
00:11:48,590 --> 00:11:50,905
Tuna kitanzi nje
kwamba anaendesha kutoka sifuri kwa kupita.

244
00:11:50,905 --> 00:11:54,630
Na tuna kitanzi kwamba anaendesha ndani
kutoka sifuri kwa kupita, na ndani ya kwamba,

245
00:11:54,630 --> 00:11:57,890
Mimi hali ya kuwa mwili
kitanzi anaendesha katika muda wa mara kwa mara.

246
00:11:57,890 --> 00:12:02,330
Basi nini mbaya zaidi kesi Runtime
ya snippet hii hasa wa kanuni?

247
00:12:02,330 --> 00:12:06,140
Naam, tena, tuna
nje kitanzi kwamba anaendesha mara uk.

248
00:12:06,140 --> 00:12:09,660
Na kila iteration time--
ya kwamba kitanzi, hasa.

249
00:12:09,660 --> 00:12:13,170
Tuna kitanzi ndani
kwamba pia anaendesha mara uk.

250
00:12:13,170 --> 00:12:16,900
Na kisha ndani ya kwamba, kuna
mara kwa mara time-- snippet kidogo huko.

251
00:12:16,900 --> 00:12:19,890
>> Hivyo kama tuna kitanzi nje kwamba
anaendesha mara p ndani ya ambayo ni

252
00:12:19,890 --> 00:12:22,880
kitanzi ndani ambayo
anaendesha p times-- nini

253
00:12:22,880 --> 00:12:26,480
mbaya zaidi kesi Runtime
ya snippet hii ya kificho?

254
00:12:26,480 --> 00:12:30,730
Je, nadhani big-O wa p mraba?

255
00:12:30,730 --> 00:12:31,690
>> Mimi nina Doug Lloyd.

256
00:12:31,690 --> 00:12:33,880
Hii ni CS50.

257
00:12:33,880 --> 00:12:35,622