1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Iedaļas 3 - ērtāk]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Hārvarda]

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

4
00:00:07,310 --> 00:00:12,700
>> Tātad pirmais jautājums ir dīvaini formulēts.

5
00:00:12,700 --> 00:00:17,480
Gdb ļauj "atkļūdot" programmu, bet, precīzāk, ko tas ļauj jums darīt?

6
00:00:17,480 --> 00:00:22,590
Es atbildētu, ka viens, un es nezinu, kas ir tieši paredzēts,

7
00:00:22,590 --> 00:00:27,910
tāpēc es esmu guessing tas ir kaut kas pa to līniju ļauj jums soli pa solim

8
00:00:27,910 --> 00:00:31,540
staigāt pa programmu, mijiedarboties ar to, pārmaiņu rādītāju, darīt visas šīs lietas -

9
00:00:31,540 --> 00:00:34,270
Pamatā pilnībā kontrolēt programmas izpildes

10
00:00:34,270 --> 00:00:38,410
un pārbaudīt kādu konkrētu daļu no programmas izpildei.

11
00:00:38,410 --> 00:00:43,030
Tāpēc šīs īpašības ļauj atkļūdot lietas.

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

13
00:00:44,830 --> 00:00:50,520
Kāpēc binārā meklēšana prasa, masīvs ir sakārtoti?

14
00:00:50,520 --> 00:00:53,360
Kas grib, lai atbildētu, ka?

15
00:00:56,120 --> 00:01:00,070
[Students] Jo tas nedarbojas, ja tas nav sakārtots. >> Jā. [Smiekli]

16
00:01:00,070 --> 00:01:04,910
Ja tas nav sakārtots, tad tas ir iespējams to sadalīt uz pusēm

17
00:01:04,910 --> 00:01:07,850
un zinu, ka viss pa kreisi ir mazāk un viss labi

18
00:01:07,850 --> 00:01:10,490
ir lielāks par vidējo vērtību.

19
00:01:10,490 --> 00:01:12,790
Tātad tas ir jābūt sakārtoti.

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

21
00:01:14,170 --> 00:01:17,570
Kāpēc ir burbulis šķirot O n kvadrātā?

22
00:01:17,570 --> 00:01:23,230
Vai kāds vispirms vēlas dot ļoti ātri augsta līmeņa pārskatu par to, ko burbulis kārtošanas ir?

23
00:01:25,950 --> 00:01:33,020
[Students] Jūs būtībā iet cauri katram elementam un jūs pārbaudīt dažus pirmos elementus.

24
00:01:33,020 --> 00:01:37,150
Ja viņi no tā, kur jūs mijmaiņas tiem, tad jūs pārbaudīt tuvāko elementus un tā tālāk.

25
00:01:37,150 --> 00:01:40,770
Kad jūs sasniedzat beigām, tad jūs zināt, ka lielākā daļa ir novietots beigās,

26
00:01:40,770 --> 00:01:42,750
lai jūs ignorēt, ka viens, tad jūs turēt uz iet cauri,

27
00:01:42,750 --> 00:01:48,490
un katru reizi, jums ir jāpārbauda vienu mazāk elementu, kamēr jūs veikt nekādas izmaiņas. >> Jā.

28
00:01:48,490 --> 00:01:58,470
To sauc burbuļa kārtošanas, jo, ja jūs uzsist masīvs uz sāniem, lai tas ir uz augšu un uz leju, vertikālās,

29
00:01:58,470 --> 00:02:03,100
tad lielās vērtības būs izlietne uz grunts un mazās vērtības burbulis augšu uz augšu.

30
00:02:03,100 --> 00:02:05,210
Tas ir, kā tā ieguva savu nosaukumu.

31
00:02:05,210 --> 00:02:08,220
Un jā, jūs vienkārši iet cauri.

32
00:02:08,220 --> 00:02:11,190
Jūs turpināt iet caur masīvs, pārnešana lielāku vērtību

33
00:02:11,190 --> 00:02:14,040
lai iegūtu lielāko vērtības uz leju.

34
00:02:14,040 --> 00:02:17,500
>> Kāpēc tas ir O n kvadrātā?

35
00:02:18,690 --> 00:02:24,620
Pirmkārt, vai kāds grib pateikt, kāpēc tas ir O n kvadrātā?

36
00:02:24,620 --> 00:02:28,760
[Students] Jo katrā reizē tā iet n reizes.

37
00:02:28,760 --> 00:02:32,100
Jūs varat būt pārliecināts, ka jūs esat pieņemts Lielākais elements visu ceļu uz leju,

38
00:02:32,100 --> 00:02:35,230
tad jums ir atkārtot, ka tik daudzi elementi. >> Jā.

39
00:02:35,230 --> 00:02:41,800
Tāpēc paturiet prātā to, ko Big O nozīmē un ko lielie Omega līdzekļiem.

40
00:02:41,800 --> 00:02:50,560
Lielais O ir kā augšējā robeža, cik lēni tas var kursēt.

41
00:02:50,560 --> 00:02:58,990
Tātad, sakot, ka tas ir O n brusas, tas nav O n vai arī tas varētu darboties

42
00:02:58,990 --> 00:03:02,640
lineārā laika, bet tas ir O no n kubā

43
00:03:02,640 --> 00:03:06,390
jo tā robežojas ar O n kubā.

44
00:03:06,390 --> 00:03:12,300
Ja tas robežojas ar O no n brusas, tad tas robežojas arī ar n kubā.

45
00:03:12,300 --> 00:03:20,280
Tātad tas ir n kvadrātā, un absolūtā sliktākajā gadījumā tā nevar darīt labāk nekā n brusas,

46
00:03:20,280 --> 00:03:22,830
kas ir iemesls, kāpēc tas ir O no n rūtiņām.

47
00:03:22,830 --> 00:03:31,200
Tātad, lai redzētu nedaudz math, kā tā nāk, lai ar n rūtiņām,

48
00:03:31,200 --> 00:03:40,530
ja mums ir piecas lietas mūsu sarakstā, pirmo reizi cik mijmaiņa mēs varētu potenciāli nepieciešams veikt

49
00:03:40,530 --> 00:03:47,170
Lai iegūtu šo? Pieņemsim tiešām tikai -

50
00:03:47,170 --> 00:03:52,040
Cik daudz mijmaiņas darījumus mums nāksies darīt pirmajā braucienā no burbuļa kārtot caur masīvu?

51
00:03:52,040 --> 00:03:53,540
[Students] n - 1. >> Jā.

52
00:03:53,540 --> 00:03:58,340
>> Ja ir 5 elementi, mēs spēsim nepieciešams veikt n - 1.

53
00:03:58,340 --> 00:04:01,100
Tad uz otru, cik daudz mijmaiņas darījumus mums nāksies darīt?

54
00:04:01,100 --> 00:04:03,440
[Students] n - 2. >> Jā.

55
00:04:03,440 --> 00:04:11,640
Un trešais būs n - 3, un tad ērtības labad es rakstīšu pēdējo divu

56
00:04:11,640 --> 00:04:15,270
kā tad mēs spēsim nepieciešams veikt 2 mijmaiņas un 1 Apmainīt.

57
00:04:15,270 --> 00:04:19,899
Es domāju, pēdējais var vai nevar faktiski nepieciešams notikt.

58
00:04:19,899 --> 00:04:22,820
Vai tas swap? Es nezinu.

59
00:04:22,820 --> 00:04:26,490
Tātad šie ir kopējie apjomi mijmaiņas vai vismaz salīdzinājumi jums ir veikt.

60
00:04:26,490 --> 00:04:29,910
Pat ja jums nav swap, jums joprojām ir nepieciešams, lai salīdzinātu vērtības.

61
00:04:29,910 --> 00:04:33,910
Tātad tur ir n - 1 salīdzinājumi pirmajā braucienā caur masīvs.

62
00:04:33,910 --> 00:04:42,050
Ja jūs pārkārtot šīs lietas, pieņemsim faktiski padara sešas lietas tāpēc lietas kaudze pat labi,

63
00:04:42,050 --> 00:04:44,790
un tad es darīšu 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Tik vienkārši pārkārtojot šīs summas, mēs gribam redzēt, cik daudz salīdzinājumus mēs

65
00:04:49,910 --> 00:04:52,700
visā algoritmu.

66
00:04:52,700 --> 00:04:56,550
Tātad, ja mēs panāktu šie puiši šeit lejā,

67
00:04:56,550 --> 00:05:07,470
tad mēs esam vēl tikai summējot tomēr daudz salīdzinājumus tur bija.

68
00:05:07,470 --> 00:05:13,280
Bet, ja mēs Rezumējot šos un mēs apkopot šos un mēs Rezumējot šos,

69
00:05:13,280 --> 00:05:18,130
tas joprojām pati problēma. Mēs tikko Apkopojot šīs konkrētās grupas.

70
00:05:18,130 --> 00:05:22,400
>> Tāpēc tagad mēs esam summējot 3 N s. Tas nav tikai 3 N s.

71
00:05:22,400 --> 00:05:27,650
Tas vienmēr būs n / 2 n s.

72
00:05:27,650 --> 00:05:29,430
Tātad šeit mēs gadās būt 6.

73
00:05:29,430 --> 00:05:34,830
Ja mums bija 10 lietas, tad mēs varētu darīt šo grupējumu par 5 dažādiem pāriem lietas

74
00:05:34,830 --> 00:05:37,180
un galu galā ar n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Tātad jūs vienmēr gatavojas saņemt N / 2 n s, un tāpēc šis mēs pierakstītu to, lai n kvadrātā / 2.

76
00:05:45,840 --> 00:05:48,890
Un tā pat ja tas faktors ir puse, kas notiek, lai nāk

77
00:05:48,890 --> 00:05:54,190
jo fakts, ka ar katru atkārtojuma pa masīva mēs salīdzinām 1 mazāk

78
00:05:54,190 --> 00:05:58,040
Tātad tas, kā mēs pa 2, bet tas joprojām ir n rūtiņām.

79
00:05:58,040 --> 00:06:01,650
Mums nav rūp konstantu faktoru pusi.

80
00:06:01,650 --> 00:06:07,760
Tātad lielo O sīkumi daudz, piemēram, tas balstās uz tikko veida darot šāda veida math,

81
00:06:07,760 --> 00:06:12,260
darot aritmētiskās summas un ģeometriskā sīkumi,

82
00:06:12,260 --> 00:06:17,750
bet lielākā daļa no tiem šajā laikā ir diezgan vienkārši.

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

84
00:06:19,290 --> 00:06:24,430
Kāpēc ir ievietošanas šķirot Omega n? Kāda omega nozīmē?

85
00:06:24,430 --> 00:06:27,730
[Divi studenti runā uzreiz - nesaprotams] >> jā.

86
00:06:27,730 --> 00:06:30,630
Omega jūs varat iedomāties, kā zemākā robeža.

87
00:06:30,630 --> 00:06:36,550
>> Tātad nav svarīgi, cik efektīvs ir Jūsu ievietošana kārtošanas algoritms,

88
00:06:36,550 --> 00:06:41,810
neatkarīgi no saraksta, kas ir pagājis, kas, tas vienmēr ir jāsalīdzina vismaz n lietas

89
00:06:41,810 --> 00:06:44,620
vai tas ir atkārtot vairāk, n lietām.

90
00:06:44,620 --> 00:06:47,280
Kāpēc tā?

91
00:06:47,280 --> 00:06:51,190
[Students] Jo, ja saraksts ir jau sakārtots, tad caur pirmā atkārtojuma

92
00:06:51,190 --> 00:06:54,080
Jūs varat tikai garantēt, ka pirmais elements ir mazāk,

93
00:06:54,080 --> 00:06:56,490
un otrajā atkārtojuma var tikai garantēt pirmās divas

94
00:06:56,490 --> 00:07:00,010
jo jūs nezināt, ka saraksta pārējais ir sakārtots. >> Jā.

95
00:07:00,010 --> 00:07:08,910
Ja jūs iet pilnīgi sakārtoti sarakstā, vismaz jums ir jāiet pa visi elementi

96
00:07:08,910 --> 00:07:12,180
lai redzētu, ka nekas ir jāpārceļ apkārt.

97
00:07:12,180 --> 00:07:14,720
Tāpēc iet pa sarakstu un saka Ak, tas jau ir sakārtoti,

98
00:07:14,720 --> 00:07:18,240
tas ir neiespējami, lai jūs zināt, tas ir sakārtoti līdz pārbaudīt katru elementu

99
00:07:18,240 --> 00:07:20,660
redzēt, ka tie ir sakārtoti secībā.

100
00:07:20,660 --> 00:07:25,290
Tātad zemākā ievietošanas šķirot ir Omega no n.

101
00:07:25,290 --> 00:07:28,210
Kas sliktākajā gadījumā darbības laiks sapludināšanas šķirot,

102
00:07:28,210 --> 00:07:31,390
sliktākajā gadījumā ir Big O atkal?

103
00:07:31,390 --> 00:07:37,660
Tātad sliktākajā gadījumā, kā tas sapludināšanas kārtošanas palaist?

104
00:07:42,170 --> 00:07:43,690
[Students] N log n. >> Jā.

105
00:07:43,690 --> 00:07:49,990
Ātrākais vispārējie šķirošanas algoritmi ir n log n. Jūs nevarat darīt labāk.

106
00:07:51,930 --> 00:07:55,130
>> Ir speciāli gadījumi, un, ja mums ir laiks šodien - bet mēs, iespējams won't -

107
00:07:55,130 --> 00:07:59,330
mēs varētu redzēt vienu, kas dara labāk nekā n log n.

108
00:07:59,330 --> 00:08:04,050
Bet vispārējā gadījumā, jūs nevarat darīt labāk nekā n log n.

109
00:08:04,050 --> 00:08:09,680
Un apvienot kārtot notiek, ir viens no jums būtu jāzina par šo kursu, kas ir n log n.

110
00:08:09,680 --> 00:08:13,260
Un tā mēs tiešām īstenos, ka šodien.

111
00:08:13,260 --> 00:08:18,070
Un visbeidzot, ne vairāk kā trīs teikumus, kā tas atlases kārtošanas darbu?

112
00:08:18,070 --> 00:08:20,370
Vai kāds vēlas atbildēt, un es ņemšu rēķināties jūsu teikumus

113
00:08:20,370 --> 00:08:22,390
jo, ja jums iet pār 3 -

114
00:08:25,530 --> 00:08:28,330
Vai kāds atceras atlases šķirot?

115
00:08:31,280 --> 00:08:37,809
Izvēle kārtošanas parasti ir diezgan viegli atcerēties tikai no nosaukuma.

116
00:08:37,809 --> 00:08:45,350
Jūs vienkārši atkārtot pa masīvs, atrast neatkarīgi lielākā vērtība ir vai mazākā -

117
00:08:45,350 --> 00:08:47,290
kādā secībā jūs šķirošana collas

118
00:08:47,290 --> 00:08:50,750
Tāpēc pieņemsim, ka mēs šķirošanas no vismazākās līdz vislielākais.

119
00:08:50,750 --> 00:08:55,250
Tu atkārtot pa masīvu, meklē kādu minimālais elements ir,

120
00:08:55,250 --> 00:08:59,750
izvēlieties to, un tad tikai swap to kāds ir pirmajā vietā.

121
00:08:59,750 --> 00:09:04,090
Un tad uz otro pārlidojumiem pāri masīvs, meklēt minimālo elementu atkal,

122
00:09:04,090 --> 00:09:07,490
izvēlieties to, un pēc tam mijmaiņas to ar to, kas uz otro pozīciju.

123
00:09:07,490 --> 00:09:10,650
Tātad mēs vienkārši picking un izvēloties minimālās vērtības

124
00:09:10,650 --> 00:09:16,050
un ievietojot tos priekšā masīva līdz tas ir sakārtots.

125
00:09:19,210 --> 00:09:21,560
Jautājumi par šo?

126
00:09:21,560 --> 00:09:25,710
>> Tie neizbēgami parādās veidlapas jums ir jāaizpilda, ja jūs iesniedzot PSET.

127
00:09:29,010 --> 00:09:32,360
Tie ir būtībā atbildes uz tiem.

128
00:09:32,360 --> 00:09:34,230
Labi, tāpēc tagad kodēšanas problēmas.

129
00:09:34,230 --> 00:09:40,140
Es jau izsūtīti pa e-pastu - Vai kāds nevar saņemt šo e-pastu? Labi.

130
00:09:40,140 --> 00:09:46,630
Es jau izsūtīti pa e-pastu telpu ka mēs ejam, lai būtu, izmantojot,

131
00:09:46,630 --> 00:09:52,120
un ja jūs noklikšķiniet uz manu vārdu - tāpēc es domāju, ka es esmu būs apakšā

132
00:09:52,120 --> 00:09:57,170
jo atpakaļsaderību r - bet, ja jūs noklikšķiniet uz manu vārdu jūs redzēt 2 pārskatīšanu.

133
00:09:57,170 --> 00:10:02,650
Pārskatīšana 1 būs es jau kopēt un ielīmēt kodu Spaces

134
00:10:02,650 --> 00:10:06,900
par meklēšanas lieta jums nāksies īstenot.

135
00:10:06,900 --> 00:10:10,540
Un pārskatīšana 2 būs kārtošanas lieta, ka mēs īstenot pēc tam.

136
00:10:10,540 --> 00:10:15,770
Tātad jūs varat noklikšķināt uz manu pārskatīšana 1 un darbu no turienes.

137
00:10:17,350 --> 00:10:22,060
Un tagad mēs vēlamies īstenot bināro meklēšanu.

138
00:10:22,060 --> 00:10:26,470
>> Vai kāds vēlas tikai dod pseudocode augsta līmeņa skaidrojums

139
00:10:26,470 --> 00:10:31,440
par to, ko mēs esam nāksies darīt meklēšanai? Yeah.

140
00:10:31,440 --> 00:10:36,170
[Students] Jūs vienkārši ņemt vidū masīva un redzēt, ja tas, ko jūs meklējat

141
00:10:36,170 --> 00:10:38,650
ir mazāks nekā vai vairāk.

142
00:10:38,650 --> 00:10:41,080
Un, ja tas ir mazāk, jums iet uz pusi, kas ir mazāk,

143
00:10:41,080 --> 00:10:44,750
un, ja tas ir vairāk, jums iet uz pusi, kas ir vairāk, un jūs atkārtot, ka līdz brīdim, kad tikai iegūt viena lieta.

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

145
00:10:46,570 --> 00:10:51,320
Ievērojiet, ka mūsu numuri masīvs jau ir sakārtoti,

146
00:10:51,320 --> 00:10:57,190
un tik tas nozīmē, ka mēs varam izmantot, un mēs varētu vispirms pārbaudīt,

147
00:10:57,190 --> 00:11:00,390
labi, es esmu meklē numuru 50.

148
00:11:00,390 --> 00:11:03,720
Lai es varētu iet uz vidu.

149
00:11:03,720 --> 00:11:07,380
Vidū ir grūti definēt, kad tas ir vēl vairākas lietas,

150
00:11:07,380 --> 00:11:10,820
bet pieņemsim tikai teikt, ka mēs vienmēr saīsināt uz vidu.

151
00:11:10,820 --> 00:11:14,420
Tātad šeit mums ir 8 lietas, tāpēc vidējie būtu 16.

152
00:11:14,420 --> 00:11:17,330
Es meklēju 50, tāpēc 50 ir lielāks par 16.

153
00:11:17,330 --> 00:11:21,310
Tāpēc tagad es varētu būtībā ārstēt manu masīvs kā šiem elementiem.

154
00:11:21,310 --> 00:11:23,450
Es varu mest prom visu no 16 pāri.

155
00:11:23,450 --> 00:11:27,440
Tagad mans masīvs ir tikai šie 4 elementi, un es atkārtoju.

156
00:11:27,440 --> 00:11:31,910
Tātad, tad es gribu, lai atrastu vidū atkal, kas būs 42.

157
00:11:31,910 --> 00:11:34,730
42 ir mazāk nekā 50, lai es varētu mest prom šos divus elementus.

158
00:11:34,730 --> 00:11:36,890
Šī ir mana atlikusī masīvs.

159
00:11:36,890 --> 00:11:38,430
Es esmu gatavojas atrast vidū atkal.

160
00:11:38,430 --> 00:11:42,100
Es domāju 50 tika slikts piemērs, jo man vienmēr bija throwing prom lietas pa kreisi,

161
00:11:42,100 --> 00:11:48,280
bet gan pašu pasākumu, ja es meklēju kaut ko

162
00:11:48,280 --> 00:11:52,100
un tas ir mazāk nekā elements es esmu šobrīd meklē,

163
00:11:52,100 --> 00:11:55,080
tad es esmu gatavojas mest prom visu uz labo pusi.

164
00:11:55,080 --> 00:11:58,150
Tāpēc tagad mums ir jāīsteno kas.

165
00:11:58,150 --> 00:12:02,310
Ievērojiet, ka mums ir nepieciešams, lai iet lieluma.

166
00:12:02,310 --> 00:12:06,730
Mēs varam arī nav nepieciešams grūti kodu izmēru.

167
00:12:06,730 --> 00:12:11,640
Tātad, ja mēs atbrīvotos no ka # define -

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

169
00:12:21,430 --> 00:12:27,180
Kā es varu labi saprast, ko no numuriem masīva lielums šobrīd ir?

170
00:12:27,180 --> 00:12:30,950
>> Cik elementi ir to skaits masīvā?

171
00:12:30,950 --> 00:12:33,630
[Studentu] Cipari, kronšteini,. Garums?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Tas neeksistē C.

173
00:12:36,600 --> 00:12:38,580
Vajag. Garums.

174
00:12:38,580 --> 00:12:42,010
Masīvi nav īpašības, tāpēc nav garums īpašums masīvi

175
00:12:42,010 --> 00:12:45,650
kas būs tikai jums tomēr ilgi tas notiek, ir.

176
00:12:48,180 --> 00:12:51,620
[Students] Skat, cik daudz atmiņas tā ir, un izdalot ar to, cik daudz - >> Jā.

177
00:12:51,620 --> 00:12:55,810
Tātad, kā mēs varam redzēt, cik daudz atmiņas tā ir? >> [Students] sizeof. >> Jā, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof ir operators, kas notiek, lai atgrieztos lielumu numuriem masīva.

179
00:13:01,680 --> 00:13:10,060
Un tas būs tomēr daudzi integers ir reizes izmēru veselam skaitlim

180
00:13:10,060 --> 00:13:14,050
jo tas, cik daudz atmiņas tas tiešām sākšanu.

181
00:13:14,050 --> 00:13:17,630
Tātad, ja es gribu vairākas lietas masīvā,

182
00:13:17,630 --> 00:13:20,560
tad es esmu gatavojas vēlas dalīt ar izmēru veselam skaitlim.

183
00:13:22,820 --> 00:13:26,010
Labi. Lai ļauj man iet lieluma šeit.

184
00:13:26,010 --> 00:13:29,430
Kāpēc man ir nepieciešams, lai iet izmēru vispār?

185
00:13:29,430 --> 00:13:38,570
Kāpēc es nevaru vienkārši darīt šeit int lielums = sizeof (Haystack) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Kāpēc tas nedarbojas?

187
00:13:41,490 --> 00:13:44,470
[Students] Tas nav globālo mainīgo.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack pastāv, un mēs esam iet skaita kā siena kaudzē,

189
00:13:51,540 --> 00:13:54,700
un tas ir sava veida foreshadowing kas ir nākt. Yeah.

190
00:13:54,700 --> 00:14:00,170
[Students] Haystack ir tikai norāde uz to, lai tā būtu atgriešanās cik liels atsauce.

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

192
00:14:02,150 --> 00:14:09,000
Es šaubos lekciju ka jūs esat redzējuši kaudzīti vēl īsti, vai ne?

193
00:14:09,000 --> 00:14:11,270
Mēs esam tikai runājuši par to.

194
00:14:11,270 --> 00:14:16,090
Tāpēc kaudze ir, ja visas jūsu mainīgo tiks uzglabāti.

195
00:14:16,090 --> 00:14:19,960
>> Jebkurš atmiņu, kas ir piešķirti vietējās mainīgie notiek kaudze,

196
00:14:19,960 --> 00:14:24,790
un katra funkcija izpaužas sava vieta uz skursteņa, savs kaudze rāmis ir tas, ko tā sauc.

197
00:14:24,790 --> 00:14:31,590
Tātad galvenais ir tās kaudze rāmi, un iekšpusē tā gatavojas pastāvēt šo numurus masīvs,

198
00:14:31,590 --> 00:14:34,270
un tas būs no izmēra sizeof (numuri).

199
00:14:34,270 --> 00:14:38,180
Tas notiek, lai būtu izmēra numuru dalot pēc lieluma elementiem,

200
00:14:38,180 --> 00:14:42,010
bet ka visi mājo Main žetonu rāmja.

201
00:14:42,010 --> 00:14:45,190
Kad mēs saucam meklēšanu, meklēšanas izpaužas sava steka rāmi,

202
00:14:45,190 --> 00:14:48,840
savu telpu, lai uzglabātu visus vietējos mainīgo.

203
00:14:48,840 --> 00:14:56,420
Bet šie argumenti - tā Haystack nav kopiju šo visam blokam.

204
00:14:56,420 --> 00:15:00,990
Mums nav caurlaide visam blokam, kā iekopēt meklēšanu.

205
00:15:00,990 --> 00:15:04,030
Tā vienkārši iet atsauci uz šo masīvu.

206
00:15:04,030 --> 00:15:11,470
Tātad meklēšana var piekļūt šiem numuriem, izmantojot šo atsauci.

207
00:15:11,470 --> 00:15:17,100
Tas vēl piekļūt lietas, kas dzīvo iekšā no galvenajiem žetonu rāmi,

208
00:15:17,100 --> 00:15:22,990
bet būtībā, ja mēs virzienus, kas būtu drīz,

209
00:15:22,990 --> 00:15:24,980
tas ir tas, ko norādes ir.

210
00:15:24,980 --> 00:15:29,400
Norādes ir tikai atsauces uz lietām, un jūs varat izmantot norādes, lai piekļūtu lietas

211
00:15:29,400 --> 00:15:32,030
ka ir arī citas lietas, "skurstenī rāmjiem.

212
00:15:32,030 --> 00:15:37,660
Tātad, pat ja skaitļi ir vietējā galvenais, mēs joprojām var piekļūt caur šo rādītāju.

213
00:15:37,660 --> 00:15:41,770
Bet, jo tas ir tikai rādītājs, un tas ir tikai norāde,

214
00:15:41,770 --> 00:15:45,040
sizeof (Haystack) atgrieztos lielumu atsauces pati.

215
00:15:45,040 --> 00:15:47,950
Tas neatgriežas lielumu lieta tas norāda uz.

216
00:15:47,950 --> 00:15:51,110
Tas neatgriežas faktisko lielumu numuriem.

217
00:15:51,110 --> 00:15:55,660
Un tāpēc tas nav dodas uz darbu, jo mēs gribam, lai.

218
00:15:55,660 --> 00:15:57,320
>> Jautājumi par šo?

219
00:15:57,320 --> 00:16:03,250
Norādes tiks ieguldīts ievērojami vairāk asiņains sīkāk nedēļās.

220
00:16:06,750 --> 00:16:13,740
Un tas ir iemesls, kāpēc daudzas lietas, kas jums redzēt, lielākā daļa meklēšanas lietas vai kārtot lietas,

221
00:16:13,740 --> 00:16:16,990
viņi gandrīz visi dodas uz nepieciešamību veikt faktisko lielumu masīva,

222
00:16:16,990 --> 00:16:20,440
jo C, mums nav ne jausmas, kāda no masīva izmērs ir.

223
00:16:20,440 --> 00:16:22,720
Jums ir nepieciešams, lai manuāli nodot to collas

224
00:16:22,720 --> 00:16:27,190
Un jūs nevarat manuāli caurlaide visam blokam, jo ​​jūs vienkārši iet uz atsauces

225
00:16:27,190 --> 00:16:30,390
un tā nevar iegūt lielumu no atsauces.

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

227
00:16:32,300 --> 00:16:38,160
Tāpēc tagad mēs vēlamies īstenot to, kas bija paskaidrots iepriekš.

228
00:16:38,160 --> 00:16:41,530
Jūs varat strādāt par to minūti,

229
00:16:41,530 --> 00:16:45,250
un jums nav jāuztraucas par kļūst viss perfekti 100% strādā.

230
00:16:45,250 --> 00:16:51,410
Vienkārši rakstīt pusi pseudocode, kā jūs domājat, ka tas ir darbs.

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

232
00:16:53,630 --> 00:16:56,350
Nav nepieciešams, lai būtu pilnīgi darīts ar šo ziņu.

233
00:16:56,350 --> 00:17:02,380
Bet vai kāds jūtas ērti ar to, ko viņi ir tik tālu,

234
00:17:02,380 --> 00:17:05,599
piemēram, kaut mēs varam strādāt kopā?

235
00:17:05,599 --> 00:17:09,690
Vai kāds vēlas tajā iesaistīties? Vai es nejauši pick.

236
00:17:12,680 --> 00:17:18,599
Tai nav jābūt labi ar jebkuru pasākumu, bet to mēs varam mainīt uz darba stāvoklī.

237
00:17:18,599 --> 00:17:20,720
[Students] Protams. >> Labi.

238
00:17:20,720 --> 00:17:27,220
Tātad jūs varat ietaupīt pārskatīšanu, noklikšķinot uz maz Save ikonu.

239
00:17:27,220 --> 00:17:29,950
Tu esi Ramya, labi? >> [Students] Jā. >> [Bowden] Labi.

240
00:17:29,950 --> 00:17:35,140
Tāpēc tagad es varu apskatīt savu pārskatīšanu un ikviens var uzvilkt pārskatīšanu.

241
00:17:35,140 --> 00:17:38,600
Un šeit mums ir - Labi.

242
00:17:38,600 --> 00:17:43,160
Tātad Ramya gāja ar rekursīvas šķīduma, kas ir noteikti derīgs risinājums.

243
00:17:43,160 --> 00:17:44,970
Ir divi veidi, kā jūs varat darīt šo problēmu.

244
00:17:44,970 --> 00:17:48,060
Jūs varat vai nu to iteratīvi vai rekursīvi.

245
00:17:48,060 --> 00:17:53,860
Vislielākās problēmas jums rodas, ko var izdarīt rekursīvi var izdarīt iteratīvi.

246
00:17:53,860 --> 00:17:58,510
Tāpēc šeit mēs esam darījuši to rekursīvi.

247
00:17:58,510 --> 00:18:03,730
>> Vai kāds vēlas noteikt, ko tas nozīmē, lai padarītu funkciju rekursīvo?

248
00:18:07,210 --> 00:18:08,920
[Students] Ja jums ir funkcija uzaicinājuma

249
00:18:08,920 --> 00:18:13,470
un tad zvana sevi līdz tas nāk ar patiesu un patiesa. >> Jā.

250
00:18:13,470 --> 00:18:17,680
Rekursīvas funkcijas ir tikai funkcija, kas sauc sevi.

251
00:18:17,680 --> 00:18:24,140
Ir trīs lielās lietas rekursīvas funkcijas ir jābūt.

252
00:18:24,140 --> 00:18:27,310
Pirmais ir acīmredzami, tas prasa pati.

253
00:18:27,310 --> 00:18:29,650
Otrais ir bāzes scenārijs.

254
00:18:29,650 --> 00:18:33,390
Tāpēc kādā brīdī funkcija ir pārtraukt zvana sevi,

255
00:18:33,390 --> 00:18:35,610
un tas, ko bāzes scenārijs ir.

256
00:18:35,610 --> 00:18:43,860
Tātad šeit mēs zinām, ka mums vajadzētu apstāties, mums vajadzētu atmest mūsu centienos

257
00:18:43,860 --> 00:18:48,150
kad starts vienāds gala - un mēs iet pār to, ko tas nozīmē.

258
00:18:48,150 --> 00:18:52,130
Bet beidzot, pēdējā lieta, ka ir svarīgi, lai rekursīvs funkcijas:

259
00:18:52,130 --> 00:18:59,250
funkcijas ir kaut pieeja gadījumu.

260
00:18:59,250 --> 00:19:04,140
Tāpat, ja jūs faktiski nav atjaunināšanu kaut kad jūs veicat otro rekursīvas zvanu,

261
00:19:04,140 --> 00:19:07,880
ja jūs burtiski vienkārši zvanot funkcija atkal ar tiem pašiem argumentiem

262
00:19:07,880 --> 00:19:10,130
un nav globālie mainīgie ir mainījušies vai jebko,

263
00:19:10,130 --> 00:19:14,430
jūs nekad nesasniegs pamata situāciju, jo tādā gadījumā tas ir slikti.

264
00:19:14,430 --> 00:19:17,950
Tas būs bezgalīgs rekursija un kaudze pārplūdes.

265
00:19:17,950 --> 00:19:24,330
Bet šeit mēs redzam, ka atjauninājums notiek, jo mēs atjaunināt sākt + beigas / 2,

266
00:19:24,330 --> 00:19:28,180
mēs atjaunināt beigu arguments šeit, mēs atjaunināt starta arguments šeit.

267
00:19:28,180 --> 00:19:32,860
Tātad visās rekursīvas zvaniem mēs atjaunināt kaut. Labi.

268
00:19:32,860 --> 00:19:38,110
Vai jūs vēlaties, lai staigāt mūs caur savu risinājumu? >> Protams.

269
00:19:38,110 --> 00:19:44,270
Es esmu, izmantojot SearchHelp lai katru reizi, kad es darīt šo funkciju zvanu

270
00:19:44,270 --> 00:19:47,910
Man ir par to, kur es esmu meklē masīvā sākumu un beigas

271
00:19:47,910 --> 00:19:49,380
, kur es skatos masīvs.

272
00:19:49,380 --> 00:19:55,330
>> Ik uz soļa, ja tas ir saprotams, ka tas ir vidus elements, kas ir sākums + beigas / 2,

273
00:19:55,330 --> 00:19:58,850
kas ir vienāda ar to, ko mēs meklējam?

274
00:19:58,850 --> 00:20:04,650
Un, ja tā ir, tad mēs atradām to, un es domāju, ka izpaužas nodots līdz līmeni recursion.

275
00:20:04,650 --> 00:20:12,540
Un, ja tā nav taisnība, tad mēs pārbaudām, vai šī vidus vērtība masīva ir pārāk liels,

276
00:20:12,540 --> 00:20:19,320
tādā gadījumā mēs skatāmies kreisajā pusē masīva dodoties no sākuma līdz vidējā rādītāja.

277
00:20:19,320 --> 00:20:22,710
Un citādi mēs beigu pusi.

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

279
00:20:24,740 --> 00:20:27,730
Izklausās labi.

280
00:20:27,730 --> 00:20:36,640
Labi, tāpēc pāris lietas, un patiesībā, tas ir ļoti augsta līmeņa lieta

281
00:20:36,640 --> 00:20:41,270
ka jūs nekad jāzina par šo kursu, bet tā ir taisnība.

282
00:20:41,270 --> 00:20:46,080
Rekursīvas funkcijas, jūs vienmēr dzirdēt, ka viņi slikts darījums

283
00:20:46,080 --> 00:20:51,160
jo, ja tu rekursīvi saukt sevi pārāk daudz reižu, jūs saņemsiet steka pārpildes

284
00:20:51,160 --> 00:20:54,990
jo, kā es teicu, katrs funkcija tiek ieviesta sava steka rāmi.

285
00:20:54,990 --> 00:20:59,500
Tāpēc katra no rekursīvs izsaukums tiek ieviesta sava steka rāmi.

286
00:20:59,500 --> 00:21:04,140
Tātad, ja jūs veicat 1000 rekursīvas zvanu, jūs saņemsiet 1000 kaudze rāmji,

287
00:21:04,140 --> 00:21:08,390
un ātri jūs novest pie kam pārāk daudz kaudze rāmji un lietas vienkārši salauzt.

288
00:21:08,390 --> 00:21:13,480
Tātad, tāpēc rekursīvas funkcijas ir tik sliktas.

289
00:21:13,480 --> 00:21:19,370
Bet tur ir jauka apakškopa rekursīvs funkcijas sauc astes rekursīvs funkcijas,

290
00:21:19,370 --> 00:21:26,120
un tas notiek, ir piemērs, viens, kur, ja kompilators pamana šo

291
00:21:26,120 --> 00:21:29,920
un tas būtu, es domāju - jo šķindēt ja jūs nodot to-O2 karoga

292
00:21:29,920 --> 00:21:33,250
tad tas būs, ka šis ir astes rekursīvs un darīt lietas labi.

293
00:21:33,250 --> 00:21:40,050
>> Tas atkārtoti pats kaudze rāmi atkal un atkal par katru rekursīvas zvanu.

294
00:21:40,050 --> 00:21:47,010
Un tāpēc, ka jūs, izmantojot to pašu kaudze rāmi, jums nav jāuztraucas par

295
00:21:47,010 --> 00:21:51,690
kādreiz kaudze pārpildīta, un tajā pašā laikā, kā jūs teica pirms,

296
00:21:51,690 --> 00:21:56,380
ja reizi atgriezties taisnība, tad tas ir jāatgriežas līdz visiem šiem kaudze rāmji

297
00:21:56,380 --> 00:22:01,740
un 10 aicinājumu SearchHelp ir atgriezties uz 9, ir jāatgriežas līdz 8.

298
00:22:01,740 --> 00:22:05,360
Tāpēc, ka nav nepieciešams, lai notiktu, ja funkcijas ir astes rekursīvs.

299
00:22:05,360 --> 00:22:13,740
Un tā, kas padara šo funkciju astes rekursīvs ir paziņojums, ka par kādu konkrētu aicinājumu uz searchHelp

300
00:22:13,740 --> 00:22:18,470
rekursīvs zvanu, ka tas ir padarot ir tas, ko tas atgriežas.

301
00:22:18,470 --> 00:22:25,290
Tātad pirmā uzaicinājuma uz SearchHelp, mēs vai nu uzreiz atgriezties viltus,

302
00:22:25,290 --> 00:22:29,590
nekavējoties atgriezties true, vai mēs rekursīvo zvanu uz SearchHelp

303
00:22:29,590 --> 00:22:33,810
ja tas, ko mēs esam atgriešanās ir tas, ka zvans tiek atgriežas.

304
00:22:33,810 --> 00:22:51,560
Un mēs nevarējām izdarīt, ja mēs kaut ko līdzīgu int x = SearchHelp, atgriešanās x * 2,

305
00:22:51,560 --> 00:22:55,440
tikai daži izlases maiņa.

306
00:22:55,440 --> 00:23:01,470
>> Tāpēc tagad tas rekursīvs zvanu, šis int x = SearchHelp rekursīvs zvanu,

307
00:23:01,470 --> 00:23:05,740
vairs astes rekursīvs jo tie patiešām ir atgriezties

308
00:23:05,740 --> 00:23:10,400
atpakaļ uz iepriekšējo kaudze rāmi tā, ka iepriekšējais aicinājums funkcijai

309
00:23:10,400 --> 00:23:13,040
tad var kaut ko darīt ar atgriešanās vērtību.

310
00:23:13,040 --> 00:23:22,190
Tātad tas nav astes rekursīvs, bet tas, ko mums bija pirms ir labi astes rekursīvs. Yeah.

311
00:23:22,190 --> 00:23:27,000
[Students] Ja ne otro bāzes lietu jāpārbauda vispirms

312
00:23:27,000 --> 00:23:30,640
jo varētu būt situācija, kad, kad jūs nodot to argumentu

313
00:23:30,640 --> 00:23:35,770
Jūs sākat = beigas, bet tie ir adatu vērtību.

314
00:23:35,770 --> 00:23:47,310
Jautājums tika nevar mēs uzskriet Ja gals ir adata vērtība

315
00:23:47,310 --> 00:23:52,000
vai sākt = galu, pienācīgi, start = beigas

316
00:23:52,000 --> 00:23:59,480
un jums nav faktiski jāpārbauda šo konkrēto vērtību vēl,

317
00:23:59,480 --> 00:24:03,910
tad sākt + END / 2 ir tikai būs tāda pati vērtība.

318
00:24:03,910 --> 00:24:07,890
Bet mēs jau esam atgriezušies nepatiess, un mēs nekad faktiski pārbaudīti vērtību.

319
00:24:07,890 --> 00:24:14,240
Tāpēc vismaz, pēc pirmā uzaicinājuma, ja izmērs ir 0, tad mēs vēlamies atgriezties viltus.

320
00:24:14,240 --> 00:24:17,710
Bet, ja lielums ir 1, tad sākums nav gatavojas vienādu beigām,

321
00:24:17,710 --> 00:24:19,820
un mēs vismaz pārbaudīt vienu elementu.

322
00:24:19,820 --> 00:24:26,750
Bet es domāju, ka jums ir taisnība, ka mēs varam nonākt tādā gadījumā, ja sāk + beigas / 2,

323
00:24:26,750 --> 00:24:31,190
sākums beidzas ar to, tāpat kā sākumā + gala / 2,

324
00:24:31,190 --> 00:24:35,350
bet mēs nekad patiesībā pārbaudīt šo elementu.

325
00:24:35,350 --> 00:24:44,740
>> Tātad, ja mēs vispirms pārbaudiet ir vidējā elements vērtība, mēs meklējam,

326
00:24:44,740 --> 00:24:47,110
tad mēs varam nekavējoties atgriezties taisnība.

327
00:24:47,110 --> 00:24:50,740
Cits ja viņi vienādi, tad tur nav turpinot punkts

328
00:24:50,740 --> 00:24:58,440
jo mēs esam tikai gatavojas atjaunināt uz gadījumu, kad mēs esam uz viena elementa masīvs.

329
00:24:58,440 --> 00:25:01,110
Ja tas viens elements nav viens mēs meklējam,

330
00:25:01,110 --> 00:25:03,530
tad viss ir kārtībā. Yeah.

331
00:25:03,530 --> 00:25:08,900
[Students] Lieta tāda, ka kopš lielums ir faktiski lielāks nekā skaits elementu masīvs,

332
00:25:08,900 --> 00:25:13,070
jau ir nobīde - >> Tā būs lielums -

333
00:25:13,070 --> 00:25:19,380
[Students] Saka, ja masīvs bija 0 izmēra, tad SearchHelp būs faktiski pārbaudīt siena kaudzē ir 0

334
00:25:19,380 --> 00:25:21,490
uz pirmo zvanu.

335
00:25:21,490 --> 00:25:25,300
Masīvs ir lielums 0, tāpēc 0 ir - >> Jā.

336
00:25:25,300 --> 00:25:30,750
Tur ir cita lieta, ka - tā varētu būt laba. Padomāsim.

337
00:25:30,750 --> 00:25:40,120
Tātad, ja masīvs bija 10 elementus un no kurām vidējā mēs ejam, lai pārbaudītu, indeksa 5,

338
00:25:40,120 --> 00:25:45,700
tāpēc mēs pārbaudītu 5, un pieņemsim, ka vērtība ir mazāka.

339
00:25:45,700 --> 00:25:50,720
Tāpēc mēs esam throwing visu prom no 5 vēlāk.

340
00:25:50,720 --> 00:25:54,030
Lai sāktu + beigas / 2 būs mūsu jaunā beigas,

341
00:25:54,030 --> 00:25:57,450
Tātad yeah, tas vienmēr paliks ārpus beigām masīva.

342
00:25:57,450 --> 00:26:03,570
Ja tas ir gadījumā, ja tas bija pat vai nepāra, tad mēs varētu pārbaudīt, teiksim, 4,

343
00:26:03,570 --> 00:26:05,770
bet mēs joprojām throwing prom -

344
00:26:05,770 --> 00:26:13,500
Tātad yeah, beigas vienmēr būs ārpus faktiskās beigām masīva.

345
00:26:13,500 --> 00:26:18,350
Tātad elementiem mēs esam koncentrējoties uz, beigas vienmēr būs viens pēc tam.

346
00:26:18,350 --> 00:26:24,270
Un tāpēc, ja sākums nav kādreiz vienlīdzīgu beigas, mēs esam masīvs 0 izmērs.

347
00:26:24,270 --> 00:26:35,600
>> Otra lieta, ko es domāju ir mēs atjaunināt sāk tikt sākt + beigas / 2,

348
00:26:35,600 --> 00:26:44,020
tāpēc tas ir gadījumā, ka es esmu, kam problēmas ar, kur sākt + beigas / 2

349
00:26:44,020 --> 00:26:46,820
ir elements mēs pārbaudīt.

350
00:26:46,820 --> 00:26:58,150
Teiksim, mums bija šo 10 elementu masīvu. Neatkarīgi.

351
00:26:58,150 --> 00:27:03,250
Lai sāktu + beigas / 2 būs kaut kas līdzīgs šo vienu,

352
00:27:03,250 --> 00:27:07,060
un ja tas nav vērtība, ka mēs gribam, lai atjauninātu.

353
00:27:07,060 --> 00:27:10,060
Šis skaitlis ir lielāks, tāpēc mēs vēlamies apskatīt šo pusi no masīva.

354
00:27:10,060 --> 00:27:15,910
Tātad, kā mēs atjaunināt sākums, mēs atjaunināt startu tagad šis elements.

355
00:27:15,910 --> 00:27:23,790
Bet tas joprojām var strādāt, vai vismaz, jūs varat darīt starts + beigas / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Students] Jums nav nepieciešams uzsākt + galu [dzirdams] >> Jā.

357
00:27:27,850 --> 00:27:33,240
Mēs jau esam pārbaudīts šo elementu, un zinu, tas nav viens, mēs meklējam.

358
00:27:33,240 --> 00:27:36,800
Tāpēc mums nav nepieciešams atjaunināt sākt būt šis elements.

359
00:27:36,800 --> 00:27:39,560
Mēs varam vienkārši izlaist to un atjaunināt sākt būt šo elementu.

360
00:27:39,560 --> 00:27:46,060
Un ir tur kādreiz lieta, teiksim, ka šis bija beigas,

361
00:27:46,060 --> 00:27:53,140
lai tad sāktu būtu tas, sāk + beigu / 2 būtu šis,

362
00:27:53,140 --> 00:28:00,580
sākums + END - Jā, es domāju, ka tas varētu nonākt bezgalīgā recursion.

363
00:28:00,580 --> 00:28:12,690
Teiksim tā ir tikai masīvs lielums 2 vai 1 lieluma masīvs. Es domāju, ka tas būs darbs.

364
00:28:12,690 --> 00:28:19,490
Tātad šobrīd, sākums ir tas elements, un gals ir 1 ārpus tā.

365
00:28:19,490 --> 00:28:24,110
Tā elements, ka mēs ejam, lai pārbaudītu, ir tas viens,

366
00:28:24,110 --> 00:28:29,400
un tad, kad mēs atjaunināt sākums, mēs atjaunināt sākums ir 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
kas beigsies mūs atpakaļ ar jāsāk šis elements.

368
00:28:33,160 --> 00:28:36,210
>> Tāpēc mēs esam pārbaudot to pašu elementu atkal un atkal.

369
00:28:36,210 --> 00:28:43,310
Tātad šis ir tas gadījums, kad katrs rekursīvas zvans ir reāli atjaunot kaut ko.

370
00:28:43,310 --> 00:28:48,370
Tāpēc mums jādara starts + beigu / 2 + 1, vai arī tur ir lieta

371
00:28:48,370 --> 00:28:50,710
kur mēs esam faktiski nav atjaunināšanu sākums.

372
00:28:50,710 --> 00:28:53,820
Ikvienam redzēt, ka?

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

374
00:28:56,310 --> 00:29:03,860
Vai kāds ir jautājumi par šo risinājumu vai jebkuru komentārus?

375
00:29:05,220 --> 00:29:10,280
Labi. Vai kāds ir iteratīvs risinājums, ka mēs visi varam apskatīt?

376
00:29:17,400 --> 00:29:20,940
Vai mēs visi darīt to rekursīvi?

377
00:29:20,940 --> 00:29:25,950
Vai arī es domāju, ja tu atver viņas, tad jūs varētu būt svarīgāka savu iepriekšējo.

378
00:29:25,950 --> 00:29:28,810
Vai tas automātiski saglabāt? Es neesmu pozitīvs.

379
00:29:35,090 --> 00:29:39,130
Vai kāds ir ilglaicīgs?

380
00:29:39,130 --> 00:29:42,430
Mēs varam staigāt pa to kopā, ja ne.

381
00:29:46,080 --> 00:29:48,100
Ideja būs tāds pats.

382
00:30:00,260 --> 00:30:02,830
Iteratīvs risinājumu.

383
00:30:02,830 --> 00:30:07,140
Mēs ejam, lai vēlas būtībā darīt to pašu domu

384
00:30:07,140 --> 00:30:16,530
kur mēs gribam, lai saglabātu jauno beigām masīva dziesmu un jauns sākums masīva

385
00:30:16,530 --> 00:30:18,510
un darīt vairāk un vairāk.

386
00:30:18,510 --> 00:30:22,430
Un, ja tas, ko mēs sekotu kā sākumā un beigās kādreiz krustojas,

387
00:30:22,430 --> 00:30:29,020
tad mēs neatradām, un mēs varam atgriezties viltus.

388
00:30:29,020 --> 00:30:37,540
Tātad, kā es varu darīt? Kāds ir ieteikumi vai kods, lai es varētu uzvilkt?

389
00:30:42,190 --> 00:30:47,450
[Students] Vai, kamēr cilpa. >> Jā.

390
00:30:47,450 --> 00:30:49,450
Jūs gatavojas vēlaties darīt cilpu.

391
00:30:49,450 --> 00:30:51,830
>> Vai jums ir kods, es varētu uzvilkt, vai ko tad tu gatavojas ierosināt?

392
00:30:51,830 --> 00:30:56,340
[Students] es tā domāju. >> Visas tiesības. Tas padara lietas vieglāk. Kāds bija jūsu vārds?

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

394
00:31:00,140 --> 00:31:04,190
Pārskatīšana 1. Labi.

395
00:31:04,190 --> 00:31:13,200
Zems ir tas, ko mēs saucām sākt agrāk.

396
00:31:13,200 --> 00:31:17,080
Up nav gluži tas, ko mēs saucām beidzas pirms.

397
00:31:17,080 --> 00:31:22,750
Patiesībā, beigas ir tagad ir masīva. Tas elements mums būtu jāapsver.

398
00:31:22,750 --> 00:31:26,890
Tik zemu ir 0, līdz ir lielums masīvs - 1,

399
00:31:26,890 --> 00:31:34,780
un tagad mēs esam looping, un mēs pārbaudes -

400
00:31:34,780 --> 00:31:37,340
Es domāju, jūs varat iet caur to.

401
00:31:37,340 --> 00:31:41,420
Kāds bija jūsu domāšanu caur šo? Staigāt mūs caur savu kodu.

402
00:31:41,420 --> 00:31:49,940
[Students] Protams. Paskaties siena kaudzē vērtību vidū un salīdzināt to ar adatu.

403
00:31:49,940 --> 00:31:58,520
Tātad, ja tas ir lielāks nekā jūsu adatas, tad jūs vēlaties, lai - ak, patiesībā, kas būtu atpakaļ.

404
00:31:58,520 --> 00:32:05,180
Jūs gatavojas vēlaties mest prom pareizo pusi, un tā jā, kas būtu veids.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Tātad tas būtu mazāk? Vai tas, ko jūs teicāt? >> [Students] Jā.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Labi. Mazāk.

407
00:32:10,390 --> 00:32:15,700
Tātad, ja tas, ko mēs meklējam, ir, ir mazāks nekā tas, ko mēs gribam,

408
00:32:15,700 --> 00:32:19,410
tad jā, mēs vēlamies, lai mest prom kreiso pusi,

409
00:32:19,410 --> 00:32:22,210
kas nozīmē, ka mēs atjaunināt visu mēs apsver

410
00:32:22,210 --> 00:32:26,610
pārvietojot zems, lai labi no masīva.

411
00:32:26,610 --> 00:32:30,130
Tas izskatās labi.

412
00:32:30,130 --> 00:32:34,550
Es domāju, ka tas ir tāds pats jautājums, kas mums teica par iepriekšējo,

413
00:32:34,550 --> 00:32:49,760
ja ja zems ir 0 un uz augšu ir 1, tad zema + uz augšu / 2 gatavojas izveidota, lai būtu tas pats vēlreiz.

414
00:32:49,760 --> 00:32:53,860
>> Un pat tad, ja tas nav gadījums, tas ir vēl efektīvāks vismaz

415
00:32:53,860 --> 00:32:57,630
lai tikai mest prom elementu mēs vienkārši paskatījās, ko mēs zinām, ir nepareizi.

416
00:32:57,630 --> 00:33:03,240
Tik zemu + uz augšu / 2 + 1 - >> [students] Tas būtu citā veidā.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Vai tas būtu - 1 un otrs būtu + 1.

418
00:33:05,900 --> 00:33:09,580
[Students] Un tur jābūt dubultā vienlīdzības zīmi. >> [Bowden] Jā.

419
00:33:09,580 --> 00:33:11,340
[Students] Jā.

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

421
00:33:15,910 --> 00:33:21,280
Un visbeidzot, tagad, ka mums ir šis + 1 - 1 lieta,

422
00:33:21,280 --> 00:33:31,520
tas ir - tas varētu būt - tas ir kādreiz iespējams mazs, lai galu galā ar kuru vērtība ir lielāka nekā līdz?

423
00:33:35,710 --> 00:33:40,320
Es domāju, ka vienīgais veids, kas var notikt - Vai ir iespējams? >> [Students] Es nezinu.

424
00:33:40,320 --> 00:33:45,220
Bet, ja tā kļūst noapaļots un tad kļūst mīnus ka 1 un pēc tam - >> Jā.

425
00:33:45,220 --> 00:33:47,480
[Students] Tas būtu iespējams iegūt messed up.

426
00:33:49,700 --> 00:33:53,940
Es domāju, ka tas būtu labs tikai tāpēc, ka

427
00:33:53,940 --> 00:33:58,800
lai tas galu galā zemākas tiem būtu jābūt vienādam, es domāju.

428
00:33:58,800 --> 00:34:03,070
Bet, ja tie ir vienādi, tad mēs nebūtu darīts, kamēr cilpa sākt ar

429
00:34:03,070 --> 00:34:06,670
un mēs tikai būtu atgriezušies vērtību. Tāpēc es domāju, ka mēs esam labi tagad.

430
00:34:06,670 --> 00:34:11,530
Ievērojiet, ka, lai gan šī problēma vairs rekursīvs

431
00:34:11,530 --> 00:34:17,400
paša veida ideju piemēro, ja mēs varam redzēt, kā tas tik viegli pakļauj sevi

432
00:34:17,400 --> 00:34:23,659
līdz rekursīvo risinājumu ar to, ka mēs esam tikai atjaunošanai indeksus atkal un atkal,

433
00:34:23,659 --> 00:34:29,960
mēs nesam problēma mazākas un mazākas, mēs esam koncentrējoties uz apakškopu masīva.

434
00:34:29,960 --> 00:34:40,860
[Students] Ja zems ir 0 un līdz 1, viņi abi ir 0 + 1/2, kas varētu iet uz 0,

435
00:34:40,860 --> 00:34:44,429
un tad viens būtu + 1, viens būtu - 1.

436
00:34:47,000 --> 00:34:50,870
[Students] Ja mēs pārbaudīt līdztiesību?

437
00:34:50,870 --> 00:34:55,100
Patīk, ja vidējā ir faktiski adata?

438
00:34:55,100 --> 00:34:58,590
Mēs esam ne šobrīd dara, ka? Oh!

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

440
00:35:05,340 --> 00:35:13,740
Jā. Mēs nevaram vienkārši darīt testu leju šeit, jo teiksim pirmo vidū -

441
00:35:13,740 --> 00:35:16,430
[Students] Tas tiešām patīk ne mest prom robežu.

442
00:35:16,430 --> 00:35:20,220
Tātad, ja jūs mest prom robežu, jums ir jāpārbauda vispirms, vai neatkarīgi.

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

444
00:35:23,350 --> 00:35:29,650
Tāpēc tagad mēs esam izmesti vienu mēs pašlaik paskatījās,

445
00:35:29,650 --> 00:35:33,260
kas nozīmē, ka mums tagad ir arī

446
00:35:33,260 --> 00:35:44,810
ja (Haystack [(zems + augšu) / 2] == adata), tad mēs varam atgriezties taisnība.

447
00:35:44,810 --> 00:35:52,070
Un vai man cits vai vienkārši, ja tas burtiski nozīmē to pašu

448
00:35:52,070 --> 00:35:57,110
jo tas ir atgriezušies taisnība.

449
00:35:57,110 --> 00:36:01,450
Tāpēc es nolikšu cits ja, bet tas nav svarīgi.

450
00:36:01,450 --> 00:36:10,440
>> Tātad cits ja tas, cits šo, un tas ir kopīga lieta man darīt

451
00:36:10,440 --> 00:36:14,340
kur pat ja tas ir gadījums, kad viss ir labi šeit,

452
00:36:14,340 --> 00:36:22,780
tāpat zema nekad nevar būt lielāks nekā uz augšu, tas nav vērts argumentācija par to, vai tā ir taisnība.

453
00:36:22,780 --> 00:36:28,010
Lai jūs varētu arī teikt, bet zema ir mazāks vai vienāds ar

454
00:36:28,010 --> 00:36:30,720
vai kamēr zems ir mazāks nekā

455
00:36:30,720 --> 00:36:35,300
tāpēc, ja viņi ir kādreiz vienādi vai zemu notiek iet uz augšu,

456
00:36:35,300 --> 00:36:40,130
tad mēs varam izkļūt no šīs cilpas.

457
00:36:41,410 --> 00:36:44,630
Jautājumi, bažas, komentāri?

458
00:36:47,080 --> 00:36:49,270
Labi. Tas izskatās labi.

459
00:36:49,270 --> 00:36:52,230
Tagad mēs vēlamies darīt šķirot.

460
00:36:52,230 --> 00:37:04,030
Ja mēs ejam uz manu otro pārskatīšanu, mēs redzam šos pašus skaitļus,

461
00:37:04,030 --> 00:37:07,550
bet tagad viņi vairs nav sakārtoti secībā.

462
00:37:07,550 --> 00:37:12,840
Un mēs gribam, lai īstenotu kādas izmantojot jebkuru algoritmu O n log n.

463
00:37:12,840 --> 00:37:17,240
Tātad, kas algoritms jūsuprāt mums vajadzētu ieviest šeit? >> [Students] sapludināšana kārtošanas.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Jā. Sapludināt kārtošanas ir O (n log n), tā ka tas, ko mēs gatavojamies darīt.

465
00:37:23,810 --> 00:37:26,680
Un problēma būs diezgan līdzīgi,

466
00:37:26,680 --> 00:37:31,920
kur tas viegli pakļauj sevi rekursīvo risinājumu.

467
00:37:31,920 --> 00:37:35,580
Mēs varam arī nākt klajā ar iteratīvs risinājums, ja mēs vēlamies,

468
00:37:35,580 --> 00:37:42,540
bet rekursijas būs vieglāk šeit un mums vajadzētu darīt rekursija.

469
00:37:45,120 --> 00:37:49,530
Es domāju, mēs staigāt pa sapludināšanas kārtot, pirmkārt,

470
00:37:49,530 --> 00:37:54,280
lai gan ir jauki video par sapludināšanas kārtot jau. [Smiekli]

471
00:37:54,280 --> 00:37:59,780
Tāpēc apvienot kādas tur ir - es esmu izšķērdēt tik daudz šajā dokumentā.

472
00:37:59,780 --> 00:38:02,080
Ak, tur ir tikai viens pa kreisi.

473
00:38:02,080 --> 00:38:03,630
Tik apvienot.

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

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

476
00:38:29,910 --> 00:38:33,460
Apvienot aizņem divas atsevišķas masīvus.

477
00:38:33,460 --> 00:38:36,780
Individuāli šie divi bloki ir gan sakārtoti.

478
00:38:36,780 --> 00:38:40,970
Tātad šis masīvs, 1, 3, 5, sakārtoti. Šis masīvs, 0, 2, 4, sakārtoti.

479
00:38:40,970 --> 00:38:46,710
Tagad to, ko sapludināšana vajadzētu darīt, ir apvienot tos vienā masīvā, kas pati sakārtoti.

480
00:38:46,710 --> 00:38:57,130
Tāpēc mēs vēlamies masīvs 6 izmēru, kas ir nāksies šos elementus iekšpusē no tā

481
00:38:57,130 --> 00:38:59,390
kas sakārtoti secībā.

482
00:38:59,390 --> 00:39:03,390
>> Un tā mēs varam izmantot to, ka šie divi bloki ir sakārtoti

483
00:39:03,390 --> 00:39:06,800
to darīt lineārā laika,

484
00:39:06,800 --> 00:39:13,510
lineārā laika nozīmē, ja tas masīvs ir izmērs x un tas ir izmērs y,

485
00:39:13,510 --> 00:39:20,970
tad kopējais algoritms jābūt O (x + y). Labi.

486
00:39:20,970 --> 00:39:23,150
Tātad ieteikumi.

487
00:39:23,150 --> 00:39:26,030
[Students] Vai mēs sākam no kreisās?

488
00:39:26,030 --> 00:39:30,150
Tātad jūs nodot 0 nosaka vispirms un tad 1 un tad šeit jūs esat pie 2.

489
00:39:30,150 --> 00:39:33,320
Tāpēc tas ir veids, kā jums ir cilnes, kas ir pārvietojas pa labi. >> [Bowden] Jā.

490
00:39:33,320 --> 00:39:41,070
Abiem šiem blokiem, ja mēs tikai koncentrēties uz kreisajā elementa.

491
00:39:41,070 --> 00:39:43,530
Jo abi bloki ir sakārtoti, mēs zinām, ka šie 2 elementi

492
00:39:43,530 --> 00:39:46,920
ir mazākais elementi nu masīvā.

493
00:39:46,920 --> 00:39:53,500
Tātad tas nozīmē, ka 1 no tiem 2 elementiem jābūt mazākais elements mūsu apvienotā masīvā.

494
00:39:53,500 --> 00:39:58,190
Tas tikai tā notiek, ka mazākais ir viens uz pareizā šajā laikā.

495
00:39:58,190 --> 00:40:02,580
Tātad mēs 0, ievietojiet to pa kreisi, jo 0 ir mazāks par 1,

496
00:40:02,580 --> 00:40:08,210
lai ņemtu 0, ievietojiet to mūsu pirmo pozīciju, un tad mēs atjaunināt šo

497
00:40:08,210 --> 00:40:12,070
šim koncentrēties uz pirmā elementa.

498
00:40:12,070 --> 00:40:14,570
Un tagad mēs atkārtot.

499
00:40:14,570 --> 00:40:20,670
Tātad tagad mēs salīdzinātu 2 un 1. 1 ir mazāks, tāpēc mēs ievietot 1.

500
00:40:20,670 --> 00:40:25,300
Mēs atjaunināt šo rādītāju, lai norādītu uz šo puisis.

501
00:40:25,300 --> 00:40:33,160
Tagad mēs to darīt atkal, tāpēc 2. Tas atjauninās, salīdzināt šos 2, 3.

502
00:40:33,160 --> 00:40:37,770
Šis atjauninājumus, tad 4 un 5.

503
00:40:37,770 --> 00:40:42,110
Tāpēc, ka ir sapludināšana.

504
00:40:42,110 --> 00:40:49,010
>> Tas būtu diezgan skaidrs, ka tas ir lineārs laiks, kopš mēs vienkārši iet pāri katram elementam vienu reizi.

505
00:40:49,010 --> 00:40:55,980
Un tas ir lielākais solis, lai īstenotu Merge šķirot to dara.

506
00:40:55,980 --> 00:40:59,330
Un tas nav tik grūti.

507
00:40:59,330 --> 00:41:15,020
Pāris lietas jāuztraucas par ir teiksim mēs apvienojas 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Šajā gadījumā mēs galu galā ar scenāriju, kurā šis kurš būs mazāks,

509
00:41:30,930 --> 00:41:36,160
tad mēs atjaunināt šo rādītāju, tas viens būs mazāks, atjaunināt šo,

510
00:41:36,160 --> 00:41:41,280
šis viens ir mazāks, un tagad jums ir jāatzīst

511
00:41:41,280 --> 00:41:44,220
kad esat kursēt no elementiem, lai salīdzinātu ar.

512
00:41:44,220 --> 00:41:49,400
Tā kā mums jau ir izmantojuši šo visu masīvs,

513
00:41:49,400 --> 00:41:55,190
viss šajā masīvā tagad tikai ievietots šeit.

514
00:41:55,190 --> 00:42:02,040
Tātad, ja mēs kādreiz satikt kur viens no mūsu masīvi ir pilnībā sajaucas jau,

515
00:42:02,040 --> 00:42:06,510
tad mēs tikai veikt visus elementus no citiem masīva un ievietot tos beigām masīva.

516
00:42:06,510 --> 00:42:13,630
Tātad mēs varam tikai ievietot 4, 5, 6. Labi.

517
00:42:13,630 --> 00:42:18,070
Tā ir viena lieta, lai noskatītos, kas paredzēti.

518
00:42:22,080 --> 00:42:26,120
Īstenotu minēto būtu solis 1.

519
00:42:26,120 --> 00:42:32,600
Sapludināt kārtot tad, pamatojoties uz to, tas ir 2 soļi, 2 dumjš pakāpieni.

520
00:42:38,800 --> 00:42:42,090
Pieņemsim tikai dod šo masīvu.

521
00:42:57,920 --> 00:43:05,680
Tātad apvienot kārtot solis 1 ir rekursīvi lauzt masīvs uz pusēm.

522
00:43:05,680 --> 00:43:09,350
Tāpēc sadalīt šo masīvu uz pusēm.

523
00:43:09,350 --> 00:43:22,920
Mums tagad ir 4, 15, 16, 50 un 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Un tagad mēs to darām atkal un mēs sadalīt tos uz pusēm.

525
00:43:25,800 --> 00:43:27,530
Es ņemšu tikai darīt to šajā pusē.

526
00:43:27,530 --> 00:43:34,790
Tātad 4, 15 un 16, 50.

527
00:43:34,790 --> 00:43:37,440
Mēs varētu darīt to pašu atkal šeit.

528
00:43:37,440 --> 00:43:40,340
Un tagad mēs sadalīt to uz pusēm vēlreiz.

529
00:43:40,340 --> 00:43:51,080
Un mums ir 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Tāpēc, ka ir mūsu bāzes scenārijs.

531
00:43:53,170 --> 00:44:00,540
Kad masīvi ir no 1 izmēra, tad mēs apstāties ar sadalīšanas uz pusēm.

532
00:44:00,540 --> 00:44:03,190
>> Tagad to, ko mēs darām ar šo?

533
00:44:03,190 --> 00:44:15,730
Mēs galu galā tas arī iedala 8, 23, 42, 108 un.

534
00:44:15,730 --> 00:44:24,000
Tāpēc tagad, ka mēs esam šajā brīdī, tagad soli divas sapludināšanas veida ir tikai apvienojot pārus ar sarakstiem.

535
00:44:24,000 --> 00:44:27,610
Tāpēc mēs vēlamies apvienot šos. Mēs vienkārši zvanu apvienoties.

536
00:44:27,610 --> 00:44:31,410
Mēs zinām sapludināšanas atgriezīsies šos sakārtoti secībā.

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

538
00:44:33,920 --> 00:44:41,440
Tagad mēs vēlamies apvienot šos, un kas būs atgriešanās sarakstu ar tiem, kas sakārtoti secībā,

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

540
00:44:44,160 --> 00:44:57,380
Mēs apvienot tos - es nevaru rakstīt - 8, 23 un 42, 108.

541
00:44:57,380 --> 00:45:02,890
Tāpēc mums ir sapludināto pāriem reizi.

542
00:45:02,890 --> 00:45:05,140
Tagad mēs vienkārši apvienot vēlreiz.

543
00:45:05,140 --> 00:45:10,130
Ievērojiet, ka katrs no šiem sarakstiem ir sakārtots pats par sevi,

544
00:45:10,130 --> 00:45:15,220
un tad mēs varam vienkārši apvienot šos sarakstus, lai iegūtu sarakstu ar 4 izmēra, kas ir sakārtoti

545
00:45:15,220 --> 00:45:19,990
un apvienot šīs divas sarakstus, lai iegūtu sarakstu ar 4 izmēru, kas ir sakārtots.

546
00:45:19,990 --> 00:45:25,710
Un visbeidzot, mēs varam apvienot šos divus sarakstus ar 4 izmēra, lai iegūtu vienu sarakstu 8 izmērs, kas ir sakārtots.

547
00:45:25,710 --> 00:45:34,030
Tātad, lai redzētu, ka tas kopumā ir n log n, mēs jau redzējām, ka Merge ir lineāra,

548
00:45:34,030 --> 00:45:40,390
tad, kad mums ir darīšana ar apvienošanu šiem, lai, piemēram, kopējās izmaksas sapludināšanu

549
00:45:40,390 --> 00:45:43,410
šīm divām sarakstiem ir tikai 2, jo -

550
00:45:43,410 --> 00:45:49,610
Vai labi, tas ir O n, bet n šeit ir tikai šie 2 elementi, tāpēc tas ir 2.

551
00:45:49,610 --> 00:45:52,850
Un tie 2 būs 2 un tie 2 būs 2 un tie 2 būs 2,

552
00:45:52,850 --> 00:45:58,820
tāpēc pāri visiem sapludināšanai, kas mums jādara, mēs galu galā dara n.

553
00:45:58,820 --> 00:46:03,210
Tāpat kā 2 + 2 + 2 + 2 ir 8, kas ir n,

554
00:46:03,210 --> 00:46:08,060
tāpēc apvienošanu šo komplektu izmaksas ir n.

555
00:46:08,060 --> 00:46:10,810
Un tad pats šeit.

556
00:46:10,810 --> 00:46:16,980
Mēs apvienot šos 2, tad šie 2, un atsevišķi šī sapludināšana būs četras operācijas,

557
00:46:16,980 --> 00:46:23,610
Šī apvienot būs četras operācijas, bet atkal, starp visiem šiem,

558
00:46:23,610 --> 00:46:29,030
mēs galu galā apvienojot n kopējais lietas, un tāpēc šis solis tiek n.

559
00:46:29,030 --> 00:46:33,670
Un tā katru līmeni ņem n elementiem tiek apvienotas.

560
00:46:33,670 --> 00:46:36,110
>> Un cik daudz piesārņojuma līmenis ir tur?

561
00:46:36,110 --> 00:46:40,160
Katrā līmenī, mūsu masīvs aug par 2 izmēru.

562
00:46:40,160 --> 00:46:44,590
Te mūsu bloki ir no 1 izmēra, šeit viņi ir 2 izmēru, šeit viņi 4 izmēra,

563
00:46:44,590 --> 00:46:46,470
un visbeidzot, viņi 8 lieluma.

564
00:46:46,470 --> 00:46:56,450
Tāpēc, ka tas ir divkāršojies, tur ir būs pavisam log n no šiem līmeņiem.

565
00:46:56,450 --> 00:47:02,090
Tātad ar log n līmenis, katra atsevišķā līmenis ņemot N Kopējais operācijas,

566
00:47:02,090 --> 00:47:05,720
mēs iegūstam n log n algoritms.

567
00:47:05,720 --> 00:47:07,790
Jautājumi?

568
00:47:08,940 --> 00:47:13,320
Ir cilvēki jau guvusi panākumus, kā īstenot šo?

569
00:47:13,320 --> 00:47:18,260
Vai kāds jau ir valsts, kur es varu tikai uzvilkt savu kodu?

570
00:47:20,320 --> 00:47:22,260
Es varu dot minūti.

571
00:47:24,770 --> 00:47:27,470
Tas viens būs ilgāks.

572
00:47:27,470 --> 00:47:28,730
Es ļoti ieteiktu atkārtojas -

573
00:47:28,730 --> 00:47:30,510
Jums nav jādara rekursija par sapludināšanu

574
00:47:30,510 --> 00:47:33,750
jo to darīt rekursija par sapludināšanu, jūs nāksies iziet ķekars dažādu izmēru.

575
00:47:33,750 --> 00:47:37,150
Jūs varat, bet tas ir kaitinošas.

576
00:47:37,150 --> 00:47:43,720
Bet rekursijas par kārtot pati ir diezgan viegli.

577
00:47:43,720 --> 00:47:49,190
Jūs vienkārši burtiski zvanīt šķirot kreisajā pusē, kārtot labajā pusē. Labi.

578
00:47:51,770 --> 00:47:54,860
Kāds ir kaut kas es varētu uzvilkt vēl?

579
00:47:54,860 --> 00:47:57,540
Vai arī es došu minūti.

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

581
00:47:59,900 --> 00:48:02,970
Kāds ir kaut kas, mēs varam strādāt ar?

582
00:48:05,450 --> 00:48:09,680
Vai arī mēs tikai strādāt ar šo un pēc tam paplašināt no turienes.

583
00:48:09,680 --> 00:48:14,050
>> Ikviens ir vairāk nekā tas, ka es varētu uzvilkt?

584
00:48:14,050 --> 00:48:17,770
[Students] Jā. Jūs varat uzvilkt raktuvē. >> Visas tiesības.

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

586
00:48:22,170 --> 00:48:25,280
[Students] Tur bija nosacījumu daudz. >> Ak, šaut. Jūs varat -

587
00:48:25,280 --> 00:48:28,110
[Students] Man ir to saglabāt. >> Jā.

588
00:48:32,420 --> 00:48:35,730
Tāpēc mēs to sapludināšanu atsevišķi.

589
00:48:35,730 --> 00:48:38,570
Ak, bet tas nav tik slikti.

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

591
00:48:41,650 --> 00:48:47,080
Tāpēc kārtošanas ir pats tikai zvana mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Paskaidro mums, ko mergeSortHelp dara.

593
00:48:49,530 --> 00:48:55,700
[Students] MergeSortHelp diezgan daudz dara divus galvenos soļus,

594
00:48:55,700 --> 00:49:01,270
kas ir, lai sakārtotu katru pusi no masīva un tad apvienot abus.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Labi, tāpēc man sekundē.

596
00:49:10,850 --> 00:49:13,210
Es domāju, ka šis - >> [students] Man vajag -

597
00:49:17,100 --> 00:49:19,400
Yeah. Es esmu trūkst kaut kas.

598
00:49:19,400 --> 00:49:23,100
Jo sapludināšanu, es saprotu, ka man ir nepieciešams, lai izveidotu jaunu bloku

599
00:49:23,100 --> 00:49:26,530
jo es nevarēju darīt to vietā. >> Jā. Jūs nevarat. Labot.

600
00:49:26,530 --> 00:49:28,170
[Students] Tāpēc es izveidotu jaunu bloku.

601
00:49:28,170 --> 00:49:31,510
Es aizmirsu beigās apvienot ar atkārtotu mainīties.

602
00:49:31,510 --> 00:49:34,490
Labi. Mums vajag jaunu masīvu.

603
00:49:34,490 --> 00:49:41,000
Jo sapludināšanas šķirot, tas gandrīz vienmēr ir taisnība.

604
00:49:41,000 --> 00:49:44,340
Daļu no izmaksām par labāku algoritmu laika gudrs

605
00:49:44,340 --> 00:49:47,310
gandrīz vienmēr nepieciešams izmantot mazliet vairāk atmiņas.

606
00:49:47,310 --> 00:49:51,570
Tātad šeit nav svarīgi, cik jūs apvienot šķirot,

607
00:49:51,570 --> 00:49:54,780
jums būtu neizbēgami nepieciešams izmantot dažas papildu atmiņu.

608
00:49:54,780 --> 00:49:58,240
Viņš vai viņa izveidoja jaunu masīvu.

609
00:49:58,240 --> 00:50:03,400
Un tad jūs sakāt beigās mēs vienkārši nepieciešams, lai kopētu jaunu bloku uz sākotnējo masīvs.

610
00:50:03,400 --> 00:50:04,830
[Students] es tā domāju, jā.

611
00:50:04,830 --> 00:50:08,210
Es nezinu, vai tas darbojas ziņā skaitīšanas atsaucoties vai kāds -

612
00:50:08,210 --> 00:50:11,650
Jā, tas būs darbs. >> [Students] Labi.

613
00:50:20,620 --> 00:50:24,480
Vai jūs mēģināt darboties šo? >> [Students] Nē, vēl ne. >> Labi.

614
00:50:24,480 --> 00:50:28,880
Sāciet to, un tad es ņemšu runāt par to otru.

615
00:50:28,880 --> 00:50:35,200
[Students] Man vajag, lai ir visas funkcijas prototipus un viss, lai gan, ne?

616
00:50:37,640 --> 00:50:40,840
Funkciju prototipus. Ak, tu domā tāpat - Jā.

617
00:50:40,840 --> 00:50:43,040
Šķirot zvana mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Tātad, lai šķirot zvanīt mergeSortHelp, mergeSortHelp vai nu ir definētas

619
00:50:47,390 --> 00:50:56,370
Pirms šķirot vai mums vienkārši vajag prototipu. Vienkārši kopēt un ielīmēt to.

620
00:50:56,370 --> 00:50:59,490
Un līdzīgi, mergeSortHelp zvana apvienot,

621
00:50:59,490 --> 00:51:03,830
bet Apvienošana nav definēts vēl, tāpēc mēs varam tikai let mergeSortHelp zināt

622
00:51:03,830 --> 00:51:08,700
ka tas, ko apvienot gatavojas izskatās, un tas, ka.

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

624
00:51:22,770 --> 00:51:32,660
Mums ir problēmas šeit, kur mums nav pamata lietu.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp ir rekursīvs, tādējādi jebkurš rekursīvas funkcijas

626
00:51:38,110 --> 00:51:42,610
būs nepieciešama sava veida bāzes lietas zināt, kad apstāties rekursīvi zvana pati.

627
00:51:42,610 --> 00:51:45,590
Kas ir mūsu bāzes scenārijs būs šeit? Yeah.

628
00:51:45,590 --> 00:51:49,110
[Students] Ja lielums ir 1? >> [Bowden] Jā.

629
00:51:49,110 --> 00:51:56,220
Tātad, piemēram, mēs redzējām labi tur, mēs apstājāmies sadalīšanas bloki

630
00:51:56,220 --> 00:52:01,850
kad mēs saņēmām uz blokiem lieluma 1, kas neizbēgami ir sakārtoti sevi.

631
00:52:01,850 --> 00:52:09,530
Tātad, ja izmērs ir vienāds ar 1, mēs zinām masīvs jau ir sakārtoti,

632
00:52:09,530 --> 00:52:12,970
lai mēs varētu vienkārši atgriezties.

633
00:52:12,970 --> 00:52:16,880
>> Ievērojiet, ka ir anulēts, tāpēc mums nav atgriešanās neko īpašu, mēs vienkārši atgriezties.

634
00:52:16,880 --> 00:52:19,580
Labi. Tātad tas ir mūsu bāzes scenārijs.

635
00:52:19,580 --> 00:52:27,440
Es domāju mūsu bāzes scenārijs varētu būt arī tad, ja mēs notikt, apvienojas masīvs 0 izmērs,

636
00:52:27,440 --> 00:52:30,030
Mēs, iespējams, vēlas, lai apturētu kādā brīdī,

637
00:52:30,030 --> 00:52:33,610
tāpēc mēs varam tikai teikt izmērs ir mazāks nekā 2 vai mazāks vai vienāds ar 1

638
00:52:33,610 --> 00:52:37,150
tāpēc, ka tas darbosies jebkurā masīva tagad.

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

640
00:52:38,870 --> 00:52:42,740
Tātad tas ir mūsu bāzes scenārijs.

641
00:52:42,740 --> 00:52:45,950
Tagad jūs vēlaties staigāt mūs cauri apvienoties?

642
00:52:45,950 --> 00:52:49,140
Ko visi šie gadījumi nozīmē?

643
00:52:49,140 --> 00:52:54,480
Šeit, mēs esam tikai darām to pašu ideju, -

644
00:52:56,970 --> 00:53:02,470
[Students] man vajag iet garām izmēru ar visiem mergeSortHelp zvaniem.

645
00:53:02,470 --> 00:53:10,080
I pievienotās izmērs kā papildu primārais un tas nav tur, tāpat izmēra / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Ak, izmērs / 2, izmērs / 2. >> [Students] Jā, un arī iepriekš funkcija, kā arī.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Šeit? >> [Students] Tikai izmēru. >> [Bowden] Ak. Izmērs, lielums? >> [Students] Jā.

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

649
00:53:23,010 --> 00:53:26,580
Ļaujiet man domāt par sekundi.

650
00:53:26,580 --> 00:53:28,780
Vai mēs uzskriet jautājumu?

651
00:53:28,780 --> 00:53:33,690
Mēs vienmēr apstrādājot kreisi kā 0. >> [Students] Nē

652
00:53:33,690 --> 00:53:36,340
Tas ir nepareizi pārāk. Žēl. Tas būtu sākums. Yeah.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Labi. Man patīk, ka labāk.

654
00:53:39,230 --> 00:53:43,880
Un beigu. Labi.

655
00:53:43,880 --> 00:53:47,200
Tātad tagad jūs vēlaties staigāt mūs cauri apvienoties? >> [Students] Labi.

656
00:53:47,200 --> 00:53:52,150
Es esmu tikai ejot caur šo jauno bloku, ka es esmu izveidojis.

657
00:53:52,150 --> 00:53:57,420
Tās izmērs ir lielums daļu masīva ka mēs gribam būt sakārtoti

658
00:53:57,420 --> 00:54:03,460
un mēģina atrast elementu, kas man būtu jāliek jaunā masīva soli.

659
00:54:03,460 --> 00:54:10,140
Tātad, lai to izdarītu, vispirms es esmu pārbaude, ja kreiso pusi no masīva joprojām ir kādi elementi,

660
00:54:10,140 --> 00:54:14,260
un ja tā nav, tad jums iet uz leju, lai šo citam nosacījumam, kas tikko saka

661
00:54:14,260 --> 00:54:20,180
labi, tai jābūt pareizā masīvā, un mēs nodot, ka pašreizējā indeksa newArray.

662
00:54:20,180 --> 00:54:27,620
>> Un tad citādi, es esmu pārbaudot, ja labajā pusē masīva ir arī pabeigta,

663
00:54:27,620 --> 00:54:30,630
tādā gadījumā es vienkārši ielieciet kreisi.

664
00:54:30,630 --> 00:54:34,180
Tas varētu faktiski nav nepieciešams. Es neesmu pārliecināts.

665
00:54:34,180 --> 00:54:40,970
Bet anyway, pārējie divi pārbaude, kura no divām ir mazāka kreisi vai pa labi.

666
00:54:40,970 --> 00:54:49,770
Un arī katrā gadījumā, es esmu palielināšanai atkarībā vietturis es pieauguma.

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

668
00:54:52,040 --> 00:54:53,840
Tas izskatās labi.

669
00:54:53,840 --> 00:54:58,800
Vai kāds ir komentāri vai bažas vai jautājumi?

670
00:55:00,660 --> 00:55:07,720
Tātad četriem gadījumiem, kas mums ir, lai lietas vērā tikai to - vai tas izskatās pieci -

671
00:55:07,720 --> 00:55:13,100
bet mums ir jāapsver, vai kreisi masīvs ir beigušies lietas, kas mums ir nepieciešams apvienot,

672
00:55:13,100 --> 00:55:16,390
vai tiesības masīvs ir beigušies lietas, kas mums ir nepieciešams apvienot -

673
00:55:16,390 --> 00:55:18,400
Es esmu norādot uz neko.

674
00:55:18,400 --> 00:55:21,730
Tātad, vai kreisi masīvs ir beigušies lietām vai tiesībām masīvs ir beigušies lietām.

675
00:55:21,730 --> 00:55:24,320
Tie ir divi gadījumi.

676
00:55:24,320 --> 00:55:30,920
Mums ir vajadzīgs arī triviāls gadījumu vai kreisā lieta ir mazāks nekā pareizo lietu.

677
00:55:30,920 --> 00:55:33,910
Tad mēs vēlamies, lai izvēlētos kreiso lieta.

678
00:55:33,910 --> 00:55:37,630
Tie ir gadījumi.

679
00:55:37,630 --> 00:55:40,990
Tātad tas bija labi, tāpēc tas, ka.

680
00:55:40,990 --> 00:55:46,760
Array kreisi. Tas ir 1, 2, 3. Labi. Tātad yeah, tie ir četras lietas, mēs varētu vēlēties darīt.

681
00:55:50,350 --> 00:55:54,510
Un mēs ne iet pār iteratīvu risinājumu.

682
00:55:54,510 --> 00:55:55,980
Es nevarētu ieteikt -

683
00:55:55,980 --> 00:56:03,070
Sapludināt kārtošanas ir piemērs funkciju, kas ir gan nav astes rekursīvs

684
00:56:03,070 --> 00:56:07,040
tas nav viegli, lai padarītu to astes rekursīvs

685
00:56:07,040 --> 00:56:13,450
bet arī tas nav ļoti viegli veikt to iteratīvs.

686
00:56:13,450 --> 00:56:16,910
Tas ir ļoti viegli.

687
00:56:16,910 --> 00:56:19,170
Šis īstenošanu sapludināšanas šķirot,

688
00:56:19,170 --> 00:56:22,140
apvienot, nav svarīgi, ko jūs darāt, jūs gatavojas būvēt sapludināšanu.

689
00:56:22,140 --> 00:56:29,170
>> Tāpēc apvienot kārtot celta uz augšu sapludināšanu rekursīvi ir tikai šīs trīs līnijas.

690
00:56:29,170 --> 00:56:34,700
Iteratīvi, tas ir vairāk kaitinošas un grūtāk domāt par.

691
00:56:34,700 --> 00:56:41,860
Bet paziņo, ka tas nav astes rekursīvs jo mergeSortHelp - ja tā sevi dēvē -

692
00:56:41,860 --> 00:56:46,590
tas vēl ir jādara lietas pēc šī rekursīvas zvanu atdevi.

693
00:56:46,590 --> 00:56:50,830
Tātad šī kaudze rāmi jāturpina pastāvēt pat pēc zvana to.

694
00:56:50,830 --> 00:56:54,170
Un tad, kad tu to sauc, kaudze rāmi jāturpina pastāvēt

695
00:56:54,170 --> 00:56:57,780
jo pat pēc šī zvana, mums joprojām ir nepieciešams apvienot.

696
00:56:57,780 --> 00:57:01,920
Un tas ir netriviāls, lai padarītu šo asti rekursīvas.

697
00:57:04,070 --> 00:57:06,270
Jautājumi?

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

699
00:57:09,860 --> 00:57:13,400
Tā iet atpakaļ uz sakārtotu - ak, tur ir divas lietas, es vēlos parādīt. Labi.

700
00:57:13,400 --> 00:57:17,840
Dodas atpakaļ uz kārtot, mēs izdarīt ātri.

701
00:57:17,840 --> 00:57:21,030
Vai meklēšanu. Šķirot? Kārtošanas. Yeah.

702
00:57:21,030 --> 00:57:22,730
Dodas atpakaļ uz kārtot pirmsākumiem.

703
00:57:22,730 --> 00:57:29,870
Mēs vēlamies izveidot algoritmu, kas sakārto masīvu, izmantojot jebkuru algoritmu

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

705
00:57:33,660 --> 00:57:40,860
Tātad, kā tas ir iespējams? Vai kāds ir jebkāda veida -

706
00:57:40,860 --> 00:57:44,300
Es mājienu pirms pie -

707
00:57:44,300 --> 00:57:48,300
Ja mēs esam par to uzlabot no n log n līdz O n,

708
00:57:48,300 --> 00:57:51,450
Mēs esam uzlabojuši mūsu algoritms laika gudrs,

709
00:57:51,450 --> 00:57:55,250
kas nozīmē to, ko mēs gatavojamies jādara, lai atgūtu to?

710
00:57:55,250 --> 00:57:59,520
[Students] Space. >> Jā. Mēs ejam, lai, izmantojot vairāk vietas.

711
00:57:59,520 --> 00:58:04,490
Un nav pat tikai vairāk vietas, tas ir eksponenciāli vairāk vietas.

712
00:58:04,490 --> 00:58:14,320
Tāpēc es domāju, ka šis algoritms veids ir pseido kaut, pseido polynom -

713
00:58:14,320 --> 00:58:18,980
pseido - es nevaru atcerēties. Pseido kaut.

714
00:58:18,980 --> 00:58:22,210
Bet tas ir tāpēc, ka mums ir nepieciešams, lai izmantotu tik daudz vietas

715
00:58:22,210 --> 00:58:28,610
ka tas sasniedzams, bet ne reāli.

716
00:58:28,610 --> 00:58:31,220
>> Un kā mēs to sasniegtu?

717
00:58:31,220 --> 00:58:36,810
Mēs varam panākt, ja mēs garantējam, ka kāds konkrēts elements masīva

718
00:58:36,810 --> 00:58:39,600
ir zem noteikta lieluma.

719
00:58:42,070 --> 00:58:44,500
Tāpēc pieņemsim tikai teikt, ka izmērs ir 200,

720
00:58:44,500 --> 00:58:48,130
jebkurš masīvā elements ir mazāks izmērs 200.

721
00:58:48,130 --> 00:58:51,080
Un tas tiešām ir ļoti reāls.

722
00:58:51,080 --> 00:58:58,660
Jūs varat ļoti viegli ir masīvs, ka jūs zināt visu, kas tajā

723
00:58:58,660 --> 00:59:00,570
būs mazāks nekā daži numuru.

724
00:59:00,570 --> 00:59:07,400
Tāpat, ja Jums ir dažas absolūti masveida vektoru vai kaut

725
00:59:07,400 --> 00:59:11,810
bet jūs zināt viss būs no 0 līdz 5,

726
00:59:11,810 --> 00:59:14,790
tad tas būs daudz ātrāk to darīt.

727
00:59:14,790 --> 00:59:17,930
Un uz kāda no elementiem saistoši ir 5,

728
00:59:17,930 --> 00:59:21,980
tāpēc tas saistās, ka ir, cik daudz atmiņas jūs būs izmantojot.

729
00:59:21,980 --> 00:59:26,300
Tāpēc saistītā ir 200.

730
00:59:26,300 --> 00:59:32,960
Teorētiski pastāv vienmēr saistās jo skaitlis var būt tikai līdz miljardiem 4,

731
00:59:32,960 --> 00:59:40,600
bet tas ir nereāli, jo tad mēs gribētu būt, izmantojot telpu

732
00:59:40,600 --> 00:59:44,400
par kārtību miljardiem 4. Tātad tas ir nereāli.

733
00:59:44,400 --> 00:59:47,060
Bet šeit mēs teikt mūsu saistoši ir 200.

734
00:59:47,060 --> 00:59:59,570
Triks, lai dara to O n ir mums veikt citu masīvu sauc skaits no lieluma saistoši.

735
00:59:59,570 --> 01:00:10,470
Tātad faktiski, tas ir īsceļu - es tiešām nezinu, ja šķindēt dara.

736
01:00:11,150 --> 01:00:15,330
Bet GCC vismaz - I'm pieņemot šķindēt dara to pārāk -

737
01:00:15,330 --> 01:00:18,180
tas būs vienkārši sāktu visu masīvs būt 0s.

738
01:00:18,180 --> 01:00:25,320
Tātad, ja es nevēlos to darīt, tad es varētu atsevišķi darīt (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <Bound, i + +) un skaitās [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Tāpēc tagad viss ir inicializēts līdz 0.

741
01:00:35,260 --> 01:00:39,570
Es atkārtot pār manu masīvs,

742
01:00:39,570 --> 01:00:51,920
un ko es daru, ir es esmu saskaitot katras - iesim uz leju šeit.

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

744
01:00:55,480 --> 01:01:00,010
Ko es esmu skaitīšanas ir atkārtojumu skaitu katram no šiem elementiem.

745
01:01:00,010 --> 01:01:03,470
Pieņemsim faktiski pievienot pāris vairāk šeit ar dažiem atkārtojas.

746
01:01:03,470 --> 01:01:11,070
Tātad vērtība, mēs esam šeit, uz šī vērtība būs masīvs [i].

747
01:01:11,070 --> 01:01:14,850
Tāpēc val varētu būt 4 vai 8 vai neatkarīgi.

748
01:01:14,850 --> 01:01:18,870
Un tagad es esmu skaitīšanas cik daudzi no šīs vērtības es esmu redzējis,

749
01:01:18,870 --> 01:01:21,230
tāpēc epizodēs [val] + +;

750
01:01:21,230 --> 01:01:29,430
Pēc tam tiek darīts, skaits ir gatavojas izskatās kaut kā 0001.

751
01:01:29,430 --> 01:01:42,190
Darīsim skaitu [Val] - BOUND + 1.

752
01:01:42,190 --> 01:01:48,230
>> Tagad tas ir tikai, lai ņemtu vērā faktu, ka mēs sākot no 0.

753
01:01:48,230 --> 01:01:50,850
Tātad, ja 200 būs mūsu lielākais skaits,

754
01:01:50,850 --> 01:01:54,720
tad 0-200 ir 201 lietas.

755
01:01:54,720 --> 01:02:01,540
Tātad skaitu, tas būs izskatās 00.001 jo mums ir viena 4.

756
01:02:01,540 --> 01:02:10,210
Tad mums būs 0001 ja mums būs 1 no 8 indeksu skaits.

757
01:02:10,210 --> 01:02:14,560
Mums būs 2 Padomes 23 indeksa skaits.

758
01:02:14,560 --> 01:02:17,630
Mums būs 2 uz 42 indeksa skaits.

759
01:02:17,630 --> 01:02:21,670
Tātad, mēs varam izmantot skaitu.

760
01:02:34,270 --> 01:02:44,920
Tātad num_of_item = skaits [i].

761
01:02:44,920 --> 01:02:52,540
Un tāpēc, ja num_of_item ir 2, tas nozīmē, ka mēs vēlamies, lai ievietotu 2 skaitu i

762
01:02:52,540 --> 01:02:55,290
mūsu šķiroto masīvs.

763
01:02:55,290 --> 01:03:02,000
Tāpēc mums ir nepieciešams, lai sekotu tam, cik tālu mēs esam uz masīvu.

764
01:03:02,000 --> 01:03:05,470
Tātad indekss = 0.

765
01:03:05,470 --> 01:03:09,910
Array - Es ņemšu tikai rakstīt to.

766
01:03:16,660 --> 01:03:18,020
Grāfu -

767
01:03:19,990 --> 01:03:28,580
masīvs [indekss + +] = i;

768
01:03:28,580 --> 01:03:32,490
Vai tas, ko es gribu? Es domāju, ka tas, ko es gribu.

769
01:03:35,100 --> 01:03:38,290
Jā, tas izskatās labi. Labi.

770
01:03:38,290 --> 01:03:43,050
Lai vai visi saprastu, ko mana grāfu masīva mērķis ir?

771
01:03:43,050 --> 01:03:48,140
Tas ir skaitot atkārtojumu skaitu katrā no šiem skaitļiem.

772
01:03:48,140 --> 01:03:51,780
Tad es esmu atkārtojot pār ka skaita masīvs,

773
01:03:51,780 --> 01:03:57,190
un kārtējā pozīcija grāfu masīvā

774
01:03:57,190 --> 01:04:01,930
ir vairāki man ir, ka vajadzētu parādīties manā šķiroto masīvā.

775
01:04:01,930 --> 01:04:06,840
Tieši tāpēc skaits gada 4 būs 1

776
01:04:06,840 --> 01:04:11,840
un skaits gada 8 būs 1, skaits no 23 ir būs 2.

777
01:04:11,840 --> 01:04:16,900
Tātad tas, kā daudzi no viņiem es gribu ievietot manā šķiroto masīvs.

778
01:04:16,900 --> 01:04:19,200
Tad es vienkārši darīt.

779
01:04:19,200 --> 01:04:28,960
Es esmu ievietojot num_of_item man ir manā šķiroto masīvs.

780
01:04:28,960 --> 01:04:31,670
>> Jautājumi?

781
01:04:32,460 --> 01:04:43,100
Un tā atkal, tas ir lineārs laiks, kopš mēs esam tikai atkārtojot pār šo vienu reizi,

782
01:04:43,100 --> 01:04:47,470
bet tas ir arī lineārs, ko šis skaitlis notiek, ir,

783
01:04:47,470 --> 01:04:50,730
un tā tas lielā mērā ir atkarīgs no tā, ko jūsu pienākums ir.

784
01:04:50,730 --> 01:04:53,290
Ar robežu 200, tas nav tik slikti.

785
01:04:53,290 --> 01:04:58,330
Ja jūsu pienākums būs 10,000, tad tas ir mazliet sliktāk,

786
01:04:58,330 --> 01:05:01,360
bet, ja jūsu pienākums būs 4 miljardus, kas ir pilnīgi nereāli

787
01:05:01,360 --> 01:05:07,720
un šis masīvs būs jābūt ar izmēru 4 miljardus, kas ir nereāli.

788
01:05:07,720 --> 01:05:10,860
Tātad tas ir kas. Jautājumi?

789
01:05:10,860 --> 01:05:13,270
[Dzirdams studentu reaģēšanas] >> Labi.

790
01:05:13,270 --> 01:05:15,710
Es sapratu viena cita lieta, kad mēs iet cauri.

791
01:05:17,980 --> 01:05:23,720
Es domāju, ka problēma bija Lucas s un, iespējams, katrs no mums esam redzējuši.

792
01:05:23,720 --> 01:05:26,330
Es pilnīgi aizmirsu.

793
01:05:26,330 --> 01:05:31,040
Vienīgais es gribēju komentēt, ka, ja jūs nodarbojas ar lietām, piemēram, indeksiem,

794
01:05:31,040 --> 01:05:38,320
tu nekad īsti redzēt šo, kad jūs esat rakstiski par cilpu,

795
01:05:38,320 --> 01:05:41,120
bet tehniski, kad jūs nodarbojas ar šiem rādītājiem,

796
01:05:41,120 --> 01:05:45,950
Jums vajadzētu diezgan daudz vienmēr nodarbojas ar neparakstītu integers.

797
01:05:45,950 --> 01:05:53,850
Iemesls tam ir, kad jūs nodarbojas ar parakstīto veseliem skaitļiem,

798
01:05:53,850 --> 01:05:56,090
tāpēc, ja jums ir 2 parakstīti integers un jūs pievienojat tos kopā

799
01:05:56,090 --> 01:06:00,640
un tie galu galā ir pārāk liels, tad jūs galu galā ar negatīvu skaitli.

800
01:06:00,640 --> 01:06:03,410
Tātad, tas ko skaitlim pārpildes ir.

801
01:06:03,410 --> 01:06:10,500
>> Ja es pievienot 2 miljardiem un 1 miljards es galu galā ar negatīvs 1 miljardus.

802
01:06:10,500 --> 01:06:15,480
Tas ir kā veseli strādā pie datoriem.

803
01:06:15,480 --> 01:06:17,510
Tātad ar izmantojot problēma -

804
01:06:17,510 --> 01:06:23,500
Tas ir labi, izņemot, ja zemu notiek, ir 2 miljardiem un līdz notiek, ir 1 miljards

805
01:06:23,500 --> 01:06:27,120
tad tas būs negatīvs 1 miljardu un tad mēs spēsim dalīt to ar 2

806
01:06:27,120 --> 01:06:29,730
un galu galā ar negatīvu 500 miljoni.

807
01:06:29,730 --> 01:06:33,760
Tātad tas ir tikai jautājums, ja jums gadās būt meklējot caur masīvu

808
01:06:33,760 --> 01:06:38,070
miljardiem lietām.

809
01:06:38,070 --> 01:06:44,050
Bet, ja zemu + līdz notiek ar pārplūdes, tad tas ir problēma.

810
01:06:44,050 --> 01:06:47,750
Tiklīdz mēs padarītu tos neparakstītu, tad 2 miljardu euro apmērā 1000000000 ir 3 miljardi.

811
01:06:47,750 --> 01:06:51,960
3000000000 dalīts ar 2 ir 1,5 miljardi euro.

812
01:06:51,960 --> 01:06:55,670
Tā tiklīdz viņi neparakstītu, viss ir ideāli.

813
01:06:55,670 --> 01:06:59,900
Un tā tas ir arī jautājums, kad jūs rakstot savu uz cilpas,

814
01:06:59,900 --> 01:07:03,940
un faktiski, tas, iespējams, tas automātiski.

815
01:07:09,130 --> 01:07:12,330
Tas būs tiešām tikai kliegt pie jums.

816
01:07:12,330 --> 01:07:21,610
Tātad, ja šis skaitlis ir pārāk liels, lai būtu tikai veselam skaitlim, bet tas varētu iederēties neparakstītu skaitlim,

817
01:07:21,610 --> 01:07:24,970
tas būs kliegt pie jums, tā, ka tāpēc tu nekad īsti uzskriet jautājumu.

818
01:07:29,150 --> 01:07:34,820
Jūs varat redzēt, ka indekss ir nekad būs negatīvs,

819
01:07:34,820 --> 01:07:39,220
un tāpēc, ja jūs atkārtojot pa masīva,

820
01:07:39,220 --> 01:07:43,970
Jūs varat gandrīz vienmēr teikt neparakstīts int i, bet jums nav īsti ir.

821
01:07:43,970 --> 01:07:47,110
Lietas notiek uz darbu diezgan daudz tikpat labi.

822
01:07:48,740 --> 01:07:50,090
Labi. [Čukst] Kas ir pulkstenis?

823
01:07:50,090 --> 01:07:54,020
Pēdējā lieta, ko es gribēju parādīt - un es ņemšu tikai darīt to patiešām ātri.

824
01:07:54,020 --> 01:08:03,190
Jūs zināt, kā mēs esam # define lai mēs varam # definēt MAX kā 5 vai kaut ko?

825
01:08:03,190 --> 01:08:05,940
Pieņemsim nav do MAKS. # Define saistības kā 200. Tas, ko mēs darījām agrāk.

826
01:08:05,940 --> 01:08:10,380
Kas definē konstante, kas ir tikai gatavojas kopēt un ielīmēt

827
01:08:10,380 --> 01:08:13,010
kur mēs notikt rakstīt saistoši.

828
01:08:13,010 --> 01:08:18,189
>> Tātad, mēs varam reāli darīt vairāk ar # definē.

829
01:08:18,189 --> 01:08:21,170
Mēs varam # definēt funkcijas.

830
01:08:21,170 --> 01:08:23,410
Viņi nav īsti funkcijas, bet mēs tos saucam funkcijas.

831
01:08:23,410 --> 01:08:36,000
Piemērs varētu būt kaut kas līdzīgs MAX (x, y) ir definēta kā (x <y y: x). Labi.

832
01:08:36,000 --> 01:08:40,660
Tātad jums vajadzētu pierast trīskāršo operators sintaksi,

833
01:08:40,660 --> 01:08:49,029
bet ir x mazāks nekā y? Atgriezties y, cits X apmaiņā.

834
01:08:49,029 --> 01:08:54,390
Tātad jūs varat redzēt, jūs varat veikt šo atsevišķu funkciju,

835
01:08:54,390 --> 01:09:01,399
un funkcijas varētu būt, piemēram, bool MAX aizņem 2 argumentus, atgriezties to.

836
01:09:01,399 --> 01:09:08,340
Šis ir viens no visbiežāk tie, es redzu darīts, piemēram, šis. Mēs tos saucam makro.

837
01:09:08,340 --> 01:09:11,790
Tas ir makro.

838
01:09:11,790 --> 01:09:15,859
Tas ir tikai sintakse par to.

839
01:09:15,859 --> 01:09:18,740
Jūs varat rakstīt makro darīt, ko vien vēlaties.

840
01:09:18,740 --> 01:09:22,649
Jūs bieži redzēt makro debugging printfs un stuff.

841
01:09:22,649 --> 01:09:29,410
Tātad tipam printf, pastāv īpašas konstantes K piemēram pasvītrojumu LINE pasvītrojumu,

842
01:09:29,410 --> 01:09:31,710
2 uzsver LINE pasvītrojumu,

843
01:09:31,710 --> 01:09:37,550
un tur ir arī es domāju 2 uzsver FUNC. Tas varētu būt tas. Kaut kā tā.

844
01:09:37,550 --> 01:09:40,880
Šīs lietas tiks aizstāts ar nosaukumu funkcijas

845
01:09:40,880 --> 01:09:42,930
vai numuru no līnijas, ka jūs par.

846
01:09:42,930 --> 01:09:48,630
Bieži, jūs rakstīt atkļūdošanas printfs ka noteikti šeit es varētu vienkārši uzrakstīt

847
01:09:48,630 --> 01:09:54,260
DEBUG un tas būs drukāt rindas numuru un funkciju, kas man gadās būt

848
01:09:54,260 --> 01:09:57,020
ka tā saskārās šīs DEBUG paziņojumu.

849
01:09:57,020 --> 01:09:59,550
Un jūs varat arī izdrukāt citas lietas.

850
01:09:59,550 --> 01:10:05,990
Tātad viena lieta, jums vajadzētu skatīties, kas ir, ja es notikt # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
kā kaut ko līdzīgu 2 * y un 2 * x.

852
01:10:11,380 --> 01:10:14,310
Tātad kāda iemesla dēļ, jūs notikt darīt daudz.

853
01:10:14,310 --> 01:10:16,650
Lai padarītu to makro.

854
01:10:16,650 --> 01:10:18,680
Šis ir faktiski sadalīts.

855
01:10:18,680 --> 01:10:23,050
Es to sauktu par darot kaut ko līdzīgu DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Tātad, ko jāatdod?

857
01:10:28,840 --> 01:10:30,580
[Students] 12.

858
01:10:30,580 --> 01:10:34,800
Jā, 12 jāatdod, un 12 tiek atgriezta.

859
01:10:34,800 --> 01:10:43,350
3 izpaužas aizstāt x, 6 izpaužas aizstāt y, un mēs atgriežamies 2 * 6, kas ir 12.

860
01:10:43,350 --> 01:10:47,710
Tagad to, ko par šo? Kas būtu atpakaļ?

861
01:10:47,710 --> 01:10:50,330
[Students] 14. >> Ideālā, 14.

862
01:10:50,330 --> 01:10:55,290
Jautājums ir, ka, kā hash definē darbu, atcerieties, tas ir burtiski kopēt un ielīmēt

863
01:10:55,290 --> 01:11:00,160
gada diezgan daudz viss, lai ko tas gatavojas jāinterpretē

864
01:11:00,160 --> 01:11:11,270
ir 3 mazāk nekā 1 plus 6, 2 reizes 1 plus 6, 2 reizes 3.

865
01:11:11,270 --> 01:11:19,780
>> Tātad šī iemesla dēļ jūs gandrīz vienmēr wrap viss iekavās.

866
01:11:22,180 --> 01:11:25,050
Jebkurš mainīgais jūs gandrīz vienmēr wrap iekavās.

867
01:11:25,050 --> 01:11:29,570
Ir gadījumi, kad jums nav, lai, piemēram, es zinu, ka man nav nepieciešams to darīt šeit

868
01:11:29,570 --> 01:11:32,110
jo mazāk nekā ir diezgan daudz vienmēr vienkārši iet uz darbu,

869
01:11:32,110 --> 01:11:34,330
kaut kas varētu pat nebūt taisnība.

870
01:11:34,330 --> 01:11:41,870
Ja ir kaut kas smieklīgs, piemēram DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
tad kas notiek, lai saņemtu aizstāts ar 1 3 mazāk nekā vienāds vienāds ar 2,

872
01:11:49,760 --> 01:11:53,460
un tā tad tas būs jādara 3 mazāk nekā 1, tas, ka vienāda 2,

873
01:11:53,460 --> 01:11:55,620
kas nav tas, ko mēs vēlamies.

874
01:11:55,620 --> 01:12:00,730
Tātad, lai novērstu operatora Prioritātes problēmas,

875
01:12:00,730 --> 01:12:02,870
vienmēr wrap iekavās.

876
01:12:03,290 --> 01:12:07,700
Labi. Un tas ir tas, 5:30.

877
01:12:08,140 --> 01:12:12,470
Ja Jums ir kādi jautājumi par PSET, dodiet mums zināt.

878
01:12:12,470 --> 01:12:18,010
Tas būtu jautri, un hakeru valodā arī ir daudz reālāks

879
01:12:18,010 --> 01:12:22,980
nekā hakeru izdevumā pagājušo gadu, tāpēc mēs ceram, ka daudzi no jums izmēģināt to.

880
01:12:22,980 --> 01:12:26,460
Pagājušajā gadā bija ļoti pārliecinošs.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]