1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Sehemu ya 3 - Zaidi Starehe]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Chuo Kikuu cha Harvard]

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

4
00:00:07,310 --> 00:00:12,700
>> Hivyo swali la kwanza ni strangely kuchukuliwa.

5
00:00:12,700 --> 00:00:17,480
GDB inakuwezesha "Debug" mpango, lakini, zaidi hasa, ni nini basi wewe kufanya?

6
00:00:17,480 --> 00:00:22,590
Mimi itabidi kujibu kwamba mmoja, na mimi sijui nini hasa ilivyotarajiwa,

7
00:00:22,590 --> 00:00:27,910
hivyo mimi nina guessing ni kitu pamoja na mistari ya inakuwezesha hatua kwa hatua

8
00:00:27,910 --> 00:00:31,540
kutembea kwa njia ya mpango, kiutendaji na hivyo, mabadiliko ya vigezo, kufanya mambo haya yote -

9
00:00:31,540 --> 00:00:34,270
kimsingi kabisa kudhibiti utekelezaji wa mpango

10
00:00:34,270 --> 00:00:38,410
na kukagua sehemu yoyote aliyopewa ya utekelezaji wa mpango.

11
00:00:38,410 --> 00:00:43,030
Hivyo wale makala basi wewe Debug mambo.

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

13
00:00:44,830 --> 00:00:50,520
Kwa nini binary tafuta zinahitaji kwamba safu sorted?

14
00:00:50,520 --> 00:00:53,360
Nani anataka kujibu?

15
00:00:56,120 --> 00:01:00,070
[Mwanafunzi] Kwa sababu haifanyi kazi kama si Iliyopangwa. >> Yeah. [Kicheko]

16
00:01:00,070 --> 00:01:04,910
Kama siyo sorted, basi ni vigumu kwa kupasuliwa katika nusu

17
00:01:04,910 --> 00:01:07,850
na najua kuwa kila kitu kwa upande wa kushoto ni kidogo na kila kitu kwa haki

18
00:01:07,850 --> 00:01:10,490
ni kubwa zaidi kuliko thamani ya kati.

19
00:01:10,490 --> 00:01:12,790
Hivyo mahitaji sorted.

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

21
00:01:14,170 --> 00:01:17,570
Kwa nini ni Bubble aina katika O ya n squared?

22
00:01:17,570 --> 00:01:23,230
Je, mtu yeyote kwanza nataka kutoa haraka sana wa ngazi za juu picha ya nini Bubble aina ni?

23
00:01:25,950 --> 00:01:33,020
[Mwanafunzi] Wewe kimsingi kupitia kila kipengele na wewe kuangalia kwanza vipengele chache.

24
00:01:33,020 --> 00:01:37,150
Kama uko nje ya wapi byta yao, kisha wewe kuangalia ijayo mambo machache na kadhalika.

25
00:01:37,150 --> 00:01:40,770
Wakati kufikia mwisho, basi, unajua kwamba kipengele kubwa ni kuwekwa katika mwisho,

26
00:01:40,770 --> 00:01:42,750
hivyo kupuuza kwamba moja kisha wewe kuendelea kwenda kupitia,

27
00:01:42,750 --> 00:01:48,490
na kila wakati wewe na kuangalia moja chini ya kipengele mpaka kufanya mabadiliko yoyote. >> Yeah.

28
00:01:48,490 --> 00:01:58,470
Ni wito Bubble aina kwa sababu kama wewe flip safu upande wake hivyo ni juu na chini, wima,

29
00:01:58,470 --> 00:02:03,100
kisha maadili kubwa itakuwa kuzama mpaka chini na maadili ndogo mapenzi Bubble hadi juu.

30
00:02:03,100 --> 00:02:05,210
Hiyo ni jinsi got jina lake.

31
00:02:05,210 --> 00:02:08,220
Na yeah, wewe tu kwenda kupitia.

32
00:02:08,220 --> 00:02:11,190
Wewe kuendelea kwenda kupitia safu, swapping thamani kubwa

33
00:02:11,190 --> 00:02:14,040
kupata maadili kubwa hadi chini.

34
00:02:14,040 --> 00:02:17,500
>> Kwa nini ni O ya n squared?

35
00:02:18,690 --> 00:02:24,620
Kwanza, haina mtu yeyote unataka kusema nini ni O ya n squared?

36
00:02:24,620 --> 00:02:28,760
[Mwanafunzi] Kwa sababu kwa ajili ya kuendesha kila unaendelea mara n.

37
00:02:28,760 --> 00:02:32,100
Unaweza tu kuwa na uhakika kwamba umechukua kipengele kubwa njia yote chini,

38
00:02:32,100 --> 00:02:35,230
basi una kwamba kurudia kwa kama mambo mengi. >> Yeah.

39
00:02:35,230 --> 00:02:41,800
Hivyo kukumbuka kile kubwa O ina maana na kile kubwa Omega njia.

40
00:02:41,800 --> 00:02:50,560
O kubwa ni kama juu amefungwa juu ya jinsi polepole inaweza kweli kukimbia.

41
00:02:50,560 --> 00:02:58,990
Hivyo kwa kusema ni O ya n squared, si O ya n au pengine itakuwa ni kuwa na uwezo wa kuendesha

42
00:02:58,990 --> 00:03:02,640
katika wakati linear, lakini ni O ya n cubed

43
00:03:02,640 --> 00:03:06,390
sababu ni imepakana na O ya n cubed.

44
00:03:06,390 --> 00:03:12,300
Kama ni imepakana na O ya n squared, basi ni imepakana na pia n cubed.

45
00:03:12,300 --> 00:03:20,280
Hivyo ni n squared, na katika kesi kabisa mbaya haiwezi kufanya vizuri zaidi kuliko n squared,

46
00:03:20,280 --> 00:03:22,830
ambayo ni kwa nini ni O ya n squared.

47
00:03:22,830 --> 00:03:31,200
Hivyo kuona math kidogo katika jinsi inakuja nje kuwa n squared,

48
00:03:31,200 --> 00:03:40,530
kama tuna mambo matano katika orodha yetu, mara ya kwanza jinsi wengi swaps inaweza sisi uwezekano haja ya kufanya

49
00:03:40,530 --> 00:03:47,170
ili kupata hii? Hebu kweli tu -

50
00:03:47,170 --> 00:03:52,040
Wangapi swaps ni sisi kwenda na kufanya katika muda kwanza wa aina Bubble kupitia safu?

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

52
00:03:53,540 --> 00:03:58,340
>> Kama kuna vipengele 5, sisi ni kwenda haja ya kufanya n - 1.

53
00:03:58,340 --> 00:04:01,100
Kisha juu ya moja ya pili jinsi wengi swaps ni sisi kwenda na kufanya?

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

55
00:04:03,440 --> 00:04:11,640
Na tatu ni kwenda kuwa n - 3, na kisha kwa urahisi nitaandika mawili ya mwisho

56
00:04:11,640 --> 00:04:15,270
kama basi sisi ni kwenda haja ya kufanya swaps 2 na 1 byta.

57
00:04:15,270 --> 00:04:19,899
Nadhani moja ya mwisho wanaweza au si kweli haja ya kutokea.

58
00:04:19,899 --> 00:04:22,820
Je, ni byta? Mimi sijui.

59
00:04:22,820 --> 00:04:26,490
Basi hizi ni jumla ya kiasi cha swaps au kulinganisha angalau una kufanya.

60
00:04:26,490 --> 00:04:29,910
Hata kama huna wabadilishane, bado wanahitaji kulinganisha maadili.

61
00:04:29,910 --> 00:04:33,910
Hivyo kuna n - kulinganisha 1 katika muda kwanza kupitia safu.

62
00:04:33,910 --> 00:04:42,050
Kama upya mambo haya, hebu kweli kufanya ni mambo sita ili mambo stack up nicely,

63
00:04:42,050 --> 00:04:44,790
na kisha mimi itabidi kufanya 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Hivyo tu rearranging sums hizi, tunataka kuona jinsi wengi kulinganisha sisi kufanya

65
00:04:49,910 --> 00:04:52,700
katika algorithm nzima.

66
00:04:52,700 --> 00:04:56,550
Hivyo kama sisi kuleta guys haya hapa chini,

67
00:04:56,550 --> 00:05:07,470
basi bado tuko tu summing kulinganisha hata hivyo wengi kulikuwa.

68
00:05:07,470 --> 00:05:13,280
Lakini kama sisi sum hizi na sisi sum hizi na sisi sum hizi,

69
00:05:13,280 --> 00:05:18,130
bado ni tatizo moja. Sisi tu jumla ya makundi hayo fulani.

70
00:05:18,130 --> 00:05:22,400
>> Hivyo sasa sisi ni summing 3 n wa. Siyo tu 3 n wa.

71
00:05:22,400 --> 00:05:27,650
Ni daima itakuwa n / n 2 wa.

72
00:05:27,650 --> 00:05:29,430
Hivyo hapa sisi kutokea kwa kuwa 6.

73
00:05:29,430 --> 00:05:34,830
Kama tulikuwa na mambo 10, basi tunaweza kufanya hii kambi kwa jozi 5 tofauti ya mambo

74
00:05:34,830 --> 00:05:37,180
na kuishia na n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Basi, wewe ni daima kwenda kupata n / n 2, na hivyo hii tutaweza hata nukta hivyo nje n squared / 2.

76
00:05:45,840 --> 00:05:48,890
Na hivyo hata kama ni sababu ya nusu, ambayo hufanyika kuja katika

77
00:05:48,890 --> 00:05:54,190
sababu ya ukweli kwamba kwa njia ya kila iteration juu ya safu sisi kulinganisha 1 chini

78
00:05:54,190 --> 00:05:58,040
hivyo kwamba ni jinsi gani sisi kupata zaidi ya 2, lakini bado ni n squared.

79
00:05:58,040 --> 00:06:01,650
Sisi hawajali kuhusu sababu mara kwa mara ya nusu.

80
00:06:01,650 --> 00:06:07,760
Hivyo mengi ya mambo makubwa O kama hii hutegemea aina tu ya kufanya aina hii ya math,

81
00:06:07,760 --> 00:06:12,260
kufanya hesabu arithmetic na stuff kijiometri mfululizo,

82
00:06:12,260 --> 00:06:17,750
lakini wengi wao katika kozi hii ni pretty moja kwa moja.

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

84
00:06:19,290 --> 00:06:24,430
Kwa nini ni insertion aina katika Omega ya n? Nini maana ya omega?

85
00:06:24,430 --> 00:06:27,730
[Wanafunzi wawili akizungumza katika moja - unintelligible] >> Yeah.

86
00:06:27,730 --> 00:06:30,630
Omega unaweza kufikiria kama chini amefungwa.

87
00:06:30,630 --> 00:06:36,550
>> Hivyo hakuna jambo jinsi ufanisi insertion yako aina algorithm ni,

88
00:06:36,550 --> 00:06:41,810
bila kujali orodha hiyo kupita katika, daima ana kwa kulinganisha vitu angalau n

89
00:06:41,810 --> 00:06:44,620
au ina iterate juu ya mambo n.

90
00:06:44,620 --> 00:06:47,280
Kwa nini?

91
00:06:47,280 --> 00:06:51,190
[Mwanafunzi] Kwa sababu kama orodha tayari Iliyopangwa, kisha kupitia iteration kwanza

92
00:06:51,190 --> 00:06:54,080
unaweza tu kuhakikisha kwamba kipengele sana kwanza ni mdogo,

93
00:06:54,080 --> 00:06:56,490
na iteration pili unaweza tu kuhakikisha mbili kwanza ni

94
00:06:56,490 --> 00:07:00,010
kwa sababu hamjui kwamba mapumziko ya orodha ni Iliyopangwa. >> Yeah.

95
00:07:00,010 --> 00:07:08,910
Kama kupita katika orodha kabisa Iliyopangwa, angalau sana una kwenda juu ya mambo yote

96
00:07:08,910 --> 00:07:12,180
kuona kuwa hakuna haja ya kuwa wakiongozwa kuzunguka.

97
00:07:12,180 --> 00:07:14,720
Hivyo kupita juu ya orodha na kusema oh, hii tayari Iliyopangwa,

98
00:07:14,720 --> 00:07:18,240
haiwezekani kwa wewe kujua ni sorted mpaka wewe kuangalia kila kipengele

99
00:07:18,240 --> 00:07:20,660
kuona kwamba wao ni ili Iliyopangwa.

100
00:07:20,660 --> 00:07:25,290
Hivyo chini amefungwa juu ya aina insertion ni Omega ya n.

101
00:07:25,290 --> 00:07:28,210
Nini hali mbaya mbio wakati wa aina kuunganisha,

102
00:07:28,210 --> 00:07:31,390
kesi mbaya kuwa kubwa O tena?

103
00:07:31,390 --> 00:07:37,660
Hivyo katika mazingira ya kesi mbaya, jinsi gani kuunganisha aina kukimbia?

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

105
00:07:43,690 --> 00:07:49,990
kasi ya jumla ya kuchagua algorithms ni n logi n. Huwezi kufanya vizuri zaidi.

106
00:07:51,930 --> 00:07:55,130
>> Kuna matukio maalum, na kama tuna muda leo - lakini sisi pengine won't -

107
00:07:55,130 --> 00:07:59,330
tunaweza kuona kwamba moja inafanya vizuri kuliko n logi n.

108
00:07:59,330 --> 00:08:04,050
Lakini katika kesi ya jumla, unaweza kufanya bora kuliko n logi n.

109
00:08:04,050 --> 00:08:09,680
Na kuunganisha aina hutokea kwa kuwa moja unapaswa kujua kwa kozi hii kwamba ni n logi n.

110
00:08:09,680 --> 00:08:13,260
Na hivyo tutaweza kweli kuwa utekelezaji kwamba leo.

111
00:08:13,260 --> 00:08:18,070
Na hatimaye, katika si zaidi ya tatu sentensi, jinsi gani uteuzi aina ya kazi?

112
00:08:18,070 --> 00:08:20,370
Je, mtu unataka kujibu, na mimi itabidi kuhesabu sentensi yako

113
00:08:20,370 --> 00:08:22,390
kwa sababu kama wewe kwenda juu ya 3 -

114
00:08:25,530 --> 00:08:28,330
Je, mtu yeyote kumbuka uteuzi aina?

115
00:08:31,280 --> 00:08:37,809
Uteuzi aina ni kawaida pretty rahisi kukumbuka tu kutoka jina.

116
00:08:37,809 --> 00:08:45,350
Wewe tu iterate juu ya safu, kupata chochote thamani kubwa ni ndogo au -

117
00:08:45,350 --> 00:08:47,290
chochote ili wewe ni kuchagua in

118
00:08:47,290 --> 00:08:50,750
Basi hebu kusema sisi ni kuchagua kutoka wadogo na wakubwa.

119
00:08:50,750 --> 00:08:55,250
Wewe iterate juu ya safu, kuangalia kwa chochote kipengele cha chini ni,

120
00:08:55,250 --> 00:08:59,750
kuchagua, na kisha wabadilishane tu ni chochote ni katika nafasi ya kwanza.

121
00:08:59,750 --> 00:09:04,090
Na kisha juu ya kupita juu ya safu ya pili, kuangalia kwa kipengele cha chini tena,

122
00:09:04,090 --> 00:09:07,490
kuchagua, na kisha wabadilishane kwa nini katika nafasi ya pili.

123
00:09:07,490 --> 00:09:10,650
Hivyo sisi ni tu kuokota na kuchagua kima cha chini cha maadili

124
00:09:10,650 --> 00:09:16,050
na kuingiza yao ndani ya safu ya mbele ya mpaka ni Iliyopangwa.

125
00:09:19,210 --> 00:09:21,560
Maswali juu ya hilo?

126
00:09:21,560 --> 00:09:25,710
>> Hizi inevitably itaonekana katika fomu una kujaza wakati wewe ni kuwasilisha pset.

127
00:09:29,010 --> 00:09:32,360
Wale ni kimsingi majibu hayo.

128
00:09:32,360 --> 00:09:34,230
Sawa, hivyo sasa coding matatizo.

129
00:09:34,230 --> 00:09:40,140
Mimi tayari kutumwa nje juu ya barua pepe - Je mtu si kupata kwamba barua pepe? Sawa.

130
00:09:40,140 --> 00:09:46,630
Mimi tayari kutumwa nje juu ya barua pepe ya nafasi ya kuwa sisi ni kwenda kuwa na kutumia,

131
00:09:46,630 --> 00:09:52,120
na kama wewe bonyeza juu ya jina langu - hivyo nadhani nina kwenda kuwa chini

132
00:09:52,120 --> 00:09:57,170
kwa sababu ya r nyuma - lakini kama wewe bonyeza juu ya jina langu utaona marekebisho 2.

133
00:09:57,170 --> 00:10:02,650
Marekebisho 1 inaenda mimi tayari kunakiliwa na pasted code katika Spaces

134
00:10:02,650 --> 00:10:06,900
kwa kitu tafuta wewe ni kwenda na kutekeleza.

135
00:10:06,900 --> 00:10:10,540
Na Revision 2 itakuwa jambo aina hiyo sisi kutekeleza baada ya hapo.

136
00:10:10,540 --> 00:10:15,770
Hivyo unaweza bonyeza Revision yangu 1 na kazi kutoka huko.

137
00:10:17,350 --> 00:10:22,060
Na sasa tunataka kutekeleza binary tafuta.

138
00:10:22,060 --> 00:10:26,470
>> Je, mtu yeyote unataka kutoa tu pseudocode ngazi ya juu maelezo

139
00:10:26,470 --> 00:10:31,440
wa nini tunakwenda kufanya kwa ajili ya kutafuta? Yeah.

140
00:10:31,440 --> 00:10:36,170
[Mwanafunzi] Wewe tu kuchukua katikati ya safu na kuona kama nini wewe kutafuta kwa

141
00:10:36,170 --> 00:10:38,650
ni kidogo kuliko au zaidi ya hapo.

142
00:10:38,650 --> 00:10:41,080
Na kama ni kidogo, unaweza kwenda nusu kwamba chini,

143
00:10:41,080 --> 00:10:44,750
na kama ni zaidi, unaweza kwenda nusu kwamba zaidi na wewe kurudia kwamba mpaka kupata tu jambo moja.

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

145
00:10:46,570 --> 00:10:51,320
Ona kwamba idadi yetu safu tayari Iliyopangwa,

146
00:10:51,320 --> 00:10:57,190
na hivyo ina maana kwamba tunaweza kuchukua faida ya kwamba na sisi inaweza kwanza kuangalia,

147
00:10:57,190 --> 00:11:00,390
sawa, mimi nina kuangalia kwa idadi 50.

148
00:11:00,390 --> 00:11:03,720
Hivyo siwezi kwenda katika katikati.

149
00:11:03,720 --> 00:11:07,380
Kati ni vigumu kufafanua wakati ni idadi hata wa mambo,

150
00:11:07,380 --> 00:11:10,820
lakini hebu sema tu tutaweza daima butu kwa katikati.

151
00:11:10,820 --> 00:11:14,420
Hivyo hapa tuna mambo 8, hivyo katikati itakuwa 16.

152
00:11:14,420 --> 00:11:17,330
Mimi nina kuangalia kwa 50, hivyo 50 ni kubwa kuliko 16.

153
00:11:17,330 --> 00:11:21,310
Hivyo sasa naweza kimsingi kutibu safu yangu kama mambo haya.

154
00:11:21,310 --> 00:11:23,450
Siwezi kutupa kila kitu kutoka 16 juu.

155
00:11:23,450 --> 00:11:27,440
Sasa safu yangu ni ya haki haya mambo 4, na mimi kurudia.

156
00:11:27,440 --> 00:11:31,910
Hivyo basi nataka kupata katikati tena, ambayo ni kwenda kuwa 42.

157
00:11:31,910 --> 00:11:34,730
42 ni chini ya 50, hivyo siwezi kutupa mambo haya mawili.

158
00:11:34,730 --> 00:11:36,890
Hii ni safu yangu iliyobaki.

159
00:11:36,890 --> 00:11:38,430
Mimi naenda kupata katikati tena.

160
00:11:38,430 --> 00:11:42,100
Nadhani 50 alikuwa ni mfano mbaya kwa sababu mimi mara zote kutupa mbali mambo ya kushoto,

161
00:11:42,100 --> 00:11:48,280
lakini kwa kipimo sawa, kama mimi nina kuangalia kwa kitu

162
00:11:48,280 --> 00:11:52,100
na ni chini ya kipengele Mimi sasa kuangalia,

163
00:11:52,100 --> 00:11:55,080
basi mimi nina kwenda kutupa kila kitu kwa haki.

164
00:11:55,080 --> 00:11:58,150
Hivyo sasa sisi haja ya kutekeleza hiyo.

165
00:11:58,150 --> 00:12:02,310
Ona kwamba sisi haja ya kupita katika kawaida.

166
00:12:02,310 --> 00:12:06,730
Tunaweza pia haja ya kawaida kwa bidii-code.

167
00:12:06,730 --> 00:12:11,640
Hivyo kama sisi kujikwamua kwamba # define -

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

169
00:12:21,430 --> 00:12:27,180
Ninawezaje nicely kufikiri nini ukubwa wa safu namba sasa ni?

170
00:12:27,180 --> 00:12:30,950
>> Wangapi mambo ni katika safu namba?

171
00:12:30,950 --> 00:12:33,630
[Mwanafunzi] Hesabu, mabano,. Urefu?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Hiyo haipo katika C.

173
00:12:36,600 --> 00:12:38,580
Haja urefu..

174
00:12:38,580 --> 00:12:42,010
Arrays hawana mali, hivyo hakuna mali urefu wa arrays

175
00:12:42,010 --> 00:12:45,650
kwamba tu kukupa hata hivyo muda mrefu hutokea kwa kuwa.

176
00:12:48,180 --> 00:12:51,620
[Mwanafunzi] Angalia kiasi gani kumbukumbu ina na kugawanya na kiasi gani - >> Yeah.

177
00:12:51,620 --> 00:12:55,810
Hivyo ni jinsi gani tunaweza kuona ni kiasi gani kumbukumbu ina? >> [Mwanafunzi] Sizeof. >> Yeah, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof ni operator ambayo inaenda kurudi ukubwa wa safu namba.

179
00:13:01,680 --> 00:13:10,060
Na kwamba ni kwenda kuwa hata hivyo wengi integers kuna ukubwa wa mara integer

180
00:13:10,060 --> 00:13:14,050
kuwa kwa kiasi gani kumbukumbu ni kweli kuchukua.

181
00:13:14,050 --> 00:13:17,630
Hivyo kama nataka idadi ya mambo katika safu,

182
00:13:17,630 --> 00:13:20,560
basi mimi nina kwenda kutaka kugawanya na ukubwa wa integer.

183
00:13:22,820 --> 00:13:26,010
Sawa. Hivyo kwamba lets mimi kupita katika ukubwa hapa.

184
00:13:26,010 --> 00:13:29,430
Kwa nini mimi haja ya kupita katika kawaida wakati wote?

185
00:13:29,430 --> 00:13:38,570
Kwa nini siwezi tu kufanya up hapa ukubwa int = sizeof (haystack) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Kwa nini hii si kazi?

187
00:13:41,490 --> 00:13:44,470
[Mwanafunzi] Ni hazibadiliki kimataifa.

188
00:13:44,470 --> 00:13:51,540
[Bowden] haystack ipo na sisi ni kupita kwa idadi kama haystack,

189
00:13:51,540 --> 00:13:54,700
na hii ni aina ya kielelezo cha nini kuja. Yeah.

190
00:13:54,700 --> 00:14:00,170
[Mwanafunzi] haystack ni kumbukumbu ya hivyo, hivyo ingekuwa kurudi jinsi kubwa akimaanisha kuwa ni.

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

192
00:14:02,150 --> 00:14:09,000
Mimi shaka katika hotuba kwamba ve kuonekana stack bado kweli, haki?

193
00:14:09,000 --> 00:14:11,270
Tumekuwa tu kusema kuhusu hilo.

194
00:14:11,270 --> 00:14:16,090
Hivyo ni stack ambapo wote wa vigezo yako ni kwenda kuhifadhiwa.

195
00:14:16,090 --> 00:14:19,960
>> Yoyote kumbukumbu hiyo zilizotengwa kwa vigezo mitaa ni kwenda katika stack,

196
00:14:19,960 --> 00:14:24,790
na kazi ya kila anapata nafasi yake juu ya stack, stack yake mwenyewe frame ni nini ni wito.

197
00:14:24,790 --> 00:14:31,590
Hivyo kuu ina stack yake frame, na ndani yake ni kwenda zipo hii safu namba,

198
00:14:31,590 --> 00:14:34,270
na ni kwenda kuwa ya kawaida sizeof (idadi).

199
00:14:34,270 --> 00:14:38,180
Ni kwenda na ukubwa wa idadi kugawanywa na ukubwa wa vipengele,

200
00:14:38,180 --> 00:14:42,010
bali wote maisha ndani ya stack frame kuu ya.

201
00:14:42,010 --> 00:14:45,190
Wakati sisi kuwaita tafuta, tafuta anapata stack yake mwenyewe frame,

202
00:14:45,190 --> 00:14:48,840
nafasi yake ya kuhifadhi wote wa vigezo yake ya ndani.

203
00:14:48,840 --> 00:14:56,420
Lakini hoja hizi - hivyo haystack si nakala ya safu hii nzima.

204
00:14:56,420 --> 00:15:00,990
Sisi si kupita katika safu nzima kama nakala ndani ya utafutaji.

205
00:15:00,990 --> 00:15:04,030
Ni tu hupita akimaanisha kwamba safu.

206
00:15:04,030 --> 00:15:11,470
Hivyo tafuta wanaweza kupata namba hizi kwa njia ya kumbukumbu hii.

207
00:15:11,470 --> 00:15:17,100
Ni bado kupata mambo ambayo kuishi ndani ya stack frame kuu ya,

208
00:15:17,100 --> 00:15:22,990
lakini kimsingi, wakati sisi kupata kuyatumia, ambayo inapaswa kuwa hivi karibuni,

209
00:15:22,990 --> 00:15:24,980
hii ni nini kuyatumia ni.

210
00:15:24,980 --> 00:15:29,400
Kuyatumia ni tu marejeo ya mambo, na unaweza kutumia kuyatumia kupata mambo

211
00:15:29,400 --> 00:15:32,030
kwamba ni katika muafaka mambo mengine 'stack.

212
00:15:32,030 --> 00:15:37,660
Hivyo hata kama idadi ni mitaa kuu, bado tunaweza kupata hiyo kupitia pointer hii.

213
00:15:37,660 --> 00:15:41,770
Lakini tangu ni tu pointer na ni tu ya kumbukumbu,

214
00:15:41,770 --> 00:15:45,040
sizeof (haystack) tu anarudi ukubwa wa kumbukumbu yenyewe.

215
00:15:45,040 --> 00:15:47,950
Ni haina kurudi ukubwa wa kitu ni akizungumzia.

216
00:15:47,950 --> 00:15:51,110
Ni haina kurudi ukubwa halisi wa idadi.

217
00:15:51,110 --> 00:15:55,660
Na hivyo hii si kwenda kufanya kazi kama sisi unataka kwa.

218
00:15:55,660 --> 00:15:57,320
>> Maswali juu ya hilo?

219
00:15:57,320 --> 00:16:03,250
Kuyatumia itakuwa wamekwenda kwa undani kwa kiasi kikubwa zaidi gory katika wiki ijayo.

220
00:16:06,750 --> 00:16:13,740
Na hii ni kwa nini mambo mengi ambayo unaweza kuona, vitu zaidi ya utafutaji au mambo aina,

221
00:16:13,740 --> 00:16:16,990
wao uko karibu wote kwenda haja ya kuchukua ukubwa halisi wa safu,

222
00:16:16,990 --> 00:16:20,440
kwa sababu katika C, hatuna wazo nini ukubwa wa safu ni.

223
00:16:20,440 --> 00:16:22,720
Unahitaji manually kupita in

224
00:16:22,720 --> 00:16:27,190
Na huwezi kupita manually katika safu nzima kwa sababu wewe ni tu kupita katika kumbukumbu

225
00:16:27,190 --> 00:16:30,390
na hivyo hawawezi kupata kawaida kutoka kumbukumbu.

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

227
00:16:32,300 --> 00:16:38,160
Hivyo sasa tunataka kutekeleza yale zilielezwa kabla.

228
00:16:38,160 --> 00:16:41,530
Unaweza kazi kwa dakika,

229
00:16:41,530 --> 00:16:45,250
na huna na wasiwasi kuhusu kupata kila kitu kikamilifu 100% kazi.

230
00:16:45,250 --> 00:16:51,410
Kuandika tu juu pseudocode nusu kwa jinsi gani na unafikiri ni lazima kazi.

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

232
00:16:53,630 --> 00:16:56,350
Hakuna haja ya kuwa kabisa kufanyika kwa hii bado.

233
00:16:56,350 --> 00:17:02,380
Lakini haina mtu yeyote kujisikia vizuri na kile walichonacho hivyo mbali,

234
00:17:02,380 --> 00:17:05,599
kama kitu tunaweza kufanya kazi kwa pamoja?

235
00:17:05,599 --> 00:17:09,690
Je, mtu yeyote unataka kujitolea? Au mimi Watapiga pick.

236
00:17:12,680 --> 00:17:18,599
Haina kuwa njema na hatua ya kitu lakini tunaweza kurekebisha katika hali ya kufanya kazi.

237
00:17:18,599 --> 00:17:20,720
[Mwanafunzi] Uhakika. >> Sawa.

238
00:17:20,720 --> 00:17:27,220
Hivyo unaweza kujiokoa marekebisho kwa kubonyeza icon kidogo Save.

239
00:17:27,220 --> 00:17:29,950
Wewe ni Ramya, haki? >> [Mwanafunzi] Yeah. >> [Bowden] Sawa.

240
00:17:29,950 --> 00:17:35,140
Hivyo sasa naweza kuona marekebisho yako na kila mtu anaweza kuvuta marekebisho.

241
00:17:35,140 --> 00:17:38,600
Na hapa tuna - Sawa.

242
00:17:38,600 --> 00:17:43,160
Hivyo Ramya akaenda pamoja ufumbuzi kujirudia, ambayo ni dhahiri ufumbuzi halali.

243
00:17:43,160 --> 00:17:44,970
Kuna njia mbili unaweza kufanya tatizo hili.

244
00:17:44,970 --> 00:17:48,060
Unaweza kufanya hivyo aidha iteratively au recursively.

245
00:17:48,060 --> 00:17:53,860
Matatizo zaidi kukutana ambayo yanaweza kufanyika recursively pia inaweza kufanyika iteratively.

246
00:17:53,860 --> 00:17:58,510
Hivyo hapa tumekuwa kufanyika ni recursively.

247
00:17:58,510 --> 00:18:03,730
>> Je, mtu unataka kufafanua nini maana ya kufanya kazi ya kujirudia?

248
00:18:07,210 --> 00:18:08,920
[Mwanafunzi] Wakati una kazi kujiita

249
00:18:08,920 --> 00:18:13,470
na kisha piga yenyewe mpaka hutoka nje na wa kweli na kweli. >> Yeah.

250
00:18:13,470 --> 00:18:17,680
kazi ya kujirudia ni kazi ambayo wito yenyewe.

251
00:18:17,680 --> 00:18:24,140
Kuna tatu kubwa mambo ambayo kazi ya kujirudia lazima.

252
00:18:24,140 --> 00:18:27,310
kwanza ni wazi, ni wito yenyewe.

253
00:18:27,310 --> 00:18:29,650
pili ni kesi ya msingi.

254
00:18:29,650 --> 00:18:33,390
Hivyo katika baadhi ya uhakika kazi inahitaji kuacha wito yenyewe,

255
00:18:33,390 --> 00:18:35,610
na kwamba ni nini kesi ya msingi ni kwa.

256
00:18:35,610 --> 00:18:43,860
Hivyo hapa tunajua kwamba tuache, tunapaswa kutoa up katika search wetu

257
00:18:43,860 --> 00:18:48,150
wakati kuanza sawa mwisho - na tutaweza kwenda juu ya nini maana ya.

258
00:18:48,150 --> 00:18:52,130
Lakini hatimaye, jambo la mwisho kwamba ni muhimu kwa ajili ya kazi ya kujirudia:

259
00:18:52,130 --> 00:18:59,250
kazi lazima kwa namna fulani mbinu kesi ya msingi.

260
00:18:59,250 --> 00:19:04,140
Kama kama wewe si kweli uppdatering chochote wakati kufanya pili ya kujirudia wito,

261
00:19:04,140 --> 00:19:07,880
kama wewe ni literally tu wito kazi tena na hoja hiyo

262
00:19:07,880 --> 00:19:10,130
na hakuna vigezo kimataifa yamebadilika au kitu chochote,

263
00:19:10,130 --> 00:19:14,430
wewe kamwe kufikia kesi ya msingi, katika kesi ambayo hiyo ni mbaya.

264
00:19:14,430 --> 00:19:17,950
Itakuwa recursion usio na kufurika stack.

265
00:19:17,950 --> 00:19:24,330
Lakini hapa tunaona kwamba update kinachotokea kwani sisi ni uppdatering kuanza + mwisho / 2,

266
00:19:24,330 --> 00:19:28,180
sisi ni uppdatering hoja mwisho hapa, sisi ni uppdatering hoja kuanza hapa.

267
00:19:28,180 --> 00:19:32,860
Hivyo katika simu zote kujirudia sisi ni uppdatering kitu. Sawa.

268
00:19:32,860 --> 00:19:38,110
Je, unataka kutembea kwetu kupitia ufumbuzi wako? >> Uhakika.

269
00:19:38,110 --> 00:19:44,270
Mimi nina kutumia SearchHelp ili kila wakati mimi kupiga simu hii kazi

270
00:19:44,270 --> 00:19:47,910
Nina mwanzo wa ambapo mimi nina kuangalia kwa katika safu na mwisho

271
00:19:47,910 --> 00:19:49,380
ya ambapo mimi nina kuangalia safu.

272
00:19:49,380 --> 00:19:55,330
>> Kwa kila hatua ambapo ni kusema ni kipengele katikati, ambayo ni mwanzo wa mwisho + / 2,

273
00:19:55,330 --> 00:19:58,850
ni sawa sawa kwa nini sisi ni kuangalia kwa?

274
00:19:58,850 --> 00:20:04,650
Na kama ni, basi sisi kupatikana, na mimi nadhani kwamba anapata kupita hadi ngazi ya recursion.

275
00:20:04,650 --> 00:20:12,540
Na kama kwamba si kweli, basi sisi kuangalia kama kwamba thamani ya katikati ya safu ni kubwa mno,

276
00:20:12,540 --> 00:20:19,320
katika kesi ambayo sisi kuangalia nusu ya kushoto ya safu kwa kwenda kutoka mwanzo hadi index katikati.

277
00:20:19,320 --> 00:20:22,710
Na vinginevyo sisi kufanya nusu ya mwisho.

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

279
00:20:24,740 --> 00:20:27,730
Kwamba sauti nzuri.

280
00:20:27,730 --> 00:20:36,640
Okay, kwa hivyo mambo ya wanandoa, na kwa kweli, hii ni kitu sana wa ngazi za juu

281
00:20:36,640 --> 00:20:41,270
kwamba kamwe haja ya kujua kwa ajili ya kozi hii, lakini ni kweli.

282
00:20:41,270 --> 00:20:46,080
Majukumu ya kujirudia, wewe daima kusikia kwamba wao ni mpango mbaya

283
00:20:46,080 --> 00:20:51,160
kwa sababu kama wewe recursively wito mwenyewe mara nyingi sana, unaweza kupata stack kufurika

284
00:20:51,160 --> 00:20:54,990
tangu, kama nilivyosema hapo kabla, kila kazi anapata stack yake mwenyewe frame.

285
00:20:54,990 --> 00:20:59,500
Hivyo kila wito wa kazi ya kujirudia anapata stack yake mwenyewe frame.

286
00:20:59,500 --> 00:21:04,140
Hivyo kama wewe kufanya wito 1000 kujirudia, unaweza kupata muafaka stack 1000,

287
00:21:04,140 --> 00:21:08,390
na haraka wewe kusababisha kuwa wengi mno stack muafaka na mambo kuvunja tu.

288
00:21:08,390 --> 00:21:13,480
Hivyo ndiyo sababu kazi ya kujirudia kwa ujumla mbaya.

289
00:21:13,480 --> 00:21:19,370
Lakini kuna subset nzuri ya utendaji kazi ya kujirudia kuitwa mkia-kujirudia,

290
00:21:19,370 --> 00:21:26,120
na hii hutokea kwa kuwa mfano wa moja ambapo kama mkusanyaji matangazo hii

291
00:21:26,120 --> 00:21:29,920
na ni lazima, Nadhani - katika Clang kama wewe kupita-O2 bendera

292
00:21:29,920 --> 00:21:33,250
basi itakuwa taarifa hii ni mkia kujirudia na kufanya mambo mema.

293
00:21:33,250 --> 00:21:40,050
>> Itakuwa Suza huo stack frame tena na tena kwa kila simu ya kujirudia.

294
00:21:40,050 --> 00:21:47,010
Na hivyo tangu unatumia huo stack frame, huna haja ya kuwa na wasiwasi kuhusu

295
00:21:47,010 --> 00:21:51,690
milele stack ya kufurika, na wakati huo huo, kama wewe alisema kabla,

296
00:21:51,690 --> 00:21:56,380
ambapo mara moja kurudi kweli, basi ina kurudi up yote ya muafaka haya stack

297
00:21:56,380 --> 00:22:01,740
na wito kwa 10 SearchHelp ina kurudi 9, ina kurudi 8.

298
00:22:01,740 --> 00:22:05,360
Hivyo kwamba haina haja ya kutokea wakati kazi ni mkia kujirudia.

299
00:22:05,360 --> 00:22:13,740
Na hivyo hufanya nini hii mkia kazi kujirudia ni taarifa kwamba kwa yoyote wito aliopewa searchHelp

300
00:22:13,740 --> 00:22:18,470
wito kujirudia kwamba ni kufanya ni nini ni kurudi.

301
00:22:18,470 --> 00:22:25,290
Hivyo katika kwanza mwito kwa SearchHelp, sisi aidha mara moja kurudi uongo,

302
00:22:25,290 --> 00:22:29,590
mara moja kurudi kweli, au sisi kufanya wito kujirudia kwa SearchHelp

303
00:22:29,590 --> 00:22:33,810
ambapo nini tuko kurudi ni nini wito kwamba ni kurudi.

304
00:22:33,810 --> 00:22:51,560
Na tunaweza kufanya hili kama sisi alifanya kitu kama int x = SearchHelp, kurudi x * 2,

305
00:22:51,560 --> 00:22:55,440
baadhi tu ya mabadiliko random.

306
00:22:55,440 --> 00:23:01,470
>> Hivyo sasa wito huu kujirudia, hii int x = SearchHelp kujirudia wito,

307
00:23:01,470 --> 00:23:05,740
hakuna tena mkia kujirudia kwa sababu ni kweli gani kuwa kurudi

308
00:23:05,740 --> 00:23:10,400
nyuma sura zilizotangulia stack ili kwamba wito kwa kazi uliopita

309
00:23:10,400 --> 00:23:13,040
wanaweza kufanya kitu kwa thamani ya kurudi.

310
00:23:13,040 --> 00:23:22,190
Hivyo hii si mkia kujirudia, lakini kile tulikuwa kabla ni nicely mkia kujirudia. Yeah.

311
00:23:22,190 --> 00:23:27,000
[Mwanafunzi] Je, si pili kesi ya msingi kuwa checked kwanza

312
00:23:27,000 --> 00:23:30,640
kwa sababu kuna inaweza kuwa hali ambapo wakati kupita hoja

313
00:23:30,640 --> 00:23:35,770
una kuanza = mwisho, lakini ni thamani sindano.

314
00:23:35,770 --> 00:23:47,310
Swali hatuwezi kukimbia katika kesi ambapo mwisho ni thamani sindano

315
00:23:47,310 --> 00:23:52,000
au kuanza = mwisho, ipasavyo, kuanza = mwisho

316
00:23:52,000 --> 00:23:59,480
na wewe si kweli kwamba checked thamani fulani bado,

317
00:23:59,480 --> 00:24:03,910
kisha kuanza + mwisho / 2 ni kwenda tu kuwa thamani sawa.

318
00:24:03,910 --> 00:24:07,890
Lakini tumekuwa tayari kurudi uongo na sisi kamwe kweli checked thamani.

319
00:24:07,890 --> 00:24:14,240
Hivyo kwa uchache sana, katika wito wa kwanza, kama kawaida ni 0, kisha tunataka kurudi uongo.

320
00:24:14,240 --> 00:24:17,710
Lakini kama kawaida ni 1, kisha kuanza si kwenda mwisho sawa,

321
00:24:17,710 --> 00:24:19,820
na tutaweza angalau kuangalia kipengele moja.

322
00:24:19,820 --> 00:24:26,750
Lakini nadhani ni haki katika kwamba tunaweza kuishia katika kesi ambapo kuanza + mwisho / 2,

323
00:24:26,750 --> 00:24:31,190
kuanza kuishia kuwa sawa kama kuanza + mwisho / 2,

324
00:24:31,190 --> 00:24:35,350
lakini sisi kamwe kweli checked kwamba kipengele.

325
00:24:35,350 --> 00:24:44,740
>> Hivyo kama sisi kwanza kuangalia ni kipengele katikati thamani sisi ni kuangalia kwa,

326
00:24:44,740 --> 00:24:47,110
basi tunaweza mara moja kurudi kweli.

327
00:24:47,110 --> 00:24:50,740
Mwingine kama uko sawa, basi hakuna uhakika katika kuendelea

328
00:24:50,740 --> 00:24:58,440
tangu tuko tu kwenda update kwa kesi ambapo sisi ni juu ya safu moja-kipengele.

329
00:24:58,440 --> 00:25:01,110
Kama kwamba kipengele moja si moja sisi ni kuangalia kwa,

330
00:25:01,110 --> 00:25:03,530
basi kila kitu ni makosa. Yeah.

331
00:25:03,530 --> 00:25:08,900
[Mwanafunzi] jambo ni kwamba tangu ukubwa ni kweli kubwa kuliko idadi ya vipengele katika safu,

332
00:25:08,900 --> 00:25:13,070
tayari kuna kukabiliana - >> Hivyo mapenzi kawaida -

333
00:25:13,070 --> 00:25:19,380
[Mwanafunzi] Sema ikiwa safu ilikuwa kawaida 0, kisha SearchHelp kweli itakuwa kuangalia haystack ya 0

334
00:25:19,380 --> 00:25:21,490
juu ya wito wa kwanza.

335
00:25:21,490 --> 00:25:25,300
safu ina ukubwa 0, hivyo ni 0 - >> Yeah.

336
00:25:25,300 --> 00:25:30,750
Kuna kitu kingine kwamba - inaweza kuwa nzuri. Hebu fikiria.

337
00:25:30,750 --> 00:25:40,120
Hivyo kama safu alikuwa vipengele 10 na moja katikati tunakwenda kuangalia ni index 5,

338
00:25:40,120 --> 00:25:45,700
hivyo sisi ni kuangalia 5, na hebu kusema kwamba thamani ni kidogo.

339
00:25:45,700 --> 00:25:50,720
Hivyo sisi ni kutupa kila kitu mbali na kuendelea 5.

340
00:25:50,720 --> 00:25:54,030
Hivyo kuanza + mwisho / 2 ni kwenda kuwa mwisho wetu mpya,

341
00:25:54,030 --> 00:25:57,450
hivyo yeah, ni daima kwenda kukaa zaidi ya mwisho wa safu.

342
00:25:57,450 --> 00:26:03,570
Kama ni kesi kama ilikuwa hata au isiyo ya kawaida, basi tunataka kuangalia, kusema, 4,

343
00:26:03,570 --> 00:26:05,770
lakini bado tuko kutupa mbali -

344
00:26:05,770 --> 00:26:13,500
Hivyo yeah, mwisho ni daima itakuwa ng'ambo ya mwisho halisi wa safu.

345
00:26:13,500 --> 00:26:18,350
Hivyo mambo sisi ni kulenga, mwisho ni daima itakuwa moja baada ya hapo.

346
00:26:18,350 --> 00:26:24,270
Na hivyo kama mwanzo gani milele mwisho sawa, sisi ni katika safu ya ukubwa 0.

347
00:26:24,270 --> 00:26:35,600
>> Kitu nyingine mimi nilikuwa nafikiri ni sisi ni uppdatering kuanza kuwa kuanza + mwisho / 2,

348
00:26:35,600 --> 00:26:44,020
hivyo hii ni kesi ya kwamba mimi nina matatizo na, ambapo kuanza + mwisho / 2

349
00:26:44,020 --> 00:26:46,820
ni kipengele tuko kuangalia.

350
00:26:46,820 --> 00:26:58,150
Hebu sema tulikuwa hii safu 10-kipengele. Chochote.

351
00:26:58,150 --> 00:27:03,250
Hivyo kuanza + mwisho / 2 ni kwenda kuwa kitu kama hii moja,

352
00:27:03,250 --> 00:27:07,060
na kama si kwamba thamani, kusema tunataka update.

353
00:27:07,060 --> 00:27:10,060
thamani ni kubwa zaidi, hivyo tunataka kuangalia hii nusu ya safu.

354
00:27:10,060 --> 00:27:15,910
Hivyo ni jinsi sisi ni uppdatering kuanza, sisi ni uppdatering mwanzo hadi sasa kuwa hii kipengele.

355
00:27:15,910 --> 00:27:23,790
Lakini hii bado wanaweza kazi, au kwa uchache sana, unaweza kufanya kuanza + mwisho / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Mwanafunzi] Huna haja ya kuwa na kuanza + mwisho [inaudible] >> Yeah.

357
00:27:27,850 --> 00:27:33,240
Sisi tayari checked hii ya kipengele na kujua si moja sisi ni kuangalia kwa.

358
00:27:33,240 --> 00:27:36,800
Hivyo hatuna haja ya update kuanza kuwa hii kipengele.

359
00:27:36,800 --> 00:27:39,560
Tunaweza tu ruka, na update kuanza kuwa hii kipengele.

360
00:27:39,560 --> 00:27:46,060
Na ni pale milele kesi, hebu sema, kwamba hii ingekuwa mwisho,

361
00:27:46,060 --> 00:27:53,140
hivyo kisha kuanza itakuwa hii, kuanza + mwisho / 2 itakuwa hii,

362
00:27:53,140 --> 00:28:00,580
kuanza + mwisho - Yeah, nadhani unaweza kuishia katika recursion usio.

363
00:28:00,580 --> 00:28:12,690
Hebu sema ni tu safu ya ukubwa 2 au safu ya kawaida ya 1. Nadhani hii kazi.

364
00:28:12,690 --> 00:28:19,490
Hivyo kwa sasa, ni kwamba kipengele kuanza na mwisho ni zaidi ya 1 ni.

365
00:28:19,490 --> 00:28:24,110
Hivyo kipengele kwamba sisi ni kwenda kuangalia ni hii moja,

366
00:28:24,110 --> 00:28:29,400
na kisha wakati sisi update kuanza, sisi ni uppdatering kuanza kuwa 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
ambayo inaenda kuisha sisi nyuma na kuanza kuwa hii kipengele.

368
00:28:33,160 --> 00:28:36,210
>> Hivyo sisi ni kuangalia kipengele sawa juu na juu tena.

369
00:28:36,210 --> 00:28:43,310
Hivyo hii ni kesi ambapo kila wito kujirudia lazima kweli update kitu.

370
00:28:43,310 --> 00:28:48,370
Hivyo tunahitaji kufanya kuanza + mwisho / 2 + 1, au mwingine kuna kesi

371
00:28:48,370 --> 00:28:50,710
ambapo sisi siyo kweli uppdatering mwanzo.

372
00:28:50,710 --> 00:28:53,820
Kila mtu kuona kwamba?

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

374
00:28:56,310 --> 00:29:03,860
Je, mtu yeyote kuwa na maswali juu ya ufumbuzi huu au maoni yoyote zaidi?

375
00:29:05,220 --> 00:29:10,280
Sawa. Je, mtu yeyote kuwa iterative ufumbuzi kwamba sisi wote kuangalia?

376
00:29:17,400 --> 00:29:20,940
Je sisi wote kufanya hivyo recursively?

377
00:29:20,940 --> 00:29:25,950
Au pia mimi nadhani kama kufunguliwa kwake, basi unaweza kuwa na overridden moja yako ya zamani.

378
00:29:25,950 --> 00:29:28,810
Je, ni moja kwa moja kuokoa? Mimi si chanya.

379
00:29:35,090 --> 00:29:39,130
Je, mtu yeyote kuwa iterative?

380
00:29:39,130 --> 00:29:42,430
Tunaweza kutembea kwa njia hiyo pamoja kama si.

381
00:29:46,080 --> 00:29:48,100
wazo ni kwenda kuwa sawa.

382
00:30:00,260 --> 00:30:02,830
Iterative ufumbuzi.

383
00:30:02,830 --> 00:30:07,140
Sisi ni kwenda wanataka kimsingi kufanya wazo sawa

384
00:30:07,140 --> 00:30:16,530
ambapo tunataka kuweka wimbo wa mwisho wa safu mpya na mwanzo mpya wa safu

385
00:30:16,530 --> 00:30:18,510
na kufanya hivyo tena na tena.

386
00:30:18,510 --> 00:30:22,430
Na kama nini tuko kuweka wimbo wa kama mwanzo na mwisho milele intersect,

387
00:30:22,430 --> 00:30:29,020
kisha sisi hakuwa wanajikuta na tunaweza kurudi uongo.

388
00:30:29,020 --> 00:30:37,540
Hivyo ni jinsi gani mimi kufanya hivyo? Mtu yeyote kuwa mapendekezo code au kwa ajili yangu ya kuvuta up?

389
00:30:42,190 --> 00:30:47,450
[Mwanafunzi] Je kitanzi wakati. >> Yeah.

390
00:30:47,450 --> 00:30:49,450
Wewe ni kwenda wanataka kufanya kitanzi.

391
00:30:49,450 --> 00:30:51,830
>> Je una code mimi naweza kuvuta, au nini walikuwa wewe kwenda kupendekeza?

392
00:30:51,830 --> 00:30:56,340
[Mwanafunzi] nadhani hivyo. >> Sawa. Hii hufanya mambo rahisi. Nini ilikuwa jina lako?

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

394
00:31:00,140 --> 00:31:04,190
Marekebisho 1. Sawa.

395
00:31:04,190 --> 00:31:13,200
Chini ni nini sisi inayoitwa kuanza kabla.

396
00:31:13,200 --> 00:31:17,080
Hadi si kabisa nini sisi inayoitwa mwisho kabla.

397
00:31:17,080 --> 00:31:22,750
Kweli, mwisho ni sasa ndani ya safu. Ni kipengele tunapaswa kuzingatia.

398
00:31:22,750 --> 00:31:26,890
Hivyo chini ni 0, juu ni ya kawaida ya safu - 1,

399
00:31:26,890 --> 00:31:34,780
na sasa sisi ni looping, na sisi ni kuangalia -

400
00:31:34,780 --> 00:31:37,340
Nadhani unaweza kutembea kwa njia hiyo.

401
00:31:37,340 --> 00:31:41,420
Nini ilikuwa mawazo yako kwa njia hii? Kutembea kwetu kupitia code yako.

402
00:31:41,420 --> 00:31:49,940
[Mwanafunzi] Uhakika. Angalia katika thamani haystack katikati na kulinganisha kwa sindano.

403
00:31:49,940 --> 00:31:58,520
Hivyo kama ni mkubwa kuliko sindano yako, basi unataka - oh, kwa kweli, kwamba wanapaswa kuwa nyuma.

404
00:31:58,520 --> 00:32:05,180
Wewe ni kwenda unataka kutupa nusu kulia, na hivyo yeah, kwamba wanapaswa kuwa njia.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Basi hii inapaswa kuwa chini? Ni kwamba alisema nini? >> [Mwanafunzi] Yeah.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Sawa. Chini.

407
00:32:10,390 --> 00:32:15,700
Hivyo kama nini sisi tunataka ni ndogo kuliko nini tunataka,

408
00:32:15,700 --> 00:32:19,410
kisha yeah, tunataka kutupa nusu kushoto,

409
00:32:19,410 --> 00:32:22,210
ambayo ina maana sisi ni uppdatering kila kitu sisi ni kuzingatia

410
00:32:22,210 --> 00:32:26,610
na kusonga chini kuelekea kulia wa safu.

411
00:32:26,610 --> 00:32:30,130
Hii inaonekana nzuri.

412
00:32:30,130 --> 00:32:34,550
Nadhani ana suala moja kwamba sisi alisema mmoja uliopita,

413
00:32:34,550 --> 00:32:49,760
ambapo kama ni ya chini na juu ni 0 1, kisha chini + up / 2 ni kwenda kuanzisha kuwa kitu kimoja tena.

414
00:32:49,760 --> 00:32:53,860
>> Na hata kama si kwamba kesi, bado ni ufanisi zaidi kwa uchache sana

415
00:32:53,860 --> 00:32:57,630
tu kutupa mbali kipengele sisi alimwangalia ambayo tunajua ni vibaya.

416
00:32:57,630 --> 00:33:03,240
Hivyo chini + up / 2 + 1 - >> [mwanafunzi] Kwamba lazima njia nyingine.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Au hii lazima - 1 na nyingine moja lazima + 1.

418
00:33:05,900 --> 00:33:09,580
[Mwanafunzi] Na kuwe mara mbili sawa na ishara. >> [Bowden] Yeah.

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

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

421
00:33:15,910 --> 00:33:21,280
Na hatimaye, sasa kwamba tuna hii 1 + - 1 kitu,

422
00:33:21,280 --> 00:33:31,520
ni - wanaweza kuwa - ni milele iwezekanavyo kwa ajili ya chini na kuishia na thamani kubwa zaidi kuliko up?

423
00:33:35,710 --> 00:33:40,320
Nadhani njia pekee ambayo inaweza kutokea - Je, inawezekana? >> [Mwanafunzi] sijui.

424
00:33:40,320 --> 00:33:45,220
Lakini kama anapata truncated na kisha anapata minus kwamba 1 na kisha - >> Yeah.

425
00:33:45,220 --> 00:33:47,480
[Mwanafunzi] Ingekuwa uwezekano kupata messed up.

426
00:33:49,700 --> 00:33:53,940
Nadhani ni lazima kuwa nzuri tu kwa sababu

427
00:33:53,940 --> 00:33:58,800
kwa kuwa na kuishia chini wangeli kuwa sawa, nadhani.

428
00:33:58,800 --> 00:34:03,070
Lakini kama ni sawa, basi sisi si wamefanya kitanzi wakati kuanza na

429
00:34:03,070 --> 00:34:06,670
na sisi tu ingekuwa akarudi thamani. Hivyo nadhani sisi ni vizuri sasa.

430
00:34:06,670 --> 00:34:11,530
Ona kwamba ingawa tatizo hili ni tena kujirudia,

431
00:34:11,530 --> 00:34:17,400
aina moja ya mawazo kuomba ambapo tunaweza kuona jinsi hii kwa urahisi hivyo kunafaa

432
00:34:17,400 --> 00:34:23,659
kwa ufumbuzi ya kujirudia na ukweli kwamba sisi ni tu uppdatering fahirisi tena na tena,

433
00:34:23,659 --> 00:34:29,960
sisi ni kufanya tatizo na ndogo ndogo, tunalenga subset ya safu.

434
00:34:29,960 --> 00:34:40,860
[Mwanafunzi] Ikiwa chini ni 0 na juu ni 1, wangeweza wote wawili kuwa 0 + 1/2, ambayo itakuwa kwenda 0,

435
00:34:40,860 --> 00:34:44,429
na kisha moja itakuwa + 1, moja itakuwa - 1.

436
00:34:47,000 --> 00:34:50,870
[Mwanafunzi] wapi sisi kuangalia usawa?

437
00:34:50,870 --> 00:34:55,100
Kama kama moja katikati ni kweli sindano?

438
00:34:55,100 --> 00:34:58,590
Sisi siyo sasa ya kufanya hivyo? Oh!

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

440
00:35:05,340 --> 00:35:13,740
Ndiyo. Hatuwezi tu kufanya mtihani chini hapa kwa sababu hebu sema katikati ya kwanza -

441
00:35:13,740 --> 00:35:16,430
[Mwanafunzi] Ni kweli kama si kutupa amefungwa.

442
00:35:16,430 --> 00:35:20,220
Hivyo kama wewe kutupa amefungwa, una kuangalia ni ya kwanza au chochote.

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

444
00:35:23,350 --> 00:35:29,650
Hivyo sasa tuna kutupwa mbali moja sisi sasa inaonekana katika,

445
00:35:29,650 --> 00:35:33,260
ambayo ina maana sisi sasa wanahitaji pia kuwa

446
00:35:33,260 --> 00:35:44,810
kama (haystack [(Asili + up) / 2] == sindano), basi tunaweza kurudi kweli.

447
00:35:44,810 --> 00:35:52,070
Na kama mimi kuweka mwingine au tu kama, ina maana halisi kitu kimoja

448
00:35:52,070 --> 00:35:57,110
kwa sababu hii ingekuwa akarudi kweli.

449
00:35:57,110 --> 00:36:01,450
Basi, mimi itabidi kuweka mwingine ikiwa, lakini haijalishi.

450
00:36:01,450 --> 00:36:10,440
>> Hivyo mwingine kama hii, pengine hii, na hili ni jambo la kawaida mimi kufanya

451
00:36:10,440 --> 00:36:14,340
ambapo hata kama ni kesi ambapo kila kitu ni nzuri hapa,

452
00:36:14,340 --> 00:36:22,780
kama chini hawezi kuwa mkuu kuliko juu, ni si thamani ya hoja kuhusu kama hiyo ni kweli.

453
00:36:22,780 --> 00:36:28,010
Hivyo unaweza kusema kama vile wakati chini ni chini ya au sawa na

454
00:36:28,010 --> 00:36:30,720
au wakati wa chini ni chini ya

455
00:36:30,720 --> 00:36:35,300
hivyo kama wao ni milele sawa au chini kinachotokea kwa kupita juu,

456
00:36:35,300 --> 00:36:40,130
basi tunaweza kuvunja nje ya kitanzi hii.

457
00:36:41,410 --> 00:36:44,630
Maswali, hoja, maoni?

458
00:36:47,080 --> 00:36:49,270
Sawa. Hii inaonekana nzuri.

459
00:36:49,270 --> 00:36:52,230
Sasa tunataka kufanya aina.

460
00:36:52,230 --> 00:37:04,030
Kama sisi kwenda kwa marekebisho yangu ya pili, tunaona idadi hayo,

461
00:37:04,030 --> 00:37:07,550
lakini sasa hawawezi tena ili Iliyopangwa.

462
00:37:07,550 --> 00:37:12,840
Na tunataka kutekeleza aina yoyote kutumia algorithm katika O ya n logi n.

463
00:37:12,840 --> 00:37:17,240
Hivyo ambayo algorithm unafikiri sisi wanapaswa kutekeleza hapa? >> [Mwanafunzi] kuchanganya aina.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Yeah. Changanya aina ni O (n logi n), hivyo kwamba ni nini tunakwenda kufanya.

465
00:37:23,810 --> 00:37:26,680
Na tatizo ni kwenda kuwa pretty sawa,

466
00:37:26,680 --> 00:37:31,920
ambapo ni urahisi kunafaa kwa ufumbuzi kujirudia.

467
00:37:31,920 --> 00:37:35,580
Tunaweza pia kuja na ufumbuzi iterative kama tunataka,

468
00:37:35,580 --> 00:37:42,540
lakini recursion itakuwa rahisi hapa na tunapaswa kufanya recursion.

469
00:37:45,120 --> 00:37:49,530
Nadhani sisi tutakwenda kwa njia ya aina kuunganisha kwanza,

470
00:37:49,530 --> 00:37:54,280
ingawa kuna video lovely juu ya aina kuunganisha tayari. [Kicheko]

471
00:37:54,280 --> 00:37:59,780
Hivyo kuunganisha aina kuna - I am kupoteza kiasi ya karatasi hii.

472
00:37:59,780 --> 00:38:02,080
Oh, kuna moja tu kushoto.

473
00:38:02,080 --> 00:38:03,630
Hivyo kuunganisha.

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

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

476
00:38:29,910 --> 00:38:33,460
Kuunganisha inachukua wawili arrays tofauti.

477
00:38:33,460 --> 00:38:36,780
Mmoja mmoja arrays wale wawili ni wawili Iliyopangwa.

478
00:38:36,780 --> 00:38:40,970
Hivyo hii safu, 1, 3, 5, Iliyopangwa. Hii safu, 0, 2, 4, Iliyopangwa.

479
00:38:40,970 --> 00:38:46,710
Sasa nini kuunganisha lazima kufanya ni kuchanganya yao katika safu moja ambayo ni yenyewe Iliyopangwa.

480
00:38:46,710 --> 00:38:57,130
Hivyo tunataka safu ya ukubwa 6 kwamba ni kwenda kuwa mambo haya ndani yake

481
00:38:57,130 --> 00:38:59,390
ili Iliyopangwa.

482
00:38:59,390 --> 00:39:03,390
>> Na ili tuweze kuchukua faida ya ukweli kwamba arrays hizi mbili ni sorted

483
00:39:03,390 --> 00:39:06,800
kufanya hivyo katika muda linear,

484
00:39:06,800 --> 00:39:13,510
linear wakati maana ikiwa safu hii ni ya kawaida x na hii ni kawaida y,

485
00:39:13,510 --> 00:39:20,970
kisha algorithm jumla lazima O (x + y). Sawa.

486
00:39:20,970 --> 00:39:23,150
Hivyo mapendekezo.

487
00:39:23,150 --> 00:39:26,030
[Mwanafunzi] Inawezekana sisi kuanza kutoka kushoto?

488
00:39:26,030 --> 00:39:30,150
Hivyo itabidi kuweka 0 kwanza chini na kisha 1 na kisha hapa uko katika 2.

489
00:39:30,150 --> 00:39:33,320
Hivyo ni aina ya kama una tab hiyo kusonga ya kulia. >> [Bowden] Yeah.

490
00:39:33,320 --> 00:39:41,070
Kwa wote wa arrays haya ikiwa sisi tu kuzingatia kipengele leftmost.

491
00:39:41,070 --> 00:39:43,530
Kwa sababu wote wawili arrays wanatenganishwa, tunajua kwamba haya mambo 2

492
00:39:43,530 --> 00:39:46,920
ni ndogo vipengele katika safu aidha.

493
00:39:46,920 --> 00:39:53,500
Hivyo hiyo ina maana kwamba 1 ya vipengele wale 2 lazima kipengele ndogo katika safu yetu enheten.

494
00:39:53,500 --> 00:39:58,190
Ni tu hivyo hutokea kuwa ndogo ni moja kwa wakati haki hii.

495
00:39:58,190 --> 00:40:02,580
Hivyo sisi kuchukua 0, kuingiza upande wa kushoto kwa sababu ni chini ya 0 1,

496
00:40:02,580 --> 00:40:08,210
hivyo kuchukua 0, kuingiza katika nafasi yetu ya kwanza, na kisha sisi update hii

497
00:40:08,210 --> 00:40:12,070
kwa sasa kuzingatia kipengele kwanza.

498
00:40:12,070 --> 00:40:14,570
Na sasa sisi kurudia.

499
00:40:14,570 --> 00:40:20,670
Hivyo sasa sisi kulinganisha na 2 1. 1 ni ndogo, hivyo tutaweza Insert 1.

500
00:40:20,670 --> 00:40:25,300
Sisi update hii pointer na kumweka kwa guy.

501
00:40:25,300 --> 00:40:33,160
Sasa sisi kufanya hivyo tena, hivyo 2. Hii update, kulinganisha haya 2, 3.

502
00:40:33,160 --> 00:40:37,770
Hii updates, basi 4 na 5.

503
00:40:37,770 --> 00:40:42,110
Hivyo kwamba ni kuunganisha.

504
00:40:42,110 --> 00:40:49,010
>> Ni lazima pretty dhahiri kwamba ni linear wakati tangu sisi tu kwenda katika kila kipengele mara moja.

505
00:40:49,010 --> 00:40:55,980
Na kwamba ni hatua kubwa kwa kutekeleza kuunganisha aina anafanya hili.

506
00:40:55,980 --> 00:40:59,330
Na si kwamba ni vigumu.

507
00:40:59,330 --> 00:41:15,020
mambo ya wanandoa na wasiwasi juu ya ni wacha kusema tulikuwa kuunganisha 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Katika kesi hii sisi kuishia katika mazingira ambapo mmoja huu ni kwenda kuwa ndogo,

509
00:41:30,930 --> 00:41:36,160
kisha sisi update hii pointer, mmoja huu ni kwenda kuwa ndogo, update hii,

510
00:41:36,160 --> 00:41:41,280
moja hii ni ndogo, na sasa una kutambua

511
00:41:41,280 --> 00:41:44,220
wakati umeweka kweli kukimbia nje ya mambo ya kulinganisha na.

512
00:41:44,220 --> 00:41:49,400
Tangu sisi tayari kutumika hii safu nzima,

513
00:41:49,400 --> 00:41:55,190
kila kitu katika safu hii ni sasa tu kuingizwa katika hapa.

514
00:41:55,190 --> 00:42:02,040
Hivyo kama sisi milele kukimbia katika hatua ambapo moja ya arrays yetu ni kabisa ilijiunga tayari,

515
00:42:02,040 --> 00:42:06,510
kisha sisi tu kuchukua mambo yote ya safu nyingine na Insert yao katika mwisho wa safu.

516
00:42:06,510 --> 00:42:13,630
Hivyo tunaweza tu Insert 4, 5, 6. Sawa.

517
00:42:13,630 --> 00:42:18,070
Hiyo ni jambo moja kuangalia nje kwa.

518
00:42:22,080 --> 00:42:26,120
Kutekeleza kwamba wanapaswa kuwa hatua 1.

519
00:42:26,120 --> 00:42:32,600
Changanya kuchambua kisha kuzingatia kwamba, ni hatua 2, 2 silly hatua.

520
00:42:38,800 --> 00:42:42,090
Hebu tu kutoa hii safu.

521
00:42:57,920 --> 00:43:05,680
Hivyo kuunganisha aina, hatua 1 ni recursively kuvunja safu ndani ya nusu.

522
00:43:05,680 --> 00:43:09,350
Hivyo kupasuliwa hii safu ndani ya nusu.

523
00:43:09,350 --> 00:43:22,920
Sisi sasa kuwa 4, 15, 16, 50 na 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Na sasa sisi kufanya hivyo tena na sisi hawa umegawanyika katika halves.

525
00:43:25,800 --> 00:43:27,530
Mimi itabidi kufanya hivyo kwa upande huu.

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

527
00:43:34,790 --> 00:43:37,440
Tunataka kufanya kitu kimoja hapa.

528
00:43:37,440 --> 00:43:40,340
Na sasa sisi kupasuliwa ndani halves tena.

529
00:43:40,340 --> 00:43:51,080
Na tuna 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Hivyo kuwa ni msingi wetu kesi.

531
00:43:53,170 --> 00:44:00,540
Mara arrays ni ya kawaida ya 1, basi sisi kuacha na kuigawanya halves.

532
00:44:00,540 --> 00:44:03,190
>> Sasa tunafanya nini kwa hili?

533
00:44:03,190 --> 00:44:15,730
Sisi kuishia hii pia kuvunja chini ndani ya 8, 23, 42, na 108.

534
00:44:15,730 --> 00:44:24,000
Hivyo sasa kwamba sisi ni katika hatua hii, sasa hatua mbili za aina kuunganisha ni kuunganisha tu jozi orodha.

535
00:44:24,000 --> 00:44:27,610
Hivyo tunataka kuunganisha haya. Sisi tu wito merge.

536
00:44:27,610 --> 00:44:31,410
Tunajua kuunganisha haya kurudi ili Iliyopangwa.

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

538
00:44:33,920 --> 00:44:41,440
Sasa tunataka kuunganisha haya, na kwamba atarudi orodha na wale ili Iliyopangwa,

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

540
00:44:44,160 --> 00:44:57,380
Sisi kuunganisha wale - siwezi kuandika - 8, 23 na 42, 108.

541
00:44:57,380 --> 00:45:02,890
Hivyo tuna jozi enheten mara moja.

542
00:45:02,890 --> 00:45:05,140
Sasa sisi tu kuunganisha tena.

543
00:45:05,140 --> 00:45:10,130
Ona kwamba kila moja ya orodha hizi ni Iliyopangwa katika yenyewe,

544
00:45:10,130 --> 00:45:15,220
na kisha tunaweza tu kuunganisha orodha hizi na kupata orodha ya ukubwa 4 ambayo ni Iliyopangwa

545
00:45:15,220 --> 00:45:19,990
na kuunganisha orodha hizi mbili na kupata orodha ya ukubwa 4 kwamba ni Iliyopangwa.

546
00:45:19,990 --> 00:45:25,710
Na hatimaye, tunaweza kuunganisha orodha hizo mbili ya ukubwa 4 kupata orodha moja ya ukubwa 8 kwamba ni Iliyopangwa.

547
00:45:25,710 --> 00:45:34,030
Hivyo kwa kuona kwamba hii ni jumla n n logi, sisi tayari kuona kwamba kuunganisha ni linear,

548
00:45:34,030 --> 00:45:40,390
hivyo wakati sisi ni kushughulika na kuunganisha haya, hivyo kama gharama ya jumla ya kuunganisha

549
00:45:40,390 --> 00:45:43,410
kwa orodha hizi mbili ni kwa sababu tu 2 -

550
00:45:43,410 --> 00:45:49,610
Au vizuri, ni O ya n, lakini n hapa ni tu haya mambo 2, hivyo ni 2.

551
00:45:49,610 --> 00:45:52,850
Na hawa 2 itakuwa 2 na hizi 2 itakuwa 2 na hizi 2 itakuwa 2,

552
00:45:52,850 --> 00:45:58,820
hivyo katika yote ya huingiza kwamba tunahitaji kufanya, sisi kuishia kufanya n.

553
00:45:58,820 --> 00:46:03,210
Kama 2 + 2 + 2 + 2 ni 8, ambayo ni n,

554
00:46:03,210 --> 00:46:08,060
hivyo gharama ya kuunganisha katika kuweka hii ni n.

555
00:46:08,060 --> 00:46:10,810
Na kisha kitu kimoja hapa.

556
00:46:10,810 --> 00:46:16,980
Tutaweza kuunganisha hizi 2, basi hawa 2, na kila mmoja kuunganisha hii itachukua shughuli nne,

557
00:46:16,980 --> 00:46:23,610
hii kuunganisha itachukua shughuli nne, lakini kwa mara nyingine tena, kati ya haya yote, kwa

558
00:46:23,610 --> 00:46:29,030
sisi kuishia kuunganisha n mambo ya jumla, na hivyo hatua hii inachukua n.

559
00:46:29,030 --> 00:46:33,670
Na hivyo kila ngazi inachukua vipengele n kuwa zimeunganishwa.

560
00:46:33,670 --> 00:46:36,110
>> Na jinsi wengi ngazi ni huko?

561
00:46:36,110 --> 00:46:40,160
Katika kila ngazi, safu yetu kukua kwa ukubwa 2.

562
00:46:40,160 --> 00:46:44,590
Hapa arrays yetu ni ya kawaida ya 1, hapa wao ni wa kawaida 2, hapa wao ni wa kawaida 4,

563
00:46:44,590 --> 00:46:46,470
na hatimaye, wao uko wa kawaida 8.

564
00:46:46,470 --> 00:46:56,450
Hivyo kwa vile ni mara mbili, kuna kwenda kuwa jumla ya logi n ya hizi ngazi.

565
00:46:56,450 --> 00:47:02,090
Hivyo kwa logi n ngazi, kila ngazi ya mtu binafsi kuchukua n shughuli jumla,

566
00:47:02,090 --> 00:47:05,720
sisi kupata logi n n algorithm.

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

568
00:47:08,940 --> 00:47:13,320
Je watu tayari alifanya maendeleo juu ya jinsi ya kutekeleza mpango huu?

569
00:47:13,320 --> 00:47:18,260
Ni mtu yeyote tayari katika hali ambapo naweza tu kuvuta kanuni zao?

570
00:47:20,320 --> 00:47:22,260
Siwezi kutoa dakika.

571
00:47:24,770 --> 00:47:27,470
Moja hii ni ya kwenda kuwa mrefu.

572
00:47:27,470 --> 00:47:28,730
Mimi sana kupendekeza chamka -

573
00:47:28,730 --> 00:47:30,510
Huna kufanya recursion kwa kuunganisha

574
00:47:30,510 --> 00:47:33,750
kwa sababu ya kufanya recursion kwa kuunganisha, utaenda kuwa na kupita rundo la ukubwa tofauti.

575
00:47:33,750 --> 00:47:37,150
Unaweza, lakini ni annoying.

576
00:47:37,150 --> 00:47:43,720
Lakini recursion kwa aina yenyewe ni rahisi pretty.

577
00:47:43,720 --> 00:47:49,190
Wewe tu literally kuwaita aina ya nusu ya kushoto, aina ya nusu ya haki. Sawa.

578
00:47:51,770 --> 00:47:54,860
Mtu yeyote kuwa kitu naweza kuvuta juu bado?

579
00:47:54,860 --> 00:47:57,540
Au mwingine mimi nitakupa dakika.

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

581
00:47:59,900 --> 00:48:02,970
Mtu yeyote kuwa kitu tunaweza kufanya kazi na?

582
00:48:05,450 --> 00:48:09,680
Au mwingine tutaweza tu kazi na hili na kisha kupanua kutoka huko.

583
00:48:09,680 --> 00:48:14,050
>> Mtu yeyote kuwa zaidi ya hii kwamba naweza kuvuta up?

584
00:48:14,050 --> 00:48:17,770
[Mwanafunzi] Yeah. Unaweza kuvuta juu yangu. >> Sawa.

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

586
00:48:22,170 --> 00:48:25,280
[Mwanafunzi] Kulikuwa na mengi ya hali ya. >> Oh, risasi. Je, unaweza -

587
00:48:25,280 --> 00:48:28,110
[Mwanafunzi] nina atayaokoa. >> Yeah.

588
00:48:32,420 --> 00:48:35,730
Hivyo sisi gani kufanya kuunganisha tofauti.

589
00:48:35,730 --> 00:48:38,570
Oh, lakini siyo kuwa mbaya.

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

591
00:48:41,650 --> 00:48:47,080
Hivyo ni aina yenyewe tu wito mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Tueleze nini mergeSortHelp gani.

593
00:48:49,530 --> 00:48:55,700
[Mwanafunzi] MergeSortHelp pretty kiasi gani hatua mbili kuu,

594
00:48:55,700 --> 00:49:01,270
ambayo ni ya kutatua kila nusu ya safu na kisha kuunganisha yao wote.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Sawa, hivyo nipe pili.

596
00:49:10,850 --> 00:49:13,210
Nadhani hii - >> [mwanafunzi] nahitaji -

597
00:49:17,100 --> 00:49:19,400
Yeah. Mimi kukosa kitu.

598
00:49:19,400 --> 00:49:23,100
Katika kuunganisha, mimi kutambua kwamba mimi haja ya kuunda safu mpya

599
00:49:23,100 --> 00:49:26,530
sababu sikuweza kufanya hivyo katika mahali. >> Ndiyo. Huwezi. Kusahihisha.

600
00:49:26,530 --> 00:49:28,170
[Mwanafunzi] Basi mimi kujenga safu mpya.

601
00:49:28,170 --> 00:49:31,510
Nimesahau mwisho wa kuunganisha kwa re-kubadilika.

602
00:49:31,510 --> 00:49:34,490
Sawa. Tunahitaji safu mpya.

603
00:49:34,490 --> 00:49:41,000
Katika aina kuunganisha, hii ni karibu daima kweli.

604
00:49:41,000 --> 00:49:44,340
Sehemu ya gharama ya algorithm bora wakati-busara

605
00:49:44,340 --> 00:49:47,310
ni karibu daima wanaohitaji kutumia kidogo zaidi kumbukumbu.

606
00:49:47,310 --> 00:49:51,570
Hivyo hapa, hakuna jambo jinsi ya kufanya kuunganisha aina ya,

607
00:49:51,570 --> 00:49:54,780
wewe bila shaka haja ya kutumia baadhi ya kumbukumbu ya ziada.

608
00:49:54,780 --> 00:49:58,240
Yeye au yeye aliumba safu mpya.

609
00:49:58,240 --> 00:50:03,400
Na kisha wewe sema mwishoni sisi tu haja ya nakala safu mpya katika safu ya awali.

610
00:50:03,400 --> 00:50:04,830
[Mwanafunzi] Nadhani hivyo, yeah.

611
00:50:04,830 --> 00:50:08,210
Mimi sijui kama kwamba kazi katika suala la kuhesabu kura kwa kumbukumbu au chochote -

612
00:50:08,210 --> 00:50:11,650
Yeah, itakuwa kazi. >> [Mwanafunzi] Sawa.

613
00:50:20,620 --> 00:50:24,480
Je kujaribu kuendesha hii? >> [Mwanafunzi] Hapana, bado. >> Sawa.

614
00:50:24,480 --> 00:50:28,880
Jaribu mbio, na basi mimi itabidi kuzungumza juu yake kwa ajili ya pili.

615
00:50:28,880 --> 00:50:35,200
[Mwanafunzi] nahitaji kuwa na prototypes wote kazi na kila kitu, ingawa, sawa?

616
00:50:37,640 --> 00:50:40,840
prototypes kazi. Oh, maana kama - Ndiyo.

617
00:50:40,840 --> 00:50:43,040
Panga wito mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Hivyo ili kwa aina kuwaita mergeSortHelp, mergeSortHelp lazima aidha wamekuwa defined

619
00:50:47,390 --> 00:50:56,370
kabla ya aina au sisi tu haja ya mfano. Tu nakala na kuweka kwamba.

620
00:50:56,370 --> 00:50:59,490
Na vile vile, mergeSortHelp wito kuunganisha,

621
00:50:59,490 --> 00:51:03,830
lakini kuunganisha haijawahi defined bado, hivyo tunaweza kujua tu basi mergeSortHelp

622
00:51:03,830 --> 00:51:08,700
kwamba kwamba ni nini kuunganisha ni kwenda kuangalia kama, na kwamba ni kwamba.

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

624
00:51:22,770 --> 00:51:32,660
Tuna suala hapa ambapo hatuna kesi ya msingi.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp ni kujirudia, hivyo kazi yoyote ya kujirudia

626
00:51:38,110 --> 00:51:42,610
ni kwenda haja ya baadhi ya aina ya kesi ya msingi ya kujua wakati kuacha recursively linalojiita.

627
00:51:42,610 --> 00:51:45,590
Nini msingi wetu kesi kwenda kuwa hapa? Yeah.

628
00:51:45,590 --> 00:51:49,110
[Mwanafunzi] Kama kawaida ni 1? >> [Bowden] Ndiyo.

629
00:51:49,110 --> 00:51:56,220
Hivyo kama tuliona haki pale, sisi kusimamishwa arrays splitting

630
00:51:56,220 --> 00:52:01,850
mara moja sisi got katika arrays ya kawaida ya 1, ambayo inevitably wanatenganishwa wenyewe.

631
00:52:01,850 --> 00:52:09,530
Hivyo kama kawaida sawa na 1, tunajua safu tayari Iliyopangwa,

632
00:52:09,530 --> 00:52:12,970
hivyo tunaweza tu kurudi.

633
00:52:12,970 --> 00:52:16,880
>> Ona kwamba ni batili, hivyo hatuwezi kurudi chochote hasa, sisi tu kurudi.

634
00:52:16,880 --> 00:52:19,580
Sawa. Basi hiyo ni msingi wetu kesi.

635
00:52:19,580 --> 00:52:27,440
Nadhani msingi wetu kesi inaweza pia kuwa kama sisi kutokea kwa kuwa kuunganisha safu ya ukubwa 0,

636
00:52:27,440 --> 00:52:30,030
sisi pengine unataka kuacha wakati fulani,

637
00:52:30,030 --> 00:52:33,610
hivyo tunaweza kusema tu kawaida chini ya 2 au chini zaidi au sawa na 1

638
00:52:33,610 --> 00:52:37,150
hivyo kwamba hii kazi kwa safu yoyote sasa.

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

640
00:52:38,870 --> 00:52:42,740
Basi hiyo ni msingi wetu kesi.

641
00:52:42,740 --> 00:52:45,950
Sasa unataka kutembea kwetu kupitia kuunganisha?

642
00:52:45,950 --> 00:52:49,140
Nini kesi hizi zote maana?

643
00:52:49,140 --> 00:52:54,480
Hadi hapa, sisi ni kufanya tu wazo huo, -

644
00:52:56,970 --> 00:53:02,470
[Mwanafunzi] Mimi haja ya kuwa na kupita kawaida na simu zote mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
Mimi aliongeza ukubwa kama msingi ya ziada na si huko, kama kawaida / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, ukubwa / 2, ukubwa / 2. >> [Mwanafunzi] Yeah, na pia katika kazi hapo juu pia.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Hapa? >> [Mwanafunzi] Tu kawaida. >> [Bowden] Oh. Ukubwa, kawaida? >> [Mwanafunzi] Yeah.

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

649
00:53:23,010 --> 00:53:26,580
Hebu fikiria kwa pili.

650
00:53:26,580 --> 00:53:28,780
Je, sisi kukimbia katika suala hilo?

651
00:53:28,780 --> 00:53:33,690
Sisi ni daima kutibu kushoto kama 0. >> [Mwanafunzi] No

652
00:53:33,690 --> 00:53:36,340
Hiyo ni vibaya mno. Sorry. Ni lazima kuanza. Yeah.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Sawa. Mimi kama kwamba bora.

654
00:53:39,230 --> 00:53:43,880
Na mwisho. Sawa.

655
00:53:43,880 --> 00:53:47,200
Hivyo sasa unataka kutembea kwetu kupitia kuunganisha? >> [Mwanafunzi] Sawa.

656
00:53:47,200 --> 00:53:52,150
Mimi tu kutembea kupitia safu hii mpya kwamba nimepata kuundwa.

657
00:53:52,150 --> 00:53:57,420
Kawaida yake ni ukubwa wa sehemu ya safu kwamba tunataka sorted

658
00:53:57,420 --> 00:54:03,460
na kujaribu kutafuta kipengele kwamba mimi wanapaswa kuweka katika hatua mpya safu.

659
00:54:03,460 --> 00:54:10,140
Hivyo kufanya hivyo, kwanza mimi nina kuangalia kama nusu ya kushoto ya safu inaendelea kuwa na vipengele yoyote zaidi,

660
00:54:10,140 --> 00:54:14,260
na kama hana, basi wewe kwenda chini kwa sharti kwamba mwingine, ambayo tu anasema

661
00:54:14,260 --> 00:54:20,180
sawa, ni lazima kuwa katika safu haki, na tutaweza kuweka kwamba katika ripoti ya sasa ya newArray.

662
00:54:20,180 --> 00:54:27,620
>> Na kisha vinginevyo, mimi nina kuangalia kama upande wa kulia wa safu pia kumaliza,

663
00:54:27,620 --> 00:54:30,630
katika kesi ambayo mimi tu ya kuweka katika kushoto.

664
00:54:30,630 --> 00:54:34,180
Kwamba wanaweza kweli kuwa muhimu. Mimi nina uhakika.

665
00:54:34,180 --> 00:54:40,970
Lakini anyway, na wengine wawili hundi ambayo ya mbili ni ndogo katika upande wa kushoto au kulia.

666
00:54:40,970 --> 00:54:49,770
Na pia katika kila kesi, mimi nina incrementing yoyote placeholder mimi increment.

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

668
00:54:52,040 --> 00:54:53,840
Hiyo inaonekana ni nzuri.

669
00:54:53,840 --> 00:54:58,800
Je, mtu yeyote kuwa na maoni au hoja au maswali?

670
00:55:00,660 --> 00:55:07,720
Hivyo kesi nne kwamba tuna kuleta mambo ndani tu kuwa - au inaonekana kama tano -

671
00:55:07,720 --> 00:55:13,100
lakini tuna kufikiria kama safu ya kushoto ina kukimbia nje ya mambo tunahitaji kuunganisha,

672
00:55:13,100 --> 00:55:16,390
kama safu haki ina kukimbia nje ya mambo tunahitaji kuunganisha -

673
00:55:16,390 --> 00:55:18,400
Mimi nina akionyesha chochote.

674
00:55:18,400 --> 00:55:21,730
Hivyo kama safu ya kushoto ina kukimbia nje ya mambo au safu haki ina kukimbia nje ya mambo.

675
00:55:21,730 --> 00:55:24,320
Wale ni kesi mbili.

676
00:55:24,320 --> 00:55:30,920
Tunahitaji pia kesi ya trivial kama kitu kushoto ni chini ya jambo sahihi.

677
00:55:30,920 --> 00:55:33,910
Kisha tunataka kuchagua kitu kushoto.

678
00:55:33,910 --> 00:55:37,630
Wale ni kesi.

679
00:55:37,630 --> 00:55:40,990
Hivyo hii ilikuwa sahihi, hivyo ndiyo hiyo.

680
00:55:40,990 --> 00:55:46,760
Array kushoto. Ni 1, 2, 3. Sawa. Hivyo yeah, hayo ni mambo nne sisi kutaka kufanya.

681
00:55:50,350 --> 00:55:54,510
Na sisi si kwenda juu ya iterative ufumbuzi.

682
00:55:54,510 --> 00:55:55,980
Napenda kupendekeza -

683
00:55:55,980 --> 00:56:03,070
Changanya aina ni mfano wa kazi kuwa ni wa si mkia kujirudia,

684
00:56:03,070 --> 00:56:07,040
si rahisi kufanya hivyo mkia kujirudia,

685
00:56:07,040 --> 00:56:13,450
lakini pia si rahisi sana kufanya hivyo iterative.

686
00:56:13,450 --> 00:56:16,910
Hii ni rahisi sana.

687
00:56:16,910 --> 00:56:19,170
Hii utekelezaji wa aina kuunganisha,

688
00:56:19,170 --> 00:56:22,140
kuchanganya, haijalishi wewe kufanya, wewe ni kwenda kujenga kuunganisha.

689
00:56:22,140 --> 00:56:29,170
>> Hivyo kuunganisha aina umejengwa juu ya kuunganisha recursively ni tu hizi mistari mitatu.

690
00:56:29,170 --> 00:56:34,700
Iteratively, ni zaidi annoying na zaidi vigumu kufikiri.

691
00:56:34,700 --> 00:56:41,860
Lakini ona kwamba si mkia kujirudia tangu mergeSortHelp - wakati wito yenyewe -

692
00:56:41,860 --> 00:56:46,590
bado anahitaji kufanya mambo baada anarudi hii kujirudia wito.

693
00:56:46,590 --> 00:56:50,830
Hivyo hii frame stack lazima kuendelea kuwepo hata baada ya wito huu.

694
00:56:50,830 --> 00:56:54,170
Na kisha wakati wewe piga hii, sura stack lazima kuendelea kuwepo

695
00:56:54,170 --> 00:56:57,780
sababu hata baada ya wito kwamba, bado tunahitaji kuunganisha.

696
00:56:57,780 --> 00:57:01,920
Na ni nontrivial kufanya mkia hii kujirudia.

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

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

699
00:57:09,860 --> 00:57:13,400
Hivyo kurejea kwa aina - oh, kuna mambo mawili nataka kuonyesha. Sawa.

700
00:57:13,400 --> 00:57:17,840
Tukirudi kwenye aina, tutaweza kufanya hivyo haraka.

701
00:57:17,840 --> 00:57:21,030
Au tafuta. Panga? Panga. Yeah.

702
00:57:21,030 --> 00:57:22,730
Tukirudi kwenye mwanzo wa aina.

703
00:57:22,730 --> 00:57:29,870
Tunataka kujenga algorithm kwamba kila safu kutumia yoyote algorithm

704
00:57:29,870 --> 00:57:33,660
katika O ya n.

705
00:57:33,660 --> 00:57:40,860
Hivyo jinsi hii inawezekana? Je, mtu yeyote kuwa na aina yoyote ya -

706
00:57:40,860 --> 00:57:44,300
Mimi aligusia kabla saa -

707
00:57:44,300 --> 00:57:48,300
Kama sisi ni juu ya kuboresha kutoka n logi n O ya n,

708
00:57:48,300 --> 00:57:51,450
sisi kuwa kuboreshwa algorithm yetu wakati-busara,

709
00:57:51,450 --> 00:57:55,250
ambayo ina maana nini sisi kwenda haja ya kufanya kwa ajili ya kufanya hivyo?

710
00:57:55,250 --> 00:57:59,520
[Mwanafunzi] Space. >> Yeah. Sisi ni kwenda kuwa na kutumia nafasi zaidi.

711
00:57:59,520 --> 00:58:04,490
Na si tu hata nafasi zaidi, ni exponentially nafasi zaidi.

712
00:58:04,490 --> 00:58:14,320
Hivyo nadhani aina hii ya algorithm ni Pseudo kitu, Pseudo polynom -

713
00:58:14,320 --> 00:58:18,980
Pseudo - siwezi kukumbuka. Pseudo kitu.

714
00:58:18,980 --> 00:58:22,210
Lakini ni kwa sababu tunahitaji kutumia kiasi nafasi

715
00:58:22,210 --> 00:58:28,610
kwamba hii ni mafanikio lakini si kweli.

716
00:58:28,610 --> 00:58:31,220
>> Na jinsi gani sisi kufikia hili?

717
00:58:31,220 --> 00:58:36,810
Tunaweza kufikia mafanikio haya kama sisi kuhakikisha kwamba yoyote ya kipengele fulani katika safu

718
00:58:36,810 --> 00:58:39,600
ni chini ya ukubwa fulani.

719
00:58:42,070 --> 00:58:44,500
Basi hebu tu kusema kwamba ukubwa ni 200,

720
00:58:44,500 --> 00:58:48,130
yoyote ya kipengele katika safu ni chini ya kawaida 200.

721
00:58:48,130 --> 00:58:51,080
Na hii ni kweli kweli sana.

722
00:58:51,080 --> 00:58:58,660
Unaweza urahisi sana kuwa na safu kwamba unajua kila kitu ndani yake

723
00:58:58,660 --> 00:59:00,570
ni kwenda kuwa chini ya idadi fulani.

724
00:59:00,570 --> 00:59:07,400
Kama kama una baadhi ya vector kabisa mkubwa au kitu

725
00:59:07,400 --> 00:59:11,810
lakini unajua kila kitu kinaenda kuwa kati ya 0 na 5,

726
00:59:11,810 --> 00:59:14,790
basi ni kwenda kuwa kwa kiasi kikubwa kasi ya kufanya hili.

727
00:59:14,790 --> 00:59:17,930
Na amefungwa juu ya yoyote ya vipengele ni 5,

728
00:59:17,930 --> 00:59:21,980
hivyo hii amefungwa, kwamba ni kiasi gani kumbukumbu utaenda kutumia.

729
00:59:21,980 --> 00:59:26,300
Hivyo amefungwa ni 200.

730
00:59:26,300 --> 00:59:32,960
Katika nadharia daima kuna amefungwa tangu integer inaweza tu kuwa hadi bilioni 4,

731
00:59:32,960 --> 00:59:40,600
lakini hiyo ni unrealistic tangu basi tunatarajia kuwa na kutumia nafasi

732
00:59:40,600 --> 00:59:44,400
juu ya utaratibu wa bilioni 4. Basi hiyo ni unrealistic.

733
00:59:44,400 --> 00:59:47,060
Lakini hapa tutaweza kusema amefungwa yetu ni 200.

734
00:59:47,060 --> 00:59:59,570
hila ili kufanya hivyo katika O ya n ni sisi kufanya mwingine safu kuitwa makosa ya kawaida amefungwa.

735
00:59:59,570 --> 01:00:10,470
Hivyo kweli, hii ni njia ya mkato kwa - Mimi kwa kweli sijui kama Clang gani hii.

736
01:00:11,150 --> 01:00:15,330
Lakini katika GCC angalau sana - I'm kuchukua Clang gani pia -

737
01:00:15,330 --> 01:00:18,180
hii tu initialize safu nzima kuwa sekunde 0.

738
01:00:18,180 --> 01:00:25,320
Hivyo kama mimi sitaki kufanya hivyo, basi mimi naweza kufanya tofauti kwa ajili ya (i = 0 int;

739
01:00:25,320 --> 01:00:31,500
i <BOUND; i + +) na makosa [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Hivyo sasa kila kitu ni initialized kwa 0.

741
01:00:35,260 --> 01:00:39,570
Mimi iterate juu ya safu yangu,

742
01:00:39,570 --> 01:00:51,920
na nini mimi kufanya ni mimi nina kuhesabu idadi ya kila - Hebu kwenda chini hapa.

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

744
01:00:55,480 --> 01:01:00,010
Nini mimi kuhesabu ni idadi ya matukio ya kila moja ya mambo hayo.

745
01:01:00,010 --> 01:01:03,470
Hebu kweli kuongeza michache zaidi katika hapa kwa kurudia baadhi.

746
01:01:03,470 --> 01:01:11,070
Hivyo thamani sisi hapa, thamani ya kwamba ni kwenda kuwa safu [i].

747
01:01:11,070 --> 01:01:14,850
Hivyo Val inaweza kuwa 4 au 8 au chochote.

748
01:01:14,850 --> 01:01:18,870
Na sasa mimi nina kuhesabu jinsi wengi wa thamani kwamba nimepata kuona,

749
01:01:18,870 --> 01:01:21,230
hivyo makosa [Val] + +;

750
01:01:21,230 --> 01:01:29,430
Baada ya hili ni kosa, makosa ni kwenda kuangalia kitu kama 0001.

751
01:01:29,430 --> 01:01:42,190
Hebu kufanya makosa [Val] - amefungwa + 1.

752
01:01:42,190 --> 01:01:48,230
>> Sasa kwa kuwa tu kuwajibika kwa ajili ya ukweli kwamba sisi ni kuanzia 0.

753
01:01:48,230 --> 01:01:50,850
Hivyo kama 200 ni kwenda kuwa idadi yetu kubwa,

754
01:01:50,850 --> 01:01:54,720
kisha 0-200 ni 201 mambo.

755
01:01:54,720 --> 01:02:01,540
Hivyo makosa, hivyo itabidi kuangalia kama 00,001 kwa sababu sisi moja 4.

756
01:02:01,540 --> 01:02:10,210
Kisha sisi itabidi 0001 ambapo tutaweza kuwa na 1 katika ripoti ya 8 ya kuhesabu.

757
01:02:10,210 --> 01:02:14,560
Sisi itabidi 2 katika ripoti ya 23 ya kuhesabu.

758
01:02:14,560 --> 01:02:17,630
Sisi itabidi 2 katika ripoti ya 42 ya kuhesabu.

759
01:02:17,630 --> 01:02:21,670
Hivyo tunaweza kutumia kuhesabu.

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

761
01:02:44,920 --> 01:02:52,540
Na hivyo kama num_of_item ni 2, kwamba maana tunataka Insert 2 ya idadi i

762
01:02:52,540 --> 01:02:55,290
ndani ya safu yetu Iliyopangwa.

763
01:02:55,290 --> 01:03:02,000
Hivyo tunahitaji kuweka wimbo wa jinsi mbali sisi ni katika safu.

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

765
01:03:05,470 --> 01:03:09,910
Array - mimi itabidi kuandika.

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

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

768
01:03:28,580 --> 01:03:32,490
Ni kwamba nini nataka? Nadhani hiyo ni nini nataka.

769
01:03:35,100 --> 01:03:38,290
Ndiyo, hii inaonekana ni nzuri. Sawa.

770
01:03:38,290 --> 01:03:43,050
Hivyo haina kila mtu kuelewa nini madhumuni ya safu yangu ni makosa?

771
01:03:43,050 --> 01:03:48,140
Ni kuhesabu idadi ya matukio ya kila moja ya namba hizi.

772
01:03:48,140 --> 01:03:51,780
Kisha Mimi iterating juu ya kwamba safu makosa,

773
01:03:51,780 --> 01:03:57,190
na msimamo idh katika safu makosa

774
01:03:57,190 --> 01:04:01,930
ni idadi ya i ni kwamba wanapaswa kuonekana katika safu yangu Iliyopangwa.

775
01:04:01,930 --> 01:04:06,840
Hiyo ndiyo sababu ya makosa ya 4 ni kwenda kuwa 1

776
01:04:06,840 --> 01:04:11,840
na makosa ya 8 ni kwenda kuwa 1, makosa ya 23 itakuwa ni 2.

777
01:04:11,840 --> 01:04:16,900
Basi hiyo ni jinsi wengi wao nataka Insert katika safu yangu Iliyopangwa.

778
01:04:16,900 --> 01:04:19,200
Kisha mimi tu kufanya hivyo.

779
01:04:19,200 --> 01:04:28,960
Mimi inserting num_of_item i ni ndani ya safu yangu Iliyopangwa.

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

781
01:04:32,460 --> 01:04:43,100
Na hivyo tena, hii ni linear wakati tangu sisi tu iterating juu ya hili mara moja,

782
01:04:43,100 --> 01:04:47,470
lakini pia ni linear katika kile idadi hii hutokea kwa kuwa,

783
01:04:47,470 --> 01:04:50,730
na hivyo sana unategemea nini amefungwa yako ni.

784
01:04:50,730 --> 01:04:53,290
Pamoja na amefungwa ya 200, si kwamba kuwa mbaya.

785
01:04:53,290 --> 01:04:58,330
Kama amefungwa yako ni kwenda kuwa 10,000, kisha hiyo kidogo mbaya,

786
01:04:58,330 --> 01:05:01,360
lakini kama amefungwa yako ni kwenda kuwa bilioni 4, kwamba ni kabisa unrealistic

787
01:05:01,360 --> 01:05:07,720
na safu hii ni ya kwenda kuwa ya kawaida bilioni 4, ambayo ni unrealistic.

788
01:05:07,720 --> 01:05:10,860
Basi hiyo ni kwamba. Maswali?

789
01:05:10,860 --> 01:05:13,270
[Inaudible mwanafunzi majibu] >> Sawa.

790
01:05:13,270 --> 01:05:15,710
Nilitambua nyingine moja kitu, tulipokuwa tunakwenda kupitia.

791
01:05:17,980 --> 01:05:23,720
Nadhani tatizo ni katika ya Lucas na pengine kila mmoja tumeona.

792
01:05:23,720 --> 01:05:26,330
Mimi kabisa alisahau.

793
01:05:26,330 --> 01:05:31,040
Kitu tu nilitaka kutoa maoni juu ni kwamba wakati wewe ni kushughulika na mambo kama fahirisi,

794
01:05:31,040 --> 01:05:38,320
wewe kweli kamwe kuona hii wakati wewe ni kuandika kwa kitanzi,

795
01:05:38,320 --> 01:05:41,120
lakini kitaalam, wakati wowote wewe ni kushughulika na fahirisi hizi,

796
01:05:41,120 --> 01:05:45,950
unapaswa pretty much daima kukabiliana na integers unsigned.

797
01:05:45,950 --> 01:05:53,850
Sababu hii ni wakati wewe ni kushughulika na integers saini,

798
01:05:53,850 --> 01:05:56,090
hivyo kama una 2 integers saini na wewe kuongeza yao pamoja

799
01:05:56,090 --> 01:06:00,640
na wanaishia kubwa mno, basi wewe kuishia na idadi hasi.

800
01:06:00,640 --> 01:06:03,410
Hivyo kwamba ni nini kufurika integer ni.

801
01:06:03,410 --> 01:06:10,500
>> Kama mimi kuongeza bilioni 2 na bilioni 1, mimi kuishia na hasi bilioni 1.

802
01:06:10,500 --> 01:06:15,480
Hiyo ni jinsi integers kazi kwenye kompyuta.

803
01:06:15,480 --> 01:06:17,510
Hivyo tatizo na kutumia -

804
01:06:17,510 --> 01:06:23,500
Hiyo ni sawa ila ikiwa chini hutokea kwa kuwa na bilioni 2 hadi hutokea kwa kuwa bilioni 1,

805
01:06:23,500 --> 01:06:27,120
basi hii itakuwa ni hasi bilioni 1 na kisha tunakwenda kugawanya kwamba kwa 2

806
01:06:27,120 --> 01:06:29,730
na kuishia na hasi milioni 500.

807
01:06:29,730 --> 01:06:33,760
Hivyo hii ni suala tu kama wewe kutokea kwa kuwa kutafuta njia ya safu

808
01:06:33,760 --> 01:06:38,070
mabilioni ya mambo.

809
01:06:38,070 --> 01:06:44,050
Lakini kama + chini juu kinachotokea kwa kufurika, basi hiyo ni tatizo.

810
01:06:44,050 --> 01:06:47,750
Haraka kama sisi kufanya nao unsigned, basi bilioni 2 plus bilioni 1 ni bilioni 3.

811
01:06:47,750 --> 01:06:51,960
Bilioni 3 kugawanywa na 2 ni bilioni 1.5.

812
01:06:51,960 --> 01:06:55,670
Hivyo kwa haraka kama wao ni unsigned, kila kitu ni kamilifu.

813
01:06:55,670 --> 01:06:59,900
Na hivyo pia kwamba suala wakati wewe kuandika yako kwa tanzi,

814
01:06:59,900 --> 01:07:03,940
na kweli, basi pengine gani moja kwa moja.

815
01:07:09,130 --> 01:07:12,330
Itakuwa kweli tu yell saa wewe.

816
01:07:12,330 --> 01:07:21,610
Hivyo kama idadi hii ni kubwa mno kuwa katika tu integer lakini ingekuwa fit katika integer unsigned,

817
01:07:21,610 --> 01:07:24,970
itakuwa yell katika wewe, hivyo ndiyo sababu wewe kamwe kweli kukimbia katika suala hilo.

818
01:07:29,150 --> 01:07:34,820
Unaweza kuona kwamba index ni kamwe kwenda kuwa hasi,

819
01:07:34,820 --> 01:07:39,220
na hivyo wakati uko juu ya iterating safu,

820
01:07:39,220 --> 01:07:43,970
unaweza karibu daima kusema unsigned int i, lakini wewe si kweli kuwa kwa.

821
01:07:43,970 --> 01:07:47,110
Mambo ni kwenda kufanya kazi pretty much tu kama vizuri.

822
01:07:48,740 --> 01:07:50,090
Sawa. [Minong'ono] Ni saa?

823
01:07:50,090 --> 01:07:54,020
Jambo la mwisho nilitaka kuonyesha - na mimi itabidi kufanya hivyo kweli haraka.

824
01:07:54,020 --> 01:08:03,190
Unajua jinsi tuna # define ili tuweze # define MAX kama 5 au kitu?

825
01:08:03,190 --> 01:08:05,940
Hebu si kufanya MAX. # Define amefungwa kama 200. Hiyo ni nini sisi alifanya mbele.

826
01:08:05,940 --> 01:08:10,380
Kwamba amefafanua mara kwa mara, ambayo ni kwenda tu kunakiliwa na pasted

827
01:08:10,380 --> 01:08:13,010
popote sisi kutokea kwa kuandika amefungwa.

828
01:08:13,010 --> 01:08:18,189
>> Hivyo tunaweza kweli kufanya zaidi na # amefafanua.

829
01:08:18,189 --> 01:08:21,170
Tunaweza # define kazi.

830
01:08:21,170 --> 01:08:23,410
Wao ni si kweli kazi, lakini tutaweza kuwaita kazi.

831
01:08:23,410 --> 01:08:36,000
itakuwa mfano kitu kama MAX (x, y) inaelezwa kama (x <y y:? x). Sawa.

832
01:08:36,000 --> 01:08:40,660
Hivyo unapaswa kupata kutumika ternary syntax operator,

833
01:08:40,660 --> 01:08:49,029
lakini ni chini ya x y? Kurudi y, mwingine kurudi x.

834
01:08:49,029 --> 01:08:54,390
Hivyo unaweza kuona unaweza kufanya hii kazi tofauti,

835
01:08:54,390 --> 01:09:01,399
na kazi inaweza kuwa kama bool MAX inachukua hoja 2, kurudi huu.

836
01:09:01,399 --> 01:09:08,340
Hii ni moja ya ndio kawaida naona kufanyika kama hii. Sisi kuwaita macros.

837
01:09:08,340 --> 01:09:11,790
Hii ni jumla.

838
01:09:11,790 --> 01:09:15,859
Hii ni syntax kwa ajili yake.

839
01:09:15,859 --> 01:09:18,740
Unaweza kuandika jumla ya kufanya chochote unataka.

840
01:09:18,740 --> 01:09:22,649
Wewe mara nyingi kuona macros kwa debugging printfs na mambo ya ajabu.

841
01:09:22,649 --> 01:09:29,410
Hivyo aina ya printf, kuna constants maalum katika C kama underscore LINE underscore,

842
01:09:29,410 --> 01:09:31,710
2 underscores LINE underscore,

843
01:09:31,710 --> 01:09:37,550
na pia kuna Nadhani 2 underscores func. Hiyo inaweza kuwa hivyo. Kitu kama hicho.

844
01:09:37,550 --> 01:09:40,880
Hayo mambo itakuwa kubadilishwa kwa jina la kazi

845
01:09:40,880 --> 01:09:42,930
au idadi ya mstari kwamba uko juu.

846
01:09:42,930 --> 01:09:48,630
Mara kwa mara, wewe kuandika printfs debugging kwamba chini hapa mimi nilikuwa basi andika tu

847
01:09:48,630 --> 01:09:54,260
Debug na itakuwa magazeti idadi line na kazi ya kuwa mimi kutokea kwa kuwa katika

848
01:09:54,260 --> 01:09:57,020
kwamba wamekutana kwamba taarifa Debug.

849
01:09:57,020 --> 01:09:59,550
Na unaweza pia magazeti mambo mengine.

850
01:09:59,550 --> 01:10:05,990
Hivyo jambo moja unapaswa kuangalia kwa ni kama mimi kutokea kwa # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
kama kitu kama 2 * y * na 2 x.

852
01:10:11,380 --> 01:10:14,310
Hivyo kwa sababu yoyote, wewe kutokea kwa kufanya hivyo mengi.

853
01:10:14,310 --> 01:10:16,650
Hivyo kufanya hivyo jumla.

854
01:10:16,650 --> 01:10:18,680
Hii ni kweli kuvunjwa.

855
01:10:18,680 --> 01:10:23,050
Napenda kuiita kwa kufanya kitu kama DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Basi nini kirejeshwe?

857
01:10:28,840 --> 01:10:30,580
[Mwanafunzi] 12.

858
01:10:30,580 --> 01:10:34,800
Ndiyo, 12 kirejeshwe, na 12 ni kurudi.

859
01:10:34,800 --> 01:10:43,350
3 anapata kubadilishwa kwa x, 6 anapata kubadilishwa kwa y, na sisi kurudi 2 * 6, ambayo ni 12.

860
01:10:43,350 --> 01:10:47,710
Sasa nini kuhusu hili? Nini kirejeshwe?

861
01:10:47,710 --> 01:10:50,330
[Mwanafunzi] 14. >> Kimawazo, 14.

862
01:10:50,330 --> 01:10:55,290
suala ni kwamba jinsi hash amefafanua kazi, kumbuka ni nakala halisi na kuweka

863
01:10:55,290 --> 01:11:00,160
wa kila kitu pretty much, ili kile hii ni kwenda kufasiriwa kama

864
01:11:00,160 --> 01:11:11,270
ni 3 chini ya 1 plus 6, 2 mara 1 plus 6, 2 mara 3.

865
01:11:11,270 --> 01:11:19,780
>> Hivyo kwa sababu hii wewe daima karibu wrap kila kitu katika mabano.

866
01:11:22,180 --> 01:11:25,050
Yoyote variable wewe daima karibu wrap katika mabano.

867
01:11:25,050 --> 01:11:29,570
Kuna matukio ambapo wewe huna, kama mimi najua kuwa mimi si haja ya kufanya hivyo hapa

868
01:11:29,570 --> 01:11:32,110
kwa sababu chini ya ni kiasi pretty daima tu kwenda kufanya kazi,

869
01:11:32,110 --> 01:11:34,330
ingawa kwamba wanaweza hata kuwa kweli.

870
01:11:34,330 --> 01:11:41,870
Kama kuna kitu kama ridiculous DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
basi hiyo ni kwenda kupata kubadilishwa na 3 chini ya 1 ni sawa sawa na 2,

872
01:11:49,760 --> 01:11:53,460
na hivyo basi ni kwenda kufanya 3 chini ya 1, 2 gani kwamba sawa,

873
01:11:53,460 --> 01:11:55,620
ambayo ni nini tunataka.

874
01:11:55,620 --> 01:12:00,730
Hivyo ili kuzuia mtu yeyote operator matatizo precedence,

875
01:12:00,730 --> 01:12:02,870
daima wrap katika mabano.

876
01:12:03,290 --> 01:12:07,700
Sawa. Na hiyo ni yake, 5:30.

877
01:12:08,140 --> 01:12:12,470
Kama una maswali yoyote juu ya pset, tujulishe.

878
01:12:12,470 --> 01:12:18,010
Ni lazima kuwa na furaha, na toleo la hacker pia ni kweli zaidi

879
01:12:18,010 --> 01:12:22,980
kuliko toleo hacker ya mwaka jana, hivyo tunatarajia mengi ya wewe kujaribu.

880
01:12:22,980 --> 01:12:26,460
Mwaka jana alikuwa sana balaa.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]