[Powered by Google Translate] [Artikulua 3 - erosoagoa]
[Rob Bowden - Harvard Unibertsitatea]
>> [Hau CS50 da. - CS50.TV]
>> Beraz, lehenengo galdera Harritzeko worded.
GDB aukera ematen dizu "arazteko" programa bat, baina, zehatzago esanda, zer ez duzu egin dezagun?
Bat erantzun dut, eta ez dakit zer zehazki espero
beraz, zerbait dut Asmatzeko da ildo aukera ematen dizu pausoz pauso
programaren bidez oinez, elkarreragin, aldagai-aldaketa, gauza horiek guztiak egin -
funtsean, guztiz kontrolatzeko programa baten exekuzioa
eta egiaztatu emandako edozein programaren exekuzioa.
Ezaugarri horiek Hargatik gauza arazteko duzu.
Ongi da.
Zergatik bitarra bilatu ez array bat horrela antolatu behar?
Nork nahi du erantzutea?
[Ikasleen] ez delako, ez du funtzionatzen ez bada horrela antolatu. >> Bai. [Barreak]
Ez da antolatuz gero, ezinezkoa da erditik zatitu
ezagutu eta ezkerreko dena ez da hain eta eskuinera guztia
erdiko balioa baino handiagoa da.
Beraz horrela antolatu behar da.
Ongi da.
Zergatik bubble n karratu O sort da?
Does Edozeinek lehen zer burbuila sort da goi-mailako ikuspegi oso azkarra eman nahi?
[Ikasleen] elementu bakoitzaren bidez, funtsean, joan eta lehenengo elementu batzuk egiaztatu.
Oraindik bada, non swap duzun, ondoren, hurrengo zenbait elementu eta horrela egiaztatu duzu.
Amaieran iritsi, eta gero elementu handiena da, amaieran jartzen badakizu,
beraz, orduan igaro alde batetara utzi,
eta aldi bakoitzean, ez da aldaketarik egin duzun arte bat gutxiago elementu egiaztatu behar duzu. >> Bai.
Deitzen da burbuila sort irauli array bada bere aldean sortu delako da eta behera, bertikalean,
gero, balio handiek beheraino hondoratzear eta balioak txikiak burbuila goian.
Hau da, bere izena nola lortu.
Eta bai, besterik ez duzu bidez.
Array bidez jarraitzen duzu, balio handiagoa aldaketa
balio handiena lortu beheraino.
>> Zergatik da n karratu O?
Lehenik eta behin, ez du inor zergatik n O karratu esan nahi?
[Ikasleak] run bakoitzean delako n aldiz jartzen da.
Bakarrik ahal izateko, ziur duzula handiena elementu guztiak hartu behera,
orduan errepikatu elementu asko jo behar duzu. >> Bai.
Beraz, kontuan hartu zer big O esan nahi du, eta zer da big Omega bitartez.
Big O nola motela benetan exekutatu aritzeko goiko bezalakoa da.
Beraz, n karratu O esanez, ez da n O edo, bestela, izan da exekutatu ahal izango litzateke
denbora lineala, baina n cubed O da
n cubed O mugatzen delako.
N karratu O mugatzen bada, gero eta mugatzen n cubed ere.
Beraz, N karratu, eta txarrena absolutuaren kasuan, ezin da egin n karratu baino hobeto,
hau da, zergatik karratu N O da.
Beraz, apur bat math ikusteko nola dator n karratu izango da,
ditugu gure zerrendan bost gauza bada, lehen aldiz, zenbat trukeak izan behar potentzialki dugu
Helburu hori lortzeko? Dezagun benetan besterik ez -
Zenbat trukeak dira burbuila sort lehen run array bidez izan dugu?
[Ikasleen] n - 1. >> Bai.
>> 1 - 5 elementu daude bada, n egin behar dugu.
Gero, bigarren bat zenbat trukeak dira, joan egin beharko dugu?
[Ikasleen] n - 2. >> Bai.
Eta hirugarren izan da n - 3, eta, ondoren, erosotasuna, azken bi idatzi egingo dut
ondoren, 2 trukeak eta swap 1 egin behar dugu.
Azkena edo ez benetan gertatuko uste dut.
Da swap? Ez dakit.
Beraz, trukeak kopuru osoa edo, gutxienez, konparazioak egin behar duzu.
Nahiz eta ez duzu swap, oraindik behar duzu balioak alderatzeko.
Beraz, n - 1 array bidez lehen run konparazioak.
Berrantolatzeko gauza horiek bada, dezagun benetan egiteko sei gauza gauza pila beraz nicely
eta, ondoren, 3 egin dut, 2, 1.
Beraz, zenbateko horiek rearranging, zenbat konparazioak egiten dugu ikusi nahi dugu
osoa algoritmoa.
Beraz, bada guys horiek behera ekarri dugu hemen,
ondoren, oraindik ari gara Hala ere, askotan konparazioak ziren summing.
Baina horiek laburbildu dugu eta horiek laburbildu dugu eta horiek laburbildu dugu,
oraindik ere arazo bera da. Bereziki talde horiek batzea besterik ez dugu.
>> Beraz, gaur egun 3 ari gara summing n-en. Ez da besterik ez 3 n.
Beti n / 2 n izango da.
Beraz, hemen 6 gertatuko dugu.
10 gauza izan bada, orduan taldekatze hau egin izan dugu 5 gauza bikote desberdin
eta, azkenean, n + n + n + n + n.
Beraz, beti ari zaren n / 2 n, eta, beraz, hau da jot dugu n karratu / 2.
Eta beraz, nahiz eta erdiak faktorea da, eta hori gertatzen da, etorri da
Izan ere, array zehar iterazio bakoitzerako bitartez 1 gutxiago alderatu dugu delako
beraz, nola lortu 2 baino gehiago ditugu, baina oraindik n karratu.
Ez dugu erdi etengabeko faktorea buruz zaintzeko.
O big stuff asko math sort hau egiteko mota hau atsegin oinarritzen da, beraz,
batuketa aritmetiko eta geometrikoak serie stuff egiten,
baina horietako gehienak Ikastaro honetan nahiko erraza da.
Ongi da.
Zergatik txertatzeko sort n Omega? Zer esan nahi du omega?
[Bi ikasle aldi berean hitz ulertezina] >> Bai.
Omega dezakezu beheko loturik gisa pentsatu.
>> Beraz, ez du axola nola eraginkorra zure txertatzeko sort algoritmoa da,
zerrenda pasa den edozein izanik ere, beti gutxienez n gauzak alderatzea
edo gauza n zehar batetik bestera joateko.
Zergatik da hori?
[Ikasleen] delako zerrendan dagoeneko antolatuz gero, lehen iterazio bidez
elementu oso lehen bakarrik dezakezu bermatzeko gutxienez,
eta bigarren iterazio dezakezu bermatzen lehen bi dira
zerrendan gainerako ordenatuko hori ezagutzen ez duzulako. >> Bai.
Guztiz horrela antolatu zerrenda pasatzen bada, gutxienez, joan elementu guztiak
ezer ez mugitu behar dira inguruan ikusteko.
Beraz, baino gehiago pasatzen zerrenda eta oh, hau da, dagoeneko horrela antolatu esaten,
ezinezkoa da eta ordenatuko zenekien elementu bakoitzaren egiaztatu arte
ordena ordenatuko dira.
Txertatzeko sort aritzeko txikiagoa Beraz, n Omega dago.
Zer da txarrena kasuan merge sort denbora exekutatzen
kasurik okerrenean big O berriro?
Txarrena kasuan agertokia, merge sort nola ez korrika?
[Ikasleen] N log n. >> Bai.
Ordenatzeko azkarrena, oro har, algoritmoak n log n dira. Ezin duzu egin, hobeto.
>> Daude kasu bereziak, eta dugu denbora izanez gero, gaur egun, baina seguruenik won't dugu
horrela, ez n log n baino hobeto ikusi ahal izan genuen.
Baina, oro har, kasu honetan, ezin duzu n log n baino hobea.
Eta batu sort gertatzen ko n log n Ikastaro hau dela jakin behar duzu.
Eta, beraz, benetan dugu gaur egun ezartzeko.
Eta, azkenik, hiru esaldi baino gehiago, nola aukeraketa sort lan egiten du?
Ba al du norbaitek nahi erantzun, eta zure esaldi zenbatu dut
3 baino gehiago joaten bada,
Does Edozeinek aukeraketa sort gogoratzen?
Aukeraketa sort nahiko erraza izan ohi da, izena gogoratzen.
Array batetik bestera joateko baino gehiago besterik ez duzu, edozein izanda ere, balio handiena edo txikiena
edozein dela ere, ordena sartu zaren ordenatzeko
Beraz, demagun txikiena etatik handiena ordenatzeko ari gara.
Batetik bestera joateko, array zehar, edozein gutxieneko elementu bila,
hautatu, eta, ondoren, besterik ez da swap edozein leku lehenengo.
Eta gero, array zehar bigarren mendatean, gutxieneko elementu bila, berriz,
aukeratu da, eta, ondoren, bigarren postua trukatzeko.
Beraz, ari gara produktuak biltzea eta gutxieneko balioak aukeratuz
eta horiek txertatu array aurrean sartu da horrela antolatu arte.
Horri buruzko galderak?
>> Hauek nahitaez betetzeko denean pset bidaltzen ari zaren duzu forma agertzen dira.
Hauek dira, funtsean, horien erantzunak.
Ongi da, eta, beraz, gaur egun arazoak kodifikazioa.
Dagoeneko bidali nuen email baino gehiago - Ba inor ez email hori? Ongi da.
Dagoeneko bidali nuen email baino gehiago ari gara espazio erabiliz,
eta nire izenaren gainean klik egiten baduzu, beraz, behealdean dut uste dut
atzeraka r delako, baina nire izenaren gainean klik egiten baduzu, 2 revisions ikusiko duzu.
Berrikusketa, ordua: 1 behar I dagoeneko kopiatu eta kodea itsatsi Espazioak
bilaketa gauza inplementatzeko izan duzu.
Eta 2 (r) en berrikusketa, ordua: sort gauza ezartzeko ondoren izango da.
Beraz, nire berrikusketa, ordua: 1 klik egin dezakezu, eta hortik landu.
Eta orain binary bilaketa ezartzea nahi dugu.
>> Does Edozeinek goi-mailako azalpen pseudocode bat eman nahi
zer bilaketa egin beharko dugu? Bai.
[Ikasleen] hartu besterik ez duzu array-erdian ikusi eta zer nahi baduzu bila
hori baino gutxiago edo hori baino gehiago da.
Eta ez bada, gutxi gorabehera, joan den gutxiago erdia,
eta gehiago da bada, joan gehiago erdia den eta errepikatu duzu, gauza bat besterik ez duzu iritsi arte.
[Bowden] Bai.
Oharra gure zenbakiak array dagoeneko ordenatuko
eta, beraz, horrek esan nahi du abantaila hartu daiteke hori eta lehen egiaztatu ahal izan genuen,
ados, 50 zenbakia bila nabil.
Beraz, erdi-erdian ezin dut joan.
Erdi gogorra da, gauza bat ere definitzeko,
baina dezagun, besterik gabe esan dugu beti erditik moztu.
Hortaz, hona hemen 8 gauzak ditugu, beraz, erdian 16 izango litzateke.
50 bila nabil, eta, beraz, 50 16 baino handiagoa da.
Beraz, gaur egun, batez ere, ezin dut tratatzeko nire array elementu horiek gisa.
Bota dut dena, 16.
Orain nire array besterik ez da 4 elementu hauek, eta nik errepikatu.
Orduan erdian berriro aurkitu nahi dut, hau da, 42 izango dira.
42 50 baino txikiagoa da, beraz, bota dut bi elementu horiek.
Hau da nire gainerako array da.
Erdian berriro aurkitu dut.
50 adibide txarra izan zen uste dut izan dut beti urrun bota gauzak ezkerrean,
baina, neurri berean, naiz badut zerbait bilatzen
eta elementu baino gutxiago da gaur egun naiz begira,
ondoren, eskubidea dena urrun bota dut.
Beraz, gaur egun ezartzeko behar dugu.
Iragarki tamaina gainditu behar ditugu.
Era berean, ez dugu behar kodea hard-tamaina.
Beraz, bada, kentzeko lortuko dugu # define -
Ongi da.
Nola nicely irudikatu dut zenbakiak array tamaina da gaur egun?
>> Zenbat elementu zenbakiak array dira?
[Ikasleak] zenbakiak, parentesi artean, luzera?
[Bowden] Horrek ez du ez C. existitzen
Beharra. Luzera.
Arrayak ez dute propietate, array jabetza luzera ez da, beraz,
du soilik eman luze Hala ere gertatzen da.
[Ikasleak] Ikus zenbat memoria ditu, eta zenbat by zatitzea - ​​>> Bai.
Beraz, nola egin dezaket zenbat memoria ditu ikusten dugu? >> [Ikasleak] Sizeof. >> Bai, sizeof.
Sizeof operadorea den zenbakiak array tamaina itzuli da.
Eta hori da ordea askotan osokoa izan badira zenbaki oso bat tamaina
geroztik zenbat memoria benetan da hartzen.
Beraz, bada, gauzak array nahi dut,
ondoren, osoko baten tamaina zatitzea nahi dut.
Ongi da. Beraz, aukera ematen dizu pasatzeko tamaina Niri hemen.
Zergatik tamaina gainditu guztiak behar dut?
Zergatik ezin egin dut hemen int size = sizeof (haystack) / sizeof (int)?
Zergatik ez du funtzionatzen?
[Ikasleak] ez da global aldagai bat.
[Bowden] Haystack badagoela eta zenbakiak ari gara haystack gisa pasatuz,
eta zer etorri foreshadowing mota da. Bai.
[Ikasleak] Haystack besterik ez da erreferentzia, eta, beraz, itzultzeko nola big erreferentzia dela litzateke.
Bai.
Zalantzan hitzaldia dut ikusi oraindik pila benetan, eskubidea?
Besterik ez dugu horri buruz hitz egiten.
Beraz, pila bat da, non zure aldagai guztiak gordetzen dira egingo.
>> Duen edozein aldagai tokiko memoria esleitu pila joan
eta funtzio bakoitzak bere espazioa lortzen pila, bere pila-markoa da, zer deitzen.
Beraz, nagusiak bere pila-markoa du, eta horren barruan zenbakiak array hau existitzen da,
eta tamaina sizeof (zenbakiak) izango da.
Elementuak tamainaren arabera banatzen zenbakiak tamaina izan da,
baina nagusiak pila marko barruan bizitza guztiak.
Bilaketa deitzen diogu, bilatu bere pila-markoa lortzen,
bere espazio, bere aldagai tokiko guztiak gordetzeko.
Baina argumentuak hauek hain haystack ez da osoa array honen kopia bat.
Ez dugu kopia bat bezala sartu bilaketa array osoa gainditu.
Array hori erreferentzia bat besterik ez da pasatzen.
Beraz, bilaketa zenbaki horiek sartu ahal izango da erreferentzia honen bidez.
Oraindik gauza nagusia pila marko barruan bizi diren sartzeko
baina funtsean, erakusle dugu, eta horrek laster izan beharko luke,
hau da, zein erakusle dira.
Erakusleak besterik ez dira gauza erreferentziak, eta gauzak sartzeko erakusleak erabili ahal izango duzu
beste gauza pila markoak dira.
Beraz, nahiz eta kopuru nagusia tokiko, oraindik ezin dugu sartu erakuslea honen bidez.
Baina besterik ez geroztik erakuslea eta erreferentzia bat besterik ez da,
sizeof (haystack) erreferentzia bera tamaina du.
Ez du itzuli beharreko gauza da seinalatuz tamaina.
Ez itzultzeko zenbakiak benetako tamaina.
Eta, beraz, hau ez da lanera joan nahi dugun bezala.
>> Horri buruzko galderak?
Erakusleak dira sartuko joan xehetasun nabarmen gehiago góry datozen asteetan.
Eta hau da, zergatik gauzak ikusten dituzu, bilaketa gauza gehienak edo sort gauza asko,
ia guztiak ari dira array benetako tamainan hartu behar du,
C, zeren eta, ez daki zer tamaina array dugu.
Pasatzen da eskuz sartu behar duzu
Eta ezin eskuz array osoa pasatzen ari zaren besterik ez delako erreferentzia pasatzen
eta ezin da tamaina erreferentzia.
Ongi da.
Beraz, gaur egun zer zen azaldu aurretik ezartzea nahi dugu.
Gainean lan egin ahal izango duzu minutu bat,
eta ez duzu dena primeran% 100 lan lortzean kezkatu.
Just idatzi pseudocode erdia nola lan egin behar dela uste duzu.
Ongi da.
Erabat honekin egin oraindik behar No.
Baina ez du inor sentitzen hain urruti dute eroso,
antzeko zerbait batera lan egin ahal izango dugu?
Does Edozeinek nahi boluntario? Edo ausaz egingo dut hautatu.
Ez du neurria edozein baina zerbait aldatu ahal izango dugu, lan-egoera.
[Ikasleak] Sure. >> Ados.
Beraz, berrikuspena gorde Save little ikonoan klik eginez.
Ramya zara, ezta? >> [Ikasleak] Bai. >> [Bowden] Larreina.
Beraz, orain zure berrikuspena ikusi ahal izango dut eta denek tira Berrikusketaren.
Eta hemen dugu - Ongi da.
Beraz Ramya konponbidea errekurtsiboa da, hau da, behin betiko baliozko irtenbide bat joan zen.
Bi modu daude arazo hau egin ahal izango duzu.
Bai egin dezakezu iteratively edo errekurtsiboki.
Egin daiteke errekurtsiboki aurkituko duzu gehien arazoak ere egin behar iteratively.
Hortaz, hona hemen egin dugun errekurtsiboki.
>> Ba al du norbaitek nahi zer funtzio bat recursive definitzeko esan nahi du?
[Ikasleak] funtzioa eduki deitzen bera
eta, ondoren, dei bera dator arte egia eta egia. >> Bai.
Recursive funtzio bat besterik ez da, bera deitzen duen funtzioa.
Badira hiru gauza handia recursive funtzio bat izan behar duela.
Lehenengo eta behin, jakina, bera deitzen da.
Bigarren oinarri-kasua da.
Beraz, uneren batean funtzioa bera deituz gelditzeko behar da,
eta horrek zer oinarri-kasua da.
Beraz, hemen gelditu behar dugu, ezagutzen dugu, amore eman behar dugu gure bilaketa
Irteeran berdinen amaieran, eta joan beharko dugu zer esan nahi duen.
Baina, azkenik, funtzio errekurtsiboa garrantzitsua da azken gauza:
funtzioak behar nolabait hurbiltzen base kasuan.
Atsegin dut ari zaren ez bada benetan ezer eguneratzeko bigarren dei errekurtsiboa egin duzu,
ari zaren literalki funtzioa deituz berriro bera argumentuak
aldagai global eta ez dute ezer aldatu edo,
inoiz ez dira oinarri kasuan iritsi da, kasu honetan hori da txarra.
Infinitua errekurtsibitateko eta pilaren gainezkatzea bat izan behar da izango da.
Baina hemen eguneratzea hori dugu eguneratzeko + amaiera / 2 gertatzen ari den ikusiko dugu,
azken argumentua eguneratzen ari gara hemen, hasierako argumentua eguneratzen ari gara hemen.
Beraz, dei errekurtsiboak guztietan zerbait eguneratzen ari gara. Ongi da.
Gurekin oinez zure irtenbidea bidez nahi al duzu? >> Sure.
SearchHelp erabiltzen dut, beraz, aldi bakoitzean funtzio-dei hau egiten dut
Non array bila nabil hasiera eta amaiera
non array nabil.
>> Pauso bakoitzean non erdiko elementu, hau da, Irteeran + amaiera / 2 da esaten,
hau da, zer bilatzen ari gara berdinak?
Eta bada, ondoren, aurkitu genuen, eta uste dut hori lortzen errekurtsio-maila gainditu.
Eta hori ez da egia, eta, ondoren, array erdiko balioa ez dela handiegia den ala ez egiaztatu dugu,
horrelako array ezker erdia, hasieratik erdiko indizea.
Eta bestela amaiera erdia egiten dugu.
[Bowden] Larreina.
Hori ona soinuak.
Ongi da, pare bat gauza, beraz, eta, benetan, oso goi-mailako gauza bat da
inoiz jakin behar da ikastaro hau, baina egia da.
Errekurtsiboa funtzioak, beti entzuten ari dira tratu txarra
errekurtsiboki deitzen bada zeure burua gehiegi aldiz, pilaren gainezkatzea delako lortuko duzu
geroztik, lehen esan dudan bezala, funtzio bakoitzak bere pila-markoa lortzen.
Beraz, funtzioa errekurtsiboa dei bakoitzak bere pila-markoa jasotzen du.
Beraz, bada, 1.000 dei errekurtsiboak egiten baduzu, 1.000 pila fotogramak eskuratzen
eta azkar eramaten gehiegi pila markoak eta gauzak apurtu behar izan duzu.
Beraz, zergatik recursive funtzioak dira, oro har, txarra.
Baina funtzio errekurtsiboa azpimultzo atsegina da izeneko buztan-errekurtsiboa funtzioak,
eta hau gertatzen da, non konpilatzailea ohar hau adibide bat izan
eta egin beharko lukete, uste dut Clang pasatzen duzu-O2 Ez
ondoren, nabarituko hau da buztan errekurtsiboa izango da eta gauza onak egiteko.
>> Dei errekurtsiboa bakoitzeko eta gehiagoko berriz pila berean marko berrerabiltzeko izango da.
Eta, beraz, pilaren markoa bera geroztik erabiltzen ari zara, ez duzu kezkatu beharrik
inoiz pilatu gainezka, eta aldi berean, aurretik esan duzun bezala,
non behin egia itzuliko gero, itzuli pila fotograma horiek guztiak ditu
eta SearchHelp 9ra itzultzeko dei 10ean, 8an itzultzeko.
Beraz, ez da beharrezkoa denean, funtzio buztana recursive gertatuko.
Eta beraz, zer egiten ari da funtzio-buztana hau recursive oharra dei searchHelp edozein
dei errekurtsiboa dela egiten da, zer itzuli da.
Beraz, lehen deialdian eta SearchHelp, berehala bai dugu itzultzeko faltsu,
berehala itzultzeko egia, edo dei errekurtsiboa bat egiten dugu SearchHelp
non zer itzultzen ari gara, zer dei hori itzuli.
Eta ezin dugu hau egin dugu antzeko zerbait int x = SearchHelp, bueltan x * 2 bada,
ausazko aldaketa batzuk.
>> Beraz, orain dei errekurtsiboa honetan, int x = SearchHelp dei errekurtsiboa
jada ez buztana errekurtsiboa da benetan ez dituelako itzuli
itzuli aurreko pila marko bat da, beraz, funtzio dei aurreko
ondoren, zerbait bueltan balioa.
Beraz, hau ez da buztana recursive, baina zer da nicely buztana recursive aurretik izan genuen. Bai.
[Ikasleak] Ez luke oinarri bigarren kasua da hautatuta lehenengo
egoera bat izan dezake non pasatzen argumentua
= amaieran hasteko duzu, baina orratz balioa dira.
Galdera izan zen ezin exekutatu kasua dugu, non amaiera orratz balio
edo hasi = amaieran, modu egokian, hasi = amaiera
eta ez duzu benetan balio hori bereziki hautatuta oraindik,
ondoren hasi + amaiera / 2 balio bera izango du.
Baina Jadanik itzuli faltsuak eta egia esan, inoiz ez dugu balioa egiaztatu.
Beraz, gutxienez, lehen deialdian, tamaina 0 bada, ondoren faltsuak itzuli nahi dugu.
Baina tamaina 1 bada, ondoren, Irteeran ez da berdina amaieran
eta, gutxienez, egiaztatu dugu elementu bat.
Baina une horretan amaituko hasi ahal izango dugu kasu batean non hasten + amaiera / 2 dela uste dut,
Irteeran amaitzen Irteeran + amaiera / 2 bezala,
baina inoiz ez dugu elementu hautatuta.
>> Beraz, egiaztatu lehenengo badugu erdiko elementuaren balioa da bilatzen ari gara,
ondoren, berehala itzuli ahal izango dugu egia.
Bestela, berdinak dira, gero jarraitu puntua ez da
ari gara, non bakarreko array elementu bat dugu kasu bat eguneratu du.
Duen elementu bakarra ez bada bilatzen ari gara,
ondoren, dena ez da zuzena. Bai.
[Ikasleak] gauza da tamaina geroztik benetan array elementu kopurua baino handiagoa dela,
dago dagoeneko desplazamendu bat >> Beraz, tamaina
[Ikasleak] Esan array tamaina 0 bada, ondoren SearchHelp egingo benetan egiaztatu 0 haystack
lehenengo deialdian.
>> Yeah - array tamaina 0, 0 da, beraz.
Hori beste gauza bat da ona izango da agian. Dezagun uste.
Beraz, bada array 10 elementu zituen, eta erdiko bat egiaztatu dugu index 5,
beraz, 5 ari gara egiaztapena, eta balioa txikiagoa da esan dezagun.
Beraz, dena bota ari gara 5 aurrerantzean.
Beraz, hasteko + amaiera / 2 gure berri amaiera izango da,
yeah, beraz, beti array amaieran kanpo geratzeko.
Kasu bat izan zen bakoiti edo bikoitia bada, orduan egiaztatu, dugu esango, 4,
ari gara, baina oraindik urrun bota -
Yeah Beraz, amaiera beti da array benetako amaiera haratago izango da.
Elementu ari gara bideratua Beraz, amaieran beti dago horren ondoren bat izango da.
Eta beraz, ez Irteeran inoiz berdinak amaieran, tamaina 0 array bat dugu.
>> Pentsatzen ari nintzen beste gauza Irteeran eguneratzen ari gara hasteko behar + amaiera / 2,
beraz, kasu honetan naiz I arazoak izatea, non hasten + amaiera / 2
elementu ikusten ari garen.
Demagun 10-array elementu hau izan genuen. Whatever.
Beraz, hasteko + amaiera / 2 da hau bezalako zerbait izan behar duela,
eta hori bada, ez da balioa, esan eguneratu nahi dugu.
Balioa handiagoa da, beraz, array zati honetan begiratu nahi dugu.
Beraz, nola Irteeran eguneratzen ari gara, hasiera ari gara eguneratzen orain elementu hau.
Baina hori, oraindik, lan egiteko, edo, gutxienez, hasieran egin dezakezu + amaiera / 2 + 1.
[Ikasleak] ez duzu hasteko + amaiera [inaudible] >> Bai.
Ditugu dagoeneko hautatuta elementu hau ezagutu eta ez da bat bilatzen ari gara.
Beraz, ez dugu behar elementu honen Irteeran eguneratzeko.
Besterik ez dugu saltatzeko eta eguneratzeko hasteko elementu hau.
Eta inoiz kasu bat dago, demagun, hori izan ziren amaieran,
beraz, ondoren, hasteko izango litzateke, hasteko + amaiera / 2 hau izango litzateke,
+ bukaera - Bai, azkenean errekurtsio infinitua uste dut.
Demagun tamaina 2 edo 1. Tamaina array bat besterik ez da array bat. Hau izango da lan uste dut.
Beraz, gaur egun, hasieran elementu eta amaiera haratago 1.
Beraz, elementu ari garela egiaztatzeko, hau da,
eta orduan Irteeran eguneratu dugu, hasiera ari gara eguneratzen 0 + 1/2,
den gurekin Irteeran elementu hori amaitzeko.
>> Beraz, elementu bera eta gehiagoko berriz egiaztatzen ari gara.
Beraz, kasu honetan, non dei errekurtsiboa behin eguneratu behar benetan zerbait da.
Beraz, Irteeran + amaiera / 2 + 1, edo, bestela, egin behar dugu, kasu batean
non ez ari gara benetan Irteeran eguneratzeko.
Pertsona orok ikusten?
Ongi da.
Does Edozeinek irtenbide hau edo edozein iruzkin gehiago buruzko galderak?
Ongi da. Does Edozeinek dute bat etorriko ahal dugun guztia begiratu irtenbidea?
Ba egin dugu errekurtsiboki?
Edo ere ireki hers bada, orduan gainidatzi dakizukeela Zure aurreko uste dut.
Ez du automatikoki gorde da? Ez naiz positiboa.
Does Edozeinek dute etorriko?
Bidez gara elkarrekin ez bada.
Ideia hori bera izango da.
Etorriko konponbidea.
Ideia bera, funtsean, egin nahi zaitugu
array amaiera pista eta array Irteeran berria non gorde nahi dugu
eta hori egin eta gehiagoko baino gehiago.
Eta zer pista ari gara inoiz gurutzatzen hasiera eta amaiera gisa mantenduz gero,
orduan ez genuen aurkitu eta itzuli faltsua ahal izango dugu.
Beraz, zer egin dut? Edonork edo iradokizunak kodea me tira?
[Ikasleak], berriz, begizta bat. >> Bai.
Begizta bat egin nahi duzu.
>> Ba kodea baduzu tira sortu nuen, edo zer ziren iradokitzen duzu?
[Ikasleak] Baietz uste dut. >> Guztiak eskubidea. Horrek gauzak errazagoa. Zein da zure izena?
[Ikasleen] Lucas.
Berrikusketa, ordua: 1. Ongi da.
Behe hasi aurretik deitu genuen.
Up ez da nahiko zer amaiera deitu dugu aurretik.
Egia esan, amaiera da orain array barruan. Elementu bat da, kontuan hartu behar dugu.
Beraz, baxua 0 da, array-tamaina - 1,
eta, gaur egun, ari gara begizta eta egiaztatzen ari gara
Dezakezu oinez uste dut.
Zein izan da zure pentsamendu honen bidez? Walk gurekin zure kodea bitartez.
[Ikasleak] Sure. Erdi-erdian balio haystack behatu eta konparatu orratza.
Oh, egia esan, atzeraka izan behar du - Beraz, ez da zure orratz baino handiagoa bada, eta, ondoren, nahi duzu.
Urruntzen eskuineko erdia bota nahi ari zara, eta, beraz, bai, horrela izan behar du.
[Bowden] Beraz, hau txikiagoa izan behar da? Da zer esan? >> [Ikasleak] Bai.
[Bowden] Larreina. Gutxiago.
Beraz, bada zer bilatzen ari gara, zer nahi dugun baino txikiagoa da,
ondoren, yeah, kanpoan ezker erdian bota nahi dugu,
horrek esan nahi du, guztia kontuan hartuta ari gara eguneratzen ari gara
array eskubidea baxua mugituz.
Itxura ona.
Nik uste dut gai berean, aurreko batean esan du,
non baxua 0 bada, eta sortu da 1, eta gero baxua + / 2 da berriro gauza bera egingo du.
>> Eta nahiz eta hori ez da kasua, oraindik da eraginkorragoa, gutxienez
bakarrik bota elementu begiratu besterik ez dugu da oker badakigu.
Beraz, baxua + up / 2 + 1 - >> [ikasleak] Hori beste modu batera izan behar du.
[Bowden] Edo hau izan behar du - 1 eta beste bat + 1 izan behar du.
[Ikasleak] Eta bikoitza izan beharko luke berdin ikurra. >> [Bowden] Bai.
[Ikasleen] Bai.
Ongi da.
Eta, azkenik, gaur egun dugun + 1 hau - 1 gauza
da, agian ez da baxua amaitzeko balio bat sortu baino handiagoa da inoiz posible al da?
Nik uste dut, posible al da bide bakarra hori gerta daiteke? >> [Ikasleak] ez dakit.
Baina lortzen trunkatuta bada, eta, ondoren, lortzen minus 1 eta gero - >> Bai.
[Ikasleak] litzateke ziurrenik get messed up.
Nik uste dut ona izango bakarra izan beharko luke
amaituko txikiagoa izan berdinak izan zuten, uste dut.
Baina ez dira berdinak izanez gero, orduan ez genuke egin bitartean loop hasteko
eta itzuli besterik ez dugu balio. Onak ditugu, gaur egun uste dut.
Ohartu, nahiz eta arazo hau ez da gehiago recursive,
ideia mota bera aplikatzen, non ikusi ahal izango dugu nola erraz erabaki bera
Izan ere, ari gara indizeak eguneratzeko eta gehiagoko baino gehiago berriro irtenbide recursive
arazo txikiagoak eta txikiagoak egiten ari gara, array azpimultzo bat ari gara bideratua.
[Ikasleak] baxua 0 bada, eta sortu da 1, bai lukete 0 + 1/2, 0 joan da,
eta, gero, + 1 bat litzateke, izango litzateke 1.
[Ikasleak] Non egiaztatzen dugu berdintasuna?
Atsegin dut erdiko bat benetan orratz bada?
Ez ari gara gaur egun egiten? Oh!
It's bada
Bai. Ezin dugu egin proba behera hemen demagun lehen erdian delako
[Ikasleak] benetan da nahi ez bota urruntzen doazen.
Beraz, bota duzu urruntzen bada koadernatuta, lehen edo dena delakoa ikusteko aukera izango duzu.
Ah. Bai. >> [Ikasleak] Bai.
Beraz, gaur egun, bota dugu urruntzen begiratu gaur egun dugu,
Horrek esan nahi du ere izan behar dugu
(haystack [(baxua) / 2 + up] == orratz) bada, gero itzultzeko egia ahal izango dugu.
Eta jarri ala ez dut bestela, edo, besterik gabe, bada, literalki gauza bera esan nahi du
hau itzuli lukeelako egia.
Beraz, jarri bestela dut, bada, baina ez du axola.
>> Beraz, bestela, bestela, eta hau ez dut gauza komun bat da
nahiz eta kasu non dena ona da hemen da,
baxua inoiz ez bezala sortu baino handiagoa da, eta ez da hori egia den ala ez buruzko arrazoibidea merezi.
Beraz, baita esan dezakezu baxua baino txikiagoa edo berdina bitartean
edo txikia baino txikiagoa da, berriz,
dira inoiz berdinak edo baxua bada gertatzen pasatzeko,
ondoren apurtu ahal izango dugu begizta hau.
Galderak, kezkak, iruzkinak?
Ongi da. Itxura ona.
Orain ordenatu egin nahi dugu.
Nire bigarren berrikuspena joanez gero, ikusiko dugu, zenbaki horiek berdinak
baina gaur egun jada ez dira ordena ordenatuko.
Eta sort ezartzeko n log n O algoritmoa erabiliz nahi dugu.
Duen algoritmoa Beraz, ez dugu hemen ezartzeko behar dela uste duzu? >> [Ikasleak] Batu sort.
[Bowden] Bai. Batu sort O (n log n) da eta, beraz, zer egin behar dugu.
Eta arazoa nahiko antzekoa izango da,
non erraz erabaki du bera recursive irtenbide bat.
Era berean, zatoz gora etorriko irtenbide bat nahi badugu,
baina errekurtsio errazagoa izango da hemen, eta errekurtsibitate egin behar dugu.
Uste dut merge sort bidez lehen egingo dugu oinez,
merge sort bideo eder bat da, nahiz eta dagoeneko. [Barreak]
Beraz, batu sort daude, beraz, paper hau askoz dut galdu.
Oh, ezker bakarra da.
Beraz, batu.
Oh, 1, 3, 5.
Ongi da.
Batu bi array hartzen.
Banaka bi array horiek biak sailkatuko da.
Beraz, array honetan, 1, 3, 5, ordenatuko da. Array honek, 0, 2, 4, ordenatuko da.
Orain zer merge egin behar konbinatu array bakar bat bera ordenatuko da.
Beraz, hori elementu horiek barruan tamaina 6 array nahi dugu
ordena ordenatuko.
>> Eta, beraz, abantaila hartu ahal izango dugu, hain zuzen, bi array horiek antolatuko dira
Horretarako, denbora lineal
denbora lineal esanahia array hau da tamaina x bada, eta hau da tamaina y
ondoren, guztira algoritmoa O (x + y) izan behar du. Ongi da.
Iradokizunak, beraz.
[Ikasleak] Ezin izan da ezker dugu?
Beraz, 0 jarriko duzu lehenengo eta behera ondoren, 1 eta, ondoren, hemen 2.
Beraz, fitxa bat eskuinera mugitzen atsegin mota da. >> [Bowden] Bai.
Array horietako bi besterik ez dugu ezkerreko elementu bada fokua.
Array bi antolatuko dira denez, ezagutzen dugun 2 elementu horiek
array bai elementu txikiena dira.
Beraz, horrek esan nahi du 1 2 elementu horiek gure array batu elementu txikiena izan behar da.
Beraz, zerbait gertatzen txikiena denbora eskuineko on bat da.
Beraz, 0 hartuko dugu, sartu da ezker 0 1 baino gutxiago baita,
beraz, 0 hartu, sartu gure jarrera lehen, eta, ondoren, hau eguneratu dugu
lehen elementu ardatz.
Eta orain errepikatu dugu.
Beraz, gaur egun, 2 alderatu dugu eta 1. 1 txikiagoa da, beraz, 1 sartu dugu.
Erakuslea hau eguneratu dugu guy hau seinalatu.
Orain egiten dugu berriro, beraz, 2. Honek, eguneratu egingo dira horiek, 2, 3 alderatu.
Eguneratzeak hau, ondoren, 4 eta 5.
Beraz, merge.
>> Nahiko argi dago denbora lineal besterik ez dugu elementu bakoitzaren zehar geroztik behin joan behar da.
Eta hori merge sort egiten da hau ezartzeko urrats handiena da.
Eta ez da zaila dela.
Pare bat gauza kezkatu demagun 1, 2, 3, 4, 5, 6 ginen batuz.
Kasu honetan amaituko dugu eszenatoki hori txikiagoa izango da,
ondoren erakuslea hau eguneratu dugu, hau da, txikiagoa izan behar du, eguneratu,
ko hau txikiagoa da, eta gaur egun ezagutzen duzu
denean, benetan duzun agortu elementuen alderatu.
Array hau guztia erabiltzen dugun geroztik,
array honetan dena da orain, hemen sartu.
Beraz, bada, non gure array bat da, guztiz bateratu da dagoeneko puntu sartu dugu inoiz exekutatu,
ondoren, hartu besterik ez dugu beste array elementu guztiak, eta horiek sartu array amaiera.
Beraz, ezin dugu sartu 4, 5, 6. Ongi da.
Hori da gauza bat ikustea da.
Urratsa 1 izan behar ezartzea.
Batu ordenatzeko ondoren horretan oinarrituta, 2 urrats, silly urrats 2.
Dezagun array hau.
Beraz, batu, ordenatu, 1. Pausoan da errekurtsiboki apurtu array halves sartu.
Beraz, zatitu array halves sartu.
Orain 4, 15, 16, 50 eta 8, 23, 42, 108.
Eta gaur egun egiten dugu berriro, eta horiek zatitu dugu halves sartu.
Besterik ez dut egin du alde honetan.
4, 15 eta 16an, beraz, 50.
Gauza bera egin nahi dugu hemen.
Eta orain, zatitu dugu halves berriro.
Eta 4, 15, 16, 50 ditugu.
Beraz, da gure oinarria kasua.
Array tamaina 1 dira ondoren, eta, ondoren gelditu splitting batera halves sartu.
>> Orain zer egiten dugu?
Amaituko dugu hau, halaber, 8, 23, 42, eta 108 sartu deskonposatzen.
Beraz, puntu honetan, gaur egun dugun Oraindik, gaur egun urratsa merge sort bi bikote besterik ez dago batuz zerrendak.
Beraz, horiek batzea nahi dugu. Deitu besterik ez dugu batu.
Merge horiek itzuli egingo ordena ordenatuko ezagutzen dugu.
4, 15.
Orain, horiek batzea nahi dugu, eta hori itzuli egingo ordena ordenatuko dituzten,
16, 50.
Horiek batu ditugu - ezin dut idatzi - 8, 23 eta 42, 108.
Beraz, batu bikote dugu behin.
Orain batzea besterik ez dugu berriro.
Iragarki zerrendak horietako bakoitza ordenatuko berez,
eta, ondoren, besterik gabe batu zerrenda horiek tamaina 4 zerrenda hori horrela antolatu
eta batu bi zerrenda horiek tamaina 4 zerrenda hori ordenatuko lortzeko.
Eta, azkenik, tamaina 4 zerrendak bi horiek batu ahal izango dugu tamaina 8 zerrenda hori ordenatuko lortzeko.
Beraz, hau da, oro har, n log n ikusteko, ikusi dugu dagoeneko merge dela lineala,
beraz, horiek batuz ari gara, aurre merge kostu orokorra
Zerrenda bi horien besterik ez da 2 delako
Edo ongi, n O da, baina n hemen 2 elementu hauek besterik ez da, beraz, 2 da.
Eta horiek 2 2 izango da eta horiek 2 2 izango da eta horiek 2 2 izango da,
beraz, idatzi egin behar dugun guztietan, amaituko dugu n egiten dute.
2 Like + 2 + 2 + 2 8 da, hau da, n,
beraz, multzo honetan konbinatzearen kostua n dago.
Eta gero, gauza bera hemen.
Horiek 2 batu dugu eta, ondoren, horiek 2, eta banan-banan merge hau lau eragiketa egingo da,
merge hau lau eragiketa egingo da, baina berriro ere, horien guztien artean,
amaituko dugu n batuz guztira gauzak, eta, beraz, urrats hau n hartzen du.
Hartzen du, eta, beraz, maila bakoitzean n ari fusionatuko elementuak.
>> Eta zenbat maila daude?
Maila bakoitzean, gure array tamaina 2 hazi da.
Hemen, gure array tamaina 1 dira, hemen Oraindik tamaina 2 dira, hemen Oraindik tamaina 4 dute,
eta, azkenik, tamaina 8 dute.
Beraz, geroztik bikoiztu egin da, ez dago log n maila horietan guztira izango dira.
Beraz, log n mailak, banakako maila bakoitzean hartzen n guztira eragiketak,
n log n algoritmoa lortuko dugu.
Zalantzak dituzu?
Dute jendea jada hau ezartzeko aurrera egin?
Dagoeneko egoera batean edonork non besterik ez dut tira bere kodea da?
Minutu bat eman ahal izango dut.
Hau da, luzeagoa izango da.
Gomendatzen dut marka ditzakezu
Ez daukazu errekurtsio egin merge
merge for errekurtsio direlako, neurri ezberdinetako sorta bat gainditu behar izan duzu.
, Egin dezakezu, baina izorratu egiten da.
Baina sort bera errekurtsio nahiko erraza da.
Literalki, besterik ez duzu deitu sort erdia ezkerreko, eskuineko erdia sort. Ongi da.
Edonork ezer, tira sortu dut, ezin dute?
Edo, bestela, minutu bat eman dut.
Ongi da.
Edonork zerbait lan egin ahal izango dugu?
Edo, bestela, besterik ez dugu honekin lan egin eta gero, hortik zabaltzeko.
>> Edonork hori baino gehiago izan dut tira daiteke?
[Ikasleen] Bai. Tira dezakezu nirea. >> Guztiak eskubidea.
Bai!
[Ikasleak] Baziren baldintzak asko. >> Oh, tiro. Can you
[Ikasleak] gorde behar dut. >> Bai.
Beraz, egin merge bereizita genuen.
Oh, baina ez da txarra dela.
Ongi da.
Beraz, sort bera besterik ez da mergeSortHelp deituz.
Gurekin Azaldu zer mergeSortHelp du.
[Ikasleen] MergeSortHelp pretty askoz du nagusiak bi urrats,
zein da array erdia bakoitzean ordenatzeko eta, ondoren, biak batu.
[Bowden] Ongi da, eta, beraz, ematen dit bigarren bat.
Hau uste dut - >> [ikasleak] behar dut
Bai. Falta zerbait dut.
Merge, array berri bat sortu behar dut konturatzen naiz
izan dut ez delako egin dute. >> Bai. Ezin duzu. Zuzendu.
[Ikasleak] Beraz, array berri bat sortu dut.
Ahaztua dut berriro aldatu batu amaieran.
Ongi da. Array berri bat behar dugu.
Merge sailkatu, hau da, ia-ia beti egia.
Algoritmoa hobea time-wise kostua Taldea
da ia beti pixka bat memoria gehiago erabili beharrik.
Beraz, ez du axola nola egin nahi duzu batu, ordenatu,
ezinbestean, aparteko memoria batzuk erabili behar zenuke.
Berak sortu berri array bat.
Eta gero, amaieran array berri bat kopiatu array jatorrizko besterik ez dugu behar diozu.
[Ikasleak] Baietz uste dut, bai.
Ez dakit hori erreferentzia edo dena delakoa kontatuta dagokionez -
Bai, lan egingo da. >> [Ikasleak] Larreina.
Ba hau abiarazi saiatu duzu? >> [Ikasleak] Ez, oraindik ez. >> Ados.
Saiatu exekutatzen ari da, eta, ondoren, horri buruz hitz egin dut, segundo bat.
[Ikasleak] funtzioa prototipoak eta dena izan behar dut, hala ere, ezta?
Funtzioa prototipoak. Oh, esan nahi duzun bezala - Bai.
Ordena da mergeSortHelp deituz.
>> Beraz, ordena sort mergeSortHelp deitu mergeSortHelp behar bai dira definitzen
sort aurretik edo besterik ez dugu behar prototipoa. Just kopiatu eta itsatsi dela.
Eta, era berean, mergeSortHelp da batu deituz,
baina merge ez du oraindik zehaztu dira, eta, beraz, besterik gabe, ezin dugu utzi mergeSortHelp jakin
horrek zer batzea da itxura, eta hori da hori.
MergeSortHelp Beraz.
Arazo bat izan behar dugu hemen, non oinarria inolaz ere ez dugu.
MergeSortHelp errekurtsiboa da, beraz, funtzioa errekurtsiboa edozein
base kasuan nolabaiteko behar denean gelditzeko errekurtsiboki bera deituz jakin behar da.
Zer dira gure oinarria kasuan gertatzen da hemen? Bai.
[Ikasleen] tamaina 1 bada? >> [Bowden] Bai.
Horrela ikusi genuen bertan, splitting array gelditu
tamaina 1, array, ezinbestean antolatuko dira bere buruari behin lortu dugu.
Beraz, tamaina berdinen 1 bada, array dagoeneko horrela antolatu ezagutzen dugu,
beraz, bakarrik itzuli ahal izango dugu.
>> Iragarki hori void, beraz, ez dugu ezer bereziki itzultzeko, itzuli besterik ez dugu.
Ongi da. Beraz, gure kasuan.
Izan ere gure kasuan gertatuko dugu batuz tamaina 0 array bat asmatzen dut,
uneren batean gelditu nahi dugu, ziurrenik,
beraz, besterik gabe, esan dezakegu tamaina baino gutxiago 2 edo gutxiago 1 edo berdin
dela, beraz, hau izango da array edozein lan egiteko.
Ongi da.
Beraz, gure kasuan.
Orain gurekin oinez merge bidez nahi al duzu?
Zer Kasu horiek guztiak esan nahi du?
Hemen, bakarrik ari gara ideia bera egiten, -
[Ikasleak] pasatuz tamaina mergeSortHelp deiak behar dut.
Tamaina gehitu dut lehen osagarri gisa, eta ez da, tamaina / 2 bezala.
[Bowden] Oh, tamaina / 2, size / 2. >> [Ikasleen] Bai, eta, gainera, funtzio gainetik ere.
[Bowden] Hona hemen? >> [Ikasleak] Just tamaina. >> [Bowden] Oh. Tamaina, tamaina? >> [Ikasleak] Bai.
[Bowden] Larreina.
Uste bigarren bat me.
Exekutatu arazo bat dugu?
Beti ari gara ezker tratatzeko 0. >> [Ikasleen] N º
Hori gertatzen da ere. Sentitzen dugu. Irteeran izan behar da. Bai.
[Bowden] Larreina. Hobea gustatzen zait.
Eta amaiera. Ongi da.
Beraz, gaur egun ez gurekin oinez merge bidez nahi al duzu? >> [Ikasleak] Larreina.
Besterik ez dut dudan array berri honen bidez sortu oinez.
Bere tamaina array zati tamaina nahi dugun ordenatuko da
eta elementu array urrats berri jarri behar dut bila.
Beraz, horretarako, lehenik eta behin array ezkerreko erdia gehiago elementu jarraitzen dut egiaztapena
eta ez bada, eta gero behera joan behar da, bestela, egoera hori, besterik ez dio
ados, eskuineko array behar da, eta hori jarriko dugu uneko indizea newArray.
>> Eta gero, bestela, array-eskuinaldean ere bada amaitu dut egiaztapena
Kasu horretan, ezker besterik ez dut jarri.
Agian ez da beharrezkoa izango. Ez nago ziur.
Baina, hala ere, beste bi kontrol bi zein ezkerreko edo eskuineko txikiagoak dira.
Eta, gainera, kasu bakoitzean, edozein biltegian I Kontatzailea dut incrementing.
[Bowden] Larreina.
Hori itxura ona.
Does Edozeinek iruzkinak edo kezka edo galdera?
Beraz, itxura edo bost bezala lau kasu besterik ez izatea gauza ekarri dugun -
baina ea ezker array agortu du gauzak batu behar dugu kontuan hartu behar dugu,
array eskubidea duen ala ez agortu du gauzak batu behar dugu
Ezer ez dut seinalatuz.
Beraz, ezker array ez du agortu gauza edo eskubidea array agortu du gauza.
Dutenek bi kasu.
Ezkerreko gauza da eskuineko gauza baino gutxiago edo kasuan trivial ere egin beharko dugu.
Ondoren, ezkerreko gauza aukeratu nahi dugu.
Horiek dira kasu guztietan.
Beraz, hau da eskubidea, eta, beraz, hori da, beraz.
Array utzi. 1, 2, 3. Ongi da. Beraz, bai, horiek dira lau gauza egin nahi dugu agian.
Eta ez dugu bat etorriko irtenbide baino gehiago joan.
Ez nuke gomendatuko
Batu nolako funtzio bat da, bai ez buztana recursive adibide bat da,
Ez da erraza da buztana recursive egiteko,
baina, aldi berean, ez da oso erraza etorriko egiteko.
Hau da, oso erraza da.
Merge sort ezartzeko honek,
batu, ez du axola zer egin nahi duzu, merge eraikitzeko duzu.
>> Beraz, batu errekurtsiboki sort konbinazio gainean eraikitako hiru lerro hauek besterik ez da.
Iteratively, gogaikarriak eta zailagoa pentsatu da.
Baina ez dela buztana mergeSortHelp geroztik recursive - bera deiak -
behar du, hala ere, gauzak egiteko dei errekurtsiboa honetan itzultzen ondoren.
Beraz, pila fotograma honetan ere hau deituz ondoren existitzen jarraitu behar du.
Eta orduan, hau deitu, pila-markoa existitzen jarraitu behar
dei hori ere behar delako ondoren, oraindik batu.
Eta nontrivial da buztan hau recursive egiteko.
Zalantzak dituzu?
Guztiak eskubidea.
Beraz, atzera joan ordenatzeko - oh, bi gauza erakutsi nahi dut. Ongi da.
Atzera eginez, ordenatu, azkar egin dugu.
Edo bilaketa. Ordena? Ordena. Bai.
Atzera eginez sort hasieratik.
Algoritmo bat ordenatzen array algoritmoa erabiliz sortu nahi dugu
n O.
Beraz, nola da posible hau? Does Edozeinek edozein
Hinted aurretik I -
Gara, bada log n n n O hobetzeko,
hobetu egin dugu gure algoritmoa time-wise,
horrek esan nahi du zer egin nahi egin behar dugu?
[Ikasleak] Space. >> Bai. Leku gehiago erabiltzen ari gara.
Eta ez, besterik gabe, leku gehiago, esponentzialki leku gehiago da.
Beraz, algoritmo-mota hori sasi zerbait, pseudo polynom dela uste dut
pseudo - ezin dut gogoratzen. Pseudo zerbait.
Baina behar dugu hainbeste espazioa erabili nahi dituelako da
hori lor da, baina ez da errealista.
>> Eta nola egin hori lortzeko?
Hau lortu ahal izango dugu bermatzen badugu array bereziki edozein elementu
azpitik dago, tamaina jakin bat.
Hargatik, besterik gabe esan tamaina 200,
array batean edozein elementu da, tamaina 200 baino gutxiago.
Eta hori da, benetan, oso errealista da.
Oso erraz egin dezakezu array bat ezagutzen duzun guztia
zenbaki bat baino gutxiago izango da.
Duzu bektore edo zerbait erabat masiboa
baina dena da 0 eta 5 bitartean izango badakizu,
ondoren, nabarmen Horretarako azkarragoa izan da.
Eta elementu edozein doazen 5 da,
doazen honetan, beraz, hau da, zenbat memoria erabiltzen ari zaren.
Beraz, koadernatuta 200 da.
Teorian, beti dago doazen zenbaki oso bat besterik ezin da 4 milioi,
baina hori gero erabili beharko genuke espazio geroztik unrealistic
4 milioi ordena. Beraz, unrealistic.
Baina hemen gure doazen esan dugu 200.
N O egiten trikimailu izeneko tamaina zenbatzen Bound beste array bat egin dugu.
Beraz, benetan, hau lasterbide bat da, ez benetan ez dakit Clang ez bada.
Baina, gutxienez GCC - I'm suposatuz Clang du ere
hau, array osoa hasieratu 0 s izan.
Beraz, ez dut nahi ez badu horretarako, eta, ondoren, banan-banan izan nuen egin for (int i = 0;
i <Bound; i + +) eta zenbatzen [i] = 0;
Beraz, gaur egun dena da 0 hasieratu.
Batetik bestera joateko baino gehiago dut nire array
eta zer egiten ari naiz, bakoitzaren kopurua dut kontatuta - jaisten da hemen.
4, 15, 16, 50, 8, 23, 42, 108 ditugu.
Kontatuta naiz elementu horiek bakoitzaren agerraldi-kopurua da.
Dezagun benetan gehitu pare bat gehiago hemen errepikatzen batzuekin batera.
Balioa Beraz, hemen dugu, horren balioa array [i].
Beraz, val 4 edo 8 edo dena delakoa izan daiteke.
Eta orain, zenbat balio duten ikusi dut dut kontatuta,
zenbatzen da, beraz [val] + +;
Hori egin ondoren, zenbatzen da 0001 bezalako zerbait bilatzeko.
Egin dezagun zenbatzen [val] - Bound + 1.
>> Orain besterik Izan ere, 0-tik hasten ari garela kontuan.
Beraz, 200 bada gure gehien izango
0 200 201 gauza da.
Zenbatzen Beraz, 00001 bezala izango da begiratu bat dugu 4 delako.
Ondoren, 0001 non 1 izan dugu Aldaketa 8an indizea izan dugu.
Aldaketa 23an indizea 2 bat izango dugu.
Aldaketa indizea 42 2 bat izango dugu.
Beraz Aldaketa erabili ahal izango dugu.
Beraz num_of_item = zenbatzen [i].
Eta hala bada num_of_item 2 da, eta horrek esan nahi du 2 txertatzeko kopurua i nahi dugu
gure array horrela antolatu du.
Beraz, segimendua egiteko, noraino dira array sartu behar dugu.
Beraz, index = 0.
Array - besterik ez dut idatzi.
Condes -
array [index + +] = i;
Da zer esan nahi dut? Nik uste dut, hori da nahi dudana.
Bai, hau itxura ona. Ongi da.
Beraz, ez denek ulertzen zer da nire zenbatzen array helburua?
, Zenbaki horiek bakoitzaren agerraldi kopurua da kontatuta.
Ondoren, bit baino gehiago naiz hori zenbatzen array,
eta zenbatzen array posizio Ith
i da kopuru hori behar ordenatuko nire array agertzen da.
Horregatik, 4 zenbatzen 1 izango
eta 8 de zenbatzen 1 izango da, 23 zenbatzen 2 izango da.
Beraz, nola horietako asko nire array ordenatuko txertatzeko nahi dut.
Ondoren, egin dut.
Num_of_item dut txertatu nire array ordenatuko sartu i.
>> Zalantzak dituzu?
Eta, beraz, berriro ere, denbora lineala ari gara geroztik honetan zehar behin errepikatzean,
baina, aldi berean zenbaki hau gertatzen da lineala,
eta, beraz, zein den zure doazen handia araberakoa da.
200 doazen batekin, hori ez da txarra dela.
Zure doazen 10.000 izan nahi baduzu, eta gero apur bat okerragoa,
baina zure koadernatuta dago 4 milioi dolarrekoa izango, bada, guztiz unrealistic
eta array hau tamaina 4 milioi, hau da, unrealistic izango dute.
Beraz, hori. Zalantzak dituzu?
[Inaudible ikaslearen erantzuna] >> Ados.
Beste gauza konturatu nintzen joan ginen.
Nik uste dut arazoa Lucas eta ziurrenik behin bakar bat ikusi dugu.
Ahaztua dut erabat.
Behar duzu nahi nuen gauza bakarra da indize bezalako gauzak aurre ari zaren,
benetan inoiz ez ikusiko duzu noiz ari zaren idazteko loop,
baina teknikoki, betiere indizeak hauekin ari zaren aurre,
pretty askoz behar duzu beti. zeinurik gabeko osoko zenbakien aurre egiteko.
Horren arrazoia denean,, zenbaki osoen sinatu ari zaren aurre,
hala badagokio sinatu zenbaki osoen 2 eta gehitu zaituzte elkarrekin
eta azkenean handiegia, eta gero azkenean zenbaki negatiboa.
Beraz, zer da zenbaki oso gainezkatze bat.
>> 2 milioi eta 1 milioi gehitu bada, amaitzeko I 1 negatiboa milioi.
Hori da, zenbaki osoko ordenagailuak nola lan egiten.
Erabiliz arazoa Beraz
Hori da bada ongi baxua gertatzen da 2 milioi dolarrekoa izango, eta sortu gertatzen 1 milioi dolarrekoa izango,
ondoren, hau da, negatiboa 1 milioi izango da eta ondoren, zatitzen dugu 2
eta, azkenean, 500 negatiboa milioi.
Beraz, hau arazo bat bakarrik gertatuko baduzu array baten bidez bilatzen da
bilioika gauza.
Baina baxua + sortu gainezkatzea gertatzen bada, ondoren, arazo bat.
Eta, ondoren, ahalik eta azkarren egin ditugu unsigned 2 milioi milioi plus 1 3 milioi da.
3 milioi 2 arabera banatzen da 1,5 milioi da.
Beraz, ahalik eta azkarren unsigned Oraindik ere, dena ezin hobea da.
Eta, beraz, hori ere arazo bat zure zaren idazten loops,
eta, benetan, ez ziur aski, automatikoki.
Benetan izango da besterik ez duzu Yell.
Beraz, kopurua handiegia da zenbaki oso bat besterik ez da, baina zeinurik gabeko osoko zenbaki bat egokitzen litzateke,
egingo du Yell, beraz, zergatik benetan ez da inoiz gai sartu exekutatu.
Indizea ez da inoiz negatiboa izango dezakezu,
eta, beraz, array bat baino gehiago ari zaren errepikatzean,
ia beti dezakezu esan unsigned int i, baina ez duzu benetan izan.
Things dira pretty askoz ere lan egiteko besterik ez baita.
Ongi da. [Xuxurlatzen] Zer ordu da?
Azken gauza erakutsi nahi nuen, eta besterik ez dut egin azkarrak benetan.
Nola # dugu # zehaztu ahal izango dugu, beraz, 5 edo zerbait gisa definitzen MAX ezagutzen duzu?
Dezagun ez MAX. # Define 200 gisa aritzeko. Horixe aurretik genuen.
Hori konstante bat da, hau da, besterik gabe, kopiatu eta itsatsi definitzen
lekuan Bound idatzi gertatuko dugu.
>> Beraz, benetan ahal izango dugu # definitzen.
Funtzio # zehaztu ahal izango dugu.
Oraindik ez dute benetan funtzioak, baina dei horiek funtzio dugu.
Adibide bat MAX (x, y) bezalako zerbait izango litzateke (?: X x <y y) bezala definitzen da. Ongi da.
Beraz, hirutarra adibidez operadorea sintaxia get erabili behar da,
baina ez da x y baino gutxiago? Itzuli y, x bestela itzultzeko.
Beraz, ikusi hau funtzio bereizi bat egin dezakezu dezakezu,
eta funtzioa boolearra MAX 2 argumentu bezala izan daiteke, itzultzeko.
Direnak ohikoena ikusten dut atsegin dute hau egin da. Horietako makro deitzen dugu.
Makro bat da.
Hau besterik ez da sintaxia.
Makro bat idatzi nahi duzuna egin dezakezu.
Maiz ikusiko duzu makro, printfs eta stuff arazteko.
Printf mota daude, beraz, berezia C konstanteak azpimarra bezalako LINE azpimarra
2 azpimarrak LINE azpimarra
eta han ere 2 azpimarrak Bil uste dut. Hori izan daiteke. Horrelako zerbait.
Gauza horiek funtzioaren izena ordeztuko dira
edo lerroan zaudela kopurua.
Maiz, arazteko printfs behera hemen orduan ezin dut idatzi idazten
Arazteko eta lerro-kopurua eta funtzioa izango gerta inprimatu egingo du
aurkitu duela arazteko adierazpena.
Eta gainera, beste gauza batzuk inprima dezakezu.
Beraz, gauza bat da watch out behar duzu gertatuko badut # define DOUBLE_MAX
moduko zerbait, 2 * y 2 * x.
Beraz, edozein arrazoigatik, asko gertatuko duzu.
Beraz, makro bat.
Hori benetan hautsi.
Deitu nuke DOUBLE_MAX (3, 6) antzeko zerbait eginez.
Beraz, zer itzuli behar?
[Ikasleak] 12.
Bai, 12 itzuli behar da, eta 12 itzuliko da.
3 lortzen x ordezkatu, 6 lortzen y ordezkatu, eta 2 * 6 itzuliko gara, hau da, 12.
Orain zer gertatzen da hau? Zer itzuli behar?
[Ikasleak] 14. >> Egokiena, 14.
Arazoa da nola definitzen hash lana, gogoratu hitzez hitz kopiatu eta itsatsi
dena nahiko askoz, beraz, zer hori behar bezala interpretatu
3 2 1 plus 6, aldiz, 1 plus 6, 2 aldiz 3 baino txikiagoa da.
>> Hori dela eta, beraz, itzulbiratu ia beti parentesi artean duzun guztia.
Edozein aldagai ere, parentesi artean ia beti biltzeko.
Daude kasu non ez duzu, ez dakit, ez da horretarako beharrik ez hemen bezala
baino gutxiago delako pretty askoz beti lanera joan
agian ez, nahiz eta egia izan arren.
DOUBLE_MAX (1 == 2) bezalako zerbait barregarria bada,
Orduan, 1 3 baino gutxiago ordeztu berdin berdin 2,
eta, beraz, ondoren 3 1 baino gutxiago egin da joan, eta ez berdintasunaren 2
eta hori ez da zer nahi dugun.
Beraz, edozein operadorea lehentasuna arazoak saihesteko,
beti parentesi biltzeko.
Ongi da. Eta hori izan da, 5:30.
Behar duzu pset buruzko zalantzarik izanez gero, iezaguzu.
Dibertigarria izan behar du, eta hacker edizioan ere askoz ere errealista da
iazko edizioan hacker baino, eta, beraz, espero dugu asko saiatu da.
Iaz oso erabatekoa izan zen.
>> [CS50.TV]