1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [Semajno 3, daŭrigis]

2
00:00:02,280 --> 00:00:04,110
>> [Davido J. Malan - Universitato Harvard]

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

4
00:00:07,130 --> 00:00:11,010
>> Bone. Bonvenon dorso. Ĉi tiu estas CS50 kaj ĉi tiu estas la fino de semajno 3.

5
00:00:11,010 --> 00:00:14,680
>> Do por tiuj nekonataj, lasta jaro Harvard ĵetis kion nomas la Novigo Lab,

6
00:00:14,680 --> 00:00:18,530
aŭ i-laboratorio, kiu estas mirinda konstruaĵo trans la riveron sur HBS la kampuso

7
00:00:18,530 --> 00:00:22,640
kiu estas malfermita al la universitato studentoj, GSAS lernantoj, studentoj el tuta kampuso,

8
00:00:22,640 --> 00:00:27,000
inkludante fakultato, kaj ĝi estas loko por kunveni por labori en pioniraj aĵoj,

9
00:00:27,000 --> 00:00:29,180
aparte emprendedor aĵoj

10
00:00:29,180 --> 00:00:33,410
se vi kaj 0 aŭ pli amikoj pensas fari ion emprendedor

11
00:00:33,410 --> 00:00:37,080
ĉu dum ĉi tiu klaso, post ĉi tiu klaso, aŭ tie.

12
00:00:37,080 --> 00:00:41,540
>> Do unu el la aferoj oni faras sur J termino estas tiuj vojaĝoj,

13
00:00:41,540 --> 00:00:44,510
unu el kiuj estas al Nov-Jorko, unu el kiuj estas Silicia Valo.

14
00:00:44,510 --> 00:00:47,530
Spaco estas tre limigita, sed estas ŝanco froti ŝultroj kun MBAs

15
00:00:47,530 --> 00:00:52,200
kaj postdiploma studentoj trans campus kaj reale pasigas tempon en tiuj respektivaj areoj

16
00:00:52,200 --> 00:00:55,500
babili ĝis startups, babilante ĉe entreprenistoj kaj similaj.

17
00:00:55,500 --> 00:00:57,870
Do, se interesas, kontrolu ĉi URL tie.

18
00:00:57,870 --> 00:01:01,220
Ankaŭ estas disponebla en la diapozitivoj ensalutintaj.

19
00:01:01,220 --> 00:01:04,610
>> Ĉu ni tono malsupren la domo audio malmulta?

20
00:01:04,610 --> 00:01:08,640
Se vi ŝatus aliĝi por tagmanĝi ĉi vendredo, 1:15 pm en Fajro & Glacio, bonvolu direkti tie.

21
00:01:08,640 --> 00:01:11,390
Apologies se la formo estas jam plenigis per la tempo vi alvenos.

22
00:01:11,390 --> 00:01:13,750
Sed ni daŭrigu tiun tradicion antaŭen.

23
00:01:13,750 --> 00:01:17,350
>> Hodiaŭ ni daŭrigos la altan nivelon diskuto de diversaj problemoj kiuj povas solvi,

24
00:01:17,350 --> 00:01:21,330
enfokusigante multe malpli, hodiaŭ almenaŭ, en kodo kaj multe pli en ideoj.

25
00:01:21,330 --> 00:01:24,720
Do pensas reen al semajno 0 kiam ni disŝiris telefono libro en duono,

26
00:01:24,720 --> 00:01:28,260
la objektivo de kiuj estis fari ion, Certe, iom drama

27
00:01:28,260 --> 00:01:32,360
sed sendi la punkto kiu traserĉado ne devas esti, nepre,

28
00:01:32,360 --> 00:01:35,100
kiel evidenta al unua vido, kiel vi povus pensi.

29
00:01:35,100 --> 00:01:40,200
Kaj problemon solvi ĝenerale eble ne nepre ĉiam estas la plej bona -

30
00:01:40,200 --> 00:01:44,130
La plej evidenta solvo por ne nepre estas la plej bona.

31
00:01:44,130 --> 00:01:47,300
Do ni havis ĉi telefonon libron kaj, sincere, ni ĉiuj en tiu ĉambro havis la instinktoj,

32
00:01:47,300 --> 00:01:51,470
plej verŝajne, por komenci en la mezo kiam serĉis Mike Smith kaj tiam iru maldekstren aŭ dekstren

33
00:01:51,470 --> 00:01:54,280
surbaze de kion ajn litero de la alfabeto ni okazis por fini plu.

34
00:01:54,280 --> 00:01:57,560
>> Sed tio simpla ideo, ke ni homoj memkompreneble tiel longe

35
00:01:57,560 --> 00:02:00,670
vere devus komenci veni al la avangardo de via menso

36
00:02:00,670 --> 00:02:03,900
ĉar kiel la problemoj akiri multe pli kompleksa ol telefono libro,

37
00:02:03,900 --> 00:02:07,420
tiuj samaj simpla, brila komprenoj estas kio tuj permesos nin

38
00:02:07,420 --> 00:02:10,259
solvi multe pli komplika kaj pli interesaj problemoj,

39
00:02:10,259 --> 00:02:12,930
inter ili iuj el la aĵoj oni prenas por donita jam tiuj tagoj.

40
00:02:12,930 --> 00:02:15,720
Miliardoj da retpaĝoj tie, kaj tamen Google kaj Bing kaj similaj

41
00:02:15,720 --> 00:02:17,660
kapablas trovi tion por ni tiel.

42
00:02:17,660 --> 00:02:22,300
Tio ne okazas per la uzo de lineara serĉo, serĉante tra ĉiuj eblaj retpaĝoj.

43
00:02:22,300 --> 00:02:25,290
Facebook povas diri al vi kiu ĉiuj viaj amikoj estas aux amikoj de amikoj,

44
00:02:25,290 --> 00:02:28,250
kaj tio ankaŭ povas esti farita ŝajne post momenteto tiujn tagojn

45
00:02:28,250 --> 00:02:30,820
kvankam ili havas milionojn da uzantoj.

46
00:02:30,820 --> 00:02:34,250
>> Kaj do kiel ni efektive solvi problemojn en tiu skalo finfine redukti

47
00:02:34,250 --> 00:02:37,830
al la ideoj, ni rigardis en semajno 0 kaj iom pli hodiaŭ.

48
00:02:37,830 --> 00:02:42,320
Ni ne denove ekzekuti ĉi algoritmon, sed memori ni ankaŭ faris en semajno 0 ĉi ekzerco

49
00:02:42,320 --> 00:02:44,780
kie ni estis ĉiuj ekstari, alpreni la numeron 1,

50
00:02:44,780 --> 00:02:48,720
kaj poste ni havis cxiu mem-grafo de emparejamiento for, aldonante viajn nombroj kune,

51
00:02:48,720 --> 00:02:51,930
tiam duono el la bando sidiĝis sur ĉiun ripeto.

52
00:02:51,930 --> 00:02:56,750
Do ni iris de 500 lernantoj al 250 al 125 ks.

53
00:02:56,750 --> 00:03:00,080
Sed kiel ni diris lundon, la potenca ideo tie

54
00:03:00,080 --> 00:03:02,460
estis, ke se ni dublis la grandeco de tiu problemo

55
00:03:02,460 --> 00:03:06,480
kaj ĉiuj infanoj de Justeco aŭ Ec 10 revenis en la ĉambron kaj aliĝis al ni,

56
00:03:06,480 --> 00:03:09,510
bone, ni povus probable kalkulu ke tutaj aldonita grupo

57
00:03:09,510 --> 00:03:13,380
kun nur 1 pli granda ripeto de la ciklo, ĉar ili nur eble duoble la grandeco

58
00:03:13,380 --> 00:03:15,630
aŭ en Ec 10 kazo de iom pli ol duobla la grandeco.

59
00:03:15,630 --> 00:03:18,440
Kaj tiel ni devus elspezi iom pli da tempo,

60
00:03:18,440 --> 00:03:22,000
sed ni ne devus elspezi 400 aŭ 700 pli paŝoj.

61
00:03:22,000 --> 00:03:26,550
>> Nur por pentri tiun bildon en maniero kiu estas iom malpli abstrakta, ni ne ĉiuj ekstari.

62
00:03:26,550 --> 00:03:31,100
Sed se tiuj el vi, kiuj elektis por sidi en la orkestro hodiaŭ ne gravas piedo,

63
00:03:31,100 --> 00:03:34,580
ni vidu, se ni povas kalkuli inter vi, kiuj la plej alta homo estas

64
00:03:34,580 --> 00:03:36,730
farante la saman specon de kompara algoritmo.

65
00:03:36,730 --> 00:03:41,830
Do se vi sidas en la orkestro, mia pardonpeti, sed paŝo 1, ekstari;

66
00:03:41,830 --> 00:03:44,650
paŝo 2, paro for kun iu apuda vi,

67
00:03:44,650 --> 00:03:49,360
elŝeligi kiu estas pli alta, kaj sidigxu, se vi estas pli mallonga.

68
00:03:49,360 --> 00:03:51,360
Tiam ripeti.

69
00:03:51,360 --> 00:03:56,280
[Studentoj murmurado]

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

71
00:04:15,320 --> 00:04:19,010
Okay. Unu estas lasi ĝin stari. Kio estas via nomo? >> Andreo.

72
00:04:19,010 --> 00:04:21,959
>> Andreo, vi estas la plej alta persono en la orkestro sekcio hodiaŭ.

73
00:04:21,959 --> 00:04:28,100
>> Gratulojn. [Aplaŭdoj kaj huraoj] Okay. Havi sidejon. Do ni trovis Andreon.

74
00:04:28,100 --> 00:04:30,870
Sed kiel longe estus ĝin portinta min, ekzemple, por trovi Andrew

75
00:04:30,870 --> 00:04:33,740
en ĉi tiu orkestro sekcio de 50 + aŭ tiom popolo?

76
00:04:33,740 --> 00:04:36,900
Mi povus esti prenita sufiĉe simpla alproksimiĝon kaj komenci tie.

77
00:04:36,900 --> 00:04:39,270
Kaj mi 2 personoj ekstari kaj mi simple kompari ilin,

78
00:04:39,270 --> 00:04:42,120
kaj tiam mi diros al kiu ajn estas iomete pli mallonga, "Okay, vi sidiĝu,"

79
00:04:42,120 --> 00:04:44,380
kaj mi tuj memoras kiu la alta persono estis.

80
00:04:44,380 --> 00:04:49,030
Tiam mi ripetas, ripeti, ripeti, kaj mi pendas sur la plej alta persono

81
00:04:49,030 --> 00:04:51,920
ĝis mi trovos iun iomete pli alta ol ili, je kiu punkto

82
00:04:51,920 --> 00:04:54,950
la iomete pli mallongaj persono devas tiam sidiĝi.

83
00:04:54,950 --> 00:04:57,690
Sed en tiu algoritmo en ĉi tiu orkestro sekcio, se estas n pri vi,

84
00:04:57,690 --> 00:05:00,480
kiom da paŝoj estas tiu algoritmo tuj prenos? >> [Studento] N.

85
00:05:00,480 --> 00:05:03,580
>> Ĝi tuj preni n, vero, ĉar en la plej malbona kazo, por tiel diri,

86
00:05:03,580 --> 00:05:09,090
la plej alta homo estas la lasta persono kiu alvenis al nur hazarda malbonan sorton.

87
00:05:09,090 --> 00:05:14,260
Do, en la plej malbona kazo, la rula tempo de tiu algoritmo estas lineara, estas n,

88
00:05:14,260 --> 00:05:18,070
kie n estas la nombro de personoj en la spaco, la grandeco de la problemo.

89
00:05:18,070 --> 00:05:19,600
Kio pri ĉi tiu algoritmo?

90
00:05:19,600 --> 00:05:22,080
La fakto ke vi cxiuj ekstaris kaj tiam denove duono el vi sidiĝis,

91
00:05:22,080 --> 00:05:23,950
duono el vi sidiĝis, duono el vi sidigxis.

92
00:05:23,950 --> 00:05:26,070
Kiom da ŝtupoj oni kiuj prenis se estas n de vi ĉi tie?

93
00:05:26,070 --> 00:05:30,200
[Studento] N log n. >> Tio estus malbona. Ensalutu n.

94
00:05:30,200 --> 00:05:32,930
>> Do ensaluti n, eĉ se vi ne sufiĉe memoras kia logaritmo estas,

95
00:05:32,930 --> 00:05:38,410
nuntempe, ĝuste estimi kiu rilatigas iel al ĉi _halving_ kaj _halving_ kaj _halving_.

96
00:05:38,410 --> 00:05:41,000
Ĝi ne devas esti faktoro de 2. Ĝi povus esti faktoro de 3.

97
00:05:41,000 --> 00:05:46,560
Sed temas pri tiu ĉi ripetado de la sama speco de faktoro tia ke la grandeco de la problemo komenciĝas tie

98
00:05:46,560 --> 00:05:49,620
sed tiam tuj iras tie, tiam tie, tiam tie, tiam tie.

99
00:05:49,620 --> 00:05:53,580
Vi ne prenante malgrandan mordas el la problemon, vi vere batante sin al ĝi

100
00:05:53,580 --> 00:05:56,160
kun granda falis plonĝo ĉiufoje.

101
00:05:56,160 --> 00:06:00,810
Do ni havis 50 personoj, tiam 25, do 12 ½ aŭ 13 homoj starantaj,

102
00:06:00,810 --> 00:06:05,370
tiam 6 ½ kaj tiel plu ĝis fine nur Andreon restis staranta.

103
00:06:05,370 --> 00:06:08,710
Do ni iras por voki ke log n, kaj vi povas bildigi tion kiel sekvas.

104
00:06:08,710 --> 00:06:12,570
Memori tiun bildon tie kie lineara algoritmo estas kiel la ruĝa linio tie,

105
00:06:12,570 --> 00:06:17,520
la flava linio estis la kalkula per 2s algoritmo kiu ni uzis por rakonti studentoj

106
00:06:17,520 --> 00:06:22,300
en la pasinteco, sed hodiaŭ la Holy Grail tuj resti ĉi verda linio

107
00:06:22,300 --> 00:06:25,470
kie se ni duobliĝis la nombro de homoj en la orkestro sekcio aŭ nur diris,

108
00:06:25,470 --> 00:06:29,170
infero, ni havas ĉiuj en la tuta ĉambro ekstari, ne tiom granda interkonsento

109
00:06:29,170 --> 00:06:31,560
ĉar ni malafable duobligi kiom da homoj estas cxi tie,

110
00:06:31,560 --> 00:06:33,500
1 pli ripeta, ne estas problemo.

111
00:06:33,500 --> 00:06:36,200
>> Ni trovis Andrew aŭ kiu ajn okazas al esti pli alta ol Andrew

112
00:06:36,200 --> 00:06:38,770
en la interetaĝo aŭ en la balkono.

113
00:06:38,770 --> 00:06:42,140
Do ĉi tiu simpla ideo, ke ni prenis tiom da por donita en telefono libro,

114
00:06:42,140 --> 00:06:46,170
rimarkas ke ekzistas tiom multaj malsamaj lokoj, en kiu ni povas apliki ĝin.

115
00:06:46,170 --> 00:06:50,810
Nur por abofetear iuj Slango - fakte, pli ol ĵargono unua,

116
00:06:50,810 --> 00:06:52,750
lasu min iri al tiu bildo ĉi tie.

117
00:06:52,750 --> 00:06:56,970
Ĝuste nun ni parolis pri n kaj n / 2 kaj poste ensaluti de n,

118
00:06:56,970 --> 00:07:00,500
sed ni povas certe supreniru kun, kiel ni faros en la kurso de la semestro,

119
00:07:00,500 --> 00:07:05,130
aliaj speco de matematika formulo por priskribi ĉi tiun ĝeneralan nocion de rula tempo.

120
00:07:05,130 --> 00:07:07,580
Tio estas ekster la kunteksto por nun cxar ni vidos post nelonge

121
00:07:07,580 --> 00:07:09,900
algoritmoj kiuj tiuj reale reprezentas.

122
00:07:09,900 --> 00:07:17,990
>> Sed rimarki tie la lineara lineo n, la rekto, estas fakte tre malalta montrante nun.

123
00:07:17,990 --> 00:07:22,950
Tio estas speco de optika iluzio en tiu ni nur ŝanĝi kion la x akso reprezentas

124
00:07:22,950 --> 00:07:26,130
kaj la y akso, kaj ni povas fari rekto punkto en ajna direkto ni volas.

125
00:07:26,130 --> 00:07:30,350
Sed la kaŭzo, ke ĝi estas tiel ŝajne ebena nun

126
00:07:30,350 --> 00:07:35,690
estas ĉar ni bezonas por fari lokon sur ĉi grafikaĵo por multe pli malrapida kurante foje.

127
00:07:35,690 --> 00:07:39,030
Cxar nun, sciu ke ekzistas iuj sufiĉe malbone algoritmoj en la vivo,

128
00:07:39,030 --> 00:07:43,790
iuj de kiuj ne prenas n paŝoj aŭ, pli bone ankoraŭ, log n paŝoj sed pli.

129
00:07:43,790 --> 00:07:48,820
Do supre la linio n tie malsupre avizo ekzistas n fojoj log de n,

130
00:07:48,820 --> 00:07:51,410
kaj ni vidos kion ĉi tio signifas antaŭ longe.

131
00:07:51,410 --> 00:07:56,010
Super tiu estas n kvadratoj, kaj ni ne vidis neniun n kvadrataj algoritmoj ankoraŭ sed ni baldaŭ.

132
00:07:56,010 --> 00:07:57,660
Kaj tio aspektas vere malbona.

133
00:07:57,660 --> 00:08:01,610
Estas 2 al la n, iu eksponenta funkcio, kiu sentas eĉ pli malbone.

134
00:08:01,610 --> 00:08:05,760
Kaj tamen, kurioze, tiam ekzistas n potenco de, kiu se vi estas ia pensante antaŭen,

135
00:08:05,760 --> 00:08:10,000
se vi ia fari la math, 2 al la n fakte revenas multe pli rekta,

136
00:08:10,000 --> 00:08:15,930
multe pli alte ol n potenco de se vi rigardas la hakiloj suficxe eksteren.

137
00:08:15,930 --> 00:08:19,890
Do rimarki nun tiuj aksoj estas arbitre 2 al 10 en la x akso.

138
00:08:19,890 --> 00:08:21,770
>> Kaj kion tio signifas?

139
00:08:21,770 --> 00:08:23,890
Tio signifas 2 personoj al 10 personoj en la salono.

140
00:08:23,890 --> 00:08:27,200
Tio estas ĉiuj x signifas: grandeco de problemo, sendepende de la kunteksto estas.

141
00:08:27,200 --> 00:08:30,420
Kaj vertikala akso nun estas la numero de duaj aŭ nombro de paŝoj -

142
00:08:30,420 --> 00:08:31,840
iuj unuo de tempo.

143
00:08:31,840 --> 00:08:34,740
Sed rimarki ke ĝi estas 0 al 60 kaj 0 al 10.

144
00:08:34,740 --> 00:08:38,549
Sed se ni ia zoom out, kiel vi povus en Excel aŭ iu cartografía programaro,

145
00:08:38,549 --> 00:08:43,370
kaj ni supreniras al 200.000, rimarki ke iu kiel 2 ĝis la n

146
00:08:43,370 --> 00:08:47,520
tuj tute Colmar la kuranta tempoj de n kvadratoj,

147
00:08:47,520 --> 00:08:50,960
n potenco de, n logo n - ĉio ni parolis pri tiel for.

148
00:08:50,960 --> 00:08:54,190
Kaj tamen la kaptita estas kiam oni komencas paroli pri aĵoj kiel Facebook

149
00:08:54,190 --> 00:08:57,150
kie vi multaj, multaj, multaj personoj ĉiuj interkonektitaj,

150
00:08:57,150 --> 00:09:00,650
Vi n personoj, ĉiu el kiuj povas havi tiom da kiel n amikoj

151
00:09:00,650 --> 00:09:02,860
se ĉiuj estas speco de buddy-buddy en la mondo,

152
00:09:02,860 --> 00:09:08,100
bone, tio estas n × n jam, do ke tio n kvadrataj eblaj amikecoj,

153
00:09:08,100 --> 00:09:10,950
almenaŭ en 1 direkto, n kvadratoj eblaj amikecojn.

154
00:09:10,950 --> 00:09:15,330
Por ke jam sugestas, ke serĉado de Facebook socia grafeo, por tiel diri,

155
00:09:15,330 --> 00:09:18,090
povas komenci esti esprimita en tiuj specoj de formuloj.

156
00:09:18,090 --> 00:09:19,820
>> Ni revenos kaj fari ĉi multe pli konkreta,

157
00:09:19,820 --> 00:09:23,280
sed nuntempe, la objektiva por la sekvanta multaj semajnoj

158
00:09:23,280 --> 00:09:27,170
tuj estos certa ne iri sur apliki algoritmoj aŭ kodo

159
00:09:27,170 --> 00:09:29,870
kiuj finas prenante tiel tempo kiel io tiamaniere.

160
00:09:29,870 --> 00:09:33,110
Sed la fascina afero pri komputiko se vi daŭrigas en ĉi tiu kampo

161
00:09:33,110 --> 00:09:38,320
prenante klasoj kiel CS121, CS124, ambaŭ el kiuj estas teorio kursoj,

162
00:09:38,320 --> 00:09:41,300
estas kiu estas vere iuj problemoj kiuj ekzistas en la mondo

163
00:09:41,300 --> 00:09:45,710
ke fundamente, gxis ni scias, ne povas esti solvita ajna pli rapida

164
00:09:45,710 --> 00:09:48,880
ol la plej malbona el tiuj grafikaĵoj fakte sugestas.

165
00:09:48,880 --> 00:09:53,660
Do tie estas multe da malfermitaj problemoj en tiu ĉi mondo fari multe pli bone ol homoj havas tiel multe.

166
00:09:53,660 --> 00:09:56,130
>> Do ni komencu do per tiu ekzemplo.

167
00:09:56,130 --> 00:09:59,650
Ni vidis Estu lukto kun ĉi en kamero, ĉiuj tro mallerte en video.

168
00:09:59,650 --> 00:10:05,270
Sed la realo estis, kiam Estu komisiis kun trovi sur tabulo kiel tiu de la numero 7,

169
00:10:05,270 --> 00:10:10,300
memori, ke mi diris tion, "Ne estas ie malantaŭ tiuj pecoj de papero aŭ blankaj pordoj

170
00:10:10,300 --> 00:10:12,570
"La numero 7. Sean, trovu ĝin por ni."

171
00:10:12,570 --> 00:10:14,200
Kaj estis mirinde mallerta rigardi

172
00:10:14,200 --> 00:10:15,790
ĉar li vere luktas kun tiu problemo.

173
00:10:15,790 --> 00:10:19,720
Sed la realo estis Sean faris tiel kiel neniu en la ĉambro povus havi farita.

174
00:10:19,720 --> 00:10:21,890
Li prenis iom pli longa ol tipa persono povus havi,

175
00:10:21,890 --> 00:10:24,760
sed li supozis, ke estis iu lertaĵo por ĉi tiu problemo,

176
00:10:24,760 --> 00:10:26,590
Li supozis, ke li mankis io.

177
00:10:26,590 --> 00:10:29,320
Kaj tio ne helpis, ke centoj da okuloj portantaj sur li.

178
00:10:29,320 --> 00:10:34,250
>> Sed la realo estis, se la enigo al la problemo estas fasko de hazardaj nombroj

179
00:10:34,250 --> 00:10:37,120
kaj vi petante por trovi 1 tia nombro,

180
00:10:37,120 --> 00:10:39,770
la plej bona vi povas fari estas lineara serĉo.

181
00:10:39,770 --> 00:10:44,060
Starti je la maldekstra, movi al la dekstra, aŭ komenci ĉe la dekstra, movi al la maldekstra.

182
00:10:44,060 --> 00:10:48,300
Retroaktive, ni povus pensi, "Estu, kial vi ne komencu la alia fino?"

183
00:10:48,300 --> 00:10:52,120
Nu, 7 povus esti same facile estis tie hazarde,

184
00:10:52,120 --> 00:10:54,980
sed mi intence metis ĝin tie ĉar mi kalkulis ke li ne tuj komencos je la fino.

185
00:10:54,980 --> 00:10:59,320
Do mi specon de manipulita la situacio, sed per hazarda ŝanco 7 povus esti ie ajn.

186
00:10:59,320 --> 00:11:02,380
Do ekde la dekstra fino povus esti pli bone tiam,

187
00:11:02,380 --> 00:11:04,320
sed kio se la venonta jaro mi movi 7 aliloke?

188
00:11:04,320 --> 00:11:06,830
Tio ne estas fundamente nova solvo al la problemo -

189
00:11:06,830 --> 00:11:10,520
ekde 1 fino aŭ la alia - kiam vi donis al neniu alia supozo.

190
00:11:10,520 --> 00:11:13,620
Do Estu komencis rigardi tra la numeroj kaj li diris: "5. Tio ne tie."

191
00:11:13,620 --> 00:11:17,280
Poste li iris tie kaj vidis 19, tiam li pauxzis por proksimume 20 sekundoj,

192
00:11:17,280 --> 00:11:22,330
poste li malfermis ĝin por 13, kaj poste ĝi fariĝis evidenta

193
00:11:22,330 --> 00:11:24,270
ke ne ŝajnas esti mastro ĉi tie.

194
00:11:24,270 --> 00:11:28,090
Ne estis 1, 2, 3, 4 aŭ similaj. Esas breĉoj en la nombroj, kiu ne helpis.

195
00:11:28,090 --> 00:11:32,320
Kaj ankaŭ, la fakto ke mi uzis tiujn malmultekostaj pecoj de papero por kovri la numeroj

196
00:11:32,320 --> 00:11:35,270
Estas vere intenca, ĉar se mi forigis cxiujn tiujn pecojn de papero,

197
00:11:35,270 --> 00:11:38,760
la plimulto de ni, Estu inkludis, probable estus ekrigardis ia macroscopically

198
00:11:38,760 --> 00:11:43,410
ĉe la skribtabulo, kaj diris: "Ho, 7 estas evidente prava." Ni faris tion tuj.

199
00:11:43,410 --> 00:11:46,460
>> Kaj tio estu la maniero la homa cerbo laboras por iu punkto,

200
00:11:46,460 --> 00:11:50,730
sed fakte, liaj okuloj aŭ menso estis probable skimming la numeroj de dekstra al maldekstra,

201
00:11:50,730 --> 00:11:55,190
maldekstre al dekstre, meze sur eksteren - io okazis fisiológicamente

202
00:11:55,190 --> 00:11:57,640
tia, ke ĝi sentis ĝin okazis tuj,

203
00:11:57,640 --> 00:12:01,360
sed malakordo eĉ interne estis iu speco de metodiko por trovi 7.

204
00:12:01,360 --> 00:12:05,160
Kaj efektive, nun ke ni parolas pri tabeloj kaj datumstrukturoj

205
00:12:05,160 --> 00:12:08,780
kaj memoro ene de komputilo, la sola afero, kiun ni homoj povas fari

206
00:12:08,780 --> 00:12:13,070
estas rigardi al individua memoro lokoj 1 samtempe.

207
00:12:13,070 --> 00:12:16,600
>> Do ĉiu alia loko povus tiel esti kovrita kun iu peco de papero

208
00:12:16,600 --> 00:12:21,170
ĉar ni ne povas vidi ĝin iel. Ni nur povas fari 1 afero je tempo.

209
00:12:21,170 --> 00:12:25,030
Do ĉi-kaze, en Estu la kazo, ni iris tie kaj tiam ni iris tien

210
00:12:25,030 --> 00:12:31,040
kaj poste ni iris tien, jen, jen, jen, ili alvenis ruza fine

211
00:12:31,040 --> 00:12:34,450
kaj nur speco de saltis ĉi tiu arbitre kaj trovis 7 tie.

212
00:12:34,450 --> 00:12:37,470
Ĉi tiu ne estis aparte speciala. Ĝi tro iris el ordo.

213
00:12:37,470 --> 00:12:39,530
Sed li fine trovis 7.

214
00:12:39,530 --> 00:12:45,360
Sed nun la takeaway vere estas la plej bona vi povas fari kiam donita neniu informo

215
00:12:45,360 --> 00:12:50,400
alia ol hazardo ordo nombroj estas por komenci el la maldekstra aŭ komenci de dekstre.

216
00:12:50,400 --> 00:12:54,950
Aŭ heck, vi povas hazarde malfermi pordojn, sed eĉ tiam kion tio signifas esti hazarda?

217
00:12:54,950 --> 00:12:57,220
Nu, ni devus iel formaligi kion signifas komenci ĉi tie,

218
00:12:57,220 --> 00:13:01,150
tiam iru tien, tiam iru tien. Estu faris grandajn, kaj estis nur amuze spekti.

219
00:13:01,150 --> 00:13:06,340
Kio se anstataŭe ni ŝanĝas la problemon iom, kaj elvoku ĉijara Sean, se vi volas?

220
00:13:06,340 --> 00:13:09,460
Ĉu iu ajn esti komforta venas sur scenejo kaj solvanta iomete malsama problemo

221
00:13:09,460 --> 00:13:12,330
kaj aperante en kamero?

222
00:13:12,330 --> 00:13:15,720
>> Ni iru trans la orkestro ĉar vi infanoj estis sufiĉe implikita hodiaŭ jam.

223
00:13:15,720 --> 00:13:21,430
Kion pri en rozkolora, en la ĉapelo? Venu malsupren. Kio estas via nomo? >> Alex. >> Alex. Okay.

224
00:13:21,430 --> 00:13:24,580
Do Alex estos ĉijara Estu kaj aperos en la sekvaj jaroj

225
00:13:24,580 --> 00:13:27,770
valoro de CS50 prelegoj.

226
00:13:27,770 --> 00:13:30,340
Alex, nice to meet you. >> Nice to meet you too.

227
00:13:30,340 --> 00:13:33,470
La defio de la mano por vi estas, ke vi havas ĝin iom pli facile

228
00:13:33,470 --> 00:13:38,950
en tiu mi diras al vi la samaj numeroj estas tie, sed ili nun ordo.

229
00:13:38,950 --> 00:13:41,800
Do nun, via celo estas trovi la numero 7.

230
00:13:41,800 --> 00:13:45,370
Kaj efektive, ni devus vere fari ĉi - you're speco de kaptiloj, kiel komputilo estus ne,

231
00:13:45,370 --> 00:13:47,990
rigardante, kion la numeroj estis antaŭ momento.

232
00:13:47,990 --> 00:13:50,360
Per kreto ĉi fakte ne tuj helpi al ĉiuj, ke multe,

233
00:13:50,360 --> 00:13:52,810
sed ni ŝajnigi ke vi ne scias, kion la originala tabelo estas.

234
00:13:52,810 --> 00:13:56,600
Vi nun scias, ke vi havas aron da ordo nombroj

235
00:13:56,600 --> 00:14:00,360
kiuj povus havi distancon inter ili, kaj via celo estas trovi la numero 7.

236
00:14:00,360 --> 00:14:05,080
Kiel vi, racian homo, iru pri trovi la numeron 7?

237
00:14:05,080 --> 00:14:07,770
>> Iru el malaltaj al altaj? >> Bone. Iru malaltaj al altaj.

238
00:14:07,770 --> 00:14:10,990
Kaj ne disŝiros ilin. Ni nur levi ilin do ni povas reuzi ilin.

239
00:14:10,990 --> 00:14:14,730
Okay, do 1. Atendu. Antaŭ vi observos iras, kiu estis 1, klare erara.

240
00:14:14,730 --> 00:14:17,270
Do kio okazas tra via menso poste? Kio estas via sekva movo?

241
00:14:17,270 --> 00:14:23,250
La proksima. >> Bone. La proksima. Bona. 3, tiel malĝusta. Kio estas via sekva movo?

242
00:14:23,250 --> 00:14:27,670
Pluiru. >> Bone. Pluiru. 5.

243
00:14:27,670 --> 00:14:31,110
Do daŭre iras, kaj lasu min transdoni al vi por la estonteco.

244
00:14:31,110 --> 00:14:35,720
7. >> Bonega. Tre bona. Trovis la numero 7. [Aplaŭdo]

245
00:14:35,720 --> 00:14:39,720
Do, kio estis bona, sed Sean tro trovis la numero 7.

246
00:14:39,720 --> 00:14:44,490
Kaj mi argumentas ke vi ne vere ekspluatis tiun plian pecon de informo,

247
00:14:44,490 --> 00:14:47,780
kiu estas kiu ĉi tiuj nombroj estas ordo.

248
00:14:47,780 --> 00:14:51,520
Do ni povas fari pli bone? Ajna sugestojn ĉi tie? Yeah, en dorso.

249
00:14:51,520 --> 00:14:54,710
[Studento] Duuma serĉo. >> Mi tute ne scias kion duuma serĉo estas.

250
00:14:54,710 --> 00:14:58,030
>> [Studento] Komenci en la mezo. >> Start en la mezo. Okay. Do ni vidu se ni povas tien veni.

251
00:14:58,030 --> 00:15:02,580
Do, se anstataŭ vi diris komenco de la meza, iru antaŭen kaj malfermu la mezo pordo.

252
00:15:02,580 --> 00:15:04,580
Estas 8 el ili, do vi tuj devas arbitre elekti la

253
00:15:04,580 --> 00:15:09,800
iomete al la maldekstra aŭ la dekstra. Okay. 7! [Aplaŭdo] Tre bela.

254
00:15:09,800 --> 00:15:11,410
Konsentite, sed kie estis ni iras kun tio?

255
00:15:11,410 --> 00:15:14,990
Ni supozu nur rompi la egaleco vi komencis tie

256
00:15:14,990 --> 00:15:16,670
ĉar tio egale povus esti okazinta tiel.

257
00:15:16,670 --> 00:15:19,540
Ni nur okazis scii ke 7 estis tie. Do ĉi tiu estas 13.

258
00:15:19,540 --> 00:15:21,980
Do, se ili estas ordo kaj ni ĵus komencis en la mezo,

259
00:15:21,980 --> 00:15:24,600
kio estus la optimuma proksima movado estis?

260
00:15:24,600 --> 00:15:27,740
Iru maldekstren. Kaj tiel tie venas la telefono libro ekzemple denove.

261
00:15:27,740 --> 00:15:30,130
Se 13 estas tie kaj ni konas la listo estas ordigita,

262
00:15:30,130 --> 00:15:33,900
tiam ĉiuj el ĉi tiuj pecoj de papero estas seninteresa al ni nun

263
00:15:33,900 --> 00:15:37,400
ĉar ni jam scias ke 7 devas esti al la maldekstra

264
00:15:37,400 --> 00:15:39,510
se ĉi tiuj nombroj estas ordo kaj ni trovis 13.

265
00:15:39,510 --> 00:15:42,500
>> Do kio estas via proksima movado tie? >> Iru al la maldekstra. >> Konsentite, bona.

266
00:15:42,500 --> 00:15:45,080
Do iru al la maldekstra, kaj - atendu, hey, hey, hey. Tio cheating.

267
00:15:47,140 --> 00:15:51,350
Do vi trovis 7, sed kio estis la algoritmo ni ĵus aplikita?

268
00:15:51,350 --> 00:15:56,450
Start en la mezo. >> Bona. Do kio estas la logika etendo de tiu sama ideo?

269
00:15:56,450 --> 00:15:58,970
Ho, por nur tiuj. >> Ekzakte. >> Do mi komencas ĉi tie. >> Bona.

270
00:15:58,970 --> 00:16:02,020
Do nun ni iris iomete al la maldekstra denove. Estas 3.

271
00:16:02,020 --> 00:16:05,310
Sed la interesaj takeaway nun estas kion oni faru al vi ne devas maltrankviligi?

272
00:16:05,310 --> 00:16:08,040
Tiuj 2. >> Tiuj 2. Do nun ĉi tiu povas iri, ĉi tiu povas iri.

273
00:16:08,040 --> 00:16:12,330
Nun la problemo kiu estis 8 tiam estis grandeco 4 nun estas grandeco 2.

274
00:16:12,330 --> 00:16:16,430
Ni nun estas belaj proksima. Denove, iru al la mezo de tiuj 2 eroj.

275
00:16:16,430 --> 00:16:20,430
>> Okay. Do ĝi estas speco de malfeliĉa ke nun ni ĉiam tuj forlasis ĉar ni rondigas sube.

276
00:16:20,430 --> 00:16:25,150
Sed tio estas bone ĉar nun ni ĵetu for kaj ĉion alian, lasante nin per nur 7.

277
00:16:25,150 --> 00:16:30,490
Ni donu ĉirkaŭvojon de aplaŭdoj. Ni trovis 7 denove. [Aplaŭdo] Okay. Certe.

278
00:16:30,490 --> 00:16:32,220
Hang on por ĝuste ankoraŭ 1 sekundo.

279
00:16:32,220 --> 00:16:36,630
Kvankam ke apud procezo ia prenis iom pli longa ol ni sentis ĝin volis,

280
00:16:36,630 --> 00:16:40,150
sincere, via unua instinktoj estis la plej bona, ĉu ne? Ni trovis 7 instantáneamente.

281
00:16:40,150 --> 00:16:46,740
Sed ni estus trovita 7 rapidaj, ne gravas, en ĉi tiu ekzemplo kontre ĉi tiu

282
00:16:46,740 --> 00:16:50,100
ĉar se la nombroj estas ĉiuj ordo, multe kiel la paĝoj en telefono libro,

283
00:16:50,100 --> 00:16:54,580
vi povas ja haku duono de la problemo denove kaj denove kaj denove.

284
00:16:54,580 --> 00:16:56,740
Kaj ne tiom facila al vidi ĉi tion kun nur 8 nombroj

285
00:16:56,740 --> 00:17:00,100
kontraste al 1.000-paĝa telefono libro kie vi vere vidas vide,

286
00:17:00,100 --> 00:17:03,120
sed en ĉi tiu kazo tie kiam Estu serĉis 7,

287
00:17:03,120 --> 00:17:06,020
kiom da paŝoj en la plej malbona kazo estus ĝin portinta lin? >> [Studento] 7.

288
00:17:06,020 --> 00:17:11,670
7 en la plej malbona kazo. Nu, en la plej malbona kazo ne 7 se estas 8 pordoj tie.

289
00:17:11,670 --> 00:17:13,440
Ĝi estus preninta lin 8 paŝoj.

290
00:17:13,440 --> 00:17:18,170
>> Do se ekzistas la n pordoj, ĝi povus esti prenita Estu paro jarojn n paŝoj.

291
00:17:18,170 --> 00:17:21,520
Nun, en via kazo, Alex, pro tio ke tiuj numeroj estas ordo -

292
00:17:21,520 --> 00:17:25,130
kaj ni povas ia inferir ĉi de kie ni estis tiel malproksime en tiu rakonto -

293
00:17:25,130 --> 00:17:28,300
kio estas la rula tempo de Alex pli inteligentaj algoritmo

294
00:17:28,300 --> 00:17:30,770
de ekde la mezo kaj tiam ripeti?

295
00:17:30,770 --> 00:17:36,490
[Studento] 3. >> Do tuj estos 3, malglate, se vi iros de 8 al 4 al 2 al 1.

296
00:17:36,490 --> 00:17:40,660
Do 3 paŝoj aŭ, pli ĝenerale, jen logo n denove.

297
00:17:40,660 --> 00:17:43,380
Ajn vi _halving_ kaj _halving_ kaj _halving_ kaj _halving_,

298
00:17:43,380 --> 00:17:45,290
jen esprimo de ĉi tiu ideo de logo n.

299
00:17:45,290 --> 00:17:48,140
Kaj por ke estus preninta vi nur 3 paŝoj, kaj ĝi efektive faris

300
00:17:48,140 --> 00:17:50,890
iam ni malfermis la pordojn _halving_ kaj _halving_,

301
00:17:50,890 --> 00:17:53,770
dum ĉi tiu estus preninta Estu iu 7 aŭ 8 paŝoj.

302
00:17:53,770 --> 00:17:56,330
Do dankon por esti kun ni ĉi tiun jaron. >> Dankon. Nice kunveno vi.

303
00:17:56,330 --> 00:18:00,170
Dankon al Alex. >> Same. [Aplaŭdo]

304
00:18:00,170 --> 00:18:02,150
>> Kio estas tiam la reala implikaĵo de tiu?

305
00:18:02,150 --> 00:18:06,050
Nun imagu ke ĝi ne estas 8 pordoj, kiuj, sincere, ĉiuj el ni povus trovi ion

306
00:18:06,050 --> 00:18:10,430
malantaŭ 8 pordoj bela rapide kun nur disŝiri la pecoj de papero kaj tuj kun niaj instinktoj.

307
00:18:10,430 --> 00:18:14,430
Sed kion se estas miliono pordoj? Kio se estas 4 miliardoj pordoj?

308
00:18:14,430 --> 00:18:19,630
En la kazo de 4 miliardoj pordojn, vi vere tuj volas iri kun Alex algoritmo,

309
00:18:19,630 --> 00:18:23,150
duuma serĉo al ni komencu nomi ĝin aŭ dividi kaj venki, pli ĝenerale,

310
00:18:23,150 --> 00:18:25,220
kie vi observos _halving_ kaj _halving_ la problemo,

311
00:18:25,220 --> 00:18:30,510
ĉar se vi havas 4 miliardoj pordoj, kiom da fojoj vi povas haku 4 miliardoj en duono?

312
00:18:30,510 --> 00:18:33,870
[Studento] 32. >> Fakte 32. Vi povas labori ĉi sur peco de papero aŭ en via kapo.

313
00:18:33,870 --> 00:18:38,490
Vi iru 4 miliardoj al 2 miliardoj al 1 miliardo al duona miliardo, al 250 milionoj, pentras, pentras, punkto.

314
00:18:38,490 --> 00:18:41,620
Kaj se vi faras ekster la math, vi tuj ja akiri 32,

315
00:18:41,620 --> 00:18:44,950
kaj tio efektive rilatas al komputiko, ĉar ni kutime rakontas en potencoj de 2.

316
00:18:44,950 --> 00:18:47,600
2 al la 32 hazarde estas 4 miliardoj.

317
00:18:47,600 --> 00:18:51,440
Do tie estas multe da graveco al tiuj specoj de potencoj de 2 en komputiko.

318
00:18:51,440 --> 00:18:55,120
>> Sed kio pri 8 miliardoj? Kiom da paŝoj estas ke tuj prenos se estas 8 miliardojn da pordoj?

319
00:18:55,120 --> 00:19:00,350
[Studento] 33. >> Do 33. Kio se estas 16 miliardoj pordoj? Kiom da paŝoj estas ke tuj prenos?

320
00:19:00,350 --> 00:19:05,020
[Studento] 34. >> 34. Ni povus ia daŭrigu tiun ad nauseam. Sed tio estas potenca afero.

321
00:19:05,020 --> 00:19:09,430
Vi povas enkonduki miliardoj da pli enigoj al via problemo sed, neniu granda interkonsenton,

322
00:19:09,430 --> 00:19:14,140
vi simple prenu 1 plia mordo el ĝi kaj tiel donas al ni iun kiel duuma serĉo

323
00:19:14,140 --> 00:19:15,920
aŭ dividi kaj venki, pli ĝenerale.

324
00:19:15,920 --> 00:19:17,990
Sed mi estas speco de cheating tie, ĉu ne?

325
00:19:17,990 --> 00:19:22,410
En la kazo de Alex algoritmo, ŝi havis avantaĝon super Sean.

326
00:19:22,410 --> 00:19:27,780
Ŝi sciis, ke tiuj nombroj estis ordo, sed Alex ne devis ordigi ilin mem.

327
00:19:27,780 --> 00:19:30,520
Mi anticipe venis supren al la nigra tabulo kaj tipon de certigis

328
00:19:30,520 --> 00:19:33,670
ke mi tiris ilin ĉiujn ekster en ordo ordo, tiam mi kovris ilin per papero.

329
00:19:33,670 --> 00:19:35,850
Sed kiom laboro faris ke kapti min?

330
00:19:35,850 --> 00:19:40,110
Se ni dividis kun tiuj nombroj en iu kvazaŭe hazarda ordo -

331
00:19:40,110 --> 00:19:43,320
en ĉi tiu kazo tiuj simplaj numeroj 1 ĝis 8 tie -

332
00:19:43,320 --> 00:19:46,090
kiel ni iru sur ordigi tiujn valorojn?

333
00:19:46,090 --> 00:19:52,530
Se vi estus homo donis tiun taskon, kian intuicia proksimigo vi prenu

334
00:19:52,530 --> 00:19:54,800
al ordiga tuta amaso de nombroj?

335
00:19:54,800 --> 00:19:57,050
Tion ili aranĝiĝas tiel puzlo pecojn. Yeah.

336
00:19:57,050 --> 00:19:59,950
>> [Studento] mi prenus ĉiun numeron kaj kompari ĝin al ĉiu

337
00:19:59,950 --> 00:20:03,180
kaj observu tuj maldekstren. >> Konsentite, bona.

338
00:20:03,180 --> 00:20:05,720
Do prenu ĉiu nombro, kompari ĝin al la flanko de ŝi,

339
00:20:05,720 --> 00:20:09,610
kaj tiam simple observu movas laŭ la listo, ia rejiggering aĵoj kiel vi iros.

340
00:20:09,610 --> 00:20:13,800
Do jen ni havas ŝancon por eble kelkaj pli ulojn por implikiĝi.

341
00:20:13,800 --> 00:20:16,290
Ĉu ni havas ankoraŭ 8 volontuloj kiuj ravus sin levas?

342
00:20:16,290 --> 00:20:23,950
Iom malpli premo ĉar vi ne estas la sola. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Venu malsupren. You guys tuj estos la numeroj 1 ĝis 8.

344
00:20:28,190 --> 00:20:36,050
Ni vidu se ni ne povas fari ĉi ordigado de Alex tiel en la sama maniero mi faris ĝin anticipe.

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

346
00:20:37,640 --> 00:20:40,760
Iru antaŭen kaj se vi volus, linio sur etapo inter la muziko stand kaj mi cxi tie

347
00:20:40,760 --> 00:20:44,960
en la sama ordo kiel la glito sur la ekrano.

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

349
00:20:50,370 --> 00:20:53,230
Ni laboras vin en la sekva ekzemplo. Ho, atendu, atendu. Ĉi tie ni iru. Atendu.

350
00:20:53,230 --> 00:20:57,570
La sekva ekzemplo estas nun. Ĉi tie vi iros. Numero 8. Venu supren.

351
00:20:57,570 --> 00:21:00,270
Bone. Ordigi mem laŭ ĉi.

352
00:21:00,270 --> 00:21:03,620
Gliti malmulta al la flanko de la muziko staras tie.

353
00:21:03,620 --> 00:21:12,310
Do ni havas 4, 2, 6 - eniri tie, tie, dekstre tie - 3.

354
00:21:12,310 --> 00:21:17,570
Yeah. Okay. Vi iros tien. Ne, vi restu tie.

355
00:21:17,570 --> 00:21:21,840
Yeah, prava. Ne ke mi malpravas. Ĝuste tie. Konsentite, tre bona. Okay.

356
00:21:21,840 --> 00:21:24,930
Do nun ni ordigi ilin en kreskanta ordo.

357
00:21:24,930 --> 00:21:26,210
>> Kiel mi povas iri faras tion?

358
00:21:26,210 --> 00:21:28,630
La algoritmo kiu estis proponita antaŭ momento estis kial ni ne nur komparu

359
00:21:28,630 --> 00:21:31,970
la ulojn, kiuj estas speco de apud la alia kaj tiam fiksi ajnan erarojn,

360
00:21:31,970 --> 00:21:33,540
movi de maldekstre al dekstre.

361
00:21:33,540 --> 00:21:36,580
Do jen ni havas 4 kaj 2, evidente el ordo. Ni interŝanĝas vi. Okay.

362
00:21:36,580 --> 00:21:40,760
Do nun mi iros por movi tra la linio. 4 kaj 6, nope. [Ridado]

363
00:21:40,760 --> 00:21:45,010
6 kaj 8, sufiĉe bone. 8 kaj 1, lasu min interŝanĝi you guys. Bone.

364
00:21:45,010 --> 00:21:48,030
Do 8 kaj 3, interŝanĝi you guys.

365
00:21:48,030 --> 00:21:52,280
8 kaj 7, lasu min interŝanĝi you guys. 5 kaj 8, bonega.

366
00:21:52,280 --> 00:21:54,820
Mi donas al vi ordo listo.

367
00:21:54,820 --> 00:21:56,860
Bone. Do ne tute.

368
00:21:56,860 --> 00:22:01,180
Sed estas pli bone ĉar la grandaj nombroj - kazo en punkto 8 -

369
00:22:01,180 --> 00:22:04,030
esti speco de bobelis el la maldekstra sur la dekstran.

370
00:22:04,030 --> 00:22:08,010
Do mi atingis 1 el ili rajton, sed sentas kiel ĉi tio ne sufiĉe solvi la problemon.

371
00:22:08,010 --> 00:22:11,150
>> Do kion vi proponas ke ni faru? >> [Studento] Konservu fari ĝin. >> Ni observu fari ĝin.

372
00:22:11,150 --> 00:22:13,740
Kaj realigi, denove, ni starigis aĵojn por nur havi ĉiuj homoj

373
00:22:13,740 --> 00:22:17,180
speco de inteligente aranĝi sin bazas sur tiu foto,

374
00:22:17,180 --> 00:22:19,040
sed nun ni devas esti multe pli metoda.

375
00:22:19,040 --> 00:22:21,510
Ni devas esti algoritma pri ĝi kvazaŭ ni skribas kodo -

376
00:22:21,510 --> 00:22:23,520
en ĉi tiu kazo parola _pseudocode_.

377
00:22:23,520 --> 00:22:26,040
Do mi simple provi tion denove. Kiu funkciis sufiĉe bone. Ĝi ne solvis ĝin.

378
00:22:26,040 --> 00:22:30,400
Sed kiam dubas, nur provu kaj reprovu. Do 2 kaj 4, ne helpis plu.

379
00:22:30,400 --> 00:22:33,200
4 kaj 6. Ah! 6 kaj 1, iomete pli bone nun.

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

381
00:22:39,740 --> 00:22:44,060
Kaj vi scias, mi probable povas ignori 8 nun ĉar li estas ĉe la fino de la listo.

382
00:22:44,060 --> 00:22:47,250
Eble ni ne devas zorgi pri iu iras preter li.

383
00:22:47,250 --> 00:22:49,240
Sed ni vidu se tio estas sekura supozo.

384
00:22:49,240 --> 00:22:52,340
Nun listo estas - malbenita - ne ordo. Ni provu ĉi denove.

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

386
00:22:56,440 --> 00:22:59,230
4 kaj 6, bona. 6 kaj 5, bona.

387
00:22:59,230 --> 00:23:04,890
6, 7, kaj 8, bona. Sed rimarki, mi povas nur halti ĉi tie kaj nun haltos tie nun?

388
00:23:04,890 --> 00:23:07,770
[Studento] Jes. >> Jes?

389
00:23:07,770 --> 00:23:11,160
Kio se unu el vi estus la numero 9 tuta vojo tien?

390
00:23:11,160 --> 00:23:13,640
Ĝi estus ordo. >> Bona. Ĝi estus ordo la unua fojo ĉirkaŭe.

391
00:23:13,640 --> 00:23:16,050
Bona. Do ni iru returne. Ni estas preskaŭ tie.

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

393
00:23:22,800 --> 00:23:26,640
>> Mi faris nun sed, denove, mi estas komputilo kiu povas nur faras kion mi diras al li,

394
00:23:26,640 --> 00:23:30,120
kaj mia sola rememoro nun estas, ke mi fakte ĝuste faris iom da laboro.

395
00:23:30,120 --> 00:23:31,700
Io ŝanĝis tie.

396
00:23:31,700 --> 00:23:37,100
Do mi ne teknike konfirmis vide aŭ Algoritma ke ĉi listo estas ja ordo.

397
00:23:37,100 --> 00:23:40,720
Do nur por bona mezuro, nur por esti anal pri tio, ni faru ĉi ankoraŭ 1 tempo.

398
00:23:40,720 --> 00:23:44,040
Do 1 kaj 2, 2 kaj 3, 3 kaj 4. Kaj vi scias kion?

399
00:23:44,040 --> 00:23:46,190
Nur por bonan mezuron, mi iros al konservi trako sur mia mano ĉi tiun fojon

400
00:23:46,190 --> 00:23:51,110
kiom da svopoj Mi faras ĝuste tiom ke mi scios kiom labori mi efektive faris.

401
00:23:51,110 --> 00:23:56,930
3 kaj 4, 4 kaj 5, 5 kaj 6, 6 kaj 7, 7 kaj 8. Neniu svopoj.

402
00:23:56,930 --> 00:24:00,800
Do nun mi laŭleĝe esti idioto por fari ĉi denove

403
00:24:00,800 --> 00:24:03,330
ĉar se mi faris nenian laboron tra tiu paŝo de la homoj,

404
00:24:03,330 --> 00:24:06,710
tiam klare ke okazos denove se neniu el ili estas ia hazarde

405
00:24:06,710 --> 00:24:10,410
adversarially movi sin ĉirkaŭe. Do nun mi povas halti.

406
00:24:10,410 --> 00:24:15,120
Nun ni petas la demando, kiom da laboro tio ĉi reale preni min?

407
00:24:15,120 --> 00:24:18,260
Kiom da ŝtupoj ne ke preni? >> N kvadrato.

408
00:24:18,260 --> 00:24:20,400
Yeah, do n kvadratoj. Kie do vi ricevis n kvadratoj de?

409
00:24:20,400 --> 00:24:22,660
Vi devas kontroli ĉiun num -

410
00:24:22,660 --> 00:24:26,530
Tie estas n nombroj, kaj vi devas kontroli ĉiun numeron kun la aliaj n nombroj.

411
00:24:26,530 --> 00:24:29,030
Bona. >> Do ĝi estas n kvadratoj. >> Bona.

412
00:24:29,030 --> 00:24:31,060
>> Do sentas ĝin tre bone povus esti n kvadratoj, ĉu ne?

413
00:24:31,060 --> 00:24:33,820
Okazis n de tiuj infanoj, 8 specife en ĉi tiu kazo,

414
00:24:33,820 --> 00:24:37,590
sed ĉiufoje mi iris tra tiu listo mi komparas la unua persono kontraŭ la dua,

415
00:24:37,590 --> 00:24:39,650
la dua kontraŭ la tria denove kaj denove kaj denove,

416
00:24:39,650 --> 00:24:42,450
kaj kiam mi alvenis al la fino, kion mi faru? Mi redid ĝin.

417
00:24:42,450 --> 00:24:46,280
Do, se ni ĝeneraligi ĉi klarigo, ni n homoj

418
00:24:46,280 --> 00:24:51,090
kaj mi faras, evidente, 8 ŝtupoj, n paŝoj, ĉiufoje mi iras tra ĉi tiu algoritmo.

419
00:24:51,090 --> 00:24:56,070
Sed kiom da fojoj en la plej malbona kazo mi devas iri tra tiu listo de homoj?

420
00:24:56,070 --> 00:24:59,370
[Studento] N-foje. >> Probable n, vero, ĉar en la plej malbona kazo,

421
00:24:59,370 --> 00:25:03,410
kio estas probable la plej malbona kazo ordigo de tiuj infanoj de la get-go?

422
00:25:03,410 --> 00:25:06,520
Se ili estas tute renversita ordo

423
00:25:06,520 --> 00:25:09,310
ĉar ĝuste supozi mense, let's - Kio estas via nomo? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Okay. Do Bowen, venu ĉi tien por nur momento.

425
00:25:12,510 --> 00:25:16,150
>> Supozu ke Bowen estis tie komence de la algoritmo,

426
00:25:16,150 --> 00:25:19,790
kaj ni ne scias, kion ĉiuj aliaj estas, sed Bowen tie, laŭ ĉi tiu algoritmo -

427
00:25:19,790 --> 00:25:23,820
kaj se vi volas nur promenas kun mi - tuj bobelo supren, kiel li faris la unuan fojon ĉirkaŭe,

428
00:25:23,820 --> 00:25:25,740
tuta vojo al la fino.

429
00:25:25,740 --> 00:25:29,400
Sed supozu ke la persono apud Bowen estis la numero 7.

430
00:25:29,400 --> 00:25:33,450
Mi devas reiri kaj akiri numero 7, kio signifas mi devas iri la tutan vojon reveni ĉi tien.

431
00:25:33,450 --> 00:25:36,980
Nun mi devas havi tiun saman promenadon kun la persono kiu estas numero 7.

432
00:25:36,980 --> 00:25:40,140
Sed kion se tiam numero 6 estis apud li tiel?

433
00:25:40,140 --> 00:25:42,180
Tiam mi devas reiri kaj akiri 6.

434
00:25:42,180 --> 00:25:46,490
Do denove, sur ĉiu ripeto de ĉi buklo mi parolas al ĉiu de la n personojn,

435
00:25:46,490 --> 00:25:50,090
kaj mi povus havi por fari n de tiuj promenadojn por certigi min tirante

436
00:25:50,090 --> 00:25:53,760
ĉiuj el la plej grandaj elementoj reen kaj reen kaj reen al la fino de la listo.

437
00:25:53,760 --> 00:25:58,230
Do n aĵoj n fojoj estas nur n × n aŭ n kvadratoj.

438
00:25:58,230 --> 00:26:02,050
>> Do jen jam ni havas algoritmon kiu ne plu n, jen ne plu log n,

439
00:26:02,050 --> 00:26:04,820
ĝi estas fakte malbona ol io ni faris antaŭe.

440
00:26:04,820 --> 00:26:09,840
Do Alex ia atingis bonŝanca en kiun Mi faris ĉion de la verko ŝajne supren fronto por ŝi,

441
00:26:09,840 --> 00:26:14,690
ĉiuj peniga laboro, por ke ŝi povis ĝui en ĉi duuma serĉo algoritmo,

442
00:26:14,690 --> 00:26:16,420
kiu estas log de n.

443
00:26:16,420 --> 00:26:18,240
Sed ĉi tiu estas konsekvenca kun lundo temo.

444
00:26:18,240 --> 00:26:23,260
Ni donis iom pli da spaco, oni uzas pli bitoj, por akceli nian rula tempo.

445
00:26:23,260 --> 00:26:26,170
Tiel kiel tie estas tio komerco-off inter tempo kaj spaco,

446
00:26:26,170 --> 00:26:31,060
tie povus ankaŭ esti nur komerco-offs inter tempo pasis supren antaŭa ia atingi aĵojn preta iri

447
00:26:31,060 --> 00:26:35,000
kaj fakte ekzekuti algoritmon kiel serĉo. Ni provu alian.

448
00:26:35,000 --> 00:26:39,050
Se vi infanoj ne gravas nur rapide reordigante vin egali ke denove,

449
00:26:39,050 --> 00:26:42,240
ni provu ion iomete malsama kie ĝi ne estas tiom simpla

450
00:26:42,240 --> 00:26:45,760
kiel simple ripari ĉiujn duoplarĝa erarojn, kiu estas super intuicia.

451
00:26:45,760 --> 00:26:48,150
Ni anstataŭ esti iom pli intenca kaj fari ĉi tion.

452
00:26:48,150 --> 00:26:51,010
Ĉi tiu tro Mi proponus estas probable bela intuicia.

453
00:26:51,010 --> 00:26:55,070
>> Ni elektu la plej malgranda persono el la listo denove kaj denove. Do jen ni iru.

454
00:26:55,070 --> 00:26:57,350
4, vi estas la plej malgranda persono mi tiel vidas ĝis nun,

455
00:26:57,350 --> 00:27:00,520
do mi tuj mense memori ke por nur montrante vin nun.

456
00:27:00,520 --> 00:27:05,020
2. Ooh! Forgesu pri numero 4. Mi nur trovis la novan malgranda elemento en tiu listo.

457
00:27:05,020 --> 00:27:07,410
Mi tuj ia memoras tion. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ooh! 1. Adiaŭ. Do nun mi iros al memori numero 1.

459
00:27:11,190 --> 00:27:14,790
Ni scias ke 1 estas la plej malgranda, sed mi estas la komputilo. Kio se estas 0?

460
00:27:14,790 --> 00:27:17,140
Kio se estas -1? Mi devas teni tuj.

461
00:27:17,140 --> 00:27:20,990
Do 3, 7, 5, nope. Okay. Do la numero 1 estis la plej malgranda.

462
00:27:20,990 --> 00:27:23,640
Lasu min elekti vin de la listo - we'll iri tiun vojon -

463
00:27:23,640 --> 00:27:27,760
kaj metis vin arbitre komence de la listo.

464
00:27:27,760 --> 00:27:29,740
Nun, atendu momenton. Mi ia trompis.

465
00:27:29,740 --> 00:27:34,010
Se ĉi tiuj infanoj reprezentas ne liston de 8 personoj sed tabelo,

466
00:27:34,010 --> 00:27:37,050
8 pecoj de apudaj memoro - vi ĝenas tretante reen por momento?

467
00:27:37,050 --> 00:27:39,060
Estas vere ne spaco por vi ĉi tie.

468
00:27:39,060 --> 00:27:41,840
Nu do kiel ni faras spaco por - kio estas via nomo? >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
Kiel ni faru spacon por Sammy?

470
00:27:43,710 --> 00:27:46,760
>> Ni movi la n kiuj estas antaŭ mi. >> Bone.

471
00:27:46,760 --> 00:27:48,850
Do ni povus kopii la n popolo, kiu estas antaŭ Li,

472
00:27:48,850 --> 00:27:52,400
do se vi infanoj volis preni 1 intenca, drama paŝo al la maldekstra.

473
00:27:52,400 --> 00:27:57,000
Ili ĉiuj faris ke en unisono, sed lastfoje mi skribis iom da kodo,

474
00:27:57,000 --> 00:27:59,740
vi ne povas ordigi de movi multajn aferojn samtempe.

475
00:27:59,740 --> 00:28:02,450
Ni povis fari ĝin en buklo, movante ĉiuj iam samtempe.

476
00:28:02,450 --> 00:28:04,340
Do se vi infanoj ne gravas tretante al la dekstra,

477
00:28:04,340 --> 00:28:07,230
kaj Sammy, se vi povus retropaŝon ĉar tie estas ankoraŭ loko por vi,

478
00:28:07,230 --> 00:28:11,420
nun ni faros. Kie estis Sammy antaŭ momento? Ĝuste tie.

479
00:28:11,420 --> 00:28:16,140
Do tie estas breĉo tie. Do vi povus movi en Sammy la makulo.

480
00:28:16,140 --> 00:28:20,580
Nun sekva persono supren kaj nun sekva persono, nun sekva persono. Nun ni havas ĉambron por Sammy.

481
00:28:20,580 --> 00:28:23,490
Nun, iu el la publiko - tio estis bona, kiu estis ĝentila,

482
00:28:23,490 --> 00:28:27,070
ĝi sentis iom temporaba - kio estas pli rapida? Yeah.

483
00:28:27,070 --> 00:28:29,440
[Studento] nova tabelo? >> Kio estas tio? >> [Studento] nova tabelo? >> Konsentite, bona.

484
00:28:29,440 --> 00:28:33,200
>> Do kohera kun tiu temo nur komerco-offs, kial ne mi simple fari novan tabelo

485
00:28:33,200 --> 00:28:36,570
 kaj tiam Sammy estos naĝante en la spaco antaŭ tiuj homoj, ekzemple,

486
00:28:36,570 --> 00:28:39,600
kaj ni povas nur komencas plenigi nova tabelo aro. Tio tro laborus.

487
00:28:39,600 --> 00:28:42,450
Sed mi ne interesiĝas pri elspezi pli spaco nuntempe. Kio estas alia alproksimiĝo?

488
00:28:42,450 --> 00:28:46,630
[Studento] Swap. >> Bone. Ni povus simple interŝanĝi tiuj 2 infanoj. Kio estas via nomo?

489
00:28:46,630 --> 00:28:49,390
Mario. >> Mario. Do Mario, vi estis aktuale tie.

490
00:28:49,390 --> 00:28:52,480
Sammy, vi povas subteni por nur momenta? Mario estis tie.

491
00:28:52,480 --> 00:28:55,830
Ni ne havas lokon por vi plu, do se vi ne gravas iri al kie Sammy estas,

492
00:28:55,830 --> 00:29:02,430
ni metos Sammy tie, kaj nun mi argumentas ke Sammy la interŝanĝante operacio estis multe pli rapida.

493
00:29:02,430 --> 00:29:06,370
Ni faris 1 operacio por interŝanĝi tiujn infanoj, aŭ eble 2 ĝis interŝanĝi tiujn knaboj,

494
00:29:06,370 --> 00:29:11,210
sed ni ne faris 1, 2, 3, 4, por ke sentu bone. Nun, atendu momenton.

495
00:29:11,210 --> 00:29:14,660
Mi ia faris la problemo malbona ĉar numero 4 estis speco de proksime al la komenco.

496
00:29:14,660 --> 00:29:19,470
Nun numero 4 estas iom pli proksima al tio, sed mi ne vere scias aŭ zorgas pri tio.

497
00:29:19,470 --> 00:29:23,330
Do ĉi tiu estas nur malbona sorto tiu numero 4 estas iom pli for de lia destinita loko.

498
00:29:23,330 --> 00:29:25,110
Do ni nun ripeti ĉi tiu algoritmo.

499
00:29:25,110 --> 00:29:28,410
>> Por recap, dum tiu rakonto estis, ĉiuj ni ne estis trairu la listo

500
00:29:28,410 --> 00:29:31,130
serĉas la plej malgranda kalkulitaj persono.

501
00:29:31,130 --> 00:29:34,530
Do nun ni faru ĝin denove. Ni ne devas maltrankviligi Sammy plu.

502
00:29:34,530 --> 00:29:37,590
Ni povas nur iru tien. Ooh! Numero 2. Tio estas bela malgranda nombro.

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

504
00:29:41,180 --> 00:29:43,770
Kaj dankeme, per hazardo, mi ne devas movi - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie ĉar li estas en sia ĝusta loko nun.

506
00:29:45,910 --> 00:29:48,110
Ni faru ĉi denove kaj ignori tiujn 2 infanoj.

507
00:29:48,110 --> 00:29:50,460
6. Tio estas bela malgranda nombro. Ooh! 8 estas definitive pli granda.

508
00:29:50,460 --> 00:29:53,410
4. Ni enfokusigi 4. Ooh! 3 estas eĉ pli bona.

509
00:29:53,410 --> 00:29:58,290
7 kaj 5. Do kion ni faru nun kun - >> Roger. >> Roger?

510
00:29:58,290 --> 00:30:00,250
Ni interŝanĝas ĝin kun numero 6.

511
00:30:00,250 --> 00:30:03,570
Do se 6 kaj 3 ŝatus interŝanĝi,

512
00:30:03,570 --> 00:30:07,320
ni nun speco de alveninta bonŝanca en tiu 6 estas pli proksima al kie devus esti,

513
00:30:07,320 --> 00:30:10,300
sed estas nur koincido tie. Do ni nun iru tien.

514
00:30:10,300 --> 00:30:13,430
8 estas bela malgranda nombro. Ooh! 4 estas pli malgranda.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. Kion ni nun faru? >> Swap. >> Ekzakte.

516
00:30:17,130 --> 00:30:19,010
Do nun ni faros ĉi tia rapida.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. Kie 5 iri? Bona. Okay.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 gets resti kie ŝi estas. Kio estas via nomo? >> Rosalie.

519
00:30:28,380 --> 00:30:31,770
Rosalie gets resti kie ŝi estas. 7 alvenas al - Ni vidos. 7, 8. Okay.

520
00:30:31,770 --> 00:30:35,100
Do 7 ricevas resti kie ŝi estas. Kio estas via nomo? >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> Do Amna gets resti kie ŝi estas, kaj la numero 8 estas jam kie li nun devus esti.

522
00:30:39,670 --> 00:30:43,960
Konsentite, bona. Sentas kiel ni ĵus kreis verkon por ni mem tie, though.

523
00:30:43,960 --> 00:30:47,440
Kio estas finfine la rula tempo de ĉi tiu algoritmo?

524
00:30:47,440 --> 00:30:51,900
Se ni pensas pri tiuj homoj ne 8 sed kiel n? >> Estas n.

525
00:30:51,900 --> 00:30:55,440
Ĝi estas n paŝoj, sed ni kontrolanta ĉiu unuopa tempo.

526
00:30:55,440 --> 00:30:57,570
Okay. N sed vi kontrolanta ĉiu unuopa tempo?

527
00:30:57,570 --> 00:31:03,450
Konsentite, sed se ĝi estas n paŝoj, cxu Mi povus ne povis ordigi vi per nur irante 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
Ho! Konsentite, ke estas granda diferenco.

529
00:31:05,590 --> 00:31:08,050
Do n kvadrata kial? Kio vere okazas?

530
00:31:08,050 --> 00:31:12,130
Estas n homoj en tiu listo, sed por trovi la plej malgranda persono en la listo

531
00:31:12,130 --> 00:31:16,200
en la plej malbona kazo, kiom da ŝtupoj mi devas preni? >> N.

532
00:31:16,200 --> 00:31:19,160
>> N, dekstra, ĉar en la plej malbona kazo, nombro 1 estas la tuta vojo tien,

533
00:31:19,160 --> 00:31:20,990
do mi devas iri preni lin aŭ ŝin.

534
00:31:20,990 --> 00:31:25,500
Kaj poste, kiam mi fine realigi 1 estis la plej malgranda, tiam ĝi estas bela rapide interŝanĝi ilin.

535
00:31:25,500 --> 00:31:28,450
Sed nun mi devas komenci de la komenco kaj serĉi kiu?

536
00:31:28,450 --> 00:31:31,980
La sekva pli malgranda persono, kiu estas 2. Kie en la plej malbona kazo estas 2?

537
00:31:31,980 --> 00:31:34,320
Ho, mia Dio. Estas tuta vojo super tie je la fino.

538
00:31:34,320 --> 00:31:37,000
Do nun mi ĵus faris alian n paŝoj, alia n paŝoj.

539
00:31:37,000 --> 00:31:41,200
Kaj se ni havas n homo kaj en la plej malbona kazo la plej malgranda persono estas n paŝojn for,

540
00:31:41,200 --> 00:31:45,230
jen denove n × n, kaj do ni denove havas n kvadratoj.

541
00:31:45,230 --> 00:31:47,280
Ĉi tio ne sentante tiel bona.

542
00:31:47,280 --> 00:31:52,150
Kaj fakte, ecx en la plej bona kazo - supozi ke ili dividi ordo -

543
00:31:52,150 --> 00:31:59,080
kiom da paŝoj necesas por mi uzas tiun ĉi algoritmon por ordigi tiujn n popolo?

544
00:31:59,080 --> 00:32:01,010
N akordita. >> Mi aŭdis n kvadratoj. Kial n akordita?

545
00:32:01,010 --> 00:32:05,240
Ĉar vi ankoraŭ devas kontroli ĉiun solan fojon. >> Jes.

546
00:32:05,240 --> 00:32:08,060
Kaj vi devas interŝanĝi ilin. >> Kvankam ni homoj estas speco de ĉioscia

547
00:32:08,060 --> 00:32:10,770
en la senco vide ke ni povas nur ia vidi ke tiu estas ordo,

548
00:32:10,770 --> 00:32:12,140
komputilo ne estas tiu inteligenta.

549
00:32:12,140 --> 00:32:14,040
Ĝi tuj rigardi tie kaj tie kaj tie,

550
00:32:14,040 --> 00:32:16,610
sed se kio ĝi estas serĉi estas la plej malgranda ero,

551
00:32:16,610 --> 00:32:22,110
vi nur scias, ke vi trovis la plej malgranda ero de kiu punkto? Iam vi estas je la fino.

552
00:32:22,110 --> 00:32:25,880
Sed en tiu punkto vi nur trovis la nuntempe plej malgranda ero.

553
00:32:25,880 --> 00:32:28,810
Vi ne nepre scias ion ajn pri la stato de la mondo.

554
00:32:28,810 --> 00:32:30,880
Do vi devas iri denove kaj denove kaj denove.

555
00:32:30,880 --> 00:32:34,880
>> Do ĉi tiu tempo Mi vere aspektas muta ĉar mi kontrolas, bone, 2, vi estas la plej malgranda,

556
00:32:34,880 --> 00:32:37,530
sed mi ne scias, ke en tuta ankoraŭ.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Konsentite, bona. 2 estis ja la plej malgranda.

558
00:32:41,090 --> 00:32:43,150
Nun ni trovi la sekva pli malgranda. Okay.

559
00:32:43,150 --> 00:32:48,350
3, vi estas nuntempe la plej malgranda. Ni vidu. 4, 5, 6, 7, 8. Konsentite, atingis bonŝanca denove.

560
00:32:48,350 --> 00:32:53,170
3 estis ĝuste en la ĝusta loko. Sed mi iros por subteni fari ĉi denove kaj denove kaj denove.

561
00:32:53,170 --> 00:32:55,990
Kiel ni povas fari nur milde bona?

562
00:32:55,990 --> 00:33:00,120
Anstataŭ havi homojn bobelo supren duoplarĝa de malgranda al granda

563
00:33:00,120 --> 00:33:04,350
kaj anstataŭ iri tien kaj reen tra la listo elekti la tiam malgranda persono,

564
00:33:04,350 --> 00:33:09,780
kial ni ne anstataŭ enmeti tiujn homojn en nova listo paŝo post paŝo?

565
00:33:09,780 --> 00:33:13,080
Ni provu tion. Nun mi nomas tion inserción varon.

566
00:33:13,080 --> 00:33:17,250
Do jen ni estas ĉi tie. Numero 1. Mi ne zorgas pri iu ajn en cxi tiu listo.

567
00:33:17,250 --> 00:33:21,310
Mia celo nun estas meti numero 1 al la komenco de ordo listo.

568
00:33:21,310 --> 00:33:23,910
Kaj mi tuj proponi kiam mi nur havas 8 pecoj de memoro,

569
00:33:23,910 --> 00:33:28,670
arbitre nun mi estas la muron inter mia supozeble unsorted listo,

570
00:33:28,670 --> 00:33:32,740
kaj cxiu, kiu estas malantaŭ mi, mi iros al postuli estas ordo.

571
00:33:32,740 --> 00:33:34,680
Do nun ni havas numeron 1.

572
00:33:34,680 --> 00:33:39,240
Mi volas enmeti lin en mian ordo listo, do mi simple tuj movi mian muron super ĉi tie,

573
00:33:39,240 --> 00:33:43,930
kaj nun mi diras ĉi listo estas ordo, ĉi listo estas Unsorted - almenaŭ kiom mi scias.

574
00:33:43,930 --> 00:33:46,070
Mi ne povas vidi ĉiujn numerojn samtempe.

575
00:33:46,070 --> 00:33:49,000
>> Nun mi hazarde renkontas numero 2. Kion mi faros kun li?

576
00:33:49,000 --> 00:33:54,380
Mi enigi vin nun en la ordo listo. Sed rimarki kiom facila ol estis.

577
00:33:54,380 --> 00:33:59,650
Mi nur devas serĉi. Nombro 1 estas tie. Ho, evidente 2 iras al la flanko de la numero 1.

578
00:33:59,650 --> 00:34:03,700
Nun kion mi faru kun 3? Mi enigi vin en la ordo listo. Sed tio estis super facila.

579
00:34:03,700 --> 00:34:07,250
Ĉi tiu estas super facila, ĉi tiu estas super facila, ĉi tiu estas super facila, super facila, super facila.

580
00:34:07,250 --> 00:34:12,790
Kaj nun ĉio estas ordo malantaŭ mi, kaj kiom da paŝoj ne ke preni?

581
00:34:12,790 --> 00:34:15,620
[Studentoj] N. >> Do ĝi estas nur n. Ni atingis bonŝanca.

582
00:34:15,620 --> 00:34:18,860
Estis nur n kial? >> [Studento] Ĉar la listo estis ordo.

583
00:34:18,860 --> 00:34:21,630
La listo estas jam ordo. Do ni havas bonŝanca.

584
00:34:21,630 --> 00:34:25,639
Sed ni desegnis algoritmo tiu tempo arneses tian sorton,

585
00:34:25,639 --> 00:34:29,420
ke bona kazo scenaron, por ne malŝpari nenecesajn tempo.

586
00:34:29,420 --> 00:34:31,750
Do ni nun havas, kion ni vokos bobelo specoj

587
00:34:31,750 --> 00:34:33,949
kie homoj ia bobelo supren duoplarĝa.

588
00:34:33,949 --> 00:34:38,100
Ni nun havas elekton speco kie ni deŝiri el la plej malgranda persono denove kaj denove.

589
00:34:38,100 --> 00:34:42,350
Kaj nun ni havas inserción speco kie ni ia proactivamente metis personoj kie ili apartenas

590
00:34:42,350 --> 00:34:45,000
en ĉiufoje ordo listo.

591
00:34:45,000 --> 00:34:49,679
Se ni povus, ronda de aplaŭdoj por tiuj infanoj tie. [Aplaŭdo]

592
00:34:49,679 --> 00:34:52,310
Ni prenu nian 5-minuta paŭzo tie.

593
00:34:52,310 --> 00:34:55,139
Kaj kiam ni revenos, ni estos blovi ĉiuj tiuj algoritmoj el la akvo

594
00:34:55,139 --> 00:35:00,260
kun io pli bona. Bone. Grandan antaŭdankon. Vi povas konservi tiujn kiel memoraĵojn.

595
00:35:01,710 --> 00:35:04,330
Bone. Ni estas dorso.

596
00:35:04,330 --> 00:35:08,420
>> Kaj recap reala rapida, ni havis tiujn 3 malsamaj aliroj al ordigado,

597
00:35:08,420 --> 00:35:13,000
la tuta punkto de kiu devis alveni al la punkto kie iu kiel Alex

598
00:35:13,000 --> 00:35:16,930
povus sercxi listo de nombroj rapide ol iu kiel Sean povis.

599
00:35:16,930 --> 00:35:19,830
Kaj eĉ se ni havas tian simplaj ekzemploj kun 8 nombroj,

600
00:35:19,830 --> 00:35:24,000
vi povus extrapolar facile al 8 paĝoj, 8 miliardoj retpaĝojn,

601
00:35:24,000 --> 00:35:26,680
aŭ 800 milionoj de amikoj en Facebook.

602
00:35:26,680 --> 00:35:30,090
Do tiuj algoritmoj povas certe grimpi al tiuj specoj de valoroj,

603
00:35:30,090 --> 00:35:32,300
kaj la ideoj estas finfine la sama.

604
00:35:32,300 --> 00:35:36,140
Do bobelo varo estis la unua, kie ni ia bobelis ĝis la plej granda persono

605
00:35:36,140 --> 00:35:39,110
tuta vojo al la rajto de homoj interŝanĝi duoplarĝa.

606
00:35:39,110 --> 00:35:42,040
Tiam ni havis kion ni vokos selektado speco kie mi iom pli intence

607
00:35:42,040 --> 00:35:46,480
tenis rigardante tra la listo, elektu la plej malgranda nombro denove kaj denove kaj denove,

608
00:35:46,480 --> 00:35:49,530
la logika rezulto de kiu estas, ke la listo estas eventuale ordo.

609
00:35:49,530 --> 00:35:53,780
Tiam en la tria, mi insertos popolon en ilia taŭga loko,

610
00:35:53,780 --> 00:35:57,720
kaj ni faris tre elpensita ekzemplo en kiu la listo jam ordo,

611
00:35:57,720 --> 00:36:01,100
sed tio estis por sendi la mesaĝon, ke en inserción speco de kazo,

612
00:36:01,100 --> 00:36:02,670
vi povas akiri bonŝanca.

613
00:36:02,670 --> 00:36:07,930
Se la nombroj estas jam ordo, ĝi estas nur tuj prenos vin n paŝojn por konfirmi tiel,

614
00:36:07,930 --> 00:36:10,870
dum elekto speco vi estas iom pli tunelan vidmanieron

615
00:36:10,870 --> 00:36:14,360
kaj vi ne iam rimarkas ke la listo estas jam ordo.

616
00:36:14,360 --> 00:36:16,830
Do ni vidu bobelo varo en agado tie.

617
00:36:16,830 --> 00:36:19,590
En jena ekzemplo, ni baldaŭ vidos vertikalajn liniojn

618
00:36:19,590 --> 00:36:23,030
kies altecojn reprezentas numerojn tiel ke ni povas ordigi de bildigi ordigi okazos.

619
00:36:23,030 --> 00:36:26,630
La pli malgranda la trinkejo, la plej malgranda de la numero, la pli granda la trinkejo, la pli granda la nombro.

620
00:36:26,630 --> 00:36:28,860
>> Kaj ni ludos ĝin en ĉi defaŭlta rapido.

621
00:36:28,860 --> 00:36:33,460
Ĝi okazas movi iom rapida por nun, sed ruĝaj estas kio montrante 2 stangoj

622
00:36:33,460 --> 00:36:35,480
esti komparitaj apud la alia.

623
00:36:35,480 --> 00:36:39,520
Kaj se vi rigardas zorge, kio okazas estas ke se la stangoj estas el ordo,

624
00:36:39,520 --> 00:36:42,300
la plej malgranda unu gets movis al la maldekstra, la granda unu al la dekstra,

625
00:36:42,300 --> 00:36:44,360
kaj tiam vi observos antaŭis.

626
00:36:44,360 --> 00:36:48,520
Do, se ni tion denove kaj denove, rimarki ke la plej malgranda stangoj

627
00:36:48,520 --> 00:36:51,090
tuj observu inching sian vojon al la maldekstra

628
00:36:51,090 --> 00:36:54,130
kaj la plej granda stangoj tuj observu inching lia vojo al la rajto.

629
00:36:54,130 --> 00:36:58,490
Kaj efektive, ni komencas vidi mastro tuta vojo sur la dekstra flanko

630
00:36:58,490 --> 00:37:04,790
samkiel ni vidis 8 kaj tiam 7 eventuale bobelis ĝis la fino de nia homa listo.

631
00:37:04,790 --> 00:37:08,750
Do ĉi tiu tuj tre rapide akiri iom teda, do lasu min deteni ĉi momente.

632
00:37:08,750 --> 00:37:10,980
Lasu min ŝanĝi la rapido esti multe pli rapida.

633
00:37:10,980 --> 00:37:15,380
Mi ne ŝanĝas la algoritmo, mi nur fari la kuraĝigo okazi pli rapide.

634
00:37:15,380 --> 00:37:18,410
Ankoraŭ bobelo varo, sama algoritmo,

635
00:37:18,410 --> 00:37:21,910
sed nun vi povas vidi multe pli rapide ol nia parola pruvo

636
00:37:21,910 --> 00:37:25,900
ke la plej granda eroj estas ja bobelis ĝis la supro.

637
00:37:25,900 --> 00:37:29,860
>> Kiel flanken, tiuj malgranduloj kvadratoj ĉe la malsupro maldekstro kaj malsupro dekstra

638
00:37:29,860 --> 00:37:33,520
estas nur iom recordatorios pri kiom da komparoj vi faras.

639
00:37:33,520 --> 00:37:37,620
Sed nuntempe, ni povas enfokusigi la piramido ke tio prenas formon, kaj tie iras.

640
00:37:37,620 --> 00:37:41,510
La plej malgranda ero estas en la maldekstra, la plej granda en la dekstra, kaj ĉio alia inter ili.

641
00:37:41,510 --> 00:37:44,470
Nun ni anstataŭ rigardu selektado varon.

642
00:37:44,470 --> 00:37:47,260
Mi tuj iros antaŭen kaj batis Alta. Ni tuj akiri novajn hazarda aro de stangoj.

643
00:37:47,260 --> 00:37:50,930
Selektado varo, revokon, iras tra la listo denove kaj denove kaj denove,

644
00:37:50,930 --> 00:37:54,900
plukinte el la plej malgranda ero. Do jen estas elekto varon.

645
00:37:54,900 --> 00:37:58,390
Ŝajnas ke la malpli da laboro okazas nun ĉar ni ne komparas duoplarĝa

646
00:37:58,390 --> 00:38:02,590
sed ni nur ordigi de ĉerizo prenante la plej malgranda eroj de dekstre maldekstren.

647
00:38:02,590 --> 00:38:06,890
Kiu portis tre malmulta tempo, tiel ke estas dicotomía jam.

648
00:38:06,890 --> 00:38:11,820
Nur ĉar algoritmo estas dirita al preni n kvadrata tempo, kiel bobelo speco

649
00:38:11,820 --> 00:38:16,100
kaj kiel selektado varo, tiuj estas vere plej malbona kazo kurante foje.

650
00:38:16,100 --> 00:38:21,790
Ekzemple, en la kazo de, ni diru, selektado varo,

651
00:38:21,790 --> 00:38:27,240
Mi vere estas elekti la plej malgranda persono kaj metante lin aŭ ŝin tie,

652
00:38:27,240 --> 00:38:29,620
tiam mi faras ĝin denove, tiam mi faras ĝin denove,

653
00:38:29,620 --> 00:38:32,070
sed ne estis malpeza optimumigo mi povus fari.

654
00:38:32,070 --> 00:38:35,040
>> Kiam mi kopiis la numero 1 here - Sammy en tiu kazo -

655
00:38:35,040 --> 00:38:38,630
Kion mi devas fari kun li post tio? >> [Studento] Lasu lin.

656
00:38:38,630 --> 00:38:40,140
Lasu lin, ĉu ne? Nenio.

657
00:38:40,140 --> 00:38:44,310
Mi ne bezonas cxiam parolas al Sammy denove ĉar se mi selektis la plej malgranda ero

658
00:38:44,310 --> 00:38:48,580
kaj metis lin tie, kial malŝparo tempo iras al la fino de mia tuta listo?

659
00:38:48,580 --> 00:38:54,590
La sekvan ripeto lasu min reale movi nur al la numero 2, nur al la numero 3.

660
00:38:54,590 --> 00:38:57,640
Do fakte, mi ne faris n aĵoj n fojojn.

661
00:38:57,640 --> 00:39:05,380
Mi faris n aĵoj, tiam n - 1 aĵoj, tiam n - 2 aĵojn, tiam n - 3 aferojn,

662
00:39:05,380 --> 00:39:07,080
tiam n - 4, pentras, pentras, punkto.

663
00:39:07,080 --> 00:39:09,470
Ni havas iom de geometria serio, kiu ĵus signifas

664
00:39:09,470 --> 00:39:11,450
vi adicianta supren progresive pli malgrandaj nombroj.

665
00:39:11,450 --> 00:39:17,940
Ne n + n + n + n sed n + 7 + 6 + 5 + 4 + 3 + 2 + 1.

666
00:39:17,940 --> 00:39:21,380
Kaj kion tio ĝenerale funkcias esti -

667
00:39:21,380 --> 00:39:24,280
Mi tuj salaton ĉe mia tablo tie por momento -

668
00:39:24,280 --> 00:39:28,990
ke tuj labori esti io kiel n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
se ni nur speco de rigardo al la dorso de math libro, kie vi havas ĉiujn cheat folioj

670
00:39:31,930 --> 00:39:33,410
por la formuloj.

671
00:39:33,410 --> 00:39:37,760
Se vi ĝuste aldonante ion n + n - 1 + n - 2, ĝi funkcias esti io kiel tio.

672
00:39:37,760 --> 00:39:42,320
Kaj se ni nur speco de multipliki ĉi eksteren, ke tio n kvadrataj minus n / 2.

673
00:39:42,320 --> 00:39:46,400
Mi konservis dirante n kvadratoj, tamen, kaj tio estas ĉar mi estis speco de prenante mensa ligilo

674
00:39:46,400 --> 00:39:51,950
ĉar fakte, n kvadratoj minus n dividita per 2 estas ja la vera nombro de paŝoj

675
00:39:51,950 --> 00:39:55,510
ke algoritmo kiel selektado speco prenus, se ni vere rakontis ĝis

676
00:39:55,510 --> 00:39:58,800
ĉiuj el tiuj komparoj kaj ĉiuj de la eta okupita laboro ni faris.

677
00:39:58,800 --> 00:40:03,210
Sed sincere, fojo n alvenas al esti kiel milionoj aŭ miliardoj, kiujn la heck cares

678
00:40:03,210 --> 00:40:07,160
se vi faras miliardo kvadrato minus unu miliardo dividita per 2?

679
00:40:07,160 --> 00:40:09,320
Al miliardoj kvadrato estas grandega nombro.

680
00:40:09,320 --> 00:40:13,580
Vi povas preni alian miliardoj ekstere de ĝi kun - n. Ne tia granda interkonsento.

681
00:40:13,580 --> 00:40:18,770
Do la pli granda la nombro atingas, la malpli grava tiuj malaltaj ordigita terminoj estas.

682
00:40:18,770 --> 00:40:24,230
Kiu zorgas se vi dividos 2 se vi parolas pri quadrillions de nombroj de paŝoj?

683
00:40:24,230 --> 00:40:29,710
>> Do ĝenerale, komputilaj sciencistoj emas forĵeti ĉion krom la plej grandaj termino,

684
00:40:29,710 --> 00:40:33,140
kaj ni nur speco de simpligi la mondo kaj diri ke tiu algoritmo

685
00:40:33,140 --> 00:40:38,130
prenis proksimume n kvadrataj paŝoj. Tio estas la rula tempo de algoritmo.

686
00:40:38,130 --> 00:40:40,760
Do ni revenos al tio en nur momento kun iu konkretaj ekzemploj,

687
00:40:40,760 --> 00:40:45,940
sed por nun, jen speco de la intuicia motivado malantaŭ nur simplificadora nia mondo

688
00:40:45,940 --> 00:40:51,170
kaj parolante pri la plej gravaj terminoj anstataŭ akiri en ĉiujn tiujn fancy formuloj.

689
00:40:51,170 --> 00:40:53,540
Por ke estis elekto varo, kaj ni ricevis iom bonŝanca tie.

690
00:40:53,540 --> 00:40:57,360
Ni rigardu inserción varon. Lasu min kaj komenci ĉi tiu siavice.

691
00:40:57,360 --> 00:41:00,330
Nun rimarki la mastro kiu okazas estas iom malsamaj,

692
00:41:00,330 --> 00:41:03,410
kaj ni komencis kun hazardaj nombroj,

693
00:41:03,410 --> 00:41:06,890
sed se ni vere rakonti ĝis la nombro de paŝoj en la plej malbona kazo,

694
00:41:06,890 --> 00:41:11,070
se la listo komencis tute en la dekstran ordo,

695
00:41:11,070 --> 00:41:13,380
ni nur preni n paŝoj por realigi tiel.

696
00:41:13,380 --> 00:41:18,240
>> Sed se la listo estis vere malantaŭen - ekzemple, en ĉi tiu kazo tie -

697
00:41:18,240 --> 00:41:23,860
tiam rimarkos ni efektive devas fari multe pli laboron en ĉi tiu kazo.

698
00:41:23,860 --> 00:41:27,080
Kaj ĝi devus ia sentas vin kiel ĉi tiu estas speco de laboro malfacila

699
00:41:27,080 --> 00:41:30,900
akiri tiujn plej malgrandaj elementoj al la maldekstra, kaj tio estas ĉar ni ricevis malfeliĉa.

700
00:41:30,900 --> 00:41:34,210
La listo estis ordo hazarde en inversa.

701
00:41:34,210 --> 00:41:38,110
Kontraste, kun inserción speco se ni imitas kion ni faris kun niaj homoj tie

702
00:41:38,110 --> 00:41:42,670
per startanta kun ĉiuj ordo kaj poste komenci, estas sufiĉe bona algoritmo, ĉu ne?

703
00:41:42,670 --> 00:41:45,010
Oni jam, fakte, ordo.

704
00:41:45,010 --> 00:41:48,670
Do ni provu resumi ekzakte kiom da tempo tio prenas ni

705
00:41:48,670 --> 00:41:52,360
per prezentanta nur iom de slango aŭ skribmaniero, ke fakte multe pli simpla

706
00:41:52,360 --> 00:41:54,320
ol la fanciness ia sugestas.

707
00:41:54,320 --> 00:41:59,030
Tion ĉi tie, ĉi granda a sur la ekrano, estas kion komputilo sciencisto estos ĝenerale uzi

708
00:41:59,030 --> 00:42:03,640
por priskribi la plej malbona kazo rula tempo de algoritmo.

709
00:42:03,640 --> 00:42:07,360
>> Denove, por plej malbona kazo, ĝi estas tute kunteksto-dependa.

710
00:42:07,360 --> 00:42:10,890
Kion ni celas diri per plej malbona kazo tute varias bazita sur la problemo ni parolas.

711
00:42:10,890 --> 00:42:14,550
Sed en la kazo de ordigado, kio estas la plej malbona ebla scenaro?

712
00:42:14,550 --> 00:42:17,860
Ĉiu estas malantaŭen ĉar nur sentas ke signifas multon da laboro por ni.

713
00:42:17,860 --> 00:42:21,330
Mi skribis tuj kelkajn el la algoritmoj kiuj ni vidis ĝis nun:

714
00:42:21,330 --> 00:42:24,930
lineara serĉo, duuma serĉo kiel kun la telefono libro aŭ la pecoj de papero,

715
00:42:24,930 --> 00:42:28,960
tiam bobelo varo, selektado varo, kaj inserción varo kiel ni vidis per niaj homoj,

716
00:42:28,960 --> 00:42:31,770
kaj tiam 1 aliaj ke tio eventuale tuj nomos kunfandi varon.

717
00:42:31,770 --> 00:42:37,710
Do en lineara serĉo en la plej malbona kazo, kiom da paŝoj necesas por trovi la nombro 7

718
00:42:37,710 --> 00:42:40,690
se estas n pordoj kiel Sean alfrontis? >> [Studento] N.

719
00:42:40,690 --> 00:42:44,180
N. Do ni tuj skribos granda a de n.

720
00:42:44,180 --> 00:42:47,010
Mi nur tuj plenigi iuj spacoj. Tiu estas nur krado de spacoj.

721
00:42:47,010 --> 00:42:52,990
Sed en la plej bona kazo kun lineara serĉo, 7 povus esti ĉe la komenco de la listo,

722
00:42:52,990 --> 00:42:55,520
Kaj Estu eble komencis rigardi la komenco de la listo.

723
00:42:55,520 --> 00:42:58,940
Do se vi uzas lineara serĉo kaj ĝuste kontrolanta maldekstre dekstren aŭ eble dekstra al maldekstra -

724
00:42:58,940 --> 00:43:02,650
ili estas ekvivalentaj - en la plej bona kazo, kiom da ŝtupoj povus lineara serĉo,

725
00:43:02,650 --> 00:43:05,550
kiel Sean algoritmo, prenu? Nur 1 paŝo.

726
00:43:05,550 --> 00:43:09,450
>> Do mi intencis diri ke estas la omega skribmaniero.

727
00:43:09,450 --> 00:43:11,570
Tiu estas nur ĉefurbo omega.

728
00:43:11,570 --> 00:43:15,000
Omega estas nur la sexy maniero diri bona kazo rula tempo.

729
00:43:15,000 --> 00:43:18,900
Do, en la plej bona kazo la rula tempo estas sola paŝo aŭ konstanta nombro de paŝoj -

730
00:43:18,900 --> 00:43:24,270
1 en ĉi tiu kazo - sed en la plej malbona kazo, granda O, estas reale n paŝoj.

731
00:43:24,270 --> 00:43:28,110
Kaj ĉi tiu tie, theta, ni fakte ne tuj rigardi ĝuste nun.

732
00:43:28,110 --> 00:43:30,090
Ne konvenas al ĉi tiu aparta ekzemplo.

733
00:43:30,090 --> 00:43:31,990
Sed nun ni provu duuma serĉo.

734
00:43:31,990 --> 00:43:35,990
En la plej malbona kazo kun duuma serĉo, kiom da ŝtupoj oni ĝin tuj prenos por trovi la nombro 7

735
00:43:35,990 --> 00:43:38,340
aŭ kion ajn ni serĉas? >> [Studento] Log n.

736
00:43:38,340 --> 00:43:40,980
Ankoraŭ tuj prenos logo n ĉar ĝuste kiel Alex havas malfeliĉa

737
00:43:40,980 --> 00:43:44,030
kiam ni vere laboris tra la problemon metode

738
00:43:44,030 --> 00:43:48,220
kaj sxi ne trovis la numero 7 ĝis la lasta pordo ŝi rigardis,

739
00:43:48,220 --> 00:43:51,720
kvankam, en justeco, ŝi alvenis al forĵeti iujn pordojn survoje,

740
00:43:51,720 --> 00:43:56,920
duuma serĉo en la plej malbona kazo havas rula tempo de logo n.

741
00:43:56,920 --> 00:43:59,230
Kaj denove, kiu parolas al ĉi dividanta kaj konkerante.

742
00:43:59,230 --> 00:44:01,140
Sed kio pri la plej bona kazo?

743
00:44:01,140 --> 00:44:04,790
Kaj Alex efektive spertis ke plej bona kazo ĝuste kiam sxi venadis sur la scenejo.

744
00:44:04,790 --> 00:44:07,290
Kiom da ŝtupoj ne kiun portas en duuma serĉo? >> [Studento] 1.

745
00:44:07,290 --> 00:44:09,380
1, nur ĉar ŝi atingis bonŝanca.

746
00:44:09,380 --> 00:44:12,520
Sed tio estas bone ĉar omega referencas al pli bona kazo scenejoj,

747
00:44:12,520 --> 00:44:15,770
bona kazo enigoj, eĉ se estas nur hazarda muta sorton.

748
00:44:15,770 --> 00:44:18,900
>> Nun, ĉi tro ni iras al nur ia permeso vakua por nun.

749
00:44:18,900 --> 00:44:21,010
Kion pri nun bobelo speco?

750
00:44:21,010 --> 00:44:24,290
En la plej malbona kazo bobelo varo, ĉiuj estas en inversa ordo,

751
00:44:24,290 --> 00:44:26,380
do ni devas fari multajn bobelanta.

752
00:44:26,380 --> 00:44:30,190
Sed kiom da paŝoj estas ke tuj prenos en la plej malbona kazo? >> [Studento] N kvadrato.

753
00:44:30,190 --> 00:44:32,550
Ĉi tiu estis la n kvadratoj, ĉar se vi opinias pri tio,

754
00:44:32,550 --> 00:44:36,410
se la listo estas tute malantaŭen - 8 estas tie, 1 estas super tie -

755
00:44:36,410 --> 00:44:40,530
kiel afero komencas bobelo, la numero 8 estas tuj movi tiel, tiamaniere,

756
00:44:40,530 --> 00:44:44,540
tiamaniere, tiel, sed kie estas la nombro 7 en la plej malbona kazo?

757
00:44:44,540 --> 00:44:47,720
Jen ŝi estas ankoraŭ tie. Do ni devas fari tion denove kaj denove.

758
00:44:47,720 --> 00:44:53,190
Kaj tie estas kie ni preni n paŝoj, tiam n - 1 paŝoj, tiam n - 2 paŝoj.

759
00:44:53,190 --> 00:44:55,960
Kaj se vi prenos mian vorton por tio - ke se vi ia multigos gxin,

760
00:44:55,960 --> 00:45:00,110
ĝi estas proksimume n kvadrataj en la fino kun iuj aliaj terminoj kiuj ni simple ignori ĉar nun -

761
00:45:00,110 --> 00:45:06,890
tiam en la plej malbona kazo bobelo varo n kvadratoj, donu aŭ preni.

762
00:45:06,890 --> 00:45:09,490
Sed kio pri la plej bona kazo bobelo speco?

763
00:45:09,490 --> 00:45:13,050
Kio estas la plej bona kazo scenaro? Ĉiuj nombroj estas ordo jam.

764
00:45:13,050 --> 00:45:15,920
Kaj kio estis la heŭristiko mi uzis, la lertaĵon mi uzis,

765
00:45:15,920 --> 00:45:20,110
kompreni ke mi faris nenian laboron kaj povis do halti frue?

766
00:45:20,110 --> 00:45:23,590
[Studento] Kontrolu ĝin unufoje. >> Kontrolu ĝin unufoje. Sed kio mi faras laŭ la vojo?

767
00:45:23,590 --> 00:45:26,130
Mi estis konservanta trako de kiom svopoj mi faris.

768
00:45:26,130 --> 00:45:30,650
Kaj mi komprenis, se mi ne kalkulis ajna svopoj sur miaj fingroj, tiam mi faris nenian laboron.

769
00:45:30,650 --> 00:45:34,300
Mi certe ne devas provi fari nenian laboron denove, do mi povas simple ĉesas.

770
00:45:34,300 --> 00:45:37,830
>> Do, en la plej bona kazo de bobelo speco kiam la listo estas jam ordo,

771
00:45:37,830 --> 00:45:41,530
kion vi dirus la omega skribmaniero, la plej bona kazo rula tempo?

772
00:45:41,530 --> 00:45:48,040
Ĝi simple n. Ni devas fari iun laboron, sed ni nur devas vidi 1 promenadon la valoro de laboro.

773
00:45:48,040 --> 00:45:50,490
Kaj ankaux cxi tie mi foriros ĉi tiun parton malplena.

774
00:45:50,490 --> 00:45:52,430
Kaj nun selektado varon.

775
00:45:52,430 --> 00:45:56,010
Selektado speco estis mi plukinte la plej malgranda persono denove kaj denove.

776
00:45:56,010 --> 00:45:58,380
Kaj kion ni diras la rula tempo de tiu estis?

777
00:45:58,380 --> 00:46:00,590
Tio estis n akordita en la plej malbona kazo.

778
00:46:00,590 --> 00:46:05,220
Kaj bedaŭrinde, en la plej bona kazo ĝi estas ankaŭ n kvadratoj

779
00:46:05,220 --> 00:46:08,840
ĉar mi ne havas la varon de ĉioscia vido de la tuta mondo;

780
00:46:08,840 --> 00:46:13,140
Mi nur scias pri plena ripeto ke mi ja trovis la plej malgranda persono.

781
00:46:13,140 --> 00:46:15,860
Do selektado speco ia sucks en tiu senso,

782
00:46:15,860 --> 00:46:17,920
sed la kapo estas la speco de intuicia.

783
00:46:17,920 --> 00:46:21,470
Estas bela facile kodi supren ĉar ĉiuj vi devas fari estas skribi paron de nestitaj por cikloj,

784
00:46:21,470 --> 00:46:24,620
tipe, kiu iras tra serĉas la plej malgranda ero

785
00:46:24,620 --> 00:46:27,840
kaj poste metas la plej malgranda ero kie ĝi apartenas al la fino de la listo.

786
00:46:27,840 --> 00:46:29,900
Do ankaŭ ĉi tie okazas esti komerco-off.

787
00:46:29,900 --> 00:46:34,440
La kvanto de tempo prenas vin pensi kaj efektive disvolvi iun por skribi kodo

788
00:46:34,440 --> 00:46:39,460
povus tre bone preni pli da tempo, se vi volas pli bonan algoritmon kaj rapida agado.

789
00:46:39,460 --> 00:46:41,780
>> Sed se vi vere nur ia kodo ion ĝis rapida kaj malpura

790
00:46:41,780 --> 00:46:45,000
kaj ĝuste ia prenu la stupidest ebla ideo vi povas pensi,

791
00:46:45,000 --> 00:46:47,580
kiuj povus fari al vi kelkajn minutojn al kodo, sed kun grandaj datenaroj

792
00:46:47,580 --> 00:46:49,580
vian algoritmo povas preni horoj por kuri.

793
00:46:49,580 --> 00:46:51,690
Kaj eĉ mi en postdiploma lernejo foje fari tiujn komerco-offs.

794
00:46:51,690 --> 00:46:55,660
Estus 3am, mi provis analizi iuj tre grandaj aro de datumoj

795
00:46:55,660 --> 00:46:59,650
rilataj al la sekureco esplorado mi faris, kaj tio estis bone elspezi 5 minutoj

796
00:46:59,650 --> 00:47:03,210
tweaking mia programo por analizi la datumojn, kaj iru dormi

797
00:47:03,210 --> 00:47:08,420
aŭ elspezi 8 horoj atingi ĝin nur rajtas tiel kuras tuj kaj ne iri dormi.

798
00:47:08,420 --> 00:47:10,530
Kaj do tro estas speco de konscia decido.

799
00:47:10,530 --> 00:47:12,740
Malpli disvolviĝo tempo, pli dormo.

800
00:47:12,740 --> 00:47:14,780
Retrospektive mi probable ne devus kuraĝigi ke

801
00:47:14,780 --> 00:47:19,120
kiam la celo tie estas optimizar kvalito de la kodo,

802
00:47:19,120 --> 00:47:21,280
sed tio tro en la reala mondo estas tre racia komerco-off.

803
00:47:21,280 --> 00:47:25,130
Malpli da tempo, malpli agadon aŭ inverse.

804
00:47:25,130 --> 00:47:28,110
Do jen ni fine trovos eblecon por paroli pri theta.

805
00:47:28,110 --> 00:47:32,830
Theta skribmaniero estas io komputilo scienculoj povas venigi en konversacio

806
00:47:32,830 --> 00:47:36,160
kiam granda a kaj omega hazarde estas la sama.

807
00:47:36,160 --> 00:47:40,160
Vi diras theta por vere sendi la mesaĝon ke ĉi tio estas speco de strikta baro.

808
00:47:40,160 --> 00:47:43,340
Ne gravas ĉu la scenejo estas bona aŭ malbona, ĝi estas n kvadratoj.

809
00:47:43,340 --> 00:47:46,510
Do estas nur ne grava en tiuj historioj tie.

810
00:47:46,510 --> 00:47:48,560
Inserción varo estas la lasta ni rigardis,

811
00:47:48,560 --> 00:47:50,830
kie mi ĵus enmeto ĉiuj en la ĝustan lokon.

812
00:47:50,830 --> 00:47:54,930
En la plej bona kazo kio estis la rula tempo de inserción varo kiel ni vidis tie?

813
00:47:54,930 --> 00:47:57,250
[Studento] La plej bona kazo? >> La plej bona kazo.

814
00:47:57,250 --> 00:48:00,100
>> Estis n ĉar en la plej bona kazo ĉiuj ordo,

815
00:48:00,100 --> 00:48:02,580
kaj Sammy kaj neniu alia vere devis movi ajn.

816
00:48:02,580 --> 00:48:04,610
Ili estis jam en siaj ĝusta loko.

817
00:48:04,610 --> 00:48:08,570
Do inserción varo en la plej bona okazo estas, en ĉi tiu kazo, n.

818
00:48:08,570 --> 00:48:12,770
Sed en la plej malbona kazo estas speco de n kvadratoj. Kial?

819
00:48:12,770 --> 00:48:16,230
Se mia listo de homoj estas en inversa ordo,

820
00:48:16,230 --> 00:48:21,260
Mi unue komencu per la nombro 8 kaj Mi enigi lin aŭ ŝin en la dekstra pozicio, kio estas korekta ĉi tie.

821
00:48:21,260 --> 00:48:25,270
Mi ia movado al la flanko. Tiuj infanoj estas Unsorted, li aŭ ŝi estas ordo.

822
00:48:25,270 --> 00:48:28,970
Sed nun mi hazarde trovos kiuj poste? >> [Studento] 7.

823
00:48:28,970 --> 00:48:31,250
7 en la plej malbona kazo ĉar ĝi estas en inversa ordo.

824
00:48:31,250 --> 00:48:34,920
>> Do jen estas 7. Kie 7 apartenas? Definitive malantaŭ mi.

825
00:48:34,920 --> 00:48:39,460
Sed nun 7 fakte apartenas ne tuj malantaŭ mi, sed malantaŭ la numero 8,

826
00:48:39,460 --> 00:48:41,880
do mi devas diri, "Pardonu min, numero 8, vi povas bv movi ĉi vojo

827
00:48:41,880 --> 00:48:44,640
"Fari spacon por 7?" Nun mi renkontas 6.

828
00:48:44,640 --> 00:48:48,530
"Ho, pardonu min, numero 8 kaj numero 7, vi povas movi por fari lokon al 6?"

829
00:48:48,530 --> 00:48:52,360
Do alivorte, kun inserción varo, kvankam mi ne faras multe movado,

830
00:48:52,360 --> 00:48:56,330
la homo malantaŭ mi faras multe pli da laboro, kaj tio alvenis al kostis iu tempo.

831
00:48:56,330 --> 00:48:58,000
Ĝi tuj kostis la komputila tempo.

832
00:48:58,000 --> 00:49:01,450
Do, en la kazo de inserción speco ni ankoraŭ suferas.

833
00:49:01,450 --> 00:49:06,260
Se oni komencas aldoni ĝis la tuta nombro de paŝoj, ni finos bati krude n kvadratoj

834
00:49:06,260 --> 00:49:11,160
ĉar ĉi tiuj infanoj bezonas fari lokon por la homa esti insertos denove en tiu listo.

835
00:49:11,160 --> 00:49:15,960
Kaj tiel en tiu ĉi kazo theta estas simple ne aplikeblas al la aparta rakonto proksima.

836
00:49:15,960 --> 00:49:21,100
Tio estas ĉio bela kaj bona. Ni havas tiuj 3 malsamaj manieroj paroli pri la rula tempo.

837
00:49:21,100 --> 00:49:26,370
Sed kion signifas ĉi reale signifas en reala terminoj se oni vere provas kodi supren algoritmon?

838
00:49:26,370 --> 00:49:31,620
>> Lasu min proponi ke ekzistas eĉ pli bona algoritmo tie

839
00:49:31,620 --> 00:49:33,740
ke mem havas iujn komercajn-offs.

840
00:49:33,740 --> 00:49:36,890
Ni tuj nomas ĝin kunfandi varo, kaj ĝi estas speco de ĉi tiu magia algoritmo

841
00:49:36,890 --> 00:49:42,840
ke ĝuste funkcias pli rapide iel, kaj estas tiel facile esprimi, almenaŭ en _pseudocode_.

842
00:49:42,840 --> 00:49:46,900
La efektivigo de ĉi tiu algoritmo merge speco tuj estos kiel sekvas.

843
00:49:46,900 --> 00:49:50,860
Kiam vi donita n elementoj - n nombroj, n homoj, kia ajn - unua tie estas prudento ĉeko.

844
00:49:50,860 --> 00:49:56,340
Se n estas malpli ol 2, kunfandi speco nur haltas. Denove, por tiel diri.

845
00:49:56,340 --> 00:50:00,830
Kial vi haltas se n estas malpli ol 2? >> [Inaudible studento respondon]

846
00:50:00,830 --> 00:50:04,480
Ĝuste. Kaj denove, n estas ne la nombro en la listo, n estas la grandeco de la listo.

847
00:50:04,480 --> 00:50:07,660
Se n estas malpli ol 2, kiu signifas via lerta estas ĉu 1,

848
00:50:07,660 --> 00:50:09,640
kie vi evidente ordo se estas 1 numeron,

849
00:50:09,640 --> 00:50:11,710
aŭ 0, en kiu kazo ne estas nenio por ordigi,

850
00:50:11,710 --> 00:50:13,570
do ni bezonas tiun specon de bazo kazo.

851
00:50:13,570 --> 00:50:20,350
Se la listo estas tiom mallonga, ke estas nur nenio por fari, laŭvorte ne faras nenion. Reveni.

852
00:50:20,350 --> 00:50:25,090
Alie ordigi la maldekstra duono de la eroj, tiam ordigi la dekstra duono de la elementoj,

853
00:50:25,090 --> 00:50:27,410
tiam kunfandi la 2 ordo duonoj.

854
00:50:27,410 --> 00:50:32,130
>> Ĉi tiu speco de similas iom cheat per mi petas al vi kiel ordigi elementoj

855
00:50:32,130 --> 00:50:34,900
kaj vi diras al mi, "ordigi la maldekstra duono, ordigi la dekstra duono."

856
00:50:34,900 --> 00:50:37,240
Mi estas kiel, "Bone. Kiel vi ordigi la maldekstra duono?"

857
00:50:37,240 --> 00:50:40,670
"Ordigu la maldekstra duono de la maldekstra duono, ordigi la dekstra duono de la maldekstra duono, kaj tiam faris."

858
00:50:40,670 --> 00:50:44,060
Vi estas speco de cikle difini kion signifas ordigi,

859
00:50:44,060 --> 00:50:46,790
sed ĝi rezultas ke fakte brila en ĉi tiu kazo.

860
00:50:46,790 --> 00:50:50,230
Ne vere ĉi vicioso kiu neniam finas

861
00:50:50,230 --> 00:50:52,550
ĉar ĝi finos kiam? >> [Studento] Kiam vi atingos 1 afero.

862
00:50:52,550 --> 00:50:54,220
Kiam vi atingos 1 afero.

863
00:50:54,220 --> 00:50:57,850
Do eĉ se vi povus komenci kun 8 personoj kaj mi diras, "ordigi la maldekstra duono de tiuj homoj,

864
00:50:57,850 --> 00:51:00,480
tiuj 4 personoj, "tiam mi diras," Kiel vi ordigi la maldekstra duono? "

865
00:51:00,480 --> 00:51:03,450
"Nu, ordigi la 2 personoj ĉi tie." Kaj tiam vi estas kiel, "Bone, bone."

866
00:51:03,450 --> 00:51:05,520
"Kiel vi ordigi la maldekstra duono de tiuj homoj?"

867
00:51:05,520 --> 00:51:09,040
"Nur ordigi ĉi 1 persono ĉi tie." Kio estas la brila revelacio nun?

868
00:51:09,040 --> 00:51:13,050
Mi devas ordigi 1 persono. Faris. Mi ne devas fari ian laboron.

869
00:51:13,050 --> 00:51:16,580
Sed nun mi devas ordigi tiun personon, sed ili estas fraŭlo, nenio farinda.

870
00:51:16,580 --> 00:51:21,490
>> Do la magio ŝajne estas en ĉi tiu tria paŝo: kunfandi la ordo duonoj.

871
00:51:21,490 --> 00:51:25,770
Do kunfandi speco prenas ĉi brila kompreno, ke se vi rompas granda problemo malsupren

872
00:51:25,770 --> 00:51:28,650
en 2 pli malgranda, idente grandeco problemoj

873
00:51:28,650 --> 00:51:32,710
kaj tiam nur speco de gluo la plej malgranda solvoj kune je la fino,

874
00:51:32,710 --> 00:51:34,720
Mi proponas ke ni povas fari multe, multe pli bone [frapetante sono]

875
00:51:34,720 --> 00:51:38,050
ol la elekto varo aŭ inserción varon.

876
00:51:38,050 --> 00:51:40,690
Mi vere estis ignorante ke por duonhoro, sed mi vere ne scias kio okazas

877
00:51:40,690 --> 00:51:45,040
ekstere hodiaŭ. [Zumantaj sono] [ridado]

878
00:51:45,040 --> 00:51:49,660
Do ni vidu se ni povas vidi ĉi tion kun iom helpo de nia amiko Rob Bowden.

879
00:51:49,660 --> 00:51:52,810
Estas 2 grandaj paŝoj en la procezo de merge varon.

880
00:51:52,810 --> 00:51:56,400
Unue, senĉese fendi la listo de tasojn en duonoj

881
00:51:56,400 --> 00:51:59,610
gxis ni havas amason da listoj kun nur 1 taso en ili.

882
00:51:59,610 --> 00:52:02,150
Ne maltrankviliĝu, se listo enhavas nepara nombro

883
00:52:02,150 --> 00:52:04,830
kaj vi ne povas fari perfekte pura kortego inter ili.

884
00:52:04,830 --> 00:52:08,740
Nur arbitre elekti kio listo por inkludi la ekstra tason in

885
00:52:08,740 --> 00:52:11,320
Do ni fendi tiuj listoj.

886
00:52:12,420 --> 00:52:14,570
Nun ni havas 2 listojn.

887
00:52:18,930 --> 00:52:20,930
Nun ni havas 4 listoj.

888
00:52:25,730 --> 00:52:28,740
Nun ni havas 8 lertaj kun sola tason en ĉiu listo.

889
00:52:28,740 --> 00:52:31,520
Do jen ĝi por paŝo 1.

890
00:52:31,520 --> 00:52:37,280
Por paŝo 2 ni ree kunfandi paroj de lertaj uzanta la merge algoritmo ni lernis antaŭe.

891
00:52:37,280 --> 00:52:44,320
Kunfandi 108 kaj 15 ni finos kun la listo 15, 108.

892
00:52:45,240 --> 00:52:51,330
Kunfandi 50 kaj 4 ni finos kun 4, 50.

893
00:52:51,330 --> 00:52:56,950
Kunfandi 8 kaj 42 ni finos kun 8, 42.

894
00:52:57,790 --> 00:53:04,360
Kaj kunfandi 23 kaj 16 ni finos kun 16, 23.

895
00:53:04,360 --> 00:53:08,030
Nun ĉiuj niaj listoj estas de amplekso 2.

896
00:53:08,030 --> 00:53:10,980
Rimarki, ke ĉiu el la 4 listoj estas ordigitaj,

897
00:53:10,980 --> 00:53:14,230
do ni povas komenci kunfandi paroj de lertaj denove.

898
00:53:14,230 --> 00:53:22,150
Kunfandi 15 kaj 108 kaj 4 kaj 50 ni unue prenas la 4, tiam la 15-

899
00:53:22,150 --> 00:53:26,250
tiam la 50, tiam la 108.

900
00:53:26,250 --> 00:53:33,020
Kunfandi 8, 42 kaj 16, 23 ni unue prenas la 8, tiam la 16-

901
00:53:33,020 --> 00:53:37,170
tiam la 23, tiam la 42.

902
00:53:37,170 --> 00:53:42,490
Do nun ni havas nur 2 listojn de grandeco 4, ĉiu el kiuj estas ordo.

903
00:53:42,490 --> 00:53:45,940
Do nun ni kunfandi tiuj 2 listojn.

904
00:53:45,940 --> 00:53:54,230
Unue ni prenas la 4, tiam ni prenos la 8, tiam ni prenos la 15

905
00:53:54,230 --> 00:54:05,280
kaj 16 kaj 23 kaj 42 kaj 50 kaj 108.

906
00:54:05,280 --> 00:54:09,020
Kaj ni faris. Ni nun havas ordo listo.

907
00:54:09,020 --> 00:54:13,740
>> Rob estis speco de utiligante iu kiun ni ankoraŭ ne faris.

908
00:54:13,740 --> 00:54:16,540
Oni sugestis, sed ni ne vere faras.

909
00:54:16,540 --> 00:54:19,230
Li faras ion fizike kun la tasojn sugestante

910
00:54:19,230 --> 00:54:23,680
li pasigis kelkajn rimedo krom tempo. >> [Studento] Spaco. >> Estis spaco.

911
00:54:23,680 --> 00:54:27,360
La fakto ke li havis tiun specon de bi-nivelo tablo kie li havis spacon ĉi tien

912
00:54:27,360 --> 00:54:31,960
kaj spaco cxi tie estis efektive implicante ke li uzas duoble pli da spaco

913
00:54:31,960 --> 00:54:36,390
kiel iu el niaj algoritmoj ĝis nun - inserción varo, bobelo varo, aŭ selektado speco -

914
00:54:36,390 --> 00:54:40,780
sed li utiligante tiun plian spacon al ia movado aĵoj tien kaj reen

915
00:54:40,780 --> 00:54:42,600
konservante aĵojn en ordo.

916
00:54:42,600 --> 00:54:47,540
Kaj eĉ se li sentas kiel ni poste ricevis al ordo listo, kiun sentis ĝin prenis iom da tempo.

917
00:54:47,540 --> 00:54:51,060
En realo, kion Rob faris estis ĝuste tiu algoritmo.

918
00:54:51,060 --> 00:54:56,780
Li unue prenis la problemon de amplekso n, dividita ĝin en maldekstra duono kaj dekstra duono.

919
00:54:56,780 --> 00:54:59,380
Tio estas, kiam li movis la tasoj. Tiam li ripetis tiun procezon.

920
00:54:59,380 --> 00:55:03,390
Li dividis 4 en 2 aroj de 2 pli tie kaj ĉi tie.

921
00:55:03,390 --> 00:55:08,520
Tiam li ripetis tiun procezon kaj dividita 2 en 2 aroj de 1 por ĉiu el tiuj diversaj tasoj.

922
00:55:08,520 --> 00:55:11,000
Kaj tie estas kie la brila ŝancon ekestas.

923
00:55:11,000 --> 00:55:15,840
En tiu punkto en la historio, Rob havis 8 listoj de grandeco 1,

924
00:55:15,840 --> 00:55:18,860
ĉiuj kiuj estis ordo jam.

925
00:55:18,860 --> 00:55:20,630
>> Tial kion li procedi fari?

926
00:55:20,630 --> 00:55:25,260
Duoplarĝa li prenis tiun ordo listo kaj tiu ordo listo kaj kunfandis ilin.

927
00:55:25,260 --> 00:55:28,200
Tiam li prenis ĉi tiu kaj kunfandis ilin, tiam ĉi tiu kaj kunfandis ilin,

928
00:55:28,200 --> 00:55:30,670
tiam ĉi tiu kaj kunfandis ilin.

929
00:55:30,670 --> 00:55:32,390
Kaj tiam kion li faros?

930
00:55:32,390 --> 00:55:36,580
Li tiam re-kuniĝis la granda lertaj kaj tiam re-kuniĝis la granda listoj.

931
00:55:36,580 --> 00:55:41,170
Kaj se vi pensas pri ĉi tiu nur intuicie por nun, kio li vere faras?

932
00:55:41,170 --> 00:55:45,450
Li dividis la problemo en duono, meze, meze, meze

933
00:55:45,450 --> 00:55:47,600
por atingi tiujn super malgrandaj listoj.

934
00:55:47,600 --> 00:55:51,290
Tiam li estis ia kombinante duobla, duopa, duobla, double.

935
00:55:51,290 --> 00:55:54,120
Do li faris duoble da laboro kiel ni vidis ĝis nun

936
00:55:54,120 --> 00:55:56,930
kun nenio engaĝante dividu kaj regu, sed neniu granda interkonsento.

937
00:55:56,930 --> 00:55:59,630
Duoble da laboro ne estas tiom granda interkonsento. Estas nur konstanta faktoro.

938
00:55:59,630 --> 00:56:03,920
Kaj kiel niaj aritmetiko esprimo antaŭe, mi nur tuj transiri el konstantaj faktoroj

939
00:56:03,920 --> 00:56:10,170
kiel fojojn 2. Kiu zorgas? Se ĝi estas 2 miliardoj fojoj 2, kiu estas ankoraŭ multe da ŝtupoj.

940
00:56:10,170 --> 00:56:13,160
Do ĉi kunfandi paŝo ŝajnas esti la ŝlosilo _insight_.

941
00:56:13,160 --> 00:56:17,000
Ni marŝas tra ĉi nur numere antaŭe - Ho, tio ne daŭrigi ankoraŭ.

942
00:56:17,000 --> 00:56:22,890
Ni marŝas tra ĉi numere nur por efektive vidi kiel ĉi ludas ekstere.

943
00:56:22,890 --> 00:56:25,940
Tio estas plejparte nur iom malriĉa viro kuraĝigo.

944
00:56:25,940 --> 00:56:27,750
Ni proponas tion.

945
00:56:27,750 --> 00:56:31,480
La rula tempo de merge speco - ni nur bezonas manieron paroli pri tio.

946
00:56:31,480 --> 00:56:34,380
Tio ne estas matematika; ĉi estas nur speco de konciza maniero de esprimi nin.

947
00:56:34,380 --> 00:56:39,080
Do T prezentas tempon kaj n reprezentas kio? >> [Studento] La grandeco de la -

948
00:56:39,080 --> 00:56:41,400
>> [Malan] La grandeco de la problemo, la nombro da personoj.

949
00:56:41,400 --> 00:56:45,470
Do mi asertas ke la rula tempo por ordigi n personojn tuj esti 0 kvanto de tempo

950
00:56:45,470 --> 00:56:50,290
se n estas malpli ol 2, ĉar se vi havas 1 taso aŭ neniu tasojn, vi havas nenion por ordigi.

951
00:56:50,290 --> 00:56:55,160
Sed pli ĝenerale, mi tuj proponi ke la rula tempo por ordigi n eroj

952
00:56:55,160 --> 00:56:59,350
tuj estos la tempo necesa por ordigi la maldekstra duono plus la dekstra duono

953
00:56:59,350 --> 00:57:03,110
plus - kio estas tio plian + n? >> [Studento] Merge varon.

954
00:57:03,110 --> 00:57:07,260
[Malan] Oni efektive kunfandi, ĉar se vi havas n / 2 eroj ĉi tie

955
00:57:07,260 --> 00:57:11,500
kaj vi havas n / 2 eroj ĉi tie, kiom da tempo estas bezonata por kunfandi ilin?

956
00:57:11,500 --> 00:57:15,050
Ĝuste kiel Rob, vi devas deŝiri ĉi tiu super ĉi tie, eble deŝiri super ĉi tie,

957
00:57:15,050 --> 00:57:17,120
deŝiri super tie, elsxiru super tie, elsxiru super tie.

958
00:57:17,120 --> 00:57:19,400
Vi devas tuŝi ĉiu el la tasoj unufoje.

959
00:57:19,400 --> 00:57:22,030
Kaj se estas 4 tasojn plus 4 tasoj, jen 8 tasojn

960
00:57:22,030 --> 00:57:25,200
aŭ, pli ĝenerale, 8 n tasoj.

961
00:57:25,200 --> 00:57:28,470
Do la fandado paŝo ni povas esprimi kiel n,

962
00:57:28,470 --> 00:57:31,330
kaj kiu laŭvorte engaĝas la nombro da fojoj Rob fizike tuŝis

963
00:57:31,330 --> 00:57:33,410
unu el tiuj Styrofoam tasoj.

964
00:57:33,410 --> 00:57:35,850
Do ni nun faru arbitra ekzemplo.

965
00:57:35,850 --> 00:57:41,850
Se tie estas 16 tasojn, kio estas la rula tempo de ordigi, uzante Rob algoritmo, 16 tasojn?

966
00:57:41,850 --> 00:57:44,710
Estas 2 fojoj la kvanto de tempo necesa por ordigi 8 tasojn

967
00:57:44,710 --> 00:57:46,920
ĉar ni havas 8 tasojn tie, 8 tasojn tie.

968
00:57:46,920 --> 00:57:51,520
Mi ne scias kiom longe tiu prenas, do ni komunigante ĝin kiel T por la momento.

969
00:57:51,520 --> 00:57:53,320
Kiu scias kio ĝi estas?

970
00:57:53,320 --> 00:57:58,990
Sed nun mi povas ordigi de rekursie aŭ ree demandi al la sama demando.

971
00:57:58,990 --> 00:58:01,920
Kiom da tempo estas bezonata por ordigi 8 tasojn?

972
00:58:01,920 --> 00:58:07,030
8 tasojn Mi intencis diri prenas la kvanton de tempo necesa por ordigi 4 tasojn plus 4 tasojn,

973
00:58:07,030 --> 00:58:08,880
tiam kunfandi ilin kune.

974
00:58:08,880 --> 00:58:13,080
Fajna. Ni nun estas en ciklo jam. Kiom da tempo necesas por ordigi 4 tasojn?

975
00:58:13,080 --> 00:58:19,150
La tempo necesa por ordigi 4 tasoj estas 2 tasojn plus 2 tasoj ordigi pli la fandado procezo.

976
00:58:19,150 --> 00:58:21,440
Fajna. Kiom da tempo necesas por ordigi 2 tasojn?

977
00:58:21,440 --> 00:58:26,290
2 tasoj estas la kvanto de tempo necesa por ordigi 1 taso plus la tempo necesa por ordigi alian tason

978
00:58:26,290 --> 00:58:29,040
plus la kvanto de tempo necesa por kunfandi, kiu estas nur 2.

979
00:58:29,040 --> 00:58:33,340
>> Fajna. Lasta demando. Kiom da tempo necesas por ordigi 1 taso?

980
00:58:33,340 --> 00:58:37,260
Jen estas la bazo kazo ke ni antaŭdiris ni volas bati antaŭe.

981
00:58:37,260 --> 00:58:42,250
La fakto ke ĝi prenas ne laboro ajn ordigi la plej malgranda el la problemoj

982
00:58:42,250 --> 00:58:44,120
signifas ke nun, ia grado lernejo stilo,

983
00:58:44,120 --> 00:58:46,460
ni povas simple iru komenci ŝtopanta tiuj nombroj reen in

984
00:58:46,460 --> 00:58:50,630
Ni nun scias, kion T de 1 estas, do mi povas ŝtopi en 0 por T de 1.

985
00:58:50,630 --> 00:58:54,420
Kiu donos al mi la respondon al T de 2, kiun mi tiam povas ŝtopi en pli supren.

986
00:58:54,420 --> 00:58:56,930
Kiu donos al mi T de 4, kiun mi povas ŝtopi en pli supren.

987
00:58:56,930 --> 00:58:58,920
Kiu donos al mi T de 8, kiun mi povas ŝtopi en pli supren.

988
00:58:58,920 --> 00:59:04,330
Kaj se mi efektive faros ke math ŝtopanta en tiuj respondoj,

989
00:59:04,330 --> 00:59:08,590
Mi poste atingi T de 16 estas 64.

990
00:59:08,590 --> 00:59:12,090
Kaj kion tio 64 reprezenti?

991
00:59:12,090 --> 00:59:15,700
Se T estas la 16, yeah, estas 16 fojoj 4.

992
00:59:15,700 --> 00:59:20,120
Do mi diras nun ke la rula tempo de ĉi tiu afero nomata kunfandi speco -

993
00:59:20,120 --> 00:59:22,590
kaj ĉi tiu tuj estos la fanciest de tiuj ni vidis ĝis nun -

994
00:59:22,590 --> 00:59:26,160
tuj estos nomata n logo n

995
00:59:26,160 --> 00:59:31,140
ĉar kiom da fojoj povas Rob fendi tuta amaso de tasojn en duono? Ensalutu n.

996
00:59:31,140 --> 00:59:34,370
Ĝi estas la sama kiel la telefono libro ekzemple, estas la sama kiel la aŭto-kalkula ekzemplo.

997
00:59:34,370 --> 00:59:36,380
>> Kiom da fojoj vi povas dividi ion en duono?

998
00:59:36,380 --> 00:59:38,410
Tamen, estas tio kunfandi paŝo.

999
00:59:38,410 --> 00:59:42,920
Vi eble devas dividi la tasoj en duono denove kaj denove kaj denove,

1000
00:59:42,920 --> 00:59:45,640
sed ĉiufoje kiam vi iras al devas mem kunfandi.

1001
00:59:45,640 --> 00:59:48,270
Kaj ni diris antaŭe ke kunfandi n tasojn prenas n paŝoj

1002
00:59:48,270 --> 00:59:52,060
ĉar vi devas deŝiri el taso, elsxiru el taso, kaj vi devas tuŝi ĉiun pokalon fojo,

1003
00:59:52,060 --> 00:59:53,510
nur kiel Rob faris.

1004
00:59:53,510 --> 00:59:59,430
Do, se ni faras ion log n fojoj kaj ni faras n aĵoj sur ĉiu el tiuj iteraciones,

1005
00:59:59,430 --> 01:00:03,090
ĉiu el tiuj halvings, ni havas n fojoj logo n.

1006
01:00:03,090 --> 01:00:07,220
Do, se ni konektas en 16 en ĉi tiu ekzemplo, 16 fojojn ensaluti de 16 -

1007
01:00:07,220 --> 01:00:10,600
Ne zorgu pri tio ĉi estas la kazo por nun ĉar mi ne desegnis la bazo -

1008
01:00:10,600 --> 01:00:16,100
sed log'o da bazo 2 de 16 estas 4, 16 fojojn 4 estas 64.

1009
01:00:16,100 --> 01:00:22,350
Sed kontraste, se ni uzas bobelo varo aŭ selektado varo aŭ inserción speco kun 16 ciferoj,

1010
01:00:22,350 --> 01:00:26,420
kio estus la rula tempo estis se n estas 16?

1011
01:00:26,420 --> 01:00:33,310
Estus 16 kvadratoj, kiu estas 256, kiuj eĉ se vi ne sufiĉe sekvis la tutan matematikon,

1012
01:00:33,310 --> 01:00:38,390
256 estas pli granda ol 64. Tio estas vere la magia takeaway tie.

1013
01:00:38,390 --> 01:00:41,990
Kaj rimarki ke laborante tra tiu en plej malgrandaj ekzemploj kiel vi deziras en pset

1014
01:00:41,990 --> 01:00:44,260
faras ĉion multe pli intuicia.

1015
01:00:44,260 --> 01:00:49,070
Sed kion tio vere signifas en terminoj de la sento de ĉi tiu algoritmo estas la jena:

1016
01:00:49,070 --> 01:00:54,520
Se ni vere rigardas merge speco tie - lasu min eltiri ĝin en tiu ĉi fenestro tie -

1017
01:00:54,520 --> 01:00:58,560
ĉi tiu estas iomete malsamaj ekzemple per kiu ni devas ĉiuj 3 de tiuj algoritmoj -

1018
01:00:58,560 --> 01:01:01,440
bobelo, selektado, kaj kunfandi - ĝuste apud la alia.

1019
01:01:01,440 --> 01:01:03,740
>> Ili ĉiuj komencis kun hazarda trinkejoj, kaj tio estas bona.

1020
01:01:03,740 --> 01:01:06,240
Neniu havas fundamentan avantaĝon super la aliaj.

1021
01:01:06,240 --> 01:01:09,500
Mi tuj post momento klaki ĉiu el tiuj kuraĝigoj - Komenci, Komencu, Komencu -

1022
01:01:09,500 --> 01:01:13,270
tiel rapide kiel mi povas tiel ke, krude, ili ĉiuj komenco samtempe,

1023
01:01:13,270 --> 01:01:17,450
kaj ni konsideras ke bobelo speco de malbona kazo rula tempo estas kio? >> [Studento] N kvadrato.

1024
01:01:17,450 --> 01:01:21,560
N akordita. Selektado speco plej malbona kazo rultempo estas? N akordita.

1025
01:01:21,560 --> 01:01:25,150
Kaj merge varo estas ŝajne - eĉ se vi ne sufiĉe sekvi ĉiujn math nun,

1026
01:01:25,150 --> 01:01:30,610
ĝi devos esti multe pli intuicia tra tempo - estas, ni asertas, n fojoj logo n.

1027
01:01:30,610 --> 01:01:35,210
Kaj ĉar log n estas severe malpli ol n iam ni havas grandajn numerojn,

1028
01:01:35,210 --> 01:01:40,230
n fojoj logo n estas pli malgranda ol n × n aŭ n kvadratoj.

1029
01:01:40,230 --> 01:01:44,410
Do kion oni sentas reale esti pli bona algoritmo en terminoj de rula tempo,

1030
01:01:44,410 --> 01:01:50,380
n fojoj logo n kontraste al n kvadratoj? Ĉi tie ni iru. Klaku, klaku, klako.

1031
01:01:55,690 --> 01:01:58,650
>> Tion signifas uzi iun kiel merge varon.

1032
01:01:58,650 --> 01:02:01,680
Ni havas momenton. Ni vidu kio okazas tie.

1033
01:02:09,440 --> 01:02:12,440
[Chuckles] Kies mono estas ĉe bobelo speco?

1034
01:02:14,960 --> 01:02:16,730
Ĝi prefere dependas de la enigo kelkfoje.

1035
01:02:16,730 --> 01:02:18,120
Ni vidu.

1036
01:02:18,120 --> 01:02:23,320
Venu. Sentas li reatingas. >> [Studento] Iru, bobelo speco!

1037
01:02:23,320 --> 01:02:27,370
[Studentoj murmurado]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Jes, jes.

1039
01:02:29,120 --> 01:02:34,520
[Studentoj murmurado] Iru, iru, iru!

1040
01:02:37,210 --> 01:02:40,450
[Ĉiuj huraado] [aplaŭdo]

1041
01:02:40,450 --> 01:02:46,240
Do nun kun 1 lasta, fina demo, se estas iom malfacila por kovri vian menson ĉirkaŭ la matematiko

1042
01:02:46,240 --> 01:02:49,280
aŭ speco de la videbligo tie, vi povas efektive aŭdi la rapidoj

1043
01:02:49,280 --> 01:02:51,000
de malsamaj algoritmoj malsame.

1044
01:02:51,000 --> 01:02:53,900
Ĉi tiu estas kuraĝigo iu faris ke en la praktiko asociitaj sonas

1045
01:02:53,900 --> 01:02:56,980
kun la procezo de interŝanĝante kaj la alteco de la stangoj.

1046
01:02:56,980 --> 01:03:00,440
Kiel ni vidos tie, tie estas kelkaj pli ordigado algoritmoj tie ke homoj elpensis.

1047
01:03:00,440 --> 01:03:03,660
Tiu unua tuj estos inserción varo, kaj ĉi flugos tra

1048
01:03:03,660 --> 01:03:07,090
kaj donu al vi aŭdebla senco de kiel tiuj diversaj algoritmoj laboro.

1049
01:03:07,090 --> 01:03:09,080
Jen inserción varon.

1050
01:03:09,080 --> 01:03:18,410
[Elektronika beeping]

1051
01:03:18,410 --> 01:03:20,730
[Malan] Bobelo varon.

1052
01:03:20,730 --> 01:03:46,850
[Rapida elektronika beeping]

1053
01:03:46,850 --> 01:03:48,950
[Malan] Elekto varon.

1054
01:03:48,950 --> 01:04:03,580
[Rapida elektronika beeping]

1055
01:04:03,580 --> 01:04:05,770
[Malan] Merge varon.

1056
01:04:05,770 --> 01:04:17,270
[Elektronika beeping]

1057
01:04:17,270 --> 01:04:20,180
[Beeping paŭzo] [ridado]

1058
01:04:20,180 --> 01:04:22,590
[Malan] Gnome varon.

1059
01:04:22,590 --> 01:04:38,580
[Elektronika beeping]

1060
01:04:39,740 --> 01:04:46,150
>> Ĉi tiu estas CS50. Ni vidos vin proksima semajno. [Aplaŭdoj kaj huraoj]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]