1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [Ġimgħa 3, Ikompli]

2
00:00:02,280 --> 00:00:04,110
>> [David J. Malan - Università ta 'Harvard]

3
00:00:04,110 --> 00:00:07,130
>> [Dan huwa CS50. - CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> Kull dritt. Merħba lura. Dan huwa CS50 u dan huwa l-aħħar ta 'ġimgħa 3.

5
00:00:11,010 --> 00:00:14,680
>> Għalhekk għal dawk familjari, sena li għaddiet Harvard nediet dak li jissejjaħ il-Lab Innovazzjoni,

6
00:00:14,680 --> 00:00:18,530
jew i-laboratorju, li huwa bini isbaħ madwar l-xmara fuq il-kampus HBS tal-

7
00:00:18,530 --> 00:00:22,640
li huwa miftuħ għall-istudenti kulleġġ, studenti GSAs, studenti minn kampus madwar,

8
00:00:22,640 --> 00:00:27,000
inkluż fakultà, u huwa post li jingħaqdu flimkien biex jaħdmu fuq affarijiet innovattivi,

9
00:00:27,000 --> 00:00:29,180
affarijiet partikolarment intraprenditorjali

10
00:00:29,180 --> 00:00:33,410
jekk inti u 0 jew aktar ħbieb qed taħseb li tagħmel xi ħaġa intraprenditorjali

11
00:00:33,410 --> 00:00:37,080
jew matul din il-klassi, wara din il-klassi, jew lil hinn.

12
00:00:37,080 --> 00:00:41,540
>> Allura waħda mill-affarijiet li jagħmlu fuq terminu J hija dawn il-vjaġġi,

13
00:00:41,540 --> 00:00:44,510
waħda minnhom hija li New York, li wieħed minnhom huwa li Silicon Valley.

14
00:00:44,510 --> 00:00:47,530
L-ispazju huwa limitat ħafna, iżda huwa opportunità biex togħrok ispallejn ma MBAs

15
00:00:47,530 --> 00:00:52,200
u studenti gradwati madwar il-kampus u attwalment jqattgħu ħin f'dawk l-oqsma rispettivi

16
00:00:52,200 --> 00:00:55,500
chatting up fetħu, chat up intraprendituri u simili.

17
00:00:55,500 --> 00:00:57,870
Allura jekk ikunu interessati, check out dan il-URL hawn.

18
00:00:57,870 --> 00:01:01,220
Huwa disponibbli wkoll fuq il-pjastri online.

19
00:01:01,220 --> 00:01:04,610
>> Jista aħna jtaffi l-awdjo-dar biss ftit?

20
00:01:04,610 --> 00:01:08,640
Jekk inti tixtieq li jingħaqdu magħna għall-ikel din il-ġimgħa, pm 1:15 fil Fire & Silġ, jekk jogħġbok ras hemmhekk.

21
00:01:08,640 --> 00:01:11,390
Apologies jekk il-formola hija diġà mimlija mill-ħin li inti naslu s'hemm.

22
00:01:11,390 --> 00:01:13,750
Iżda aħna ser tkompli dan onward tradizzjoni.

23
00:01:13,750 --> 00:01:17,350
>> Illum aħna tkompli d-diskussjoni livell ogħla ta 'diversi problemi li nistgħu ssolvi,

24
00:01:17,350 --> 00:01:21,330
jiffoka ħafna inqas, illum inqas, fuq il-kodiċi u ħafna aktar fuq l-ideat.

25
00:01:21,330 --> 00:01:24,720
Allura taħseb lura għal ġimgħa 0 meta aħna Tore ktieb tat-telefon fil-nofs,

26
00:01:24,720 --> 00:01:28,260
l-għan tiegħu kien li jagħmel xi ħaġa, ċertament, xi ftit drammatiku

27
00:01:28,260 --> 00:01:32,360
imma li jibagħtu l-punt li tiftix ma għandhom ikunu, neċessarjament,

28
00:01:32,360 --> 00:01:35,100
kif ovvji ewwel daqqa t'għajn kif inti tista 'taħseb.

29
00:01:35,100 --> 00:01:40,200
U sabiex jissolvew problemi b'mod ġenerali mhux bilfors dejjem l-aħjar -

30
00:01:40,200 --> 00:01:44,130
L-aktar soluzzjoni ovvja mhux bilfors tkun l-aħjar.

31
00:01:44,130 --> 00:01:47,300
Allura kellna dan il-ktieb tat-telefon u, franchement, lkoll f'din il-kamra kienet l-instincts,

32
00:01:47,300 --> 00:01:51,470
aktar probabbli, li għandu jibda fl-nofs meta jkunu qed ifittxu Mike Smith u mbagħad mur lemin jew xellug

33
00:01:51,470 --> 00:01:54,280
ibbażata fuq kwalunkwe ittra ta 'l-alfabett aħna ġara li jispiċċaw fuq.

34
00:01:54,280 --> 00:01:57,560
>> Iżda dik l-idea sempliċi li aħna bnedmin ħadu għall mogħtija għal sakemm

35
00:01:57,560 --> 00:02:00,670
verament għandha tibda fuq quddiemnett tal-moħħ tiegħek

36
00:02:00,670 --> 00:02:03,900
għaliex il-problemi nikseb ħafna aktar kumpless minn ktieb tat-telefon,

37
00:02:03,900 --> 00:02:07,420
dawk l-istess sempliċi, intuwizzjoni brillanti huma liema huma se jħallina naħsdu

38
00:02:07,420 --> 00:02:10,259
sabiex isolvu problemi ħafna aktar ikkumplikati u aktar interessanti,

39
00:02:10,259 --> 00:02:12,930
fosthom uħud mill-affarijiet nieħdu għall mogħtija diġà f'dawn il-jiem.

40
00:02:12,930 --> 00:02:15,720
Biljuni ta 'paġni tal-web hemmhekk, u għadhom Google u Bing u simili

41
00:02:15,720 --> 00:02:17,660
huma kapaċi jsibu affarijiet għalina bħal dik.

42
00:02:17,660 --> 00:02:22,300
Li mhux jiġri bl-użu ta 'tfittxija lineari, tiftix permezz-paġni kollha web possibbli.

43
00:02:22,300 --> 00:02:25,290
Facebook huwa kapaċi jgħidlek li kollha tal-ħbieb tiegħek huma jew ħbieb tal-ħbieb,

44
00:02:25,290 --> 00:02:28,250
u li wisq jista 'jsir apparentement fi instant f'dawn il-jiem

45
00:02:28,250 --> 00:02:30,820
anki jekk dawn għandhom miljuni ta 'utenti.

46
00:02:30,820 --> 00:02:34,250
>> U hekk kif għandna attwalment isolvu problemi fuq skala li finalment se tnaqqas

47
00:02:34,250 --> 00:02:37,830
l-ideat ħarisna lejn fl f'ġimgħa 0 u daqsxejn aktar illum.

48
00:02:37,830 --> 00:02:42,320
Aħna mhux se terġa 'tesegwixxi dan algoritmu, iżda tfakkar aħna wkoll għamlet fil f'ġimgħa 0 f'dan l-eżerċizzju

49
00:02:42,320 --> 00:02:44,780
fejn kellna kulħadd bilwieqfa, jieħdu fuq in-numru 1,

50
00:02:44,780 --> 00:02:48,720
u allura kellna kulħadd awto-għadd mill-tqabbil off, li żżid in-numri tiegħek flimkien,

51
00:02:48,720 --> 00:02:51,930
allura nofs il-gang poġġa bilqiegħda fuq kull iterazzjoni.

52
00:02:51,930 --> 00:02:56,750
Allura aħna marru minn 500 student għal 250 sa 125 u ibqa 'sejjer hekk.

53
00:02:56,750 --> 00:03:00,080
Imma kif għidna nhar it-Tnejn, l-idea qawwija hemmhekk

54
00:03:00,080 --> 00:03:02,460
kienet li jekk aħna rdoppja l-daqs ta 'dik il-problema

55
00:03:02,460 --> 00:03:06,480
u l-gidien mill-Ġustizzja jew Ec 10 daħal lura fil-kamra u ingħaqdet magħna,

56
00:03:06,480 --> 00:03:09,510
ukoll, nistgħu probabbilment joqgħod dak il-grupp aggregat kollu

57
00:03:09,510 --> 00:03:13,380
mal biss 1 iterazzjoni big aktar tal-linja għaliex biss forsi doppju tad-daqs

58
00:03:13,380 --> 00:03:15,630
jew fil-każ daqsxejn aktar mid-doppju tad-daqs Ec 10 ta.

59
00:03:15,630 --> 00:03:18,440
U hekk aħna se jkollu jonfoq ftit aktar żmien,

60
00:03:18,440 --> 00:03:22,000
iżda aħna ma jkollu jonfoq 400 jew 700 aktar passi.

61
00:03:22,000 --> 00:03:26,550
>> Just li żebgħa din l-istampa b'mod li l-ftit inqas astratt, ejja ma jkunu kulħadd stand up.

62
00:03:26,550 --> 00:03:31,100
Imma jekk dawk minnkom li għażlu li joqogħdu fil-orkestra tal-lum ma mfakkar wieqfa,

63
00:03:31,100 --> 00:03:34,580
ejja ara jekk nistgħu insemmu fost inti li l-persuna tallest hija

64
00:03:34,580 --> 00:03:36,730
billi għamlet l-istess tip ta 'algoritmu komparattiv.

65
00:03:36,730 --> 00:03:41,830
Mela jekk int seduta fil-orkestra, apologies tiegħi, imma pass 1, stand up;

66
00:03:41,830 --> 00:03:44,650
pass 2, par off ma 'xi ħadd fil-qrib miegħek,

67
00:03:44,650 --> 00:03:49,360
figura li huwa taller, u joqogħdu bilqegħda jekk inti iqsar.

68
00:03:49,360 --> 00:03:51,360
Imbagħad irrepeti.

69
00:03:51,360 --> 00:03:56,280
[Studenti murmuring]

70
00:04:13,450 --> 00:04:15,320
>> Okay.

71
00:04:15,320 --> 00:04:19,010
Okay. Wieħed titħalla wieqfa. X'hemm isem tiegħek? >> Andrew.

72
00:04:19,010 --> 00:04:21,959
>> Andrew, inti l-persuna tallest fit-taqsima orkestra illum.

73
00:04:21,959 --> 00:04:28,100
>> Prosit. [Applause u cheering] Okay. Jkollhom sedil. Allura sibna Andrew.

74
00:04:28,100 --> 00:04:30,870
Imma kemm żmien ser jieħu me, per eżempju, biex isibu Andrew

75
00:04:30,870 --> 00:04:33,740
f'din it-taqsima orkestra ta '50 + jew hekk in-nies?

76
00:04:33,740 --> 00:04:36,900
I jistgħu ħadu approċċ pjuttost sempliċi u tibda hawn.

77
00:04:36,900 --> 00:04:39,270
U jien 2 persuni stand up u I biss jqabbluhom,

78
00:04:39,270 --> 00:04:42,120
u mbagħad I say kull min huwa kemmxejn iqsar, "Okay, inti tiltaqa,"

79
00:04:42,120 --> 00:04:44,380
u jien ser tiftakar li l-persuna taller kien.

80
00:04:44,380 --> 00:04:49,030
Imbagħad Nirrepeti, irrepeti, irrepeti, u jien tistrieħ fuq il-persuna tallest

81
00:04:49,030 --> 00:04:51,920
sal I issib xi ħadd ftit taller minn dawn, f'liema punt

82
00:04:51,920 --> 00:04:54,950
il-persuna kemmxejn iqsar irid imbagħad joqogħdu bilqegħda.

83
00:04:54,950 --> 00:04:57,690
Iżda f'dak algoritmu f'din it-taqsima orkestra, jekk ikun hemm n minnkom,

84
00:04:57,690 --> 00:05:00,480
kemm passi huwa li algoritmu se jieħu? >> [Student] N.

85
00:05:00,480 --> 00:05:03,580
>> Huwa ser jieħu n, id-dritt, minħabba li fl-agħar każ, biex ngħidu hekk,

86
00:05:03,580 --> 00:05:09,090
il-persuna tallest hija l-persuna ħafna aħħar li niġi biex biss billi xortih ħażina każwali.

87
00:05:09,090 --> 00:05:14,260
Allura fl-agħar każ, il-ħin tmexxija ta 'din l-algorithm hija lineari, huwa n,

88
00:05:14,260 --> 00:05:18,070
fejn n huwa n-numru totali ta 'nies fl-ispazju, id-daqs tal-problema.

89
00:05:18,070 --> 00:05:19,600
Xi ngħidu dwar dan algoritmu?

90
00:05:19,600 --> 00:05:22,080
Il-fatt li intom kollha saqajh u mbagħad għal darb'oħra nofs inti sib stabbiliti,

91
00:05:22,080 --> 00:05:23,950
nofs inti sib stabbiliti, nofs inti sib stabbiliti.

92
00:05:23,950 --> 00:05:26,070
Kemm passi għandhom li ħadu jekk hemm n minnkom hawn?

93
00:05:26,070 --> 00:05:30,200
[Student] N log n. >> Dan ikun agħar. Log n.

94
00:05:30,200 --> 00:05:32,930
>> Allura log n, anki jekk inti ma pjuttost tiftakar dak logaritmu hija,

95
00:05:32,930 --> 00:05:38,410
għal issa, biss japprezzaw li għandu x'jaqsam b'xi mod li din tnaqqas bin-nofs u tnaqqas bin-nofs u tnaqqas bin-nofs.

96
00:05:38,410 --> 00:05:41,000
Ma kellhiex tkun fattur ta '2. Dan jista 'jkun fattur ta' 3.

97
00:05:41,000 --> 00:05:46,560
Imma hija din ripetizzjoni ta 'l-istess tip ta' fattur tali li d-daqs tal-problema tibda hawn

98
00:05:46,560 --> 00:05:49,620
iżda imbagħad immedjatament tmur hawn, allura hawnhekk, allura hawnhekk, allura hawnhekk.

99
00:05:49,620 --> 00:05:53,580
Int mhux qed tieħu gdim żgħar barra mill-problema, int verament tqattiegħ bogħod lejn din

100
00:05:53,580 --> 00:05:56,160
bil-kbir waqgħet swoop kull darba.

101
00:05:56,160 --> 00:06:00,810
Allura kellna 50 persuna, imbagħad 25, imbagħad 12 ½ jew 13-nies bil-wieqfa,

102
00:06:00,810 --> 00:06:05,370
imbagħad 6 ½ u oħrajn sakemm permanenti finalment biss Andrew tħalliet.

103
00:06:05,370 --> 00:06:08,710
Allura aħna qed tmur biex sejħa li log ta 'n, u inti tista Ħares din kif ġej.

104
00:06:08,710 --> 00:06:12,570
Recall din l-istampa hawn fejn algoritmu lineari huwa bħall-linja ħamra hemm,

105
00:06:12,570 --> 00:06:17,520
il-linja isfar kienet l-għadd mill 2s algoritmu li aħna użati għall-istudenti għadd

106
00:06:17,520 --> 00:06:22,300
fil-passat, iżda llum il-Grail qaddis se jibqa din il-linja ħadra

107
00:06:22,300 --> 00:06:25,470
fejn jekk aħna rduppjat l-għadd ta 'nies fis-sezzjoni orkestra jew biss qal,

108
00:06:25,470 --> 00:06:29,170
infern, ejja jkollhom kulħadd fil-kamra kollha bilwieqfa, ma jkunx tali big deal

109
00:06:29,170 --> 00:06:31,560
għaliex aħna bejn wieħed u ieħor tirdoppja kif ħafna nies huma stabbiliti hawn,

110
00:06:31,560 --> 00:06:33,500
1 iterazzjoni aktar, mhux problema.

111
00:06:33,500 --> 00:06:36,200
>> Imxejna sabet Andrew jew min jiġri li jkun taller minn Andrew

112
00:06:36,200 --> 00:06:38,770
fil-mezzanin jew fil-gallarija.

113
00:06:38,770 --> 00:06:42,140
Allura din l-idea sempliċi li ħadna tant għall mogħtija fil-ktieb tat-telefon,

114
00:06:42,140 --> 00:06:46,170
tirrealizza li hemm postijiet tant differenti li bihom nistgħu japplikaw għaliha.

115
00:06:46,170 --> 00:06:50,810
Just biex SLAP xi lingwaġġ - fil-fatt, minflok lingwaġġ 1,

116
00:06:50,810 --> 00:06:52,750
let me go għal din l-istampa hawn.

117
00:06:52,750 --> 00:06:56,970
Dritt issa tkellimna dwar n u n / 2 u mbagħad log ta 'ln,

118
00:06:56,970 --> 00:07:00,500
iżda nistgħu ċertament toħroġ bi, kif aħna se matul il-kors tas-semestru,

119
00:07:00,500 --> 00:07:05,130
xorta oħra ta 'formuli matematiċi sabiex jiddeskrivi dan il-kunċett ġenerali ta' running time.

120
00:07:05,130 --> 00:07:07,580
Dawn huma barra mill-kuntest għal issa għaliex aħna ser tara qabel twil

121
00:07:07,580 --> 00:07:09,900
algoritmi li dawn fil-fatt jirrappreżentaw.

122
00:07:09,900 --> 00:07:17,990
>> Iżda l-avviż hawn il-linja n lineari, il-linja dritta, huwa attwalment baxx ħafna tipponta dritt issa.

123
00:07:17,990 --> 00:07:22,950
Li tip ta 'illużjoni ottika li aħna biss bidla dak l-assi x tirrappreżenta

124
00:07:22,950 --> 00:07:26,130
u l-assi y, u nistgħu nagħmlu punt linja dritta fi kwalunkwe direzzjoni li rridu.

125
00:07:26,130 --> 00:07:30,350
Iżda r-raġuni li huwa hekk apparentement fissa issa

126
00:07:30,350 --> 00:07:35,690
huwa għaliex għandna bżonn biex tagħmel spazju fuq din il-graff għal żminijiet ħafna aktar kajman running.

127
00:07:35,690 --> 00:07:39,030
Għal issa, jafu li hemm xi algoritmi pretty ħżiena fil-ħajja,

128
00:07:39,030 --> 00:07:43,790
li wħud minnhom ma tieħu passi n jew, aħjar għadhom, log passi n iżda aktar.

129
00:07:43,790 --> 00:07:48,820
Allura fuq mil-linja n hawn fuq l-avviż qiegħ hemm żminijiet n log ta 'ln,

130
00:07:48,820 --> 00:07:51,410
u aħna ser tara dak li dan ifisser qabel twil.

131
00:07:51,410 --> 00:07:56,010
Fuq din huwa n kwadrat, u aħna ma bbenefikawx xi algoritmi kwadru n għadhom imma aħna waslu biex.

132
00:07:56,010 --> 00:07:57,660
U li jistenna tassew ħżiena.

133
00:07:57,660 --> 00:08:01,610
Hemm 2 għall-n, xi ħaġa esponenzjali, li jħoss saħansitra agħar.

134
00:08:01,610 --> 00:08:05,760
And yet, curiously, allura hemm n kubiku, li jekk int it-tip ta 'ħsieb quddiem,

135
00:08:05,760 --> 00:08:10,000
jekk inti tip ta 'tagħmel l-matematika, 2 għall-n attwalment isir ferm straighter,

136
00:08:10,000 --> 00:08:15,930
ħafna ogħla milli n up kubiku jekk inti tħares lejn l-assi biżżejjed out.

137
00:08:15,930 --> 00:08:19,890
Allura Avviż dritt issa dawn l-assi huma arbitrarjament 2-10 fuq l-assi x.

138
00:08:19,890 --> 00:08:21,770
>> U dak ma jfisser?

139
00:08:21,770 --> 00:08:23,890
Dan ifisser 2 nies sa 10 nies fil-kamra.

140
00:08:23,890 --> 00:08:27,200
Li kollox mezzi x: daqs tal-problema, tkun xi tkun il-kuntest huwa.

141
00:08:27,200 --> 00:08:30,420
U l-assi vertikali dritt issa huwa numru ta 'sekonda jew numru ta' passi -

142
00:08:30,420 --> 00:08:31,840
xi unità ta 'ħin.

143
00:08:31,840 --> 00:08:34,740
Iżda avviż li għamilhom 0 sa 60 u 0-10.

144
00:08:34,740 --> 00:08:38,549
Imma jekk aħna tip ta 'zoom out, kif inti tista' fl-Excel jew xi softwer iċċartjar,

145
00:08:38,549 --> 00:08:43,370
u immorru sa 200.000, avviż li xi ħaġa bħal 2 sa n

146
00:08:43,370 --> 00:08:47,520
se kompletament jisbqu l-ħinijiet kurrenti ta 'n kwadrat,

147
00:08:47,520 --> 00:08:50,960
n kubiku, n log n - kollox konna tkellimna dwar s'issa.

148
00:08:50,960 --> 00:08:54,190
And yet-qabda huwa meta tibda titkellem dwar affarijiet bħal Facebook

149
00:08:54,190 --> 00:08:57,150
fejn ikollok, ħafna ħafna, ħafna nies kollha interkonnessi,

150
00:08:57,150 --> 00:09:00,650
għandek n-nies, li kull wieħed minnhom jista 'jkollhom bħala ħafna bħala ħbieb n

151
00:09:00,650 --> 00:09:02,860
jekk kulħadd huwa tip ta 'buddy buddy-fid-dinja,

152
00:09:02,860 --> 00:09:08,100
ukoll, dan huwa n darbiet n diġà, b'tali mod li l-ħbiberiji n possibbli kwadri,

153
00:09:08,100 --> 00:09:10,950
mill-inqas fl-1 direzzjoni, n ħbiberiji possibbli kwadru.

154
00:09:10,950 --> 00:09:15,330
Allura li diġà jissuġġerixxi li tiftix graff soċjali Facebook, biex ngħidu hekk,

155
00:09:15,330 --> 00:09:18,090
jistgħu jibdew jiġu espressi dawn it-tipi ta 'formuli.

156
00:09:18,090 --> 00:09:19,820
>> Aħna ser jiġu lura u tagħmel dan ħafna aktar konkreti,

157
00:09:19,820 --> 00:09:23,280
iżda għal issa, l-għan għall-ġimgħat ħafna li jmiss

158
00:09:23,280 --> 00:09:27,170
se tkun żgur li ma tmur dwar algoritmi implimentazzjoni jew tal-kodiċi

159
00:09:27,170 --> 00:09:29,870
li jispiċċaw teħid ta 'żmien kemm xi ħaġa bħal din.

160
00:09:29,870 --> 00:09:33,110
Imma l-ħaġa affaxxinanti dwar ix-xjenza tal-kompjuter jekk inti tkompli fuq f'dan il-qasam

161
00:09:33,110 --> 00:09:38,320
tieħu klassijiet bħal CS121, CS124, it-tnejn li huma korsijiet teorija,

162
00:09:38,320 --> 00:09:41,300
hija li hemm attwalment xi problemi li jeżistu f'dan dinja

163
00:09:41,300 --> 00:09:45,710
li fundamentalment, safejn nafu, ma jistgħux jiġu solvuti aktar malajr

164
00:09:45,710 --> 00:09:48,880
mill-agħar ta 'dawn graffs attwalment jissuġġerixxi.

165
00:09:48,880 --> 00:09:53,660
Allura hemm ħafna problemi miftuħa f'din id-dinja li jagħmlu ħafna aħjar minn bnedmin ikollhom s'issa.

166
00:09:53,660 --> 00:09:56,130
>> Mela ejja nibdew imbagħad ma dan l-eżempju.

167
00:09:56,130 --> 00:09:59,650
Rajna taqbida Sean ma 'din camera fuq, wisq awkwardly fuq video.

168
00:09:59,650 --> 00:10:05,270
Iżda r-realtà kien meta Sean kienet imqabbda konstatazzjoni fuq bord bħal dan in-numru 7,

169
00:10:05,270 --> 00:10:10,300
ifakkar li jien qal li, "Hemm x'imkien wara dawn il-biċċiet tal-karti jew bibien abjad

170
00:10:10,300 --> 00:10:12,570
"In-numru 7. Sean, isibuha għalina."

171
00:10:12,570 --> 00:10:14,200
U kien wonderfully skomdi għall-għassa

172
00:10:14,200 --> 00:10:15,790
għaliex kien verament qed jitħabtu ma 'din il-problema.

173
00:10:15,790 --> 00:10:19,720
Iżda r-realtà kienet Sean ma kif ukoll xi ħadd fil-kamra jista 'jkollha jsir.

174
00:10:19,720 --> 00:10:21,890
Huwa ħa ftit itwal minn persuna tipiku jista 'jkollhom,

175
00:10:21,890 --> 00:10:24,760
iżda huwa preżunt li kien hemm xi trick għal din il-problema,

176
00:10:24,760 --> 00:10:26,590
huwa preżunt li kien xi ħaġa nieqsa.

177
00:10:26,590 --> 00:10:29,320
U ma jgħinu li mijiet ta 'l-għajnejn kienu li jkollhom isfel fuq lilu.

178
00:10:29,320 --> 00:10:34,250
>> Iżda r-realtà kienet jekk il-kontribut għall-problema huwa mazz ta 'numri bl-addoċċ

179
00:10:34,250 --> 00:10:37,120
u int qed jintalbu biex isibu 1 in-numru,

180
00:10:37,120 --> 00:10:39,770
l-aħjar li tista 'tagħmel huwa tfittxija lineari.

181
00:10:39,770 --> 00:10:44,060
Ibda fuq ix-xellug, jimxu lejn il-lemin, jew jibda fil-dritt, jimxu lejn ix-xellug.

182
00:10:44,060 --> 00:10:48,300
Retroattivament, aħna tista 'tkun ħsieb, "Sean, għaliex ma inti biss tibda mill-tarf l-ieħor?"

183
00:10:48,300 --> 00:10:52,120
Ukoll, 7 setgħet daqstant faċilment kien hawn saltwarjament,

184
00:10:52,120 --> 00:10:54,980
iżda I deliberatament tqiegħed lilha hemmhekk minħabba I dehret hu mhux se jibda fl-aħħar.

185
00:10:54,980 --> 00:10:59,320
So I tip ta 'manipulati-sitwazzjoni, iżda b'kumbinazzjoni każwali 7 seta' kien kullimkien.

186
00:10:59,320 --> 00:11:02,380
Allura jibda mill-aħħar id-dritt seta 'kien aħjar imbagħad,

187
00:11:02,380 --> 00:11:04,320
imma dak jekk il-sena li jmiss I jiċċaqalqu 7 x'imkien ieħor?

188
00:11:04,320 --> 00:11:06,830
Li mhux soluzzjoni fundamentalment ġdid għall-problema -

189
00:11:06,830 --> 00:11:10,520
jibdew mill-1 tarf jew l-oħra - meta int tingħata l-ebda suppożizzjonijiet oħra.

190
00:11:10,520 --> 00:11:13,620
Allura Sean bdiet tfittex permezz-numri u qal, "5. Li mhux hawn."

191
00:11:13,620 --> 00:11:17,280
Imbagħad huwa mar hawn u raw 19, imbagħad huwa waqfa qasira għal madwar 20 sekondi,

192
00:11:17,280 --> 00:11:22,330
allura huwa kien fetaħ dan għal 13, u mbagħad ħareġ ċar

193
00:11:22,330 --> 00:11:24,270
li ma jidhirx li hemm tendenza hawn.

194
00:11:24,270 --> 00:11:28,090
Ma kienx 1, 2, 3, 4 jew simili. Kien hemm lakuni fil-numri, li ma jgħinu.

195
00:11:28,090 --> 00:11:32,320
U wkoll, il-fatt li I użati dawn il-biċċiet irħas ta 'karta biex tkopri up in-numri

196
00:11:32,320 --> 00:11:35,270
huwa attwalment intenzjonata, għaliex jekk I jitneħħew dawn biċċiet tal-karti,

197
00:11:35,270 --> 00:11:38,760
ħafna minna, Sean inklużi, probabbilment kien glanced tip ta 'makroskopikament

198
00:11:38,760 --> 00:11:43,410
fil-blackboard u qal, "Oh, 7 hija ovvjament hemm dritt." Aħna ma kien istantanjament.

199
00:11:43,410 --> 00:11:46,460
>> U li jista 'jkun il-mod il-moħħ tal-bniedem xogħlijiet sa ċertu punt,

200
00:11:46,460 --> 00:11:50,730
iżda fir-realtà, l-għajnejn tiegħu jew mind kien probabbilment xkumar-numri mill-lemin għax-xellug,

201
00:11:50,730 --> 00:11:55,190
xellug għal-lemin, middle fuq barra - xi ħaġa li kien għaddej fiżjoloġikament

202
00:11:55,190 --> 00:11:57,640
tali li qisni kien qed jiġri istantanjament,

203
00:11:57,640 --> 00:12:01,360
iżda odds huma saħansitra internament kien hemm xi tip ta 'metodoloġija għall-konstatazzjoni 7.

204
00:12:01,360 --> 00:12:05,160
U fil-fatt, issa li aħna qed jitkellem dwar arrays u strutturi ta 'data

205
00:12:05,160 --> 00:12:08,780
u ġewwa memorja ta 'kompjuter, l-unika ħaġa aħna bnedmin tista' tagħmel

206
00:12:08,780 --> 00:12:13,070
hu li tħares lejn postijiet memorja individwali 1 kull darba.

207
00:12:13,070 --> 00:12:16,600
>> Allura kull post ieħor tista 'ukoll tkun koperta up ma' wħud biċċa karta

208
00:12:16,600 --> 00:12:21,170
għaliex aħna ma tistax tara dan xorta waħda. Nistgħu biss tagħmel 1 ħaġa kull darba.

209
00:12:21,170 --> 00:12:25,030
Allura f'dan il-każ, fil-każ Sean, aħna marru hawn u mbagħad aħna marru hawn

210
00:12:25,030 --> 00:12:31,040
u allura aħna marru hawn, hawn, hawn, hawn, ltqajna għaqlija sa tmiem

211
00:12:31,040 --> 00:12:34,450
u biss tip ta 'skipped dan wieħed arbitrarju u sabet 7 hemmhekk.

212
00:12:34,450 --> 00:12:37,470
Dan wieħed ma kienx partikolarment speċjali. Hija wisq kien out of order.

213
00:12:37,470 --> 00:12:39,530
Imma hu finalment sabet 7.

214
00:12:39,530 --> 00:12:45,360
Imma issa l-takeaway verament hija li l-aħjar li tista 'tagħmel meta jingħata l-ebda informazzjoni

215
00:12:45,360 --> 00:12:50,400
għajr numri bl-addoċċ magħżula huwa li tibda mill-xellug jew tibda minn fuq il-lemin.

216
00:12:50,400 --> 00:12:54,950
Jew Heck, inti tista saltwarjament jiftħu bibien, imma anki allura dak ma jfisser li jkun każwali?

217
00:12:54,950 --> 00:12:57,220
Well, aħna d jkollhom li b'xi mod jifformalizzaw xi jfisser li tibda hawn,

218
00:12:57,220 --> 00:13:01,150
imbagħad mur hawn, imbagħad mur hawn. Sean ma kbira, u kien biss gost nara.

219
00:13:01,150 --> 00:13:06,340
X'jiġri jekk minflok nagħmlu l-bidla l-problema ftit u żid sal Sean din is-sena, jekk inti se?

220
00:13:06,340 --> 00:13:09,460
Would xi ħadd tkun komda ġejjin fuq il-palk u jsolvu problema kemmxejn differenti

221
00:13:09,460 --> 00:13:12,330
u li jidhru fuq camera?

222
00:13:12,330 --> 00:13:15,720
>> Ejja ħa mmorru lil hinn mill-orkestra għaliex inti guys kienu pjuttost involuti llum diġà.

223
00:13:15,720 --> 00:13:21,430
Kif dwar fil roża, fil-kappell? Come fuq l isfel. X'inhu l-isem tiegħek? >> Alex. >> Alex. Okay.

224
00:13:21,430 --> 00:13:24,580
Allura Alex se tkun Sean din is-sena u se jidher fil-snin li ġejjin

225
00:13:24,580 --> 00:13:27,770
valur ta 'CS50 lectures.

226
00:13:27,770 --> 00:13:30,340
Alex, sbieħ li jissodisfaw inti. >> Nizza li jissodisfaw inti wisq.

227
00:13:30,340 --> 00:13:33,470
L-isfida fil-idejn għalik huwa li ikollok daqsxejn aktar faċli

228
00:13:33,470 --> 00:13:38,950
f'dak jien tghidlek l-istess numri huma hawnhekk, iżda huma issa magħżula.

229
00:13:38,950 --> 00:13:41,800
Allura issa għan tiegħek hu li ssib il-numru 7.

230
00:13:41,800 --> 00:13:45,370
U fil-fatt, għandna verament jagħmlu dan - it-tip you're ta 'qerq, bħal kompjuter se le,

231
00:13:45,370 --> 00:13:47,990
billi tħares lejn dak in-numri kienu mument ilu.

232
00:13:47,990 --> 00:13:50,360
Ma 'ġibs dan fil-fatt mhux se jgħinu kollha li ħafna,

233
00:13:50,360 --> 00:13:52,810
imma ejja nippretendu li inti ma tafx x'inhu l-array oriġinali.

234
00:13:52,810 --> 00:13:56,600
Kulma għandek tkun taf issa huwa li inti għandek firxa ta 'numri magħżula

235
00:13:56,600 --> 00:14:00,360
li jista 'jkollhom lakuni bejniethom, u mira tiegħek huwa li jinstabu n-numru 7.

236
00:14:00,360 --> 00:14:05,080
Kif inti, bniedem raġonevoli li, imorru jsibu l-għadd 7?

237
00:14:05,080 --> 00:14:07,770
>> Mur minn baxxi għal għoljin? Okay. >> Mur baxxi għal għoljin.

238
00:14:07,770 --> 00:14:10,990
U ma jitqattax lilhom off. Ejja biss lift up hekk nistgħu jerġgħu jużawhom.

239
00:14:10,990 --> 00:14:14,730
Okay, so 1. Stenna. Qabel ma inti żżomm għaddej, li kien 1, kjarament żbaljat.

240
00:14:14,730 --> 00:14:17,270
Allura x'inhu għaddej permezz ta 'moħħok li jmiss? X'hemm pass li jmiss tiegħek?

241
00:14:17,270 --> 00:14:23,250
Il-li jmiss waħda. Okay. >> Il-li jmiss waħda. Tajba. 3, hekk żbaljata. X'hemm pass li jmiss tiegħek?

242
00:14:23,250 --> 00:14:27,670
Żomm għaddejjin. >> Kull dritt. Żomm għaddejjin. 5.

243
00:14:27,670 --> 00:14:31,110
Sabiex iżommu għaddejjin, u let me inti idejn dan għal posterità.

244
00:14:31,110 --> 00:14:35,720
7. >>. Eċċellenti Tajjeb ħafna. Misjuba n-numru 7. [Applause]

245
00:14:35,720 --> 00:14:39,720
Allura li kienet tajba, imma Sean wisq sabu l numru 7.

246
00:14:39,720 --> 00:14:44,490
U jien jargumentaw li int ma verament sfruttati din il-biċċa ta 'informazzjoni addizzjonali,

247
00:14:44,490 --> 00:14:47,780
li huwa li dawn in-numri huma magħżula.

248
00:14:47,780 --> 00:14:51,520
Allura nistgħu nagħmlu aħjar? Xi suġġerimenti hawn? Yeah, fid-dahar.

249
00:14:51,520 --> 00:14:54,710
[Student] search Binarju. >> Għandi l-ebda idea dak li tfittxija binarja hu.

250
00:14:54,710 --> 00:14:58,030
>> [Student] Tibda fin-nofs. >> Bidu fin-nofs. Okay. Mela ejja ara jekk nistgħu naslu s'hemm.

251
00:14:58,030 --> 00:15:02,580
Mela jekk minflok int told bidu mill-nofs, imorru quddiem u tiftaħ il-bieb tan-nofs.

252
00:15:02,580 --> 00:15:04,580
Hemm 8 minnhom, hekk int se jkollhom arbitrarjament jagħżlu l-waħda

253
00:15:04,580 --> 00:15:09,800
ftit lejn ix-xellug jew lejn il-lemin. Okay. 7! [Applause] Sbieħ ħafna.

254
00:15:09,800 --> 00:15:11,410
Okay, iżda fejn kienu aħna jmorru ma 'dan?

255
00:15:11,410 --> 00:15:14,990
Ejja nassumu biss biex jiksru r-rabta li inti kien beda hawn

256
00:15:14,990 --> 00:15:16,670
minħabba li ugwalment seta 'ġara ukoll.

257
00:15:16,670 --> 00:15:19,540
Aħna biss ġara li tkun taf li 7 kien hemm. Allura dan huwa 13.

258
00:15:19,540 --> 00:15:21,980
Mela jekk dawn qed magħżula u aħna kemm bdiet fin-nofs,

259
00:15:21,980 --> 00:15:24,600
dak li l-pass li jmiss aħjar ġew?

260
00:15:24,600 --> 00:15:27,740
Mur fuq ix-xellug. U hekk hawn jidħol l-eżempju ktieb tat-telefon ġdid.

261
00:15:27,740 --> 00:15:30,130
Jekk 13 huwa hawnhekk u nafu l-lista hija magħżula,

262
00:15:30,130 --> 00:15:33,900
allura kollha ta 'dawn il-biċċiet tal-karti huma uninteresting lilna issa

263
00:15:33,900 --> 00:15:37,400
għaliex aħna diġà jafu li 7 għandu jkun lejn ix-xellug

264
00:15:37,400 --> 00:15:39,510
jekk dawn in-numri huma magħżula u sibna 13.

265
00:15:39,510 --> 00:15:42,500
>> Allura x'hemm pass li jmiss tiegħek hawn? >> Mur lejn ix-xellug. >> Okay, tajba.

266
00:15:42,500 --> 00:15:45,080
Allura jmorru lejn ix-xellug, u - stenna, ħej, ħej, ħej. Li qerq.

267
00:15:47,140 --> 00:15:51,350
Allura inti misjuba 7, iżda dak li kien l-algoritmu aħna biss applikati?

268
00:15:51,350 --> 00:15:56,450
Ibda fin-nofs. >> Tajba. Allura x'inhu l-estensjoni loġika ta 'dik l-idea istess?

269
00:15:56,450 --> 00:15:58,970
Oh, għal ftit dawn. >> Eżattament. >> So I tibda hawn. >> Tajba.

270
00:15:58,970 --> 00:16:02,020
Allura issa aħna marru ftit lejn ix-xellug mill-ġdid. Huwa 3.

271
00:16:02,020 --> 00:16:05,310
Iżda l-takeaway interessanti issa hija li wieħed do inti ma għandekx għall-kura dwar?

272
00:16:05,310 --> 00:16:08,040
Dawn 2. >> Dawn 2. Allura issa dan wieħed jista 'jmur lil hinn, dan wieħed jista' jmur lil hinn.

273
00:16:08,040 --> 00:16:12,330
Issa l-problema li kienet ta '8 allura kien 4 Daqs issa huwa daqs 2.

274
00:16:12,330 --> 00:16:16,430
Aħna jkollna pretty qrib. Għal darb'oħra, mur l-nofs ta 'dawn l-elementi 2.

275
00:16:16,430 --> 00:16:20,430
>> Okay. Allura huwa tip ta 'ħasra li issa aħna qed dejjem se titħalla għaliex aħna qed arrotondament' l isfel.

276
00:16:20,430 --> 00:16:25,150
Iżda li l-multa minħabba li issa għandna tarmi dan bogħod u kull ħaġa oħra, jħallu lilna ma 'biss 7.

277
00:16:25,150 --> 00:16:30,490
Ejjew nagħtu rawnd ta 'applause. Sibna 7 mill-ġdid. [Applause] Okay. Sure.

278
00:16:30,490 --> 00:16:32,220
Tistrieħ fuq għal biss 1 aktar 2.

279
00:16:32,220 --> 00:16:36,630
Anki jekk dan it-tip proċess li jmiss ta ħadu ftit itwal minn ħassejna li kieku,

280
00:16:36,630 --> 00:16:40,150
franchement, instincts tiegħek l-ewwel kienu l-aħjar, id-dritt? Sibna 7 istantanju.

281
00:16:40,150 --> 00:16:46,740
Iżda aħna sabu 7 aktar malajr, l-ebda kwistjoni dak, f'dan l-eżempju kontra dan wieħed

282
00:16:46,740 --> 00:16:50,100
għaliex jekk in-numri huma kollha magħżula, ħafna bħall-paġni fil-ktieb tat-telefon,

283
00:16:50,100 --> 00:16:54,580
inti tista 'tabilħaqq CHOP nofs il-problema mill-ġdid u għal darb'oħra u għal darb'oħra.

284
00:16:54,580 --> 00:16:56,740
U m'humiex daqshekk faċli biex tara dan biss bi 8 numri

285
00:16:56,740 --> 00:17:00,100
bħala kuntrarju għal ktieb tat-telefon 1000-paġna fejn inti verament tara dan viżwalment,

286
00:17:00,100 --> 00:17:03,120
imma f'dan il-każ hawnhekk meta Sean kien it-tiftix għal 7,

287
00:17:03,120 --> 00:17:06,020
kemm passi fil-agħar każ ikun jidher ħadu lilu? >> [Student] 7.

288
00:17:06,020 --> 00:17:11,670
7 fil-agħar każ. Ukoll, fl-agħar każ mhux 7 jekk ikun hemm 8 bibien hawn.

289
00:17:11,670 --> 00:17:13,440
Dan kien jieħu lilu 8 passi.

290
00:17:13,440 --> 00:17:18,170
>> Mela jekk hemm taċ-bibien n, jista ħadu Sean ftit snin ilu passi n.

291
00:17:18,170 --> 00:17:21,520
Issa, fil-każ tiegħek, Alex, peress li dawn in-numri huma magħżula -

292
00:17:21,520 --> 00:17:25,130
u nistgħu tip ta 'jiddeduċu dan minn fejn aħna ħadthom ġiet s'issa f'din l-istorja -

293
00:17:25,130 --> 00:17:28,300
x'inhu l-ħin tmexxija ta 'l-algoritmu aktar intelliġenti Alex

294
00:17:28,300 --> 00:17:30,770
tal-bidu mill-nofs u mbagħad tirrepeti?

295
00:17:30,770 --> 00:17:36,490
[Student] 3. >> Allura li għaddej biex tkun 3, bejn wieħed u ieħor, jekk inti tmur 8-4 għal 2 sa 1.

296
00:17:36,490 --> 00:17:40,660
Allura 3 passi jew, b'mod aktar ġenerali, li l-log n-ġdid.

297
00:17:40,660 --> 00:17:43,380
Kwalunkwe ħin li inti qed tonqos bin-nofs u tnaqqas bin-nofs u tnaqqas bin-nofs u tnaqqas bin-nofs,

298
00:17:43,380 --> 00:17:45,290
li l-espressjoni ta 'din l-idea ta' log n.

299
00:17:45,290 --> 00:17:48,140
U hekk li kien jieħu inti biss 3 passi, u fil-fatt għamlet

300
00:17:48,140 --> 00:17:50,890
ladarba aħna miftuħa l-bibien tnaqqis bin-nofs u tnaqqas bin-nofs,

301
00:17:50,890 --> 00:17:53,770
billi dan kien jieħu Sean xi 7 jew 8 passi.

302
00:17:53,770 --> 00:17:56,330
Allura nirringrazzjak talli magħna din is-sena. >> Grazzi. Nizza laqgħa inti.

303
00:17:56,330 --> 00:18:00,170
Grazzi lil Alex. >> Bl-istess mod. [Applause]

304
00:18:00,170 --> 00:18:02,150
>> X'hemm allura l-implikazzjoni reali ta 'dan?

305
00:18:02,150 --> 00:18:06,050
Issa immaġina li mhuwiex 8 bibien, li, franchement, lkoll jistgħu jsibu xi ħaġa

306
00:18:06,050 --> 00:18:10,430
wara 8 bibien pretty malajr biss billi tiċċarrat-biċċiet tal-karti u jmorru mal instincts tagħna.

307
00:18:10,430 --> 00:18:14,430
Imma x'jiġri jekk huwa xi bibien miljun? X'jiġri jekk huwa 4000000000 bibien?

308
00:18:14,430 --> 00:18:19,630
Fil-każ ta '4 biljun bibien, int verament se tixtieq li tmur ma algoritmu Alex, l-

309
00:18:19,630 --> 00:18:23,150
binarja tfittxija kif aħna ser tibda ssejjaħ dan jew jaqsmu u jirbħu, b'mod aktar ġenerali,

310
00:18:23,150 --> 00:18:25,220
fejn inti żżomm tnaqqis bin-nofs u tnaqqas bin-nofs l-problema,

311
00:18:25,220 --> 00:18:30,510
għaliex jekk ikollok 4000000000 bibien, kif ħafna drabi tista 'inti CHOP 4 biljun fl-nofs?

312
00:18:30,510 --> 00:18:33,870
[Student] 32. >> Huwa fil-fatt 32. Tista 'taħdem dan out fuq biċċa karta jew fir-ras.

313
00:18:33,870 --> 00:18:38,490
Inti tmur 4000000000-2000000000 to 1 biljun għal nofs biljun, sa 250 miljun, dot, dot, dot.

314
00:18:38,490 --> 00:18:41,620
U jekk inti tagħmel l-matematika, int ser fil-fatt tikseb 32,

315
00:18:41,620 --> 00:18:44,950
u li attwalment tirrigwarda xjenza tal-kompjuter għaliex aħna normalment jgħodd poteri ta '2.

316
00:18:44,950 --> 00:18:47,600
2 għall-32 jiġri li jkun ta '4 biljun.

317
00:18:47,600 --> 00:18:51,440
Allura hemm ħafna ta 'rilevanza għall-dawn it-tipi ta' poteri ta '2 fix-xjenza tal-kompjuter.

318
00:18:51,440 --> 00:18:55,120
>> Imma xi ngħidu dwar 8000000000? Kemm passi huwa li se tieħu jekk ikun hemm 8000000000 bibien?

319
00:18:55,120 --> 00:19:00,350
[Student] 33. Allura 33. >> X'jiġri jekk hemm 16000000000 bibien? Kemm passi huwa li se jieħu?

320
00:19:00,350 --> 00:19:05,020
[Student] 34. >> 34. Nistgħu tip ta 'jkompli dan nauseam ad. Imma li l-ħaġa qawwija.

321
00:19:05,020 --> 00:19:09,430
Inti tista 'tintroduċi biljuni ta' inputs aktar għall-problema tiegħek, iżda, no big deal,

322
00:19:09,430 --> 00:19:14,140
inti biss tieħu 1 gidma addizzjonali minnha u b'hekk tagħtina xi ħaġa bħal tfittxija binarja

323
00:19:14,140 --> 00:19:15,920
jew jaqsmu u jirbħu, b'mod aktar ġenerali.

324
00:19:15,920 --> 00:19:17,990
Imma jien tip ta 'qerq hawn, id-dritt?

325
00:19:17,990 --> 00:19:22,410
Fil-każ ta 'algoritmu Alex, hija kellha l-vantaġġ fuq Sean.

326
00:19:22,410 --> 00:19:27,780
Kienet taf li dawn in-numri ġew magħżula, iżda Alex ma għandekx sort lilhom lilha nfisha.

327
00:19:27,780 --> 00:19:30,520
I bil-quddiem waslet sa l-blackboard u tip ta 'għamel żgur

328
00:19:30,520 --> 00:19:33,670
li I ġibdet minnhom kollha barra sabiex magħżul, imbagħad I koperti minnhom bil-karta.

329
00:19:33,670 --> 00:19:35,850
Imma kemm ix-xogħol ma dik jieħdu me?

330
00:19:35,850 --> 00:19:40,110
Jekk kellna bdew ma 'dawn in-numri f'xi ordni apparentement każwali -

331
00:19:40,110 --> 00:19:43,320
f'dan il-każ dawn in-numri sempliċi, 1 sa 8 hawn -

332
00:19:43,320 --> 00:19:46,090
kif do we go dwar l-għażla dawn il-valuri?

333
00:19:46,090 --> 00:19:52,530
Jekk inti kienu bniedem minħabba dan il-kompitu, liema tip ta 'approċċ intuwittivi se tieħu

334
00:19:52,530 --> 00:19:54,800
li issortjar mazz sħiħ ta 'numri?

335
00:19:54,800 --> 00:19:57,050
Dawn l-affarijiet kienu stabbiliti bħala biċċiet puzzle. Yeah.

336
00:19:57,050 --> 00:19:59,950
>> [Student] nerfa kull numru u jqabbilha għal kull wieħed

337
00:19:59,950 --> 00:20:03,180
u jibqgħu għaddejjin lejn ix-xellug. >> Okay, tajba.

338
00:20:03,180 --> 00:20:05,720
Sabiex jieħdu kull numru, din titqabbel ma 'dik li jmiss lilha,

339
00:20:05,720 --> 00:20:09,610
u mbagħad biss iżommu jimxu tul il-lista, tip ta 'rejiggering affarijiet kif tmur.

340
00:20:09,610 --> 00:20:13,800
Allura hawnhekk għandna ċans għal forsi ftit aktar folks biex jinvolvu ruħhom.

341
00:20:13,800 --> 00:20:16,290
Do għandna 8 voluntiera aktar li imħabba li toħroġ?

342
00:20:16,290 --> 00:20:23,950
Pressjoni ftit inqas peress li int mhux l-uniku wieħed. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Come fuq l isfel. You guys huma ser ikunu n-numri 1 sa 8.

344
00:20:28,190 --> 00:20:36,050
Ejja naraw jekk aħna ma tistax tagħmel dan issortjar għall Alex ħafna bl-istess mod I ma kien qabel.

345
00:20:36,050 --> 00:20:37,640
1, 2, 3, 4.

346
00:20:37,640 --> 00:20:40,760
Jimxi 'l quddiem u jekk inti, linja up fuq il-palk bejn l-istand tal-mużika u lili hawn

347
00:20:40,760 --> 00:20:44,960
fl-istess ordni bħall-slide fuq l-iskrin.

348
00:20:47,910 --> 00:20:49,680
Uh oh-.

349
00:20:50,370 --> 00:20:53,230
Aħna ser naħdmu inti fis-eżempju li jmiss. Oh, stenna, stenna. Here we go. Stenna.

350
00:20:53,230 --> 00:20:57,570
L-eżempju li jmiss huwa issa. Hawnhekk inti tmur. Numru 8. Come fuq up.

351
00:20:57,570 --> 00:21:00,270
Kull dritt. Sort yourselves skond dan.

352
00:21:00,270 --> 00:21:03,620
Żerżaq biss ftit għall-ġenb tal-mużika stand hawn.

353
00:21:03,620 --> 00:21:12,310
Allura aħna għandna 4, 2, 6 - tikseb fil hemm, minn hawn, hemm dritt - 3.

354
00:21:12,310 --> 00:21:17,570
Yeah. Okay. Inti tmur minn hawn. Le, inti toqgħod hemm.

355
00:21:17,570 --> 00:21:21,840
Yeah, hemm dritt. No jien żbaljat. Dritt hemmhekk. Okay, tajba ħafna. Okay.

356
00:21:21,840 --> 00:21:24,930
Allura issa ejja sort lilhom fl-ordni dejjem tiżdied.

357
00:21:24,930 --> 00:21:26,210
>> Kif nista tmur dwar kif isir dan?

358
00:21:26,210 --> 00:21:28,630
L-algoritmu li kien ġie propost mument ilu kien għaliex ma aħna biss iqabbel

359
00:21:28,630 --> 00:21:31,970
l-folks li huma tip ta 'ħdejn xulxin u mbagħad tiffissa kwalunkwe żbalji,

360
00:21:31,970 --> 00:21:33,540
jiċċaqalqu mix-xellug għal-lemin.

361
00:21:33,540 --> 00:21:36,580
Allura hawnhekk għandna 4 u 2, ovvjament out of order. Ejja tpartit inti. Okay.

362
00:21:36,580 --> 00:21:40,760
Allura issa jien ser jimxu l-linja. 4 u 6, Nope. [Daħk]

363
00:21:40,760 --> 00:21:45,010
6 u 8, pjuttost tajba. 8 u 1, let me tpartit inti guys. Kull dritt.

364
00:21:45,010 --> 00:21:48,030
Allura 8 u 3, tpartit inti guys.

365
00:21:48,030 --> 00:21:52,280
8 u 7, let me tpartit inti guys. 5 u 8, eċċellenti.

366
00:21:52,280 --> 00:21:54,820
I jagħtuk lista magħżula.

367
00:21:54,820 --> 00:21:56,860
Kull dritt. Allura ma pjuttost.

368
00:21:56,860 --> 00:22:01,180
Iżda huwa aħjar għax in-numri akbar - każ fil-punt 8 -

369
00:22:01,180 --> 00:22:04,030
jkunu tip ta 'effervexxentement up mill-xellug għal fuq il-lemin.

370
00:22:04,030 --> 00:22:08,010
Allura sirt 1 minnhom id-dritt, iżda jħoss bħal dan ma pjuttost issolvi l-problema.

371
00:22:08,010 --> 00:22:11,150
>> Allura dak li tipproponi nagħmlu jmiss? >> [Student] Żomm tagħmel dan. >> Aħna tkompli tagħmel dan.

372
00:22:11,150 --> 00:22:13,740
U realizzata, għal darb'oħra, aħna waqqafna affarijiet up bi ftit jkollhom l-bnedmin

373
00:22:13,740 --> 00:22:17,180
tip ta 'intelliġenti jirranġaw stess ibbażati fuq dak stampa,

374
00:22:17,180 --> 00:22:19,040
iżda issa għandna li jkunu ferm iktar metodiku.

375
00:22:19,040 --> 00:22:21,510
Aħna rridu nkunu algorithmic dwar dan bħallikieku aħna qed miktub kodiċi -

376
00:22:21,510 --> 00:22:23,520
f'dan il-każ pseudocode verbali.

377
00:22:23,520 --> 00:22:26,040
So let me biss jippruvaw li għal darb'oħra. Dan ħadmet pjuttost tajjeb. Hija ma issolviha.

378
00:22:26,040 --> 00:22:30,400
Iżda meta dubju, biss jippruvaw u erġa 'pprova. Allura 2 u 4, ma jgħinu aktar.

379
00:22:30,400 --> 00:22:33,200
4 u 6. Ah! 6 u 1, ftit aħjar issa.

380
00:22:33,200 --> 00:22:39,740
6 u 3, tajba. 6 u 7, 7 u 5, 7 u 8, tajba.

381
00:22:39,740 --> 00:22:44,060
U inti taf, I tista 'probabbilment jinjora 8 issa għaliex huwa fl-aħħar tal-lista.

382
00:22:44,060 --> 00:22:47,250
Forsi aħna ma jkollhomx għalfejn tinkwieta dwar xi ħadd li jmorru passat lilu.

383
00:22:47,250 --> 00:22:49,240
Imma ejja ara jekk thats suppożizzjoni sikuri.

384
00:22:49,240 --> 00:22:52,340
Issa lista hija - kkritikat - mhux magħżula. Ejja nippruvaw dan mill-ġdid.

385
00:22:52,340 --> 00:22:56,440
Allura 2 u 4, 4 u 1, 4 u 3.

386
00:22:56,440 --> 00:22:59,230
4 u 6, tajba. 6 u 5, tajba.

387
00:22:59,230 --> 00:23:04,890
6, 7, u 8, tajba. Iżda l-avviż, nista 'biss tieqaf hawn u issa tieqaf hawn issa?

388
00:23:04,890 --> 00:23:07,770
[Student] Iva. >> Yeah?

389
00:23:07,770 --> 00:23:11,160
X'jiġri jekk wieħed minnkom kien in-numru 9 it-triq kollha hemmhekk?

390
00:23:11,160 --> 00:23:13,640
Ikun kienu ġew magħżula. >> Tajba. Ikun kienu ġew magħżula l-ewwel darba madwar.

391
00:23:13,640 --> 00:23:16,050
Tajba. Mela ejja jmorru lura mill-ġdid. Aħna kważi hemm.

392
00:23:16,050 --> 00:23:22,800
1 u 2, 2 u 3, 3 u 4, 4 u 5, 5 u 6, 6 u 7, 7 u 8.

393
00:23:22,800 --> 00:23:26,640
>> I am isir issa, iżda, għal darb'oħra, jien kompjuter li tista 'biss tagħmel dak li jien qal li tagħmel,

394
00:23:26,640 --> 00:23:30,120
u rikollizzjoni biss tiegħi issa hija li I attwalment biss għamlet daqsxejn ta 'xogħol.

395
00:23:30,120 --> 00:23:31,700
Xi ħaġa inbidlet hawn.

396
00:23:31,700 --> 00:23:37,100
So I ma teknikament ikkonfermat viżwalment jew algorithmically li din il-lista hija tabilħaqq magħżula.

397
00:23:37,100 --> 00:23:40,720
Hekk biss għal miżura tajba, biss li jkun anali dwar dan, ejja tagħmel dan iż-żmien 1 aktar.

398
00:23:40,720 --> 00:23:44,040
Allura 1 u 2, 2 u 3, 3 u 4. U inti taf liema?

399
00:23:44,040 --> 00:23:46,190
Just għal miżura tajba, jien ser iżommu kont fuq naħa tiegħi din id-darba

400
00:23:46,190 --> 00:23:51,110
kemm swaps nagħmel biss hekk li jien naf kemm ix-xogħol stajt attwalment isir.

401
00:23:51,110 --> 00:23:56,930
3 u 4, 4 u 5, 5 u 6, 6 u 7, 7 u 8. Ebda swaps.

402
00:23:56,930 --> 00:24:00,800
Allura issa nixtieq leġittimament tkun idjota biex jagħmlu dan mill-ġdid

403
00:24:00,800 --> 00:24:03,330
għaliex jekk I ma ebda xogħol permezz ta 'dan pass tal-bnedmin,

404
00:24:03,330 --> 00:24:06,710
allura b'mod ċar li għaddej biex jerġa 'jiġri jekk l-ebda wieħed minnhom huwa tip ta saltwarjament

405
00:24:06,710 --> 00:24:10,410
kontradittorju li jiċċaqalqu minnhom infushom madwar. Allura issa I tista 'twaqqaf.

406
00:24:10,410 --> 00:24:15,120
Issa ejja titlob il-kwistjoni, kemm ix-xogħol ma 'dan fil-fatt tieħu me?

407
00:24:15,120 --> 00:24:18,260
Kemm passi ma din tieħu? >> N kwadru.

408
00:24:18,260 --> 00:24:20,400
Yeah, hekk n kwadru. Fejn tista 'tikseb n kwadrat minn?

409
00:24:20,400 --> 00:24:22,660
Int għandek tiċċekkja kull num -

410
00:24:22,660 --> 00:24:26,530
Hemm n-numri, u inti għandek tiċċekkja kull numru man-numri n-oħra.

411
00:24:26,530 --> 00:24:29,030
Tajba. >> Allura huwa n kwadru. >> Tajba.

412
00:24:29,030 --> 00:24:31,060
>> Allura jħoss simili jista 'jkun tajjeb ħafna n kwadrat, id-dritt?

413
00:24:31,060 --> 00:24:33,820
M'hemm l-n 'dawn guys, 8 speċifikament f'dan il-każ,

414
00:24:33,820 --> 00:24:37,590
imma kull darba I marru permezz ta din il-lista I kien li jqabbel l-ewwel persuna kontra t-tieni,

415
00:24:37,590 --> 00:24:39,650
it-tieni kontra l-3 ġdid u għal darb'oħra u għal darb'oħra,

416
00:24:39,650 --> 00:24:42,450
u meta sirt l-aħħar, dak li ma nagħmel? I redid dan.

417
00:24:42,450 --> 00:24:46,280
Allura jekk aħna tiġġeneralizza din l-ispjegazzjoni, aħna għandna n-nies

418
00:24:46,280 --> 00:24:51,090
u jien jagħmlu, ovvjament, 8 passi, n passi, kull darba mmur permezz ta 'dan algoritmu.

419
00:24:51,090 --> 00:24:56,070
Imma kif ħafna drabi fil-agħar każ għandi jkollhom jgħaddu din il-lista ta 'nies?

420
00:24:56,070 --> 00:24:59,370
[Student] N darbiet. >> Probabbilment n, id-dritt, minħabba li fl-agħar każ,

421
00:24:59,370 --> 00:25:03,410
x'hemm probabbilment l-arranġament tal-agħar każ ta 'dawn guys mill-get-go?

422
00:25:03,410 --> 00:25:06,520
Jekk dawn qed kompletament maqluba ordni

423
00:25:06,520 --> 00:25:09,310
minħabba biss jissoponi mentalment, let's - X'hemm isem tiegħek? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Okay. Allura Bowen, come fuq matul hawn għal ftit mument.

425
00:25:12,510 --> 00:25:16,150
>> Ejja ngħidu li Bowen kien hawn fil-bidu ta 'l-algoritmu,

426
00:25:16,150 --> 00:25:19,790
u ma nafux dak li kulħadd huwa, iżda Bowen hawnhekk, skond din algoritmu -

427
00:25:19,790 --> 00:25:23,820
u jekk inti tixtieq li biss stroll miegħi - se bużżieqa up, kif għamel l-ewwel darba madwar,

428
00:25:23,820 --> 00:25:25,740
it-triq kollha sa l-aħħar.

429
00:25:25,740 --> 00:25:29,400
Iżda jissoponi li l-persuna li jmiss għall Bowen kien in-numru 7.

430
00:25:29,400 --> 00:25:33,450
I ikollhom imorru lura u tikseb numru 7, li jfisser I ikollhom imorru-triq kollha lura hawn.

431
00:25:33,450 --> 00:25:36,980
Issa I għandhom ikollhom l-istess stroll mal-persuna li tkun numru 7.

432
00:25:36,980 --> 00:25:40,140
Imma x'jiġri jekk mbagħad numru 6 kien li jmiss lilu kif ukoll?

433
00:25:40,140 --> 00:25:42,180
Imbagħad I għandhom imorru lura u nikseb 6.

434
00:25:42,180 --> 00:25:46,490
Għalhekk għal darb'oħra, fuq kull iterazzjoni ta 'dan loop jien tkellem lil kull wieħed mill-poplu n,

435
00:25:46,490 --> 00:25:50,090
u I jista 'jkollhom biex jagħmlu n' dawn strolls biex tiżgura jien ġbid

436
00:25:50,090 --> 00:25:53,760
l-elementi kollha akbar lura u lura u lura lill-aħħar nett tal-lista.

437
00:25:53,760 --> 00:25:58,230
Affarijiet Allura n n darbiet huwa biss darba n n n kwadru jew.

438
00:25:58,230 --> 00:26:02,050
>> Allura hawnhekk diġà għandna algoritmu li m'għadux n, li m'għadhiex log n,

439
00:26:02,050 --> 00:26:04,820
huwa attwalment agħar minn kull ħaġa li aħna ghamilt qabel.

440
00:26:04,820 --> 00:26:09,840
Allura tip Alex tas ltqajna xxurtjati li għamilt kollha tal-ħidma apparentement bil-quddiem għall tagħha,

441
00:26:09,840 --> 00:26:14,690
kollha tax-xogħol għoljin, b'tali mod li hi tista 'tgawdi f'dan algoritmu tfittxija binarja,

442
00:26:14,690 --> 00:26:16,420
li huwa log ta 'n.

443
00:26:16,420 --> 00:26:18,240
Iżda dan huwa konsistenti ma 'tema nhar it-Tnejn.

444
00:26:18,240 --> 00:26:23,260
Aħna taw ftit spazju aktar, aħna użati bits aktar, sabiex iħaffu l-running time tagħna.

445
00:26:23,260 --> 00:26:26,170
Tant simili hemm dan kompromess bejn żmien u spazju,

446
00:26:26,170 --> 00:26:31,060
hemm jista 'wkoll jkun biss kompromessi bejn il-ħin mgħoddi up tip quddiem jkollna affarijiet lesta li tmur

447
00:26:31,060 --> 00:26:35,000
u fil-fatt eżekuzzjoni algoritmu simili tfittxija. Ejja nippruvaw ieħor.

448
00:26:35,000 --> 00:26:39,050
Jekk inti guys ma mind biss malajr titranġa infuskom biex jaqblu li għal darb'oħra,

449
00:26:39,050 --> 00:26:42,240
ejja tipprova xi ħaġa xi ftit differenti fejn mhuwiex daqshekk sempliċi

450
00:26:42,240 --> 00:26:45,760
kif biss tiffissa l-iżbalji pairwise, li huwa super intuwittivi.

451
00:26:45,760 --> 00:26:48,150
Ejja minflok jkun ftit aktar deliberata u jagħmlu dan.

452
00:26:48,150 --> 00:26:51,010
Dan wieħed wisq nipproponi li huwa probabbilment pjuttost intuwittivi.

453
00:26:51,010 --> 00:26:55,070
>> Ejja agħżel il-persuna iżgħar mil-lista mill-ġdid u għal darb'oħra. Allura here we go.

454
00:26:55,070 --> 00:26:57,350
4, inti l-persuna iżgħar stajt b'hekk qatt dehret sallum,

455
00:26:57,350 --> 00:27:00,520
hekk jien ser mentalment jiftakar li bi ftit tipponta lejn inti għal issa.

456
00:27:00,520 --> 00:27:05,020
2. Ooh! Tinsieh numru 4. I biss sabu l-element ġdid iżgħar f'din il-lista.

457
00:27:05,020 --> 00:27:07,410
Jien ser tip ta 'ftakar li. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ooh! 1. Goodbye. Allura issa jien se tiftakar numru 1.

459
00:27:11,190 --> 00:27:14,790
Aħna nafu li 1 huwa l-iżgħar, imma jien l-kompjuter. X'jiġri jekk hemm 0?

460
00:27:14,790 --> 00:27:17,140
X'jiġri jekk hemm -1? Għandi biex jibqgħu għaddejjin.

461
00:27:17,140 --> 00:27:20,990
Allura 3, 7, 5, Nope. Okay. Allura numru 1 kien l-iżgħar.

462
00:27:20,990 --> 00:27:23,640
Let me tagħżel int mil-lista - we'll go dan il-mod -

463
00:27:23,640 --> 00:27:27,760
u tpoġġi lilek arbitrarju fil-bidu tal-lista.

464
00:27:27,760 --> 00:27:29,740
Issa, stenna minuta. I tip ta 'misruqin.

465
00:27:29,740 --> 00:27:34,010
Jekk dawn guys jirrappreżentaw mhux lista ta '8 persuni, iżda firxa,

466
00:27:34,010 --> 00:27:37,050
8 biċċiet ta 'memorja kontigwu - do you mind pass lura għal ftit mument?

467
00:27:37,050 --> 00:27:39,060
Hemm fil-fatt ebda spazju għal dritt inti hawn.

468
00:27:39,060 --> 00:27:41,840
Allura kif nistgħu tagħmel spazju għall - x'hemm isem tiegħek? >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
Kif nistgħu tagħmel spazju għal Sammy?

470
00:27:43,710 --> 00:27:46,760
>> Nimxu 'l-n li huma qabel lili. Okay. >>

471
00:27:46,760 --> 00:27:48,850
Allura nistgħu jimxu l-persuni li huma n quddiemu,

472
00:27:48,850 --> 00:27:52,400
hekk jekk inti guys tixtieq li tieħu 1 deliberat, pass drammatika lejn ix-xellug.

473
00:27:52,400 --> 00:27:57,000
Huma kollha ma li jopponu ghal, imma aħħar darba I kiteb xi kodiċi,

474
00:27:57,000 --> 00:27:59,740
inti ma tistax issolvi tat jiċċaqalqu ħafna affarijiet kollha f'daqqa.

475
00:27:59,740 --> 00:28:02,450
Nistgħu nagħmlu dan fil-linja, li jiċċaqalqu kulħadd darba fi żmien.

476
00:28:02,450 --> 00:28:04,340
Mela jekk inti guys ma mind pass lura lejn il-lemin,

477
00:28:04,340 --> 00:28:07,230
u Sammy, jekk inti tista 'pass lura għaliex hemm għadu ebda kamra ghalik,

478
00:28:07,230 --> 00:28:11,420
issa ejja tagħmel dan. Fejn kien Sammy mument ilu? Dritt hemmhekk.

479
00:28:11,420 --> 00:28:16,140
Allura hemm lakuna hemmhekk. Allura inti tista 'timxi lejn post Sammy s.

480
00:28:16,140 --> 00:28:20,580
Issa persuna li jmiss up u issa persuna li jmiss, issa persuna li jmiss. Issa għandna kamra għal Sammy.

481
00:28:20,580 --> 00:28:23,490
Issa, xi ħadd mill-udjenza - li kienet tajba, li kienet korretta,

482
00:28:23,490 --> 00:28:27,070
li ħass ftit ħin - x'hemm aktar mgħaġġel? Yeah.

483
00:28:27,070 --> 00:28:29,440
[Student] A firxa ġdida? >> X'hemm li? >> [Student] A firxa ġdida? >> Okay, tajba.

484
00:28:29,440 --> 00:28:33,200
>> Allura konsistenti ma 'din it-tema ta' ftit kompromessi, għaliex ma I biss tagħmel firxa ġdida

485
00:28:33,200 --> 00:28:36,570
 u mbagħad Sammy se jkun għawm fl-ispazju quddiem ta 'dawn in-nies, per eżempju,

486
00:28:36,570 --> 00:28:39,600
u nistgħu biss tibda timla firxa ġdida għal kollox. Li wisq tkun taħdem.

487
00:28:39,600 --> 00:28:42,450
Imma jien ma interessati fl-infiq aktar spazju illum. X'hemm approċċ ieħor?

488
00:28:42,450 --> 00:28:46,630
[Student] Swap. Okay. >> Aħna jista 'biss tpartit dawn guys 2. X'hemm isem tiegħek?

489
00:28:46,630 --> 00:28:49,390
Mario. >> Mario. Allura Mario, inti kienu attwalment hawn.

490
00:28:49,390 --> 00:28:52,480
Sammy, inti tista 'back up għal ftit mument? Mario kien hawn.

491
00:28:52,480 --> 00:28:55,830
Aħna ma jkollhomx spazju għalik aktar, hekk jekk inti ma mind se fejn Sammy hija,

492
00:28:55,830 --> 00:29:02,430
aħna ser tpoġġi Sammy hawn, u issa I d jargumentaw li l-operazzjoni iskambji Sammy kien ħafna aktar mgħaġġla.

493
00:29:02,430 --> 00:29:06,370
Għamilna 1 tħaddim li tpartit dawn guys, jew forsi 2 li tpartit dawn guys,

494
00:29:06,370 --> 00:29:11,210
imma aħna ma tagħmel 1, 2, 3, 4, b'tali mod li jħoss aħjar. Issa, stenna minuta.

495
00:29:11,210 --> 00:29:14,660
I tip ta 'għamel l-problema agħar minħabba numru 4 kien tip ta' qrib il-bidu.

496
00:29:14,660 --> 00:29:19,470
Issa numru 4 huwa xi ftit aktar mill-qrib għal dan il-għan, imma jien ma verament jafu jew kura dwar dan.

497
00:29:19,470 --> 00:29:23,330
Allura dan huwa biss xortih ħażina li numru 4 huwa ftit aktar 'l bogħod mill-post destinat tagħha.

498
00:29:23,330 --> 00:29:25,110
Mela ejja issa irrepeti dan algoritmu.

499
00:29:25,110 --> 00:29:28,410
>> Biex terġa, sakemm li l-istorja kienet, kollox aħna ma kien walk permezz tal-lista

500
00:29:28,410 --> 00:29:31,130
tfittex l-persuna iżgħar nnumerati.

501
00:29:31,130 --> 00:29:34,530
Allura issa ejja jagħmlu mill-ġdid. Aħna ma jkollhomx għalfejn tinkwieta dwar Sammy aktar.

502
00:29:34,530 --> 00:29:37,590
Nistgħu biss jmorru hawn. Ooh! Numru 2. Li numru pjuttost żgħir.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. Okay, tajba.

504
00:29:41,180 --> 00:29:43,770
U Thankfully, b'kumbinazzjoni, jien ma jkollhom jimxu - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie għaliex huwa fil-post dritt tiegħu issa.

506
00:29:45,910 --> 00:29:48,110
Ejja nagħmlu dan mill-ġdid u jinjora dawn guys 2.

507
00:29:48,110 --> 00:29:50,460
6. Li numru pjuttost żgħir. Ooh! 8 hija definittivament akbar.

508
00:29:50,460 --> 00:29:53,410
4. Ejja niffukaw fuq 4. Ooh! 3 huwa anki aħjar.

509
00:29:53,410 --> 00:29:58,290
7 u 5. Allura dak li nagħmlu issa ma '- >> Roger. >> Roger?

510
00:29:58,290 --> 00:30:00,250
Ejja tpartit lilu bin-numru 6.

511
00:30:00,250 --> 00:30:03,570
Mela jekk 6 u 3 tixtieq li tpartit,

512
00:30:03,570 --> 00:30:07,320
konna issa tip ta gotten xxurtjati li 6 huwa eqreb lejn fejn hija għandha tkun,

513
00:30:07,320 --> 00:30:10,300
imma huwa biss koinċidenza hawn. Mela ejja issa mur hawn.

514
00:30:10,300 --> 00:30:13,430
8 huwa numru pjuttost żgħir. Ooh! 4 huwa iżgħar.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. What do we issa do? Swap. >> >> Eżattament.

516
00:30:17,130 --> 00:30:19,010
Allura issa ejja tagħmel dan it-tip ta mgħaġġel.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. Fejn ma 5 imorru? Tajba. Okay.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 gets li tissospendi fejn hi. X'hemm isem tiegħek? >> Rosalie.

519
00:30:28,380 --> 00:30:31,770
Rosalie gets li tissospendi fejn hi. 7 gets - Ejja naraw. 7, 8. Okay.

520
00:30:31,770 --> 00:30:35,100
Allura 7 gets li tissospendi fejn hi. X'hemm isem tiegħek? >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> Allura Amna gets li tissospendi fejn hi, u numru 8 huwa diġà fejn issa għandu jkun.

522
00:30:39,670 --> 00:30:43,960
Okay, tajba. Iħoss simili aħna qed biss joħolqu x-xogħol għalina hawnhekk, għalkemm.

523
00:30:43,960 --> 00:30:47,440
X'hemm finalment l-running time ta 'dan algoritmu?

524
00:30:47,440 --> 00:30:51,900
Jekk naħsbu dwar dawn in-nies mhux bħala 8, iżda bħala n? >> Huwa n.

525
00:30:51,900 --> 00:30:55,440
Huwa n-passi, imma aħna qed tkun eżaminata kull wieħed ħin.

526
00:30:55,440 --> 00:30:57,570
Okay. N imma int iċċekkjar kull wieħed ħin?

527
00:30:57,570 --> 00:31:03,450
Okay, iżda jekk huwa n-passi, m'għandux I kienu kapaċi biex issolvi lilek minn biss jmorru 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
Oh! Okay, li differenza kbira.

529
00:31:05,590 --> 00:31:08,050
Allura n kwadrat għaliex? X'qed verament jiġri?

530
00:31:08,050 --> 00:31:12,130
Hemm nies n f'din il-lista, iżda jsibu l-persuna iżgħar fil-lista

531
00:31:12,130 --> 00:31:16,200
fl-agħar każ, kemm passi għandi tieħu? >> N.

532
00:31:16,200 --> 00:31:19,160
>> N, id-dritt, minħabba li fl-agħar każ, in-numru 1 huwa it-triq kollha hemmhekk,

533
00:31:19,160 --> 00:31:20,990
so I ikollhom imorru nikseb lilu jew lilha.

534
00:31:20,990 --> 00:31:25,500
U mbagħad meta I finalment realizzata 1 kien l-iżgħar, allura huwa pjuttost malajr biex tpartit lilhom.

535
00:31:25,500 --> 00:31:28,450
Imma issa I għandhom jibdew mill-bidu u jfittxu għal min?

536
00:31:28,450 --> 00:31:31,980
Il-persuna li jmiss iżgħar, li huwa 2. Meta fil-każ agħar huwa 2?

537
00:31:31,980 --> 00:31:34,320
Oh, Alla tiegħi. Huwa it-triq kollha hawn fuq fl-aħħar.

538
00:31:34,320 --> 00:31:37,000
Allura issa stajt biss isir ieħor passi n, ieħor passi n.

539
00:31:37,000 --> 00:31:41,200
U jekk konna ltqajna nies n u fl-agħar każ il-persuna iżgħar hija n-passi bogħod,

540
00:31:41,200 --> 00:31:45,230
li l-jerġa n-ħinijiet n, u hekk aħna darb'oħra għandna n kwadru.

541
00:31:45,230 --> 00:31:47,280
Dan ma tħossok daqshekk tajjeb.

542
00:31:47,280 --> 00:31:52,150
U fil-fatt, anki fil-każ aħjar - jissoponi li dawn jibdew off magħżula -

543
00:31:52,150 --> 00:31:59,080
kemm passi ma jieħdu għalija li jużaw dan algoritmu biex issolvi dawn in-nies n?

544
00:31:59,080 --> 00:32:01,010
N kwadrat. >> Smajt n kwadru. Għaliex n kwadrat?

545
00:32:01,010 --> 00:32:05,240
Għaliex inti xorta għandek tiċċekkja kull wieħed ħin. >> Yeah.

546
00:32:05,240 --> 00:32:08,060
U inti għandek tpartit lilhom. >> Anki jekk aħna bnedmin huma tip ta 'omniscient

547
00:32:08,060 --> 00:32:10,770
fis-sens viżwalment li nistgħu biss tip ta 'tara li dan huwa magħżul,

548
00:32:10,770 --> 00:32:12,140
kompjuter ma tkunx dik intelliġenti.

549
00:32:12,140 --> 00:32:14,040
Huwa ser tfittex hawn u hawn u hawn,

550
00:32:14,040 --> 00:32:16,610
imma jekk dak huwa tfittex huwa l-element iżgħar,

551
00:32:16,610 --> 00:32:22,110
inti biss taf li inti tinstab l-element iżgħar minn dak il-punt? Ladarba int fl-aħħar.

552
00:32:22,110 --> 00:32:25,880
Iżda f'dak il-punt inti stajt biss sabu l-element bħalissa iżgħar.

553
00:32:25,880 --> 00:32:28,810
Inti ma neċessarjament jaf xi ħaġa oħra dwar l-istat tad-dinja.

554
00:32:28,810 --> 00:32:30,880
Allura inti għandek tmur għal darb'oħra u għal darb'oħra u għal darb'oħra.

555
00:32:30,880 --> 00:32:34,880
>> Allura dan iż-żmien I really do ħarsa mutu għaliex jien iċċekkjar, okay, 2, int l-iżgħar,

556
00:32:34,880 --> 00:32:37,530
imma jien ma nafx li b'kollox s'issa.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Okay, tajba. 2 kien tabilħaqq l-iżgħar.

558
00:32:41,090 --> 00:32:43,150
Issa ejja ssib il-iżgħar li jmiss. Okay.

559
00:32:43,150 --> 00:32:48,350
3, int bħalissa l-iżgħar. Ejja naraw. 4, 5, 6, 7, 8. Okay, ltqajna xxurtjati għal darb'oħra.

560
00:32:48,350 --> 00:32:53,170
3 kien tabilħaqq fil-post it-tajjeb. Imma jien ser iżommu tagħmel dan mill-ġdid u għal darb'oħra u għal darb'oħra.

561
00:32:53,170 --> 00:32:55,990
Kif nistgħu nagħmlu dejjem hekk ftit aħjar?

562
00:32:55,990 --> 00:33:00,120
Minflok ma jkollhom nies bużżieqa up pairwise minn iżgħar sa l-akbar

563
00:33:00,120 --> 00:33:04,350
u minflok tmur quddiem u lura permezz tal-lista għażla tal-persuna imbagħad iżgħar,

564
00:33:04,350 --> 00:33:09,780
għaliex ma we minflok daħħal dawn in-nies fi stadju lista ġdida mill-pass?

565
00:33:09,780 --> 00:33:13,080
Ejja nippruvaw dan. Issa let me sejħa dan it-tip inserzjoni ħaġa.

566
00:33:13,080 --> 00:33:17,250
Allura aħna qegħdin hawn hawn. Numru 1. I do not care about ħaddieħor f'din il-lista.

567
00:33:17,250 --> 00:33:21,310
L-għan tiegħi dritt issa huwa li tpoġġi numru 1 fil-bidu ta 'lista magħżula.

568
00:33:21,310 --> 00:33:23,910
U jien ser nipproponi peress li jien biss jkollhom 8 biċċiet ta 'memorja,

569
00:33:23,910 --> 00:33:28,670
arbitrarjament dritt issa I am il-ħajt bejn lista allegatament mhux magħżul tiegħi,

570
00:33:28,670 --> 00:33:32,740
u kulmin huwa lura lili jien ser jitolbu huwa magħżul.

571
00:33:32,740 --> 00:33:34,680
Allura issa għandna numru 1.

572
00:33:34,680 --> 00:33:39,240
Irrid li daħħal lilu fis lista magħżula tiegħi, hekk jien biss se jimxu ħajt tiegħi hawn fuq,

573
00:33:39,240 --> 00:33:43,930
u issa I jitolbu din il-lista huwa magħżul, din il-lista mhux magħżul - mill-inqas safejn naf.

574
00:33:43,930 --> 00:33:46,070
Ma nistax nara il-numri f'daqqa.

575
00:33:46,070 --> 00:33:49,000
>> Issa I jiġri li jiltaqgħu numru 2. What do I do miegħu?

576
00:33:49,000 --> 00:33:54,380
I daħħal inti issa fil-lista magħżula. Imma avviż kif faċli li kien.

577
00:33:54,380 --> 00:33:59,650
I biss għandek tfittex. Numru 1 hemm. Oh, ovvjament 2 tmur għall-naħa ta 'numru 1.

578
00:33:59,650 --> 00:34:03,700
Issa x'għandi nagħmel bi 3? I daħħal inti fil-lista magħżula. Iżda dan kien super faċli.

579
00:34:03,700 --> 00:34:07,250
Dan huwa super faċli, dan huwa super faċli, dan huwa super, super faċli faċli, faċli super.

580
00:34:07,250 --> 00:34:12,790
U issa kollox huwa magħżul lura lili, u kemm passi ma din tieħu?

581
00:34:12,790 --> 00:34:15,620
[Studenti] N. >> Allura huwa biss n. Aħna ltqajna xxurtjati.

582
00:34:15,620 --> 00:34:18,860
Kien biss n għaliex? >> [Student] Minħabba li l-lista ġiet magħżula.

583
00:34:18,860 --> 00:34:21,630
Il-lista hija diġà magħżula. Allura aħna ltqajna xxurtjati.

584
00:34:21,630 --> 00:34:25,639
Iżda aħna iddisinjat algoritmu dan iż-żmien li ċineg li tip ta 'xortih,

585
00:34:25,639 --> 00:34:29,420
li aħjar xenarju, billi ma ħela ta 'ħin bla bżonn.

586
00:34:29,420 --> 00:34:31,750
Allura issa għandna dak li aħna ser sejħa xorta bużżieqa

587
00:34:31,750 --> 00:34:33,949
fejn in-nies tip ta 'bużżieqa up pairwise.

588
00:34:33,949 --> 00:34:38,100
Issa għandna tip ta 'għażla fejn aħna ġewwieni l-persuna iżgħar u għal darb'oħra.

589
00:34:38,100 --> 00:34:42,350
U issa għandna tip inserzjoni fejn aħna xorta ta proattiv jpoġġi ż fejn huma jappartjenu

590
00:34:42,350 --> 00:34:45,000
f'lista dejjem magħżula.

591
00:34:45,000 --> 00:34:49,679
Jekk nistgħu, rawnd ta 'applause għal dawn guys hawn. [Applause]

592
00:34:49,679 --> 00:34:52,310
Ejja tieħu 5-minuta break tagħna hawn.

593
00:34:52,310 --> 00:34:55,139
U meta niġu lura, aħna se blow kollha ta 'dawn algoritmi barra mill-ilma

594
00:34:55,139 --> 00:35:00,260
ma 'xi ħaġa aħjar. Kull dritt. Grazzi ħafna. Tista 'żżomm dawk kif souvenirs.

595
00:35:01,710 --> 00:35:04,330
Kull dritt. Aħna lura.

596
00:35:04,330 --> 00:35:08,420
>> U biex terġa fast reali, kellna dawn l-approċċi differenti għall-għażla 3,

597
00:35:08,420 --> 00:35:13,000
il-punt kollu tagħha kien li jasal sal-punt fejn xi ħadd bħal Alex

598
00:35:13,000 --> 00:35:16,930
tista 'tfittex lista ta' numri aktar malajr milli xi ħadd bħal Sean jistgħu.

599
00:35:16,930 --> 00:35:19,830
U anki jekk aħna għandna eżempji sempliċi bħal ma 8 numri,

600
00:35:19,830 --> 00:35:24,000
inti tista 'faċilment tiġi estrapolata għal 8 paġni web, paġni tal-web 8000000000,

601
00:35:24,000 --> 00:35:26,680
jew 800000000 ħbieb fuq Facebook.

602
00:35:26,680 --> 00:35:30,090
Allura dawn algoritmi jistgħu ċertament iskala għal dawk it-tipi ta 'valuri,

603
00:35:30,090 --> 00:35:32,300
u l-ideat huma finalment l-istess.

604
00:35:32,300 --> 00:35:36,140
Sort bużżieqa Allura kien l-ewwel fejn aħna tip ta 'effervexxentement-persuna akbar

605
00:35:36,140 --> 00:35:39,110
it-triq kollha lejn il-lemin billi jiġu skambjati nies pairwise.

606
00:35:39,110 --> 00:35:42,040
Imbagħad kellna dak li aħna ser sejħa xorta għażla fejn I ftit aktar deliberatament

607
00:35:42,040 --> 00:35:46,480
tinżamm tfittex permezz tal-lista, l-għażla l-iżgħar numru ġdid u għal darb'oħra u għal darb'oħra,

608
00:35:46,480 --> 00:35:49,530
ir-riżultat loġiku tagħha huwa li l-lista eventwalment magħżula.

609
00:35:49,530 --> 00:35:53,780
Imbagħad fit-tielet waħda, I jiddaħħal in-nies fil-post xieraq tagħhom,

610
00:35:53,780 --> 00:35:57,720
u għamilna eżempju ħafna artifiċjali f'dik il-lista kienet diġà magħżula,

611
00:35:57,720 --> 00:36:01,100
iżda li kien jibgħat il-messaġġ li fil-każ tip inserzjoni, il-

612
00:36:01,100 --> 00:36:02,670
inti tista 'tikseb xorti.

613
00:36:02,670 --> 00:36:07,930
Jekk in-numri huma diġà magħżula, huwa biss se tieħu inti n passi biex tikkonferma kemm,

614
00:36:07,930 --> 00:36:10,870
billi sort għażla int viżjoni mina ftit aktar

615
00:36:10,870 --> 00:36:14,360
u inti qatt ma jirrealizzaw li l-lista hija diġà magħżula.

616
00:36:14,360 --> 00:36:16,830
Mela ejja ara sort bużżieqa fl-azzjoni hawn.

617
00:36:16,830 --> 00:36:19,590
Fl-eżempju li ġej, aħna qed madwar biex tara bars vertikali

618
00:36:19,590 --> 00:36:23,030
għoli li jirrappreżentaw numri sabiex inkunu nistgħu sort ta Ħares issortjar jiġri.

619
00:36:23,030 --> 00:36:26,630
L-iżgħar il-bar, l-iżgħar in-numru; l-akbar il-bar, l-akbar l-għadd.

620
00:36:26,630 --> 00:36:28,860
>> U aħna ser joqogħdu fuq din il-veloċità default.

621
00:36:28,860 --> 00:36:33,460
Huwa ser jimxu malajr ftit għal issa, imma aħmar huwa dak li juri 2 bars

622
00:36:33,460 --> 00:36:35,480
jiġu mqabbla ġenb ma 'ġenb.

623
00:36:35,480 --> 00:36:39,520
U jekk inti watch mill-qrib, dak li jiġri huwa li jekk il-vireg huma out of order,

624
00:36:39,520 --> 00:36:42,300
l-iżgħar wieħed gets jiċċaqalqu lejn ix-xellug, il-wieħed akbar lejn il-lemin,

625
00:36:42,300 --> 00:36:44,360
u allura inti żżomm avvanz.

626
00:36:44,360 --> 00:36:48,520
Allura jekk nagħmlu dan għal darb'oħra u għal darb'oħra, l-avviż li l-vireg iżgħar

627
00:36:48,520 --> 00:36:51,090
huma se jżommu inching triqthom lejn ix-xellug

628
00:36:51,090 --> 00:36:54,130
u l-vireg akbar huma ser iżommu inching triqthom lejn il-lemin.

629
00:36:54,130 --> 00:36:58,490
U fil-fatt, aħna qed jibdew biex tara mudell-triq kollha fuq in-naħa tal-lemin

630
00:36:58,490 --> 00:37:04,790
bħad rajna 8 u mbagħad eventwalment 7 tbaqbieq sa l-aħħar ħafna tal-lista tal-bniedem tagħna.

631
00:37:04,790 --> 00:37:08,750
Allura dan se malajr ħafna tikseb daqsxejn tedious, so let me twaqqaf dan għal mument.

632
00:37:08,750 --> 00:37:10,980
Let me jibdlu l-veloċità li jkunu ferm aktar mgħaġġla.

633
00:37:10,980 --> 00:37:15,380
Jien ma jinbidlu l-algoritmu, jien biss tagħmel l-animazzjoni iseħħ aktar malajr.

634
00:37:15,380 --> 00:37:18,410
Still bużżieqa tip, algoritmu istess,

635
00:37:18,410 --> 00:37:21,910
imma issa tista 'tara ħafna aktar mgħaġġla minn dimostrazzjoni verbali tagħna

636
00:37:21,910 --> 00:37:25,900
li l-elementi akbar huma tabilħaqq tbaqbieq sal-quċċata.

637
00:37:25,900 --> 00:37:29,860
>> Bħala twarrib, dawn kwadri ftit fil-qiegħ tax-xellug u l-qiegħ dritt

638
00:37:29,860 --> 00:37:33,520
huma biss ftit noti ta 'tfakkir dwar kif ħafna paraguni li qed isir.

639
00:37:33,520 --> 00:37:37,620
Iżda għal issa, nistgħu niffukaw fuq il-piramida li l-tieħu forma, u hemm din tmur.

640
00:37:37,620 --> 00:37:41,510
L-element iżgħar hija fuq ix-xellug, l-akbar fuq il-lemin u kull ħaġa oħra bejniethom.

641
00:37:41,510 --> 00:37:44,470
Issa ejja minflok tagħti ħarsa lejn it-tip ta 'għażla.

642
00:37:44,470 --> 00:37:47,260
Jien ser jimxi 'l quddiem u hit Stop. Aħna ser tikseb sett każwali ġdid ta 'bars.

643
00:37:47,260 --> 00:37:50,930
Sort Għażla, irtirar, tmur permezz tal-lista mill-ġdid u għal darb'oħra u għal darb'oħra,

644
00:37:50,930 --> 00:37:54,900
tnittif l-element iżgħar. Allura hawnhekk huwa tip ta 'għażla.

645
00:37:54,900 --> 00:37:58,390
Jidher qisu hemm ħidma anqas jiġri issa għaliex aħna mhux qed jitqabblu pairwise

646
00:37:58,390 --> 00:38:02,590
imma aħna qed biss tip ta 'cherry picking l-elementi iżgħar minn lemin għax-xellug.

647
00:38:02,590 --> 00:38:06,890
Dan ħa ftit żmien, hekk hemm dikotomija diġà.

648
00:38:06,890 --> 00:38:11,820
Sempliċiment għax algoritmu huwa qal li jieħdu n ħin kwadrat, bħall-tip bużżieqa

649
00:38:11,820 --> 00:38:16,100
u bħall sort għażla, dawn huma verament ħinijiet agħar każ running.

650
00:38:16,100 --> 00:38:21,790
Per eżempju, fil-każ ta ', ejja ngħidu, sort għażla,

651
00:38:21,790 --> 00:38:27,240
I attwalment am għażla tal-persuna iżgħar u t-tqegħid lilu jew lilha hawn,

652
00:38:27,240 --> 00:38:29,620
allura jien tagħmel dan mill-ġdid, imbagħad jien tagħmel dan mill-ġdid,

653
00:38:29,620 --> 00:38:32,070
iżda kien hemm ottimizzazzjoni żgħira I tista 'tagħmel.

654
00:38:32,070 --> 00:38:35,040
>> Hekk kif mort numru 1 hawn - Sammy f'dak il-każ -

655
00:38:35,040 --> 00:38:38,630
dak li għamlet I bżonn tagħmel miegħu wara? >> [Student] Leave lilu.

656
00:38:38,630 --> 00:38:40,140
Leave lilu, id-dritt? Xejn.

657
00:38:40,140 --> 00:38:44,310
I ma kellhomx bżonn li qatt jitkellem Sammy darb'oħra għaliex jekk kelli għażlet l-element iżgħar

658
00:38:44,310 --> 00:38:48,580
u jniżżlu hawn, għaliex iż-żmien l-iskart sejjer sa l-aħħar tal-lista sħiħa tiegħi?

659
00:38:48,580 --> 00:38:54,590
Fuq il-iterazzjoni li jmiss let me attwalment jimxu biss numru 2, biss għal numru 3.

660
00:38:54,590 --> 00:38:57,640
Allura fir-realtà, I ma kienx qed jagħmlu affarijiet n n darbiet.

661
00:38:57,640 --> 00:39:05,380
I kienet tagħmel affarijiet n, allura n - 1 affarijiet, allura n - 2 affarijiet, allura n - 3 affarijiet,

662
00:39:05,380 --> 00:39:07,080
allura n - 4, dot, dot, dot.

663
00:39:07,080 --> 00:39:09,470
Għandna daqsxejn ta 'serje ġeometrika, li sempliċiment ifisser

664
00:39:09,470 --> 00:39:11,450
int żżid up numri progressivament iżgħar.

665
00:39:11,450 --> 00:39:17,940
Mhux n + n + n + n, iżda n + 7 + 6 + 5 + 4 + 3 + 2 + 1.

666
00:39:17,940 --> 00:39:21,380
U dak li ġeneralment taħdem biex ikun -

667
00:39:21,380 --> 00:39:24,280
Jien ser mess up bord tiegħi hawn għal ftit mument -

668
00:39:24,280 --> 00:39:28,990
li għaddej biex jaħdmu biex tkun xi ħaġa bħal n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
jekk aħna biss tip ta 'ħarsa fuq wara ta' ktieb matematika fejn inti għandek l-folji iqarrqu

670
00:39:31,930 --> 00:39:33,410
għall-formuli.

671
00:39:33,410 --> 00:39:37,760
Jekk int sempliċement tiżdied xi ħaġa n + n - 1 + n - 2, hija taħdem biex tkun xi ħaġa bħal din.

672
00:39:37,760 --> 00:39:42,320
U jekk aħna biss tip ta 'immoltiplika dan out, li l-n kwadrat minus n / 2.

673
00:39:42,320 --> 00:39:46,400
I tinżamm qal n kwadrat, għalkemm, u dan għaliex I kien tip ta 'teħid ta' shortcut mentali

674
00:39:46,400 --> 00:39:51,950
għaliex fir-realtà, n kwadrat nieqes n diviż bi 2 huwa tabilħaqq in-numru reali ta 'passi

675
00:39:51,950 --> 00:39:55,510
li algoritmu bħal tip ta 'għażla se jieħu jekk aħna verament magħduda

676
00:39:55,510 --> 00:39:58,800
kollha ta 'dawk il-paraguni u kollha tal-ħidma busy ftit aħna kienu qed jagħmlu.

677
00:39:58,800 --> 00:40:03,210
Iżda franchement, ladarba n gets li jkun bħal miljun jew biljun, li l-Heck cares

678
00:40:03,210 --> 00:40:07,160
jekk inti qed tagħmel xi biljun nieqes kwadru ta 'biljun diviż bi 2?

679
00:40:07,160 --> 00:40:09,320
A biljun kwadru huwa numru kbir.

680
00:40:09,320 --> 00:40:13,580
Tista 'tieħu ieħor biljun off ta' dan ma '- n. Mhuwiex tali big deal.

681
00:40:13,580 --> 00:40:18,770
Allura l-akbar in-numri jiksbu, l-inqas importanti dawn it-termini ordnati aktar baxxi huma.

682
00:40:18,770 --> 00:40:24,230
Who cares jekk inti iddividi 2 jekk inti qed jitkellem dwar quadrillions ta 'numri ta' passi?

683
00:40:24,230 --> 00:40:29,710
>> Għalhekk, b'mod ġenerali, xjenzjati tal-kompjuter tendenza li tarmi kollox iżda t-terminu akbar,

684
00:40:29,710 --> 00:40:33,140
u aħna biss tip ta 'jissimplifika-dinja u jgħidu li din algorithm

685
00:40:33,140 --> 00:40:38,130
ħadet passi madwar n kwadru. Dik hija l-running time ta 'algoriżmu.

686
00:40:38,130 --> 00:40:40,760
Allura aħna ser terga 'lura għal din fi ftit mument ma' xi eżempji konkreti,

687
00:40:40,760 --> 00:40:45,940
iżda għal issa, dak it-tip ta 'l-motivazzjoni intuwittivi wara biss jissimplifika dinja tagħna

688
00:40:45,940 --> 00:40:51,170
u jitkellem dwar it-termini l-aktar importanti, aktar milli jkollna fis kollha dawn il-formuli fancy.

689
00:40:51,170 --> 00:40:53,540
Allura li kien tip ta 'għażla, u aħna ltqajna ftit xxurtjati hemmhekk.

690
00:40:53,540 --> 00:40:57,360
Ejja nħarsu lejn tip inserzjoni. Let me imorru quddiem u tibda dan wieħed ukoll.

691
00:40:57,360 --> 00:41:00,330
Issa avviż il-mudell li qed jiġri huwa xi ftit differenti,

692
00:41:00,330 --> 00:41:03,410
u bdejna bil numri bl-addoċċ,

693
00:41:03,410 --> 00:41:06,890
imma jekk aħna effettivament jgħoddu l-għadd ta 'passi fl-agħar każ,

694
00:41:06,890 --> 00:41:11,070
jekk il-lista bdiet kompletament fl-ordni dritt,

695
00:41:11,070 --> 00:41:13,380
aħna biss jieħdu passi n li tirrealizza kemm.

696
00:41:13,380 --> 00:41:18,240
>> Iżda jekk il-lista kienu attwalment lura - per eżempju, f'dan il-każ hawnhekk -

697
00:41:18,240 --> 00:41:23,860
allura avviż aħna fil-fatt ikollhom jagħmlu xogħol ħafna aktar f'dan il-każ.

698
00:41:23,860 --> 00:41:27,080
U għandu tip ta 'jħossu li inti bħal dan wieħed huwa tip ta' xogħol aktar diffiċli

699
00:41:27,080 --> 00:41:30,900
biex tikseb dawk l-elementi iżgħar lejn ix-xellug, u dan għaliex aħna ltqajna unlucky.

700
00:41:30,900 --> 00:41:34,210
Il-lista ġiet magħżula aċċidentalment fir-reverse.

701
00:41:34,210 --> 00:41:38,110
B'kuntrast, ma sort inserzjoni jekk irridu jimitaw dak li għamilna mal-bnedmin tagħna hawnhekk

702
00:41:38,110 --> 00:41:42,670
mill-bidu ma 'kulħadd magħżul u mbagħad tibda, huwa algoritmu pjuttost tajba, id-dritt?

703
00:41:42,670 --> 00:41:45,010
Huwa diġà, fil-fatt, magħżula.

704
00:41:45,010 --> 00:41:48,670
Mela ejja jippruvaw li jitqassar eżattament kemm ħin dawn l-affarijiet qed jieħdu magħna

705
00:41:48,670 --> 00:41:52,360
bl-introduzzjoni biss daqsxejn ta 'lingwaġġ jew notazzjoni li l-fatt ferm aktar sempliċi

706
00:41:52,360 --> 00:41:54,320
mill-tip fanciness ta jissuġġerixxi.

707
00:41:54,320 --> 00:41:59,030
Din ħaġa hawn, dan O kbir fuq l-iskrin, huwa dak xjenzat kompjuter se ġeneralment jużaw

708
00:41:59,030 --> 00:42:03,640
biex jiddeskrivi l-ħin agħar każ tmexxija ta 'algoriżmu.

709
00:42:03,640 --> 00:42:07,360
>> Għal darb'oħra, billi l-agħar każ, huwa totalment dipendenti mill-kuntest.

710
00:42:07,360 --> 00:42:10,890
Dak li jfisser mill-agħar każ totalment tvarja bbażati fuq il-problema li aħna qed jitkellem dwar.

711
00:42:10,890 --> 00:42:14,550
Iżda fil-każ ta 'għażla, x'inhu l-agħar xenarju possibbli?

712
00:42:14,550 --> 00:42:17,860
Kollox huwa lura għax hija biss iħoss bħal dan ifisser ħafna xogħol għalina.

713
00:42:17,860 --> 00:42:21,330
Stajt jotted xi ftit mill-algoritmi li aħna stajt tidher s'issa:

714
00:42:21,330 --> 00:42:24,930
Tfittxija lineari, tfittxija binarja bħall mal-ktieb tat-telefon jew il-biċċiet tal-karti,

715
00:42:24,930 --> 00:42:28,960
sort sort bużżieqa, sort għażla, u l-inserzjoni mbagħad simili rajna mal-bnedmin tagħna,

716
00:42:28,960 --> 00:42:31,770
u mbagħad 1 ohra li l-eventwalment se jissejjaħ jingħaqdu tip.

717
00:42:31,770 --> 00:42:37,710
Għalhekk fl-tfittxija lineari fl-agħar każ, kemm passi ma jieħdu biex isibu l-numru 7

718
00:42:37,710 --> 00:42:40,690
jekk ikun hemm bibien n bħall Sean ffaċċjati? >> [Student] N.

719
00:42:40,690 --> 00:42:44,180
N. Allura aħna qed tmur biex jiktbu big O ta 'n.

720
00:42:44,180 --> 00:42:47,010
Jien biss ser timla xi vojt. Dan huwa biss grilja ta 'matriċi.

721
00:42:47,010 --> 00:42:52,990
Iżda fil-każ aħjar ma 'tfittxija lineari, 7 seta' kien fil-bidu nett tal-lista,

722
00:42:52,990 --> 00:42:55,520
u Sean jista bdew ifittxu fil-bidu tal-lista.

723
00:42:55,520 --> 00:42:58,940
Mela jekk inti qed tuża tfittxija lineari u biss verifika xellug għal-lemin jew forsi lemin għax-xellug -

724
00:42:58,940 --> 00:43:02,650
dawn qed ekwivalenti - fil-każ aqwa kif ħafna passi tista 'tfittxija lineari,

725
00:43:02,650 --> 00:43:05,550
bħal algoritmu Sean, tieħu? Just 1 pass.

726
00:43:05,550 --> 00:43:09,450
>> Allura jien se ngħid li l-notazzjoni omega.

727
00:43:09,450 --> 00:43:11,570
Dan huwa biss omega kapital.

728
00:43:11,570 --> 00:43:15,000
Omega huwa biss il-mod ta 'tgħid sexy każ l-aħjar running time.

729
00:43:15,000 --> 00:43:18,900
Allura fil-każ aħjar il-running time huwa pass wieħed jew numru kostanti ta 'passi -

730
00:43:18,900 --> 00:43:24,270
1 f'dan il-każ - imma fl-agħar każ, big O, huwa attwalment passi n.

731
00:43:24,270 --> 00:43:28,110
U dan wieħed hawn, theta, aħna qed attwalment mhux se tħares lejn id-dritt issa.

732
00:43:28,110 --> 00:43:30,090
Mhuwiex rilevanti għal dan l-eżempju partikolari.

733
00:43:30,090 --> 00:43:31,990
Imma issa ejja ipprova tiftix binarju.

734
00:43:31,990 --> 00:43:35,990
Fl-agħar każ ma 'tfittxija binarju, kemm passi huwa se jieħu biex issib in-numru 7

735
00:43:35,990 --> 00:43:38,340
jew kwalunkwe aħna qed tfittex? >> [Student] Log n.

736
00:43:38,340 --> 00:43:40,980
Still ser tieħu n log għaliex eżatt bħal Alex ltqajna unlucky

737
00:43:40,980 --> 00:43:44,030
meta aħna verament maħduma permezz tal-problema metodiku

738
00:43:44,030 --> 00:43:48,220
u hi ma sabx il-numru 7 sakemm il-bieb ħafna aħħar hi ħares lejn,

739
00:43:48,220 --> 00:43:51,720
anki jekk, fil-ġustizzja, qabbdet biex armih bibien ċerti tul it-triq,

740
00:43:51,720 --> 00:43:56,920
tfittxija binarju fl-agħar każ għandu ħin tmexxija ta 'log n.

741
00:43:56,920 --> 00:43:59,230
U għal darb'oħra, li titkellem għal dan diviżjoni u conquering.

742
00:43:59,230 --> 00:44:01,140
Imma xi ngħidu dwar fil-każ aħjar?

743
00:44:01,140 --> 00:44:04,790
U Alex attwalment esperjenza f'dak il-każ l-aħjar dritt meta hi daħlet up fuq il-palk.

744
00:44:04,790 --> 00:44:07,290
Kemm passi ma din tieħu fit-tfittxija binarja? >> [Student] 1.

745
00:44:07,290 --> 00:44:09,380
1, sempliċiment għaliex hija ltqajna xxurtjati.

746
00:44:09,380 --> 00:44:12,520
Iżda li l-multa minħabba omega jirreferi għal xenarji każ aħjar,

747
00:44:12,520 --> 00:44:15,770
inputs aħjar każ, anki jekk huwa jinsab biss każwali Xorti dumb.

748
00:44:15,770 --> 00:44:18,900
>> Issa, dan ukoll aħna qed tmur biex biss tip ta 'vojt leave għal issa.

749
00:44:18,900 --> 00:44:21,010
Sort bużżieqa Kif dwar issa?

750
00:44:21,010 --> 00:44:24,290
Fl-agħar każ ma sort bużżieqa, kulħadd huwa fl-ordni invers,

751
00:44:24,290 --> 00:44:26,380
hekk għandna nagħmlu ħafna ta 'tbaqbieq.

752
00:44:26,380 --> 00:44:30,190
Imma kif ħafna passi huwa li se tieħu fl-agħar każ? >> [Student] N kwadru.

753
00:44:30,190 --> 00:44:32,550
Dan kien il-n kwadrat, għaliex jekk inti taħseb dwarha,

754
00:44:32,550 --> 00:44:36,410
jekk il-lista hija kompletament lura - 8 huwa aktar hawn, 1 huwa minn hawn -

755
00:44:36,410 --> 00:44:40,530
bħala ħaġa jibdew bużżieqa, in-numru 8 huwa ser jiċċaqalqu b'dan il-mod, dan il-mod,

756
00:44:40,530 --> 00:44:44,540
B'dan il-mod, dan il-mod, iżda fejn huwa n-numru 7 fl-agħar każ?

757
00:44:44,540 --> 00:44:47,720
Hawn hi għadha hemmhekk. Allura aħna għandna biex jagħmlu mill-ġdid u għal darb'oħra.

758
00:44:47,720 --> 00:44:53,190
U li fejn irridu jiksbu passi n, allura n - 1 passi, allura n - 2 passi.

759
00:44:53,190 --> 00:44:55,960
U jekk inti tieħu kelma tiegħi għaliha - li jekk inti-tip ta 'immoltiplika dan jitwettaq,

760
00:44:55,960 --> 00:45:00,110
huwa bejn wieħed u ieħor kwadru n fl-aħħar ma 'xi termini oħra li aħna ser biss jinjora għal issa -

761
00:45:00,110 --> 00:45:06,890
imbagħad fil-tip bużżieqa agħar każ huwa n kwadrat, jagħtu jew jieħu.

762
00:45:06,890 --> 00:45:09,490
Imma x'inhuma l-aħjar każ ma sort bużżieqa?

763
00:45:09,490 --> 00:45:13,050
X'inhi l-aħjar xenarju? Kollha tal-numri huma magħżula diġà.

764
00:45:13,050 --> 00:45:15,920
U dak kien il-heuristic I użati, il-trick I użati,

765
00:45:15,920 --> 00:45:20,110
li tirrealizza li kelli jsir l-ebda xogħol u tista 'għalhekk twaqqaf kmieni?

766
00:45:20,110 --> 00:45:23,590
[Student] Iċċekkja darba. >> Iċċekkja darba. Imma dak li kien I tagħmel tul it-triq?

767
00:45:23,590 --> 00:45:26,130
I kien iżżomm rekord ta 'kemm tpartit I magħmula.

768
00:45:26,130 --> 00:45:30,650
U jien realizzati jekk jien ma jingħaddux ebda swaps fuq swaba tiegħi, imbagħad I ghamilt ebda xogħol.

769
00:45:30,650 --> 00:45:34,300
I ċertament ma għandhiex tipprova tagħmel ebda xogħol ġdid, hekk nista 'biss tieqaf.

770
00:45:34,300 --> 00:45:37,830
>> Allura fil-każ aħjar ta 'tip bużżieqa meta l-lista hija diġà magħżula,

771
00:45:37,830 --> 00:45:41,530
dak would you say in-notazzjoni omega huwa, l-aħjar każ running time?

772
00:45:41,530 --> 00:45:48,040
Huwa biss n. Għandna biex jagħmlu xi xogħol, iżda aħna biss għandek tagħmel jiswew 1 stroll ta 'ħidma.

773
00:45:48,040 --> 00:45:50,490
U hawnhekk ukoll jien ser tħalli din vojt parti.

774
00:45:50,490 --> 00:45:52,430
U issa sort għażla.

775
00:45:52,430 --> 00:45:56,010
Sort Għażla kien me tnittif il-persuna iżgħar u għal darb'oħra.

776
00:45:56,010 --> 00:45:58,380
U dak ma ngħidu l-running time ta 'li kien?

777
00:45:58,380 --> 00:46:00,590
Dan kien n kwadrat fl-agħar każ.

778
00:46:00,590 --> 00:46:05,220
U sfortunatament, fl-aħjar każ huwa wkoll n kwadrat

779
00:46:05,220 --> 00:46:08,840
minħabba I ma jkollhomx il-tip ta 'dawl omniscient tad-dinja kollha;

780
00:46:08,840 --> 00:46:13,140
I biss jafu fuq iterazzjoni sħiħ li stajt tabilħaqq instabu l-persuna iżgħar.

781
00:46:13,140 --> 00:46:15,860
Allura l-għażla it-tip tip ta 'sucks f'dan is-sens,

782
00:46:15,860 --> 00:46:17,920
iżda l-rasu huwa huwa tip ta 'intuwittivi.

783
00:46:17,920 --> 00:46:21,470
Huwa pjuttost faċli għall-kodiċi up għaliex kull ma għandek tagħmel hu li tikteb ftit nested għal-linji,

784
00:46:21,470 --> 00:46:24,620
tipikament, li tmur permezz tfittex l-element iżgħar

785
00:46:24,620 --> 00:46:27,840
u mbagħad ipoġġu l-element iżgħar fejn jappartjeni fl-aħħar tal-lista.

786
00:46:27,840 --> 00:46:29,900
Allura hawnhekk ukoll hemm għaddej li jkun kompromess.

787
00:46:29,900 --> 00:46:34,440
L-ammont ta 'ħin li tieħu inti biex jaħsbu u li fil-fatt jiżviluppaw xi ħaġa bil-kitba kodiċi

788
00:46:34,440 --> 00:46:39,460
tista 'faċilment jieħdu aktar żmien jekk inti tixtieq a prestazzjoni aħjar algoritmu u aktar malajr.

789
00:46:39,460 --> 00:46:41,780
>> Imma jekk int verament biss tip ta 'ħaġa Kodiċi up malajr u maħmuġin

790
00:46:41,780 --> 00:46:45,000
u biss tip ta 'tieħu l-idea stupidest possibbli inti tista' taħseb,

791
00:46:45,000 --> 00:46:47,580
li jista 'jieħu inti ftit minuti għall-kodiċi, iżda ma' settijiet ta 'data kbar

792
00:46:47,580 --> 00:46:49,580
algoritmu tiegħek jista 'jieħu sigħat jiddekorri.

793
00:46:49,580 --> 00:46:51,690
U anki jien fl-iskola gradwati se kultant tagħmel dawn il-kompromessi.

794
00:46:51,690 --> 00:46:55,660
Ikun 03:00, I kien qed jipprova janalizza xi sett ta 'data kbar ħafna

795
00:46:55,660 --> 00:46:59,650
relatat mal-riċerka tas-sigurtà I kienet tagħmel, u kien la jonfqu 5 minuti

796
00:46:59,650 --> 00:47:03,210
tweaking programm tiegħi biex tanalizza l-informazzjoni u tmur torqod

797
00:47:03,210 --> 00:47:08,420
jew iqattgħu 8 sigħat jkollna dan biss id-dritt hekk hija u tieqaf istantanjament u ma tmur torqod.

798
00:47:08,420 --> 00:47:10,530
U għalhekk hemm wisq huwa tip ta 'deċiżjoni konxja.

799
00:47:10,530 --> 00:47:12,740
Inqas iżvilupp ħin, aktar irqad.

800
00:47:12,740 --> 00:47:14,780
Retrospettivament, I probabbilment ma għandu jinkoraġġixxi li

801
00:47:14,780 --> 00:47:19,120
meta l-għan hawnhekk huwa li jottimizzaw kwalità tal-kodiċi,

802
00:47:19,120 --> 00:47:21,280
iżda li wisq fid-dinja reali hija ħafna raġonevoli kompromess.

803
00:47:21,280 --> 00:47:25,130
Inqas ħin, il-prestazzjoni inqas jew viċi versa.

804
00:47:25,130 --> 00:47:28,110
Allura hawnhekk aħna finalment jiksbu opportunità biex jitkellmu dwar theta.

805
00:47:28,110 --> 00:47:32,830
Theta notazzjoni hija xi ħaġa xjenzati tal-kompjuter tista 'ġġib up fil-konverżazzjoni

806
00:47:32,830 --> 00:47:36,160
meta big O u omega jiġri li jkun l-istess.

807
00:47:36,160 --> 00:47:40,160
You say theta biex verament jibgħat il-messaġġ li dan huwa tip ta 'stretta marbuta.

808
00:47:40,160 --> 00:47:43,340
Ma jimpurtax jekk l-xenarju hija tajba jew ħażina, huwa n kwadru.

809
00:47:43,340 --> 00:47:46,510
Allura huwa biss mhux rilevanti dawn l-istejjer hawn.

810
00:47:46,510 --> 00:47:48,560
Sort Inserzjoni hija l-aħħar wieħed ħarisna lejn,

811
00:47:48,560 --> 00:47:50,830
fejn I kien biss ddaħħal kulħadd fil-post it-tajjeb.

812
00:47:50,830 --> 00:47:54,930
Fil-każ aħjar dak li kien il-ħin tmexxija ta 'tip inserzjoni kif aħna raw dan hawn?

813
00:47:54,930 --> 00:47:57,250
[Student] L-aħjar każ? >> L-aħjar każ.

814
00:47:57,250 --> 00:48:00,100
>> Kien n għax magħżula kulħadd fil-każ aħjar,

815
00:48:00,100 --> 00:48:02,580
u Sammy u l-ebda wieħed inkella verament kellha timxi għal kollox.

816
00:48:02,580 --> 00:48:04,610
Huma kienu diġà fis-seħħ id-dritt tagħhom.

817
00:48:04,610 --> 00:48:08,570
Allura inserzjoni sort fil-każ aħjar huwa, f'dan il-każ, n.

818
00:48:08,570 --> 00:48:12,770
Iżda fl-agħar każ huwa tip ta 'n kwadru. Għaliex?

819
00:48:12,770 --> 00:48:16,230
Jekk il-lista tiegħi ta 'bniedem fl-ordni invers,

820
00:48:16,230 --> 00:48:21,260
I l-ewwel tibda bil-numru 8 u I daħħal lilu jew lilha fil-pożizzjoni dritt, li huwa dritt hawn.

821
00:48:21,260 --> 00:48:25,270
I tip ta 'moviment għall-ġenb. Dawn guys huma mhux magħżula, hu jew hi huwa magħżul.

822
00:48:25,270 --> 00:48:28,970
Imma issa I jiġri li ssib li jmiss? >> [Student] 7.

823
00:48:28,970 --> 00:48:31,250
7 fl-agħar każ, għaliex dan huwa fl-ordni invers.

824
00:48:31,250 --> 00:48:34,920
>> Allura hawnhekk huwa 7. Fejn ma 7 jappartjenu? Żgur lura lili.

825
00:48:34,920 --> 00:48:39,460
Imma issa 7 attwalment tappartjeni mhux immedjatament wara lili iżda wara numru 8,

826
00:48:39,460 --> 00:48:41,880
so I għandhom jgħidu, "Skuża me, numru 8, tista 'jekk jogħġbok timxi b'dan il-mod

827
00:48:41,880 --> 00:48:44,640
"Biex tagħmel spazju għal 7?" Issa I jiltaqgħu 6.

828
00:48:44,640 --> 00:48:48,530
"Oh, skuża me, numru 8 u n-numru 7, inti tista 'timxi biex tagħmel spazju għal 6?"

829
00:48:48,530 --> 00:48:52,360
Allura fi kliem ieħor, ma sort inserzjoni, anki jekk jien ma nagħmilx moviment ħafna,

830
00:48:52,360 --> 00:48:56,330
il-poplu wara me qed jagħmlu xogħol ħafna aktar, u li ltqajna biex ispiża ħin xi ħadd.

831
00:48:56,330 --> 00:48:58,000
Huwa ser jiswew l-ħin tal-kompjuter.

832
00:48:58,000 --> 00:49:01,450
Allura fil-każ ta 'tip inserzjoni aħna xorta jsofru.

833
00:49:01,450 --> 00:49:06,260
Jekk inti tibda żżid l-għadd totali ta 'passi, aħna jispiċċaw laqtu bejn wieħed u ieħor kwadru n

834
00:49:06,260 --> 00:49:11,160
minħabba li dawn guys bżonn tagħmel spazju għall-bniedem li jiddaħħlu lura fis dik il-lista.

835
00:49:11,160 --> 00:49:15,960
U hekk f'dan il-każ theta huwa biss mhux applikabbli għall-istorja partikolari fil-idejn.

836
00:49:15,960 --> 00:49:21,100
Li kollox sbieħ u tajbin. Aħna dawn il-modi differenti ta '3 jitkellem dwar il-ħin qed taħdem.

837
00:49:21,100 --> 00:49:26,370
Imma dak ma dan fil-fatt tfisser f'termini reali jekk aħna fil-fatt jipprovaw kodiċi up algoritmu?

838
00:49:26,370 --> 00:49:31,620
>> Let me tipproponi li hemm algoritmu anki aħjar hemmhekk

839
00:49:31,620 --> 00:49:33,740
li hi stess għandha xi kompromessi.

840
00:49:33,740 --> 00:49:36,890
Aħna ser sejħa hija jingħaqdu sort, u huwa tip ta 'dan algoritmu maġika

841
00:49:36,890 --> 00:49:42,840
li biss taħdem aktar malajr b'xi, u huwa daqshekk faċli biex jesprimu, għall-inqas fil pseudocode.

842
00:49:42,840 --> 00:49:46,900
L-implimentazzjoni ta 'dan it-tip inkorporazzjoni algoritmu se tkun kif ġej.

843
00:49:46,900 --> 00:49:50,860
Meta inti qed tingħata n elementi - numri n, n-nies, ikun x'ikun - 1 hemm l-verifika sanità.

844
00:49:50,860 --> 00:49:56,340
Jekk n hija inqas minn 2, jingħaqdu tip biss waqfiet. Hija prospetti, biex ngħidu hekk.

845
00:49:56,340 --> 00:50:00,830
Għaliex kieku inti tieqaf jekk n hija inqas minn 2? >> [Rispons istudent inaudible]

846
00:50:00,830 --> 00:50:04,480
Dritt. U għal darb'oħra, n mhuwiex in-numru fil-lista, n huwa d-daqs tal-lista.

847
00:50:04,480 --> 00:50:07,660
Jekk n hija inqas minn 2, li tfisser lista tiegħek huwa jew 1,

848
00:50:07,660 --> 00:50:09,640
fejn int ovvjament magħżula jekk huwa numru 1,

849
00:50:09,640 --> 00:50:11,710
jew 0, f'liema każ hemm xejn biex issolvi,

850
00:50:11,710 --> 00:50:13,570
għalhekk għandna bżonn dan it-tip ta 'każ bażi.

851
00:50:13,570 --> 00:50:20,350
Jekk il-lista hija tant qasir li hemm biss xejn li tagħmel, litteralment ma tagħmel xejn. Ritorn.

852
00:50:20,350 --> 00:50:25,090
Inkella sort-nofs tax-xellug ta 'l-elementi, allura sort l-nofs tal-lemin ta' l-elementi,

853
00:50:25,090 --> 00:50:27,410
imbagħad jingħaqdu l-nofsijiet 2 magħżula.

854
00:50:27,410 --> 00:50:32,130
>> Dan it-tip ta tidher qisha iqarrqu ftit fejn jien inti titlob kif sort elementi

855
00:50:32,130 --> 00:50:34,900
u int javżak me, "Sort-nofs tax-xellug, isolvi l-nofs tal-lemin."

856
00:50:34,900 --> 00:50:37,240
Jien simili, "Kull dritt. Kif inti sort l-nofs tax-xellug?"

857
00:50:37,240 --> 00:50:40,670
"Sort l-nofs tax-xellug tan-nofs tax-xellug, isolvi l-nofs tal-lemin tan-nofs tax-xellug, u mbagħad isir."

858
00:50:40,670 --> 00:50:44,060
Inti tip ta 'ċiklikament li jiddefinixxu dak li tfisser li sort,

859
00:50:44,060 --> 00:50:46,790
iżda jirriżulta li l-fatt brillanti f'dan il-każ.

860
00:50:46,790 --> 00:50:50,230
Mhuwiex verament dan iċ-ċiklu vizzjuż li qatt ma tispiċċa

861
00:50:50,230 --> 00:50:52,550
minħabba li ma jintemmx meta? >> [Student] Meta inti tilħaq 1 ħaġa.

862
00:50:52,550 --> 00:50:54,220
Meta inti tilħaq 1 ħaġa.

863
00:50:54,220 --> 00:50:57,850
Għalhekk anki jekk inti tista 'tibda ma' 8 persuni u jien ngħid, "sort l-nofs tax-xellug ta 'dawn in-nies,

864
00:50:57,850 --> 00:51:00,480
dawn in-nies 4, "imbagħad I say," Kif inti sort l-nofs tax-xellug? "

865
00:51:00,480 --> 00:51:03,450
"Well, sort-poplu 2 hawn." U allura int simili, "Kull dritt, multa."

866
00:51:03,450 --> 00:51:05,520
"Kif inti sort l-nofs tax-xellug ta 'dawk in-nies?"

867
00:51:05,520 --> 00:51:09,040
"Just sort din il-persuna 1 hawn." X'hemm-rivelazzjoni brillanti issa?

868
00:51:09,040 --> 00:51:13,050
Għandi biex issolvi persuna 1. Magħmul. I ma jkollhom jagħmlu xi xogħol.

869
00:51:13,050 --> 00:51:16,580
Imma issa għandi biex issolvi din il-persuna, iżda dawn qed persuna waħda, xejn li jagħmlu.

870
00:51:16,580 --> 00:51:21,490
>> Allura l-magic apparentement huwa f'dan tielet pass: jingħaqdu l-nofsijiet magħżula.

871
00:51:21,490 --> 00:51:25,770
Sort Allura jingħaqdu jieħu din ħarsa brillanti li jekk inti break problema kbira isfel

872
00:51:25,770 --> 00:51:28,650
fis-2 iżgħar, identiku daqs problemi

873
00:51:28,650 --> 00:51:32,710
u mbagħad biss tip ta 'kolla-soluzzjonijiet iżgħar flimkien fl-aħħar,

874
00:51:32,710 --> 00:51:34,720
Nipproponi li nistgħu nagħmlu ħafna, ħafna aħjar [ħoss tapping]

875
00:51:34,720 --> 00:51:38,050
minn kwalunkwe ta 'tip ta' għażla jew tip inserzjoni.

876
00:51:38,050 --> 00:51:40,690
Stajt attwalment ġew injorat li għal nofs siegħa, imma jien verament ma nafx x'inhu għaddej

877
00:51:40,690 --> 00:51:45,040
barra illum. [Whirring ħoss] [Rires]

878
00:51:45,040 --> 00:51:49,660
Mela ejja ara jekk nistgħu naraw dan bi ftit għajnuna mill Bowden tagħna ħabib Rob.

879
00:51:49,660 --> 00:51:52,810
Hemm 2 passi kbar fil-proċess ta 'tip jingħaqdu.

880
00:51:52,810 --> 00:51:56,400
L-ewwel, kontinwament taqsam il-lista tal-cups fis nofsijiet

881
00:51:56,400 --> 00:51:59,610
sakemm għandna mazz ta 'listi mal biss 1 tazza fihom.

882
00:51:59,610 --> 00:52:02,150
Tinkwetax jekk lista fiha numru fard

883
00:52:02,150 --> 00:52:04,830
u inti ma tistax tagħmel qatgħa perfettament nadif bejniethom.

884
00:52:04,830 --> 00:52:08,740
Just pick arbitrarjament li lista biex tinkludi l-tazza żejda pulzieri

885
00:52:08,740 --> 00:52:11,320
Mela ejja maqsuma dawn il-listi.

886
00:52:12,420 --> 00:52:14,570
Issa għandna 2 listi.

887
00:52:18,930 --> 00:52:20,930
Issa għandna 4 listi.

888
00:52:25,730 --> 00:52:28,740
Issa għandna 8 listi ma 'tazza waħda f'kull lista.

889
00:52:28,740 --> 00:52:31,520
Allura dak li għall-pass 1.

890
00:52:31,520 --> 00:52:37,280
Għal pass 2 aħna ripetutament jingħaqdu pari ta 'listi li jużaw l-algoritmu jingħaqdu aħna tgħallimna qabel.

891
00:52:37,280 --> 00:52:44,320
Twaħħid 108 u 15 aħna tispiċċa bil-lista 15, 108.

892
00:52:45,240 --> 00:52:51,330
Twaħħid 50 u 4 aħna jispiċċaw ma '4, 50.

893
00:52:51,330 --> 00:52:56,950
Twaħħid 8 u 42 aħna jispiċċaw bi 8, 42.

894
00:52:57,790 --> 00:53:04,360
U qed jingħaqdu 23 u 16 aħna jispiċċaw ma 16, 23.

895
00:53:04,360 --> 00:53:08,030
Issa listi kollha tagħna huma ta 'daqs 2.

896
00:53:08,030 --> 00:53:10,980
Avviż li kull wieħed mill-listi 4 huwa magħżul,

897
00:53:10,980 --> 00:53:14,230
hekk aħna tista 'tibda amalgamazzjoni pari ta' listi ġdid.

898
00:53:14,230 --> 00:53:22,150
Twaħħid 15 u 108 u 4 u 50 aħna l-ewwel jieħdu l-4, allura l-15,

899
00:53:22,150 --> 00:53:26,250
allura l-50, allura l-108.

900
00:53:26,250 --> 00:53:33,020
Twaħħid 8, 42 u 16, 23 aħna l-ewwel jieħu l-8, allura l-16,

901
00:53:33,020 --> 00:53:37,170
allura l-23, allura l-42.

902
00:53:37,170 --> 00:53:42,490
Allura issa għandna biss 2 listi ta 'daqs 4, li kull wieħed minnhom huwa magħżul.

903
00:53:42,490 --> 00:53:45,940
Allura issa aħna jingħaqdu dawn il-listi 2.

904
00:53:45,940 --> 00:53:54,230
L-ewwel nieħdu l-4, allura aħna jieħdu l-8, allura aħna jieħdu l-15

905
00:53:54,230 --> 00:54:05,280
u 16 u 23 u 42 u 50 u 108.

906
00:54:05,280 --> 00:54:09,020
U aħna qed isir. Issa għandna lista magħżula.

907
00:54:09,020 --> 00:54:13,740
>> Rob kien tip ta 'tieħu vantaġġ ta' xi ħaġa li aħna għadhom m'għamlux.

908
00:54:13,740 --> 00:54:16,540
Ġie ssuġġerit, imma aħna ma attwalment jagħmlu dan.

909
00:54:16,540 --> 00:54:19,230
Huwa kien isir xi ħaġa fiżikament mal-cups li tissuġġerixxi

910
00:54:19,230 --> 00:54:23,680
kien infiq xi riżors minbarra żmien. >> [Student]. Ispazju >> Kien ispazju.

911
00:54:23,680 --> 00:54:27,360
Il-fatt li huwa kien dan it-tip ta 'bi-livell tabella fejn kellu spazju up here

912
00:54:27,360 --> 00:54:31,960
u l-ispazju stabbiliti hawn kien attwalment dan jimplika li hu użu spazjali darbtejn daqs

913
00:54:31,960 --> 00:54:36,390
bħala kwalunkwe ta 'algoritmi tagħna s'issa - tip inserzjoni, sort bżieżaq, jew l-għażla sort -

914
00:54:36,390 --> 00:54:40,780
iżda kien jitqawwa dan l-ispazju addizzjonali għal tip ta 'affarijiet jimxu quddiem u lura

915
00:54:40,780 --> 00:54:42,600
filwaqt li jżommu l-affarijiet fl-ordni.

916
00:54:42,600 --> 00:54:47,540
U anki jekk iħoss bħal sirna għal lista magħżula, li qisni hija ħadet ftit żmien.

917
00:54:47,540 --> 00:54:51,060
Fir-realtà, dak li Rob kien isir kien eżattament dan algoritmu.

918
00:54:51,060 --> 00:54:56,780
Huwa l-ewwel ħa l-problema ta 'n-daqs, maqsuma hija fis-nofs tax-xellug u nofs id-dritt.

919
00:54:56,780 --> 00:54:59,380
Li meta huwa mċaqlaq-cups. Imbagħad huwa ripetut il-proċess.

920
00:54:59,380 --> 00:55:03,390
Huwa maqsum 4 fi 2 settijiet ta '2 hawn fuq u hawn fuq.

921
00:55:03,390 --> 00:55:08,520
Imbagħad huwa ripetut il-proċess u maqsum 2 fis-2 settijiet ta '1 għal kull waħda minn dawn tazzi varji.

922
00:55:08,520 --> 00:55:11,000
U li fejn l-opportunità brillanti tqum.

923
00:55:11,000 --> 00:55:15,840
F'dak il-punt fl-istorja, Rob kellhom 8 listi ta 'daqs 1,

924
00:55:15,840 --> 00:55:18,860
li kollha kienu magħżula diġà.

925
00:55:18,860 --> 00:55:20,630
>> Mela allura dak ma hu tipproċedi biex tagħmel?

926
00:55:20,630 --> 00:55:25,260
Pairwise huwa ħa din il-lista magħżula u din il-lista magħżula u magħquda minnhom.

927
00:55:25,260 --> 00:55:28,200
Imbagħad huwa ħa dan wieħed u magħquda minnhom, allura dan wieħed u magħquda minnhom,

928
00:55:28,200 --> 00:55:30,670
allura dan wieħed u magħquda minnhom.

929
00:55:30,670 --> 00:55:32,390
U allura dak ma hu tagħmel jmiss?

930
00:55:32,390 --> 00:55:36,580
Huwa mbagħad jerġa 'amalgamata l-listi akbar u mbagħad jerġa' amalgamata l-listi akbar.

931
00:55:36,580 --> 00:55:41,170
U jekk taħseb dwar dan biss intuwittivament għal issa, dak li kien hu verament tagħmel?

932
00:55:41,170 --> 00:55:45,450
Huwa kien diviż il-problema fil nofs, fil nofs, fil nofs, nofs

933
00:55:45,450 --> 00:55:47,600
sabiex jiksbu dawn il-listi żgħar super.

934
00:55:47,600 --> 00:55:51,290
Imbagħad kien it-tip ta 'kif tgħaqqad, double doppja, double, double.

935
00:55:51,290 --> 00:55:54,120
Hekk kien isir darbtejn bħala xogħol kemm aħna stajt tidher s'issa

936
00:55:54,120 --> 00:55:56,930
ma 'xi ħaġa li tinvolvi firda u conquer, iżda l-ebda big deal.

937
00:55:56,930 --> 00:55:59,630
Xogħol doppju mhuwiex tali big deal. Huwa biss fattur kostanti.

938
00:55:59,630 --> 00:56:03,920
U ħafna bħal espressjoni aritmetika tagħna qabel, jien biss se jaqsmu l-fatturi kostanti

939
00:56:03,920 --> 00:56:10,170
bħal ħinijiet 2. Who cares? Jekk huwa 2 biljuni darbiet 2, li għadu ħafna ta 'passi.

940
00:56:10,170 --> 00:56:13,160
Allura dan il-pass li qed jingħaqdu jidher li jkun l-għarfien ċavetta.

941
00:56:13,160 --> 00:56:17,000
Ejja jimxu permezz ta 'dan biss numerikament qabel - Oh, dak ma jitkompla għadu.

942
00:56:17,000 --> 00:56:22,890
Ejja jimxu permezz ta 'dan numerikament biss biex effettivament jaraw kif dan jilgħab barra.

943
00:56:22,890 --> 00:56:25,940
Dan huwa aktar biss animazzjoni raġel fqir ftit ta.

944
00:56:25,940 --> 00:56:27,750
Ejja jipproponi dan.

945
00:56:27,750 --> 00:56:31,480
Il-ħin tmexxija ta 'tip jingħaqdu - aħna biss bżonn ta' mod ta 'jitkellem dwar dan.

946
00:56:31,480 --> 00:56:34,380
Dan mhux matematika, din hija biss it-tip ta 'mod konċiż li jesprimu nfusna.

947
00:56:34,380 --> 00:56:39,080
Allura T tirrappreżenta ħin u n jirrappreżenta dak? >> [Student] Id-daqs tal--

948
00:56:39,080 --> 00:56:41,400
>> [Malan] Id-daqs tal-problema, l-għadd ta 'nies.

949
00:56:41,400 --> 00:56:45,470
Allura jien fejn sostniet li l-ħin taħdem biex issolvi n-nies n se jkun ta '0 ammont ta' ħin

950
00:56:45,470 --> 00:56:50,290
jekk n hija inqas minn 2, għaliex jekk għandek 1 tazza jew l-ebda tazzi, għandek xejn biex issolvi.

951
00:56:50,290 --> 00:56:55,160
Iżda aktar ġenerali, jien ser nipproponi li l-ħin taħdem biex issolvi l-elementi n

952
00:56:55,160 --> 00:56:59,350
se tkun il-ħin li tieħu biex issolvi l-nofs tax-xellug kif ukoll il-nofs tal-lemin

953
00:56:59,350 --> 00:57:03,110
plus - x'hemm dan addizzjonali + n? >> [Student] sort Merge.

954
00:57:03,110 --> 00:57:07,260
[Malan] Huwa fatt li qed jingħaqdu, għaliex jekk ikollok n / 2 elementi hawn

955
00:57:07,260 --> 00:57:11,500
u inti għandek n / 2 elementi hawn, kemm ħin ma jieħdu biex jingħaqdu?

956
00:57:11,500 --> 00:57:15,050
Eżatt bħal Rob, inti għandek ġewwieni dan wieħed hawn fuq, forsi ġewwieni hawn fuq,

957
00:57:15,050 --> 00:57:17,120
ġewwieni hawn fuq, ġewwieni hawn fuq, ġewwieni hawn fuq.

958
00:57:17,120 --> 00:57:19,400
Inti għandek tmissx kull wieħed mill-cups darba.

959
00:57:19,400 --> 00:57:22,030
U jekk hemm 4 tazzi plus 4 tazzi, li 8 tazzi

960
00:57:22,030 --> 00:57:25,200
jew b'mod aktar ġenerali, 8 tazzi n.

961
00:57:25,200 --> 00:57:28,470
Allura l-pass li qed jingħaqdu nistgħu jesprimu bħala n-

962
00:57:28,470 --> 00:57:31,330
u li litteralment jinvolvi n-numru ta 'drabi Rob fiżikament jintmess

963
00:57:31,330 --> 00:57:33,410
wieħed minn dawn tazzi Styrofoam.

964
00:57:33,410 --> 00:57:35,850
Mela ejja issa do eżempju arbitrarja.

965
00:57:35,850 --> 00:57:41,850
Jekk hemm 16 tazzi, x'inhu l-ħin tmexxija ta 'l-għażla, bl-użu algoritmu Rob s, 16 tazzi?

966
00:57:41,850 --> 00:57:44,710
Huwa 2 darbiet l-ammont ta 'ħin li tieħu biex issolvi 8 tazzi

967
00:57:44,710 --> 00:57:46,920
għaliex għandna 8 tazzi hawn, 8 tazzi hawn.

968
00:57:46,920 --> 00:57:51,520
I do not know kemm żmien li tieħu, hekk aħna qed jiġġeneralizzaw bħala T għall-mument.

969
00:57:51,520 --> 00:57:53,320
Min jaf għalxiex?

970
00:57:53,320 --> 00:57:58,990
Imma issa I tista 'tip ta' recursively jew ripetutament jistaqsu l-istess kwistjoni.

971
00:57:58,990 --> 00:58:01,920
Kif ħafna ħin ma jieħdu biex issolvi 8 tazzi?

972
00:58:01,920 --> 00:58:07,030
8 tazzi jien ser ngħid tieħu l-ammont ta 'ħin li tieħu biex issolvi 4 tazzi plus 4 tazzi,

973
00:58:07,030 --> 00:58:08,880
imbagħad jingħaqdu flimkien.

974
00:58:08,880 --> 00:58:13,080
Fine. Aħna jkollna fis-ċiklu diġà. Kemm idum ma jieħdu biex issolvi 4 tazzi?

975
00:58:13,080 --> 00:58:19,150
Il-ħin li tieħu biex issolvi 4 tazzi huwa 2 tazzi flimkien ma '2 tazzi issortjar flimkien mal-proċess li qed jingħaqdu.

976
00:58:19,150 --> 00:58:21,440
Fine. Kemm idum ma jieħdu biex sort 2 tazzi?

977
00:58:21,440 --> 00:58:26,290
2 tazzi huwa l-ammont ta 'ħin li tieħu biex issolvi 1 tazza flimkien mal-ħin li tieħu biex issolvi ieħor tazza

978
00:58:26,290 --> 00:58:29,040
flimkien mal-ammont ta 'ħin li tieħu biex jingħaqdu, li huwa biss 2.

979
00:58:29,040 --> 00:58:33,340
>> Fine. Aħħar mistoqsija. Kemm idum ma jieħdu biex sort 1 tazza?

980
00:58:33,340 --> 00:58:37,260
Hawn hu l-każ ta 'bażi ​​li aħna mbassra aħna'd hit qabel.

981
00:58:37,260 --> 00:58:42,250
Il-fatt li dan jieħu ebda xogħol tkun xi tkun biex issolvi l-iżgħar tal-problemi

982
00:58:42,250 --> 00:58:44,120
ifisser li issa, it-tip ta 'stil iskola grad,

983
00:58:44,120 --> 00:58:46,460
nistgħu biss tmur tibda fejn jitwaħħal dawn in-numri lura pulzieri

984
00:58:46,460 --> 00:58:50,630
Aħna issa jkunu jafu liema T ta '1 huwa, so I tista' plagg fil 0 għall T ta '1.

985
00:58:50,630 --> 00:58:54,420
Li se tagħti me-risposta għal T-2, li jiena mbagħad tista 'plagg fil sa ogħla.

986
00:58:54,420 --> 00:58:56,930
Li se tagħti me T ta '4, li nista' plagg fil sa ogħla.

987
00:58:56,930 --> 00:58:58,920
Li se tagħti me T tat-8, li nista 'plagg fil sa ogħla.

988
00:58:58,920 --> 00:59:04,330
U jekk I attwalment do li matematika minn fejn jitwaħħal fil dawn it-tweġibiet,

989
00:59:04,330 --> 00:59:08,590
I imbagħad nikseb T ta '16 huwa 64.

990
00:59:08,590 --> 00:59:12,090
U dak jirrappreżentaw 64 ma?

991
00:59:12,090 --> 00:59:15,700
Jekk T huwa 16, yeah, huwa 16 darbiet 4.

992
00:59:15,700 --> 00:59:20,120
So I jsostnu issa li l-ħin tmexxija ta 'dan ħaġa imsejħa jingħaqdu sort -

993
00:59:20,120 --> 00:59:22,590
u dan se jkun l-fanciest ta 'dawk we stajt tidher s'issa -

994
00:59:22,590 --> 00:59:26,160
se jiġu msejħa n log n

995
00:59:26,160 --> 00:59:31,140
minħabba kif ħafna drabi tista 'Rob maqsum mazz sħiħ ta' tazzi-nofs? Log n.

996
00:59:31,140 --> 00:59:34,370
Huwa l-istess bħall-eżempju ktieb tat-telefon, huwa l-istess bħal l-eżempju awto-għadd.

997
00:59:34,370 --> 00:59:36,380
>> Kemm-il darba tista 'taqsam xi ħaġa fil-nofs?

998
00:59:36,380 --> 00:59:38,410
Madankollu, hemm dan il-pass li qed jingħaqdu.

999
00:59:38,410 --> 00:59:42,920
Inti jista 'jkollok li jaqsam il-kikkri fil nofs mill-ġdid u għal darb'oħra u għal darb'oħra,

1000
00:59:42,920 --> 00:59:45,640
imma kull darba li int se jkollhom jingħaqdu.

1001
00:59:45,640 --> 00:59:48,270
U aħna qal qabel li jingħaqdu tazzi n jieħu passi n

1002
00:59:48,270 --> 00:59:52,060
għaliex ikollok biex ġewwieni out tazza, ġewwieni out tazza, u inti għandek tolqot kull tazza darba,

1003
00:59:52,060 --> 00:59:53,510
bħad Rob għamlet.

1004
00:59:53,510 --> 00:59:59,430
Allura jekk aħna qed tagħmel log xi ħaġa n-ħinijiet u aħna qed tagħmel l-affarijiet n fuq kull wieħed minn dawk iterazzjonijiet,

1005
00:59:59,430 --> 01:00:03,090
kull wieħed minn dawk halvings, għandna n log ħinijiet n.

1006
01:00:03,090 --> 01:00:07,220
Allura jekk aħna plagg fil-16 f'dan l-eżempju, 16-il darba log ta '16 -

1007
01:00:07,220 --> 01:00:10,600
ma joqogħdu jinkwetaw dwar għaliex dan huwa l-każ għal issa għaliex stajt ma ġibed l-bażi -

1008
01:00:10,600 --> 01:00:16,100
iżda log tal-bażi 2 tas-16 huwa ta '4, 16 darbiet 4 huwa 64.

1009
01:00:16,100 --> 01:00:22,350
Iżda għall-kuntrarju, jekk kellna użati tip bużżieqa jew tip jew inserzjoni għażla it-tip ma '16 numri,

1010
01:00:22,350 --> 01:00:26,420
dak li l-ħin taħdem kienu kieku n hija 16?

1011
01:00:26,420 --> 01:00:33,310
Ikun 16 kwadrat, li huwa 256, li anki jekk int ma pjuttost segwew l-matematika,

1012
01:00:33,310 --> 01:00:38,390
256 huwa akbar minn 64. Dik hija verament l-takeaway maġika hawn.

1013
01:00:38,390 --> 01:00:41,990
U jirrealizzaw li jaħdmu permezz ta 'dan fl-eżempji iżgħar kif inti ser fuq pset

1014
01:00:41,990 --> 01:00:44,260
jagħmilha ferm aktar intuwittivi.

1015
01:00:44,260 --> 01:00:49,070
Imma dak li verament ifisser f'termini tal-jħossu ta 'dan algoritmu huwa dan:

1016
01:00:49,070 --> 01:00:54,520
Jekk aħna verament tħares lejn it-tip jingħaqdu hawn - let me pull it up f'dan il-tieqa hawn -

1017
01:00:54,520 --> 01:00:58,560
dan huwa eżempju kemmxejn differenti li bihom aħna għandna kollha 3 ta 'dawn algoritmi -

1018
01:00:58,560 --> 01:01:01,440
bużżieqa, għażla, u jingħaqdu - biss ħdejn xulxin.

1019
01:01:01,440 --> 01:01:03,740
>> Huma kollha bdew bil-bars każwali, u li tajjeb.

1020
01:01:03,740 --> 01:01:06,240
Ħadd ma għandha vantaġġ fundamentali fuq l-ieħor.

1021
01:01:06,240 --> 01:01:09,500
Jien ser fil-mument ikklikkja kull wieħed minn dawn animazzjonijiet - Bidu, Bidu, Bidu -

1022
01:01:09,500 --> 01:01:13,270
malajr kemm nista 'biex, bejn wieħed u ieħor, huma kollha jibdew fl-istess ħin,

1023
01:01:13,270 --> 01:01:17,450
u ejja jikkunsidraw il-każ agħar tip bużżieqa ta 'running time huwa dak? >> [Student] N kwadru.

1024
01:01:17,450 --> 01:01:21,560
N kwadrat. Agħar każ tip Għażla running time hu? N kwadrat.

1025
01:01:21,560 --> 01:01:25,150
U xorta jingħaqdu hija apparentement - anki jekk inti ma pjuttost issegwi l-matematika issa,

1026
01:01:25,150 --> 01:01:30,610
li ser issir ħafna aktar intuwittivi matul iż-żmien - huwa, aħna jsostnu, n log ħinijiet n.

1027
01:01:30,610 --> 01:01:35,210
U minħabba log n huwa strettament inqas minn n ladarba għandna numri kbar,

1028
01:01:35,210 --> 01:01:40,230
n-ħinijiet log n hija iżgħar minn darba n n n kwadrat jew.

1029
01:01:40,230 --> 01:01:44,410
Allura dak ma jħossu li attwalment jiġi algoritmu aħjar f'termini ta 'running time,

1030
01:01:44,410 --> 01:01:50,380
n-ħinijiet log n-kuntrarju n kwadrat? Here we go. Ikklikkja, click, ikklikkja.

1031
01:01:55,690 --> 01:01:58,650
>> Dak hu li jfisser li tuża xi ħaġa simili sort jingħaqdu.

1032
01:01:58,650 --> 01:02:01,680
Għandna mument. Ejja naraw x'jiġri hawn.

1033
01:02:09,440 --> 01:02:12,440
[Chuckles] Li l-flus fuq tip bużżieqa?

1034
01:02:14,960 --> 01:02:16,730
Hija pjuttost jiddependi fuq il-kontribut kultant.

1035
01:02:16,730 --> 01:02:18,120
Ejja naraw.

1036
01:02:18,120 --> 01:02:23,320
Come fuq. Hija tħoss bħal hu ilaħħqu. >> [Student] Go, sort bużżieqa!

1037
01:02:23,320 --> 01:02:27,370
[Studenti murmuring]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Yeah, yeah.

1039
01:02:29,120 --> 01:02:34,520
[Studenti murmuring] Go, mur, mur!

1040
01:02:37,210 --> 01:02:40,450
[Kollha cheering] [applause]

1041
01:02:40,450 --> 01:02:46,240
Allura issa ma '1-aħħar, demo finali, jekk huwa ftit diffiċli biex nagħlaq moħħ tiegħek madwar l-matematika

1042
01:02:46,240 --> 01:02:49,280
jew tip ta 'l-viżwalizzazzjoni hemm, inti tista' attwalment tisma 'l-veloċitajiet

1043
01:02:49,280 --> 01:02:51,000
ta 'algoritmi differenti b'mod differenti.

1044
01:02:51,000 --> 01:02:53,900
Dan huwa xi ħadd animazzjoni magħmula li attwalment assoċjati ħsejjes

1045
01:02:53,900 --> 01:02:56,980
mal-proċess ta 'iskambji u l-għoli tal-bars.

1046
01:02:56,980 --> 01:03:00,440
Kif aħna ser tara hawn, hemm xi algoritmi ftit issortjar aktar hemmhekk li folks ħsibt ta '.

1047
01:03:00,440 --> 01:03:03,660
Dan ewwel waħda se tkun sort inserzjoni, u dan se jtir permezz

1048
01:03:03,660 --> 01:03:07,090
u jagħtuk sens li tinstema 'kif jaħdmu dawn algoritmi varji.

1049
01:03:07,090 --> 01:03:09,080
Hawnhekk huwa tip inserzjoni.

1050
01:03:09,080 --> 01:03:18,410
[Beeping elettroniku]

1051
01:03:18,410 --> 01:03:20,730
[Malan] sort bubble.

1052
01:03:20,730 --> 01:03:46,850
[Mgħaġġla beeping elettroniku]

1053
01:03:46,850 --> 01:03:48,950
[Malan] sort Għażla.

1054
01:03:48,950 --> 01:04:03,580
[Mgħaġġla beeping elettroniku]

1055
01:04:03,580 --> 01:04:05,770
[Malan] sort Merge.

1056
01:04:05,770 --> 01:04:17,270
[Beeping elettroniku]

1057
01:04:17,270 --> 01:04:20,180
[Beeping imewwet] [Rires]

1058
01:04:20,180 --> 01:04:22,590
[Malan] sort Gnome.

1059
01:04:22,590 --> 01:04:38,580
[Beeping elettroniku]

1060
01:04:39,740 --> 01:04:46,150
>> Dan huwa CS50. Aħna ser tara inti ġimgħa d-dieħla. [Applause u cheering]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]