1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [Aste 3, Continúa]

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

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

4
00:00:07,130 --> 00:00:11,010
>> Guztiak eskubidea. Ongi etorri berriro. Hau CS50 da eta 3 aste bukaera honetan.

5
00:00:11,010 --> 00:00:14,680
>> Beraz, ezagunenak dira, iaz Harvard zer Innovation Lab izeneko jarri zuen abian,

6
00:00:14,680 --> 00:00:18,530
edo i-lab, HBS en campus ibaian zehar eraikin zoragarri bat da

7
00:00:18,530 --> 00:00:22,640
hau da, unibertsitateko ikasle, ikasle GSAS, guztietan campus ikasleek zabalik,

8
00:00:22,640 --> 00:00:27,000
fakultateko barne, eta elkarrekin gauza berritzailea lan egiteko leku bat da,

9
00:00:27,000 --> 00:00:29,180
batik bat, ekintzaile gauzak

10
00:00:29,180 --> 00:00:33,410
eta 0 edo gehiago lagunak dira zerbait ekintzailea egiten bada, pentsatzen

11
00:00:33,410 --> 00:00:37,080
bai klase honetan zehar, klase honen ondoren, edo haratago.

12
00:00:37,080 --> 00:00:41,540
>> Beraz J epe egin dute gauza bat bidaiak horiek,

13
00:00:41,540 --> 00:00:44,510
eta horietako batek, New York, eta horietako batek Silicon Valley da.

14
00:00:44,510 --> 00:00:47,530
Space oso mugatua da, baina aukera bat sorbalda igurtzi to MBAs

15
00:00:47,530 --> 00:00:52,200
eta campus osoan zehar, eta egia esan, ikasleek graduondoko denbora eremu horiek, hurrenez hurren

16
00:00:52,200 --> 00:00:55,500
txateatzen startups, ekintzaile txateatzen eta antzekoak.

17
00:00:55,500 --> 00:00:57,870
Beraz, bada, egiaztatu URL hau hemen.

18
00:00:57,870 --> 00:01:01,220
Da, halaber, eskuragarri online diapositibak.

19
00:01:01,220 --> 00:01:04,610
>> Ezin behera tonua ditugu etxe audio besterik pixka bat?

20
00:01:04,610 --> 00:01:08,640
Bazkaria gurekin ostiral honetan izan nahi baduzu, Fire & Ice 1:15 etan, mesedez, buru dago.

21
00:01:08,640 --> 00:01:11,390
Apologies formularioa dagoeneko iritsi duzun denbora bete.

22
00:01:11,390 --> 00:01:13,750
Baina tradizio hau jarraitu dugu aurrera.

23
00:01:13,750 --> 00:01:17,350
>> Gaur egun, hainbat arazo konpondu ahal izango dugu, maila handiagoa eztabaida jarraituko dugu,

24
00:01:17,350 --> 00:01:21,330
askoz ere txikiagoa da bideratua, gaur egun, gutxienez, kodea, eta askoz ere ideia gehiago.

25
00:01:21,330 --> 00:01:24,720
Beraz, uste back aste 0 telefono-liburu bat Tore dugu erdia,

26
00:01:24,720 --> 00:01:28,260
horren helburua zen zerbait egin behar, admittedly, apur bat dramatikoa

27
00:01:28,260 --> 00:01:32,360
baina puntu Bilatzen duen ez izatea, nahitaez bidaltzeko,

28
00:01:32,360 --> 00:01:35,100
Lehen begiratuan agian uste duzu argi geratu da.

29
00:01:35,100 --> 00:01:40,200
Eta, oro har, arazo konpontzeko agian ez du zertan beti onena

30
00:01:40,200 --> 00:01:44,130
Konponbide nabarmenena agian ez duela zertan onena izan.

31
00:01:44,130 --> 00:01:47,300
Beraz, telefono-liburu hau izan genuen, eta Egia, gela honetan gurekin izan senak

32
00:01:47,300 --> 00:01:51,470
seguru asko, erdi-erdian Mike Smith bila hasi eta, ondoren, joan ezkerrera edo eskuinera

33
00:01:51,470 --> 00:01:54,280
alfabetoaren letra edozein izanda ere azkenean gertatu oinarritzen da.

34
00:01:54,280 --> 00:01:57,560
>> Baina hori ideia sinplea da dugu gizakiak hartu duten hain luze ematen

35
00:01:57,560 --> 00:02:00,670
benetan zure gogoaren abangoardian etortzen hasi behar

36
00:02:00,670 --> 00:02:03,900
arazoak lortu telefono-liburu bat baino askoz konplexuagoa delako,

37
00:02:03,900 --> 00:02:07,420
berean simple horiek, ikuspegi liluragarria gaitu egingo dira

38
00:02:07,420 --> 00:02:10,259
askoz ere zailagoa da eta gehiago interesgarri arazoak konpontzeko,

39
00:02:10,259 --> 00:02:12,930
horien artean, gauza batzuk dagoeneko egun hauetan emandako hartuko dugu.

40
00:02:12,930 --> 00:02:15,720
Bilioika web orrialdeak daude, eta oraindik, Google eta Bing eta antzeko

41
00:02:15,720 --> 00:02:17,660
gauzak aurkitzeko gai Gurekin horrela.

42
00:02:17,660 --> 00:02:22,300
Hori ez da gertatzen lineal bilaketa baten bidez, guztiak ahalik eta web orriak bidez bilatzen.

43
00:02:22,300 --> 00:02:25,290
Facebook da gai dira zure lagunak dira, edo lagunen lagunak,

44
00:02:25,290 --> 00:02:28,250
eta hori ere egin ahal izango dira, itxuraz berehalako batean egun hauetan

45
00:02:28,250 --> 00:02:30,820
nahiz eta milioika erabiltzaileei dute.

46
00:02:30,820 --> 00:02:34,250
>> Eta, beraz, nola arazoak konpontzeko benetan eskala horretan izango da, azken finean, murrizteko

47
00:02:34,250 --> 00:02:37,830
ideiak begiratu aste 0 dugu, eta pixka bat gehiago gaur egun.

48
00:02:37,830 --> 00:02:42,320
Ez dugu berriro algoritmo hau exekutatu, baina gogoratzen aste 0 ariketa hau ere egin genuen

49
00:02:42,320 --> 00:02:44,780
non denek genuen Zutik, 1 zenbakia izango ditu, eta

50
00:02:44,780 --> 00:02:48,720
eta, ondoren, denek auto-kopuruan izan dugu off parekatu, zure zenbakiak gehituz batera,

51
00:02:48,720 --> 00:02:51,930
ondoren, Koadrilaren erdia eseri iterazio guztietan.

52
00:02:51,930 --> 00:02:56,750
Beraz, 500 ikasle eta 250 125 joan ginen, eta abar.

53
00:02:56,750 --> 00:03:00,080
Baina, astelehena, gisa esan, ideia indartsua dago

54
00:03:00,080 --> 00:03:02,460
izan zen, tamaina bikoiztu dugu arazo hori bada

55
00:03:02,460 --> 00:03:06,480
eta Justizia edo EE 10 lagunak itzuli zen gelan sartu eta gurekin sartu

56
00:03:06,480 --> 00:03:09,510
ondo izan dugu, ziurrenik, agregazio osoa talde hori zenbatu

57
00:03:09,510 --> 00:03:13,380
1 Begizta gehiago big iterazio zuten soilik agian duelako bikoiztu tamaina

58
00:03:13,380 --> 00:03:15,630
edo EE 10 kasua bikoitza tamaina baino pixka bat gehiago.

59
00:03:15,630 --> 00:03:18,440
Eta, beraz, apur bat pasatzeko denbora gehiago genuke,

60
00:03:18,440 --> 00:03:22,000
baina ez genuke izan 400 edo 700 urrats gehiago pasatzeko.

61
00:03:22,000 --> 00:03:26,550
>> Just argazki hau margotzeko modu bat, apur bat gutxiago abstraktuak, ez dute denek Zutik.

62
00:03:26,550 --> 00:03:31,100
Baina dutenek aukeratu zuen, gaur egun, orkestra eseri axola ez balu, zutik,

63
00:03:31,100 --> 00:03:34,580
dezagun ikusi dugu irudikatu dezakezu artean duten pertsona altuena da

64
00:03:34,580 --> 00:03:36,730
konparazio-algoritmoa moduko bera eginez.

65
00:03:36,730 --> 00:03:41,830
Beraz, bada, orkestra, nire apologies, baina 1. Pausoan ari zaren eserita, Zutik;

66
00:03:41,830 --> 00:03:44,650
2. urratsa, bikotea off edonork Gertuko duzu,

67
00:03:44,650 --> 00:03:49,360
irudikatu nor da taller, eta eseri zara laburragoa bada.

68
00:03:49,360 --> 00:03:51,360
Ondoren, errepikatu.

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

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

71
00:04:15,320 --> 00:04:19,010
Ongi da. One geratzen da zutik. Zein da zure izena? >> Andrew.

72
00:04:19,010 --> 00:04:21,959
>> Andrew, orkestra atalean pertsona garaiena gaur dira.

73
00:04:21,959 --> 00:04:28,100
>> Zorionak. [Txaloak eta txaloak] Larreina. Eserlekua. Beraz, Andrew aurkitu dugu.

74
00:04:28,100 --> 00:04:30,870
Baina zenbat denbora hartu me, esate baterako, Andrew aurkitu

75
00:04:30,870 --> 00:04:33,740
50 + edo, beraz, pertsona orkestra hau?

76
00:04:33,740 --> 00:04:36,900
Hartu nuen oso ikuspegi sinple bat eta hemen.

77
00:04:36,900 --> 00:04:39,270
Eta 2 pertsona dut Zutik eta alderatu besterik ez ditut,

78
00:04:39,270 --> 00:04:42,120
eta, ondoren, esaten duenak pixka bat laburragoa izan da, "Ongi da, eseri duzu"

79
00:04:42,120 --> 00:04:44,380
eta taller pertsona izan zen gogoratzen dut.

80
00:04:44,380 --> 00:04:49,030
Ondoren, errepikatu dut errepikatu, errepikatu, eta pertsona altuena zintzilik I

81
00:04:49,030 --> 00:04:51,920
aurkitu dut norbait horiek baino apur bat taller arte, eta amaitzen da

82
00:04:51,920 --> 00:04:54,950
pixka bat laburragoa izan ditu, ondoren, eseri.

83
00:04:54,950 --> 00:04:57,690
Baina orkestra Atal honetan algoritmoa dela, badago-n,

84
00:04:57,690 --> 00:05:00,480
zenbat urrats algoritmoa, hartu egingo da? >> [Ikasleen] N.

85
00:05:00,480 --> 00:05:03,580
>> N hartu, eskuinera, kasurik okerrenean, eta, beraz, delako hitz egiten da,

86
00:05:03,580 --> 00:05:09,090
altuena pertsona oso azken pertsona dut besterik ez ausazko zorte txarra da.

87
00:05:09,090 --> 00:05:14,260
Beraz, kasu horretan, txarrena, algoritmoa, denbora lineala da, n,

88
00:05:14,260 --> 00:05:18,070
non n espazioa pertsonen kopurua guztira, arazoaren tamaina da.

89
00:05:18,070 --> 00:05:19,600
Algoritmoa honi buruz?

90
00:05:19,600 --> 00:05:22,080
Izan ere, guztiak altxatu eta berriro erdia eseri,

91
00:05:22,080 --> 00:05:23,950
duzun erdia eseri, eseri duzun erdia.

92
00:05:23,950 --> 00:05:26,070
Zenbat urrats behar izan diren duzun n bada hemen?

93
00:05:26,070 --> 00:05:30,200
[Ikasleen] N log n. >> Hori okerragoa izango litzateke. Saioa hasi n.

94
00:05:30,200 --> 00:05:32,930
>> Beraz, saioa n, nahiz eta ez duzu nahiko gogoratu logaritmo bat zer den,

95
00:05:32,930 --> 00:05:38,410
oraingoz, eskertzen erlazionatzen dela, nolabait, hau eta halving halving eta halving.

96
00:05:38,410 --> 00:05:41,000
Faktorea 2 ez du zertan izan behar. 3-faktore bat izan daiteke.

97
00:05:41,000 --> 00:05:46,560
Baina faktore, hala nola, mota berean errepikatzea da, arazoaren tamaina hemen hasten da

98
00:05:46,560 --> 00:05:49,620
baina gero, berehala doa hemen, eta ondoren, hemen, eta gero hemen, eta gero hemen.

99
00:05:49,620 --> 00:05:53,580
Ziztadak txikiak hartzen ari zara arazoa, benetan ari zaren kanpoan Tajadura ere

100
00:05:53,580 --> 00:05:56,160
handi bat jaitsi swoop aldi bakoitzean.

101
00:05:56,160 --> 00:06:00,810
Beraz, 50 pertsona izan genuen eta, ondoren, 25 eta, ondoren, 12 ½ edo 13 pertsonak zutik,

102
00:06:00,810 --> 00:06:05,370
ondoren, 6 ½ eta abar zutik azkenik besterik ez Andrew geratu zen arte.

103
00:06:05,370 --> 00:06:08,710
Beraz n erregistroa deitzen dugu, eta hau honela ikusteko dezakezu.

104
00:06:08,710 --> 00:06:12,570
Gogoratu hemen argazki hau non algoritmo lineal bat, lerro gorriaren bezala dago,

105
00:06:12,570 --> 00:06:17,520
lerro horiak zenbaketa 2s algoritmoa izan zen ikasle kontatuta erabiltzen dugun

106
00:06:17,520 --> 00:06:22,300
iraganean, baina, gaur egun, Santo Grial berdea linea honetan jarraituko du

107
00:06:22,300 --> 00:06:25,470
non orkestra atalean pertsonen kopurua bikoiztu egin dugu izanez gero edo, besterik gabe, esan zuen,

108
00:06:25,470 --> 00:06:29,170
infernua, egin ditzagun osoan gela guztiek Zutik, ez aurre handi bat, hala nola,

109
00:06:29,170 --> 00:06:31,560
gutxi gorabehera bikoiztu delako zenbat pertsonak dira hemen,

110
00:06:31,560 --> 00:06:33,500
1 iterazio gehiago, ez da arazo bat.

111
00:06:33,500 --> 00:06:36,200
>> Aurkitu dugu Andrew edo duenarentzat gertatzen Andrew baino altuagoa izan

112
00:06:36,200 --> 00:06:38,770
entreplanta edo balkoian.

113
00:06:38,770 --> 00:06:42,140
Simple hartu dugun hainbeste telefono-liburu batean ematen Beraz, ideia hau,

114
00:06:42,140 --> 00:06:46,170
konturatzen ez direla hainbeste toki ezberdinetan aplikatu ahal izango dugu.

115
00:06:46,170 --> 00:06:50,810
Just jargon batzuk Slap - benetan, baino jargon lehenik eta behin,

116
00:06:50,810 --> 00:06:52,750
utzi joan argazki hau me hemen.

117
00:06:52,750 --> 00:06:56,970
Oraintxe n eta n / 2 buruz hitz egin dugu, eta, ondoren, saioa n,

118
00:06:56,970 --> 00:07:00,500
baina etorri, seihilekoan zehar egingo dugu,

119
00:07:00,500 --> 00:07:05,130
beste formula matematiko sort iraupena ideia orokor hau deskribatzeko.

120
00:07:05,130 --> 00:07:07,580
Hauek dira oraingoz testuinguru luze baino lehen ikusiko dugu delako

121
00:07:07,580 --> 00:07:09,900
algoritmo horiek benetan ordezkatzen.

122
00:07:09,900 --> 00:07:17,990
>> Baina hemen nabarituko lineal line n, lerro zuzena da, benetan, oso baxua seinalatuz oraintxe.

123
00:07:17,990 --> 00:07:22,950
Ilusio optikoa sort hori aldatu besterik ez dugu zer adierazten du x ardatzaren

124
00:07:22,950 --> 00:07:26,130
eta y ardatza, eta nahi dugun norabidea edozein zuzen puntu bat egin ahal izango dugu.

125
00:07:26,130 --> 00:07:30,350
Baina arrazoia da, beraz, itxuraz lauak gaur egun

126
00:07:30,350 --> 00:07:35,690
grafikoa gela egin behar dugu exekutatzen ari askoz motelagoa aldiz delako.

127
00:07:35,690 --> 00:07:39,030
Oraingoz, jakin bizitza algoritmo nahiko txarra batzuk daudela,

128
00:07:39,030 --> 00:07:43,790
horietako batzuk ez hartu n urratsak edo, hobeto oraindik, n urrats baina gehiago saioa.

129
00:07:43,790 --> 00:07:48,820
Beraz, lerro gainetik n hemen beheko oharra n aldiz n erregistroa,

130
00:07:48,820 --> 00:07:51,410
ikusi eta zer esan nahi du, hau baino lehen luzea dugu.

131
00:07:51,410 --> 00:07:56,010
Gainetik karratu n, eta ez dugu edozein n karratu algoritmoak ikusi oraindik, baina buruz ari gara.

132
00:07:56,010 --> 00:07:57,660
Eta hori itxura oso txarra da.

133
00:07:57,660 --> 00:08:01,610
Dago 2 n, zerbait esponentzialean, eta sentitzen are okerragoa da.

134
00:08:01,610 --> 00:08:05,760
Eta, hala ere, bitxikeria bada ere, gero n cubed, Oraindik duzu aurretik pentsatzen sort izanez gero,

135
00:08:05,760 --> 00:08:10,000
mota egin nahi duzu matematika, 2 n benetan askoz straighter bihurtzen da,

136
00:08:10,000 --> 00:08:15,930
askoz ere handiagoa n baino cubed ardatz begiratuz gero urruti nahikoa out.

137
00:08:15,930 --> 00:08:19,890
Beraz, konturatu oraintxe ardatzak hauek dira arbitrarioki 2 10 x ardatza.

138
00:08:19,890 --> 00:08:21,770
>> Eta zer esan nahi du horrek?

139
00:08:21,770 --> 00:08:23,890
Horrek esan nahi du 2 pertsonek gela 10 pertsona.

140
00:08:23,890 --> 00:08:27,200
Arazo tamaina, edozein testuinguru da: That guztiak x bide bat da.

141
00:08:27,200 --> 00:08:30,420
Eta ardatz bertikala oraintxe segundo kopurua edo urrats kopurua

142
00:08:30,420 --> 00:08:31,840
denbora-unitate batzuk.

143
00:08:31,840 --> 00:08:34,740
Baina hori 0 eta 60 eta 0 eta 10.

144
00:08:34,740 --> 00:08:38,549
Baina zoom out mota, Excel edo diagramen software batzuk agian, bada

145
00:08:38,549 --> 00:08:43,370
eta igo dugu, 200.000 nabarituko 2 atsegin n zerbait

146
00:08:43,370 --> 00:08:47,520
n karratu aldiz martxan guztiz gaindituak izaten da,

147
00:08:47,520 --> 00:08:50,960
n cubed, n log n - dena buruz hitz egin dugu, beraz, oso urrun.

148
00:08:50,960 --> 00:08:54,190
Eta, oraindik, harrapaketa Facebook bezalako gauzak buruz hitz egiten hasi

149
00:08:54,190 --> 00:08:57,150
asko, asko, jende asko guztiak elkarrekin lotuak,

150
00:08:57,150 --> 00:09:00,650
pertsona izan dira parte hartu dutenak, n, bakoitzak horietatik n lagunak asko izan dezake

151
00:09:00,650 --> 00:09:02,860
guztiek buddy-buddy sort bada munduan,

152
00:09:02,860 --> 00:09:08,100
ondo, n aldiz n dagoeneko, eta, beraz, hori ahalik eta lagun karratu n

153
00:09:08,100 --> 00:09:10,950
gutxienez 1 norabidea, n karratu ahalik eta adiskidetasuna.

154
00:09:10,950 --> 00:09:15,330
Beraz, dagoeneko iradokitzen Facebook gizarte grafikoan bilatuz, nolabait esateko,

155
00:09:15,330 --> 00:09:18,090
formula mota horiek adierazten has daiteke.

156
00:09:18,090 --> 00:09:19,820
>> Itzuli gara eta hau askoz zehatzagoak egiteko,

157
00:09:19,820 --> 00:09:23,280
baina, oraingoz, hurrengo asteetan asko helburu

158
00:09:23,280 --> 00:09:27,170
ziur ez algoritmoak ezartzeko edo kode buruz izango da

159
00:09:27,170 --> 00:09:29,870
honen antzeko zerbait sortu denbora askoz gisa hartu amaieran.

160
00:09:29,870 --> 00:09:33,110
Baina informatika buruz gauza liluragarriak jarraitzen baduzu, arlo honetan

161
00:09:33,110 --> 00:09:38,320
klaseak hartu CS121, CS124 bezala, biak ikastaroak teoria,

162
00:09:38,320 --> 00:09:41,300
dagoela, egia esan, mundu honetan dauden arazo batzuk

163
00:09:41,300 --> 00:09:45,710
funtsean, ezagutzen dugun neurrian, ezin dira konpondu edozein azkarrago

164
00:09:45,710 --> 00:09:48,880
grafikoak horien txarrena baino benetan iradokitzen du.

165
00:09:48,880 --> 00:09:53,660
Beraz, mundu honetan irekita arazo askoz hobeto gizakiak baino, beraz, orain arte egin asko.

166
00:09:53,660 --> 00:09:56,130
>> Beraz, dezagun hasteko, ondoren, adibide honekin.

167
00:09:56,130 --> 00:09:59,650
Sean kamera honekin borroka, guztiak ere awkwardly bideoa ikusi dugu.

168
00:09:59,650 --> 00:10:05,270
Baina errealitatea zen Sean taula honetan zenbaki 7 atsegin aurkitzeko tasked zen,

169
00:10:05,270 --> 00:10:10,300
gogoratzen esan nuen, "Ez dago nonbait paper pieza horiek edo zuria ateak atzean

170
00:10:10,300 --> 00:10:12,570
"Kopurua 7. Sean, aurkitu digu."

171
00:10:12,570 --> 00:10:14,200
Eta wonderfully awkward zen ikusteko

172
00:10:14,200 --> 00:10:15,790
izan zen benetan delako arazo honekin borrokan.

173
00:10:15,790 --> 00:10:19,720
Baina errealitatea zen Sean egin gelan edonork egin izan baita.

174
00:10:19,720 --> 00:10:21,890
Pixka bat gehiago hartu zuen, ohiko pertsona baino liteke izan,

175
00:10:21,890 --> 00:10:24,760
baina ez zela trikimailu batzuk arazo hau bere gain hartu zuen,

176
00:10:24,760 --> 00:10:26,590
zela zerbait falta zuen bere gain hartu zuen.

177
00:10:26,590 --> 00:10:29,320
Eta ez da begiak ehunka jaitsi zirela kontuan hartuta zuen.

178
00:10:29,320 --> 00:10:34,250
>> Baina errealitatea zen arazoa sarrera ausazko zenbakiak sorta bat bada

179
00:10:34,250 --> 00:10:37,120
eta zu, hala nola 1 zenbakia eskatu

180
00:10:37,120 --> 00:10:39,770
onena egin dezakezu bilaketa lineala.

181
00:10:39,770 --> 00:10:44,060
Hasi ezker, eskuinera mugitzeko, edo eskubidea etan hasiko da, ezkerrera mugitu.

182
00:10:44,060 --> 00:10:48,300
Retroactively, pentsatzen dugu agian, "Sean, zergatik ez beste muturrean besterik ez duzu hasi?"

183
00:10:48,300 --> 00:10:52,120
Beno, 7 bezain erraz izan da izan hemen ausaz,

184
00:10:52,120 --> 00:10:54,980
baina nahita jarri dut han figured I ez du amaieran hasi behar duelako.

185
00:10:54,980 --> 00:10:59,320
Beraz, manipulatu mota dut egoera, baina aukera ausazko 7 izan zitekeen edozein lekutan.

186
00:10:59,320 --> 00:11:02,380
Beraz, eskuin muturrean hasita hobea izan liteke, ondoren,

187
00:11:02,380 --> 00:11:04,320
baina zer izanez gero, hurrengo urteko 7 mugitzen dut beste nonbait?

188
00:11:04,320 --> 00:11:06,830
Hori ez da arazoaren konponbidea funtsean berri bat -

189
00:11:06,830 --> 00:11:10,520
1 amaieran edo beste hasita duzunean emandako beste hipotesi ez.

190
00:11:10,520 --> 00:11:13,620
Beraz, Sean zenbakiak bidez bila hasi zen, eta esan zuen, "5. Hori ez da hemen."

191
00:11:13,620 --> 00:11:17,280
Gero, hara joan zen eta 19 ikusi eta, ondoren, pausatuta 20 segundotan egin zuen,

192
00:11:17,280 --> 00:11:22,330
ondoren, hau ireki zuen 13 eta, ondoren, itxurazko bihurtu zen

193
00:11:22,330 --> 00:11:24,270
ez dagoela ez dirudi hemen eredu bat izan.

194
00:11:24,270 --> 00:11:28,090
Ezin izan da, 1, 2, 3, 4 edo antzekoak. Baziren zenbakiak hutsuneak, eta horrek ez du lagunduko.

195
00:11:28,090 --> 00:11:32,320
Eta ere, Izan ere, erabili dut paper pieza merkea hauek estaltzeko zenbakiak

196
00:11:32,320 --> 00:11:35,270
da, benetan, nahita, kendu dut paper pieza horiek guztiak galtzen delako,

197
00:11:35,270 --> 00:11:38,760
gurekin gehienak, Sean barne, seguruenik begiratu litzateke sort macroscopically-

198
00:11:38,760 --> 00:11:43,410
arbelean eta esan zuen, "Oh, 7, jakina da bertan." Ez dugu berehala.

199
00:11:43,410 --> 00:11:46,460
>> Eta hori, neurri batean lan egiten du, giza burmuina izan daiteke,

200
00:11:46,460 --> 00:11:50,730
baina errealitatean, bere begiak edo kontuan izan zen ziurrenik skimming zenbakiak eskuinetik ezkerrera,

201
00:11:50,730 --> 00:11:55,190
eskubidea, erdiko kanpo utzi zerbait izan zen joan fisiologikoki

202
00:11:55,190 --> 00:11:57,640
hala nola sentitu zen berehala gertatzen ari den bezala,

203
00:11:57,640 --> 00:12:01,360
baina odds are barrutik metodologia mota batzuk ez zen 7 aurkitzeko.

204
00:12:01,360 --> 00:12:05,160
Eta, hain zuzen ere, gaur egun ari gara array egitura eta datuak buruz hitz egiten

205
00:12:05,160 --> 00:12:08,780
eta memoria ordenagailu baten barruan, gauza bakarra dugu gizakiak egin dezaket

206
00:12:08,780 --> 00:12:13,070
oroimen indibiduala kokapenak begiratu 1 aldi berean.

207
00:12:13,070 --> 00:12:16,600
>> Beraz, beste behin, baliteke baita ere estalita paper batzuk

208
00:12:16,600 --> 00:12:21,170
ikusi ahal izango dugu ez delako dena den. Bakarrik egin ahal izango ditugu, aldi berean gauza 1.

209
00:12:21,170 --> 00:12:25,030
Beraz, kasu honetan, Sean kasuan, hemen ginen eta gero, hara joan ginen

210
00:12:25,030 --> 00:12:31,040
eta gero, hara joan ginen, hemen, hemen, hemen, baina clever amaieran

211
00:12:31,040 --> 00:12:34,450
eta mota horretako saltatu hau arbitrarioki eta 7 bertan aurkitu.

212
00:12:34,450 --> 00:12:37,470
Hau ez da batez ere berezia izan zen. Oso ordena.

213
00:12:37,470 --> 00:12:39,530
Baina azkenik aurkitu zuen 7.

214
00:12:39,530 --> 00:12:45,360
Baina orain takeaway onena egin dezakezu orduan emandako informazioa ez da benetan

215
00:12:45,360 --> 00:12:50,400
zenbakiak ausaz ordenatuko baino beste ezker edo eskuinera abiatuko da.

216
00:12:50,400 --> 00:12:54,950
Edo arraioa, ausaz dezakezu ireki ateak, baina orduan ere zer ez ausazko izan nahi?

217
00:12:54,950 --> 00:12:57,220
Beno, nolabait formalizatzeko zer esan nahi du, hemen hasteko genuke,

218
00:12:57,220 --> 00:13:01,150
ondoren, hemen, eta hemen. Sean handia egin, eta soilik ondo pasatzeko izan zen ikusteko.

219
00:13:01,150 --> 00:13:06,340
Zer ordez bada arazoa pixka bat aldatu dugu eta ekarri aurtengo Sean, bada?

220
00:13:06,340 --> 00:13:09,460
Egingo luke edonork izango eroso datozen etapa, eta pixka bat beste arazo bat konpontzeko

221
00:13:09,460 --> 00:13:12,330
eta kamera agertzen?

222
00:13:12,330 --> 00:13:15,720
>> Dezagun orkestra haratago joan you guys delako nahiko parte hartzen duten gaur egun dagoeneko.

223
00:13:15,720 --> 00:13:21,430
How about pink, kapela? Goazen behera. Zein da zure izena? >> Alex. >> Alex. Ongi da.

224
00:13:21,430 --> 00:13:24,580
Beraz, Alex aurtengo Sean izango da, eta agertuko da hurrengo urteetan hainbat

225
00:13:24,580 --> 00:13:27,770
CS50 hitzaldiak merezi du.

226
00:13:27,770 --> 00:13:30,340
Alex, politak zu ezagutzeaz. >> Nice zu ere.

227
00:13:30,340 --> 00:13:33,470
Esku erronka da zuretzat errazagoa eta pixka bat duzula

228
00:13:33,470 --> 00:13:38,950
duzun naiz kontatzeko zenbakiek berdinak dira hemen, baina gaur egun ordenatuko dira.

229
00:13:38,950 --> 00:13:41,800
Beraz, zure helburua da 7 zenbakia aurkitu.

230
00:13:41,800 --> 00:13:45,370
Eta benetan, benetan behar dugu hau iruzurra mota you're, ordenagailu bat bezala izango litzateke,

231
00:13:45,370 --> 00:13:47,990
zer begira zenbakiak izan ziren une batez ago.

232
00:13:47,990 --> 00:13:50,360
Klarion honekin benetan ez da asko lagunduko du,

233
00:13:50,360 --> 00:13:52,810
baina dezagun asmoa ez duzula ez dakit zer array jatorrizko da.

234
00:13:52,810 --> 00:13:56,600
Gaur egun ezagutzen duzun guztia duzula zenbakiak ordenatuko array

235
00:13:56,600 --> 00:14:00,360
haien arteko hutsuneak izan daiteke, eta zure helburua da 7 zenbakia aurkitu.

236
00:14:00,360 --> 00:14:05,080
Nola nahi duzu, zentzuzko gizakiaren, 7 zenbakia aurkitzeko?

237
00:14:05,080 --> 00:14:07,770
>> Handiko baxua? >> Ados. Joan handiko baxua.

238
00:14:07,770 --> 00:14:10,990
Eta ez malko horiek off. Dezagun igogailua horiek horiek berrerabili ahal izateko.

239
00:14:10,990 --> 00:14:14,730
Ongi da, eta, beraz, 1. Itxaron. Mantentzeko joan aurretik, 1, argi eta garbi okerra izan zen.

240
00:14:14,730 --> 00:14:17,270
Beraz, zer zure kontuan bidez hurrengo? Zein da zure hurrengo mugitzen da?

241
00:14:17,270 --> 00:14:23,250
Hurrengoa. >> Ados. Hurrengoa. Good. 3, eta, beraz, okerra. Zein da zure hurrengo mugitzen da?

242
00:14:23,250 --> 00:14:27,670
Joan mantentzeko. >> Guztiak eskubidea. Joan mantentzeko. 5.

243
00:14:27,670 --> 00:14:31,110
Beraz, joan mantentzeko, eta utzi entregatu me hau posteridad.

244
00:14:31,110 --> 00:14:35,720
7. >> Bikain. Oso ona. Found kopurua 7. [Txalo]

245
00:14:35,720 --> 00:14:39,720
Beraz, ona izan zen, baina Sean ere, 7 zenbakia aurkitu.

246
00:14:39,720 --> 00:14:44,490
Eta ez duzula benetan ustiatu informazio pieza gehiago defendatzen dut,

247
00:14:44,490 --> 00:14:47,780
hau da, zenbaki horiek ordenatuko dira.

248
00:14:47,780 --> 00:14:51,520
Beraz, hobeto egiten dugu? Edozein iradokizun hemen? Bai, berriro.

249
00:14:51,520 --> 00:14:54,710
[Ikasleak] Binary bilaketa. >> Ideia ez daukat zer bitar bilaketa.

250
00:14:54,710 --> 00:14:58,030
>> [Ikasleak] Hasi erdian. >> Erdian Hasi. Ongi da. Beraz, ikus dezagun ez gara daiteke.

251
00:14:58,030 --> 00:15:02,580
Beraz ordez bada kontatzen ari zaren Irteeran erdialdetik aurrera eta erdiko atea ireki.

252
00:15:02,580 --> 00:15:04,580
Horietako 8, beraz, arbitrarioki aukeratu bat ari zaren.

253
00:15:04,580 --> 00:15:09,800
pixka bat ezkerrera edo eskuinera. Ongi da. 7! [Txalo] Very nice.

254
00:15:09,800 --> 00:15:11,410
Ongi da, baina non ziren joan honekin?

255
00:15:11,410 --> 00:15:14,990
Dezagun abiarazi izan duzu hemen gorbata besterik ez hausteko

256
00:15:14,990 --> 00:15:16,670
berdin gertatu delako izan da baita.

257
00:15:16,670 --> 00:15:19,540
Gertatu zen 7 zegoen jakin nahi dugu. Beraz, honen 13ra arte egongo da.

258
00:15:19,540 --> 00:15:21,980
Beraz, ari ordenatuko eta erdian hasi ginen,

259
00:15:21,980 --> 00:15:24,600
zer egingo zenuke hurrengo mugimenduan optimoa izan dira?

260
00:15:24,600 --> 00:15:27,740
Joan ezkerrera. Eta, beraz, hemen telefono book Adibidez dator berriro.

261
00:15:27,740 --> 00:15:30,130
13ra arte egongo da hemen eta zerrenda ordenatuko bada badakigu,

262
00:15:30,130 --> 00:15:33,900
ondoren, paper pieza horiek guztiak gurekin uninteresting

263
00:15:33,900 --> 00:15:37,400
dagoeneko 7 ezkerreko behar dugu ezagutzen delako

264
00:15:37,400 --> 00:15:39,510
zenbaki horiek antolatuko dira eta 13 aurkitu dugu.

265
00:15:39,510 --> 00:15:42,500
>> Beraz, zer da da zure hurrengo mugimenduan hemen? >> Ezkerrera joan. >> Ongi, ona da.

266
00:15:42,500 --> 00:15:45,080
Beraz, ezkerrean, eta - itxaron, hey, hey, hey. Hori iruzurra.

267
00:15:47,140 --> 00:15:51,350
Beraz, 7 aurkitu duzu, baina zer zen algoritmoa aplikatu besterik ez dugu?

268
00:15:51,350 --> 00:15:56,450
Hasi erdian. >> Good. Beraz, zer ideia bereko luzapena logikoa da?

269
00:15:56,450 --> 00:15:58,970
Oh, besterik ez horiek. >> Zehazki. >> Beraz, hemen hasten dut. >> Good.

270
00:15:58,970 --> 00:16:02,020
Beraz, gaur egun, apur bat ezkerrera joan ginen berriro. 3 da.

271
00:16:02,020 --> 00:16:05,310
Baina interesgarria takeaway gaur egun ez duten do bat zaintzeko buruz?

272
00:16:05,310 --> 00:16:08,040
Hauek 2. >> Hauek 2. Beraz, gaur egun hau urrun joan daiteke, urrun joan daiteke.

273
00:16:08,040 --> 00:16:12,330
, Orain zela 8 gero arazoa zen, tamaina 4 tamaina 2.

274
00:16:12,330 --> 00:16:16,430
Nahiko hurbil ari gara. Berriz ere, 2 elementu horiek erdian joan da.

275
00:16:16,430 --> 00:16:20,430
>> Ongi da. Beraz, sort da zorigaiztoko orain dela beti ari gara ezkerrera joan gara biribiltze duelako behera.

276
00:16:20,430 --> 00:16:25,150
Baina hori fina, gaur egun hau bota dugulako kanpoan eta beste guztia, gurekin utzi besterik ez 7.

277
00:16:25,150 --> 00:16:30,490
Eman dezagun txalo txanda. 7 aurkitu dugu berriro. [Txaloak] Larreina. Ziur.

278
00:16:30,490 --> 00:16:32,220
Just 1 bigarren Hang on.

279
00:16:32,220 --> 00:16:36,630
Nahiz eta prozesu hori hurrengo mota hartu pixka bat gehiago sentitzen dugu lukeena baino,

280
00:16:36,630 --> 00:16:40,150
Egia, zure lehen senak onenak izan ziren, ezta? 7 eta berehala aurkitu dugu.

281
00:16:40,150 --> 00:16:46,740
Baina aurkitu izana genuke 7 azkarrago, ez du axola zer, adibide honetan hau versus

282
00:16:46,740 --> 00:16:50,100
zenbakiak ordenatuko dira guztiak galtzen delako, askoz ere telefono-liburu batean orri bezala,

283
00:16:50,100 --> 00:16:54,580
hain zuzen ere, arazoaren erdia dezakezu txikitu berriro eta behin eta berriro.

284
00:16:54,580 --> 00:16:56,740
Eta ez da nahiko erraza ikusteko 8 zenbakiak

285
00:16:56,740 --> 00:17:00,100
1.000 orrialde telefono-liburuaren non ikusiko duzula bisualki ez bezala,

286
00:17:00,100 --> 00:17:03,120
baina kasu honetan hemen Sean zen 7 bilatuz,

287
00:17:03,120 --> 00:17:06,020
zenbat kasu txarrena urrats hartu zion? >> [Ikasleak] 7.

288
00:17:06,020 --> 00:17:11,670
Txarrena kasuan, 7. Beno, kasu txarrenean ez 7 ez 8 ateak hemen.

289
00:17:11,670 --> 00:17:13,440
Hartu dute litzateke zion 8 urrats.

290
00:17:13,440 --> 00:17:18,170
>> Beraz, n ateak bada, hartu dute agian Sean, duela pare bat urte n urratsak.

291
00:17:18,170 --> 00:17:21,520
Orain, zure kasua, Alex, ematen, zenbaki horiek ordenatuko

292
00:17:21,520 --> 00:17:25,130
eta non izan dugu, beraz, istorio hau den neurrian mota hau infer dugu

293
00:17:25,130 --> 00:17:28,300
Alex algoritmoa adimendunak iraupena

294
00:17:28,300 --> 00:17:30,770
erdi-erdian, eta ondoren hasten errepikatzea?

295
00:17:30,770 --> 00:17:36,490
[Ikasleak] 3. >> Beraz, 3, gutxi gorabehera, 8 4 bazoaz 2 eta 1 joan.

296
00:17:36,490 --> 00:17:40,660
3 urrats Beraz, edo, oro har, log n berriro.

297
00:17:40,660 --> 00:17:43,380
Edonoiz eta zaren halving eta halving halving eta halving,

298
00:17:43,380 --> 00:17:45,290
log n ideia hori adierazpen bat da.

299
00:17:45,290 --> 00:17:48,140
Eta horrela hartu nahi duzun 3 urrats besterik ez, eta, hain zuzen ere, egin

300
00:17:48,140 --> 00:17:50,890
behin, ateak eta halving halving ireki genuen,

301
00:17:50,890 --> 00:17:53,770
hau hartu dute, berriz, Sean batzuk 7 edo 8 urrats.

302
00:17:53,770 --> 00:17:56,330
Beraz, eskerrik asko aurten gurekin izateagatik. >> Eskerrik asko. Niza bilera duzu.

303
00:17:56,330 --> 00:18:00,170
Eskerrik asko Alex. >> Era berean. [Txalo]

304
00:18:00,170 --> 00:18:02,150
>> Zer da hau benetako inplikazioa?

305
00:18:02,150 --> 00:18:06,050
Orain imajinatu ez duela 8 ateak,, Egia, guztiok zerbait aurkitu

306
00:18:06,050 --> 00:18:10,430
8 ateak atzean nahiko azkar paper pieza tearing eta gure senak.

307
00:18:10,430 --> 00:18:14,430
Baina, zer da milioi ateak bada? Zer da bada 4 milioi ateak?

308
00:18:14,430 --> 00:18:19,630
4 milioi ateak kasuan, benetan ari zaren Alex-en algoritmoa joan nahi du,

309
00:18:19,630 --> 00:18:23,150
bitarra bilaketa deituz gisa hasiko edo zatitzea eta konkistatzeko, oro har,

310
00:18:23,150 --> 00:18:25,220
arazoa halving eta halving mantendu,

311
00:18:25,220 --> 00:18:30,510
4 milioi ateak duzu bada, zenbat aldiz daitekeelako 4 milioi txikitu erditik?

312
00:18:30,510 --> 00:18:33,870
[Ikasleak] 32. >> Benetan da 32. Hau lan egin dezakezu paper zati bat edo zure burua.

313
00:18:33,870 --> 00:18:38,490
4 milioi - 2 milioi 1 milioi bat milioi erdi joan behar duzu, 250 milioi, dot, dot, dot.

314
00:18:38,490 --> 00:18:41,620
Eta ez duzu bada math, 32 hain zuzen ere, lortu zaren joan,

315
00:18:41,620 --> 00:18:44,950
eta hori benetan informatika normalean erlazionatzen dugu 2 eskumenak zenbatu.

316
00:18:44,950 --> 00:18:47,600
2 32 gertatzen 4 milioi dolarrekoa izango da.

317
00:18:47,600 --> 00:18:51,440
Beraz, 2 eskumenak informatikako mota horiek garrantzi handia.

318
00:18:51,440 --> 00:18:55,120
>> Baina, zer da 8 milioi? Zenbat urrats hori hartu daude 8 milioi ateak?

319
00:18:55,120 --> 00:19:00,350
[Ikasleak] 33. >> Beraz, 33. Zer badago 16 milioi ateak? Zenbat urrats hori hartu?

320
00:19:00,350 --> 00:19:05,020
[Ikasleak] 34. >> 34. Mota jarraitu izan dugu, ad nauseam hau. Baina hori gauza bat indartsua da.

321
00:19:05,020 --> 00:19:09,430
Bilioika input gehiago aurkeztu ahal izango duzu zure arazoa, baina, big aurre ez,

322
00:19:09,430 --> 00:19:14,140
hartu besterik ez duzu 1 ziztadak osagarria da, eta, beraz, bilaketa bitarra antzeko zerbait ematen digu

323
00:19:14,140 --> 00:19:15,920
edo zatitzea eta konkistatzeko, oro har.

324
00:19:15,920 --> 00:19:17,990
Baina hemen tranpa mota naiz, ezta?

325
00:19:17,990 --> 00:19:22,410
Alex-en algoritmoa kasuan, Sean abantaila bat izan zuen.

326
00:19:22,410 --> 00:19:27,780
Zenbaki horiek ordenatuko ziren bazekien, baina Alex ez dituzten ordenatzeko bere burua.

327
00:19:27,780 --> 00:19:30,520
Aldez aurretik izan zen sortu egin ziurtatu arbel eta mota

328
00:19:30,520 --> 00:19:33,670
Drew ditut guztiak, ordena horrela antolatu, eta gero horiek estaltzen dut paper.

329
00:19:33,670 --> 00:19:35,850
Baina zenbat lan egin zuen hartzen duten me?

330
00:19:35,850 --> 00:19:40,110
Genuen hasi bada off itxuraz ausazko ordena zenbaki horiek

331
00:19:40,110 --> 00:19:43,320
kasu honetan horiek errazagoa zenbakiak, 8 Hemen bidez 1 -

332
00:19:43,320 --> 00:19:46,090
nola joaten balio horiek ordenatzeko dugu?

333
00:19:46,090 --> 00:19:52,530
Zeregin hori giza zinen bada, zer nolako ikuspegi intuitiboa hartu nahi duzun

334
00:19:52,530 --> 00:19:54,800
zenbaki-sorta oso bat ordenatzeko?

335
00:19:54,800 --> 00:19:57,050
Gauza hauek ezarritako puzzle pieza gisa. Bai.

336
00:19:57,050 --> 00:19:59,950
>> [Ikasleak] zenbaki bakoitzean hartu nahi dut eta alderatu bakoitzak

337
00:19:59,950 --> 00:20:03,180
eta ezkerrera joan. >> Ongi, ona da.

338
00:20:03,180 --> 00:20:05,720
Beraz, zenbaki bakoitza, konparatu bat ondoan,

339
00:20:05,720 --> 00:20:09,610
eta, ondoren, bakarrik zerrendan, joan ahala gauzak rejiggering mota batera mugitzen mantentzeko.

340
00:20:09,610 --> 00:20:13,800
Hortaz, hona hemen, agian batzuk gehiago folks parte hartzeko aukera dugu.

341
00:20:13,800 --> 00:20:16,290
8 boluntario gehiago etortzen maite dugu?

342
00:20:16,290 --> 00:20:23,950
A gutxiago presio pixka Oraindik ez bakarra. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Goazen behera. Zaudete zenbakiak 1 8 bidez.

344
00:20:28,190 --> 00:20:36,050
Ikus dezagun ezin dugu egin Ordenatzeko honetan Alex askoz ere modu berean egin nuen, aldez aurretik.

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

346
00:20:37,640 --> 00:20:40,760
Anima zaitez eta duzun izanez gero, etapa on line sortu music stand eta ni hemen arteko

347
00:20:40,760 --> 00:20:44,960
pantailan diapositiba gisa eta ordena berdinean.

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

349
00:20:50,370 --> 00:20:53,230
Lan egin dugu, sartu hurrengo adibidez. Oh, itxaron, itxaron. Hemen goaz. Itxaron.

350
00:20:53,230 --> 00:20:57,570
Hurrengo adibide da orain. Hemen duzu joan. Multzoko 8. Goazen sortu.

351
00:20:57,570 --> 00:21:00,270
Guztiak eskubidea. Ordena honen arabera zuei.

352
00:21:00,270 --> 00:21:03,620
Irristatu apur bat musikaren alde stand hemen.

353
00:21:03,620 --> 00:21:12,310
Beraz, 4, 2, 6 dugu - bertan, hemen baino gehiago, bertan 3.

354
00:21:12,310 --> 00:21:17,570
Bai. Ongi da. Baino gehiago duzu hemen. Ez, bertan geratuko duzu.

355
00:21:17,570 --> 00:21:21,840
Bai, bertan. N º oker nago. Eskuin dago. Ados, oso ona da. Ongi da.

356
00:21:21,840 --> 00:21:24,930
Beraz, gaur egun dezagun ordenatzeko ordena handitzeko.

357
00:21:24,930 --> 00:21:26,210
>> Nola egin dezaket hau egiten dut?

358
00:21:26,210 --> 00:21:28,630
Algoritmoa proposatu zen duela une bat izan zen, zergatik ez konparatu besterik ez dugu

359
00:21:28,630 --> 00:21:31,970
folks diren mota bata bestearen ondoan eta, ondoren, konpondu akatsak edozein

360
00:21:31,970 --> 00:21:33,540
ezkerretik eskuinera mugituz.

361
00:21:33,540 --> 00:21:36,580
Beraz, hemen, 4 eta 2 dugu, jakina, ordena. Dezagun swap duzu. Ongi da.

362
00:21:36,580 --> 00:21:40,760
Beraz, lerro behera noa. 4 eta 6, Laguia. [Barreak]

363
00:21:40,760 --> 00:21:45,010
6 eta 8, pretty good. 8 eta 1, utzi duzu swap me guys. Guztiak eskubidea.

364
00:21:45,010 --> 00:21:48,030
8 eta 3 Beraz, swap duzu guys.

365
00:21:48,030 --> 00:21:52,280
8 eta 7, utzi duzu swap me guys. 5 eta 8, bikaina.

366
00:21:52,280 --> 00:21:54,820
Ematen dizut horrela antolatu zerrenda bat.

367
00:21:54,820 --> 00:21:56,860
Guztiak eskubidea. Beraz, ez da nahiko.

368
00:21:56,860 --> 00:22:01,180
Baina hobe da handiagoa zenbakiak delako kasuan puntu 8 -

369
00:22:01,180 --> 00:22:04,030
dute mota bubbled ezker eskuinera.

370
00:22:04,030 --> 00:22:08,010
Beraz, horietako 1 got diot, baina sentitzen atsegin dute hau ez da nahiko arazoa konpontzen.

371
00:22:08,010 --> 00:22:11,150
>> Beraz, zer egingo zenuke hurrengo egiten dugu proposatzen duzu? >> [Ikasleak] Mantendu egiten. >> Egiten jarraitu dugu.

372
00:22:11,150 --> 00:22:13,740
Eta konturatzen, berriz, gauzak dugu gizakietan guztiak izatea

373
00:22:13,740 --> 00:22:17,180
sort adimentsuan antolatu bere burua argazki horretan oinarritzen da,

374
00:22:17,180 --> 00:22:19,040
baina gaur egun askoz ere metodikoa izan behar dugu.

375
00:22:19,040 --> 00:22:21,510
Buruzko algoritmikoak kodea izango bagina bezala ari gara idazten ditugu

376
00:22:21,510 --> 00:22:23,520
kasu honetan, hitzezko pseudocode.

377
00:22:23,520 --> 00:22:26,040
Hargatik saiatu berriro. Hori lan egin nahiko ongi. Ez da konpondu.

378
00:22:26,040 --> 00:22:30,400
Baina zalantzan jartzen denean, saiatu eta saiatu berriro. Hori dela eta, 2 eta 4, ez da laguntza gehiago.

379
00:22:30,400 --> 00:22:33,200
4 eta 6. Ah! 6 eta 1, apur bat hobeto gaur egun.

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

381
00:22:39,740 --> 00:22:44,060
Eta badakizu, ziurrenik ezin dut ignore 8 zerrendaren amaieran zuen delako.

382
00:22:44,060 --> 00:22:47,250
Agian ez dugu hura igaroz norbait kezkatu.

383
00:22:47,250 --> 00:22:49,240
Baina ikus dezagun suposizio bat dela segurua bada.

384
00:22:49,240 --> 00:22:52,340
Orain zerrenda - madarikatua ez ordenatuko. Dezagun saiatu berriro.

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

386
00:22:56,440 --> 00:22:59,230
4 eta 6, ona da. 6 eta 5, ona da.

387
00:22:59,230 --> 00:23:04,890
6, 7 eta 8, ona da. Baina oharra, ezin gelditu besterik ez dut hemen gelditu eta hemen orain?

388
00:23:04,890 --> 00:23:07,770
[Ikasleak] Bai. >> Bai?

389
00:23:07,770 --> 00:23:11,160
Zer duzu bat izan bada, kopurua 9 han?

390
00:23:11,160 --> 00:23:13,640
Izan ordenatuko da. >> Good. Izana litzateke horrela antolatu lehenengo aldiz inguruan.

391
00:23:13,640 --> 00:23:16,050
Good. Beraz, goazen berriro. Ia ez gara.

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

393
00:23:22,800 --> 00:23:26,640
>> Egin dut, gaur egun, baina, berriro ere, ordenagailu bat besterik ezin da egin, zer egin dut kontatu dut,

394
00:23:26,640 --> 00:23:30,120
eta nire oroitzapena bakarra da, benetan dut lan apur bat egin zuten.

395
00:23:30,120 --> 00:23:31,700
Zerbait aldatu hemen.

396
00:23:31,700 --> 00:23:37,100
Beraz, ez dut teknikoki baieztatu ikusmen edo algorithmically zerrenda hori horrela antolatu da, hain zuzen ere.

397
00:23:37,100 --> 00:23:40,720
Beraz, neurri ona, besterik gabe, honi buruz anal izan, egin dezagun, une honetan 1 gehiago.

398
00:23:40,720 --> 00:23:44,040
Beraz, 1 eta 2, 2 eta 3, 3 eta 4. Eta zer ezagutzen duzu?

399
00:23:44,040 --> 00:23:46,190
Just neurri ona, segimendua egiteko, une honetan, nire eskua dut

400
00:23:46,190 --> 00:23:51,110
zenbat trukeak besterik ez beraz, ezagutzen dut zenbat lan egiten dut benetan egiten dut.

401
00:23:51,110 --> 00:23:56,930
3 eta 4, 4 eta 5, 5 eta 6, 6 eta 7, 7 eta 8. Trukeak No.

402
00:23:56,930 --> 00:24:00,800
Beraz, orain legitimoa nuke lelo hau berriro egin

403
00:24:00,800 --> 00:24:03,330
gabe lan egin nuen Gizatiarrak pass honen bidez ere,

404
00:24:03,330 --> 00:24:06,710
ondoren, argi eta garbi hori berriro gertatuko da horietako bat ere ez da sort ausaz bada

405
00:24:06,710 --> 00:24:10,410
adversarially bere burua mugitzen inguruan. Beraz, gaur egun gelditu ezin dut.

406
00:24:10,410 --> 00:24:15,120
Orain dezagun galdera galdetu, zenbat lan egin zuen hau benetan hartu nahi?

407
00:24:15,120 --> 00:24:18,260
Zenbat urratsak ez hartzeko? >> N karratu.

408
00:24:18,260 --> 00:24:20,400
Bai, eta, beraz, n karratu. Nora egin n karratu lortu duzu?

409
00:24:20,400 --> 00:24:22,660
Num bakoitzean egiaztatu behar duzu

410
00:24:22,660 --> 00:24:26,530
Dago n zenbakiak, eta zenbaki bakoitzaren ikusteko n beste zenbakiak.

411
00:24:26,530 --> 00:24:29,030
Good. >> Beraz, karratu n. >> Good.

412
00:24:29,030 --> 00:24:31,060
>> Beraz, izan bezala oso ondo egon n karratu, eskuinera sentitzen da?

413
00:24:31,060 --> 00:24:33,820
Guys horiek. N, 8, bereziki kasu honetan,

414
00:24:33,820 --> 00:24:37,590
baina denbora Zerrenda honen bidez joan nintzen bakoitzean bigarren aurkako lehen pertsonan nintzen alderatuz,

415
00:24:37,590 --> 00:24:39,650
hirugarren aurka bigarren berriro, eta behin eta berriro,

416
00:24:39,650 --> 00:24:42,450
eta noiz, azkenean lortu dut, zer egin dezaket? Redid dut.

417
00:24:42,450 --> 00:24:46,280
Beraz, oro har, azalpen hau bada, pertsona dugu n

418
00:24:46,280 --> 00:24:51,090
eta, naiz egiten, jakina, 8 urratsak, n urrats algoritmo honen bidez, denbora guztietan.

419
00:24:51,090 --> 00:24:56,070
Baina zenbat aldiz kasurik okerrenean pertsonen zerrenda honen bidez joan egin behar dut?

420
00:24:56,070 --> 00:24:59,370
[Ikasleen] N aldiz. >> Seguruenik n, eskuinera, kasurik okerrenean ere,

421
00:24:59,370 --> 00:25:03,410
zer da, ziur aski, guys horiek kasuan txarrena antolaketa-get joan?

422
00:25:03,410 --> 00:25:06,520
Erabat ari dira bada alderantzikatu

423
00:25:06,520 --> 00:25:09,310
besterik ez delako demagun mentalki, let's - Zein da zure izena? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Ongi da. Horrela, Bowen, une bat besterik ez hona etorri.

425
00:25:12,510 --> 00:25:16,150
>> Demagun Bowen hemen algoritmoa hasieran izan zela,

426
00:25:16,150 --> 00:25:19,790
eta ez dakigu zer Besteek, baina Bowen hemen, algoritmoa honen arabera

427
00:25:19,790 --> 00:25:23,820
eta nirekin ibili nahi izanez gero, burbuila sortu da, lehen aldiz egin zuen inguruan,

428
00:25:23,820 --> 00:25:25,740
amaieran.

429
00:25:25,740 --> 00:25:29,400
Baina demagun ondoan Bowen pertsona kopurua 7 izan zen.

430
00:25:29,400 --> 00:25:33,450
Atzera joan eta 7, eta horrek esan nahi du modu guztiak joan itzuli behar dut hemen daukat.

431
00:25:33,450 --> 00:25:36,980
Orain ibilaldi hori bera izan duen pertsona kopurua 7 daukat.

432
00:25:36,980 --> 00:25:40,140
Baina zer gertatzen da gero, multzoko 6 zion ondoan izan baita?

433
00:25:40,140 --> 00:25:42,180
Ondoren, atzera joan eta 6 lortu behar dut.

434
00:25:42,180 --> 00:25:46,490
Beraz, berriro ere, begizta honen iterazio guztietan n pertsona bakoitzari ari naiz,

435
00:25:46,490 --> 00:25:50,090
eta n egiteko ibilaldi horien ziurtatu dio dut

436
00:25:50,090 --> 00:25:53,760
elementu handiena itzuli eta itzuli eta itzuli zerrendaren bukaeran oso guztiak.

437
00:25:53,760 --> 00:25:58,230
Beraz, gauza n n aldiz n aldiz n edo n karratu da.

438
00:25:58,230 --> 00:26:02,050
>> Hortaz, hona hemen dagoeneko algoritmo bat jada ez n, no longer log n dugu,

439
00:26:02,050 --> 00:26:04,820
benetan ezer egin dugu aurretik baino okerragoa da.

440
00:26:04,820 --> 00:26:09,840
Beraz, Alex mota lortu zortea duten lana itxuraz bere aurrean egin nuen,

441
00:26:09,840 --> 00:26:14,690
garestiak lan guztiak, beraz, bilaketa bitarraren algoritmoa gozatu ahal izan zuen,

442
00:26:14,690 --> 00:26:16,420
n erregistroa da.

443
00:26:16,420 --> 00:26:18,240
Baina hori koherentea da astelehenetik gaia.

444
00:26:18,240 --> 00:26:23,260
Pixka bat eman dugu, leku gehiago, bit gehiago erabili dugu, gure denborak azkartzeko.

445
00:26:23,260 --> 00:26:26,170
Beraz, askoz ere denbora eta espazioaren arteko merkataritza-off bezala,

446
00:26:26,170 --> 00:26:31,060
ditzake merkataritza-offs denbora arteko gauzak joan prest lortzean sort aurrean

447
00:26:31,060 --> 00:26:35,000
eta benetan bilaketa bezalako algoritmo bat exekutatzen ari da. Dezagun saiatu beste bat.

448
00:26:35,000 --> 00:26:39,050
You guys axola ez balu, besterik ez azkar rearranging dator zuei berriro,

449
00:26:39,050 --> 00:26:42,240
utzi saiatu zerbait pixka bat desberdinak non ere ez da oso erraza

450
00:26:42,240 --> 00:26:45,760
bezala konpondu pairwise akatsak, hau da, super intuitiboa.

451
00:26:45,760 --> 00:26:48,150
Dezagun ordez apur bat gehiago nahita eta hau egin.

452
00:26:48,150 --> 00:26:51,010
Da, ziur aski, hau ere proposatuko nuke nahiko intuitiboa.

453
00:26:51,010 --> 00:26:55,070
>> Zerrendako pertsona txikiena hautatu dadila behin eta berriro. Beraz, hemen goaz.

454
00:26:55,070 --> 00:26:57,350
4, txikiena pertsona horrela ikusi dut hain urruti zaude,

455
00:26:57,350 --> 00:27:00,520
beraz, adimen-gogoratu besterik ez duzu orain seinalatu noa.

456
00:27:00,520 --> 00:27:05,020
2. Ooh! Ahaztu multzoko 4. Aurkitu dut zerrenda honetan elementu berriak txikiena.

457
00:27:05,020 --> 00:27:07,410
Mota gogoratu dut. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ooh! 1. Goodbye. Beraz multzoko 1 gogoratzen dut.

459
00:27:11,190 --> 00:27:14,790
1 txikiena dugu ezagutzen,, baina ordenagailua naiz. Zer badago, 0 bat?

460
00:27:14,790 --> 00:27:17,140
Zer badago -1 bat? Jarraitzeko behar dut.

461
00:27:17,140 --> 00:27:20,990
Beraz, 3, 7, 5, Laguia. Ongi da. Multzoko 1 Beraz, txikiena izan zen.

462
00:27:20,990 --> 00:27:23,640
Duzun me zerrenda - we'll joan Modu honetan

463
00:27:23,640 --> 00:27:27,760
eta jarri arbitrarioki zerrendaren hasieran.

464
00:27:27,760 --> 00:27:29,740
Orain, minutu bat itxaron. Mota cheated dut.

465
00:27:29,740 --> 00:27:34,010
Guys horiek ordezkatzen 8 pertsonek ez da zerrenda, baina array bat bada,

466
00:27:34,010 --> 00:27:37,050
Eta 8 memoria Elkarren ondoko zatiak ez atzera hurrats axola, une bat besterik ez duzu?

467
00:27:37,050 --> 00:27:39,060
Ez, egia esan, ez duzu espazio hemen.

468
00:27:39,060 --> 00:27:41,840
Beraz, nola egin espazio egin dugu - Zein da zure izena? >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
Nola espazio egin dugu Sammy?

470
00:27:43,710 --> 00:27:46,760
>> N me aurretik mugitzen dugu. >> Ados.

471
00:27:46,760 --> 00:27:48,850
Beraz, n duten pertsonen haren aurrean mugitu ahal izan genuen,

472
00:27:48,850 --> 00:27:52,400
baduzu guys nahi 1 nahita, dramatikoa ezkerrera urrats.

473
00:27:52,400 --> 00:27:57,000
Egin ziren denak batera, baina azken aldian kodea idatzi nuen,

474
00:27:57,000 --> 00:27:59,740
ezin duzu ordenatzeko mugitzeko gauza asko aldi berean.

475
00:27:59,740 --> 00:28:02,450
Egin izan dugu begizta batean, denok mugitzen aldi berean behin.

476
00:28:02,450 --> 00:28:04,340
Beraz, baduzu guys ez litzateke axola hurrats eskuinera,

477
00:28:04,340 --> 00:28:07,230
eta Sammy, atzera urratsa bada izan oraindik ez da gela ez dela,

478
00:28:07,230 --> 00:28:11,420
gaur egun egin dezagun hau. Non izan zen Sammy Duela momentu bat? Eskuin dago.

479
00:28:11,420 --> 00:28:16,140
Beraz, hutsune bat dago. Beraz, Sammy bere Leku mugitu ahal izango duzu.

480
00:28:16,140 --> 00:28:20,580
Orain hurrengo pertsona eta, gaur egun, hurrengo pertsona, orain hurrengo pertsona. Orain, Sammy gela ditugu.

481
00:28:20,580 --> 00:28:23,490
Orain, ikusleek norbait ona zen, zuzena zen,

482
00:28:23,490 --> 00:28:27,070
da denbora-kontsumitzen apur bat sentitzen - Zer da azkarragoa? Bai.

483
00:28:27,070 --> 00:28:29,440
[Ikasleak] array berri bat? >> Zer da hori? >> [Ikasleak] array berri bat? >> Ongi, ona da.

484
00:28:29,440 --> 00:28:33,200
>> Beraz, besterik gabe, merkataritza-offs gai honekin koherentea, zergatik ez egin dut array bat berria

485
00:28:33,200 --> 00:28:36,570
 eta, ondoren, pertsona horien aurrean espazio Sammy egingo da, igeriketa, adibidez,

486
00:28:36,570 --> 00:28:39,600
eta bakarrik hasi ahal izango dugu array bat beteko guztira. Hau ere lan egiten dute.

487
00:28:39,600 --> 00:28:42,450
Baina ez dut leku gehiago gastatzea gaur egun interesa. Zer da hurbilketa bat da?

488
00:28:42,450 --> 00:28:46,630
[Ikasleak] Swap. >> Ados. 2 guys horiek bakarrik izan dugu trukatu. Zein da zure izena?

489
00:28:46,630 --> 00:28:49,390
Mario. >> Mario. Mario Beraz, gaur egun, hemen duzu.

490
00:28:49,390 --> 00:28:52,480
Sammy, babeskopia une bat besterik ez? Mario izan zen hemen.

491
00:28:52,480 --> 00:28:55,830
Ez dugu zure gela gehiago, beraz, ez bada nahi duzun axola non Sammy joan

492
00:28:55,830 --> 00:29:02,430
Sammy jarri dugu hemen, eta, orain, argudiatzeko Sammy aldaketa eragiketa zela askoz azkarrago nuke.

493
00:29:02,430 --> 00:29:06,370
1 eragiketa egin dugu guys horiek trukatu, edo agian 2 guys horiek trukatu,

494
00:29:06,370 --> 00:29:11,210
baina ez dugu 1, 2, 3, 4, eta, beraz, hori sentitzen hobea. Orain, minutu bat itxaron.

495
00:29:11,210 --> 00:29:14,660
Egin mota I arazoa okerragoa kopurua 4 mota izan zen hasiera-hasieratik hurbil delako.

496
00:29:14,660 --> 00:29:19,470
Orain multzoko 4 Horretarako, apur bat hurbilago, baina ez dakit edo horri buruzko zaintzeko.

497
00:29:19,470 --> 00:29:23,330
Beraz, zorte txarra hori da zenbakia 4 dela apur bat urrunago bere lekua helburu.

498
00:29:23,330 --> 00:29:25,110
Hargatik errepikatu algoritmoa.

499
00:29:25,110 --> 00:29:28,410
>> , Laburpena, betiere, istorioa bezala, guztiek izan zen genuen zerrendan zehar oinez

500
00:29:28,410 --> 00:29:31,130
zenbakidun txikiena pertsona bila.

501
00:29:31,130 --> 00:29:34,530
Beraz, gaur egun egin dezagun berriro. Ez dugu Sammy kezkatu gehiago.

502
00:29:34,530 --> 00:29:37,590
Bakarrik joan ahal izango dugu hemen. Ooh! Multzoko 2. Hori nahiko kopuru txiki bat da.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. Ongi, ona da.

504
00:29:41,180 --> 00:29:43,770
Eta zorionez, kasualitatez, ez dut mugitu - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie zuen bere tokia eskuin delako orain.

506
00:29:45,910 --> 00:29:48,110
Egin dezagun berriro, eta 2 guys horiek alde batetara utzi.

507
00:29:48,110 --> 00:29:50,460
6. Hori nahiko kopuru txiki bat da. Ooh! 8 izango da, zalantzarik gabe handiagoa da.

508
00:29:50,460 --> 00:29:53,410
4. Dezagun 4 ardatz. Ooh! 3 are hobeto.

509
00:29:53,410 --> 00:29:58,290
7 eta 5. Beraz, zer egiten dugu - >> Roger. >> Roger?

510
00:29:58,290 --> 00:30:00,250
Dezagun swap bere multzoko 6.

511
00:30:00,250 --> 00:30:03,570
Beraz, 6 eta 3 trukatu nahi nuke,

512
00:30:03,570 --> 00:30:07,320
dugu mota horretako ahaztuak 6 non egon behar zuen hurbiltzen da zortea,

513
00:30:07,320 --> 00:30:10,300
baina besterik ez da kasualitate hutsa hemen. Hargatik sartu hemen.

514
00:30:10,300 --> 00:30:13,430
8 pretty kopuru txiki bat da. Ooh! 4 txikiagoa da.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. Zer egiten dugu? >> Swap. >> Zehazki.

516
00:30:17,130 --> 00:30:19,010
Beraz, gaur egun egin dezagun azkarrago sort honetan.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. Non ez 5? Good. Ongi da.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 lortzen zuen lo. Zein da zure izena? >> Rosalie.

519
00:30:28,380 --> 00:30:31,770
Rosalie lortzen zuen lo. 7 lortzen - Ikus dezagun. 7, 8. Ongi da.

520
00:30:31,770 --> 00:30:35,100
Beraz, 7 lortzen, bertan lo. Zein da zure izena? >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> Beraz, Amna lortzen, bertan lo egin, eta multzoko 8. Da jada non egin behar zuen izan.

522
00:30:39,670 --> 00:30:43,960
Ongi, ona da. Sentitzen ari garen bezala, geure buruari lana sortzea hemen, baina.

523
00:30:43,960 --> 00:30:47,440
Zer da, azken finean, algoritmo honen iraupena?

524
00:30:47,440 --> 00:30:51,900
Ez 8 gisa, baina n gisa pertsona hauei buruzko uste baduzu? >> N da.

525
00:30:51,900 --> 00:30:55,440
Urratsak n, baina aldi bakoitzean bakarra egiaztatzen ari gara.

526
00:30:55,440 --> 00:30:57,570
Ongi da. N, baina aldi bakoitzean bakarra markatuta ari?

527
00:30:57,570 --> 00:31:03,450
Ados, baina, urrats bat ematen badu n, ez luke izan dut ordenatzeko besterik ez joan 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
Oh! Ados, diferentzia handi bat da.

529
00:31:05,590 --> 00:31:08,050
Beraz, n karratu zergatik? Zer da benetan gertatzen da?

530
00:31:08,050 --> 00:31:12,130
N zerrenda honetan jendea dago, baina zerrendan pertsona txikiena aurkitu

531
00:31:12,130 --> 00:31:16,200
kasu horretan, txarrena, zenbat urrats hartu behar dut? >> N.

532
00:31:16,200 --> 00:31:19,160
>> N, eskuinera, kasurik okerrenean, multzoko 1. Delako han modu guztiak, hau da,

533
00:31:19,160 --> 00:31:20,990
beraz lortzeko bere joan behar dut.

534
00:31:20,990 --> 00:31:25,500
Eta orduan konturatzen, azkenik, I 1 txikiena zen eta, ondoren, nahiko azkarra da horietako swap.

535
00:31:25,500 --> 00:31:28,450
Baina orain, hasieratik hasteko eta nor bilatzeko behar dut?

536
00:31:28,450 --> 00:31:31,980
Hurrengo txikiena pertsona, hau da, 2. Non kasuan, txarrena 2?

537
00:31:31,980 --> 00:31:34,320
Oh, ene Jainkoa. Hemen modu amaieran da.

538
00:31:34,320 --> 00:31:37,000
Beraz, orain, beste urrats n, n urrats beste egiten dut.

539
00:31:37,000 --> 00:31:41,200
Eta dugu got bada, n pertsona eta kasu horretan, txarrena da pertsona txikiena n urratsak kanpoan,

540
00:31:41,200 --> 00:31:45,230
hori berriro n aldiz-n, eta, beraz, berriro dugu karratu n.

541
00:31:45,230 --> 00:31:47,280
Hau ez da, beraz, eta oso ondo sentitu naiz.

542
00:31:47,280 --> 00:31:52,150
Eta, hain zuzen ere, nahiz eta, kasu horretan, onena demagun off hasten direla ordenatuko

543
00:31:52,150 --> 00:31:59,080
zenbat urrats ez algoritmo hau erabiltzeagatik n pertsona horiek ordenatzeko?

544
00:31:59,080 --> 00:32:01,010
N karratu. >> N entzun nuen karratu. Zergatik karratu n?

545
00:32:01,010 --> 00:32:05,240
Duzu aldi bakoitzean bakarra dela ikusteko. >> Bai.

546
00:32:05,240 --> 00:32:08,060
Eta haien trukatu behar duzu. >> Nahiz eta gizakiak omniscient mota

547
00:32:08,060 --> 00:32:10,770
zentzu begien besterik gabe, hori horrela antolatu mota dugu,

548
00:32:10,770 --> 00:32:12,140
ordenagailu bat ez da smart.

549
00:32:12,140 --> 00:32:14,040
Eta hemen, hemen eta hemen begiratu,

550
00:32:14,040 --> 00:32:16,610
baina zer da bilatzen elementu txikiena bada,

551
00:32:16,610 --> 00:32:22,110
bakarrik ezagutzen duzu zein puntu elementu txikiena aurkitu duzula? Behin Oraindik amaieran.

552
00:32:22,110 --> 00:32:25,880
Baina puntu horretan bakarrik aurkitu dituzun elementu gaur egun txikiena.

553
00:32:25,880 --> 00:32:28,810
Ez duzu nahitaez munduko egoerari buruz beste ezer ezagutzen.

554
00:32:28,810 --> 00:32:30,880
Beraz, behin eta berriro eta berriro joan behar duzu.

555
00:32:30,880 --> 00:32:34,880
>> Une honetan ez dut begiratu muda Beraz, dut, ados, izan ere, egiaztapena 2, txikiena bazaude,

556
00:32:34,880 --> 00:32:37,530
baina ez dakit hori guztira oraindik.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Ongi, ona da. 2 izan zen, hain zuzen ere txikiena.

558
00:32:41,090 --> 00:32:43,150
Aurki dezagun hurrengo txikiena. Ongi da.

559
00:32:43,150 --> 00:32:48,350
3, gaur egun Oraindik duzu txikiena. Ikus dezagun. 4, 5, 6, 7, 8. Ongi da, baina zortea berriro.

560
00:32:48,350 --> 00:32:53,170
3 izan zen, hain zuzen ere, leku egokian. Baina hau egiteko berriz, eta behin eta berriro mantentzeko noa.

561
00:32:53,170 --> 00:32:55,990
Nola egin dezaket inoiz beraz apur bat hobea egiten dugu?

562
00:32:55,990 --> 00:33:00,120
Horren ordez pertsona burbuila dutela pairwise txikiena etatik handiena

563
00:33:00,120 --> 00:33:04,350
eta horren ordez, atzera eta aurrera joan ondoren txikiena pertsona hautatzen zerrenda bidez,

564
00:33:04,350 --> 00:33:09,780
zergatik ez sartu ordez pertsona horiek zerrenda urrats berri bat sartu paso?

565
00:33:09,780 --> 00:33:13,080
Dezagun saiatu honekin. Dezagun gauza txertatzeko sort hau deitu me.

566
00:33:13,080 --> 00:33:17,250
Beraz, hemen hemen gaude. Número: 1. Inork zerrenda honetan ez dut axola.

567
00:33:17,250 --> 00:33:21,310
Nire helburua oraintxe multzoko 1 ordenatuko zerrenda baten hasieran jartzen da.

568
00:33:21,310 --> 00:33:23,910
Eta proposatzen dut 8 memoria zatiak besterik ez dut geroztik,

569
00:33:23,910 --> 00:33:28,670
arbitrarioki oraintxe nire zerrenda ustez Unsorted arteko horma naiz,

570
00:33:28,670 --> 00:33:32,740
eta edonork me atzean erreklamatzeko noa ordenatuko da.

571
00:33:32,740 --> 00:33:34,680
Beraz, gaur egun zenbaki 1 behar dugu.

572
00:33:34,680 --> 00:33:39,240
Nire zerrenda ordenatuko sartu zion txertatzeko nahi dut, besterik ez naiz hemen baino gehiago nire hormara mugitzeko, beraz,

573
00:33:39,240 --> 00:33:43,930
eta zerrenda hori horrela antolatu aldarrikatzen dut, zerrenda honetan Unsorted - gutxienez, beraz, urruti ezagutzen dudan bezala.

574
00:33:43,930 --> 00:33:46,070
Zenbaki guztiak ikusi ezin dut aldi berean.

575
00:33:46,070 --> 00:33:49,000
>> Orain multzoko 2 topo gertatuko dut. Zer egin dut berarekin?

576
00:33:49,000 --> 00:33:54,380
Sartu naiz ordenatzen du zerrenda. Baina konturatu nola erraza izan zen.

577
00:33:54,380 --> 00:33:59,650
Besterik ez dut begiratzen. Zenbakia 1 dago. Oh, jakina, 2 multzoko 1. Alde doa.

578
00:33:59,650 --> 00:34:03,700
Orain zer egiten dut 3? Sartu dut ordenatzen du zerrenda. Baina hori super erraza izan zen.

579
00:34:03,700 --> 00:34:07,250
Super erraza, hau da super erraza, erraza super, super erraza, super erraza da.

580
00:34:07,250 --> 00:34:12,790
Eta orain dena da me atzean ordenatuta, eta zenbat urrats ez hartzen?

581
00:34:12,790 --> 00:34:15,620
[Ikasle] N. >> Beraz, soilik n. Zortea lortu dugu.

582
00:34:15,620 --> 00:34:18,860
Bakarrik n zergatik izan da? >> [Ikasleak] zerrenda zen horrela antolatu delako.

583
00:34:18,860 --> 00:34:21,630
Zerrenda dagoeneko ordenatuko da. Beraz, zortea ginen.

584
00:34:21,630 --> 00:34:25,639
Baina algoritmo bat diseinatu dugu denbora hori zorte mota horretako harnesses

585
00:34:25,639 --> 00:34:29,420
kasu horretan onena agertokia, ez alferrikako denborarik galdu.

586
00:34:29,420 --> 00:34:31,750
Beraz, gaur egun zer burbuila-era askotako deitu dugu,

587
00:34:31,750 --> 00:34:33,949
non pertsonek pairwise sortu bubble mota.

588
00:34:33,949 --> 00:34:38,100
Orain aukeraketa sort non pertsona txikiena pluck dugu behin eta berriro.

589
00:34:38,100 --> 00:34:42,350
Eta orain txertatzeko sort dugu non jarri sort-proaktiboan dugu jendea non sartzen dira

590
00:34:42,350 --> 00:34:45,000
gero ordenatuko zerrendan.

591
00:34:45,000 --> 00:34:49,679
Ezin izan bada, hemen guys horiek txalo txanda. [Txalo]

592
00:34:49,679 --> 00:34:52,310
Dezagun gure 5 minutuko break hemen.

593
00:34:52,310 --> 00:34:55,139
Eta itzuli gara, algoritmoak horiek guztiak kolpe egingo dugu ur-out

594
00:34:55,139 --> 00:35:00,260
zerbait hobea. Guztiak eskubidea. Eskerrik asko asko. Oroigarri gisa gorde dezakezu.

595
00:35:01,710 --> 00:35:04,330
Guztiak eskubidea. Itzuli gara.

596
00:35:04,330 --> 00:35:08,420
>> Eta benetako azkar laburpena, 3 ezberdinak izan genuen ikuspegi horien arabera ordenatzeko,

597
00:35:08,420 --> 00:35:13,000
horietatik puntu osoa izan zen puntua lortu non Alex bezalako norbait

598
00:35:13,000 --> 00:35:16,930
zenbakiak azkarrago zerrenda bat bilatu Sean Could bezalako norbait baino.

599
00:35:16,930 --> 00:35:19,830
Eta, besteak beste, nahiz eta 8 zenbakiak adibide simple dugu,

600
00:35:19,830 --> 00:35:24,000
erraz 8 web-orriak, 8 milioi web orrialde estrapolatu ahal izango duzu,

601
00:35:24,000 --> 00:35:26,680
edo Facebook-en 800 milioi lagun.

602
00:35:26,680 --> 00:35:30,090
Beraz, algoritmo horiek, zalantzarik gabe, balio mota horiek eskalatzeko,

603
00:35:30,090 --> 00:35:32,300
eta ideiak dira, azken finean, gauza bera da.

604
00:35:32,300 --> 00:35:36,140
Burbuila lehen Beraz sort non bubbled mota dugu pertsona handiena

605
00:35:36,140 --> 00:35:39,110
eskuineko bidea pertsonek aldaketa pairwise.

606
00:35:39,110 --> 00:35:42,040
Ondoren, aukeraketa sort deitu dugu non apur bat gehiago nahita izan genuen

607
00:35:42,040 --> 00:35:46,480
mantendu zerrendan zehar joan, bilatzen kopurua txikiena hautatuz behin eta berriro, eta berriro,

608
00:35:46,480 --> 00:35:49,530
emaitza logikoa da zerrenda hori azkenean horrela antolatu.

609
00:35:49,530 --> 00:35:53,780
Gero, hirugarren batean, pertsona txertatuko dut leku egokia da,

610
00:35:53,780 --> 00:35:57,720
eta oso contrived adibide bat zerrendan dagoeneko horrela antolatu genuen,

611
00:35:57,720 --> 00:36:01,100
baina hori izan zen mezua bidali txertatzeko sort kasu horretan,

612
00:36:01,100 --> 00:36:02,670
lortzeko zortea dezakezu.

613
00:36:02,670 --> 00:36:07,930
Zenbakiak ordenatuko dira dagoeneko bada, besterik ez da n urratsak askoz ere berretsi du,

614
00:36:07,930 --> 00:36:10,870
aukeraketa sort, berriz, apur bat gehiago tunel ikuspegia Oraindik

615
00:36:10,870 --> 00:36:14,360
eta ez duzu inoiz konturatzen zerrenda ordenatuko dagoeneko.

616
00:36:14,360 --> 00:36:16,830
Beraz, ikus dezagun burbuila ekintza sort hemen.

617
00:36:16,830 --> 00:36:19,590
Ondorengo adibidez, barra bertikalak ikusteko gaude

618
00:36:19,590 --> 00:36:23,030
horren altuera adierazten da, beraz, ikusteko gertatuko ordenatzeko ordenatzeko dezakegu.

619
00:36:23,030 --> 00:36:26,630
Txikiagoa bar, zenbaki txikiagoa; handiagoa barra, kopurua handiagoa.

620
00:36:26,630 --> 00:36:28,860
>> Eta jolastu dugu default abiadura honetan.

621
00:36:28,860 --> 00:36:33,460
Orain little azkar mugitu da, baina gorria da zer 2 taberna erakusten

622
00:36:33,460 --> 00:36:35,480
ari aldean alboan.

623
00:36:35,480 --> 00:36:39,520
Eta ikusten duzu lotura estua bada, zer gertatzen da, tabernak dira ordena,

624
00:36:39,520 --> 00:36:42,300
txikiago bat lortzen ezkerrera mugitu, eskuinera bat handiagoa,

625
00:36:42,300 --> 00:36:44,360
eta, ondoren, aurrera mantentzeko.

626
00:36:44,360 --> 00:36:48,520
Beraz, egiten dugu behin eta berriro, konturatu taberna txikiena

627
00:36:48,520 --> 00:36:51,090
beraien bidean ezkerrera inching mantentzeko

628
00:36:51,090 --> 00:36:54,130
eta taberna handiena beraien bidean eskuinera inching mantentzeko.

629
00:36:54,130 --> 00:36:58,490
Eta, hain zuzen ere, eredu bat ikusten ari gara eskuinaldean modu hasita

630
00:36:58,490 --> 00:37:04,790
8 bezala ikusi dugu, eta, ondoren, 7 azkenean bubbling gure zerrendan giza amaiera urrun.

631
00:37:04,790 --> 00:37:08,750
Beraz, hau da, oso azkar pixka bat lapurtera, eta, beraz, utzi hau gelditzeko une batez.

632
00:37:08,750 --> 00:37:10,980
Dezagun abiadura aldatzeko me askoz azkarrago.

633
00:37:10,980 --> 00:37:15,380
Ez dut algoritmoa aldatu, besterik ez dut animazioa gertatuko azkarrago egiteko.

634
00:37:15,380 --> 00:37:18,410
Oraindik burbuila sort, algoritmoa bera,

635
00:37:18,410 --> 00:37:21,910
baina gaur egun askoz ere azkarrago ikusi ahal izango duzu gure manifestazio hitzezko baino

636
00:37:21,910 --> 00:37:25,900
handiena duten elementuak dira, hain zuzen ere goiko bubbling.

637
00:37:25,900 --> 00:37:29,860
>> Bat alde batera utzita, beheko ezkerreko laukiak txiki eta eskubide horiek beheko

638
00:37:29,860 --> 00:37:33,520
besterik ez dira zenbat konparazioak egiten ari zaren gogorarazleak txiki.

639
00:37:33,520 --> 00:37:37,620
Baina orain, piramide forma duen hartu ahal izango dugu pilatzen dira, eta ez da doan.

640
00:37:37,620 --> 00:37:41,510
Ezkerreko, eskuineko handiena, eta beste guztia artean elementu txikiena da.

641
00:37:41,510 --> 00:37:44,470
Orain dezagun ordez aukeraketa sort begirada bat hartu.

642
00:37:44,470 --> 00:37:47,260
Aurretik joan eta Stop sakatu dut. Taberna ausazko multzoa iritsi gara.

643
00:37:47,260 --> 00:37:50,930
Aukeraketa ordenatu, abisuaren, zerrendan zehar doa berriro, eta behin eta berriro,

644
00:37:50,930 --> 00:37:54,900
plucking elementu txikiena. Hortaz, hona hemen aukeraketa sort da.

645
00:37:54,900 --> 00:37:58,390
Itxura ez du bere lana gutxiago gaur egun gertatzen ari den bezala da, ez delako ari gara pairwise alderatuz

646
00:37:58,390 --> 00:38:02,590
baina ari gara gerezi eskubidea elementuak txikiena aukeratzea ezkerrera ordenatzeko.

647
00:38:02,590 --> 00:38:06,890
Oso denbora gutxi izan zen, eta, beraz, beraz, ez dikotomia bat da dagoeneko.

648
00:38:06,890 --> 00:38:11,820
Just delako algoritmo bat da, esan zuen, eta, denbora n karratu hartu, burbuila ordenatu bezala

649
00:38:11,820 --> 00:38:16,100
eta aukeraketa sort bezala, horiek dira benetan txarrena kasuan aldiz exekutatzen ari da.

650
00:38:16,100 --> 00:38:21,790
Esate baterako, kasuan, demagun, hautaketa ordena

651
00:38:21,790 --> 00:38:27,240
Actually I am pertsona txikiena hautatu eta bere jarriz hemen,

652
00:38:27,240 --> 00:38:29,620
ondoren, berriro egiten ari naiz, gero dut egiten ari da berriro,

653
00:38:29,620 --> 00:38:32,070
baina apur bat egin izan dut optimizazioa.

654
00:38:32,070 --> 00:38:35,040
>> 1 hemen bezain laster joan zen bizitzera I - Sammy kasu horretan

655
00:38:35,040 --> 00:38:38,630
zer egin berarekin hortik aurrera egin behar dut? >> [Ikasleak] Utzi zion.

656
00:38:38,630 --> 00:38:40,140
Utzi, ezta? Ezer ez.

657
00:38:40,140 --> 00:38:44,310
Ez dut inoiz hitz Sammy berriro hautatu badituzu elementu txikiena izan dudalako

658
00:38:44,310 --> 00:38:48,580
eta hemen jarri zion, zergatik hondakinak denbora nire zerrenda osoa amaieran?

659
00:38:48,580 --> 00:38:54,590
Hurrengo iterazio On benetan mugitu me multzoko 2 bakarrik, bakarrik multzoko 3.

660
00:38:54,590 --> 00:38:57,640
Beraz, errealitatean, ez nintzen gauza n n aldiz egiten.

661
00:38:57,640 --> 00:39:05,380
1 gauzak, eta n - 2 gauzak, gero n - 3 gauza n gauzak, eta ondoren n egiten zen I

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

663
00:39:07,080 --> 00:39:09,470
Serie geometriko bat apur bat, besterik gabe, esan nahi ditugu

664
00:39:09,470 --> 00:39:11,450
gehitzen ari zaren pixkanaka txikiagoa zenbakiak.

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

666
00:39:17,940 --> 00:39:21,380
Eta zer esan, oro har, lanak izan

667
00:39:21,380 --> 00:39:24,280
Nahastea dut nire taula gora hemen une bat besterik ez -

668
00:39:24,280 --> 00:39:28,990
/ 2 - den lan n antzeko zerbait (1 n)

669
00:39:28,990 --> 00:39:31,930
besterik ez badugu begirada mota math book non Cheat orriak guztiak dituzula atzeko aldean

670
00:39:31,930 --> 00:39:33,410
formulak.

671
00:39:33,410 --> 00:39:37,760
Ari zaren besterik ez bada zerbait gehituz n + n - 1 + n - 2, berau hau atsegin zerbait izan behar duela.

672
00:39:37,760 --> 00:39:42,320
Eta gara mota biderkatu hau bada, hori karratu ken n / 2 n.

673
00:39:42,320 --> 00:39:46,400
N esaten karratu, nahiz eta mantendu dut, eta hori nintzen mota mental lasterbide bat hartu duelako

674
00:39:46,400 --> 00:39:51,950
errealitatean, n delako karratu minus n 2 arabera banatzen da, hain zuzen ere, urrats kopuru benetako

675
00:39:51,950 --> 00:39:55,510
aukeraketa sort bezala algoritmoa benetan zenbatuko dugu bada hartuko luke

676
00:39:55,510 --> 00:39:58,800
konparazioak horiek guztiak eta lanpetuta little lana egiten ari gara guztiak.

677
00:39:58,800 --> 00:40:03,210
Baina, Egia, behin n lortzen milioi bat edo milioi demontre zaintzen duten bezala

678
00:40:03,210 --> 00:40:07,160
ari zaren bat milioi karratu minus milioi 2 banatuta egiten bada?

679
00:40:07,160 --> 00:40:09,320
A milioi zenbaki karratu handi bat da.

680
00:40:09,320 --> 00:40:13,580
Beste milioi off hartu ahal izango duzu - n. Aurre handi bat, hala nola, ez da.

681
00:40:13,580 --> 00:40:18,770
Beraz, zenbakiak handiagoa lortzeko, hain garrantzitsua ordenatuan termino horiek txikiagoak dira.

682
00:40:18,770 --> 00:40:24,230
Nork zaintzen 2 zatitzen bada ari zaren urrats zenbakiak quadrillions buruz hitz egiten badugu?

683
00:40:24,230 --> 00:40:29,710
>> Beraz, oro har, ordenagailu zientzialari ohi gola botatzen guztia, baina epe handiena,

684
00:40:29,710 --> 00:40:33,140
eta errazteko besterik ez mota dugu munduaren eta esan algoritmoa,

685
00:40:33,140 --> 00:40:38,130
hartu zuen gutxi gorabehera n karratu urratsak. Algoritmo bat exekutatzen ari da.

686
00:40:38,130 --> 00:40:40,760
Beraz, itzuli dugu une bat besterik ez da hau hormigoizko adibide batzuekin,

687
00:40:40,760 --> 00:40:45,940
baina orain, intuitiboa motibazioa sort gure mundua sinplifikatuz atzean

688
00:40:45,940 --> 00:40:51,170
eta fancy formula horiek guztiak sartzeko beharrean baldintza garrantzitsuena buruz hitz egiten.

689
00:40:51,170 --> 00:40:53,540
Beraz, aukeraketa sort zen, eta pixka bat zortea genuen han.

690
00:40:53,540 --> 00:40:57,360
Dezagun txertatzeko sort begiratu. Dezagun aurrera eta hau hasteko baita.

691
00:40:57,360 --> 00:41:00,330
Orain konturatu ereduarekin gertatzen apur bat desberdina da,

692
00:41:00,330 --> 00:41:03,410
eta zenbakiak ausazko hasi dugu,

693
00:41:03,410 --> 00:41:06,890
baina benetan zenbatzen badituzu urratsen kopurua txarrena kasuan,

694
00:41:06,890 --> 00:41:11,070
zerrenda hasi zen erabat ordena egokian,

695
00:41:11,070 --> 00:41:13,380
n bakarrik nahi dugu urrats askoz ere konturatzen.

696
00:41:13,380 --> 00:41:18,240
>> Baina zerrenda ziren benetan bada atzeraka - Adibidez, hemen kasu honetan -

697
00:41:18,240 --> 00:41:23,860
ondoren nabarituko kasu honetan lan asko egin behar izan dugu.

698
00:41:23,860 --> 00:41:27,080
Eta mota egin behar litzateke hau sentitzen gogorragoa lan mota

699
00:41:27,080 --> 00:41:30,900
elementu horiek txikiak ezkerreko, eta hori lortu dugu unlucky delako.

700
00:41:30,900 --> 00:41:34,210
Zerrenda gabe alderantzizko antolatuko zen.

701
00:41:34,210 --> 00:41:38,110
Por el contrario, txertatzeko sort imitatzen dugu zer egin dugu gure gizakietan bada hemen

702
00:41:38,110 --> 00:41:42,670
denek horrela antolatu hasi eta ondoren hasi, algoritmo nahiko ona da, ezta?

703
00:41:42,670 --> 00:41:45,010
Dagoeneko, izan ere, ordenatuko da.

704
00:41:45,010 --> 00:41:48,670
Beraz, utzi gauza horiek zehatz-mehatz zenbat denbora hartu dira gurekin laburbiltzen saiatuko en

705
00:41:48,670 --> 00:41:52,360
jargon apur bat besterik ez edo notazio askoz errazagoa da benetan sartu

706
00:41:52,360 --> 00:41:54,320
sort-fanciness baino iradokitzen du.

707
00:41:54,320 --> 00:41:59,030
Gauza hau hemen, big O pantailan, ordenagailu zientzialari bat izango da, oro har, erabili

708
00:41:59,030 --> 00:42:03,640
kasurik okerrenean algoritmo bat deskribatzeko.

709
00:42:03,640 --> 00:42:07,360
>> Berriz ere, kasu txarrenean, guztiz testuinguruaren mendeko da.

710
00:42:07,360 --> 00:42:10,890
Zer esan nahi dugu kasu txarrena erabat desberdina izango da arazo buruz hitz egiten ari gara oinarritzen da.

711
00:42:10,890 --> 00:42:14,550
Baina Ordenatzeko kasuan, txarrena ahalik eta eszenatoki zer?

712
00:42:14,550 --> 00:42:17,860
Dena da atzeraka delako eta bakarrik sentitzen duten bezala, lan asko esan nahi du Gurekin.

713
00:42:17,860 --> 00:42:21,330
Jotted dut Nik horrela ikusten dugu orain arte algoritmoak batzuk:

714
00:42:21,330 --> 00:42:24,930
lineal bilaketa, bilaketa bitarra telefono-book edo paper zatiak bezala,

715
00:42:24,930 --> 00:42:28,960
gero burbuila ordenatu, aukeraketa, ordenatu, eta txertatzeko sort bezala, ikusi dugu gure gizakietan

716
00:42:28,960 --> 00:42:31,770
eta, ondoren, 1 bestelako den azkenean deitu batu sort.

717
00:42:31,770 --> 00:42:37,710
Beraz, kasurik okerrenean bilaketa lineala, zenbat urrats ditu kopurua 7 aurkituko hartu

718
00:42:37,710 --> 00:42:40,690
ate n dira Sean aurrean bezala bada? >> [Ikasleen] N.

719
00:42:40,690 --> 00:42:44,180
N. Beraz, big n O idatzi dugu.

720
00:42:44,180 --> 00:42:47,010
Hutsuneak batzuk bete besterik ez dut egingo. Hutsuneak sareta bat besterik ez da.

721
00:42:47,010 --> 00:42:52,990
Baina bilaketa lineal kasuan onena, 7 zerrendaren Irteeran agian izan da,

722
00:42:52,990 --> 00:42:55,520
eta Sean hasi liteke zerrendaren hasiera begira.

723
00:42:55,520 --> 00:42:58,940
Beraz, bada bilaketa lineala erabiltzen ari zarela eta ezkerretik eskuinera, edo agian eskuinetik ezkerrera egiaztapena

724
00:42:58,940 --> 00:43:02,650
baliokideak dira kasu horretan onena zenbat urrats gerta daiteke lineala bilaketa

725
00:43:02,650 --> 00:43:05,550
Sean-en algoritmoa bezala, hartu nahi duzu? Just 1 urratsa.

726
00:43:05,550 --> 00:43:09,450
>> Beraz, omega idazkera esan nahi dut.

727
00:43:09,450 --> 00:43:11,570
Kapital omega hau besterik ez da.

728
00:43:11,570 --> 00:43:15,000
Omega besterik ez da onena kasu iraupena esaten modu sexy.

729
00:43:15,000 --> 00:43:18,900
Beraz, kasu horretan, onena ari da denbora urrats bakar bat edo konstante zenbakiaren urrats

730
00:43:18,900 --> 00:43:24,270
1 Kasu honetan, baina kasu horretan, txarrena, big O, benetan da n urratsak.

731
00:43:24,270 --> 00:43:28,110
Eta hau hemen, theta, benetan ari gara ez begiratzen oraintxe.

732
00:43:28,110 --> 00:43:30,090
Ez da adibide hau, bereziki garrantzitsua da.

733
00:43:30,090 --> 00:43:31,990
Baina orain dezagun saiatu bitar bilaketa.

734
00:43:31,990 --> 00:43:35,990
In, bilaketa bitarra kasuan txarrenean, zenbat urrats kopurua 7 aurkituko hartu du

735
00:43:35,990 --> 00:43:38,340
edo dena delakoa bilatzen ari gara? >> [Ikasleen] Log n.

736
00:43:38,340 --> 00:43:40,980
Oraindik log-n bezala Alex got delako unlucky

737
00:43:40,980 --> 00:43:44,030
arazoa bidez benetan dugu lan metodikoki

738
00:43:44,030 --> 00:43:48,220
eta ez zuen aurkitu azken begiratu zuen atea arte, 7 zenbakia

739
00:43:48,220 --> 00:43:51,720
nahiz eta, zuzentasuna, kanpoan bota ateak zenbait bidean lortu zuen,

740
00:43:51,720 --> 00:43:56,920
binary log n kasurik okerrenean bilaketa iraupena du.

741
00:43:56,920 --> 00:43:59,230
Eta berriro ere, hau zatituz eta konkistatu hitz egiten du.

742
00:43:59,230 --> 00:44:01,140
Baina zer gertatzen da kasu onena?

743
00:44:01,140 --> 00:44:04,790
Eta Alex benetan bizitako Kasu horretan, onena izan zen zuen agertokian.

744
00:44:04,790 --> 00:44:07,290
Zenbat urrats bilaketa bitarra ez hartu? >> [Ikasleak] 1.

745
00:44:07,290 --> 00:44:09,380
1, bakarrik lortu zuen zortea delako.

746
00:44:09,380 --> 00:44:12,520
Baina hori da onena kasu eszenatoki fina omega aipatzen delako,

747
00:44:12,520 --> 00:44:15,770
kasu input onena, nahiz eta muda ausazko zorte besterik ez da.

748
00:44:15,770 --> 00:44:18,900
>> Orain, hau ere baja hutsik mota ari gara orain.

749
00:44:18,900 --> 00:44:21,010
How about burbuila sort?

750
00:44:21,010 --> 00:44:24,290
Burbuila sort kasu txarrenean, denok alderantzizko ordenan da,

751
00:44:24,290 --> 00:44:26,380
beraz bubbling asko egin behar dugu.

752
00:44:26,380 --> 00:44:30,190
Baina zenbat urrats da txarrena kasuan hartu? >> [Ikasleen] N karratu.

753
00:44:30,190 --> 00:44:32,550
Hau izan zen n karratuko, uste duzulako,

754
00:44:32,550 --> 00:44:36,410
zerrenda erabat atzeraka - 8 da hemen, 1 da hemen.

755
00:44:36,410 --> 00:44:40,530
gauza burbuila hasteko Horrela, modu honetan, 8 zenbakia eraman behar du,

756
00:44:40,530 --> 00:44:44,540
kasurik okerrenean kopurua 7 Horrela, modu honetan, baina non da?

757
00:44:44,540 --> 00:44:47,720
Hemen jarraitzen zuen han. Beraz, behin eta berriro egin behar izan dugu.

758
00:44:47,720 --> 00:44:53,190
Eta hori da, non n urratsak, eta, ondoren, n - 1 urratsak eta, ondoren, n - 2 urrats.

759
00:44:53,190 --> 00:44:55,960
Eta nire hitza hartu duzu bada - mota duzu biderkatzen bada,

760
00:44:55,960 --> 00:45:00,110
gutxi gorabehera n amaieran egingo dugun oraintxe ignore beste termino batzuk karratu

761
00:45:00,110 --> 00:45:06,890
ondoren, txarrena kasuan burbuila sailkatu n karratu da, eman edo hartu.

762
00:45:06,890 --> 00:45:09,490
Baina burbuila sort kasua onena buruz zer?

763
00:45:09,490 --> 00:45:13,050
Zer da kasu onena agertokia? Zenbakiak guztiak antolatuko dira dagoeneko.

764
00:45:13,050 --> 00:45:15,920
Eta zer heuristiko erabiltzen dut, trikimailu erabiltzen dut,

765
00:45:15,920 --> 00:45:20,110
izan dut egindako lana ez, eta, beraz, ezin izan dute gelditu goiz konturatzen?

766
00:45:20,110 --> 00:45:23,590
[Ikasleak] Begiratu behin. >> Begiratu behin. Baina zer zen egiten dut bidean?

767
00:45:23,590 --> 00:45:26,130
Pista nintzen mantenduz zenbat trukeak egin nuen.

768
00:45:26,130 --> 00:45:30,650
Zenbatzen ez badut, trukeak edozein, nire behatzak, eta gero egin dut lana ez konturatu nintzen.

769
00:45:30,650 --> 00:45:34,300
Behar du, zalantzarik gabe, ez dut saiatu lanak ez dira berriro egin, eta, beraz, besterik gabe gelditu ahal izango dut.

770
00:45:34,300 --> 00:45:37,830
>> Beraz, burbuila-sort kasuan onena zerrendan dagoeneko ordenatuta,

771
00:45:37,830 --> 00:45:41,530
zer, omega idazkera esan duzu, kasuan onena iraupena?

772
00:45:41,530 --> 00:45:48,040
Just n. Lan egin behar dugu, baina besterik ez dugu 1 ibilaldi lana merezi.

773
00:45:48,040 --> 00:45:50,490
Eta hemen ere, zati hau hutsik utzi behar dut.

774
00:45:50,490 --> 00:45:52,430
Eta orain, aukeraketa sort.

775
00:45:52,430 --> 00:45:56,010
Aukeraketa sort izan plucking pertsona txikiena me behin eta berriro.

776
00:45:56,010 --> 00:45:58,380
Eta zer egin izan zen denbora exekutatzen ari dela esan genezake?

777
00:45:58,380 --> 00:46:00,590
Hori izan zen n kasurik okerrenean karratu.

778
00:46:00,590 --> 00:46:05,220
Eta, zoritxarrez, kasu horretan onena Honez gain n karratu

779
00:46:05,220 --> 00:46:08,840
mundu osoan ikuspegi omniscient sort izan ez dudalako;

780
00:46:08,840 --> 00:46:13,140
Osoa iterazio gainean besterik ez dut ezagutzen ditudan pertsona txikiena, hain zuzen ere aurkitu.

781
00:46:13,140 --> 00:46:15,860
Aukeraketa sort mota zentzu horretan sucks

782
00:46:15,860 --> 00:46:17,920
baina hankaz intuitiboa mota da.

783
00:46:17,920 --> 00:46:21,470
Nahiko erraza da kodea da egin behar duzun guztia idatzi loops for habiaratua pare bat delako,

784
00:46:21,470 --> 00:46:24,620
normalean, txikiena elementu bila pasatzen

785
00:46:24,620 --> 00:46:27,840
eta, ondoren, non pertenece zerrendaren amaieran elementu txikiena jartzen.

786
00:46:27,840 --> 00:46:29,900
Beraz, hemen ere ez da merkataritza-off bat izango da.

787
00:46:29,900 --> 00:46:34,440
Zenbat denbora uste eta benetan zerbait garatzeko kodea idatziz hartzen du

788
00:46:34,440 --> 00:46:39,460
oso ondo hartu nahi duzun algoritmoa hobea eta azkarragoa performance bat izanez gero denbora gehiago.

789
00:46:39,460 --> 00:46:41,780
>> Baina besterik ez duzula mota kodea zerbait sortu bada, azkar eta zikin

790
00:46:41,780 --> 00:46:45,000
eta, besterik gabe mota ideia stupidest posible uste dezakezu,

791
00:46:45,000 --> 00:46:47,580
iraun dezake minutu batzuk kodea, baina datuak multzo handi

792
00:46:47,580 --> 00:46:49,580
zure algoritmoa ordu iraun dezake exekutatu.

793
00:46:49,580 --> 00:46:51,690
Eta are eskola graduondoko batzuetan horiek merkataritza-offs.

794
00:46:51,690 --> 00:46:55,660
3am litzateke, batzuk oso handiak datuak multzoa aztertzen saiatzen ari zen I

795
00:46:55,660 --> 00:46:59,650
segurtasun ikerketa egiten ari nintzen, eta bai zen, 5 minutu igaro

796
00:46:59,650 --> 00:47:03,210
tweaking nire programa datuak aztertu eta joan lo egin

797
00:47:03,210 --> 00:47:08,420
edo pasatzeko 8 ordu lortzean egokia berehala exekutatzen da, beraz, eta ez joan, lo egin.

798
00:47:08,420 --> 00:47:10,530
Eta, beraz, han ere kontziente erabakia mota da.

799
00:47:10,530 --> 00:47:12,740
Garapen-denbora gutxiago, gehiago lo.

800
00:47:12,740 --> 00:47:14,780
Atzera begirako, ziurrenik ez dut bultzatu dela

801
00:47:14,780 --> 00:47:19,120
helburua hemen kalitatea optimizatzeko kodea,

802
00:47:19,120 --> 00:47:21,280
baina mundu errealean oso moduzko merkataritza-off da.

803
00:47:21,280 --> 00:47:25,130
Denbora gutxiago, errendimendu gutxiago, edo alderantziz.

804
00:47:25,130 --> 00:47:28,110
Hortaz, hona hemen, azkenik, lortu dugu theta buruz hitz egiteko aukera.

805
00:47:28,110 --> 00:47:32,830
Theta idazkera ordenagailuan zientzialari ekarri elkarrizketetan zerbait da

806
00:47:32,830 --> 00:47:36,160
big O eta omega gertatuko berdinak izatea.

807
00:47:36,160 --> 00:47:40,160
Theta benetan bidali mezu hori estu loturik mota da esaten duzu.

808
00:47:40,160 --> 00:47:43,340
Ez dio axola, egoera ona edo txarra den ala ez, eta karratu n.

809
00:47:43,340 --> 00:47:46,510
Beraz, ez da garrantzitsua hemen ipuin hauek.

810
00:47:46,510 --> 00:47:48,560
Insertion sort (a) ren begiratu dugu, hau da,

811
00:47:48,560 --> 00:47:50,830
non nintzen guztiontzat leku egokian txertatzen.

812
00:47:50,830 --> 00:47:54,930
Kasu honetan onena txertatzeko sort iraupena izan zen ikusi dugu hemen?

813
00:47:54,930 --> 00:47:57,250
[Ikasleak] kasua? >> Kasua.

814
00:47:57,250 --> 00:48:00,100
>> N kasuan, onena izan zen guztiontzat horrela antolatu delako,

815
00:48:00,100 --> 00:48:02,580
eta Sammy eta ez beste inor benetan guztiak eraman behar izan zuen.

816
00:48:02,580 --> 00:48:04,610
Dagoeneko ziren leku eskuineko.

817
00:48:04,610 --> 00:48:08,570
Beraz txertatzeko onena kasu sort da, kasu honetan, n.

818
00:48:08,570 --> 00:48:12,770
Baina kasu horretan, txarrena karratu n mota da. Zergatik?

819
00:48:12,770 --> 00:48:16,230
Gizakien zerrendan alderantzizko ordenan bada,

820
00:48:16,230 --> 00:48:21,260
8 zenbakia dut eta berarekin sartu dut, edo bere posizioa eskubidea, hau da, hemen.

821
00:48:21,260 --> 00:48:25,270
Mota alde mugitzen dut. Guys hauek Unsorted zuen, edo horrela antolatu du.

822
00:48:25,270 --> 00:48:28,970
Baina orain, nor hurrengo gertatuko I? >> [Ikasleak] 7.

823
00:48:28,970 --> 00:48:31,250
Kasu horretan, txarrena 7 alderantzizko ordenan delako.

824
00:48:31,250 --> 00:48:34,920
>> Beraz, hemen da, 7. Non ez 7 sartzen zara? Definitely me atzean.

825
00:48:34,920 --> 00:48:39,460
Baina, orain 7 benetan pertenece ez berehala me atzean, baina multzoko 8 atzean,

826
00:48:39,460 --> 00:48:41,880
izan dut, beraz, esan "me Barkatu, multzoko 8, mugitzeko modu hau mesedez

827
00:48:41,880 --> 00:48:44,640
"7 gela egiteko?" Orain 6 topo.

828
00:48:44,640 --> 00:48:48,530
"Oh, libratuko me, 8 eta 7, 6 gela egiteko mugitu duzu?"

829
00:48:48,530 --> 00:48:52,360
Beraz, beste era batera esanda, txertatzeko sort, nahiz eta ez dut askoz mugimendu egiten,

830
00:48:52,360 --> 00:48:56,330
me atzean pertsona asko lan gehiago egiten ari dira, eta hori lortu norbait denbora kostatuko.

831
00:48:56,330 --> 00:48:58,000
Ordenagailua denbora kostatuko da.

832
00:48:58,000 --> 00:49:01,450
Beraz, txertatzeko sort kasuan jasaten jarraitzen dugu.

833
00:49:01,450 --> 00:49:06,260
Urratsen kopuru osoa gehitzen bada, amaituko dugu, gutxi gorabehera n karratu sakatuz

834
00:49:06,260 --> 00:49:11,160
guys horiek gela egin behar, giza delako txertatuko dira zerrenda horretan itzuli.

835
00:49:11,160 --> 00:49:15,960
Eta horrela, kasu honetan theta besterik ez da esku istorioa jakin ez dagokio.

836
00:49:15,960 --> 00:49:21,100
Hori da polita eta ona. Iraupena buruz hitz egiten 3 modu ezberdinetan hauek ditugu.

837
00:49:21,100 --> 00:49:26,370
Baina zer du termino errealetan, benetan esan nahi benetan saiatu egin behar dugu gero algoritmo bat sortu kodea?

838
00:49:26,370 --> 00:49:31,620
>> Utzidazu proposatu ez daude algoritmoa are hobeto

839
00:49:31,620 --> 00:49:33,740
bera, zenbait merkataritza-offs.

840
00:49:33,740 --> 00:49:36,890
Sort batzeko deia ari gara, eta hau magikoa algoritmoa sort da

841
00:49:36,890 --> 00:49:42,840
bakarrik lan egiten azkarrago nolabait, eta beraz, erraza da, gutxienez pseudocode adierazteko.

842
00:49:42,840 --> 00:49:46,900
Algoritmoa merge sort hau ezartzeko, honela izango da.

843
00:49:46,900 --> 00:49:50,860
Duzunean n elementu - n zenbakiak, n pertsona, edozein delarik ere lehen behatu txeke bat eman.

844
00:49:50,860 --> 00:49:56,340
N 2 baino gutxiago bada, batu sort besterik ez gelditzen da. Itzultzen da, nolabait esateko.

845
00:49:56,340 --> 00:50:00,830
Zergatik n 2 baino gutxiago bada geldiarazten ez dituzun? >> [Inaudible ikaslearen erantzuna]

846
00:50:00,830 --> 00:50:04,480
Eskuin. Eta berriro ere, n da, ez dago zerrendan, n zerrendaren tamaina da.

847
00:50:04,480 --> 00:50:07,660
N 2 baino gutxiago bada, horrek esan nahi du zure zerrenda bai 1,

848
00:50:07,660 --> 00:50:09,640
non zauden, jakina, horrela antolatu da zenbaki 1 bada,

849
00:50:09,640 --> 00:50:11,710
edo 0, eta kasu horretan ez dago ezer ordenatzeko,

850
00:50:11,710 --> 00:50:13,570
base kasuan sort behar dugu.

851
00:50:13,570 --> 00:50:20,350
Zerrenda laburra da, beraz, ez dagoela ezer egin bada, literalki, ez ezer. Joan-etorrikoa.

852
00:50:20,350 --> 00:50:25,090
Bestela, ordenatzeko elementuak ezkerreko erdia eta, ondoren, ordenatzeko elementuak eskuineko erdia,

853
00:50:25,090 --> 00:50:27,410
ondoren batu ordenatuko halves 2.

854
00:50:27,410 --> 00:50:32,130
>> Mota hau apur bat Cheat dirudienez, horren bidez galdetzen dut nola elementu ordenatzeko

855
00:50:32,130 --> 00:50:34,900
eta ni ari zaren kontatzea, "Ordenatu ezkerreko erdialdean, eskuineko erdia ordenatzeko."

856
00:50:34,900 --> 00:50:37,240
Bezala, nago "eskubidea guztiak. Nola ezkerreko erdian ordenatzeko?"

857
00:50:37,240 --> 00:50:40,670
"Ordenatu ezker ezkerreko erdia erdia, ezkerreko erdia erdia ordenatzeko, eta, ondoren, egin".

858
00:50:40,670 --> 00:50:44,060
Ziklikoki zer ordenatzeko esan nahi du definitzeko mota zara,

859
00:50:44,060 --> 00:50:46,790
baina bihurtzen da, kasu honetan, benetan zoragarria.

860
00:50:46,790 --> 00:50:50,230
Ez da benetan gurpil ziklo hau ez da inoiz bukatzen

861
00:50:50,230 --> 00:50:52,550
noiz amaituko ez delako? >> [Ikasleak] 1 gauza iristen denean.

862
00:50:52,550 --> 00:50:54,220
1 gauza iritsiko duzu.

863
00:50:54,220 --> 00:50:57,850
Beraz, nahiz eta 8 pertsona has dezakezu eta esaten dut, "Ordenatu pertsona horien erdia ezkerreko

864
00:50:57,850 --> 00:51:00,480
4 pertsona horiek, "gero esango dizut," Nola ezkerreko erdian ordenatzeko duzu? "

865
00:51:00,480 --> 00:51:03,450
"Beno, ordenatzeko 2 pertsonek hemen." Eta gero, hala nola "guztiak, eskuineko fina".

866
00:51:03,450 --> 00:51:05,520
"Nola ezkerreko pertsona horien erdia ordenatzeko duzu?"

867
00:51:05,520 --> 00:51:09,040
"Just ordenatzeko 1 pertsonek hau hemen." Zein liluragarria errebelazio orain?

868
00:51:09,040 --> 00:51:13,050
1 pertsonek ordenatzeko behar dut. Eginda. Nik ez dut edozein lan egiteko.

869
00:51:13,050 --> 00:51:16,580
Baina orain, pertsona hau ordenatzeko behar dut, baina pertsona bakar bat, ez da ezer egin behar dira.

870
00:51:16,580 --> 00:51:21,490
>> Beraz, magia, itxuraz, hirugarren urrats honetan: ordenatuko halves batzea.

871
00:51:21,490 --> 00:51:25,770
Beraz batu sort liluragarria ezagutzeko honek arazo handi bat apurtzen bada behera

872
00:51:25,770 --> 00:51:28,650
2, txikiagoa berdinean tamainako arazoak sartu

873
00:51:28,650 --> 00:51:32,710
eta, ondoren, kola mota irtenbide txikiak eta amaieran,

874
00:51:32,710 --> 00:51:34,720
Asko dugu, askoz hobeto [hariztaketa soinua proposatzen dut]

875
00:51:34,720 --> 00:51:38,050
aukeraketa sort edo txertatzeko sort edozein baino.

876
00:51:38,050 --> 00:51:40,690
Benetan Nik ordu erdi ez ikusi egingo zaio, baina benetan ez dakit zer ari den gertatzen

877
00:51:40,690 --> 00:51:45,040
gaur egun kanpo. [Whirring soinu] [barreak]

878
00:51:45,040 --> 00:51:49,660
Beraz, ikus dezagun hau ikus daiteke gure lagun Rob Bowden pixka laguntza.

879
00:51:49,660 --> 00:51:52,810
2 merge sort prozesuan urrats handiak daude.

880
00:51:52,810 --> 00:51:56,400
Lehenik eta behin, etengabe zatitu cups zerrenda halves sartu

881
00:51:56,400 --> 00:51:59,610
horietan kopa 1 besterik ez dugu zerrendak sorta bat arte.

882
00:51:59,610 --> 00:52:02,150
Ez kezkatu zerrenda batean bakoitiak zenbaki bat badu

883
00:52:02,150 --> 00:52:04,830
eta ezin duzu haien arteko ebaki primeran garbi bat egiteko.

884
00:52:04,830 --> 00:52:08,740
Just arbitrarioki hautatzeko zerrenda extra kopa sartu, besteak beste

885
00:52:08,740 --> 00:52:11,320
Beraz, dezagun zatitu, zerrenda horiek.

886
00:52:12,420 --> 00:52:14,570
Orain 2 zerrendak dugu.

887
00:52:18,930 --> 00:52:20,930
Orain 4 zerrendak dugu.

888
00:52:25,730 --> 00:52:28,740
Orain 8 zerrendak zerrenda bakoitzean kopa bakar bat dugu.

889
00:52:28,740 --> 00:52:31,520
Beraz, urrats 1.

890
00:52:31,520 --> 00:52:37,280
Urratsa 2 bikoteka behin eta berriz batu ditugu zerrendak merge aurretik ikasi dugu algoritmoa erabiliz.

891
00:52:37,280 --> 00:52:44,320
108 eta 15 biltzen amaituko dugu zerrendan 15, 108.

892
00:52:45,240 --> 00:52:51,330
50 eta 4 biltzen amaituko dugu, 4, 50.

893
00:52:51,330 --> 00:52:56,950
8 eta 42 biltzen amaituko dugu, 8, 42.

894
00:52:57,790 --> 00:53:04,360
Eta 23 eta 16 batuz sortu amaituko dugu 16, 23.

895
00:53:04,360 --> 00:53:08,030
Orain gure zerrendak tamaina 2.

896
00:53:08,030 --> 00:53:10,980
Iragarki 4 zerrendak bakoitza ordenatuko

897
00:53:10,980 --> 00:53:14,230
beraz, zerrendak bikoteak batuz berriro hasi ahal izango dugu.

898
00:53:14,230 --> 00:53:22,150
15 eta 108 eta 4 eta 50 batzen 4 lehen hartu dugu, gero, 15,

899
00:53:22,150 --> 00:53:26,250
ondoren, 50 eta, ondoren, 108.

900
00:53:26,250 --> 00:53:33,020
8, 42 eta 16, 23 biltzen lehen hartu dugu 8, ondoren, 16,

901
00:53:33,020 --> 00:53:37,170
ondoren, 23 eta, ondoren, 42.

902
00:53:37,170 --> 00:53:42,490
Beraz, orain 2 tamaina 4 zerrendak besterik ez ditugu, eta bakoitzak bere ordenatuko da.

903
00:53:42,490 --> 00:53:45,940
Beraz, gaur egun, 2, zerrenda horiek batu ditugu.

904
00:53:45,940 --> 00:53:54,230
Lehenik eta behin, 4 hartuko dugu eta, ondoren, 8 hartuko dugu eta, ondoren, 15 hartuko dugu

905
00:53:54,230 --> 00:54:05,280
eta 16 eta 23 eta 42 eta 50 eta 108.

906
00:54:05,280 --> 00:54:09,020
Eta Bukatutakoan dugu. Zerrenda ordenatuko dugu.

907
00:54:09,020 --> 00:54:13,740
>> Rob aprobetxatuz mota zerbait ez dugu oraindik egin zen.

908
00:54:13,740 --> 00:54:16,540
It iradoki zen, baina ez du ezer egiten.

909
00:54:16,540 --> 00:54:19,230
Zerbait zen egiten fisikoki cups iradokitzen

910
00:54:19,230 --> 00:54:23,680
baliabide batzuk zuen gastua gain. >> [Ikasleak] Space. >> Espazioa izan da.

911
00:54:23,680 --> 00:54:27,360
Izan ere, zuela bi-maila taula non sort hau espazio zuen hemen

912
00:54:27,360 --> 00:54:31,960
eta hemen behera espazioa zen benetan, esan zuen bi aldiz ere espazio erabiliz ulertuta

913
00:54:31,960 --> 00:54:36,390
txertatzeko ordenatu, burbuila ordenatu, edo hautapena sort gure algoritmoak edozein beraz, orain arte bezala

914
00:54:36,390 --> 00:54:40,780
baina osagarriak espazioa aprobetxatuz zuen atzera eta aurrera mugitzen gauza mota

915
00:54:40,780 --> 00:54:42,600
mantenduz gauza ordena.

916
00:54:42,600 --> 00:54:47,540
Eta nahiz eta horrela antolatu zerrenda bat lortu dugu bezala sentitzen du, sentitu zuen, berriz, bat bezala.

917
00:54:47,540 --> 00:54:51,060
Egia esan, zer Rob zen egiten ari zen, hain zuzen ere algoritmo hau.

918
00:54:51,060 --> 00:54:56,780
Lehen aldiz hartu zuen tamaina n arazoa, banatu erdi ezkerreko eta eskuineko erdia.

919
00:54:56,780 --> 00:54:59,380
Cups mugitu zuen. Ondoren, prozesu hori errepikatu zuen.

920
00:54:59,380 --> 00:55:03,390
4 2 2 multzo banatu zituen hemen eta gehiagoko hemen baino gehiago.

921
00:55:03,390 --> 00:55:08,520
Ondoren, prozesu hori errepikatu zuen eta 2 banatzen da 2 1 multzo horiek hainbat cups bakoitzean.

922
00:55:08,520 --> 00:55:11,000
Eta hori da, non, aukera bikaina sortzen.

923
00:55:11,000 --> 00:55:15,840
Istorioa puntu hartan, Rob izan 8 1. Tamaina zerrendak,

924
00:55:15,840 --> 00:55:18,860
horietatik dagoeneko horrela antolatu ziren.

925
00:55:18,860 --> 00:55:20,630
>> Orduan zer egin, aurrera jarraitu zuen?

926
00:55:20,630 --> 00:55:25,260
Pairwise hau horrela antolatu zerrenda eta ordenatuko zerrenda hau hartu zuen, eta horiek batu.

927
00:55:25,260 --> 00:55:28,200
Ondoren, hau hartu zuen, eta horiek batu, eta gero hau, eta hauek batu

928
00:55:28,200 --> 00:55:30,670
ondoren, hau bat eta batu ditu.

929
00:55:30,670 --> 00:55:32,390
Eta gero, zer egin hurrengo egin zuen?

930
00:55:32,390 --> 00:55:36,580
Ondoren, berriro fusionatuko handiagoa zerrendak eta, ondoren, handiagoak zerrendak berriro fusionatuko.

931
00:55:36,580 --> 00:55:41,170
Eta honi buruz uste baduzu besterik ez oraingoz intuitiboki, zer zen egiten benetan?

932
00:55:41,170 --> 00:55:45,450
Arazoa zen zatituz erdia, erdiak, erdiak, erdia

933
00:55:45,450 --> 00:55:47,600
super txiki horiek zerrendak lortzeko.

934
00:55:47,600 --> 00:55:51,290
Ondoren, bikoitza, double, bikoitza, bikoitza konbinatuz mota izan zen.

935
00:55:51,290 --> 00:55:54,120
Beraz, bi aldiz izan zen lana askoz gisa egiten dut ikusi dugun bezala, beraz, orain arte

936
00:55:54,120 --> 00:55:56,930
ezer arrail eta konkistatzeko, baina big aurre ez duten.

937
00:55:56,930 --> 00:55:59,630
Birritan ere ez da big aurre. Etengabeko faktore bat besterik ez da.

938
00:55:59,630 --> 00:56:03,920
Eta askoz ere gure adierazpen aritmetikoa aurretik bezala, besterik ez dut faktore konstante zeharkatuko du

939
00:56:03,920 --> 00:56:10,170
aldiz 2 atsegin dute. Nork zaintzen? 2 bilioika bada 2 aldiz, oraindik urrats asko.

940
00:56:10,170 --> 00:56:13,160
Beraz, urrats hau batuz gako insight izango dela dirudi.

941
00:56:13,160 --> 00:56:17,000
Dezagun honen bidez ibiltzea besterik ez zenbakiaren aurretik - Oh, hori ez da jarraitu behar oraindik.

942
00:56:17,000 --> 00:56:22,890
Dezagun hau zenbakiaren, besterik gabe, benetan ikusteko nola jokatzen du izarrekin ibiltzeko.

943
00:56:22,890 --> 00:56:25,940
Hau da, batez ere apur bat pobrea gizon animazioa.

944
00:56:25,940 --> 00:56:27,750
Dezagun proposatzen hau.

945
00:56:27,750 --> 00:56:31,480
Merge sort denbora - honi buruz hitz egiteko modu bat besterik ez dugu behar.

946
00:56:31,480 --> 00:56:34,380
Hau ez da matematika, hau da, geure burua adierazteko modu succinct mota.

947
00:56:34,380 --> 00:56:39,080
Beraz, T adierazten du denbora eta n zer adierazten du? >> [Ikasleak] tamaina

948
00:56:39,080 --> 00:56:41,400
>> [Malan] arazoaren tamaina, pertsonen kopurua.

949
00:56:41,400 --> 00:56:45,470
Beraz, n pertsona ordenatzeko denbora exekutatzen ari dela, 0 denbora zenbatekoa izango naiz erreklamatzeko

950
00:56:45,470 --> 00:56:50,290
n 2 baino gutxiago bada, 1 kopa edo cups ez bada, ez da ezer ordenatzeko delako duzu.

951
00:56:50,290 --> 00:56:55,160
Baina, oro har, denborak aurrera egin du n elementuak ordenatzeko proposatzen dut

952
00:56:55,160 --> 00:56:59,350
ezkerreko erdia ordenatzeko hartzen du plus eskuineko erdia izango da

953
00:56:59,350 --> 00:57:03,110
plus - zer gehigarri hau + n? >> [Ikasleak] Batu sort.

954
00:57:03,110 --> 00:57:07,260
[Malan] actually da, batuz bada n / 2 elementu duzulako hemen

955
00:57:07,260 --> 00:57:11,500
eta n / 2 elementu Hemen duzu, zenbat denbora du batu behar da?

956
00:57:11,500 --> 00:57:15,050
Just Rob bezala, hau pluck hemen duzu, agian pluck hemen,

957
00:57:15,050 --> 00:57:17,120
pluck baino gehiago hemen, pluck baino gehiago hemen, pluck baino gehiago hemen.

958
00:57:17,120 --> 00:57:19,400
Cups, bakoitza ukitu behin duzu.

959
00:57:19,400 --> 00:57:22,030
Eta ez da 4 cups gehi 4 cups bada, 8 cups

960
00:57:22,030 --> 00:57:25,200
edo, oro har, 8 cups n.

961
00:57:25,200 --> 00:57:28,470
Beraz batuz urratsa n gaitezke adierazteko,

962
00:57:28,470 --> 00:57:31,330
eta hori, literalki, zenbat aldiz Rob fisikoki ukitu dakar

963
00:57:31,330 --> 00:57:33,410
Styrofoam cups horietako bat.

964
00:57:33,410 --> 00:57:35,850
Hargatik egin arbitrarioak adibide bat.

965
00:57:35,850 --> 00:57:41,850
16 cups bada, zer ordenatzeko iraupena, Rob bildu, 16 cups erabiliz?

966
00:57:41,850 --> 00:57:44,710
2 aldiz denbora zenbatekoa 8 cups hartzen ordenatzeko

967
00:57:44,710 --> 00:57:46,920
8 cups dugulako hemen, 8 cups hemen.

968
00:57:46,920 --> 00:57:51,520
Ez dakit zenbat denbora hartzen du, beraz, generalizing T gisa ari gara oraingoz.

969
00:57:51,520 --> 00:57:53,320
Nork daki zer da?

970
00:57:53,320 --> 00:57:58,990
Baina orain ordenatzeko errekurtsiboki edo galdera bera behin eta berriz eskatu ahal izango dut.

971
00:57:58,990 --> 00:58:01,920
Zenbat denbora du 8 cups ordenatzeko hartu?

972
00:58:01,920 --> 00:58:07,030
8 cups esan nahi dut, 4 cups gehi 4 cups ordenatzeko hartzen du zenbat denbora hartzen du,

973
00:58:07,030 --> 00:58:08,880
gero batuz elkarrekin.

974
00:58:08,880 --> 00:58:13,080
Ederren. Ziklo batean lortzean ari gara dagoeneko. Nola irauten du 4 cups ordenatzeko hartu?

975
00:58:13,080 --> 00:58:19,150
4 cups ordenatzeko hartzen du 2 cups plus 2 cups, ordenatzeko plus batuz prozesua da.

976
00:58:19,150 --> 00:58:21,440
Ederren. Nola irauten du 2 cups ordenatzeko hartu?

977
00:58:21,440 --> 00:58:26,290
2 cups 1 kopa ordenatzeko zenbat denbora hartzen du gehi kopa beste ordenatzeko hartzen du

978
00:58:26,290 --> 00:58:29,040
plus zenbat denbora batzea hartzen du, besterik ez 2.

979
00:58:29,040 --> 00:58:33,340
>> Ederren. Azken galdera. Nola irauten du 1 kopa ordenatzeko hartu?

980
00:58:33,340 --> 00:58:37,260
Hona hemen oinarri kasuan iragarri dugun hit lehenago genuke.

981
00:58:37,260 --> 00:58:42,250
Izan ere, egiten duen lana inolako arazo txikiena ordenatzeko

982
00:58:42,250 --> 00:58:44,120
esan nahi du, gaur egun, eskola kalifikazioa estilo ordenatu,

983
00:58:44,120 --> 00:58:46,460
bakarrik joan ahal izango dugu zenbaki horiek plugging back sartu

984
00:58:46,460 --> 00:58:50,630
Orain badakigu zer da 1 T, eta, beraz, T 0 1 konektatu ahal izango dut.

985
00:58:50,630 --> 00:58:54,420
Horrek erantzuna emango me 2 T, ondoren I goragotik konektatu.

986
00:58:54,420 --> 00:58:56,930
Hori me emango, 4 T, goragotik I entxufatu.

987
00:58:56,930 --> 00:58:58,920
Hori me emango 8 T, goragotik konektatu ahal izango dut.

988
00:58:58,920 --> 00:59:04,330
Eta egia esan, ez dut bada math hori, erantzun horiek plugging,

989
00:59:04,330 --> 00:59:08,590
Lortu ondoren, 16-T ez da 64.

990
00:59:08,590 --> 00:59:12,090
Eta zer 64 ordezkatzen du?

991
00:59:12,090 --> 00:59:15,700
T 16 bada, bai, 16 aldiz 4.

992
00:59:15,700 --> 00:59:20,120
Beraz, orain dela gauza honen iraupena izeneko batu sort aldarrikatzen dut

993
00:59:20,120 --> 00:59:22,590
eta hori ikusi dugu, beraz, oso urrun direnak fanciest izango

994
00:59:22,590 --> 00:59:26,160
deritzo egingo n log n

995
00:59:26,160 --> 00:59:31,140
zenbat aldiz zatitu erdia cups sorta oso bat Rob daitekeelako? Saioa hasi n.

996
00:59:31,140 --> 00:59:34,370
Telefono book Adibidez gisa berean da, auto-Manacorense adibide gisa bera da.

997
00:59:34,370 --> 00:59:36,380
>> Zenbat aldiz erdia zerbait zatitzea duzu?

998
00:59:36,380 --> 00:59:38,410
Hala eta guztiz ere, ez dago batuz urratsa da hau.

999
00:59:38,410 --> 00:59:42,920
Cups zatitzeko erdia behin eta berriro eta berriro, baliteke

1000
00:59:42,920 --> 00:59:45,640
baina, aldi bakoitzean bazoazela batu dute.

1001
00:59:45,640 --> 00:59:48,270
Eta lehenago esan genuen n cups batuz hartzen n urratsak

1002
00:59:48,270 --> 00:59:52,060
kopa bat pluck delako, pluck kopa bat, eta behin kopa behin ukitu behar duzu,

1003
00:59:52,060 --> 00:59:53,510
Rob bezala besterik ez zuten.

1004
00:59:53,510 --> 00:59:59,430
Beraz, bada zerbait log n aldiz egiten ari gara eta n gauzak egiten ari gara, iterazio horietako bakoitzean,

1005
00:59:59,430 --> 01:00:03,090
halvings horietako bakoitzean, n aldiz log n dugu.

1006
01:00:03,090 --> 01:00:07,220
Beraz, bada entxufatu 16 Adibide honetan, 16 aldiz saioa 16 -

1007
01:00:07,220 --> 01:00:10,600
ez kezkatu zergatik orain gertatzen da oinarria marrazten dut ez delako

1008
01:00:10,600 --> 01:00:16,100
baina log base 2 16 4, 16 aldiz 4 da 64.

1009
01:00:16,100 --> 01:00:22,350
Baina, aitzitik, genuen erabiltzen bada burbuila sort edo hautapena sort edo txertatzeko sort 16 zenbakiak,

1010
01:00:22,350 --> 01:00:26,420
zer egingo zenuke exekutatzen ari den denbora izan dira n 16 bada?

1011
01:00:26,420 --> 01:00:33,310
16 karratu izango litzateke, hau da, 256, nahiz eta ondoren ez duzu nahiko math guztiak

1012
01:00:33,310 --> 01:00:38,390
256 64 baino handiagoa da. Hori da benetan magikoa takeaway hemen.

1013
01:00:38,390 --> 01:00:41,990
Eta honen bidez konturatzen adibide txikiagoa baita pset batean lan

1014
01:00:41,990 --> 01:00:44,260
egiten du guztiak askoz intuitiboagoa.

1015
01:00:44,260 --> 01:00:49,070
Baina, zer da benetan algoritmoa hau sentitzen dagokionez esan nahi du:

1016
01:00:49,070 --> 01:00:54,520
Benetan merge sort hemen nahi baduzu, begiratu dezagun tira me up Hemen leiho hau

1017
01:00:54,520 --> 01:00:58,560
Horren bidez, algoritmoak horiek guztiak 3 dugu apur bat desberdina adibide da

1018
01:00:58,560 --> 01:01:01,440
burbuila, aukeraketa, eta batu besterik aldamenean.

1019
01:01:01,440 --> 01:01:03,740
>> Tabernak ausazko hasi dute, eta hori ona da.

1020
01:01:03,740 --> 01:01:06,240
Inor ez da beste funtsezko abantaila bat dauka.

1021
01:01:06,240 --> 01:01:09,500
Dut une batean joan egin klik animazioak horietako bakoitzean - Hasi, Hasi, hasiera

1022
01:01:09,500 --> 01:01:13,270
azkar ahal ditut, beraz, gutxi gorabehera, aldi berean Irteeran,

1023
01:01:13,270 --> 01:01:17,450
eta dezagun kontuan hartu burbuila sort okerragoa kasuan denbora exekutatzen ari dela? >> [Ikasleen] N karratu.

1024
01:01:17,450 --> 01:01:21,560
N karratu. Sort-en hautapena txarrena kasuan denbora lasterketak? N karratu.

1025
01:01:21,560 --> 01:01:25,150
Eta merge sort itxuraz, nahiz eta zuk ez duzu nahiko math guztiak jarraitu orain

1026
01:01:25,150 --> 01:01:30,610
bihurtu da askoz ere intuitiboagoa denboran zehar egingo da, aldarrikatzen dugu, n aldiz log-n.

1027
01:01:30,610 --> 01:01:35,210
Eta log n delako zorrozki baino gutxiago n behin big zenbakiak ditugu,

1028
01:01:35,210 --> 01:01:40,230
n aldiz log n n aldiz baino txikiagoa n edo n karratu.

1029
01:01:40,230 --> 01:01:44,410
Beraz, zer du benetan iraupena termino algoritmoa hobeto sentitzen da,

1030
01:01:44,410 --> 01:01:50,380
n aldiz log n n karratu aurrean? Hemen goaz. Egin klik, egin klik egin klik.

1031
01:01:55,690 --> 01:01:58,650
>> Horixe merge sort antzeko zerbait esan nahi du.

1032
01:01:58,650 --> 01:02:01,680
Une bat daukagu. Dezagun zer gertatzen den ikusteko hemen.

1033
01:02:09,440 --> 01:02:12,440
[Chuckles] Whose burbuila sort dirua?

1034
01:02:14,960 --> 01:02:16,730
Sarrera batzuetan beharrean araberakoa da.

1035
01:02:16,730 --> 01:02:18,120
Ikus dezagun.

1036
01:02:18,120 --> 01:02:23,320
Goazen. Zituen bezala harrapatzeko sentitzen da. >> [Ikasleak] joan, burbuila ordena!

1037
01:02:23,320 --> 01:02:27,370
[Ikasle murmuring]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Bai, bai.

1039
01:02:29,120 --> 01:02:34,520
[Ikasle murmuring] joan, joan, joan!

1040
01:02:37,210 --> 01:02:40,450
[Txaloak] [guztiak kontsolatzeko]

1041
01:02:40,450 --> 01:02:46,240
Beraz, gaur egun 1, azken final demo, bada pixka bat delikatua your mind itzulbiratu math inguruan

1042
01:02:46,240 --> 01:02:49,280
edo sort han ikus, benetan dezakezu abiadura entzun

1043
01:02:49,280 --> 01:02:51,000
algoritmo beste modu ezberdina du.

1044
01:02:51,000 --> 01:02:53,900
Hau da benetan egin duten bazkide soinuak animazio norbait

1045
01:02:53,900 --> 01:02:56,980
aldaketa prozesua eta tabernak altuera.

1046
01:02:56,980 --> 01:03:00,440
Hemen ikusten dugun bezala dugu, ez da gutxi Ordenatzeko algoritmoak daude folks duten pentsatu.

1047
01:03:00,440 --> 01:03:03,660
Lehena hori txertatzeko sort izango da, eta hau izango da hegan bidez

1048
01:03:03,660 --> 01:03:07,090
eman eta hauek nola algoritmoak hainbat lan zentzua akustikoa.

1049
01:03:07,090 --> 01:03:09,080
Hona hemen txertatzeko sort da.

1050
01:03:09,080 --> 01:03:18,410
[Elektronikoen beeping]

1051
01:03:18,410 --> 01:03:20,730
[Malan] Bubble sort.

1052
01:03:20,730 --> 01:03:46,850
[Azkarrago elektronikoen beeping]

1053
01:03:46,850 --> 01:03:48,950
[Malan] Aukeraketa sort.

1054
01:03:48,950 --> 01:04:03,580
[Azkarrago elektronikoen beeping]

1055
01:04:03,580 --> 01:04:05,770
[Malan] Batu sort.

1056
01:04:05,770 --> 01:04:17,270
[Elektronikoen beeping]

1057
01:04:17,270 --> 01:04:20,180
[Beeping moteldu] [barreak]

1058
01:04:20,180 --> 01:04:22,590
[Malan] Gnome sort.

1059
01:04:22,590 --> 01:04:38,580
[Elektronikoen beeping]

1060
01:04:39,740 --> 01:04:46,150
>> Hau CS50 da. Ikusiko dugu datorren astean. [Txaloak eta txaloak]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]