1
00:00:00,000 --> 00:00:00,488

2
00:00:00,488 --> 00:00:10,800
>> [Daqq tal-mużika]

3
00:00:10,800 --> 00:00:13,500
DAVID Malan: Kull dritt.

4
00:00:13,500 --> 00:00:14,670
Kull dritt, welcome lura.

5
00:00:14,670 --> 00:00:18,120
Allura dan huwa Ġimgħa 4, il-bidu
tiegħu, diġà.

6
00:00:18,120 --> 00:00:21,320
U inti ser tfakkar li l-aħħar ġimgħa, npoġġux
kodiċi riservati għall biss ftit

7
00:00:21,320 --> 00:00:24,240
u bdejna nitkellmu ftit aktar
ta 'livell għoli, dwar affarijiet bħal

8
00:00:24,240 --> 00:00:28,130
tiftix u għażla, li għalkemm
ideat pjuttost sempliċi, huma

9
00:00:28,130 --> 00:00:31,840
rappreżentant ta 'klassi ta' problemi
inti se tibda biex isolvu partikolarment

10
00:00:31,840 --> 00:00:34,820
kif inti tibda taħseb dwar finali
proġetti u soluzzjonijiet interessanti inti

11
00:00:34,820 --> 00:00:36,760
jista 'jkollok problemi tad-dinja reali.

12
00:00:36,760 --> 00:00:39,490
Issa tip bużżieqa kienet waħda mill-aktar sempliċi
bħal algoritmi, u

13
00:00:39,490 --> 00:00:42,900
maħduma billi dawn in-numri żgħar
f'lista jew fil-firxa tip ta '

14
00:00:42,900 --> 00:00:46,530
bużżieqa mod tagħhom sal-quċċata, u l-
numri kbar jimxu mod tagħhom sa

15
00:00:46,530 --> 00:00:47,930
l-aħħar ta 'dik il-lista.

16
00:00:47,930 --> 00:00:50,650
>> U tfakkar li nistgħu Ħares
bubble sort ftit

17
00:00:50,650 --> 00:00:52,310
xi ħaġa bħal din.

18
00:00:52,310 --> 00:00:53,640
So let me go quddiem u kklikkja Bidu.

19
00:00:53,640 --> 00:00:55,350
Stajt magħżula minn qabel sort bubble.

20
00:00:55,350 --> 00:00:58,920
U jekk inti recall li l-blu taller
linji jirrappreżentaw numri kbar, żgħar

21
00:00:58,920 --> 00:01:03,300
linji blu jirrappreżentaw numri żgħar, kif
aħna jgħaddu din darb'oħra u għal darb'oħra u

22
00:01:03,300 --> 00:01:07,680
għal darb'oħra, li jqabbel żewġ bars wieħed ħdejn l-
oħra bl-aħmar, aħna qed tmur biex tpartit l-

23
00:01:07,680 --> 00:01:11,010
akbar u l-iżgħar jekk
huma out of order.

24
00:01:11,010 --> 00:01:14,150
>> Allura dan se jmorru fuq u jmorru fuq u jmorru
fuq, u tkun taf tara li l-akbar

25
00:01:14,150 --> 00:01:16,700
Elementi qed jagħmlu triqthom lejn il-
dritt, u l-elementi iżgħar huma

26
00:01:16,700 --> 00:01:17,900
jagħmlu mod tagħhom lejn ix-xellug.

27
00:01:17,900 --> 00:01:21,380
Iżda aħna bdew jikkwantifikaw
l-effiċjenza, l-

28
00:01:21,380 --> 00:01:22,970
kwalità ta 'dan algoritmu.

29
00:01:22,970 --> 00:01:25,200
U aħna qal li fl-agħar
każ, dan algoritmu ħa

30
00:01:25,200 --> 00:01:27,940
bejn wieħed u ieħor kemm-passi?

31
00:01:27,940 --> 00:01:28,980
>> Allura n kwadru.

32
00:01:28,980 --> 00:01:30,402
U dak li kien n?

33
00:01:30,402 --> 00:01:31,650
>> UDJENZA: Numru ta 'elementi.

34
00:01:31,650 --> 00:01:32,790
>> DAVID Malan: Allura n kienet l-
numru ta 'elementi.

35
00:01:32,790 --> 00:01:33,730
U hekk aħna ser jagħmlu dan ta 'spiss.

36
00:01:33,730 --> 00:01:36,650
Kwalunkwe ħin rridu nitkellmu dwar id-daqs
ta 'problema jew id-daqs ta'

37
00:01:36,650 --> 00:01:39,140
input, jew l-ammont ta 'ħin li tieħu
biex jipprovdi produzzjoni, aħna ser biss

38
00:01:39,140 --> 00:01:41,610
tkun xi tkun ġeneralizzata
l-input huwa kif n.

39
00:01:41,610 --> 00:01:45,970
Allura lura fil-Ġimgħa 0, paġni l-għadd
fil-ktieb tat-telefon kien n.

40
00:01:45,970 --> 00:01:47,550
In-numru ta 'studenti
fil-kamra kienet n.

41
00:01:47,550 --> 00:01:49,630
Allura hawnhekk, wisq, aħna qed wara
dak il-mudell.

42
00:01:49,630 --> 00:01:52,800
>> Issa n kwadrat mhuwiex partikolarment
fast, hekk aħna ppruvaw li naħdmu aħjar.

43
00:01:52,800 --> 00:01:55,970
U hekk aħna ħares lejn koppja ta '
algoritmi oħra, fosthom

44
00:01:55,970 --> 00:01:57,690
kienu sort għażla.

45
00:01:57,690 --> 00:01:59,180
Allura sort għażla kienet
ftit differenti.

46
00:01:59,180 --> 00:02:03,130
Kien kważi sempliċi, I DARE ngħid,
fejn I bdiet fil-bidu tal-

47
00:02:03,130 --> 00:02:06,740
lista ta 'voluntiera tagħna u I biss darb'oħra
u għal darb'oħra u għal darb'oħra marru permezz

48
00:02:06,740 --> 00:02:10,060
il-lista, tnittif l-iżgħar
element fi żmien u jniżżlu jew

49
00:02:10,060 --> 00:02:13,040
tagħha fil-bidu tal-lista.

50
00:02:13,040 --> 00:02:16,410
>> Iżda dan, wisq, ladarba aħna bdew jaħsbu
permezz tal-matematika u akbar

51
00:02:16,410 --> 00:02:19,860
stampa, ħsibt dwar kif ħafna drabi
I kien għaddej quddiem u lura u lura

52
00:02:19,860 --> 00:02:24,090
u lura, għidna fl-agħar każ,
sort għażla, wisq, kien dak?

53
00:02:24,090 --> 00:02:24,960
n kwadrat.

54
00:02:24,960 --> 00:02:27,490
Issa fid-dinja reali, dan jista 'jkun
fil-fatt tkun marġinalment aktar mgħaġġel.

55
00:02:27,490 --> 00:02:30,620
Minħabba darb'oħra, I ma għandhomx iżommu
treġġigħ lura darba I kien magħżula l-

56
00:02:30,620 --> 00:02:31,880
elementi iżgħar.

57
00:02:31,880 --> 00:02:35,090
Imma jekk naħsbu dwar n kbir ħafna, u
jekk inti tagħmel tip ta 'l-matematika bħala

58
00:02:35,090 --> 00:02:39,170
Jien għamilt fuq il-bord, bl-kwadrat n
xi ħaġa minus, kollox

59
00:02:39,170 --> 00:02:41,850
minbarra n kwadrat, ladarba n
gets verament kbir, ma

60
00:02:41,850 --> 00:02:42,850
verament kwistjoni kemm.

61
00:02:42,850 --> 00:02:45,470
Sabiex xjenzjati tal-kompjuter, aħna sort ta '
jagħlqu għajnejhom għall-iżgħar

62
00:02:45,470 --> 00:02:49,220
fatturi u tiffoka biss fuq il-fattur fil-
espressjoni li għaddej biex jagħmlu

63
00:02:49,220 --> 00:02:50,330
l-akbar differenza.

64
00:02:50,330 --> 00:02:52,840
>> Ukoll, fl-aħħar, ħarisna
fil sort inserzjoni.

65
00:02:52,840 --> 00:02:56,620
U dan kien simili fl-ispirtu, imma
pjuttost milli jgħaddu iteratively u

66
00:02:56,620 --> 00:03:01,250
jagħżlu l-iżgħar element wieħed fi
time, I minflok ħa l-idejn li I

67
00:03:01,250 --> 00:03:04,070
ġiet ittrattata, u I iddeċieda, kollha
dritt, inti jappartjenu hawn.

68
00:03:04,070 --> 00:03:06,160
Imbagħad mort fuq l-element li jmiss
u ddeċieda li hu jew

69
00:03:06,160 --> 00:03:07,470
hi ikkontrollata hawn.

70
00:03:07,470 --> 00:03:08,810
U mbagħad I mċaqalqa fuq u fuq.

71
00:03:08,810 --> 00:03:11,780
U jien jista lill, tul it-triq,
shift dawn guys sabiex

72
00:03:11,780 --> 00:03:13,030
tagħmel spazju għalihom.

73
00:03:13,030 --> 00:03:16,880
Allura li kien tip ta 'l-inverżjoni mentali
ta 'tip għażla li aħna

74
00:03:16,880 --> 00:03:18,630
imsejħa sort inserzjoni.

75
00:03:18,630 --> 00:03:20,810
>> Allura dawn is-suġġetti li jseħħu
fid-dinja reali.

76
00:03:20,810 --> 00:03:23,640
Just ftit snin ilu, meta ċertu
senatur kien għaddej għall-president,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, fil-mument l-CEO ta '
Google, fil-fatt kellhom l-opportunità

78
00:03:27,160 --> 00:03:28,040
għal intervista lilu.

79
00:03:28,040 --> 00:03:32,010
U ħsibna aħna'd jaqsmu din YouTube
clip għalik hawn, jekk nistgħu dawran up

80
00:03:32,010 --> 00:03:32,950
il-volum.

81
00:03:32,950 --> 00:03:39,360
>> [Daqq video]

82
00:03:39,360 --> 00:03:44,620
>> -Issa, Senatur, int hawn fuq Google,
u I simili biex jaħsbu tal-presidenza

83
00:03:44,620 --> 00:03:46,042
bħala intervista tax-xogħol.

84
00:03:46,042 --> 00:03:47,770
>> [Daħk]

85
00:03:47,770 --> 00:03:50,800
>> -Issa huwa diffiċli biex jiksbu
xogħol bħala president.

86
00:03:50,800 --> 00:03:52,480
U int għaddejjin
l-ħruxija issa.

87
00:03:52,480 --> 00:03:54,330
Huwa wkoll diffiċli li jsibu xogħol fil-Google.

88
00:03:54,330 --> 00:03:59,610
Għandna mistoqsijiet u aħna nitolbu
mistoqsijiet lill-kandidati tagħna.

89
00:03:59,610 --> 00:04:02,250
U dan huwa wieħed mill Larry Schwimmer.

90
00:04:02,250 --> 00:04:05,325
>> [Daħk]

91
00:04:05,325 --> 00:04:06,400
You guys think-jien kidding?

92
00:04:06,400 --> 00:04:08,750
Huwa dritt hawn.

93
00:04:08,750 --> 00:04:12,110
X'inhu l-aktar mod effiċjenti biex
sort miljun interi żewġ-bit?

94
00:04:12,110 --> 00:04:15,810
>> [Daħk]

95
00:04:15,810 --> 00:04:18,260
>> Well, uh -

96
00:04:18,260 --> 00:04:19,029
>> I'm sorry-.

97
00:04:19,029 --> 00:04:19,745
Forsi għandna -

98
00:04:19,745 --> 00:04:21,000
>> -No, no, no, no, no.

99
00:04:21,000 --> 00:04:21,470
>> -Li mhux -

100
00:04:21,470 --> 00:04:22,185
OK.

101
00:04:22,185 --> 00:04:25,328
>> -I think it-tip bużżieqa
jkun il-mod żbaljat biex imorru.

102
00:04:25,328 --> 00:04:26,792
>> [Daħk]

103
00:04:26,792 --> 00:04:28,510
>> [Cheering U applause]

104
00:04:28,510 --> 00:04:31,211
>> -Come on, li qallu dan?

105
00:04:31,211 --> 00:04:32,155
OK.

106
00:04:32,155 --> 00:04:33,350
>> [Daqq video END]

107
00:04:33,350 --> 00:04:35,070
>> DAVID Malan: Allura hemm ikollok.

108
00:04:35,070 --> 00:04:39,600
Allura bdejna biex tikkwantifika dawn running
drabi, biex ngħidu hekk, ma 'xi ħaġa

109
00:04:39,600 --> 00:04:43,480
imsejħa notazzjoni asintotiku, li hija
biss li jirreferu għall tip tagħna ta 'tidwir

110
00:04:43,480 --> 00:04:47,420
għajnejhom għal dawk il-fatturi iżgħar u
biss tħares lejn l-running time,

111
00:04:47,420 --> 00:04:51,250
l-prestazzjoni ta 'dawn algoritmi,
bħala n gets verament kbir matul iż-żmien.

112
00:04:51,250 --> 00:04:55,110
U hekk aħna introdotti big O. U big O
xi ħaġa rappreżentati li ħsibna

113
00:04:55,110 --> 00:04:57,000
ta bħala bound fuq.

114
00:04:57,000 --> 00:04:59,570
U fil-fatt, Barry, nistgħu ibaxxu
mill-mic ftit?

115
00:04:59,570 --> 00:05:01,040
>> Ħsibna ta 'dan huwa marbut fuq.

116
00:05:01,040 --> 00:05:04,710
O daqshekk kbira ta 'n mezzi kwadrati li
l-agħar każ, xi ħaġa bħal

117
00:05:04,710 --> 00:05:07,780
sort għażla se jieħu
n passi kwadrati.

118
00:05:07,780 --> 00:05:10,310
Jew xi ħaġa bħal sort inserzjoni
kieku passi kwadrati n.

119
00:05:10,310 --> 00:05:15,150
Issa għal xi ħaġa bħal inserzjoni
sort, dak li kien l-agħar każ?

120
00:05:15,150 --> 00:05:18,200
Minħabba l-firxa, x'inhu l-agħar
xenarju possibbli li inti tista 'ssib

121
00:05:18,200 --> 00:05:20,650
yourself jiffaċċjaw?

122
00:05:20,650 --> 00:05:21,860
>> Huwa kompletament lura, id-dritt?

123
00:05:21,860 --> 00:05:24,530
Għaliex jekk huwa kompletament lura,
għandek tagħmel lott kollu ta 'xogħol.

124
00:05:24,530 --> 00:05:26,420
Għaliex jekk int kompletament lura,
int ser issib il-

125
00:05:26,420 --> 00:05:28,840
element akbar hawnhekk, anki jekk
jappartjeni stabbiliti hemmhekk.

126
00:05:28,840 --> 00:05:31,140
Allura int ser ngħid, id-dritt, fil-
dan il-mument fil-ħin, inti jagħmlu parti minn hawn,

127
00:05:31,140 --> 00:05:32,310
sabiex inti jitilqu minnu biss.

128
00:05:32,310 --> 00:05:35,425
>> Imbagħad inti tirrealizza, oh, kkritikat, I jkollhom
jimxu dan l-element kemmxejn iżgħar biex

129
00:05:35,425 --> 00:05:36,470
ix-xellug tal inti.

130
00:05:36,470 --> 00:05:38,770
Imbagħad I għandek tagħmel dan mill-ġdid
u għal darb'oħra u għal darb'oħra.

131
00:05:38,770 --> 00:05:41,410
U jekk I mixi u lura, inti
se sort tal jħossu l-prestazzjoni ta '

132
00:05:41,410 --> 00:05:45,540
din l-algorithm minħabba kontinwament am I
jsir ċaqliq kulħadd fid-

133
00:05:45,540 --> 00:05:46,510
array biex tagħmel spazju għal dan.

134
00:05:46,510 --> 00:05:47,750
Allura dak l-agħar każ.

135
00:05:47,750 --> 00:05:48,570
>> B'kuntrast -

136
00:05:48,570 --> 00:05:50,320
u dan kien cliffhanger aħħar darba -

137
00:05:50,320 --> 00:05:54,065
għidna li sort inserzjoni
kien omega 'dak?

138
00:05:54,065 --> 00:05:57,530
X'hemm-running-aħjar każ
ħin ta 'tip inserzjoni?

139
00:05:57,530 --> 00:05:58,520
Allura huwa attwalment n.

140
00:05:58,520 --> 00:06:00,980
Dan kien il-vojt li aħna xellug
fuq il-bord aħħar darba.

141
00:06:00,980 --> 00:06:03,160
>> U huwa omega 'n għaliex għaliex?

142
00:06:03,160 --> 00:06:06,630
Ukoll, fl-aqwa każ, x'hemm
sort inserzjoni se jingħataw?

143
00:06:06,630 --> 00:06:09,830
Well, lista thats kompletament magħżula
diġà, xogħol minimu li tagħmel.

144
00:06:09,830 --> 00:06:12,460
Imma x'hemm pulita dwar sort inserzjoni
hija li minħabba dan tibda hawn u

145
00:06:12,460 --> 00:06:15,340
jiddeċiedi, oh, inti huma n-numru
waħda, inti jappartjenu hawn.

146
00:06:15,340 --> 00:06:16,970
Oh, dak fortuna tajba.

147
00:06:16,970 --> 00:06:17,740
>> Int l-għadd tnejn.

148
00:06:17,740 --> 00:06:19,030
You jagħmlu parti minn hawn.

149
00:06:19,030 --> 00:06:21,010
Numru tlieta, anki aħjar,
inti jappartjenu hawn.

150
00:06:21,010 --> 00:06:25,210
Hekk kif jiġrilha l-aħħar tal-
pseudocode lista, għal kull sort inserzjoni tal

151
00:06:25,210 --> 00:06:28,010
li aħna mixi permezz verbalment
aħħar darba, dan isir.

152
00:06:28,010 --> 00:06:32,790
Iżda sort għażla, għall-kuntrarju,
tinżamm tagħmel dak?

153
00:06:32,790 --> 00:06:35,260
>> Jinżammu għaddejjin permezz tal-lista
ġdid u għal darb'oħra u għal darb'oħra.

154
00:06:35,260 --> 00:06:39,160
Minħabba l-għarfien ewlieni kien hemm biss
ladarba inti stajt ħares-triq kollha lejn l-

155
00:06:39,160 --> 00:06:42,500
aħħar tal-lista tista 'tkun ċerta
li l-element inti magħżula kienet

156
00:06:42,500 --> 00:06:45,560
tabilħaqq l-iżgħar bħalissa element.

157
00:06:45,560 --> 00:06:48,920
Allura dawn differenti mentali mudelli aħħar
up jipproduċi xi ħafna reali tad-dinja

158
00:06:48,920 --> 00:06:53,130
differenzi għalina, kif ukoll dawn
differenzi asintotika teoretiċi.

159
00:06:53,130 --> 00:06:56,910
>> Hekk biss biex terġa, imbagħad, big O ta 'n
kwadrat, Rajna bħal ftit

160
00:06:56,910 --> 00:06:58,350
algoritmi s'issa.

161
00:06:58,350 --> 00:06:59,580
Big O ta 'n?

162
00:06:59,580 --> 00:07:02,870
X'hemm algoritmu li jistgħu
jingħad li big O ta n?

163
00:07:02,870 --> 00:07:06,930
Fl-agħar każ, hija tieħu
numru lineari ta 'passi.

164
00:07:06,930 --> 00:07:07,810
>> OK, tfittxija lineari.

165
00:07:07,810 --> 00:07:10,470
U fl-agħar każ, fejn huwa l-
element li qed tfittex għal meta

166
00:07:10,470 --> 00:07:12,950
applikazzjoni tfittxija lineari?

167
00:07:12,950 --> 00:07:14,680
>> OK, fl-agħar każ,
huwa lanqas hemm.

168
00:07:14,680 --> 00:07:17,000
Jew bit-tieni l-agħar każ, huwa
it-triq kollha fl-aħħar, li hija

169
00:07:17,000 --> 00:07:18,880
plus-or-minus differenza pass wieħed.

170
00:07:18,880 --> 00:07:21,180
Għalhekk fl-aħħar tal-ġurnata,
nistgħu ngħidu huwa lineari.

171
00:07:21,180 --> 00:07:23,910
Big O ta 'n ikun tfittxija lineari,
minħabba fl-agħar każ, il-

172
00:07:23,910 --> 00:07:26,610
element mhux anki hemmhekk jew huwa
it-triq kollha fl-aħħar.

173
00:07:26,610 --> 00:07:29,370
>> Ukoll, big O ta 'log ta' n.

174
00:07:29,370 --> 00:07:32,760
Aħna ma jitkellem fid-dettall kbir dwar
dan, iżda Rajna dan qabel.

175
00:07:32,760 --> 00:07:36,840
Liema jibda fl-hekk imsejħa logaritmika
żmien, fl-agħar każ?

176
00:07:36,840 --> 00:07:38,500
>> Yeah, search hekk binarja.

177
00:07:38,500 --> 00:07:42,930
U tfittxija binarja fl-agħar każ
jista 'jkollhom l-element x'imkien

178
00:07:42,930 --> 00:07:45,640
-nofs, jew x'imkien
ġewwa l-firxa.

179
00:07:45,640 --> 00:07:48,040
Imma inti biss jsibuha ladarba inti
jaqsam il-lista fil nofs, fil-

180
00:07:48,040 --> 00:07:48,940
nofs, fil nofs, fil nofs.

181
00:07:48,940 --> 00:07:50,200
U mbagħad voila, huwa hemmhekk.

182
00:07:50,200 --> 00:07:52,500
Jew darb'oħra, agħar każ,
huwa lanqas hemm.

183
00:07:52,500 --> 00:07:56,770
Imma inti ma taf li mhuwiex hemm
sakemm inti tip ta 'jilħqu dak l-aħħar

184
00:07:56,770 --> 00:08:00,470
bottom-elementi l-aktar minn tnaqqis bin-nofs
u tnaqqis bin-nofs u tnaqqas bin-nofs.

185
00:08:00,470 --> 00:08:01,400
>> Big O ta '1.

186
00:08:01,400 --> 00:08:03,540
Allura nistgħu big O ta '2, big O ta '3.

187
00:08:03,540 --> 00:08:06,260
Ghaċ inti tixtieq biss numru kostanti,
aħna biss tip ta 'ftit jissimplifikaw

188
00:08:06,260 --> 00:08:07,280
li bħala big O ta '1.

189
00:08:07,280 --> 00:08:10,440
Anki jekk jekk realistikament, hija tieħu
2 jew saħansitra 100 passi, jekk huwa

190
00:08:10,440 --> 00:08:13,680
numru kostanti ta 'passi,
aħna biss jgħidu O kbir ta '1.

191
00:08:13,680 --> 00:08:15,930
X'hemm algoritmu li l-
fil big O ta '1?

192
00:08:15,930 --> 00:08:18,350
>> UDJENZA: Tfittxija-tul
ta 'varjabbli.

193
00:08:18,350 --> 00:08:21,090
>> DAVID Malan: Sib l-
tul ta 'varjabbli?

194
00:08:21,090 --> 00:08:23,870
>> UDJENZA: Le, it-tul
jekk huwa diġà magħżula.

195
00:08:23,870 --> 00:08:24,160
>> DAVID Malan: Tajba.

196
00:08:24,160 --> 00:08:27,850
OK, sabiex tinstab it-tul ta 'xi ħaġa
jekk it-tul ta 'li xi ħaġa, bħal

197
00:08:27,850 --> 00:08:30,020
firxa, hija maħżuna f'xi varjabbli.

198
00:08:30,020 --> 00:08:33,380
Għaliex inti tista 'biss taqra l-varjabbli,
jew jistampaw il-varjabbli, jew

199
00:08:33,380 --> 00:08:34,960
biss ġeneralment aċċess dak il-varjabbli.

200
00:08:34,960 --> 00:08:37,299
U voila, li jieħu ż-żmien kostanti.

201
00:08:37,299 --> 00:08:38,909
>> B'kuntrast, think lura li tobrox.

202
00:08:38,909 --> 00:08:42,460
Think lura għall-ewwel ġimgħa ta 'C,
ssejjaħ biss printf u l-istampar

203
00:08:42,460 --> 00:08:46,240
xi ħaġa fuq l-iskrin huwa probabbilment
ħin kostanti, minħabba li biss tieħu

204
00:08:46,240 --> 00:08:50,880
xi numru ta 'ċikli CPU biex juru
dak it-test fuq l-iskrin.

205
00:08:50,880 --> 00:08:52,720
Jew stenna - ma?

206
00:08:52,720 --> 00:08:56,430
Kif inkella tista we mudell l-
prestazzjoni ta 'printf?

207
00:08:56,430 --> 00:09:00,420
Kieku xi ħadd tixtieq li ma jaqblux, li
forsi mhuwiex żmien tassew kostanti?

208
00:09:00,420 --> 00:09:03,600
F'liema sens jista printf-ġirja
żmien, fil-fatt istampar string fuq

209
00:09:03,600 --> 00:09:05,580
l-iskrin, tkun xi ħaġa
minbarra kostanti.

210
00:09:05,580 --> 00:09:07,860
>> UDJENZA: [inaudible].

211
00:09:07,860 --> 00:09:08,230
>> DAVID Malan: Yeah.

212
00:09:08,230 --> 00:09:09,300
Għalhekk jiddependi fuq il-perspettiva tagħna.

213
00:09:09,300 --> 00:09:13,390
Jekk għandna attwalment think tal-input li
printf bħala l-sekwenza, u

214
00:09:13,390 --> 00:09:16,380
għalhekk aħna jitkejjel id-daqs ta 'dak
input skond it-tul tagħha - so ejja sejħa

215
00:09:16,380 --> 00:09:17,780
li tul un kif ukoll -

216
00:09:17,780 --> 00:09:21,990
forsi, printf innifsu O kbira ta 'n
minħabba li għaddej biex tieħu inti n passi

217
00:09:21,990 --> 00:09:24,750
li jistampa kull wieħed minn dawn n
karattri, aktar probabbli.

218
00:09:24,750 --> 00:09:27,730
Mill-inqas sal-punt li aħna nassumu
li forsi huwa għall-użu ta 'loop

219
00:09:27,730 --> 00:09:28,560
taħt il-barnuża.

220
00:09:28,560 --> 00:09:30,860
>> Imma rridu naraw li tħares lejn dak
kodiċi jifhmu aħjar.

221
00:09:30,860 --> 00:09:33,650
U fil-fatt, ladarba inti guys tibda
analiżi algoritmi tiegħek, inti ser

222
00:09:33,650 --> 00:09:34,900
litteralment tagħmel dan.

223
00:09:34,900 --> 00:09:37,765
Sort ta boċċa kodiċi tiegħek u think
dwar - id-dritt, I jkollhom din loop

224
00:09:37,765 --> 00:09:41,870
hawn jew għandi loops nested hawn,
li għaddej biex tagħmel affarijiet n b'n drabi,

225
00:09:41,870 --> 00:09:46,050
u inti tista sort tar-raġuni tiegħek mod
permezz tal-kodiċi, anki jekk huwa

226
00:09:46,050 --> 00:09:47,980
pseudocode u mhux il-kodiċi attwali.

227
00:09:47,980 --> 00:09:49,730
>> Allura dak dwar omega 'n kwadru?

228
00:09:49,730 --> 00:09:53,582
Dak li kien algoritmu li fl-aħjar
każ, xorta ħa n passi kwadrati?

229
00:09:53,582 --> 00:09:54,014
Yeah?

230
00:09:54,014 --> 00:09:54,880
>> UDJENZA: [inaudible].

231
00:09:54,880 --> 00:09:55,900
>> DAVID Malan: Allura sort għażla.

232
00:09:55,900 --> 00:09:59,150
Għaliex f'dak il-problema verament imnaqqsa
l-fatt li għal darb'oħra, jien ma nafx

233
00:09:59,150 --> 00:10:02,600
Stajt sabu l-iżgħar kurrenti tagħhom sakemm
Stajt ċċekkjati l-elementi kollha darn.

234
00:10:02,600 --> 00:10:08,050
Allura omega ', ngħidu aħna, n, aħna
biss ħarāet bil wieħed.

235
00:10:08,050 --> 00:10:09,300
Sort Inserzjoni.

236
00:10:09,300 --> 00:10:12,370
Jekk il-lista jiġri li jiġu magħżula
diġà, fl-aħjar każ aħna biss għandhom

237
00:10:12,370 --> 00:10:15,090
jagħmlu pass wieħed permezz tagħha,
f'liema punt aħna qed żgur.

238
00:10:15,090 --> 00:10:17,890
U allura li jista 'jingħad
biex tkun lineari, għall-żgur.

239
00:10:17,890 --> 00:10:20,570
>> What about omega-1?

240
00:10:20,570 --> 00:10:23,790
X'inhuma, fl-aħjar każ, jista 'jieħu
numru kostanti ta 'passi?

241
00:10:23,790 --> 00:10:27,220
Tfittxija Għalhekk lineari, jekk inti biss tikseb xxurtjati
u l-element li qed tfittex

242
00:10:27,220 --> 00:10:31,000
huwa dritt fil-bidu tal-lista,
jekk dan huwa fejn int tibda tiegħek

243
00:10:31,000 --> 00:10:33,070
lineari traversal ta dik il-lista.

244
00:10:33,070 --> 00:10:35,180
>> U dan huwa minnu ta '
numru ta 'affarijiet.

245
00:10:35,180 --> 00:10:37,660
Per eżempju, anke binarju
tfittxija hija omega ta '1.

246
00:10:37,660 --> 00:10:40,310
Għaliex dak li jekk ikollok verament darn
xortik tajba u smack dab-fin-nofs ta '

247
00:10:40,310 --> 00:10:42,950
firxa tiegħek huwa n-numru
qed tfittex?

248
00:10:42,950 --> 00:10:45,730
Allura inti tista 'tikseb xortik tajba hemmhekk, kif ukoll.

249
00:10:45,730 --> 00:10:49,190
>> Dan wieħed, fl-aħħarnett, omega 'n log n.

250
00:10:49,190 --> 00:10:52,573
Allura n log n, aħna ma verament
jitkellmu dwar għada, iżda -

251
00:10:52,573 --> 00:10:53,300
>> UDJENZA: Jingħaqdu sort?

252
00:10:53,300 --> 00:10:53,960
>> DAVID Malan: sort Merge.

253
00:10:53,960 --> 00:10:56,920
Dan kien l-aħħar darba cliffhanger ta,
fejn aħna propost, u aħna wera

254
00:10:56,920 --> 00:10:58,600
viżwalment, li hemm algoritmi.

255
00:10:58,600 --> 00:11:02,470
U jingħaqdu tip ta 'waħda biss bħal
algoritmu li huwa fundamentalment aktar mgħaġġel

256
00:11:02,470 --> 00:11:03,450
minn xi wħud minn dawn guys oħra.

257
00:11:03,450 --> 00:11:07,800
Fil-fatt, jingħaqdu qasir mhux biss fil-
aħjar każ n n log, fl-agħar

258
00:11:07,800 --> 00:11:09,460
n log n każ.

259
00:11:09,460 --> 00:11:14,540
U meta jkollok dan koinċidenza ta '
omega u big O huma l-istess ħaġa?

260
00:11:14,540 --> 00:11:17,310
Aħna fil-fatt jistgħu jiddeskrivu li bħala x'hemm
imsejħa theta, għalkemm huwa

261
00:11:17,310 --> 00:11:18,220
ftit inqas komuni.

262
00:11:18,220 --> 00:11:21,730
Iżda dan ifisser biss l-żewġ limiti,
f'dan il-każ, huma l-istess.

263
00:11:21,730 --> 00:11:25,770
>> Allura jingħaqdu sort, dan xi
verament jsarrafx biss fl għalina?

264
00:11:25,770 --> 00:11:27,000
Ukoll, mfakkra l-motivazzjoni.

265
00:11:27,000 --> 00:11:30,340
Let me pull up animazzjoni ieħor li
aħna ma nħarsu lejn l-aħħar darba.

266
00:11:30,340 --> 00:11:33,390
Dan wieħed, l-istess idea, iżda
huwa ftit akbar.

267
00:11:33,390 --> 00:11:36,160
U jien ser imorru quddiem u tfakkar
ewwel - għandna sort inserzjoni fuq

268
00:11:36,160 --> 00:11:39,410
fuq ix-xellug ta 'fuq, imbagħad sort għażla,
sort bużżieqa, koppja ta 'tipi oħra -

269
00:11:39,410 --> 00:11:42,670
qoxra u malajr - li aħna ma tkellmu
dwar, u borġ u jingħaqdu tip.

270
00:11:42,670 --> 00:11:47,090
>> Allura mill-inqas tipprova li tiffoka għajnejn tiegħek fuq
l-ewwel tliet fuq ix-xellug u mbagħad

271
00:11:47,090 --> 00:11:49,120
jingħaqdu sort meta I ikklikkja
dan vleġġa ħadra.

272
00:11:49,120 --> 00:11:51,900
Imma jien ser let kull wieħed minnhom run, biss biex
jagħtuk sens tad-diversità ta '

273
00:11:51,900 --> 00:11:53,980
algoritmi li jeżistu fid-dinja.

274
00:11:53,980 --> 00:11:56,180
Jien ser let din ir-run
għal ftit ftit sekondi.

275
00:11:56,180 --> 00:11:59,640
U jekk inti tiffoka għajnejn tiegħek - pick
algoritmu, tiffoka fuq dan għal ftit

276
00:11:59,640 --> 00:12:02,970
sekondi - inti ser tibda tara l-
mudell li huwa ta 'implimentazzjoni.

277
00:12:02,970 --> 00:12:04,530
>> Jingħaqdu sort, avviż, isir.

278
00:12:04,530 --> 00:12:06,430
Sort borġ, sort malajr, qoxra -

279
00:12:06,430 --> 00:12:09,480
hekk jidher aħna introdotti t-tliet
agħar algoritmi aħħar ġimgħa.

280
00:12:09,480 --> 00:12:12,960
Iżda li tajjeb li aħna qed hawn illum biex
tħares lejn sort jingħaqdu, li hija waħda ta '

281
00:12:12,960 --> 00:12:16,500
dawk eħfef huwa li tħares lejn, anke
għalkemm hija probabbilment se liwja moħħok

282
00:12:16,500 --> 00:12:17,490
biss ftit.

283
00:12:17,490 --> 00:12:21,130
Hawnhekk nistgħu naraw biss kemm
sort għażla sucks.

284
00:12:21,130 --> 00:12:24,600
>> Iżda fuq in-naħa flip, huwa
verament faċli biex jiġi implimentat.

285
00:12:24,600 --> 00:12:28,160
U forsi għal P Set 3, li wieħed mill-
algoritmi għażilt biex jimplimentaw

286
00:12:28,160 --> 00:12:28,960
għall-edizzjoni standard.

287
00:12:28,960 --> 00:12:30,970
Perfettament multa, perfettament korretta.

288
00:12:30,970 --> 00:12:35,210
>> Iżda għal darb'oħra, bħala n gets kbira, jekk inti
jagħżlu li jimplimentaw l-algoritmu aktar malajr

289
00:12:35,210 --> 00:12:39,020
simili jingħaqdu sort, odds huma akbar u
inputs akbar, il-kodiċi tiegħek hija biss

290
00:12:39,020 --> 00:12:39,800
ser jimxu aktar mgħaġġel.

291
00:12:39,800 --> 00:12:41,090
Your website għaddej biex jaħdmu aħjar.

292
00:12:41,090 --> 00:12:42,650
Utenti tiegħek ser ikunu kuntenti.

293
00:12:42,650 --> 00:12:45,280
U għalhekk hemm dawn l-effetti
li attwalment jagħti

294
00:12:45,280 --> 00:12:47,350
us xi fond maħsub.

295
00:12:47,350 --> 00:12:49,990
>> Mela ejja tagħti ħarsa lejn dak li jingħaqdu
sort huwa attwalment madwar kollha.

296
00:12:49,990 --> 00:12:52,992
Il-ħaġa jibred hija li jingħaqdu
sort huwa biss dan.

297
00:12:52,992 --> 00:12:56,300
Dan huwa, għal darb'oħra, dak li konna imsejħa
pseudocode, being pseudocode

298
00:12:56,300 --> 00:12:57,720
Sintassi Ingliż simili.

299
00:12:57,720 --> 00:12:59,890
U l-sempliċità hija
tip ta 'affaxxinanti.

300
00:12:59,890 --> 00:13:02,840
>> Allura fuq input ta 'elementi n - sabiex
ifisser biss, hawn firxa.

301
00:13:02,840 --> 00:13:04,000
Huwa ltqajna affarijiet n fiha.

302
00:13:04,000 --> 00:13:05,370
Li kollox aħna qed tgħid hemmhekk.

303
00:13:05,370 --> 00:13:07,560
>> Jekk n huwa inqas minn 2, ritorn.

304
00:13:07,560 --> 00:13:08,640
Allura dan huwa biss il-każ trivjali.

305
00:13:08,640 --> 00:13:12,580
Jekk n huwa inqas minn 2, allura ovvjament huwa
1 jew 0, f'liema każ il-ħaġa

306
00:13:12,580 --> 00:13:14,780
huwa diġà magħżula jew kważi ma jeżistix,
hekk biss ritorn.

307
00:13:14,780 --> 00:13:15,900
M'hemm xejn li jagħmlu.

308
00:13:15,900 --> 00:13:18,360
Allura dak każ sempliċi ġewwieni off.

309
00:13:18,360 --> 00:13:20,110
>> Else, għandna tliet passi.

310
00:13:20,110 --> 00:13:23,650
Sort in-nofs xellugi tal-elementi, sort
il-nofs tal-lemin ta 'l-elementi,

311
00:13:23,650 --> 00:13:26,650
u mbagħad jingħaqdu l-nofsijiet magħżula.

312
00:13:26,650 --> 00:13:29,400
X'hemm interessanti hawnhekk huwa li
Jien tip ta 'punting, right?

313
00:13:29,400 --> 00:13:32,300
Hemm tip ta 'definizzjoni ċirkolari
għal dan algoritmu.

314
00:13:32,300 --> 00:13:35,986
F'liema sens huwa dan l-algoritmu
ċirkolari definizzjoni?

315
00:13:35,986 --> 00:13:37,850
>> UDJENZA: [inaudible].

316
00:13:37,850 --> 00:13:41,670
>> DAVID Malan: Yeah, algoritmu issortjar tiegħi,
tnejn mill-passi tiegħu huma "sort

317
00:13:41,670 --> 00:13:44,640
xi ħaġa. "U hekk li iqajjem il-
kwistjoni, ukoll, dak li jien ser tuża

318
00:13:44,640 --> 00:13:46,460
biex issolvi l-nofs tax-xellug
u l-half-dritt?

319
00:13:46,460 --> 00:13:49,600
U l-sbuħija hawnhekk hija li anke jekk
għal darb'oħra, dan huwa l-mind-liwi

320
00:13:49,600 --> 00:13:54,030
parti potenzjalment, tista 'tuża istess
algoritmu biex isolvi l-nofs tax-xellug.

321
00:13:54,030 --> 00:13:54,700
>> Imma stenna minuta.

322
00:13:54,700 --> 00:13:57,070
Meta inti qed told biex isolvi l-
nofs tax-xellug, liema huma ż-żewġ

323
00:13:57,070 --> 00:13:58,240
passi se tkun li jmiss?

324
00:13:58,240 --> 00:14:00,550
Aħna ser issolvi in-nofs xellugi tal-
nofs tax-xellug u d-dritt

325
00:14:00,550 --> 00:14:01,420
nofs in-nofs xellugi.

326
00:14:01,420 --> 00:14:04,430
Indanna, kif nista sort dawk iż-żewġ
nofsijiet jew kwarti,, issa?

327
00:14:04,430 --> 00:14:05,260
>> Imma dak li OK.

328
00:14:05,260 --> 00:14:07,830
Għandna algoritmu issortjar hawn.

329
00:14:07,830 --> 00:14:10,660
U anki jekk inti tista 'ninkwetaw
ewwel dan huwa tip ta 'infinita

330
00:14:10,660 --> 00:14:12,780
loop, huwa ċiklu li qatt ma
ser jispiċċaw - huwa ser

331
00:14:12,780 --> 00:14:15,770
tispiċċa ladarba x'jiġri?

332
00:14:15,770 --> 00:14:16,970
Ladarba n huwa inqas minn 2.

333
00:14:16,970 --> 00:14:19,180
Li eventwalment se jiġri,
għaliex jekk inti żżomm tnaqqis bin-nofs u

334
00:14:19,180 --> 00:14:23,020
tnaqqis bin-nofs fl naqset bin-nofs f'dawn nofsijiet, żgur
eventwalment int ser jispiċċaw

335
00:14:23,020 --> 00:14:25,350
up bil biss 1 jew 0 elementi.

336
00:14:25,350 --> 00:14:28,500
F'liema punt, dan algoritmu
tgħid li inti qed isir.

337
00:14:28,500 --> 00:14:31,020
>> Allura l-magic reali f'dan
algoritmu jidher li jkun

338
00:14:31,020 --> 00:14:33,470
dak il-pass finali, li qed jingħaqdu.

339
00:14:33,470 --> 00:14:37,190
Li l-idea sempliċi biss jingħaqdu żewġ
affarijiet, dan huwa dak li finalment għaddej

340
00:14:37,190 --> 00:14:40,920
biex inessu biex issolvi firxa ta ',
ejja ngħidu, tmien elementi.

341
00:14:40,920 --> 00:14:44,410
So I jkollhom tmien blalen istress aktar up
hawn, tmien biċċiet tal-karti, u wieħed

342
00:14:44,410 --> 00:14:45,500
Google ħġieġ -

343
00:14:45,500 --> 00:14:46,140
li nasal biex iżommu.

344
00:14:46,140 --> 00:14:46,960
>> [Daħk]

345
00:14:46,960 --> 00:14:48,970
>> DAVID Malan: Jekk aħna nkunu nistgħu nieħdu tmien
voluntiera, u ejja ara jekk nistgħu

346
00:14:48,970 --> 00:14:51,430
jilagħbu din out, so.

347
00:14:51,430 --> 00:14:52,500
Ara naqra, OK.

348
00:14:52,500 --> 00:14:53,565
Computer xjenza huwa jkollna gost.

349
00:14:53,565 --> 00:14:54,320
Kull dritt.

350
00:14:54,320 --> 00:14:57,770
Allura kif dwarek tlieta,
idejn akbar up hemm.

351
00:14:57,770 --> 00:14:58,580
Erba fid-dahar.

352
00:14:58,580 --> 00:15:02,220
U kif madwar aħna ser nagħmlu għalik
tliet f'dan ringiela?

353
00:15:02,220 --> 00:15:03,390
U erba 'fil-front.

354
00:15:03,390 --> 00:15:04,920
Allura inti tmienja, come fuq up.

355
00:15:04,920 --> 00:15:12,060
>> [Daħk]

356
00:15:12,060 --> 00:15:13,450
>> DAVID Malan: Jien attwalment
mhux ċert dak li hu.

357
00:15:13,450 --> 00:15:14,810
Huwa l-blalen istress?

358
00:15:14,810 --> 00:15:16,510
Il-lampi desk?

359
00:15:16,510 --> 00:15:18,650
Il-materjal?

360
00:15:18,650 --> 00:15:19,680
L-internet?

361
00:15:19,680 --> 00:15:20,160
>> OK.

362
00:15:20,160 --> 00:15:21,310
Allura ġejjin fuq up.

363
00:15:21,310 --> 00:15:22,310
Min jixtieq -

364
00:15:22,310 --> 00:15:23,570
iżommu ġejjin up.

365
00:15:23,570 --> 00:15:24,240
Ejja ara.

366
00:15:24,240 --> 00:15:26,460
U dan tpoġġik post -

367
00:15:26,460 --> 00:15:27,940
int f'post wieħed.

368
00:15:27,940 --> 00:15:28,670
Uh-oh, stenna minuta.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - oh, tajba.

370
00:15:30,760 --> 00:15:31,310
Kull dritt, aħna qed tajba.

371
00:15:31,310 --> 00:15:35,130
Kull dritt, sabiex kulħadd ikollu sede,
iżda mhux fuq il-Google Glass.

372
00:15:35,130 --> 00:15:36,475
Let me kju dawn il-up.

373
00:15:36,475 --> 00:15:37,115
X'hemm isem tiegħek?

374
00:15:37,115 --> 00:15:37,440
>> Michelle: Michelle.

375
00:15:37,440 --> 00:15:38,090
>> DAVID Malan: Michelle?

376
00:15:38,090 --> 00:15:42,000
Kull dritt, ikollok lill-dehra
l-geek, jekk dan huwa OK.

377
00:15:42,000 --> 00:15:44,625
Well, I do wisq, I suppose,
għal ftit mument.

378
00:15:44,625 --> 00:15:45,875
Kull dritt, standby.

379
00:15:45,875 --> 00:15:48,510

380
00:15:48,510 --> 00:15:50,950
Imxejna ġiet tipprova toħroġ bi
użu każ għall Google ħġieġ, u aħna

381
00:15:50,950 --> 00:15:53,750
ħsibt li jkun gost li biss tagħmel
dan meta n-nies huma onstage.

382
00:15:53,750 --> 00:15:57,120
Aħna se jirreġistraw id-dinja
mill-perspettiva tagħhom.

383
00:15:57,120 --> 00:15:58,410
Kull dritt.

384
00:15:58,410 --> 00:15:59,830
Mhux probabbilment dak Google maħsub.

385
00:15:59,830 --> 00:16:02,260
Kull dritt, jekk inti ma mind liebes
dan għall-minuti skomdi li ġejjin,

386
00:16:02,260 --> 00:16:03,150
li tkun isbaħ.

387
00:16:03,150 --> 00:16:08,620
>> Kull dritt, hekk aħna hawn firxa ta '
elementi, u li array, bħala kull l-

388
00:16:08,620 --> 00:16:11,480
biċċiet tal-karti f'dawn folks "
idejn, bħalissa jintbagħtu f'volumi kbar.

389
00:16:11,480 --> 00:16:12,050
>> Michelle: Oh, li hekk stramb.

390
00:16:12,050 --> 00:16:12,810
>> DAVID Malan: Huwa pretty ħafna każwali.

391
00:16:12,810 --> 00:16:15,760
U fi ftit mument, aħna qed tmur biex tipprova
biex jimplimentaw jingħaqdu sort flimkien

392
00:16:15,760 --> 00:16:17,950
u ara fejn dik ewlenija hija ħarsa.

393
00:16:17,950 --> 00:16:21,970
U l-trick hawnhekk ma sort jingħaqdu huwa
xi ħaġa li aħna ma jassumi s'issa.

394
00:16:21,970 --> 00:16:24,030
Għandna attwalment bżonn xi
spazju addizzjonali.

395
00:16:24,030 --> 00:16:26,650
Allura dak li għaddej biex tkun partikolarment
interessanti dwar dan hija li dawn

396
00:16:26,650 --> 00:16:29,270
guys huma ser jiċċaqalqu madwar ftit
bit, għaliex jien ser jassumi li

397
00:16:29,270 --> 00:16:31,880
hemm firxa żejda ta 'spazju,
ngħidu, id-dritt warajhom.

398
00:16:31,880 --> 00:16:34,570
>> Mela jekk dawn qed wara president tagħhom,
dak l-firxa sekondarja.

399
00:16:34,570 --> 00:16:36,960
Jekk dawn qed bilqiegħda hawn, li l-
l-array primarja.

400
00:16:36,960 --> 00:16:40,170
Iżda din hija riżorsa li għandna
jkunux ingranati s'issa ma bużżieqa

401
00:16:40,170 --> 00:16:42,040
sort, ma sort għażla,
ma sort inserzjoni.

402
00:16:42,040 --> 00:16:44,600
Recall aħħar ġimgħa, kulħadd biss
tip ta 'shuffled fis-seħħ.

403
00:16:44,600 --> 00:16:46,840
Huma ma tuża kwalunkwe memorja addizzjonali.

404
00:16:46,840 --> 00:16:49,310
Għamilna kamra għal nies minn
jiċċaqalqu nies madwar.

405
00:16:49,310 --> 00:16:50,580
>> Allura dan huwa ħarsa ewlieni, wisq.

406
00:16:50,580 --> 00:16:53,410
Hemm dan il-kompromess, b'mod ġenerali
xjenza tal-kompjuter, ta 'riżorsi.

407
00:16:53,410 --> 00:16:55,800
Jekk inti tixtieq li tħaffef xi ħaġa
bħal ħin, int ser

408
00:16:55,800 --> 00:16:56,900
jkollhom iħallsu prezz.

409
00:16:56,900 --> 00:17:00,750
U waħda minn dawk il-prezzijiet ħafna drabi hija
ispazju, l-ammont tal-memorja jew hard

410
00:17:00,750 --> 00:17:01,700
disk ispazju li inti qed tuża.

411
00:17:01,700 --> 00:17:03,640
Or, franchement, l-ammont
ta 'żmien programmer.

412
00:17:03,640 --> 00:17:06,700
Kemm ħin li tieħu inti, il-bniedem,
li fil-fatt jimplimentaw ftit aktar

413
00:17:06,700 --> 00:17:07,829
algoritmu kkumplikata.

414
00:17:07,829 --> 00:17:09,760
Iżda għal-lum, il-kompromess
huwa żmien u l-ispazju.

415
00:17:09,760 --> 00:17:11,930
>> Hekk jekk inti guys tista 'biss istiva up tiegħek
numri hekk nistgħu naraw li int

416
00:17:11,930 --> 00:17:15,839
tabilħaqq tqabbil 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
Eċċellenti.

418
00:17:16,599 --> 00:17:19,520
Hekk jien ser tipprova orchestrate
affarijiet, jekk inti guys tista 'sempliċement

419
00:17:19,520 --> 00:17:21,800
segwiex tiegħi hawn.

420
00:17:21,800 --> 00:17:26,650
>> So I am ser jimplimentaw, l-ewwel, il-
ewwel pass tal-pseudocode, li huwa

421
00:17:26,650 --> 00:17:29,440
fuq l-input ta 'elementi n, jekk n hija
inqas minn 2, mbagħad jirritornaw.

422
00:17:29,440 --> 00:17:31,370
Ovvjament, li ma
japplikaw, hekk aħna jimxu fuq.

423
00:17:31,370 --> 00:17:33,340
Allura sort in-nofs xellugi tal-elementi.

424
00:17:33,340 --> 00:17:36,220
Allura dan ifisser li jien ser tiffoka tiegħi
attenzjoni għal ftit mument fuq dawn

425
00:17:36,220 --> 00:17:37,310
erba guys hawn.

426
00:17:37,310 --> 00:17:39,774
Kull dritt, x'għandi nagħmel jmiss do?

427
00:17:39,774 --> 00:17:40,570
>> UDJENZA: Sort in-nofs xellugi.

428
00:17:40,570 --> 00:17:42,780
>> DAVID Malan: Allura issa għandi biex issolvi
in-nofs xellugi ta 'dawn guys.

429
00:17:42,780 --> 00:17:45,580
Minħabba darb'oħra, jassumi lilek innifsek il-
għan huwa biex issolvi l-nofs tax-xellug.

430
00:17:45,580 --> 00:17:46,440
Kif inti tagħmel dan?

431
00:17:46,440 --> 00:17:49,140
Just segwi l-istruzzjonijiet, anke
jekk aħna qed tagħmel dan mill-ġdid.

432
00:17:49,140 --> 00:17:50,160
Allura sort in-nofs xellugi.

433
00:17:50,160 --> 00:17:52,030
Issa jien issortjar dawn iż-żewġ guys.

434
00:17:52,030 --> 00:17:53,563
Dak li jiġi jmiss?

435
00:17:53,563 --> 00:17:54,510
>> UDJENZA: Sort in-nofs xellugi.

436
00:17:54,510 --> 00:17:55,460
>> DAVID Malan: sort in-nofs xellugi.

437
00:17:55,460 --> 00:18:00,680
Allura issa dawn, dan is-sit hawn,
hija lista ta 'daqs 1.

438
00:18:00,680 --> 00:18:01,365
U x'hemm isem tiegħek mill-ġdid?

439
00:18:01,365 --> 00:18:02,390
>> PRINCESS DAISY: Princess Daisy.

440
00:18:02,390 --> 00:18:03,690
>> DAVID Malan: Princess Daisy huwa hawnhekk.

441
00:18:03,690 --> 00:18:07,470
U hekk hi huwa diġà magħżula, minħabba
il-lista hija ta 'daqs 1.

442
00:18:07,470 --> 00:18:09,490
What do I do jmiss?

443
00:18:09,490 --> 00:18:13,680
OK, lura, għaliex din il-lista ta '
daqs 1, li hija inqas minn 2.

444
00:18:13,680 --> 00:18:14,320
Imbagħad x'inhu l-pass li jmiss?

445
00:18:14,320 --> 00:18:17,490
U issa għandek tip ta '
wieħed imur lura fil moħħok.

446
00:18:17,490 --> 00:18:19,340
>> Tip li l-nofs tal-lemin, li tkun -

447
00:18:19,340 --> 00:18:19,570
dak l-isem tiegħek?

448
00:18:19,570 --> 00:18:20,220
>> LINDA: Linda.

449
00:18:20,220 --> 00:18:20,980
>> DAVID Malan: Linda.

450
00:18:20,980 --> 00:18:23,210
U hekk dak li nagħmlu issa li
għandna lista ta 'daqs 1?

451
00:18:23,210 --> 00:18:24,440
>> UDJENZA: Ritorn.

452
00:18:24,440 --> 00:18:24,760
>> DAVID Malan: Bir-reqqa.

453
00:18:24,760 --> 00:18:29,540
Nerġgħu lura ewwel, u issa t-tielet
pass - u jekk I tip ta 'juru dan billi

454
00:18:29,540 --> 00:18:33,490
tħaddan iż-żewġ sedili issa, issa I
għandek jingħaqdu dawn iż-żewġ elementi.

455
00:18:33,490 --> 00:18:35,530
Allura issa sfortunatament, l-elementi
huma out of order.

456
00:18:35,530 --> 00:18:39,920
Iżda li meta l-proċess li qed jingħaqdu
tibda tikseb konvinċenti.

457
00:18:39,920 --> 00:18:42,410
>> Hekk jekk inti guys tista 'toqgħod up għal ftit
mument, jien ser bżonn inti, fil-

458
00:18:42,410 --> 00:18:44,170
mument, li pass wara president tiegħek.

459
00:18:44,170 --> 00:18:46,480
U jekk Linda, għaliex 2 huwa
iżgħar minn 4, għaliex ma

460
00:18:46,480 --> 00:18:48,130
inti come madwar l-ewwel?

461
00:18:48,130 --> 00:18:48,690
Jibqgħu hemm.

462
00:18:48,690 --> 00:18:50,520
Allura Linda, inti come madwar l-ewwel.

463
00:18:50,520 --> 00:18:53,820
>> Issa fir-realtà jekk huwa biss firxa
nistgħu biss jiċċaqalqu tagħha fil-ħin reali

464
00:18:53,820 --> 00:18:55,360
minn dan il-presidenza għal dan il-post.

465
00:18:55,360 --> 00:18:57,770
Allura immaġina li ħa xi kostanti
numru ta 'passi 1.

466
00:18:57,770 --> 00:18:58,480
U issa -

467
00:18:58,480 --> 00:19:01,490
imma għandna bżonn li tpoġġi lilek
l-ewwel post hawn.

468
00:19:01,490 --> 00:19:03,930
>> U issa jekk inti tista come madwar,
kif ukoll, aħna qed tmur biex

469
00:19:03,930 --> 00:19:06,300
tkun post tnejn.

470
00:19:06,300 --> 00:19:09,120
U anki jekk dan iħoss simili huwa
tieħu filwaqt, x'hemm sbieħ issa huwa

471
00:19:09,120 --> 00:19:14,710
li l-nofs tax-xellug tal-
nofs tax-xellug huwa issa magħżula.

472
00:19:14,710 --> 00:19:18,010
Allura dak li kien l-pass li jmiss, jekk aħna issa
Rewind aktar fl-istorja?

473
00:19:18,010 --> 00:19:18,980
>> UDJENZA: nofs Dritt.

474
00:19:18,980 --> 00:19:19,900
>> DAVID Malan: sort l-nofs tal-lemin.

475
00:19:19,900 --> 00:19:21,320
Allura inti guys għandek tagħmel dan, ukoll.

476
00:19:21,320 --> 00:19:23,510
Hekk jekk inti tista 'stand up
għal ftit mument?

477
00:19:23,510 --> 00:19:25,192
U x'hemm isem tiegħek?

478
00:19:25,192 --> 00:19:25,540
>> JESS: Jess.

479
00:19:25,540 --> 00:19:25,870
>> DAVID Malan: Jess.

480
00:19:25,870 --> 00:19:29,720
OK, hekk Jess issa huwa ix-xellug
nofs il-nofs tal-lemin.

481
00:19:29,720 --> 00:19:31,400
U hekk hi lista ta 'daqs 1.

482
00:19:31,400 --> 00:19:32,380
Hi ovvjament magħżula.

483
00:19:32,380 --> 00:19:33,070
U l-isem tiegħek mill-ġdid?

484
00:19:33,070 --> 00:19:33,630
>> Michelle: Michelle.

485
00:19:33,630 --> 00:19:35,340
>> DAVID Malan: Michelle hija ovvjament
lista ta 'daqs 1.

486
00:19:35,340 --> 00:19:36,050
Hi diġà magħżula.

487
00:19:36,050 --> 00:19:38,690
Allura issa l-magic jiġri,
il-proċess li qed jingħaqdu.

488
00:19:38,690 --> 00:19:39,790
Hekk li għaddej biex jasal l-ewwel?

489
00:19:39,790 --> 00:19:41,560
Ovvjament Michelle.

490
00:19:41,560 --> 00:19:43,280
Hekk jekk inti tista come madwar lura.

491
00:19:43,280 --> 00:19:47,090
L-ispazju li għandna disponibbli għall tagħha issa
huwa dritt wara dan il-presidenza hawn.

492
00:19:47,090 --> 00:19:51,580
U issa jekk inti tista 'terga' lura kif ukoll,
issa għandna, tkun ċara, żewġ

493
00:19:51,580 --> 00:19:53,810
nofsijiet, b'kull wieħed daqs 2 -

494
00:19:53,810 --> 00:19:57,090
u biss għall-finijiet rappreżentazzjoni tal, jekk inti
tista 'tagħmel xi ftit ta' spazju -

495
00:19:57,090 --> 00:19:59,780
waħda xellug nofs hawn, waħda
nofs tal-lemin hawn.

496
00:19:59,780 --> 00:20:01,160
>> Rewind aktar fl-istorja.

497
00:20:01,160 --> 00:20:02,270
X'inhu pass huwa li jmiss?

498
00:20:02,270 --> 00:20:03,030
>> UDJENZA: Jingħaqdu.

499
00:20:03,030 --> 00:20:04,160
>> DAVID Malan: Allura issa għandna biex jingħaqdu.

500
00:20:04,160 --> 00:20:07,490
Allura OK, hekk issa, Thankfully, aħna
biss jinħelsu erba siġġijiet.

501
00:20:07,490 --> 00:20:11,480
Allura aħna ħadthom użati darbtejn kemm memorja, iżda
nistgħu nagħtu flip-flopping bejn

502
00:20:11,480 --> 00:20:12,330
iż-żewġ arrays.

503
00:20:12,330 --> 00:20:14,190
Allura liema numru huwa li jasal l-ewwel?

504
00:20:14,190 --> 00:20:14,850
Allura Michelle, ovvjament.

505
00:20:14,850 --> 00:20:16,680
Allura ġejjin madwar u jieħdu
sedil tiegħek hawn.

506
00:20:16,680 --> 00:20:19,120
U allura numru 2 hija ovvjament
jmiss, sabiex inti jiġu hawn.

507
00:20:19,120 --> 00:20:21,520
Numru 4, numru 6.

508
00:20:21,520 --> 00:20:23,390
U għal darb'oħra, anki jekk hemm
Ftit ftit ta 'mixi involuti,

509
00:20:23,390 --> 00:20:26,010
verament, dawn jista 'jiġri istantanjament,
billi jiċċaqilqu waħda -

510
00:20:26,010 --> 00:20:26,880
OK, ukoll rwol.

511
00:20:26,880 --> 00:20:28,350
>> [Daħk]

512
00:20:28,350 --> 00:20:29,680
>> DAVID Malan: U issa aħna qed
fil-forma pjuttost tajba.

513
00:20:29,680 --> 00:20:34,910
In-nofs xellugi tal-kollu
input issa ġiet magħżula.

514
00:20:34,910 --> 00:20:37,370
Kull dritt, hekk dawn guys kellhom
l-vantaġġ ta 'tiegħi -

515
00:20:37,370 --> 00:20:40,340
kif ma kien jispiċċaw l-bniet fuq il-
xellug u l-subien fuq il-lemin?

516
00:20:40,340 --> 00:20:42,450
>> OK, hekk guys "dawran issa.

517
00:20:42,450 --> 00:20:44,680
So I mhux se jimxu miegħek permezz
dawn il-passi.

518
00:20:44,680 --> 00:20:46,550
Ser naraw jekk nistgħu terġa 'tapplika
l-istess pseudocode.

519
00:20:46,550 --> 00:20:50,050
Jekk inti tixtieq li tmur quddiem u stand up,
u inti guys, let me jagħtuk l-mic.

520
00:20:50,050 --> 00:20:52,990
Ara jekk inti ma tistax tirreplika dak
aħna biss ma hawn fuq l-

521
00:20:52,990 --> 00:20:53,880
tarf l-ieħor tal-lista.

522
00:20:53,880 --> 00:20:59,530
Li jeħtieġ li jitkellem l-ewwel,
ibbażata fuq l-algoritmu?

523
00:20:59,530 --> 00:21:03,210
Allura jispjegaw dak li qed tagħmel qabel
ma tagħmel xi movimenti sieq.

524
00:21:03,210 --> 00:21:05,930
>> SPEAKER 1: Kull dritt, hekk peress li
I am in-nofs xellugi tal-

525
00:21:05,930 --> 00:21:07,790
nofs tax-xellug, I-ritorn.

526
00:21:07,790 --> 00:21:08,730
Dritt?

527
00:21:08,730 --> 00:21:09,250
>> DAVID Malan: Tajba.

528
00:21:09,250 --> 00:21:10,350
>> SPEAKER 1: U mbagħad -

529
00:21:10,350 --> 00:21:11,800
>> DAVID Malan: Min jagħmel
l-mic mur jmiss?

530
00:21:11,800 --> 00:21:12,920
>> SPEAKER 1: numru jmiss.

531
00:21:12,920 --> 00:21:14,720
>> SPEAKER 2: Hekk jien il-nofs tal-lemin
tal-nofs tax-xellug tal-

532
00:21:14,720 --> 00:21:17,830
nofs tax-xellug, u I-ritorn.

533
00:21:17,830 --> 00:21:18,050
>> DAVID Malan: Tajba.

534
00:21:18,050 --> 00:21:18,550
Inti tirritorna.

535
00:21:18,550 --> 00:21:21,855
Allura issa x'inhu l-up li jmiss għalik tnejn?

536
00:21:21,855 --> 00:21:23,740
>> SPEAKER 2: Irridu tara li l-iżgħar.

537
00:21:23,740 --> 00:21:24,200
>> DAVID Malan: Eżattament.

538
00:21:24,200 --> 00:21:24,940
Aħna rridu li jingħaqdu.

539
00:21:24,940 --> 00:21:27,590
L-ispazju aħna qed tmur biex jużaw biex jingħaqdu
inti fis, anki jekk dawn qed

540
00:21:27,590 --> 00:21:30,250
ovvjament diġà magħżula, aħna qed tmur
biex isegwu l-istess algoritmu.

541
00:21:30,250 --> 00:21:31,560
Hekk li tmur lura l-ewwel?

542
00:21:31,560 --> 00:21:35,720
Allura 3, u mbagħad 7.

543
00:21:35,720 --> 00:21:38,570
U issa l-mic tmur
għal dawn guys, OK?

544
00:21:38,570 --> 00:21:43,590
>> SPEAKER 3: Hekk jien il-nofs tal-lemin ta 'l-
nofs tax-xellug, u n tiegħi huwa inqas minn

545
00:21:43,590 --> 00:21:45,048
1, hekk jien biss se jgħaddu -

546
00:21:45,048 --> 00:21:46,380
>> DAVID Malan: Tajba.

547
00:21:46,380 --> 00:21:49,450
>> SPEAKER 4: Jien l-nofs tal-lemin ta 'l-
nofs tal-lemin ta 'l-nofs tal-lemin, u jien

548
00:21:49,450 --> 00:21:51,740
wkoll persuna waħda, hekk jien
ser jirritornaw.

549
00:21:51,740 --> 00:21:52,990
Allura issa aħna jingħaqdu.

550
00:21:52,990 --> 00:21:55,140

551
00:21:55,140 --> 00:21:56,150
>> SPEAKER 3: Allura immorru lura.

552
00:21:56,150 --> 00:21:57,160
>> DAVID Malan: Allura inti tmur fil-dahar.

553
00:21:57,160 --> 00:21:59,200
Allura 5 tmur l-ewwel, imbagħad 8.

554
00:21:59,200 --> 00:22:01,240
U issa udjenza, li hija l-
pass irridu issa Rewind

555
00:22:01,240 --> 00:22:02,200
lura fl-imħuħ tagħna?

556
00:22:02,200 --> 00:22:02,940
>> UDJENZA: Jingħaqdu.

557
00:22:02,940 --> 00:22:07,270
>> DAVID Malan: twaħħid nofs tax-xellug u tal-lemin
nofs in-nofs xellugi oriġinali.

558
00:22:07,270 --> 00:22:08,840
Allura issa -

559
00:22:08,840 --> 00:22:10,520
u biss biex dan ikun ċar,
jagħmlu ftit ta 'spazju

560
00:22:10,520 --> 00:22:11,690
bejn żewġ guys inti.

561
00:22:11,690 --> 00:22:13,800
Allura issa li l-żewġ listi,
xellug u lemin.

562
00:22:13,800 --> 00:22:18,320
Allura kif nistgħu issa jingħaqdu inti guys fis
l-filliera ta 'quddiem tas-sedili mill-ġdid?

563
00:22:18,320 --> 00:22:19,600
>> 3 tmur l-ewwel.

564
00:22:19,600 --> 00:22:20,850
Imbagħad 5, ovvjament.

565
00:22:20,850 --> 00:22:23,110

566
00:22:23,110 --> 00:22:27,330
Imbagħad 7, u issa 8.

567
00:22:27,330 --> 00:22:28,710
OK, u issa ninsabu?

568
00:22:28,710 --> 00:22:29,650
>> UDJENZA: Ma sarx.

569
00:22:29,650 --> 00:22:32,440
>> DAVID Malan: Ma sarx, għaliex
ovvjament, hemm pass wieħed fadal.

570
00:22:32,440 --> 00:22:35,720
Iżda għal darb'oħra, ir-raġuni jien jużaw dan
jargon bħal "Rewind fil moħħok,"

571
00:22:35,720 --> 00:22:37,160
huwa minħabba li tassew
dak li qed jiġri.

572
00:22:37,160 --> 00:22:39,610
Aħna ser kollha permezz ta 'dawn il-passi,
iżda aħna qed tip ta 'espressjonijiet fit għal

573
00:22:39,610 --> 00:22:42,480
mument, aktar profonda għadis fil-
algoritmu, jieqaf għal mument,

574
00:22:42,480 --> 00:22:45,840
għadis fond fil-algoritmu, u
issa għandna biex issolvi ta kontrina fil tagħna

575
00:22:45,840 --> 00:22:49,430
imħuħ u jneħħu kollha ta 'dawn saffi
li konna tip ta 'posposti.

576
00:22:49,430 --> 00:22:51,790
>> Allura issa għandna żewġ listi ta 'daqs 4.

577
00:22:51,790 --> 00:22:54,790
Jekk inti guys tista 'toqgħod up-aħħar darba
u jagħmlu daqsxejn ta 'spazju hawn biex

578
00:22:54,790 --> 00:22:57,230
jagħmluha ċara li dan huwa ix-xellug
nofs il-oriġinali, l-

579
00:22:57,230 --> 00:22:58,620
nofs tal-lemin ta 'l-oriġinali.

580
00:22:58,620 --> 00:23:01,060
Min hu l-ewwel numru li aħna
bżonn biex jiġbdu fil-dahar?

581
00:23:01,060 --> 00:23:01,870
Michelle, tal-kors.

582
00:23:01,870 --> 00:23:03,230
>> Allura aħna tpoġġi Michelle hawn.

583
00:23:03,230 --> 00:23:05,080
U li għandu numru 2?

584
00:23:05,080 --> 00:23:06,440
Numru 2 jixgħel lura ukoll.

585
00:23:06,440 --> 00:23:07,800
Numru 3?

586
00:23:07,800 --> 00:23:08,510
Eċċellenti.

587
00:23:08,510 --> 00:23:16,570
Numru 4, numru 5, numru 6,
numru 7, u n-numru 8.

588
00:23:16,570 --> 00:23:18,850
>> OK, hekk qisni ħafna
ta 'passi, għall-żgur.

589
00:23:18,850 --> 00:23:22,390
Imma issa ejja ara jekk aħna ma tista 'tikkonferma
tip ta 'intuwittivament li dan

590
00:23:22,390 --> 00:23:26,190
algoritmu fundamentalment, partikolarment fir-
n gets verament kbir, kif aħna stajt tidher

591
00:23:26,190 --> 00:23:29,170
mal-animazzjonijiet, huwa
fundamentalment aktar malajr.

592
00:23:29,170 --> 00:23:33,400
So I titlob dan algoritmu, fl-agħar
każ u anki fl-aħjar każ,

593
00:23:33,400 --> 00:23:36,160
huwa kbir O ta 'n darbiet log n.

594
00:23:36,160 --> 00:23:39,160
Dan huwa, hemm xi aspett ta 'dan
algoritmu li tieħu passi n, iżda

595
00:23:39,160 --> 00:23:43,110
hemm aspett ieħor x'imkien
li iterazzjoni, li looping, li

596
00:23:43,110 --> 00:23:44,410
jieħu passi log n.

597
00:23:44,410 --> 00:23:49,154
Nistgħu iqiegħed subgħajh tagħna fuq dak dawk
żewġ numri huma jirreferu għall?

598
00:23:49,154 --> 00:23:51,320
Well, meta -

599
00:23:51,320 --> 00:23:54,160
where'd l mic imorru?

600
00:23:54,160 --> 00:23:58,660
>> SPEAKER 1: Would il-log n tkun
tkissir us up f'żewġ -

601
00:23:58,660 --> 00:23:59,630
billi tiddividi żewġ, essenzjalment.

602
00:23:59,630 --> 00:24:00,120
>> DAVID Malan: Eżattament.

603
00:24:00,120 --> 00:24:03,000
Kwalunkwe ħin li naraw fi kwalunkwe algoritmu b'hekk
S'issa, hemm kien dan il-mudell ta '

604
00:24:03,000 --> 00:24:04,200
diviżjoni, diviżjoni, diviżjoni.

605
00:24:04,200 --> 00:24:05,700
U huwa tipikament mnaqqsa
għal xi ħaġa li

606
00:24:05,700 --> 00:24:07,100
logaritmika, log bażi 2.

607
00:24:07,100 --> 00:24:10,180
Iżda tista 'verament tkun xejn,
imma bażi 2 log.

608
00:24:10,180 --> 00:24:11,330
>> Issa dak dwar il-n?

609
00:24:11,330 --> 00:24:14,550
I jista 'jara li aħna tip ta maqsum inti
guys - maqsum inti, maqsuma int,

610
00:24:14,550 --> 00:24:15,910
maqsum inti, maqsuma int.

611
00:24:15,910 --> 00:24:18,760
Fejn ma l-aħħar jiġu minn?

612
00:24:18,760 --> 00:24:19,810
>> Allura huwa l-amalgamazzjoni.

613
00:24:19,810 --> 00:24:20,610
Minħabba taħseb dwarha.

614
00:24:20,610 --> 00:24:25,420
Meta inti jingħaqdu tmien persuni flimkien,
fejn nofshom huma sett ta 'erba'

615
00:24:25,420 --> 00:24:27,770
u nofs l-ieħor huma ieħor
sett ta 'erba, kif taħseb li tmur

616
00:24:27,770 --> 00:24:28,820
dwar kif isir l-amalgamazzjoni?

617
00:24:28,820 --> 00:24:30,830
Ukoll, inti guys ma kien
pjuttost intuwittivament.

618
00:24:30,830 --> 00:24:34,140
>> Imma jekk jien minflok ma kien ftit aktar
metodiku, I jista 'jkollhom mfakkar fil

619
00:24:34,140 --> 00:24:38,090
il-persuna fuq ix-xellug ewwel mal xellug tiegħi
idejn, mfakkar fil-persuna fuq ix-xellug

620
00:24:38,090 --> 00:24:42,080
ta 'dik in-nofs mal-lemin tiegħi, u
biss sussegwentement mixi permezz tal-

621
00:24:42,080 --> 00:24:46,990
lista, li tipponta lejn l-iżgħar element
kull darba, li jiċċaqalqu finger tiegħi fuq u

622
00:24:46,990 --> 00:24:48,970
fuq kif meħtieġ matul l-lista.

623
00:24:48,970 --> 00:24:51,890
Imma x'hemm importanti dwar dan li qed jingħaqdu
proċess huwa jien jqabbel dawn pari

624
00:24:51,890 --> 00:24:53,460
ta 'elementi.

625
00:24:53,460 --> 00:24:57,270
Mill-nofs tal-lemin u mix-xellug
nofs, jien qatt darba treġġigħ lura.

626
00:24:57,270 --> 00:25:00,570
>> Allura l-inkorporazzjoni innifsu qed tieħu
mhux aktar minn n passi.

627
00:25:00,570 --> 00:25:03,250
U kif ħafna drabi ma I jkollhom
biex tagħmel dan jingħaqdu?

628
00:25:03,250 --> 00:25:07,150
Ukoll, mhux aktar minn n, u aħna biss
raw li ma 'l-inkorporazzjoni finali.

629
00:25:07,150 --> 00:25:13,120
U hekk jekk inti tagħmel xi ħaġa li jieħu
log n passi n darbiet, jew viċe versa,

630
00:25:13,120 --> 00:25:15,210
li għaddej biex tagħtina n ħinijiet log n.

631
00:25:15,210 --> 00:25:16,310
>> U għaliex huwa dan aħjar?

632
00:25:16,310 --> 00:25:19,600
Ukoll, jekk aħna diġà jafu li log
n huwa aħjar minn n - id-dritt?

633
00:25:19,600 --> 00:25:22,590
Rajna fit-tfittxija binarja, il-ktieb tat-telefon
eżempju, log n kien definittivament

634
00:25:22,590 --> 00:25:23,760
aħjar minn lineari.

635
00:25:23,760 --> 00:25:28,420
Allura dan ifisser n ħinijiet log n hija
definittivament aħjar minn n darbiet ieħor

636
00:25:28,420 --> 00:25:30,390
n, AKA n kwadrat.

637
00:25:30,390 --> 00:25:32,400
U dan huwa dak li aħna finalment jħossu.

638
00:25:32,400 --> 00:25:34,928
>> Round daqshekk kbira ta 'applause, jekk
nistgħu, għal dawn guys.

639
00:25:34,928 --> 00:25:38,920
>> [Applause]

640
00:25:38,920 --> 00:25:41,550
>> DAVID Malan: U rigali firda tiegħek -
inti tista 'żżomm in-numri,

641
00:25:41,550 --> 00:25:44,010
jekk inti tixtieq.

642
00:25:44,010 --> 00:25:45,620
U rigal firda tiegħek, bħas-soltu.

643
00:25:45,620 --> 00:25:47,290
Oh, u ahna nibaghtulek
l-footage, Michelle.

644
00:25:47,290 --> 00:25:48,343
Grazzi.

645
00:25:48,343 --> 00:25:49,250
Kull dritt.

646
00:25:49,250 --> 00:25:50,400
Tgħin lilek innifsek għal ballun stress.

647
00:25:50,400 --> 00:25:54,110
>> U let me pull up, fil-frattemp,
ħabib tagħna Rob Bowden li joffru

648
00:25:54,110 --> 00:25:59,520
perspettiva kemmxejn differenti fuq dan,
peress li inti tista 'taħseb dwar dawn

649
00:25:59,520 --> 00:26:01,280
passi jiġri fil kemmxejn
b'mod differenti.

650
00:26:01,280 --> 00:26:04,750
Fil-fatt, l-set-up għal dak Rob huwa madwar
li juruna tassumi li konna

651
00:26:04,750 --> 00:26:09,030
diġà għamlu l up diviżjoni tal-
lista big fi tmien listi żgħar,

652
00:26:09,030 --> 00:26:10,570
kull daqs 1.

653
00:26:10,570 --> 00:26:13,350
>> Allura aħna qed jinbidlu l-pseudocode a
ftit biss biex issolvi tat jiksbu fil-

654
00:26:13,350 --> 00:26:15,320
idea qalba ta 'kif l-amalgamazzjoni xogħlijiet.

655
00:26:15,320 --> 00:26:17,600
Iżda l-ħin tmexxija ta 'dak
hu waslu biex jagħmlu għadu

656
00:26:17,600 --> 00:26:19,110
ser ikunu l-istess.

657
00:26:19,110 --> 00:26:23,540
U għal darb'oħra, l-set-up hawnhekk huwa li hu
bdew ma 'tmien listi ta' daqs 1.

658
00:26:23,540 --> 00:26:27,730
Allura inti ħadthom qbiżt l-parti fejn hu
attwalment isir il-log n, log n, log n

659
00:26:27,730 --> 00:26:31,205
diviżjoni tal-input.

660
00:26:31,205 --> 00:26:32,120
>> [Daqq video]

661
00:26:32,120 --> 00:26:33,615
>> -Li huwa għal pass wieħed.

662
00:26:33,615 --> 00:26:38,270
Għal pass tnejn, ripetutament
jingħaqdu pari ta 'listi.

663
00:26:38,270 --> 00:26:39,210
>> DAVID Malan: Hm.

664
00:26:39,210 --> 00:26:41,270
Biss awdjo huwa li ġejjin
minn kompjuter tiegħi.

665
00:26:41,270 --> 00:26:42,520
Ejja nippruvaw dan mill-ġdid.

666
00:26:42,520 --> 00:26:45,330

667
00:26:45,330 --> 00:26:48,310
>> Just arbitrarju pick -
issa għandna erba 'listi.

668
00:26:48,310 --> 00:26:51,590

669
00:26:51,590 --> 00:26:52,120
Tgħallem qabel.

670
00:26:52,120 --> 00:26:53,040
>> DAVID Malan: Hemm immorru.

671
00:26:53,040 --> 00:27:00,510
>> Twaħħid-108 u 15, aħna jispiċċaw
up mal-lista 15, 108.

672
00:27:00,510 --> 00:27:07,170
Twaħħid 50 u 4, aħna
tispiċċa bil 4, 50.

673
00:27:07,170 --> 00:27:12,990
Twaħħid 8 u 42, aħna
jispiċċaw bi 8, 42.

674
00:27:12,990 --> 00:27:19,970
U l-amalgamazzjoni 23 u 16, aħna
tispiċċa bil 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Issa listi kollha tagħna huma ta 'daqs 2.

676
00:27:23,270 --> 00:27:26,690
Avviż li kull tal-
erba 'listi huwa magħżul.

677
00:27:26,690 --> 00:27:29,450
Allura aħna tista 'tibda qed jingħaqdu
pari ta 'listi darb'oħra.

678
00:27:29,450 --> 00:27:38,420
Twaħħid 15 u 108 u 4 u 50, aħna
ewwel jieħdu l-4, allura l-15, imbagħad

679
00:27:38,420 --> 00:27:41,500
l-50, allura l-108.

680
00:27:41,500 --> 00:27:50,610
Twaħħid 8, 42 u 16, 23, aħna l-ewwel tieħu
l-8, allura l-16, allura l-23,

681
00:27:50,610 --> 00:27:52,700
allura l-42.

682
00:27:52,700 --> 00:27:57,600
>> Allura issa għandna biss żewġ listi ta 'daqs
4, li kull wieħed minnhom huwa magħżul.

683
00:27:57,600 --> 00:28:01,170
Allura issa aħna jingħaqdu dawn iż-żewġ listi.

684
00:28:01,170 --> 00:28:11,835
L-ewwel, aħna jieħdu l-4, allura aħna jieħdu l-
8, allura nieħdu l-15, imbagħad 16, imbagħad

685
00:28:11,835 --> 00:28:19,456
23, imbagħad 42, imbagħad 50, imbagħad 108.

686
00:28:19,456 --> 00:28:19,872
>> [Daqq video END]

687
00:28:19,872 --> 00:28:23,430
>> DAVID Malan: Għal darb'oħra, avviż, hu qatt ma
mimsus tazza jingħataw żmien aktar minn wieħed

688
00:28:23,430 --> 00:28:24,860
wara avvanz lil hinn minnha.

689
00:28:24,860 --> 00:28:26,200
Hekk hu qatt ma tirrepeti.

690
00:28:26,200 --> 00:28:29,850
Hekk hu dejjem li jiċċaqalqu lejn il-ġenb,
u li fejn sirna n tagħna.

691
00:28:29,850 --> 00:28:33,290
>> Għaliex ma let me pull up animazzjoni wieħed
li rajna qabel, iżda din id-darba

692
00:28:33,290 --> 00:28:35,110
jiffoka biss fuq it-tip jingħaqdu.

693
00:28:35,110 --> 00:28:38,030
Let me imorru quddiem u zoom
fil dwar dan hawn.

694
00:28:38,030 --> 00:28:42,530
Ewwel let me jagħżlu input każwali,
tagħmel dan aktar evidenti, u inti tista sort ta 'tara

695
00:28:42,530 --> 00:28:46,600
dak li aħna ħa għall mogħtija, qabel,
jingħaqdu tip huwa attwalment tagħmel.

696
00:28:46,600 --> 00:28:50,330
>> Allura avviż li inti tikseb dawn nofsijiet jew
dawn kwarti jew dawn tmienja tal-

697
00:28:50,330 --> 00:28:53,140
problema li kollha f'daqqa
jibdew jieħdu forma tajba.

698
00:28:53,140 --> 00:28:57,070
U mbagħad finalment, inti tara fuq
l-aħħar ħafna li bam,

699
00:28:57,070 --> 00:28:58,860
kollox huwa magħquda flimkien.

700
00:28:58,860 --> 00:29:01,690
>> Allura dawn huma biss tlieta differenti
jieħu fuq l-istess idea.

701
00:29:01,690 --> 00:29:05,980
Iżda l-għarfien ewlieni, bħad qasma
u conquer fl-ewwel klassi,

702
00:29:05,980 --> 00:29:10,640
kienet li aħna iddeċieda li b'xi mod jaqsam
il-problema fis xi ħaġa kbira, fis

703
00:29:10,640 --> 00:29:14,760
sort xi ħaġa ta identiċi fl-ispirtu,
iżda iżgħar u iżgħar

704
00:29:14,760 --> 00:29:15,660
u iżgħar.

705
00:29:15,660 --> 00:29:18,420
>> Issa gost mod ieħor biex issolvi tar jaħsbu
dwar dawn, anki jekk mhuwiex

706
00:29:18,420 --> 00:29:20,520
ser jagħtuk l-istess intuwittivi
fehim, huwa

707
00:29:20,520 --> 00:29:21,640
l-animazzjoni wara.

708
00:29:21,640 --> 00:29:25,400
Allura dan huwa xi ħadd video jitqiegħdu flimkien
li assoċjati differenti

709
00:29:25,400 --> 00:29:29,970
ħsejjes bl-operazzjonijiet varji għall
sort inserzjoni, per sort jingħaqdu, u

710
00:29:29,970 --> 00:29:31,150
għal ftit oħrajn.

711
00:29:31,150 --> 00:29:32,330
Allura fil-mument, jien ser hit Play.

712
00:29:32,330 --> 00:29:33,600
Huwa madwar minuta twil.

713
00:29:33,600 --> 00:29:37,410
U anki jekk inti xorta tista 'tara l-
mudelli jiġri, din id-darba inti tista '

714
00:29:37,410 --> 00:29:41,420
wkoll jisimgħu kif dawn algoritmi huma
jwettqu b'mod differenti u ma '

715
00:29:41,420 --> 00:29:43,950
mudelli kemmxejn differenti.

716
00:29:43,950 --> 00:29:45,830
>> Dan huwa tip inserzjoni.

717
00:29:45,830 --> 00:29:50,400
>> [Tones KUNDIZZJONIJIET]

718
00:29:50,400 --> 00:29:52,400
>> DAVID Malan: Huwa darb'oħra qed jipprova
li daħħal kull element

719
00:29:52,400 --> 00:29:52,900
fis fejn jappartjeni.

720
00:29:52,900 --> 00:29:54,628
Dan huwa tip bubble.

721
00:29:54,628 --> 00:30:10,097
>> [Tones KUNDIZZJONIJIET]

722
00:30:10,097 --> 00:30:13,630
>> DAVID Malan: U inti tista sort ta 'jħossu
kif relattivament ftit xogħol li huwa qed jagħmel

723
00:30:13,630 --> 00:30:15,834
fuq kull pass.

724
00:30:15,834 --> 00:30:20,470
Dan huwa dak tediousness ħsejjes simili.

725
00:30:20,470 --> 00:30:21,472
>> [Tones KUNDIZZJONIJIET]

726
00:30:21,472 --> 00:30:25,222
>> DAVID Malan: Dan huwa tip ta 'għażla,
fejn aħna tagħżel l-element li rridu mill

727
00:30:25,222 --> 00:30:28,845
għaddejjin mill-ġdid u għal darb'oħra u għal darb'oħra
u t-tqegħid fil-bidu.

728
00:30:28,845 --> 00:30:37,674
>> [Tones KUNDIZZJONIJIET]

729
00:30:37,674 --> 00:30:43,970
>> DAVID Malan: Dan huwa jingħaqdu sort, li
inti tista 'verament tibda tħossok.

730
00:30:43,970 --> 00:30:51,810
>> [Tones KUNDIZZJONIJIET]

731
00:30:51,810 --> 00:30:54,770
>> [Daħk]

732
00:30:54,770 --> 00:30:58,395
>> DAVID Malan: Xi ħaġa imsejħa gnome
sort, li aħna ma ħares lejn.

733
00:30:58,395 --> 00:31:13,630
>> [Tones KUNDIZZJONIJIET]

734
00:31:13,630 --> 00:31:17,910
>> DAVID Malan: So let me tara, issa,
distratt kif inti nisperaw li bil-

735
00:31:17,910 --> 00:31:21,110
mużika, jekk I jistgħu jiżolqu ftit
daqsxejn ta 'matematika fil hawn.

736
00:31:21,110 --> 00:31:24,850
Allura hemm raba mod li nistgħu
jaħsbu dwar xi jfisser li dawn

737
00:31:24,850 --> 00:31:29,210
funzjonijiet li jitwettqu aktar malajr minn dawk
li konna rajna qabel.

738
00:31:29,210 --> 00:31:32,470
U jekk int ġejjin fil-kors minn
sfond matematika, inti

739
00:31:32,470 --> 00:31:36,030
tassew taf forsi diġà li inti
jistgħu SLAP terminu fuq din it-teknika -

740
00:31:36,030 --> 00:31:40,400
jiġifieri recursion, funzjoni
li b'xi mod jitlob huwa stess.

741
00:31:40,400 --> 00:31:44,780
>> U għal darb'oħra, ifakkar li sort jingħaqdu
pseudocode kien jirrikorri fis-sens

742
00:31:44,780 --> 00:31:48,460
li wieħed mill-passi jingħaqdu sort ta
kien li jsejħu sort -

743
00:31:48,460 --> 00:31:49,740
jiġifieri, innifsu.

744
00:31:49,740 --> 00:31:52,480
Iżda Thankfully, għaliex aħna tinżamm
sejħa sort, jew jingħaqdu sort,

745
00:31:52,480 --> 00:31:55,880
speċifikament, fuq iżgħar
u l-lista iżgħar, aħna eventwalment

746
00:31:55,880 --> 00:32:00,005
qiegħ barra grazzi għall dak li aħna ser sejħa
base case, il-każ hard-kodifikati li

747
00:32:00,005 --> 00:32:04,270
qal jekk il-lista huwa żgħir, inqas minn 2
f'dak il-każ, biss jirritorna immedjatament.

748
00:32:04,270 --> 00:32:07,550
Jekk aħna ma kellhiex il-każ speċjali, il-
algoritmu kieku qatt qiegħ barra,

749
00:32:07,550 --> 00:32:11,010
u inti tabilħaqq jsibu rwieħhom
loop infinita verament dejjem.

750
00:32:11,010 --> 00:32:14,330
>> Iżda jissoponi li ridna li issa tqiegħed
xi numri fuq dan, għal darb'oħra, bl-użu n

751
00:32:14,330 --> 00:32:15,660
id-daqs tal-input.

752
00:32:15,660 --> 00:32:18,680
U jien ridt li jgħidlek, x'hemm
il-ħin totali involut

753
00:32:18,680 --> 00:32:19,800
running sort jingħaqdu?

754
00:32:19,800 --> 00:32:22,960
Jew b'mod iktar ġenerali, x'hemm
l-ispiża ta 'dan fil-ħin?

755
00:32:22,960 --> 00:32:24,730
>> Ukoll huwa pjuttost faċli tkejjel dak.

756
00:32:24,730 --> 00:32:29,010
Jekk n huwa inqas minn 2, iż-żmien involut
fl-għażla elementi n,

757
00:32:29,010 --> 00:32:30,480
fejn n hija 2, hija 0.

758
00:32:30,480 --> 00:32:31,410
Għaliex aħna biss ritorn.

759
00:32:31,410 --> 00:32:32,510
M'hemm l-ebda xogħol li għandu jsir.

760
00:32:32,510 --> 00:32:35,660
Issa forsi, forsi huwa pass wieħed jew tnejn
passi biex insemmu l-ammont ta '

761
00:32:35,660 --> 00:32:38,420
xogħol, iżda huwa qrib biżżejjed għal 0 dik
Jien biss se ngħid ebda xogħol hija

762
00:32:38,420 --> 00:32:40,940
meħtieġ jekk il-lista hija tant żgħira
li jiġu uninteresting.

763
00:32:40,940 --> 00:32:42,580
>> Iżda f'dan il-każ huwa interessanti.

764
00:32:42,580 --> 00:32:47,320
Il-każ rikursivi kien il-fergħa ta '
l pseudocode dak imsemmi inkella, sort

765
00:32:47,320 --> 00:32:52,000
in-nofs xellugi, issolvi d-dritt
nofs, tgħaqqad iż-żewġ nofsijiet.

766
00:32:52,000 --> 00:32:55,530
Issa għaliex din l-espressjoni
jirrappreżenta dak spiża?

767
00:32:55,530 --> 00:32:58,690
Ukoll, T ta 'n ifisser biss l-
ħin biex issolvi l-elementi n.

768
00:32:58,690 --> 00:33:03,070
U mbagħad fuq il-lemin tal-
ugwali sinjal hemm, it-T ta 'n maqsuma

769
00:33:03,070 --> 00:33:06,600
minn 2 hija tirreferi għall-ispiża ta 'dak?

770
00:33:06,600 --> 00:33:07,570
Sortjar in-nofs xellugi.

771
00:33:07,570 --> 00:33:10,990
It-T-oħra ta 'n diviż bi 2 huwa
preżumibbilment jirreferu għall-ispiża biex

772
00:33:10,990 --> 00:33:12,390
isolvi l-nofs tal-lemin.

773
00:33:12,390 --> 00:33:14,590
>> U allura l-n plus?

774
00:33:14,590 --> 00:33:15,420
Huwa l-amalgamazzjoni.

775
00:33:15,420 --> 00:33:19,120
Għaliex jekk għandek żewġ listi, wieħed ta '
n daqs matul 2 u ieħor ta 'qies n

776
00:33:19,120 --> 00:33:22,580
aktar minn 2, inti għandek essenzjalment tmissx
kull wieħed minn dawk l-elementi, bħal Rob

777
00:33:22,580 --> 00:33:24,990
mimsus kull wieħed mill-cups, u biss
kif aħna osservat f'kull tal-

778
00:33:24,990 --> 00:33:26,310
voluntiera fuq il-palk.

779
00:33:26,310 --> 00:33:28,790
Allura n hija l-ispiża ta 'għaqda.

780
00:33:28,790 --> 00:33:31,780
>> Issa sfortunatament, din il-formula
huwa wkoll innifsu rikursiv.

781
00:33:31,780 --> 00:33:36,390
Mela jekk staqsa l-mistoqsija, jekk n hija, ngħidu aħna,
16, jekk hemm 16-il persuna fuq il-palk

782
00:33:36,390 --> 00:33:40,670
jew 16 tazzi fil-video, kemm total
passi ma jieħdu biex sort lilhom

783
00:33:40,670 --> 00:33:41,550
ma sort jingħaqdu?

784
00:33:41,550 --> 00:33:45,790
Huwa fil-fatt mhux risposta ovvja,
għaliex issa inti għandek sort ta '

785
00:33:45,790 --> 00:33:48,500
recursively twieġeb din il-formula.

786
00:33:48,500 --> 00:33:51,190
>> Imma dak li OK, għaliex let me tipproponi
li aħna tagħmel dan li ġej.

787
00:33:51,190 --> 00:33:56,670
Il-ħin involuti biex issolvi 16-il persuna jew
16 cups se tkun rappreżentata

788
00:33:56,670 --> 00:33:58,020
ġeneralment bħala T-16.

789
00:33:58,020 --> 00:34:01,400
Iżda li jkun daqs, skond tagħna
formula preċedenti, 2 darbiet l-ammont

790
00:34:01,400 --> 00:34:04,780
ta 'ħin li tieħu biex issolvi
8 tazzi plus 16.

791
00:34:04,780 --> 00:34:08,590
U għal darb'oħra, plus 16 huwa l-ħin li jingħaqdu,
u l-żewġ ħinijiet T tat-8 hija l-

792
00:34:08,590 --> 00:34:10,790
ħin biex issolvi nofs tax-xellug u dritt nofs.

793
00:34:10,790 --> 00:34:11,989
>> Iżda għal darb'oħra, dan mhux biżżejjed.

794
00:34:11,989 --> 00:34:13,210
Irridu adsa aktar profonda.

795
00:34:13,210 --> 00:34:16,409
Dan ifisser li għandna nirrispondu l-
kwistjoni, dak li huwa T tat-8?

796
00:34:16,409 --> 00:34:19,610
Ukoll T tat-8 huwa biss 2
żminijiet T tal-4 plus 8.

797
00:34:19,610 --> 00:34:20,520
Well, x'hemm T tal-4?

798
00:34:20,520 --> 00:34:23,780
T ta '4 huwa biss 2 darbiet T tat-2 plus 4.

799
00:34:23,780 --> 00:34:25,489
Well, x'hemm T tat-2?

800
00:34:25,489 --> 00:34:29,030
T tat-2 huwa biss 2 darbiet T ta '1 plus 2.

801
00:34:29,030 --> 00:34:31,940
>> U għal darb'oħra, aħna qed tip ta 'jkollna
staġnati f'dan iċ-ċiklu.

802
00:34:31,940 --> 00:34:34,790
Iżda huwa dwar li tolqot dak
hekk imsejħa każ bażi.

803
00:34:34,790 --> 00:34:37,310
Għaliex x'hemm T ta '1, aħna ma titlob?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
Allura issa finalment, nistgħu naħdmu lura.

806
00:34:39,730 --> 00:34:44,290
>> Jekk T-1 0 huwa, I issa tista 'tmur lura up wieħed
linja li dan Guy hawn, u nista '

807
00:34:44,290 --> 00:34:46,330
plug in 0 għall T-1.

808
00:34:46,330 --> 00:34:51,770
Allura dan ifisser li huwa ugwali 2 darbiet żero,
inkella magħruf bħala 0, plus 2.

809
00:34:51,770 --> 00:34:53,739
U hekk dik l-espressjoni kollu huwa 2.

810
00:34:53,739 --> 00:34:58,740
>> Issa jekk I jieħdu l-T ta '2, li tweġiba
huwa 2, plagg fil-linja tan-nofs, T

811
00:34:58,740 --> 00:35:02,740
ta '4, li tagħti me 2 darbiet
2 plus 4, hekk 8.

812
00:35:02,740 --> 00:35:07,080
Jekk I imbagħad plagg fil 8 mas-sena
linja, li tagħti me 2 darbiet 8, 16.

813
00:35:07,080 --> 00:35:12,470
U jekk aħna mbagħad tkompli li bl-
24, u żżid f'16, aħna finalment jiksbu

814
00:35:12,470 --> 00:35:13,820
valur ta '64.

815
00:35:13,820 --> 00:35:18,480
>> Issa li fih innifsu tip ta 'jitkellem
xejn man-notazzjoni n, il-

816
00:35:18,480 --> 00:35:20,700
big O, il-omega li konna
kien jitkellem dwar.

817
00:35:20,700 --> 00:35:24,890
Iżda jirriżulta li 64 huwa tabilħaqq
16, id-daqs tal-input,

818
00:35:24,890 --> 00:35:27,110
log bażi 2 tas-16.

819
00:35:27,110 --> 00:35:30,200
U jekk dan huwa ftit familjari, biss
jaħsbu lura, u dan ser terga 'lura

820
00:35:30,200 --> 00:35:30,700
lilek eventwalment.

821
00:35:30,700 --> 00:35:33,775
Jekk dan huwa bażi log 2, huwa simili 2
jitgħollew sal-dak jagħtik 16?

822
00:35:33,775 --> 00:35:36,380
Oh, li 4, dan huwa 16-il darba 4.

823
00:35:36,380 --> 00:35:39,380
>> U għal darb'oħra, mhuwiex big deal jekk dan
huwa tip ta 'memorja imċajpra issa.

824
00:35:39,380 --> 00:35:43,720
Iżda għal issa, jieħdu fuq il-fidi
li 16 log 16 huwa 64.

825
00:35:43,720 --> 00:35:46,590
U għalhekk fil-fatt, ma 'dan sanità sempliċi
jivverifikaw, konna ikkonfermata -

826
00:35:46,590 --> 00:35:48,250
iżda mhux ippruvat formalment -

827
00:35:48,250 --> 00:35:52,800
li l-ħin ta 'tmexxija jingħaqdu
sort huwa tabilħaqq n log n.

828
00:35:52,800 --> 00:35:53,790
>> Allura mhux ħażin.

829
00:35:53,790 --> 00:35:57,260
Huwa definittivament aħjar mill-
algoritmi Rajna s'issa, u

830
00:35:57,260 --> 00:36:00,710
huwa għaliex aħna ħadthom leveraged, wieħed,
ta 'teknika msejħa recursion.

831
00:36:00,710 --> 00:36:03,880
Iżda aktar interessanti minn dak li
kunċett ta 'diviżjoni u conquering.

832
00:36:03,880 --> 00:36:07,460
Għal darb'oħra, verament ġimgħa 0 għalf li
anke issa qed terġa 'sseħħ fil-

833
00:36:07,460 --> 00:36:08,740
b'mod aktar konvinċenti.

834
00:36:08,740 --> 00:36:11,750
>> Issa eżerċizzju ftit gost, jekk inti stajt
qatt ma għamlu dan - u inti probabilment

835
00:36:11,750 --> 00:36:14,660
ma jkollhomx, minħabba tip ta 'normal
nies ma naħsibx li jagħmlu dan.

836
00:36:14,660 --> 00:36:20,650
Imma jekk immur għal google.com u jekk
I tixtieq titgħallem xi ħaġa dwar

837
00:36:20,650 --> 00:36:22,356
recursion, Ikteb.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Daħk]

840
00:36:29,058 --> 00:36:32,030
[Daħk AKTAR]

841
00:36:32,030 --> 00:36:33,385
DAVID Malan: Bad Joke bil-mod tixrid.

842
00:36:33,385 --> 00:36:34,450
[Daħk]

843
00:36:34,450 --> 00:36:36,970
DAVID Malan: Biss fil-każ, huwa hemmhekk.

844
00:36:36,970 --> 00:36:38,710
I ma jespliċitaw hija żbaljata,
u hemm l-ċajta.

845
00:36:38,710 --> 00:36:40,810
Kull dritt.

846
00:36:40,810 --> 00:36:42,950
Jispjegaw lill-poplu li jmiss lilek jekk
għadu ma pjuttost għafast għadha biss.

847
00:36:42,950 --> 00:36:47,650
Iżda recursion, b'mod aktar ġenerali, jirreferi
għall-proċess ta 'funzjoni sejħa

848
00:36:47,650 --> 00:36:51,430
innifsu, jew b'mod iktar ġenerali, li jiddividu l-
problema f'xi ħaġa li tista 'tkun

849
00:36:51,430 --> 00:36:56,220
solvuti frammentat mill-soluzzjoni identika
problemi rappreżentattivi.

850
00:36:56,220 --> 00:36:58,400
>> Ukoll, ejja gerijiet bidla
għal ftit mument.

851
00:36:58,400 --> 00:37:00,840
Aħna nixtiequ li jintemm fit ċerti cliffhangers,
Mela ejja nibdew biex jistabbilixxu

852
00:37:00,840 --> 00:37:05,870
l-istadju, għal diversi minuti,
fuq idea sempliċi ħafna -

853
00:37:05,870 --> 00:37:07,620
dik ta 'iskambji żewġ elementi, id-dritt?

854
00:37:07,620 --> 00:37:10,040
Kollha ta 'dawn algoritmi aħna kont qed
jitkellem dwar l-aħħar ftit

855
00:37:10,040 --> 00:37:12,420
lectures jinvolvu xi
tip ta 'iskambji.

856
00:37:12,420 --> 00:37:14,630
Illum kien viżwalizzata minnhom jkollna
up barra ta 'siġġijiet tagħhom u

857
00:37:14,630 --> 00:37:18,570
madwar mixi, imma fil-kodiċi, nixtiequ
ħu element minn firxa waħda

858
00:37:18,570 --> 00:37:20,370
u plop fis ieħor.

859
00:37:20,370 --> 00:37:21,880
>> Allura kif do we go dwar kif isir dan?

860
00:37:21,880 --> 00:37:24,850
Well, let me imorru quddiem u jiktbu
programm quick hawn.

861
00:37:24,850 --> 00:37:31,600
Jien ser jimxi 'l quddiem u jagħmlu
dan kif ġej.

862
00:37:31,600 --> 00:37:33,910
Ejja sejħa dan -

863
00:37:33,910 --> 00:37:38,070
dak li rridu sejħa dan wieħed?

864
00:37:38,070 --> 00:37:38,650
>> Attwalment, l-ebda.

865
00:37:38,650 --> 00:37:39,420
Let me kontrina.

866
00:37:39,420 --> 00:37:41,220
Ma rridx li tagħmel dan
cliffhanger s'issa.

867
00:37:41,220 --> 00:37:42,270
Hija se jħassru l-gost.

868
00:37:42,270 --> 00:37:43,600
Ejja nagħmlu dan minflok.

869
00:37:43,600 --> 00:37:47,430
>> Ejja ngħidu li nixtieq li jiktbu ftit
programm u li issa tħaddan din

870
00:37:47,430 --> 00:37:48,700
idea ta 'recursion.

871
00:37:48,700 --> 00:37:50,370
I tip ta 'ltqajna qabel myself hemmhekk.

872
00:37:50,370 --> 00:37:51,420
Jien ser jagħmlu dan li ġej.

873
00:37:51,420 --> 00:38:00,220
>> L-ewwel, a quick jinkludu ta 'standard io.h,
kif ukoll jinkludu ta cs50.h.

874
00:38:00,220 --> 00:38:03,200
U allura jien ser jimxi 'l quddiem
u tiddikjara null prinċipali int

875
00:38:03,200 --> 00:38:04,360
bil-mod normali.

876
00:38:04,360 --> 00:38:07,920
I realizzati I ve misnamed-fajl, hekk
let me żid ftit. estensjoni c hawn hekk

877
00:38:07,920 --> 00:38:09,510
li nistgħu jikkompilaw kif suppost.

878
00:38:09,510 --> 00:38:10,970
Tibda din il-funzjoni off.

879
00:38:10,970 --> 00:38:13,290
>> U l-funzjoni I jridu jiktbu, pjuttost
sempliċiment, huwa wieħed li jitlob lill-

880
00:38:13,290 --> 00:38:16,210
utent għal numru u mbagħad iżid up
il-numri bejn li

881
00:38:16,210 --> 00:38:19,920
numru u, jgħidu, 0.

882
00:38:19,920 --> 00:38:22,510
Allura l-ewwel jien ser jimxi 'l quddiem
u tiddikjara n int.

883
00:38:22,510 --> 00:38:24,760
Imbagħad I kopja xi kodiċi li
konna użati għal waqt.

884
00:38:24,760 --> 00:38:26,660
Filwaqt xi ħaġa huwa veru.

885
00:38:26,660 --> 00:38:28,000
I ser jiġu lura għal dak fil-mument.

886
00:38:28,000 --> 00:38:29,010
>> What do I trid tagħmel?

887
00:38:29,010 --> 00:38:33,460
Irrid ngħid printf pożittiv
numru sħiħ jekk jogħġbok.

888
00:38:33,460 --> 00:38:36,130
U allura jien ser
jgħidu n gets tikseb int.

889
00:38:36,130 --> 00:38:38,800
Għalhekk għal darb'oħra, xi kodiċi boilerplate
li konna użati qabel.

890
00:38:38,800 --> 00:38:40,810
U jien se tagħmel dan
filwaqt li n huwa inqas minn 1.

891
00:38:40,810 --> 00:38:44,120
Allura dan se jiżgura li l-utent
tagħti me numru sħiħ pożittiv.

892
00:38:44,120 --> 00:38:45,490
>> U issa jien ser jagħmlu dan li ġej.

893
00:38:45,490 --> 00:38:51,020
I trid iżżid up kollha tan-numri
bejn 1 u un, jew 0 u n-

894
00:38:51,020 --> 00:38:52,570
ekwivalenti, biex tikseb is-somma totali.

895
00:38:52,570 --> 00:38:55,100
Allura l-simbolu sigma big
li inti tista 'recall.

896
00:38:55,100 --> 00:38:59,050
Hekk jien ser tagħmel dan billi l-ewwel sejħa
funzjoni msejħa sigma,

897
00:38:59,050 --> 00:39:06,030
jgħaddiha fl n, u mbagħad jien ser
jgħidu printf, it-tweġiba hija hemm dritt.

898
00:39:06,030 --> 00:39:08,180
>> Għalhekk fil-qosor, I jiksbu u
int mill-utent.

899
00:39:08,180 --> 00:39:09,280
I jiżgura huwa pożittiv.

900
00:39:09,280 --> 00:39:12,700
Niddikjara a imsejjaħ tweġiba varjabbli ta '
int tip u maħżen fiha r-ritorn

901
00:39:12,700 --> 00:39:15,610
valur tal sigma, tgħaddi fis n bħala input.

902
00:39:15,610 --> 00:39:17,060
U mbagħad I jistampa din ir-risposta.

903
00:39:17,060 --> 00:39:19,550
>> Sfortunatament, anke jekk sigma ħsejjes
bħal xi ħaġa li jista 'jkun fil-

904
00:39:19,550 --> 00:39:24,040
il-fajl math.h, dikjarazzjoni tiegħu,
huwa attwalment mhux.

905
00:39:24,040 --> 00:39:24,690
Allura dak OK.

906
00:39:24,690 --> 00:39:26,170
I tista 'timplimenta dan myself.

907
00:39:26,170 --> 00:39:29,160
Jien ser timplimenta funzjoni msejħa
sigma, u li għaddej biex tieħu

908
00:39:29,160 --> 00:39:29,900
parametru -

909
00:39:29,900 --> 00:39:32,100
ejja biss sejħa hija m, biss
dan huwa differenti.

910
00:39:32,100 --> 00:39:35,910
U mbagħad up hawn, jien ser ngħid,
ukoll, jekk m ikun inqas minn 1 - dan huwa

911
00:39:35,910 --> 00:39:38,180
Programm ħafna uninteresting.

912
00:39:38,180 --> 00:39:41,700
Hekk jien ser jimxi 'l quddiem u
immedjatament jirritorna 0.

913
00:39:41,700 --> 00:39:45,920
Hija biss ma jagħmilx sens li jammontaw kollha
in-numri bejn 1 u m jekk m

914
00:39:45,920 --> 00:39:48,470
hija nnifisha 0 jew negattiv.

915
00:39:48,470 --> 00:39:50,900
>> U allura jien ser jimxi 'l quddiem
u tagħmel dan ħafna iteratively.

916
00:39:50,900 --> 00:39:53,090
Jien ser jagħmlu dan it-tip ta 'qodma l-iskola,
u jien ser jimxi 'l quddiem

917
00:39:53,090 --> 00:39:57,150
u jgħidu li jien ser
tiddikjara somma li tkun 0.

918
00:39:57,150 --> 00:39:59,630
Imbagħad jien ser ikollhom
a għal loop ta int -

919
00:39:59,630 --> 00:40:02,820
u let me tagħmel dan biex jaqblu tagħna
kodiċi ta 'distribuzzjoni, hekk ikollok kopja

920
00:40:02,820 --> 00:40:07,500
fid-dar. i int gets 1 fuq sa
i huwa inqas minn jew ugwali għal m.

921
00:40:07,500 --> 00:40:09,430
i plus plus.

922
00:40:09,430 --> 00:40:11,430
U allura ġewwa ta 'dan għall loop -

923
00:40:11,430 --> 00:40:12,440
aħna qed kważi hemm -

924
00:40:12,440 --> 00:40:15,810
somma gets somma plus 1.

925
00:40:15,810 --> 00:40:17,670
U allura jien ser jirritorna l-ammont.

926
00:40:17,670 --> 00:40:19,420
>> So I ma 'dan malajr,
pjuttost ċertament.

927
00:40:19,420 --> 00:40:22,775
Iżda għal darb'oħra, il-funzjoni ewlenija pjuttost
sempliċi, ibbażat fuq kodiċi konna

928
00:40:22,775 --> 00:40:23,190
miktub s'issa.

929
00:40:23,190 --> 00:40:25,610
Juża l-linja doppja biex tikseb pożittiv
int mill-utent.

930
00:40:25,610 --> 00:40:29,870
I imbagħad jgħaddu li int għal funzjoni ġdida
imsejħa sigma, ssejjaħ dan, għal darb'oħra, n.

931
00:40:29,870 --> 00:40:33,100
U jien jaħżnu l-valur tar-ritorn, ir-risposta
mill-kaxxa s-sewda bħalissa

932
00:40:33,100 --> 00:40:35,460
magħrufa bħala sigma, fil-varjabbli
imsejħa risposta.

933
00:40:35,460 --> 00:40:36,580
Imbagħad I jistampaw.

934
00:40:36,580 --> 00:40:39,090
>> Jekk aħna issa tkompli l-istorja,
kif hija sigma implimentat?

935
00:40:39,090 --> 00:40:40,840
Nipproponi li jimplimentaw kif ġej.

936
00:40:40,840 --> 00:40:43,560
L-ewwel, xi ftit ta 'żball ta' verifika
biex tiżgura li l-utent mhux

937
00:40:43,560 --> 00:40:46,480
messing miegħi u li jgħaddi fl
xi valur negattiv jew 0.

938
00:40:46,480 --> 00:40:49,710
Imbagħad I tiddikjara varjabbli imsejjaħ
somma u tistabbilixxi li 0.

939
00:40:49,710 --> 00:40:55,910
>> U issa nibda biex jiċċaqalqu minn i ugwali
1 it-triq kollha sa u inkluż m,

940
00:40:55,910 --> 00:41:00,130
għaliex nixtieq li tinkludi l-
numri minn wieħed sa m, inklużi.

941
00:41:00,130 --> 00:41:04,350
U ġewwa ta 'dan għal loop, I biss ma
somma gets kwalunkwe huwa issa, flimkien mal-

942
00:41:04,350 --> 00:41:08,900
valur ta 'i.

943
00:41:08,900 --> 00:41:10,370
Flimkien mal-valur ta 'i.

944
00:41:10,370 --> 00:41:14,090
>> Bħala twarrib, jekk inti stajt ma bbenefikawx dan
qabel, hemm xi zokkor sintattika

945
00:41:14,090 --> 00:41:14,870
għal din il-linja.

946
00:41:14,870 --> 00:41:21,120
I jistgħu jikteb dan bħala plus daqs i,
biss biex jiffrankaw myself ftit keystrokes

947
00:41:21,120 --> 00:41:22,570
u biex tfittex cooler daqsxejn.

948
00:41:22,570 --> 00:41:23,140
Imma li kollox.

949
00:41:23,140 --> 00:41:24,660
Huwa funzjonalment l-istess ħaġa.

950
00:41:24,660 --> 00:41:26,710
>> Sfortunatament, dan il-kodiċi tal-
mhux se jikkumpilaw s'issa.

951
00:41:26,710 --> 00:41:31,600
Jekk I run jagħmlu sigma 0, kif am
I se tikseb għajjat ​​fil?

952
00:41:31,600 --> 00:41:33,473
X'hemm Huwa ser ma simili?

953
00:41:33,473 --> 00:41:35,740
>> UDJENZA: [inaudible].

954
00:41:35,740 --> 00:41:37,800
>> DAVID Malan: Yeah, I ma ddikjarawx
il-funzjoni top up, right?

955
00:41:37,800 --> 00:41:40,590
C huwa tip ta stupid, fis-sens li biss
ma dak li inti tgħid li tagħmel, u inti

956
00:41:40,590 --> 00:41:41,880
għandek tagħmel dan f'dik l-ordni.

957
00:41:41,880 --> 00:41:45,910
U hekk jekk I hit Ikteb hawn, jien ser
tikseb twissija dwar sigma impliċitu

958
00:41:45,910 --> 00:41:46,860
dikjarazzjoni.

959
00:41:46,860 --> 00:41:48,120
>> Oh, mhux problema.

960
00:41:48,120 --> 00:41:50,370
I tista 'tmur sal-quċċata, u nista'
jiġifieri, id-dritt, stenna minuta.

961
00:41:50,370 --> 00:41:54,240
Sigma hija funzjoni li prospetti
l int u jistenna

962
00:41:54,240 --> 00:41:56,620
int bħala input, b'waqfa u virgola.

963
00:41:56,620 --> 00:41:59,550
Jew I tista 'tpoġġi l-funzjoni sħiħa
hawn fuq ewlenija, iżda b'mod ġenerali, I d

964
00:41:59,550 --> 00:42:02,260
jirrakkomanda kontra li, għaliex dan huwa
sbieħ li dejjem ikollhom prinċipali fil-quċċata hekk

965
00:42:02,260 --> 00:42:06,310
inti tista 'adsa dritt u jafu liema
programm qed jagħmel mill-qari prinċipali ewwel.

966
00:42:06,310 --> 00:42:07,930
>> Allura issa let me ċar l-iskrin.

967
00:42:07,930 --> 00:42:09,330
Remake sigma 0.

968
00:42:09,330 --> 00:42:10,340
Kollha jidher li check out.

969
00:42:10,340 --> 00:42:11,970
Let me run sigma 0.

970
00:42:11,970 --> 00:42:12,770
Inter pożittiv.

971
00:42:12,770 --> 00:42:15,580
I ser tagħtiha l-għadd
3 li jżommha sempliċi.

972
00:42:15,580 --> 00:42:18,710
Allura li għandha tagħti me 3
plus 2 plus 1, hekk 6.

973
00:42:18,710 --> 00:42:20,750
Ikteb, u tabilħaqq niġi 6.

974
00:42:20,750 --> 00:42:21,820
>> I tista 'tagħmel xi ħaġa akbar -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Just bħala tanġent, jien ser tagħmel
xi ħaġa redikoli bħal verament kbir

977
00:42:27,690 --> 00:42:30,375
numru, Oh, li attwalment jinħadmu -

978
00:42:30,375 --> 00:42:31,600
eh, ma naħsibx li d-dritt.

979
00:42:31,600 --> 00:42:32,810
Ejja ara.

980
00:42:32,810 --> 00:42:34,060
Ejja verament mess miegħu.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Li l-problema.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
X'qed jiġri?

985
00:42:44,970 --> 00:42:46,050
Il-kodiċi m'huwiex ħażin.

986
00:42:46,050 --> 00:42:48,470
Huwa għadu lineari.

987
00:42:48,470 --> 00:42:50,810
Whistling huwa effett tajjeb, għalkemm.

988
00:42:50,810 --> 00:42:52,060
X'qed jiġri?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Mhux żgur jekk I smajt dan.

991
00:42:55,620 --> 00:42:57,620
Għalhekk jirriżulta li - u
dan huwa bħala aside.

992
00:42:57,620 --> 00:42:59,400
Dan mhux qalba għall-
idea ta 'recursion.

993
00:42:59,400 --> 00:43:02,480
Jirriżulta, għaliex jien jippruvaw
jirrappreżentaw numru kbir bħal dan, l-aktar

994
00:43:02,480 --> 00:43:06,980
probabbli huwa qed interpretat ħażin
billi C bħala numru pożittiv mhux,

995
00:43:06,980 --> 00:43:09,980
iżda numru negattiv.

996
00:43:09,980 --> 00:43:12,690
>> Aħna ma tkellmu dwar dan, iżda
jinstabx hemm għadd negattivi

997
00:43:12,690 --> 00:43:14,210
fid-dinja flimkien
għal numri pożittivi.

998
00:43:14,210 --> 00:43:16,290
U l-mezzi li permezz tagħhom tista
jirrappreżentaw numru negattiv

999
00:43:16,290 --> 00:43:19,530
essenzjalment hija, tuża waħda
bit speċjali biex jindikaw

1000
00:43:19,530 --> 00:43:20,400
pożittiv fuq negattiv.

1001
00:43:20,400 --> 00:43:22,950
Huwa ftit aktar kumplessi minn dan,
iżda li l-idea bażika.

1002
00:43:22,950 --> 00:43:26,740
>> Allura sfortunatament, jekk C hija konfuża wieħed
ta 'dawk bits bħala fatt li jfisser,

1003
00:43:26,740 --> 00:43:30,790
oh, dan huwa numru negattiv, loop tiegħi
hawn, per eżempju, huwa fatt qatt ma

1004
00:43:30,790 --> 00:43:31,740
ser tintemm.

1005
00:43:31,740 --> 00:43:33,850
Mela jekk jien kienu attwalment istampar xi ħaġa
ġdid u għal darb'oħra, aħna se

1006
00:43:33,850 --> 00:43:34,650
tara lott kollu.

1007
00:43:34,650 --> 00:43:36,220
Iżda għal darb'oħra, dan huwa minbarra l-punt.

1008
00:43:36,220 --> 00:43:38,590
Dan huwa verament ftit tip ta '
kurżità intellettwali li aħna ser jidħlu

1009
00:43:38,590 --> 00:43:39,550
lura biex eventwalment.

1010
00:43:39,550 --> 00:43:43,400
Iżda għal issa, dan huwa korrett
implimentazzjoni jekk nassumu li l-

1011
00:43:43,400 --> 00:43:45,970
utent se jipprovdi ints
li jaqblu fi ħdan ints.

1012
00:43:45,970 --> 00:43:49,370
>> Imma I jsostnu li dan il-kodiċi, franchement,
jista 'jsir tant aktar sempliċi.

1013
00:43:49,370 --> 00:43:54,060
Jekk l-għan fil-idejn huwa li jieħu numru
bħal mu żid up kollha tal-

1014
00:43:54,060 --> 00:43:59,510
numri bejn dan u 1, jew bil-maqlub
bejn l-1 u, nitlob

1015
00:43:59,510 --> 00:44:03,380
li nista 'jissellef din l-idea li jingħaqdu
sort kellha, li kien qed jieħu problema

1016
00:44:03,380 --> 00:44:05,660
ta 'dan id-daqs u jaqsmuh
fis xi ħaġa iżgħar.

1017
00:44:05,660 --> 00:44:09,875
Forsi mhux nofs, iżda iżgħar, iżda
rappreżentattiv-istess.

1018
00:44:09,875 --> 00:44:12,130
Istess idea, iżda problema iżgħar.

1019
00:44:12,130 --> 00:44:15,470
>> Hekk jien attwalment - let me jiffrankaw dan il-fajl
ma 'numru verżjoni differenti.

1020
00:44:15,470 --> 00:44:17,670
Aħna ser sejħa din il-verżjoni
1 minflok 0.

1021
00:44:17,670 --> 00:44:20,790
U jien jsostnu li I jistgħu attwalment
reimplement dan f'dan it-tip ta '

1022
00:44:20,790 --> 00:44:22,160
mind-liwi mod.

1023
00:44:22,160 --> 00:44:23,710
>> Jien ser jitilqu parti minnha biss.

1024
00:44:23,710 --> 00:44:27,710
Jien se ngħid jekk m ikun inqas
minn jew saħansitra ugwali għal 0 -

1025
00:44:27,710 --> 00:44:29,280
Jien biss se tkun ftit
aktar anali dan iż-żmien

1026
00:44:29,280 --> 00:44:30,520
mal-verifika żball tiegħi -

1027
00:44:30,520 --> 00:44:33,190
Jien ser imorru quddiem u lura 0.

1028
00:44:33,190 --> 00:44:34,490
Dan huwa arbitrarju.

1029
00:44:34,490 --> 00:44:37,500
I am biss sempliċement jiddeċiedu jekk l-utent
tagħti me numru negattiv, jien

1030
00:44:37,500 --> 00:44:41,490
jirritornaw 0, u għandhom qrajt
id-dokumentazzjoni aktar mill-qrib.

1031
00:44:41,490 --> 00:44:42,170
>> Else -

1032
00:44:42,170 --> 00:44:44,070
Avviż dak li jien ser tagħmel.

1033
00:44:44,070 --> 00:44:49,260
Else I am ser jirritorna m plus -

1034
00:44:49,260 --> 00:44:51,010
dak li huwa sigma ta 'm?

1035
00:44:51,010 --> 00:44:56,710
Ukoll, sigma ta 'm plus minus 1 m,
plus minus m 2, plus minus 3 m.

1036
00:44:56,710 --> 00:44:58,030
Ma rridx li tikteb kollha ta 'dak out.

1037
00:44:58,030 --> 00:44:59,120
Għaliex ma I biss żi punt?

1038
00:44:59,120 --> 00:45:05,080
Recursively sejħa myself ma 'ftit
problema iżgħar, semicolon,

1039
00:45:05,080 --> 00:45:06,840
u sejħa hija ta 'kuljum?

1040
00:45:06,840 --> 00:45:07,040
>> Dritt?

1041
00:45:07,040 --> 00:45:10,980
Issa hawnhekk, wisq, inti tista 'tħossok jew jinkwetaw
li dan huwa loop infinita li jien

1042
00:45:10,980 --> 00:45:15,450
jinduċu, fejn I am implimentazzjoni
sigma billi ċċempel sigma.

1043
00:45:15,450 --> 00:45:20,342
Imma dak li perfettament OK, minħabba I
ħasbu quddiem l miżjuda li linji?

1044
00:45:20,342 --> 00:45:22,600
>> UDJENZA: [inaudible].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID Malan: 23 sa 26, li
huwa jekk il-kundizzjoni tiegħi.

1046
00:45:25,430 --> 00:45:28,390
Għaliex x'hemm sbieħ dwar il-
tnaqqis hawn, għaliex I iżommu

1047
00:45:28,390 --> 00:45:31,180
għoti problemi sigma iżgħar, iżgħar
problemi, iżgħar - mhuwiex

1048
00:45:31,180 --> 00:45:31,870
nofs id-daqs.

1049
00:45:31,870 --> 00:45:34,380
Huwa biss pass tarbija iżgħar,
iżda li OK.

1050
00:45:34,380 --> 00:45:38,050
Minħabba eventwalment, aħna ser jaħdmu
mod tagħna sa 1 jew 0.

1051
00:45:38,050 --> 00:45:41,630
U ladarba aħna hit 0, sigma mhux
ser sejħa nnifisha aktar.

1052
00:45:41,630 --> 00:45:43,590
Huwa ser jirritorna minnufih 0.

1053
00:45:43,590 --> 00:45:47,960
>> Allura l-effett, jekk inti tip ta 'riħ din
up f'moħħu tiegħek, huwa li żżid m plus

1054
00:45:47,960 --> 00:45:52,740
m minus 1, plus minus m 2, plus minus m
3, plus dot, dot, dot, m minus

1055
00:45:52,740 --> 00:45:57,820
m, eventwalment giving you 0, u l-
effett huwa finalment li jkunu miżjuda l

1056
00:45:57,820 --> 00:45:59,070
dawn l-affarijiet flimkien.

1057
00:45:59,070 --> 00:46:02,380
Allura aħna ma, ma recursion,
solvuta l-problema li għandna

1058
00:46:02,380 --> 00:46:03,470
ma setgħetx issolvi qabel.

1059
00:46:03,470 --> 00:46:06,840
Tabilħaqq, verżjoni 0 ta 'dan, u kull
problema sal-lum, kien solvable

1060
00:46:06,840 --> 00:46:09,980
ma biss bl-użu ta 'linji jew waqt
ħoloq jew constructs simili.

1061
00:46:09,980 --> 00:46:13,150
>> Imma recursion, I daresay, jagħtina
mod differenti ta 'ħsieb dwar

1062
00:46:13,150 --> 00:46:17,010
problemi, fejn jekk aħna tista 'tieħu
problema, jaqsamha minn xi ħaġa

1063
00:46:17,010 --> 00:46:22,340
kemmxejn kbir fis xi ħaġa kemmxejn
iżgħar, I jsostnu li nistgħu issolviha

1064
00:46:22,340 --> 00:46:26,040
forsi ftit aktar elegantly f'termini
tad-disinn, b'inqas kodiċi,

1065
00:46:26,040 --> 00:46:30,980
u forsi anki isolvu problemi aktar dak li jkun
jkun aktar diffiċli, kif aħna ser eventwalment

1066
00:46:30,980 --> 00:46:33,280
tara, soluzzjoni purament iteratively.

1067
00:46:33,280 --> 00:46:35,980
>> Iżda l-cliffhanger li għamilt
nirtira us fuq kien dan.

1068
00:46:35,980 --> 00:46:40,720
Let me imorru quddiem u tiftaħ
up fajl mill -

1069
00:46:40,720 --> 00:46:44,300
attwalment, let me go u
tagħmel dan malajr reali.

1070
00:46:44,300 --> 00:46:46,875
Let me imorru quddiem u tipproponi
dan li ġej.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Fost kodiċi lum hija dan il-fajl hawn.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Dan wieħed hawn, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Allura dan huwa programm ftit stupid li
I bit-tarjola up li t-talbiet li tagħmel

1076
00:47:06,260 --> 00:47:06,940
dan li ġej.

1077
00:47:06,940 --> 00:47:10,140
Fil prinċipali, l-ewwel jiddikjara
int imsejħa x u tassenja dan

1078
00:47:10,140 --> 00:47:11,100
il-valur ta '1.

1079
00:47:11,100 --> 00:47:13,520
Imbagħad tiddikjara y int u
tassenja dan il-valur 2.

1080
00:47:13,520 --> 00:47:15,310
Imbagħad tistampa dak xuy huwa.

1081
00:47:15,310 --> 00:47:17,781
Imbagħad jgħid, iskambji, dot dot dot.

1082
00:47:17,781 --> 00:47:21,670
>> Imbagħad hija tallega li ssejjaħ funzjoni
imsejħa tpartit, li jgħaddi fil x u

1083
00:47:21,670 --> 00:47:24,290
y, l-idea ta 'liema huwa li nisperaw
xuy se terga 'lura

1084
00:47:24,290 --> 00:47:25,620
differenti, l-oppost.

1085
00:47:25,620 --> 00:47:27,110
Imbagħad titlob skambjat!

1086
00:47:27,110 --> 00:47:28,420
ma 'punt exclamation.

1087
00:47:28,420 --> 00:47:30,190
Imbagħad tistampa xuy.

1088
00:47:30,190 --> 00:47:33,480
>> Iżda jirriżulta li din ħafna
dimostrazzjoni sempliċi isfel

1089
00:47:33,480 --> 00:47:35,570
hawnhekk huwa attwalment buggy.

1090
00:47:35,570 --> 00:47:38,870
Anke jekk jien tiddikjara temporanju
varjabbli u temporanjament tqegħid fis

1091
00:47:38,870 --> 00:47:42,010
dan, allura jien jassenjaw mill-ġdid
a l-valur ta 'b -

1092
00:47:42,010 --> 00:47:45,080
li jħoss raġonevoli, għaliex stajt
salvati kopja ta 'temperatura fil-.

1093
00:47:45,080 --> 00:47:48,410
Imbagħad I taġġorna b lill ugwali
kwalunkwe kien fl temperatura.

1094
00:47:48,410 --> 00:47:51,610
Din it-tip ta 'logħba qoxra ta' ċaqliq ta '
fis bu b ġo billi jużaw dan

1095
00:47:51,610 --> 00:47:54,360
middle-raġel imsejjaħ temp iħoss
perfettament raġonevoli.

1096
00:47:54,360 --> 00:47:57,270
>> Imma I jsostnu li meta I run dan
kodiċi, kif jien ser tagħmel issa -

1097
00:47:57,270 --> 00:47:59,490
let me imorru quddiem u paste fil hawn.

1098
00:47:59,490 --> 00:48:01,995
I ser sejħa dan noswap.c.

1099
00:48:01,995 --> 00:48:05,630
U kif tissuġġerixxi l-isem, dan mhuwiex
se jkun programm korretta.

1100
00:48:05,630 --> 00:48:09,460
Jagħmlu noswap. / Le swap.

1101
00:48:09,460 --> 00:48:12,110
x hija l-1, y huwa 2, iskambji, biddlu.

1102
00:48:12,110 --> 00:48:14,220
x hija l-1, y huwa 2.

1103
00:48:14,220 --> 00:48:16,920
Dan huwa fundamentalment żbaljat, anke
għalkemm dan jidher perfettament

1104
00:48:16,920 --> 00:48:17,730
raġonevoli lili.

1105
00:48:17,730 --> 00:48:21,330
U hemm raġuni, iżda aħna mhux qed
se jiżvelaw ir-raġuni għadha biss.

1106
00:48:21,330 --> 00:48:24,610
>> Għal issa-tieni cliffhanger ridt
li tħallik ma huwa dan,

1107
00:48:24,610 --> 00:48:27,120
tħabbira ta 'tip fuq kodiċijiet kupun.

1108
00:48:27,120 --> 00:48:31,590
Innovazzjoni tagħna mal-jiem tard din is-sena
pprovoka numru mhux trivjali

1109
00:48:31,590 --> 00:48:33,830
ta 'mistoqsijiet, li kienet
Mhijiex l-intenzjoni tagħna.

1110
00:48:33,830 --> 00:48:36,590
L-intenzjoni ta 'dawn il-kodiċijiet kupun,
fejn jekk inti tagħmel parti mill-problema

1111
00:48:36,590 --> 00:48:39,850
stabbiliti kmieni, u b'hekk jkollna b'jum żejjed,
kien verament biex jgħinuk guys jgħinu

1112
00:48:39,850 --> 00:48:42,420
yourself jibdew kmieni, sort
ta 'mill Jingħata inċentiv inti.

1113
00:48:42,420 --> 00:48:44,880
Jgħinna jiddistribwixxu tagħbija madwar
ħinijiet tal-uffiċċju aħjar sabiex

1114
00:48:44,880 --> 00:48:45,740
huwa tip ta 'win-win.

1115
00:48:45,740 --> 00:48:48,860
>> Sfortunatament, I think istruzzjonijiet tiegħi
ma ġewx, sa llum, ċar ħafna, hekk

1116
00:48:48,860 --> 00:48:52,230
I marru lura dan il-weekend u aġġornati
l-spec fil akbar, aktar kuraġġuża test li

1117
00:48:52,230 --> 00:48:53,600
jispjegaw balal bħal dawn.

1118
00:48:53,600 --> 00:48:56,900
U biss biex jgħidu li aktar pubblikament, bi
inadempjenza, settijiet problema huma dovuti il-Ħamis

1119
00:48:56,900 --> 00:48:58,400
f'nofsinhar, per-sillabu.

1120
00:48:58,400 --> 00:49:02,030
Jekk tibda kmieni, irfinar parti
l-problema stabbilita sal-Erbgħa at 12:00

1121
00:49:02,030 --> 00:49:05,170
PM, il-parti li tirrigwarda kupun
kodiċi, l-idea hija li inti tista 'testendi

1122
00:49:05,170 --> 00:49:07,710
iskadenza tiegħek għall-
P stabbilit sal-Ġimgħa.

1123
00:49:07,710 --> 00:49:10,890
Dan huwa, daqsxejn off parti żgħira tal-P
stabbiliti relattiv għal dak li tipikament huwa l-

1124
00:49:10,890 --> 00:49:13,200
problema akbar, u tixtri
yourself b'jum żejjed.

1125
00:49:13,200 --> 00:49:15,190
Għal darb'oħra, jiġrilha inti taħseb dwar
il-problema sett, gets inti

1126
00:49:15,190 --> 00:49:16,380
ħinijiet tal-uffiċċju qabel.

1127
00:49:16,380 --> 00:49:20,670
Iżda l-problema kodiċi tal-kupun għadu
meħtieġa, anki jekk inti ma tissottomettih.

1128
00:49:20,670 --> 00:49:23,340
>> Iżda aktar compellingly hija din.

1129
00:49:23,340 --> 00:49:26,520
(Whisper STAGE) U dawk folks li jħallu
kmieni huma gonna jiddispjaċina minnu.

1130
00:49:26,520 --> 00:49:28,620
Kif huma l-folks fuq il-gallarija.

1131
00:49:28,620 --> 00:49:32,510
I ruhna bil-quddiem lill-folks fuq
il-gallarija għal raġunijiet li se jkunu

1132
00:49:32,510 --> 00:49:33,920
ċar fil-ftit mument.

1133
00:49:33,920 --> 00:49:37,050
>> Allura aħna fortunati li jkollhom waħda ta '
Ex fellows tagħlim ras CS50 fiż

1134
00:49:37,050 --> 00:49:39,302
kumpanija msejħa dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Huma ħafna ġenerożament donat
kodiċi tal-kupun hawn għal dan l-ispazju ħafna,

1136
00:49:45,500 --> 00:49:48,180
li jkun sa mill-
soltu 2 gigabytes.

1137
00:49:48,180 --> 00:49:51,740
Allura dak li ħsibt aħna se nagħmlu dwar dan
Nota finali hija tagħmel daqsxejn ta 'giveaway,

1138
00:49:51,740 --> 00:49:55,380
fejn fi ftit mument, aħna se jiżvelaw
ir-rebbieħ u li jkollha kupun

1139
00:49:55,380 --> 00:49:57,980
kodiċi li inti tista 'imbagħad mur tagħhom
website, tip fil, u voila, jiksbu

1140
00:49:57,980 --> 00:50:01,370
lott kollu aktar spazju Dropbox għall tiegħek
apparat u għall-fajls personali tiegħek.

1141
00:50:01,370 --> 00:50:05,690
>> U l-ewwel, li jixtiequ jipparteċipaw
f'dan tpinġija?

1142
00:50:05,690 --> 00:50:09,630
OK, issa li jagħmilha saħansitra aktar gost.

1143
00:50:09,630 --> 00:50:14,010
Il-persuna li tirċievi dan 25-gigabyte
kodiċi tal-kupun - li hija ferm

1144
00:50:14,010 --> 00:50:16,150
aktar konvinċenti mill-tard
ġranet issa, forsi -

1145
00:50:16,150 --> 00:50:20,620
huwa dak li hu bilqiegħda fuq quċċata ta '
kuxxin tas-sedil li taħtu hemm

1146
00:50:20,620 --> 00:50:21,620
li kodiċi tal-kupun.

1147
00:50:21,620 --> 00:50:23,480
Inti issa tista 'tfittex taħt
kuxxin tas-sedil tiegħek.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [Daqq video]

1150
00:50:29,680 --> 00:50:31,620
>> -One, tnejn, tlieta.

1151
00:50:31,620 --> 00:50:35,015
>> [Screaming]

1152
00:50:35,015 --> 00:50:35,985
>> -Inti tikseb karozza!

1153
00:50:35,985 --> 00:50:36,670
Ikollok karozza!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID Malan: Aħna se tara
inti l-Erbgħa.

1155
00:50:37,970 --> 00:50:38,904
>> -Inti tikseb karozza!

1156
00:50:38,904 --> 00:50:39,371
Ikollok karozza!

1157
00:50:39,371 --> 00:50:40,305
Ikollok karozza!

1158
00:50:40,305 --> 00:50:41,706
Ikollok karozza!

1159
00:50:41,706 --> 00:50:43,107
Ikollok karozza!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID Malan: folks Gallarija, come
stabbiliti hawn il-quddiem,

1161
00:50:45,530 --> 00:50:46,866
fejn għandna ekstras.

1162
00:50:46,866 --> 00:50:50,282
>> Kulħadd gets-karozza!

1163
00:50:50,282 --> 00:50:52,234
Kulħadd gets karozza!

1164
00:50:52,234 --> 00:50:52,722
>> [Daqq video END]

1165
00:50:52,722 --> 00:50:54,590
>> Narrator: Fil-CS50 jmiss -

1166
00:50:54,590 --> 00:51:00,374
>> SPEAKER 5: Oh gosh tiegħi gosh gosh gosh
gosh gosh gosh gosh gosh gosh -

1167
00:51:00,374 --> 00:51:02,106
>> [Jilgħab UKELELE]