1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Seksyon 3 - Higit kumportableng]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Harvard University]

3
00:00:05,070 --> 00:00:07,310
>> [Ito ay CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Kaya ang unang tanong ay kakaiba worded.

5
00:00:12,700 --> 00:00:17,480
GDB hinahayaan mo ang "i-debug" isang programa, ngunit, higit na partikular, kung ano ang sabihin gagawin mo?

6
00:00:17,480 --> 00:00:22,590
Kukunin ko na answer na ang isa, at hindi ko alam kung ano ang eksaktong inaasahan,

7
00:00:22,590 --> 00:00:27,910
kaya ako paghula ito ay isang bagay na kasama ang mga linya nito ay hinahayaan ka hakbang sa pamamagitan ng hakbang

8
00:00:27,910 --> 00:00:31,540
maglakad sa pamamagitan ng programa, makipag-ugnayan sa mga ito, ang mga pagbabago variable, gawin ang lahat ng mga bagay na ito -

9
00:00:31,540 --> 00:00:34,270
talaga ganap na kontrolin ang pagpapatupad ng isang programa

10
00:00:34,270 --> 00:00:38,410
at siyasatin ang anumang ibinigay na bahagi ng pagpapatupad ng programa.

11
00:00:38,410 --> 00:00:43,030
Kaya Hinahayaan ka ide-debug ang mga bagay ng mga tampok na iyon.

12
00:00:43,030 --> 00:00:44,830
Okay.

13
00:00:44,830 --> 00:00:50,520
Bakit ang binary paghahanap nangangailangan na ang isang array pinagsunod-sunod?

14
00:00:50,520 --> 00:00:53,360
Sino ang nais sagutin iyon?

15
00:00:56,120 --> 00:01:00,070
[Mag-aaral] Dahil hindi ito gumana kung hindi ito pinagsunod-sunod. >> Oo. [Tawa]

16
00:01:00,070 --> 00:01:04,910
Kung hindi ito pinagsunod-sunod, pagkatapos imposibleng hatiin ito sa kalahati

17
00:01:04,910 --> 00:01:07,850
at malaman na ang lahat sa kaliwa ay mas mababa at lahat sa kanan

18
00:01:07,850 --> 00:01:10,490
ay mas malaki kaysa sa gitna halaga.

19
00:01:10,490 --> 00:01:12,790
Kaya ito ay kinakailangan na pinagsunod-sunod.

20
00:01:12,790 --> 00:01:14,170
Okay.

21
00:01:14,170 --> 00:01:17,570
Bakit bubble uri sa O ng n squared?

22
00:01:17,570 --> 00:01:23,230
Ba ang sinuman munang gusto mong magbigay ng isang napaka-mabilis na mataas na antas ng pangkalahatang-ideya ng kung ano ang bubble-uuri?

23
00:01:25,950 --> 00:01:33,020
[Mag-aaral] mo talaga pumunta sa pamamagitan ng bawat elemento at suriin mo ang unang ilang mga elemento.

24
00:01:33,020 --> 00:01:37,150
Kung hindi nila ito kung saan mong magpalit ang mga ito, pagkatapos ay mong suriin ang susunod na ilang mga elemento at iba pa.

25
00:01:37,150 --> 00:01:40,770
Kapag naabot mo na ang katapusan, alam mo na ang pinakamalaking elemento ay nakalagay sa dulo,

26
00:01:40,770 --> 00:01:42,750
kaya huwag pansinin na ang isa pagkatapos mong panatilihin sa pagpunta sa pamamagitan ng,

27
00:01:42,750 --> 00:01:48,490
at sa bawat oras na mayroon kang upang suriin ang isa mas elemento hanggang sa magsagawa ka ng mga walang mga pagbabago. >> Oo.

28
00:01:48,490 --> 00:01:58,470
Ito ay tinatawag na bubble-uuri dahil kung i-flip mo ang hanay sa tabi upang ito ay up at down, vertical,

29
00:01:58,470 --> 00:02:03,100
ang malaking halaga ay tumining at ang maliit na halaga bubble sa itaas.

30
00:02:03,100 --> 00:02:05,210
Kung paano nakuha ang pangalan nito.

31
00:02:05,210 --> 00:02:08,220
At oo, pumunta lamang sa pamamagitan ng.

32
00:02:08,220 --> 00:02:11,190
Mong patuloy na pagpunta sa pamamagitan ng array, pagpapalit ang mas malaking halaga

33
00:02:11,190 --> 00:02:14,040
upang makuha ang pinakamalaking halaga sa ibaba.

34
00:02:14,040 --> 00:02:17,500
>> Bakit ito O ng n squared?

35
00:02:18,690 --> 00:02:24,620
Una, ang sinuman nais na sabihin kung bakit ito O ng n squared?

36
00:02:24,620 --> 00:02:28,760
[Mag-aaral] Dahil para sa bawat run na ito napupunta n beses.

37
00:02:28,760 --> 00:02:32,100
Maaari ka lamang maging sigurado na iyong kinuha ang pinakamalaking elemento lahat ng paraan,

38
00:02:32,100 --> 00:02:35,230
pagkatapos ay mayroon kang upang ulitin na para sa maraming mga sangkap. >> Oo.

39
00:02:35,230 --> 00:02:41,800
Kaya tandaan kung ano ang malaking O ay nangangahulugan at kung ano ang malaking Omega paraan.

40
00:02:41,800 --> 00:02:50,560
Ang malaking O ay tulad ng sa itaas na nakatali sa kung paano mabagal ito aktwal na patakbuhin.

41
00:02:50,560 --> 00:02:58,990
Kaya sa pamamagitan ng sinasabi ito ay O ng n squared, ito ay hindi O ng n o tao ay upang tumakbo

42
00:02:58,990 --> 00:03:02,640
sa linear oras, ngunit ito ay O ng n nakakubo

43
00:03:02,640 --> 00:03:06,390
dahil ito ay bounded sa pamamagitan ng O ng n nakakubo.

44
00:03:06,390 --> 00:03:12,300
Kung ito ay bounded sa pamamagitan ng O ng n squared, pagkatapos ito ay bounded ng n nakakubo din.

45
00:03:12,300 --> 00:03:20,280
Kaya n squared, at sa absolute pinakamasama kaso hindi ito maaaring gawin mas mahusay kaysa sa n squared,

46
00:03:20,280 --> 00:03:22,830
na ang dahilan kung bakit O n squared.

47
00:03:22,830 --> 00:03:31,200
Kaya upang makita ang bahagyang matematika sa kung paano ito ay n squared,

48
00:03:31,200 --> 00:03:40,530
kung kami ay may limang bagay sa aming listahan, sa unang pagkakataon kung gaano karaming mga swaps kami potensyal na kailangan upang gumawa ng

49
00:03:40,530 --> 00:03:47,170
upang makakuha ng ito? Natin ang aktwal na lamang -

50
00:03:47,170 --> 00:03:52,040
Gaano karaming mga swaps ay namin upang gumawa ng sa unang pagtakbo ng bubble-uuri sa pamamagitan ng array?

51
00:03:52,040 --> 00:03:53,540
[Mag-aaral] n - 1. >> Oo.

52
00:03:53,540 --> 00:03:58,340
>> Kung may 5 elemento, kami ay pagpunta sa kailangan upang gumawa ng n - 1.

53
00:03:58,340 --> 00:04:01,100
Pagkatapos sa ikalawang isa kung gaano karaming mga swaps ay namin upang gumawa?

54
00:04:01,100 --> 00:04:03,440
[Mag-aaral] n - 2. >> Oo.

55
00:04:03,440 --> 00:04:11,640
At third n - 3, at pagkatapos ay para sa kaginhawaan kong isulat ang huling dalawang mga

56
00:04:11,640 --> 00:04:15,270
bilang kami ay kailangang gumawa ng mga 2 swaps at 1 makipagpalitan.

57
00:04:15,270 --> 00:04:19,899
Hulaan ko ang huling isa ay maaaring o hindi maaaring aktwal na kailangang mangyari.

58
00:04:19,899 --> 00:04:22,820
Ito sa isang makipagpalitan? Hindi ko alam.

59
00:04:22,820 --> 00:04:26,490
Kaya ito ay ang kabuuang halaga ng mga swaps o hindi bababa sa paghahambing mayroon kang upang gumawa ng.

60
00:04:26,490 --> 00:04:29,910
Kahit na hindi mo swap, kailangan mo pa rin upang ihambing ang mga halaga.

61
00:04:29,910 --> 00:04:33,910
Kaya may mga n - 1 paghahambing sa unang pagtakbo sa pamamagitan ng array.

62
00:04:33,910 --> 00:04:42,050
Kung mong isaayos muli ang mga bagay na ito, ipaalam sa aktwal na gawin itong anim na mga bagay upang ang mga bagay stack up mabuti,

63
00:04:42,050 --> 00:04:44,790
at pagkatapos ay makikita ko 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Kaya lang rearranging mga sums ito, nais namin upang makita kung gaano karaming mga mga paghahambing na gumawa kami

65
00:04:49,910 --> 00:04:52,700
sa buong algorithm.

66
00:04:52,700 --> 00:04:56,550
Kaya kung dalhin namin mga guys down na dito,

67
00:04:56,550 --> 00:05:07,470
pagkatapos pa namin lamang summing gayunpaman maraming mga paghahambing na may mga.

68
00:05:07,470 --> 00:05:13,280
Ngunit kung namin sabihin sa ilang mga ito at nagtutuos namin ito at naming sabihin sa ilang mga,

69
00:05:13,280 --> 00:05:18,130
ito ay pa rin ang parehong problema. Lang namin sabihin sa ilang mga partikular na mga grupo.

70
00:05:18,130 --> 00:05:22,400
>> Kaya ngayon kami ay summing 3 n ng. Hindi lang 3 n ng.

71
00:05:22,400 --> 00:05:27,650
Palagi itong pagpunta sa n / 2 n ng.

72
00:05:27,650 --> 00:05:29,430
Kaya dito namin mangyari na magkaroon ng 6.

73
00:05:29,430 --> 00:05:34,830
Kung tayo ay may 10 bagay, at pagkatapos ay maaari kaming gawin ang pagpapangkat na ito para sa 5 iba't ibang mga pares ng mga bagay

74
00:05:34,830 --> 00:05:37,180
at nagtatapos sa n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Kaya palagi ka pagpunta upang makakuha n / 2 n ng, at kaya ito ipapakita namin itala ito sa n squared / 2.

76
00:05:45,840 --> 00:05:48,890
At kaya kahit ito ang kadahilanan ng kalahati, na mangyayari sa darating sa

77
00:05:48,890 --> 00:05:54,190
dahil sa ang katunayan na sa pamamagitan ng bawat pag-ulit sa ibabaw ng array ihambing namin 1 mas

78
00:05:54,190 --> 00:05:58,040
kaya na kung paano makuha namin ang sa 2, ngunit pa rin ito n squared.

79
00:05:58,040 --> 00:06:01,650
Hindi namin pakialam tungkol sa pare-pareho ang salik ng kalahati.

80
00:06:01,650 --> 00:06:07,760
Kaya ng maraming ng malaking O bagay tulad nito ay nakasalalay sa lamang uri ng paggawa ng ganitong uri ng matematika,

81
00:06:07,760 --> 00:06:12,260
paggawa ng mga sums ng aritmetika at geometric serye bagay-bagay,

82
00:06:12,260 --> 00:06:17,750
ngunit karamihan sa mga ito sa kursong ito ay medyo direkta.

83
00:06:17,750 --> 00:06:19,290
Okay.

84
00:06:19,290 --> 00:06:24,430
Bakit pagpapasok ng uri sa Omega ng n? Ano ang ibig sabihin ng wakas?

85
00:06:24,430 --> 00:06:27,730
[Dalawang mag-aaral nagsasalita nang sabay-sabay - hindi maintindihan] >> Oo.

86
00:06:27,730 --> 00:06:30,630
Omega mo ay maaaring sa tingin ng bilang sa mas mababang nakatali.

87
00:06:30,630 --> 00:06:36,550
>> Kaya hindi mahalaga kung paano mahusay na ang iyong pagpapasok ng-uuri algorithm,

88
00:06:36,550 --> 00:06:41,810
sa kabila ng listahan na nakapasa sa, palaging may upang ihambing ang hindi bababa sa n bagay

89
00:06:41,810 --> 00:06:44,620
o upang umulit sa n bagay.

90
00:06:44,620 --> 00:06:47,280
Bakit na?

91
00:06:47,280 --> 00:06:51,190
[Mag-aaral] Dahil kung ang listahan na pinagsunod-sunod, at pagkatapos ay sa pamamagitan ng unang pag-ulit

92
00:06:51,190 --> 00:06:54,080
maaari ka lamang ginagarantiya na ang unang elemento ay ang hindi bababa sa,

93
00:06:54,080 --> 00:06:56,490
at ang pangalawang pag-ulit ka lamang ginagarantiya ang unang dalawang mga

94
00:06:56,490 --> 00:07:00,010
dahil hindi mo alam na ang natitirang bahagi ng listahan ay pinagsunod-sunod. >> Oo.

95
00:07:00,010 --> 00:07:08,910
Kung pumasa ka sa isang ganap na pinagsunod-sunod sa listahan, sa pinakadulo hindi bababa sa mayroon kang upang pumunta sa lahat ng mga elemento

96
00:07:08,910 --> 00:07:12,180
upang makita na walang kailangang inilipat sa paligid.

97
00:07:12,180 --> 00:07:14,720
Kaya pagpasa sa ibabaw ng listahan at sinasabi oh, ito ay na pinagsunod-sunod,

98
00:07:14,720 --> 00:07:18,240
ito ay imposible para sa iyo na malaman ito pinagsunod-sunod hanggang mong suriin ang bawat elemento

99
00:07:18,240 --> 00:07:20,660
upang makita na sila sa pinagsunod-sunod pagkakasunod-sunod.

100
00:07:20,660 --> 00:07:25,290
Kaya ang mas mababang sumunod sa pagpapasok ng-uuri ay Omega ng n.

101
00:07:25,290 --> 00:07:28,210
Ano ang pinakamasama kaso tumatakbo ang oras ng pagsasama-uuri,

102
00:07:28,210 --> 00:07:31,390
pinakamasama kaso pagiging ang malaking O muli?

103
00:07:31,390 --> 00:07:37,660
Kaya sa pinakamasama kaso sitwasyon, paano pagsasama-uuri tatakbo?

104
00:07:42,170 --> 00:07:43,690
[Mag-aaral] N log n. >> Oo.

105
00:07:43,690 --> 00:07:49,990
Ang pinakamabilis na pangkalahatang pag-uuri algorithm n log n. Hindi mo maaaring gawin mas mahusay.

106
00:07:51,930 --> 00:07:55,130
>> May mga espesyal na mga kaso, at kung kami ay may oras ngayon - ngunit namin marahil won't -

107
00:07:55,130 --> 00:07:59,330
maaari naming makita na gumagana ang mas mahusay kaysa sa n log n.

108
00:07:59,330 --> 00:08:04,050
Ngunit sa pangkalahatang kaso, hindi mo maaaring gawin mas mahusay kaysa sa n log n.

109
00:08:04,050 --> 00:08:09,680
At sumanib-uri-uriin ang mangyayari na ang isa na dapat mong malaman para sa kurso na n log n.

110
00:08:09,680 --> 00:08:13,260
At kaya ipapakita namin aktwal na pagpapatupad na ngayon.

111
00:08:13,260 --> 00:08:18,070
At sa wakas, sa hindi hihigit sa tatlong mga pangungusap, kung paano gumagana ang pagpili-uuri?

112
00:08:18,070 --> 00:08:20,370
Gusto ba ang isang tao upang sagutin, at makikita ko ang bilang ng iyong mga pangungusap

113
00:08:20,370 --> 00:08:22,390
dahil kung kang pumunta ng lagpas 3 -

114
00:08:25,530 --> 00:08:28,330
Ba ang sinuman tandaan ang pagpili-uuri?

115
00:08:31,280 --> 00:08:37,809
Ang Pinili-uuri ay karaniwang medyo madaling tandaan mula sa pangalan.

116
00:08:37,809 --> 00:08:45,350
Mo lang umulit sa ibabaw ng array, hanapin ang anuman ang pinakamalaking halaga o pinakamaliit -

117
00:08:45,350 --> 00:08:47,290
sa anumang pagkakasunod-sunod na iyong pag-uuri-uri.

118
00:08:47,290 --> 00:08:50,750
Kaya sabihin nating namin ang pag-uuri-uri mula sa pinakamaliit sa pinakamalaking.

119
00:08:50,750 --> 00:08:55,250
Kang umulit sa ibabaw ng array, na naghahanap para sa anumang ang minimum na elemento ay,

120
00:08:55,250 --> 00:08:59,750
piliin ito, at pagkatapos lamang magpalitan anumang sa unang lugar.

121
00:08:59,750 --> 00:09:04,090
At pagkatapos ay sa ikalawang pass sa ibabaw ng array, hanapin muli ang minimum na elemento,

122
00:09:04,090 --> 00:09:07,490
piliin ito, at pagkatapos ay i-swap ang mga ito sa kung ano ang sa pangalawang posisyon.

123
00:09:07,490 --> 00:09:10,650
Kaya lamang namin ay pagpili at pagpili ng ang minimum na halaga

124
00:09:10,650 --> 00:09:16,050
at pagpasok sa mga ito sa harap ng array hanggang ito ay pinagsunod-sunod.

125
00:09:19,210 --> 00:09:21,560
Mga tanong sa na?

126
00:09:21,560 --> 00:09:25,710
>> Mga hindi maaaring hindi lumitaw sa form na mayroon kang upang punan kapag ikaw ay nagsusumite ang pset.

127
00:09:29,010 --> 00:09:32,360
Iyon ang isa lamang na ang mga sagot sa mga.

128
00:09:32,360 --> 00:09:34,230
Okay, kaya ngayon coding ng mga problema.

129
00:09:34,230 --> 00:09:40,140
Ko na ipapadala sa pamamagitan ng email - ba sinuman na hindi makakuha ng email na iyon? Okay.

130
00:09:40,140 --> 00:09:46,630
Ko na ipapadala sa email ang espasyo na kami ay pagpunta sa gumagamit,

131
00:09:46,630 --> 00:09:52,120
at kung ikaw ay mag-click sa aking pangalan - kaya tingin ko ako pagpunta sa ibaba

132
00:09:52,120 --> 00:09:57,170
dahil ng paurong r - ngunit kung nag-click ka sa aking pangalan makakakita ka ng 2 mga pagbabago.

133
00:09:57,170 --> 00:10:02,650
Rebisyon 1 na ako na kopyahin at ilagay ang code sa espasyo

134
00:10:02,650 --> 00:10:06,900
para sa mga bagay ng paghahanap ay pagpunta upang ipatupad.

135
00:10:06,900 --> 00:10:10,540
At Rebisyon 2 ay ang uri ng bagay na namin ipatupad pagkatapos na.

136
00:10:10,540 --> 00:10:15,770
Kaya maaari mong i-click sa aking Rebisyon 1 at gumana mula doon.

137
00:10:17,350 --> 00:10:22,060
At ngayon ay gusto naming ipatupad ang binary paghahanap.

138
00:10:22,060 --> 00:10:26,470
>> Ba ang sinuman nais lamang magbigay ng isang pseudocode mataas na antas na paliwanag

139
00:10:26,470 --> 00:10:31,440
ng kung ano ang kami ay pagpunta sa gawin para sa paghahanap? Oo.

140
00:10:31,440 --> 00:10:36,170
[Mag-aaral] mo lang sa gitna ng array at makita kung ano ang iyong hinahanap para sa

141
00:10:36,170 --> 00:10:38,650
ay mas mababa kaysa sa o higit pa kaysa sa.

142
00:10:38,650 --> 00:10:41,080
At kung ito ay mas kaunti, mas mong pumunta sa kalahati na mas,

143
00:10:41,080 --> 00:10:44,750
at kung ito ay higit pa, pumunta ka sa kalahati na mas at ulitin mo na hanggang sa ikaw ay makakuha ng isang bagay.

144
00:10:44,750 --> 00:10:46,570
[Bowden] Oo.

145
00:10:46,570 --> 00:10:51,320
Pansinin na ang aming numero ng array na pinagsunod-sunod,

146
00:10:51,320 --> 00:10:57,190
at sa gayon ay nangangahulugan na maaari naming samantalahin ng na at maaaring suriin muna namin,

147
00:10:57,190 --> 00:11:00,390
okay, Naghahanap ako para sa bilang na 50.

148
00:11:00,390 --> 00:11:03,720
Sa gayon ay maaari kong pumunta sa gitna.

149
00:11:03,720 --> 00:11:07,380
Gitnang mahirap upang tukuyin kapag ito ay isang kahit na bilang ng mga bagay,

150
00:11:07,380 --> 00:11:10,820
ngunit sabihin lamang sabihin lagi naming truncate sa gitna.

151
00:11:10,820 --> 00:11:14,420
Kaya dito mayroon kaming 8 bagay, kaya gitna ay 16.

152
00:11:14,420 --> 00:11:17,330
Naghahanap ako para sa 50, kaya 50 ay mas malaki kaysa sa 16.

153
00:11:17,330 --> 00:11:21,310
Kaya ngayon ko talaga tinatrato ang aking array sa bilang ng mga sangkap na ito.

154
00:11:21,310 --> 00:11:23,450
Ko itapon ang lahat mula 16 sa paglipas ng.

155
00:11:23,450 --> 00:11:27,440
Ngayon ang aking array lamang ang 4 na elemento, at ulitin ko.

156
00:11:27,440 --> 00:11:31,910
Kaya pagkatapos Gusto kong makahanap muli sa gitna, na kung saan ay pagpunta sa 42.

157
00:11:31,910 --> 00:11:34,730
42 ay mas mababa sa 50, kaya ko itapon ang dalawang mga elemento.

158
00:11:34,730 --> 00:11:36,890
Ito ang aking natitirang array.

159
00:11:36,890 --> 00:11:38,430
Ako pagpunta upang mahanap muli ang gitna.

160
00:11:38,430 --> 00:11:42,100
Hulaan ko 50 ay isang masamang halimbawa dahil palagi ko ay itsa bagay sa kaliwa,

161
00:11:42,100 --> 00:11:48,280
ngunit sa pamamagitan ng ang parehong sukatan, kung ako naghahanap para sa isang bagay

162
00:11:48,280 --> 00:11:52,100
at ito ay mas mababa kaysa sa elemento Kasalukuyan Naghahanap ako sa,

163
00:11:52,100 --> 00:11:55,080
pagkatapos ay ako pagpunta upang itapon ang lahat sa kanan.

164
00:11:55,080 --> 00:11:58,150
Kaya ngayon ay kailangan naming ipatupad na.

165
00:11:58,150 --> 00:12:02,310
Pansinin na kailangan namin upang pumasa sa laki.

166
00:12:02,310 --> 00:12:06,730
Maaari din namin hindi kailangan na hard-code na laki.

167
00:12:06,730 --> 00:12:11,640
Kaya kung makuha namin mapupuksa ng na # tukuyin -

168
00:12:19,630 --> 00:12:21,430
Okay.

169
00:12:21,430 --> 00:12:27,180
Paano ko mabuti malaman kung ano ang laki ng array numero kasalukuyang?

170
00:12:27,180 --> 00:12:30,950
>> Gaano karaming mga elemento sa array numero?

171
00:12:30,950 --> 00:12:33,630
[Mag-aaral] Numero, bracket,. Haba?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Iyon ay hindi umiiral sa C.

173
00:12:36,600 --> 00:12:38,580
Kailangan. Haba.

174
00:12:38,580 --> 00:12:42,010
Array ay hindi magkaroon ng mga ari-arian, kaya may walang ari-arian ng haba ng array

175
00:12:42,010 --> 00:12:45,650
na lang magbibigay sa iyo gayunpaman mahaba ang mangyayari upang maging.

176
00:12:48,180 --> 00:12:51,620
[Mag-aaral] Tingnan kung gaano karaming memory mayroon itong at hatiin sa pamamagitan ng kung magkano - >> Oo.

177
00:12:51,620 --> 00:12:55,810
Kaya kung paano namin makita kung gaano karaming memory mayroon itong? >> [Mag-aaral] Sizeof. >> Oo, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof ay ang operator na ibalik ang laki ng array numero.

179
00:13:01,680 --> 00:13:10,060
At na pagpunta sa gayunpaman maraming integer may mga beses ang laki ng isang integer

180
00:13:10,060 --> 00:13:14,050
dahil na ang kung gaano karaming memory na aktwal na ito tumatagal.

181
00:13:14,050 --> 00:13:17,630
Kaya kung gusto ko ang bilang ng mga bagay sa array,

182
00:13:17,630 --> 00:13:20,560
pagkatapos ay ako pagpunta sa gusto mong hatiin ng laki ng isang integer.

183
00:13:22,820 --> 00:13:26,010
Okay. Kaya na ay nagbibigay-daan sa akin pumasa sa laki dito.

184
00:13:26,010 --> 00:13:29,430
Bakit ko kailangan upang pumasa sa laki sa lahat?

185
00:13:29,430 --> 00:13:38,570
Bakit hindi ko lang gawin dito int laki = sizeof (mandala ng dayami) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Bakit ito hindi gumagana?

187
00:13:41,490 --> 00:13:44,470
[Mag-aaral] Ito ay hindi isang pandaigdigang variable.

188
00:13:44,470 --> 00:13:51,540
Mandala ng dayami [Bowden] umiiral at kami ay pagpasa sa mga numero bilang mandala ng dayami,

189
00:13:51,540 --> 00:13:54,700
at ito ay uri ng isang foreshadowing ng kung ano ang darating. Oo.

190
00:13:54,700 --> 00:14:00,170
[Mag-aaral] mandala ng dayami ang reference dito, kaya ito bumalik kung paano malaki ang reference na.

191
00:14:00,170 --> 00:14:02,150
Oo.

192
00:14:02,150 --> 00:14:09,000
Pagdudahan ko sa panayam na nakita mo stack ang talaga, i-right?

193
00:14:09,000 --> 00:14:11,270
Sinasalita namin ang tungkol dito.

194
00:14:11,270 --> 00:14:16,090
Kaya stack ay kung saan ang lahat ng iyong mga variable ay pagpunta sa ay naka-imbak.

195
00:14:16,090 --> 00:14:19,960
>> Anumang memory na inilalaan para sa mga lokal na variable ay pagpunta sa stack,

196
00:14:19,960 --> 00:14:24,790
at mga function na ang bawat nakakakuha ng sarili nitong lugar sa stack, sariling stack frame nito ay kung ano ang tawag.

197
00:14:24,790 --> 00:14:31,590
Kaya pangunahing may stack frame nito, at sa loob nito na umiiral ang mga numero ng array,

198
00:14:31,590 --> 00:14:34,270
at ito ng laki sizeof (mga numero).

199
00:14:34,270 --> 00:14:38,180
Ito ay pagpunta sa laki ng mga numero na hinati sa pamamagitan ng laki ng mga elemento,

200
00:14:38,180 --> 00:14:42,010
ngunit na ang lahat ng buhay sa loob ng stack frame pangunahing.

201
00:14:42,010 --> 00:14:45,190
Kapag tinatawag naming paghahanap, paghahanap nakakakuha ng sariling stack frame nito,

202
00:14:45,190 --> 00:14:48,840
sarili nitong puwang upang mag-imbak ang lahat ng mga lokal na variable.

203
00:14:48,840 --> 00:14:56,420
Ngunit ang mga argumento - kaya mandala ng dayami ay hindi isang kopya ng buong array na ito.

204
00:14:56,420 --> 00:15:00,990
Hindi namin pumasa sa buong array bilang isang kopya sa paghahanap.

205
00:15:00,990 --> 00:15:04,030
Mayroon lamang ang nagpapasa ng isang reference sa array na.

206
00:15:04,030 --> 00:15:11,470
Kaya paghahanap ay maaaring ma-access ang mga bilang na ito sa pamamagitan ng reference.

207
00:15:11,470 --> 00:15:17,100
Pa rin ito-access ang mga bagay na nakatira sa loob ng stack frame pangunahing,

208
00:15:17,100 --> 00:15:22,990
ngunit isa lamang, kapag makuha namin sa mga payo, na dapat na sa lalong madaling panahon,

209
00:15:22,990 --> 00:15:24,980
ito ay kung ano ang payo ay.

210
00:15:24,980 --> 00:15:29,400
Payo lamang ang mga sanggunian sa mga bagay, at maaari mong gamitin ang mga payo upang ma-access ang mga bagay

211
00:15:29,400 --> 00:15:32,030
na sa frame ng stack ng iba pang mga bagay '.

212
00:15:32,030 --> 00:15:37,660
Kaya kahit numero lokal sa pangunahing, maaari pa rin namin itong ma-access sa pamamagitan ng pointer.

213
00:15:37,660 --> 00:15:41,770
Ngunit dahil lamang pointer at ito ay isang reference lamang,

214
00:15:41,770 --> 00:15:45,040
sizeof (mandala ng dayami) lamang nagbabalik ang laki ng sanggunian mismo.

215
00:15:45,040 --> 00:15:47,950
Hindi ito ibalik ang laki ng bagay na ito na tumuturo sa.

216
00:15:47,950 --> 00:15:51,110
Ito ay hindi ibalik ang aktwal na laki ng mga numero.

217
00:15:51,110 --> 00:15:55,660
At kaya ito ay hindi pagpunta upang gumana bilang gusto naming ito sa.

218
00:15:55,660 --> 00:15:57,320
>> Mga tanong sa na?

219
00:15:57,320 --> 00:16:03,250
Ay nawala ang mga payo sa sa makabuluhang mas madugo detalye sa linggo darating.

220
00:16:06,750 --> 00:16:13,740
At ito ay kung bakit ang isang maraming ng mga bagay na nakikita mo, karamihan sa mga search bagay o-uuri ng mga bagay,

221
00:16:13,740 --> 00:16:16,990
sila ay halos lahat ng pagpunta sa kailangan ang aktwal na laki ng array,

222
00:16:16,990 --> 00:16:20,440
dahil sa C, wala kaming ideya kung ano ang laki ng array ay.

223
00:16:20,440 --> 00:16:22,720
Kailangan mo upang mano-manong pumasa ito.

224
00:16:22,720 --> 00:16:27,190
At hindi manu-mano mong maaaring pumasa sa buong array dahil ka pagpasa sa ang reference

225
00:16:27,190 --> 00:16:30,390
at hindi ito maaaring makuha ang laki mula sa reference.

226
00:16:30,390 --> 00:16:32,300
Okay.

227
00:16:32,300 --> 00:16:38,160
Kaya ngayon gusto naming ipatupad kung ano ay ipinaliwanag bago.

228
00:16:38,160 --> 00:16:41,530
Maaari kang gumawa sa ito para sa isang minuto,

229
00:16:41,530 --> 00:16:45,250
at hindi mo na kailangang mag-alala tungkol sa pagkuha ng lahat ng perpektong 100% gumagana.

230
00:16:45,250 --> 00:16:51,410
Magsulat lamang ang kalahati pseudocode para sa kung paano sa tingin mo ito ay gagana.

231
00:16:52,000 --> 00:16:53,630
Okay.

232
00:16:53,630 --> 00:16:56,350
Hindi na kailangang ganap na tapos na ito.

233
00:16:56,350 --> 00:17:02,380
Ngunit ang sinuman kumportable sa kung ano ang mayroon silang sa ngayon,

234
00:17:02,380 --> 00:17:05,599
tulad ng isang bagay na kami sa sama-sama?

235
00:17:05,599 --> 00:17:09,690
Ba ang sinuman nais magboluntaryo? O ko random pick.

236
00:17:12,680 --> 00:17:18,599
Hindi ito sa pamamagitan ng anumang panukalang ngunit ang isang bagay na maaari naming baguhin sa estado ng nagtatrabaho.

237
00:17:18,599 --> 00:17:20,720
[Mag-aaral] Oo naman. >> Okay.

238
00:17:20,720 --> 00:17:27,220
Sa gayon maaari mong i-save ang mga rebisyon sa pamamagitan ng pag-click sa maliit na icon ng I-save.

239
00:17:27,220 --> 00:17:29,950
Ikaw Ramya, karapatan? >> [Mag-aaral] Oo. >> [Bowden] Okay.

240
00:17:29,950 --> 00:17:35,140
Kaya ngayon maaari kong tingnan ang iyong mga rebisyon at ang lahat ay maaaring hilahin ang rebisyon.

241
00:17:35,140 --> 00:17:38,600
At dito mayroon kaming - Okay.

242
00:17:38,600 --> 00:17:43,160
Kaya nagpunta Ramya ang recursive na solusyon, na kung saan ay talagang isang wastong solusyon.

243
00:17:43,160 --> 00:17:44,970
Mayroong dalawang mga paraan na maaari mong gawin ito problema.

244
00:17:44,970 --> 00:17:48,060
Maaari mong alinman sa gawin ito iteratively o recursively.

245
00:17:48,060 --> 00:17:53,860
Ay maaari ring gawin ang mga Karamihan sa mga problema na iyong makakaharap na maaaring gawin recursively iteratively.

246
00:17:53,860 --> 00:17:58,510
Kaya dito namin nagawa mo na ito recursively.

247
00:17:58,510 --> 00:18:03,730
>> Ba ang may gusto na tukuyin kung ano ang ibig sabihin nito ay upang gumawa ng isang recursive function na?

248
00:18:07,210 --> 00:18:08,920
[Mag-aaral] Kapag mayroon kang isang function tawagan mismo

249
00:18:08,920 --> 00:18:13,470
at pagkatapos ay tumawag mismo hanggang ito ay sa totoo at tunay. >> Oo.

250
00:18:13,470 --> 00:18:17,680
Isang recursive function na ay isang function na tawag sa mismong.

251
00:18:17,680 --> 00:18:24,140
May tatlong malaking bagay na recursive function na ay dapat magkaroon ng.

252
00:18:24,140 --> 00:18:27,310
Ang una ay malinaw naman, tawag mismo.

253
00:18:27,310 --> 00:18:29,650
Ang pangalawa ay ang pangunahing kaso.

254
00:18:29,650 --> 00:18:33,390
Kaya sa isang punto ang function ay kailangang tumigil sa pagtawag mismo,

255
00:18:33,390 --> 00:18:35,610
at iyon ang kung ano ang base kaso ay para sa.

256
00:18:35,610 --> 00:18:43,860
Kaya dito alam namin na dapat naming itigil, dapat naming magbigay sa aming paghahanap

257
00:18:43,860 --> 00:18:48,150
kapag simula ay katumbas ng pagtatapos - at kami na pumunta sa kung ano ang nangangahulugan iyon.

258
00:18:48,150 --> 00:18:52,130
Ngunit sa wakas, ang huling bagay na mahalaga para sa recursive function:

259
00:18:52,130 --> 00:18:59,250
ang mga function ay dapat sa paanuman paparating ang pangunahing kaso.

260
00:18:59,250 --> 00:19:04,140
Nais kung hindi ka aktwal na pag-update ng anumang bagay kapag gumawa ka ng pangalawang recursive tawag,

261
00:19:04,140 --> 00:19:07,880
kung literal ka lang ng pagtawag sa function na muli gamit ang parehong mga argumento

262
00:19:07,880 --> 00:19:10,130
at walang pangkalahatang variable ay nagbago o anumang bagay,

263
00:19:10,130 --> 00:19:14,430
hindi mo maabot ang base kaso, kung saan ang kaso na masamang.

264
00:19:14,430 --> 00:19:17,950
Ito ay isang walang-katapusang recursion at stack overflow.

265
00:19:17,950 --> 00:19:24,330
Ngunit dito namin makita na update ay nangyayari dahil kami ay nag-a-update simulan + pagtatapos / 2,

266
00:19:24,330 --> 00:19:28,180
naming ina-update ang katapusan argumento dito, nag-update kami sa simula ng argumento dito.

267
00:19:28,180 --> 00:19:32,860
Kaya sa lahat ng recursive tawag Nag-a-update kami ng isang bagay. Okay.

268
00:19:32,860 --> 00:19:38,110
Gusto mong maglakad sa amin sa pamamagitan ng iyong solusyon? >> Oo naman.

269
00:19:38,110 --> 00:19:44,270
Gumagamit ako ng SearchHelp kaya na sa tuwing ako makagawa ng mga function na tawag na ito

270
00:19:44,270 --> 00:19:47,910
Ko ang simula ng kung saan Naghahanap ako para sa array at sa katapusan

271
00:19:47,910 --> 00:19:49,380
kung saan Naghahanap ako sa array.

272
00:19:49,380 --> 00:19:55,330
>> Sa bawat hakbang na kung saan ito sinasabi ito sa gitna elemento, na simula + pagtatapos / 2,

273
00:19:55,330 --> 00:19:58,850
ay na katumbas sa kung ano ang iyong hinahanap namin?

274
00:19:58,850 --> 00:20:04,650
At kung ito ay, pagkatapos ay nakita namin ito, at hulaan ko na maipo pumasa sa ang mga antas ng recursion.

275
00:20:04,650 --> 00:20:12,540
At kung na hindi totoo, pagkatapos naming suriin kung na gitnang halaga ng array ay masyadong malaki,

276
00:20:12,540 --> 00:20:19,320
kung saan tinitingnan namin sa kaliwang kalahati ng array sa pamamagitan ng pagpunta mula sa simula sa gitna index.

277
00:20:19,320 --> 00:20:22,710
At kung hindi man gawin namin ang kalahati ng pagtatapos.

278
00:20:22,710 --> 00:20:24,740
[Bowden] Okay.

279
00:20:24,740 --> 00:20:27,730
Maganda iyan.

280
00:20:27,730 --> 00:20:36,640
Okay, kaya ang ilang ng mga bagay-bagay, at aktwal, ito ay isang napaka-mataas na antas na bagay

281
00:20:36,640 --> 00:20:41,270
na hindi mo na kailangan malaman para sa kursong ito, ngunit ito ay totoo.

282
00:20:41,270 --> 00:20:46,080
Recursive function, palagi kang marinig na hindi sila ng isang masamang pakikitungo

283
00:20:46,080 --> 00:20:51,160
dahil kung tumawag ka recursively iyong sarili masyadong maraming beses, makakakuha ka ng stack overflow

284
00:20:51,160 --> 00:20:54,990
dahil, bilang ko sinabi bago, ang bawat function na ay nakakakuha ng sarili nitong stack frame.

285
00:20:54,990 --> 00:20:59,500
Kaya bawat tawag ng recursive function na nakakakuha ng sariling stack frame nito.

286
00:20:59,500 --> 00:21:04,140
Kaya kung gumawa ka ng 1,000 recursive tawag, makakakuha ka ng 1,000 frame stack,

287
00:21:04,140 --> 00:21:08,390
at mabilis na humantong sa pagkakaroon ng masyadong maraming mga stack frame at masira lang ang mga bagay.

288
00:21:08,390 --> 00:21:13,480
Kaya na ang dahilan kung bakit recursive function pangkalahatang masamang.

289
00:21:13,480 --> 00:21:19,370
Ngunit may ay isang magaling na subset ng mga recursive function na tinatawag buntot-recursive function,

290
00:21:19,370 --> 00:21:26,120
at ito ang mangyayari sa isang halimbawa ng kung saan kung tagatala ang paunawa na ito

291
00:21:26,120 --> 00:21:29,920
at dapat ito, tingin ko - kumalatong kung pumasa ka sa-O2 bandila

292
00:21:29,920 --> 00:21:33,250
ito mapansin ito ay buntot recursive at gumawa ng mga bagay nang mahusay.

293
00:21:33,250 --> 00:21:40,050
>> Ito ay muling gamitin ang parehong frame ng stack nang paulit-ulit para sa bawat recursive tawag.

294
00:21:40,050 --> 00:21:47,010
At kaya dahil ginagamit mo ang parehong frame ng stack, hindi mo kailangang mag-alala tungkol

295
00:21:47,010 --> 00:21:51,690
kailanman stack umaapaw, at sa parehong oras, tulad ng sinabi mo bago,

296
00:21:51,690 --> 00:21:56,380
kung saan sa sandaling bumalik ka totoo, pagkatapos ito ay may upang bumalik ang lahat ng mga frame ng stack

297
00:21:56,380 --> 00:22:01,740
at ang ika-10 na tawag sa SearchHelp ay bumalik sa ika-9, bumalik sa ika-8.

298
00:22:01,740 --> 00:22:05,360
Sa gayon ay hindi kailangang mangyari kapag ang mga function buntot recursive.

299
00:22:05,360 --> 00:22:13,740
At kaya kung bakit ito buntot recursive function na notice na para sa anumang naibigay na pagtawag sa searchHelp

300
00:22:13,740 --> 00:22:18,470
recursive tawag na ito sa paggawa ng kung ano ang ito bumabalik.

301
00:22:18,470 --> 00:22:25,290
Kaya sa unang tawag sa SearchHelp, hindi namin alinman kaagad bumalik false,

302
00:22:25,290 --> 00:22:29,590
agad na nagbabalik ng tunay, o gumawa kami ng recursive tawag sa SearchHelp

303
00:22:29,590 --> 00:22:33,810
kung saan kung ano ang namin ang bumabalik ay kung ano ang tawag na bumabalik.

304
00:22:33,810 --> 00:22:51,560
At hindi namin maaaring gawin ito kung ginawa namin ang isang bagay tulad ng int x = SearchHelp, bumalik x * 2,

305
00:22:51,560 --> 00:22:55,440
lamang ang ilang mga random na pagbabago.

306
00:22:55,440 --> 00:23:01,470
>> Kaya ngayon ito recursive tawag, ito int x = SearchHelp recursive tawag,

307
00:23:01,470 --> 00:23:05,740
hindi na buntot recursive dahil ang aktwal na ito upang bumalik

308
00:23:05,740 --> 00:23:10,400
bumalik sa isang nakaraang stack frame sa gayon ay na nakaraang tawag sa function na

309
00:23:10,400 --> 00:23:13,040
maaaring gawin ng isang bagay sa ang halaga ng return.

310
00:23:13,040 --> 00:23:22,190
Kaya ito ay hindi buntot recursive, ngunit kung ano ang nagkaroon kami bago ay mabuti buntot recursive. Oo.

311
00:23:22,190 --> 00:23:27,000
[Mag-aaral] ay hindi Kung naka-check ang pangalawang kaso base unang

312
00:23:27,000 --> 00:23:30,640
dahil may isang sitwasyon kung saan kapag pumasa ka ito ang argumento

313
00:23:30,640 --> 00:23:35,770
mo na simulan = pagtatapos, ngunit nila ang halaga ng karayom.

314
00:23:35,770 --> 00:23:47,310
Ang mga tanong ay hindi namin maaaring tumakbo sa kaso kung saan pagtatapos ay ang halaga ng karayom

315
00:23:47,310 --> 00:23:52,000
o simulan = pagtatapos, naaangkop, simulan = pagtatapos

316
00:23:52,000 --> 00:23:59,480
at hindi mo aktwal na check sa partikular na halaga,

317
00:23:59,480 --> 00:24:03,910
pagkatapos ay simulan ang + pagtatapos / 2 ay lamang pagpunta sa parehong halaga.

318
00:24:03,910 --> 00:24:07,890
Ngunit na namin ibinalik mali at hindi namin aktwal check ang halaga.

319
00:24:07,890 --> 00:24:14,240
Kaya sa pinakadulo hindi bababa sa, sa unang tawag, kung ang laki ay 0, pagkatapos ay nais naming upang bumalik false.

320
00:24:14,240 --> 00:24:17,710
Ngunit kung ang laki ay 1, pagkatapos ng pagsisimula ay hindi pagpunta sa katumbas ng pagtatapos,

321
00:24:17,710 --> 00:24:19,820
at kami na hindi bababa sa suriin ang isang elemento.

322
00:24:19,820 --> 00:24:26,750
Ngunit tingin ko na ikaw ay pakanan sa maaari naming magtapos sa isang kaso kung saan simulan + pagtatapos / 2,

323
00:24:26,750 --> 00:24:31,190
simula nagtatapos up ang parehong bilang simula + pagtatapos / 2,

324
00:24:31,190 --> 00:24:35,350
ngunit hindi namin hindi aktwal na check elemento na.

325
00:24:35,350 --> 00:24:44,740
>> Kaya kung namin suriin muna ang ang gitnang elemento ang halaga na kaming naghahanap ng mga,

326
00:24:44,740 --> 00:24:47,110
maaari agad naming nagbabalik ng tunay.

327
00:24:47,110 --> 00:24:50,740
Iba Pa kung sila ay pantay-pantay, at pagkatapos ay walang punto sa magpatuloy

328
00:24:50,740 --> 00:24:58,440
dahil lamang namin ay pagpunta upang i-update sa isang kaso na kung saan kami ay sa isang solong-element array.

329
00:24:58,440 --> 00:25:01,110
Kung iisang elemento ay hindi kaming naghahanap ng mga,

330
00:25:01,110 --> 00:25:03,530
pagkatapos ay ang lahat ng bagay ay mali. Oo.

331
00:25:03,530 --> 00:25:08,900
[Mag-aaral] bagay ay na dahil laki ay talagang mas malaki kaysa sa bilang ng mga elemento sa array,

332
00:25:08,900 --> 00:25:13,070
ay offset - >> Kaya ay laki -

333
00:25:13,070 --> 00:25:19,380
[Mag-aaral] Sabihin kung ang array ang laki 0, pagkatapos ang SearchHelp ang talagang suriin ang mandala ng dayami na 0

334
00:25:19,380 --> 00:25:21,490
sa unang tawag.

335
00:25:21,490 --> 00:25:25,300
Array ay may laki 0, kaya 0 ang - >> Oo.

336
00:25:25,300 --> 00:25:30,750
Mayroong isa pang bagay na - maaari itong maging mahusay. Natin sa tingin.

337
00:25:30,750 --> 00:25:40,120
Kaya kung ang array ay may 10 mga elemento at gitna na kami ay pagpunta upang suriin ang index 5,

338
00:25:40,120 --> 00:25:45,700
kaya kami ay check 5, at sabihin nating ang halaga ay mas mababa.

339
00:25:45,700 --> 00:25:50,720
Kaya namin ang ibinabato lahat ang layo mula sa 5 pasulong.

340
00:25:50,720 --> 00:25:54,030
Kaya simulan ang + pagtatapos / 2 na ang aming bagong pagtatapos,

341
00:25:54,030 --> 00:25:57,450
kaya oo, palagi itong pagpunta upang manatili higit sa dulo ng array.

342
00:25:57,450 --> 00:26:03,570
Kung ito ang kaso kung ito ay kahit o kakaibang, pagkatapos ay namin check, sabihin nating, 4,

343
00:26:03,570 --> 00:26:05,770
ngunit pa namin ang itsa -

344
00:26:05,770 --> 00:26:13,500
Kaya oo, ang pagtatapos ay palaging pagpunta sa higit sa aktwal na dulo ng array.

345
00:26:13,500 --> 00:26:18,350
Kaya ang mga elemento na kami ay tumututok sa, pagtatapos ay palaging ang isa pagkatapos na.

346
00:26:18,350 --> 00:26:24,270
At kaya kung simula ginagawa kailanman katumbas ng pagtatapos, hindi namin sa isang hanay ng mga laki 0.

347
00:26:24,270 --> 00:26:35,600
>> Ang iba pang mga bagay na ako ay nag-iisip Nag-a-update namin ang simula upang simulan ang + pagtatapos / 2,

348
00:26:35,600 --> 00:26:44,020
kaya ito ang kaso na nagkakaroon ako ng problema sa, kung saan simulan + pagtatapos / 2

349
00:26:44,020 --> 00:26:46,820
ang elemento Sinusuri namin.

350
00:26:46,820 --> 00:26:58,150
Sabihin nating nagkaroon kami ang 10-elemento array. Anuman.

351
00:26:58,150 --> 00:27:03,250
Kaya simulan ang + pagtatapos / 2 ay pagpunta sa isang bagay tulad ng isang ito,

352
00:27:03,250 --> 00:27:07,060
at kung hindi iyon ang halaga, sabihin natin na gusto naming i-update.

353
00:27:07,060 --> 00:27:10,060
Ang halaga ay mas mataas, kaya gusto naming upang tingnan ito kalahati ng array.

354
00:27:10,060 --> 00:27:15,910
Kaya kung paano namin ina-update ang simula, kami ay nag-a-update simula ngayon ito elemento.

355
00:27:15,910 --> 00:27:23,790
Ngunit ito ay maaaring pa rin gumagana, o sa pinakadulo hindi bababa sa, maaari mong gawin ng pagsisimula + pagtatapos / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Mag-aaral] Hindi mo na kailangan upang simulan ang + pagtatapos [hindi marinig] >> Oo.

357
00:27:27,850 --> 00:27:33,240
Na namin ang check ang elementong ito at alam ito ay hindi kaming naghahanap ng mga.

358
00:27:33,240 --> 00:27:36,800
Kaya hindi namin kailangan upang i-update ang pagsisimula ito elemento.

359
00:27:36,800 --> 00:27:39,560
Maaari lang namin laktawan ang mga ito at i-update ang simulan na ito elemento.

360
00:27:39,560 --> 00:27:46,060
At doon ay kailanman kaso ng, sabihin nating, na ito ay pagtatapos,

361
00:27:46,060 --> 00:27:53,140
kaya pagkatapos simulan ito ay, simulan ang + pagtatapos / 2 ay ito,

362
00:27:53,140 --> 00:28:00,580
simulan + pagtatapos - Oo, tingin ko ito magtapos sa walang hangganang recursion.

363
00:28:00,580 --> 00:28:12,690
Ipagpalagay natin na ito ay isang hanay ng mga laki ng 2 o ng isang hanay ng mga laki 1. Tingin ko ito gagana.

364
00:28:12,690 --> 00:28:19,490
Sa kasalukuyan, simula na elemento at pagtatapos ay 1 lampas ito.

365
00:28:19,490 --> 00:28:24,110
Kaya ang elemento na kami ay pagpunta upang suriin ang isang ito,

366
00:28:24,110 --> 00:28:29,400
at pagkatapos ay kapag update namin ang pagsisimula, kami ay nag-a-update simula sa 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
na upang tapusin sa amin pabalik sa simula ito elemento.

368
00:28:33,160 --> 00:28:36,210
>> Kaya Sinusuri namin ang parehong elemento nang paulit-ulit.

369
00:28:36,210 --> 00:28:43,310
Kaya ito ang kaso kung saan ang bawat recursive tawag ay dapat aktwal na i-update ang isang bagay.

370
00:28:43,310 --> 00:28:48,370
Kaya kailangan namin upang gawin ang simula + pagtatapos / 2 + 1, o iba pang may kaso

371
00:28:48,370 --> 00:28:50,710
kung saan hindi namin aktwal na pag-update ng pagsisimula.

372
00:28:50,710 --> 00:28:53,820
Makita ng lahat ang na?

373
00:28:53,820 --> 00:28:56,310
Okay.

374
00:28:56,310 --> 00:29:03,860
Ba ang sinuman katanungan sa ang solusyon na ito o ng anumang higit pang mga komento?

375
00:29:05,220 --> 00:29:10,280
Okay. Ba ang sinuman na isang umuulit ng solusyon na maaari namin ang lahat ng tumingin sa?

376
00:29:17,400 --> 00:29:20,940
Ba namin ang lahat ng gawin ito recursively?

377
00:29:20,940 --> 00:29:25,950
O ring hulaan ko kung binuksan mo sa kanya, baka mayroon ka masapawan ang iyong nakaraang isa.

378
00:29:25,950 --> 00:29:28,810
Ba awtomatikong i-save? Hindi ako positibo.

379
00:29:35,090 --> 00:29:39,130
Ba ang sinuman na umuulit?

380
00:29:39,130 --> 00:29:42,430
Maaari kaming maglakad sa pamamagitan nito kung hindi.

381
00:29:46,080 --> 00:29:48,100
Ang ideya ay ang parehong.

382
00:30:00,260 --> 00:30:02,830
Umuulit solusyon.

383
00:30:02,830 --> 00:30:07,140
Kami ay pagpunta sa gusto sa isa lamang na gawin ang parehong ideya

384
00:30:07,140 --> 00:30:16,530
kung saan gusto naming subaybayan ng bagong dulo ng array at ang bagong simula ng array

385
00:30:16,530 --> 00:30:18,510
at gawin na paulit-ulit.

386
00:30:18,510 --> 00:30:22,430
At kung kung ano ang namin ang pagpapanatiling track ng bilang sa simula at sa katapusan na magsalubong,

387
00:30:22,430 --> 00:30:29,020
hindi namin ginawa mahanap ito at maaari naming bumalik false.

388
00:30:29,020 --> 00:30:37,540
Kaya paano ang gagawin ko na? Sinuman ay may mga mungkahi o code para sa akin upang makuha ang?

389
00:30:42,190 --> 00:30:47,450
[Mag-aaral] ba ng isang habang loop. >> Oo.

390
00:30:47,450 --> 00:30:49,450
Pagpunta sa gusto mong gawin ang isang loop.

391
00:30:49,450 --> 00:30:51,830
>> Mayroon ka ba code maaari kong makuha ang, o kung ano ang iyong pagpunta sa iminumungkahi?

392
00:30:51,830 --> 00:30:56,340
[Mag-aaral] tingin ko ito. >> Lahat ng karapatan. Na ito ay gumagawa ng mga bagay na mas madali. Ano ang iyong pangalan?

393
00:30:56,340 --> 00:30:57,890
[Mag-aaral] Lucas.

394
00:31:00,140 --> 00:31:04,190
Rebisyon 1. Okay.

395
00:31:04,190 --> 00:31:13,200
Mababang ay kung ano ang aming tinatawag na simulan ang bago.

396
00:31:13,200 --> 00:31:17,080
Up ay hindi lubos kung ano ang aming tinatawag na pagtatapos bago.

397
00:31:17,080 --> 00:31:22,750
Aktwal na, ang pagtatapos na ngayon sa loob ng array. Ang isang elemento na dapat naming isaalang-alang.

398
00:31:22,750 --> 00:31:26,890
Kaya mababa 0, hanggang ang laki ng array - 1,

399
00:31:26,890 --> 00:31:34,780
at ngayon kami ay looping, at kami ay check -

400
00:31:34,780 --> 00:31:37,340
Hulaan ko maaari mong maglakad sa pamamagitan nito.

401
00:31:37,340 --> 00:31:41,420
Ano ang iyong pag-iisip sa pamamagitan ng? Maglakad sa amin sa pamamagitan ng iyong code.

402
00:31:41,420 --> 00:31:49,940
[Mag-aaral] Oo naman. Hanapin sa mandala ng dayami na halaga sa gitna at ihambing ang mga ito sa karayom.

403
00:31:49,940 --> 00:31:58,520
Kaya kung ito ay mas mataas kaysa sa iyong karayom, pagkatapos gusto mo - oh, aktwal na, na dapat na paurong.

404
00:31:58,520 --> 00:32:05,180
Ka na gusto mong itapon ang karapatan kalahati, at iba pa oo, na dapat na ang paraan.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Kaya ito ay dapat na mas mababa? Ay na kung ano ang sinabi mo? >> [Mag-aaral] Oo.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Okay. Kaunti.

407
00:32:10,390 --> 00:32:15,700
Kaya kung ano ang namin ang pagtingin sa ay mas maliit kaysa sa kung ano ang gusto naming,

408
00:32:15,700 --> 00:32:19,410
pagkatapos ay oo, gusto naming itapon ang kaliwang kalahati,

409
00:32:19,410 --> 00:32:22,210
na nangangahulugan Nag-a-update namin ang lahat ng isinasaalang-alang namin

410
00:32:22,210 --> 00:32:26,610
sa pamamagitan ng paglipat mababa sa kanan ng array.

411
00:32:26,610 --> 00:32:30,130
Ito mukhang mahusay.

412
00:32:30,130 --> 00:32:34,550
Tingin ko ito ay ang parehong isyu na sinabi namin sa nakaraang,

413
00:32:34,550 --> 00:32:49,760
kung saan kung mababa ay 0 at up ay 1, pagkatapos mababa + up / 2 ay i-set up ang parehong bagay muli.

414
00:32:49,760 --> 00:32:53,860
>> At kahit na hindi ito ang kaso, ito ay pa rin sa mas mahusay na sa pinakadulo hindi bababa sa

415
00:32:53,860 --> 00:32:57,630
lang itapon ang sangkap lang namin tumingin sa kung saan alam namin ang mali.

416
00:32:57,630 --> 00:33:03,240
Kaya mababa + up / 2 + 1 - >> [mag-aaral] Iyon ay dapat na sa iba pang mga paraan.

417
00:33:03,240 --> 00:33:05,900
[Bowden] O ito ay dapat na - 1 at ang iba pang isa ay dapat + 1.

418
00:33:05,900 --> 00:33:09,580
[Mag-aaral] At dapat ay may double equals sign. >> [Bowden] Oo.

419
00:33:09,580 --> 00:33:11,340
[Mag-aaral] Oo.

420
00:33:14,540 --> 00:33:15,910
Okay.

421
00:33:15,910 --> 00:33:21,280
At sa wakas, ngayon na kami ay may ito + 1 - 1 bagay,

422
00:33:21,280 --> 00:33:31,520
ito - maaaring hindi ito - ito kailanman posible para sa mababang upang tapusin na may isang halaga na mas malaki kaysa sa up?

423
00:33:35,710 --> 00:33:40,320
Tingin ko ang tanging paraan na maaaring mangyari - posible? >> [Mag-aaral] Hindi ko alam.

424
00:33:40,320 --> 00:33:45,220
Ngunit kung ito ay nakakakuha ng pinutol at pagkatapos ay nakakakuha ng minus 1 at pagkatapos - >> Oo.

425
00:33:45,220 --> 00:33:47,480
[Mag-aaral] Ito posibleng makapag-messed up.

426
00:33:49,700 --> 00:33:53,940
Tingin ko dapat ito ay mabuti lamang dahil

427
00:33:53,940 --> 00:33:58,800
para dito upang tapusin ang mas mababang sila magiging katumbas, sa tingin ko.

428
00:33:58,800 --> 00:34:03,070
Ngunit kung ang mga ito ay pantay-pantay, at pagkatapos ay hindi namin maaaring gawin habang loop upang simulan na may

429
00:34:03,070 --> 00:34:06,670
at lamang namin ay ibinalik na halaga. Kaya tingin ko hindi namin magandang ngayon.

430
00:34:06,670 --> 00:34:11,530
Pansinin na kahit na ang problemang ito ay hindi na recursive,

431
00:34:11,530 --> 00:34:17,400
ang parehong uri ng mga ideya nalalapat kung saan maaari naming makita kung paano ito kaya lends mismo madali

432
00:34:17,400 --> 00:34:23,659
sa isang recursive na solusyon sa pamamagitan ng katotohanan na lang namin-a-update ka sa mga indeks ng paulit-ulit,

433
00:34:23,659 --> 00:34:29,960
ginagawa namin ang problema mas maliit at mas maliit, kami ay nakatuon sa isang subset ng array.

434
00:34:29,960 --> 00:34:40,860
[Mag-aaral] Kung mababa ay 0 at hanggang ay 1, ang mga ito ay parehong 0 + 1/2, na kung saan ay pumunta sa 0,

435
00:34:40,860 --> 00:34:44,429
at pagkatapos ay isa + 1, ay isa na - 1.

436
00:34:47,000 --> 00:34:50,870
[Mag-aaral] Saan na tayo check ng pagkakapantay-pantay?

437
00:34:50,870 --> 00:34:55,100
Gusto kung ang gitna ay aktwal na karayom?

438
00:34:55,100 --> 00:34:58,590
Hindi namin kasalukuyang ginagawa na? Oh!

439
00:35:00,610 --> 00:35:02,460
Kung it's -

440
00:35:05,340 --> 00:35:13,740
Oo. Hindi lamang namin gawin ang mga pagsubok pababa dito dahil sabihin nating ang unang gitna -

441
00:35:13,740 --> 00:35:16,430
[Mag-aaral] aktwal Ito ay bang hindi itapon ang bound.

442
00:35:16,430 --> 00:35:20,220
Kaya kung itapon ang bound, mayroon kang suriin muna ito o anumang.

443
00:35:20,220 --> 00:35:23,350
Ah. Oo. >> [Mag-aaral] Oo.

444
00:35:23,350 --> 00:35:29,650
Kaya ngayon namin itinapon ang kasalukuyan naming tumingin sa,

445
00:35:29,650 --> 00:35:33,260
na nangangahulugan na kailangan namin ngayon ay mayroon ding

446
00:35:33,260 --> 00:35:44,810
kung (mandala ng dayami [(mababang + up) / 2] == karayom), pagkatapos ay maaari naming nagbabalik ng tunay.

447
00:35:44,810 --> 00:35:52,070
At kung ko bang ilagay ang tao o lamang kung, ito ay nangangahulugan na literal ang parehong bagay

448
00:35:52,070 --> 00:35:57,110
dahil ito ay ibinalik totoo.

449
00:35:57,110 --> 00:36:01,450
Kaya makikita ko bang ilagay ang tao kung, ngunit hindi mahalaga.

450
00:36:01,450 --> 00:36:10,440
>> Kaya tao kung ito, tao na ito, at ito ay isang karaniwang bagay na gagawin ko

451
00:36:10,440 --> 00:36:14,340
kung saan kahit kung ito ay sa kaso kung saan ang lahat ng bagay ay handa na dito,

452
00:36:14,340 --> 00:36:22,780
tulad ng mababa hindi kailanman maaaring maging mas malaki kaysa up, hindi nagkakahalaga ng pagdadahilan tungkol sa kung na totoo.

453
00:36:22,780 --> 00:36:28,010
Kaya maaari mong pati na rin sabihin habang mababa ay mas mababa sa o katumbas ng

454
00:36:28,010 --> 00:36:30,720
o habang mababa ay mas mababa sa

455
00:36:30,720 --> 00:36:35,300
kaya kung ang mga ito ay kailanman katumbas o mababa ang mangyayari upang pumasa sa up,

456
00:36:35,300 --> 00:36:40,130
maaari naming masira labas ng loop na ito.

457
00:36:41,410 --> 00:36:44,630
Mga katanungan, mga alalahanin, mga komento?

458
00:36:47,080 --> 00:36:49,270
Okay. Ito mukhang mahusay.

459
00:36:49,270 --> 00:36:52,230
Ngayon gusto naming gawin-uuri.

460
00:36:52,230 --> 00:37:04,030
Kung pumunta kami sa aking pangalawang rebisyon, makikita namin ang parehong mga numero,

461
00:37:04,030 --> 00:37:07,550
ngunit ngayon ang mga ito ay hindi na sa pinagsunod-sunod pagkakasunod-sunod.

462
00:37:07,550 --> 00:37:12,840
At gusto naming ipatupad ng-uuri sa paggamit ng anumang algorithm sa O ng n log n.

463
00:37:12,840 --> 00:37:17,240
Kaya kung saan algorithm tingin mo dapat naming ipatupad dito? >> [Mag-aaral] magsamang bumaybay-uuri.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Oo. Pagsamahin-uuri ay O (n log n), kaya na kung ano ang kami ay pagpunta sa gawin.

465
00:37:23,810 --> 00:37:26,680
At ang problema ay medyo katulad,

466
00:37:26,680 --> 00:37:31,920
kung saan ito lends mismo madali sa isang recursive na solusyon.

467
00:37:31,920 --> 00:37:35,580
Maaari din namin makabuo ng isang umuulit na solusyon kung gusto namin,

468
00:37:35,580 --> 00:37:42,540
ngunit recursion ay madali dito at dapat namin gawin recursion.

469
00:37:45,120 --> 00:37:49,530
Hulaan ko namin ang maglakad sa pamamagitan ng pagsasama-uuri unang,

470
00:37:49,530 --> 00:37:54,280
kahit na mayroong isang magandang video sa pagsasama-uuri na. [Tawa]

471
00:37:54,280 --> 00:37:59,780
Kaya sumanib-uuri may - aksaya ako kaya magkano ng ang papel na ito.

472
00:37:59,780 --> 00:38:02,080
Oh, mayroon lamang isang kaliwa.

473
00:38:02,080 --> 00:38:03,630
Kaya sumanib.

474
00:38:08,190 --> 00:38:12,470
Oh, 1, 3, 5.

475
00:38:26,090 --> 00:38:27,440
Okay.

476
00:38:29,910 --> 00:38:33,460
Sumanib tumatagal ng dalawang magkahiwalay na array.

477
00:38:33,460 --> 00:38:36,780
Indibidwal na mga dalawang array ay parehong pinagsunod-sunod.

478
00:38:36,780 --> 00:38:40,970
Kaya ito array, 1, 3, 5, pinagsunod-sunod. Ito array, 0, 2, 4, pinagsunod-sunod.

479
00:38:40,970 --> 00:38:46,710
Ngayon kung ano sumanib dapat gawin ay pagsamahin ang mga ito sa isang solong array na mismo pinagsunod-sunod.

480
00:38:46,710 --> 00:38:57,130
Kaya gusto namin ang isang hanay ng mga laki 6 na pagpunta sa mga elementong ito sa loob nito

481
00:38:57,130 --> 00:38:59,390
sa pinagsunod-sunod pagkakasunod-sunod.

482
00:38:59,390 --> 00:39:03,390
>> At upang maaari naming samantalahin ng katotohanan na ang mga ito ng dalawang array ay pinagsunod-sunod

483
00:39:03,390 --> 00:39:06,800
upang gawin ito sa linear oras,

484
00:39:06,800 --> 00:39:13,510
linear oras kahulugan kung ang array na ito ay ang laki x at ito ang laki y,

485
00:39:13,510 --> 00:39:20,970
pagkatapos ay ang kabuuang algorithm ay dapat na O (x + y). Okay.

486
00:39:20,970 --> 00:39:23,150
Kaya mungkahi.

487
00:39:23,150 --> 00:39:26,030
[Mag-aaral] ma namin simulan mula sa kaliwa?

488
00:39:26,030 --> 00:39:30,150
Kaya makikita mo ilagay ang 0 down na una at pagkatapos ay ang 1 at pagkatapos dito sa 2.

489
00:39:30,150 --> 00:39:33,320
Kaya ito ay uri ng tulad ng mayroon ka ng isang tab na lumilipat sa kanan. >> [Bowden] Oo.

490
00:39:33,320 --> 00:39:41,070
Para sa parehong ng mga array kung tumuon lamang namin sa pinakakaliwa elemento.

491
00:39:41,070 --> 00:39:43,530
Dahil parehong mga array ay pinagsunod-sunod, alam namin na ang mga 2 elemento

492
00:39:43,530 --> 00:39:46,920
ay ang pinakamaliit na mga elemento sa alinman sa array.

493
00:39:46,920 --> 00:39:53,500
Kaya na nangangahulugan na ang 1 ng mga 2 elemento ay dapat na ang pinakamaliit na elemento sa aming naka-merge na array.

494
00:39:53,500 --> 00:39:58,190
Lang kaya ang mangyayari na ang pinakamaliit na ang isa sa tamang oras na ito.

495
00:39:58,190 --> 00:40:02,580
Kaya tumagal namin 0, ipasok ito sa kaliwa dahil 0 ay mas mababa sa 1,

496
00:40:02,580 --> 00:40:08,210
kaya tumagal 0, ipasok ito sa aming unang posisyon, at pagkatapos ay i-update namin ito

497
00:40:08,210 --> 00:40:12,070
ngayon tumutok sa unang elemento.

498
00:40:12,070 --> 00:40:14,570
At ngayon namin ulitin.

499
00:40:14,570 --> 00:40:20,670
Kaya ngayon namin ihambing ang 2 at 1. 1 ay mas maliit, kaya ipapakita namin ipasok 1.

500
00:40:20,670 --> 00:40:25,300
Naming i-update ang pointer upang ituro sa tao na ito.

501
00:40:25,300 --> 00:40:33,160
Ngayon ginagawa namin itong muli, kaya 2. Na ito ay mag-a-update, ihambing ang mga 2, 3.

502
00:40:33,160 --> 00:40:37,770
Ito update, pagkatapos ay 4 at 5.

503
00:40:37,770 --> 00:40:42,110
Kaya na pagsasama.

504
00:40:42,110 --> 00:40:49,010
>> Dapat ito ay medyo halata na ito ay linear oras dahil pumunta lamang namin ang buong bawat elemento nang isang beses.

505
00:40:49,010 --> 00:40:55,980
At iyon ay ang pinakamalaking hakbang sa pagpapatupad ng pagsasama-uuri ay ginagawa ito.

506
00:40:55,980 --> 00:40:59,330
At ito ay hindi na mahirap.

507
00:40:59,330 --> 00:41:15,020
Ilang bagay na mag-alala tungkol Ipagpalagay natin na tayo ay pinagsasama ang 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Sa kasong ito namin magtapos sa sitwasyon kung saan ang isang ito ay mas maliit,

509
00:41:30,930 --> 00:41:36,160
pagkatapos naming i-update ang pointer, ang isang ito ay mas maliit, i-update ito,

510
00:41:36,160 --> 00:41:41,280
ito ang mas maliit, at ngayon ay mayroon kang makilala

511
00:41:41,280 --> 00:41:44,220
kapag aktwal na iyong maubusan ng mga elemento upang ihambing.

512
00:41:44,220 --> 00:41:49,400
Dahil na namin ginagamit ang buong array,

513
00:41:49,400 --> 00:41:55,190
lahat sa array na ito na ngayon lamang ipinasok sa dito.

514
00:41:55,190 --> 00:42:02,040
Kaya kung namin tumakbo sa punto kung saan ang isa sa aming mga array ay ganap na Pinagsama,

515
00:42:02,040 --> 00:42:06,510
pagkatapos lang ang dadalhin namin ang lahat ng mga elemento ng iba pang mga array at ipasok ang mga ito sa dulo ng array.

516
00:42:06,510 --> 00:42:13,630
Upang maaari naming lamang magpasok ng 4, 5, 6. Okay.

517
00:42:13,630 --> 00:42:18,070
Ito ay isang bagay upang panoorin ang para sa.

518
00:42:22,080 --> 00:42:26,120
Pagpapatupad na dapat na hakbang 1.

519
00:42:26,120 --> 00:42:32,600
Pagsamahin ang uri-uriin pagkatapos batay sa na, 2 hakbang, 2 ulok hakbang.

520
00:42:38,800 --> 00:42:42,090
Sabihin lang bigyan ang array na ito.

521
00:42:57,920 --> 00:43:05,680
Kaya sumanib-uuri, ang hakbang 1 sa recursively masira ang hanay sa mga halves.

522
00:43:05,680 --> 00:43:09,350
Kaya nahati ang array na ito sa halves.

523
00:43:09,350 --> 00:43:22,920
Na kami ngayon 4, 15, 16, 50 at 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
At ngayon ginagawa namin itong muli at hatiin namin ito sa halves.

525
00:43:25,800 --> 00:43:27,530
Lamang ko makikita gawin ito sa bandang ito.

526
00:43:27,530 --> 00:43:34,790
Kaya 4, 15 at 16, 50.

527
00:43:34,790 --> 00:43:37,440
Gusto naming gawin ang parehong bagay sa paglipas dito.

528
00:43:37,440 --> 00:43:40,340
At ngayon namin hatiin ito sa halves muli.

529
00:43:40,340 --> 00:43:51,080
At mayroon kaming 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Kaya na ang aming base kaso.

531
00:43:53,170 --> 00:44:00,540
Kapag ang mga array ng laki 1, pagkatapos namin itigil ang paghahati ng pang-halves.

532
00:44:00,540 --> 00:44:03,190
>> Ngayon kung ano ang namin na ito?

533
00:44:03,190 --> 00:44:15,730
Kami magtapos ito ay masira sa 8, 23, 42, at 108.

534
00:44:15,730 --> 00:44:24,000
Kaya ngayon na hindi namin sa puntong ito, ngayon hakbang dalawang ng pagsasama-uuri ay lamang pinagsasama ng mga pares sa listahan.

535
00:44:24,000 --> 00:44:27,610
Kaya gusto namin upang sumanib mga. Lang namin tawagan sumanib.

536
00:44:27,610 --> 00:44:31,410
Alam namin na ang pagsasama ay bumalik ito sa pinagsunod-sunod pagkakasunod-sunod.

537
00:44:31,410 --> 00:44:33,920
4, 15.

538
00:44:33,920 --> 00:44:41,440
Ngayon nais namin upang sumanib mga ito, at na ay magbabalik ng isang listahan sa mga pinagsunod-sunod pagkakasunod-sunod,

539
00:44:41,440 --> 00:44:44,160
16, 50.

540
00:44:44,160 --> 00:44:57,380
Bumaybay namin mga - hindi ako sumulat - 8, 23 at 42, 108.

541
00:44:57,380 --> 00:45:02,890
Kaya mayroon kami ng mga naka-merge na pares sabay-sabay.

542
00:45:02,890 --> 00:45:05,140
Ngayon lang namin sumanib muli.

543
00:45:05,140 --> 00:45:10,130
Pansinin na ang bawat isa sa mga listahang ito ay pinagsunod-sunod sa mismong,

544
00:45:10,130 --> 00:45:15,220
at pagkatapos ay maaari naming lamang sumanib ang mga listahang ito upang makakuha ng isang listahan ng mga laki 4 na pinagsunod-sunod

545
00:45:15,220 --> 00:45:19,990
at sumanib sa dalawang mga listahan upang makakuha ng isang listahan ng mga laki 4 na pinagsunod-sunod.

546
00:45:19,990 --> 00:45:25,710
At sa wakas, maaari naming sumanib sa mga dalawang mga listahan ng mga laki 4 upang makakuha ng isang listahan ng mga laki 8 na pinagsunod-sunod.

547
00:45:25,710 --> 00:45:34,030
Kaya upang makita na ito ay pangkalahatang n log n, nakita namin na na pagsasama ay linear,

548
00:45:34,030 --> 00:45:40,390
kaya kapag kami ay pagharap sa pinagsasama ang mga, kaya tulad ng ang kabuuang gastos ng pagsasama

549
00:45:40,390 --> 00:45:43,410
para sa dalawang mga listahan ay 2 dahil -

550
00:45:43,410 --> 00:45:49,610
O mahusay, ito O ng n, ngunit n dito ang 2 elemento, kaya ito ay 2.

551
00:45:49,610 --> 00:45:52,850
At ang mga 2 ay 2 at mga 2 ay 2 at mga 2 ay 2,

552
00:45:52,850 --> 00:45:58,820
ito sa lahat ng merges na kailangan namin upang gawin, magtapos namin ginagawa n.

553
00:45:58,820 --> 00:46:03,210
Tulad ng 2 + 2 + 2 + 2 8, na n,

554
00:46:03,210 --> 00:46:08,060
kaya ang gastos ng pagbubuklod sa set na ito ay n.

555
00:46:08,060 --> 00:46:10,810
At pagkatapos ay ang parehong bagay dito.

556
00:46:10,810 --> 00:46:16,980
Susubukan naming pagsamahin ang mga 2, pagkatapos mga 2, at kanya-kanyang sumanib ito ay tumagal ng apat na pagpapatakbo,

557
00:46:16,980 --> 00:46:23,610
ito sumanib tumagal ng apat na pagpapatakbo, ngunit muli, sa pagitan ng lahat ng mga ito,

558
00:46:23,610 --> 00:46:29,030
magtapos namin pinagsasama n kabuuang mga bagay, at kaya ang hakbang na ito ay tumatagal ng n.

559
00:46:29,030 --> 00:46:33,670
At kaya antas ng bawat isa ay tumatagal ng n elemento na Pinagsama.

560
00:46:33,670 --> 00:46:36,110
>> At kung gaano karaming mga antas?

561
00:46:36,110 --> 00:46:40,160
Sa bawat antas, ang aming array ay lumalaki sa pamamagitan ng laki 2.

562
00:46:40,160 --> 00:46:44,590
Narito aming array ng laki 1, dito sila ng laki 2, narito sila ng laki 4,

563
00:46:44,590 --> 00:46:46,470
at sa wakas, sila ng laki 8.

564
00:46:46,470 --> 00:46:56,450
Kaya dahil ito ay pagdodoble, may pagpunta sa isang kabuuan ng log n ng mga antas na ito.

565
00:46:56,450 --> 00:47:02,090
Kaya sa pag-log n antas, ang bawat indibidwal na antas pagkuha n kabuuang pagpapatakbo,

566
00:47:02,090 --> 00:47:05,720
makuha namin ang isang n log n algorithm.

567
00:47:05,720 --> 00:47:07,790
Mga tanong?

568
00:47:08,940 --> 00:47:13,320
Na-ng mga tao na gumawa ng progreso sa kung paano ipatupad ang?

569
00:47:13,320 --> 00:47:18,260
Sinuman na sa isang estado na kung saan maaari ko lamang makuha ang kanilang mga code?

570
00:47:20,320 --> 00:47:22,260
Maaari ko bang magbigay ng isang minuto.

571
00:47:24,770 --> 00:47:27,470
Ito ay pagpunta sa na.

572
00:47:27,470 --> 00:47:28,730
Ko lubos na inirerekomenda magbalik -

573
00:47:28,730 --> 00:47:30,510
Hindi mo kailangang gawin ang recursion para sa pagsasama

574
00:47:30,510 --> 00:47:33,750
dahil gawin recursion para sa pagsasama, ka upang pumasa ang isang grupo ng mga iba't ibang laki.

575
00:47:33,750 --> 00:47:37,150
Maaari mong, ngunit ito ay nakakainis.

576
00:47:37,150 --> 00:47:43,720
Ngunit recursion-uri-uriin mismo ay medyo madali.

577
00:47:43,720 --> 00:47:49,190
Mo lang literal tumawag uri sa kaliwang kalahati,-uuri sa kanang kalahati. Okay.

578
00:47:51,770 --> 00:47:54,860
Sinuman ay may anumang bagay na maaari kong makuha ang pa?

579
00:47:54,860 --> 00:47:57,540
O tao Bibigyan kita ng isang minuto.

580
00:47:58,210 --> 00:47:59,900
Okay.

581
00:47:59,900 --> 00:48:02,970
Sinuman ay may isang bagay na maaari naming?

582
00:48:05,450 --> 00:48:09,680
O kaya makikita lang namin na ito at pagkatapos ay palawakin mula doon.

583
00:48:09,680 --> 00:48:14,050
>> Sinuman ay may higit pa kaysa sa na maaari kong makuha ang?

584
00:48:14,050 --> 00:48:17,770
[Mag-aaral] Oo. Maaari mong makuha ang mina. >> Lahat ng karapatan.

585
00:48:17,770 --> 00:48:19,730
Oo!

586
00:48:22,170 --> 00:48:25,280
[Mag-aaral] May ng maraming ng mga kondisyon. >> Oh, shoot. Maaari mong -

587
00:48:25,280 --> 00:48:28,110
[Mag-aaral] kailangan ko upang i-save ang mga ito. >> Oo.

588
00:48:32,420 --> 00:48:35,730
Kaya ginawa namin gawin ang sumanib sa hiwalay.

589
00:48:35,730 --> 00:48:38,570
Oh, ngunit ito ay hindi na masamang.

590
00:48:39,790 --> 00:48:41,650
Okay.

591
00:48:41,650 --> 00:48:47,080
Kaya-uuri ay mismo lamang pagtawag mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Ipaliwanag sa amin kung ano ang mergeSortHelp ginagawa.

593
00:48:49,530 --> 00:48:55,700
[Mag-aaral] MergeSortHelp medyo magkano ang ipinapakita ng dalawang pangunahing mga hakbang,

594
00:48:55,700 --> 00:49:01,270
na upang pag-uri-uriin ang bawat kalahati ng array at pagkatapos ay upang sumanib ang parehong sa kanila.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Okay, kaya ninyo ako ng isang segundo.

596
00:49:10,850 --> 00:49:13,210
Sa tingin ko ito - >> [mag-aaral] Kailangan ko bang -

597
00:49:17,100 --> 00:49:19,400
Oo. Ako nawawalang ng isang bagay.

598
00:49:19,400 --> 00:49:23,100
Sa pagsasama, Napagtanto ko na kailangan ko upang lumikha ng isang bagong array

599
00:49:23,100 --> 00:49:26,530
dahil hindi ko maaaring gawin ito sa lugar. >> Oo. Hindi ka maaari. Iwasto.

600
00:49:26,530 --> 00:49:28,170
[Mag-aaral] Kaya kong lumikha ng isang bagong array.

601
00:49:28,170 --> 00:49:31,510
Nakalimutan ko ang sa dulo ng sumanib muling baguhin.

602
00:49:31,510 --> 00:49:34,490
Okay. Kailangan namin ng isang bagong array.

603
00:49:34,490 --> 00:49:41,000
Sa pagsasama-uuri, ito ay halos palaging totoo.

604
00:49:41,000 --> 00:49:44,340
Bahagi ng gastos ng isang mas mahusay na oras na matalino algorithm

605
00:49:44,340 --> 00:49:47,310
ay halos palaging nangangailangan gamitin ng kaunti pang memory.

606
00:49:47,310 --> 00:49:51,570
Kaya dito, kahit na kung paano ito gawin sumanib uri,

607
00:49:51,570 --> 00:49:54,780
ay hindi maaaring hindi mo kailangan upang gamitin ang ilang dagdag na memorya.

608
00:49:54,780 --> 00:49:58,240
Niya nilikha ang isang bagong array.

609
00:49:58,240 --> 00:50:03,400
At pagkatapos ay sabihin sa dulo kailangan lang namin upang kopyahin ang bagong array sa orihinal na array.

610
00:50:03,400 --> 00:50:04,830
[Mag-aaral] tingin ko ito, oo.

611
00:50:04,830 --> 00:50:08,210
Hindi ko alam kung na gumagana sa mga tuntunin ng pagbibilang sa pamamagitan ng reference o anumang -

612
00:50:08,210 --> 00:50:11,650
Oo, ito gumagana. >> [Mag-aaral] Okay.

613
00:50:20,620 --> 00:50:24,480
Ang ibig mo bang subukang patakbuhin ito? >> [Mag-aaral] Hindi, hindi pa. >> Okay.

614
00:50:24,480 --> 00:50:28,880
Subukang patakbuhin ito, at pagkatapos ay kukunin ko na makipag-usap tungkol dito para sa isang segundo.

615
00:50:28,880 --> 00:50:35,200
[Mag-aaral] Kailangan ko ang lahat ng mga modelo ng function na at ang lahat, bagaman, i-right?

616
00:50:37,640 --> 00:50:40,840
Ang mga modelo ng function na. Oh, ibig sabihin tulad ng - Oo.

617
00:50:40,840 --> 00:50:43,040
-Uri-uriin ang pagtawag mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Kaya sa order para sa uri sa tawagan ang mergeSortHelp, mergeSortHelp dapat alinman na-tinukoy

619
00:50:47,390 --> 00:50:56,370
bago-uuri o kailangan lang namin ang prototype. Kopyahin lamang at i-paste na.

620
00:50:56,370 --> 00:50:59,490
At katulad, pagtawag ng mergeSortHelp ay pagsamahin

621
00:50:59,490 --> 00:51:03,830
ngunit sumanib ay hindi pa tinukoy, sa gayon maaari naming ipaalam lamang sa mergeSortHelp alam

622
00:51:03,830 --> 00:51:08,700
na iyon ang bumaybay ay pagpunta sa hitsura, at na na.

623
00:51:09,950 --> 00:51:15,730
Kaya mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Mayroon kaming isang isyu dito kung saan mayroon kaming walang batayang kaso.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp ay recursive, kaya ang anumang recursive function na

626
00:51:38,110 --> 00:51:42,610
ay pagpunta sa kailangan ang ilang mga uri ng mga kaso ng base sa alam kapag upang itigil recursively pagtawag mismo.

627
00:51:42,610 --> 00:51:45,590
Ano ang aming base kaso ng pagpunta sa na dito? Oo.

628
00:51:45,590 --> 00:51:49,110
[Mag-aaral] Kung laki ay 1? >> [Bowden] Oo.

629
00:51:49,110 --> 00:51:56,220
Kaya tulad ng nakita natin doon, huminto kami ng mga array paghahati ng pang-

630
00:51:56,220 --> 00:52:01,850
sabay-sabay namin nakuha sa mga array ng laki 1, na kung saan ay hindi maaaring hindi pinagsunod-sunod ang kanilang mga sarili.

631
00:52:01,850 --> 00:52:09,530
Kaya kung laki katumbas 1, alam namin array ay na pinagsunod-sunod,

632
00:52:09,530 --> 00:52:12,970
upang maaari naming lamang bumalik.

633
00:52:12,970 --> 00:52:16,880
>> Mapansin na walang bisa, kaya hindi namin bumalik anumang partikular, namin lamang bumalik.

634
00:52:16,880 --> 00:52:19,580
Okay. Upang ang aming base kaso.

635
00:52:19,580 --> 00:52:27,440
Ako hulaan ang aming base kaso maaari rin kung mangyari namin pinagsasama ang isang hanay ng mga laki 0,

636
00:52:27,440 --> 00:52:30,030
marahil namin nais na huminto sa ilang mga punto,

637
00:52:30,030 --> 00:52:33,610
upang maaari naming sabihin na ang laki mas mababa sa 2 o mas mababa sa o katumbas ng 1

638
00:52:33,610 --> 00:52:37,150
kaya na ito ay gumana para sa anumang array sa ngayon.

639
00:52:37,150 --> 00:52:38,870
Okay.

640
00:52:38,870 --> 00:52:42,740
Upang ang aming base kaso.

641
00:52:42,740 --> 00:52:45,950
Ngayon ang gusto mong maglakad sa amin sa pamamagitan ng pagsasama?

642
00:52:45,950 --> 00:52:49,140
Ano ang ibig sabihin ng lahat ng mga kasong ito?

643
00:52:49,140 --> 00:52:54,480
Up dito, kami ay paggawa ng parehong ideya, ang -

644
00:52:56,970 --> 00:53:02,470
[Mag-aaral] Kailangan ko na pagpasa laki sa lahat ng mga tawag mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
Nagdagdag ako laki bilang isang karagdagang pangunahing at hindi doon, tulad ng laki / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, laki / 2, laki / 2. >> [Mag-aaral] Oo, at din sa itaas function na pati na rin.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Narito? >> [Mag-aaral] lang laki. >> [Bowden] Oh. Laki, laki? >> [Mag-aaral] Oo.

648
00:53:21,320 --> 00:53:23,010
[Bowden] Okay.

649
00:53:23,010 --> 00:53:26,580
Hayaan akong-isip para sa pangalawang.

650
00:53:26,580 --> 00:53:28,780
Ba naming tumakbo sa isang isyu?

651
00:53:28,780 --> 00:53:33,690
Palagi kaming pagpapagamot sa kaliwa bilang 0. >> [Mag-aaral] No.

652
00:53:33,690 --> 00:53:36,340
Na ang mali. Sorry. Dapat itong maging simula. Oo.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Okay. Gusto ko na mas mahusay.

654
00:53:39,230 --> 00:53:43,880
At pagtatapos. Okay.

655
00:53:43,880 --> 00:53:47,200
Kaya ngayon ang gusto mong maglakad sa amin sa pamamagitan ng pagsasama? >> [Mag-aaral] Okay.

656
00:53:47,200 --> 00:53:52,150
Lang ako sa paglalakad sa pamamagitan ng bagong array na ito na aking nilikha.

657
00:53:52,150 --> 00:53:57,420
Ang laki nito ay ang laki ng bahagi ng array na gusto namin na pinagsunod-sunod

658
00:53:57,420 --> 00:54:03,460
at sinusubukan upang mahanap ang mga elemento na dapat kong ilagay sa bagong array hakbang.

659
00:54:03,460 --> 00:54:10,140
Kaya upang gawin iyon, unang ako check kung ang kaliwang kalahati ng array ay patuloy upang magkaroon ng anumang higit pang mga elemento,

660
00:54:10,140 --> 00:54:14,260
at kung ito ay hindi, pagkatapos mong pumunta down na pang tao na kondisyon, na lang sabi

661
00:54:14,260 --> 00:54:20,180
okay, dapat ito ay sa tamang array, at maglalagay kami na sa kasalukuyang index ng newArray.

662
00:54:20,180 --> 00:54:27,620
>> At pagkatapos ay kung hindi man, ako check kung ang kanang bahagi ng array din tapos,

663
00:54:27,620 --> 00:54:30,630
kung saan ko lang ilagay sa kaliwa.

664
00:54:30,630 --> 00:54:34,180
Na hindi maaaring aktwal na kinakailangan. Hindi ako sigurado.

665
00:54:34,180 --> 00:54:40,970
Ngunit pa rin, ang iba pang dalawang check kung alin sa dalawang mas maliit sa kaliwa o kanan.

666
00:54:40,970 --> 00:54:49,770
At din sa bawat kaso, ako incrementing alinman placeholder ko dagdagan.

667
00:54:49,770 --> 00:54:52,040
[Bowden] Okay.

668
00:54:52,040 --> 00:54:53,840
Na mukhang mabuti.

669
00:54:53,840 --> 00:54:58,800
Ba ang sinuman na may mga komento o mga alalahanin o mga tanong?

670
00:55:00,660 --> 00:55:07,720
Kaya ang apat na mga kaso na mayroon kaming upang dalhin ang mga bagay lamang pagiging - o mukhang limang -

671
00:55:07,720 --> 00:55:13,100
ngunit mayroon kaming upang isaalang-alang kung ang kaliwang array ay maubusan ng mga bagay na kailangan namin upang sumanib,

672
00:55:13,100 --> 00:55:16,390
kung ang kanan array ay maubusan ng mga bagay na kailangan namin upang sumanib -

673
00:55:16,390 --> 00:55:18,400
Pagturo ako sa wala.

674
00:55:18,400 --> 00:55:21,730
Kaya kung ang kaliwang array ay tumakbo na ng mga bagay o ang karapatan na array ay maubusan ng mga bagay.

675
00:55:21,730 --> 00:55:24,320
Iyon ang dalawang mga kaso.

676
00:55:24,320 --> 00:55:30,920
Kailangan din namin ang trivia kaso kung ang kaliwang bagay ay mas mababa ang mga tamang bagay.

677
00:55:30,920 --> 00:55:33,910
Pagkatapos gusto naming pumili ng kaliwang bagay.

678
00:55:33,910 --> 00:55:37,630
Iyon ang mga kaso.

679
00:55:37,630 --> 00:55:40,990
Kaya ito ay karapatan, kaya na na.

680
00:55:40,990 --> 00:55:46,760
Array natitira. 1, 2, 3. Okay. Kaya oo, mga sa apat na mga bagay na maaari naming nais gawin.

681
00:55:50,350 --> 00:55:54,510
At hindi namin ay pumunta sa isang umuulit solusyon.

682
00:55:54,510 --> 00:55:55,980
Hindi ko inirerekomenda -

683
00:55:55,980 --> 00:56:03,070
Pagsamahin-uuri ay isang halimbawa ng isang function na ay parehong hindi buntot recursive,

684
00:56:03,070 --> 00:56:07,040
hindi madaling ito buntot recursive,

685
00:56:07,040 --> 00:56:13,450
kundi pati na rin ito ay hindi masyadong madaling upang gawin itong umuulit.

686
00:56:13,450 --> 00:56:16,910
Ito ay napakadali.

687
00:56:16,910 --> 00:56:19,170
Ang pagpapatupad ng pagsasama-uuri,

688
00:56:19,170 --> 00:56:22,140
pagsamahin, hindi mahalaga kung ano ang ginagawa mo, ikaw ay pagpunta sa bumuo ng pagsasama.

689
00:56:22,140 --> 00:56:29,170
>> Kaya sumanib recursively-uuri na itinayo sa tuktok ng pagsasama lamang ang tatlong linya.

690
00:56:29,170 --> 00:56:34,700
Iteratively, ito ay mas nakakainis at mas mahirap na isipin ang tungkol.

691
00:56:34,700 --> 00:56:41,860
Ngunit mapansin na ito ay hindi buntot recursive dahil mergeSortHelp - kapag ito tawag mismo -

692
00:56:41,860 --> 00:56:46,590
pa rin ito kailangang gawin ang mga bagay pagkatapos ito recursive tawag babalik.

693
00:56:46,590 --> 00:56:50,830
Kaya stack frame na ito ay dapat patuloy na umiiral kahit na matapos pagtawag na ito.

694
00:56:50,830 --> 00:56:54,170
At pagkatapos ay kapag tumawag ka ito, ang stack frame ay dapat patuloy na umiiral

695
00:56:54,170 --> 00:56:57,780
dahil kahit na pagkatapos na tawag, kailangan pa rin namin upang sumanib.

696
00:56:57,780 --> 00:57:01,920
At ito ay nontrivial buntot ito recursive.

697
00:57:04,070 --> 00:57:06,270
Mga tanong?

698
00:57:08,300 --> 00:57:09,860
Ayos lang.

699
00:57:09,860 --> 00:57:13,400
Kaya pagpunta bumalik upang ayusin - oh, mayroong dalawang mga bagay na gusto kong ipakita. Okay.

700
00:57:13,400 --> 00:57:17,840
Pagpunta pagbukud-, makikita namin gawin ito mabilis.

701
00:57:17,840 --> 00:57:21,030
O paghahanap. -Uri-uriin? Sort. Oo.

702
00:57:21,030 --> 00:57:22,730
Pagpunta sa Beginnings ng-uuri.

703
00:57:22,730 --> 00:57:29,870
Gusto naming lumikha ng isang algorithm na uri ang array gamit ang anumang algorithm

704
00:57:29,870 --> 00:57:33,660
sa O ng n.

705
00:57:33,660 --> 00:57:40,860
Kaya paano ito posible? Ba ang sinuman anumang uri ng -

706
00:57:40,860 --> 00:57:44,300
Hinted ko bago sa -

707
00:57:44,300 --> 00:57:48,300
Kung hindi namin upang mapabuti ang mula n log n sa O ng n,

708
00:57:48,300 --> 00:57:51,450
napabuti namin ang ang aming algorithm oras-matalino,

709
00:57:51,450 --> 00:57:55,250
na nangangahulugan na kung ano ang kami pagpunta sa kailangan upang gawin upang gumawa ng up para sa?

710
00:57:55,250 --> 00:57:59,520
[Mag-aaral] Space. >> Oo. Kami ay pagpunta sa paggamit ng mas maraming espasyo.

711
00:57:59,520 --> 00:58:04,490
At hindi kahit lamang ng mas maraming espasyo, exponentially mas maraming espasyo.

712
00:58:04,490 --> 00:58:14,320
Kaya tingin ko ito uri ng algorithm ay palsipikado isang bagay, palsipikado polynom -

713
00:58:14,320 --> 00:58:18,980
palsipikado - hindi ko matandaan. Palsipikado isang bagay.

714
00:58:18,980 --> 00:58:22,210
Subalit dahil kailangan namin upang gamitin kaya magkano espasyo

715
00:58:22,210 --> 00:58:28,610
na ito ay matamo ngunit hindi makatotohanang.

716
00:58:28,610 --> 00:58:31,220
>> At kung paano namin makamit ito?

717
00:58:31,220 --> 00:58:36,810
Maaari naming makamit ang kung gina-garantiya namin na ang anumang partikular na elemento sa array

718
00:58:36,810 --> 00:58:39,600
ay sa ibaba sa isang tiyak na laki.

719
00:58:42,070 --> 00:58:44,500
Kaya hayaan lang sabihin na laki ay 200,

720
00:58:44,500 --> 00:58:48,130
anumang elemento sa isang array sa ibaba laki 200.

721
00:58:48,130 --> 00:58:51,080
At ito ay talagang napaka-makatotohanang.

722
00:58:51,080 --> 00:58:58,660
Maaari mong napaka madaling isang array na alam mo ang lahat ng nasa loob nito

723
00:58:58,660 --> 00:59:00,570
ay pagpunta sa mas mababa kaysa sa ilang bilang.

724
00:59:00,570 --> 00:59:07,400
Gusto kung mayroon kang ilang mga talagang napakalaking vector o isang bagay

725
00:59:07,400 --> 00:59:11,810
ngunit alam mo ang lahat ng pagpunta sa pagitan ng 0 at 5,

726
00:59:11,810 --> 00:59:14,790
ito makabuluhang mas mabilis na gawin ito.

727
00:59:14,790 --> 00:59:17,930
At ang bound sa anumang ng mga elemento ay 5,

728
00:59:17,930 --> 00:59:21,980
kaya ito bound, na kung gaano karaming memory ka pagpunta sa gumagamit.

729
00:59:21,980 --> 00:59:26,300
Kaya ang bound ay 200.

730
00:59:26,300 --> 00:59:32,960
Sa basal ay laging bound dahil may isang integer ay maaari lamang maging hanggang 4 na bilyong,

731
00:59:32,960 --> 00:59:40,600
ngunit hindi makatotohanang dahil nais naming gumagamit espasyo

732
00:59:40,600 --> 00:59:44,400
sa pagkakasunud-sunod ng 4 bilyong. Kaya na hindi makatotohanang.

733
00:59:44,400 --> 00:59:47,060
Ngunit dito makikita namin sabihin ang aming bound ay 200.

734
00:59:47,060 --> 00:59:59,570
Ang panlinlang upang gawin ito sa O ng n naming gumawa ng isa pang array na tinatawag na bilang ng laki bound.

735
00:59:59,570 --> 01:00:10,470
Sa aktwal, ito ay isang shortcut para sa - aktwal ko hindi alam kung kumalatong ito.

736
01:00:11,150 --> 01:00:15,330
Ngunit sa GCC sa pinakadulo hindi bababa sa - I'm ipagpalagay kumalatong ginagawa ito masyadong -

737
01:00:15,330 --> 01:00:18,180
ito ay lamang initialize ang buong array na 0s.

738
01:00:18,180 --> 01:00:25,320
Kaya kung hindi ko nais upang gawin iyon, pagkatapos maaari kong hiwalay para sa (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <bound; i + +) at bilang [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Kaya ngayon lahat ay nasimulan sa 0.

741
01:00:35,260 --> 01:00:39,570
Ako umulit sa paglipas ng aking array,

742
01:00:39,570 --> 01:00:51,920
at kung ano ako paggawa ay pagbibilang ako ang bilang ng bawat - Hayaan ang pumunta pababa dito.

743
01:00:51,920 --> 01:00:55,480
Mayroon kaming 4, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
Ano ako pagbibilang ay ang bilang ng mga pangyayari ng bawat isa sa mga elementong iyon.

745
01:01:00,010 --> 01:01:03,470
Natin ang aktwal na magdagdag ng ilang mas in dito gamit ang ilang mga umuulit.

746
01:01:03,470 --> 01:01:11,070
Kaya ang halaga na mayroon kami dito, ang halaga ng na pagpunta sa array [i].

747
01:01:11,070 --> 01:01:14,850
Kaya Val ay maaaring 4 o 8 o anumang.

748
01:01:14,850 --> 01:01:18,870
At ngayon ako pagbibilang kung gaano karaming ng halagang iyon Nakita ko na,

749
01:01:18,870 --> 01:01:21,230
kaya bilang [Val] + +;

750
01:01:21,230 --> 01:01:29,430
Pagkatapos ito ay tapos na, bilang ay pagpunta upang tumingin ng isang bagay tulad ng 0001.

751
01:01:29,430 --> 01:01:42,190
Natin gawin bilang [Val] - Bound + 1.

752
01:01:42,190 --> 01:01:48,230
>> Ngayon na lang sa account para sa ang katunayan na kami ay nagsisimula mula 0.

753
01:01:48,230 --> 01:01:50,850
Kaya kung 200 ay pagpunta sa aming pinakamalaking bilang,

754
01:01:50,850 --> 01:01:54,720
pagkatapos 0 sa 200 201 bagay.

755
01:01:54,720 --> 01:02:01,540
Kaya bilang, ito hitsura ng 00,001 dahil mayroon kaming isang 4.

756
01:02:01,540 --> 01:02:10,210
Pagkatapos ay magpapadala kami sa 0001 kung saan ipapakita namin magkaroon ng 1 sa ika-8 index ng bilang ng.

757
01:02:10,210 --> 01:02:14,560
Magkakaroon kami ng 2 sa ika-23 na index ng bilang ng.

758
01:02:14,560 --> 01:02:17,630
Magkakaroon kami ng 2 sa 42 index ng bilang ng.

759
01:02:17,630 --> 01:02:21,670
Upang maaari naming gamitin bilang.

760
01:02:34,270 --> 01:02:44,920
Kaya num_of_item = bilang ng [i].

761
01:02:44,920 --> 01:02:52,540
At kaya kung num_of_item ay 2, na nangangahulugan na gusto naming upang ipasok ang 2 ng bilang i

762
01:02:52,540 --> 01:02:55,290
sa aming pinagsunod-sunod array.

763
01:02:55,290 --> 01:03:02,000
Kaya kailangan namin upang subaybayan kung gaano kalayo namin sa array.

764
01:03:02,000 --> 01:03:05,470
Kaya index = 0.

765
01:03:05,470 --> 01:03:09,910
Array - kukunin ko na lang magsulat dito.

766
01:03:16,660 --> 01:03:18,020
Ibinibilang -

767
01:03:19,990 --> 01:03:28,580
array [index + +] = i;

768
01:03:28,580 --> 01:03:32,490
Ay na kung ano ang gusto kong? Tingin ko na kung ano ang gusto kong.

769
01:03:35,100 --> 01:03:38,290
Oo, ito mukhang mahusay. Okay.

770
01:03:38,290 --> 01:03:43,050
Kaya ang lahat maunawaan kung ano ang layunin ng aking mga bilang ng array ay?

771
01:03:43,050 --> 01:03:48,140
Pagbibilang Ito ay ang bilang ng mga pangyayari ng bawat isa sa mga numerong ito.

772
01:03:48,140 --> 01:03:51,780
Pagkatapos ako iterating sa paglipas na bilang ng array,

773
01:03:51,780 --> 01:03:57,190
at ith posisyon sa array bilang

774
01:03:57,190 --> 01:04:01,930
ay ang bilang ng mga i kung na dapat lumitaw sa aking pinagsunod-sunod array.

775
01:04:01,930 --> 01:04:06,840
Iyon ang dahilan kung bakit ang bilang ng 4 ay magiging 1

776
01:04:06,840 --> 01:04:11,840
at bilang na 8 ay pagpunta sa 1, ang mga bilang na 23 ay pagpunta sa 2.

777
01:04:11,840 --> 01:04:16,900
Kaya na kung gaano karami sa mga ito ang gusto ko upang ipasok sa aking pinagsunod-sunod array.

778
01:04:16,900 --> 01:04:19,200
Pagkatapos ko lang gawin iyon.

779
01:04:19,200 --> 01:04:28,960
Ako pagpasok num_of_item i sa aking pinagsunod-sunod array.

780
01:04:28,960 --> 01:04:31,670
>> Mga tanong?

781
01:04:32,460 --> 01:04:43,100
At kaya muli, ito ay linear oras dahil lamang namin ay iterating sa paglipas ng ito sabay-sabay,

782
01:04:43,100 --> 01:04:47,470
ngunit ito rin linear sa kung ano ang bilang na ito ay mangyayari upang maging,

783
01:04:47,470 --> 01:04:50,730
at kaya mabigat ay depende sa kung ano ang iyong bound.

784
01:04:50,730 --> 01:04:53,290
Na may isang bound ng 200, na hindi na masamang.

785
01:04:53,290 --> 01:04:58,330
Kung ang iyong bound ay pagpunta sa 10,000, pagkatapos na ang isang maliit na mas masahol pa,

786
01:04:58,330 --> 01:05:01,360
ngunit kung ang iyong bound ay pagpunta sa may 4 na bilyong, na ganap na hindi makatotohanang

787
01:05:01,360 --> 01:05:07,720
at ang array na ito ng laki 4 bilyong, na hindi makatotohanang.

788
01:05:07,720 --> 01:05:10,860
Kaya na na. Mga tanong?

789
01:05:10,860 --> 01:05:13,270
[Hindi marinig na mag-aaral tugon] >> Okay.

790
01:05:13,270 --> 01:05:15,710
Natanto ko isa pang bagay kapag kami ay pagpunta sa pamamagitan ng.

791
01:05:17,980 --> 01:05:23,720
Tingin ko ang problema ay sa Lucas at marahil bawat solong nasaksihan namin.

792
01:05:23,720 --> 01:05:26,330
Ako ganap na nakalimutan.

793
01:05:26,330 --> 01:05:31,040
Ang tanging bagay na Nais kong magkomento sa ay na kapag ikaw ay pagharap sa mga bagay tulad ng mga indeks,

794
01:05:31,040 --> 01:05:38,320
hindi mo talaga makikita ito kapag sumusulat ka ng para sa loop,

795
01:05:38,320 --> 01:05:41,120
ngunit technically, sa tuwing ikaw ay pagharap sa mga indeks ng,

796
01:05:41,120 --> 01:05:45,950
dapat mong medyo magkano palaging haharapin ang mga unsigned integer.

797
01:05:45,950 --> 01:05:53,850
Ang dahilan para sa ay kapag ikaw ay pagharap sa sign integer,

798
01:05:53,850 --> 01:05:56,090
kaya kung mayroon kang 2 sign integer at mong idagdag ang mga ito nang sama-sama

799
01:05:56,090 --> 01:06:00,640
at magtapos sila masyadong malaki, pagkatapos mo magtapos sa isang negatibong numero.

800
01:06:00,640 --> 01:06:03,410
Kaya na kung ano ang integer overflow.

801
01:06:03,410 --> 01:06:10,500
>> Kung idagdag ko ang 2 bilyong at 1 bilyong, ako magtapos sa negatibong 1 bilyon.

802
01:06:10,500 --> 01:06:15,480
Iyon ay kung paano gumagana ang mga integer sa mga computer.

803
01:06:15,480 --> 01:06:17,510
Kaya ang problema sa gamit -

804
01:06:17,510 --> 01:06:23,500
Iyon ay pinong maliban kung mababa ang mangyayari sa 2 bilyong at mangyayari hanggang 1 bilyon,

805
01:06:23,500 --> 01:06:27,120
pagkatapos ito ay pagpunta sa negatibong 1 bilyon at pagkatapos kami ay pagpunta sa hatiin sa pamamagitan ng 2

806
01:06:27,120 --> 01:06:29,730
at nagtatapos sa negatibong 500 milyong.

807
01:06:29,730 --> 01:06:33,760
Kaya ito ay lamang ng isang isyu kung mangyari na naghahanap sa pamamagitan ng isang array

808
01:06:33,760 --> 01:06:38,070
ng mga bilyun-bilyong ng mga bagay.

809
01:06:38,070 --> 01:06:44,050
Ngunit kung mababa + up ang mangyayari sa pag-apaw, pagkatapos na ang isang problema.

810
01:06:44,050 --> 01:06:47,750
Lalong madaling panahon na ginawa namin ang mga ito unsigned, pagkatapos 2 bilyong plus 1 bilyon ay 3 bilyong.

811
01:06:47,750 --> 01:06:51,960
3 bilyong na hinati sa pamamagitan ng 2 ay 1.5 bilyong.

812
01:06:51,960 --> 01:06:55,670
Ito sa lalong madaling sila unsigned, ang lahat ng bagay ay perpekto.

813
01:06:55,670 --> 01:06:59,900
At kaya na rin ng isyu kapag sumusulat ka sa iyong para sa loop,

814
01:06:59,900 --> 01:07:03,940
at aktwal na, marahil ito ginagawa ito awtomatiko.

815
01:07:09,130 --> 01:07:12,330
Ito ay aktwal na lamang sumigaw sa iyo.

816
01:07:12,330 --> 01:07:21,610
Kaya kung ang bilang na ito ay masyadong malaki upang maging sa isang integer lamang ngunit magkasya sa isang wala pang kontratang integer,

817
01:07:21,610 --> 01:07:24,970
sumigaw sa iyo, kaya na ang dahilan kung bakit hindi mo talaga tumatakbo sa isyu.

818
01:07:29,150 --> 01:07:34,820
Maaari mong makita na ang isang index ay hindi kailanman negatibo,

819
01:07:34,820 --> 01:07:39,220
at kaya kapag ka iterating higit sa isang array,

820
01:07:39,220 --> 01:07:43,970
maaari mong halos palaging sabihin unsigned int i, ngunit hindi mo talagang may sa.

821
01:07:43,970 --> 01:07:47,110
Mga bagay ay gumagana medyo mas lamang pati na rin.

822
01:07:48,740 --> 01:07:50,090
Okay. [Whispers] Anong oras na?

823
01:07:50,090 --> 01:07:54,020
Ang huling bagay na Nais kong upang ipakita - at kukunin ko na lang gawin ito talagang mabilis.

824
01:07:54,020 --> 01:08:03,190
Alam mo kung paano # namin na tukuyin upang maaari naming # tukuyin ang MAX bilang 5 o isang bagay?

825
01:08:03,190 --> 01:08:05,940
Natin hindi gawin ng MAX. # Tukuyin bound ng 200. Kung ano ang ginawa namin bago.

826
01:08:05,940 --> 01:08:10,380
Na tumutukoy sa isang pare-pareho, na kung saan ay lamang ang pagpunta sa kopyahin at ilagay

827
01:08:10,380 --> 01:08:13,010
saanman mangyayari namin na magsulat bound.

828
01:08:13,010 --> 01:08:18,189
>> Upang maaari naming aktwal na makagawa ng higit pa sa # tumutukoy.

829
01:08:18,189 --> 01:08:21,170
Maaari naming # tukuyin ang mga function.

830
01:08:21,170 --> 01:08:23,410
Hindi ito talagang pag-andar, ngunit kami tatawag sa kanila function.

831
01:08:23,410 --> 01:08:36,000
Ang isang halimbawa ay ang isang bagay tulad ng MAX (x, y) ay tinukoy bilang (x <y y:? X). Okay.

832
01:08:36,000 --> 01:08:40,660
Kaya dapat kang masanay sa tatluhan operator syntax,

833
01:08:40,660 --> 01:08:49,029
ngunit x mas mababa sa y? Bumalik y, tao bumalik x.

834
01:08:49,029 --> 01:08:54,390
Sa gayon maaari mong makita na maaari mong gawin ang isang hiwalay na function,

835
01:08:54,390 --> 01:09:01,399
at ang function ay maaaring tulad ng bool MAX ay tumatagal ng 2 argumento, bumalik ito.

836
01:09:01,399 --> 01:09:08,340
Ito ay isa sa mga pinaka-karaniwang mga nakikita ko ginawa tulad nito. Tinatawag namin ang mga ito macros.

837
01:09:08,340 --> 01:09:11,790
Ito ay isang macro.

838
01:09:11,790 --> 01:09:15,859
Ito ay ang syntax para dito.

839
01:09:15,859 --> 01:09:18,740
Maaari kang magsulat ng isang macro upang gawin ang anumang gusto mong.

840
01:09:18,740 --> 01:09:22,649
Ka madalas makita ang mga macros para sa pag-debug ng printfs at bagay-bagay.

841
01:09:22,649 --> 01:09:29,410
Kaya isang uri ng printf, may mga espesyal na mga constants sa C tulad ng salungguhit LINE salungguhit,

842
01:09:29,410 --> 01:09:31,710
2 underscore LINE salungguhit,

843
01:09:31,710 --> 01:09:37,550
at mayroon ding tingin ko 2 underscore FUNC. Na maaaring maging ito. Isang bagay tulad na.

844
01:09:37,550 --> 01:09:40,880
Mga bagay ay pinalitan ng ang pangalan ng function na

845
01:09:40,880 --> 01:09:42,930
o ang bilang ng linya na ikaw ay nasa.

846
01:09:42,930 --> 01:09:48,630
Madalas, isulat mo ang pag-debug ng mga printfs na pababa dito maaari kong magsulat lamang

847
01:09:48,630 --> 01:09:54,260
DEBUG at ito ay i-print ang linya bilang at pag-andar na mangyari ko sa

848
01:09:54,260 --> 01:09:57,020
Nakatagpo na DEBUG statement.

849
01:09:57,020 --> 01:09:59,550
At maaari mo ring i-print ang iba pang mga bagay.

850
01:09:59,550 --> 01:10:05,990
Kaya ang isang bagay na dapat mong panoorin para sa kung mangyayari kong # tukuyin ang DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
bilang isang bagay tulad ng 2 * y at 2 * x.

852
01:10:11,380 --> 01:10:14,310
Kaya para sa anumang dahilan, mangyari ka upang gawin iyon ng maraming.

853
01:10:14,310 --> 01:10:16,650
Kaya gawin itong isang macro.

854
01:10:16,650 --> 01:10:18,680
Ito ay talagang nasira.

855
01:10:18,680 --> 01:10:23,050
Gusto ko tawagan ang mga ito sa pamamagitan ng paggawa ng isang bagay tulad ng DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Kaya ano ang dapat ibabalik?

857
01:10:28,840 --> 01:10:30,580
[Mag-aaral] 12.

858
01:10:30,580 --> 01:10:34,800
Oo, 12 dapat ibabalik, at 12 ay ibinalik.

859
01:10:34,800 --> 01:10:43,350
3 ay makakakuha ng papalitan para sa x, 6 ay makakakuha ng papalitan para sa y, at bumalik kami ng 2 * 6, na kung saan ay 12.

860
01:10:43,350 --> 01:10:47,710
Ngayon kung ano ang tungkol dito? Ano ang dapat na ibinalik?

861
01:10:47,710 --> 01:10:50,330
[Mag-aaral] 14. >> May perpektong, 14.

862
01:10:50,330 --> 01:10:55,290
Ang isyu ay kung paano hash tumutukoy sa trabaho, tandaan na ito ay isang literal na kopyahin at i-paste ang

863
01:10:55,290 --> 01:11:00,160
ng medyo magkano ang lahat, kaya kung ano ito ay pagpunta sa kahulugan bilang

864
01:11:00,160 --> 01:11:11,270
3 mas mababa sa 1 plus 6, 2 beses 1 plus 6, 2 beses 3.

865
01:11:11,270 --> 01:11:19,780
>> Kaya para sa kadahilanang ito halos palaging I-wrap ang lahat sa panaklong.

866
01:11:22,180 --> 01:11:25,050
Anumang variable halos palaging pambalot ng naka-panaklong.

867
01:11:25,050 --> 01:11:29,570
May mga kaso kung saan hindi mo na kailangang, tulad ng alam ko na hindi ko kailangan upang gawin iyon dito

868
01:11:29,570 --> 01:11:32,110
dahil mas mababa ay medyo mas laging lamang sa trabaho,

869
01:11:32,110 --> 01:11:34,330
bagaman na hindi maaaring kahit na totoo.

870
01:11:34,330 --> 01:11:41,870
Kung mayroong isang bagay na katawa-tawa tulad ng DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
pagkatapos na pagpunta upang pinalitan ng 3 mas mababa sa 1 katumbas ng katumbas ng 2,

872
01:11:49,760 --> 01:11:53,460
at kaya pagkatapos ito ay pagpunta sa gawin 3 mas mababa sa 1, ay na katumbas 2,

873
01:11:53,460 --> 01:11:55,620
na hindi kung ano ang gusto namin.

874
01:11:55,620 --> 01:12:00,730
Kaya upang maiwasan ang anumang mga problema sa operator mangingibabaw,

875
01:12:00,730 --> 01:12:02,870
laging I-wrap sa panaklong.

876
01:12:03,290 --> 01:12:07,700
Okay. At na, 5:30.

877
01:12:08,140 --> 01:12:12,470
Kung mayroon kang anumang mga katanungan sa pset, ipaalam sa amin.

878
01:12:12,470 --> 01:12:18,010
Dapat itong maging masaya, at ang Hacker edition din mas makatotohanang

879
01:12:18,010 --> 01:12:22,980
kaysa sa Hacker edisyon ng nakaraang taon, kaya inaasahan namin na ng maraming iyo na subukan ito.

880
01:12:22,980 --> 01:12:26,460
Ng nakaraang taon ay masyadong napakalaki.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]