1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Sekcio 3 - Pli Vasta]

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

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

4
00:00:07,310 --> 00:00:12,700
>> Do la unua demando estas strange worded.

5
00:00:12,700 --> 00:00:17,480
GDB permesas "elpurigi" programo, sed, pli specife, kion signifas tio lasu vin fari?

6
00:00:17,480 --> 00:00:22,590
Mi respondos, ke unu, kaj mi ne scias kio precize atendis,

7
00:00:22,590 --> 00:00:27,910
tial mi konjektas estas iu laŭ la linioj de ĝi permesas paŝo post paŝo

8
00:00:27,910 --> 00:00:31,540
trairu la programo, interagi kun ĝi, ŝanĝo variabloj, faras cxion cxi tion -

9
00:00:31,540 --> 00:00:34,270
esence tute kontroli ekzekuto de programo

10
00:00:34,270 --> 00:00:38,410
kaj inspekti ajna parto de la ekzekuto de la programo.

11
00:00:38,410 --> 00:00:43,030
Do tiuj karakterizaĵoj lasu vin elpurigi aĵoj.

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

13
00:00:44,830 --> 00:00:50,520
Kial duuma serĉo postulas ke tabelo estos ordo?

14
00:00:50,520 --> 00:00:53,360
Kiu volas respondi?

15
00:00:56,120 --> 00:01:00,070
[Studento] Ĉar ĝi ne funkcias se ĝi ne ordo. >> Jes. [Ridado]

16
00:01:00,070 --> 00:01:04,910
Se ĝi ne ordo, tiam ĝi estas neebla al fendi ĝin en duono

17
00:01:04,910 --> 00:01:07,850
kaj scias, ke ĉiu al la maldekstra estas malpli kaj ĉiu al la dekstra

18
00:01:07,850 --> 00:01:10,490
estas pli granda ol la meza valoro.

19
00:01:10,490 --> 00:01:12,790
Do devas esti ordo.

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

21
00:01:14,170 --> 00:01:17,570
Kial bobelo varo en ho de n kvadratoj?

22
00:01:17,570 --> 00:01:23,230
Ĉu iu unua volas doni tre rapida alta nivelo superrigardon pri kio bobelo varo estas?

23
00:01:25,950 --> 00:01:33,020
[Studento] Vi esence iri tra ĉiu elemento kaj vi kontrolu la unuaj kelkaj elementoj.

24
00:01:33,020 --> 00:01:37,150
Se ili estas el kie vi interŝanĝi ilin, tiam vi kontrolu la venontaj elementoj kaj tiel plu.

25
00:01:37,150 --> 00:01:40,770
Kiam vi atingas la fino, tiam vi scias ke la plej granda ero metiĝas ĉe la fino,

26
00:01:40,770 --> 00:01:42,750
tiel vi ignoras tiu tiam vi daŭre iras tra,

27
00:01:42,750 --> 00:01:48,490
kaj ĉiufoje vi havas por kontroli unu malpli ero ĝis vi ne faru ŝanĝojn. >> Jes.

28
00:01:48,490 --> 00:01:58,470
Ĝi estas nomita bobelo speco ĉar se vi klaki la tabelo sur lia flanko tuj kiam estas supren kaj malsupren, vertikala,

29
00:01:58,470 --> 00:02:03,100
tiam la grandaj valoroj enprofundigos al la fundo kaj la malgrandaj valoroj volo bobelo ĝis la supro.

30
00:02:03,100 --> 00:02:05,210
Tiel estas kiel ĝi alvenis lia nomo.

31
00:02:05,210 --> 00:02:08,220
Kaj jes, vi simple iru tra.

32
00:02:08,220 --> 00:02:11,190
Vi daŭre iras tra la tabelo, interŝanĝi la granda valoro

33
00:02:11,190 --> 00:02:14,040
atingi la plej grandan valorojn al la fundo.

34
00:02:14,040 --> 00:02:17,500
>> Kial ho de n kvadratoj?

35
00:02:18,690 --> 00:02:24,620
Unue, ĉu iu volas diri kial ĝi estas ho de n kvadratoj?

36
00:02:24,620 --> 00:02:28,760
[Studento] Ĉar por ĉiu run iras n fojojn.

37
00:02:28,760 --> 00:02:32,100
Vi povas nur esti certa, ke vi prenis la plej grandan elementon tuta vojo suben,

38
00:02:32,100 --> 00:02:35,230
tiam vi devas ripeti ke dum tiom da elementoj. >> Jes.

39
00:02:35,230 --> 00:02:41,800
Do memoru, kion granda a signifas kaj kion granda omega rimedoj.

40
00:02:41,800 --> 00:02:50,560
La granda O estas kiel la supera baro sur kiel malrapida ĝi povas efektive kuri.

41
00:02:50,560 --> 00:02:58,990
Do dirante ke estas ho de n kvadratoj, ne estas ho de n alie ĝi povus funkcii

42
00:02:58,990 --> 00:03:02,640
en lineara tempo, sed ĝi estas O de n potenco de

43
00:03:02,640 --> 00:03:06,390
ĉar ĝi estas barita per O de n potenco de.

44
00:03:06,390 --> 00:03:12,300
Se ĝi estas barita per O de n kvadratoj, tiam ĝi estas barita ankaŭ per n potenco de.

45
00:03:12,300 --> 00:03:20,280
Do ĝi estas n kvadratoj, kaj en la absoluta plej malbona kazo ĝi ne povas fari pli bone ol n kvadratoj,

46
00:03:20,280 --> 00:03:22,830
tial ĝi estas O de n kvadratoj.

47
00:03:22,830 --> 00:03:31,200
Do por vidi malpezan math ĉe kiel eliras esti n kvadratoj,

48
00:03:31,200 --> 00:03:40,530
se ni havas kvin aĵojn en nia listo, la unua fojo kiom svopoj ni povus potenciale bezonos fari

49
00:03:40,530 --> 00:03:47,170
por atingi tion? Ni fakte ĝuste -

50
00:03:47,170 --> 00:03:52,040
Kiom da svopoj ni tuj devos fari en la unua kuro de bobelo speco tra la tabelo?

51
00:03:52,040 --> 00:03:53,540
[Studento] n - 1. >> Jes.

52
00:03:53,540 --> 00:03:58,340
>> Se estas 5 eroj, ni tuj bezonos fari n - 1.

53
00:03:58,340 --> 00:04:01,100
Tiam sur la dua kiom svopoj ni tuj devos fari?

54
00:04:01,100 --> 00:04:03,440
[Studento] n - 2. >> Jes.

55
00:04:03,440 --> 00:04:11,640
Kaj la tria tuj esti n - 3, kaj tiam por oportuneco Mi skribos la lastaj du

56
00:04:11,640 --> 00:04:15,270
kiel do ni tuj bezonos fari 2 svopoj kaj 1 interŝanĝa.

57
00:04:15,270 --> 00:04:19,899
Mi supozas ke la lasta povas aŭ ne vere bezonas okazi.

58
00:04:19,899 --> 00:04:22,820
Ĉu tio estas interŝanĝa? Mi ne scias.

59
00:04:22,820 --> 00:04:26,490
Do tio estas la tuta kvanto de svopoj aŭ almenaŭ komparoj vi devas fari.

60
00:04:26,490 --> 00:04:29,910
Eĉ se vi ne interŝanĝas, vi ankoraŭ bezonas kompari la valoroj.

61
00:04:29,910 --> 00:04:33,910
Do estas n - 1 komparoj en la unua kuro tra la tabelo.

62
00:04:33,910 --> 00:04:42,050
Se vi reordigi tion, ni vere faras ses aferoj estas tiel aĵoj pilo supren bele,

63
00:04:42,050 --> 00:04:44,790
kaj tiam Mi faros 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Do ĝuste reordigante tiuj sumoj, ni volas vidi kiom da komparoj ni faras

65
00:04:49,910 --> 00:04:52,700
en la tuta algoritmo.

66
00:04:52,700 --> 00:04:56,550
Do, se ni alportos tiuj infanoj cxi tie,

67
00:04:56,550 --> 00:05:07,470
tiam ni ankoraŭ nur sumanta tamen multaj komparoj estis.

68
00:05:07,470 --> 00:05:13,280
Sed se ni resumi tiujn kaj ni resumi tiujn kaj ni resumi tiujn,

69
00:05:13,280 --> 00:05:18,130
ĝi estas ankoraŭ la sama problemo. Ni nur resumi tiujn apartajn grupojn.

70
00:05:18,130 --> 00:05:22,400
>> Do nun ni sumanta 3 n-aj jaroj. Ne nur 3 n-aj jaroj.

71
00:05:22,400 --> 00:05:27,650
Ĝi estas ĉiam tuj estos n / 2 n-aj jaroj.

72
00:05:27,650 --> 00:05:29,430
Do jen ni hazarde havas 6.

73
00:05:29,430 --> 00:05:34,830
Se ni havis 10 aĵoj, tiam ni povus fari ĉi grupo por 5 malsamaj paroj de aĵoj

74
00:05:34,830 --> 00:05:37,180
kaj fini kun n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Do vi ĉiam ricevos n / 2 n estas, kaj tial ĉi ni jot ĝin al n kvadrataj / 2.

76
00:05:45,840 --> 00:05:48,890
Kaj tial, kvankam ĝi estas la faktoro de duono, kio okazas veni en

77
00:05:48,890 --> 00:05:54,190
pro la fakto ke per ĉiu ripeto super la tabelo oni komparas 1 malpli

78
00:05:54,190 --> 00:05:58,040
por ke estas kiel ni preni la super 2, sed estas ankoraŭ n kvadratoj.

79
00:05:58,040 --> 00:06:01,650
Ni ne zorgas pri la konstanta faktoro de duona.

80
00:06:01,650 --> 00:06:07,760
Do multan granda a stuff kiel ĉi dependas nur speco de fari ĉi speco de Y,

81
00:06:07,760 --> 00:06:12,260
fari aritmetikajn sumoj kaj geometria serio stuff,

82
00:06:12,260 --> 00:06:17,750
sed plej multaj el ili en ĉi tiu kurso estas bela simpla.

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

84
00:06:19,290 --> 00:06:24,430
Kial inserción varo en omega de n? Kion omega signifas?

85
00:06:24,430 --> 00:06:27,730
[Du studentoj parolis samtempe - nekomprenebla] >> Jes.

86
00:06:27,730 --> 00:06:30,630
Omega vi povas pensi pri kiel la suba baro.

87
00:06:30,630 --> 00:06:36,550
>> Do ne gravas kiom efika vian inserción speco algoritmo estas,

88
00:06:36,550 --> 00:06:41,810
sendepende de la listo ke tio pasis en, ĝi ĉiam devas kompari almenaŭ n aĵoj

89
00:06:41,810 --> 00:06:44,620
aŭ ĝi devas persisti super n aĵoj.

90
00:06:44,620 --> 00:06:47,280
Kial estas tio?

91
00:06:47,280 --> 00:06:51,190
[Studento] Ĉar se la listo estas jam ordo, tiam tra la unua ripeto

92
00:06:51,190 --> 00:06:54,080
vi nur povas garantii ke la unua elemento estas la malplej,

93
00:06:54,080 --> 00:06:56,490
kaj la dua iteracio vi nur povas garantii la unua du estas

94
00:06:56,490 --> 00:07:00,010
ĉar vi ne scias, ke la resto de la listo estas ordigita. >> Jes.

95
00:07:00,010 --> 00:07:08,910
Se pasas en tute ordo listo, almenaŭ vi devas iri super ĉiuj elementoj

96
00:07:08,910 --> 00:07:12,180
vidi ke nenio bezonas al esti movita ĉirkaŭ.

97
00:07:12,180 --> 00:07:14,720
Do pasas super la listo kaj dirante oh, tio estas jam ordo,

98
00:07:14,720 --> 00:07:18,240
estas neebla por vi scii ĝi estas ordo ĝis vi kontrolu ĉiun elementon

99
00:07:18,240 --> 00:07:20,660
vidi ke ili estas en ordo ordo.

100
00:07:20,660 --> 00:07:25,290
Do la suba baro sur inserción varo estas omega de n.

101
00:07:25,290 --> 00:07:28,210
Kio la plej malbona kazo rula tempo de merge varo,

102
00:07:28,210 --> 00:07:31,390
plej malbona kazo esti granda a denove?

103
00:07:31,390 --> 00:07:37,660
Do, en la plej malbona kazo scenejo, kiom tio merge speco kuri?

104
00:07:42,170 --> 00:07:43,690
[Studento] N log n. >> Jes.

105
00:07:43,690 --> 00:07:49,990
La plej rapida ĝenerala klasifiko algoritmoj estas n logo n. Vi ne povas fari pli bone.

106
00:07:51,930 --> 00:07:55,130
>> Ekzistas specialaj kazoj, kaj se ni havas tempon hodiaŭ - sed ni verŝajne won't -

107
00:07:55,130 --> 00:07:59,330
ni povis vidi kiu faras pli bone ol n logo n.

108
00:07:59,330 --> 00:08:04,050
Sed en la ĝenerala kazo, vi ne povas fari pli bone ol n logo n.

109
00:08:04,050 --> 00:08:09,680
Kaj kunfandi speco hazarde estas tiu, kiun vi devas scii por ĉi tiu kurso ke estas n logo n.

110
00:08:09,680 --> 00:08:13,260
Kaj tiel ni vere povas efektivigi ke hodiaŭ.

111
00:08:13,260 --> 00:08:18,070
Kaj fine, en ne pli ol tri frazoj, kiel faras elekton speco laboro?

112
00:08:18,070 --> 00:08:20,370
Ĉu iu volas respondi, kaj mi rakontos viaj frazoj

113
00:08:20,370 --> 00:08:22,390
ĉar se vi transiru 3 -

114
00:08:25,530 --> 00:08:28,330
Ĉu iu memoras selektado speco?

115
00:08:31,280 --> 00:08:37,809
Selektado varo estas kutime bela facile memori nur de la nomo.

116
00:08:37,809 --> 00:08:45,350
Vi nur persisti super la tabelo, trovi kion ajn la plej granda valoro estas aŭ malgranda -

117
00:08:45,350 --> 00:08:47,290
kion ajn celo vi ordigi in

118
00:08:47,290 --> 00:08:50,750
Do diru ni ordigi de malgranda al la plej granda.

119
00:08:50,750 --> 00:08:55,250
Vi persisti super la tabelo, serĉante ajn la minimuma elemento estas,

120
00:08:55,250 --> 00:08:59,750
elektu ĝin, kaj tiam nur interŝanĝi ĝin kio ajn en la unua loko.

121
00:08:59,750 --> 00:09:04,090
Kaj poste sur la dua pasas super la tabelo, serĉi la minimuma ero denove,

122
00:09:04,090 --> 00:09:07,490
elektu ĝin, kaj tiam interŝanĝi ĝin kun kio estas en la dua pozicio.

123
00:09:07,490 --> 00:09:10,650
Do ni estas nur pluki kaj elektante la minimuma valoroj

124
00:09:10,650 --> 00:09:16,050
kaj enmeto ilin en la fronto de la tabelo ĝis estas ordo.

125
00:09:19,210 --> 00:09:21,560
Demandojn sur tio?

126
00:09:21,560 --> 00:09:25,710
>> Tiuj neeviteble aperas en la formoj vi devas plenigi kiam vi submetis la pset.

127
00:09:29,010 --> 00:09:32,360
Tiuj estas esence la respondojn al tiuj.

128
00:09:32,360 --> 00:09:34,230
Konsentite, tiel nun kodigo problemojn.

129
00:09:34,230 --> 00:09:40,140
Mi jam sendis pli ol retpoŝto - Ĉu iu ne havas tiun retmesaĝon? Okay.

130
00:09:40,140 --> 00:09:46,630
Mi jam sendis pli ol retpoŝto la spaco kiu ni tuj estos uzante,

131
00:09:46,630 --> 00:09:52,120
kaj se vi klakas sur mia nomo - do mi kredas ke mi esti en la fundo

132
00:09:52,120 --> 00:09:57,170
ĉar el la malantaŭen r - sed se vi klakas sur mia nomo vi vidos 2 revizioj.

133
00:09:57,170 --> 00:10:02,650
Revizio 1 tuj estos mi jam kopiis kaj pasted la kodon en Spacetoj

134
00:10:02,650 --> 00:10:06,900
por la serĉo afero vi tuj devos apliki.

135
00:10:06,900 --> 00:10:10,540
Kaj redaktoj 2 estos la varo kiu ni implemento post tio.

136
00:10:10,540 --> 00:10:15,770
Do vi povas klaki sur mia Revizio 1 kaj labori de tie.

137
00:10:17,350 --> 00:10:22,060
Kaj nun ni volas apliki duuma serĉo.

138
00:10:22,060 --> 00:10:26,470
>> Ĉu iu volas nur doni _pseudocode_ altnivela ekspliko

139
00:10:26,470 --> 00:10:31,440
de kio ni tuj devas fari por serĉo? Yeah.

140
00:10:31,440 --> 00:10:36,170
[Studento] Vi nur preni la mezo de la tabelo kaj vidu se kion vi serĉas

141
00:10:36,170 --> 00:10:38,650
estas malpli ol tiu aŭ pli ol tio.

142
00:10:38,650 --> 00:10:41,080
Kaj se ĝi estas malpli, vi iras al la duono jen malpli,

143
00:10:41,080 --> 00:10:44,750
kaj se ĝi estas pli, iru al la duono kiu estas pli kaj vi ripetas ke ĝis vi simple akiri unu afero.

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

145
00:10:46,570 --> 00:10:51,320
Rimarku ke nia nombroj tabelo jam ordo,

146
00:10:51,320 --> 00:10:57,190
kaj por ke signifas, ke ni povas utiligi tiun kaj ni povus unue kontrolu,

147
00:10:57,190 --> 00:11:00,390
estas bone, Mi serĉas la numeron 50.

148
00:11:00,390 --> 00:11:03,720
Do mi povas iri al la mezo.

149
00:11:03,720 --> 00:11:07,380
Mezo estas malfacile difini kiam estas para kvanto de aĵoj,

150
00:11:07,380 --> 00:11:10,820
sed ni nur diros ni ĉiam detranĉi al la mezo.

151
00:11:10,820 --> 00:11:14,420
Do jen ni havas 8, do la mezo estus 16.

152
00:11:14,420 --> 00:11:17,330
Mi serĉas 50, do 50 estas pli granda ol 16.

153
00:11:17,330 --> 00:11:21,310
Do nun mi povas baze trakti mian tabelo kiel tiuj elementoj.

154
00:11:21,310 --> 00:11:23,450
Mi povas forĵeti ĉion de 16 pli.

155
00:11:23,450 --> 00:11:27,440
Nun mia tabelo estas nur tiuj 4 elementoj, kaj mi ripetas.

156
00:11:27,440 --> 00:11:31,910
Tial mi volas trovi la mezo denove, kio tuj estos 42.

157
00:11:31,910 --> 00:11:34,730
42 estas malpli ol 50, do mi povas forĵeti tiujn du elementoj.

158
00:11:34,730 --> 00:11:36,890
Ĉi tio estas mia cetera tabelo.

159
00:11:36,890 --> 00:11:38,430
Mi iros por trovi la mezo denove.

160
00:11:38,430 --> 00:11:42,100
Mi supozas 50 estis malbona ekzemplo ĉar mi ĉiam ĵetante sin aĵojn al la maldekstra,

161
00:11:42,100 --> 00:11:48,280
sed por la sama mezuro, se Mi serĉas ion

162
00:11:48,280 --> 00:11:52,100
kaj estas malpli ol la elemento Mi nune rigardas,

163
00:11:52,100 --> 00:11:55,080
tiam Mi iros forĵeti ĉion por la rajto.

164
00:11:55,080 --> 00:11:58,150
Do nun ni devas apliki tion.

165
00:11:58,150 --> 00:12:02,310
Rimarku ke ni bezonas por pasi de grandeco.

166
00:12:02,310 --> 00:12:06,730
Ni povas ankaŭ ne bezonas malmola kodo grandeco.

167
00:12:06,730 --> 00:12:11,640
Do, se ni liveri de tiu # difini -

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

169
00:12:21,430 --> 00:12:27,180
Kiel mi povas bele elkompreni kiel la grandeco de la nombroj tabelo aktuale estas?

170
00:12:27,180 --> 00:12:30,950
>> Kiom da elementoj estas en la numeroj tabelo?

171
00:12:30,950 --> 00:12:33,630
[Studento] Nombroj, krampoj,. Longo?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Tio ne ekzistas en C.

173
00:12:36,600 --> 00:12:38,580
Bezonas. Longa.

174
00:12:38,580 --> 00:12:42,010
Arrays ne havas propraĵoj, do ne estas longo propraĵo de tabeloj

175
00:12:42,010 --> 00:12:45,650
ke estos ĝuste doni al vi tamen longe okazas esti.

176
00:12:48,180 --> 00:12:51,620
[Studento] Vidu kiom memoro estas kaj dividi per kiom - >> Jes.

177
00:12:51,620 --> 00:12:55,810
Do kiel ni povas vidi kiom da memoro ĝi havas? >> [Studento] sizeof. >> Jes, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof estas la operatoro ke tuj revenos la grandeco de la nombroj tabelo.

179
00:13:01,680 --> 00:13:10,060
Kaj tiu tuj estos tamen multaj entjeroj estas fojoj la grandeco de entjero

180
00:13:10,060 --> 00:13:14,050
ĉar tio estas kiel multe memoro ĝi estas efektive prenas tion.

181
00:13:14,050 --> 00:13:17,630
Do se mi volas ke la nombro de aĵoj en la tabelo,

182
00:13:17,630 --> 00:13:20,560
tiam mi tuj volas dividi per la grandeco de entjero.

183
00:13:22,820 --> 00:13:26,010
Okay. Do kiu lasas min pasi en grandeco tie.

184
00:13:26,010 --> 00:13:29,430
Kial mi bezonas por pasi de grandeco ajn?

185
00:13:29,430 --> 00:13:38,570
Kial mi ne nur faru ĉi tien int grandeco = sizeof (fojnamaso) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Kial ĉi tio ne funkcias?

187
00:13:41,490 --> 00:13:44,470
[Studento] Ne estas malloka variablo.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack ekzistas kaj ni pasante en nombroj kiel fojnamaso,

189
00:13:51,540 --> 00:13:54,700
kaj jen estas ia prefiguración de kio estas venonta. Yeah.

190
00:13:54,700 --> 00:14:00,170
[Studento] Haystack estas nur la referenco al ĝi, do ĝi revenus kiom granda ke referenco estas.

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

192
00:14:02,150 --> 00:14:09,000
Mi dubas en prelego, kiun vi vidis la pilo tamen vere, ĉu ne?

193
00:14:09,000 --> 00:14:11,270
Ni ĵus parolis pri ĝi.

194
00:14:11,270 --> 00:14:16,090
Do la pilo estas kie ĉiuj viaj variabloj tuj estos stokitaj.

195
00:14:16,090 --> 00:14:19,960
>> Neniu memoro ke tio destinis por lokaj variabloj tuj en la pilo,

196
00:14:19,960 --> 00:14:24,790
kaj ĉiu funkcio prenas lian propran spacon en la pilo, lia propra stako kadro estas kio ĝi estas nomata.

197
00:14:24,790 --> 00:14:31,590
Do ĉefa havas sian pilo kadro, kaj ene de ĝi tuj ekzistas ĉi nombroj tabelo,

198
00:14:31,590 --> 00:14:34,270
kaj tio okazas al esti de amplekso sizeof (nombroj).

199
00:14:34,270 --> 00:14:38,180
Ĝi tuj devos grandeco de nombroj dividitaj de grandeco de elementoj,

200
00:14:38,180 --> 00:14:42,010
sed ke ĉiuj vivoj ene ĉefa La pilo kadro.

201
00:14:42,010 --> 00:14:45,190
Kiam ni nomas serĉo, serĉo ricevas sian propran pilo kadro,

202
00:14:45,190 --> 00:14:48,840
lia propra spaco por stoki ĉiuj ties lokaj variabloj.

203
00:14:48,840 --> 00:14:56,420
Sed tiuj argumentoj - tiel fojnamaso ne estas kopio de tiu tuta tabelo.

204
00:14:56,420 --> 00:15:00,990
Ni ne pasas en la tuta tabelo kiel kopion en serĉo.

205
00:15:00,990 --> 00:15:04,030
Ĝi simple pasas referenco al tiu tabelo.

206
00:15:04,030 --> 00:15:11,470
Do serĉo povas aliri tiujn numerojn por ĉi tiu referenco.

207
00:15:11,470 --> 00:15:17,100
Ĝi estas ankoraŭ aliri la aferojn kiuj vivas ene de ĉefaj la pilo kadro,

208
00:15:17,100 --> 00:15:22,990
sed esence, kiam ni atingos punteros, kiu devus esti poste,

209
00:15:22,990 --> 00:15:24,980
ĉi tio estas kion punteros estas.

210
00:15:24,980 --> 00:15:29,400
Punteros estas nur aludoj al aĵoj, kaj vi povas uzi punteros aliri aĵoj

211
00:15:29,400 --> 00:15:32,030
kiuj estas en aliaj aĵoj 'stako kadroj.

212
00:15:32,030 --> 00:15:37,660
Do eĉ se nombroj estas loka al ĉefa, ni povas ankoraŭ konsenti li tra ĉi puntero.

213
00:15:37,660 --> 00:15:41,770
Sed ĉar ĝi estas nur montrilo kaj estas nur referenco,

214
00:15:41,770 --> 00:15:45,040
sizeof (fojnamaso) ĝuste redonas la grandecon de la referenco mem.

215
00:15:45,040 --> 00:15:47,950
Ĝi ne redonas la grandeco de la aĵo ĝi estas indikante.

216
00:15:47,950 --> 00:15:51,110
Ne denove la reala grandeco de nombroj.

217
00:15:51,110 --> 00:15:55,660
Kaj tiel ĉi tio ne tuj funkcias kiel ni volas ke ĝi.

218
00:15:55,660 --> 00:15:57,320
>> Demandojn sur tio?

219
00:15:57,320 --> 00:16:03,250
Punteros estos eniris en signife pli sangriento detalo en semajnojn por alveni.

220
00:16:06,750 --> 00:16:13,740
Kaj jen estas tio multon, kiun vi vidas, plej serĉo aĵoj aŭ varo aferojn,

221
00:16:13,740 --> 00:16:16,990
ili estas preskaŭ ĉiuj tuj bezonas preni la reala grandeco de la tabelo,

222
00:16:16,990 --> 00:16:20,440
ĉar en C, ni ne havas ideon kion la grandeco de la tabelo estas.

223
00:16:20,440 --> 00:16:22,720
Vi devas permane pasi ĝin in

224
00:16:22,720 --> 00:16:27,190
Kaj vi ne povas permane pasi en la tuta tabelo ĉar vi ĵus pasis en la referenco

225
00:16:27,190 --> 00:16:30,390
kaj ĝi ne povas atingi la grandecon de la referenco.

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

227
00:16:32,300 --> 00:16:38,160
Do nun ni volas apliki tion, kio estis klarigita antaŭe.

228
00:16:38,160 --> 00:16:41,530
Vi povas labori sur ĝi dum minuto,

229
00:16:41,530 --> 00:16:45,250
kaj vi ne devas zorgi pri akirante ĉio perfekte 100% laboras.

230
00:16:45,250 --> 00:16:51,410
Nur redakti la duono _pseudocode_ por kiom vi kredas ke devus funkcii.

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

232
00:16:53,630 --> 00:16:56,350
Neniu bezonas esti tute farita kun tiu ankoraŭ.

233
00:16:56,350 --> 00:17:02,380
Sed ĉu iu sentas komforte kun kion ili havas ĝis nun,

234
00:17:02,380 --> 00:17:05,599
kiel iu povas labori kun kune?

235
00:17:05,599 --> 00:17:09,690
Ĉu iu volas volontulon? Aŭ mi hazarde elektas.

236
00:17:12,680 --> 00:17:18,599
Ĝi ne devas esti ĝuste per ia mezuro sed iu povas modifi enen laborante stato.

237
00:17:18,599 --> 00:17:20,720
[Studento] Certe. >> Bone.

238
00:17:20,720 --> 00:17:27,220
Do vi povas savi la revizio klakante sur la eta Save ikono.

239
00:17:27,220 --> 00:17:29,950
Vi estas Ramya, ĉu ne? >> [Studento] Yeah. >> [Bowden] Okay.

240
00:17:29,950 --> 00:17:35,140
Do nun mi povas vidi vian revizio kaj ĉiuj povas tiri supren la revizio.

241
00:17:35,140 --> 00:17:38,600
Kaj ĉi tie ni havas - Okay.

242
00:17:38,600 --> 00:17:43,160
Do Ramya iris kun la rekursia solvo, kiu estas definitive validan solvo.

243
00:17:43,160 --> 00:17:44,970
Estas du manieroj vi povas fari ĉi tiun problemon.

244
00:17:44,970 --> 00:17:48,060
Vi povas aŭ fari ĝin ripete aŭ rekursie.

245
00:17:48,060 --> 00:17:53,860
Plej problemojn vi renkontos kiuj povas fari rekursie povas ankaŭ fari ripete.

246
00:17:53,860 --> 00:17:58,510
Do jen ni faris ĝin rekursie.

247
00:17:58,510 --> 00:18:03,730
>> Ĉu iu volas difini kion signifas fari funkcio rekursia?

248
00:18:07,210 --> 00:18:08,920
[Studento] Kiam vi havas funkcion nomas sin

249
00:18:08,920 --> 00:18:13,470
kaj tiam nomita sin ĝis ĝi eliras kun vera kaj veraj. >> Jes.

250
00:18:13,470 --> 00:18:17,680
A rekursia funkcio estas simple funkcio kiu nomas sin.

251
00:18:17,680 --> 00:18:24,140
Estas tri grandaj aĵoj kiuj rekursia funkcio devas havi.

252
00:18:24,140 --> 00:18:27,310
La unua estas evidente, flamo sin.

253
00:18:27,310 --> 00:18:29,650
La dua estas la bazo kazo.

254
00:18:29,650 --> 00:18:33,390
Do je iu punkto la funkcio bezonas halti nomas sin,

255
00:18:33,390 --> 00:18:35,610
kaj tio la bazo kazo estas por.

256
00:18:35,610 --> 00:18:43,860
Do jen ni scias, ke ni devus halti, ni devus rezigni de nia serĉo

257
00:18:43,860 --> 00:18:48,150
kiam komenco egalas fino - kaj ni transiru kion tio signifas.

258
00:18:48,150 --> 00:18:52,130
Sed fine, la lasta afero kiun gravas por rekursie funkcioj:

259
00:18:52,130 --> 00:18:59,250
la funkcioj devas iel alproksimigi la bazo kazo.

260
00:18:59,250 --> 00:19:04,140
Kiel se vi fakte ne ĝisdatigi nenion kiam vi faras la duan rekursia alvoko,

261
00:19:04,140 --> 00:19:07,880
se vi laŭvorte ĝuste nomi la funkcion denove kun la samaj argumentoj

262
00:19:07,880 --> 00:19:10,130
kaj neniu tutmonda variabloj ŝanĝis aŭ nenion,

263
00:19:10,130 --> 00:19:14,430
vi neniam atingos la bazo kazo, en kiu kazo tio estas malbona.

264
00:19:14,430 --> 00:19:17,950
Estos malfinia rekursio kaj pilo superflui.

265
00:19:17,950 --> 00:19:24,330
Sed ĉi tie ni vidas ke la ĝisdatigo okazas ĉar ni estas ĝisdatigo komenci + fino / 2,

266
00:19:24,330 --> 00:19:28,180
ni ĝisdatigi la fino argumento tie, ni ĝisdatigi la komenco argumento tie.

267
00:19:28,180 --> 00:19:32,860
Do en ĉiu rekursie alvokoj ni ĝisdatigo ion. Okay.

268
00:19:32,860 --> 00:19:38,110
Ĉu vi volas promeni ni per viaj solvo? >> Certe.

269
00:19:38,110 --> 00:19:44,270
Mi uzas SearchHelp por ke ĉiufoje mi fari ĉi tiun funkcion alvoko

270
00:19:44,270 --> 00:19:47,910
Mi havas la komenco de kie Mi serĉas en la tabelo kaj la fino

271
00:19:47,910 --> 00:19:49,380
de kie Mi serĉas la tabelo.

272
00:19:49,380 --> 00:19:55,330
>> Je ĉiu paŝo kie diras tion estas la mezo elemento, kiu estas komenco + fino / 2,

273
00:19:55,330 --> 00:19:58,850
estas ke egala al kion ni serĉas?

274
00:19:58,850 --> 00:20:04,650
Kaj se jes, tiam ni trovis ĝin, kaj mi supozas ke gets pasis laŭ la niveloj de rekursio.

275
00:20:04,650 --> 00:20:12,540
Kaj se tio ne estas vera, tiam ni kontrolu ĉu tiu meza valoro de la tabelo estas tro granda,

276
00:20:12,540 --> 00:20:19,320
en kies kazo ni rigardas la maldekstra duono de la tabelo irante de komenco al la mezo indekso.

277
00:20:19,320 --> 00:20:22,710
Kaj se ne ni faru la fino duono.

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

279
00:20:24,740 --> 00:20:27,730
Tio sonas bona.

280
00:20:27,730 --> 00:20:36,640
Okay, do kelkaj aferoj, kaj fakte, tio estas tre alta nivelo afero

281
00:20:36,640 --> 00:20:41,270
ke vi neniam bezonas scii por ĉi tiu kurso, sed ĝi estas vera.

282
00:20:41,270 --> 00:20:46,080
Rekursiaj funkcioj, vi ĉiam aŭdi ke ili estas malbonaj interkonsenton

283
00:20:46,080 --> 00:20:51,160
ĉar se vi rekursie voki vin tro multfoje, vi ricevas pilo superflui

284
00:20:51,160 --> 00:20:54,990
pro tio ke, kiel mi diris antaŭe, ĉiu funkcio atingas sian propran pilo kadro.

285
00:20:54,990 --> 00:20:59,500
Do ĉiu alvoko de la rekursia funkcio atingas sian propran pilo kadro.

286
00:20:59,500 --> 00:21:04,140
Do se vi faras 1.000 rekursiaj vokoj, vi ricevas 1.000 pilo kadroj,

287
00:21:04,140 --> 00:21:08,390
kaj rapide vi kondukos al havi tro multajn pilo kadroj kaj aĵoj nur rompi.

288
00:21:08,390 --> 00:21:13,480
Por ke tio rekursie funkcioj estas ĝenerale malbona.

289
00:21:13,480 --> 00:21:19,370
Sed estas belan subaro de rekursiaj funkcioj nomas vosto-rekursie funkcioj,

290
00:21:19,370 --> 00:21:26,120
kaj ĉi tio okazas al esti ekzemplo de unu kie se la tradukilo rimarkas tiun

291
00:21:26,120 --> 00:21:29,920
kaj ĝi devus, mi kredas - en Clang se vi pasas ĝi la-O2 flago

292
00:21:29,920 --> 00:21:33,250
tiam rimarkos ĉi estas vosto rekursie kaj fari aferojn bone.

293
00:21:33,250 --> 00:21:40,050
>> Ĝi reuzi la sama pilo kadro denove kaj denove por ĉiu rekursie alvokon.

294
00:21:40,050 --> 00:21:47,010
Kaj tiel ekde vi uzas la saman pilo kadro, vi ne bezonas zorgi pri

295
00:21:47,010 --> 00:21:51,690
iam pilo superfluas, kaj samtempe, kiel vi diris antaŭe,

296
00:21:51,690 --> 00:21:56,380
kie iam vi revenos vera, tiam ĝi devas reveni supren ĉiuj tiuj pilo kadroj

297
00:21:56,380 --> 00:22:01,740
kaj la 10-a alvoko por SearchHelp devas reveni al la 9a, devas reveni al la 8a.

298
00:22:01,740 --> 00:22:05,360
Por ke ne bezonas okazi kiam funkcioj estas vosto rekursie.

299
00:22:05,360 --> 00:22:13,740
Kaj tiel tio faras tiun funkcion vosto rekursie estas avizo kiu por ajna donita alvokon al searchHelp

300
00:22:13,740 --> 00:22:18,470
la rekursiaj alvokon ke ĝi estas fari kion ĝi estas reveni.

301
00:22:18,470 --> 00:22:25,290
Do en la unua alvoko al SearchHelp, ni aŭ tuj redoni malvera,

302
00:22:25,290 --> 00:22:29,590
tuj revenos vera, aŭ ni faras rekursia alvoko al SearchHelp

303
00:22:29,590 --> 00:22:33,810
kie kion ni reveni estas kion tiu alvoko estas reveni.

304
00:22:33,810 --> 00:22:51,560
Kaj ni ne povis fari tion, se ni faris ion kiel int x = SearchHelp, reveno x * 2,

305
00:22:51,560 --> 00:22:55,440
nur iuj hazardaj ŝanĝon.

306
00:22:55,440 --> 00:23:01,470
>> Do nun tiu rekursia alvoko, tiu int x = SearchHelp rekursia alvoko,

307
00:23:01,470 --> 00:23:05,740
ne plu vosto rekursie ĉar fakte ne devas reveni

308
00:23:05,740 --> 00:23:10,400
reen al antaŭa pilo kadro por ke tiu antaŭa alvoko al la funkcio

309
00:23:10,400 --> 00:23:13,040
povas tiam ion fari kun la reveno valoro.

310
00:23:13,040 --> 00:23:22,190
Do tiu estas ne vosto rekursie, sed kion ni havis antaŭe estas bele vosto rekursie. Yeah.

311
00:23:22,190 --> 00:23:27,000
[Studento] Should ne la dua bazo okazo kontrolis unua

312
00:23:27,000 --> 00:23:30,640
ĉar ne eblis situacio kie al vi pasi ĝin la argumento

313
00:23:30,640 --> 00:23:35,770
vi komencos = fino, sed ili estas la nadlo valoro.

314
00:23:35,770 --> 00:23:47,310
La demando estis ne povas ni kuras en la kazo kie fino estas la nadlo valoro

315
00:23:47,310 --> 00:23:52,000
aŭ komenci = fino, taŭge, starti = fino

316
00:23:52,000 --> 00:23:59,480
kaj vi ne vere kontrolis tiun apartan valoron ankoraŭ,

317
00:23:59,480 --> 00:24:03,910
tiam komencos + fino / 2 estas simple tuj estos la sama valoro.

318
00:24:03,910 --> 00:24:07,890
Sed ni jam revenis falsaj kaj ni neniam vere kontrolis la valoro.

319
00:24:07,890 --> 00:24:14,240
Do almenaŭ, en la unua alvoko, se grandeco estas 0, tiam ni volas reveni falsaj.

320
00:24:14,240 --> 00:24:17,710
Sed se grandeco estas 1, tiam komenco ne tuj egala fino,

321
00:24:17,710 --> 00:24:19,820
kaj ni almenaŭ kontrolu la elemento.

322
00:24:19,820 --> 00:24:26,750
Sed mi kredas ke vi pravas pri ke ni povas fini en kazo kie komenci + fino / 2,

323
00:24:26,750 --> 00:24:31,190
komenco finas esti la sama kiel komenco + fino / 2,

324
00:24:31,190 --> 00:24:35,350
sed ni neniam vere kontrolis tiu elemento.

325
00:24:35,350 --> 00:24:44,740
>> Do, se ni unue provu estas la meza ero la valoron ni serĉas,

326
00:24:44,740 --> 00:24:47,110
tiam ni povas tuj reveni vera.

327
00:24:47,110 --> 00:24:50,740
Else if ili estas egalaj, tiam ne estas punkto en daŭrigi

328
00:24:50,740 --> 00:24:58,440
ekde ni ĵus tuj ĝisdatigi al kazo kie ni estas en sama-era tabelo.

329
00:24:58,440 --> 00:25:01,110
Se tio sola ero ne estas la ni serĉas,

330
00:25:01,110 --> 00:25:03,530
tiam ĉio estas malbone. Yeah.

331
00:25:03,530 --> 00:25:08,900
[Studento] La afero estas ke ekde grandeco estas efektive pli grandaj ol la nombro de eroj en la tabelo,

332
00:25:08,900 --> 00:25:13,070
ekzistas jam kompensi - >> Do volo grandeco -

333
00:25:13,070 --> 00:25:19,380
[Studento] Diru se la tabelo estis grandeco 0, tiam la SearchHelp efektive kontroli fojnamaso de 0

334
00:25:19,380 --> 00:25:21,490
je la unua alvoko.

335
00:25:21,490 --> 00:25:25,300
La tabelo havas grandecon 0, tiel la 0 estas - >> Jes.

336
00:25:25,300 --> 00:25:30,750
Estas alia afero, ke - eble estus bona. Ni pensas.

337
00:25:30,750 --> 00:25:40,120
Do se la tabelo havis 10 elementoj kaj la meza ni iras por kontroli estas indekso 5,

338
00:25:40,120 --> 00:25:45,700
do ni kontrolanta 5, kaj diru, ke la valoro estas malpli.

339
00:25:45,700 --> 00:25:50,720
Do ni ĵeti ĉio for de 5 antaŭen.

340
00:25:50,720 --> 00:25:54,030
Do komencu + fino / 2 estas tuj estos nia nova fino,

341
00:25:54,030 --> 00:25:57,450
do jes, ĝi estas ĉiam restos tie de la fino de la tabelo.

342
00:25:57,450 --> 00:26:03,570
Se ĝi estas kazo se ĝi eĉ aŭ nepara, tiam ni devus kontroli, diru, 4,

343
00:26:03,570 --> 00:26:05,770
sed ni ankoraŭ ĵetante for -

344
00:26:05,770 --> 00:26:13,500
Do jes, fino estas ĉiam tuj estos preter la realaj fino de la tabelo.

345
00:26:13,500 --> 00:26:18,350
Do la elementoj ni enfokusigante, fino estas ĉiam tuj estos la unu post tio.

346
00:26:18,350 --> 00:26:24,270
Kaj do se komenco faras cxiam egala fino, ni estas en tabelo de amplekso 0.

347
00:26:24,270 --> 00:26:35,600
>> La alia afero mi pensis estas ni ĝisdatigo komenco esti komenci + fino / 2,

348
00:26:35,600 --> 00:26:44,020
do ĉi tiu estas la kazo, ke mi havas problemojn kun, kie komenci + fino / 2

349
00:26:44,020 --> 00:26:46,820
estas la elemento ni checking.

350
00:26:46,820 --> 00:26:58,150
Supozu ke ni havis tiun 10-era tabelo. Kion ajn.

351
00:26:58,150 --> 00:27:03,250
Do komencu + fino / 2 estas tuj estos iu kiel ĉi tiu,

352
00:27:03,250 --> 00:27:07,060
kaj se tio ne estas la valoro, ke ni volas ĝisdatigi.

353
00:27:07,060 --> 00:27:10,060
La valoro estas pli granda, do ni volas rigardi tiun duonon de la tabelo.

354
00:27:10,060 --> 00:27:15,910
Do kiel ni ĝisdatigo komenco, ni ĝisdatigo komenco nun esti ĉi elemento.

355
00:27:15,910 --> 00:27:23,790
Sed ĉi tio povas ankoraŭ labori, aŭ almenaŭ, vi povas fari komenco + fino / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Studento] Vi ne bezonas esti komenci + fino [inaudible] >> Jes.

357
00:27:27,850 --> 00:27:33,240
Ni jam kontrolis tiun elementon kaj scias ke estas ne unu ni serĉas.

358
00:27:33,240 --> 00:27:36,800
Do ni ne bezonas ĝisdatigi komenco esti tiu ero.

359
00:27:36,800 --> 00:27:39,560
Ni povas nur salti ĝin kaj ĝisdatigos komenci esti ĉi elemento.

360
00:27:39,560 --> 00:27:46,060
Kaj estas tie iam kazo, ni diru, ke tio estis fino,

361
00:27:46,060 --> 00:27:53,140
do tiam komencos estus tio, starti + fino / 2 estus tio,

362
00:27:53,140 --> 00:28:00,580
komenci + fino - Jes, mi kredas ke povas fini en malfinia rekursio.

363
00:28:00,580 --> 00:28:12,690
Diru estas nur aro de amplekso 2 aŭ tabelo de amplekso 1. Mi kredas ke tiu funkcios.

364
00:28:12,690 --> 00:28:19,490
Do nune, komenco estas tiu elemento kaj fino estas 1 preter ĝi.

365
00:28:19,490 --> 00:28:24,110
Do la elemento kiu ni iras por kontroli estas ĉi tiu,

366
00:28:24,110 --> 00:28:29,400
kaj poste kiam ni ĝisdatigi komenco, ni ĝisdatigo komenco esti 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
kiu iras al fino ni denove kun komenco esti ĉi elemento.

368
00:28:33,160 --> 00:28:36,210
>> Do ni kontrolanta la sama elemento denove kaj denove.

369
00:28:36,210 --> 00:28:43,310
Do ĉi tiu estas la kazo en kiu ĉiu rekursie alvoko devas vere aktualigi ion.

370
00:28:43,310 --> 00:28:48,370
Do ni bezonas fari komenco + fino / 2 + 1, alie tie estas kazo

371
00:28:48,370 --> 00:28:50,710
kie ni fakte ne ĝisdatigi komenco.

372
00:28:50,710 --> 00:28:53,820
Ĉiuj vidas tion?

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

374
00:28:56,310 --> 00:29:03,860
Ĉu iu havas demandojn pri tiu solvo aŭ ajna pli da komentoj?

375
00:29:05,220 --> 00:29:10,280
Okay. Ĉu iu jam ripeta solvo kiu povas ĉiuj rigardi?

376
00:29:17,400 --> 00:29:20,940
Ĉu ni ĉiuj tion rekursie?

377
00:29:20,940 --> 00:29:25,950
Aŭ ankaŭ mi supozas se vi malfermis lia, tiam vi havu duarangigita vian antaŭa.

378
00:29:25,950 --> 00:29:28,810
Ĉu ĝi aŭtomate savi? Mi ne estas pozitiva.

379
00:29:35,090 --> 00:29:39,130
Ĉu iu jam ripeta?

380
00:29:39,130 --> 00:29:42,430
Ni povas marŝi tra ĝi kune se ne.

381
00:29:46,080 --> 00:29:48,100
La ideo tuj estos la sama.

382
00:30:00,260 --> 00:30:02,830
Ripeta solvo.

383
00:30:02,830 --> 00:30:07,140
Ni tuj volas esence fari la sama ideo

384
00:30:07,140 --> 00:30:16,530
kie ni volas konservi trako de la nova fino de la tabelo kaj la nova komenco de la tabelo

385
00:30:16,530 --> 00:30:18,510
kaj faru tion denove kaj.

386
00:30:18,510 --> 00:30:22,430
Kaj se tio, kion ni konservanta trako de la komenco kaj la fino iam sekci,

387
00:30:22,430 --> 00:30:29,020
tiam ni ne trovis ĝin kaj ni povas reveni falsaj.

388
00:30:29,020 --> 00:30:37,540
Do kiel mi faru tion? Ĉiu havas sugestojn aŭ kodo por mi tiri supren?

389
00:30:42,190 --> 00:30:47,450
[Studento] Do momenton buklo. >> Jes.

390
00:30:47,450 --> 00:30:49,450
Vi tuj volas fari banton.

391
00:30:49,450 --> 00:30:51,830
>> Ĉu vi havas kodon mi povus tiri supren, aŭ kio estis vi tuj sugestas?

392
00:30:51,830 --> 00:30:56,340
[Studento] Mi pensas tiel. >> Bone. Ĉi tio faras tion pli facila. Kio estis via nomo?

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

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

395
00:31:04,190 --> 00:31:13,200
Malalta estas kion ni nomas komenci antaŭe.

396
00:31:13,200 --> 00:31:17,080
Ĝis estas ne tute kion ni nomas fino antaŭe.

397
00:31:17,080 --> 00:31:22,750
Vere, fino estas nun en la tabelo. Ĝi estas ero ni devus konsideri.

398
00:31:22,750 --> 00:31:26,890
Tiel malalta estas 0, supren estas la grandeco de la tabelo - 1,

399
00:31:26,890 --> 00:31:34,780
kaj nun ni estas looping, kaj ni estas kontrolanta -

400
00:31:34,780 --> 00:31:37,340
Mi supozas ke vi povas marŝi tra ĝi.

401
00:31:37,340 --> 00:31:41,420
Kio estis via penso tra ĉi? Marŝi ni per via kodo.

402
00:31:41,420 --> 00:31:49,940
[Studento] Certe. Rigardu la fojnamaso valoro en la mezo kaj kompari ĝin al nadlo.

403
00:31:49,940 --> 00:31:58,520
Do, se ĝi estas pli granda ol via nadlo, tiam vi volas - ho, vere, tio devus esti malantaŭen.

404
00:31:58,520 --> 00:32:05,180
Vi tuj volas forĵeti la dekstra duono, kaj tiel yeah, kiu devus esti la vojo.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Do tiu devus esti malpli? Estas ke kion vi diris? >> [Studento] Yeah.

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

407
00:32:10,390 --> 00:32:15,700
Do, se tio, kion ni rigardis estas pli malgranda ol kion ni volas,

408
00:32:15,700 --> 00:32:19,410
tiam jes, ni volas forĵeti la maldekstra duono,

409
00:32:19,410 --> 00:32:22,210
kio signifas ni ĝisdatigo ĉio ni konsideri

410
00:32:22,210 --> 00:32:26,610
movante malalta dekstre de la tabelo.

411
00:32:26,610 --> 00:32:30,130
Ĉi aspektas bona.

412
00:32:30,130 --> 00:32:34,550
Mi kredas ke ĝi havas la saman problemon, kiun ni diris en la antaŭa,

413
00:32:34,550 --> 00:32:49,760
kie se malaltaj estas 0 kaj ĝis estas 1, tiam malalta + up / 2 estas tuj starigis al esti la sama afero denove.

414
00:32:49,760 --> 00:32:53,860
>> Kaj eĉ se tio ne estas la kazo, estas ankoraŭ pli efika almenaŭ

415
00:32:53,860 --> 00:32:57,630
justaj forĵeti la elemento ni nur rigardis, kiun ni konas estas erara.

416
00:32:57,630 --> 00:33:03,240
Tiel malalta + up / 2 + 1 - >> [studento] Tio devus esti en la alia direkto.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Aŭ ĉi devus esti - 1 kaj la alia devas esti + 1.

418
00:33:05,900 --> 00:33:09,580
[Studento] Kaj devus esti duobla egala signo. >> [Bowden] Yeah.

419
00:33:09,580 --> 00:33:11,340
[Studento] Yeah.

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

421
00:33:15,910 --> 00:33:21,280
Kaj fine, nun ke ni havas ĉi + 1 - 1 aferon,

422
00:33:21,280 --> 00:33:31,520
estas - ĝi povus ne esti - chu iam ebla por malalta por fini kun valoro pli granda ol ĉe?

423
00:33:35,710 --> 00:33:40,320
Mi kredas ke la sola maniero kiu povas okazi - Ĉu eblas? >> [Studento] Mi ne scias.

424
00:33:40,320 --> 00:33:45,220
Sed se ĝi alvenas senpintigita kaj tiam ricevas minus ke 1 kaj poste - >> Jes.

425
00:33:45,220 --> 00:33:47,480
[Studento] Estus eble get paneas.

426
00:33:49,700 --> 00:33:53,940
Mi kredas ke devus esti bona nur ĉar

427
00:33:53,940 --> 00:33:58,800
cxar por fini suba ili devus esti egala, mi pensas.

428
00:33:58,800 --> 00:34:03,070
Sed se ili estas egalaj, tiam ni ne plenumis dum buklo komenci kun

429
00:34:03,070 --> 00:34:06,670
kaj ni ĵus revenis de la valoro. Do mi kredas ke ni estas bona nun.

430
00:34:06,670 --> 00:34:11,530
Rimarku ke kvankam tiu problemo ne plu estas rekursie,

431
00:34:11,530 --> 00:34:17,400
la sama speco de ideoj apliki kie ni povas vidi kiel ĉi tiel facile pruntas

432
00:34:17,400 --> 00:34:23,659
al rekursiaj solvo de la fakto ke ni nur ĝisdatigi la indeksoj denove kaj denove,

433
00:34:23,659 --> 00:34:29,960
ni faris la problemo pli kaj pli malgranda, ni enfokusigas sur subaro de la tabelo.

434
00:34:29,960 --> 00:34:40,860
[Studento] Se malalta estas 0 kaj ĝis estas 1, ili ambaŭ esti 0 + 1/2, kiu irus al 0,

435
00:34:40,860 --> 00:34:44,429
kaj tiam tiu estus + 1, tiu estus - 1.

436
00:34:47,000 --> 00:34:50,870
[Studento] Kien ni kontrolanta egaleco?

437
00:34:50,870 --> 00:34:55,100
Kiel se la mezo estas vere nadlo?

438
00:34:55,100 --> 00:34:58,590
Ni ne nuntempe faras tion? Ho!

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

440
00:35:05,340 --> 00:35:13,740
Jes. Ni ne povas nur fari la provon ĉi tie ĉar diru la unua duono -

441
00:35:13,740 --> 00:35:16,430
[Studento] Ĝi estas fakte kiel ne forĵeti la bara.

442
00:35:16,430 --> 00:35:20,220
Do se vi forĵetu la baro, vi devas kontroli ĝin unua aŭ kiom.

443
00:35:20,220 --> 00:35:23,350
Ah. Yeah. >> [Studento] Yeah.

444
00:35:23,350 --> 00:35:29,650
Do nun ni forĵetis la ni aktuale rigardis,

445
00:35:29,650 --> 00:35:33,260
kio signifas ke ni nun bezonas havi ankaŭ

446
00:35:33,260 --> 00:35:44,810
if (fojnamaso [(malalta + supren) / 2] == kudrilo), tiam ni povas reveni vera.

447
00:35:44,810 --> 00:35:52,070
Kaj ĉu mi metis alian aŭ nur se, ĝi signifas laŭvorte la samon

448
00:35:52,070 --> 00:35:57,110
ĉar ĉi tio estus revenis vera.

449
00:35:57,110 --> 00:36:01,450
Do mi metis alian se, sed ne gravas.

450
00:36:01,450 --> 00:36:10,440
>> Do alia se ĉi, alie tio kaj ĉi tiu estas komuna afero mi faras

451
00:36:10,440 --> 00:36:14,340
kie eĉ se ĝi estas la kazo kie ĉio estas bona ĉi tie,

452
00:36:14,340 --> 00:36:22,780
kiel malalta neniam povas esti pli granda ol supre, tio ne valoras rezonado pri tio, ĉu tio estas vera.

453
00:36:22,780 --> 00:36:28,010
Do eble tiel diri dum malalta estas malpli ol aŭ egala al

454
00:36:28,010 --> 00:36:30,720
aŭ dum malalta estas malpli ol

455
00:36:30,720 --> 00:36:35,300
do se ili estas iam egala aŭ malalta okazas por preterlasi ĝin,

456
00:36:35,300 --> 00:36:40,130
tiam ni povas rompi tiun banton.

457
00:36:41,410 --> 00:36:44,630
Demandojn, maltrankviloj, komentoj?

458
00:36:47,080 --> 00:36:49,270
Okay. Ĉi aspektas bona.

459
00:36:49,270 --> 00:36:52,230
Nun ni volas fari varon.

460
00:36:52,230 --> 00:37:04,030
Se ni iras al mia dua revizio, ni vidas ĉi tiujn samajn numerojn,

461
00:37:04,030 --> 00:37:07,550
sed nun ili ne plu estas en ordo ordo.

462
00:37:07,550 --> 00:37:12,840
Kaj ni volas apliki speco uzante ajnan algoritmo en O de n logo n.

463
00:37:12,840 --> 00:37:17,240
Do kio algoritmo vi opinias ke ni devus apliki tie? >> [Studento] Merge varon.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Yeah. Kunfandi varo estas O (n log n), do tio estas kion ni faros.

465
00:37:23,810 --> 00:37:26,680
Kaj la problemo tuj estos bela similaj,

466
00:37:26,680 --> 00:37:31,920
kie facile pruntas al rekursiaj solvo.

467
00:37:31,920 --> 00:37:35,580
Ni povas ankaŭ veni supren kun ripeta solvo se ni volas,

468
00:37:35,580 --> 00:37:42,540
sed rekursio estos pli facile tie kaj ni devus fari rekursio.

469
00:37:45,120 --> 00:37:49,530
Mi supozas ke ni iru laux tra merge speco unue,

470
00:37:49,530 --> 00:37:54,280
kvankam estas bela video sur merge speco jam. [Ridado]

471
00:37:54,280 --> 00:37:59,780
Do kunfandi speco estas - mi malŝparas tiel de ĉi papero.

472
00:37:59,780 --> 00:38:02,080
Ho, tie estas nur unu maldekstre.

473
00:38:02,080 --> 00:38:03,630
Do kunfandi.

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

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

476
00:38:29,910 --> 00:38:33,460
Merge prenas du apartaj tabeloj.

477
00:38:33,460 --> 00:38:36,780
Individue tiuj du areoj estas ambaŭ ordo.

478
00:38:36,780 --> 00:38:40,970
Do tiu tabelo, 1, 3, 5, ordo. Tiu tabelo, 0, 2, 4, ordo.

479
00:38:40,970 --> 00:38:46,710
Nun kio merge devus fari estas kombini ilin en sola tabelo, kiu estas mem ordigita.

480
00:38:46,710 --> 00:38:57,130
Do ni volas tabelo de amplekso 6 kiu tuj havos tiujn elementojn ene de ĝi

481
00:38:57,130 --> 00:38:59,390
en ordo ordo.

482
00:38:59,390 --> 00:39:03,390
>> Kaj tiel ni povas utiligi la fakton, ke tiuj du areoj estas ordo

483
00:39:03,390 --> 00:39:06,800
fari tion en lineara tempo,

484
00:39:06,800 --> 00:39:13,510
lineara tempo signifon se ĉi tabelo estas grandeco x kaj ĉi tiu estas grandeco y,

485
00:39:13,510 --> 00:39:20,970
tiam la tuta algoritmo devus esti O (x + y). Okay.

486
00:39:20,970 --> 00:39:23,150
Do sugestoj.

487
00:39:23,150 --> 00:39:26,030
[Studento] Could ni komencu de la maldekstra?

488
00:39:26,030 --> 00:39:30,150
Do vi metos la 0 malsupren unua kaj tiam la 1 kaj tiam ĉi tie vi estas en la 2.

489
00:39:30,150 --> 00:39:33,320
Do ĝi estas speco de kiel vi havas langeto ke moviĝas al dekstre. >> [Bowden] Yeah.

490
00:39:33,320 --> 00:39:41,070
Por ambaŭ el tiuj tabeloj se ni nur koncentriĝas pri la plej maldekstra elemento.

491
00:39:41,070 --> 00:39:43,530
Ĉar ambaŭ tabeloj estas ordo, ni scias ke ĉi tiuj 2 eroj

492
00:39:43,530 --> 00:39:46,920
estas la plej malgranda eroj en ĉiu tabelo.

493
00:39:46,920 --> 00:39:53,500
Do tio signifas ke 1 de tiuj 2 eroj devas esti la plej malgranda ero en nia kunfandis tabelo.

494
00:39:53,500 --> 00:39:58,190
Simple tiel okazas ke la plej malgranda estas la unu dekstre ĉi tiu tempo.

495
00:39:58,190 --> 00:40:02,580
Do ni prenu 0, enŝovu ĝin sur la maldekstra ĉar 0 estas malpli ol 1,

496
00:40:02,580 --> 00:40:08,210
do prenu 0, enŝovu ĝin en nia unua pozicio, kaj tiam ni ĝisdatigi ĉi

497
00:40:08,210 --> 00:40:12,070
nun koncentriĝas pri la unua ero.

498
00:40:12,070 --> 00:40:14,570
Kaj nun ni ripeti.

499
00:40:14,570 --> 00:40:20,670
Do nun ni komparu 2 kaj 1. 1 estas pli malgranda, do ni devos enmeti 1.

500
00:40:20,670 --> 00:40:25,300
Ni ĝisdatigos ĉi puntero atentigi al ĉi ulo.

501
00:40:25,300 --> 00:40:33,160
Nun ni faru ĝin denove, tiel 2. Ĉi ĝisdatigos, kompari tiuj 2, 3.

502
00:40:33,160 --> 00:40:37,770
Ĉi ĝisdatigoj, tiam 4 kaj 5.

503
00:40:37,770 --> 00:40:42,110
Do tio estas merge.

504
00:40:42,110 --> 00:40:49,010
>> Ĝi devus esti bela preterlasas ke ĝi estas lineara tempo post kiam ni nur iri trans ĉiu elemento unufoje.

505
00:40:49,010 --> 00:40:55,980
Kaj tiu estas la plej granda paŝo al implementando merge varo fari ĉi tion.

506
00:40:55,980 --> 00:40:59,330
Kaj tio ne estas tiel malfacila.

507
00:40:59,330 --> 00:41:15,020
Paro aĵoj zorgi pri estas let diru ni kunfandi 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
En ĉi tiu kazo ni finas en la scenejo kie ĉi tiu tuj estos pli malgranda,

509
00:41:30,930 --> 00:41:36,160
tiam ni ĝisdatigi ĉi pointer, ĉi tiu tuj estos pli malgranda, ĝisdatigi ĉi,

510
00:41:36,160 --> 00:41:41,280
ĉi tiu estas pli malgranda, kaj nun vi devas rekoni

511
00:41:41,280 --> 00:41:44,220
kiam vi vere kuras el elementoj kompari kun.

512
00:41:44,220 --> 00:41:49,400
Kiel ni jam uzis tiun tutan tabelo,

513
00:41:49,400 --> 00:41:55,190
ĉiu en ĉi tiu tabelo estas nun nur enmetita en ĉi tie.

514
00:41:55,190 --> 00:42:02,040
Do, se ni iam kolizii la punkto kie unu el niaj tabeloj estas tute kunfandita jam,

515
00:42:02,040 --> 00:42:06,510
tiam ni nur prenu ĉiujn elementojn de la alia tabelo kaj enmeti ilin en la fino de la tabelo.

516
00:42:06,510 --> 00:42:13,630
Do ni povas simple enŝovi 4, 5, 6. Okay.

517
00:42:13,630 --> 00:42:18,070
Tio estas unu afero por rigardi signifas.

518
00:42:22,080 --> 00:42:26,120
Implementando kiu devus esti paŝo 1.

519
00:42:26,120 --> 00:42:32,600
Kunfandi ordigi tiam bazita sur tio, ĝi estas 2 paŝoj, 2 stulta paŝoj.

520
00:42:38,800 --> 00:42:42,090
Ni nur donos cxi tiun tabelo.

521
00:42:57,920 --> 00:43:05,680
Do kunfandi varo, paŝo 1 estas rekursie rompas la tabelo en duonoj.

522
00:43:05,680 --> 00:43:09,350
Do fendi ĉi tabelo en duonoj.

523
00:43:09,350 --> 00:43:22,920
Ni nun havas 4, 15, 16, 50 kaj 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Kaj nun ni faru ĝin denove kaj ni dividis tiujn en duonoj.

525
00:43:25,800 --> 00:43:27,530
Mi nur faras sur tiu ĉi flanko.

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

527
00:43:34,790 --> 00:43:37,440
Ni devus fari la samon pri tie.

528
00:43:37,440 --> 00:43:40,340
Kaj nun ni fendi ĝin en duonoj denove.

529
00:43:40,340 --> 00:43:51,080
Kaj ni havas 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Por ke estas nia bazo kazo.

531
00:43:53,170 --> 00:44:00,540
Iam la tabeloj estas de amplekso 1, tiam ni haltos kun la disiĝo en duonoj.

532
00:44:00,540 --> 00:44:03,190
>> Nun kion ni faru pri tio?

533
00:44:03,190 --> 00:44:15,730
Ni finos ĉi ankaŭ rompi en 8, 23, 42, kaj 108.

534
00:44:15,730 --> 00:44:24,000
Do nun ni estas en ĉi tiu punkto, nun tretas du el merge varo nur kunfandi paroj al la listoj.

535
00:44:24,000 --> 00:44:27,610
Do ni volas kunfandi tiujn. Ni nur nomas kunfandi.

536
00:44:27,610 --> 00:44:31,410
Ni scias merge revenos tiuj en ordo ordo.

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

538
00:44:33,920 --> 00:44:41,440
Nun ni volas kunfandi tiujn, kaj ke revenos lerta kun tiuj en ordo ordo,

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

540
00:44:44,160 --> 00:44:57,380
Ni kunfandi tiujn - mi ne povas skribi - 8, 23 kaj 42, 108.

541
00:44:57,380 --> 00:45:02,890
Do ni havas kunfandis paroj samtempe.

542
00:45:02,890 --> 00:45:05,140
Nun ni nur kunfandi denove.

543
00:45:05,140 --> 00:45:10,130
Rimarku ke ĉiu de tiuj listoj estas ordigitaj en si mem,

544
00:45:10,130 --> 00:45:15,220
kaj tiam ni povas nur kunfandi tiujn listojn por akiri liston de grandeco 4 kiu estas ordo

545
00:45:15,220 --> 00:45:19,990
kaj kunfandi tiujn du listojn por akiri liston de grandeco 4 kiu estas ordo.

546
00:45:19,990 --> 00:45:25,710
Kaj fine, ni povas kunfandi tiujn du listojn de grandeco 4 akiri unu listo de amplekso 8 kiu ordo.

547
00:45:25,710 --> 00:45:34,030
Do por vidi ke ĉi tio estas ĝenerale n logo n, ni jam vidis, ke merge estas lineara,

548
00:45:34,030 --> 00:45:40,390
do kiam ni pritraktas kunfandi tiujn, do kiel la entuta kosto de merge

549
00:45:40,390 --> 00:45:43,410
cxar tiuj du lertaj estas nur 2 ĉar -

550
00:45:43,410 --> 00:45:49,610
Aŭ bone, ĝi estas O de n, sed n tie estas nur tiuj 2 elementoj, do ĝi estas 2.

551
00:45:49,610 --> 00:45:52,850
Kaj tiuj 2 estos 2 kaj tiuj 2 estos 2 kaj tiuj 2 estos 2,

552
00:45:52,850 --> 00:45:58,820
tiom trans ĉiuj kunfandas ke ni bezonas fari, ni finos faras n.

553
00:45:58,820 --> 00:46:03,210
Kiel 2 + 2 + 2 + 2 estas 8, kiu estas n,

554
00:46:03,210 --> 00:46:08,060
do la kosto de fandado en ĉi tiu aro estas n.

555
00:46:08,060 --> 00:46:10,810
Kaj tiam la samon ĉi tie.

556
00:46:10,810 --> 00:46:16,980
Ni kunfandi tiujn 2, tiam tiuj 2, kaj individue ĉi merge prenos kvar operacioj,

557
00:46:16,980 --> 00:46:23,610
ĉi merge prenos kvar operacioj, sed denove, inter ĉiuj de ĉi tiuj,

558
00:46:23,610 --> 00:46:29,030
ni finos kunfandante n tuta aferojn, kaj tial tiu paŝo prenas n.

559
00:46:29,030 --> 00:46:33,670
Kaj tiel ĉiu nivelo prenas n eroj esti kunfandita.

560
00:46:33,670 --> 00:46:36,110
>> Kaj kiom da niveloj estas tie?

561
00:46:36,110 --> 00:46:40,160
Je ĉiu nivelo, nia tabelo kreskas por grandeco 2.

562
00:46:40,160 --> 00:46:44,590
Jen nia arrays estas de amplekso 1, tie ili estas de amplekso 2, tie ili estas de amplekso 4,

563
00:46:44,590 --> 00:46:46,470
kaj fine, ili estas de amplekso 8.

564
00:46:46,470 --> 00:46:56,450
Do pro tio ke ĝi duobliĝis, ne tuj estos la tuta de log n de tiuj niveloj.

565
00:46:56,450 --> 00:47:02,090
Do kun logo n niveloj, ĉiu individua nivelo prenante n tuta operacioj,

566
00:47:02,090 --> 00:47:05,720
ni preni n logo n algoritmo.

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

568
00:47:08,940 --> 00:47:13,320
Ĉu homoj jam faris progreson pri kiel realigi tion?

569
00:47:13,320 --> 00:47:18,260
Ĉu iu jam en stato kie mi povas simple tiri siajn kodo?

570
00:47:20,320 --> 00:47:22,260
Mi povas doni minuto.

571
00:47:24,770 --> 00:47:27,470
Ĉi tiu tuj estos plu.

572
00:47:27,470 --> 00:47:28,730
Mi forte rekomendas ripetas -

573
00:47:28,730 --> 00:47:30,510
Vi ne devas fari rekursio por merge

574
00:47:30,510 --> 00:47:33,750
ĉar fari rekursio por merge, vi tuj devas pasi faskon de malsamaj grandecoj.

575
00:47:33,750 --> 00:47:37,150
Vi povas, sed estas ĝena.

576
00:47:37,150 --> 00:47:43,720
Sed rekursio por speco mem estas sufiĉe facila.

577
00:47:43,720 --> 00:47:49,190
Vi nur laŭvorte nomas specon sur maldekstra duono, varo sur dekstra duono. Okay.

578
00:47:51,770 --> 00:47:54,860
Ĉiu havas nenion mi povas tiri supren yet?

579
00:47:54,860 --> 00:47:57,540
Alie mi donos unu minuto.

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

581
00:47:59,900 --> 00:48:02,970
Ĉiu havas ion ni povas laboro kun?

582
00:48:05,450 --> 00:48:09,680
Alie ni nur funkcias kun ĉi tiu kaj tiam pligrandigi de tie.

583
00:48:09,680 --> 00:48:14,050
>> Ĉiu havas pli ol tio, ke mi povas tiri supren?

584
00:48:14,050 --> 00:48:17,770
[Studento] Yeah. Vi povas tiri supren mia. >> Bone.

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

586
00:48:22,170 --> 00:48:25,280
[Studento] Ne estis multaj kondiĉoj. >> Ho, pafi. Can you -

587
00:48:25,280 --> 00:48:28,110
[Studento] mi devas savi ĝin. >> Jes.

588
00:48:32,420 --> 00:48:35,730
Do ni faris fari la merge aparte.

589
00:48:35,730 --> 00:48:38,570
Ho, sed ne estas tiel malbona.

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

591
00:48:41,650 --> 00:48:47,080
Do varo estas mem nur nomante mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Klarigi al ni kion mergeSortHelp faras.

593
00:48:49,530 --> 00:48:55,700
[Studento] MergeSortHelp preskaux faras la du ĉefaj paŝoj,

594
00:48:55,700 --> 00:49:01,270
kiu estas por ordigi ĉiu duono de la tabelo kaj tiam kunigi ilin ambaŭ.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Okay, do donu al mi la duan.

596
00:49:10,850 --> 00:49:13,210
Mi kredas ke tiu - >> [studento] Mi bezonas -

597
00:49:17,100 --> 00:49:19,400
Yeah. Mi mankis io.

598
00:49:19,400 --> 00:49:23,100
En merge, mi rimarkas, ke mi devas krei novan tabelo

599
00:49:23,100 --> 00:49:26,530
ĉar mi ne povis fari ĝin en loko. >> Jes. Vi ne povas. Korekti.

600
00:49:26,530 --> 00:49:28,170
[Studento] Do mi kreu novan tabelo.

601
00:49:28,170 --> 00:49:31,510
Mi forgesis fine de kunfandi al re-ŝanĝi.

602
00:49:31,510 --> 00:49:34,490
Okay. Ni bezonas novan tabelo.

603
00:49:34,490 --> 00:49:41,000
En merge varo, ĉi tiu estas preskaŭ ĉiam vera.

604
00:49:41,000 --> 00:49:44,340
Parto de la kosto de pli bona algoritmo tempo-saĝa

605
00:49:44,340 --> 00:49:47,310
estas preskaŭ ĉiam bezoni uzi iom pli memoro.

606
00:49:47,310 --> 00:49:51,570
Do jen, kiel ajn vi faras kunfandi varo,

607
00:49:51,570 --> 00:49:54,780
vi neeviteble bezonos uzi iun ekstra memoro.

608
00:49:54,780 --> 00:49:58,240
Li aŭ ŝi kreis novan tabelo.

609
00:49:58,240 --> 00:50:03,400
Kaj tiam vi diros al la fino ni nur bezonas kopii nova tabelo en la originala tabelo.

610
00:50:03,400 --> 00:50:04,830
[Studento] I think so, jes.

611
00:50:04,830 --> 00:50:08,210
Mi ne scias se tiu laboras en terminoj de kalkulado per referenco aux kion ajn -

612
00:50:08,210 --> 00:50:11,650
Yeah, ĝi funkcios. >> [Studento] Okay.

613
00:50:20,620 --> 00:50:24,480
Ĉu vi provas kuri tio? >> [Studento] Ne, ankoraŭ ne. >> Bone.

614
00:50:24,480 --> 00:50:28,880
Provu kurante ĝin, kaj tiam mi parolos pri tio dum sekundo.

615
00:50:28,880 --> 00:50:35,200
[Studento] mi devas ricevi la funkcio prototipoj kaj ĉiu, kvankam, ĉu ne?

616
00:50:37,640 --> 00:50:40,840
La funkcio prototipoj. Ho, vi volas diri kiel - Jes.

617
00:50:40,840 --> 00:50:43,040
Ordigi alvokas mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Do en ordo por speco nomi mergeSortHelp, mergeSortHelp devas aŭ estis difinita

619
00:50:47,390 --> 00:50:56,370
antaux varo aŭ ni simple bezonas la prototipo. Simple kopiu kaj gluu tio.

620
00:50:56,370 --> 00:50:59,490
Kaj simile, mergeSortHelp alvokas kunfandi,

621
00:50:59,490 --> 00:51:03,830
sed merge ne estis difinita ankoraŭ, do ni povas simple lasu mergeSortHelp scias

622
00:51:03,830 --> 00:51:08,700
ke tio estas kion kunfandi tuj aspekti, kaj tio estas tiel.

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

624
00:51:22,770 --> 00:51:32,660
Ni havas problemon tie, kie ni havas neniun bazon kazo.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp estas rekursie, do ajna rekursia funkcio

626
00:51:38,110 --> 00:51:42,610
tuj bezonas ian bazon kazo scii kiam halti rekursie nomante sin.

627
00:51:42,610 --> 00:51:45,590
Kio estas nia bazo kazo tuj estos tie? Yeah.

628
00:51:45,590 --> 00:51:49,110
[Studento] Se la grandeco estas 1? >> [Bowden] Jes.

629
00:51:49,110 --> 00:51:56,220
Do kiel ni vidis dekstre tie, ni haltis forkiĝanta arrays

630
00:51:56,220 --> 00:52:01,850
iam ni eniris tabeloj de amplekso 1, kiu neeviteble estas ordo samaj.

631
00:52:01,850 --> 00:52:09,530
Do se grandeco egalas 1, ni konas la tabelo jam ordo,

632
00:52:09,530 --> 00:52:12,970
do ni povas simple reveni.

633
00:52:12,970 --> 00:52:16,880
>> Rimarku ke estas malplena, do ni ne revenos ion apartan, ni ĵus revenis.

634
00:52:16,880 --> 00:52:19,580
Okay. Do jen nia bazo kazo.

635
00:52:19,580 --> 00:52:27,440
Mi supozas nia bazo kazo eblus ankaŭ se ni hazarde esti kunfandi tabelo de amplekso 0,

636
00:52:27,440 --> 00:52:30,030
ni probable volas halti je iu punkto,

637
00:52:30,030 --> 00:52:33,610
do ni povas simple diri grandeco malpli ol 2 malpli ol aŭ egala al 1

638
00:52:33,610 --> 00:52:37,150
por ke ĉi funkcios por ajna tabelo nun.

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

640
00:52:38,870 --> 00:52:42,740
Do jen nia bazo kazo.

641
00:52:42,740 --> 00:52:45,950
Nun vi volas promeni nin tra merge?

642
00:52:45,950 --> 00:52:49,140
Kion ĉiuj tiuj kazoj signifas?

643
00:52:49,140 --> 00:52:54,480
Ĝis ĉi tie, ni nur fari la saman ideon, la -

644
00:52:56,970 --> 00:53:02,470
[Studento] Mi bezonas esti pasante grandeco kun ĉiuj mergeSortHelp alvokoj.

645
00:53:02,470 --> 00:53:10,080
Mi aldonis grandecon kiel aldona primara kaj ne ekzistas, kiel grandeco / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Ho, grandeco / 2, grandeco / 2. >> [Studento] Jes, kaj ankaŭ en la pli supre funkcio tiel.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Jen? >> [Studento] Just grandeco. >> [Bowden] Oh. Grandeco, grandeco? >> [Studento] Yeah.

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

649
00:53:23,010 --> 00:53:26,580
Lasu min pensi por sekundo.

650
00:53:26,580 --> 00:53:28,780
Ĉu ni kolizios afero?

651
00:53:28,780 --> 00:53:33,690
Ni ĉiam trakti la maldekstra kiel 0. >> [Studento] No

652
00:53:33,690 --> 00:53:36,340
Tio estas erara tro. Pardonu. Ĝi devus esti komenco. Yeah.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Okay. Mi ŝatas ke pli bona.

654
00:53:39,230 --> 00:53:43,880
Kaj fino. Okay.

655
00:53:43,880 --> 00:53:47,200
Do nun vi volas promeni nin tra merge? >> [Studento] Okay.

656
00:53:47,200 --> 00:53:52,150
Mi ĵus promenis tra tiu nova tabelo ke mi kreis.

657
00:53:52,150 --> 00:53:57,420
Lia grandeco estas la grandeco de la porcio de la tabelo, ke ni volas esti ordo

658
00:53:57,420 --> 00:54:03,460
kaj provi trovi la elemento kiu mi metis en la nova tabelo paŝo.

659
00:54:03,460 --> 00:54:10,140
Do fari tion, unue mi kontrolanta se la maldekstra duono de la tabelo daŭre havas plu elementoj,

660
00:54:10,140 --> 00:54:14,260
kaj se ne, tiam vi iru al tiu alia kondiĉo, kiu ĵus diras

661
00:54:14,260 --> 00:54:20,180
bone, ĝi devas esti en la dekstra tabelo, kaj ni metu, ke en la nuna indekso de newArray.

662
00:54:20,180 --> 00:54:27,620
>> Kaj tiam alie, mi kontrolas se la dekstra flanko de la tabelo ankaŭ finis,

663
00:54:27,620 --> 00:54:30,630
en kies kazo mi simple metas en la maldekstran.

664
00:54:30,630 --> 00:54:34,180
Tio eble ne vere esti necesa. Mi ne estas certa.

665
00:54:34,180 --> 00:54:40,970
Sed ĉiuokaze, la aliaj du ĉeko kiu el la du estas pli malgranda en la maldekstra aŭ la dekstra.

666
00:54:40,970 --> 00:54:49,770
Kaj ankaŭ en ĉiu kazo, mi pliigante ajn lokokupilo mi pliigo.

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

668
00:54:52,040 --> 00:54:53,840
Tio aspektas bona.

669
00:54:53,840 --> 00:54:58,800
Ĉu iu havas komentojn aux zorgojn aŭ demandoj?

670
00:55:00,660 --> 00:55:07,720
Do la kvar kazoj, ke ni devas alporti aĵojn enen nur esti - aŭ ĝi aspektas kiel kvin -

671
00:55:07,720 --> 00:55:13,100
sed ni devas konsideri ĉu la maldekstra tabelo kuris el aferojn ni bezonas kunfandi,

672
00:55:13,100 --> 00:55:16,390
ĉu la dekstra tabelo kuris el aferojn ni bezonas kunfandi -

673
00:55:16,390 --> 00:55:18,400
Mi montras al nenio.

674
00:55:18,400 --> 00:55:21,730
Do ĉu la maldekstra tabelo kuris eksteren de aĵoj aŭ la dekstra tabelo kuris eksteren de aĵoj.

675
00:55:21,730 --> 00:55:24,320
Tiuj estas du kazoj.

676
00:55:24,320 --> 00:55:30,920
Ni ankaŭ bezonas la banala okazo de ĉu la maldekstra afero estas malpli ol la ĝusta.

677
00:55:30,920 --> 00:55:33,910
Tiam ni volas elekti la maldekstra afero.

678
00:55:33,910 --> 00:55:37,630
Tiuj estas la kazoj.

679
00:55:37,630 --> 00:55:40,990
Do tiu estas prava, do tio estas tiel.

680
00:55:40,990 --> 00:55:46,760
Array lasis. Estas 1, 2, 3. Okay. Do jes, tiuj estas la kvar aĵoj ni volus fari.

681
00:55:50,350 --> 00:55:54,510
Kaj ni ne iros tra ripeta solvo.

682
00:55:54,510 --> 00:55:55,980
Mi ne rekomendas -

683
00:55:55,980 --> 00:56:03,070
Kunfandi varo estas ekzemplo de funkcio kiu estas ambaŭ ne vosto rekursie,

684
00:56:03,070 --> 00:56:07,040
ĝi ne estas facila por fari ĝin vosto rekursie,

685
00:56:07,040 --> 00:56:13,450
sed ankaŭ ĝi ne estas tre facile fari ĝin ripeta.

686
00:56:13,450 --> 00:56:16,910
Ĉi tio estas tre facila.

687
00:56:16,910 --> 00:56:19,170
Tiu aplikado de merge varo,

688
00:56:19,170 --> 00:56:22,140
kunfandi, negrave kion vi faros, vi tuj konstrui merge.

689
00:56:22,140 --> 00:56:29,170
>> Do kunfandi speco konstruita sur supro de merge rekursie estas ĝuste tiuj tri linioj.

690
00:56:29,170 --> 00:56:34,700
Ripete, estas pli ĝena kaj pli malfacile pensi.

691
00:56:34,700 --> 00:56:41,860
Sed rimarki ke ĝi estas ne vosto rekursie ekde mergeSortHelp - kiam li nomas sin -

692
00:56:41,860 --> 00:56:46,590
ĝi ankoraŭ bezonas fari aĵojn post ĉi rekursia alvoko revenas.

693
00:56:46,590 --> 00:56:50,830
Do tiu pilo kadro devas ankoraŭ ekzistas eĉ post nomi tion ĉi.

694
00:56:50,830 --> 00:56:54,170
Kaj kiam vi nomas tion, la stako kadro devas ankoraŭ ekzistas

695
00:56:54,170 --> 00:56:57,780
ĉar eĉ post tiu alvoko, ni ankoraŭ bezonas kunfandi.

696
00:56:57,780 --> 00:57:01,920
Kaj estas netriviala fari ĉi vosto rekursie.

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

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

699
00:57:09,860 --> 00:57:13,400
Do reiri al ordigi - ho, tie estas du aferoj mi volas montri. Okay.

700
00:57:13,400 --> 00:57:17,840
Reiros al varo, ni faros ĉi rapide.

701
00:57:17,840 --> 00:57:21,030
Aŭ serĉo. Ordigi? Ordigi. Yeah.

702
00:57:21,030 --> 00:57:22,730
Irante al la komencoj de varo.

703
00:57:22,730 --> 00:57:29,870
Ni volas krei algoritmon kiu specoj la tabelo uzante ajnan algoritmo

704
00:57:29,870 --> 00:57:33,660
en O de n.

705
00:57:33,660 --> 00:57:40,860
Do kiel estas tio eblis? Ĉu iu havas iun specon de -

706
00:57:40,860 --> 00:57:44,300
Mi sugestis antaŭe al -

707
00:57:44,300 --> 00:57:48,300
Se ni estas sur plibonigi de n logo n al O de n,

708
00:57:48,300 --> 00:57:51,450
ni plibonigis nian algoritmon tempo-saĝa,

709
00:57:51,450 --> 00:57:55,250
kion signifas kio ni tuj bezonas fari por kompensi tion?

710
00:57:55,250 --> 00:57:59,520
[Studento] Spaco. >> Jes. Ni tuj estos uzanta pli da spaco.

711
00:57:59,520 --> 00:58:04,490
Kaj eĉ ne nur pli spaco, estas eksponente pli da spaco.

712
00:58:04,490 --> 00:58:14,320
Do mi kredas ke tiu tipo de algoritmo estas pseŭdo ion, pseŭdo polynom -

713
00:58:14,320 --> 00:58:18,980
pseŭdo - mi ne povas memori. Pseŭdo ion.

714
00:58:18,980 --> 00:58:22,210
Sed estas ĉar ni bezonas uzi tiom da spaco

715
00:58:22,210 --> 00:58:28,610
ke ĉi tio estas realigebla, sed ne realisma.

716
00:58:28,610 --> 00:58:31,220
>> Kaj kiel ni atingi tion?

717
00:58:31,220 --> 00:58:36,810
Ni povas atingi tion, se ni garantias ke iu ajn aparta ero en la tabelo

718
00:58:36,810 --> 00:58:39,600
estas sub certa grandeco.

719
00:58:42,070 --> 00:58:44,500
Do ni nur diros, ke grandeco estas 200,

720
00:58:44,500 --> 00:58:48,130
neniu elemento en tabelo estas sube grandeco 200.

721
00:58:48,130 --> 00:58:51,080
Kaj jen estas vere tre realisma.

722
00:58:51,080 --> 00:58:58,660
Vi povas tre facile havi tabelo, ke vi scias ĉion en ĝi

723
00:58:58,660 --> 00:59:00,570
tuj estos malpli ol iu nombro.

724
00:59:00,570 --> 00:59:07,400
Kiel se vi havas iun absolute amasa vektoro aŭ io

725
00:59:07,400 --> 00:59:11,810
sed vi scias ĉion tuj estos inter 0 kaj 5,

726
00:59:11,810 --> 00:59:14,790
tiam tuj estos signife pli rapide fari tion.

727
00:59:14,790 --> 00:59:17,930
Kaj la baro sur iu el la elementoj estas 5,

728
00:59:17,930 --> 00:59:21,980
tial ĉi baro, tio estas kiom memoro vi tuj estos uzi.

729
00:59:21,980 --> 00:59:26,300
Do la bara estas 200.

730
00:59:26,300 --> 00:59:32,960
En teorio ĉiam estas bara ekde entjero povas esti nur ĝis 4 milionoj,

731
00:59:32,960 --> 00:59:40,600
sed tio estas nerealisma tiam ni volonte uzos spaco

732
00:59:40,600 --> 00:59:44,400
en la ordo de 4 miliardoj. Do jen nerealisma.

733
00:59:44,400 --> 00:59:47,060
Sed ĉi tie ni diros nian bara estas 200.

734
00:59:47,060 --> 00:59:59,570
La lertaĵo por fari ĝin en O de n estas ni fari alian tabelo nomis grafoj de grandeco baro.

735
00:59:59,570 --> 01:00:10,470
Do fakte, ĉi tiu estas simbola ligilo por - Mi vere ne scias se Clang tion faras.

736
01:00:11,150 --> 01:00:15,330
Sed en GCC almenaŭ - I'm supozante Clang faras tro -

737
01:00:15,330 --> 01:00:18,180
ĉi tio nur pravalorizi la tuta tabelo esti _0s_.

738
01:00:18,180 --> 01:00:25,320
Do, se mi ne volas fari tion, tiam mi povus aparte fari por (_int_ i = 0;

739
01:00:25,320 --> 01:00:31,500
i <ligita; i + +) kaj grafoj [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Do nun ĉiu inicializado al 0.

741
01:00:35,260 --> 01:00:39,570
Mi persisti super mia tabelo,

742
01:00:39,570 --> 01:00:51,920
kaj kion mi faras estas mi rakonti la nombro de ĉiu - Ni iru malsupren tie.

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

744
01:00:55,480 --> 01:01:00,010
Kion mi rakonti estas la nombro de okazajxoj de ĉiu el tiuj elementoj.

745
01:01:00,010 --> 01:01:03,470
Ni efektive aldonu kelkajn pli en ĉi tie kun iu ripetas.

746
01:01:03,470 --> 01:01:11,070
Do la valoron ni havas ĉi tie, la valoro de tiu tuj estos tabelo [i].

747
01:01:11,070 --> 01:01:14,850
Do val eblis 4 aŭ 8 aŭ kion ajn.

748
01:01:14,850 --> 01:01:18,870
Kaj nun mi rakonti kiel multaj el kiuj valoro mi vidis,

749
01:01:18,870 --> 01:01:21,230
tiel grafoj [val] + +;

750
01:01:21,230 --> 01:01:29,430
Post ĉi tiu estas farita, grafoj tuj serĉos iun kiel 0001.

751
01:01:29,430 --> 01:01:42,190
Ni faru grafoj [val] - bara + 1.

752
01:01:42,190 --> 01:01:48,230
>> Nun tio estas nur por klarigi la fakton ke ni ekde 0.

753
01:01:48,230 --> 01:01:50,850
Do se 200 tuj estos nia plej granda nombro,

754
01:01:50,850 --> 01:01:54,720
tiam 0 al 200 estas 201 aĵoj.

755
01:01:54,720 --> 01:02:01,540
Do grafoj, ĝi devos aspekti 00001 ĉar ni havas unu 4.

756
01:02:01,540 --> 01:02:10,210
Tiam ni devos 0001, kie ni havos 1 en la 8a indekso de grafo.

757
01:02:10,210 --> 01:02:14,560
Ni havas 2 en la 23a indekso de grafo.

758
01:02:14,560 --> 01:02:17,630
Ni havas 2 en la 42 indekso de grafo.

759
01:02:17,630 --> 01:02:21,670
Do ni povas uzi kalkulon.

760
01:02:34,270 --> 01:02:44,920
Do num_of_item = grafoj [i].

761
01:02:44,920 --> 01:02:52,540
Kaj do se num_of_item estas 2, tio signifas ke ni volas enmeti 2 de la nombro mi

762
01:02:52,540 --> 01:02:55,290
en niajn ordo tabelo.

763
01:02:55,290 --> 01:03:02,000
Tial oni devas konservi trako de kiom for ni estas en la tabelo.

764
01:03:02,000 --> 01:03:05,470
Do indekso = 0.

765
01:03:05,470 --> 01:03:09,910
Array - mi nur skribas ĝin.

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

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

768
01:03:28,580 --> 01:03:32,490
Ĉu tio estas kion mi volas? Mi kredas ke estas kion mi volas.

769
01:03:35,100 --> 01:03:38,290
Jes, tiu aspektas bone. Okay.

770
01:03:38,290 --> 01:03:43,050
Do ne ĉiuj komprenas kion la celo de mia grafoj tabelo estas?

771
01:03:43,050 --> 01:03:48,140
Ĝi kalkulas la nombron de spritaĵoj de ĉiu el ĉi tiuj nombroj.

772
01:03:48,140 --> 01:03:51,780
Tiam mi ripetanta super kiu rakontas tabelo,

773
01:03:51,780 --> 01:03:57,190
kaj la th,-a pozicio en la grafoj tabelo

774
01:03:57,190 --> 01:04:01,930
estas la nombro de i estas tio devus aperi en mia ordo tabelo.

775
01:04:01,930 --> 01:04:06,840
Tial grafoj de 4 tuj esti 1

776
01:04:06,840 --> 01:04:11,840
kaj grafoj de 8 tuj esti 1, grafoj de 23 tuj estos 2.

777
01:04:11,840 --> 01:04:16,900
Do jen kiel multaj el ili mi volas enmeti en mian ordo tabelo.

778
01:04:16,900 --> 01:04:19,200
Tiam mi nur faras tion.

779
01:04:19,200 --> 01:04:28,960
Mi enmeto num_of_item i estas en mia ordo tabelo.

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

781
01:04:32,460 --> 01:04:43,100
Kaj tial denove, ĉi tiu estas lineara tempo kiam ni nur ripetanta super cxi tiun fojon,

782
01:04:43,100 --> 01:04:47,470
sed estas ankaŭ lineara en kio estas tiu nombro hazarde estas,

783
01:04:47,470 --> 01:04:50,730
kaj tiel ĝi peze dependas sur kion via baro estas.

784
01:04:50,730 --> 01:04:53,290
Kun bara de 200, tio ne estas tiel malbona.

785
01:04:53,290 --> 01:04:58,330
Se via baro tuj estos 10.000, tiam tio estas iom malbona,

786
01:04:58,330 --> 01:05:01,360
sed se via baro tuj estos 4 milionoj, tio estas tute nerealisma

787
01:05:01,360 --> 01:05:07,720
kaj ĉi tabelo tuj devas esti de amplekso 4 miliardoj, kiu estas nerealisma.

788
01:05:07,720 --> 01:05:10,860
Do jen tiel. Demandoj?

789
01:05:10,860 --> 01:05:13,270
[Inaudible studento respondon] >> Bone.

790
01:05:13,270 --> 01:05:15,710
Mi rimarkis unu alia afero kiam ni iris tra.

791
01:05:17,980 --> 01:05:23,720
Mi kredas ke la problemo estis en Lucas kaj probable ĉiu unuopa unu ni vidis.

792
01:05:23,720 --> 01:05:26,330
Mi tute forgesis.

793
01:05:26,330 --> 01:05:31,040
La sola afero, kiun mi volis komenti estas ke kiam vi traktas aferojn kiel indeksoj,

794
01:05:31,040 --> 01:05:38,320
vi neniam vere vidi ĉi tion kiam vi skribas por ciklo,

795
01:05:38,320 --> 01:05:41,120
sed teknike, kiam ajn vi pritraktas tiujn indeksoj,

796
01:05:41,120 --> 01:05:45,950
vi devus preskaux cxiam trakti sensigna entjeroj.

797
01:05:45,950 --> 01:05:53,850
La kialo estas, kiam vi pritraktas subskribis entjeroj,

798
01:05:53,850 --> 01:05:56,090
do se vi havas 2 subskribis entjeroj kaj vi aldoni ilin kune

799
01:05:56,090 --> 01:06:00,640
kaj ili finos tro granda, tiam vi finos kun negativa nombro.

800
01:06:00,640 --> 01:06:03,410
Do jen kio entjero superflui estas.

801
01:06:03,410 --> 01:06:10,500
>> Se mi aldonas 2 miliardoj kaj 1 miliardo, mi finas kun negativa 1 miliardo.

802
01:06:10,500 --> 01:06:15,480
Tiel estas kiel entjeroj labori en komputiloj.

803
01:06:15,480 --> 01:06:17,510
Do la problemo kun uzanta -

804
01:06:17,510 --> 01:06:23,500
Tio estas bone krom se malaltaj hazarde estas 2 miliardoj kaj ĝis okazas al esti 1 miliardo,

805
01:06:23,500 --> 01:06:27,120
tiam ĉi tuj estos negativa 1 miliardo kaj poste ni iras al dividi ke per 2

806
01:06:27,120 --> 01:06:29,730
kaj fini kun negativa 500 milionoj.

807
01:06:29,730 --> 01:06:33,760
Do ĉi tiu estas nur afero se vi hazarde estos serĉanta tra tabelo

808
01:06:33,760 --> 01:06:38,070
de miliardoj da aĵoj.

809
01:06:38,070 --> 01:06:44,050
Sed se malaltaj + supren okazas al superflui, tiam tio estas problemo.

810
01:06:44,050 --> 01:06:47,750
Tuj kiam ni faras ilin sensigna, tiam 2 miliardoj plus 1 biliono estas 3 miliardoj.

811
01:06:47,750 --> 01:06:51,960
3 miliardoj dividita per 2 estas 1,5 miliardoj.

812
01:06:51,960 --> 01:06:55,670
Tuj, kiam ili estas sensigna, ĉio estas perfekta.

813
01:06:55,670 --> 01:06:59,900
Kaj tiel tio estas ankaŭ temo kiam vi skribas vian por cikloj,

814
01:06:59,900 --> 01:07:03,940
kaj fakte, ĝi probable faras ĝin aŭtomate.

815
01:07:09,130 --> 01:07:12,330
Ĝi fakte nur krias al vi.

816
01:07:12,330 --> 01:07:21,610
Do, se ĉi tiu numero estas tro granda por esti en nur entjero sed ĝi havis en sensigna entjera,

817
01:07:21,610 --> 01:07:24,970
ĝi krias al Vi, por ke tio neniam vere kuras en la temo.

818
01:07:29,150 --> 01:07:34,820
Vi povas vidi ke indico estas neniam tuj estos negativa,

819
01:07:34,820 --> 01:07:39,220
kaj do kiam vi ripetanta super tabelo,

820
01:07:39,220 --> 01:07:43,970
vi povas preskaŭ ĉiam diri sensigna _int_ i, sed vi ne devas vere.

821
01:07:43,970 --> 01:07:47,110
Aĵoj iras labori preskaux same bone.

822
01:07:48,740 --> 01:07:50,090
Okay. [Flustras] Kioma horo estas?

823
01:07:50,090 --> 01:07:54,020
La lasta afero mi volis montri - kaj mi nur faras vere rapida.

824
01:07:54,020 --> 01:08:03,190
Vi scias, kiel ni # difini por ke ni povu # difini MAX kiel 5 aŭ ion?

825
01:08:03,190 --> 01:08:05,940
Ni ne faru MAX. # Difini ligita kiel 200. Tion ni faris antaŭe.

826
01:08:05,940 --> 01:08:10,380
Kiu difinas konstanta, kiu estas ĝuste tuj estos kopiitaj kaj pasted

827
01:08:10,380 --> 01:08:13,010
kien ajn ni hazarde skribi baro.

828
01:08:13,010 --> 01:08:18,189
>> Do ni povas efektive fari pli kun # difinu.

829
01:08:18,189 --> 01:08:21,170
Ni povas difini # funkcioj.

830
01:08:21,170 --> 01:08:23,410
Ili estas ne vere funkcias, sed ni vokos ilin funkcioj.

831
01:08:23,410 --> 01:08:36,000
Ekzemplo estus iu kiel MAX (x, y) estas difinita kiel (x <y? Y: x). Okay.

832
01:08:36,000 --> 01:08:40,660
Do vi devus alkutimiĝi al triargumenta operatoro sintakso,

833
01:08:40,660 --> 01:08:49,029
sed estas x malpli ol y? Reveno y, alie redoni x.

834
01:08:49,029 --> 01:08:54,390
Do vi povas vidi vi povas fari ĉi apartan funkcion,

835
01:08:54,390 --> 01:09:01,399
kaj la funkcio povus esti kiel bool MAX prenas 2 argumentojn, revenu ĉi.

836
01:09:01,399 --> 01:09:08,340
Tiu estas unu el la plej komunaj mi vidas farita kiel ĉi tio. Ni nomas ilin makrooj.

837
01:09:08,340 --> 01:09:11,790
Tio ĉi estas makro.

838
01:09:11,790 --> 01:09:15,859
Tiu estas ĝuste la sintakson por ĝi.

839
01:09:15,859 --> 01:09:18,740
Vi povas skribi makroo fari kion ajn vi volas.

840
01:09:18,740 --> 01:09:22,649
Vi ofte vidas makrooj por elpurigi printfs kaj aĵoj.

841
01:09:22,649 --> 01:09:29,410
Do tipo de printf, estas specialaj konstantaj en C kiel substreki LINIO substreki,

842
01:09:29,410 --> 01:09:31,710
2 substrekoj LINIO substreki,

843
01:09:31,710 --> 01:09:37,550
kaj ekzistas ankaŭ mi opinias 2 substrekoj func. Tio povus esti ĝin. Io simila.

844
01:09:37,550 --> 01:09:40,880
Tiuj aĵoj estos anstataŭita per la nomo de la funkcio

845
01:09:40,880 --> 01:09:42,930
aŭ la numeron de la linio kiu vi estas plu.

846
01:09:42,930 --> 01:09:48,630
Ofte, vi skribas elpurigante printfs ke cxi tie mi povis tiam ĝuste skribi

847
01:09:48,630 --> 01:09:54,260
Debug kaj estos presi la numero de linio kaj funkcio, kiun mi hazarde estas en

848
01:09:54,260 --> 01:09:57,020
ke renkontita, ke debug komunikaĵo.

849
01:09:57,020 --> 01:09:59,550
Kaj vi povas ankaŭ printi aliaj aĵoj.

850
01:09:59,550 --> 01:10:05,990
Do unu afero vi devus rigardi eksteren por estas, se mi hazarde # difini DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
kiel iu kiel 2 * y kaj 2 * x.

852
01:10:11,380 --> 01:10:14,310
Do ial ajn vi hazarde fari tion tre.

853
01:10:14,310 --> 01:10:16,650
Do fari macro.

854
01:10:16,650 --> 01:10:18,680
Ĉi tiu estas efektive rompitaj.

855
01:10:18,680 --> 01:10:23,050
Mi nomos ĝin faras ion kiel DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Do kion devus esti revenis?

857
01:10:28,840 --> 01:10:30,580
[Studento] 12.

858
01:10:30,580 --> 01:10:34,800
Jes, 12 estu revenis, kaj 12 estas redonita.

859
01:10:34,800 --> 01:10:43,350
3 gets anstataŭis por x, 6 gets anstataŭis por y, kaj ni revenu 2 * 6, kiu estas 12.

860
01:10:43,350 --> 01:10:47,710
Nun kio pri tio? Kio devus revenis?

861
01:10:47,710 --> 01:10:50,330
[Studento] 14. >> Ideale, 14.

862
01:10:50,330 --> 01:10:55,290
La temo estas tio kiom hash difinas laboron, memoru ĝi estas laŭvorta kopio kaj pasto

863
01:10:55,290 --> 01:11:00,160
de preskaux cxion, do kion ĉi tuj esti interpretita kiel

864
01:11:00,160 --> 01:11:11,270
estas 3 malpli ol 1 plus 6, 2 fojoj 1 plus 6, 2 fojoj 3.

865
01:11:11,270 --> 01:11:19,780
>> Do tial vi preskaŭ ĉiam envolver ĉiu en krampoj.

866
01:11:22,180 --> 01:11:25,050
Neniu variablo vi preskaŭ ĉiam envolver en krampoj.

867
01:11:25,050 --> 01:11:29,570
Estas kazoj kie oni ne devas, kiel mi scias, ke mi ne bezonas fari tion ĉi tie

868
01:11:29,570 --> 01:11:32,110
ĉar malpli ol estas preskaux cxiam nur irante labori,

869
01:11:32,110 --> 01:11:34,330
kvankam tio eble ne eĉ esti vera.

870
01:11:34,330 --> 01:11:41,870
Se estas iu ridinda kiel DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
tiam tiu tuj get anstataŭis kun 3 malpli ol 1 egalas egalas 2,

872
01:11:49,760 --> 01:11:53,460
kaj tiel tiam tuj faros 3 malpli ol 1, ĉu tio egala 2,

873
01:11:53,460 --> 01:11:55,620
kio ne estas, kion ni volas.

874
01:11:55,620 --> 01:12:00,730
Do, por eviti ajnan operatoro prioritaton problemoj,

875
01:12:00,730 --> 01:12:02,870
ĉiam envolver en krampoj.

876
01:12:03,290 --> 01:12:07,700
Okay. Kaj tio estas ĝi, 5:30.

877
01:12:08,140 --> 01:12:12,470
Se vi havas demandojn pri la pset, ni sciis.

878
01:12:12,470 --> 01:12:18,010
Ĝi devus esti amuza, kaj la hacker eldono ankaŭ estas multe pli realisma

879
01:12:18,010 --> 01:12:22,980
ol la hacker eldono de la pasinta jaro, do ni esperas ke multaj el vi provu ĝin.

880
01:12:22,980 --> 01:12:26,460
Pasinta jaro estis tre blindiga.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]