>> [Prehrávanie hudby]
>> ANDI PENG: Vitajte na týždeň 3 oddielu.
Vďaka, chlapci, pre všetky prichádzajúce do tohto skoršieho štartu čas dnes.
Máme pekný, malý intímne skupina dnes.
Takže dúfajme, že sa dostaneme povrch, možno skoro,
trochu brzo dnes.
Tak rýchlo, len niektoré Oznámenia pre relácie dnešného dňa.
Než začneme, my sme bude jednoducho ísť cez
niekoľko krátkych logistické problémy, pset Otázky, Rozprava, také veci.
A potom budeme ponor priamo.
Budeme používať debugger s názvom GDB na začať odhaľovať náš kód, ktorý David
vysvetlené v prednáške na druhý deň.
Pôjdeme cez štyri typy druhov.
Pôjdeme cez ne celkom rýchlo pretože sú to celkom náročné.
Ale viem, že všetky snímky a Zdrojový kód je vždy on-line.
Tak neváhajte, vo Vašom prečítaniu, aby vrátiť a pozrieť sa na to.
>> Prejdeme asymptotickej notácie, ktorý
je len ozdobný spôsob, ako hovoriť "runtime"
kde máme veľký O, ktorý David je vysvetlené v prednáške.
A máme aj Omega, ktorý je dolná hranica runtime.
A budeme hovoriť trochu viac do hĺbky o tom, ako tieto práce.
A konečne, pôjdeme cez binárne vyhľadávanie, pretože mnoho z vás, ktorí už
Pozrel sa na svoje psets pravdepodobne viete, že to je otázka, ktorá je vo vašej pset.
Takže budete všetci radi že budeme rozprávať to dnes.
>> A konečne, podľa vašich oddiel spätná väzba, som vlastne
odišiel asi 15 minút pri koniec jednoducho ísť cez
logistika pset3, nejaké otázky, možno trochu poradenstvo, ak chcete,
Než začneme programovanie.
Takže poďme sa pokúsiť sa dostať cez materiál celkom rýchlo.
A potom môžeme stráviť nejaký čas pričom ďalšie otázky pre pset.
OK.
>> Rýchlo, takže len pár oznámenia Než začneme dnes.
Po prvé, vitajte na to, to prostredníctvom dvoch svojich psets.
Som sa pozrieť na your-- jo, poďme získať potlesk pre tento jeden.
Vlastne, bol som naozaj, naozaj ohromený.
Triedené som prvý pset pre vás Minulý týždeň a vy ste urobili neuveriteľný.
>> Štýl bol na mieste okrem niekoľkých komentárov.
Uistite sa, že ste vždy komentovanie váš kód.
Ale vaša psets boli na mieste.
A tak ďalej.
A to je dobré pre porovnávač na vidieť, že chlapci sú uvedení
v ako veľa úsilia vo vašom štýle a váš návrh v kóde
že by sme chceli pre vás vidieť.
Takže som išiel po mojej vďačnosti pre zvyšok TA.
>> Existujú však Niekoľko otázok Rozprava
Ja len chcem ísť cez to by sa aj môj život
a mnoho iný TA "život trochu jednoduchšie.
Po prvé, som si všimol minulosť week-- koľko z vás
Boli beží na check50 váš kód Pred odoslaním?
OK.
Takže každý by mal robiť check50, protože-- secret-- sme vlastne
bežať check50 ako súčasť nášho správnosti skripty pre testovanie kódu.
Takže ak váš kód zlyháva check50, so všetkou pravdepodobnosťou,
to asi bude zlyhať našu kontrolu rovnako.
Niekedy vy majú správne odpovede.
Rovnako ako v chamtivý, niektoré máte správne číslo,
stačí vytlačiť nejaké extra veci.
A to navyše vec skutočne zlyhá šek,
pretože počítač nie je Naozaj viete, čo to hľadá.
A tak to bude len prejsť, vidieť, že váš výstup nie je
zodpovedať tomu, čo očakávame odpoveď byť, a označiť je to zle.
>> A ja viem, že sa stalo v niektoré z vašich prípadov tento týždeň.
Tak som sa vrátil a ručne nestal kód každého.
V budúcnosti však, prosím, uistite sa,
že utekáš skontrolovať 50 na vašom kóde.
Vzhľadom k tomu, že je to tak trochu bolesti CK musieť vrátiť späť a ručne preradenie do inej triedy
každý pset pre každého slobodný, malý minul inštancie.
Takže som nemal vzlietnuť žiadne body.
Myslím, že som si vzal voľno možná jeden alebo dva pre dizajn.
V budúcnosti aj keď, ak ste nedarí check50,
budú prijaté body off správnosť.
>> Okrem toho, sú psets vzhľadom piatok napoludnie.
Myslím, že je to sedem minút neskoré doba odkladu, že sme dať.
Per Harvard času, oni majú dovolené bolo sedem minút neskoro na všetko.
Tak tu na Yale, budeme držať sa, že rovnako.
Ale celkom veľa, na 12:07, ak vaše pset nie je,
to bude označený ako neskoro.
A tak, keď je označená ako neskoro, TA-- ja som
Stále bude triedenie vaše psets.
Takže budete stále vidieť stupeň objaviť.
Avšak, viem, že sa na koniec semestra,
všetky neskorej psets bude len automaticky vynulovaná počítačom.
>> Robíme to z dvoch dôvodov.
Raz, niekedy dostaneme ospravedlnila, ako výhovorky dekana
neskôr, že neviem o doteraz.
Tak sme radi, aby sa uistil, že sme triedenie všetko len v prípade, rovnako ako, že som
Chýba dekana výhovorku.
A za druhé, majte na myseľ, stále sa môžete
odpojiť jedného pset že má plnej šírke bodov.
A tak sme radi stupeň všetky vaše psets len
aby sa ubezpečil, že váš priestor je tam a vy ich skúšať.
Takže aj keď je to neskoro, budete stále získať úver na pôsobnosti bodov, myslím.
>> Takže morálne príbehu je, aby že vaše psets sú v on-včas.
A ak nie sú v on-včas, viem, že to nie je veľký.
Jo, než som ísť ďalej, nemá niekto mať Akékoľvek otázky týkajúce pset spätnú väzbu?
Jo.
>> Divákov: Vedeli ste, že sme môžu klesnúť jeden z psets?
>> ANDI PENG: Jo.
Takže je tu deväť psets celkovo v priebehu semestra.
A ak máte priestor points-- takže rozsah je len,
celkom veľa, ste pokusom o Problém, ste uvedení v čase,
sa vám ukazujú, že ste preukázal, že ste čítal spec.
To je celkom veľký priestor.
A ak ste sa plnia rozsah bodov, my
môžu klesnúť najnižšiu jedným z plného rozsahu.
Tak to je vo svoj prospech, aby dokončiť a skúsiť každý pset.
>> Aj upload-- ak žiadny z je pracovať, je nahrať všetky.
A potom budeme snáď môcť aby vám niektoré z týchto bodov späť.
Super.
Nejaké ďalšie otázky?
Skvelé.
>> Po druhé, kancelária hours-- pár rýchle poznámky o úradných hodinách.
Takže najprv, príde na začiatku týždňa.
Nikto nie je nikdy v úradné hodiny na pondelok.
Christabel prišiel úradné hodiny minulú noc.
Jo, Christabel.
A to, čo sme sa v kancelárii hodiny v noci, Christabel?
>> Divákov: Mali sme zmrzlinu.
>> ANDI PENG: Tak to je v poriadku, mali sme zmrzlina v úradných hodinách minulú noc.
Aj keď nemôžem sľúbiť, že budeme mať zmrzlinu na úradné hodiny
každý týždeň, čo som vám sľúbiť, je to, že tam bude významne
lepší študentka pomer TA.
Rovnako ako legitímne, je to ako tri ku jednej.
Vzhľadom k tomu, že kontrast s Štvrtok, máte asi 150
naozaj zdôraznil, deti a žiadnu zmrzlinu.
A to jednoducho nie je produktívne pre nikoho.
Takže Ponaučenie z príbehu je, príde čoskoro na pracovný čas a dobrých vecí
stane sa.
>> Tiež, príďte pripravení klásť otázky.
Ty vieš?
Bez ohľadu na to, čo TA, ja myslím, hovorili,
sme sa dostať pár študentov ktorí prídu na štvrtok v, ako, 10:50
nie po prečítaní spec bytia ako pomôž mi, pomôž mi.
Bohužiaľ v tomto bode, je tu nie je moc, čo môžeme urobiť, aby vám pomohol.
Tak príďte na začiatku týždňa.
Príďte skoro na úradné hodiny.
Príďte pripravení klásť otázky.
Uistite sa, že vás, ako študent, sú miesta, kde
musíte byť tak, že TA môže vás spolu,
čo je to, čo úradné hodiny by mali byť pridelené pre.
>> Po druhé, takže viem, že profesormi rád, aby nás prekvapil s testami.
Mal som profesora tie ako, yo, mimochodom,
pamätajte, že v polovici obdobia Máte budúci pondelok.
Jo, som nevedel o tom strednodobom horizonte.
Takže ja budem, že TA ktorá vám pripomína, všetci, že kvíz
0-- pretože, viete, že sme CS.
Teraz, keď sme urobili pole, dostanete prečo je to kvíz 0, nie kvíz 1, eh?
OK.
Oh, dostal som nejaké smiech na tomto jeden.
OK.
>> Takže kvíz 0 bude 14.októbra, pokiaľ ste v sekcii pondelok streda
15. októbra, ak ste v sekcia utorok štvrtok.
To neplatí pre tí z vás na Harvarde
who-- Myslím, že budete všetci pričom vaše kvízy na 14 ..
>> Tak jo, budúci týždeň, ak David, v prednáške, ide,
jo, tak o tom kvíz budúci týždeň, vy všetci
nebude v šoku, pretože ste prišli na časti
a viete, že vaše kvíz 0 je za dva týždne.
A budeme mať kontrolu zasadnutie a všetko.
Takže žiadne obavy o sa báť za to.
Akékoľvek otázky before-- otázky vo všetkých otázkach týkajúcich sa logistických,
triedenie, úradné hodiny, profily?
Jo.
>> Divákov: Takže je kvíz bude v priebehu prednášky?
>> ANDI PENG: Jo.
Takže kvízu, myslím si, je 60 minút pridelené v tomto časovom úseku
že budete len vziať v prednáškovej sále.
Takže nemusíte prísť o, rovnako ako, náhodný 7:00 PM.
Je to všetko dobré.
Jo.
Super.
>> Dobre.
Takže budeme zaviesť koncept pre vás
tento týždeň, že David má už druh z dotkla v prednáške minulý týždeň.
Hovorí sa tomu GDB.
A koľko z vás, zatiaľ čo v priebeh písanie psets,
zaznamenali veľké tlačidlo, ktoré hovorí, "Debug" v hornej časti vášho IDE?
OK.
Takže teraz budeme skutočne dostať odkryť záhada, čo týmto tlačidlom skutočne
robí.
A ja vám zaručiť, je to krásna, krásna vec.
>> Takže až do teraz, myslím, že tam bolo dve veci
Študenti boli typicky robí pri ladení psets.
Jeden z nich, buď pridať printf () - tak každých pár riadkov,
pridávajú v printf () - ach, čo je to premenná?
Ach, ako je táto premenná now-- a tak nejako vidieť progresiu
z kódu, ako to beží.
Alebo druhá metóda deti urobiť, je že stačí napísať celú vec
a potom ísť takto na konci.
Dúfajme, že to funguje.
Ja vám zaručiť, GDB je lepšie než obaja z týchto metód.
Jo.
Takže to bude váš nový najlepší priateľ.
Vzhľadom k tomu, že je to krásna vec ktorý vizuálne zobrazuje oba
čo váš kód robí v určitom bode
rovnako ako to, čo všetky vaše premenné sú účtovné,
ako to, čo ich hodnoty, v tomto konkrétnom bode.
A týmto spôsobom, môžete si naozaj nastaviť zarážky v kóde.
Môžete spustiť cez riadok po riadku.
A GDB budú mať len pre vy, zobrazí sa pre vás,
čo všetky vaše premenné sú, čo robia,
čo sa deje v kóde.
A takým spôsobom, že je to tak oveľa jednoduchšie vidieť
čo sa deje, namiesto printf-ing alebo písanie sa vaše vyhlásenie.
>> Takže urobíme príklad neskôr.
Takže to vyzerá trochu abstraktné.
Žiadne starosti, urobíme príklady.
A tak v podstate, tri najväčšie, najpoužívanejšie funkcie, ktoré budete potrebovať v GDB
sú ďalšie, prekročiť, a krok do tlačidiel.
Idem cez hlavu tam, v skutočnosti, práve teraz.
>> Takže môžete vidieť, že chlapci všetko alebo by som mal priblížiť trochu?
V zadnej, môžete vidieť, že?
Mám priblížiť?
Len trošku?
OK v pohode.
Tam sme ísť.
OK.
>> Tak som si, tu, moji implementácie pre chamtivý.
A aj keď veľa z vás napísal chamtivý v while form-- že
je úplne prijateľný spôsob, ako robiť to-- iný spôsob, ako to urobiť, je jednoducho
rozdeliť v modulo.
Vzhľadom k tomu, potom môžete mať svoj hodnota a potom mať svoje zostávajúce.
A potom stačí pridať to všetko dohromady.
Má logiku, čo robím tu zmysel pre každého,
Ako začneme?
Druh?
Super.
Skvelé.
Je to celkom sexi kus kódu, povedal by som.
Ako som povedal, David, v prednáška, po chvíli,
všetci začnete vidieť kód ako niečo, čo je krásne.
A niekedy, keď vidíte, krásna kód, je to tak nádherný pocit.
>> Takže sa však, keď tento kód je veľmi krásne, že nefunguje správne.
Takže poďme bežať check50 na túto tému.
Skontrolujte, či 50 20-- OOP.
2?
Je to pset2?
Jo.
Oh, pset1.
OK.
Tak sme sa spustiť check50.
>> A ako vy môžete vidieť tu, to nedarí niekoľko prípadov.
A pre niektoré z vás, v Priebeh robí váš problém súpravy,
ste ako, ehm, prečo je to tak nefunguje.
Prečo to funguje pre niektoré hodnoty, ale nie pre ostatné?
No, GDB bude vám pomôže zistiť out, prečo tieto vstupy boli nefunguje.
>> OK.
Tak uvidíme, jeden z Kontroly som bol neúspešný v check50
bola vstupná hodnota 0,41.
Takže správna odpoveď, že mali by ste sa dostať je 4.
Ale namiesto toho, čo som vytlačenie je 3-n, čo je nesprávny.
Takže poďme stačí spustiť tento ručne, len Uistite sa, že check50 funguje.
Urobme ./greedy.
Jejda, musím urobiť chamtivý.
Tam sme ísť.
Teraz ./greedy.
>> Koľko je dlhuje?
Urobme 0,41.
A jo, vidíme tu že je to výstup 3
keď správna odpoveď, v skutočnosti by malo byť 4.
Takže poďme vstúpiť GDB a vidieť, ako môže ísť o tom, ktorým tento problém.
>> Takže prvý krok v Vždy ladenie kódu
je nastaviť zarážku, alebo bod, na ktorý
Chcete v počítači alebo debugger začať uvažovať.
Takže ak nemáte naozaj viete, čo je tvoj problém,
Zvyčajne, typický, čo chceme urobiť, je nastaviť náš zarážku na hlavnú.
Takže ak vy môžete vidieť červené tlačidlo priamo tam,
Jo, to som bol ja nastavenia breakpoint pre hlavnú funkciu.
Aj kliknite na to.
>> A potom môžem ísť až na môjho tlačidlo Debug.
Trafil som ten gombík.
Dovoľte mi, aby som zoom späť, či môžem.
Tam sme ísť.
Takže máme tu, panel na pravej strane.
Je mi ľúto, chlapci v chrbte, vy Nemôžete naozaj vidieť naozaj dobre.
Ale v podstate všetky toto právo panel robí
je sledovanie ako zvýraznené línie, čo je riadok kódu
že počítač je v súčasnosti beží, rovnako ako všetky vaše premenné
tu dole.
>> Takže ste dostali centov, mincí, n, všetky vyhlásený rôzne veci
v tomto bode.
Žiadne starosti, pretože sme vlastne inicializuje je na všetkých premenných doteraz.
Takže vo vašom počítači, vaše Počítač je len vidieť,
oh, 32767 bol naposledy použitý funkcie tohto pamäťového priestoru v mojom počítači.
A tak to je, kde je v súčasnej dobe centov.
Ale nie, že akonáhle sa spustiť kód, by sa mala stať inicializovaný.
>> Takže poďme prejsť, riadok linka, čo sa tu deje.
OK.
Tak tu sú tri Tlačidla, ktoré som práve vysvetlil.
Máte Play, alebo funkcia Run, tlačidlo, budete mať krok nad tlačidlom,
a máte tiež krok do tlačidla.
A v podstate, všetci traja je jednoducho ísť cez váš kód
a robiť rôzne veci.
>> Takže obvykle, keď ste ladenie, Nechceme, aby jednoducho stlačiť Play,
pretože Play bude práve beží váš kód k jeho koncu.
A potom nebudete v skutočnosti viete, čo je tvoj problém
je, ak si nastaviť viac zarážky.
Ak nastavíte viac zarážky, to bude len automaticky
spustiť z jednej zarážky, na ďalšie, na ďalšie.
Ale v tomto prípade máme len, že jeden, pretože my
Chcete pracovať našu cestu od zhora nadol nadol.
Takže budeme ignorovať ten gombík teraz na účely tohto programu.
>> Takže Krok cez funkciu len Kroky nad každým jednu linku
a povie vám, čo počítač robí.
Step do funkcie pokračuje do skutočnú funkciu
že je na vašom riadku kódu.
Tak napríklad, rovnako ako printf (), že je funkcia, že jo?
Keby som chcel fyzicky krok do funkcie printf (),
Ja by som skutočne ísť do kusu smerovacie číslo, kde printf () bol napísaný a vidieť
čo sa tam deje.
>> Ale zvyčajne, budeme predpokladať, že kód, ktorý dáme vám funguje.
Predpokladáme, printf () pracuje.
Predpokladáme, že GetInt () funguje.
Takže nie je potrebné krok do týchto funkcií.
Ale či je tu funkcia že píšete sami
že chcete skontrolovať čo sa deje,
by ste chceli kroku do tejto funkcie.
>> Takže teraz sme len tak prekročiť tento kus kódu.
Takže poďme sa pozrieť.
Oh, print, "Ach hai, ako mnoho zmien je dlžný? "
Nezaujíma nás.
Vieme, že to funguje, tak sme krok nad ním.
>> Takže n, čo je naša float, že máme initialized-- alebo declared--
up na vrchole, sme teraz rovnajúcej sa, že pre GetFloat ().
Takže poďme krok cez to.
A vidíme u dno tu, program
nabáda ma na vstup hodnotu.
Takže poďme Zadajte hodnotu chceme testovať tu, čo je 0,41.
Skvelé.
>> Takže teraz n- si chlapci vidieť tu, u bottom-- je to
stored-- pretože my Zatiaľ nie sú zaoblené, to je
uložené v tomto ako obrie float, že je, 4099999996,
čo je dosť blízko, aby naše účely, práve teraz, na 0,41.
A potom sa uvidí neskôr, keď sme pokračovať prekročil programu,
po tu, n sa stal zaoblené a centov stal 41.
Skvelé.
Takže vieme, že naše zaokrúhlenie má prácu.
Vieme, že máme správny počet centov,
takže vieme, že je to nie je naozaj problém.
>> Takže budeme pokračovať krokovanie Na v tomto programe.
Ideme sem.
A tak po tomto riadku kódu, my by mali vedieť, koľko štvrtiny máme.
Sme prekročiť.
A vidíte my, v skutočnosti, mať jeden štvrťroku, pretože sme sa odpočíta 25
z našej počiatočnej hodnoty 41.
A máme 16 doľava pre naše centov.
>> Má každý pochopiť, ako Program je krokovanie
a prečo centov je dnes 16 a prečo, teraz, mince sa stala 1?
Je každý nasledujúci, že logika?
Super.
Tak, aby na tomto okamihu pracovný program je, že jo?
Vieme, že to robí presne to, to, čo chceme, aby to.
A my nie v skutočnosti musieť vytlačiť, ach, čo
Je centov v tomto bode, čo je mincí v tomto bode.
>> Aj naďalej sa prostredníctvom programu.
Krok cez.
Super.
Ideme cez desaťhalierniky.
Skvelé.
Vidíme, že je to vziať off 0,10 $ za desetník.
A teraz máme dve mince.
To je správne.
>> Ideme cez haliere a vidíme, že sme sa dostali zostane centov.
Hmm, to je divné.
Tu hore na programe, mal som k odpočítať svoje haliere.
Možno som jednoducho nebol tým, že linka práva.
A beda, môžete vidieť tu, pretože vieme,
že sme posilnenie potrubím 32 a 33,
že je miesto, kde náš program nesprávne mal premenných spustiť.
Takže môžeme pozerať a vidieť, oh, Som odpočítaním centov tu,
ale ja nie som v skutočnosti pridať do môjho hodnotou mince.
Som pridanie do centov.
A ja nechcem pridať do centov, chcem pridať do mincí.
Takže keď sme sa zmeniť na mince, máme pracovný program.
Môžem bežať check50.
Stačí si len opustíte GDB práva tu a spustite check50 znova.
Mohol by som to urobiť.
Musím urobiť chamtivý.
0.41.
A tu je to tlač out správnu odpoveď.
>> Tak ako vy môžete vidieť, GDB je naozaj mocný nástroj
pretože keď máme toľko kód deje, a tak veľa premenných
že je to pre nás ťažké, ako človek, sledovať.
Počítač, v GDB debugger, má schopnosť
udržiavať prehľad o všetkom.
Ja viem, v Visionaire, vy pravdepodobne mohol zasiahnuť niektoré segmentácia chyby
pretože ste používali mimo hranice svojho poľa.
V príklade Caesara, to je presne to, čo som tu vykonaná.
>> Tak som zabudol skontrolovať čo by sa mohlo stať, keby mi
nemal dva argumenty príkazového riadka.
Len som to dať do tejto kontroly.
A tak, keď som bežať Debug-- nastavím môj bod prerušenia tam doprava.
Bežím ladenie.
>> OK.
Jo.
Takže vlastne, GDB mal sa mi tam povedal,
Bola to chyba, tam segmentácie.
Ja neviem, čo sa deje práve tam, ale keď som bežal,
že to funguje.
Pri spustení riadkov kódu a cez GDB mohol len náhle skončiť na vás,
ísť hore a pozrieť sa, čo je červená chyba je.
To vám poviem, Hej, mal poruchu segmentáciu,
čo znamená, že ste sa pokúsili o prístup priestory v poli, ktoré neexistuje.
Jo.
>> Takže ďalší problém Nastavte tento týždeň, vy
bude pravdepodobne mať veľa Premenné plávajúce okolo.
Vy nebudete byť istí, čo všetci na mysli v určitom okamihu.
Takže GDB vám naozaj pomôže v premýšľaním čo oni sú všetci rovná
a sú schopní vidieť, že vizuálne.
Je niekto zmätený o tom, ako niečo z toho pracuje?
Super.
Dobre.
Takže po tom, my sme bude potápať doprava
do sú štyri rôzne typy druhov pre tento týždeň.
Ako mnohí z vás, najprv zo všetkého, ako začneme,
Prečítal celý spec pre pset3?
OK.
Som hrdý na vás chlapci.
To je ako polovica triedy, ktorá je výrazne viac ako minule.
>> Tak to je skvelé, pretože keď hovoríme o obsahu
v lecture-- alebo ľúto, v section-- sa mi páči
týkať veľa ktorý späť na to, čo je pset
a ako chcete implementovať, že vo vašom pset.
Takže ak prídete s čítať spec, to bude
bolo oveľa jednoduchšie pre vás pochopiť čo hovorím, keď hovorím,
oh hej, mohlo by to byť naozaj dobré miesto na vykonanie tohto druhu.
Takže tí z vás, ktorí si prečítať spec vedia, že, ako súčasť vášho pset,
budete musieť napísať typ druhu.
Takže to môže byť veľmi užitočné pre mnoho z vás dnes.
>> Takže budeme začať s, v podstate, najviac jednoduchý typ
Sort, výber triedenia.
Typický algoritmus pre ako by sme ísť o to
je-- David prešiel to všetko v prednáška, tak som si rýchlo pohybovať pozdĺž
here-- je v podstate, vy majú celý rad hodnôt.
A potom nájdete podrobnosti Najmenšia hodnota netriedený
a zamieňať túto hodnotu s Prvý netriedený hodnota.
A potom si len stále opakovať so zvyškom vášho zoznamu.
>> A tu je vizuálny vysvetlenie o tom, ako to by mohlo fungovať.
Tak napríklad, keď sme boli na začiatok s radom piatich elementov, index
0 až 4, s 3, 5, 2, 6, a 4 Hodnoty umiestnené v array-- tak práve teraz,
my len tak predpokladať, že sú všetci netriedený
preto, že neboli testované inak.
>> Tak, ako sa výber druhu by Práca je to, že by ako prvý
prejsť celok z netriedeného poľa.
To by vybrať najmenšiu hodnotu.
V tomto prípade, 3, pravá Teraz, je najmenšia.
To dostane až 5.
Nie, 5 nie je väčšia than-- alebo ľúto, nie je menšia than-- 3.
Takže minimálna hodnota je stále 3.
A potom sa dostanete na 2.
Počítač vidí, oh, 2 je menšia ako 3.
2 teraz musí byť minimálna hodnota.
A tak 2 swapy s týmto prvým hodnotou.
>> Takže po jednom priechodu, môžeme skutočne vidieť že 2 a 3 sú prehodené.
A my sme len tak v tom pokračovať To opäť so zvyškom poľa.
Takže budeme len prejsť posledné štyri indexy poľa.
Uvidíme, že 3 je ďalšie minimálna hodnota.
Takže ideme na swap, ktorý sa 4.
A potom sme to len tak, aby beh cez kým nie, nakoniec, vy
dostať sa do triedeného poľa, v ktorom 2, 3, 4, 5, a 6 sú všetky zoradené.
Rozumejú logiku o tom, ako výber triedenie funguje?
>> Proste mať nejaký na minimálnu hodnotu.
Ste sledovanie, čo to je.
A keď ju nájdete, je zamieňať s prvou hodnotou v array--
alebo, nie je prvý value-- ďalšia hodnota v matici.
Super.
>> Takže ako chlapci druh Videl z krátkej zazrel,
ideme pseudocode to.
Takže ak vy vzadu chcú tvoria skupinu, všetci pri stole
môžu tvoriť trochu partnera, idem dať sa vám bude páčiť tri minúty
len prebrať logika, v angličtine,
o tom, ako by sme mohli byť schopní implementovať pseudokód napísať výberom Triediť.
A je tu cukrík.
Prosím, prísť a dostať cukríky.
Ak ste do chrbta a chcete cukrovinky, môžem hodiť cukroví na vás.
V skutočnosti, robiť vás-- chladu.
Oh, prepáč.
OK.
>> Takže ak by sme chceli, as trieda, zápis pseudokód
na to, ako by sa dalo pristupovať tento problém, stačí pokojne.
Budem jednoducho ísť okolo a, v poriadku, spýtajte sa skupiny
na ďalší riadok Čo by sme mali robiť.
Takže ak vy chcete začať off, čo je prvá vec,
robiť, keď sa snažíte vykonávať spôsob, ako vyriešiť tento program
selektívne zoradiť zoznam?
Poďme len predpokladať, my majú celý rad, v poriadku?
>> Divákov: Chcete vytvoriť niektoré druh [nepočuteľný], že ste
beh cez celé tvoje pole.
>> ANDI PENG: Správne.
Takže budete chcieť opakovať cez všetky priestoru, je to tak?
Takže, skvelé.
Ak si chcú chalani mi dať ďalšie line-- jo, do chrbta.
>> Publikum: Pozrite sa na ne všetko pre najmenších.
>> ANDI PENG: Ideme na to.
Takže chceme prejsť a skontrolovať, vidieť, čo je minimálna hodnota, že jo?
Chystám sa skrátiť, že na "min."
Čo vy chcete robiť po ste našli minimálnu hodnotu?
>> Divákov: [Nepočuteľné]
ANDI PENG: Takže vy budete chcieť spínač je s prvým z tohto poľa,
v poriadku?
To je začiatok, budem hovoriť.
Dobre.
Takže teraz, že ste vymenili prvé človek, čo chcete robiť po tom?
Takže teraz vieme, že toto tu musí byť najmenšia hodnota, je to tak?
Potom budete mať ďalšie odpočinok matice, ktorá je netriedený.
Takže to, čo chcete robiť tu, ak máte chlapci chcú, aby mi ďalší riadok?
Divákov: Takže chcete iterácii po zvyšok poľa.
ANDI PENG: Jo.
A tak to, čo robí iterácie druh znamenať pravdepodobne budeme potrebovať?
Aký typ of--
>> Publikum: Oh, ďalší premenná?
ANDI PENG: Pravdepodobne ďalšie pre sláčiky, je to tak?
Takže sme pravdepodobne bude chcieť prechádzať through-- skvele.
A potom ste sa vrátiť a Pravdepodobne skontrolovať minimálna znovu,
v poriadku?
A ty budeš stále opakovať to, pretože slučiek len tak
zachovať systémom, nie?
>> Tak ako vy môžete vidieť, my Len majú všeobecnú pseudocode
o tom, ako chceme, aby tento program vyzerať.
Tento ITERATE tu, čo máme typicky musieť napísať do nášho kódu
ak chceme iterovat prostredníctvom pole, aký typ konštrukcie?
Myslím si, že Christabel už povedal skôr.
>> Divákov: A pre sláčiky.
>> ANDI PENG: A pre sláčiky?
Presne tak.
Takže je to pravdepodobne Bude to pre slučku.
Čo je to šek tu bude znamenať?
Zvyčajne, ak chcete skontrolovať ak niečo je niečo else--
>> Divákov: Ak.
>> ANDI PENG: if, že jo?
A potom odkladacie tu, budeme prejsť neskôr, pretože David
prešiel, že v prednáške rovnako.
A potom druhá ITERATE implies--
>> Divákov: Ďalším pre sláčiky.
>> ANDI PENG: --another pre sláčiky, presne tak.
Takže ak sa pozeráme na to správne,
je vidieť, že sme pravdepodobne bude potrebovať vnorené pre sláčiky
s podmieneného príkazu v tú a potom skutočný kus kódu, ktorý je
chystá vymeniť hodnôt.
Tak som práve všeobecne písaný kód tu pseudokód.
A potom sme to vlastne bude fyzicky, ako trieda,
pokúsiť sa realizovať to dnes.
Vráťme sa do tohto IDE.
>> Uh Oh.
Prečo je to ne-- je to tak.
OK.
Ospravedlňujeme sa, ale dovoľte mi, aby som sa snaží priblížiť trochu viac.
Tam sme ísť.
Všetko, čo robím tu je, ktoré som vytvoril program s názvom "výber / sort.c."
Som vytvoril rad deviatich hodnoty, 4, 8, 2, 1, 6, 9, 7, 5, 3.
V súčasnej dobe, ako môžete vidieť, že sú neusporiadané.
n bude číslo, ktoré vám povie množstvo hodnôt
máte v poli.
V tomto prípade sme majú deväť hodnoty.
A ja som práve dostal na slučku tu že vytlačí netriedeného poľa.
>> A na záver, som sa tiež dostal na slučky, že práve tlačí to znova.
Takže teoreticky, ak je tento program pracuje správne, na konci,
mali by ste vidieť tlačený pre sláčiky , V ktorom 1, 2, 3, 4, 5, 6, 7, 8,
9 sú správne, aby.
>> Takže máme našu pseudocode tu.
Má niekto chcel to-- som len ísť požiadať o volunteers--
povedz mi presne, čo mám písať, pokiaľ Ak chceme, ako prvý, len opakovať
prostredníctvom začiatku tohto poľa?
Aký je riadok kódu, že som pravdepodobne bude potrebovať tu?
>> Divákov: [Nepočuteľné]
>> ANDI PENG: Jo, pocit zadarmo to-- Je nám ľúto,
Nemusíte sa stať up-- pocit zatiaľ zvýšiť váš hlas trochu.
>> Obecenstvo: pre int i rovná 0--
>> ANDI PENG: Jo, dobrý.
>> Divákov: i je menšia ako dĺžka poľa.
>> ANDI PENG: Takže majte na myseľ tu, pretože sme
nemajú funkciu, ktorá us hovorí, že dĺžka poľa,
už máme hodnota, ktorá ukladá, že.
Je to tak?
Ďalšia vec, ktorú majte v mind-- v poli
deviatich hodnôt, aké sú indexy?
Povedzme, že to pole bolo 0 až 3.
Vidíte, že posledný index je v skutočnosti 3.
Nie je to 4, aj keď tam je štyri hodnoty v poli.
>> Takže tu, musíme byť veľmi opatrní na to, čo naše podmienky pre dĺžku
bude.
>> Divákov: Nebolo by to n mínus 1?
ANDI PENG: Ide to n mínus 1, presne tak.
Dáva to zmysel, prečo to je n mínus 1, všetci?
Je to preto, že pole sú nula-indexované.
Začnú na 0 a prevádzkovať až n mínus 1.
Jo, je to trochu zložitejšie.
OK.
A potom--
Publikum: Isnt'1 že už postarané aj keď,
jednoduchým nehovorí "menšie ako alebo presne "a len povedal:" menej ako? "
>> ANDI PENG: To je naozaj dobrá otázka.
Áno, áno.
Ale tiež spôsob, akým sme vykonávanie kontroly právo,
je potrebné porovnať dve hodnoty.
Takže ste vlastne chcete nechajte "na" prázdny.
Vzhľadom k tomu, ak si porovnať toto, vy nebudete
nič po ňom porovnať, že jo?
Jo.
Takže aj ++.
Poďme pridať naše držiaky.
Jejda.
Skvelé.
Takže máme začiatok našej vonkajšej slučky.
Takže teraz pravdepodobne chcieť vytvoriť premennú pre vedenie
Trať najmenšiu hodnotu, je to tak?
Má niekto chcel mi dať riadok kódu, ktorý by to robil?
Čo budeme potrebovať, ak ideme chcieť uložiť niečo?
>> Správne.
Možno, že lepší názov pre to by be-- "temp" úplne works--
možno viac vhodne pomenovaný by bolo, ak chceme, aby najmenšie value--
>> Divákov: Min.
ANDI PENG: min, tam ideme.
min by bolo dobré.
A tak tu to, čo my Chcete inicializovať ju?
To je trochu zložitejšie.
Pretože práve teraz u začiatok tohto poľa,
ste sa pozrel na čokoľvek, že jo?
Tak čo, automaticky, pokiaľ sme len na i rovná 0,
to, čo chceme inicializovať naša prvá minimálna hodnota to?
Divákov: i.
ANDI PENG: i, presne tak.
Christabel, prečo chceme, inicializovať to aj?
>> Publikum: Vzhľadom k tomu, no, začíname s 0.
Takže, pretože máme s čím porovnávať to je minimálny skončí na 0.
>> ANDI PENG: Presne tak.
Takže ona je presne to pravé.
Pretože máme vlastne napriek tomu sa pozrel na čokoľvek,
nevieme, čo naše minimálna hodnota.
Chceme len inicializovať ju i, ktorá v súčasnej dobe, je tu.
A ako budeme pokračovať presunúť dole toto pole,
uvidíme, že s každým Ďalší priechod, aj zvýši.
A tak sa v tomto bode, aj sa pravdepodobne bude
že chcú byť minimálne, pretože to bude čokoľvek
je začiatok netriedeného pole.
Super.
>> Takže teraz chcete pridať slučky for tu to je
bude iterovat netriedený, alebo zvyšok tohto poľa.
Má niekto chcel mi dať riadok kódu, ktorý by to robil?
Hint-- čo potrebujeme tu dole?
Čo sa deje ísť to pre sláčiky?
Jo.
Divákov: Tak sme chceli majú iný celé číslo,
preto, že sme beží cez zvyšok matice namiesto I, možno
j.
>> ANDI PENG: Jo, j znie dobre.
Rovná?
>> Divákov: Takže by bolo aj plus 1, pretože začínate na ďalšiu hodnotu.
A potom sa to znova end--, j je menej ako n mínus 1 a potom j ++.
ANDI PENG: Skvelé.
>> A potom tu, budeme chcieť skontrolovať, či je splnená podmienka naša,
v poriadku?
Vzhľadom k tomu, že chcete zmeniť minimálnu hodnotu
ak je to v skutočnosti menší, než to, čo ste prirovnal ju k, nie?
Takže to, čo budeme chcieť v tú?
Skontrolujte.
Aký typ vyhlásenia sme pravdepodobne bude
tí chcete použiť, keby sme chcete skontrolovať niečo?
>> Divákov: if.
>> ANDI PENG: if.
Tak if-- a čo to bude podmienka, že chceme dovnútra
našej if?
>> AUDIENCE: V prípade, že hodnota j je menšia ako hodnota ja-
>> ANDI PENG: Presne tak.
Tak if-- tak toto pole sa nazýva "pole."
Skvelé.
Takže ak array-- čo to bolo?
Zopakuj to.
>> Divákov: Ak je pole-j je menšia ako array-i, potom by sme zmeniť min.
Takže min by j.
>> ANDI PENG: Dáva to zmysel?
OK.
A teraz tu dole, sme vlastne chcú realizovať swap, že jo?
Takže spomínate, v prednáške, že Dávid, keď sa snažil vymeniť the-- to, čo bolo
to-- pomarančový džús a milk--
>> Divákov: To bolo hrubé.
>> ANDI PENG: Jo, to bolo celkom hrubý.
Ale bol to celkom dobrý koncept demonštrovať čas.
Takže myslíte, že z vašich hodnôt tu.
Máte poľa min, rad i,
alebo čo sme sa pokúšali vymeniť tu.
A ty asi nedá naliať ich do navzájom v rovnakú dobu, že?
Tak čo s tým budeme musieť vytvoriť tu
aby správne vymeniť hodnoty?
>> Divákov: dočasné premenné.
>> ANDI PENG: dočasné premenné.
Takže poďme robiť int temp.
Vidíš, to bude lepšie čas to-- hej, čo to bolo?
OK.
Takže by to bolo lepšie čas pomenovať premennú "Temp."
Takže poďme robiť int temp.
Čo budeme SET TEMP rovno tu?
Publikum: Min?
ANDI PENG: Je to trochu zložitejšie.
V skutočnosti nezáleží na tom, do konca roka.
Nezáleží na tom, čo Poradie sa rozhodnete vymeniť v
tak dlho, ako budete robiť istý, že ste sledovanie, čo ste swapovanie.
>> Divákov: Mohlo by to byť array-i.
>> ANDI PENG: Jo, poďme robiť pole-I.
A čo potom je ďalší riadok kódu chceme mať tu?
Divákov: array-i rovná array-J.
ANDI PENG: A konečne?
Divákov: array-j sa rovná array-i.
Divákov: Alebo array-j rovná array-temp-- alebo teplota.
>> ANDI PENG: OK.
Takže poďme bežať to a uvidíme, či to bude fungovať.
Tam, kde sa deje, že?
Oh, to je problém.
Pozri, na linke 40, my sme sa snaží používať pole-J?
Ale kde j existujú iba v?
>> Publikum: V cykle for.
ANDI PENG: Správne.
Tak čo s tým budeme musieť urobiť?
>> Divákov: Definovať to vonku the--
Publikum: Hej, myslím, že máš použiť iný if, že jo?
Tak, ako v prípade, že minimum-- v poriadku, nechajte ma premýšľať.
>> ANDI peng: Chlapci, vyskúšajte sa pozrieť Poďme
pozri, čo sa niečo, čo môžeme robiť?
>> Divákov: OK.
Takže v prípade, že minimálna nerovná j-- takže v prípade, že minimum je stále já--
potom by sme nemuseli vymeniť.
>> ANDI PENG: Znamená to, že rovné i?
Čo chceš povedať tu?
>> Publikum: Alebo jo, v prípade, že Minimálna nerovná i, jo.
ANDI PENG: OK.
No, to rieši, druh, naše problémy.
Ale to stále ešte nerieši problém z toho, čo sa stane, keď j-- od j
neexistuje mimo neho, čo si chceme s tým robiť?
Deklarovať to vonku?
Poďme skúsiť spustiť tento.
Uh Oh.
Náš druh nefunguje.
>> Ako vidíte, naša pôvodná array mal tieto hodnoty.
A potom by mal mať bol v 1, 2, 3, 4, 5, 6, 7, 8, 9.
Nefunguje to.
Ahh.
Čo budeme robiť?
Divákov: Debug.
ANDI PENG: Dobre, môžeme to skúsiť.
Môžeme ladiť.
Oddialenie trochu.
Vydajme našu zarážku.
Poďme jako-- OK.
>> Takže preto, že už vieme, že tieto riadky, 15 až 22,
sú working-- pretože všetko, čo robím, je Len iterácie a printing--
Môžem ísť dopredu a vynechať to.
Začnime na riadku 25.
OOP, dovoľte mi, aby som sa zbaviť toho.
>> Divákov: Takže je zarážka kde začína ladenie?
ANDI PENG: Or zastaví.
Divákov: Or zastaví.
ANDI PENG: Jo.
Môžete nastaviť viac zarážky a to môže len skočiť z jedného na druhého.
Ale v tomto prípade nevieme, kde je táto chyba deje.
Tak sme sa len chcete začať od zhora nadol.
Jo.
OK.
>> Takže táto linka tu, môžeme zasiahnuť.
Môžete vidieť tu dole, máme pole.
To sú hodnoty ktoré sú v poli.
Vidíte, že, ako sa index 0, to zodpovedá value-- oh,
Budem sa snažiť priblížiť.
Ospravedlňujeme sa, ale je to naozaj ťažké na see-- na indexe pole 0,
máme hodnotu 4 a potom tak ďalej a tak ďalej.
Máme lokálne premenné.
Práve teraz som sa rovná 0, čo chceme, aby to bolo.
>> A tak sa poďme držať krokovanie.
Naše minimum je rovné 0, čo tiež chceme, aby to bolo.
A potom sme sa vstúpiť na náš druhý pre slučky, ak array-j je menšie ako pole-i,
čo nebolo.
Takže ste vidieť, ako že preskočil, že?
>> Divákov: Takže ak by v prípade, minimum, všetko that-- nie že by to
byť vnútri prvého cyklu for?
ANDI PENG: Nie, pretože si napriek tomu chcete testovať.
Chcete urobiť porovnanie každý čas, dokonca aj po spustení cez to.
Nemusíte len chcem, aby to na prvé premietanie.
Ak chcete to s každý ďalší zase priechod.
Takže vy chcete skontrolovať Váš zdravotný stav vo vnútri.
Takže sme len tak udržujú v prevádzke tadiaľ.
Dám vám chlapci nápovedu.
To má čo do činenia s tým, že pri máte kontrolu svoj podmienečný,
nie ste kontrolu pre správne indexu.
Takže teraz ste kontrola index poľa j je menšie ako pole
index i.
Ale to, čo robíš sa na počiatku pre slučky?
Nie si nastavenie j rovnajúcu sa aj?
>> Jo, takže môžeme vlastne ukončite ladiaci tu.
Takže poďme sa pozrieť na našu pseudokódu.
For-- ideme začiatok i rovná 0.
Chystáme sa ísť až na n mínus 1.
Poďme zistiť, sme mať toto právo?
Jo, že mal pravdu.
>> Takže tu vnútri, my sme bude vytvoriť minimálnu hodnotu
a nastaviť, aby sa rovná aj.
Vedeli sme to urobiť?
Jo, to urobil.
Teraz v našom vnútornom pre sláčiky, my sme robiť j rovná aj na n mínus 1.
Vedeli sme to urobiť?
Skutočne, my sme robili to.
>> Tak Avšak to, čo sme porovnávanie tu?
>> Divákov: j plus 1.
ANDI PENG: Presne tak.
A potom budete chcieť nastaviť vaše minimálne rovná j plus 1 i.
Tak som šiel cez to naozaj rýchlo.
Myslíte si chlapci pochopili prečo je to j plus 1?
OK.
>> Takže vo vašom poli, v vaše prvé priechod,
Váš pre sláčiky, pre int i = 0, nech to jednoducho
Predpokladám, že to ešte nebol zmenený.
Máme rad, úplne, len štyri netriedené prvky, nie?
Takže chceme inicializovať aj rovná 0.
A ja sa chystá práve prejsť tejto slučky.
A tak sa v prvom prechode, ideme inicializovať premennú s názvom "min"
že tiež sa rovná i, pretože nemáme minimálnu hodnotu.
Tak, že je v súčasnej dobe presne 0 i.
A potom budeme prejsť.
A my chceme, aby sa znovu opakovať.
Teraz, keď sme našli to, čo náš minimálny je, chceme iterovat
znovu vidieť, či je to porovnanie, je to tak?
Tak j, tu, sa deje na rovné aj, čo je 0.
A potom, ak array j a i, ktorý je ten, ktorý je ďalší nad, as menej
než to, čo aktuálne minimum je hodnota, ktoré chcete vymeniť.
>> Takže povedzme, že máme má, rovnako ako, 2, 5, 1, 8.
Práve teraz, aj je rovné 0 a j je rovné 0.
A to je náš minimálna hodnota.
Ak je pole-j a ja-, takže v prípade, že raz to je po jednom pozeráme
je väčší ako ten pred tým, to bude stáť minimum.
>> Takže tu vidíme, že 5 nie je menšia ako to.
Takže to bude nebyť 5.
Vidíme, že 1 je menšia ako 2, nie?
Takže teraz vieme, že naše minimum je bude hodnota indexu pri 0, 1, 2.
Jo?
A potom, keď sa dostanete sem, môžete vymeniť správne hodnoty.
>> Takže keď vy ste boli len mať j Ako ste sa nepozerali na jednom
po ňom.
Vy ste pri pohľade na rovnaká hodnota, ktorá
je dôvod, prečo to jednoducho nič nerobím.
Znamená to, že zmysel pre každého, Preto sme potrebovali, aby plus 1 tam?
OK.
Teraz stačí spustiť cez neho, aby sa Uistite sa, že zvyšok je kód správny.
Prečo sa deje, že?
Ach, to je min tu.
Boli sme nákupný nesprávnu hodnotu.
Ale nie.
>> Ach jo, tu dole sme boli vymení nesprávne hodnoty rovnako.
Pretože sme sa pozerali na i a j.
To sú tie, ktoré sme kontrolovali.
Vlastne chceme swap minimum, súčasná minimálna,
s tým, čo jeden vonku je.
A ako vy môžete vidieť dole tu, máme zoradené pole.
Je to jednoducho musel urobiť s skutočnosť, že, keď
sme boli zaškrtnutím Hodnoty sme porovnávanie
sme sa nepozerali na správnych hodnotách.
Pozerali sme sa na rovnakej jednom tu, nie v skutočnosti ju vymeniť.
Musíte sa pozrieť na ten budúci k nej a potom môžete vymeniť.
Takže to je to, čo bolo celkom Pred odpočúvanie náš kód.
A to, čo tu urobil som všetko, čo je ladiaci program mohol urobiť pre teba
Len som to urobil na doska, pretože je to jednoduchšie,
vidieť, skôr než sa snažiť priblížite debuggera.
Znamená to, že zmysel pre všetkých?
Super.
>> Dobre.
Môžeme prejsť k hovoriť o asymptotickej notácie, ktorý
je len fantázia spôsob, ako hovoriť runtimes všetkých týchto druhov.
Takže viem, Davida, v prednáške, dotkla runtime.
A išiel cez celý vzorca o tom, ako vypočítať doby chodu.
Žiadne obavy o tom.
Ak ste naozaj zvedavý na, ako to funguje,
neváhajte sa mnou hovoriť po bode.
Môžeme prejsť formula dohromady.
Ale vy všetci chalani majú naozaj viem, je, že n na druhú nad 2
je to isté ako n na druhú.
Vzhľadom k tomu, najväčšieho počtu, exponent, rastie najviac.
A tak sa pre naše účely, všetko sa staráme o
je to, že obrie číslo, ktoré rastie.
>> Takže to, čo je najlepšie prípad runtime výberového druhu?
Ak sa chystáte mať iterovat zoznamom
a potom iterovat zvyšok tohto zoznamu,
koľkokrát sú budete pravdepodobne,
v najhoršom case-- v najlepšom prípade, sorry-- prebehnúť?
Možno lepšia otázka je sa opýtať, čo je najhorší prípad
runtime výberového druhu.
Divákov: n na druhú.
ANDI PENG: Je to n na druhú, vpravo.
Tak jednoduchý spôsob, ako myslieť, je to ako, kedykoľvek budete mať dvoch vnorených pre slučky,
to bude n druhú.
Pretože sú nielen vám preteká opäť,
musíte sa vrátiť okolo a skrz nej prechádzajú
opäť dovnútra pre každú hodnotu.
Takže v tomto prípade, vediete n časy n na druhú, čo je-- ľúto,
n krát n, ktorý sa rovná n na druhú.
>> A druh je tiež trochu unikátna v tom zmysle
že ak nemá tieto nevadí hodnoty sú už v poriadku.
Je to stále bude prebehnúť tak ako tak.
Povedzme, že to bolo 1, 2, 3, 4.
Bez ohľadu na to, či to bolo v poriadok, to ešte by prebehol
a ešte skontroloval minimálnu hodnotu.
To by robili Rovnaký počet kontrol
zakaždým, aj keď je robil nie vlastne sa ničoho dotknúť.
>> Takže v tomto prípade, že najlepšie a najhoršie runtime sú skutočne rovnocenné.
Takže očakávané runtime výberového druhu,
ktoré označujeme symbolom of theta, theta, v tomto prípade,
by tiež bolo n druhú.
Všetci traja z nich by sa n druhú.
Je každý jasné, prečo runtime je n na druhú?
>> Dobre.
Takže ja som jednoducho ísť rýchlo spúšťať cez zvyšok druhov.
Algoritmus pre bublina sort-- pamätať,
to bol prvý David prešiel na prednáške.
V podstate si krok celý zoznam
a vy ste práve swap-- Porovnať dve naraz.
A ak jeden je väčší, ako ste práve ich vymeniť.
Takže ak sú väčšie, mali by ste vymeniť.
Mám oficiálne tu.
>> Takže povedzme, že ste mali 8, 6, 4, 2.
Vy by ste porovnať 8 a 6.
Vy by ste potrebné ich vymeniť.
Tie by sa porovnávať 8 a 4.
Vy by ste potrebné ich vymeniť.
Ak musíte vymeniť 8 a je 2, zmena je tiež.
Takže v tom zmysle, môžete vidieť, odohrávajúce sa po dlhú dobu,
ako hodnoty druh bublinu konca, čo je dôvod, prečo hovoríme
bublinkové radenie.
>> Radi by sme len prejsť znovu náš druhý priechod, a naše tretie priechod,
a náš štvrtom priechodu.
V podstate, bublinkové radenie práve beží kým neurobíte žiadne ďalšie swapy.
Takže v tomto zmysle, je to len všeobecný pseudokód pre neho.
Žiadne starosti, to všetko bude on-line.
Nemusíme sa vlastne ísť cez tento.
>> Práve sme inicializovať čítač premenná, ktorá začína na 0 ° C.
A my iterovat celé pole.
A ak jedna hodnota je--, pokiaľ to hodnota je väčšia ako táto hodnota,
budete sa ich vymeniť.
A potom ste len bude pokračovať.
A budete počítať.
A vy len tak, aby robil to, keď prebieha meranie, je väčšia
ako 0, čo znamená, že zakaždým, budete musieť vymeniť,
viete, že chcete ísť späť a znovu skontrolujte.
Chcete zachovať kontrolu, kým nebudete vedieť že vy nemusíte vymeniť ešte.
>> Takže aké sú najlepšie a najhoršie puzdro behové moduly pre bubble druhu?
A hint-- je to vlastne líši od výberu druhu v tom zmysle,
že tieto dve odpovede nie sú rovnaké.
Premýšľajte o tom, čo by sa stalo v prípad, ak to bolo už zoradené.
A premýšľať o tom, čo by sa stalo, keby to bolo
v prípade, v ktorom nebola zoradené.
A môžete trochu spustiť cez prečo sa to deje.
Dám ti chalani, ako, 30 sekúnd o tom premýšľať.
>> OK.
Má niekto uhádnuť, čo je Najhorší prípad runtime bublinkovej druhu je?
Jo.
>> Divákov: Bolo by to, ako, n krát n mínus 1, alebo niečo také?
Rovnako ako zakaždým, keď beží, je to len, ako, jeden menej odkladacia
že to, čo to bolo.
>> ANDI PENG: Jo, tak máš úplnú pravdu.
A to je prípad, kedy vaše Odpoveď bola v skutočnosti oveľa zložitejšie
než je tá, ktorú treba dať.
Takže to bude run-- Som chystá vymazať všetko tu.
Sú všetci dobre?
Môžem vymazať to?
OK.
Budete prejsť n Časy sa prvýkrát, že?
A idú prejsť n mínus 1 druhýkrát, je to tak?
A potom budete mať deje, n Mine 2, a tak ďalej.
David to urobil v prednáške, kde, Ak ste pridali všetky tieto hodnoty,
dostanete niečo, čo je jako-- yeah-- nad 2, ktorý v podstate len znižuje
až n na druhú.
Budeš sa dostať divný frakcie tam.
A tak len viem, že n na druhú vždy
má prednosť pred frakcie.
A tak v tomto prípade, najhoršie runtime by n druhú.
Ak by to bolo v zostupnom objednávka, myslieť si,
musieť urobiť swap zakaždým.
>> Aký by mal byť, potenciálne, najlepšom prípade runtime?
Povedzme, v prípade, že zoznam bol už v poriadku, čo by runtime byť?
>> Divákov: n.
ANDI PENG: Je to n, presne tak.
A prečo je to n?
Divákov: Pretože ste práve musieť skontrolovať každý raz.
ANDI PENG: Presne tak.
Takže v tom najlepšom možnom behu, Pokiaľ tento zoznam bol už
sorted-- povedzme 1, 2, 3, 4-- vy by len prejsť, mali by ste skontrolovať,
by ste vidieť, oh, všetci vyjsť.
Nemusel som sa vymeniť.
Skončil som.
Takže v tomto prípade, je to len n alebo počet krokov, ktoré práve
musel skontrolovať v prvom zozname.
>> A potom, čo sme teraz hit insertion sort, kde
algoritmus je v podstate rozdeliť to do triedeného aj netriedeného časť.
A potom jeden po druhom, netriedeného hodnoty
vložené do ich vhodnej pozície v začiatku zoznamu.
>> Tak napríklad, máme Zoznam 3, 5, 2, 6, 4 znova.
Vieme, že je to v súčasnej dobe netriedený preto, že sme jednoducho
začal na to pozerať.
Sme sa pozrieť, a my vieme, že Prvá hodnota je triedený, že jo?
Ak ste len pri pohľade na rad veľkosť jedného, ​​viete, že je to triediť.
>> Takže vieme, že ďalšie štyri sú netriedený.
Prechádzame a vidíme, že hodnoty.
Poďme späť.
Vidíte tú hodnotu 5?
Pozrieme sa na to.
My porovnať ju s 3.
Vieme, že to je väčšia než 3, takže vieme, že to je triediť.
Takže vieme, že prvé dva sú radené a posledné tri nie sú.
>> Sme sa pozrieť na 2.
Prvý sme skontrolovať s 5.
Je to menej ako 5?
To nie je.
Takže musíme hľadať ďalej nadol.
Potom môžete skontrolovať 2 VYP 3.
Je to menej ako?
Nie.
Takže viete, 2 musí byť vložená Na prednej a 3 a 5
obaja majú byť vytlačený.
Urobte to opäť s 6 a 4.
A my sme jednoducho udržať kontrolu v podstate, kde sme len skontrolovať, skontrolovať, skontrolovať.
A kým to je v práve postavenie, sme trochu proste
vložte ju do správnej polohy, čo je miesto, kde názov pochádza.
>> Tak to je len algoritmus, pseudokód per sa, druh,
o tom, ako by sme realizovať inzercia triedenia.
Pseudokód je tu.
Je to všetko online.
Žiadne starosti, či vy ste sa snaží kopírovať to dole.
Takže ešte raz, čo rovnaký question-- by bolo najlepšie a najhoršie runtime
vkladanie druhu?
Je to veľmi podobné na poslednú otázku.
Dám ti chalani, ako, 30 sekúnd premýšľať o tom rovnako.
>> OK Má niekto chcel daj mi najhoršie runtime?
Jo.
>> Divákov: n na druhú.
>> ANDI PENG: Je to n na druhú.
A prečo je to n na druhú?
>> Publikum: Pretože v obrátenom poradí, máte
prejsť n n časy, čo je--
ANDI PENG: Jo, presne tak.
Takže to isté ako v bubline druhu.
Pokiaľ tento zoznam je v zostupnom poradí, ty si
bude musieť skontrolovať prvý raz.
A potom sa s každým ďalšie hodnotu, že ste
musieť pozrieť sa na to proti každý hodnota, je to tak?
A tak úplne, budete robiť an časy n prihrávka ďalšie n pasu, ktorý
n je na druhú.
A čo najlepšom prípade?
Jo.
>> Divákov: n mínus 1, pretože Prvý z nich je už na druhú.
>> ANDI PENG: Tak blízko.
Odpoveď je vlastne n.
Vzhľadom k tomu, pričom prvý z nich je radené, nemusí to actually--
sme jednoducho kľučku, v že príklad, že 2
sa stalo, že je najmenší číslo.
Ale to nie je tak byť vždy.
V prípade 2 sa už zoradená na začiatku ale vyzeráš, a tam je 1 tu,
1 bude to rana.
A to skončí bytia odpichov tak ako tak.
>> Takže v najlepšom prípade, je to vlastne len bude n.
Ak máte 1, 2, 3, 4, 5, 6, 7, 8, ty si
sa prejsť že celý zoznam raz
skontrolovať, či je všetko v poriadku.
Je každý jasno v chode časy výberu rovnako?
Ja viem, že som prechádzal ty naozaj rýchlo.
Ale viem, že ak viete, všeobecné koncepty, mali by ste byť dobre.
OK.
Tak som si len dať chlapci možno, rovnako ako, minútu sa poraďte so svojím susedom
o tom, čo to sú len niektoré z hlavných rozdielov
medzi týmito typmi druhov.
Pôjdeme cez to skoro.
Publikum: Oh, OK.
ANDI PENG: Jo.
OK.
Cool, poďme znovu zídu ako trieda.
OK.
Takže to bolo celkom otvorená otázka v tom zmysle,
že je tu veľa odpovedí na ne.
A pôjdeme cez niektoré z nich stručne.
Chcel som, aby vám chlapci premýšľať o tom, čo diferencované
všetky tri typy druhov.
A ja som počul tiež, veľký question-- čo merge sort robiť?
Výborná otázka, pretože to je to, čo sme pokrývať ďalšie.
>> Tak zlúčiť sort človek druh, ktorý funguje
veľmi odlišne od ostatných druhov.
Ako vy môžete see-- David urobil, že demo
kde mal všetko v pohode zvuky keď vidí, ako zlúčiť
triedenie bežal, ako, nekonečne rýchlejšie, než ostatní dva typy?
OK.
Tak to je preto, že zlúčenie triediť implementuje, ktoré rozdeľujú
a podmaniť si predstavu, že sme hovoril o veľa v prednáške.
V tom zmysle, že sme chceli pracovať múdrejší, nie ťažšie, keď ste rozdeliť
a podmaniť si problémy, a rozdeľujú ich nadol, a potom dať dohromady,
dobré veci sa vždy stane.
>> Tak tak, že zlúčenie sort v podstate funguje
je, že sa rozdeľuje netriedené poľa na polovicu.
A potom to má dve polovice polí.
A to len triedi tieto dve polovice.
Je to jednoducho stále delenie na polovicu, v polovica, v polovici kým všetko je radený
a potom rekurzívne dáva to všetko dohromady.
>> Tak to je naozaj abstraktné.
Tak to je len trochu pseudokódu.
Znamená to, že zmysel v ako to beží?
Takže povedzme, že máte poľa n elementy, že jo?
Ak n je menší ako 2, môžete sa vrátiť.
Vzhľadom k tomu, viete, že či existuje len jedna vec, musí byť radené.
Else, radiť ľavú polovicu, a potom radiť pravú polovicu,
a potom zlúčiť.
>> Takže zatiaľ čo to vyzerá veľmi jednoduché, v skutočnosti, premýšľal o tom to
trochu ťažké. Vzhľadom k tomu, že ste rád, No, to je trochu beh na seba.
Je to tak?
Je to beh na seba.
Takže v tomto zmysle, David dotkol pri rekurziu v triede.
A to je pojem budeme hovoriť o viac.
Je to, že toto, tieto dve linky Tu, v skutočnosti je len program
hovoriť, aby sa spúšťal sám s rôznym vstupom.
Takže skôr ako bežať seba s celistvosť n elementy,
môžete zlomiť to do ľavú polovicu a pravá polovica
a spustite ho znova.
>> A potom sa pozrieme na to vizuálne, preto, že som vizuálny žiak.
Funguje to pre mňa lepšie.
Takže sa pozrieme na vizuálne príklad tu.
>> Povedzme, že máme celý rad, šesť prvky, 3, 5, 2, 6, 4, 1, sa netriedia.
Dobre, je tu veľa na tejto stránke.
Takže ak vy môžete pozrieť na Prvý krok sa tu, 3, 5, 2, 6, 4, 1,
môžete rozdeliť ho na polovicu.
Máte 3, 5, 2, 6, 4, 1.
Viete, že tieto aren't-- vás Neviem, či sú radené, alebo nie,
takže si udržať lámanie je dole, na polovicu, na polovicu, na polovicu, až nakoniec,
máte len jeden prvok.
A jeden prvok je vždy radené, že jo?
>> Takže vieme, že 3, 5, 2, 4, 6, 1 samy o sebe, sú zoradené.
A teraz môžeme dať ich dohromady.
Takže vieme, na 3, 5.
Dali sme dohromady tie.
Vieme, že je to triediť.
Na 2 je tam stále.
Môžeme dať 4 a 6 dohromady.
Vieme, že to je zoradená, tak sme dali, že spoločne.
A 1 je tam.
>> A potom sa stačí pozrieť sa na tieto dve polovice tu.
Máte 3, 5, 2, 2, 3, 5.
Len si môžete porovnať začiatok všetkého.
Vzhľadom k tomu, viete, že to je radený a viete, že to je triediť.
Takže vy nemusíte ani na porovnať 5, stačí porovnať 3.
A 2 je menšia ako 3, takže Viete 2 musí ísť na konci.
>> To isté tam.
1 musí ísť sem.
A potom, keď idete dať tieto dve hodnoty dohromady,
viete, že to je zoradená a viete, že je triedený.
Takže potom 1 a 2 je 1 je menšia ako 2.
To vám povie, že 1 by mal ísť na konci tohto
bez pri pohľade na 3 alebo 5.
A potom na 4, môžete len skontrolujte, že ide priamo tu.
Nemusíte sa pozrieť na 5.
To isté sa 6.
Viete, že to jednoducho 6-- nemusí byť díval.
>> A tak sa týmto spôsobom, ste len ukladanie sami
veľa krokov, keď ste porovnávanie.
Nemusíte porovnať každý prvok s inými prvkami.
Práve ste porovnať proti tým, že musíte porovnať ju proti.
Tak to je trochu abstraktný pojem.
Žiadne starosti, ak to nie je docela ťa biť ešte v poriadku.
Ale všeobecne, to je ako zlúčenie triedenie funguje.
Otázky, rýchlych otázok, Než som sa presunúť na?
Jo.
>> Divákov: Takže ste povedal, že ste užili polohách 1, a potom 4 a 6
a dať ich do.
Takže nie sú those-- nie sú Pozeráte sa na ne
ako samostatné prvky, nie ako celku?
ANDI PENG: Jo.
Takže to, čo sa deje je to, že ste v podstate
vytvárajú úplne nové pole.
Takže viete, že tu, mám dve polia o veľkosti 3, nie?
Takže viete, že môj triedeného array musí mať šesť prvkov.
Takže si stačí vytvoriť nová množstvo pamäte.
Takže ste niečo ako že plytvanie pamäti,
ale to nevadí, pretože je to tak malý.
Takže sa pozrieť na 1 a sa pozriete na 2.
A viete, že 1 je menšia ako 2.
Takže viete, že 1 by mal ísť do počiatok všetkých z nich.
>> Nemusíte ani potreba pozrite sa na 3 a 5.
Takže viete 1 je tam.
Potom ste v podstate odseknú na 1.
Je to, ako, mŕtvy k nám.
Potom sme proste 2, 3, 5, a potom sa 4 a 6.
A potom viete, že, vás porovnať 4 a 2,
Ach, tá 2 by malo ísť tam.
Takže ste PLOP na 2 dole, si nakrájame ho.
Takže stačí mať 3 a 5 v 4 a 6.
A vy ste len držať sekanie ho kým sa dať je v poli.
>> Divákov: Takže ste len vždy nákupný [nepočuteľných]?
>> ANDI PENG: Presne tak.
Takže v tomto zmysle, že ste len porovnanie, v podstate,
jedno číslo proti iné číslo.
A pretože viete, že to radené, vás
Nemusíte sa pozerať skrz všetky čísla.
Stačí sa len pozrieť na prvý z nich.
A potom sa môžete len PLOP je dole, pretože viete,
oni patrí tam, kam potrebujú patriť.
Jo.
Dobrá otázka.
>> A potom, ak niekto z vás sú trochu ambiciózny,
neváhajte sa pozrieť na tento kód.
To je vlastne fyzická realizácia
o tom, ako by sme napísať merge sort.
A môžete vidieť, že je to veľmi krátka.
Ale nápady za to sú celkom zložité.
Takže ak máte pocit, ako kreslenie na to vo svoje domáce úlohy dnes večer, neváhajte.
>> OK.
Tak aj Dávid prešiel toto v prednáške.
Aké sú najlepšie vec runtime, najhorší prípad runtimes,
a očakávané runtimes korešpondencia druhu?
Pár sekúnd premýšľať.
To je celkom ťažké, ale druh intuitívne, ak si myslíte o tom.
Dobre.
>> Divákov: Je najhorší prípad n log n?
ANDI PENG: Presne tak.
A prečo je to n log n.
>> Divákov: Nie je to preto, že sa stáva exponenciálne rýchlejší,
takže je to ako funkciu, ktorá nie len jednoducho byť n
na druhú, alebo tak niečo?
ANDI PENG: Presne tak.
Takže dôvod, prečo runtime v tejto oblasti je n log
n je protože-- to, čo ste robí vo všetkých týchto krokov?
Iba sekanie ho v polovici, že jo?
A tak, keď robíme log, všetko, čo to robí
rozdeľuje problém na polovicu, na polovicu, na polovicu, vo viacerých polovice.
A v tomto zmysle, môžete druh z eliminovať lineárny model
že sme používali.
Pretože keď si nakrájame veci v polovici, je to protokol.
To je len matematický spôsob, ako reprezentovať to.
>> A potom konečne, na konci, ste len aby jeden posledný priechod
dať všetky z nich v poriadku, nie?
A tak, keď stačí, aby skontrolovať jednu vec, to je n.
A tak ste trochu vynásobením dvaja spolu.
Takže je to ako, že máš, že konečné skontrolujte, či n tu s log n
tady.
A ak sa množiť je, že je n log n.
>> A tak to najlepšie a najhoršie prípad prípad, a očakáva, že sú všetci n log n.
Je to tiež ako iného druhu.
Je to ako výber druhu v tom zmysle, že
Nezáleží na tom, aké sú vaše Zoznam je, je to len bude
sa urobiť to isté zakaždým.
OK.
Tak ako vy môžete vidieť, aj keď že druhy, ktoré sme preč through-- n
štvorcový, to nie je moc efektívne.
A aj to n log n je nie je najúčinnejší.
Ak vy ste zvedaví, tam je radenie mechanizmy,
že sú tak účinné, že sú Takmer v podstate byt v behu.
>> Máte nejaký protokol n je.
Máte nejaké log log n je.
My nedotýkajte sa na ne v tejto triede práve teraz.
Ale ak vy ste zvedaví, neváhajte google, čo je
najvýkonnejšie triediace mechanizmy.
Ja neviem, existujú niektorí z nich naozaj na smiech,
jako-- tam je nejaké naozaj legrační tie, ktoré ľudia robia.
A vy ste vedel, ako by vôbec nenapadlo.
Takže google, ak máte trochu voľného čas, na to, čo sú niektoré vtipné spôsoby,
že people-- ako aj efektívna ways-- ľudia
boli schopní realizovať najrôznejšie.
OK.
A tu je len šikovný malý graf.
Viem, že vás všetkých, pred týmto kvízu 0, bude vo vašom izbe pravdepodobne snaží
zapamätať to.
Tak to je pekné tam pre vás.
Len nezabudnite na logiku, ktorá made-- prečo tieto čísla boli vyskytujúce.
Ak ste vždy prehral, ​​len aby istí, že viete, čo druhy sú.
A môžete prejsť je vo vašej mysli
prísť na to, prečo tí, Odpovede sú tieto odpovede.
>> Dobre.
Takže budeme pohybovať na, konečne, na vyhľadávanie.
Vzhľadom k tomu, ako tí z vás, ktorí po prečítaní pset,
Vyhľadávanie je tiež súčasťou tento týždeň problém sady.
Budete vyzvaní na implementáciu dva typy vyhľadávania.
Jedným z nich je lineárny vyhľadávanie a jeden je binárne vyhľadávanie.
>> Takže lineárne hľadanie je pomerne jednoduché.
Len chcete hľadať prvok zo zoznamu, či ste to.
Musíte len iterovat.
A keď sa rovná niečo, stačí vrátiť, nie?
Ale ten, ktorý sme najviac záujem hovoriť o
je binárne vyhľadávanie, vpravo, čo je rozdeľ a panuj mechanizmus, ktorý
David demonštroval v prednáške.
>> Spomeňte si na telefónny zoznam príklad že sa stále vychovávať,
ten, že sa druh snažil trochu na tento posledný rok,
kde rozdeliť problém na polovicu, na polovicu, na polovicu, znovu a znovu,
kým nenájdete to, čo hľadáte?
A vy ste dostal runtime of že rovnako.
A môžete vidieť, je to významne účinnejší
než akýkoľvek iný typ vyhľadávania.
>> Takže spôsob, akým by sme ísť o vykonávanie binárneho vyhľadávania
je, ak by sme mali poľa, index 0 až 6, sedem prvky,
sa môžeme pozrieť v stredu, right-- Ospravedlňujem sa, ak náš dotaz first--
ak chceme položiť otázku, robí polia obsahujú prvok 7,
Je zrejmé, že sú ľudia, a majúci taká malá pole, je to pre nás ľahké
povedať áno.
Ale spôsob realizovať binárny Hľadanie by sa pozrieť do stredu.
>> Vieme, že index 3 prostredný, pretože my
viem, je ich tam sedem prvky.
Aké 7 deleno 2?
Môžete stopnúť, ktoré navyše 1.
Máte 3 v stredu.
Tak je pole 3 rovná 7?
To nie je, že jo?
Ale môžeme urobiť pár kontrol.
Je pole 3 menšie ako 7, alebo je pole 3 väčšie ako 7?
>> A my vieme, že je to menej ako 7.
Takže vieme, že, oh, to musí nemusí byť v ľavej polovici.
Vieme, že to musí byť v pravej polovici, že jo?
Takže môžeme len stopnúť polovicu poľa.
Nemáme dokonca ani pozri sa na to ešte.
Pretože vieme, že polovica našej problem--
vieme, že odpoveď je v pravá polovica nášho problému.
Tak sme sa len pozrieť na to teraz.
>> Takže teraz sme sa pozrieť na Uprostred toho, čo zostalo.
To index 5.
Robíme rovnakú kontrolu znova a vidíme, že je to menšie.
Takže sa pozrieme na ľavej strane to.
A potom vidíme, ten šek.
Je hodnota poľa v index 4 rovná 7?
To je.
Takže sa môžeme vrátiť pravda, pretože sme zistili, že hodnotu v našom zozname.
Má tak, ako som išiel cez že zmysel pre všetkých?
OK.
Dám ti chlapci možno, rovnako ako, tri, štyri minúty prísť na to,
ako sa to v pseudokódu.
>> Tak si predstavte som vás požiadal, aby ste napísať Funkcia tzv search (), ktorý sa vrátil
hodnotu, logickú hodnotu, to bola pravda alebo false-- podobne,
true, ak ste našli hodnota, false, ak ste to neurobili.
A potom ste boli prešiel v hodnoty, ktorú
Hľadali do hodnôt, ktoré je array-- oh, rozhodne som dal
že na zlom mieste.
OK.
Tak ako tak, že by mal mať bolo na pravej strane hodnôt.
A potom int n je číslo prvkov v tomto poli.
Ako by ste ísť o snahe pseudokódu tento problém v?
Dám sa vám bude páčiť tri minúty na to.
Nie, myslím, že je only-- jo, je tu ešte jedna priamo tu.
Divákov: Môžem?
ANDI PENG: Jo, mám ťa.
Je to pracovné?
OK v pohode.
>> OK.
Tak jo chlapi, my sme bude udržať na uzde ho.
OK.
Takže predpokladáme, máme tento krásny malá polia s n hodnôt v ňom.
Nechcel som kresliť čiary.
Ale ako by sme ísť o snaží písať to?
Má niekto chcel daj mi prvý riadok?
Ak chcete mi dať Prvý riadok tohto pseudokódu.
>> Divákov: [Nepočuteľné]
Divákov: by ste chceli prechádzať through--
Divákov: Len ďalší pre sláčiky?
Divákov: --for.
>> ANDI PENG: Tak toto je trochu zložitejšie.
Myslíš, že about-- chcete sa udržujú v prevádzke tejto slučky
znova a znova, do kedy?
>> Divákov: Do [nepočuteľných] hodnota sa rovná tejto hodnote.
ANDI PENG: Presne tak.
Takže môžete vlastne len write-- môžeme ešte zjednodušiť ju viac.
Môžeme len robiť while, že jo?
Takže môžete mať len loop-- vieme, že je to za to.
Ale práve teraz, idem hovoriť "slučka" - tým, čo?
Loop until-- čo je náš ukončenie stavu?
Myslím, že som to počula.
Počul som, niekto to povedať.
>> Divákov: Hodnoty sa rovná stred.
ANDI PENG: Povedz to znova.
Publikum: Alebo, kým sa Hodnota, ktorú hľadáte
k je rovná strednej hodnote.
>> ANDI PENG: Čo keď to nie je tam?
Čo ak je hodnota hľadáte pre nie je vlastne v tomto poli?
Divákov: Vrátite 1.
>> ANDI PENG: Ale to, čo chceme slučky, až keď máme stav?
Jo.
>> Divákov: Kým je tu len jedna hodnota?
ANDI PENG: Môžete slučka until-- takže viete, že ste
bude mať maximálnu hodnotu, je to tak?
A viete, že budete mať hodnotu min, že jo?
Vzhľadom k tomu tiež, to je niečo, Zabudol som povedať predtým,
že niečo, čo je kriticky binárne vyhľadávanie
je, že vaše pole už je zoradený.
Pretože neexistuje žiadny spôsob, ako robiť , Ak sú to len náhodné hodnoty.
Neviete, ak je to väčšie ako ostatné, nie?
>> Takže viete, že vaše maximálne a Vaše min tu, nie?
Pokiaľ bude nastavenie Váš max vo vašich minút a mid--
nech to len predpokladať stredná hodnota je správne here--
budete v podstate slučka kým je minimum
zhruba rovnaký ako max, vpravo, alebo ak vaše maximálna nie je rovnaký ako min.
Je to tak?
Vzhľadom k tomu, keď sa to stane, viete, že že ste nakoniec narazila na rovnakú hodnotu.
Takže chcete, aby slučke, kým vašej min je menší alebo rovný to-- oops,
nie menej ako alebo rovné, na druhú stranu around-- Max.
>> Vedeli, že zmysel?
Vzal som niekoľko pokusov dostať toto právo.
Ale slučka, kým vaše maximálne hodnoty je v podstate takmer nižšej
než alebo rovná vašej minimum, že jo?
To je, keď viete, že ste sa zblížil.
Divákov: Ak by vaše maximálne hodnota bola nižšia, než je minimum?
ANDI PENG: Ak sa budete držať prispôsobí, čo
je to, čo sa chystáme je potrebné robiť v tomto.
Dáva to zmysel?
Minimálna a max sú len celé čísla, že sme pravdepodobne
bude chcieť vytvoriť, aby trať, kde sa pozeráme.
Vzhľadom k tomu, pole existuje bez ohľadu na to, čo robíme.
Rovnako ako, nie sme v skutočnosti fyzicky sekanie mimo poľa, nie?
Sme len nastavenie kde sa pozeráme.
Dáva to zmysel?
>> Divákov: Jo.
>> ANDI PENG: OK.
Takže ak to je podmienka pre naše slučku, to, čo chceme v tejto slučky?
Čo budeme sa chcieť robiť?
Takže teraz, máme max a min, pravý,
pravdepodobne vytvoril tu niekde.
Budeme chcieť nájsť strednú, že jo?
Ako sme bude schopný nájsť uprostred?
Čo je mathematical--
Divákov: Max a min deleným 2.
ANDI PENG: Presne tak.
Dáva to zmysel?
A to vy, prečo by sme nebol len use--, prečo sme to urobili
namiesto toho robí len n deleno 2?
Je to preto, že n je hodnota že to bude zostať rovnaké.
Je to tak?
Ale ako sme prispôsobiť našu minimum a maximálnej hodnoty, sa chystajú zmeniť.
A ako výsledok, naše middle bude príliš meniť.
Takže to je dôvod, prečo chceme, to urobiť tu.
OK.
>> A potom, že teraz sme našli our-- jo.
>> Divákov: Len rýchly question-- keď hovoríte, min a max,
sme za predpokladu, že to už je zoradený?
>> ANDI PENG: Jo, to je vlastne Predpokladom pre binárne vyhľadávanie,
že musíte vedieť, že to triediť.
Čo je dôvod, prečo triediť, píšete vo vašom problém nastaviť pred binárneho vyhľadávania.
OK.
Takže teraz, keď vieme, kde naša stred je, čo chceš robiť?
>> Divákov: Chceme porovnať že do druhej.
ANDI PENG: Presne tak.
Takže budete porovnávať strednej hodnote, že jo?
A čo to povedať nás, keď sme porovnať?
Čo chceme robiť potom?
>> Divákov: Ak je hodnota väčšia ako polovice, chceme znížiť ju.
ANDI PENG: Presne tak.
Takže ak je táto hodnota väčšia než polovici, my sme
bude chcieť zmeniť tieto minimálne a maxes, že jo?
Čo chceme zmeniť?
Takže ak vieme, že hodnota je niekde tu to, čo robiť, tí, zmeniť?
Chceme zmeniť naše Minimálna byť stredná, že jo?
A potom ešte, ak je to v tomto polovica, čo chceme zmeniť?
>> Divákov: Vaše maximálne.
ANDI PENG: Jo.
A potom ste len tak aby looping, že jo?
Pretože teraz, po jednom prechode vďaka, máte max sem.
A potom môžete prepočítať v polovici.
A potom si môžete porovnať.
A budete ďalej kým min a maxes
majú v podstate konvergovanej.
A to je, keď viete, že že ste narazila na koniec.
A to buď ste ho našli alebo nemáte v tomto bode.
>> Má to zmysel, aby všetky?
OK.
To je docela dôležité, pretože budete mať
písať to v kóde večer.
Ale vy máte celkom dobrý zmysel pre to, čo by ste mali robiť,
čo je dobré.
OK.
Takže máme asi sedem minút ľavej časti.
Takže budeme hovoriť o tento pset, že budeme robiť.
Takže pset je rozdelená na dve polovice.
Prvá polovica sa týka vykonávanie find
v ktorom píšete lineárny hľadania, je binárne vyhľadávanie a triedenie algoritmus.
>> Tak toto je prvý tentoraz v pset kde
budeme dávať vám chlapci, čo sa nazýva Distribúcia kód, čo je kód
že sme pre-písaný, ale práve opustil niekoľko kúskov off
pre vás až do konca písania.
Takže vás chlapci, keď sa pozriete na to kód, by ste mohli dostať naozaj strach.
Ak ste rovnako ako ja, ach, Neviem, čo to robí,
Ja neviem, rovnako ako, že sa zdá tak zložité, ehm, relaxovať.
Je to v poriadku.
Prečítajte si špec.
Spec vám vysvetlí presne Čo všetky tieto programy robia.
>> Napríklad, generate.c je program že príde s pset.
Nemusíte skutočne sa ho dotknúť, ale mali by ste pochopiť, čo to robí.
A generate.c, všetko, čo robí, je buď generovanie náhodných čísel
alebo si môžete dať semeno, ako keď vopred dohodnuté číslo, ktoré je potrebné,
a to generuje viac čísel.
Takže tam je špecifický spôsob, ako implementovať generate.c v ktorom
stačí urobiť veľa čísel pre vás otestovať svoje iné metódy na.
>> Takže ak by ste chceli, pre Príkladom, otestujte nález,
budete chcieť spustiť generate.c, generujú veľa čísel,
a potom spustiť funkciu pomocníkov.
Váš pomocníci funkcia je miesto, kde ste vlastne fyzicky písania kódu.
A myslieť pomocníkov ako súbor knižnice píšete, že nález volá.
A tak sa v rámci helpers.c, budete robiť vyhľadávanie a radenie.
>> A potom budete v podstate stačí dať ich všetky dohromady.
Spec vám poradí, ako sa dať, že na príkazovom riadku.
A budete môcť vyskúšať, či nie je váš triediť a hľadať pracujú.
Super.
Má už niekto začal a stretávalo s problémami alebo otázky
majú práve teraz s tým?
OK.
>> Divákov: Počkajte.
Mám otázku.
>> ANDI PENG: Jo.
>> Divákov: Tak som začal robiť lineárne hľadanie v helpers.c
a to nebolo naozaj funguje.
Ale neskôr som zistil, že sme práve musíš ju zmazať a urobiť binárne vyhľadávanie.
Takže to je jedno, či to nebude fungovať?
>> ANDI PENG: Krátka odpoveď znie nie.
Ale pretože sme ne--
Divákov: Ale nikto v skutočnosti kontrola.
ANDI PENG: Sme Nikdy ide vidieť, že.
Ale pravdepodobne budete chcieť, aby sa istí, že vaše hľadanie funguje.
Pretože ak vaše lineárne Hľadanie nefunguje,
potom je šanca sú vaše binárne vyhľadávanie nebude fungovať rovnako.
Pretože máte podobnú Logika v oboch z nich.
A nie, to naozaj nezáleží.
Takže len tie, ktoré budete zase v sú triediť a binárne vyhľadávanie.
Jo.
>> A tiež, veľa detí bolo snaží sa zostaviť helpers.c.
Nie ste vlastne dovolené to urobiť, pretože helpers.c
nemá hlavnú funkciu.
A tak by ste mali iba byť v skutočnosti kompilácie
vytvorenie a nájsť, pretože nájsť hovory helpers.c a funkcie v nej.
Takže to robí ladenie ako osina v zadku.
Ale to je to, čo musíme urobiť.
Divákov: Len Urobíte všetko, že jo?
ANDI PENG: stačí robiť všetko rovnako, jo.
OK.
Tak to je, pokiaľ ide o to, čo pset žiada, aby ste všetci robiť.
Ak máte akékoľvek otázky, pocit zadarmo a opýtajte sa ma po bode.
Budem tu, rovnako ako, 20 minút.
>> A áno, je to pset naozaj nie je tak zlé.
Mali by ste byť v poriadku.
Tie, len riadiť sa pokynmi.
Druh majú pocit, logicky, čo Deje sa to, a budete v pohode.
Nebuďte príliš veľký strach.
Je tu veľa kódu už písali tu.
Nebuďte príliš veľký strach, ak nemáte pochopiť, čo to všetko znamená.
Ak je to veľa, je to úplne v poriadku.
A prišiel úradné hodiny.
Pomôžeme vám sa pozrieť.
>> Divákov: S extra funkcie, sa pozrieme na tie?
>> ANDI PENG: Jo, tie, ktoré sú v kóde.
V hre 15 polovica je to už napísal pre teba.
Takže tieto funkcie sú už v kóde.
Jo.
Dobre.
No, veľa šťastia.
Je to nechutné deň.
Takže dúfajme, že vy sa necíti príliš zlé na tom, zostať vnútri a kódovanie.