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

2
00:00:05,830 --> 00:00:07,910
>> Lahat ng karapatan, kaya, computational kumplikado.

3
00:00:07,910 --> 00:00:10,430
Lamang ng isang piraso ng isang babala
bago namin sumisid sa masyadong far--

4
00:00:10,430 --> 00:00:13,070
Makikita ito ay marahil ay kabilang sa
ang mga bagay na pinaka-math-mabigat

5
00:00:13,070 --> 00:00:14,200
usapan namin tungkol sa CS50.

6
00:00:14,200 --> 00:00:16,950
Sana ito ay hindi masyadong napakalaki
at susubukan naming at gagabay sa iyo

7
00:00:16,950 --> 00:00:19,200
sa pamamagitan ng proseso, ngunit
lamang ng isang piraso ng isang makatarungang babala.

8
00:00:19,200 --> 00:00:21,282
May isang maliit na piraso
ng math kasangkot dito.

9
00:00:21,282 --> 00:00:23,990
Lahat ng karapatan, kaya upang gumawa ng
paggamit ng aming computational mapagkukunan

10
00:00:23,990 --> 00:00:28,170
sa tunay na world-- ito ay talagang
Mahalaga na maunawaan na algorithm

11
00:00:28,170 --> 00:00:30,750
at kung paano sila proseso data.

12
00:00:30,750 --> 00:00:32,810
Kung kami ay may isang tunay na
mahusay na algorithm, kami

13
00:00:32,810 --> 00:00:36,292
ay maaaring mabawasan ang dami ng mga mapagkukunan
mayroon kaming magagamit sa pakikitungo sa mga ito.

14
00:00:36,292 --> 00:00:38,750
Kung kami ay may isang algorithm na
ay pagpunta sa tumagal ng maraming trabaho

15
00:00:38,750 --> 00:00:41,210
upang i-proseso ang isang tunay na
malaking hanay ng data, ito ay

16
00:00:41,210 --> 00:00:44,030
pagpunta sa nangangailangan ng mas maraming
at mas maraming mga mapagkukunan, na kung saan

17
00:00:44,030 --> 00:00:47,980
ay pera, RAM, lahat na uri ng mga bagay-bagay.

18
00:00:47,980 --> 00:00:52,090
>> Kaya, na makaka-aralan ang isang
algorithm gamit ang tool na set,

19
00:00:52,090 --> 00:00:56,110
talaga, itatanong ng question--
kung paano gumagana ang scale algorithm

20
00:00:56,110 --> 00:00:59,020
bilang ihagis namin ang higit pa at mas maraming data at ito?

21
00:00:59,020 --> 00:01:02,220
Sa CS50, ang halaga ng data hindi namin
nagtatrabaho sa ay medyo maliit.

22
00:01:02,220 --> 00:01:05,140
Sa pangkalahatan, ang aming mga programa ay pagpunta
upang tumakbo sa isang segundo o less--

23
00:01:05,140 --> 00:01:07,830
marahil ng isang pulutong ng mas kaunting
lalo na sa maagang bahagi.

24
00:01:07,830 --> 00:01:12,250
>> Ngunit isipin ang tungkol sa isang kumpanya na trato
sa daan-daang milyon-milyong mga customer.

25
00:01:12,250 --> 00:01:14,970
At kailangan nila upang i-proseso
na data ng customer.

26
00:01:14,970 --> 00:01:18,260
Bilang ng bilang ng mga customer nila
Mayroon makakakuha ng mas malaki at mas malaki,

27
00:01:18,260 --> 00:01:21,230
ito ay nangangailangan ng pagpunta sa
mas at mas maraming mga mapagkukunan.

28
00:01:21,230 --> 00:01:22,926
Paano marami pang resources?

29
00:01:22,926 --> 00:01:25,050
Well, na depende sa kung gaano
kami ay suriin ang algorithm,

30
00:01:25,050 --> 00:01:28,097
gamit ang mga tool na ito sa toolbox.

31
00:01:28,097 --> 00:01:31,180
Kapag pinag-uusapan natin ang pagiging kumplikado ng
isang algorithm-- na kung minsan ay makikita mo

32
00:01:31,180 --> 00:01:34,040
marinig ito tinutukoy bilang oras
kumplikado o space kumplikado

33
00:01:34,040 --> 00:01:36,190
ngunit lamang namin ang pagpunta
upang tumawag complexity--

34
00:01:36,190 --> 00:01:38,770
pangkalahatan ay pinag-uusapan natin ang tungkol sa
ang pinakamasama-case na sitwasyon.

35
00:01:38,770 --> 00:01:42,640
Dahil sa ang ganap na pinakamasama tumpok ng
data na maaaring namin ay ibinabato sa ito,

36
00:01:42,640 --> 00:01:46,440
kung paano ang algorithm na ito ng pagpunta sa
iproseso o pakikitungo sa mga na data?

37
00:01:46,440 --> 00:01:51,450
Karaniwan naming tawagan ang pinakamasama-case
runtime ng isang algorithm big-O.

38
00:01:51,450 --> 00:01:56,770
Kaya ay maaaring sinabi ng isang algorithm upang
tumakbo sa O ng n o O ng n squared.

39
00:01:56,770 --> 00:01:59,110
At higit pa tungkol sa kung ano
mga ibig sabihin sa isang segundo.

40
00:01:59,110 --> 00:02:01,620
>> Minsan, bagaman, ang ginagawa namin pag-aalaga
tungkol sa mga pinakamahusay na-case na sitwasyon.

41
00:02:01,620 --> 00:02:05,400
Kung ang data ay ang lahat ng bagay na gusto naming
ito upang maging at ito ay ganap na perpekto

42
00:02:05,400 --> 00:02:09,630
at kami ay pagpapadala ito perpekto
set ng data sa pamamagitan ng aming algorithm.

43
00:02:09,630 --> 00:02:11,470
Paano ito ay hawakan sa na sitwasyon?

44
00:02:11,470 --> 00:02:15,050
Minsan naming sumangguni sa na bilang
big-Omega, para sa mga kaibahan sa mga malaking-O,

45
00:02:15,050 --> 00:02:16,530
kami ay may malaking-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega para sa pinakamahusay na-case na sitwasyon.

47
00:02:18,880 --> 00:02:21,319
Big-O para sa pinakamasama-case na sitwasyon.

48
00:02:21,319 --> 00:02:23,860
Karaniwan, kapag ang pinag-uusapan natin
ang pagiging kumplikado ng isang algorithm,

49
00:02:23,860 --> 00:02:26,370
pinag-uusapan natin ang tungkol sa mga
pinakamasama-case na sitwasyon.

50
00:02:26,370 --> 00:02:28,100
Kaya panatilihin na sa isip.

51
00:02:28,100 --> 00:02:31,510
>> At sa klase na ito, kami ay karaniwang pagpunta
upang iwanan ang mahigpit na pagtatasa sa isang tabi.

52
00:02:31,510 --> 00:02:35,350
May mga agham at mga patlang
mapagmahal sa ganitong uri ng bagay-bagay.

53
00:02:35,350 --> 00:02:37,610
Kapag ang usapan namin tungkol sa pangangatwiran
sa pamamagitan ng mga algorithm,

54
00:02:37,610 --> 00:02:41,822
na kung saan kami ay gawin piraso-by-piraso para sa maraming
algorithms usapan namin sa klase.

55
00:02:41,822 --> 00:02:44,780
Kami ay talagang pakikipag-usap tungkol
pangangatwiran sa pamamagitan nito na may bait,

56
00:02:44,780 --> 00:02:47,070
Hindi na may mga formula, o mga katibayan,
o anumang bagay na tulad ng.

57
00:02:47,070 --> 00:02:51,600
Kaya huwag mag-alala, hindi namin ay magiging
nagiging sa isang malaking klase ng math.

58
00:02:51,600 --> 00:02:55,920
>> Kaya sinabi ko pinapahalagahan namin tungkol sa pagiging kumplikado
dahil ito ay humihingi ng mga katanungan, kung paano

59
00:02:55,920 --> 00:03:00,160
huwag aming mga algorithm hawakan mas malaki at
mas malaking hanay ng data hagis sa kanila.

60
00:03:00,160 --> 00:03:01,960
Well, kung ano ang isang set ng data?

61
00:03:01,960 --> 00:03:03,910
Ano ang ibig sabihin ko kapag sinabi ko na?

62
00:03:03,910 --> 00:03:07,600
Ito ay nangangahulugan na ang anumang gumagawa ng pinaka
kahulugan sa konteksto, upang maging matapat.

63
00:03:07,600 --> 00:03:11,160
Kung kami ay may isang algorithm, ang
Proseso Strings-- hindi namin marahil

64
00:03:11,160 --> 00:03:13,440
pakikipag-usap tungkol sa laki ng mga string.

65
00:03:13,440 --> 00:03:15,190
Iyan ay ang data set--
ang laki, ang bilang

66
00:03:15,190 --> 00:03:17,050
ng mga character na bumubuo sa string.

67
00:03:17,050 --> 00:03:20,090
Kung pinag-uusapan natin ang tungkol sa isang
algorithm na ang proseso ng file,

68
00:03:20,090 --> 00:03:23,930
maaaring pakikipag-usap namin tungkol sa kung paano
maraming kilobytes masaklaw na file.

69
00:03:23,930 --> 00:03:25,710
At iyan ang set ng data.

70
00:03:25,710 --> 00:03:28,870
Kung pinag-uusapan natin ang tungkol sa isang algorithm
na humahawak sa mga array mas pangkalahatang paraan,

71
00:03:28,870 --> 00:03:31,510
tulad ng pag-uuri algorithm
o naghahanap algorithm,

72
00:03:31,510 --> 00:03:36,690
marahil kami ay pakikipag-usap tungkol sa bilang
ng mga elemento na bumubuo ng isang array.

73
00:03:36,690 --> 00:03:39,272
>> Ngayon, maaari naming sukatin ang isang
algorithm-- sa partikular,

74
00:03:39,272 --> 00:03:40,980
kapag sinasabi ko makakaya namin
sukatin ang isang algorithm, ako

75
00:03:40,980 --> 00:03:43,840
ibig sabihin maaari naming masukat kung gaano
maraming mga mapagkukunan na aabutin up.

76
00:03:43,840 --> 00:03:48,990
Kung ang mga resources ay, kung gaano karaming
bytes ng RAM-- o megabytes ng RAM

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

78
00:03:49,790 --> 00:03:52,320
O kung magkano ang panahon na kailangan upang tumakbo.

79
00:03:52,320 --> 00:03:56,200
At maaari naming tawagan ang
masukat, nagkataon, f ng n.

80
00:03:56,200 --> 00:03:59,420
Saan ang n ay ang bilang ng mga
mga elemento sa hanay ng data.

81
00:03:59,420 --> 00:04:02,640
At f ng n ay kung gaano karaming mga somethings.

82
00:04:02,640 --> 00:04:07,530
Gaano karaming mga unit ng mga mapagkukunan ay
ito ay nangangailangan upang i-proseso ang data na iyon.

83
00:04:07,530 --> 00:04:10,030
>> Ngayon, namin talagang hindi pag-aalaga
tungkol sa kung ano f ng n ay eksakto.

84
00:04:10,030 --> 00:04:13,700
Sa katunayan, napaka-bihira namin will--
tiyak ay hindi na ito sa class-- ko

85
00:04:13,700 --> 00:04:18,709
sumisid sa anumang talagang malalim
pagtatasa ng kung ano f ng n ay.

86
00:04:18,709 --> 00:04:23,510
Kami ay pagpunta sa makipag-usap tungkol sa kung ano f ng
n ay humigit-kumulang o kung ano ito ay may gawi na.

87
00:04:23,510 --> 00:04:27,600
At ang mga ugali ng isang algorithm ay
idinidikta ng kanyang pinakamataas na kataga order.

88
00:04:27,600 --> 00:04:29,440
At maaari naming makita kung ano ang aking
ibig sabihin sa pamamagitan ng na sa pamamagitan ng pagsasagawa

89
00:04:29,440 --> 00:04:31,910
isang tumingin sa isang mas kongkreto halimbawa.

90
00:04:31,910 --> 00:04:34,620
>> Kaya sabihin natin na mayroon kami
tatlong iba't-ibang mga algorithm.

91
00:04:34,620 --> 00:04:39,350
Ang unang na kung saan tumatagal ng n
nakakubo, ang ilang mga yunit ng mga mapagkukunan

92
00:04:39,350 --> 00:04:42,880
upang i-proseso ang isang hanay ng mga laki n data.

93
00:04:42,880 --> 00:04:47,000
Kami ay may isang pangalawang algorithm na tumatagal
n nakakubo plus n nakalapat mapagkukunan

94
00:04:47,000 --> 00:04:49,350
upang i-proseso ang isang hanay ng mga laki n data.

95
00:04:49,350 --> 00:04:52,030
At kami ay may isang ikatlong
algorithm na tumatakbo in-- na

96
00:04:52,030 --> 00:04:58,300
tumatagal ng hanggang n nakakubo minus 8n nakalapat
plus 20 n dami ng kayamanan

97
00:04:58,300 --> 00:05:02,370
upang i-proseso ang isang algorithm
may data set ng size n.

98
00:05:02,370 --> 00:05:05,594
>> Ngayon muli, talagang hindi namin ay pagpunta
upang makakuha ng sa antas na ito ng detalye.

99
00:05:05,594 --> 00:05:08,260
Talagang ako lang ay ang mga up
dito bilang isang paglalarawan ng isang punto

100
00:05:08,260 --> 00:05:10,176
na pupuntahan ko na maging
paggawa sa isang segundo, na kung saan

101
00:05:10,176 --> 00:05:12,980
ay na lamang talagang pakialam namin
tungkol sa mga ugali ng mga bagay-bagay

102
00:05:12,980 --> 00:05:14,870
bilang makakuha ng mas malaki ang mga hanay ng data.

103
00:05:14,870 --> 00:05:18,220
Kaya kung ang hanay ng data ay maliit, may
talagang isang medyo malaking pagkakaiba

104
00:05:18,220 --> 00:05:19,870
sa mga algorithm.

105
00:05:19,870 --> 00:05:23,000
Ang ikatlong algorithm doon
tumatagal ng 13 beses na,

106
00:05:23,000 --> 00:05:27,980
13 beses ang dami ng mga mapagkukunan
upang magpatakbo ng kamag-anak sa una.

107
00:05:27,980 --> 00:05:31,659
>> Kung ang aming data set ay size 10, na
ay mas malaki, ngunit hindi kinakailangan na malaki,

108
00:05:31,659 --> 00:05:33,950
maaari naming makita na mayroong
talagang isang piraso ng isang pagkakaiba.

109
00:05:33,950 --> 00:05:36,620
Ang ikatlong algorithm
nagiging mas mahusay.

110
00:05:36,620 --> 00:05:40,120
Ito ay tungkol sa aktwal na 40% -
o 60% mas mahusay.

111
00:05:40,120 --> 00:05:41,580
Ito ay tumatagal ng 40% ng halaga ng oras.

112
00:05:41,580 --> 00:05:45,250
Maaari itong run-- maaari itong tumagal
400 mga yunit ng mga mapagkukunan

113
00:05:45,250 --> 00:05:47,570
upang i-proseso ang isang hanay ng size 10 data.

114
00:05:47,570 --> 00:05:49,410
Sapagkat ang unang
algorithm, sa pamamagitan ng kaibahan,

115
00:05:49,410 --> 00:05:54,520
tumatagal ng 1,000 yunit ng mga mapagkukunan
upang i-proseso ang isang hanay ng size 10 data.

116
00:05:54,520 --> 00:05:57,240
Ngunit tumingin kung ano ang mangyayari bilang
ang aming mga numero na nakukuha kahit na mas malaki.

117
00:05:57,240 --> 00:05:59,500
>> Ngayon, ang pagkakaiba
sa pagitan ng mga algorithm

118
00:05:59,500 --> 00:06:01,420
magsisimula na maging isang maliit na mas maliwanag.

119
00:06:01,420 --> 00:06:04,560
At ang mga katotohanan na may mga
mas mababang-order terms-- o sa halip,

120
00:06:04,560 --> 00:06:09,390
mga tuntunin na may mas mababang exponents--
simulan upang maging kaugnay.

121
00:06:09,390 --> 00:06:12,290
Kung ang isang hanay ng data ay ng laki
1000 at ang unang algorithm

122
00:06:12,290 --> 00:06:14,170
ay tumatakbo sa isang bilyong mga hakbang.

123
00:06:14,170 --> 00:06:17,880
At ang pangalawang algorithm ay tumatakbo sa
isang bilyon at isang milyong mga hakbang.

124
00:06:17,880 --> 00:06:20,870
At tumatakbo ang ikatlong algorithm
sa nahihiya lamang ng isang bilyong mga hakbang.

125
00:06:20,870 --> 00:06:22,620
Ito ay medyo marami ang isang bilyong mga hakbang.

126
00:06:22,620 --> 00:06:25,640
Simulan mga tuntunin ng mas mababang-order
upang maging tunay na kaugnay.

127
00:06:25,640 --> 00:06:27,390
At lamang sa tunay
martilyo sa bahay ang point--

128
00:06:27,390 --> 00:06:31,240
kung ang input ng data ay ang laki ng isang
million-- lahat ng tatlong mga medyo marami

129
00:06:31,240 --> 00:06:34,960
kumuha ng isa quintillion-- kung
aking matematika ay correct-- hakbang

130
00:06:34,960 --> 00:06:37,260
upang i-proseso ang isang input ng data
ng laki ng isang milyon.

131
00:06:37,260 --> 00:06:38,250
Iyan ay isang pulutong ng mga hakbang.

132
00:06:38,250 --> 00:06:42,092
At ang katunayan na ang isa sa kanila baka
tumagal ng ilang 100,000, o isang pares ng 100

133
00:06:42,092 --> 00:06:44,650
million kahit na mas mababa kapag
pinag-uusapan natin ang tungkol sa isang bilang

134
00:06:44,650 --> 00:06:46,990
na big-- ito ay uri ng hindi kaugnay na.

135
00:06:46,990 --> 00:06:50,006
Lahat sila ay may posibilidad na gumawa
humigit-kumulang n nakakubo,

136
00:06:50,006 --> 00:06:52,380
at sa gayon kami ay tunay na sumangguni
sa lahat ng mga algorithm

137
00:06:52,380 --> 00:06:59,520
bilang sa pagkakasunod-sunod ng n
nakakubo o malaki-O ng n nakakubo.

138
00:06:59,520 --> 00:07:03,220
>> Narito ang isang listahan ng ilan sa mga mas
karaniwang computational kumplikado klase

139
00:07:03,220 --> 00:07:05,820
na makikita namin nakakaharap sa
algorithms, sa pangkalahatan.

140
00:07:05,820 --> 00:07:07,970
At din partikular sa CS50.

141
00:07:07,970 --> 00:07:11,410
Ang mga ito ay iniutos mula sa
pangkalahatan pinakamabilis sa itaas,

142
00:07:11,410 --> 00:07:13,940
sa pangkalahatan ay pinakamabagal sa ilalim.

143
00:07:13,940 --> 00:07:16,920
Kaya pare-pareho ang oras algorithm madalas
na ang pinakamabilis na, hindi alintana

144
00:07:16,920 --> 00:07:19,110
ang laki ng
input data pumasa ka sa.

145
00:07:19,110 --> 00:07:23,760
Lagi silang kumuha ng isang operasyon o
isang yunit ng mga mapagkukunan upang harapin.

146
00:07:23,760 --> 00:07:25,730
Ito ay maaaring maging 2, kapangyarihan ito
magiging 3, maaaring ito ay 4.

147
00:07:25,730 --> 00:07:26,910
Ngunit ito ay isang constant number.

148
00:07:26,910 --> 00:07:28,400
Hindi ito nag-iiba.

149
00:07:28,400 --> 00:07:31,390
>> Logarithmic time algorithms
bahagyang mas mahusay.

150
00:07:31,390 --> 00:07:33,950
At isang tunay na magandang halimbawa ng
isang logarithmic oras algorithm

151
00:07:33,950 --> 00:07:37,420
tiyak na iyong nakikita sa pamamagitan ng ngayon ay ang
pansiwang bukod ng phone book

152
00:07:37,420 --> 00:07:39,480
upang mahanap Mike Smith sa aklat ng telepono.

153
00:07:39,480 --> 00:07:40,980
Cut namin ang problema sa kalahati.

154
00:07:40,980 --> 00:07:43,580
At gayon n makakakuha ng mas malaki
at mas malaki at larger--

155
00:07:43,580 --> 00:07:47,290
sa katunayan, ang bawat oras mong i-double
n, tatagal lamang ito ng isa pang hakbang.

156
00:07:47,290 --> 00:07:49,770
Kaya na ng maraming mas mahusay
sa, sabihin nating, sa haba ng panahon.

157
00:07:49,770 --> 00:07:53,030
Alin ang kung double ka n, ito
tumatagal ng double ang bilang ng mga hakbang.

158
00:07:53,030 --> 00:07:55,980
Kung ikaw triple n, ito ay tumatagal ng
triple ang bilang ng mga hakbang.

159
00:07:55,980 --> 00:07:58,580
Isang hakbang sa bawat unit.

160
00:07:58,580 --> 00:08:01,790
>> Pagkatapos bagay makakuha ng isang maliit more--
mas mababa maliit na mahusay na mula doon.

161
00:08:01,790 --> 00:08:06,622
Mayroon kang linear rhythmic oras, minsan
tinatawag na haba ng panahon log o lamang n log n.

162
00:08:06,622 --> 00:08:08,330
At bibigyan namin ng isang halimbawa
ng isang algorithm na

163
00:08:08,330 --> 00:08:13,370
tumatakbo sa n log n, na kung saan ay mas mahusay pa rin
kaysa sa parisukat time-- n nakalapat.

164
00:08:13,370 --> 00:08:17,320
O polinomyal oras, n dalawang
ng anumang numero na mas malaki kaysa sa dalawa.

165
00:08:17,320 --> 00:08:20,810
O pagpaparami oras, na
ay kahit worse-- C sa n.

166
00:08:20,810 --> 00:08:24,670
Kaya ang ilang mga tapat na numero itataas sa
ang kapangyarihan ng laki ng input.

167
00:08:24,670 --> 00:08:28,990
Kaya kung may 1,000-- kung ang
input data ay sukat ng 1000,

168
00:08:28,990 --> 00:08:31,310
ito ay tumagal ng C sa 1000 power.

169
00:08:31,310 --> 00:08:33,559
Ito ay isang pulutong mas masahol pa kaysa polinomyal oras.

170
00:08:33,559 --> 00:08:35,030
>> Factorial time ay kahit na mas masahol pa.

171
00:08:35,030 --> 00:08:37,760
At sa katunayan, may tunay gawin
umiiral walang katapusan na oras algorithm,

172
00:08:37,760 --> 00:08:43,740
tulad ng, tinatawag tangang sort-- na
trabaho ay upang random shuffle isang array

173
00:08:43,740 --> 00:08:45,490
at pagkatapos ay suriin upang makita
kung ito ay pinagsunod-sunod.

174
00:08:45,490 --> 00:08:47,589
At kung ito ay hindi, sapalaran
kaladkarin ang mga paa muli ang array

175
00:08:47,589 --> 00:08:49,130
at suriin upang makita kung ito ay pinagsunod-sunod.

176
00:08:49,130 --> 00:08:51,671
At bilang maaari mong marahil imagine--
maaari mong isipin ang isang sitwasyon

177
00:08:51,671 --> 00:08:55,200
kung saan sa pinakamasama-case, na kalooban
hindi aktwal na magsimula sa mga array.

178
00:08:55,200 --> 00:08:57,150
Algorithm na nais tumakbo magpakailanman.

179
00:08:57,150 --> 00:08:59,349
At sa gayon ay magiging isang
walang katapusan na oras algorithm.

180
00:08:59,349 --> 00:09:01,890
Sana hindi mo ay sumusulat
anumang factorial o walang katapusan na oras

181
00:09:01,890 --> 00:09:04,510
algorithm sa CS50.

182
00:09:04,510 --> 00:09:09,150
>> Kaya, sabihin kumuha ng isang maliit na mas
kongkreto pagtingin sa ilan sa mas simple

183
00:09:09,150 --> 00:09:11,154
computational kumplikado klase.

184
00:09:11,154 --> 00:09:13,070
Kaya mayroon kaming isang example--
o dalawang halimbawa here--

185
00:09:13,070 --> 00:09:15,590
ng pare-pareho ang oras algorithm,
na laging dalhin

186
00:09:15,590 --> 00:09:17,980
isang operasyon sa pinakamasama-case.

187
00:09:17,980 --> 00:09:20,050
Kaya ang unang example--
kami ay may isang function

188
00:09:20,050 --> 00:09:23,952
tinatawag 4 para sa iyo, na
tumatagal ng isang hanay ng mga laki 1,000.

189
00:09:23,952 --> 00:09:25,660
Ngunit pagkatapos ay tila
ay hindi aktwal na hitsura

190
00:09:25,660 --> 00:09:29,000
sa ay hindi talagang pakialam it-- kung ano ang
sa loob ng mga ito, sa na array.

191
00:09:29,000 --> 00:09:30,820
Laging nagbabalik lamang ng apat.

192
00:09:30,820 --> 00:09:32,940
Kaya, algorithm na iyon,
sa kabila ng katotohanan na ito

193
00:09:32,940 --> 00:09:35,840
tumatagal ng 1,000 mga elemento ay hindi ay
gumawa ng anumang bagay sa kanila.

194
00:09:35,840 --> 00:09:36,590
Nagbabalik apat lamang.

195
00:09:36,590 --> 00:09:38,240
Ito ay palaging isang solong hakbang.

196
00:09:38,240 --> 00:09:41,600
>> Sa katunayan, magdagdag ng 2 nums-- saan
na nakita natin dati bilang well--

197
00:09:41,600 --> 00:09:43,680
Pinoproseso lamang ng dalawang integer.

198
00:09:43,680 --> 00:09:44,692
Ito ay hindi isang solong hakbang.

199
00:09:44,692 --> 00:09:45,900
Ito ay talagang isang pares na mga hakbang.

200
00:09:45,900 --> 00:09:50,780
Makakakuha ka ng isang, ikaw ay makakuha ng b, idagdag mo ang mga ito
sama-sama, at ikaw output ang mga resulta.

201
00:09:50,780 --> 00:09:53,270
Kaya ito ay 84 na hakbang.

202
00:09:53,270 --> 00:09:55,510
Ngunit ito ay palaging tapat,
hindi alintana ng isa o b.

203
00:09:55,510 --> 00:09:59,240
Mayroon kang makakuha ng, makakuha b, magdagdag
ang mga ito nang sama-sama, output ang mga resulta.

204
00:09:59,240 --> 00:10:02,900
Kaya na ang isang pare-pareho ang oras algorithm.

205
00:10:02,900 --> 00:10:05,170
>> Narito ang isang halimbawa ng isang
sa haba ng panahon algorithm--

206
00:10:05,170 --> 00:10:08,740
isang algorithm na gets-- na tumatagal
isang karagdagang hakbang, marahil,

207
00:10:08,740 --> 00:10:10,740
habang lumalaki ang iyong input sa pamamagitan ng 1.

208
00:10:10,740 --> 00:10:14,190
Kaya, sabihin natin na kaming naghahanap ng mga
ang bilang 5 sa loob ng isang array.

209
00:10:14,190 --> 00:10:16,774
Maaari mong magkaroon ng isang sitwasyon kung saan
maaari mong mahanap ito medyo maaga.

210
00:10:16,774 --> 00:10:18,606
Ngunit maaari mo ring magkaroon ng
isang sitwasyon kung saan ito

211
00:10:18,606 --> 00:10:20,450
ay maaaring ang huling element ng array.

212
00:10:20,450 --> 00:10:23,780
Sa isang hanay ng mga laki 5, kung
kami ay naghahanap para sa mga numero ng 5.

213
00:10:23,780 --> 00:10:25,930
Gusto tumagal ng 5 hakbang.

214
00:10:25,930 --> 00:10:29,180
At sa katunayan, isipin na may
hindi 5 kahit saan sa array na ito.

215
00:10:29,180 --> 00:10:32,820
Kami pa rin ang tunay na may upang tumingin sa
bawat isang elemento ng array

216
00:10:32,820 --> 00:10:35,550
upang matukoy
kung o hindi 5 ay doon.

217
00:10:35,550 --> 00:10:39,840
>> Kaya sa pinakamasama-case, na kung saan ay na
ang elemento ay huling sa array

218
00:10:39,840 --> 00:10:41,700
o hindi umiiral sa lahat.

219
00:10:41,700 --> 00:10:44,690
Mayroon pa kaming upang tumingin sa
lahat ng mga n elemento.

220
00:10:44,690 --> 00:10:47,120
At kaya ito algorithm
tumatakbo sa haba ng panahon.

221
00:10:47,120 --> 00:10:50,340
Maaari mong kumpirmahin na sa pamamagitan ng
extrapolating nang kaunti sa pagsasabing,

222
00:10:50,340 --> 00:10:53,080
kung nagkaroon kami ng array 6-elemento at
humahanap kami ng mga number 5,

223
00:10:53,080 --> 00:10:54,890
maaari itong tumagal ng 6 na mga hakbang.

224
00:10:54,890 --> 00:10:57,620
Kung kami ay may isang array 7-elemento at
kami ay naghahanap para sa mga numero ng 5.

225
00:10:57,620 --> 00:10:59,160
Maaaring tumagal ng 7 mga hakbang.

226
00:10:59,160 --> 00:11:02,920
Habang nagdadagdag kami ng isa pang elemento sa aming
array, ito ay tumatagal ng isa pang hakbang.

227
00:11:02,920 --> 00:11:06,750
Iyan ay isang linear algorithm
sa pinakamalala-case.

228
00:11:06,750 --> 00:11:08,270
>> Ilang mabilis na mga katanungan para sa iyo.

229
00:11:08,270 --> 00:11:11,170
Ano ang runtime-- kung ano ang
ang pinakamasama-case runtime

230
00:11:11,170 --> 00:11:13,700
ng mga ito partikular na snippet ng code?

231
00:11:13,700 --> 00:11:17,420
Kaya ako ng isang 4 loop dito na tumatakbo
mula j katumbas ng 0, ang lahat ng mga paraan ng hanggang sa m.

232
00:11:17,420 --> 00:11:21,980
At kung ano ang ko na nakikita dito, ay na ang mga
katawan ng loop tumatakbo sa tapat na oras.

233
00:11:21,980 --> 00:11:24,730
Kaya gamit ang mga terminolohiya na
na pinag-usapan namin na about-- ano

234
00:11:24,730 --> 00:11:29,390
ay ang pinakamasama-case
runtime ng algorithm na ito?

235
00:11:29,390 --> 00:11:31,050
Kumuha ng isang segundo.

236
00:11:31,050 --> 00:11:34,270
Ang panloob na bahagi ng loop
tumatakbo sa tapat na oras.

237
00:11:34,270 --> 00:11:37,510
At ang mga panlabas na bahagi ng
loop ang magpapatakbo ng beses m.

238
00:11:37,510 --> 00:11:40,260
Kaya kung ano ang pinakamasama-case runtime dito?

239
00:11:40,260 --> 00:11:43,210
Hulaan mo ba big-O ng m?

240
00:11:43,210 --> 00:11:44,686
Gusto mong maging tama.

241
00:11:44,686 --> 00:11:46,230
>> Paano ang tungkol sa isa pa?

242
00:11:46,230 --> 00:11:48,590
Oras na ito kami ay may isang
loop sa loob ng isang loop.

243
00:11:48,590 --> 00:11:50,905
Kami ay may isang panlabas na loop
na tumatakbo mula sa zero sa p.

244
00:11:50,905 --> 00:11:54,630
At kami ay may isang panloob na loop na tumatakbo
mula sa zero sa p, at sa loob ng na,

245
00:11:54,630 --> 00:11:57,890
Estado ko na ang katawan ng
loop tumatakbo sa tapat na oras.

246
00:11:57,890 --> 00:12:02,330
Kaya kung ano ang pinakamasama-case runtime
ng mga ito partikular na snippet ng code?

247
00:12:02,330 --> 00:12:06,140
Well, muli, kami ay may isang
panlabas na loop na tumatakbo ulit p.

248
00:12:06,140 --> 00:12:09,660
At sa bawat pag-ulit time--
ng na loop, sa halip.

249
00:12:09,660 --> 00:12:13,170
Mayroon kaming isang panloob na loop
na din ang nagpapatakbo ng beses p.

250
00:12:13,170 --> 00:12:16,900
At pagkatapos ay sa loob ng na, may mga
constant time-- kaunti doon snippet.

251
00:12:16,900 --> 00:12:19,890
>> Kaya kung kami ay may isang panlabas na loop na
tumatakbo beses p sa loob ng kung saan ay

252
00:12:19,890 --> 00:12:22,880
sa loob ng isang loop na
tumatakbo p times-- kung ano ang

253
00:12:22,880 --> 00:12:26,480
ang pinakamasama-case runtime
ng ang snippet ng code?

254
00:12:26,480 --> 00:12:30,730
Hulaan mo ba big-O ng p nakalapat?

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

256
00:12:31,690 --> 00:12:33,880
Ito ay CS50.

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