[Powered by Google Translate] [Iedaļas 3 - ērtāk]
[Rob Bowden - Hārvarda]
>> [Tas ir CS50. - CS50.TV]
>> Tātad pirmais jautājums ir dīvaini formulēts.
Gdb ļauj "atkļūdot" programmu, bet, precīzāk, ko tas ļauj jums darīt?
Es atbildētu, ka viens, un es nezinu, kas ir tieši paredzēts,
tāpēc es esmu guessing tas ir kaut kas pa to līniju ļauj jums soli pa solim
staigāt pa programmu, mijiedarboties ar to, pārmaiņu rādītāju, darīt visas šīs lietas -
Pamatā pilnībā kontrolēt programmas izpildes
un pārbaudīt kādu konkrētu daļu no programmas izpildei.
Tāpēc šīs īpašības ļauj atkļūdot lietas.
Labi.
Kāpēc binārā meklēšana prasa, masīvs ir sakārtoti?
Kas grib, lai atbildētu, ka?
[Students] Jo tas nedarbojas, ja tas nav sakārtots. >> Jā. [Smiekli]
Ja tas nav sakārtots, tad tas ir iespējams to sadalīt uz pusēm
un zinu, ka viss pa kreisi ir mazāk un viss labi
ir lielāks par vidējo vērtību.
Tātad tas ir jābūt sakārtoti.
Labi.
Kāpēc ir burbulis šķirot O n kvadrātā?
Vai kāds vispirms vēlas dot ļoti ātri augsta līmeņa pārskatu par to, ko burbulis kārtošanas ir?
[Students] Jūs būtībā iet cauri katram elementam un jūs pārbaudīt dažus pirmos elementus.
Ja viņi no tā, kur jūs mijmaiņas tiem, tad jūs pārbaudīt tuvāko elementus un tā tālāk.
Kad jūs sasniedzat beigām, tad jūs zināt, ka lielākā daļa ir novietots beigās,
lai jūs ignorēt, ka viens, tad jūs turēt uz iet cauri,
un katru reizi, jums ir jāpārbauda vienu mazāk elementu, kamēr jūs veikt nekādas izmaiņas. >> Jā.
To sauc burbuļa kārtošanas, jo, ja jūs uzsist masīvs uz sāniem, lai tas ir uz augšu un uz leju, vertikālās,
tad lielās vērtības būs izlietne uz grunts un mazās vērtības burbulis augšu uz augšu.
Tas ir, kā tā ieguva savu nosaukumu.
Un jā, jūs vienkārši iet cauri.
Jūs turpināt iet caur masīvs, pārnešana lielāku vērtību
lai iegūtu lielāko vērtības uz leju.
>> Kāpēc tas ir O n kvadrātā?
Pirmkārt, vai kāds grib pateikt, kāpēc tas ir O n kvadrātā?
[Students] Jo katrā reizē tā iet n reizes.
Jūs varat būt pārliecināts, ka jūs esat pieņemts Lielākais elements visu ceļu uz leju,
tad jums ir atkārtot, ka tik daudzi elementi. >> Jā.
Tāpēc paturiet prātā to, ko Big O nozīmē un ko lielie Omega līdzekļiem.
Lielais O ir kā augšējā robeža, cik lēni tas var kursēt.
Tātad, sakot, ka tas ir O n brusas, tas nav O n vai arī tas varētu darboties
lineārā laika, bet tas ir O no n kubā
jo tā robežojas ar O n kubā.
Ja tas robežojas ar O no n brusas, tad tas robežojas arī ar n kubā.
Tātad tas ir n kvadrātā, un absolūtā sliktākajā gadījumā tā nevar darīt labāk nekā n brusas,
kas ir iemesls, kāpēc tas ir O no n rūtiņām.
Tātad, lai redzētu nedaudz math, kā tā nāk, lai ar n rūtiņām,
ja mums ir piecas lietas mūsu sarakstā, pirmo reizi cik mijmaiņa mēs varētu potenciāli nepieciešams veikt
Lai iegūtu šo? Pieņemsim tiešām tikai -
Cik daudz mijmaiņas darījumus mums nāksies darīt pirmajā braucienā no burbuļa kārtot caur masīvu?
[Students] n - 1. >> Jā.
>> Ja ir 5 elementi, mēs spēsim nepieciešams veikt n - 1.
Tad uz otru, cik daudz mijmaiņas darījumus mums nāksies darīt?
[Students] n - 2. >> Jā.
Un trešais būs n - 3, un tad ērtības labad es rakstīšu pēdējo divu
kā tad mēs spēsim nepieciešams veikt 2 mijmaiņas un 1 Apmainīt.
Es domāju, pēdējais var vai nevar faktiski nepieciešams notikt.
Vai tas swap? Es nezinu.
Tātad šie ir kopējie apjomi mijmaiņas vai vismaz salīdzinājumi jums ir veikt.
Pat ja jums nav swap, jums joprojām ir nepieciešams, lai salīdzinātu vērtības.
Tātad tur ir n - 1 salīdzinājumi pirmajā braucienā caur masīvs.
Ja jūs pārkārtot šīs lietas, pieņemsim faktiski padara sešas lietas tāpēc lietas kaudze pat labi,
un tad es darīšu 3, 2, 1.
Tik vienkārši pārkārtojot šīs summas, mēs gribam redzēt, cik daudz salīdzinājumus mēs
visā algoritmu.
Tātad, ja mēs panāktu šie puiši šeit lejā,
tad mēs esam vēl tikai summējot tomēr daudz salīdzinājumus tur bija.
Bet, ja mēs Rezumējot šos un mēs apkopot šos un mēs Rezumējot šos,
tas joprojām pati problēma. Mēs tikko Apkopojot šīs konkrētās grupas.
>> Tāpēc tagad mēs esam summējot 3 N s. Tas nav tikai 3 N s.
Tas vienmēr būs n / 2 n s.
Tātad šeit mēs gadās būt 6.
Ja mums bija 10 lietas, tad mēs varētu darīt šo grupējumu par 5 dažādiem pāriem lietas
un galu galā ar n + n + n + n + n.
Tātad jūs vienmēr gatavojas saņemt N / 2 n s, un tāpēc šis mēs pierakstītu to, lai n kvadrātā / 2.
Un tā pat ja tas faktors ir puse, kas notiek, lai nāk
jo fakts, ka ar katru atkārtojuma pa masīva mēs salīdzinām 1 mazāk
Tātad tas, kā mēs pa 2, bet tas joprojām ir n rūtiņām.
Mums nav rūp konstantu faktoru pusi.
Tātad lielo O sīkumi daudz, piemēram, tas balstās uz tikko veida darot šāda veida math,
darot aritmētiskās summas un ģeometriskā sīkumi,
bet lielākā daļa no tiem šajā laikā ir diezgan vienkārši.
Labi.
Kāpēc ir ievietošanas šķirot Omega n? Kāda omega nozīmē?
[Divi studenti runā uzreiz - nesaprotams] >> jā.
Omega jūs varat iedomāties, kā zemākā robeža.
>> Tātad nav svarīgi, cik efektīvs ir Jūsu ievietošana kārtošanas algoritms,
neatkarīgi no saraksta, kas ir pagājis, kas, tas vienmēr ir jāsalīdzina vismaz n lietas
vai tas ir atkārtot vairāk, n lietām.
Kāpēc tā?
[Students] Jo, ja saraksts ir jau sakārtots, tad caur pirmā atkārtojuma
Jūs varat tikai garantēt, ka pirmais elements ir mazāk,
un otrajā atkārtojuma var tikai garantēt pirmās divas
jo jūs nezināt, ka saraksta pārējais ir sakārtots. >> Jā.
Ja jūs iet pilnīgi sakārtoti sarakstā, vismaz jums ir jāiet pa visi elementi
lai redzētu, ka nekas ir jāpārceļ apkārt.
Tāpēc iet pa sarakstu un saka Ak, tas jau ir sakārtoti,
tas ir neiespējami, lai jūs zināt, tas ir sakārtoti līdz pārbaudīt katru elementu
redzēt, ka tie ir sakārtoti secībā.
Tātad zemākā ievietošanas šķirot ir Omega no n.
Kas sliktākajā gadījumā darbības laiks sapludināšanas šķirot,
sliktākajā gadījumā ir Big O atkal?
Tātad sliktākajā gadījumā, kā tas sapludināšanas kārtošanas palaist?
[Students] N log n. >> Jā.
Ātrākais vispārējie šķirošanas algoritmi ir n log n. Jūs nevarat darīt labāk.
>> Ir speciāli gadījumi, un, ja mums ir laiks šodien - bet mēs, iespējams won't -
mēs varētu redzēt vienu, kas dara labāk nekā n log n.
Bet vispārējā gadījumā, jūs nevarat darīt labāk nekā n log n.
Un apvienot kārtot notiek, ir viens no jums būtu jāzina par šo kursu, kas ir n log n.
Un tā mēs tiešām īstenos, ka šodien.
Un visbeidzot, ne vairāk kā trīs teikumus, kā tas atlases kārtošanas darbu?
Vai kāds vēlas atbildēt, un es ņemšu rēķināties jūsu teikumus
jo, ja jums iet pār 3 -
Vai kāds atceras atlases šķirot?
Izvēle kārtošanas parasti ir diezgan viegli atcerēties tikai no nosaukuma.
Jūs vienkārši atkārtot pa masīvs, atrast neatkarīgi lielākā vērtība ir vai mazākā -
kādā secībā jūs šķirošana collas
Tāpēc pieņemsim, ka mēs šķirošanas no vismazākās līdz vislielākais.
Tu atkārtot pa masīvu, meklē kādu minimālais elements ir,
izvēlieties to, un tad tikai swap to kāds ir pirmajā vietā.
Un tad uz otro pārlidojumiem pāri masīvs, meklēt minimālo elementu atkal,
izvēlieties to, un pēc tam mijmaiņas to ar to, kas uz otro pozīciju.
Tātad mēs vienkārši picking un izvēloties minimālās vērtības
un ievietojot tos priekšā masīva līdz tas ir sakārtots.
Jautājumi par šo?
>> Tie neizbēgami parādās veidlapas jums ir jāaizpilda, ja jūs iesniedzot PSET.
Tie ir būtībā atbildes uz tiem.
Labi, tāpēc tagad kodēšanas problēmas.
Es jau izsūtīti pa e-pastu - Vai kāds nevar saņemt šo e-pastu? Labi.
Es jau izsūtīti pa e-pastu telpu ka mēs ejam, lai būtu, izmantojot,
un ja jūs noklikšķiniet uz manu vārdu - tāpēc es domāju, ka es esmu būs apakšā
jo atpakaļsaderību r - bet, ja jūs noklikšķiniet uz manu vārdu jūs redzēt 2 pārskatīšanu.
Pārskatīšana 1 būs es jau kopēt un ielīmēt kodu Spaces
par meklēšanas lieta jums nāksies īstenot.
Un pārskatīšana 2 būs kārtošanas lieta, ka mēs īstenot pēc tam.
Tātad jūs varat noklikšķināt uz manu pārskatīšana 1 un darbu no turienes.
Un tagad mēs vēlamies īstenot bināro meklēšanu.
>> Vai kāds vēlas tikai dod pseudocode augsta līmeņa skaidrojums
par to, ko mēs esam nāksies darīt meklēšanai? Yeah.
[Students] Jūs vienkārši ņemt vidū masīva un redzēt, ja tas, ko jūs meklējat
ir mazāks nekā vai vairāk.
Un, ja tas ir mazāk, jums iet uz pusi, kas ir mazāk,
un, ja tas ir vairāk, jums iet uz pusi, kas ir vairāk, un jūs atkārtot, ka līdz brīdim, kad tikai iegūt viena lieta.
[Bowden] Jā.
Ievērojiet, ka mūsu numuri masīvs jau ir sakārtoti,
un tik tas nozīmē, ka mēs varam izmantot, un mēs varētu vispirms pārbaudīt,
labi, es esmu meklē numuru 50.
Lai es varētu iet uz vidu.
Vidū ir grūti definēt, kad tas ir vēl vairākas lietas,
bet pieņemsim tikai teikt, ka mēs vienmēr saīsināt uz vidu.
Tātad šeit mums ir 8 lietas, tāpēc vidējie būtu 16.
Es meklēju 50, tāpēc 50 ir lielāks par 16.
Tāpēc tagad es varētu būtībā ārstēt manu masīvs kā šiem elementiem.
Es varu mest prom visu no 16 pāri.
Tagad mans masīvs ir tikai šie 4 elementi, un es atkārtoju.
Tātad, tad es gribu, lai atrastu vidū atkal, kas būs 42.
42 ir mazāk nekā 50, lai es varētu mest prom šos divus elementus.
Šī ir mana atlikusī masīvs.
Es esmu gatavojas atrast vidū atkal.
Es domāju 50 tika slikts piemērs, jo man vienmēr bija throwing prom lietas pa kreisi,
bet gan pašu pasākumu, ja es meklēju kaut ko
un tas ir mazāk nekā elements es esmu šobrīd meklē,
tad es esmu gatavojas mest prom visu uz labo pusi.
Tāpēc tagad mums ir jāīsteno kas.
Ievērojiet, ka mums ir nepieciešams, lai iet lieluma.
Mēs varam arī nav nepieciešams grūti kodu izmēru.
Tātad, ja mēs atbrīvotos no ka # define -
Labi.
Kā es varu labi saprast, ko no numuriem masīva lielums šobrīd ir?
>> Cik elementi ir to skaits masīvā?
[Studentu] Cipari, kronšteini,. Garums?
[Bowden] Tas neeksistē C.
Vajag. Garums.
Masīvi nav īpašības, tāpēc nav garums īpašums masīvi
kas būs tikai jums tomēr ilgi tas notiek, ir.
[Students] Skat, cik daudz atmiņas tā ir, un izdalot ar to, cik daudz - >> Jā.
Tātad, kā mēs varam redzēt, cik daudz atmiņas tā ir? >> [Students] sizeof. >> Jā, sizeof.
Sizeof ir operators, kas notiek, lai atgrieztos lielumu numuriem masīva.
Un tas būs tomēr daudzi integers ir reizes izmēru veselam skaitlim
jo tas, cik daudz atmiņas tas tiešām sākšanu.
Tātad, ja es gribu vairākas lietas masīvā,
tad es esmu gatavojas vēlas dalīt ar izmēru veselam skaitlim.
Labi. Lai ļauj man iet lieluma šeit.
Kāpēc man ir nepieciešams, lai iet izmēru vispār?
Kāpēc es nevaru vienkārši darīt šeit int lielums = sizeof (Haystack) / sizeof (int)?
Kāpēc tas nedarbojas?
[Students] Tas nav globālo mainīgo.
[Bowden] Haystack pastāv, un mēs esam iet skaita kā siena kaudzē,
un tas ir sava veida foreshadowing kas ir nākt. Yeah.
[Students] Haystack ir tikai norāde uz to, lai tā būtu atgriešanās cik liels atsauce.
Yeah.
Es šaubos lekciju ka jūs esat redzējuši kaudzīti vēl īsti, vai ne?
Mēs esam tikai runājuši par to.
Tāpēc kaudze ir, ja visas jūsu mainīgo tiks uzglabāti.
>> Jebkurš atmiņu, kas ir piešķirti vietējās mainīgie notiek kaudze,
un katra funkcija izpaužas sava vieta uz skursteņa, savs kaudze rāmis ir tas, ko tā sauc.
Tātad galvenais ir tās kaudze rāmi, un iekšpusē tā gatavojas pastāvēt šo numurus masīvs,
un tas būs no izmēra sizeof (numuri).
Tas notiek, lai būtu izmēra numuru dalot pēc lieluma elementiem,
bet ka visi mājo Main žetonu rāmja.
Kad mēs saucam meklēšanu, meklēšanas izpaužas sava steka rāmi,
savu telpu, lai uzglabātu visus vietējos mainīgo.
Bet šie argumenti - tā Haystack nav kopiju šo visam blokam.
Mums nav caurlaide visam blokam, kā iekopēt meklēšanu.
Tā vienkārši iet atsauci uz šo masīvu.
Tātad meklēšana var piekļūt šiem numuriem, izmantojot šo atsauci.
Tas vēl piekļūt lietas, kas dzīvo iekšā no galvenajiem žetonu rāmi,
bet būtībā, ja mēs virzienus, kas būtu drīz,
tas ir tas, ko norādes ir.
Norādes ir tikai atsauces uz lietām, un jūs varat izmantot norādes, lai piekļūtu lietas
ka ir arī citas lietas, "skurstenī rāmjiem.
Tātad, pat ja skaitļi ir vietējā galvenais, mēs joprojām var piekļūt caur šo rādītāju.
Bet, jo tas ir tikai rādītājs, un tas ir tikai norāde,
sizeof (Haystack) atgrieztos lielumu atsauces pati.
Tas neatgriežas lielumu lieta tas norāda uz.
Tas neatgriežas faktisko lielumu numuriem.
Un tāpēc tas nav dodas uz darbu, jo mēs gribam, lai.
>> Jautājumi par šo?
Norādes tiks ieguldīts ievērojami vairāk asiņains sīkāk nedēļās.
Un tas ir iemesls, kāpēc daudzas lietas, kas jums redzēt, lielākā daļa meklēšanas lietas vai kārtot lietas,
viņi gandrīz visi dodas uz nepieciešamību veikt faktisko lielumu masīva,
jo C, mums nav ne jausmas, kāda no masīva izmērs ir.
Jums ir nepieciešams, lai manuāli nodot to collas
Un jūs nevarat manuāli caurlaide visam blokam, jo ​​jūs vienkārši iet uz atsauces
un tā nevar iegūt lielumu no atsauces.
Labi.
Tāpēc tagad mēs vēlamies īstenot to, kas bija paskaidrots iepriekš.
Jūs varat strādāt par to minūti,
un jums nav jāuztraucas par kļūst viss perfekti 100% strādā.
Vienkārši rakstīt pusi pseudocode, kā jūs domājat, ka tas ir darbs.
Labi.
Nav nepieciešams, lai būtu pilnīgi darīts ar šo ziņu.
Bet vai kāds jūtas ērti ar to, ko viņi ir tik tālu,
piemēram, kaut mēs varam strādāt kopā?
Vai kāds vēlas tajā iesaistīties? Vai es nejauši pick.
Tai nav jābūt labi ar jebkuru pasākumu, bet to mēs varam mainīt uz darba stāvoklī.
[Students] Protams. >> Labi.
Tātad jūs varat ietaupīt pārskatīšanu, noklikšķinot uz maz Save ikonu.
Tu esi Ramya, labi? >> [Students] Jā. >> [Bowden] Labi.
Tāpēc tagad es varu apskatīt savu pārskatīšanu un ikviens var uzvilkt pārskatīšanu.
Un šeit mums ir - Labi.
Tātad Ramya gāja ar rekursīvas šķīduma, kas ir noteikti derīgs risinājums.
Ir divi veidi, kā jūs varat darīt šo problēmu.
Jūs varat vai nu to iteratīvi vai rekursīvi.
Vislielākās problēmas jums rodas, ko var izdarīt rekursīvi var izdarīt iteratīvi.
Tāpēc šeit mēs esam darījuši to rekursīvi.
>> Vai kāds vēlas noteikt, ko tas nozīmē, lai padarītu funkciju rekursīvo?
[Students] Ja jums ir funkcija uzaicinājuma
un tad zvana sevi līdz tas nāk ar patiesu un patiesa. >> Jā.
Rekursīvas funkcijas ir tikai funkcija, kas sauc sevi.
Ir trīs lielās lietas rekursīvas funkcijas ir jābūt.
Pirmais ir acīmredzami, tas prasa pati.
Otrais ir bāzes scenārijs.
Tāpēc kādā brīdī funkcija ir pārtraukt zvana sevi,
un tas, ko bāzes scenārijs ir.
Tātad šeit mēs zinām, ka mums vajadzētu apstāties, mums vajadzētu atmest mūsu centienos
kad starts vienāds gala - un mēs iet pār to, ko tas nozīmē.
Bet beidzot, pēdējā lieta, ka ir svarīgi, lai rekursīvs funkcijas:
funkcijas ir kaut pieeja gadījumu.
Tāpat, ja jūs faktiski nav atjaunināšanu kaut kad jūs veicat otro rekursīvas zvanu,
ja jūs burtiski vienkārši zvanot funkcija atkal ar tiem pašiem argumentiem
un nav globālie mainīgie ir mainījušies vai jebko,
jūs nekad nesasniegs pamata situāciju, jo tādā gadījumā tas ir slikti.
Tas būs bezgalīgs rekursija un kaudze pārplūdes.
Bet šeit mēs redzam, ka atjauninājums notiek, jo mēs atjaunināt sākt + beigas / 2,
mēs atjaunināt beigu arguments šeit, mēs atjaunināt starta arguments šeit.
Tātad visās rekursīvas zvaniem mēs atjaunināt kaut. Labi.
Vai jūs vēlaties, lai staigāt mūs caur savu risinājumu? >> Protams.
Es esmu, izmantojot SearchHelp lai katru reizi, kad es darīt šo funkciju zvanu
Man ir par to, kur es esmu meklē masīvā sākumu un beigas
, kur es skatos masīvs.
>> Ik uz soļa, ja tas ir saprotams, ka tas ir vidus elements, kas ir sākums + beigas / 2,
kas ir vienāda ar to, ko mēs meklējam?
Un, ja tā ir, tad mēs atradām to, un es domāju, ka izpaužas nodots līdz līmeni recursion.
Un, ja tā nav taisnība, tad mēs pārbaudām, vai šī vidus vērtība masīva ir pārāk liels,
tādā gadījumā mēs skatāmies kreisajā pusē masīva dodoties no sākuma līdz vidējā rādītāja.
Un citādi mēs beigu pusi.
[Bowden] Labi.
Izklausās labi.
Labi, tāpēc pāris lietas, un patiesībā, tas ir ļoti augsta līmeņa lieta
ka jūs nekad jāzina par šo kursu, bet tā ir taisnība.
Rekursīvas funkcijas, jūs vienmēr dzirdēt, ka viņi slikts darījums
jo, ja tu rekursīvi saukt sevi pārāk daudz reižu, jūs saņemsiet steka pārpildes
jo, kā es teicu, katrs funkcija tiek ieviesta sava steka rāmi.
Tāpēc katra no rekursīvs izsaukums tiek ieviesta sava steka rāmi.
Tātad, ja jūs veicat 1000 rekursīvas zvanu, jūs saņemsiet 1000 kaudze rāmji,
un ātri jūs novest pie kam pārāk daudz kaudze rāmji un lietas vienkārši salauzt.
Tātad, tāpēc rekursīvas funkcijas ir tik sliktas.
Bet tur ir jauka apakškopa rekursīvs funkcijas sauc astes rekursīvs funkcijas,
un tas notiek, ir piemērs, viens, kur, ja kompilators pamana šo
un tas būtu, es domāju - jo šķindēt ja jūs nodot to-O2 karoga
tad tas būs, ka šis ir astes rekursīvs un darīt lietas labi.
>> Tas atkārtoti pats kaudze rāmi atkal un atkal par katru rekursīvas zvanu.
Un tāpēc, ka jūs, izmantojot to pašu kaudze rāmi, jums nav jāuztraucas par
kādreiz kaudze pārpildīta, un tajā pašā laikā, kā jūs teica pirms,
ja reizi atgriezties taisnība, tad tas ir jāatgriežas līdz visiem šiem kaudze rāmji
un 10 aicinājumu SearchHelp ir atgriezties uz 9, ir jāatgriežas līdz 8.
Tāpēc, ka nav nepieciešams, lai notiktu, ja funkcijas ir astes rekursīvs.
Un tā, kas padara šo funkciju astes rekursīvs ir paziņojums, ka par kādu konkrētu aicinājumu uz searchHelp
rekursīvs zvanu, ka tas ir padarot ir tas, ko tas atgriežas.
Tātad pirmā uzaicinājuma uz SearchHelp, mēs vai nu uzreiz atgriezties viltus,
nekavējoties atgriezties true, vai mēs rekursīvo zvanu uz SearchHelp
ja tas, ko mēs esam atgriešanās ir tas, ka zvans tiek atgriežas.
Un mēs nevarējām izdarīt, ja mēs kaut ko līdzīgu int x = SearchHelp, atgriešanās x * 2,
tikai daži izlases maiņa.
>> Tāpēc tagad tas rekursīvs zvanu, šis int x = SearchHelp rekursīvs zvanu,
vairs astes rekursīvs jo tie patiešām ir atgriezties
atpakaļ uz iepriekšējo kaudze rāmi tā, ka iepriekšējais aicinājums funkcijai
tad var kaut ko darīt ar atgriešanās vērtību.
Tātad tas nav astes rekursīvs, bet tas, ko mums bija pirms ir labi astes rekursīvs. Yeah.
[Students] Ja ne otro bāzes lietu jāpārbauda vispirms
jo varētu būt situācija, kad, kad jūs nodot to argumentu
Jūs sākat = beigas, bet tie ir adatu vērtību.
Jautājums tika nevar mēs uzskriet Ja gals ir adata vērtība
vai sākt = galu, pienācīgi, start = beigas
un jums nav faktiski jāpārbauda šo konkrēto vērtību vēl,
tad sākt + END / 2 ir tikai būs tāda pati vērtība.
Bet mēs jau esam atgriezušies nepatiess, un mēs nekad faktiski pārbaudīti vērtību.
Tāpēc vismaz, pēc pirmā uzaicinājuma, ja izmērs ir 0, tad mēs vēlamies atgriezties viltus.
Bet, ja lielums ir 1, tad sākums nav gatavojas vienādu beigām,
un mēs vismaz pārbaudīt vienu elementu.
Bet es domāju, ka jums ir taisnība, ka mēs varam nonākt tādā gadījumā, ja sāk + beigas / 2,
sākums beidzas ar to, tāpat kā sākumā + gala / 2,
bet mēs nekad patiesībā pārbaudīt šo elementu.
>> Tātad, ja mēs vispirms pārbaudiet ir vidējā elements vērtība, mēs meklējam,
tad mēs varam nekavējoties atgriezties taisnība.
Cits ja viņi vienādi, tad tur nav turpinot punkts
jo mēs esam tikai gatavojas atjaunināt uz gadījumu, kad mēs esam uz viena elementa masīvs.
Ja tas viens elements nav viens mēs meklējam,
tad viss ir kārtībā. Yeah.
[Students] Lieta tāda, ka kopš lielums ir faktiski lielāks nekā skaits elementu masīvs,
jau ir nobīde - >> Tā būs lielums -
[Students] Saka, ja masīvs bija 0 izmēra, tad SearchHelp būs faktiski pārbaudīt siena kaudzē ir 0
uz pirmo zvanu.
Masīvs ir lielums 0, tāpēc 0 ir - >> Jā.
Tur ir cita lieta, ka - tā varētu būt laba. Padomāsim.
Tātad, ja masīvs bija 10 elementus un no kurām vidējā mēs ejam, lai pārbaudītu, indeksa 5,
tāpēc mēs pārbaudītu 5, un pieņemsim, ka vērtība ir mazāka.
Tāpēc mēs esam throwing visu prom no 5 vēlāk.
Lai sāktu + beigas / 2 būs mūsu jaunā beigas,
Tātad yeah, tas vienmēr paliks ārpus beigām masīva.
Ja tas ir gadījumā, ja tas bija pat vai nepāra, tad mēs varētu pārbaudīt, teiksim, 4,
bet mēs joprojām throwing prom -
Tātad yeah, beigas vienmēr būs ārpus faktiskās beigām masīva.
Tātad elementiem mēs esam koncentrējoties uz, beigas vienmēr būs viens pēc tam.
Un tāpēc, ja sākums nav kādreiz vienlīdzīgu beigas, mēs esam masīvs 0 izmērs.
>> Otra lieta, ko es domāju ir mēs atjaunināt sāk tikt sākt + beigas / 2,
tāpēc tas ir gadījumā, ka es esmu, kam problēmas ar, kur sākt + beigas / 2
ir elements mēs pārbaudīt.
Teiksim, mums bija šo 10 elementu masīvu. Neatkarīgi.
Lai sāktu + beigas / 2 būs kaut kas līdzīgs šo vienu,
un ja tas nav vērtība, ka mēs gribam, lai atjauninātu.
Šis skaitlis ir lielāks, tāpēc mēs vēlamies apskatīt šo pusi no masīva.
Tātad, kā mēs atjaunināt sākums, mēs atjaunināt startu tagad šis elements.
Bet tas joprojām var strādāt, vai vismaz, jūs varat darīt starts + beigas / 2 + 1.
[Students] Jums nav nepieciešams uzsākt + galu [dzirdams] >> Jā.
Mēs jau esam pārbaudīts šo elementu, un zinu, tas nav viens, mēs meklējam.
Tāpēc mums nav nepieciešams atjaunināt sākt būt šis elements.
Mēs varam vienkārši izlaist to un atjaunināt sākt būt šo elementu.
Un ir tur kādreiz lieta, teiksim, ka šis bija beigas,
lai tad sāktu būtu tas, sāk + beigu / 2 būtu šis,
sākums + END - Jā, es domāju, ka tas varētu nonākt bezgalīgā recursion.
Teiksim tā ir tikai masīvs lielums 2 vai 1 lieluma masīvs. Es domāju, ka tas būs darbs.
Tātad šobrīd, sākums ir tas elements, un gals ir 1 ārpus tā.
Tā elements, ka mēs ejam, lai pārbaudītu, ir tas viens,
un tad, kad mēs atjaunināt sākums, mēs atjaunināt sākums ir 0 + 1/2,
kas beigsies mūs atpakaļ ar jāsāk šis elements.
>> Tāpēc mēs esam pārbaudot to pašu elementu atkal un atkal.
Tātad šis ir tas gadījums, kad katrs rekursīvas zvans ir reāli atjaunot kaut ko.
Tāpēc mums jādara starts + beigu / 2 + 1, vai arī tur ir lieta
kur mēs esam faktiski nav atjaunināšanu sākums.
Ikvienam redzēt, ka?
Labi.
Vai kāds ir jautājumi par šo risinājumu vai jebkuru komentārus?
Labi. Vai kāds ir iteratīvs risinājums, ka mēs visi varam apskatīt?
Vai mēs visi darīt to rekursīvi?
Vai arī es domāju, ja tu atver viņas, tad jūs varētu būt svarīgāka savu iepriekšējo.
Vai tas automātiski saglabāt? Es neesmu pozitīvs.
Vai kāds ir ilglaicīgs?
Mēs varam staigāt pa to kopā, ja ne.
Ideja būs tāds pats.
Iteratīvs risinājumu.
Mēs ejam, lai vēlas būtībā darīt to pašu domu
kur mēs gribam, lai saglabātu jauno beigām masīva dziesmu un jauns sākums masīva
un darīt vairāk un vairāk.
Un, ja tas, ko mēs sekotu kā sākumā un beigās kādreiz krustojas,
tad mēs neatradām, un mēs varam atgriezties viltus.
Tātad, kā es varu darīt? Kāds ir ieteikumi vai kods, lai es varētu uzvilkt?
[Students] Vai, kamēr cilpa. >> Jā.
Jūs gatavojas vēlaties darīt cilpu.
>> Vai jums ir kods, es varētu uzvilkt, vai ko tad tu gatavojas ierosināt?
[Students] es tā domāju. >> Visas tiesības. Tas padara lietas vieglāk. Kāds bija jūsu vārds?
[Students] Lucas.
Pārskatīšana 1. Labi.
Zems ir tas, ko mēs saucām sākt agrāk.
Up nav gluži tas, ko mēs saucām beidzas pirms.
Patiesībā, beigas ir tagad ir masīva. Tas elements mums būtu jāapsver.
Tik zemu ir 0, līdz ir lielums masīvs - 1,
un tagad mēs esam looping, un mēs pārbaudes -
Es domāju, jūs varat iet caur to.
Kāds bija jūsu domāšanu caur šo? Staigāt mūs caur savu kodu.
[Students] Protams. Paskaties siena kaudzē vērtību vidū un salīdzināt to ar adatu.
Tātad, ja tas ir lielāks nekā jūsu adatas, tad jūs vēlaties, lai - ak, patiesībā, kas būtu atpakaļ.
Jūs gatavojas vēlaties mest prom pareizo pusi, un tā jā, kas būtu veids.
[Bowden] Tātad tas būtu mazāk? Vai tas, ko jūs teicāt? >> [Students] Jā.
[Bowden] Labi. Mazāk.
Tātad, ja tas, ko mēs meklējam, ir, ir mazāks nekā tas, ko mēs gribam,
tad jā, mēs vēlamies, lai mest prom kreiso pusi,
kas nozīmē, ka mēs atjaunināt visu mēs apsver
pārvietojot zems, lai labi no masīva.
Tas izskatās labi.
Es domāju, ka tas ir tāds pats jautājums, kas mums teica par iepriekšējo,
ja ja zems ir 0 un uz augšu ir 1, tad zema + uz augšu / 2 gatavojas izveidota, lai būtu tas pats vēlreiz.
>> Un pat tad, ja tas nav gadījums, tas ir vēl efektīvāks vismaz
lai tikai mest prom elementu mēs vienkārši paskatījās, ko mēs zinām, ir nepareizi.
Tik zemu + uz augšu / 2 + 1 - >> [students] Tas būtu citā veidā.
[Bowden] Vai tas būtu - 1 un otrs būtu + 1.
[Students] Un tur jābūt dubultā vienlīdzības zīmi. >> [Bowden] Jā.
[Students] Jā.
Labi.
Un visbeidzot, tagad, ka mums ir šis + 1 - 1 lieta,
tas ir - tas varētu būt - tas ir kādreiz iespējams mazs, lai galu galā ar kuru vērtība ir lielāka nekā līdz?
Es domāju, ka vienīgais veids, kas var notikt - Vai ir iespējams? >> [Students] Es nezinu.
Bet, ja tā kļūst noapaļots un tad kļūst mīnus ka 1 un pēc tam - >> Jā.
[Students] Tas būtu iespējams iegūt messed up.
Es domāju, ka tas būtu labs tikai tāpēc, ka
lai tas galu galā zemākas tiem būtu jābūt vienādam, es domāju.
Bet, ja tie ir vienādi, tad mēs nebūtu darīts, kamēr cilpa sākt ar
un mēs tikai būtu atgriezušies vērtību. Tāpēc es domāju, ka mēs esam labi tagad.
Ievērojiet, ka, lai gan šī problēma vairs rekursīvs
paša veida ideju piemēro, ja mēs varam redzēt, kā tas tik viegli pakļauj sevi
līdz rekursīvo risinājumu ar to, ka mēs esam tikai atjaunošanai indeksus atkal un atkal,
mēs nesam problēma mazākas un mazākas, mēs esam koncentrējoties uz apakškopu masīva.
[Students] Ja zems ir 0 un līdz 1, viņi abi ir 0 + 1/2, kas varētu iet uz 0,
un tad viens būtu + 1, viens būtu - 1.
[Students] Ja mēs pārbaudīt līdztiesību?
Patīk, ja vidējā ir faktiski adata?
Mēs esam ne šobrīd dara, ka? Oh!
Ja it's -
Jā. Mēs nevaram vienkārši darīt testu leju šeit, jo teiksim pirmo vidū -
[Students] Tas tiešām patīk ne mest prom robežu.
Tātad, ja jūs mest prom robežu, jums ir jāpārbauda vispirms, vai neatkarīgi.
Ah. Yeah. >> [Students] Jā.
Tāpēc tagad mēs esam izmesti vienu mēs pašlaik paskatījās,
kas nozīmē, ka mums tagad ir arī
ja (Haystack [(zems + augšu) / 2] == adata), tad mēs varam atgriezties taisnība.
Un vai man cits vai vienkārši, ja tas burtiski nozīmē to pašu
jo tas ir atgriezušies taisnība.
Tāpēc es nolikšu cits ja, bet tas nav svarīgi.
>> Tātad cits ja tas, cits šo, un tas ir kopīga lieta man darīt
kur pat ja tas ir gadījums, kad viss ir labi šeit,
tāpat zema nekad nevar būt lielāks nekā uz augšu, tas nav vērts argumentācija par to, vai tā ir taisnība.
Lai jūs varētu arī teikt, bet zema ir mazāks vai vienāds ar
vai kamēr zems ir mazāks nekā
tāpēc, ja viņi ir kādreiz vienādi vai zemu notiek iet uz augšu,
tad mēs varam izkļūt no šīs cilpas.
Jautājumi, bažas, komentāri?
Labi. Tas izskatās labi.
Tagad mēs vēlamies darīt šķirot.
Ja mēs ejam uz manu otro pārskatīšanu, mēs redzam šos pašus skaitļus,
bet tagad viņi vairs nav sakārtoti secībā.
Un mēs gribam, lai īstenotu kādas izmantojot jebkuru algoritmu O n log n.
Tātad, kas algoritms jūsuprāt mums vajadzētu ieviest šeit? >> [Students] sapludināšana kārtošanas.
[Bowden] Jā. Sapludināt kārtošanas ir O (n log n), tā ka tas, ko mēs gatavojamies darīt.
Un problēma būs diezgan līdzīgi,
kur tas viegli pakļauj sevi rekursīvo risinājumu.
Mēs varam arī nākt klajā ar iteratīvs risinājums, ja mēs vēlamies,
bet rekursijas būs vieglāk šeit un mums vajadzētu darīt rekursija.
Es domāju, mēs staigāt pa sapludināšanas kārtot, pirmkārt,
lai gan ir jauki video par sapludināšanas kārtot jau. [Smiekli]
Tāpēc apvienot kādas tur ir - es esmu izšķērdēt tik daudz šajā dokumentā.
Ak, tur ir tikai viens pa kreisi.
Tik apvienot.
Ak, 1, 3, 5.
Labi.
Apvienot aizņem divas atsevišķas masīvus.
Individuāli šie divi bloki ir gan sakārtoti.
Tātad šis masīvs, 1, 3, 5, sakārtoti. Šis masīvs, 0, 2, 4, sakārtoti.
Tagad to, ko sapludināšana vajadzētu darīt, ir apvienot tos vienā masīvā, kas pati sakārtoti.
Tāpēc mēs vēlamies masīvs 6 izmēru, kas ir nāksies šos elementus iekšpusē no tā
kas sakārtoti secībā.
>> Un tā mēs varam izmantot to, ka šie divi bloki ir sakārtoti
to darīt lineārā laika,
lineārā laika nozīmē, ja tas masīvs ir izmērs x un tas ir izmērs y,
tad kopējais algoritms jābūt O (x + y). Labi.
Tātad ieteikumi.
[Students] Vai mēs sākam no kreisās?
Tātad jūs nodot 0 nosaka vispirms un tad 1 un tad šeit jūs esat pie 2.
Tāpēc tas ir veids, kā jums ir cilnes, kas ir pārvietojas pa labi. >> [Bowden] Jā.
Abiem šiem blokiem, ja mēs tikai koncentrēties uz kreisajā elementa.
Jo abi bloki ir sakārtoti, mēs zinām, ka šie 2 elementi
ir mazākais elementi nu masīvā.
Tātad tas nozīmē, ka 1 no tiem 2 elementiem jābūt mazākais elements mūsu apvienotā masīvā.
Tas tikai tā notiek, ka mazākais ir viens uz pareizā šajā laikā.
Tātad mēs 0, ievietojiet to pa kreisi, jo 0 ir mazāks par 1,
lai ņemtu 0, ievietojiet to mūsu pirmo pozīciju, un tad mēs atjaunināt šo
šim koncentrēties uz pirmā elementa.
Un tagad mēs atkārtot.
Tātad tagad mēs salīdzinātu 2 un 1. 1 ir mazāks, tāpēc mēs ievietot 1.
Mēs atjaunināt šo rādītāju, lai norādītu uz šo puisis.
Tagad mēs to darīt atkal, tāpēc 2. Tas atjauninās, salīdzināt šos 2, 3.
Šis atjauninājumus, tad 4 un 5.
Tāpēc, ka ir sapludināšana.
>> Tas būtu diezgan skaidrs, ka tas ir lineārs laiks, kopš mēs vienkārši iet pāri katram elementam vienu reizi.
Un tas ir lielākais solis, lai īstenotu Merge šķirot to dara.
Un tas nav tik grūti.
Pāris lietas jāuztraucas par ir teiksim mēs apvienojas 1, 2, 3, 4, 5, 6.
Šajā gadījumā mēs galu galā ar scenāriju, kurā šis kurš būs mazāks,
tad mēs atjaunināt šo rādītāju, tas viens būs mazāks, atjaunināt šo,
šis viens ir mazāks, un tagad jums ir jāatzīst
kad esat kursēt no elementiem, lai salīdzinātu ar.
Tā kā mums jau ir izmantojuši šo visu masīvs,
viss šajā masīvā tagad tikai ievietots šeit.
Tātad, ja mēs kādreiz satikt kur viens no mūsu masīvi ir pilnībā sajaucas jau,
tad mēs tikai veikt visus elementus no citiem masīva un ievietot tos beigām masīva.
Tātad mēs varam tikai ievietot 4, 5, 6. Labi.
Tā ir viena lieta, lai noskatītos, kas paredzēti.
Īstenotu minēto būtu solis 1.
Sapludināt kārtot tad, pamatojoties uz to, tas ir 2 soļi, 2 dumjš pakāpieni.
Pieņemsim tikai dod šo masīvu.
Tātad apvienot kārtot solis 1 ir rekursīvi lauzt masīvs uz pusēm.
Tāpēc sadalīt šo masīvu uz pusēm.
Mums tagad ir 4, 15, 16, 50 un 8, 23, 42, 108.
Un tagad mēs to darām atkal un mēs sadalīt tos uz pusēm.
Es ņemšu tikai darīt to šajā pusē.
Tātad 4, 15 un 16, 50.
Mēs varētu darīt to pašu atkal šeit.
Un tagad mēs sadalīt to uz pusēm vēlreiz.
Un mums ir 4, 15, 16, 50.
Tāpēc, ka ir mūsu bāzes scenārijs.
Kad masīvi ir no 1 izmēra, tad mēs apstāties ar sadalīšanas uz pusēm.
>> Tagad to, ko mēs darām ar šo?
Mēs galu galā tas arī iedala 8, 23, 42, 108 un.
Tāpēc tagad, ka mēs esam šajā brīdī, tagad soli divas sapludināšanas veida ir tikai apvienojot pārus ar sarakstiem.
Tāpēc mēs vēlamies apvienot šos. Mēs vienkārši zvanu apvienoties.
Mēs zinām sapludināšanas atgriezīsies šos sakārtoti secībā.
4, 15.
Tagad mēs vēlamies apvienot šos, un kas būs atgriešanās sarakstu ar tiem, kas sakārtoti secībā,
16, 50.
Mēs apvienot tos - es nevaru rakstīt - 8, 23 un 42, 108.
Tāpēc mums ir sapludināto pāriem reizi.
Tagad mēs vienkārši apvienot vēlreiz.
Ievērojiet, ka katrs no šiem sarakstiem ir sakārtots pats par sevi,
un tad mēs varam vienkārši apvienot šos sarakstus, lai iegūtu sarakstu ar 4 izmēra, kas ir sakārtoti
un apvienot šīs divas sarakstus, lai iegūtu sarakstu ar 4 izmēru, kas ir sakārtots.
Un visbeidzot, mēs varam apvienot šos divus sarakstus ar 4 izmēra, lai iegūtu vienu sarakstu 8 izmērs, kas ir sakārtots.
Tātad, lai redzētu, ka tas kopumā ir n log n, mēs jau redzējām, ka Merge ir lineāra,
tad, kad mums ir darīšana ar apvienošanu šiem, lai, piemēram, kopējās izmaksas sapludināšanu
šīm divām sarakstiem ir tikai 2, jo -
Vai labi, tas ir O n, bet n šeit ir tikai šie 2 elementi, tāpēc tas ir 2.
Un tie 2 būs 2 un tie 2 būs 2 un tie 2 būs 2,
tāpēc pāri visiem sapludināšanai, kas mums jādara, mēs galu galā dara n.
Tāpat kā 2 + 2 + 2 + 2 ir 8, kas ir n,
tāpēc apvienošanu šo komplektu izmaksas ir n.
Un tad pats šeit.
Mēs apvienot šos 2, tad šie 2, un atsevišķi šī sapludināšana būs četras operācijas,
Šī apvienot būs četras operācijas, bet atkal, starp visiem šiem,
mēs galu galā apvienojot n kopējais lietas, un tāpēc šis solis tiek n.
Un tā katru līmeni ņem n elementiem tiek apvienotas.
>> Un cik daudz piesārņojuma līmenis ir tur?
Katrā līmenī, mūsu masīvs aug par 2 izmēru.
Te mūsu bloki ir no 1 izmēra, šeit viņi ir 2 izmēru, šeit viņi 4 izmēra,
un visbeidzot, viņi 8 lieluma.
Tāpēc, ka tas ir divkāršojies, tur ir būs pavisam log n no šiem līmeņiem.
Tātad ar log n līmenis, katra atsevišķā līmenis ņemot N Kopējais operācijas,
mēs iegūstam n log n algoritms.
Jautājumi?
Ir cilvēki jau guvusi panākumus, kā īstenot šo?
Vai kāds jau ir valsts, kur es varu tikai uzvilkt savu kodu?
Es varu dot minūti.
Tas viens būs ilgāks.
Es ļoti ieteiktu atkārtojas -
Jums nav jādara rekursija par sapludināšanu
jo to darīt rekursija par sapludināšanu, jūs nāksies iziet ķekars dažādu izmēru.
Jūs varat, bet tas ir kaitinošas.
Bet rekursijas par kārtot pati ir diezgan viegli.
Jūs vienkārši burtiski zvanīt šķirot kreisajā pusē, kārtot labajā pusē. Labi.
Kāds ir kaut kas es varētu uzvilkt vēl?
Vai arī es došu minūti.
Labi.
Kāds ir kaut kas, mēs varam strādāt ar?
Vai arī mēs tikai strādāt ar šo un pēc tam paplašināt no turienes.
>> Ikviens ir vairāk nekā tas, ka es varētu uzvilkt?
[Students] Jā. Jūs varat uzvilkt raktuvē. >> Visas tiesības.
Jā!
[Students] Tur bija nosacījumu daudz. >> Ak, šaut. Jūs varat -
[Students] Man ir to saglabāt. >> Jā.
Tāpēc mēs to sapludināšanu atsevišķi.
Ak, bet tas nav tik slikti.
Labi.
Tāpēc kārtošanas ir pats tikai zvana mergeSortHelp.
Paskaidro mums, ko mergeSortHelp dara.
[Students] MergeSortHelp diezgan daudz dara divus galvenos soļus,
kas ir, lai sakārtotu katru pusi no masīva un tad apvienot abus.
[Bowden] Labi, tāpēc man sekundē.
Es domāju, ka šis - >> [students] Man vajag -
Yeah. Es esmu trūkst kaut kas.
Jo sapludināšanu, es saprotu, ka man ir nepieciešams, lai izveidotu jaunu bloku
jo es nevarēju darīt to vietā. >> Jā. Jūs nevarat. Labot.
[Students] Tāpēc es izveidotu jaunu bloku.
Es aizmirsu beigās apvienot ar atkārtotu mainīties.
Labi. Mums vajag jaunu masīvu.
Jo sapludināšanas šķirot, tas gandrīz vienmēr ir taisnība.
Daļu no izmaksām par labāku algoritmu laika gudrs
gandrīz vienmēr nepieciešams izmantot mazliet vairāk atmiņas.
Tātad šeit nav svarīgi, cik jūs apvienot šķirot,
jums būtu neizbēgami nepieciešams izmantot dažas papildu atmiņu.
Viņš vai viņa izveidoja jaunu masīvu.
Un tad jūs sakāt beigās mēs vienkārši nepieciešams, lai kopētu jaunu bloku uz sākotnējo masīvs.
[Students] es tā domāju, jā.
Es nezinu, vai tas darbojas ziņā skaitīšanas atsaucoties vai kāds -
Jā, tas būs darbs. >> [Students] Labi.
Vai jūs mēģināt darboties šo? >> [Students] Nē, vēl ne. >> Labi.
Sāciet to, un tad es ņemšu runāt par to otru.
[Students] Man vajag, lai ir visas funkcijas prototipus un viss, lai gan, ne?
Funkciju prototipus. Ak, tu domā tāpat - Jā.
Šķirot zvana mergeSortHelp.
>> Tātad, lai šķirot zvanīt mergeSortHelp, mergeSortHelp vai nu ir definētas
Pirms šķirot vai mums vienkārši vajag prototipu. Vienkārši kopēt un ielīmēt to.
Un līdzīgi, mergeSortHelp zvana apvienot,
bet Apvienošana nav definēts vēl, tāpēc mēs varam tikai let mergeSortHelp zināt
ka tas, ko apvienot gatavojas izskatās, un tas, ka.
Tā mergeSortHelp.
Mums ir problēmas šeit, kur mums nav pamata lietu.
MergeSortHelp ir rekursīvs, tādējādi jebkurš rekursīvas funkcijas
būs nepieciešama sava veida bāzes lietas zināt, kad apstāties rekursīvi zvana pati.
Kas ir mūsu bāzes scenārijs būs šeit? Yeah.
[Students] Ja lielums ir 1? >> [Bowden] Jā.
Tātad, piemēram, mēs redzējām labi tur, mēs apstājāmies sadalīšanas bloki
kad mēs saņēmām uz blokiem lieluma 1, kas neizbēgami ir sakārtoti sevi.
Tātad, ja izmērs ir vienāds ar 1, mēs zinām masīvs jau ir sakārtoti,
lai mēs varētu vienkārši atgriezties.
>> Ievērojiet, ka ir anulēts, tāpēc mums nav atgriešanās neko īpašu, mēs vienkārši atgriezties.
Labi. Tātad tas ir mūsu bāzes scenārijs.
Es domāju mūsu bāzes scenārijs varētu būt arī tad, ja mēs notikt, apvienojas masīvs 0 izmērs,
Mēs, iespējams, vēlas, lai apturētu kādā brīdī,
tāpēc mēs varam tikai teikt izmērs ir mazāks nekā 2 vai mazāks vai vienāds ar 1
tāpēc, ka tas darbosies jebkurā masīva tagad.
Labi.
Tātad tas ir mūsu bāzes scenārijs.
Tagad jūs vēlaties staigāt mūs cauri apvienoties?
Ko visi šie gadījumi nozīmē?
Šeit, mēs esam tikai darām to pašu ideju, -
[Students] man vajag iet garām izmēru ar visiem mergeSortHelp zvaniem.
I pievienotās izmērs kā papildu primārais un tas nav tur, tāpat izmēra / 2.
[Bowden] Ak, izmērs / 2, izmērs / 2. >> [Students] Jā, un arī iepriekš funkcija, kā arī.
[Bowden] Šeit? >> [Students] Tikai izmēru. >> [Bowden] Ak. Izmērs, lielums? >> [Students] Jā.
[Bowden] Labi.
Ļaujiet man domāt par sekundi.
Vai mēs uzskriet jautājumu?
Mēs vienmēr apstrādājot kreisi kā 0. >> [Students] Nē
Tas ir nepareizi pārāk. Žēl. Tas būtu sākums. Yeah.
[Bowden] Labi. Man patīk, ka labāk.
Un beigu. Labi.
Tātad tagad jūs vēlaties staigāt mūs cauri apvienoties? >> [Students] Labi.
Es esmu tikai ejot caur šo jauno bloku, ka es esmu izveidojis.
Tās izmērs ir lielums daļu masīva ka mēs gribam būt sakārtoti
un mēģina atrast elementu, kas man būtu jāliek jaunā masīva soli.
Tātad, lai to izdarītu, vispirms es esmu pārbaude, ja kreiso pusi no masīva joprojām ir kādi elementi,
un ja tā nav, tad jums iet uz leju, lai šo citam nosacījumam, kas tikko saka
labi, tai jābūt pareizā masīvā, un mēs nodot, ka pašreizējā indeksa newArray.
>> Un tad citādi, es esmu pārbaudot, ja labajā pusē masīva ir arī pabeigta,
tādā gadījumā es vienkārši ielieciet kreisi.
Tas varētu faktiski nav nepieciešams. Es neesmu pārliecināts.
Bet anyway, pārējie divi pārbaude, kura no divām ir mazāka kreisi vai pa labi.
Un arī katrā gadījumā, es esmu palielināšanai atkarībā vietturis es pieauguma.
[Bowden] Labi.
Tas izskatās labi.
Vai kāds ir komentāri vai bažas vai jautājumi?
Tātad četriem gadījumiem, kas mums ir, lai lietas vērā tikai to - vai tas izskatās pieci -
bet mums ir jāapsver, vai kreisi masīvs ir beigušies lietas, kas mums ir nepieciešams apvienot,
vai tiesības masīvs ir beigušies lietas, kas mums ir nepieciešams apvienot -
Es esmu norādot uz neko.
Tātad, vai kreisi masīvs ir beigušies lietām vai tiesībām masīvs ir beigušies lietām.
Tie ir divi gadījumi.
Mums ir vajadzīgs arī triviāls gadījumu vai kreisā lieta ir mazāks nekā pareizo lietu.
Tad mēs vēlamies, lai izvēlētos kreiso lieta.
Tie ir gadījumi.
Tātad tas bija labi, tāpēc tas, ka.
Array kreisi. Tas ir 1, 2, 3. Labi. Tātad yeah, tie ir četras lietas, mēs varētu vēlēties darīt.
Un mēs ne iet pār iteratīvu risinājumu.
Es nevarētu ieteikt -
Sapludināt kārtošanas ir piemērs funkciju, kas ir gan nav astes rekursīvs
tas nav viegli, lai padarītu to astes rekursīvs
bet arī tas nav ļoti viegli veikt to iteratīvs.
Tas ir ļoti viegli.
Šis īstenošanu sapludināšanas šķirot,
apvienot, nav svarīgi, ko jūs darāt, jūs gatavojas būvēt sapludināšanu.
>> Tāpēc apvienot kārtot celta uz augšu sapludināšanu rekursīvi ir tikai šīs trīs līnijas.
Iteratīvi, tas ir vairāk kaitinošas un grūtāk domāt par.
Bet paziņo, ka tas nav astes rekursīvs jo mergeSortHelp - ja tā sevi dēvē -
tas vēl ir jādara lietas pēc šī rekursīvas zvanu atdevi.
Tātad šī kaudze rāmi jāturpina pastāvēt pat pēc zvana to.
Un tad, kad tu to sauc, kaudze rāmi jāturpina pastāvēt
jo pat pēc šī zvana, mums joprojām ir nepieciešams apvienot.
Un tas ir netriviāls, lai padarītu šo asti rekursīvas.
Jautājumi?
Labi.
Tā iet atpakaļ uz sakārtotu - ak, tur ir divas lietas, es vēlos parādīt. Labi.
Dodas atpakaļ uz kārtot, mēs izdarīt ātri.
Vai meklēšanu. Šķirot? Kārtošanas. Yeah.
Dodas atpakaļ uz kārtot pirmsākumiem.
Mēs vēlamies izveidot algoritmu, kas sakārto masīvu, izmantojot jebkuru algoritmu
kas O n.
Tātad, kā tas ir iespējams? Vai kāds ir jebkāda veida -
Es mājienu pirms pie -
Ja mēs esam par to uzlabot no n log n līdz O n,
Mēs esam uzlabojuši mūsu algoritms laika gudrs,
kas nozīmē to, ko mēs gatavojamies jādara, lai atgūtu to?
[Students] Space. >> Jā. Mēs ejam, lai, izmantojot vairāk vietas.
Un nav pat tikai vairāk vietas, tas ir eksponenciāli vairāk vietas.
Tāpēc es domāju, ka šis algoritms veids ir pseido kaut, pseido polynom -
pseido - es nevaru atcerēties. Pseido kaut.
Bet tas ir tāpēc, ka mums ir nepieciešams, lai izmantotu tik daudz vietas
ka tas sasniedzams, bet ne reāli.
>> Un kā mēs to sasniegtu?
Mēs varam panākt, ja mēs garantējam, ka kāds konkrēts elements masīva
ir zem noteikta lieluma.
Tāpēc pieņemsim tikai teikt, ka izmērs ir 200,
jebkurš masīvā elements ir mazāks izmērs 200.
Un tas tiešām ir ļoti reāls.
Jūs varat ļoti viegli ir masīvs, ka jūs zināt visu, kas tajā
būs mazāks nekā daži numuru.
Tāpat, ja Jums ir dažas absolūti masveida vektoru vai kaut
bet jūs zināt viss būs no 0 līdz 5,
tad tas būs daudz ātrāk to darīt.
Un uz kāda no elementiem saistoši ir 5,
tāpēc tas saistās, ka ir, cik daudz atmiņas jūs būs izmantojot.
Tāpēc saistītā ir 200.
Teorētiski pastāv vienmēr saistās jo skaitlis var būt tikai līdz miljardiem 4,
bet tas ir nereāli, jo tad mēs gribētu būt, izmantojot telpu
par kārtību miljardiem 4. Tātad tas ir nereāli.
Bet šeit mēs teikt mūsu saistoši ir 200.
Triks, lai dara to O n ir mums veikt citu masīvu sauc skaits no lieluma saistoši.
Tātad faktiski, tas ir īsceļu - es tiešām nezinu, ja šķindēt dara.
Bet GCC vismaz - I'm pieņemot šķindēt dara to pārāk -
tas būs vienkārši sāktu visu masīvs būt 0s.
Tātad, ja es nevēlos to darīt, tad es varētu atsevišķi darīt (int i = 0;
i <Bound, i + +) un skaitās [i] = 0;
Tāpēc tagad viss ir inicializēts līdz 0.
Es atkārtot pār manu masīvs,
un ko es daru, ir es esmu saskaitot katras - iesim uz leju šeit.
Mums ir 4, 15, 16, 50, 8, 23, 42, 108.
Ko es esmu skaitīšanas ir atkārtojumu skaitu katram no šiem elementiem.
Pieņemsim faktiski pievienot pāris vairāk šeit ar dažiem atkārtojas.
Tātad vērtība, mēs esam šeit, uz šī vērtība būs masīvs [i].
Tāpēc val varētu būt 4 vai 8 vai neatkarīgi.
Un tagad es esmu skaitīšanas cik daudzi no šīs vērtības es esmu redzējis,
tāpēc epizodēs [val] + +;
Pēc tam tiek darīts, skaits ir gatavojas izskatās kaut kā 0001.
Darīsim skaitu [Val] - BOUND + 1.
>> Tagad tas ir tikai, lai ņemtu vērā faktu, ka mēs sākot no 0.
Tātad, ja 200 būs mūsu lielākais skaits,
tad 0-200 ir 201 lietas.
Tātad skaitu, tas būs izskatās 00.001 jo mums ir viena 4.
Tad mums būs 0001 ja mums būs 1 no 8 indeksu skaits.
Mums būs 2 Padomes 23 indeksa skaits.
Mums būs 2 uz 42 indeksa skaits.
Tātad, mēs varam izmantot skaitu.
Tātad num_of_item = skaits [i].
Un tāpēc, ja num_of_item ir 2, tas nozīmē, ka mēs vēlamies, lai ievietotu 2 skaitu i
mūsu šķiroto masīvs.
Tāpēc mums ir nepieciešams, lai sekotu tam, cik tālu mēs esam uz masīvu.
Tātad indekss = 0.
Array - Es ņemšu tikai rakstīt to.
Grāfu -
masīvs [indekss + +] = i;
Vai tas, ko es gribu? Es domāju, ka tas, ko es gribu.
Jā, tas izskatās labi. Labi.
Lai vai visi saprastu, ko mana grāfu masīva mērķis ir?
Tas ir skaitot atkārtojumu skaitu katrā no šiem skaitļiem.
Tad es esmu atkārtojot pār ka skaita masīvs,
un kārtējā pozīcija grāfu masīvā
ir vairāki man ir, ka vajadzētu parādīties manā šķiroto masīvā.
Tieši tāpēc skaits gada 4 būs 1
un skaits gada 8 būs 1, skaits no 23 ir būs 2.
Tātad tas, kā daudzi no viņiem es gribu ievietot manā šķiroto masīvs.
Tad es vienkārši darīt.
Es esmu ievietojot num_of_item man ir manā šķiroto masīvs.
>> Jautājumi?
Un tā atkal, tas ir lineārs laiks, kopš mēs esam tikai atkārtojot pār šo vienu reizi,
bet tas ir arī lineārs, ko šis skaitlis notiek, ir,
un tā tas lielā mērā ir atkarīgs no tā, ko jūsu pienākums ir.
Ar robežu 200, tas nav tik slikti.
Ja jūsu pienākums būs 10,000, tad tas ir mazliet sliktāk,
bet, ja jūsu pienākums būs 4 miljardus, kas ir pilnīgi nereāli
un šis masīvs būs jābūt ar izmēru 4 miljardus, kas ir nereāli.
Tātad tas ir kas. Jautājumi?
[Dzirdams studentu reaģēšanas] >> Labi.
Es sapratu viena cita lieta, kad mēs iet cauri.
Es domāju, ka problēma bija Lucas s un, iespējams, katrs no mums esam redzējuši.
Es pilnīgi aizmirsu.
Vienīgais es gribēju komentēt, ka, ja jūs nodarbojas ar lietām, piemēram, indeksiem,
tu nekad īsti redzēt šo, kad jūs esat rakstiski par cilpu,
bet tehniski, kad jūs nodarbojas ar šiem rādītājiem,
Jums vajadzētu diezgan daudz vienmēr nodarbojas ar neparakstītu integers.
Iemesls tam ir, kad jūs nodarbojas ar parakstīto veseliem skaitļiem,
tāpēc, ja jums ir 2 parakstīti integers un jūs pievienojat tos kopā
un tie galu galā ir pārāk liels, tad jūs galu galā ar negatīvu skaitli.
Tātad, tas ko skaitlim pārpildes ir.
>> Ja es pievienot 2 miljardiem un 1 miljards es galu galā ar negatīvs 1 miljardus.
Tas ir kā veseli strādā pie datoriem.
Tātad ar izmantojot problēma -
Tas ir labi, izņemot, ja zemu notiek, ir 2 miljardiem un līdz notiek, ir 1 miljards
tad tas būs negatīvs 1 miljardu un tad mēs spēsim dalīt to ar 2
un galu galā ar negatīvu 500 miljoni.
Tātad tas ir tikai jautājums, ja jums gadās būt meklējot caur masīvu
miljardiem lietām.
Bet, ja zemu + līdz notiek ar pārplūdes, tad tas ir problēma.
Tiklīdz mēs padarītu tos neparakstītu, tad 2 miljardu euro apmērā 1000000000 ir 3 miljardi.
3000000000 dalīts ar 2 ir 1,5 miljardi euro.
Tā tiklīdz viņi neparakstītu, viss ir ideāli.
Un tā tas ir arī jautājums, kad jūs rakstot savu uz cilpas,
un faktiski, tas, iespējams, tas automātiski.
Tas būs tiešām tikai kliegt pie jums.
Tātad, ja šis skaitlis ir pārāk liels, lai būtu tikai veselam skaitlim, bet tas varētu iederēties neparakstītu skaitlim,
tas būs kliegt pie jums, tā, ka tāpēc tu nekad īsti uzskriet jautājumu.
Jūs varat redzēt, ka indekss ir nekad būs negatīvs,
un tāpēc, ja jūs atkārtojot pa masīva,
Jūs varat gandrīz vienmēr teikt neparakstīts int i, bet jums nav īsti ir.
Lietas notiek uz darbu diezgan daudz tikpat labi.
Labi. [Čukst] Kas ir pulkstenis?
Pēdējā lieta, ko es gribēju parādīt - un es ņemšu tikai darīt to patiešām ātri.
Jūs zināt, kā mēs esam # define lai mēs varam # definēt MAX kā 5 vai kaut ko?
Pieņemsim nav do MAKS. # Define saistības kā 200. Tas, ko mēs darījām agrāk.
Kas definē konstante, kas ir tikai gatavojas kopēt un ielīmēt
kur mēs notikt rakstīt saistoši.
>> Tātad, mēs varam reāli darīt vairāk ar # definē.
Mēs varam # definēt funkcijas.
Viņi nav īsti funkcijas, bet mēs tos saucam funkcijas.
Piemērs varētu būt kaut kas līdzīgs MAX (x, y) ir definēta kā (x <y y: x). Labi.
Tātad jums vajadzētu pierast trīskāršo operators sintaksi,
bet ir x mazāks nekā y? Atgriezties y, cits X apmaiņā.
Tātad jūs varat redzēt, jūs varat veikt šo atsevišķu funkciju,
un funkcijas varētu būt, piemēram, bool MAX aizņem 2 argumentus, atgriezties to.
Šis ir viens no visbiežāk tie, es redzu darīts, piemēram, šis. Mēs tos saucam makro.
Tas ir makro.
Tas ir tikai sintakse par to.
Jūs varat rakstīt makro darīt, ko vien vēlaties.
Jūs bieži redzēt makro debugging printfs un stuff.
Tātad tipam printf, pastāv īpašas konstantes K piemēram pasvītrojumu LINE pasvītrojumu,
2 uzsver LINE pasvītrojumu,
un tur ir arī es domāju 2 uzsver FUNC. Tas varētu būt tas. Kaut kā tā.
Šīs lietas tiks aizstāts ar nosaukumu funkcijas
vai numuru no līnijas, ka jūs par.
Bieži, jūs rakstīt atkļūdošanas printfs ka noteikti šeit es varētu vienkārši uzrakstīt
DEBUG un tas būs drukāt rindas numuru un funkciju, kas man gadās būt
ka tā saskārās šīs DEBUG paziņojumu.
Un jūs varat arī izdrukāt citas lietas.
Tātad viena lieta, jums vajadzētu skatīties, kas ir, ja es notikt # define DOUBLE_MAX
kā kaut ko līdzīgu 2 * y un 2 * x.
Tātad kāda iemesla dēļ, jūs notikt darīt daudz.
Lai padarītu to makro.
Šis ir faktiski sadalīts.
Es to sauktu par darot kaut ko līdzīgu DOUBLE_MAX (3, 6).
Tātad, ko jāatdod?
[Students] 12.
Jā, 12 jāatdod, un 12 tiek atgriezta.
3 izpaužas aizstāt x, 6 izpaužas aizstāt y, un mēs atgriežamies 2 * 6, kas ir 12.
Tagad to, ko par šo? Kas būtu atpakaļ?
[Students] 14. >> Ideālā, 14.
Jautājums ir, ka, kā hash definē darbu, atcerieties, tas ir burtiski kopēt un ielīmēt
gada diezgan daudz viss, lai ko tas gatavojas jāinterpretē
ir 3 mazāk nekā 1 plus 6, 2 reizes 1 plus 6, 2 reizes 3.
>> Tātad šī iemesla dēļ jūs gandrīz vienmēr wrap viss iekavās.
Jebkurš mainīgais jūs gandrīz vienmēr wrap iekavās.
Ir gadījumi, kad jums nav, lai, piemēram, es zinu, ka man nav nepieciešams to darīt šeit
jo mazāk nekā ir diezgan daudz vienmēr vienkārši iet uz darbu,
kaut kas varētu pat nebūt taisnība.
Ja ir kaut kas smieklīgs, piemēram DOUBLE_MAX (1 == 2),
tad kas notiek, lai saņemtu aizstāts ar 1 3 mazāk nekā vienāds vienāds ar 2,
un tā tad tas būs jādara 3 mazāk nekā 1, tas, ka vienāda 2,
kas nav tas, ko mēs vēlamies.
Tātad, lai novērstu operatora Prioritātes problēmas,
vienmēr wrap iekavās.
Labi. Un tas ir tas, 5:30.
Ja Jums ir kādi jautājumi par PSET, dodiet mums zināt.
Tas būtu jautri, un hakeru valodā arī ir daudz reālāks
nekā hakeru izdevumā pagājušo gadu, tāpēc mēs ceram, ka daudzi no jums izmēģināt to.
Pagājušajā gadā bija ļoti pārliecinošs.
>> [CS50.TV]