1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Sezzjoni 3 - aktar komdi]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Università ta 'Harvard]

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

4
00:00:07,310 --> 00:00:12,700
>> Allura l-ewwel domanda hija fformulata stramba.

5
00:00:12,700 --> 00:00:17,480
GDB ihallik "debug" programm, iżda, b'mod aktar speċifiku, dak ma let inti tagħmel?

6
00:00:17,480 --> 00:00:22,590
I ser tingħata risposta għal din waħda, u jien ma nafx x'inhu eżattament mistenni,

7
00:00:22,590 --> 00:00:27,910
hekk jien guessing huwa xi ħaġa fuq il-linji ta ihallik pass pass

8
00:00:27,910 --> 00:00:31,540
jimxu permezz tal-programm, jinteraġixxu ma 'dan, varjabbli bidla, tagħmel dawn l-affarijiet -

9
00:00:31,540 --> 00:00:34,270
bażikament kompletament kontroll eżekuzzjoni ta 'programm

10
00:00:34,270 --> 00:00:38,410
u jispezzjona kull parti partikolari tan-esekuzzjoni tal-programm.

11
00:00:38,410 --> 00:00:43,030
Allura dawk il-karatteristiċi tavżak debug affarijiet.

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

13
00:00:44,830 --> 00:00:50,520
Għaliex ma tfittxija binarju jeħtieġu li l-firxa tiġi riżolta?

14
00:00:50,520 --> 00:00:53,360
Min jixtieq li tingħata risposta għal din?

15
00:00:56,120 --> 00:01:00,070
[Student] Minħabba li ma jaħdimx jekk ma jkunx magħżula. >> Yeah. [Daħk]

16
00:01:00,070 --> 00:01:04,910
Jekk huwa ma jintgħażlux, allura huwa impossibbli li jaqsam min-nofs

17
00:01:04,910 --> 00:01:07,850
u jafu li kollox lejn ix-xellug huwa inqas u kollox lejn il-lemin

18
00:01:07,850 --> 00:01:10,490
huwa akbar mill-valur medju.

19
00:01:10,490 --> 00:01:12,790
Għalhekk jeħtieġ li jiġu magħżula.

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

21
00:01:14,170 --> 00:01:17,570
Għaliex huwa tip bużżieqa fil O ta 'n kwadrat?

22
00:01:17,570 --> 00:01:23,230
Hawn xi ħadd l-ewwel trid tagħti malajr ħafna ta 'livell għoli ħarsa ġenerali ta' dak it-tip bużżieqa hu?

23
00:01:25,950 --> 00:01:33,020
[Student] Inti bażikament jmorru permezz ta 'kull element u inti tiċċekkja l-elementi ewwel ftit.

24
00:01:33,020 --> 00:01:37,150
Jekk dawn qed barra ta 'fejn inti tpartit lilhom, allura inti tiċċekkja l-elementi li ġejjin u l-bqija.

25
00:01:37,150 --> 00:01:40,770
Meta inti jilħqu t-tmiem, imbagħad inti taf li l-ikbar element jitqiegħed fl-aħħar,

26
00:01:40,770 --> 00:01:42,750
sabiex inti jinjora li wieħed imbagħad inti żżomm fuq għaddejjin,

27
00:01:42,750 --> 00:01:48,490
u kull darba li inti għandek tiċċekkja element wieħed inqas sakemm inti tagħmel l-ebda tibdil. >> Yeah.

28
00:01:48,490 --> 00:01:58,470
Huwa sejjaħ tip bużżieqa għaliex jekk inti flip-firxa fuq il-ġenb tiegħu hekk huwa u 'l isfel, vertikali,

29
00:01:58,470 --> 00:02:03,100
il-valuri kbar se sink mal-qiegħ u l-valuri żgħar se buzzieqa sal-quċċata.

30
00:02:03,100 --> 00:02:05,210
Li kif ltqajna l-isem tagħha.

31
00:02:05,210 --> 00:02:08,220
U yeah, inti biss jgħaddu.

32
00:02:08,220 --> 00:02:11,190
Inti żżomm għaddejja l-array, jagħmlu skambju ta 'l-akbar valur

33
00:02:11,190 --> 00:02:14,040
biex jiksbu l-valuri akbar mal-qiegħ.

34
00:02:14,040 --> 00:02:17,500
>> Għaliex huwa O ta 'n kwadrat?

35
00:02:18,690 --> 00:02:24,620
L-ewwel, ħadd ma jridu jgħidu għaliex huwa O ta 'n kwadrat?

36
00:02:24,620 --> 00:02:28,760
[Student] Minħabba għal kull ġirja tmur n darbiet.

37
00:02:28,760 --> 00:02:32,100
Inti tista 'biss tkun żgur li ħadt l-element akbar it-triq kollha,

38
00:02:32,100 --> 00:02:35,230
imbagħad inti għandek jirrepetu li għal kemm ħafna elementi. >> Yeah.

39
00:02:35,230 --> 00:02:41,800
Allura wieħed iżomm f'moħħu dak big O mezzi u dak li tfisser Omega kbar.

40
00:02:41,800 --> 00:02:50,560
Il O big huwa bħall-upper marbuta fuq kif bil-mod li jista 'tmexxi effettivament.

41
00:02:50,560 --> 00:02:58,990
Allura billi qal O huwa n kwadrat, mhuwiex O ta 'n jew inkella jkun kapaċi li jimxu

42
00:02:58,990 --> 00:03:02,640
fil-ħin lineari, iżda huwa O ta 'n kubiku

43
00:03:02,640 --> 00:03:06,390
minħabba li hija limitata bir O ta 'n kubiku.

44
00:03:06,390 --> 00:03:12,300
Jekk huwa mdawwar bil O ta 'n kwadrat, allura huwa tmiss wkoll mill n kubiku.

45
00:03:12,300 --> 00:03:20,280
Għalhekk huwa n kwadrat, u fil-każ assoluta agħar ma tistax tagħmel aħjar minn n kwadrat,

46
00:03:20,280 --> 00:03:22,830
li hija għaliex huwa O ta 'n kwadru.

47
00:03:22,830 --> 00:03:31,200
Allura biex tara matematika żgħir lejn kif niġu biex tkun n kwadrat,

48
00:03:31,200 --> 00:03:40,530
jekk għandna ħames affarijiet fil-lista tagħna, l-ewwel darba kemm swaps nistgħu potenzjalment bżonn li jagħmlu

49
00:03:40,530 --> 00:03:47,170
sabiex tikseb dan? Ejja attwalment biss -

50
00:03:47,170 --> 00:03:52,040
Kemm tpartit aħna se jkollhom jagħmlu fl-ewwel ġirja tal sort bużżieqa permezz tal-firxa?

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

52
00:03:53,540 --> 00:03:58,340
>> Jekk ikun hemm 5 elementi, aħna qed tmur biex jeħtieġu jagħmlu n - 1.

53
00:03:58,340 --> 00:04:01,100
Imbagħad fuq it-tieni waħda kemm swaps huma aħna se jkollhom jagħmlu?

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

55
00:04:03,440 --> 00:04:11,640
U t-tielet se tkun n - 3, u mbagħad għall-konvenjenza I se jikteb l-aħħar tnejn

56
00:04:11,640 --> 00:04:15,270
kif allura aħna qed tmur għall-ħtieġa li tagħmel 2 tpartit u 1 tpartit.

57
00:04:15,270 --> 00:04:19,899
I raden l-aħħar wieħed jistgħu jew ma jistgħux attwalment ħtieġa li jiġri.

58
00:04:19,899 --> 00:04:22,820
Huwa ta 'swap? I do not know.

59
00:04:22,820 --> 00:04:26,490
Allura dawn huma l-ammonti totali ta 'swaps jew inqas paraguni għandek tagħmel.

60
00:04:26,490 --> 00:04:29,910
Anki jekk inti ma tpartit, inti xorta jkollok bżonn biex tqabbel il-valuri.

61
00:04:29,910 --> 00:04:33,910
Allura hemm n - 1 tqabbil fl-ewwel ġirja permezz tal-firxa.

62
00:04:33,910 --> 00:04:42,050
Jekk inti rranġati mill-ġdid dawn l-affarijiet, ejja tagħmel attwalment minnu sitt affarijiet affarijiet munzell up nicely,

63
00:04:42,050 --> 00:04:44,790
u mbagħad I ser tagħmel 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Hekk biss titranġa dawn is-somom, irridu naraw kemm paraguni nagħmlu

65
00:04:49,910 --> 00:04:52,700
fil-algoritmu kollu.

66
00:04:52,700 --> 00:04:56,550
Allura jekk aħna idaħħlu dawn guys stabbiliti hawn,

67
00:04:56,550 --> 00:05:07,470
allura aħna qed għadhom biss jingħaddu l-paraguni madankollu ħafna kien hemm.

68
00:05:07,470 --> 00:05:13,280
Imma jekk aħna qosor dawn u aħna qosor dawn u aħna qosor dawn,

69
00:05:13,280 --> 00:05:18,130
huwa għadu l-istess problema. Aħna biss is-somma dawk il-gruppi partikolari.

70
00:05:18,130 --> 00:05:22,400
>> Allura issa aħna qed jingħaddu 3 ta n. Huwa mhux biss 3 s n.

71
00:05:22,400 --> 00:05:27,650
Huwa dejjem se jkunu n / 2 tal-n.

72
00:05:27,650 --> 00:05:29,430
Allura hawnhekk għandna jiġri li jkollhom 6.

73
00:05:29,430 --> 00:05:34,830
Jekk kellna 10 affarijiet, allura stajna nagħmlu dan il-grupp għal 5 pari differenti ta 'affarijiet

74
00:05:34,830 --> 00:05:37,180
u tispiċċa bil n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Allura int dejjem se tikseb n / 2 tal-n, u għalhekk dan aħna ser LOGHOME out għal n kwadrat / 2.

76
00:05:45,840 --> 00:05:48,890
U għalhekk anki jekk huwa l-fattur ta 'nofs, li jiġri li jaqgħu fl-

77
00:05:48,890 --> 00:05:54,190
minħabba l-fatt li permezz ta 'kull iterazzjoni fuq il-firxa inqabblu 1 inqas

78
00:05:54,190 --> 00:05:58,040
b'tali mod li l-mod kif nagħmlu l-aktar minn 2, iżda xorta huwa n kwadru.

79
00:05:58,040 --> 00:06:01,650
Aħna ma jimpurtahom dwar il-fattur kostanti ta 'nofs.

80
00:06:01,650 --> 00:06:07,760
Allura ħafna ta 'O għalf kbar bħal din tistrieħ fuq biss tip ta' kif isir dan it-tip ta 'matematika,

81
00:06:07,760 --> 00:06:12,260
jagħmlu somom aritmetika u l-għalf serje ġeometrika,

82
00:06:12,260 --> 00:06:17,750
iżda ħafna minnhom f'dan il-kors huma pjuttost sempliċi.

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

84
00:06:19,290 --> 00:06:24,430
Għaliex huwa tip inserzjoni fl-Omega n? X'tagħmel omega jfisser?

85
00:06:24,430 --> 00:06:27,730
[2 istudenti jitkellmu f'daqqa - mhux intelliġibbli] Yeah >>.

86
00:06:27,730 --> 00:06:30,630
Omega inti tista 'taħseb bħala l-aktar baxx marbut.

87
00:06:30,630 --> 00:06:36,550
>> Allura l-ebda kwistjoni kif effiċjenti algoritmu tiegħek tip inserzjoni hija,

88
00:06:36,550 --> 00:06:41,810
irrispettivament mill-lista li l-għadda fi, dejjem irid iqabbel l-inqas n affarijiet

89
00:06:41,810 --> 00:06:44,620
jew għandu jtenni fuq affarijiet n.

90
00:06:44,620 --> 00:06:47,280
Għaliex huwa li?

91
00:06:47,280 --> 00:06:51,190
[Student] Minħabba li jekk il-lista hija diġà magħżula, imbagħad permezz l-ewwel iterazzjoni

92
00:06:51,190 --> 00:06:54,080
inti tista 'biss tiggarantixxi li l-element ewwel huwa l-inqas,

93
00:06:54,080 --> 00:06:56,490
u l-tieni iterazzjoni inti tista 'biss jiggarantixxu l-ewwel tnejn huma

94
00:06:56,490 --> 00:07:00,010
għaliex inti ma taf li l-bqija tal-lista hija magħżula. >> Yeah.

95
00:07:00,010 --> 00:07:08,910
Jekk inti tgħaddi f'lista kompletament magħżula, għall-inqas ikollok tmur fuq l-elementi kollha

96
00:07:08,910 --> 00:07:12,180
biex tara li xejn jeħtieġ li jiġu mċaqalqa madwar.

97
00:07:12,180 --> 00:07:14,720
Allura tgħaddi minn fuq il-lista u qal oh, dan diġà magħżula,

98
00:07:14,720 --> 00:07:18,240
huwa impossibbli li tkun taf huwa magħżul sakemm inti tiċċekkja kull element

99
00:07:18,240 --> 00:07:20,660
biex tara li dawn huma fl-ordni magħżula.

100
00:07:20,660 --> 00:07:25,290
Allura l-aktar baxx marbut fuq tip inserzjoni huwa Omega ta 'n.

101
00:07:25,290 --> 00:07:28,210
X'hemm l-agħar każ running time ta 'tip jingħaqdu,

102
00:07:28,210 --> 00:07:31,390
agħar każ hija O kbar mill-ġdid?

103
00:07:31,390 --> 00:07:37,660
Allura fil-agħar każ, kif ma sort jingħaqdu run?

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

105
00:07:43,690 --> 00:07:49,990
L-algoritmi aktar mgħaġġla issortjar ġenerali huma n log n. Inti ma tistax tagħmel aħjar.

106
00:07:51,930 --> 00:07:55,130
>> Hemm każijiet speċjali, u jekk ikollna ħin llum - iżda aħna probabbilment won't -

107
00:07:55,130 --> 00:07:59,330
nistgħu naraw dak li ma aħjar minn n log n.

108
00:07:59,330 --> 00:08:04,050
Iżda fil-każ ġenerali, inti ma tistax tagħmel aħjar minn n log n.

109
00:08:04,050 --> 00:08:09,680
U jingħaqdu tip jiġri li jkun il-wieħed inti għandek tkun taf għal dan il-kors li hu n log n.

110
00:08:09,680 --> 00:08:13,260
U hekk aħna ser ikunu fil-fatt jimplimentaw dik llum.

111
00:08:13,260 --> 00:08:18,070
U fl-aħħarnett, f'mhux aktar minn tliet sentenzi, kif jaħdem it-tip ta 'għażla?

112
00:08:18,070 --> 00:08:20,370
Ma xi ħadd tixtieq li tingħata risposta, u jien ser joqgħod sentenzi tiegħek

113
00:08:20,370 --> 00:08:22,390
għaliex jekk inti tmur fuq 3 -

114
00:08:25,530 --> 00:08:28,330
Hawn xi ħadd ftakar sort għażla?

115
00:08:31,280 --> 00:08:37,809
Sort Għażla normalment huwa pjuttost faċli biex tiftakar ftit mill-isem.

116
00:08:37,809 --> 00:08:45,350
Inti biss ttenni fuq il-firxa, isibu ikun x'ikun l-akbar valur huwa jew iżgħar -

117
00:08:45,350 --> 00:08:47,290
tkun xi ordni int issortjar pulzieri

118
00:08:47,290 --> 00:08:50,750
Mela ejja ngħidu aħna qed issortjar minn iżgħar sa l-akbar.

119
00:08:50,750 --> 00:08:55,250
Inti ttenni fuq il-firxa, ifittxu ikun x'ikun l-element minimu huwa,

120
00:08:55,250 --> 00:08:59,750
tagħżel hija, u mbagħad biss tpartit huwa dak kollu li huwa fl-ewwel post.

121
00:08:59,750 --> 00:09:04,090
U mbagħad fuq il-pass 2 fuq il-firxa, tfittex l-element minimu mill-ġdid,

122
00:09:04,090 --> 00:09:07,490
tagħżel hija, u mbagħad tpartit ma 'dak fil-pożizzjoni 2.

123
00:09:07,490 --> 00:09:10,650
Allura aħna biss picking u jagħżlu l-valuri minimi

124
00:09:10,650 --> 00:09:16,050
u dawn jiddaħħlu fil-faċċata tal-array sakemm huwa magħżul.

125
00:09:19,210 --> 00:09:21,560
Mistoqsijiet dwar li?

126
00:09:21,560 --> 00:09:25,710
>> Dawn inevitabbilment jidhru fil-forom ikollok biex jimlew meta int tissottometti l-pset.

127
00:09:29,010 --> 00:09:32,360
Dawk huma bażikament l-tweġibiet għal dawk.

128
00:09:32,360 --> 00:09:34,230
Okay, hekk issa kodifikazzjoni problemi.

129
00:09:34,230 --> 00:09:40,140
I diġà bagħtet matul email - Did ħadd ma nikseb li email? Okay.

130
00:09:40,140 --> 00:09:46,630
I diġà bagħtet fuq email-ispazju li aħna qed tmur biex tkun qed tuża,

131
00:09:46,630 --> 00:09:52,120
u jekk tikklikkja fuq isem tiegħi - hekk naħseb jien ser tkun fil-qiegħ

132
00:09:52,120 --> 00:09:57,170
minħabba lr lura - imma jekk tikklikkja fuq isem tiegħi tkun taf tara 2 reviżjonijiet.

133
00:09:57,170 --> 00:10:02,650
Reviżjoni 1 se tkun diġà I kkupjati u pasted l-kodiċi fis Spazji

134
00:10:02,650 --> 00:10:06,900
għall-ħaġa tiftix int ser jkollhom jimplimentaw.

135
00:10:06,900 --> 00:10:10,540
U Reviżjoni 2 se jkun il-ħaġa tip li nimplimentaw wara dik.

136
00:10:10,540 --> 00:10:15,770
Allura inti tista 'tikklikkja fuq Reviżjoni tiegħi 1 u jaħdmu minn hemm.

137
00:10:17,350 --> 00:10:22,060
U issa irridu li jimplimentaw tfittxija binarja.

138
00:10:22,060 --> 00:10:26,470
>> Hawn xi ħadd jridux biss jagħtu pseudocode ta 'livell għoli spjegazzjoni

139
00:10:26,470 --> 00:10:31,440
ta 'dak li aħna qed tmur biex ikollhom jagħmlu għall-tiftix? Yeah.

140
00:10:31,440 --> 00:10:36,170
[Student] Inti biss tieħu l-nofs tal-firxa u ara jekk dak li qed tfittex

141
00:10:36,170 --> 00:10:38,650
huwa inqas minn dak jew aktar minn dak.

142
00:10:38,650 --> 00:10:41,080
U jekk huwa inqas, inti tmur għall-nofs li l-anqas,

143
00:10:41,080 --> 00:10:44,750
u jekk huwa aktar, inti tmur man-nofs li l-aktar u inti irrepeti li sakemm inti biss tikseb wieħed ħaġa.

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

145
00:10:46,570 --> 00:10:51,320
Avviż li n-numri firxa tagħna huwa diġà magħżula,

146
00:10:51,320 --> 00:10:57,190
u sabiex dan ifisser li nistgħu nieħdu vantaġġ ta 'dan u nistgħu ewwel jivverifika,

147
00:10:57,190 --> 00:11:00,390
okay, jien infittxu l-għadd 50.

148
00:11:00,390 --> 00:11:03,720
So I tista 'tmur fil-nofs.

149
00:11:03,720 --> 00:11:07,380
Nofsani huwa diffiċli li jiġu ddefiniti meta huwa anke numru ta 'affarijiet,

150
00:11:07,380 --> 00:11:10,820
imma ejja biss jgħidu aħna ser dejjem truncate l-nofs.

151
00:11:10,820 --> 00:11:14,420
Allura hawnhekk għandna 8 affarijiet, sabiex il-middle ikun 16.

152
00:11:14,420 --> 00:11:17,330
I infittex 50, hekk 50 huwa akbar minn 16.

153
00:11:17,330 --> 00:11:21,310
Allura issa I jistgħu bażikament jittrattaw firxa tiegħi bħala dawn l-elementi.

154
00:11:21,310 --> 00:11:23,450
I tista tarmi l bogħod kollox mill-16 fuq.

155
00:11:23,450 --> 00:11:27,440
Issa firxa tiegħi huwa biss dawn l-elementi 4, u nirrepeti.

156
00:11:27,440 --> 00:11:31,910
Allura mbagħad I jridu jsibu l-nofs mill-ġdid, li se tkun 42.

157
00:11:31,910 --> 00:11:34,730
42 huwa anqas minn 50, so I tista tarmi l bogħod dawn iż-żewġ elementi.

158
00:11:34,730 --> 00:11:36,890
Dan huwa array li jifdal tiegħi.

159
00:11:36,890 --> 00:11:38,430
Jien ser isibu l-nofs mill-ġdid.

160
00:11:38,430 --> 00:11:42,100
I raden 50 kien eżempju ħażin minħabba I kien dejjem tarmi l-affarijiet lejn ix-xellug,

161
00:11:42,100 --> 00:11:48,280
iżda mill-istess miżura, jekk jien tfittex xi ħaġa

162
00:11:48,280 --> 00:11:52,100
u huwa inqas mill-element jien bħalissa tħares lejn,

163
00:11:52,100 --> 00:11:55,080
allura jien ser tarmi kollox lejn il-lemin.

164
00:11:55,080 --> 00:11:58,150
Allura issa għandna bżonn li jimplimentaw dik.

165
00:11:58,150 --> 00:12:02,310
Avviż li għandna bżonn li tgħaddi fid-daqs.

166
00:12:02,310 --> 00:12:06,730
Nistgħu wkoll ma jeħtiġux li hard-kodiċi ta 'daqs.

167
00:12:06,730 --> 00:12:11,640
Allura jekk aħna teħles minn dik # jiddefinixxu -

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

169
00:12:21,430 --> 00:12:27,180
Kif nista nicely ċifra barra dak id-daqs tal-array numri bħalissa hu?

170
00:12:27,180 --> 00:12:30,950
>> Kemm l-elementi huma fil-firxa numri?

171
00:12:30,950 --> 00:12:33,630
[Student] Numri, brazzi,. Tul?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Dan ma jeżistix fil C.

173
00:12:36,600 --> 00:12:38,580
Ħtieġa. Tul.

174
00:12:38,580 --> 00:12:42,010
Arrays m'għandhomx proprjetajiet, b'hekk m'hemm l-ebda proprjetà tul ta 'arrays

175
00:12:42,010 --> 00:12:45,650
li se biss jagħtik madankollu żmien li jiġri li jkun.

176
00:12:48,180 --> 00:12:51,620
[Student] Ara kemm memorja huwa għandu u iddividi kemm - Yeah. >>

177
00:12:51,620 --> 00:12:55,810
Allura kif nistgħu tara kemm memorja li tkun? >> [Student] Sizeof. >> Yeah, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof huwa l-operatur li għaddej biex jirritorna l-daqs tal-array numri.

179
00:13:01,680 --> 00:13:10,060
U li għaddej biex jiġu interi madankollu ħafna hemm darbiet id-daqs ta 'numru sħiħ

180
00:13:10,060 --> 00:13:14,050
peress li l-kemm memorja huwa attwalment bidu.

181
00:13:14,050 --> 00:13:17,630
Mela jekk irrid in-numru ta 'affarijiet fil-firxa,

182
00:13:17,630 --> 00:13:20,560
allura jien ser jridu iddividi-daqs ta 'numru sħiħ.

183
00:13:22,820 --> 00:13:26,010
Okay. Allura li tikri me jgħaddu fid-daqs hawnhekk.

184
00:13:26,010 --> 00:13:29,430
Għaliex għandi bżonn li tgħaddi fid-daqs fil-livelli kollha?

185
00:13:29,430 --> 00:13:38,570
Għaliex ma nistax nara biss tagħmel up here daqs int = sizeof (haystack) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Għaliex ma dan ma taħdimx?

187
00:13:41,490 --> 00:13:44,470
[Student] Mhuwiex varjabbli globali.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack jeżisti u aħna qed jgħaddi f'numri kif haystack,

189
00:13:51,540 --> 00:13:54,700
u dan huwa tip ta 'foreshadowing ta' x'inhu li ġejjin. Yeah.

190
00:13:54,700 --> 00:14:00,170
[Istudent] Haystack huwa biss ir-referenza għaliha, u għalhekk se jerġa 'lura kemm hu kbir dan ir-referenza.

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

192
00:14:02,150 --> 00:14:09,000
I dubju fir lecture li inti stajt tidher l-munzell għadhom verament, id-dritt?

193
00:14:09,000 --> 00:14:11,270
Imxejna biss mitkellma dwar dan.

194
00:14:11,270 --> 00:14:16,090
Allura l-munzell huwa fejn kollha ta 'varjabbli tiegħek ser jiġu maħżuna.

195
00:14:16,090 --> 00:14:19,960
>> Kull memorja li s allokat għal varjazzjonijiet lokali sejra fid-munzell,

196
00:14:19,960 --> 00:14:24,790
u kull funzjoni gets spazju tagħha stess fuq il-munzell, il-qafas tagħha stess munzell huwa dak li sejjaħ.

197
00:14:24,790 --> 00:14:31,590
Allura prinċipali għandha qafas munzell tagħha, u ġewwa ta 'dan huwa ser jeżistu f'dan firxa numri,

198
00:14:31,590 --> 00:14:34,270
u li għaddej biex tkun ta 'sizeof daqs (numri).

199
00:14:34,270 --> 00:14:38,180
Huwa ser ikollhom daqs ta 'numri diviż skond id-daqs ta' elementi,

200
00:14:38,180 --> 00:14:42,010
iżda li l-ħajja fi ħdan il-qafas munzell prinċipali tal.

201
00:14:42,010 --> 00:14:45,190
Meta nitolbu tfittxija, tfittxija gets frejm tagħha munzell stess,

202
00:14:45,190 --> 00:14:48,840
ispazju tagħha stess taħżen kollha ta 'varjabbli lokali tiegħu.

203
00:14:48,840 --> 00:14:56,420
Iżda dawn l-argumenti - sabiex haystack mhux kopja ta 'din il-firxa sħiħa.

204
00:14:56,420 --> 00:15:00,990
Aħna ma jgħaddu fil-firxa sħiħa bħala kopja fl-tfittxija.

205
00:15:00,990 --> 00:15:04,030
Hija biss tgħaddi referenza għal dak array.

206
00:15:04,030 --> 00:15:11,470
Allura tfittxija tista 'aċċess dawn in-numri ta' referenza permezz ta 'dan.

207
00:15:11,470 --> 00:15:17,100
Huwa għadu aċċess għall-affarijiet li jgħixu ġewwa tal-qafas munzell prinċipali, il-

208
00:15:17,100 --> 00:15:22,990
imma bażikament, meta irridu jiksbu l pointers, li għandu jkun malajr,

209
00:15:22,990 --> 00:15:24,980
dan huwa dak pointers huma.

210
00:15:24,980 --> 00:15:29,400
Pointers huma biss referenzi għal affarijiet, u tista 'tuża indikaturi għall-aċċess affarijiet

211
00:15:29,400 --> 00:15:32,030
li huma frames munzell affarijiet oħra ".

212
00:15:32,030 --> 00:15:37,660
Allura anke jekk in-numri hija lokali għal main, aħna xorta jistgħu jkollhom aċċess għaliha permezz ta 'dan pointer.

213
00:15:37,660 --> 00:15:41,770
Iżda peress li huwa biss pointer u huwa biss ta 'referenza,

214
00:15:41,770 --> 00:15:45,040
sizeof (haystack) jirritorna d-daqs tar-referenza innifsu.

215
00:15:45,040 --> 00:15:47,950
Ma lura id-daqs tal-ħaġa huwa li tipponta lejn.

216
00:15:47,950 --> 00:15:51,110
Hija ma jirritorna l-daqs attwali ta 'numri.

217
00:15:51,110 --> 00:15:55,660
U hekk dan mhux sejjer jaħdem kif aħna tixtieq li.

218
00:15:55,660 --> 00:15:57,320
>> Mistoqsijiet dwar li?

219
00:15:57,320 --> 00:16:03,250
Pointers se tkun marret fi f'aktar dettall sinifikament aktar rija fil-ġimgħat li ġejjin.

220
00:16:06,750 --> 00:16:13,740
U dan huwa għaliex ħafna affarijiet li tara, affarijiet tat-tiftix aktar jew affarijiet sort,

221
00:16:13,740 --> 00:16:16,990
dawn qed kważi kollha ser ikollok bżonn tieħu l-daqs attwali tal-firxa,

222
00:16:16,990 --> 00:16:20,440
minħabba fis-C, aħna għandna ebda idea x'inhi l-daqs tal-array huwa.

223
00:16:20,440 --> 00:16:22,720
Ikollok bżonn li manwalment jgħaddu hija pulzieri

224
00:16:22,720 --> 00:16:27,190
U inti ma tistax manwalment jgħaddu fil-firxa sħiħa għax int biss tgħaddi fir-referenza

225
00:16:27,190 --> 00:16:30,390
u hija ma tistax tikseb id-daqs mir-referenza.

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

227
00:16:32,300 --> 00:16:38,160
Allura issa rridu li jimplimentaw dak li kien spjegat qabel.

228
00:16:38,160 --> 00:16:41,530
Tista 'taħdem fuq dan għal minuta,

229
00:16:41,530 --> 00:16:45,250
u inti ma għandekx għalfejn tinkwieta dwar jkollna kollox perfettament 100% tax-xogħol.

230
00:16:45,250 --> 00:16:51,410
Just tikteb l-pseudocode nofs għal kif taħseb li għandha taħdem.

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

232
00:16:53,630 --> 00:16:56,350
Ebda ħtieġa biex jiġu kompletament jsir ma 'din s'issa.

233
00:16:56,350 --> 00:17:02,380
Iżda ħadd ma jħossuhom komdi ma 'dak li s'issa,

234
00:17:02,380 --> 00:17:05,599
bħal xi ħaġa nistgħu naħdmu flimkien?

235
00:17:05,599 --> 00:17:09,690
Hawn xi ħadd jixtiequ jagħmlu volontarjat? Jew I se saltwarjament pick.

236
00:17:12,680 --> 00:17:18,599
Ma għandhom ikunu id-dritt b'xi miżura imma xi ħaġa li nistgħu timmodifika fi stat ta 'ħidma.

237
00:17:18,599 --> 00:17:20,720
[Student] Sure. Okay. >>

238
00:17:20,720 --> 00:17:27,220
Allura tista 'tfaddal-reviżjoni billi tikklikkja fuq l-ikona Save ftit.

239
00:17:27,220 --> 00:17:29,950
Inti Ramya, id-dritt? >> [Student] Yeah. >> [Bowden] Okay.

240
00:17:29,950 --> 00:17:35,140
Allura issa I jista 'jara r-reviżjoni tiegħek u kulħadd jista' pull up-reviżjoni.

241
00:17:35,140 --> 00:17:38,600
U hawn aħna għandna - Okay.

242
00:17:38,600 --> 00:17:43,160
Allura Ramya marru bis-soluzzjoni rikursivi, li huwa definittivament soluzzjoni valida.

243
00:17:43,160 --> 00:17:44,970
Hemm żewġ modi kif inti tista 'tagħmel din il-problema.

244
00:17:44,970 --> 00:17:48,060
Inti tista 'jew tagħmel dan iteratively jew recursively.

245
00:17:48,060 --> 00:17:53,860
Ħafna mill-problemi li inti tiltaqa li jista 'jsir recursively jista' jsir ukoll iteratively.

246
00:17:53,860 --> 00:17:58,510
Allura hawnhekk għandna ghamilt recursively.

247
00:17:58,510 --> 00:18:03,730
>> Ma xi ħadd tixtieq li jiddefinixxu dak li tfisser li tagħmel funzjoni jirrikorri?

248
00:18:07,210 --> 00:18:08,920
[Student] Meta għandek funzjoni sejħa nnifisha

249
00:18:08,920 --> 00:18:13,470
u mbagħad sejħa nnifisha sakemm toħroġ ma 'vera u vera. >> Yeah.

250
00:18:13,470 --> 00:18:17,680
Funzjoni jirrikorri hija biss funzjoni li jitlob huwa stess.

251
00:18:17,680 --> 00:18:24,140
Hemm tliet affarijiet kbar li funzjoni rikursivi għandu jkollu.

252
00:18:24,140 --> 00:18:27,310
L-ewwel huwa ovvjament, hija ssejjaħ lilha nnifisha.

253
00:18:27,310 --> 00:18:29,650
It-tieni huwa l-każ bażi.

254
00:18:29,650 --> 00:18:33,390
Allura f'xi punt l-funzjoni jeħtieġ li tieqaf ssejjaħ lilha nnifisha,

255
00:18:33,390 --> 00:18:35,610
u dan huwa dak l-każ bażi huwa għall.

256
00:18:35,610 --> 00:18:43,860
Allura hawnhekk aħna nafu li aħna għandu jieqaf, għandna jieqfu fit-tfittxija tagħna

257
00:18:43,860 --> 00:18:48,150
meta bidu huwa ugwali għan - u aħna ser jmorru fuq dak li tfisser.

258
00:18:48,150 --> 00:18:52,130
Iżda fl-aħħar, l-aħħar ħaġa li l-importanti għall-funzjonijiet jirrikorri:

259
00:18:52,130 --> 00:18:59,250
il-funzjonijiet għandhom b'xi mod approċċ il-każ bażi.

260
00:18:59,250 --> 00:19:04,140
Bħal jekk int ma fil-fatt aġġornament xejn meta inti tagħmel is-sejħa rikursivi 2,

261
00:19:04,140 --> 00:19:07,880
jekk int litteralment biss li ssejjaħ il-funzjoni mill-ġdid ma 'l-istess argumenti

262
00:19:07,880 --> 00:19:10,130
u l-ebda varjabbli globali nbidlu jew xejn,

263
00:19:10,130 --> 00:19:14,430
int qatt mhi ser tilħaq il-każ bażi, f'liema każ l-ħażina.

264
00:19:14,430 --> 00:19:17,950
Din se tkun recursion infinita u overflow munzell.

265
00:19:17,950 --> 00:19:24,330
Imma hawn naraw li l-aġġornament qed jiġri peress li aħna qed jaġġornaw tibda + tmiem / 2,

266
00:19:24,330 --> 00:19:28,180
aħna qed taġġorna l-argument aħħar hawnhekk, aħna qed taġġorna l-argument bidu hawnhekk.

267
00:19:28,180 --> 00:19:32,860
Għalhekk fl-sejħiet kollha rikursivi aħna aġġornament xi ħaġa. Okay.

268
00:19:32,860 --> 00:19:38,110
Tixtieq li jimxu magħna permezz soluzzjoni tiegħek? >> Sure.

269
00:19:38,110 --> 00:19:44,270
Jien jużaw SearchHelp hekk li kull darba nagħmel din is-sejħa funzjoni

270
00:19:44,270 --> 00:19:47,910
Għandi l-bidu ta 'fejn jien tfittex fil-firxa u t-tmiem

271
00:19:47,910 --> 00:19:49,380
ta 'fejn jien tfittex l-array.

272
00:19:49,380 --> 00:19:55,330
>> F'kull pass fejn huwa qal li huwa l-element tan-nofs, li huwa bidu + tmiem / 2,

273
00:19:55,330 --> 00:19:58,850
hija li daqs dak li aħna qed tfittex?

274
00:19:58,850 --> 00:20:04,650
U jekk huwa, imbagħad sibna, u I raden li gets mgħoddija l-livelli ta 'recursion.

275
00:20:04,650 --> 00:20:12,540
U jekk dan mhux veru, allura aħna tivverifika jekk dak il-valur tan-nofs tal-firxa hija kbira wisq,

276
00:20:12,540 --> 00:20:19,320
f'liema każ aħna nħarsu lejn in-nofs tax-xellug tal-firxa billi tmur mill-bidu sat-indiċi tan-nofs.

277
00:20:19,320 --> 00:20:22,710
U inkella nagħmlu l-nofs aħħar.

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

279
00:20:24,740 --> 00:20:27,730
Li ħsejjes tajba.

280
00:20:27,730 --> 00:20:36,640
Okay, so a koppja affarijiet, u fil-fatt, din hija ħaġa ħafna ta 'livell għoli

281
00:20:36,640 --> 00:20:41,270
li qatt mhu ser ikollok bżonn li tkun taf għal dan il-kors, iżda huwa veru.

282
00:20:41,270 --> 00:20:46,080
Funzjonijiet jirrikorri, inti dejjem tisma li dawn qed ftehim ħażin

283
00:20:46,080 --> 00:20:51,160
għaliex jekk inti recursively sejħa lilek innifsek wisq drabi, ikollok overflow munzell

284
00:20:51,160 --> 00:20:54,990
peress li, kif għidt qabel, kull funzjoni gets frejm tagħha munzell stess.

285
00:20:54,990 --> 00:20:59,500
Allura kull sejħa tal-funzjoni jirrikorri gets frejm tagħha munzell stess.

286
00:20:59,500 --> 00:21:04,140
Mela jekk inti tagħmel sejħiet 1000 rikursivi, ikollok frejms munzell 1000,

287
00:21:04,140 --> 00:21:08,390
u malajr inti twassal biex wara frames wisq munzell u affarijiet biss break.

288
00:21:08,390 --> 00:21:13,480
Allura hu għalhekk li l-funzjonijiet rikursivi huma ġeneralment ħżiena.

289
00:21:13,480 --> 00:21:19,370
Iżda hemm subsett sbieħ ta 'funzjonijiet jirrikorri imsejħa tail-funzjonijiet rikursivi,

290
00:21:19,370 --> 00:21:26,120
u dan jiġri li jkun eżempju ta 'waħda fejn jekk il-kumpilatur avviżi din

291
00:21:26,120 --> 00:21:29,920
u dan għandu, naħseb - fil clang jekk inti tgħaddi din l-O2 bandiera

292
00:21:29,920 --> 00:21:33,250
allura se Avviż dan huwa denb rikursivi u tagħmel l-affarijiet tajba.

293
00:21:33,250 --> 00:21:40,050
>> Se użu mill-ġdid il-qafas munzell istess tul u aktar mill-ġdid għal kull sejħa rikursivi.

294
00:21:40,050 --> 00:21:47,010
U hekk peress li inti qed tuża l-qafas munzell istess, inti m'għandekx bżonn ninkwetaw dwar

295
00:21:47,010 --> 00:21:51,690
qatt munzell overflowing, u fl-istess ħin, bħalek qal qabel,

296
00:21:51,690 --> 00:21:56,380
fejn ladarba inti tirritorna veru, allura għandu jirritorna up kollha ta 'dawn il-frejms munzell

297
00:21:56,380 --> 00:22:01,740
u s-sejħa 10 sa SearchHelp għandha tirritorna lill-9, għandu jirritorna t-8.

298
00:22:01,740 --> 00:22:05,360
Allura li ma għandux bżonn li jiġri meta l-funzjonijiet huma denb rikursivi.

299
00:22:05,360 --> 00:22:13,740
U hekk dak li jagħmel dan denb funzjoni jirrikorri huwa avviż li għal kwalunkwe sejħa għal searchHelp

300
00:22:13,740 --> 00:22:18,470
-sejħa jirrikorri li huwa jagħmel huwa dak li huwa jirritorna.

301
00:22:18,470 --> 00:22:25,290
Għalhekk fl-ewwel sejħa għall-SearchHelp, aħna jew immedjetament jibgħatu lura falza,

302
00:22:25,290 --> 00:22:29,590
immedjatament lura vera, jew nagħmlu sejħa jirrikorri għall SearchHelp

303
00:22:29,590 --> 00:22:33,810
fejn dak li aħna qed jirritornaw huwa dak li sejħa huwa jirritorna.

304
00:22:33,810 --> 00:22:51,560
U aħna ma setgħux jagħmlu dan jekk aħna ma xi ħaġa simili int x = SearchHelp, ritorn x * 2,

305
00:22:51,560 --> 00:22:55,440
biss ftit każwali bidla.

306
00:22:55,440 --> 00:23:01,470
>> Allura issa din is-sejħa rikursivi, dan int x = sejħa SearchHelp rikursivi,

307
00:23:01,470 --> 00:23:05,740
m'għadhiex denb rikursivi għaliex fil-fatt ma jkollhomx għalfejn imorru lura

308
00:23:05,740 --> 00:23:10,400
lura għal qafas munzell ta 'qabel b'tali mod li dik is-sejħa preċedenti għall-funzjoni

309
00:23:10,400 --> 00:23:13,040
tista 'mbagħad tagħmel xi ħaġa bil-valur tar-ritorn.

310
00:23:13,040 --> 00:23:22,190
Allura dan mhux denb rikursivi, imma dak li kellna qabel huwa nicely denb rikursivi. Yeah.

311
00:23:22,190 --> 00:23:27,000
[Student] ma Jekk il-każ bażi tat-tieni jiġu ċċekkjati 1

312
00:23:27,000 --> 00:23:30,640
għaliex jista 'jkun hemm sitwazzjoni fejn meta inti tgħaddi dan l-argument

313
00:23:30,640 --> 00:23:35,770
inti għandek tibda = il-għan, iżda huma l-valur tal-labra.

314
00:23:35,770 --> 00:23:47,310
Il-kwistjoni ma tistax we run fis-każ fejn aħħari huwa l-valur tal-labra

315
00:23:47,310 --> 00:23:52,000
jew jibdew = il-għan, kif xieraq, bidu = tmiem

316
00:23:52,000 --> 00:23:59,480
u int ma attwalment ivverifikat li valur partikolari għadhom,

317
00:23:59,480 --> 00:24:03,910
imbagħad tibda + tarf / 2 huwa biss se tkun l-istess valur.

318
00:24:03,910 --> 00:24:07,890
Imma konna diġà lura foloz u aħna qatt verament ċċekkjati l-valur.

319
00:24:07,890 --> 00:24:14,240
Allura għall-inqas, fl-ewwel sejħa, jekk id-daqs huwa 0, allura aħna rridu li jirritornaw falza.

320
00:24:14,240 --> 00:24:17,710
Iżda jekk id-daqs huwa 1, allura bidu mhux se aħħar ugwali,

321
00:24:17,710 --> 00:24:19,820
u aħna ser jiċċekkja l-inqas l-element wieħed.

322
00:24:19,820 --> 00:24:26,750
Imma naħseb inti dritt f'dak nistgħu jispiċċaw fil-każ fejn tibda + tmiem / 2,

323
00:24:26,750 --> 00:24:31,190
bidu jispiċċa jkun l-istess bħal bidu + tmiem / 2,

324
00:24:31,190 --> 00:24:35,350
imma aħna qatt ma attwalment ċċekkjati dan l-element.

325
00:24:35,350 --> 00:24:44,740
>> Allura jekk aħna l-ewwel jivverifika l-element nofs il-valur aħna qed tfittex,

326
00:24:44,740 --> 00:24:47,110
allura nistgħu immedjatament lura veru.

327
00:24:47,110 --> 00:24:50,740
Else jekk dawn qed ugwali, allura hemm l-ebda punt fil-kontinwazzjoni

328
00:24:50,740 --> 00:24:58,440
peress li aħna qed biss jmorru biex taġġorna għal każ fejn ninsabu fuq firxa waħda element.

329
00:24:58,440 --> 00:25:01,110
Jekk dan l-element waħdieni ma jkunx dak li aħna qed tfittex,

330
00:25:01,110 --> 00:25:03,530
allura kollox huwa ħażin. Yeah.

331
00:25:03,530 --> 00:25:08,900
[Student] Il-ħaġa hija li peress li d-daqs huwa attwalment akbar mill-għadd ta 'elementi fil-firxa,

332
00:25:08,900 --> 00:25:13,070
diġà jkun hemm offset - >> Allura se-daqs -

333
00:25:13,070 --> 00:25:19,380
[Student] Jiġifieri jekk il-firxa kienet daqs 0, allura l-SearchHelp fatt se jiċċekkja haystack ta '0

334
00:25:19,380 --> 00:25:21,490
fuq l-ewwel sejħa.

335
00:25:21,490 --> 00:25:25,300
Il-firxa għandha daqs 0, sabiex il-0 hija - >> Yeah.

336
00:25:25,300 --> 00:25:30,750
Hemm ħaġa oħra li - jista 'jkun tajjeb. Ejja jaħsbu.

337
00:25:30,750 --> 00:25:40,120
Allura jekk il-firxa kienet 10 Elementi u tan-nofs aħna qed tmur biex jivverifikaw huwa indiċi 5,

338
00:25:40,120 --> 00:25:45,700
hekk aħna qed iċċekkjar 5, u ejja ngħidu li l-valur ikun inqas.

339
00:25:45,700 --> 00:25:50,720
Allura aħna qed jitfg kollox bogħod minn 5 'il quddiem.

340
00:25:50,720 --> 00:25:54,030
Allura tibda + tarf / 2 se tkun il-għan il-ġdid tagħna,

341
00:25:54,030 --> 00:25:57,450
hekk yeah, huwa dejjem ser jibqgħu hinn mit-tmiem tal-firxa.

342
00:25:57,450 --> 00:26:03,570
Jekk huwa każ jekk kien saħansitra jew fard, allura aħna se check, jiġifieri, 4,

343
00:26:03,570 --> 00:26:05,770
iżda aħna qed għadhom jitfg bogħod -

344
00:26:05,770 --> 00:26:13,500
So yeah, aħħar huwa dejjem se jkunu lil hinn mill-aħħar attwali ta 'l-array.

345
00:26:13,500 --> 00:26:18,350
Allura l-elementi qegħdin jiffokaw fuq, tarf huwa dejjem se jkun il-wieħed wara dik.

346
00:26:18,350 --> 00:26:24,270
U hekk jekk bidu ma qatt tmiem ugwali, aħna fil-firxa ta 'daqs 0.

347
00:26:24,270 --> 00:26:35,600
>> Il-ħaġa oħra I kienet taħseb hija li aħna aġġornament bidu li tibda + tmiem / 2,

348
00:26:35,600 --> 00:26:44,020
għalhekk dan huwa l-każ li jien trouble wara ma ', fejn tibda + tarf / 2

349
00:26:44,020 --> 00:26:46,820
huwa l-element aħna qed iċċekkjar.

350
00:26:46,820 --> 00:26:58,150
Ejja ngħidu li kellna din array 10-element. Tkun xi tkun.

351
00:26:58,150 --> 00:27:03,250
Allura tibda + tarf / 2 se tkun xi ħaġa bħal dan wieħed,

352
00:27:03,250 --> 00:27:07,060
u jekk dan mhux il-valur, ngħidu aħna rridu li taġġorna.

353
00:27:07,060 --> 00:27:10,060
Il-valur huwa ikbar, hekk aħna tixtieq li tħares lejn dan nofs il-firxa.

354
00:27:10,060 --> 00:27:15,910
Allura kif aħna qed aġġornament bidu, aħna qed taġġorna bidu sa issa jkun dan l-element.

355
00:27:15,910 --> 00:27:23,790
Iżda dan jista 'xorta taħdem, jew għall-inqas, inti tista' tagħmel bidu + tmiem / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Student] Inti ma għandekx bżonn li jiġu jibdew + tmiem [inaudible] >> Yeah.

357
00:27:27,850 --> 00:27:33,240
Aħna diġà ċċekkjati dan l-element u jafu mhuwiex l-waħda aħna qed tfittex.

358
00:27:33,240 --> 00:27:36,800
Allura aħna ma bżonn li jaġġornaw bidu sabiex tkun dan l-element.

359
00:27:36,800 --> 00:27:39,560
Nistgħu biss skip dan u taġġorna jibdew ikunu dan l-element.

360
00:27:39,560 --> 00:27:46,060
U hemm qatt każ, ejja ngħidu, li dan kien il-għan,

361
00:27:46,060 --> 00:27:53,140
hekk imbagħad tibda tkun din, tibda + tmiem / 2 tkun din,

362
00:27:53,140 --> 00:28:00,580
bidu + finali - Yeah, naħseb li jista 'jispiċċa fil-recursion infinita.

363
00:28:00,580 --> 00:28:12,690
Ejja ngħidu huwa biss firxa ta 'daqs 2 jew firxa ta' daqs 1. Naħseb li dan se taħdem.

364
00:28:12,690 --> 00:28:19,490
Allura bħalissa, bidu huwa dan l-element u għan huwa 1 lil hinn minnha.

365
00:28:19,490 --> 00:28:24,110
Allura l-element li aħna qed tmur biex jivverifikaw huwa dan wieħed,

366
00:28:24,110 --> 00:28:29,400
u mbagħad meta aħna aġġornament bidu, aħna qed aġġornament bidu sabiex tkun 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
li se jispiċċaw us lura ma jibda dan l-element tkun.

368
00:28:33,160 --> 00:28:36,210
>> Allura aħna qed iċċekkjar tal-element istess tul u aktar mill-ġdid.

369
00:28:36,210 --> 00:28:43,310
Allura dan huwa l-każ fejn kull sejħa jirrikorri għandu tabilħaqq taġġorna xi ħaġa.

370
00:28:43,310 --> 00:28:48,370
Għalhekk għandna bżonn li nagħmlu bidu + tmiem / 2 + 1, jew inkella hemm każ

371
00:28:48,370 --> 00:28:50,710
fejn aħna mhux qed attwalment aġġornament bidu.

372
00:28:50,710 --> 00:28:53,820
Kulħadd tara li?

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

374
00:28:56,310 --> 00:29:03,860
Ħadd ma jkollu mistoqsijiet dwar din is-soluzzjoni jew kummenti kwalunkwe aktar?

375
00:29:05,220 --> 00:29:10,280
Okay. Hawn xi ħadd li iterattiv soluzzjoni li aħna lkoll nistgħu nħarsu lejn?

376
00:29:17,400 --> 00:29:20,940
Did aħna kollha jagħmlu dan recursively?

377
00:29:20,940 --> 00:29:25,950
Jew ukoll I raden jekk inti miftuħa ont, allura inti jista 'jkollok megħluba waħda preċedenti tiegħek.

378
00:29:25,950 --> 00:29:28,810
Ma awtomatikament jiffranka? Jien ma pożittiv.

379
00:29:35,090 --> 00:29:39,130
Hawn xi ħadd li iterattiv?

380
00:29:39,130 --> 00:29:42,430
Nistgħu jimxu permezz ta 'dan flimkien jekk le.

381
00:29:46,080 --> 00:29:48,100
L-idea se tkun l-istess.

382
00:30:00,260 --> 00:30:02,830
Iterattiv soluzzjoni.

383
00:30:02,830 --> 00:30:07,140
Aħna qed tmur jridu bażikament jagħmlu l-istess idea

384
00:30:07,140 --> 00:30:16,530
fejn irridu jżommu rekord ta 'l-aħħar il-ġdid tal-firxa u l-bidu ġdid ta' l-array

385
00:30:16,530 --> 00:30:18,510
u tagħmel dan aktar u aktar.

386
00:30:18,510 --> 00:30:22,430
U jekk dak li aħna qed iżżomm rekord ta 'kif il-bidu u t-tmiem qatt jiltaqgħu,

387
00:30:22,430 --> 00:30:29,020
allura aħna ma jsibuha u nistgħu ritorn foloz.

388
00:30:29,020 --> 00:30:37,540
Allura kif nista 'nagħmlu? Kull min ikollu suġġerimenti jew kodiċi għalija biex pull up?

389
00:30:42,190 --> 00:30:47,450
[Student] Do loop waqt. >> Yeah.

390
00:30:47,450 --> 00:30:49,450
Inti tmur tixtieq li tagħmel loop.

391
00:30:49,450 --> 00:30:51,830
>> Kellek kodiċi I tista 'pull up, jew dak li inti kienu ser jissuġġerixxu?

392
00:30:51,830 --> 00:30:56,340
[Student] I think so. >> Kull dritt. Dan jagħmel l-affarijiet eħfef. Liema kien l-isem tiegħek?

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

394
00:31:00,140 --> 00:31:04,190
Reviżjoni 1. Okay.

395
00:31:04,190 --> 00:31:13,200
Low huwa dak li aħna msejħa tibda qabel.

396
00:31:13,200 --> 00:31:17,080
Up huwa pjuttost mhux dak li aħna imsejjaħ il-għan qabel.

397
00:31:17,080 --> 00:31:22,750
Attwalment, l-aħħar issa hija fil-firxa. Huwa element għandna jikkunsidraw.

398
00:31:22,750 --> 00:31:26,890
Allura baxx huwa 0, up huwa l-daqs tal-array - 1,

399
00:31:26,890 --> 00:31:34,780
u issa aħna qed looping, u aħna verifika -

400
00:31:34,780 --> 00:31:37,340
I raden inti tista 'timxi permezz tiegħu.

401
00:31:37,340 --> 00:31:41,420
Liema kienet ħsieb tiegħek permezz ta 'dan? Walk lilna permezz ta 'kodiċi tiegħek.

402
00:31:41,420 --> 00:31:49,940
[Student] Sure. Ħares lejn il-valur haystack fin-nofs u jqabbilha lil labra.

403
00:31:49,940 --> 00:31:58,520
Mela jekk huwa ikbar minn labra tiegħek, allura inti tixtieq li - oh, fil-fatt, li għandu jkun lura.

404
00:31:58,520 --> 00:32:05,180
Inti qed tmur jridu tarmi l-nofs tal-lemin, u hekk yeah, li għandu jkun il-mod.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Għalhekk dan għandu jkun inqas? Hija li dak li qal? >> [Student] Yeah.

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

407
00:32:10,390 --> 00:32:15,700
Mela jekk dak li aħna qed tħares lejn huwa iżgħar minn dak li rridu,

408
00:32:15,700 --> 00:32:19,410
allura yeah, irridu li tarmi l-nofs tax-xellug,

409
00:32:19,410 --> 00:32:22,210
li jfisser aħna aġġornament kollox aħna qed jikkunsidraw

410
00:32:22,210 --> 00:32:26,610
billi jiċċaqilqu baxx għad-dritt tal-firxa.

411
00:32:26,610 --> 00:32:30,130
Dan jidher tajjeb.

412
00:32:30,130 --> 00:32:34,550
Naħseb li għandu l-istess kwistjoni li għidna fuq dak preċedenti,

413
00:32:34,550 --> 00:32:49,760
fejn jekk baxxa hija 0 u up huwa 1, imbagħad baxxa + up / 2 se jitwaqqaf l-istess ħaġa mill-ġdid.

414
00:32:49,760 --> 00:32:53,860
>> U anki jekk dan mhux il-każ, hija għadha aktar effiċjenti għall-inqas

415
00:32:53,860 --> 00:32:57,630
li biss tarmi l bogħod l-element aħna biss ħares lejn li nafu hija żbaljata.

416
00:32:57,630 --> 00:33:03,240
Allura baxx + up / 2 + 1 - >> [student] Li għandu jkun il-mod ieħor.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Jew dan għandu jkun - 1 u l-ieħor għandu jkun + 1.

418
00:33:05,900 --> 00:33:09,580
[Student] U għandu jkun hemm double ugwali sinjal. >> [Bowden] Yeah.

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

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

421
00:33:15,910 --> 00:33:21,280
U fl-aħħarnett, issa li għandna dan 1 + - 1 ħaġa,

422
00:33:21,280 --> 00:33:31,520
huwa - jista 'ma jkunx - huwa dejjem possibbli għall baxx li tispiċċa bil-valur akbar minn up?

423
00:33:35,710 --> 00:33:40,320
Naħseb li l-uniku mod li jista 'jiġri - Huwa possibbli? >> [Student] I do not know.

424
00:33:40,320 --> 00:33:45,220
Iżda jekk jiġrilha maqtugħ u mbagħad gets minus li 1 u mbagħad - >> Yeah.

425
00:33:45,220 --> 00:33:47,480
[Student] Ikun possibilment nikseb messed up.

426
00:33:49,700 --> 00:33:53,940
Naħseb li għandu jkun tajjeb biss għax

427
00:33:53,940 --> 00:33:58,800
biex din jispiċċaw aktar baxxi huma jkollhom tkun ugwali, naħseb.

428
00:33:58,800 --> 00:34:03,070
Imma jekk huma ugwali, allura aħna ma għamlu l-linja filwaqt li tibda bil

429
00:34:03,070 --> 00:34:06,670
u aħna biss kienu lura l-valur. So I think we qed tajba issa.

430
00:34:06,670 --> 00:34:11,530
Avviż li anki jekk din il-problema ma tibqax rikursivi,

431
00:34:11,530 --> 00:34:17,400
l-istess tip ta 'ideat japplika fejn nistgħu naraw kif dan daqshekk faċilment jippresta ruħu

432
00:34:17,400 --> 00:34:23,659
għal soluzzjoni rikursivi mill-fatt li aħna qed biss aġġornament tal-indiċi fuq u aktar mill-ġdid,

433
00:34:23,659 --> 00:34:29,960
aħna qed jagħmlu l-problema iżgħar, aħna qed jiffokaw fuq subsett ta 'l-array.

434
00:34:29,960 --> 00:34:40,860
[Student] Jekk baxxa hija 0 u up huwa 1, dawn it-tnejn ikunu 0 + 1/2, li tmur għal 0,

435
00:34:40,860 --> 00:34:44,429
u mbagħad wieħed ikun + 1, wieħed ikun - 1.

436
00:34:47,000 --> 00:34:50,870
[Student] Fejn ninsabu verifika ugwaljanza?

437
00:34:50,870 --> 00:34:55,100
Bħal jekk il-wieħed nofs huwa attwalment labra?

438
00:34:55,100 --> 00:34:58,590
Aħna bħalissa ma tagħmel dan? Oh!

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

440
00:35:05,340 --> 00:35:13,740
Iva. Ma nistgħux sempliċement jagħmel it-test stabbiliti hawnhekk għaliex ejja ngħidu l-nofs 1 -

441
00:35:13,740 --> 00:35:16,430
[Student] Huwa fil-fatt simili ma tarmi l-bound.

442
00:35:16,430 --> 00:35:20,220
Mela jekk inti tarmi l-illegat, inti għandek tiċċekkja l-ewwel jew kwalunkwe.

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

444
00:35:23,350 --> 00:35:29,650
Allura issa għandna tintrema l-waħda għandna attwalment ħares lejn,

445
00:35:29,650 --> 00:35:33,260
li jfisser li għandna issa jeħtieġ li jkollhom ukoll

446
00:35:33,260 --> 00:35:44,810
jekk (haystack [(Baxx + up) / 2] == labra), allura nistgħu jirritornaw veru.

447
00:35:44,810 --> 00:35:52,070
U jekk nressaq ieħor jew biss jekk, dan ifisser litteralment l-istess ħaġa

448
00:35:52,070 --> 00:35:57,110
għaliex dan kien lura veru.

449
00:35:57,110 --> 00:36:01,450
So I ser jitqiegħdu inkella jekk, iżda ma jimpurtax.

450
00:36:01,450 --> 00:36:10,440
>> Mela inkella jekk dan, inkella dan, u din hija ħaġa komuni nagħmel

451
00:36:10,440 --> 00:36:14,340
fejn anki jekk huwa l-każ fejn kollox huwa tajjeb hawn,

452
00:36:14,340 --> 00:36:22,780
bħal baxxi qatt ma jista 'jkun ikbar minn up, mhuwiex raġunament jiswew madwar jekk dan huwa veru.

453
00:36:22,780 --> 00:36:28,010
Allura inti tista 'ukoll jgħidu filwaqt li huwa baxx inqas minn jew ugwali għal

454
00:36:28,010 --> 00:36:30,720
jew waqt baxxa hija anqas minn

455
00:36:30,720 --> 00:36:35,300
hekk jekk huma qatt ugwali jew baxxa jiġri biex jiġu rrinunzjati,

456
00:36:35,300 --> 00:36:40,130
allura nistgħu break out ta 'dan loop.

457
00:36:41,410 --> 00:36:44,630
Mistoqsijiet, tħassib, il-kummenti?

458
00:36:47,080 --> 00:36:49,270
Okay. Dan jidher tajjeb.

459
00:36:49,270 --> 00:36:52,230
Issa rridu nagħmlu tip.

460
00:36:52,230 --> 00:37:04,030
Jekk immorru tieni reviżjoni tiegħi, naraw dawn in-numri l-istess,

461
00:37:04,030 --> 00:37:07,550
iżda issa dawn m'għadhomx sabiex magħżula.

462
00:37:07,550 --> 00:37:12,840
U aħna rridu li jimplimentaw it-tip tuża kwalunkwe algoritmu fil O n log n.

463
00:37:12,840 --> 00:37:17,240
Allura liema algoritmu do you think we għandhom jimplimentaw hawn? >> [Student] sort Merge.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Yeah. Jingħaqdu tip huwa O (n log n), b'tali mod li dak li aħna qed tmur biex tagħmel.

465
00:37:23,810 --> 00:37:26,680
U l-problema se tkun pjuttost simili,

466
00:37:26,680 --> 00:37:31,920
fejn faċilment jippresta ruħu għal soluzzjoni rikursivi.

467
00:37:31,920 --> 00:37:35,580
Nistgħu wkoll toħroġ bi soluzzjoni iterattiv jekk irridu,

468
00:37:35,580 --> 00:37:42,540
iżda recursion se jkun aktar faċli hawn u għandna nagħmlu recursion.

469
00:37:45,120 --> 00:37:49,530
I raden aħna se jimxu permezz sort jingħaqdu l-ewwel,

470
00:37:49,530 --> 00:37:54,280
għalkemm hemm video sabiħ fuq tip jingħaqdu diġà. [Daħk]

471
00:37:54,280 --> 00:37:59,780
Allura jingħaqdu sort hemm - I am ħela tant ta 'dan id-dokument.

472
00:37:59,780 --> 00:38:02,080
Oh, hemm wieħed biss xellug.

473
00:38:02,080 --> 00:38:03,630
Allura jingħaqdu.

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
Jingħaqdu jieħu żewġ arrays separati.

477
00:38:33,460 --> 00:38:36,780
Individwalment dawk arrays 2 huma t-tnejn magħżula.

478
00:38:36,780 --> 00:38:40,970
Allura dan array, 1, 3, 5, magħżula. Dan firxa, 0, 2, 4, magħżula.

479
00:38:40,970 --> 00:38:46,710
Issa dak jingħaqdu għandha tagħmel huwa jinġabru flimkien ġo firxa unika li huwa nnifsu magħżula.

480
00:38:46,710 --> 00:38:57,130
Allura rridu firxa ta 'daqs 6 li huwa se jkollu dawn l-elementi ġewwa ta' dan

481
00:38:57,130 --> 00:38:59,390
sabiex magħżula.

482
00:38:59,390 --> 00:39:03,390
>> U hekk nistgħu nieħdu vantaġġ mill-fatt li dawn arrays 2 huma magħżula

483
00:39:03,390 --> 00:39:06,800
biex jagħmlu dan fil-ħin lineari,

484
00:39:06,800 --> 00:39:13,510
tifsira żmien lineari jekk dan array huwa x daqs u dan huwa y daqs,

485
00:39:13,510 --> 00:39:20,970
allura l-algoritmu totali għandu jkun O (x + y). Okay.

486
00:39:20,970 --> 00:39:23,150
Allura suġġerimenti.

487
00:39:23,150 --> 00:39:26,030
[Student] Jista nibdew mix-xellug?

488
00:39:26,030 --> 00:39:30,150
Allura inti ser tpoġġi l-isfel 0 ewwel u allura l-1 u allura hawnhekk int fil-2.

489
00:39:30,150 --> 00:39:33,320
Allura huwa tip simili ikollok tab li l-mixja lejn il-lemin. >> [Bowden] Yeah.

490
00:39:33,320 --> 00:39:41,070
Għal dawn iż-żewġ arrays jekk aħna biss jiffoka fuq l-element leftmost.

491
00:39:41,070 --> 00:39:43,530
Minħabba ż-żewġ arrays huma magħżula, nafu li dawn l-elementi 2

492
00:39:43,530 --> 00:39:46,920
huma l-elementi iżgħar fi kwalunkwe firxa.

493
00:39:46,920 --> 00:39:53,500
Allura dan ifisser li 1 ta 'dawn l-elementi 2 għandha tkun l-element iżgħar firxa magħquda tagħna.

494
00:39:53,500 --> 00:39:58,190
Huwa biss hekk jiġri li l-iżgħar huwa dak fuq il-lemin din id-darba.

495
00:39:58,190 --> 00:40:02,580
Allura aħna jieħdu 0, daħħalha fuq ix-xellug minħabba 0 hija inqas minn 1,

496
00:40:02,580 --> 00:40:08,210
sabiex jieħdu 0, daħħalha fil-pożizzjoni ewwel tagħna, u allura aħna taġġorna dan

497
00:40:08,210 --> 00:40:12,070
li issa jiffokaw fuq l-ewwel element.

498
00:40:12,070 --> 00:40:14,570
U issa aħna jirrepetu.

499
00:40:14,570 --> 00:40:20,670
Allura issa nqabblu 2 u 1. 1 huwa iżgħar, hekk aħna ser daħħal 1.

500
00:40:20,670 --> 00:40:25,300
Aħna taġġorna dan il-werrej għall-punt li dan Guy.

501
00:40:25,300 --> 00:40:33,160
Issa nagħmlu dan mill-ġdid, hekk 2. Dan se taġġorna, iqabblu dawn 2, 3.

502
00:40:33,160 --> 00:40:37,770
Din taġġorna, imbagħad 4 u 5.

503
00:40:37,770 --> 00:40:42,110
Allura dan huwa jingħaqdu.

504
00:40:42,110 --> 00:40:49,010
>> Għandu jkun pjuttost ovvju li huwa żmien lineari peress li aħna biss jmorru madwar kull element darba.

505
00:40:49,010 --> 00:40:55,980
U li huwa l-pass akbar biex timplimenta tip jingħaqdu qed tagħmel dan.

506
00:40:55,980 --> 00:40:59,330
U mhuwiex li diffiċli.

507
00:40:59,330 --> 00:41:15,020
A affarijiet ftit li jinkwetaw dwar huwa ejja ngħidu aħna kienu qed jingħaqdu 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
F'dan il-każ aħna jispiċċaw fix-xenarju fejn dan wieħed se tkun iżgħar,

509
00:41:30,930 --> 00:41:36,160
allura aħna aġġornament dan il-werrej, dan wieħed se tkun iżgħar, jaġġornaw dan,

510
00:41:36,160 --> 00:41:41,280
dan wieħed iżgħar, u issa inti għandek jirrikonoxxu

511
00:41:41,280 --> 00:41:44,220
meta inti ħadthom attwalment jispiċċaw ta 'elementi li tqabbel magħhom.

512
00:41:44,220 --> 00:41:49,400
Peress li aħna diġà użaw dan array kollu,

513
00:41:49,400 --> 00:41:55,190
kollox f'dan array issa huwa biss mdaħħla hawn.

514
00:41:55,190 --> 00:42:02,040
Allura jekk aħna qatt run fis-punt fejn wieħed mill arrays tagħna huwa jagħqad kompletament diġà,

515
00:42:02,040 --> 00:42:06,510
allura aħna biss jieħdu l-elementi tal-firxa l-oħra u daħħal minnhom fil-tmiem tal-firxa.

516
00:42:06,510 --> 00:42:13,630
Allura nistgħu biss daħħal 4, 5, 6. Okay.

517
00:42:13,630 --> 00:42:18,070
Din hija ħaġa waħda li toqgħod attent għalihom.

518
00:42:22,080 --> 00:42:26,120
Implimentazzjoni li għandu jkun pass 1.

519
00:42:26,120 --> 00:42:32,600
Jingħaqdu sort allura bbażata fuq dan, huwa 2 passi, 2 passi iblah.

520
00:42:38,800 --> 00:42:42,090
Ejja biss jagħtu din array.

521
00:42:57,920 --> 00:43:05,680
Allura jingħaqdu sort, pass 1 huwa li recursively jiksru l-firxa fil-nofsijiet.

522
00:43:05,680 --> 00:43:09,350
Allura maqsuma din array in nofsijiet.

523
00:43:09,350 --> 00:43:22,920
Issa għandna 4, 15, 16, 50 u 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
U issa aħna tagħmel dan mill-ġdid u aħna maqsuma dawn fis nofsijiet.

525
00:43:25,800 --> 00:43:27,530
I biss ser tagħmel dan fuq din in-naħa.

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

527
00:43:34,790 --> 00:43:37,440
Aħna se nagħmlu l-istess ħaġa fuq hawn.

528
00:43:37,440 --> 00:43:40,340
U issa aħna qasmitha fis nofsijiet mill-ġdid.

529
00:43:40,340 --> 00:43:51,080
U aħna għandna 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Allura dan huwa każ bażi tagħna.

531
00:43:53,170 --> 00:44:00,540
Ladarba l-arrays huma ta 'daqs 1, allura aħna tieqaf mal-qsim fis nofsijiet.

532
00:44:00,540 --> 00:44:03,190
>> Issa dak li nagħmlu ma 'dan?

533
00:44:03,190 --> 00:44:15,730
Aħna jispiċċaw dan ukoll se jitqassmu 8, 23, 42, u 108.

534
00:44:15,730 --> 00:44:24,000
Allura issa li aħna qed f'dan il-punt, issa pass tnejn tip jingħaqdu huwa biss jingħaqdu pari għal-listi.

535
00:44:24,000 --> 00:44:27,610
Allura aħna rridu li jingħaqdu dawn. Aħna biss sejħa jingħaqdu.

536
00:44:27,610 --> 00:44:31,410
Nafu jingħaqdu se terġa 'lura dawn fl-ordni magħżula.

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

538
00:44:33,920 --> 00:44:41,440
Issa rridu li jingħaqdu dawn, u li se terġa 'lura lista ma' dawk sabiex magħżula,

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

540
00:44:44,160 --> 00:44:57,380
Aħna jingħaqdu dawk - I ma tistax tikteb - 8, 23 u 42, 108.

541
00:44:57,380 --> 00:45:02,890
Allura aħna għandna pari amalgamati darba.

542
00:45:02,890 --> 00:45:05,140
Issa aħna biss jingħaqdu mill-ġdid.

543
00:45:05,140 --> 00:45:10,130
Avviż li kull wieħed minn dawn il-listi huwa magħżul minnha nnifisha,

544
00:45:10,130 --> 00:45:15,220
u allura nistgħu biss jingħaqdu dawn il-listi biex tikseb lista ta 'daqs 4 li huwa magħżul

545
00:45:15,220 --> 00:45:19,990
u jingħaqdu dawn iż-żewġ listi li tikseb lista ta 'daqs 4 li huwa magħżul.

546
00:45:19,990 --> 00:45:25,710
U fl-aħħarnett, nistgħu jingħaqdu dawn iż-żewġ listi ta 'daqs 4 li tikseb wieħed lista ta' daqs 8 li huwa magħżul.

547
00:45:25,710 --> 00:45:34,030
Allura biex tara li dan huwa b'mod ġenerali n log n, aħna diġà raw li jingħaqdu huwa lineari,

548
00:45:34,030 --> 00:45:40,390
hekk meta aħna qed jittrattaw ma 'li qed jingħaqdu dawn, hekk bħall-ispiża globali ta' inkorporazzjoni

549
00:45:40,390 --> 00:45:43,410
għal dawn iż-żewġ listi huwa biss 2 minħabba -

550
00:45:43,410 --> 00:45:49,610
Jew ukoll, huwa O ta 'n, iżda n hawnhekk hija biss dawn l-elementi 2, dan huwa 2.

551
00:45:49,610 --> 00:45:52,850
U dawn 2 ser ikunu 2 u dawn 2 se jkunu 2 u dawn 2 se jkun 2,

552
00:45:52,850 --> 00:45:58,820
hekk firxa kollha tas-tamalgama li għandna bżonn li tagħmel, aħna jispiċċaw jagħmlu n.

553
00:45:58,820 --> 00:46:03,210
Bħal 2 + 2 + 2 + 2 huwa 8, li huwa n,

554
00:46:03,210 --> 00:46:08,060
sabiex l-ispiża ta 'amalgamazzjoni f'dan is-sett huwa n.

555
00:46:08,060 --> 00:46:10,810
U allura l-istess ħaġa hawn.

556
00:46:10,810 --> 00:46:16,980
Aħna ser jingħaqdu dawn 2, allura dawn 2, u individwalment din l-inkorporazzjoni se jieħu erba 'operazzjonijiet,

557
00:46:16,980 --> 00:46:23,610
din l-inkorporazzjoni se jieħu erba 'operazzjonijiet, iżda għal darb'oħra, bejn dawn kollha,

558
00:46:23,610 --> 00:46:29,030
aħna jispiċċaw jingħaqdu n affarijiet totali, u għalhekk dan il-pass jieħu n.

559
00:46:29,030 --> 00:46:33,670
U hekk kull livell jieħu elementi n jkunu magħquda.

560
00:46:33,670 --> 00:46:36,110
>> U kif ħafna livelli huma hemmhekk?

561
00:46:36,110 --> 00:46:40,160
F'kull livell, array tagħna tikber skond id-daqs 2.

562
00:46:40,160 --> 00:46:44,590
Hawnhekk arrays tagħna huma ta 'daqs 1, hawn dawn qed ta' daqs 2, hawn dawn qed ta 'daqs 4,

563
00:46:44,590 --> 00:46:46,470
u finalment, dawn qed ta 'daqs 8.

564
00:46:46,470 --> 00:46:56,450
Allura peress li huwa irduppjar, hemm ser jkun hemm total ta 'log n ta' dawn il-livelli.

565
00:46:56,450 --> 00:47:02,090
Allura ma log n-livelli, kull livell individwali tieħu n-operazzjonijiet kollha,

566
00:47:02,090 --> 00:47:05,720
irridu jiksbu l-log n n algoritmu.

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

568
00:47:08,940 --> 00:47:13,320
Have nies li diġà għamlu progress fuq kif jiġi implimentat dan?

569
00:47:13,320 --> 00:47:18,260
Huwa xi ħadd diġà tinsab fi stat fejn nista 'biss pull up kodiċi tagħhom?

570
00:47:20,320 --> 00:47:22,260
I jistgħu jagħtuk minuta.

571
00:47:24,770 --> 00:47:27,470
Dan wieħed se jkun itwal.

572
00:47:27,470 --> 00:47:28,730
I jirrakkomanda ħafna jerġgħu jitfaċċaw -

573
00:47:28,730 --> 00:47:30,510
Inti ma għandekx tagħmel recursion għall jingħaqdu

574
00:47:30,510 --> 00:47:33,750
minħabba li jekk isir recursion għall jingħaqdu, int ser ikollhom jgħaddu minn mazz ta 'daqsijiet differenti.

575
00:47:33,750 --> 00:47:37,150
Tista ', iżda huwa annoying.

576
00:47:37,150 --> 00:47:43,720
Iżda recursion għal tip nnifisha hija pjuttost faċli.

577
00:47:43,720 --> 00:47:49,190
Inti biss litteralment sejħa sort fuq nofs tax-xellug, sort fuq nofs tal-lemin. Okay.

578
00:47:51,770 --> 00:47:54,860
Kull min ikollu xi ħaġa I tista 'pull up għadhom?

579
00:47:54,860 --> 00:47:57,540
Jew inkella I ser jagħti minuta.

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

581
00:47:59,900 --> 00:48:02,970
Kull min ikollu xi ħaġa nistgħu naħdmu ma?

582
00:48:05,450 --> 00:48:09,680
Jew inkella aħna ser biss xogħol ma 'dan u mbagħad jespandu minn hemm.

583
00:48:09,680 --> 00:48:14,050
>> Kull min ikollu aktar minn dan li nista 'pull up?

584
00:48:14,050 --> 00:48:17,770
[Student] Yeah. Inti tista 'pull up minjiera. >> Kull dritt.

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

586
00:48:22,170 --> 00:48:25,280
[Student] Kien hemm ħafna ta 'kondizzjonijiet. >> Oh, rimja. Tista inti -

587
00:48:25,280 --> 00:48:28,110
[Student] Għandi biex isalvawh. >> Yeah.

588
00:48:32,420 --> 00:48:35,730
Allura għamilna jagħmlu l-inkorporazzjoni separatament.

589
00:48:35,730 --> 00:48:38,570
Oh, iżda mhux dik ħażina.

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

591
00:48:41,650 --> 00:48:47,080
Allura xorta huwa nnifsu biss sejħa mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Spjega lilna dak mergeSortHelp ma.

593
00:48:49,530 --> 00:48:55,700
[Student] MergeSortHelp pretty ħafna ma l-passi żewġ prinċipali,

594
00:48:55,700 --> 00:49:01,270
li huwa li sort kull nofs tal-firxa u mbagħad jingħaqdu tnejn minnhom.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Okay, so tagħti me a 2.

596
00:49:10,850 --> 00:49:13,210
Naħseb li dan - >> [student] I bżonn -

597
00:49:17,100 --> 00:49:19,400
Yeah. Jien xi ħaġa nieqsa.

598
00:49:19,400 --> 00:49:23,100
Fil jingħaqdu, I jirrealizzaw li għandi bżonn li jinħoloq firxa ġdida

599
00:49:23,100 --> 00:49:26,530
minħabba I ma setgħux jagħmlu dan fil-post. >> Iva. Inti ma tistax. Ikkoreġi.

600
00:49:26,530 --> 00:49:28,170
[Student] So I joħolqu firxa ġdida.

601
00:49:28,170 --> 00:49:31,510
I nesa fl-aħħar tal jingħaqdu biex terġa 'bidla.

602
00:49:31,510 --> 00:49:34,490
Okay. Għandna bżonn firxa ġdida.

603
00:49:34,490 --> 00:49:41,000
Fil-tip jingħaqdu, dan huwa kważi dejjem veru.

604
00:49:41,000 --> 00:49:44,340
Parti mill-ispiża ta 'l-algoritmu aħjar ħin għaqli

605
00:49:44,340 --> 00:49:47,310
huwa kważi dejjem jeħtieġu li jużaw memorja ftit aktar.

606
00:49:47,310 --> 00:49:51,570
Allura hawn, ma jimpurtax kif inti tagħmel jingħaqdu sort,

607
00:49:51,570 --> 00:49:54,780
inti inevitabbilment jeħtieġ li tuża xi memorja żejda.

608
00:49:54,780 --> 00:49:58,240
Hu jew hi maħluqa firxa ġdida.

609
00:49:58,240 --> 00:50:03,400
U allura inti tgħidli fl-aħħar aħna biss bżonn li kopja firxa ġdida fil-firxa oriġinali.

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

611
00:50:04,830 --> 00:50:08,210
I do not know jekk li jaħdem f'termini ta 'għadd b'referenza jew kwalunkwe -

612
00:50:08,210 --> 00:50:11,650
Yeah, din se taħdem. >> [Student] Okay.

613
00:50:20,620 --> 00:50:24,480
Ridt tipprova taħdem din? >> [Student] Nru, li għadha ma ġietx. Okay. >>

614
00:50:24,480 --> 00:50:28,880
Ipprova running, u mbagħad I ser nitkellmu dwar dan għat-tieni.

615
00:50:28,880 --> 00:50:35,200
[Student] I-ħtieġa li jkollhom l-prototipi funzjoni u kollox, għalkemm, id-dritt?

616
00:50:37,640 --> 00:50:40,840
Il-prototipi funzjoni. Oh, inti tfisser simili - Iva.

617
00:50:40,840 --> 00:50:43,040
Sort qed titlob mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Allura sabiex tip li jsejħu mergeSortHelp, mergeSortHelp għandu jew ġew definiti

619
00:50:47,390 --> 00:50:56,370
qabel sort jew aħna biss bżonn il-prototip. Just kopja u paste dan.

620
00:50:56,370 --> 00:50:59,490
U bl-istess mod, mergeSortHelp qed titlob jingħaqdu,

621
00:50:59,490 --> 00:51:03,830
iżda jingħaqdu ma ġiex definit għadhom, hekk nistgħu biss let mergeSortHelp jafu

622
00:51:03,830 --> 00:51:08,700
li dan huwa dak jingħaqdu se look like, u li li.

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

624
00:51:22,770 --> 00:51:32,660
Għandna kwistjoni hawnhekk fejn għandna l-ebda każ bażi.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp huwa rikursivi, sabiex kwalunkwe rikursivi funzjoni

626
00:51:38,110 --> 00:51:42,610
se jeħtieġu xi tip ta 'każ bażi li tkun taf meta tieqaf recursively ssejjaħ lilha nnifisha.

627
00:51:42,610 --> 00:51:45,590
X'inhu każ bażi tagħna se tkun hawn? Yeah.

628
00:51:45,590 --> 00:51:49,110
[Student] Jekk id-daqs huwa 1? >> [Bowden] Iva.

629
00:51:49,110 --> 00:51:56,220
Allura bħal rajna hemm dritt, aħna waqfet arrays qsim

630
00:51:56,220 --> 00:52:01,850
ladarba aħna ltqajna fis arrays ta 'daqs 1, li inevitabbilment huma magħżula infushom.

631
00:52:01,850 --> 00:52:09,530
Mela jekk id-daqs huwa ugwali għal 1, nafu l-array huwa diġà magħżula,

632
00:52:09,530 --> 00:52:12,970
hekk nistgħu biss ritorn.

633
00:52:12,970 --> 00:52:16,880
>> Avviż li s null, hekk aħna ma jirritornawx xejn partikolari, aħna biss ritorn.

634
00:52:16,880 --> 00:52:19,580
Okay. Allura dak il-każ bażi tagħna.

635
00:52:19,580 --> 00:52:27,440
I raden każ bażiku tagħna tista 'wkoll tkun jekk aħna jiġri li jkun jingħaqdu firxa ta' daqs 0,

636
00:52:27,440 --> 00:52:30,030
aħna probabbilment jixtiequ jieqfu f'xi punt,

637
00:52:30,030 --> 00:52:33,610
hekk nistgħu biss jgħidu daqs inqas minn 2 jew inqas minn jew ugwali għal 1

638
00:52:33,610 --> 00:52:37,150
sabiex din se taħdem għal kwalunkwe firxa issa.

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

640
00:52:38,870 --> 00:52:42,740
Allura dak il-każ bażi tagħna.

641
00:52:42,740 --> 00:52:45,950
Issa tridu jimxu lilna permezz jingħaqdu?

642
00:52:45,950 --> 00:52:49,140
What do kollha dawn il-każijiet jfisser?

643
00:52:49,140 --> 00:52:54,480
Up hawn, aħna qed biss tagħmel l-istess idea, il -

644
00:52:56,970 --> 00:53:02,470
[Student] I ħtieġa li tkun tgħaddi daqs ma 'l-sejħiet mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
I miżjuda daqs bħala primarja addizzjonali u mhuwiex hemmhekk, bħal daqs / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, id-daqs / 2, id-daqs / 2. >> [Student] Yeah, u wkoll fil-funzjoni ta 'hawn fuq kif ukoll.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Here? >> [Student] Just daqs. >> [Bowden] Oh. Daqs? Daqs, >> [Student] Yeah.

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

649
00:53:23,010 --> 00:53:26,580
Let me think għat-tieni.

650
00:53:26,580 --> 00:53:28,780
Do we run fi kwistjoni?

651
00:53:28,780 --> 00:53:33,690
Aħna dejjem trattament fuq ix-xellug bħala 0. >> [Student] No

652
00:53:33,690 --> 00:53:36,340
Dak ħażin wisq. Jiddispjacini. Għandu jkun bidu. Yeah.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Okay. I simili li aħjar.

654
00:53:39,230 --> 00:53:43,880
U t-tmiem. Okay.

655
00:53:43,880 --> 00:53:47,200
Allura issa inti tixtieq li jimxu lilna permezz jingħaqdu? >> [Student] Okay.

656
00:53:47,200 --> 00:53:52,150
Jien biss mixi permezz ta 'dan firxa ġdida li stajt maħluqa.

657
00:53:52,150 --> 00:53:57,420
Id-daqs tiegħu huwa d-daqs tal-porzjon ta 'l-array li aħna rridu li jiġu magħżula

658
00:53:57,420 --> 00:54:03,460
u tipprova ssib l-element li għandi tpoġġi fil-pass firxa ġdida.

659
00:54:03,460 --> 00:54:10,140
Allura biex tagħmel dan, l-ewwel jien iċċekkjar jekk l-nofs tax-xellug ta 'l-array għad għandha elementi kwalunkwe aktar,

660
00:54:10,140 --> 00:54:14,260
u jekk ma jiġrix dan, allura inti jinżlu għal din il-kundizzjoni inkella, li sempliċiment jgħid

661
00:54:14,260 --> 00:54:20,180
okay, dan għandu jkun fil-firxa dritt, u aħna ser tpoġġi li fl-indiċi attwali ta 'newArray.

662
00:54:20,180 --> 00:54:27,620
>> U mbagħad mod ieħor, jien verifika jekk il-lemin tal-firxa hija wkoll lest,

663
00:54:27,620 --> 00:54:30,630
f'liema każ I biss jitqiegħed fil-xellug.

664
00:54:30,630 --> 00:54:34,180
Dan ma jista 'attwalment tkun meħtieġa. M'inix ċert.

665
00:54:34,180 --> 00:54:40,970
Iżda xorta waħda, tnejn l-oħra verifika li l-tnejn huma iżgħar fid-xellug jew il-lemin.

666
00:54:40,970 --> 00:54:49,770
U wkoll f'kull każ, jien inkrementazzjoni liema minnhom placeholder I inkrement.

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

668
00:54:52,040 --> 00:54:53,840
Li jidher tajjeb.

669
00:54:53,840 --> 00:54:58,800
Ħadd ma jkollu kummenti jew tħassib jew mistoqsijiet?

670
00:55:00,660 --> 00:55:07,720
Allura l-erba 'każijiet li għandna biex iġibu l-affarijiet fil biss qed - jew jidher qisu 5 -

671
00:55:07,720 --> 00:55:13,100
iżda aħna għandna biex jikkunsidraw jekk il-firxa tax-xellug tkun jispiċċaw ta 'affarijiet li rridu li jingħaqdu,

672
00:55:13,100 --> 00:55:16,390
jekk il-firxa dritt jispiċċaw ta 'affarijiet li rridu jingħaqdu -

673
00:55:16,390 --> 00:55:18,400
Jien tipponta lejn xejn.

674
00:55:18,400 --> 00:55:21,730
Allura jekk il-firxa tax-xellug tkun jispiċċaw ta 'affarijiet jew il-firxa dritt ikun jispiċċaw ta' affarijiet.

675
00:55:21,730 --> 00:55:24,320
Dawn huma żewġ każijiet.

676
00:55:24,320 --> 00:55:30,920
Għandna bżonn ukoll il-każ trivjali ta 'jekk il-ħaġa xellug huwa inqas mill-aħjar ħaġa.

677
00:55:30,920 --> 00:55:33,910
Imbagħad irridu li jagħżlu l-ħaġa xellug.

678
00:55:33,910 --> 00:55:37,630
Dawn huma l-każijiet.

679
00:55:37,630 --> 00:55:40,990
Allura dan kien dritt, b'tali mod li li.

680
00:55:40,990 --> 00:55:46,760
Array xellug. Huwa 1, 2, 3. Okay. So yeah, dawn huma l-affarijiet erba nistgħu trid tagħmel.

681
00:55:50,350 --> 00:55:54,510
U aħna mhux se jmorru fuq iterattiv soluzzjoni.

682
00:55:54,510 --> 00:55:55,980
I ma jirrakkomandaw -

683
00:55:55,980 --> 00:56:03,070
Jingħaqdu tip huwa eżempju ta 'funzjoni li huwa kemm le denb rikursivi,

684
00:56:03,070 --> 00:56:07,040
mhuwiex faċli li tagħmel dan denb rikursivi,

685
00:56:07,040 --> 00:56:13,450
iżda wkoll mhuwiex faċli ħafna biex jagħmlu dan iterattiv.

686
00:56:13,450 --> 00:56:16,910
Dan huwa faċli ħafna.

687
00:56:16,910 --> 00:56:19,170
Din l-implimentazzjoni ta 'tip jingħaqdu,

688
00:56:19,170 --> 00:56:22,140
jingħaqdu, l-ebda kwistjoni dak li inti tagħmel, int ser tibni jingħaqdu.

689
00:56:22,140 --> 00:56:29,170
>> Allura jingħaqdu tip mibnija fuq quċċata ta 'inkorporazzjoni recursively huwa biss dawn il-linji tlieta.

690
00:56:29,170 --> 00:56:34,700
Iteratively, huwa aktar tedjanti u aktar diffiċli biex jaħsbu.

691
00:56:34,700 --> 00:56:41,860
Iżda avviż li din mhix denb rikursivi peress mergeSortHelp - meta jitlob huwa stess -

692
00:56:41,860 --> 00:56:46,590
għad jeħtieġ li tagħmel affarijiet wara dan prospetti sejħa jirrikorri.

693
00:56:46,590 --> 00:56:50,830
Allura dan il-qafas munzell għandhom jibqgħu eżistenti anki wara li ssejjaħ dan.

694
00:56:50,830 --> 00:56:54,170
U allura meta inti sejħa dan, il-qafas munzell għandha tkompli teżisti

695
00:56:54,170 --> 00:56:57,780
minħabba li, anki wara li sejħa, għad għandna bżonn li jingħaqdu.

696
00:56:57,780 --> 00:57:01,920
U huwa nontrivial biex jagħmlu dan denb rikursivi.

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

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

699
00:57:09,860 --> 00:57:13,400
Allura jmorru lura biex issolvi - oh, hemm żewġ affarijiet nixtieq li juru. Okay.

700
00:57:13,400 --> 00:57:17,840
Li jmorru lura sa sort, aħna ser tagħmel dan malajr.

701
00:57:17,840 --> 00:57:21,030
. Tfittxija jew Sort? Sort. Yeah.

702
00:57:21,030 --> 00:57:22,730
Tmur lura għall-bidu ta 'tip.

703
00:57:22,730 --> 00:57:29,870
Aħna rridu li joħolqu algoritmu li xorta l-firxa jużaw kwalunkwe algoritmu

704
00:57:29,870 --> 00:57:33,660
fil O ta 'n.

705
00:57:33,660 --> 00:57:40,860
Allura kif dan huwa possibbli? Ħadd ma jkollu xi tip ta '-

706
00:57:40,860 --> 00:57:44,300
I aċċennata qabel fi -

707
00:57:44,300 --> 00:57:48,300
Jekk aħna qed madwar biex jitjieb minn n log n sa O ta 'ln,

708
00:57:48,300 --> 00:57:51,450
aħna tejbu algoritmu tagħna ħin għaqli,

709
00:57:51,450 --> 00:57:55,250
li jfisser dak li aħna se bżonn tagħmel biex tpatti għal dan?

710
00:57:55,250 --> 00:57:59,520
[Student] Ispazju. >> Yeah. Aħna ser tkun qed tuża aktar spazju.

711
00:57:59,520 --> 00:58:04,490
U lanqas biss aktar spazju, huwa spazju b'mod esponenzjali aktar.

712
00:58:04,490 --> 00:58:14,320
Għalhekk naħseb dan it-tip ta 'algoritmu hija xi ħaġa psewdo, polynom psewdo -

713
00:58:14,320 --> 00:58:18,980
psewdo - I ma tistax tiftakar. Psewdo xi ħaġa.

714
00:58:18,980 --> 00:58:22,210
Iżda huwa għaliex għandna bżonn l-użu spazju tant

715
00:58:22,210 --> 00:58:28,610
li dan jista 'jinkiseb iżda mhux realistiku.

716
00:58:28,610 --> 00:58:31,220
>> U kif nistgħu jintlaħaq dan?

717
00:58:31,220 --> 00:58:36,810
Aħna tista 'tikseb dan jekk aħna jiggarantixxu li kull element partikolari fil-firxa

718
00:58:36,810 --> 00:58:39,600
huwa taħt ċertu daqs.

719
00:58:42,070 --> 00:58:44,500
Mela ejja biss jgħidu li d-daqs huwa ta '200,

720
00:58:44,500 --> 00:58:48,130
kwalunkwe element fil-firxa hija taħt id-daqs 200.

721
00:58:48,130 --> 00:58:51,080
U dan huwa attwalment ħafna realistiku.

722
00:58:51,080 --> 00:58:58,660
Tista 'faċilment jkollhom firxa li taf kollox fiha

723
00:58:58,660 --> 00:59:00,570
se tkun anqas minn ċertu numru.

724
00:59:00,570 --> 00:59:07,400
Bħal jekk ikollok xi vector assolutament massiva jew xi ħaġa

725
00:59:07,400 --> 00:59:11,810
imma inti taf kollox se tkun bejn 0 u 5,

726
00:59:11,810 --> 00:59:14,790
allura huwa għaddej biex tkun ħafna aktar mgħaġġla biex jagħmlu dan.

727
00:59:14,790 --> 00:59:17,930
U l-marbuta fuq kwalunkwe mill-elementi huwa 5,

728
00:59:17,930 --> 00:59:21,980
għalhekk dan marbuta, li hija kemm memorja int se tkun qed tuża.

729
00:59:21,980 --> 00:59:26,300
Allura l-marbuta huwa 200.

730
00:59:26,300 --> 00:59:32,960
Fit-teorija dejjem ikun hemm marbut peress integer tista 'biss tkun sa 4 biljun,

731
00:59:32,960 --> 00:59:40,600
iżda li mhux realistiku minn dakinhar aħna'd tkun qed tuża l-ispazju

732
00:59:40,600 --> 00:59:44,400
dwar l-ordni ta '4 biljun. Allura dak realistiku.

733
00:59:44,400 --> 00:59:47,060
Imma hawn aħna ser ngħidu marbut tagħna huwa 200.

734
00:59:47,060 --> 00:59:59,570
Il-trick li tagħmel dan fil-parti O ta 'n hija li nagħmlu ieħor array imsejħa għadd ta' daqs BOUND.

735
00:59:59,570 --> 01:00:10,470
Allura fil-fatt, dan huwa shortcut għal - I attwalment do not know jekk clang ma dan.

736
01:00:11,150 --> 01:00:15,330
Iżda fil GCC almenu - I'm clang jekk wieħed jassumi tagħmlu wisq -

737
01:00:15,330 --> 01:00:18,180
dan se biss initialize-firxa sħiħa li jkun 0s.

738
01:00:18,180 --> 01:00:25,320
Mela jekk jien ma tridx tagħmel dan, imbagħad I tista 'tagħmel separatament għal (i int = 0;

739
01:00:25,320 --> 01:00:31,500
i <MARBUTIN; i + +) u għadd [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Allura issa kollox huwa initialized għal 0.

741
01:00:35,260 --> 01:00:39,570
I jtenni fuq firxa tiegħi,

742
01:00:39,570 --> 01:00:51,920
u dak li qed nagħmel huwa jien għadd tan-numru ta 'kull - Ejja jinżlu hawn.

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

744
01:00:55,480 --> 01:01:00,010
Dak li jien għadd huwa n-numru ta 'okkorrenzi ta' kull wieħed minn dawn l-elementi.

745
01:01:00,010 --> 01:01:03,470
Ejja attwalment żid ftit aktar fil hawn ma 'xi jirrepeti.

746
01:01:03,470 --> 01:01:11,070
Allura l-valur għandna hawnhekk, il-valur ta 'dik se tkun array [i].

747
01:01:11,070 --> 01:01:14,850
Allura val jista 'jkun 4 jew 8 jew ikun x'ikun.

748
01:01:14,850 --> 01:01:18,870
U issa jien għadd kemm ta 'dak il-valur stajt tidher,

749
01:01:18,870 --> 01:01:21,230
hekk għadd [val] + +;

750
01:01:21,230 --> 01:01:29,430
Wara dan isir, l-għadd huwa ser tfittex xi ħaġa bħal 0001.

751
01:01:29,430 --> 01:01:42,190
Ejja nagħmlu jgħodd [val] - BOUND + 1.

752
01:01:42,190 --> 01:01:48,230
>> Issa li jinsab biss li jagħtu kont għall-fatt li aħna qed jibdew minn 0.

753
01:01:48,230 --> 01:01:50,850
Mela jekk 200 hija se tkun akbar numru tagħna,

754
01:01:50,850 --> 01:01:54,720
imbagħad 0-200 huwa 201 affarijiet.

755
01:01:54,720 --> 01:02:01,540
Għalhekk għadd, dan ser look like 00001 għaliex aħna għandna waħda 4.

756
01:02:01,540 --> 01:02:10,210
Imbagħad aħna ser ikollhom 0001 fejn aħna ser ikollhom 1 fl-indiċi 8 ta 'għadd.

757
01:02:10,210 --> 01:02:14,560
Aħna ser ikollhom 2 fl-indiċi 23 ta 'għadd.

758
01:02:14,560 --> 01:02:17,630
Aħna ser ikollhom 2 fl-indiċi 42 ta 'għadd.

759
01:02:17,630 --> 01:02:21,670
Allura nistgħu nużaw għadd.

760
01:02:34,270 --> 01:02:44,920
Allura num_of_item = għadd [i].

761
01:02:44,920 --> 01:02:52,540
U għalhekk jekk num_of_item huwa 2, li jfisser irridu li daħħal 2 ta 'l-għadd i

762
01:02:52,540 --> 01:02:55,290
fis firxa magħżula tagħna.

763
01:02:55,290 --> 01:03:02,000
Għalhekk għandna bżonn li jżommu rekord ta 'kemm aħna fil-firxa.

764
01:03:02,000 --> 01:03:05,470
= Indiċi Allura 0.

765
01:03:05,470 --> 01:03:09,910
Array - I taf biss tiktibha.

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

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

768
01:03:28,580 --> 01:03:32,490
Hija li dak li nixtieq? Naħseb li dak li nixtieq.

769
01:03:35,100 --> 01:03:38,290
Iva, dan jidher tajjeb. Okay.

770
01:03:38,290 --> 01:03:43,050
Allura ma kulħadd jifhem dak li l-iskop ta 'firxa għadd tiegħi hu?

771
01:03:43,050 --> 01:03:48,140
Huwa għadd tan-numru ta 'okkorrenzi ta' kull wieħed minn dawn in-numri.

772
01:03:48,140 --> 01:03:51,780
Imbagħad I am iterazzjoni fuq dak array jgħodd,

773
01:03:51,780 --> 01:03:57,190
u l-pożizzjoni ith fil-firxa għadd

774
01:03:57,190 --> 01:04:01,930
huwa n-numru ta 'i i li għandhom jidhru fir firxa magħżula tiegħi.

775
01:04:01,930 --> 01:04:06,840
C'est pourquoi għadd ta '4 se tkun 1

776
01:04:06,840 --> 01:04:11,840
u l-għadd ta '8 se tkun l-1, l-għadd tat-23 se tkun 2.

777
01:04:11,840 --> 01:04:16,900
Allura dak kemm minnhom nixtieq li daħħal fis firxa magħżula tiegħi.

778
01:04:16,900 --> 01:04:19,200
Imbagħad I biss tagħmel dan.

779
01:04:19,200 --> 01:04:28,960
I am ddaħħal num_of_item i s fis firxa magħżula tiegħi.

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

781
01:04:32,460 --> 01:04:43,100
U hekk darb'oħra, dan huwa żmien lineari peress li aħna huma biss iterazzjoni fuq dan darba,

782
01:04:43,100 --> 01:04:47,470
imma hija wkoll lineari fil dak dan in-numru jiġri li jkun,

783
01:04:47,470 --> 01:04:50,730
u għalhekk tiddependi ħafna fuq dak marbut tiegħek.

784
01:04:50,730 --> 01:04:53,290
Bil marbuta ta '200, li mhux dik ħażina.

785
01:04:53,290 --> 01:04:58,330
Jekk marbuta tiegħek se tkun 10,000, allura dak l-ftit agħar,

786
01:04:58,330 --> 01:05:01,360
imma jekk marbuta tiegħek se jkun ta '4 biljun, li l-kompletament mhux realistiku

787
01:05:01,360 --> 01:05:07,720
u dan array se jkollhom ikunu ta 'daqs 4 biljuni, li mhijiex realistika.

788
01:05:07,720 --> 01:05:10,860
Allura dak li. Mistoqsijiet?

789
01:05:10,860 --> 01:05:13,270
[Rispons istudent inaudible] >> Okay.

790
01:05:13,270 --> 01:05:15,710
I realizzati ħaġa waħda oħra meta konna għaddejjin.

791
01:05:17,980 --> 01:05:23,720
Naħseb li l-problema kienet fil-s Lucas u probabbilment kull wieħed Rajna.

792
01:05:23,720 --> 01:05:26,330
I kompletament nesa.

793
01:05:26,330 --> 01:05:31,040
L-unika ħaġa jien ridt li jikkummenta fuq hija li meta inti qed jittrattaw ma 'affarijiet bħal indiċijiet,

794
01:05:31,040 --> 01:05:38,320
int qatt ma verament tara dan meta int bil-miktub ta 'għall-loop,

795
01:05:38,320 --> 01:05:41,120
iżda teknikament, kull meta inti qed jittrattaw ma 'dawn l-indiċi

796
01:05:41,120 --> 01:05:45,950
għandek pretty ħafna dejjem jittrattaw interi mhux iffirmat.

797
01:05:45,950 --> 01:05:53,850
Ir-raġuni għal dan hija meta inti qed jittrattaw ma 'interi iffirmat,

798
01:05:53,850 --> 01:05:56,090
hekk jekk ikollok 2 interi iffirmati u inti żid flimkien

799
01:05:56,090 --> 01:06:00,640
u dawn jispiċċaw kbira wisq, allura inti tispiċċa ma 'numru negattiv.

800
01:06:00,640 --> 01:06:03,410
Allura dak hu li jfur numru sħiħ huwa.

801
01:06:03,410 --> 01:06:10,500
>> Jekk I żid 2 biljun u 1 biljun, I jispiċċaw ma negattiva 1 biljun.

802
01:06:10,500 --> 01:06:15,480
Thats kif interi jaħdmu fuq il-kompjuters.

803
01:06:15,480 --> 01:06:17,510
Allura l-problema bl-użu -

804
01:06:17,510 --> 01:06:23,500
Dik il-multa ħlief jekk baxxa jiġri li jkun 2 biljun u sa jiġri li jkun 1 biljun,

805
01:06:23,500 --> 01:06:27,120
allura dan se jkun negattiv 1 biljun u mbagħad aħna qed tmur biex jaqsmu dan bi 2

806
01:06:27,120 --> 01:06:29,730
u tispiċċa bil negattiva 500 miljun.

807
01:06:29,730 --> 01:06:33,760
Allura dan huwa biss kwistjoni jekk jiġri li tkun tiftix permezz ta 'firxa

808
01:06:33,760 --> 01:06:38,070
ta 'biljuni ta' affarijiet.

809
01:06:38,070 --> 01:06:44,050
Iżda jekk + baxxa sa jiġri li jfur, allura dak l-problema.

810
01:06:44,050 --> 01:06:47,750
Hekk kif aħna jagħmluhom mhux iffirmat, allura 2000000000 flimkien ma '1 biljun 3 biljun.

811
01:06:47,750 --> 01:06:51,960
3000000000 diviż bi 2 huwa 1.5 biljun.

812
01:06:51,960 --> 01:06:55,670
Allura hekk kif dawn qed mhux iffirmat, kollox huwa perfett.

813
01:06:55,670 --> 01:06:59,900
U hekk dan huwa wkoll kwistjoni meta int bil-miktub tiegħek għall-linji,

814
01:06:59,900 --> 01:07:03,940
u fil-fatt, hija probabbilment ma dan awtomatikament.

815
01:07:09,130 --> 01:07:12,330
Hija fil-fatt se biss Yell fi inti.

816
01:07:12,330 --> 01:07:21,610
Allura jekk dan in-numru huwa kbir wisq biex tkun biss numru sħiħ iżda se tajbin fil integer mhux iffirmat,

817
01:07:21,610 --> 01:07:24,970
se Yell fi inti, hekk hu għalhekk li inti qatt ma jinżel fit-kwistjoni.

818
01:07:29,150 --> 01:07:34,820
Tista 'tara li l-indiċi jkun qatt ser tkun negattiva,

819
01:07:34,820 --> 01:07:39,220
u hekk meta int iterazzjoni fuq firxa,

820
01:07:39,220 --> 01:07:43,970
inti tista 'kważi dejjem ngħid mhux iffirmat int i, imma inti ma verament ikollhom.

821
01:07:43,970 --> 01:07:47,110
Affarijiet huma ser jaħdmu pretty ħafna biss ukoll.

822
01:07:48,740 --> 01:07:50,090
Okay. [Whispers] Liema ħin huwa?

823
01:07:50,090 --> 01:07:54,020
L-aħħar ħaġa li ridt li juru - u jien ser biss tagħmel dan verament malajr.

824
01:07:54,020 --> 01:08:03,190
Inti taf kif għandna # jiddefinixxu hekk nistgħu # tiddefinixxi MAX bħala 5 jew xi ħaġa?

825
01:08:03,190 --> 01:08:05,940
Ejja ma tagħmel MAX. # Tiddefinixxi BOUND bħala 200. Dan huwa dak li għamilna qabel.

826
01:08:05,940 --> 01:08:10,380
Dan jiddefinixxi kostanti, li huwa biss se jiġu kkupjati u pasted

827
01:08:10,380 --> 01:08:13,010
fejn aħna jiġri li tikteb BOUND.

828
01:08:13,010 --> 01:08:18,189
>> Allura aħna jistgħu attwalment jagħmlu aktar ma # jiddefinixxi.

829
01:08:18,189 --> 01:08:21,170
Nistgħu # jiddefinixxi l-funzjonijiet.

830
01:08:21,170 --> 01:08:23,410
Huma qed mhux verament funzjonijiet, imma aħna ser jsejħulhom funzjonijiet.

831
01:08:23,410 --> 01:08:36,000
Ta 'eżempju tkun xi ħaġa bħal MAX (x, y) huwa definit bħala (x <y y:? X). Okay.

832
01:08:36,000 --> 01:08:40,660
Allura inti għandek tikseb użati biex sintassi operatur tlett fibri,

833
01:08:40,660 --> 01:08:49,029
iżda huwa x inqas minn y? Ritorn y, inkella ritorn x.

834
01:08:49,029 --> 01:08:54,390
Allura tista 'tara inti tista' tagħmel din il-funzjoni separata,

835
01:08:54,390 --> 01:09:01,399
u l-funzjoni tista 'tkun simili bool MAX tieħu 2 argumenti, jirritorna din.

836
01:09:01,399 --> 01:09:08,340
Din hija waħda mill-aktar komuni nara jsir bħal dan. Aħna jsejħulhom macros.

837
01:09:08,340 --> 01:09:11,790
Din hija makro.

838
01:09:11,790 --> 01:09:15,859
Dan huwa biss l-sintassi għal dan.

839
01:09:15,859 --> 01:09:18,740
Tista 'tikteb makro biex jagħmlu dak kollu li trid.

840
01:09:18,740 --> 01:09:22,649
You spiss tara macros għal debugging printfs u l-għalf.

841
01:09:22,649 --> 01:09:29,410
Allura tip ta 'printf, hemm kostanti speċjali C bħall jenfasizzaw LINE jenfasizzaw,

842
01:09:29,410 --> 01:09:31,710
2 jenfasizza LINJA jenfasizzaw,

843
01:09:31,710 --> 01:09:37,550
u hemm ukoll naħseb 2 jenfasizza funzjonijiet. Li jista 'jkun fiha. Xi ħaġa bħal dik.

844
01:09:37,550 --> 01:09:40,880
Dawk l-affarijiet se jiġu sostitwiti bl-isem tal-funzjoni

845
01:09:40,880 --> 01:09:42,930
jew in-numru tal-linja li int fuq.

846
01:09:42,930 --> 01:09:48,630
Spiss, tikteb printfs debugging li stabbiliti hawn I jistgħu mbagħad biss tikteb

847
01:09:48,630 --> 01:09:54,260
Debug u se jistampaw il-numru linja u l-funzjoni li I jiġri li jkun fil-

848
01:09:54,260 --> 01:09:57,020
li ltaqgħu magħhom tali dikjarazzjoni debug.

849
01:09:57,020 --> 01:09:59,550
U inti tista 'jistampa wkoll affarijiet oħra.

850
01:09:59,550 --> 01:10:05,990
Allura wieħed ħaġa li għandek toqgħod attent għalihom hija jekk I jiġri li jiddefinixxu # DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
bħala xi ħaġa simili 2 * y u 2 * x.

852
01:10:11,380 --> 01:10:14,310
Allura għal raġuni kwalunkwe, jiġri li tagħmel dan ħafna.

853
01:10:14,310 --> 01:10:16,650
Sabiex tagħmel dan makro.

854
01:10:16,650 --> 01:10:18,680
Dan huwa attwalment maqsuma.

855
01:10:18,680 --> 01:10:23,050
I call dan billi tagħmel xi ħaġa simili DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Allura dak li għandhom jingħataw lura?

857
01:10:28,840 --> 01:10:30,580
[Student] 12.

858
01:10:30,580 --> 01:10:34,800
Iva, 12 għandhom jiġu rritornati, u 12 huwa rritornat.

859
01:10:34,800 --> 01:10:43,350
3 gets mibdula għal x, 6 gets mibdula għall y, u nerġgħu lura 2 * 6, li huwa 12.

860
01:10:43,350 --> 01:10:47,710
Issa dak dwar dan? Liema għandhom jingħataw lura?

861
01:10:47,710 --> 01:10:50,330
[Student] 14. >> Idealment, 14.

862
01:10:50,330 --> 01:10:55,290
Il-kwistjoni hija li kif hash jiddefinixxi x-xogħol, ftakar huwa kopja u paste litterali

863
01:10:55,290 --> 01:11:00,160
ta 'kollox pretty ħafna, hekk dak li dan ikun ser jiġi interpretat bħala li

864
01:11:00,160 --> 01:11:11,270
huwa 3 inqas minn 1 flimkien 6, 2 darbiet 1 flimkien 6, 2 darbiet 3.

865
01:11:11,270 --> 01:11:19,780
>> Allura għal din ir-raġuni inti kważi dejjem wrap kollox fil-parentesi.

866
01:11:22,180 --> 01:11:25,050
Kwalunkwe varjabbli inti kważi dejjem wrap fil-parentesi.

867
01:11:25,050 --> 01:11:29,570
Hemm każijiet fejn inti ma għandekx, bħal naf li jien ma bżonn tagħmel li hawn

868
01:11:29,570 --> 01:11:32,110
minħabba inqas milli huwa pretty ħafna dejjem biss imur għax-xogħol,

869
01:11:32,110 --> 01:11:34,330
għalkemm dan ma jista 'anke jkun veru.

870
01:11:34,330 --> 01:11:41,870
Jekk ikun hemm xi ħaġa redikola simili DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
allura li għaddej biex tikseb sostitwiti bi 3 anqas minn 1 huwa ugwali 2,

872
01:11:49,760 --> 01:11:53,460
u hekk allura li għaddej biex tagħmel 3 anqas minn 1, ma li 2 indaqs,

873
01:11:53,460 --> 01:11:55,620
li ma jkunx dak li rridu.

874
01:11:55,620 --> 01:12:00,730
Allura biex jevitaw kwalunkwe problemi operatur preċedenza,

875
01:12:00,730 --> 01:12:02,870
dejjem wrap fil-parentesi.

876
01:12:03,290 --> 01:12:07,700
Okay. U li dan, 5:30.

877
01:12:08,140 --> 01:12:12,470
Jekk għandek xi mistoqsijiet dwar il-pset, let us know.

878
01:12:12,470 --> 01:12:18,010
Għandu jkun gost, u l-edizzjoni Hacker wkoll huwa ħafna aktar realistiku

879
01:12:18,010 --> 01:12:22,980
mill-edizzjoni Hacker tas-sena li għaddiet, hekk aħna nittamaw li ħafna inti tipprova dan.

880
01:12:22,980 --> 01:12:26,460
S-sena li għaddiet kien kbir ħafna.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]