1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [3 skirsnis - patogiau]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Harvardo universiteto]

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

4
00:00:07,310 --> 00:00:12,700
>> Taigi į pirmąjį klausimą būtų keistai suformuluotas.

5
00:00:12,700 --> 00:00:17,480
GDB leidžia jums "debug" programa, bet, tiksliau, ką jis jums tai padaryti?

6
00:00:17,480 --> 00:00:22,590
Aš atsakyti į šį vieną, ir aš nežinau, ką tiksliai tikimasi,

7
00:00:22,590 --> 00:00:27,910
todėl aš atspėti, tai kažkas palei jo linijas leidžia jums žingsnis po žingsnio

8
00:00:27,910 --> 00:00:31,540
vaikščioti per programa, bendrauti su juo, pakeisti kintamieji, padaryti visus šiuos dalykus -

9
00:00:31,540 --> 00:00:34,270
iš esmės visiškai kontroliuoti programos vykdymą

10
00:00:34,270 --> 00:00:38,410
ir apžiūrėti bet kuriuo programos vykdymo.

11
00:00:38,410 --> 00:00:43,030
Taigi šios funkcijos leidžia jums derinti dalykų.

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

13
00:00:44,830 --> 00:00:50,520
Kodėl dvejetainis paieškos reikalauja, kad masyvas būti rūšiuojami?

14
00:00:50,520 --> 00:00:53,360
Kas nori atsakyti, kad?

15
00:00:56,120 --> 00:01:00,070
[Studentas] Kadangi jis neveikia, jei ji nėra rūšiuojamos. >> Taip. [Juokas]

16
00:01:00,070 --> 00:01:04,910
Jei jis nėra rūšiuojamos, tada tai neįmanoma padalinti per pusę

17
00:01:04,910 --> 00:01:07,850
ir žinoti, kad viskas į kairę yra mažesnis ir viskas į dešinę

18
00:01:07,850 --> 00:01:10,490
yra didesnis nei vidutinis dydis.

19
00:01:10,490 --> 00:01:12,790
Todėl ji turi būti rūšiuojami.

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

21
00:01:14,170 --> 00:01:17,570
Kodėl burbulas rūšiuoti O n kvadrato?

22
00:01:17,570 --> 00:01:23,230
Ar kas nors norite suteikti labai greitai aukšto lygio apžvalgą, ką burbulas rūšiuoti?

23
00:01:25,950 --> 00:01:33,020
[Studentas] Jūs iš esmės pereiti per kiekvieno elemento ir jums patikrinti keletą pirmųjų elementai.

24
00:01:33,020 --> 00:01:37,150
Jei jie iš ten, kur jums apsikeitimo juos, tada jums patikrinti artimiausius elementus ir pan.

25
00:01:37,150 --> 00:01:40,770
Kai pasieksite pabaigos, tuomet jūs žinote, kad didžiausias elementas dedamas pabaigoje,

26
00:01:40,770 --> 00:01:42,750
todėl jūs ignoruoti, kad tada jūs nuolat išgyvena,

27
00:01:42,750 --> 00:01:48,490
ir kiekvieną kartą, jūs turite patikrinti vieną mažiau elementą, kol jūs padaryti jokių pakeitimų. >> Taip.

28
00:01:48,490 --> 00:01:58,470
Tai vadinama burbulas rūšiuoti, nes jei jums apversti masyvas ant šono, todėl iki ir žemyn, vertikali,

29
00:01:58,470 --> 00:02:03,100
Tada didelės vertės bus kriaukle prie dugno ir mažos vertės burbulas iki viršaus.

30
00:02:03,100 --> 00:02:05,210
Tai, kaip jis gavo savo pavadinimą.

31
00:02:05,210 --> 00:02:08,220
Ir taip, jūs tiesiog eiti per.

32
00:02:08,220 --> 00:02:11,190
Jūs nuolat išgyvena masyvą, keičiant didesnę vertę

33
00:02:11,190 --> 00:02:14,040
gauti didžiausios vertės iki dugno.

34
00:02:14,040 --> 00:02:17,500
>> Kodėl ji yra O n kvadrato?

35
00:02:18,690 --> 00:02:24,620
Pirma, ar kas nors nori pasakyti, kodėl ji O n kvadrato?

36
00:02:24,620 --> 00:02:28,760
[Studentas] Dėl kiekvieno reiso metu jis eina n kartų.

37
00:02:28,760 --> 00:02:32,100
Galite būti tikri, kad jūs atlikote didžiausias elementas visą kelią žemyn,

38
00:02:32,100 --> 00:02:35,230
tada jūs turite pakartoti, kad kuo daugiau elementų. >> Taip.

39
00:02:35,230 --> 00:02:41,800
Todėl atminkite, Big O reiškia ir ką reiškia didelis Omega.

40
00:02:41,800 --> 00:02:50,560
Didelis O kaip viršutinė riba, kaip lėtai jis iš tikrųjų gali paleisti.

41
00:02:50,560 --> 00:02:58,990
Taigi, sakydamas, kad tai Õ n kvadrato, tai nėra O n arba kitur, kad būtų galima paleisti

42
00:02:58,990 --> 00:03:02,640
eilutėmis, tačiau ji yra O n sudedamos kubeliais supjaustytos

43
00:03:02,640 --> 00:03:06,390
nes ji yra apribota O n sudedamos kubeliais supjaustytos.

44
00:03:06,390 --> 00:03:12,300
, Jei ji riboja O n kvadrato, tada jis riboja taip pat n sudedamos kubeliais supjaustytos.

45
00:03:12,300 --> 00:03:20,280
Taigi, tai yra n kvadrato ir absoliučios blogiausiu atveju jis negali padaryti geriau nei n kvadrato,

46
00:03:20,280 --> 00:03:22,830
kuris yra, kodėl ji O n kvadrato.

47
00:03:22,830 --> 00:03:31,200
Taigi, norint pamatyti šiek tiek matematikos, kaip ji išeina n kvadrato,

48
00:03:31,200 --> 00:03:40,530
jei mes turime penkis dalykus mūsų sąraše, pirmą kartą, kiek apsikeitimo sandoriai galėtume potencialiai reikia padaryti

49
00:03:40,530 --> 00:03:47,170
siekiant gauti? Tegul iš tikrųjų tik

50
00:03:47,170 --> 00:03:52,040
Kiek apsikeitimo sandoriai mes turėsime padaryti Pirmą kartą taikant burbulas rūšiuoti per masyvo?

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

52
00:03:53,540 --> 00:03:58,340
>> Jei yra 5 elementai, mes ketiname reikia padaryti n - 1.

53
00:03:58,340 --> 00:04:01,100
Tada antrasis kiek apsikeitimo sandoriai mes turėsime padaryti?

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

55
00:04:03,440 --> 00:04:11,640
O trečiajame bus n - 3, o dėl patogumo, aš parašyti per pastaruosius dvejus

56
00:04:11,640 --> 00:04:15,270
nes tada mes ketiname reikia padaryti 2 apsikeitimo sandorius ir 1 SWAP.

57
00:04:15,270 --> 00:04:19,899
Manau, naujausia gali arba negali iš tikrųjų reikia, kad taip atsitiktų.

58
00:04:19,899 --> 00:04:22,820
Tai yra swap? Nežinau.

59
00:04:22,820 --> 00:04:26,490
Taigi tai yra bendrą sumą, apsikeitimo sandorių ar bent palyginimai, jūs turite padaryti.

60
00:04:26,490 --> 00:04:29,910
Net jei jūs neturite swap, jums vis tiek reikia palyginti vertybes.

61
00:04:29,910 --> 00:04:33,910
Taigi yra n - 1 palyginimai pirmąjį masyvo paleisti per.

62
00:04:33,910 --> 00:04:42,050
Jei jūs pertvarkyti šiuos dalykus, galime iš tikrųjų padaryti jį šešių dalykų, todėl viskas sukrauti gražiai,

63
00:04:42,050 --> 00:04:44,790
ir tada aš padaryti 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Taigi, tiesiog pertvarkyti šių sumų, mes norime pamatyti, kiek palyginimai mes darome

65
00:04:49,910 --> 00:04:52,700
visą algoritmą.

66
00:04:52,700 --> 00:04:56,550
Taigi, jei mes suteikiame žemai čia, šie vaikinai

67
00:04:56,550 --> 00:05:07,470
tada mes dar tik susumuojant Tačiau daugelis palyginti, tai nebuvo.

68
00:05:07,470 --> 00:05:13,280
Bet jei mes Apibendrinant šiuos ir mes Apibendrinant tai ir mes Apibendrinant tai,

69
00:05:13,280 --> 00:05:18,130
tai vis dar ta pati problema. Mes tiesiog apibendrinti šias konkrečias grupes.

70
00:05:18,130 --> 00:05:22,400
>> Taigi dabar mes sumuojant 3 n. Tai ne tik 3 n.

71
00:05:22,400 --> 00:05:27,650
Jis visada bus n / 2 n.

72
00:05:27,650 --> 00:05:29,430
Taigi čia mes atsitikti, kad 6.

73
00:05:29,430 --> 00:05:34,830
Jei mes turėjome 10 dalykų, tada mes galime padaryti šį grupavimą 5 skirtingų dalykų porų

74
00:05:34,830 --> 00:05:37,180
ir galų gale su n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Todėl jūs visada ketinate gauti n / 2 n ir todėl tai mes Užrašoma jį n kvadrato / 2.

76
00:05:45,840 --> 00:05:48,890
Ir todėl, nors tai pusė veiksnys, kuris atsitinka ateiti

77
00:05:48,890 --> 00:05:54,190
, nes tai, kad per kiekvieną per masyvo iteracijos mes palyginti 1 mažiau

78
00:05:54,190 --> 00:05:58,040
todėl tai, kaip mes gauname daugiau nei 2, bet ji vis dar n kvadrato.

79
00:05:58,040 --> 00:06:01,650
Mums nerūpi, apie pusę pastoviu koeficientu.

80
00:06:01,650 --> 00:06:07,760
Taigi, Big O daug dalykų, kaip tai remiasi tik rūšies daro šį matematikos rūšiuoti,

81
00:06:07,760 --> 00:06:12,260
daro aritmetines sumas ir geometrinę progresiją stuff,

82
00:06:12,260 --> 00:06:17,750
tačiau dauguma jų į šį kursą yra gana paprasta.

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

84
00:06:19,290 --> 00:06:24,430
Kodėl įterpimas n Omega rūšiuoti? Ką Omega reiškia?

85
00:06:24,430 --> 00:06:27,730
[Du studentai, kalbantys vienu metu - nesuprantami] >> Yeah.

86
00:06:27,730 --> 00:06:30,630
Omega jūs galite galvoti kaip apatinė riba.

87
00:06:30,630 --> 00:06:36,550
>> Taigi nesvarbu, kaip efektyviai jūsų įterpimo rūšiavimo algoritmas,

88
00:06:36,550 --> 00:06:41,810
neatsižvelgiant į tai, kad praėjo sąraše, ji visada turi palyginti bent n dalykus

89
00:06:41,810 --> 00:06:44,620
arba jis turi pakartoti per n dalykų.

90
00:06:44,620 --> 00:06:47,280
Kodėl taip yra?

91
00:06:47,280 --> 00:06:51,190
[Studentas] Dėl, jei sąrašas jau surūšiuoti, tada per pirmas iteracijos

92
00:06:51,190 --> 00:06:54,080
jūs galite tik garantuoti, kad pirmasis elementas yra mažiau,

93
00:06:54,080 --> 00:06:56,490
ir antrajame iteracijos galite garantuoti tik pirmieji du yra

94
00:06:56,490 --> 00:07:00,010
, nes jūs nežinote, kad likusi dalis yra rūšiuojamos sąrašo. >> Taip.

95
00:07:00,010 --> 00:07:08,910
Jei pereisite visiškai rūšiuotų sąrašą, bent jau, jūs turite pereiti per visus elementus

96
00:07:08,910 --> 00:07:12,180
matyti, kad nieko nereikia būti perkeltas aplink.

97
00:07:12,180 --> 00:07:14,720
Taigi pravažiavimą sąrašą ir sako: oh, tai jau surūšiuoti,

98
00:07:14,720 --> 00:07:18,240
tai neįmanoma, kad jūs žinote, tai rūšiuojamos, kol jums patikrinti kiekvieną elementą

99
00:07:18,240 --> 00:07:20,660
pamatyti, kad jie rūšiuotų tvarka.

100
00:07:20,660 --> 00:07:25,290
Taigi apačios įterpimo Rūšiuoti Omega n.

101
00:07:25,290 --> 00:07:28,210
Kas blogiausiu atveju veikia Merge sort laikas,

102
00:07:28,210 --> 00:07:31,390
Big O blogiausiu atveju dar kartą?

103
00:07:31,390 --> 00:07:37,660
Taigi, blogiausiu atveju, kaip sujungti rūšiuoti paleisti?

104
00:07:42,170 --> 00:07:43,690
[Studentas] n log n. >> Taip.

105
00:07:43,690 --> 00:07:49,990
Sparčiausiai bendri rūšiavimo algoritmai n log n. Jūs negalite padaryti geriau.

106
00:07:51,930 --> 00:07:55,130
>> Yra specialūs atvejai, ir jei mes turime laiko šiandien - bet mes tikriausiai won't -

107
00:07:55,130 --> 00:07:59,330
mes galime pamatyti vieną, kad veikia geriau nei n log n.

108
00:07:59,330 --> 00:08:04,050
Tačiau bendruoju atveju, jūs negalite padaryti geriau nei n log n.

109
00:08:04,050 --> 00:08:09,680
Ir sujungti rūšiuoti atsitinka, kad jūs turėtumėte žinoti, šį kursą, kuris yra n log n.

110
00:08:09,680 --> 00:08:13,260
Ir taip mes iš tikrųjų būti įgyvendinti, kad šiandien.

111
00:08:13,260 --> 00:08:18,070
Ir galiausiai, ne daugiau kaip tris sakinius, kaip atrankos rūšiavimo darbą?

112
00:08:18,070 --> 00:08:20,370
Ar kas nors norite atsiliepti, ir aš suskaičiuoti savo sakinius

113
00:08:20,370 --> 00:08:22,390
nes jei jūs einate per 3 -

114
00:08:25,530 --> 00:08:28,330
Ar kas nors prisimena atrankos rūšiuoti?

115
00:08:31,280 --> 00:08:37,809
Pasirinkimas rūšiuoti yra paprastai gana lengva atsiminti tik iš pavadinimo.

116
00:08:37,809 --> 00:08:45,350
Jūs tiesiog pakartoti per masyvo, todėl surasti kokia didžiausia vertė yra arba mažiausia -

117
00:08:45,350 --> 00:08:47,290
kokia tvarka, kokia jūs rūšiavimas.

118
00:08:47,290 --> 00:08:50,750
Taigi tarkim mes rūšiavimo nuo mažiausio iki didžiausių.

119
00:08:50,750 --> 00:08:55,250
Jūs pakartoti per masyvą, nepriklausomai minimalus elementas yra

120
00:08:55,250 --> 00:08:59,750
pasirinkite jį, ir tada tiesiog apsikeitimo jį, kokia yra pirmoje vietoje.

121
00:08:59,750 --> 00:09:04,090
Ir tada antrojo jus per masyvo, vėl ieškoti minimalaus elemento,

122
00:09:04,090 --> 00:09:07,490
pasirinkite jį, tada apsikeitimo jį su tuo, kas yra antroje vietoje.

123
00:09:07,490 --> 00:09:10,650
Taigi mes tiesiog skinti ir pasirinkti mažiausių verčių

124
00:09:10,650 --> 00:09:16,050
ir įterpti juos į masyvo priekyje, kol jis yra rūšiuojama.

125
00:09:19,210 --> 00:09:21,560
Turite klausimų apie tai?

126
00:09:21,560 --> 00:09:25,710
>> Tai neišvengiamai formų, turite užpildyti, kai jūs pateikdami pset.

127
00:09:29,010 --> 00:09:32,360
Tie, kurie iš esmės yra atsakymai į šiuos.

128
00:09:32,360 --> 00:09:34,230
Gerai, kad dabar kodavimo problemas.

129
00:09:34,230 --> 00:09:40,140
Aš jau išsiuntė per email - Ar kas nors negalite gauti, kad laišką? Gerai.

130
00:09:40,140 --> 00:09:46,630
Aš jau išsiuntė per e-mail erdvę, kad mes ketiname naudoti,

131
00:09:46,630 --> 00:09:52,120
ir jei jūs paspausite ant mano vardo, todėl manau, kad aš ruošiuosi būti apačioje

132
00:09:52,120 --> 00:09:57,170
dėl atgalinio r - bet jei paspausite ant mano vardo jūs pamatysite 2 pakeitimus.

133
00:09:57,170 --> 00:10:02,650
Bus aš jau nukopijuoti ir įklijuoti kodą į erdvių Peržiūra 1

134
00:10:02,650 --> 00:10:06,900
paieškos dalykas, kad jūs ketinate turi įgyvendinti.

135
00:10:06,900 --> 00:10:10,540
Ir 2 redakcija bus rūšiuoti dalykas, kad mes įgyvendinti po to.

136
00:10:10,540 --> 00:10:15,770
Taigi, jūs galite spustelėti ant mano redakcijos 1 ir dirbti iš ten.

137
00:10:17,350 --> 00:10:22,060
Ir dabar mes norime įgyvendinti Dvejetainė paieška.

138
00:10:22,060 --> 00:10:26,470
>> Ar kas nors nori tiesiog duoti pseudocode aukšto lygio paaiškinimą

139
00:10:26,470 --> 00:10:31,440
ką mes ketiname turite padaryti paieškai? Taip.

140
00:10:31,440 --> 00:10:36,170
[Studentas] Jūs tiesiog pasiimti iš masyvo viduryje ir pamatyti, jei tai, ką jūs ieškote

141
00:10:36,170 --> 00:10:38,650
yra mažesnis negu arba daugiau nei tai.

142
00:10:38,650 --> 00:10:41,080
Ir jei tai mažiau, jūs einate į pusę mažiau,

143
00:10:41,080 --> 00:10:44,750
ir jei tai daugiau, jūs einate pusę, kad daugiau ir jums kartoti, kad tol, kol jūs tiesiog gaunate vieną dalyką.

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

145
00:10:46,570 --> 00:10:51,320
Atkreipkite dėmesį, kad mūsų numeriai masyvas jau surūšiuoti,

146
00:10:51,320 --> 00:10:57,190
ir todėl tai reiškia, kad mes galime pasinaudoti, kad ir mes galime pirmiausia patikrinkite,

147
00:10:57,190 --> 00:11:00,390
gerai, aš žiūriu skaičius 50.

148
00:11:00,390 --> 00:11:03,720
Taigi, aš galiu eiti į vidurį.

149
00:11:03,720 --> 00:11:07,380
Viduryje yra sunku apibrėžti, kai jis net keletas dalykų,

150
00:11:07,380 --> 00:11:10,820
bet tegul tiesiog pasakyti, mes visada trumpinti į vidurį.

151
00:11:10,820 --> 00:11:14,420
Taigi čia mes turime 8 dalykų, kad viduryje būtų 16.

152
00:11:14,420 --> 00:11:17,330
Aš ieškau 50, kad 50 yra daugiau nei 16.

153
00:11:17,330 --> 00:11:21,310
Taigi, dabar aš iš esmės gali gydyti savo masyvas kaip šių elementų.

154
00:11:21,310 --> 00:11:23,450
Galiu išmesti viską, nuo 16 per.

155
00:11:23,450 --> 00:11:27,440
Dabar mano masyvas yra tik šie 4 elementai, o aš kartoti.

156
00:11:27,440 --> 00:11:31,910
Taip, tada aš noriu rasti viduryje vėl, kuris bus 42.

157
00:11:31,910 --> 00:11:34,730
42 yra mažiau nei 50, kad galėčiau išmesti šiuos du elementus.

158
00:11:34,730 --> 00:11:36,890
Čia yra mano likęs masyvas.

159
00:11:36,890 --> 00:11:38,430
Aš ruošiuosi dar kartą rasti vidurį.

160
00:11:38,430 --> 00:11:42,100
Manau, 50 blogas pavyzdys, nes aš visada buvo mesti toli dalykus į kairę,

161
00:11:42,100 --> 00:11:48,280
bet pagal tą pačią priemonę, jei aš ieškote ko nors,

162
00:11:48,280 --> 00:11:52,100
ir tai yra mažiau nei elemento Aš šiuo metu ieško

163
00:11:52,100 --> 00:11:55,080
tada aš ruošiuosi išmesti viską, į dešinę.

164
00:11:55,080 --> 00:11:58,150
Taigi, dabar mes turime tai įgyvendinti.

165
00:11:58,150 --> 00:12:02,310
Atkreipkite dėmesį, kad mes turime praeiti dydžio.

166
00:12:02,310 --> 00:12:06,730
Mes taip pat galime nereikia sunkiai kodo dydžio.

167
00:12:06,730 --> 00:12:11,640
Taigi, jei mes atsikratyti, kad # define -

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

169
00:12:21,430 --> 00:12:27,180
Kaip aš galiu gražiai išsiaiškinti, ką skaičių masyve dydis šiuo metu yra?

170
00:12:27,180 --> 00:12:30,950
>> Kiek elementai skaičių masyve?

171
00:12:30,950 --> 00:12:33,630
[Studentas] Skaičiai, laikikliai, ilgis?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Tai nėra egzistuoti C.

173
00:12:36,600 --> 00:12:38,580
Reikia. Ilgio.

174
00:12:38,580 --> 00:12:42,010
Matricos neturi savybių, todėl nėra ilgis nuosavybė masyvai

175
00:12:42,010 --> 00:12:45,650
kad bus tiesiog suteikti jums, kaip ilgai tai atsitinka būti.

176
00:12:48,180 --> 00:12:51,620
[Studentas] Žr kiek atminties ji ir padalinti kiek - >> Taip.

177
00:12:51,620 --> 00:12:55,810
Taigi, kaip mes galime pamatyti, kiek atminties ji? >> [Studentas] sizeof. >> Taip, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof yra operatorius, kad ketina grįžti skaičių masyve dydį.

179
00:13:01,680 --> 00:13:10,060
Ir tai bus tačiau daugelis sveikieji skaičiai yra sveikasis skaičius dydis

180
00:13:10,060 --> 00:13:14,050
nes tai, kiek atminties ji iš tikrųjų pradėjimo.

181
00:13:14,050 --> 00:13:17,630
Taigi, jei aš noriu, kad daug dalykų masyvo,

182
00:13:17,630 --> 00:13:20,560
tada aš ruošiuosi norite padalinti sveikojo skaičiaus dydį.

183
00:13:22,820 --> 00:13:26,010
Gerai. Taip, kad leidžia man pereiti dydžio.

184
00:13:26,010 --> 00:13:29,430
Kodėl aš turiu išlaikyti dydžio?

185
00:13:29,430 --> 00:13:38,570
Kodėl aš negaliu tiesiog padaryti čia int dydis = sizeof (kaugė) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Kodėl tai neveikia?

187
00:13:41,490 --> 00:13:44,470
[Studentas] Tai ne pasaulio kintamasis.

188
00:13:44,470 --> 00:13:51,540
[Bowden] šieno kupetoje egzistuoja ir mes artimųjų skaičiais kaip šieno kupetoje,

189
00:13:51,540 --> 00:13:54,700
ir tai, kas turi ateiti foreshadowing natūra. Taip.

190
00:13:54,700 --> 00:14:00,170
[Studentas] šieno kupetoje yra tik nuoroda į jį, todėl ji grįš, kaip didelis, kad nuoroda.

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

192
00:14:02,150 --> 00:14:09,000
Auditorijose ir aš abejoju, kad jūs mačiau krūvą tikrai dar, tiesa?

193
00:14:09,000 --> 00:14:11,270
Mes ką tik kalbėjo apie tai.

194
00:14:11,270 --> 00:14:16,090
Taigi, kamino, kur visiems savo kintamiesiems bus saugomi.

195
00:14:16,090 --> 00:14:19,960
>> Bet atminties, kuri skirta vietos kintamieji vyksta ant klojinio,

196
00:14:19,960 --> 00:14:24,790
ir kiekviena funkcija gauna savo vietos kamino, savo kamino rėmas yra, kaip ji vadinasi.

197
00:14:24,790 --> 00:14:31,590
Taigi, pagrindinis turi savo kamino rėmas, o viduje ji ketina egzistuoja šį skaičių masyvas,

198
00:14:31,590 --> 00:14:34,270
ir tai bus dydis sizeof (numeriai).

199
00:14:34,270 --> 00:14:38,180
Jis ketina turėti skaičių, suskirstyti pagal dydį elementų dydį,

200
00:14:38,180 --> 00:14:42,010
bet kad gyvena, visos pagrindinis kamino rėmo.

201
00:14:42,010 --> 00:14:45,190
Kai mes vadiname paieška, Paieškos gauna savo kamino rėmo,

202
00:14:45,190 --> 00:14:48,840
savo vietos laikyti visus savo vietos kintamieji.

203
00:14:48,840 --> 00:14:56,420
Tačiau šie argumentai - taip kaugė nėra visos šio masyvo kopija.

204
00:14:56,420 --> 00:15:00,990
Mes neturime perduoti visą masyvą, kaip į paieškos kopija.

205
00:15:00,990 --> 00:15:04,030
Jis tiesiog eina nuorodą į šį masyvo.

206
00:15:04,030 --> 00:15:11,470
Taigi paiešką galite prieiti prie šių skaičių per šią nuorodą.

207
00:15:11,470 --> 00:15:17,100
Jis vis dar gauti prieigą prie dalykų, kurie gyvena viduje pagrindinis kamino rėmo,

208
00:15:17,100 --> 00:15:22,990
bet iš esmės, kai mes gauname rodyklės, kurios turėtų būti greitai,

209
00:15:22,990 --> 00:15:24,980
tai yra tai, ką rodykles.

210
00:15:24,980 --> 00:15:29,400
Pointeriai tik nuorodos dalykų, ir jūs galite naudoti rodykles ir atidarykite dalykų

211
00:15:29,400 --> 00:15:32,030
kurie yra kitų daiktų kamino kadrų.

212
00:15:32,030 --> 00:15:37,660
Taigi, nors numeriai yra vietos į pagrindinį, mes vis dar gali jį pasiekti per šį rodyklė.

213
00:15:37,660 --> 00:15:41,770
Bet kadangi tai tiesiog rodyklė ir tai tik nuoroda,

214
00:15:41,770 --> 00:15:45,040
sizeof (kaugė) sugrįžtų pačios nuoroda dydį.

215
00:15:45,040 --> 00:15:47,950
Jis negrąžina dalykas, tai nukreipta į dydį.

216
00:15:47,950 --> 00:15:51,110
Jis negrąžina tikrąjį dydį skaičių.

217
00:15:51,110 --> 00:15:55,660
Ir taip, tai nesiruošia dirbti, kaip mes norime, kad ji.

218
00:15:55,660 --> 00:15:57,320
>> Turite klausimų apie tai?

219
00:15:57,320 --> 00:16:03,250
Rodykles atvyko į gerokai daugiau Gory išsamiai savaitėmis į priekį.

220
00:16:06,750 --> 00:16:13,740
Ir štai kodėl daug dalykų, kad jūs matote, dauguma paieškos daiktų ar rūšiuoti dalykų,

221
00:16:13,740 --> 00:16:16,990
jie beveik visi ketinate reikia imtis tikrąjį dydį masyvo,

222
00:16:16,990 --> 00:16:20,440
C, nes mes neturime jokios idėjos, ką masyvo dydis yra.

223
00:16:20,440 --> 00:16:22,720
Jums reikia rankiniu būdu perduoti jį.

224
00:16:22,720 --> 00:16:27,190
Ir jūs galite ne rankiniu būdu perduoti visą masyvą, nes jūs tik artimųjų nuoroda

225
00:16:27,190 --> 00:16:30,390
ir jis negali gauti dydį nuo normos.

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

227
00:16:32,300 --> 00:16:38,160
Taigi, dabar mes norime įgyvendinti tai, ką buvo paaiškinta anksčiau.

228
00:16:38,160 --> 00:16:41,530
Jūs galite dirbti tai už minutę,

229
00:16:41,530 --> 00:16:45,250
ir jūs neturite nerimauti apie tai, kaip viskas puikiai 100% darbo.

230
00:16:45,250 --> 00:16:51,410
Tiesiog parašyti, kaip jūs manote, kad ji turėtų dirbti pusę pseudocode.

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

232
00:16:53,630 --> 00:16:56,350
Nereikia būti visiškai tai padarysite dar.

233
00:16:56,350 --> 00:17:02,380
Bet ar kas nors jaustis patogiai su tuo, ką jie iki šiol,

234
00:17:02,380 --> 00:17:05,599
kaip kažkas, kad galime dirbti kartu?

235
00:17:05,599 --> 00:17:09,690
Ar kas nors nori savanoriauti? Ar aš atsitiktinai pasirinkti.

236
00:17:12,680 --> 00:17:18,599
Ji neturi būti jokių priemonių, bet ką mes galime pakeisti į darbo būseną.

237
00:17:18,599 --> 00:17:20,720
[Studentas] Žinoma. >> Gerai.

238
00:17:20,720 --> 00:17:27,220
Taigi jūs galite išsaugoti peržiūrėti paspaudę ant mažai Išsaugoti piktogramą.

239
00:17:27,220 --> 00:17:29,950
Esate Ramya, tiesa? >> [Studentas] Yeah. >> [Bowden] Gerai.

240
00:17:29,950 --> 00:17:35,140
Taigi, dabar galiu peržiūrėti savo peržiūrą ir kiekvienas gali atsigriebti peržiūrėti.

241
00:17:35,140 --> 00:17:38,600
O čia - Gerai.

242
00:17:38,600 --> 00:17:43,160
Taigi Ramya nuėjo su grįžtamojo sprendimui, kuris tikrai tinkamas sprendimas.

243
00:17:43,160 --> 00:17:44,970
Yra du būdai, kuriuos galite padaryti su šia problema.

244
00:17:44,970 --> 00:17:48,060
Jūs galite padaryti jį keletą kartų arba rekursyviai.

245
00:17:48,060 --> 00:17:53,860
Dauguma jūsų problemų, kad galima padaryti rekursyviai taip pat gali būti atliekamas keletą kartų.

246
00:17:53,860 --> 00:17:58,510
Taigi čia mes padarėme rekursyviai.

247
00:17:58,510 --> 00:18:03,730
>> Ar kas nors nori apibrėžti, ką tai reiškia, kad funkcija rekursinis?

248
00:18:07,210 --> 00:18:08,920
[Studentas] Jei turite funkciją vadinti save

249
00:18:08,920 --> 00:18:13,470
ir tada skambinti, kol jis išeina su tiesa ir teisinga. >> Taip.

250
00:18:13,470 --> 00:18:17,680
Tiesiog rekursinis funkcija yra funkcija, kuri vadina save.

251
00:18:17,680 --> 00:18:24,140
Rekursinis funkcija turi turėti Yra trys dideli dalykai.

252
00:18:24,140 --> 00:18:27,310
Pirmasis yra akivaizdu, kad ji vadina save.

253
00:18:27,310 --> 00:18:29,650
Antra, pagal bazinį scenarijų.

254
00:18:29,650 --> 00:18:33,390
Taigi kažkuriuo momentu funkcija turi sustabdyti skambinate save,

255
00:18:33,390 --> 00:18:35,610
ir tai, ką bazinį scenarijų yra.

256
00:18:35,610 --> 00:18:43,860
Taigi čia mes žinome, kad turime sustabdyti, mes turėtume pasiduoti mūsų paieškos

257
00:18:43,860 --> 00:18:48,150
, kai pradžia yra lygi pabaigoje - ir mes pereiti, ką tai reiškia.

258
00:18:48,150 --> 00:18:52,130
Bet pagaliau, paskutinis dalykas, kad svarbu rekursyvinių funkcijų:

259
00:18:52,130 --> 00:18:59,250
funkcijos turi kažkaip kreiptis į bazinę skyrių (didžiąsias į mažąsias arba atvirkščiai).

260
00:18:59,250 --> 00:19:04,140
Patinka, jei jūs ne iš tikrųjų atnaujinti nieko, kai jūs padaryti antrą rekursinis skambutį,

261
00:19:04,140 --> 00:19:07,880
jei jūs tiesiog tik paskambinus funkciją vėl su tais pačiais argumentais,

262
00:19:07,880 --> 00:19:10,130
ir nėra visuotiniai kintamieji, pasikeitė arba nieko,

263
00:19:10,130 --> 00:19:14,430
jūs niekada nepasieks pagrindą, tokiu atveju, kad blogai.

264
00:19:14,430 --> 00:19:17,950
Tai bus begalinė rekursija ir nepakeliama.

265
00:19:17,950 --> 00:19:24,330
Bet čia mes matome, kad atnaujinimas vyksta, nes mes atnaujinti pradėti + END / 2,

266
00:19:24,330 --> 00:19:28,180
Mes atnaujiname argumentas pabaigos, mes atnaujiname argumentas pradžios.

267
00:19:28,180 --> 00:19:32,860
Taigi visose rekursinis kvietimus mes atnaujinti kažką. Gerai.

268
00:19:32,860 --> 00:19:38,110
Ar norite eiti su mumis per savo sprendimą? >> Žinoma.

269
00:19:38,110 --> 00:19:44,270
Aš naudoju SearchHelp taip, kad kiekvieną kartą, kai aš darau tai skambinimo funkcijos

270
00:19:44,270 --> 00:19:47,910
Turiu, kur aš ieškau masyve pradžią ir pabaigą

271
00:19:47,910 --> 00:19:49,380
nuo to, kur aš ieškau masyvo.

272
00:19:49,380 --> 00:19:55,330
>> Kiekviename žingsnyje, kur jis sakydamas, kad tai vidutinio elementas, kuris yra pradžia + pabaiga / 2,

273
00:19:55,330 --> 00:19:58,850
yra lygi tai, ko mes ieškome?

274
00:19:58,850 --> 00:20:04,650
Ir jei ji yra, tada mes ją radau, ir aš manau, kad gauna išlaikė iki rekursijos lygį.

275
00:20:04,650 --> 00:20:12,540
Ir jei tai nėra tiesa, tada mes patikrinti, ar, kad masyvo viduryje vertė yra per didelis,

276
00:20:12,540 --> 00:20:19,320
tokiu atveju mes pažvelgti į kairę pusę masyvo nuo pradžios iki vidurinės indeksą.

277
00:20:19,320 --> 00:20:22,710
Ir kitaip mes pabaigos 1/2.

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

279
00:20:24,740 --> 00:20:27,730
Skamba viliojančiai.

280
00:20:27,730 --> 00:20:36,640
Gerai, kad pora dalykų, ir iš tikrųjų, tai yra labai aukšto lygio dalykas

281
00:20:36,640 --> 00:20:41,270
kad jūs niekada reikia žinoti šio kurso, bet tai tiesa.

282
00:20:41,270 --> 00:20:46,080
Rekursyvūs funkcijas, kuriuos Jūs visada girdite, kad jie blogai elgtis

283
00:20:46,080 --> 00:20:51,160
nes jei jūs rekursyviai vadina save per daug kartų, gausite nepakeliama

284
00:20:51,160 --> 00:20:54,990
, nes, kaip minėjau anksčiau, kiekviena funkcija gauna savo kamino rėmo.

285
00:20:54,990 --> 00:20:59,500
Taigi, kiekvienas grįžtamojo funkcijos skambučių gauna savo kamino rėmo.

286
00:20:59,500 --> 00:21:04,140
Taigi, jei jūs padarote 1000 rekursinių skambučius, gausite 1000 žetonų rėmus,

287
00:21:04,140 --> 00:21:08,390
greitai ir sukelti per daug žetonų rėmeliai ir dalykų tiesiog pertrauka.

288
00:21:08,390 --> 00:21:13,480
, Kad kodėl rekursyvūs funkcijos paprastai yra blogai.

289
00:21:13,480 --> 00:21:19,370
Bet yra gražus rekursyvinių funkcijų poaibis vadinamas uodega-rekursinių funkcijas,

290
00:21:19,370 --> 00:21:26,120
ir tai atsitinka būti pavyzdys, kur, jei kompiliatorius PRANEŠIMAI tai

291
00:21:26,120 --> 00:21:29,920
ir ji turėtų, manau, Apsukite metalinis garsas, jei pereisite-O2 vėliavos

292
00:21:29,920 --> 00:21:33,250
tada jis tai pastebės, uodega rekursinis ir kad viskas gerai.

293
00:21:33,250 --> 00:21:40,050
>> Jis bus naudoti to paties kamino rėmo vėl ir vėl už kiekvieną grįžtamojo ryšio.

294
00:21:40,050 --> 00:21:47,010
Ir taip, nes jūs naudojate tą patį kamino rėmelį jums nereikia jaudintis dėl

295
00:21:47,010 --> 00:21:51,690
kada nors sukrauti perpildyta, ir tuo pačiu metu, kaip jūs sakėte anksčiau,

296
00:21:51,690 --> 00:21:56,380
kur, kai grįšite tiesa, tada jis turi grąžinti iki visų šių kamino kadrų

297
00:21:56,380 --> 00:22:01,740
ir 10-asis kvietimas SearchHelp turi grįžti į 9-ojo, turi grįžti į 8-oji.

298
00:22:01,740 --> 00:22:05,360
Taip, kad nereikia atsitikti, kai funkcijos yra uodega rekursinis.

299
00:22:05,360 --> 00:22:13,740
Ir taip, ką daro ši funkcija uodega rekursinis pranešimas, kad už bet kurį kvietimą į searchHelp

300
00:22:13,740 --> 00:22:18,470
, rekursinis skambučio, kad tai yra, ką jis grąžina.

301
00:22:18,470 --> 00:22:25,290
Taigi pirmojo kvietimo į SearchHelp, mes iš karto gražins false,

302
00:22:25,290 --> 00:22:29,590
nedelsiant grąžinti tiesa, ar mes darome rekursinis raginimą SearchHelp

303
00:22:29,590 --> 00:22:33,810
kur ką mes grįžti yra kas, kad skambutis grįžta.

304
00:22:33,810 --> 00:22:51,560
Ir mes galime tai padaryti, jei mes padarėme kažką panašaus int x = SearchHelp, grąžinimo x * 2,

305
00:22:51,560 --> 00:22:55,440
tik keletas atsitiktinį pasikeitimą.

306
00:22:55,440 --> 00:23:01,470
>> Taigi dabar tai rekursinis skambutis, tai int x = SearchHelp rekursinis skambutis,

307
00:23:01,470 --> 00:23:05,740
nebėra rekursinis uodega, nes ji iš tikrųjų turi grąžinti

308
00:23:05,740 --> 00:23:10,400
atgal į ankstesnį kamino tarpą taip, kad raginimai funkcijos

309
00:23:10,400 --> 00:23:13,040
tada gali kažką daryti su grįžimo vertės.

310
00:23:13,040 --> 00:23:22,190
Taigi, tai nėra uodega rekursinis, bet tai, ką turėjo prieš tai gražiai uodega rekursinis. Taip.

311
00:23:22,190 --> 00:23:27,000
[Studentas] Jei ne antrą atraminį režimą turėtų būti tikrinama pirmiausia

312
00:23:27,000 --> 00:23:30,640
, nes ten gali būti situacija, kur kai pereisite argumentą

313
00:23:30,640 --> 00:23:35,770
turite start = pabaigos, bet jie yra adata vertė.

314
00:23:35,770 --> 00:23:47,310
Klausimas buvo ne mes paleisti į bylą, kur pabaigoje yra adata vertė

315
00:23:47,310 --> 00:23:52,000
arba pradėti = Pabaigos, tinkamai pradėti = Pabaigos

316
00:23:52,000 --> 00:23:59,480
ir jūs ne iš tikrųjų patikrinta, ypatingą vertę dar

317
00:23:59,480 --> 00:24:03,910
tada pradėti + END / 2 tiesiog bus ta pati vertė.

318
00:24:03,910 --> 00:24:07,890
Bet mes jau grįžo klaidingas ir mes niekada iš tikrųjų patikrinta vertę.

319
00:24:07,890 --> 00:24:14,240
Taigi, bent jau, kai pirmajame kvietime, jei dydis yra 0, tada mes norime grąžinti reikšmę FALSE.

320
00:24:14,240 --> 00:24:17,710
Bet jei dydis yra 1, tada pradžia nesiruošia į vienodą pabaigoje,

321
00:24:17,710 --> 00:24:19,820
ir mes bent patikrinti vieną elementą.

322
00:24:19,820 --> 00:24:26,750
Bet aš manau, kad tu teisus, kad mes gali baigtis tuo atveju, kai pradeda + END / 2,

323
00:24:26,750 --> 00:24:31,190
pradžia galų gale buvo pati pradžia + galutiniam / 2,

324
00:24:31,190 --> 00:24:35,350
bet mes niekada iš tikrųjų patikrinta, elementas.

325
00:24:35,350 --> 00:24:44,740
>> Taigi, jei mes pirmiausia patikrina, yra viduryje elementas vertė mes ieškome,

326
00:24:44,740 --> 00:24:47,110
tada mes galime iš karto grįžti tiesa.

327
00:24:47,110 --> 00:24:50,740
Kita, jei jie lygūs, tada nėra prasmės toliau tęsti

328
00:24:50,740 --> 00:24:58,440
nes mes tik ketina atnaujinti atveju, kai mes esame vieno elemento masyvo.

329
00:24:58,440 --> 00:25:01,110
Jei tai vienas elementas yra ne vienas, mes ieškome,

330
00:25:01,110 --> 00:25:03,530
tada viskas yra blogai. Taip.

331
00:25:03,530 --> 00:25:08,900
[Studentas] dalykas yra tai, kad nuo dydžio iš tiesų yra didesnis nei masyvo elementų skaičius,

332
00:25:08,900 --> 00:25:13,070
jau yra kompensuoti - >> Taigi bus dydis -

333
00:25:13,070 --> 00:25:19,380
[Studentas] Pasakykite, jei masyvo dydis 0, tada SearchHelp tikrai bus patikrinti nuo 0 kaugė

334
00:25:19,380 --> 00:25:21,490
pirmojo kvietimo.

335
00:25:21,490 --> 00:25:25,300
Masyvas dydis 0, 0 - >> Taip.

336
00:25:25,300 --> 00:25:30,750
Yra dar vienas dalykas, kad tai gali būti gera. Pagalvokime.

337
00:25:30,750 --> 00:25:40,120
Taigi, jei masyvo turėjo 10 elementai ir vidurinis mes ketiname patikrinti 5 puslapis,

338
00:25:40,120 --> 00:25:45,700
todėl mes patikrinti 5 ir tarkime, kad vertė yra mažesnė.

339
00:25:45,700 --> 00:25:50,720
Taigi, mes mesti viską toli nuo 5 tolyn.

340
00:25:50,720 --> 00:25:54,030
Taigi pradėkite + pabaiga / 2 bus mūsų naujas galas,

341
00:25:54,030 --> 00:25:57,450
Taigi, yeah, ji visada liksi už masyvo pabaigos.

342
00:25:57,450 --> 00:26:03,570
, Jei tai yra atveju, jei ji buvo net ar nelyginis, tada mes norėtume patikrinti, tarkim, 4,

343
00:26:03,570 --> 00:26:05,770
bet mes vis dar mesti toli -

344
00:26:05,770 --> 00:26:13,500
Taigi, yeah, pabaiga visada bus negalima realiai masyvo pabaigos.

345
00:26:13,500 --> 00:26:18,350
Taigi, mes sutelkiant dėmesį į elementų, pabaiga visada bus po to vienas.

346
00:26:18,350 --> 00:26:24,270
Ir todėl, jei pradžia ar kada nors vienodą pabaigą, mes esame masyvo dydžiui 0.

347
00:26:24,270 --> 00:26:35,600
>> Kitas dalykas, aš galvoju, mes atnaujinti pradžios turi būti pradėti + END / 2,

348
00:26:35,600 --> 00:26:44,020
todėl tai yra tas atvejis, Turiu problemų su, kur pradėti + END / 2

349
00:26:44,020 --> 00:26:46,820
yra Mes tikriname elementas.

350
00:26:46,820 --> 00:26:58,150
Tarkime, kad mes tai 10 elementų masyvą. Koks skirtumas.

351
00:26:58,150 --> 00:27:03,250
Taigi pradėkite + pabaiga / 2 bus kažkas patiko šį vieną,

352
00:27:03,250 --> 00:27:07,060
ir, jei tai ne vertė, tarkim, mes norime atnaujinti.

353
00:27:07,060 --> 00:27:10,060
Vertė yra didesnė, todėl mes norime pažvelgti į šio masyvo pusę.

354
00:27:10,060 --> 00:27:15,910
Taigi, kaip mes atnaujinti pradėti, mes atnaujinti pradėti dabar šis elementas.

355
00:27:15,910 --> 00:27:23,790
Tačiau tai gali dirbti, arba bent jau, jūs galite padaryti pradžią + pabaiga / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Studentas] Jums nereikia būti pradėti + END [nesigirdi] >> Taip.

357
00:27:27,850 --> 00:27:33,240
Mes jau patikrinta šį elementą ir žinau, tai ne vienas, mes ieškome.

358
00:27:33,240 --> 00:27:36,800
Taigi mums nereikia atnaujinti pradžios šis elementas.

359
00:27:36,800 --> 00:27:39,560
Mes galime tiesiog praleiskite jį ir atnaujinti pradžia turi būti šis elementas.

360
00:27:39,560 --> 00:27:46,060
Ir yra ten kada nors, tarkim, kad tai buvo pabaiga

361
00:27:46,060 --> 00:27:53,140
taip, tada pradėti būtų, pradėkite + END / 2 būtų tai,

362
00:27:53,140 --> 00:28:00,580
pradėti + END - Taip, manau, kad tai gali baigtis begalinės rekursijos.

363
00:28:00,580 --> 00:28:12,690
Tarkime, kad tai tik dydis 2 arba 1 dydžio masyvo masyvas. Manau, kad tai veiks.

364
00:28:12,690 --> 00:28:19,490
Taigi šiuo metu, pradžia yra šis elementas ir pabaiga yra 1 už jos ribų.

365
00:28:19,490 --> 00:28:24,110
Taigi yra šis elementas, kad mes ketiname patikrinti,

366
00:28:24,110 --> 00:28:29,400
ir tada, kai mes atnaujiname pradžios mes atnaujinti pradžia turi būti 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
kuris baigsis mums atgal su pradžia yra šis elementas.

368
00:28:33,160 --> 00:28:36,210
>> Todėl mes patikrinti tą patį elementą, vėl ir vėl.

369
00:28:36,210 --> 00:28:43,310
Taigi tai yra tuo atveju, kai kiekvienas rekursinis skambutis turi faktiškai atnaujinti kažką.

370
00:28:43,310 --> 00:28:48,370
Taigi, mums reikia padaryti pradžią + END / 2 + 1, arba kitas atvejis

371
00:28:48,370 --> 00:28:50,710
kai mes ne iš tikrųjų atnaujinimo pradžios.

372
00:28:50,710 --> 00:28:53,820
Visiems žiūrėti, kad?

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

374
00:28:56,310 --> 00:29:03,860
Ar kas nors turite klausimų dėl šio tirpalo arba bet daugiau komentarų?

375
00:29:05,220 --> 00:29:10,280
Gerai. Ar kas nors turite kartotinis sprendimas, kad mes visi galime pažvelgti?

376
00:29:17,400 --> 00:29:20,940
Ar mes visi tai padarysime rekursyviai?

377
00:29:20,940 --> 00:29:25,950
Ar taip pat aš manau, jei jūs atidarėte svetimi, tada jums gali tekti viršesni už ankstesnį.

378
00:29:25,950 --> 00:29:28,810
Ji automatiškai išsaugoti? Aš nesu teigiamas.

379
00:29:35,090 --> 00:29:39,130
Ar kas nors turite kartotinis?

380
00:29:39,130 --> 00:29:42,430
Mes galime vaikščioti per ją kartu, jei ne.

381
00:29:46,080 --> 00:29:48,100
Idėja bus tas pats.

382
00:30:00,260 --> 00:30:02,830
Ciklinis sprendimą.

383
00:30:02,830 --> 00:30:07,140
Mes ketiname norite iš esmės padaryti tą pačią idėją

384
00:30:07,140 --> 00:30:16,530
kur mes norime sekti naujos masyvo pabaigos ir nauja pradžia, masyvo

385
00:30:16,530 --> 00:30:18,510
ir padaryti, kad vėl ir vėl.

386
00:30:18,510 --> 00:30:22,430
Ir jei tai, ką mes nuolat stebėti, kaip pradžioje ir pabaigoje, kada susikerta,

387
00:30:22,430 --> 00:30:29,020
tada mes ne suprato, kad tai ir mes galime grįžti klaidinga.

388
00:30:29,020 --> 00:30:37,540
Taip, kaip man tai padaryti? Kiekvienas turite pasiūlymų ar kodas man traukti?

389
00:30:42,190 --> 00:30:47,450
[Studentas] Ar while cikle. >> Taip.

390
00:30:47,450 --> 00:30:49,450
Jūs ketinate norite padaryti kilpą.

391
00:30:49,450 --> 00:30:51,830
>> Ar turite kodą gali atsigriebti, ar ką jūs ketinate pasiūlyti?

392
00:30:51,830 --> 00:30:56,340
[Studentas] Manau, kad taip. >> Gerai. Tai leidžia lengviau. Koks buvo jūsų vardas?

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

394
00:31:00,140 --> 00:31:04,190
Peržiūra 1. Gerai.

395
00:31:04,190 --> 00:31:13,200
Mažai yra, ką mes vadinami pradėti prieš.

396
00:31:13,200 --> 00:31:17,080
Up yra ne visai tai, ką mes vadinome pabaigoje prieš.

397
00:31:17,080 --> 00:31:22,750
Tiesą sakant, dabar per masyvo pabaigos. Tai elementas, mes turėtume apsvarstyti.

398
00:31:22,750 --> 00:31:26,890
Toks mažas, yra 0, masyvo dydis - 1,

399
00:31:26,890 --> 00:31:34,780
ir dabar mes kilpų, taip pat patikrina,

400
00:31:34,780 --> 00:31:37,340
Manau, galite vaikščioti per ją.

401
00:31:37,340 --> 00:31:41,420
Koks buvo jūsų mąstymas per šį? Vaikščioti mus per savo kodą.

402
00:31:41,420 --> 00:31:49,940
[Studentas] Žinoma. Ieškoti šieno kupetoje vertės viduryje ir palyginti ją su adata.

403
00:31:49,940 --> 00:31:58,520
Taigi, jei jis didesnis nei jūsų adatos, tada jūs norite - O, iš tikrųjų, kad turėtų būti atgal.

404
00:31:58,520 --> 00:32:05,180
Jūs ketinate norite išmesti dešinėje pusėje, ir taip taip, tai turėtų būti būdas.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Taigi tai turėtų būti mažesnis? Yra tai, kad ką jūs pasakėte? >> [Studentas] Yeah.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Gerai. Mažiau.

407
00:32:10,390 --> 00:32:15,700
Taigi, jei tai, ką mes ieškome ne mažesnis nei tai, ką norime,

408
00:32:15,700 --> 00:32:19,410
tada taip, mes norime išmesti į kairę pusę,

409
00:32:19,410 --> 00:32:22,210
, o tai reiškia, mes atnaujinti viską, mes dirbame, kad

410
00:32:22,210 --> 00:32:26,610
juda mažas masyvo teise.

411
00:32:26,610 --> 00:32:30,130
Tai gerai atrodo.

412
00:32:30,130 --> 00:32:34,550
Manau, kad tai turi tą pačią problemą, kad mes pasakė pirmiau paminėtu,

413
00:32:34,550 --> 00:32:49,760
kur, jei mažai yra 0 ir yra 1, tada mažas + iki / 2 ketina įsteigti vėl tas pats.

414
00:32:49,760 --> 00:32:53,860
>> O net jei tai ne tas atvejis, jis vis dar efektyviau, bent jau

415
00:32:53,860 --> 00:32:57,630
tiesiog išmesti elementą, mes tiesiog atrodė, kuriuos mes žinome, yra negerai.

416
00:32:57,630 --> 00:33:03,240
Toks mažas + aukštyn / 2 + 1 - >> [studentas] Tai turėtų būti kitas būdas.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Arba tai turėtų būti - 1, o kita turėtų būti + 1.

418
00:33:05,900 --> 00:33:09,580
[Studentas] Ir ten turėtų būti dvigubai lygybės ženklo. >> [Bowden] Yeah.

419
00:33:09,580 --> 00:33:11,340
[Studentas] Taip.

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

421
00:33:15,910 --> 00:33:21,280
Ir, pagaliau, dabar, kad mes turime šį + 1 - 1 dalykas,

422
00:33:21,280 --> 00:33:31,520
tai - ji gali būti - jis niekada mažas, kad galų gale, kurių vertė yra didesnė nei iki?

423
00:33:35,710 --> 00:33:40,320
Manau, kad vienintelis būdas, kad gali atsitikti - Ar tai įmanoma? >> [Studentas] Nežinau.

424
00:33:40,320 --> 00:33:45,220
Bet jei jis bus sutrumpintas ir tada gauna minus, kad 1 ir tada - >> Taip.

425
00:33:45,220 --> 00:33:47,480
[Studentas] Tai galbūt gauti messed up.

426
00:33:49,700 --> 00:33:53,940
Manau, kad tai turėtų būti gerai, tik todėl, kad

427
00:33:53,940 --> 00:33:58,800
, kad jis galų gale mažesnis, jie turės būti lygus, manau.

428
00:33:58,800 --> 00:34:03,070
Bet jei jie yra lygūs, tada mes nebūtų padarė while cikle prasideda

429
00:34:03,070 --> 00:34:06,670
ir mes tiesiog būtų grąžintas vertę. Taigi, aš manau, kad mes gerai dabar.

430
00:34:06,670 --> 00:34:11,530
Atkreipkite dėmesį, kad, nors ši problema nebėra rekursinis

431
00:34:11,530 --> 00:34:17,400
taikoma tos pačios rūšies idėjų, kur mes galime pamatyti, kaip tai taip lengvai skolina pati

432
00:34:17,400 --> 00:34:23,659
rekursinis sprendimą dėl to, kad mes tiesiog atnaujinti indeksus vėl ir vėl,

433
00:34:23,659 --> 00:34:29,960
mes darome problema mažesni ir mažesni, mes sutelkiant dėmesį į masyvo pogrupyje.

434
00:34:29,960 --> 00:34:40,860
[Studentas] Jei mažai yra 0 ir yra 1, jie abu turi būti 0 + 1/2, kuri būtų eiti į 0,

435
00:34:40,860 --> 00:34:44,429
ir tada būtų + 1, vienas būtų - 1.

436
00:34:47,000 --> 00:34:50,870
[Studentas] Kur mes patikrinti lygybę?

437
00:34:50,870 --> 00:34:55,100
Pavyzdžiui, jei vidurinis yra iš tikrųjų adata?

438
00:34:55,100 --> 00:34:58,590
Šiuo metu mes negalime tai daro? Oh!

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

440
00:35:05,340 --> 00:35:13,740
Taip. Mes galime ne tik atlikti testą žemyn čia, nes tarkim pirmą viduryje -

441
00:35:13,740 --> 00:35:16,430
[Studentas] Tai tikrai patinka neišmeskite jungiasi.

442
00:35:16,430 --> 00:35:20,220
Taigi, jei jūs išmesti jungiasi, jūs turite patikrinti ji pirmą kartą arba nepriklausomai.

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

444
00:35:23,350 --> 00:35:29,650
Taigi dabar mes išmesti vieną, šiuo metu mes pažvelgė,

445
00:35:29,650 --> 00:35:33,260
tai reiškia, kad dabar mes turime taip pat turi

446
00:35:33,260 --> 00:35:44,810
if (kaugė [(žemos + Up) / 2] == adata), tada mes galime grįžti tiesa.

447
00:35:44,810 --> 00:35:52,070
Ir ar kitur arba tiesiog jei aš įdėti, tai reiškia, pažodžiui tą patį

448
00:35:52,070 --> 00:35:57,110
, nes tai būtų grįžo tiesa.

449
00:35:57,110 --> 00:36:01,450
Todėl aš įdėti else if, bet nesvarbu.

450
00:36:01,450 --> 00:36:10,440
>> Else if, dar tai, ir tai yra bendras dalykas, aš

451
00:36:10,440 --> 00:36:14,340
kai, net jei jis yra tuo atveju, kai viskas yra gerai čia,

452
00:36:14,340 --> 00:36:22,780
kaip mažas, niekada negali būti didesnis nei iki, tai nėra verta samprotauti apie tai, ar tai tiesa.

453
00:36:22,780 --> 00:36:28,010
Taigi, jūs galite taip pat pasakyti, o žemas, yra mažesnis arba lygus

454
00:36:28,010 --> 00:36:30,720
o žemas yra mažesnis nei

455
00:36:30,720 --> 00:36:35,300
todėl, jei jie kada nors yra lygus arba mažai atsitinka, kad pass up,

456
00:36:35,300 --> 00:36:40,130
tada mes galime išeiti iš šio ciklo.

457
00:36:41,410 --> 00:36:44,630
Klausimai, rūpesčius, komentarai?

458
00:36:47,080 --> 00:36:49,270
Gerai. Tai gerai atrodo.

459
00:36:49,270 --> 00:36:52,230
Dabar mes norime padaryti rūšiuoti.

460
00:36:52,230 --> 00:37:04,030
Jei mes einame į mano antras peržiūros, mes matome tuos pačius numerius,

461
00:37:04,030 --> 00:37:07,550
bet dabar jie nebėra rūšiuotų tvarka.

462
00:37:07,550 --> 00:37:12,840
Ir mes norime įgyvendinti rūšiuoti naudojant bet kurį algoritmą O n log n.

463
00:37:12,840 --> 00:37:17,240
Taigi, kuris algoritmas manote turėtume įgyvendinti čia? >> [Studentas] suliejimas rūšiuoti.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Taip. Sujungti rūšiuoti yra O (n log n), kad tai, ką mes ketiname daryti.

465
00:37:23,810 --> 00:37:26,680
Ir problema bus labai panašus,

466
00:37:26,680 --> 00:37:31,920
kur lengvai skolina pati į rekursinis sprendimo.

467
00:37:31,920 --> 00:37:35,580
Mes taip pat galime sugalvoti kartotinis tirpalu, jei norime,

468
00:37:35,580 --> 00:37:42,540
bet rekursija bus lengviau čia ir mes turėtume daryti, rekursija.

469
00:37:45,120 --> 00:37:49,530
Aš manau, kad mes vaikščioti per sujungti rūšiuoti,

470
00:37:49,530 --> 00:37:54,280
, nors yra puikus vaizdo suliejimo rūšiuoti. [Juokas]

471
00:37:54,280 --> 00:37:59,780
Taigi sujungti rūšiuoti yra - aš eikvoti tiek daug šio dokumento.

472
00:37:59,780 --> 00:38:02,080
O, yra tik vienas kairėje.

473
00:38:02,080 --> 00:38:03,630
Taigi suliejimą.

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

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

476
00:38:29,910 --> 00:38:33,460
Suliejimas trunka dvi atskiras masyvų.

477
00:38:33,460 --> 00:38:36,780
Atskirai šios dvi matricos yra tiek surūšiuoti.

478
00:38:36,780 --> 00:38:40,970
Taigi šis masyvas, 1, 3, 5, surūšiuoti. Šis masyvas, 0, 2, 4, surūšiuoti.

479
00:38:40,970 --> 00:38:46,710
Dabar ką sujungti reikia padaryti, yra sujungti juos į vieną masyvą, kuri pati yra rūšiuojamos.

480
00:38:46,710 --> 00:38:57,130
Taigi, mes norime masyvo dydis 6, kad ketina turėti šiuos elementus, viduje ji

481
00:38:57,130 --> 00:38:59,390
rūšiuotas tvarka.

482
00:38:59,390 --> 00:39:03,390
>> Ir todėl mes galime pasinaudoti dėl to, kad šios dvi matricos yra rūšiuojamos

483
00:39:03,390 --> 00:39:06,800
tai padaryti linijinio laiko,

484
00:39:06,800 --> 00:39:13,510
linijinis laikas reiškia, jei šis masyvas dydis x ir tai yra dydis m,

485
00:39:13,510 --> 00:39:20,970
bendras algoritmas turėtų būti O (x + y). Gerai.

486
00:39:20,970 --> 00:39:23,150
Taigi, pasiūlymai.

487
00:39:23,150 --> 00:39:26,030
[Studentas] Ar mes galime pradėti iš kairės?

488
00:39:26,030 --> 00:39:30,150
Todėl jūs įdėti 0 žemyn ir tada 1 ir tada čia esate ne 2.

489
00:39:30,150 --> 00:39:33,320
Todėl natūra, kaip jums skirtuką, kad juda į dešinę. >> [Bowden] Yeah.

490
00:39:33,320 --> 00:39:41,070
Tiek iš šių masyvų, jei mes tik sutelkti dėmesį į kairiausias elemento.

491
00:39:41,070 --> 00:39:43,530
Kadangi abi matricos yra rūšiuojamos, mes žinome, kad šie 2 elementai

492
00:39:43,530 --> 00:39:46,920
yra smulkiausi elementai arba masyvo.

493
00:39:46,920 --> 00:39:53,500
Taigi, tai reiškia, kad 1 iš šių 2 elementai turi būti mažiausias elementas mūsų susijungusios masyvo.

494
00:39:53,500 --> 00:39:58,190
Jis tiesiog taip atsitinka, kad mažiausias yra dešinėje Šiuo metu vienas.

495
00:39:58,190 --> 00:40:02,580
Todėl mes 0, įdėkite jį į kairę, nes 0 yra mažiau nei 1,

496
00:40:02,580 --> 00:40:08,210
todėl imasi 0, įdėkite ją į mūsų pirmąją poziciją, ir tada mes atnaujinti šį

497
00:40:08,210 --> 00:40:12,070
sutelkti dėmesį į pirmojo elemento.

498
00:40:12,070 --> 00:40:14,570
Ir dabar mes pakartoti.

499
00:40:14,570 --> 00:40:20,670
Taigi dabar mes palyginti 2 ir 1. 1 yra mažesnis, todėl mes įterpti 1.

500
00:40:20,670 --> 00:40:25,300
Mes atnaujinti šį žymiklį pažymėti šis vaikinas.

501
00:40:25,300 --> 00:40:33,160
Dabar mes tai darome dar kartą, todėl 2. Tai bus atnaujinti, palyginti šias 2, 3.

502
00:40:33,160 --> 00:40:37,770
Šis atnaujinimas, tada 4 ir 5.

503
00:40:37,770 --> 00:40:42,110
Taigi, kad yra sujungti.

504
00:40:42,110 --> 00:40:49,010
>> Ji turėtų būti gana akivaizdu, kad tai yra linijinis laikas, nes mes tiesiog pereiti per kiekvieno elemento kartą.

505
00:40:49,010 --> 00:40:55,980
Ir kad didžiausias žingsnis siekiant įgyvendinti sujungti tarsi tai daro.

506
00:40:55,980 --> 00:40:59,330
Ir tai nereiškia, kad sunku.

507
00:40:59,330 --> 00:41:15,020
Pora dalykų, nerimauti yra, tarkim, mes buvo sujungti 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Šiuo atveju mes galų gale tam atvejui, jei šis yra, bus mažesni,

509
00:41:30,930 --> 00:41:36,160
tada mes atnaujinti šį žymeklį, tai vienas bus mažesni, atnaujinti,

510
00:41:36,160 --> 00:41:41,280
tai vienas mažesnis, ir dabar jūs turite pripažinti,

511
00:41:41,280 --> 00:41:44,220
, kai jūs iš tikrųjų paleisti iš elementų, palyginti su.

512
00:41:44,220 --> 00:41:49,400
Kadangi mes jau visą šį masyvo,

513
00:41:49,400 --> 00:41:55,190
viskas šioje matricoje dabar tiesiog įterpiamas į čia.

514
00:41:55,190 --> 00:42:02,040
Taigi, jei mes kada nors paleisti į tašką, kai vienas iš mūsų masyvų jau visiškai susijungė,

515
00:42:02,040 --> 00:42:06,510
tada mes tiesiog imtis visų Kita masyvo elementus ir įdėkite juos į masyvo pabaigos.

516
00:42:06,510 --> 00:42:13,630
Taigi, mes galime tiesiog įdėkite 4, 5, 6. Gerai.

517
00:42:13,630 --> 00:42:18,070
Tai yra vienas dalykas, kad atkreipti dėmesį.

518
00:42:22,080 --> 00:42:26,120
Įgyvendinimo, kad turėtų būti 1 žingsnis.

519
00:42:26,120 --> 00:42:32,600
Tada sujungti rūšiuoti remiantis, kad jis 2 žingsniai, 2 kvaili žingsniai.

520
00:42:38,800 --> 00:42:42,090
Tegul tik šio masyvo.

521
00:42:57,920 --> 00:43:05,680
Taigi, sujungti rūšiuoti, 1 pakopa yra rekursyviai nutraukti masyvą į dvi dalis.

522
00:43:05,680 --> 00:43:09,350
Taigi padalinti šį masyvą į dvi dalis.

523
00:43:09,350 --> 00:43:22,920
Dabar mes turime 4, 15, 16, 50 ir 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Ir dabar mes jį dar kartą ir mes padalinti juos į dvi dalis.

525
00:43:25,800 --> 00:43:27,530
Aš tiesiog daryti šioje pusėje.

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

527
00:43:34,790 --> 00:43:37,440
Mes darysime tą patį čia.

528
00:43:37,440 --> 00:43:40,340
Ir dabar mes padalinti jį į dvi dalis vėl.

529
00:43:40,340 --> 00:43:51,080
Ir mes turime 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Taigi, tai yra mūsų bazinį scenarijų.

531
00:43:53,170 --> 00:44:00,540
Kai matricos yra 1 dydžio, tada mes nustojame su skirstymą į dvi dalis.

532
00:44:00,540 --> 00:44:03,190
>> Dabar ką daryti su šiuo teiginiu?

533
00:44:03,190 --> 00:44:15,730
Mes galų gale tai taip pat suskirstyti į 8, 23, 42, ir 108.

534
00:44:15,730 --> 00:44:24,000
Taigi dabar, kad mes šiuo metu, dabar du sujungti rūšiuoti žingsnis yra tiesiog sujungti poras į sąrašus.

535
00:44:24,000 --> 00:44:27,610
Taigi, mes norime sujungti šias. Mes tiesiog paskambinkite suliejimą.

536
00:44:27,610 --> 00:44:31,410
Mes žinome, sujungti bus grąžinti juos rūšiuotas tvarka.

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

538
00:44:33,920 --> 00:44:41,440
Dabar mes norime sujungti ir kad bus grąžinti sąrašą su rūšiuotų tvarka,

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

540
00:44:44,160 --> 00:44:57,380
Mes sujungti tų, - aš negaliu rašyti - 8, 23 ir 42, 108.

541
00:44:57,380 --> 00:45:02,890
Taigi, mes turime sulieti porų vienu metu.

542
00:45:02,890 --> 00:45:05,140
Dabar mes tiesiog sujungti dar kartą.

543
00:45:05,140 --> 00:45:10,130
Atkreipkite dėmesį, kad kiekvienas iš šių sąrašų, yra rūšiuojama savaime

544
00:45:10,130 --> 00:45:15,220
ir tada mes galime tiesiog sujungti šiuos sąrašus gauti 4 dydžio sąrašą, kuris yra rūšiuojamas

545
00:45:15,220 --> 00:45:19,990
ir sujungti šiuos du sąrašus gauti 4 dydžio sąrašą, kuriame vyksta rūšiavimas.

546
00:45:19,990 --> 00:45:25,710
Ir, pagaliau, mes galime sujungti šiuos du sąrašus dydis 4 gauti vieną sąrašą, dydis 8, surūšiuoti.

547
00:45:25,710 --> 00:45:34,030
Taigi, norint pamatyti, kad tai yra bendras n log n, mes jau matėme, kad sujungti yra tiesinė,

548
00:45:34,030 --> 00:45:40,390
todėl, kai mes susiduriame su Sujungiant šiuos, kaip bendrų išlaidų suliejimą

549
00:45:40,390 --> 00:45:43,410
šių dviejų sąrašų, yra tik 2, nes -

550
00:45:43,410 --> 00:45:49,610
Ar gerai, O n, bet n čia yra tik šie 2 elementai, todėl 2.

551
00:45:49,610 --> 00:45:52,850
Ir tai 2 bus 2 ir šių 2 bus 2 ir tai 2 bus 2,

552
00:45:52,850 --> 00:45:58,820
visoje susilieja, kad mes turime padaryti, mes galų gale padaryti n.

553
00:45:58,820 --> 00:46:03,210
Kaip ir 2 + 2 + 2 + 2 8, kuris yra n,

554
00:46:03,210 --> 00:46:08,060
taip sujungti šio rinkinio kaina yra n.

555
00:46:08,060 --> 00:46:10,810
Ir tada tas pats čia.

556
00:46:10,810 --> 00:46:16,980
Mes sujungti šių 2, tada jos 2 ir individualiai tai sujungti per keturias operacijas,

557
00:46:16,980 --> 00:46:23,610
tai sujungti užtruks keturias operacijas, tačiau dar kartą, tarp visų šių,

558
00:46:23,610 --> 00:46:29,030
mes galų gale sujungti n viso dalykų, ir todėl šis žingsnis yra n.

559
00:46:29,030 --> 00:46:33,670
Ir taip kiekvienas lygis trunka n elementai, nesujungti.

560
00:46:33,670 --> 00:46:36,110
>> Kiek lygių yra?

561
00:46:36,110 --> 00:46:40,160
Kiekviename lygmenyje, iš daugybės auga pagal dydį 2.

562
00:46:40,160 --> 00:46:44,590
Čia mūsų matricos yra 1 dydžio, čia jie 2 dydžio, čia jie 4 dydžio,

563
00:46:44,590 --> 00:46:46,470
ir, galiausiai, jie 8 dydžio.

564
00:46:46,470 --> 00:46:56,450
Taigi, kadangi tai yra du kartus, yra ir bus iš viso n log iš šių lygių.

565
00:46:56,450 --> 00:47:02,090
Taigi su log n lygių, kiekvienas lygis, atsižvelgiant n bendras operacijas,

566
00:47:02,090 --> 00:47:05,720
mes gauname n log n algoritmas.

567
00:47:05,720 --> 00:47:07,790
Turite klausimų?

568
00:47:08,940 --> 00:47:13,320
Ar žmonės jau padarė pažangą, kaip įgyvendinti?

569
00:47:13,320 --> 00:47:18,260
Ar kas nors jau yra valstybės, kur galiu tik atsigriebti savo kodą?

570
00:47:20,320 --> 00:47:22,260
Aš galiu duoti vieną minutę.

571
00:47:24,770 --> 00:47:27,470
Tai vienas bus ilgesnis.

572
00:47:27,470 --> 00:47:28,730
Aš labai rekomenduoju pasikartotų -

573
00:47:28,730 --> 00:47:30,510
Jūs neturite daryti Rekursija suliejimą

574
00:47:30,510 --> 00:47:33,750
nes priešingu Rekursija suliejimą, jūs ketinate turi išlaikyti krūvą įvairių dydžių.

575
00:47:33,750 --> 00:47:37,150
Galite, bet tai erzina.

576
00:47:37,150 --> 00:47:43,720
Bet rekursija dėl pačios rūšies yra gana lengva.

577
00:47:43,720 --> 00:47:49,190
Jūs tiesiog tiesiog paskambinti rūšiuoti kairę pusę, tarsi dešinėje pusėje. Gerai.

578
00:47:51,770 --> 00:47:54,860
Kiekvienas turi ką galiu atsigriebti dar?

579
00:47:54,860 --> 00:47:57,540
Kitaip aš duosiu minutę.

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

581
00:47:59,900 --> 00:48:02,970
Kiekvienas turi ką mes galime dirbti su?

582
00:48:05,450 --> 00:48:09,680
Arba dar mes tiesiog dirbti tai ir tada išplėskite iš ten.

583
00:48:09,680 --> 00:48:14,050
>> Kiekvienas turi daugiau nei tai, kad aš galiu atsigriebti?

584
00:48:14,050 --> 00:48:17,770
[Studentas] Taip. Galite traukti mano. >> Gerai.

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

586
00:48:22,170 --> 00:48:25,280
[Studentas] buvo daug sąlygų. >> O, šaudyti. Ar galite

587
00:48:25,280 --> 00:48:28,110
[Studentas] Turiu ją išsaugoti. >> Taip.

588
00:48:32,420 --> 00:48:35,730
Taigi, mes padarėme padaryti suliejimą atskirai.

589
00:48:35,730 --> 00:48:38,570
Oh, bet tai nereiškia, kad blogai.

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

591
00:48:41,650 --> 00:48:47,080
Taigi, rūšiuoti tiesiog paskambinę mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Paaiškinti mums, ką mergeSortHelp.

593
00:48:49,530 --> 00:48:55,700
[Studentas] MergeSortHelp gana daug daro du pagrindinius veiksmus,

594
00:48:55,700 --> 00:49:01,270
kuris yra rūšiuoti kiekvieną masyvo pusę ir tada sujungti juos abu.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Gerai, kad duoti man per sekundę.

596
00:49:10,850 --> 00:49:13,210
Manau, kad tai - >> [studentas] Man reikia

597
00:49:17,100 --> 00:49:19,400
Taip. Aš kažko trūksta.

598
00:49:19,400 --> 00:49:23,100
Suliejimą, aš suprantu, kad man reikia sukurti naują masyvą

599
00:49:23,100 --> 00:49:26,530
, nes aš negalėjo padaryti jį į vietą. >> Taip. Jūs galite ne. Ištaisyti.

600
00:49:26,530 --> 00:49:28,170
[Studentas] Taigi, aš sukurti naują masyvą.

601
00:49:28,170 --> 00:49:31,510
Aš pamiršau sujungti vėl pakeisti pabaigoje.

602
00:49:31,510 --> 00:49:34,490
Gerai. Mes turime naują masyvą.

603
00:49:34,490 --> 00:49:41,000
Merge sort, tai beveik visada tiesa.

604
00:49:41,000 --> 00:49:44,340
Dalis geriau algoritmas laiko protingas išlaidas

605
00:49:44,340 --> 00:49:47,310
beveik visada reikia naudoti šiek tiek daugiau atminties.

606
00:49:47,310 --> 00:49:51,570
Taigi čia, nesvarbu, kaip jūs tai darote sujungti rūšiuoti,

607
00:49:51,570 --> 00:49:54,780
jūs neišvengiamai reikia naudoti tam tikrą papildomą atmintį.

608
00:49:54,780 --> 00:49:58,240
Jis arba ji sukūrė naują masyvą.

609
00:49:58,240 --> 00:50:03,400
Ir tada jums sako, kad pabaigoje mes tiesiog reikia nukopijuoti naują masyvą, į pirminį masyvo.

610
00:50:03,400 --> 00:50:04,830
[Studentas] Manau, kad taip, taip.

611
00:50:04,830 --> 00:50:08,210
Aš nežinau, jei kuri veikia skaičiuojant nuoroda ar whatever -

612
00:50:08,210 --> 00:50:11,650
Taip, jis bus dirbti. >> [Studentas] Gerai.

613
00:50:20,620 --> 00:50:24,480
Ar jūs pabandykite paleisti? >> [Studentas] Ne, dar ne. >> Gerai.

614
00:50:24,480 --> 00:50:28,880
Pabandykite paleisti jį, o tada aš kalbėti apie tai už antrą.

615
00:50:28,880 --> 00:50:35,200
[Studentas] man reikia, kad visi funkcija prototipus ir viskas, nors, tiesa?

616
00:50:37,640 --> 00:50:40,840
Funkcijos prototipus. O, tu kalbi kaip - Taip.

617
00:50:40,840 --> 00:50:43,040
Rūšiuoti skambina mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Taigi, tam, kad rūšiuoti skambinti mergeSortHelp, mergeSortHelp turi arba buvo apibrėžta

619
00:50:47,390 --> 00:50:56,370
prieš rūšiuoti ar mes tiesiog reikia prototipą. Tiesiog nukopijuokite ir įklijuokite kad.

620
00:50:56,370 --> 00:50:59,490
Ir panašiai, mergeSortHelp ragina sujungti,

621
00:50:59,490 --> 00:51:03,830
bet sujungti dar nebuvo apibrėžta, todėl mes galime tiesiog leiskite mergeSortHelp žinoti

622
00:51:03,830 --> 00:51:08,700
, kad tai, ką sujungti atrodys, ir tai, kad.

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

624
00:51:22,770 --> 00:51:32,660
Mes turime problemą čia, kur mes neturime bazinį scenarijų.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp yra rekursinis, todėl bet rekursinis funkcija

626
00:51:38,110 --> 00:51:42,610
going to reikia kažkokią bazine žinoti, kada sustoti rekursyviai pasivadino.

627
00:51:42,610 --> 00:51:45,590
Kas yra mūsų bazinį scenarijų bus čia? Taip.

628
00:51:45,590 --> 00:51:49,110
[Studentas] Jei dydis yra 1? >> [Bowden] Taip.

629
00:51:49,110 --> 00:51:56,220
Taigi, kaip matėme teisę ten, mes sustojo išskaidyti masyvų

630
00:51:56,220 --> 00:52:01,850
kartą patekome į masyvų yra 1, kuris neišvengiamai yra rūšiuojamos.

631
00:52:01,850 --> 00:52:09,530
Taigi, jei dydis lygus 1, mes žinome, masyvas jau surūšiuoti,

632
00:52:09,530 --> 00:52:12,970
todėl mes galime tik grįžti.

633
00:52:12,970 --> 00:52:16,880
>> Atkreipkite dėmesį, kad negalioja, todėl mes negalime grįžti nieko ypatingą, mes tiesiog grįžti.

634
00:52:16,880 --> 00:52:19,580
Gerai. Štai taip atrodo mūsų bazinį scenarijų.

635
00:52:19,580 --> 00:52:27,440
Manau, mūsų bazinį scenarijų taip pat gali būti, jei atsitiktų būti sujungti masyvas dydžiui 0,

636
00:52:27,440 --> 00:52:30,030
mes tikriausiai norite sustabdyti tam tikru momentu,

637
00:52:30,030 --> 00:52:33,610
todėl mes galime tik pasakyti dydis mažiau nei 2 ar mažiau kaip arba lygi 1

638
00:52:33,610 --> 00:52:37,150
kad tai bus dirbti bet kuriuo masyvo dabar.

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

640
00:52:38,870 --> 00:52:42,740
Štai taip atrodo mūsų bazinį scenarijų.

641
00:52:42,740 --> 00:52:45,950
Dabar jūs norite eiti su mumis per suliejimą?

642
00:52:45,950 --> 00:52:49,140
Ką reiškia visi šie atvejai?

643
00:52:49,140 --> 00:52:54,480
Čia, mes tiesiog daro tą pačią idėją, -

644
00:52:56,970 --> 00:53:02,470
[Studentas] man reikia artimųjų dydį su visais mergeSortHelp skambučius.

645
00:53:02,470 --> 00:53:10,080
Dydžio kaip aš pridėjo papildomą pirminiuose ir jo ten nėra, pavyzdžiui, dydžio / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] O, dydis / 2, dydis / 2. >> [Studentas] Taip, ir pirmiau funkcija, taip pat.

647
00:53:16,210 --> 00:53:21,320
[Bowden]? >> [Studentas] Tiesiog dydis. >> [Bowden] Oh. Dydis, dydis? >> [Studentas] Yeah.

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

649
00:53:23,010 --> 00:53:26,580
Leisk pagalvoti per sekundę.

650
00:53:26,580 --> 00:53:28,780
Mes paleisti į klausimą?

651
00:53:28,780 --> 00:53:33,690
Mes visada gydyti į kairę kaip 0. >> [Studentas] L.

652
00:53:33,690 --> 00:53:36,340
Kad negerai. Atsiprašau. Ji turėtų būti pradžia. Taip.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Gerai. Man patinka, kad geriau.

654
00:53:39,230 --> 00:53:43,880
Ir baigiasi. Gerai.

655
00:53:43,880 --> 00:53:47,200
Taigi, dabar jūs norite eiti su mumis per suliejimą? >> [Studentas] Gerai.

656
00:53:47,200 --> 00:53:52,150
Aš tiesiog vaikščioti per šio naujo masyvo, kad aš sukūriau.

657
00:53:52,150 --> 00:53:57,420
Jo dydis yra masyvo dalies dydis, kad mes norime būti rūšiuojami

658
00:53:57,420 --> 00:54:03,460
ir bando rasti elementą, kad aš įdėti į naują masyvo žingsnio.

659
00:54:03,460 --> 00:54:10,140
Tai padaryti, kad, visų pirma, aš patikrinti, jei yra kairėje pusėje, masyvo ir toliau turi bet daugiau elementų,

660
00:54:10,140 --> 00:54:14,260
ir jei jis nėra, tada jūs einate žemyn, kad dar būklės, kuris tiesiog sako

661
00:54:14,260 --> 00:54:20,180
gerai, ji turi būti teisinga masyvo, ir mes įdėti, kad į dabartinę indekso newArray.

662
00:54:20,180 --> 00:54:27,620
>> Ir tada kitaip, aš patikrinti, jei dešinėje pusėje masyvo taip pat baigiama,

663
00:54:27,620 --> 00:54:30,630
tokiu atveju aš tiesiog įdėti kairėje.

664
00:54:30,630 --> 00:54:34,180
Kad gali ne iš tikrųjų būtina. Nesu tikras.

665
00:54:34,180 --> 00:54:40,970
Bet vistiek, kiti du patikrinimas, kuris iš dviejų yra mažesnis kairės į dešinę.

666
00:54:40,970 --> 00:54:49,770
, O taip pat kiekvienu konkrečiu atveju, aš incrementing nepriklausomai nuo vietos rezervavimo ženklą, aš prieaugio.

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

668
00:54:52,040 --> 00:54:53,840
Kad gerai atrodo.

669
00:54:53,840 --> 00:54:58,800
Ar kas nors turite pastabų ar Taikoma arba klausimų?

670
00:55:00,660 --> 00:55:07,720
Taigi keturiose bylose turime neštis savo daiktus į tiesiog yra arba atrodo, kad 5 -

671
00:55:07,720 --> 00:55:13,100
bet mes turime apsvarstyti, ar į kairę masyvas buvo paleisti iš dalykų, mes turime sujungti,

672
00:55:13,100 --> 00:55:16,390
, ar teisė masyvas buvo paleisti iš dalykų, mes turime sujungti

673
00:55:16,390 --> 00:55:18,400
Aš nukreipta nieko.

674
00:55:18,400 --> 00:55:21,730
Taigi,, ar kairę masyvas paleisti iš dalykų, arba teisę masyvas paleisti iš ką.

675
00:55:21,730 --> 00:55:24,320
Tai yra du atvejai.

676
00:55:24,320 --> 00:55:30,920
Mes taip pat reikia trivialus atvejis, ar į kairę dalykas yra mažiau nei teisingas dalykas.

677
00:55:30,920 --> 00:55:33,910
Tai mes norime pasirinkti kairįjį patį.

678
00:55:33,910 --> 00:55:37,630
Tai yra atvejai.

679
00:55:37,630 --> 00:55:40,990
Taigi tai buvo teisus, todėl tai, kad.

680
00:55:40,990 --> 00:55:46,760
Masyvas kairę. Tai 1, 2, 3. Gerai. Taigi, yeah, jie yra keturi dalykai, mes norime tai padaryti.

681
00:55:50,350 --> 00:55:54,510
Ir mes negalime eiti per pasikartojantis sprendimą.

682
00:55:54,510 --> 00:55:55,980
Aš nepatarčiau -

683
00:55:55,980 --> 00:56:03,070
Sujungti rūšiuoti funkcijos pavyzdys, kuris yra ir ne uodega rekursinis

684
00:56:03,070 --> 00:56:07,040
tai nėra lengva, kad jis uodega rekursinis,

685
00:56:07,040 --> 00:56:13,450
bet taip pat ji nėra labai lengva, kad jis pasikartojantis.

686
00:56:13,450 --> 00:56:16,910
Tai labai paprasta.

687
00:56:16,910 --> 00:56:19,170
Šis Merge sort įgyvendinimą,

688
00:56:19,170 --> 00:56:22,140
sujungti, nesvarbu, ką jūs darote, jūs ketinate kurti suliejimą.

689
00:56:22,140 --> 00:56:29,170
>> Taigi sujungti tarsi pastatytas ant viršaus suliejimo rekursyviai yra tik šių trijų eilučių.

690
00:56:29,170 --> 00:56:34,700
Keletą kartų, tai labiau erzina ir sunkiau galvoti apie.

691
00:56:34,700 --> 00:56:41,860
, Bet pastebėsite, kad tai ne uodega rekursinis nuo mergeSortHelp - kai ji vadina save -

692
00:56:41,860 --> 00:56:46,590
ji vis dar turi daryti tai, ko po šio rekursinis skambučių grąžos.

693
00:56:46,590 --> 00:56:50,830
Taigi tai kamino rėmas turi ir toliau egzistuoti net paskambinus.

694
00:56:50,830 --> 00:56:54,170
Ir tada, kai tai vadiname, kamino rėmas turi ir toliau egzistuoti

695
00:56:54,170 --> 00:56:57,780
nes net po to kvietimo, mes vis dar reikia sujungti.

696
00:56:57,780 --> 00:57:01,920
Ir tai yra Nenereikšmingas kad ši uodega rekursinis.

697
00:57:04,070 --> 00:57:06,270
Turite klausimų?

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

699
00:57:09,860 --> 00:57:13,400
Taigi vyksta rūšiuoti - O, yra du dalykai, aš noriu parodyti. Gerai.

700
00:57:13,400 --> 00:57:17,840
Grįžtant rūšiuoti, mes tai padaryti greitai.

701
00:57:17,840 --> 00:57:21,030
Ar paieškos terminą. Rūšiuoti? Rūšiuoti. Taip.

702
00:57:21,030 --> 00:57:22,730
Grįžtant prie rūšies pradžia.

703
00:57:22,730 --> 00:57:29,870
Mes norime sukurti algoritmą, kuris rūšių masyvo, naudodami bet kokį algoritmą

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

705
00:57:33,660 --> 00:57:40,860
Taigi, kaip tai įmanoma? Ar kas nors turite rūšiuoti -

706
00:57:40,860 --> 00:57:44,300
Aš užsiminė prieš ne -

707
00:57:44,300 --> 00:57:48,300
Jei mes netrukus pasitaisys iš n log n O n,

708
00:57:48,300 --> 00:57:51,450
mes turime tobulinti mūsų algoritmas laiko protingas,

709
00:57:51,450 --> 00:57:55,250
o tai reiškia, ką mes ketiname reikia padaryti, kad už tai?

710
00:57:55,250 --> 00:57:59,520
[Studentas] tarpas. >> Taip. Mes ketinate naudoti daugiau vietos.

711
00:57:59,520 --> 00:58:04,490
Ir net ne tik daugiau vietos, tai eksponentiškai daugiau erdvės.

712
00:58:04,490 --> 00:58:14,320
Todėl manau, kad šis algoritmas yra pseudo kažkas pseudo polinom -

713
00:58:14,320 --> 00:58:18,980
Pseudo - Aš negaliu prisiminti. Pseudo kažką.

714
00:58:18,980 --> 00:58:22,210
Bet tai reiškia, kad mes turime naudoti tiek daug vietos

715
00:58:22,210 --> 00:58:28,610
, kad tai įmanoma, bet ne realus.

716
00:58:28,610 --> 00:58:31,220
>> Ir kaip mes tai pasiekti?

717
00:58:31,220 --> 00:58:36,810
Mes galime pasiekti tai, jei mes garantuojame, kad bet kuris konkretus elementas masyve

718
00:58:36,810 --> 00:58:39,600
yra mažesnė už tam tikrą dydį.

719
00:58:42,070 --> 00:58:44,500
Todėl galime tik pasakyti, kad dydis yra 200,

720
00:58:44,500 --> 00:58:48,130
bet kuris masyvo elementas yra žemiau dydis 200.

721
00:58:48,130 --> 00:58:51,080
Ir iš tikrųjų tai yra labai realus.

722
00:58:51,080 --> 00:58:58,660
Jūs galite labai lengvai masyvą, kad jūs žinote viską, kas jame

723
00:58:58,660 --> 00:59:00,570
bus mažiau nei kai kurios numerį.

724
00:59:00,570 --> 00:59:07,400
Pavyzdžiui, jei turite kokių nors visiškai masyvi vektoriniu ar kažką

725
00:59:07,400 --> 00:59:11,810
, bet jūs žinote, viskas bus nuo 0 iki 5,

726
00:59:11,810 --> 00:59:14,790
tada jis bus žymiai greičiau tai padaryti.

727
00:59:14,790 --> 00:59:17,930
Ir jungiasi bet elementų yra 5,

728
00:59:17,930 --> 00:59:21,980
, todėl šis vertinimas, tai yra, kiek atminties jūs ketinate naudoti.

729
00:59:21,980 --> 00:59:26,300
Taigi jungiasi yra 200.

730
00:59:26,300 --> 00:59:32,960
Teoriškai visada privalo nuo sveikasis skaičius gali būti tik gali siekti 4 mlrd,

731
00:59:32,960 --> 00:59:40,600
bet tai nerealus dalykas, nes tada mes norime būti, naudojant palydoviniu arba

732
00:59:40,600 --> 00:59:44,400
4 mlrd tvarka. Taigi, kad nerealu.

733
00:59:44,400 --> 00:59:47,060
Bet čia mes pasakyti mūsų jungiasi yra 200.

734
00:59:47,060 --> 00:59:59,570
Pavyko tai daryti O n yra mes kitą masyve skaičiuojamas dydžio LAIKYTIS.

735
00:59:59,570 --> 01:00:10,470
Taigi, iš tikrųjų, tai yra nuoroda - Aš iš tikrųjų nežinau, jei Apsukite metalinis garsas tai daro.

736
01:00:11,150 --> 01:00:15,330
, Bet I 'GCC bent jau darant prielaidą, Apsukite metalinis garsas tai taip pat -

737
01:00:15,330 --> 01:00:18,180
tai bus tik inicijuoti visą masyvą būti 0s.

738
01:00:18,180 --> 01:00:25,320
Taigi, jei aš nenoriu padaryti, kad, tada aš galėčiau atskirai padaryti for (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <privalomi; i + +) ir skaičius [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Taigi, dabar viskas yra inicializuoti iki 0.

741
01:00:35,260 --> 01:00:39,570
Aš kartoti per mano masyvo,

742
01:00:39,570 --> 01:00:51,920
ir tai, ką aš darau, tai aš skaičiuojant kiekvieno Leiskite eiti čia.

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

744
01:00:55,480 --> 01:01:00,010
Ką aš skaičiuoti įvykių, kiekvienas iš šių elementų skaičius.

745
01:01:00,010 --> 01:01:03,470
Leiskite pridėti pora daugiau čia su kai kuriais kartojasi.

746
01:01:03,470 --> 01:01:11,070
Todėl vertė mes čia, kad vertė bus masyvas [i].

747
01:01:11,070 --> 01:01:14,850
Taigi, gali būti 4 ar 8 ar kokia val.

748
01:01:14,850 --> 01:01:18,870
Ir dabar aš skaičiuoti, kiek tos vertės, aš mačiau,

749
01:01:18,870 --> 01:01:21,230
taip skaičiaus [val] + +;

750
01:01:21,230 --> 01:01:29,430
Po to, kai tai bus padaryta, skaičius ketina atrodyti 0001.

751
01:01:29,430 --> 01:01:42,190
Darykime skaičių [val] - LAIKYTIS + 1.

752
01:01:42,190 --> 01:01:48,230
>> Dabar tai tik atsiskaityti už tai, kad mes pradedame nuo 0.

753
01:01:48,230 --> 01:01:50,850
Taigi, jei 200 bus mūsų didžiausias skaičius,

754
01:01:50,850 --> 01:01:54,720
tada 0 200 yra 201 dalykų.

755
01:01:54,720 --> 01:02:01,540
Taigi skaičius, jis bus atrodyti 00.001, nes mes turime vieną 4.

756
01:02:01,540 --> 01:02:10,210
Tada mes turime 0001, kur mes turime 1 8-ajame indekso skaičius.

757
01:02:10,210 --> 01:02:14,560
Mes turime 2 23 indekso skaičius.

758
01:02:14,560 --> 01:02:17,630
Mes turime 2 42-ąjį skaičiaus indekso.

759
01:02:17,630 --> 01:02:21,670
Taigi, mes galime naudoti skaičius.

760
01:02:34,270 --> 01:02:44,920
Taigi num_of_item = skaičius [i].

761
01:02:44,920 --> 01:02:52,540
Ir todėl, jei num_of_item yra 2, tai reiškia, kad mes norime įterpti 2 skaičiaus i

762
01:02:52,540 --> 01:02:55,290
į mūsų rūšiuotų masyvo.

763
01:02:55,290 --> 01:03:02,000
Taigi, mes turime sekti, kaip toli mes į masyvo.

764
01:03:02,000 --> 01:03:05,470
Taigi indeksas = 0.

765
01:03:05,470 --> 01:03:09,910
Array - aš tiesiog rašyti.

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

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

768
01:03:28,580 --> 01:03:32,490
Kad tai, ką aš noriu? Manau, kad tai, ko aš noriu.

769
01:03:35,100 --> 01:03:38,290
Taip, tai gerai atrodo. Gerai.

770
01:03:38,290 --> 01:03:43,050
Taigi, visi supranta, ką mano skaičiavimų masyvo tikslas?

771
01:03:43,050 --> 01:03:48,140
Jis tikisi įvykių kiekvienos iš šių numerių skaičių.

772
01:03:48,140 --> 01:03:51,780
Tada aš iteravimu per masyvas, kuris skaičiuoja,

773
01:03:51,780 --> 01:03:57,190
osios pozicijos grafų masyve

774
01:03:57,190 --> 01:04:01,930
yra i "numeris, kuris turėtų pasirodyti mano rūšiuotų masyvo.

775
01:04:01,930 --> 01:04:06,840
Štai kodėl skaičius bus 1 iš 4

776
01:04:06,840 --> 01:04:11,840
ir tikisi, kad bus 1 iš 8 Suskaičiavus 23 bus 2.

777
01:04:11,840 --> 01:04:16,900
Taip, kad kiek jų norite įterpti į mano rūšiuotų masyvo.

778
01:04:16,900 --> 01:04:19,200
Tada aš tiesiog tai padaryti.

779
01:04:19,200 --> 01:04:28,960
Aš įterpiant num_of_item i į mano rūšiuotų masyvo.

780
01:04:28,960 --> 01:04:31,670
>> Turite klausimų?

781
01:04:32,460 --> 01:04:43,100
Ir tokiu būdu vėlgi, tai yra linijinis laikas, nes mes tiesiog iteravimu per vieną kartą,

782
01:04:43,100 --> 01:04:47,470
tačiau ji taip pat linijinis, ką šis skaičius būna, kad,

783
01:04:47,470 --> 01:04:50,730
ir todėl labai priklauso nuo to, ką jūsų jungiasi yra.

784
01:04:50,730 --> 01:04:53,290
Jungiasi su 200, tai nėra taip blogai.

785
01:04:53,290 --> 01:04:58,330
Jei jūsų jungiasi bus 10.000, tada, kad šiek tiek blogiau,

786
01:04:58,330 --> 01:05:01,360
bet jei jūsų jungiasi bus 4 milijardų eurų, tai visiškai nerealu

787
01:05:01,360 --> 01:05:07,720
ir šis masyvas turi būti dydis 4 mlrd., o tai nėra realu.

788
01:05:07,720 --> 01:05:10,860
Taigi tai, kad. Turite klausimų?

789
01:05:10,860 --> 01:05:13,270
[Nesigirdi studentas atsakas] >> Gerai.

790
01:05:13,270 --> 01:05:15,710
Supratau, vienas kitas dalykas, kai mes buvome išgyvena.

791
01:05:17,980 --> 01:05:23,720
Manau, kad problema buvo Lucas ir turbūt kiekvienas iš matėme.

792
01:05:23,720 --> 01:05:26,330
Aš visiškai pamiršau.

793
01:05:26,330 --> 01:05:31,040
Vienintelis dalykas, aš norėjau komentarą apie tai, kad kai jūs susiduriame su dalykų, pavyzdžiui, indeksų,

794
01:05:31,040 --> 01:05:38,320
jūs niekada pamatyti tai, kai rašote už linijos,

795
01:05:38,320 --> 01:05:41,120
, tačiau techniniu požiūriu, kai jūs susiduriame su šių rodiklių,

796
01:05:41,120 --> 01:05:45,950
beveik visada turėtumėte susidoroti su nepasirašytos sveikieji skaičiai.

797
01:05:45,950 --> 01:05:53,850
Dėl šios priežasties, kai jūs susiduriame su pasirašytų sveikieji skaičiai,

798
01:05:53,850 --> 01:05:56,090
todėl, jei turite 2 pasirašytas sveikieji skaičiai ir įtraukite juos kartu

799
01:05:56,090 --> 01:06:00,640
ir jie galų gale per didelis, tada jūs galų gale su neigiamas skaičius.

800
01:06:00,640 --> 01:06:03,410
, Kad sveikasis skaičius perpildymo.

801
01:06:03,410 --> 01:06:10,500
>> Jei galiu pridėti 2 mlrd 1 mlrd., Aš galų gale su neigiamu 1 mlrd.

802
01:06:10,500 --> 01:06:15,480
Štai kaip sveikieji skaičiai kompiuteriuose.

803
01:06:15,480 --> 01:06:17,510
Taigi problema su naudojant

804
01:06:17,510 --> 01:06:23,500
Tai gerai, išskyrus atvejus, kai mažas atsitinka būti 2 mlrd. Ir atsitinka, turi būti 1 mlrd,

805
01:06:23,500 --> 01:06:27,120
tada tai bus Neigiamas 1 milijardų ir tada mes ketiname padalyti iš 2

806
01:06:27,120 --> 01:06:29,730
ir galų gale su neigiamu 500.000.000.

807
01:06:29,730 --> 01:06:33,760
Taigi tai yra tik klausimas, jei atsitiktų reikia ieškoti per masyvo

808
01:06:33,760 --> 01:06:38,070
milijardų dalykų.

809
01:06:38,070 --> 01:06:44,050
Bet jei mažas + iki atsitinka perkrautas, tada, kad yra problema.

810
01:06:44,050 --> 01:06:47,750
Kuo greičiau mes juos nepasirašytos nei 2 mlrd plius 1 mlrd 3 mlrd.

811
01:06:47,750 --> 01:06:51,960
3 mlrd. Padalinti iš 2 yra 1,5 mlrd.

812
01:06:51,960 --> 01:06:55,670
Todėl, kai tik jie nepasirašytos, viskas yra tobula.

813
01:06:55,670 --> 01:06:59,900
Ir kad taip pat problema, kai rašote už kilpos,

814
01:06:59,900 --> 01:07:03,940
Ir iš tikrųjų, tai tikriausiai ji automatiškai.

815
01:07:09,130 --> 01:07:12,330
Tai tikrai bus tik klykauti ne jums.

816
01:07:12,330 --> 01:07:21,610
Taigi, jei šis skaičius yra per didelis, kad būti tik sveikasis skaičius, bet ji tiktų sveikasis skaičius be ženklo,

817
01:07:21,610 --> 01:07:24,970
klykauti jus, todėl tai, kodėl jūs niekada paleisti į šį klausimą.

818
01:07:29,150 --> 01:07:34,820
Galite matyti, kad indeksas niekada bus neigiamas,

819
01:07:34,820 --> 01:07:39,220
ir todėl, kai jūs iteravimu per masyvo,

820
01:07:39,220 --> 01:07:43,970
jūs galite beveik visada pasakyti, unsigned int i, bet jūs tikrai turite.

821
01:07:43,970 --> 01:07:47,110
Viskas vyksta gana daug dirbti lygiai taip pat.

822
01:07:48,740 --> 01:07:50,090
Gerai. [Šnabžda] Kiek dabar laiko?

823
01:07:50,090 --> 01:07:54,020
Paskutinis dalykas, aš norėjau parodyti, ir aš tiesiog padaryk tai tikrai greitai.

824
01:07:54,020 --> 01:08:03,190
Jūs žinote, kaip mes # define, kad mes galėtume # define MAX kaip 5 ar kažką?

825
01:08:03,190 --> 01:08:05,940
Tegul ne padaryti MAKS. # Define įpareigota kaip 200. Štai ką mes padarėme prieš.

826
01:08:05,940 --> 01:08:10,380
Kuris apibrėžia konstanta, kuri yra tik ketina būti nukopijuotas ir įklijuotas

827
01:08:10,380 --> 01:08:13,010
kur mes atsitikti rašyti LAIKYTIS.

828
01:08:13,010 --> 01:08:18,189
>> Taigi, mes galime iš tikrųjų # apibrėžia.

829
01:08:18,189 --> 01:08:21,170
# Mes galime nustatyti funkcijas.

830
01:08:21,170 --> 01:08:23,410
Jie tikrai ne funkcijas, bet mes jiems skambinti funkcijos.

831
01:08:23,410 --> 01:08:36,000
Pavyzdys galėtų būti kažkas panašaus max (x, y) yra apibrėžiama kaip (x <y y: x). Gerai.

832
01:08:36,000 --> 01:08:40,660
Taigi, jūs turėtumėte priprasti prie trejopo operatoriaus sintaksė,

833
01:08:40,660 --> 01:08:49,029
bet yra x mažiau nei y? Grįžti y, else return x.

834
01:08:49,029 --> 01:08:54,390
Todėl jūs galite pamatyti, jūs galite padaryti šį atskirą funkciją,

835
01:08:54,390 --> 01:09:01,399
ir funkcija gali būti, pavyzdžiui bool MAX trunka 2 argumentus, tai grąžinti.

836
01:09:01,399 --> 01:09:08,340
Tai yra vienas iš labiausiai paplitusių, matau vyksta taip. Mes vadiname juos makrokomandas.

837
01:09:08,340 --> 01:09:11,790
Tai yra makrokomanda.

838
01:09:11,790 --> 01:09:15,859
Tai tik dėl to sintaksė.

839
01:09:15,859 --> 01:09:18,740
Jūs galite rašyti makrokomandą daryti ką nori.

840
01:09:18,740 --> 01:09:22,649
Jūs dažnai pamatyti makrokomandas derinimo printfs ir kita.

841
01:09:22,649 --> 01:09:29,410
Todėl printf tipo, yra specialios konstantos C, kaip pabrėžiama LINE pabrėžti,

842
01:09:29,410 --> 01:09:31,710
2 pabrėžia LINE pabrėžti,

843
01:09:31,710 --> 01:09:37,550
ir ten taip pat manau, kad 2 pabrėžia FUNC. Kad gali būti. Kažkas panašaus.

844
01:09:37,550 --> 01:09:40,880
Tie dalykai bus pakeistas su funkcijos pavadinimu

845
01:09:40,880 --> 01:09:42,930
arba linijos, kad jūs.

846
01:09:42,930 --> 01:09:48,630
Dažnai, galite parašyti, kad žemyn čia galėčiau tada tiesiog parašyti Derinimo printfs

847
01:09:48,630 --> 01:09:54,260
Derinti ir ji bus atspausdinti eilutės numerį ir funkcijas, kad man atsitiktų būti

848
01:09:54,260 --> 01:09:57,020
kad ji susidūrė su pareiškimą, kad DEBUG.

849
01:09:57,020 --> 01:09:59,550
Ir jūs taip pat gali spausdinti kitus dalykus.

850
01:09:59,550 --> 01:10:05,990
Taigi vienas dalykas, kurį turėtų atkreipti dėmesį, jei aš atsitikti, kad # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
kaip kažką panašaus į 2 * y ir 2 * x.

852
01:10:11,380 --> 01:10:14,310
Taigi, dėl bet kokios priežasties, jums atsitikti, kad daug.

853
01:10:14,310 --> 01:10:16,650
Todėl įsitikinkite, kad makro.

854
01:10:16,650 --> 01:10:18,680
Tai iš tiesų sulaužyta.

855
01:10:18,680 --> 01:10:23,050
Aš vadinčiau jį daro kažką panašaus DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Taigi, ką turėtų būti grąžintas?

857
01:10:28,840 --> 01:10:30,580
[Studentas] 12.

858
01:10:30,580 --> 01:10:34,800
Taip, 12 turėtų būti grąžintas, ir 12 yra grąžinamas.

859
01:10:34,800 --> 01:10:43,350
3 yra pakeičiamas x, 6 yra pakeičiamas y, ir mes grįžti 2 * 6, kuris yra 12.

860
01:10:43,350 --> 01:10:47,710
Dabar, ką apie tai? Ką turėtų būti grąžintas?

861
01:10:47,710 --> 01:10:50,330
[Studentas] 14. >> Idealiu atveju, 14.

862
01:10:50,330 --> 01:10:55,290
Problema ta, kad, kaip maišos apibrėžia darbą, prisiminti tai pažodinis kopijuoti ir įklijuoti

863
01:10:55,290 --> 01:11:00,160
beveik viską, todėl tai, ką tai bus aiškinama kaip

864
01:11:00,160 --> 01:11:11,270
yra 3 kartus mažesni nei 1 plius 6, 2 kartus 1 plius 6, 2 kartus 3.

865
01:11:11,270 --> 01:11:19,780
>> Taigi dėl šios priežasties jūs beveik visada wrap viską skliausteliuose.

866
01:11:22,180 --> 01:11:25,050
Bet koks kintamasis, kurį beveik visada wrap skliausteliuose.

867
01:11:25,050 --> 01:11:29,570
Yra atvejų, kur jūs neturite, kaip aš žinau, kad nereikia daryti, kad čia

868
01:11:29,570 --> 01:11:32,110
nes mažiau, nei tai yra beveik visada tik ketina dirbti,

869
01:11:32,110 --> 01:11:34,330
nors tai gali net būti tiesa.

870
01:11:34,330 --> 01:11:41,870
Jei yra kažkas juokinga kaip DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
tada, kad ketina gauti pakeisti 3 kartus mažesni nei 1 lygus, lygus 2,

872
01:11:49,760 --> 01:11:53,460
ir taip, tada tai ketinate daryti 3 kartus mažesni nei 1, kad lygios 2,

873
01:11:53,460 --> 01:11:55,620
kuris yra ne tai, ką norime.

874
01:11:55,620 --> 01:12:00,730
Taigi, siekiant išvengti bet kokių operatorių pirmenybe problemas,

875
01:12:00,730 --> 01:12:02,870
visada wrap skliausteliuose.

876
01:12:03,290 --> 01:12:07,700
Gerai. Ir štai, 5:30.

877
01:12:08,140 --> 01:12:12,470
Jei turite klausimų dėl pset, praneškite mums.

878
01:12:12,470 --> 01:12:18,010
Jis turėtų būti įdomus, ir hakeris leidimas taip pat yra daug realesnis

879
01:12:18,010 --> 01:12:22,980
nei hacker leidimas pernai, todėl tikimės, kad iš jūsų daug išbandyti jį.

880
01:12:22,980 --> 01:12:26,460
Pernai buvo labai didele.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]