[Powered by Google Translate] [Sekcio 3 - Pli Vasta]
[Rob Bowden - Universitato Harvard]
>> [Jen CS50. - CS50.TV]
>> Do la unua demando estas strange worded.
GDB permesas "elpurigi" programo, sed, pli specife, kion signifas tio lasu vin fari?
Mi respondos, ke unu, kaj mi ne scias kio precize atendis,
tial mi konjektas estas iu laŭ la linioj de ĝi permesas paŝo post paŝo
trairu la programo, interagi kun ĝi, ŝanĝo variabloj, faras cxion cxi tion -
esence tute kontroli ekzekuto de programo
kaj inspekti ajna parto de la ekzekuto de la programo.
Do tiuj karakterizaĵoj lasu vin elpurigi aĵoj.
Okay.
Kial duuma serĉo postulas ke tabelo estos ordo?
Kiu volas respondi?
[Studento] Ĉar ĝi ne funkcias se ĝi ne ordo. >> Jes. [Ridado]
Se ĝi ne ordo, tiam ĝi estas neebla al fendi ĝin en duono
kaj scias, ke ĉiu al la maldekstra estas malpli kaj ĉiu al la dekstra
estas pli granda ol la meza valoro.
Do devas esti ordo.
Okay.
Kial bobelo varo en ho de n kvadratoj?
Ĉu iu unua volas doni tre rapida alta nivelo superrigardon pri kio bobelo varo estas?
[Studento] Vi esence iri tra ĉiu elemento kaj vi kontrolu la unuaj kelkaj elementoj.
Se ili estas el kie vi interŝanĝi ilin, tiam vi kontrolu la venontaj elementoj kaj tiel plu.
Kiam vi atingas la fino, tiam vi scias ke la plej granda ero metiĝas ĉe la fino,
tiel vi ignoras tiu tiam vi daŭre iras tra,
kaj ĉiufoje vi havas por kontroli unu malpli ero ĝis vi ne faru ŝanĝojn. >> Jes.
Ĝi estas nomita bobelo speco ĉar se vi klaki la tabelo sur lia flanko tuj kiam estas supren kaj malsupren, vertikala,
tiam la grandaj valoroj enprofundigos al la fundo kaj la malgrandaj valoroj volo bobelo ĝis la supro.
Tiel estas kiel ĝi alvenis lia nomo.
Kaj jes, vi simple iru tra.
Vi daŭre iras tra la tabelo, interŝanĝi la granda valoro
atingi la plej grandan valorojn al la fundo.
>> Kial ho de n kvadratoj?
Unue, ĉu iu volas diri kial ĝi estas ho de n kvadratoj?
[Studento] Ĉar por ĉiu run iras n fojojn.
Vi povas nur esti certa, ke vi prenis la plej grandan elementon tuta vojo suben,
tiam vi devas ripeti ke dum tiom da elementoj. >> Jes.
Do memoru, kion granda a signifas kaj kion granda omega rimedoj.
La granda O estas kiel la supera baro sur kiel malrapida ĝi povas efektive kuri.
Do dirante ke estas ho de n kvadratoj, ne estas ho de n alie ĝi povus funkcii
en lineara tempo, sed ĝi estas O de n potenco de
ĉar ĝi estas barita per O de n potenco de.
Se ĝi estas barita per O de n kvadratoj, tiam ĝi estas barita ankaŭ per n potenco de.
Do ĝi estas n kvadratoj, kaj en la absoluta plej malbona kazo ĝi ne povas fari pli bone ol n kvadratoj,
tial ĝi estas O de n kvadratoj.
Do por vidi malpezan math ĉe kiel eliras esti n kvadratoj,
se ni havas kvin aĵojn en nia listo, la unua fojo kiom svopoj ni povus potenciale bezonos fari
por atingi tion? Ni fakte ĝuste -
Kiom da svopoj ni tuj devos fari en la unua kuro de bobelo speco tra la tabelo?
[Studento] n - 1. >> Jes.
>> Se estas 5 eroj, ni tuj bezonos fari n - 1.
Tiam sur la dua kiom svopoj ni tuj devos fari?
[Studento] n - 2. >> Jes.
Kaj la tria tuj esti n - 3, kaj tiam por oportuneco Mi skribos la lastaj du
kiel do ni tuj bezonos fari 2 svopoj kaj 1 interŝanĝa.
Mi supozas ke la lasta povas aŭ ne vere bezonas okazi.
Ĉu tio estas interŝanĝa? Mi ne scias.
Do tio estas la tuta kvanto de svopoj aŭ almenaŭ komparoj vi devas fari.
Eĉ se vi ne interŝanĝas, vi ankoraŭ bezonas kompari la valoroj.
Do estas n - 1 komparoj en la unua kuro tra la tabelo.
Se vi reordigi tion, ni vere faras ses aferoj estas tiel aĵoj pilo supren bele,
kaj tiam Mi faros 3, 2, 1.
Do ĝuste reordigante tiuj sumoj, ni volas vidi kiom da komparoj ni faras
en la tuta algoritmo.
Do, se ni alportos tiuj infanoj cxi tie,
tiam ni ankoraŭ nur sumanta tamen multaj komparoj estis.
Sed se ni resumi tiujn kaj ni resumi tiujn kaj ni resumi tiujn,
ĝi estas ankoraŭ la sama problemo. Ni nur resumi tiujn apartajn grupojn.
>> Do nun ni sumanta 3 n-aj jaroj. Ne nur 3 n-aj jaroj.
Ĝi estas ĉiam tuj estos n / 2 n-aj jaroj.
Do jen ni hazarde havas 6.
Se ni havis 10 aĵoj, tiam ni povus fari ĉi grupo por 5 malsamaj paroj de aĵoj
kaj fini kun n + n + n + n + n.
Do vi ĉiam ricevos n / 2 n estas, kaj tial ĉi ni jot ĝin al n kvadrataj / 2.
Kaj tial, kvankam ĝi estas la faktoro de duono, kio okazas veni en
pro la fakto ke per ĉiu ripeto super la tabelo oni komparas 1 malpli
por ke estas kiel ni preni la super 2, sed estas ankoraŭ n kvadratoj.
Ni ne zorgas pri la konstanta faktoro de duona.
Do multan granda a stuff kiel ĉi dependas nur speco de fari ĉi speco de Y,
fari aritmetikajn sumoj kaj geometria serio stuff,
sed plej multaj el ili en ĉi tiu kurso estas bela simpla.
Okay.
Kial inserción varo en omega de n? Kion omega signifas?
[Du studentoj parolis samtempe - nekomprenebla] >> Jes.
Omega vi povas pensi pri kiel la suba baro.
>> Do ne gravas kiom efika vian inserción speco algoritmo estas,
sendepende de la listo ke tio pasis en, ĝi ĉiam devas kompari almenaŭ n aĵoj
aŭ ĝi devas persisti super n aĵoj.
Kial estas tio?
[Studento] Ĉar se la listo estas jam ordo, tiam tra la unua ripeto
vi nur povas garantii ke la unua elemento estas la malplej,
kaj la dua iteracio vi nur povas garantii la unua du estas
ĉar vi ne scias, ke la resto de la listo estas ordigita. >> Jes.
Se pasas en tute ordo listo, almenaŭ vi devas iri super ĉiuj elementoj
vidi ke nenio bezonas al esti movita ĉirkaŭ.
Do pasas super la listo kaj dirante oh, tio estas jam ordo,
estas neebla por vi scii ĝi estas ordo ĝis vi kontrolu ĉiun elementon
vidi ke ili estas en ordo ordo.
Do la suba baro sur inserción varo estas omega de n.
Kio la plej malbona kazo rula tempo de merge varo,
plej malbona kazo esti granda a denove?
Do, en la plej malbona kazo scenejo, kiom tio merge speco kuri?
[Studento] N log n. >> Jes.
La plej rapida ĝenerala klasifiko algoritmoj estas n logo n. Vi ne povas fari pli bone.
>> Ekzistas specialaj kazoj, kaj se ni havas tempon hodiaŭ - sed ni verŝajne won't -
ni povis vidi kiu faras pli bone ol n logo n.
Sed en la ĝenerala kazo, vi ne povas fari pli bone ol n logo n.
Kaj kunfandi speco hazarde estas tiu, kiun vi devas scii por ĉi tiu kurso ke estas n logo n.
Kaj tiel ni vere povas efektivigi ke hodiaŭ.
Kaj fine, en ne pli ol tri frazoj, kiel faras elekton speco laboro?
Ĉu iu volas respondi, kaj mi rakontos viaj frazoj
ĉar se vi transiru 3 -
Ĉu iu memoras selektado speco?
Selektado varo estas kutime bela facile memori nur de la nomo.
Vi nur persisti super la tabelo, trovi kion ajn la plej granda valoro estas aŭ malgranda -
kion ajn celo vi ordigi in
Do diru ni ordigi de malgranda al la plej granda.
Vi persisti super la tabelo, serĉante ajn la minimuma elemento estas,
elektu ĝin, kaj tiam nur interŝanĝi ĝin kio ajn en la unua loko.
Kaj poste sur la dua pasas super la tabelo, serĉi la minimuma ero denove,
elektu ĝin, kaj tiam interŝanĝi ĝin kun kio estas en la dua pozicio.
Do ni estas nur pluki kaj elektante la minimuma valoroj
kaj enmeto ilin en la fronto de la tabelo ĝis estas ordo.
Demandojn sur tio?
>> Tiuj neeviteble aperas en la formoj vi devas plenigi kiam vi submetis la pset.
Tiuj estas esence la respondojn al tiuj.
Konsentite, tiel nun kodigo problemojn.
Mi jam sendis pli ol retpoŝto - Ĉu iu ne havas tiun retmesaĝon? Okay.
Mi jam sendis pli ol retpoŝto la spaco kiu ni tuj estos uzante,
kaj se vi klakas sur mia nomo - do mi kredas ke mi esti en la fundo
ĉar el la malantaŭen r - sed se vi klakas sur mia nomo vi vidos 2 revizioj.
Revizio 1 tuj estos mi jam kopiis kaj pasted la kodon en Spacetoj
por la serĉo afero vi tuj devos apliki.
Kaj redaktoj 2 estos la varo kiu ni implemento post tio.
Do vi povas klaki sur mia Revizio 1 kaj labori de tie.
Kaj nun ni volas apliki duuma serĉo.
>> Ĉu iu volas nur doni _pseudocode_ altnivela ekspliko
de kio ni tuj devas fari por serĉo? Yeah.
[Studento] Vi nur preni la mezo de la tabelo kaj vidu se kion vi serĉas
estas malpli ol tiu aŭ pli ol tio.
Kaj se ĝi estas malpli, vi iras al la duono jen malpli,
kaj se ĝi estas pli, iru al la duono kiu estas pli kaj vi ripetas ke ĝis vi simple akiri unu afero.
[Bowden] Yeah.
Rimarku ke nia nombroj tabelo jam ordo,
kaj por ke signifas, ke ni povas utiligi tiun kaj ni povus unue kontrolu,
estas bone, Mi serĉas la numeron 50.
Do mi povas iri al la mezo.
Mezo estas malfacile difini kiam estas para kvanto de aĵoj,
sed ni nur diros ni ĉiam detranĉi al la mezo.
Do jen ni havas 8, do la mezo estus 16.
Mi serĉas 50, do 50 estas pli granda ol 16.
Do nun mi povas baze trakti mian tabelo kiel tiuj elementoj.
Mi povas forĵeti ĉion de 16 pli.
Nun mia tabelo estas nur tiuj 4 elementoj, kaj mi ripetas.
Tial mi volas trovi la mezo denove, kio tuj estos 42.
42 estas malpli ol 50, do mi povas forĵeti tiujn du elementoj.
Ĉi tio estas mia cetera tabelo.
Mi iros por trovi la mezo denove.
Mi supozas 50 estis malbona ekzemplo ĉar mi ĉiam ĵetante sin aĵojn al la maldekstra,
sed por la sama mezuro, se Mi serĉas ion
kaj estas malpli ol la elemento Mi nune rigardas,
tiam Mi iros forĵeti ĉion por la rajto.
Do nun ni devas apliki tion.
Rimarku ke ni bezonas por pasi de grandeco.
Ni povas ankaŭ ne bezonas malmola kodo grandeco.
Do, se ni liveri de tiu # difini -
Okay.
Kiel mi povas bele elkompreni kiel la grandeco de la nombroj tabelo aktuale estas?
>> Kiom da elementoj estas en la numeroj tabelo?
[Studento] Nombroj, krampoj,. Longo?
[Bowden] Tio ne ekzistas en C.
Bezonas. Longa.
Arrays ne havas propraĵoj, do ne estas longo propraĵo de tabeloj
ke estos ĝuste doni al vi tamen longe okazas esti.
[Studento] Vidu kiom memoro estas kaj dividi per kiom - >> Jes.
Do kiel ni povas vidi kiom da memoro ĝi havas? >> [Studento] sizeof. >> Jes, sizeof.
Sizeof estas la operatoro ke tuj revenos la grandeco de la nombroj tabelo.
Kaj tiu tuj estos tamen multaj entjeroj estas fojoj la grandeco de entjero
ĉar tio estas kiel multe memoro ĝi estas efektive prenas tion.
Do se mi volas ke la nombro de aĵoj en la tabelo,
tiam mi tuj volas dividi per la grandeco de entjero.
Okay. Do kiu lasas min pasi en grandeco tie.
Kial mi bezonas por pasi de grandeco ajn?
Kial mi ne nur faru ĉi tien int grandeco = sizeof (fojnamaso) / sizeof (int)?
Kial ĉi tio ne funkcias?
[Studento] Ne estas malloka variablo.
[Bowden] Haystack ekzistas kaj ni pasante en nombroj kiel fojnamaso,
kaj jen estas ia prefiguración de kio estas venonta. Yeah.
[Studento] Haystack estas nur la referenco al ĝi, do ĝi revenus kiom granda ke referenco estas.
Yeah.
Mi dubas en prelego, kiun vi vidis la pilo tamen vere, ĉu ne?
Ni ĵus parolis pri ĝi.
Do la pilo estas kie ĉiuj viaj variabloj tuj estos stokitaj.
>> Neniu memoro ke tio destinis por lokaj variabloj tuj en la pilo,
kaj ĉiu funkcio prenas lian propran spacon en la pilo, lia propra stako kadro estas kio ĝi estas nomata.
Do ĉefa havas sian pilo kadro, kaj ene de ĝi tuj ekzistas ĉi nombroj tabelo,
kaj tio okazas al esti de amplekso sizeof (nombroj).
Ĝi tuj devos grandeco de nombroj dividitaj de grandeco de elementoj,
sed ke ĉiuj vivoj ene ĉefa La pilo kadro.
Kiam ni nomas serĉo, serĉo ricevas sian propran pilo kadro,
lia propra spaco por stoki ĉiuj ties lokaj variabloj.
Sed tiuj argumentoj - tiel fojnamaso ne estas kopio de tiu tuta tabelo.
Ni ne pasas en la tuta tabelo kiel kopion en serĉo.
Ĝi simple pasas referenco al tiu tabelo.
Do serĉo povas aliri tiujn numerojn por ĉi tiu referenco.
Ĝi estas ankoraŭ aliri la aferojn kiuj vivas ene de ĉefaj la pilo kadro,
sed esence, kiam ni atingos punteros, kiu devus esti poste,
ĉi tio estas kion punteros estas.
Punteros estas nur aludoj al aĵoj, kaj vi povas uzi punteros aliri aĵoj
kiuj estas en aliaj aĵoj 'stako kadroj.
Do eĉ se nombroj estas loka al ĉefa, ni povas ankoraŭ konsenti li tra ĉi puntero.
Sed ĉar ĝi estas nur montrilo kaj estas nur referenco,
sizeof (fojnamaso) ĝuste redonas la grandecon de la referenco mem.
Ĝi ne redonas la grandeco de la aĵo ĝi estas indikante.
Ne denove la reala grandeco de nombroj.
Kaj tiel ĉi tio ne tuj funkcias kiel ni volas ke ĝi.
>> Demandojn sur tio?
Punteros estos eniris en signife pli sangriento detalo en semajnojn por alveni.
Kaj jen estas tio multon, kiun vi vidas, plej serĉo aĵoj aŭ varo aferojn,
ili estas preskaŭ ĉiuj tuj bezonas preni la reala grandeco de la tabelo,
ĉar en C, ni ne havas ideon kion la grandeco de la tabelo estas.
Vi devas permane pasi ĝin in
Kaj vi ne povas permane pasi en la tuta tabelo ĉar vi ĵus pasis en la referenco
kaj ĝi ne povas atingi la grandecon de la referenco.
Okay.
Do nun ni volas apliki tion, kio estis klarigita antaŭe.
Vi povas labori sur ĝi dum minuto,
kaj vi ne devas zorgi pri akirante ĉio perfekte 100% laboras.
Nur redakti la duono _pseudocode_ por kiom vi kredas ke devus funkcii.
Okay.
Neniu bezonas esti tute farita kun tiu ankoraŭ.
Sed ĉu iu sentas komforte kun kion ili havas ĝis nun,
kiel iu povas labori kun kune?
Ĉu iu volas volontulon? Aŭ mi hazarde elektas.
Ĝi ne devas esti ĝuste per ia mezuro sed iu povas modifi enen laborante stato.
[Studento] Certe. >> Bone.
Do vi povas savi la revizio klakante sur la eta Save ikono.
Vi estas Ramya, ĉu ne? >> [Studento] Yeah. >> [Bowden] Okay.
Do nun mi povas vidi vian revizio kaj ĉiuj povas tiri supren la revizio.
Kaj ĉi tie ni havas - Okay.
Do Ramya iris kun la rekursia solvo, kiu estas definitive validan solvo.
Estas du manieroj vi povas fari ĉi tiun problemon.
Vi povas aŭ fari ĝin ripete aŭ rekursie.
Plej problemojn vi renkontos kiuj povas fari rekursie povas ankaŭ fari ripete.
Do jen ni faris ĝin rekursie.
>> Ĉu iu volas difini kion signifas fari funkcio rekursia?
[Studento] Kiam vi havas funkcion nomas sin
kaj tiam nomita sin ĝis ĝi eliras kun vera kaj veraj. >> Jes.
A rekursia funkcio estas simple funkcio kiu nomas sin.
Estas tri grandaj aĵoj kiuj rekursia funkcio devas havi.
La unua estas evidente, flamo sin.
La dua estas la bazo kazo.
Do je iu punkto la funkcio bezonas halti nomas sin,
kaj tio la bazo kazo estas por.
Do jen ni scias, ke ni devus halti, ni devus rezigni de nia serĉo
kiam komenco egalas fino - kaj ni transiru kion tio signifas.
Sed fine, la lasta afero kiun gravas por rekursie funkcioj:
la funkcioj devas iel alproksimigi la bazo kazo.
Kiel se vi fakte ne ĝisdatigi nenion kiam vi faras la duan rekursia alvoko,
se vi laŭvorte ĝuste nomi la funkcion denove kun la samaj argumentoj
kaj neniu tutmonda variabloj ŝanĝis aŭ nenion,
vi neniam atingos la bazo kazo, en kiu kazo tio estas malbona.
Estos malfinia rekursio kaj pilo superflui.
Sed ĉi tie ni vidas ke la ĝisdatigo okazas ĉar ni estas ĝisdatigo komenci + fino / 2,
ni ĝisdatigi la fino argumento tie, ni ĝisdatigi la komenco argumento tie.
Do en ĉiu rekursie alvokoj ni ĝisdatigo ion. Okay.
Ĉu vi volas promeni ni per viaj solvo? >> Certe.
Mi uzas SearchHelp por ke ĉiufoje mi fari ĉi tiun funkcion alvoko
Mi havas la komenco de kie Mi serĉas en la tabelo kaj la fino
de kie Mi serĉas la tabelo.
>> Je ĉiu paŝo kie diras tion estas la mezo elemento, kiu estas komenco + fino / 2,
estas ke egala al kion ni serĉas?
Kaj se jes, tiam ni trovis ĝin, kaj mi supozas ke gets pasis laŭ la niveloj de rekursio.
Kaj se tio ne estas vera, tiam ni kontrolu ĉu tiu meza valoro de la tabelo estas tro granda,
en kies kazo ni rigardas la maldekstra duono de la tabelo irante de komenco al la mezo indekso.
Kaj se ne ni faru la fino duono.
[Bowden] Okay.
Tio sonas bona.
Okay, do kelkaj aferoj, kaj fakte, tio estas tre alta nivelo afero
ke vi neniam bezonas scii por ĉi tiu kurso, sed ĝi estas vera.
Rekursiaj funkcioj, vi ĉiam aŭdi ke ili estas malbonaj interkonsenton
ĉar se vi rekursie voki vin tro multfoje, vi ricevas pilo superflui
pro tio ke, kiel mi diris antaŭe, ĉiu funkcio atingas sian propran pilo kadro.
Do ĉiu alvoko de la rekursia funkcio atingas sian propran pilo kadro.
Do se vi faras 1.000 rekursiaj vokoj, vi ricevas 1.000 pilo kadroj,
kaj rapide vi kondukos al havi tro multajn pilo kadroj kaj aĵoj nur rompi.
Por ke tio rekursie funkcioj estas ĝenerale malbona.
Sed estas belan subaro de rekursiaj funkcioj nomas vosto-rekursie funkcioj,
kaj ĉi tio okazas al esti ekzemplo de unu kie se la tradukilo rimarkas tiun
kaj ĝi devus, mi kredas - en Clang se vi pasas ĝi la-O2 flago
tiam rimarkos ĉi estas vosto rekursie kaj fari aferojn bone.
>> Ĝi reuzi la sama pilo kadro denove kaj denove por ĉiu rekursie alvokon.
Kaj tiel ekde vi uzas la saman pilo kadro, vi ne bezonas zorgi pri
iam pilo superfluas, kaj samtempe, kiel vi diris antaŭe,
kie iam vi revenos vera, tiam ĝi devas reveni supren ĉiuj tiuj pilo kadroj
kaj la 10-a alvoko por SearchHelp devas reveni al la 9a, devas reveni al la 8a.
Por ke ne bezonas okazi kiam funkcioj estas vosto rekursie.
Kaj tiel tio faras tiun funkcion vosto rekursie estas avizo kiu por ajna donita alvokon al searchHelp
la rekursiaj alvokon ke ĝi estas fari kion ĝi estas reveni.
Do en la unua alvoko al SearchHelp, ni aŭ tuj redoni malvera,
tuj revenos vera, aŭ ni faras rekursia alvoko al SearchHelp
kie kion ni reveni estas kion tiu alvoko estas reveni.
Kaj ni ne povis fari tion, se ni faris ion kiel int x = SearchHelp, reveno x * 2,
nur iuj hazardaj ŝanĝon.
>> Do nun tiu rekursia alvoko, tiu int x = SearchHelp rekursia alvoko,
ne plu vosto rekursie ĉar fakte ne devas reveni
reen al antaŭa pilo kadro por ke tiu antaŭa alvoko al la funkcio
povas tiam ion fari kun la reveno valoro.
Do tiu estas ne vosto rekursie, sed kion ni havis antaŭe estas bele vosto rekursie. Yeah.
[Studento] Should ne la dua bazo okazo kontrolis unua
ĉar ne eblis situacio kie al vi pasi ĝin la argumento
vi komencos = fino, sed ili estas la nadlo valoro.
La demando estis ne povas ni kuras en la kazo kie fino estas la nadlo valoro
aŭ komenci = fino, taŭge, starti = fino
kaj vi ne vere kontrolis tiun apartan valoron ankoraŭ,
tiam komencos + fino / 2 estas simple tuj estos la sama valoro.
Sed ni jam revenis falsaj kaj ni neniam vere kontrolis la valoro.
Do almenaŭ, en la unua alvoko, se grandeco estas 0, tiam ni volas reveni falsaj.
Sed se grandeco estas 1, tiam komenco ne tuj egala fino,
kaj ni almenaŭ kontrolu la elemento.
Sed mi kredas ke vi pravas pri ke ni povas fini en kazo kie komenci + fino / 2,
komenco finas esti la sama kiel komenco + fino / 2,
sed ni neniam vere kontrolis tiu elemento.
>> Do, se ni unue provu estas la meza ero la valoron ni serĉas,
tiam ni povas tuj reveni vera.
Else if ili estas egalaj, tiam ne estas punkto en daŭrigi
ekde ni ĵus tuj ĝisdatigi al kazo kie ni estas en sama-era tabelo.
Se tio sola ero ne estas la ni serĉas,
tiam ĉio estas malbone. Yeah.
[Studento] La afero estas ke ekde grandeco estas efektive pli grandaj ol la nombro de eroj en la tabelo,
ekzistas jam kompensi - >> Do volo grandeco -
[Studento] Diru se la tabelo estis grandeco 0, tiam la SearchHelp efektive kontroli fojnamaso de 0
je la unua alvoko.
La tabelo havas grandecon 0, tiel la 0 estas - >> Jes.
Estas alia afero, ke - eble estus bona. Ni pensas.
Do se la tabelo havis 10 elementoj kaj la meza ni iras por kontroli estas indekso 5,
do ni kontrolanta 5, kaj diru, ke la valoro estas malpli.
Do ni ĵeti ĉio for de 5 antaŭen.
Do komencu + fino / 2 estas tuj estos nia nova fino,
do jes, ĝi estas ĉiam restos tie de la fino de la tabelo.
Se ĝi estas kazo se ĝi eĉ aŭ nepara, tiam ni devus kontroli, diru, 4,
sed ni ankoraŭ ĵetante for -
Do jes, fino estas ĉiam tuj estos preter la realaj fino de la tabelo.
Do la elementoj ni enfokusigante, fino estas ĉiam tuj estos la unu post tio.
Kaj do se komenco faras cxiam egala fino, ni estas en tabelo de amplekso 0.
>> La alia afero mi pensis estas ni ĝisdatigo komenco esti komenci + fino / 2,
do ĉi tiu estas la kazo, ke mi havas problemojn kun, kie komenci + fino / 2
estas la elemento ni checking.
Supozu ke ni havis tiun 10-era tabelo. Kion ajn.
Do komencu + fino / 2 estas tuj estos iu kiel ĉi tiu,
kaj se tio ne estas la valoro, ke ni volas ĝisdatigi.
La valoro estas pli granda, do ni volas rigardi tiun duonon de la tabelo.
Do kiel ni ĝisdatigo komenco, ni ĝisdatigo komenco nun esti ĉi elemento.
Sed ĉi tio povas ankoraŭ labori, aŭ almenaŭ, vi povas fari komenco + fino / 2 + 1.
[Studento] Vi ne bezonas esti komenci + fino [inaudible] >> Jes.
Ni jam kontrolis tiun elementon kaj scias ke estas ne unu ni serĉas.
Do ni ne bezonas ĝisdatigi komenco esti tiu ero.
Ni povas nur salti ĝin kaj ĝisdatigos komenci esti ĉi elemento.
Kaj estas tie iam kazo, ni diru, ke tio estis fino,
do tiam komencos estus tio, starti + fino / 2 estus tio,
komenci + fino - Jes, mi kredas ke povas fini en malfinia rekursio.
Diru estas nur aro de amplekso 2 aŭ tabelo de amplekso 1. Mi kredas ke tiu funkcios.
Do nune, komenco estas tiu elemento kaj fino estas 1 preter ĝi.
Do la elemento kiu ni iras por kontroli estas ĉi tiu,
kaj poste kiam ni ĝisdatigi komenco, ni ĝisdatigo komenco esti 0 + 1/2,
kiu iras al fino ni denove kun komenco esti ĉi elemento.
>> Do ni kontrolanta la sama elemento denove kaj denove.
Do ĉi tiu estas la kazo en kiu ĉiu rekursie alvoko devas vere aktualigi ion.
Do ni bezonas fari komenco + fino / 2 + 1, alie tie estas kazo
kie ni fakte ne ĝisdatigi komenco.
Ĉiuj vidas tion?
Okay.
Ĉu iu havas demandojn pri tiu solvo aŭ ajna pli da komentoj?
Okay. Ĉu iu jam ripeta solvo kiu povas ĉiuj rigardi?
Ĉu ni ĉiuj tion rekursie?
Aŭ ankaŭ mi supozas se vi malfermis lia, tiam vi havu duarangigita vian antaŭa.
Ĉu ĝi aŭtomate savi? Mi ne estas pozitiva.
Ĉu iu jam ripeta?
Ni povas marŝi tra ĝi kune se ne.
La ideo tuj estos la sama.
Ripeta solvo.
Ni tuj volas esence fari la sama ideo
kie ni volas konservi trako de la nova fino de la tabelo kaj la nova komenco de la tabelo
kaj faru tion denove kaj.
Kaj se tio, kion ni konservanta trako de la komenco kaj la fino iam sekci,
tiam ni ne trovis ĝin kaj ni povas reveni falsaj.
Do kiel mi faru tion? Ĉiu havas sugestojn aŭ kodo por mi tiri supren?
[Studento] Do momenton buklo. >> Jes.
Vi tuj volas fari banton.
>> Ĉu vi havas kodon mi povus tiri supren, aŭ kio estis vi tuj sugestas?
[Studento] Mi pensas tiel. >> Bone. Ĉi tio faras tion pli facila. Kio estis via nomo?
[Studento] Lucas.
Revizio 1. Okay.
Malalta estas kion ni nomas komenci antaŭe.
Ĝis estas ne tute kion ni nomas fino antaŭe.
Vere, fino estas nun en la tabelo. Ĝi estas ero ni devus konsideri.
Tiel malalta estas 0, supren estas la grandeco de la tabelo - 1,
kaj nun ni estas looping, kaj ni estas kontrolanta -
Mi supozas ke vi povas marŝi tra ĝi.
Kio estis via penso tra ĉi? Marŝi ni per via kodo.
[Studento] Certe. Rigardu la fojnamaso valoro en la mezo kaj kompari ĝin al nadlo.
Do, se ĝi estas pli granda ol via nadlo, tiam vi volas - ho, vere, tio devus esti malantaŭen.
Vi tuj volas forĵeti la dekstra duono, kaj tiel yeah, kiu devus esti la vojo.
[Bowden] Do tiu devus esti malpli? Estas ke kion vi diris? >> [Studento] Yeah.
[Bowden] Okay. Malpli.
Do, se tio, kion ni rigardis estas pli malgranda ol kion ni volas,
tiam jes, ni volas forĵeti la maldekstra duono,
kio signifas ni ĝisdatigo ĉio ni konsideri
movante malalta dekstre de la tabelo.
Ĉi aspektas bona.
Mi kredas ke ĝi havas la saman problemon, kiun ni diris en la antaŭa,
kie se malaltaj estas 0 kaj ĝis estas 1, tiam malalta + up / 2 estas tuj starigis al esti la sama afero denove.
>> Kaj eĉ se tio ne estas la kazo, estas ankoraŭ pli efika almenaŭ
justaj forĵeti la elemento ni nur rigardis, kiun ni konas estas erara.
Tiel malalta + up / 2 + 1 - >> [studento] Tio devus esti en la alia direkto.
[Bowden] Aŭ ĉi devus esti - 1 kaj la alia devas esti + 1.
[Studento] Kaj devus esti duobla egala signo. >> [Bowden] Yeah.
[Studento] Yeah.
Okay.
Kaj fine, nun ke ni havas ĉi + 1 - 1 aferon,
estas - ĝi povus ne esti - chu iam ebla por malalta por fini kun valoro pli granda ol ĉe?
Mi kredas ke la sola maniero kiu povas okazi - Ĉu eblas? >> [Studento] Mi ne scias.
Sed se ĝi alvenas senpintigita kaj tiam ricevas minus ke 1 kaj poste - >> Jes.
[Studento] Estus eble get paneas.
Mi kredas ke devus esti bona nur ĉar
cxar por fini suba ili devus esti egala, mi pensas.
Sed se ili estas egalaj, tiam ni ne plenumis dum buklo komenci kun
kaj ni ĵus revenis de la valoro. Do mi kredas ke ni estas bona nun.
Rimarku ke kvankam tiu problemo ne plu estas rekursie,
la sama speco de ideoj apliki kie ni povas vidi kiel ĉi tiel facile pruntas
al rekursiaj solvo de la fakto ke ni nur ĝisdatigi la indeksoj denove kaj denove,
ni faris la problemo pli kaj pli malgranda, ni enfokusigas sur subaro de la tabelo.
[Studento] Se malalta estas 0 kaj ĝis estas 1, ili ambaŭ esti 0 + 1/2, kiu irus al 0,
kaj tiam tiu estus + 1, tiu estus - 1.
[Studento] Kien ni kontrolanta egaleco?
Kiel se la mezo estas vere nadlo?
Ni ne nuntempe faras tion? Ho!
Se it's -
Jes. Ni ne povas nur fari la provon ĉi tie ĉar diru la unua duono -
[Studento] Ĝi estas fakte kiel ne forĵeti la bara.
Do se vi forĵetu la baro, vi devas kontroli ĝin unua aŭ kiom.
Ah. Yeah. >> [Studento] Yeah.
Do nun ni forĵetis la ni aktuale rigardis,
kio signifas ke ni nun bezonas havi ankaŭ
if (fojnamaso [(malalta + supren) / 2] == kudrilo), tiam ni povas reveni vera.
Kaj ĉu mi metis alian aŭ nur se, ĝi signifas laŭvorte la samon
ĉar ĉi tio estus revenis vera.
Do mi metis alian se, sed ne gravas.
>> Do alia se ĉi, alie tio kaj ĉi tiu estas komuna afero mi faras
kie eĉ se ĝi estas la kazo kie ĉio estas bona ĉi tie,
kiel malalta neniam povas esti pli granda ol supre, tio ne valoras rezonado pri tio, ĉu tio estas vera.
Do eble tiel diri dum malalta estas malpli ol aŭ egala al
aŭ dum malalta estas malpli ol
do se ili estas iam egala aŭ malalta okazas por preterlasi ĝin,
tiam ni povas rompi tiun banton.
Demandojn, maltrankviloj, komentoj?
Okay. Ĉi aspektas bona.
Nun ni volas fari varon.
Se ni iras al mia dua revizio, ni vidas ĉi tiujn samajn numerojn,
sed nun ili ne plu estas en ordo ordo.
Kaj ni volas apliki speco uzante ajnan algoritmo en O de n logo n.
Do kio algoritmo vi opinias ke ni devus apliki tie? >> [Studento] Merge varon.
[Bowden] Yeah. Kunfandi varo estas O (n log n), do tio estas kion ni faros.
Kaj la problemo tuj estos bela similaj,
kie facile pruntas al rekursiaj solvo.
Ni povas ankaŭ veni supren kun ripeta solvo se ni volas,
sed rekursio estos pli facile tie kaj ni devus fari rekursio.
Mi supozas ke ni iru laux tra merge speco unue,
kvankam estas bela video sur merge speco jam. [Ridado]
Do kunfandi speco estas - mi malŝparas tiel de ĉi papero.
Ho, tie estas nur unu maldekstre.
Do kunfandi.
Ho, 1, 3, 5.
Okay.
Merge prenas du apartaj tabeloj.
Individue tiuj du areoj estas ambaŭ ordo.
Do tiu tabelo, 1, 3, 5, ordo. Tiu tabelo, 0, 2, 4, ordo.
Nun kio merge devus fari estas kombini ilin en sola tabelo, kiu estas mem ordigita.
Do ni volas tabelo de amplekso 6 kiu tuj havos tiujn elementojn ene de ĝi
en ordo ordo.
>> Kaj tiel ni povas utiligi la fakton, ke tiuj du areoj estas ordo
fari tion en lineara tempo,
lineara tempo signifon se ĉi tabelo estas grandeco x kaj ĉi tiu estas grandeco y,
tiam la tuta algoritmo devus esti O (x + y). Okay.
Do sugestoj.
[Studento] Could ni komencu de la maldekstra?
Do vi metos la 0 malsupren unua kaj tiam la 1 kaj tiam ĉi tie vi estas en la 2.
Do ĝi estas speco de kiel vi havas langeto ke moviĝas al dekstre. >> [Bowden] Yeah.
Por ambaŭ el tiuj tabeloj se ni nur koncentriĝas pri la plej maldekstra elemento.
Ĉar ambaŭ tabeloj estas ordo, ni scias ke ĉi tiuj 2 eroj
estas la plej malgranda eroj en ĉiu tabelo.
Do tio signifas ke 1 de tiuj 2 eroj devas esti la plej malgranda ero en nia kunfandis tabelo.
Simple tiel okazas ke la plej malgranda estas la unu dekstre ĉi tiu tempo.
Do ni prenu 0, enŝovu ĝin sur la maldekstra ĉar 0 estas malpli ol 1,
do prenu 0, enŝovu ĝin en nia unua pozicio, kaj tiam ni ĝisdatigi ĉi
nun koncentriĝas pri la unua ero.
Kaj nun ni ripeti.
Do nun ni komparu 2 kaj 1. 1 estas pli malgranda, do ni devos enmeti 1.
Ni ĝisdatigos ĉi puntero atentigi al ĉi ulo.
Nun ni faru ĝin denove, tiel 2. Ĉi ĝisdatigos, kompari tiuj 2, 3.
Ĉi ĝisdatigoj, tiam 4 kaj 5.
Do tio estas merge.
>> Ĝi devus esti bela preterlasas ke ĝi estas lineara tempo post kiam ni nur iri trans ĉiu elemento unufoje.
Kaj tiu estas la plej granda paŝo al implementando merge varo fari ĉi tion.
Kaj tio ne estas tiel malfacila.
Paro aĵoj zorgi pri estas let diru ni kunfandi 1, 2, 3, 4, 5, 6.
En ĉi tiu kazo ni finas en la scenejo kie ĉi tiu tuj estos pli malgranda,
tiam ni ĝisdatigi ĉi pointer, ĉi tiu tuj estos pli malgranda, ĝisdatigi ĉi,
ĉi tiu estas pli malgranda, kaj nun vi devas rekoni
kiam vi vere kuras el elementoj kompari kun.
Kiel ni jam uzis tiun tutan tabelo,
ĉiu en ĉi tiu tabelo estas nun nur enmetita en ĉi tie.
Do, se ni iam kolizii la punkto kie unu el niaj tabeloj estas tute kunfandita jam,
tiam ni nur prenu ĉiujn elementojn de la alia tabelo kaj enmeti ilin en la fino de la tabelo.
Do ni povas simple enŝovi 4, 5, 6. Okay.
Tio estas unu afero por rigardi signifas.
Implementando kiu devus esti paŝo 1.
Kunfandi ordigi tiam bazita sur tio, ĝi estas 2 paŝoj, 2 stulta paŝoj.
Ni nur donos cxi tiun tabelo.
Do kunfandi varo, paŝo 1 estas rekursie rompas la tabelo en duonoj.
Do fendi ĉi tabelo en duonoj.
Ni nun havas 4, 15, 16, 50 kaj 8, 23, 42, 108.
Kaj nun ni faru ĝin denove kaj ni dividis tiujn en duonoj.
Mi nur faras sur tiu ĉi flanko.
Do 4, 15 kaj 16, 50.
Ni devus fari la samon pri tie.
Kaj nun ni fendi ĝin en duonoj denove.
Kaj ni havas 4, 15, 16, 50.
Por ke estas nia bazo kazo.
Iam la tabeloj estas de amplekso 1, tiam ni haltos kun la disiĝo en duonoj.
>> Nun kion ni faru pri tio?
Ni finos ĉi ankaŭ rompi en 8, 23, 42, kaj 108.
Do nun ni estas en ĉi tiu punkto, nun tretas du el merge varo nur kunfandi paroj al la listoj.
Do ni volas kunfandi tiujn. Ni nur nomas kunfandi.
Ni scias merge revenos tiuj en ordo ordo.
4, 15.
Nun ni volas kunfandi tiujn, kaj ke revenos lerta kun tiuj en ordo ordo,
16, 50.
Ni kunfandi tiujn - mi ne povas skribi - 8, 23 kaj 42, 108.
Do ni havas kunfandis paroj samtempe.
Nun ni nur kunfandi denove.
Rimarku ke ĉiu de tiuj listoj estas ordigitaj en si mem,
kaj tiam ni povas nur kunfandi tiujn listojn por akiri liston de grandeco 4 kiu estas ordo
kaj kunfandi tiujn du listojn por akiri liston de grandeco 4 kiu estas ordo.
Kaj fine, ni povas kunfandi tiujn du listojn de grandeco 4 akiri unu listo de amplekso 8 kiu ordo.
Do por vidi ke ĉi tio estas ĝenerale n logo n, ni jam vidis, ke merge estas lineara,
do kiam ni pritraktas kunfandi tiujn, do kiel la entuta kosto de merge
cxar tiuj du lertaj estas nur 2 ĉar -
Aŭ bone, ĝi estas O de n, sed n tie estas nur tiuj 2 elementoj, do ĝi estas 2.
Kaj tiuj 2 estos 2 kaj tiuj 2 estos 2 kaj tiuj 2 estos 2,
tiom trans ĉiuj kunfandas ke ni bezonas fari, ni finos faras n.
Kiel 2 + 2 + 2 + 2 estas 8, kiu estas n,
do la kosto de fandado en ĉi tiu aro estas n.
Kaj tiam la samon ĉi tie.
Ni kunfandi tiujn 2, tiam tiuj 2, kaj individue ĉi merge prenos kvar operacioj,
ĉi merge prenos kvar operacioj, sed denove, inter ĉiuj de ĉi tiuj,
ni finos kunfandante n tuta aferojn, kaj tial tiu paŝo prenas n.
Kaj tiel ĉiu nivelo prenas n eroj esti kunfandita.
>> Kaj kiom da niveloj estas tie?
Je ĉiu nivelo, nia tabelo kreskas por grandeco 2.
Jen nia arrays estas de amplekso 1, tie ili estas de amplekso 2, tie ili estas de amplekso 4,
kaj fine, ili estas de amplekso 8.
Do pro tio ke ĝi duobliĝis, ne tuj estos la tuta de log n de tiuj niveloj.
Do kun logo n niveloj, ĉiu individua nivelo prenante n tuta operacioj,
ni preni n logo n algoritmo.
Demandoj?
Ĉu homoj jam faris progreson pri kiel realigi tion?
Ĉu iu jam en stato kie mi povas simple tiri siajn kodo?
Mi povas doni minuto.
Ĉi tiu tuj estos plu.
Mi forte rekomendas ripetas -
Vi ne devas fari rekursio por merge
ĉar fari rekursio por merge, vi tuj devas pasi faskon de malsamaj grandecoj.
Vi povas, sed estas ĝena.
Sed rekursio por speco mem estas sufiĉe facila.
Vi nur laŭvorte nomas specon sur maldekstra duono, varo sur dekstra duono. Okay.
Ĉiu havas nenion mi povas tiri supren yet?
Alie mi donos unu minuto.
Okay.
Ĉiu havas ion ni povas laboro kun?
Alie ni nur funkcias kun ĉi tiu kaj tiam pligrandigi de tie.
>> Ĉiu havas pli ol tio, ke mi povas tiri supren?
[Studento] Yeah. Vi povas tiri supren mia. >> Bone.
Jes!
[Studento] Ne estis multaj kondiĉoj. >> Ho, pafi. Can you -
[Studento] mi devas savi ĝin. >> Jes.
Do ni faris fari la merge aparte.
Ho, sed ne estas tiel malbona.
Okay.
Do varo estas mem nur nomante mergeSortHelp.
Klarigi al ni kion mergeSortHelp faras.
[Studento] MergeSortHelp preskaux faras la du ĉefaj paŝoj,
kiu estas por ordigi ĉiu duono de la tabelo kaj tiam kunigi ilin ambaŭ.
[Bowden] Okay, do donu al mi la duan.
Mi kredas ke tiu - >> [studento] Mi bezonas -
Yeah. Mi mankis io.
En merge, mi rimarkas, ke mi devas krei novan tabelo
ĉar mi ne povis fari ĝin en loko. >> Jes. Vi ne povas. Korekti.
[Studento] Do mi kreu novan tabelo.
Mi forgesis fine de kunfandi al re-ŝanĝi.
Okay. Ni bezonas novan tabelo.
En merge varo, ĉi tiu estas preskaŭ ĉiam vera.
Parto de la kosto de pli bona algoritmo tempo-saĝa
estas preskaŭ ĉiam bezoni uzi iom pli memoro.
Do jen, kiel ajn vi faras kunfandi varo,
vi neeviteble bezonos uzi iun ekstra memoro.
Li aŭ ŝi kreis novan tabelo.
Kaj tiam vi diros al la fino ni nur bezonas kopii nova tabelo en la originala tabelo.
[Studento] I think so, jes.
Mi ne scias se tiu laboras en terminoj de kalkulado per referenco aux kion ajn -
Yeah, ĝi funkcios. >> [Studento] Okay.
Ĉu vi provas kuri tio? >> [Studento] Ne, ankoraŭ ne. >> Bone.
Provu kurante ĝin, kaj tiam mi parolos pri tio dum sekundo.
[Studento] mi devas ricevi la funkcio prototipoj kaj ĉiu, kvankam, ĉu ne?
La funkcio prototipoj. Ho, vi volas diri kiel - Jes.
Ordigi alvokas mergeSortHelp.
>> Do en ordo por speco nomi mergeSortHelp, mergeSortHelp devas aŭ estis difinita
antaux varo aŭ ni simple bezonas la prototipo. Simple kopiu kaj gluu tio.
Kaj simile, mergeSortHelp alvokas kunfandi,
sed merge ne estis difinita ankoraŭ, do ni povas simple lasu mergeSortHelp scias
ke tio estas kion kunfandi tuj aspekti, kaj tio estas tiel.
Do mergeSortHelp.
Ni havas problemon tie, kie ni havas neniun bazon kazo.
MergeSortHelp estas rekursie, do ajna rekursia funkcio
tuj bezonas ian bazon kazo scii kiam halti rekursie nomante sin.
Kio estas nia bazo kazo tuj estos tie? Yeah.
[Studento] Se la grandeco estas 1? >> [Bowden] Jes.
Do kiel ni vidis dekstre tie, ni haltis forkiĝanta arrays
iam ni eniris tabeloj de amplekso 1, kiu neeviteble estas ordo samaj.
Do se grandeco egalas 1, ni konas la tabelo jam ordo,
do ni povas simple reveni.
>> Rimarku ke estas malplena, do ni ne revenos ion apartan, ni ĵus revenis.
Okay. Do jen nia bazo kazo.
Mi supozas nia bazo kazo eblus ankaŭ se ni hazarde esti kunfandi tabelo de amplekso 0,
ni probable volas halti je iu punkto,
do ni povas simple diri grandeco malpli ol 2 malpli ol aŭ egala al 1
por ke ĉi funkcios por ajna tabelo nun.
Okay.
Do jen nia bazo kazo.
Nun vi volas promeni nin tra merge?
Kion ĉiuj tiuj kazoj signifas?
Ĝis ĉi tie, ni nur fari la saman ideon, la -
[Studento] Mi bezonas esti pasante grandeco kun ĉiuj mergeSortHelp alvokoj.
Mi aldonis grandecon kiel aldona primara kaj ne ekzistas, kiel grandeco / 2.
[Bowden] Ho, grandeco / 2, grandeco / 2. >> [Studento] Jes, kaj ankaŭ en la pli supre funkcio tiel.
[Bowden] Jen? >> [Studento] Just grandeco. >> [Bowden] Oh. Grandeco, grandeco? >> [Studento] Yeah.
[Bowden] Okay.
Lasu min pensi por sekundo.
Ĉu ni kolizios afero?
Ni ĉiam trakti la maldekstra kiel 0. >> [Studento] No
Tio estas erara tro. Pardonu. Ĝi devus esti komenco. Yeah.
[Bowden] Okay. Mi ŝatas ke pli bona.
Kaj fino. Okay.
Do nun vi volas promeni nin tra merge? >> [Studento] Okay.
Mi ĵus promenis tra tiu nova tabelo ke mi kreis.
Lia grandeco estas la grandeco de la porcio de la tabelo, ke ni volas esti ordo
kaj provi trovi la elemento kiu mi metis en la nova tabelo paŝo.
Do fari tion, unue mi kontrolanta se la maldekstra duono de la tabelo daŭre havas plu elementoj,
kaj se ne, tiam vi iru al tiu alia kondiĉo, kiu ĵus diras
bone, ĝi devas esti en la dekstra tabelo, kaj ni metu, ke en la nuna indekso de newArray.
>> Kaj tiam alie, mi kontrolas se la dekstra flanko de la tabelo ankaŭ finis,
en kies kazo mi simple metas en la maldekstran.
Tio eble ne vere esti necesa. Mi ne estas certa.
Sed ĉiuokaze, la aliaj du ĉeko kiu el la du estas pli malgranda en la maldekstra aŭ la dekstra.
Kaj ankaŭ en ĉiu kazo, mi pliigante ajn lokokupilo mi pliigo.
[Bowden] Okay.
Tio aspektas bona.
Ĉu iu havas komentojn aux zorgojn aŭ demandoj?
Do la kvar kazoj, ke ni devas alporti aĵojn enen nur esti - aŭ ĝi aspektas kiel kvin -
sed ni devas konsideri ĉu la maldekstra tabelo kuris el aferojn ni bezonas kunfandi,
ĉu la dekstra tabelo kuris el aferojn ni bezonas kunfandi -
Mi montras al nenio.
Do ĉu la maldekstra tabelo kuris eksteren de aĵoj aŭ la dekstra tabelo kuris eksteren de aĵoj.
Tiuj estas du kazoj.
Ni ankaŭ bezonas la banala okazo de ĉu la maldekstra afero estas malpli ol la ĝusta.
Tiam ni volas elekti la maldekstra afero.
Tiuj estas la kazoj.
Do tiu estas prava, do tio estas tiel.
Array lasis. Estas 1, 2, 3. Okay. Do jes, tiuj estas la kvar aĵoj ni volus fari.
Kaj ni ne iros tra ripeta solvo.
Mi ne rekomendas -
Kunfandi varo estas ekzemplo de funkcio kiu estas ambaŭ ne vosto rekursie,
ĝi ne estas facila por fari ĝin vosto rekursie,
sed ankaŭ ĝi ne estas tre facile fari ĝin ripeta.
Ĉi tio estas tre facila.
Tiu aplikado de merge varo,
kunfandi, negrave kion vi faros, vi tuj konstrui merge.
>> Do kunfandi speco konstruita sur supro de merge rekursie estas ĝuste tiuj tri linioj.
Ripete, estas pli ĝena kaj pli malfacile pensi.
Sed rimarki ke ĝi estas ne vosto rekursie ekde mergeSortHelp - kiam li nomas sin -
ĝi ankoraŭ bezonas fari aĵojn post ĉi rekursia alvoko revenas.
Do tiu pilo kadro devas ankoraŭ ekzistas eĉ post nomi tion ĉi.
Kaj kiam vi nomas tion, la stako kadro devas ankoraŭ ekzistas
ĉar eĉ post tiu alvoko, ni ankoraŭ bezonas kunfandi.
Kaj estas netriviala fari ĉi vosto rekursie.
Demandoj?
Bone.
Do reiri al ordigi - ho, tie estas du aferoj mi volas montri. Okay.
Reiros al varo, ni faros ĉi rapide.
Aŭ serĉo. Ordigi? Ordigi. Yeah.
Irante al la komencoj de varo.
Ni volas krei algoritmon kiu specoj la tabelo uzante ajnan algoritmo
en O de n.
Do kiel estas tio eblis? Ĉu iu havas iun specon de -
Mi sugestis antaŭe al -
Se ni estas sur plibonigi de n logo n al O de n,
ni plibonigis nian algoritmon tempo-saĝa,
kion signifas kio ni tuj bezonas fari por kompensi tion?
[Studento] Spaco. >> Jes. Ni tuj estos uzanta pli da spaco.
Kaj eĉ ne nur pli spaco, estas eksponente pli da spaco.
Do mi kredas ke tiu tipo de algoritmo estas pseŭdo ion, pseŭdo polynom -
pseŭdo - mi ne povas memori. Pseŭdo ion.
Sed estas ĉar ni bezonas uzi tiom da spaco
ke ĉi tio estas realigebla, sed ne realisma.
>> Kaj kiel ni atingi tion?
Ni povas atingi tion, se ni garantias ke iu ajn aparta ero en la tabelo
estas sub certa grandeco.
Do ni nur diros, ke grandeco estas 200,
neniu elemento en tabelo estas sube grandeco 200.
Kaj jen estas vere tre realisma.
Vi povas tre facile havi tabelo, ke vi scias ĉion en ĝi
tuj estos malpli ol iu nombro.
Kiel se vi havas iun absolute amasa vektoro aŭ io
sed vi scias ĉion tuj estos inter 0 kaj 5,
tiam tuj estos signife pli rapide fari tion.
Kaj la baro sur iu el la elementoj estas 5,
tial ĉi baro, tio estas kiom memoro vi tuj estos uzi.
Do la bara estas 200.
En teorio ĉiam estas bara ekde entjero povas esti nur ĝis 4 milionoj,
sed tio estas nerealisma tiam ni volonte uzos spaco
en la ordo de 4 miliardoj. Do jen nerealisma.
Sed ĉi tie ni diros nian bara estas 200.
La lertaĵo por fari ĝin en O de n estas ni fari alian tabelo nomis grafoj de grandeco baro.
Do fakte, ĉi tiu estas simbola ligilo por - Mi vere ne scias se Clang tion faras.
Sed en GCC almenaŭ - I'm supozante Clang faras tro -
ĉi tio nur pravalorizi la tuta tabelo esti _0s_.
Do, se mi ne volas fari tion, tiam mi povus aparte fari por (_int_ i = 0;
i <ligita; i + +) kaj grafoj [i] = 0;
Do nun ĉiu inicializado al 0.
Mi persisti super mia tabelo,
kaj kion mi faras estas mi rakonti la nombro de ĉiu - Ni iru malsupren tie.
Ni havas 4, 15, 16, 50, 8, 23, 42, 108.
Kion mi rakonti estas la nombro de okazajxoj de ĉiu el tiuj elementoj.
Ni efektive aldonu kelkajn pli en ĉi tie kun iu ripetas.
Do la valoron ni havas ĉi tie, la valoro de tiu tuj estos tabelo [i].
Do val eblis 4 aŭ 8 aŭ kion ajn.
Kaj nun mi rakonti kiel multaj el kiuj valoro mi vidis,
tiel grafoj [val] + +;
Post ĉi tiu estas farita, grafoj tuj serĉos iun kiel 0001.
Ni faru grafoj [val] - bara + 1.
>> Nun tio estas nur por klarigi la fakton ke ni ekde 0.
Do se 200 tuj estos nia plej granda nombro,
tiam 0 al 200 estas 201 aĵoj.
Do grafoj, ĝi devos aspekti 00001 ĉar ni havas unu 4.
Tiam ni devos 0001, kie ni havos 1 en la 8a indekso de grafo.
Ni havas 2 en la 23a indekso de grafo.
Ni havas 2 en la 42 indekso de grafo.
Do ni povas uzi kalkulon.
Do num_of_item = grafoj [i].
Kaj do se num_of_item estas 2, tio signifas ke ni volas enmeti 2 de la nombro mi
en niajn ordo tabelo.
Tial oni devas konservi trako de kiom for ni estas en la tabelo.
Do indekso = 0.
Array - mi nur skribas ĝin.
Grafoj -
tabelo [indekso + +] = i;
Ĉu tio estas kion mi volas? Mi kredas ke estas kion mi volas.
Jes, tiu aspektas bone. Okay.
Do ne ĉiuj komprenas kion la celo de mia grafoj tabelo estas?
Ĝi kalkulas la nombron de spritaĵoj de ĉiu el ĉi tiuj nombroj.
Tiam mi ripetanta super kiu rakontas tabelo,
kaj la th,-a pozicio en la grafoj tabelo
estas la nombro de i estas tio devus aperi en mia ordo tabelo.
Tial grafoj de 4 tuj esti 1
kaj grafoj de 8 tuj esti 1, grafoj de 23 tuj estos 2.
Do jen kiel multaj el ili mi volas enmeti en mian ordo tabelo.
Tiam mi nur faras tion.
Mi enmeto num_of_item i estas en mia ordo tabelo.
>> Demandoj?
Kaj tial denove, ĉi tiu estas lineara tempo kiam ni nur ripetanta super cxi tiun fojon,
sed estas ankaŭ lineara en kio estas tiu nombro hazarde estas,
kaj tiel ĝi peze dependas sur kion via baro estas.
Kun bara de 200, tio ne estas tiel malbona.
Se via baro tuj estos 10.000, tiam tio estas iom malbona,
sed se via baro tuj estos 4 milionoj, tio estas tute nerealisma
kaj ĉi tabelo tuj devas esti de amplekso 4 miliardoj, kiu estas nerealisma.
Do jen tiel. Demandoj?
[Inaudible studento respondon] >> Bone.
Mi rimarkis unu alia afero kiam ni iris tra.
Mi kredas ke la problemo estis en Lucas kaj probable ĉiu unuopa unu ni vidis.
Mi tute forgesis.
La sola afero, kiun mi volis komenti estas ke kiam vi traktas aferojn kiel indeksoj,
vi neniam vere vidi ĉi tion kiam vi skribas por ciklo,
sed teknike, kiam ajn vi pritraktas tiujn indeksoj,
vi devus preskaux cxiam trakti sensigna entjeroj.
La kialo estas, kiam vi pritraktas subskribis entjeroj,
do se vi havas 2 subskribis entjeroj kaj vi aldoni ilin kune
kaj ili finos tro granda, tiam vi finos kun negativa nombro.
Do jen kio entjero superflui estas.
>> Se mi aldonas 2 miliardoj kaj 1 miliardo, mi finas kun negativa 1 miliardo.
Tiel estas kiel entjeroj labori en komputiloj.
Do la problemo kun uzanta -
Tio estas bone krom se malaltaj hazarde estas 2 miliardoj kaj ĝis okazas al esti 1 miliardo,
tiam ĉi tuj estos negativa 1 miliardo kaj poste ni iras al dividi ke per 2
kaj fini kun negativa 500 milionoj.
Do ĉi tiu estas nur afero se vi hazarde estos serĉanta tra tabelo
de miliardoj da aĵoj.
Sed se malaltaj + supren okazas al superflui, tiam tio estas problemo.
Tuj kiam ni faras ilin sensigna, tiam 2 miliardoj plus 1 biliono estas 3 miliardoj.
3 miliardoj dividita per 2 estas 1,5 miliardoj.
Tuj, kiam ili estas sensigna, ĉio estas perfekta.
Kaj tiel tio estas ankaŭ temo kiam vi skribas vian por cikloj,
kaj fakte, ĝi probable faras ĝin aŭtomate.
Ĝi fakte nur krias al vi.
Do, se ĉi tiu numero estas tro granda por esti en nur entjero sed ĝi havis en sensigna entjera,
ĝi krias al Vi, por ke tio neniam vere kuras en la temo.
Vi povas vidi ke indico estas neniam tuj estos negativa,
kaj do kiam vi ripetanta super tabelo,
vi povas preskaŭ ĉiam diri sensigna _int_ i, sed vi ne devas vere.
Aĵoj iras labori preskaux same bone.
Okay. [Flustras] Kioma horo estas?
La lasta afero mi volis montri - kaj mi nur faras vere rapida.
Vi scias, kiel ni # difini por ke ni povu # difini MAX kiel 5 aŭ ion?
Ni ne faru MAX. # Difini ligita kiel 200. Tion ni faris antaŭe.
Kiu difinas konstanta, kiu estas ĝuste tuj estos kopiitaj kaj pasted
kien ajn ni hazarde skribi baro.
>> Do ni povas efektive fari pli kun # difinu.
Ni povas difini # funkcioj.
Ili estas ne vere funkcias, sed ni vokos ilin funkcioj.
Ekzemplo estus iu kiel MAX (x, y) estas difinita kiel (x <y? Y: x). Okay.
Do vi devus alkutimiĝi al triargumenta operatoro sintakso,
sed estas x malpli ol y? Reveno y, alie redoni x.
Do vi povas vidi vi povas fari ĉi apartan funkcion,
kaj la funkcio povus esti kiel bool MAX prenas 2 argumentojn, revenu ĉi.
Tiu estas unu el la plej komunaj mi vidas farita kiel ĉi tio. Ni nomas ilin makrooj.
Tio ĉi estas makro.
Tiu estas ĝuste la sintakson por ĝi.
Vi povas skribi makroo fari kion ajn vi volas.
Vi ofte vidas makrooj por elpurigi printfs kaj aĵoj.
Do tipo de printf, estas specialaj konstantaj en C kiel substreki LINIO substreki,
2 substrekoj LINIO substreki,
kaj ekzistas ankaŭ mi opinias 2 substrekoj func. Tio povus esti ĝin. Io simila.
Tiuj aĵoj estos anstataŭita per la nomo de la funkcio
aŭ la numeron de la linio kiu vi estas plu.
Ofte, vi skribas elpurigante printfs ke cxi tie mi povis tiam ĝuste skribi
Debug kaj estos presi la numero de linio kaj funkcio, kiun mi hazarde estas en
ke renkontita, ke debug komunikaĵo.
Kaj vi povas ankaŭ printi aliaj aĵoj.
Do unu afero vi devus rigardi eksteren por estas, se mi hazarde # difini DOUBLE_MAX
kiel iu kiel 2 * y kaj 2 * x.
Do ial ajn vi hazarde fari tion tre.
Do fari macro.
Ĉi tiu estas efektive rompitaj.
Mi nomos ĝin faras ion kiel DOUBLE_MAX (3, 6).
Do kion devus esti revenis?
[Studento] 12.
Jes, 12 estu revenis, kaj 12 estas redonita.
3 gets anstataŭis por x, 6 gets anstataŭis por y, kaj ni revenu 2 * 6, kiu estas 12.
Nun kio pri tio? Kio devus revenis?
[Studento] 14. >> Ideale, 14.
La temo estas tio kiom hash difinas laboron, memoru ĝi estas laŭvorta kopio kaj pasto
de preskaux cxion, do kion ĉi tuj esti interpretita kiel
estas 3 malpli ol 1 plus 6, 2 fojoj 1 plus 6, 2 fojoj 3.
>> Do tial vi preskaŭ ĉiam envolver ĉiu en krampoj.
Neniu variablo vi preskaŭ ĉiam envolver en krampoj.
Estas kazoj kie oni ne devas, kiel mi scias, ke mi ne bezonas fari tion ĉi tie
ĉar malpli ol estas preskaux cxiam nur irante labori,
kvankam tio eble ne eĉ esti vera.
Se estas iu ridinda kiel DOUBLE_MAX (1 == 2),
tiam tiu tuj get anstataŭis kun 3 malpli ol 1 egalas egalas 2,
kaj tiel tiam tuj faros 3 malpli ol 1, ĉu tio egala 2,
kio ne estas, kion ni volas.
Do, por eviti ajnan operatoro prioritaton problemoj,
ĉiam envolver en krampoj.
Okay. Kaj tio estas ĝi, 5:30.
Se vi havas demandojn pri la pset, ni sciis.
Ĝi devus esti amuza, kaj la hacker eldono ankaŭ estas multe pli realisma
ol la hacker eldono de la pasinta jaro, do ni esperas ke multaj el vi provu ĝin.
Pasinta jaro estis tre blindiga.
>> [CS50.TV]