>> [Zenelejátszási]
>> ANDI Peng: Üdvözöljük héten 3 szakasz.
Köszi, srácok, minden jön hogy ez a korábbi kezdési időpont ma.
Van egy szép, kis intim csoport ma.
Így remélhetőleg sikerülni fog befejezni, talán korai,
Egy kicsit korai még ma.
Olyan gyorsan, csak néhány bejelentések a napirenden ma.
Mielőtt belevágnánk, mi vagyunk fog csak megy át
néhány rövid logisztikai kérdések, PSET kérdésekre, kikérdez, ilyesmi.
És akkor majd zuhanásra.
Majd egy nyomkövető nevű GDB kezdeni leleplezése a kódot, amely David
kifejtette előadást a minap.
Átnézzük a négyféle fajta.
Átnézzük őket elég gyorsan hiszen ők elég intenzív.
De tudom, hogy minden diák és forráskód mindig online.
Szóval nyugodtan, a átolvasás, hogy menj vissza, és nézd meg ezt.
>> Elmegyünk keresztül aszimptotikus jelölés, amely
csak egy divatos módon mondván, hogy "runtimes"
ahol már a nagy O, amelyek David kifejtette előadásában.
És mi is az Omega, amely az alsó határ idejét.
És fogunk beszélni egy kicsit mélyreható vonatkozóan, hogyan ezek a munkák.
És végül, megyünk át a bináris keresés, mert sok van, akik már
pillantott meg psets valószínűleg tudja, hogy ezt a kérdést, hogy ez a PSET.
Szóval akkor minden boldog hogy fedezze ezt ma.
>> És végül, egy a szakaszban visszajelzést, én valóban
bal körülbelül 15 percen át A végén, hogy csak megy át
logisztikai pset3, bármilyen kérdése, talán egy kicsit útmutatást, ha úgy tetszik,
mielőtt elkezdjük a programozást.
Úgyhogy próbáljuk átvészelni az anyag elég gyorsan.
És akkor mi is eltölteni egy kis időt figyelembe több kérdés az PSET.
OKÉ.
>> Gyorsan, így csak néhány bejelentések, mielőtt elkezdjük a mai napon.
Először is, szívesen teszi keresztül két a psets.
Vettem egy pillantást your-- igen, mielőtt kap egy tapsot, hogy az egyik.
Igazából, én nagyon, nagyon lenyűgözött.
Én osztályozzák az első PSET srácok a múlt héten, és a srácok tette hihetetlen.
>> Stílus volt pont mellett néhány megjegyzést.
Győződjön meg róla, hogy mindig kommentálva a kódot.
De a psets voltak a kérdésben.
És csak így tovább.
És ez jó a gréder, hogy láthatjuk, hogy a srácok üzembe
annyi erőfeszítést az Ön stílusát és a design a kódban
az, hogy szeretnénk, hogy lásd.
Úgyhogy halad végig hálámat a többi TAS.
>> Azonban van egy Néhány kikérdez kérdések
Csak azt akarom, hogy menjen át, hogy tenné mind az életem
és egy csomó más TA "él egy kicsit könnyebb.
Először is, azt vettem észre ezt már week-- hányan
már fut a check50 A kód elküldése előtt?
OKÉ.
Tehát mindenkinek meg kell csinálni check50, because-- egy secret-- valójában
fuss check50 részeként a korrektség szkriptek tesztelésére a kódot.
Tehát, ha a kód hiányában check50, minden valószínűség szerint,
ez valószínűleg a nem a check is.
Néha srácok a helyes válaszokat.
Mint, a kapzsi, néhány Önnek joga van a számok,
Ön csak nyomtassa ki valami extra.
És, hogy extra dolgokat valójában nem az ellenőrzés,
mert a számítógép nem Tényleg tudom mi a keres.
És ez így lesz, csak végigmenni, látni, hogy a kimenet nem
egyezik azzal, amit várunk a válasz lenni, és jelölje meg a baj.
>> És tudom, hogy történt, néhány esetben ezen a héten.
Így mentem vissza, és manuálisan újraosztályozva mindenki kódot.
A jövőben, bár, Kérjük, győződjön meg róla,
hogy futsz ellenőrizze 50 a kódot.
Mert ez egyfajta fájdalom a TA hogy vissza kell mennie, és manuálisan újraosztályozásról
minden egyes PSET minden Egyetlen, kicsit hiányzott például.
Szóval nem vette le a pontokat.
Azt hiszem, levette talán egy vagy két a tervezés.
A jövőben, bár, ha te ennek hiányában check50,
pont kerül sor off helyességét.
>> Továbbá psets is miatt pénteken délben.
Azt hiszem, van egy hét perces késői türelmi idő, amit kapsz.
Per Harvard időben, ők hagyjuk hét perc végén mindent.
Tehát itt a Yale-en, akkor tartsák be azt is.
De nagyon sok, a 00:07, ha a PSET nincs,
ez meg fog jelölni, mint későn.
És így amíg az jelölve a végén, a TA-- vagyok
még mindig lesz osztályozás a psets.
Szóval továbbra is lát egy fokozat jelenik meg.
Ugyanakkor tudjuk, hogy a A végén a félév,
minden késedelmes psets csak úgy lesz automatikusan nullázódik a számítógép.
>> Tesszük ezt két okból.
Az egyik, néha megkapjuk elnézést, mint a dékáni kifogásokat,
később, hogy nem tud még.
Tehát szeretném győződjön meg arról, mi a besorolási mindent csak abban az esetben, mint én vagyok
Hiányzik egy dékáni kifogás.
És másodszor, tartsa szem előtt, akkor is
egy csepp PSET, hogy van teljes körű pont.
És így szeretünk évfolyam az összes psets csak
meggyőződni arról, hogy a szonda és ott próbál nekik.
Így még ha késő van, akkor még mindig kap hitelt hatálya pontot, azt hiszem.
>> Szóval a történet tanulsága az, hogy Ellenőrizze, hogy a psets vannak az időben.
És ha azok nem az időben, tudom, hogy ez nem jó.
Ja, mielőtt lépni, nem akárki volna bármilyen kérdése PSET visszajelzést?
Igen.
>> Közönség: Azt mondtad, mi csepp az egyik psets?
>> ANDI Peng: Igen.
Szóval van kilenc psets összességében során a félév.
És ha van elegendő mozgástér points-- így hatálya csak,
nagyon sok, te próbál a probléma, te üzembe időben,
mutatod, hogy már bizonyította, hogy elolvasta a spec.
Ez elég sok hatálya alá.
És ha teljesítik hatálya pontot, akkor
csökkenhet a legalacsonyabb egyet a teljes körű.
Szóval ez az Ön előnye, hogy töltse ki és próbálja minden PSET.
>> Még upload-- ha egyik őket dolgozni, töltse fel őket.
És akkor majd remélhetőleg képesek kapsz néhány ilyen pont vissza.
Hűvös.
Más kérdés?
Nagy.
>> Másodszor, irodai hours-- pár gyors jegyzeteket munkaidőben.
Tehát először jött a hét elején.
Senki sem eddiginél munkaidőn hétfőn.
Christabel jött munkaidőn tegnap este.
Ja, Christabel.
És mit van az irodában órán múlt éjjel, Christabel?
>> Közönség: Mi volt a fagylalt.
>> ANDI Peng: Szóval ez így van, mi volt jégkrémet munkaidőn tegnap este.
Míg nem ígérhetem, hogy mi lesz fagylaltot munkaidőn
Minden héten, amit én is ígérem az, hogy lesz egy jelentősen
jobb tanuló TA arányt.
Mint legális, ez olyan, mint 3-1.
Mivel ezzel ellentétben, Csütörtök, megvan mintegy 150
Tényleg hangsúlyozta a gyerekek, és nem fagylaltot.
És ez csak nem produktív bárki.
Szóval a történet tanulsága van, korán jött a munkaidőn és a jó dolgokat
meg fog történni.
>> Szintén érdemes felkészülni, hogy kérdéseket tegyenek fel.
Tudod?
Függetlenül attól, amit Tas én gondolom, már azt mondja,
mi már kezd egy pár diákok akik jönnek csütörtökön, mint, 10:50
mivel nem olvassa a specifikációt hogy olyan lesz mint nekem segíteni, segítsen nekem.
Sajnos ezen a ponton, van Nem sokat tehetünk, hogy segítsen.
Ezért kérjük, jöjjön a hét elején.
Gyere már, hogy hivatali időben.
Gyere elkészített kérdéseket feltenni.
Győződjön meg arról, hogy Ön, mint egy diák, van, ahol
meg kell, hogy legyen, hogy a TA is elvezeti Önt mentén,
ami pedig munkaidőn ki kell kiosztani.
>> Másodszor, így tudom, hogy a professzorok szeretném meglepni minket tesztek.
Volt egy tanár azoknak mint, yo, az úton,
ne feledjük, hogy középtávú Van jövő hétfőn.
Ja, nem tudtam róla középtávú.
Így fogok lenni, hogy a TA emlékezteti, minden kvíz
0--, mert tudod, mi vagyunk CS.
Most, hogy megtettem tömbök, kapsz miért kvíz 0, nem Quiz 1, he?
OKÉ.
Ó, kaptam néhány kuncog hogy az egyik.
OKÉ.
>> Tehát kvíz 0 lesz, október 14 ha te vagy a hétfő-szerda részén
és október 15. ha a A kedd-csütörtök részt.
Ez nem vonatkozik az Azoknak, a Harvard
who-- azt hiszem, mindannyian figyelembe vetélkedők 14-én.
>> Szóval igen, a jövő héten, ha David, az előadás, megy,
Igen, arról, hogy kvíz jövő héten, akkor az összes
nem lesz döbbenve, mert azért jött, hogy a rész
és tudod, hogy a kvíz 0 jelentése két hét alatt.
És mi lesz felülvizsgálata ülések és mindent.
Így nem aggódik félek, hogy.
Bármilyen kérdése before-- bármilyen kérdése Egyáltalán kapcsolatos logisztikai kérdések,
osztályozás, munkaidejében szakaszok?
Igen.
>> Közönség: Tehát a teszt lesz ideje alatt előadást?
>> ANDI Peng: Igen.
Tehát a kvíz, azt hiszem, 60 perc allokált, hogy időréshez
hogy akkor csak vegye a teremben.
Szóval nem kell bejönni a, mondjuk, egy véletlen 07:00.
Minden rendben van.
Igen.
Hűvös.
>> Minden rendben.
Szóval megyünk bevezetni a koncepciót az Ön számára
ezen a héten, hogy Dávid már egyfajta A érintettünk előadást a múlt héten.
Úgy hívják GDB.
És hányan, míg írása közben a psets,
észrevették a nagy gombot, hogy azt mondja, "Debug" a tetején az IDE?
OKÉ.
Szóval most mi lesz valójában kap, hogy felfedez A rejtély, hogy mi az a gomb tényleg
csinál.
És én garantálom, hogy ez egy szép, szép dolog.
>> Szóval eddig, azt hiszem, van már két dolog
diákok már jellemzően csinálsz, amikor hibakeresés psets.
Az egyik, hogy vagy hozzá printf () - így minden pár sort,
Hozzáteszik egy printf () - Ó, mi ez a változó?
Ó, mi ez a változó now-- és akkor milyen láthatjuk a fejlődést
a kód futása közben.
Vagy a második módszer a gyerekek tennie, hogy csak írni az egészet
és aztán megy, mint ez a végén.
Remélhetőleg ez működik.
Garantálom neked, GDB jobb mint e két módszer.
Igen.
Szóval ez lesz az új legjobb barátja.
Mert ez egy szép dolog amely vizuálisan megjeleníti mind
mi a kód csinál egy meghatározott ponthoz
valamint mi az összes változók könyv,
mint hogy milyen értékeket vallanak, ezen a bizonyos pontot.
És így, akkor tényleg töréspont a kódban.
Akkor végigmenni sorról sorra.
És GDB csak meg a te, meg az Ön számára,
mi az összes változót vannak, mit csinálnak,
mi folyik a kódot.
És oly módon, hogy ez így sokkal könnyebb látni
mi történik helyett printf-nek vagy leírom a kimutatásokban.
>> Tehát mi nem egy példa erre később.
Szóval ez úgy tűnik, egy kicsit elvont.
Semmi gond, mi intézzük példákat.
És így lényegében a három legnagyobb, A leggyakrabban használt funkciókat, amelyekre szüksége lehet GDB
Melyek a következő, átlépni, és belép a gombok.
Megyek feje fölött ott, igazából most.
>> Szóval lehet, srácok mindannyian látni, hogy vagy kell nagyítani egy kicsit?
A hátsó, látod ezt?
Kell nagyítás?
Csak egy kicsit?
OK, hűvös.
Ott vagyunk.
OKÉ.
>> Szóval van itt, én végrehajtás kapzsi.
És bár sok srácok írt kapzsi while ciklus form--, hogy
egy tökéletesen elfogadható módja it-- másik módja az, hogy az, hogy egyszerűen
osztja a modulo.
Mert akkor lehet a értéket, és ezt követően a maradékot.
És akkor csak add össze az egészet.
Vajon a logikája, hogy mit csinálok Itt értelme mindenkinek,
mielőtt elkezdjük?
Fajta?
Hűvös.
Nagy.
Ez egy nagyon szexi darab kód, azt mondanám.
Mint mondtam, David, a előadás, egy idő után,
akkor minden újra látni kódot mint valamit, ami szép.
És néha, ha látni szép kód, ez egy ilyen csodálatos érzés.
>> Így azonban, miközben ez a kód nagyon szép, hogy nem működik megfelelően.
Szóval futni check50 ezen.
Ellenőrizze 50 20-- OOP.
2?
Ez pset2?
Igen.
Ó, pset1.
OKÉ.
Szóval mi fut check50.
>> És ahogy ti is láthatja, ez ennek hiányában egy-két esetben.
És néhányan közületek, a Természetesen csinál a problémát készletek,
Ön, mint, ah, miért nem működik.
Miért van az, dolgozik egy értékeket, de nem mások?
Nos, a GDB fog, hogy segítsen kitalálni hogy miért ezeket a ráfordításokat nem működik.
>> OKÉ.
Tehát lássuk, az egyik ellenőrzéseket voltam ennek hiányában a check50
volt a bemeneti értéke 0,41.
Tehát a helyes válasz, hogy akkor kapok egy 4.
De ahelyett, amit én kinyomtatásával a 3-n, ami helytelen.
Úgyhogy csak fuss kézzel is, csak győződjön meg arról, hogy check50 dolgozik.
Csináljuk ./greedy.
Hoppá, azt kell, hogy kapzsi.
Ott vagyunk.
Most ./greedy.
>> Mennyibe kerül tartozott?
Csináljuk 0.41.
És igen, azt látjuk itt hogy ez kimenetre 3
ha a helyes választ, sőt, kell 4.
Úgyhogy adja GDB, és nézzük meg mehet a rögzítés ez a probléma.
>> Tehát az első lépés a Mindig hibakeresés a kódot
az, hogy hozzanak egy töréspont, vagy az a pont, ahol
szeretné, hogy a számítógép vagy a debugger kezdeni a.
Tehát, ha nem igazán tudom, mi a probléma,
Általában, a tipikus dolog, amit szeretnénk tennie, hogy állítsa meg töréspont a fő.
Tehát, ha ti is látni ezt piros gombot ott,
Ja, én voltam beállításával típuspontjának a fő funkciója.
Rákattintok, hogy.
>> És akkor mehet akár én Debug gombra.
Elütöttem a gombot.
Hadd kicsinyítéshez ha tudok.
Ott vagyunk.
Tehát van itt, a panel jobb oldalán.
Sajnálom, srácok, a hátsó, akkor Nem igazán lehet látni igazán jól.
De lényegében minden, ez a jobb oldali panelen csinál
figyelemmel kísérése, mind a kiemelt vonal, amely a sorban a kód
hogy a számítógép jelenleg futó, valamint az összes változó
itt lenn.
>> Szóval megvan cent, érme, n, minden bejelentett különböző dolgokra
ezen a ponton.
Nem kell aggódni, mert van valójában nem inicializálni őket, hogy minden változó tartalom.
Így a számítógép, a számítógép csak látta,
ó, 32767 volt az utoljára használt funkció Az, hogy tárhely a gépemen.
És ez az, ahol cent jelenleg.
De nem, hogy ha egyszer futtatja a kódot, kell válnia inicializált.
>> Szóval menjünk át, sorról vonal, mi folyik itt.
OKÉ.
Tehát itt van a három gombok, hogy én csak magyarázta.
Megvan a játék, vagy a Run funkció, gombot, akkor a lépés több mint gombot,
és akkor is a lépés a gombot.
, És lényegében, mind a három ezek csak menj át a kódot
és különböző dolgokat.
>> Így általában, ha éppen a hibakeresés, mi nem akarjuk, hogy csak hit játék,
mert Play csak fuss A kód a végét.
És akkor valójában nem tudom, mi a bajod
van, hacsak nem állítod, több töréspont.
Ha több töréspont, akkor csak automatikusan
futnak egyik töréspont, A következő, a következő.
De ebben az esetben mi már Csak, hogy az egyik, mert
akar dolgozni az utat fentről lefelé lefelé.
Mi is így fogjuk figyelmen kívül hagyni azt a gombot most a célra a program.
>> Tehát a lépés több mint funkció csak lépések alatt minden egyvonalas
és megmondja, hogy mi A futó programok.
A lépés a funkció megy a tényleges funkciója
ez a sor kódot.
Így például, mint a printf (), hogy egy olyan funkció, ugye?
Ha akartam fizikailag lépést a printf () függvény,
Én valóban bemegy a darab kód ahol a printf () írta és látni
mi folyik ott.
>> De általában azt feltételezzük, hogy A kód, amit kapsz működik.
Feltételezzük, hogy a printf () dolgozik.
Azt feltételezzük, hogy GetInt () dolgozik.
Tehát nincs szükség belép ezeket a funkciókat.
De ha van funkciók saját maga által írt
hogy az ellenőrizni kívánt hogy mi folyik itt,
amit szeretne lépni be ezt a tisztséget.
>> Akkor most mi csak megy átlépni ezt a kódrészletet.
Tehát lássuk.
Ó, nyomtatás, "Ó hai, hogyan sok változás áll fenn? "
Nem érdekel minket.
Tudjuk, hogy ez működik, így átlépni azt.
>> Tehát n, ami a mi úszó, hogy mi már initialized-- vagy declared--
akár a tetején, mi most egyenlő, hogy a GetFloat ().
Úgyhogy átlépni ezt.
És látjuk a alsó itt, a program
arra ösztönöz, hogy adjon meg egy értéket.
Úgyhogy bemeneti értéket akarunk kipróbálni itt, ami 0,41.
Nagy.
>> Tehát most n-- srácok lásd Itt, a bottom-- ez
stored-- mert Nem kerek mégis, ez
alatt az, mint a hatalmas úszó, amely 0,4099999996,
ami elég közel van a célokra, most, hogy 0,41.
És aztán majd meglátjuk később, mint mi tovább átlépve a program,
után itt, n vált lekerekített és cent lett 41.
Nagy.
Tehát tudjuk, hogy mi a kerekítés dolgozik.
Tudjuk, hogy mi van a megfelelő számú cent,
így tudjuk, hogy ez nem igazán a probléma.
>> Tehát továbbra is lépve tovább ebben a programban.
Mi megy itt.
És így, miután ezt a kódsort, mi tudnia kell, hogy hány negyedévben már.
Mi átlépni.
És látod mi, sőt, egy negyedévben mert már levontuk 25
a mi kezdeti értéke 41.
És mi van a 16 bal a mi cent.
>> Mindenki érti, hogyan A program átlépve
és miért cent mára 16 és miért most, érmék vált 1?
Mindenki követő logika?
Hűvös.
Tehát ahogy ezen a ponton, a programban dolgozik, ugye?
Tudjuk, hogy csinál pontosan mi akarjuk.
És valójában nem kell kinyomtatni, jaj, mit
van cent ezen a ponton, mi érméket ezen a ponton.
>> Továbbra is folyik a programon keresztül.
Átlép.
Hűvös.
Mi megy át Dimes.
Nagy.
Látjuk, hogy ez hozott off 0,10 $ egy fillért sem.
És most van két érmét.
Így van.
>> Mi megy át fillérekért, és azt látjuk, hogy megvan maradt cent.
Hmm, ez furcsa.
Akár itt a programot, azt kellett volna hogy levonjuk én fillérekért.
Talán csak nem voltam csinálja vonal jobb.
És sajnos, láthatjuk Itt, mert tudjuk,
hogy fokozzák vonalakon keresztül 32 és 33,
ez az, ahol a programunk helytelenül volt változók futni.
Így meg tudjuk nézni és látni, ó, Én kivonva cent itt,
de nem vagyok ténylegesen hozzátéve, hogy az én érme értékét.
Én vagyok hozzá, hogy cent.
És nem akarom felvenni cent, szeretném hozzátenni, hogy érméket.
Tehát, ha változtatni kell, érmék, mi van egy munkaprogramot.
Tudok futni check50.
Tudod csak lépjen ki a GDB jobb Itt majd futtassa check50 újra.
Én is csak ezt.
Azt kell, hogy kapzsi.
0.41.
És itt, ez a nyomtatás ki a helyes választ.
>> Tehát ahogy ti is látni, GDB egy igazán hatékony eszköz
amikor már annyira kód folyik, és annyi változó
hogy nehéz számunkra, mint egy ember, hogy nyomon követni.
A számítógép, a GDB debugger, amely képes
nyomon követni mindent.
Tudom, a Visionaire, srácok valószínűleg Lehet, hogy a hit néhány szegmentációs hiba
mert futottak a határokat a tömb.
A példában Caesar, ez Pontosan azt, amit idehaza.
>> Így elfelejtettem, hogy ellenőrizze a mi lenne, ha én
nem volt két parancssori paramétereket.
Csak nem ebbe az ellenőrzést.
És így ha futok Debug-- állítottam én töréspontot ott.
Futok Debug.
>> OKÉ.
Igen.
Tehát tulajdonképpen, GDB kellett volna hogy azt mondta nekem, hogy
volt szegmentációs hiba van.
Nem tudom, mi folyik ott, de amikor futott,
ez működött.
Amikor futtatja sornyi kódot keresztül, és GDB talán csak hirtelen kilép rád,
felmegy, és megnézzük, mi a piros hiba.
Ez megmondom, hé, te Volt egy szegmentációs hiba,
ami azt jelenti, hogy a megnyitni kívánt térben egy tömbben, hogy nem létezik.
Igen.
>> Tehát a következő probléma beállítani ezen a héten, srácok
Valószínűleg sok változók lebeg.
Ugye nem lesz biztos benne, mi jelentenek ezek egy bizonyos ponton.
Tehát GDB valóban segít kitalálni hogy mi mindannyian egyenlő
és hogy képes látni, hogy vizuálisan.
Ha valaki világos, hogy mi sem, hogy dolgozik?
Hűvös.
Minden rendben.
Így azután, hogy vagyunk fog merülni jobbra
figyelembe négy különböző típusú fajta erre a hétre.
Hányan vagytok, első Az összes, mielőtt elkezdjük,
Elolvastam a teljes specifikáció pset3?
OKÉ.
Büszke vagyok a srácok.
Ez olyan, mintha a fele az osztályban, ami lényegesen több, mint a múltkor.
>> Szóval ez jó, mert amikor beszélünk a tartalmat
A lecture-- vagy sajnálom, A section-- szeretem
kapcsolódnak egy csomó, hogy vissza, amit a PSET van
és hogyan szeretné végre, hogy a PSET.
Tehát, ha jön, amelynek olvassa a specifikációt, akkor az
sokkal könnyebb az Ön számára, hogy megértsék mit beszélek, amikor azt mondom,
ó hé, ez lehet egy igazán jó hely, hogy végre ez a fajta.
Tehát azok, akik elolvasták a spec tudom, hogy részeként a PSET,
fogsz kell levelet típusú sort.
Tehát ez lehet nagyon hasznos Egy csomó van ma.
>> Szóval majd elindul, Lényegében, a legegyszerűbb típus
A sort, a kiválasztási sorrend.
A tipikus algoritmus hogyan megyünk erről
is-- Dávid ment át ezeket mind előadás, úgyhogy gyorsan mozognak
here-- alapvetően, akkor Van egy sor értékek.
És akkor megtalálja a legkisebb szétválogatás nélküli értéke
és akkor cseréld azt az értéket Az első nem válogatott értéket.
Aztán csak folyamatos ismétlése a többi a lista.
>> És itt egy vizuális magyarázat Az, hogy hogyan fog működni.
Így például, ha voltunk kezdeni egy sor öt elem, index
0-4, 3, 5, 2, 6, és 4 értékeket helyezni a array-- most így,
mi csak fog vállalni hogy ezek mind nem válogatott
mert még nem tesztelték másképp.
>> Szóval, hogy a válogatott a fajta lenne a munka, hogy ez az első
végigmenni a teljes A szétválogatás nélkül tömb.
Úgy vedd ki a legkisebb értéket.
Ebben az esetben a 3, jobbra Most, a legkisebb.
Egyre 5.
Nem, 5 nem nagyobb than-- vagy sajnálom, nem kevesebb than-- 3.
Így a minimális érték még mindig 3.
És akkor kapsz 2.
A számítógép látja, ó, 2. kevesebb, mint 3.
2 most kell lennie a minimum érték.
És így 2-swap, hogy első érték.
>> Tehát miután egy menetben, akkor valóban látni hogy a 2. és a 3. felcserélődnek.
És mi csak folytatódni fog csinál ez ismét a többi a tömb.
Szóval megyünk, csak végigmenni Az elmúlt négy indexek a tömb.
Meglátjuk, hogy a 3. A következő minimális értéket.
Mi is így fogjuk cserélni, hogy a 4.
És akkor mi csak fog tartani fut át, amíg végül, akkor
eljut egy rendezett tömbben, ahol 2, 3, 4, 5, és 6. minden rendezve.
Mindenki érti a logikát hogyan válogatott egyfajta működik?
>> Csak van valami egy minimális értéket.
Te követi nyomon a mi az.
És ha találsz, akkor cseréld az első érték a array--
vagy, nem az első value-- A következő érték a tömbben.
Hűvös.
>> Tehát ahogy ti egyfajta láttam egy pillantás,
fogunk pszeudókód ezt.
Tehát, ha a srácok a hátsó szeretné csoportot alkotnak, mindenki az asztalnál
alkothat egy kicsit partnere, megyek adni nektek, mint három perc
hogy csak beszélni keresztül A logika, angol,
Az, hogy hogyan lehet, hogy végre pszeudokódja, hogy írjon egy kiválasztási sorrend.
És ott van a cukorkát.
Kérlek, gyere fel és kap édességet.
Ha a hátsó, és szeretné édességet, tudok dobni édességet rád.
Igazából nem you-- hűvös.
Oh bocsánat.
OKÉ.
>> Tehát, ha szeretnénk, mint egy osztály, írási pszeudokódja
hogyan lehetne megközelíteni ezt a problémát, csak nyugodtan.
Megyek körül, és, annak érdekében, kérdezze csoportok
A következő sor mit kell tennünk.
Tehát, ha akartok kezdeni is, mi az első dolog,
a teendő, ha akarsz végre egy módja annak, hogy megoldja ezt a programot
szelektíven rendezni egy listát?
Nézzük csak feltételezni tudjuk van egy tömbben, rendben?
>> Közönség: Azt akarod, hogy egyfajta fajta [hallhatatlan], hogy te
fut át ​​az egész tömböt.
>> ANDI Peng: Jobb.
Szóval fogsz szeretné iterációkhoz keresztül minden helyet, igaz?
Olyan nagy.
Ha akartok, hogy nekem a következő line-- igen, hátul.
>> Közönség: Nézd meg őket mindezt a legkisebb.
>> ANDI Peng: Tessék.
Ezért szeretnénk, hogy menjen át, és ellenőrizze, hogy mi a minimális érték, ugye?
Megyek rövidítésére, hogy a "min."
Mit akartok csinálni után megtalálta a minimális értéket?
>> Közönség: [hallható]
ANDI Peng: Szóval fogsz akar kapcsolja az első tömb,
ugye?
Ez az elején, én fogok mondani.
Minden rendben.
Tehát most, hogy már cserélték az első Egy, mit akarsz csinálni utána?
Tehát most már tudjuk, hogy ez itt kell lennie a legkisebb érték, ugye?
Akkor van egy további pihenésre a tömb ez nem válogatott.
Szóval mit akarsz itt csinálni, ha srácok akar adni nekem a következő sorban?
Közönség: Tehát azt szeretnénk, hogy ismételget keresztül a többi a tömb.
ANDI Peng: Igen.
És így mit iterációjával keresztül fajta jelenti azt valószínűleg szükséged?
Milyen típusú of--
>> Közönség: Ó, egy újabb változó?
ANDI Peng: Valószínűleg a másik a loop, ugye?
Szóval valószínűleg akarnak iterációkhoz through-- nagy.
És akkor fogsz visszatérni, és valószínűleg ellenőrizni a minimális újra,
ugye?
És te fogsz ismételgetni ezt, mert a hurkok csak megy
hogy folyamatosan fut, ugye?
>> Tehát ahogy ti is látni, mi Van egy általános pszeudokódja
Az, hogy hogyan akarjuk ezt a programot, hogy az.
Ez hajtogat itt, mit teszünk tipikusan kell írni a kódunkat
ha azt akarjuk, hogy halad végig egy tömb, milyen struktúrában?
Azt hiszem Christabel Már mondtam ilyet.
>> Közönség: A hurok.
>> ANDI Peng: egy ciklusban?
Pontosan.
Tehát valószínűleg ez lesz egy ciklusban.
Mi a csekk itt fog jelenti?
Általában, ha azt szeretnénk, hogy ellenőrizze ha valami olyasmi else--
>> Közönség: Ha.
>> ANDI Peng: Egy ha, ugye?
És akkor a swap Itt fogunk megy át később, mert Dávid
ment keresztül, hogy előadást is.
És akkor a második hajtogat implies--
>> Közönség: Egy másik hurok.
>> ANDI Peng: --another a hurok, pontosan.
Tehát, ha keresünk Ebben rendesen, mi
Láthatjuk, hogy mi vagyunk talán Szükségem lesz egy beágyazott hurok
A feltételes utasítás ott majd a tényleges kódrészletet, ami
majd cserélni az értékeket.
Szóval már csak általában írásos Egy pszeudokódja kódot itt.
És akkor mi történt valójában fizikailag, mint osztály,
megpróbálja végrehajtani ezt ma.
Menjünk vissza ebbe IDE.
>> UH Oh.
Miért van ez nem-- ez van.
OKÉ.
Sajnáljuk, hadd próbálja nagyítás egy kicsit.
Ott vagyunk.
Minden csinálok itt van már létre A program a "kiválasztás / sort.c."
Létrehoztam egy sor kilenc értékek, 4, 8, 2, 1, 6, 9, 7, 5, 3.
Jelenleg csak tudsz lásd, azok rendezetlen.
n lesz a számot, megmondja, hogy az összeg az értékek
üzenetünk van a tömbben.
Ebben az esetben már kilenc értékeket.
És én most kaptam egy hurok itt hogy kiírja a szétválogatás nélkül tömb.
>> És a végén, én is kaptam egy részére hurok, hogy mindig csak ki újra.
Tehát elméletileg, ha ez a program helyesen működik, a végén,
látnod kell egy nyomtatott for ciklus amelyben az 1, 2, 3, 4, 5, 6, 7, 8,
9 egyaránt helyesen annak érdekében.
>> Tehát van a pszeudokódja itt.
Akar valaki az alábbiakra: Én csak megyek kérni volunteers--
mondja meg pontosan, hogy mit kell megadnia, ha akarunk, először csak ismételget
az elején ez a tömb?
Mi a kódsort vagyok Valószínűleg szükségem lesz itt?
>> Közönség: [hallható]
>> ANDI Peng: Igen, úgy érzi, Ingyenes alábbiakra: bocs, akkor
Nem kell állni up-- érzést szabadon emelje fel a hangját egy kicsit.
>> Közönség: Az int i értéke 0--
>> ANDI Peng: Igen, jó.
>> Közönség: i-nél kisebb tömb hossza.
>> ANDI Peng: Szóval tartsd bánja itt, mert
Nem kell, hogy a funkció azt mondja, a hossza a tömb,
már van egy értéket, amely tárolja, hogy.
Jobb?
A másik dolog, hogy tartsa A mind-- egy tömbben
Kilenc értékek, melyek az indexek?
Mondjuk úgy, hogy ez a tömb volt, 0-3.
Látod, hogy az utolsó index tulajdonképpen 3.
Ez nem 4, bár van négy tömb elemeinek.
>> Tehát itt, van, hogy nagyon óvatosnak kell A mi helyzetünk a hossza
lesz.
>> Közönség: Nem lenne n mínusz 1?
ANDI Peng: Ez lesz n mínusz 1, pontosan.
Van ennek értelme, miért ez n mínusz 1, mindenki?
Ez azért van, mert a tömbök nulla indexelt.
Kezdik 0 és fuss n-ig mínusz 1.
Igen, ez egy kicsit trükkös.
OKÉ.
És akkor--
Közönség: Isnt'1, hogy már gondoskodott ellenére,
ha csak nem azt mondja, "kisebb vagy egyenlő ", és csak azt mondom," kevesebb, mint? "
>> ANDI Peng: Ez egy nagyon jó kérdés.
Szóval igen.
Hanem, az is, hogy vagyunk végrehajtása ellenőrzésének jogát,
meg kell összehasonlítani két érték.
Szóval tényleg akar hagyja a "hogy" üres.
Mert ha összehasonlítjuk ez, hogy nem fogod
Van valami után összehasonlítani, ugye?
Igen.
Tehát i ++.
Adjuk hozzá a zárójelben.
Hoppá.
Nagy.
Így már a kezdet a mi külső hurok.
Tehát most akkor ehhez létrehozunk egy változót tartása
pályán a legkisebb érték, ugye?
Tudja valaki akar adni nekem a kódsort tenne ilyet?
Mire van szükségünk, ha megyünk hogy a tárolni kívánt valamit?
>> Jobb.
Talán jobb név, hogy lenne be-- "temp" teljesen works--
Talán egy találóan elnevezett lenne, ha azt akarjuk, a legkisebb value--
>> Közönség: Min.
ANDI Peng: min, ott megyünk.
min lenne jó.
És így van, mit tegyünk akarjuk inicializálni azt?
Ez egy kicsit trükkös.
Mert most a elején ez a tömb,
Ön még nem nézett semmit, ugye?
Tehát mi, automatikusan, ha mi csak a i értéke 0,
mit akarunk inicializálni Első minimális értéket?
Közönség: i.
ANDI Peng: i, pontosan.
Christabel, miért akarjuk inicializálása hogy én?
>> Közönség: mert jól, kezdünk 0.
Szóval azért, mert nincs mit összehasonlítani azt a minimális lesz a vége, hogy 0.
>> ANDI Peng: Pontosan.
Így hát pontosan így van.
Mert mi van valójában nem nézett semmit,
nem tudjuk, mi a legkisebb érték.
Azt akarjuk, hogy csak inicializálni azt i, amelyek jelenleg, itt van.
És ahogy továbbra is lejjebb ez a tömb,
majd meglátjuk, hogy az egyes További át, i megnöveli.
És így ezen a ponton, i valószínűleg lesz
azt szeretnék, hogy a minimális, mert lesz bármi
a kezdet A szétválogatás nélkül tömb.
Hűvös.
>> Tehát most szeretné adni egy for ciklus itt ez
fog halad végig a szétválogatás nélküli, vagy a többi ezt a tömböt.
Akar valaki adjon nekem egy kódsort tenne ilyet?
Hint-- mi kell ide?
Mi fog menni ez a for ciklus?
Igen.
Közönség: Szóval mi lenne akar eltérő egész szám,
mert kifutunk át a többi A tömb helyett i, így talán
j.
>> ANDI Peng: Igen, j hangzik nekem.
Eredmény?
>> Közönség: Szóval lenne i + 1, mert kezded a következő érték.
És akkor a end-- így ismét, j n-nél kisebb mínusz 1, majd j ++.
ANDI Peng: Nagy.
>> És akkor itt fogunk akarni hogy ellenőrizze, hogy ha a feltétel teljesül,
ugye?
Mivel azt szeretnénk, hogy változtatni a minimális érték
Ha ez valóban kisebb, mint amit te hasonlítsa össze, ugye?
Akkor most mit akarnak itt?
Ellenőrizze, hogy.
Milyen típusú nyilatkozatot fogunk valószínűleg lesz
ti szeretné használni, ha szeretné ellenőrizni valamit?
>> Közönség: if.
>> ANDI Peng: if.
Szóval if-- és mi lesz a feltétellel, hogy azt akarjuk belül
a mi if?
>> KÖZÖNSÉG: Ha a j értékének kevesebb, mint az értéke én--
>> ANDI Peng: Pontosan.
Tehát if-- így ez a tömb az úgynevezett "array".
Nagy.
Tehát, ha array-- mi volt ez?
Mondd újra.
>> Közönség: Ha array-j kevesebb, mint array-i, akkor mi lenne változtatni a min.
Így a min lenne j.
>> ANDI Peng: Van ennek értelme?
OKÉ.
És most itt lent, mi valójában kívánja megvalósítani a swap, ugye?
Szóval emlékszem, az előadás, hogy Dávid, amikor akart cserélni the-- mi volt
it-- narancslevet és milk--
>> Közönség: Ez volt a bruttó.
>> ANDI Peng: Igen, ez a fajta bruttó.
De ez egy nagyon jó koncepciót bemutató ideje.
Szóval szerintem az értékeidet itt.
Van egy sor min, egy sor I,
vagy bármi akartuk cserélni itt.
És valószínűleg nem tudod öntsük őket egymást ugyanabban az időben, jobb?
Szóval mi megyünk hogy létre kell hozni ide
annak érdekében, hogy a csere az értékeket helyesen?
>> Közönség: Egy átmeneti változó.
>> ANDI Peng: Egy átmeneti változó.
Tehát lássuk int temp.
Lásd, ez lenne a jobb ideje az alábbiakra: hé, mi volt ez?
OKÉ.
Tehát ez lett volna jobb ideje, hogy nevét a változó "temp".
Tehát lássuk int temp.
Mit fogunk beállított hőmérséklet egyenlő itt?
Közönség: Min?
ANDI Peng: Ez egy kicsit trükkös.
Ez valójában nem számít a végén.
Nem számít, milyen érdekében úgy dönt, hogy ráköltözni
amíg még van róla Ön nyomon követését, amit csere.
>> Közönség: Ez lehet tömb-i.
>> ANDI Peng: Igen, csináljuk tömb-i.
És akkor mi a következő sort A kód azt akarjuk, hogy itt?
Közönség: tömb-i értéke tömb-j.
ANDI Peng: És végül?
Közönség: tömb-j egyenlő tömb-i.
Közönség: Vagy tömb-j egyenlők array-temp-- vagy, temp.
>> ANDI Peng: OK.
Úgyhogy futtatni ezt és látni ha ez működni fog.
Hol van ez a helyzet?
Ó, ez a probléma.
Lásd a 40. sor, mi vagyunk akarják használni tömb-j?
De hol j csak létezik?
>> Közönség: A for ciklus.
ANDI Peng: Jobb.
Szóval mit fogunk kell csinálni?
>> Közönség: Határozza meg ezen kívül the--
Közönség: Igen, azt hiszem ezt arra, hogy más, ha a nyilatkozatot, ugye?
Szóval, mint, ha a minimum-- Rendben, hadd gondolkozzam.
>> ANDI Peng: Srácok, próbálja hogy vessen egy pillantást Nézzünk
lásd, mi valami, amit tehetünk itt?
>> Közönség: OK.
Tehát, ha a minimális nem egyenlő j-- így ha a minimum még én--
akkor nem kell cserélni.
>> ANDI Peng: Van, hogy az egyenlő i?
Mit akarsz mondani itt?
>> Közönség: Vagy igen, ha a legalább nem egyenlő i, igen.
ANDI Peng: OK.
Nos, hogy megoldja, milyen, a problémáinkat.
De ez még nem oldja meg a probléma, hogy mi történik, ha j-- óta j
nem létezik rajta kívül, mi Mit akarunk csinálni vele?
Kijelentem, hogy ezen kívül?
Próbáljuk futtatása.
UH Oh.
A sorrend nem működik.
>> Mint látható, a kezdeti tömb volt ezeket az értékeket.
És utána kellett volna volt 1, 2, 3, 4, 5, 6, 7, 8, 9.
Nem működik.
Ahh.
Mit csináljunk?
Közönség: Debug.
ANDI Peng: Rendben, próbáljuk ezt.
Mi lehet a hibakeresés.
Zoom out egy kicsit.
Állítsunk a töréspontot.
Menjünk az általam elvártnál OK.
>> Szóval, mert mi már tudjuk, hogy E sorok, 15 és 22.,
vannak working-- mert minden, amit csinálok, az Csak iterációjával keresztül, és printing--
Én is megy előre, és hagyja, hogy.
Kezdjük a 25. sortól.
OOP, hadd megszabadulni, hogy.
>> Közönség: Tehát a töréspont a ahol a hibakeresés indul?
ANDI Peng: Vagy megáll.
Közönség: Vagy megáll.
ANDI Peng: Igen.
Beállíthatjuk, több töréspont és ez is csak ugrani az egyik a másik.
De ebben az esetben nem tudjuk ahol a hiba történik.
Szóval mi csak szeretnénk indul fentről lefelé.
Ja.
OKÉ.
>> Tehát ez a sor itt, lépnénk.
Láthatjuk itt lent, megvan egy tömbben.
Azok az értékek amelyek a tömbben.
Látod, hogy milyen index 0, akkor megfelel a value-- ó,
Én fogom próbálni a nagyításhoz.
Sajnálom, de ez nagyon nehéz hogy see-- a tömb indexe 0,
van egy értéke 4 és majd így tovább, és így tovább.
Megvan a lokális változók.
Most éppen egyenlő 0, ami azt akarjuk, hogy legyen.
>> És így maradjunk átlépett.
A minimális egyenlő 0, ami azt is szeretnénk, hogy legyen.
És akkor mi meg a másodikat hurok, ha tömb-j jelentése kevesebb, mint tömb-I,
amelyeknek nem volt.
Szóval láttad, hogyan hogy átugorja az?
>> Közönség: Tehát ha a ha minimum, minden hogy-- ne, hogy
belsejében az első for ciklust?
ANDI Peng: Nem, mert továbbra is szeretné kipróbálni.
Azt akarod, hogy csinál egy összehasonlítást minden idő után is fut rajta.
Nem csak azt, hogy csináld Az első pass-through.
Meg akarom csinálni a minden további át újra.
Tehát azt szeretnénk, hogy ellenőrizze a Ön állapota belül.
Úgyhogy most megyek folyamatosan fut át ​​itt.
Adok nektek egy tippet.
Ez arról szól, hogy az a tény, hogy amikor te ellenőrzi a feltételes,
te nem ellenőrzi A helyes index.
Akkor most te ellenőrzése mezőindexe j kevesebb, mint tömb
indexe i.
De mit csinálsz fel az elején a for ciklus?
Nem vagy beállítás j egyenlő i?
>> Igen, mi is valójában kilép a debugger itt.
Szóval vessünk egy pillantást a pszeudokódja.
For-- megyünk kezdődik az i értéke 0.
Fogunk felmenni n mínusz 1.
Nézzük, megvoltak, igaz ez?
Ja, hogy igaza volt.
>> Így aztán idebent vagyunk létre fog hozni egy minimális értéket
és beállíthatja az egyenlő i.
Vajon mi az?
Ja, csináltam.
Most a mi belső hurok vagyunk fog tenni j egyenlő I. n mínusz 1.
Vajon mi az?
Sőt, ezt tettük.
>> Így azonban mit keresünk összehasonlítva itt?
>> Közönség: j + 1.
ANDI Peng: Pontosan.
És akkor fogsz szeretné állítani A minimális egyenlő j plusz 1 is.
Így mentem keresztül, hogy nagyon gyorsan.
Srácok, értem Ezért ez j + 1?
OKÉ.
>> Így a tömb, a az első áthaladnak,
a for ciklus, az int i értéke 0, nézzük csak
Feltételezem, hogy ez nem változott még.
Van egy sor, teljesen, Mindössze négy szétválogatás nélküli elemek, ugye?
Ezért szeretnénk inicializálni i értéke 0.
És én fog csak végigmenni ezen a hurok.
És így az első lépés, megyünk inicializálni egy változót a "min"
hogy szintén egyenlő I, mert nincs egy minimális értéket.
Szóval ez jelenleg 0-val egyenlő is.
És akkor mi lesz, hogy menjen át.
És szeretnénk iterációkhoz újra.
Most, hogy megtaláltam, amit a minimális van, azt akarjuk, hogy halad végig
újra látni, ha ez az összehasonlítás, az igaz?
Tehát j, itt, folyik egyenlő i, ami 0.
És akkor, ha tömb j plusz, ami az egyik, hogy a következő vége, mivel kevesebb
mint amit a jelenlegi minimális érték, szeretné cserélni.
>> Tehát mondjuk, mi már kapott, mint a, 2, 5, 1, 8.
Most éppen egyenlő 0 és j értéke 0.
És ez a minimum érték.
Ha tömb-j plusz én-- így ha az egyik ez után egy keresünk
nagyobb, mint az előtte, ez meg fog válni a minimum.
>> Tehát itt azt látjuk, hogy az 5. nem kevesebb, mint hogy.
Szóval ez lesz nem lesz 5.
Látjuk, hogy az 1. kevesebb, mint 2, ugye?
Tehát most már tudjuk, hogy a mi minimum lesz az index értéke a 0, 1, 2.
Igen?
Aztán, amikor már itt lent, akkor csere a helyes értékeket.
>> Tehát, ha a srácok csak úgy, a j előtt, akkor nem nézi az egy
utána.
Néztek ugyanazt az értéket, amely
Ezért ez csak nem csinál semmit.
Van ennek értelme mindenkinek, Ezért szükséges, hogy plusz 1 ott?
OKÉ.
Most nézzük csak végigmenni úgy, hogy arról, hogy a többi kód helyes.
Miért van ez történik?
Ah, ez a perc itt.
Voltunk összehasonlítjuk a rossz értéket.
Oh ne.
>> Ó, igen, itt lent voltunk csere a rossz értékeket is.
Mert kerestünk i és j.
Ezek azok voltunk megnézni.
Igazából akarjuk cserélni legalább a jelenlegi minimális,
A bármilyen kívül senki nem.
És ahogy ti is lent Itt van egy rendezett tömbben.
Csak volt köze az a tény, hogy amikor a
voltunk ellenőrzése értékeket kaptunk összehasonlításával,
mi nem keresi a megfelelő értékeket.
Néztük ugyanaz Itt valójában nem csere is.
Meg kell nézni az egyik mellett hozzá, és akkor lehet cserélni.
Szóval ez a fajta lehallgatás kódunkat előtt.
És mit csináltam itt mindent A debugger volna tenni az Ön számára
Én csak tettem a fórumon, mert könnyebb
hogy ahelyett, Nagyításhoz a debugger.
Van ennek értelme mindenki?
Hűvös.
>> Minden rendben.
Mi lehet lépni beszél aszimptotikus jelölés, amely
csak egy divatos szóval a runtimes az összes ilyen fajta.
Szóval tudom, hogy Dávid, az előadás, érintette runtimes.
És ment keresztül az egész vegyület hogyan kell kiszámítani a runtimes.
Nem kell aggódni miatta.
Ha igazán kíváncsi A hogyan működik,
nyugodtan beszélni velem szakasz után.
Mi lehet a séta képletekkel együtt.
De minden a srácok, hogy valóban tudom, hogy n faragva több mint 2
ugyanaz a dolog, mint n négyzeten.
Mivel a legnagyobb számban, a kitevő, nő a legjobban.
És így a mi szempontunkból, Minden törődünk
az, hogy a hatalmas szám, amely egyre fejlődik.
>> Tehát mi a legjobb esetben futásidejű kiválasztási sorrend?
Ha megy, hogy végiglépkedhetünk listát
majd halad végig A többi, hogy a listát,
hányszor Fogsz valószínűleg,
a legrosszabb case-- a legjobb esetben sorry-- végigmenni?
Lehet, hogy a jobb kérdés megkérdezni, mi a legrosszabb esetben
futásidejű kiválasztás sort.
Közönség: n négyzeten.
ANDI Peng: Ez n faragva, ugye.
Tehát egy egyszerű módja annak gondol ez olyan, mint, Önnek bármikor két egymásba ágyazott ciklusok esetében,
ez lesz n faragva.
Mert nem csak te fut át ​​ismét,
akkor vissza kell mennie körül, és futni rajta
ismét benne minden értéket.
Tehát ebben az esetben, futsz n szer n faragva, amely is-- sajnálom,
n-szer n, ami megegyezik n faragva.
>> És sort is egy kicsit egyedülálló abban az értelemben,
hogy nem számít, ha ezeket értékek már sorrendben.
Ez még mindig tart végigmenni egyébként.
Mondjuk úgy, hogy ez a mennyiség 1, 2, 3, 4.
Függetlenül attól, hogy ez volt a érdekében, hogy el tudta volna fogadni végigfutott
és még mindig ellenőrizni a minimális értéket.
Ez lett volna a ugyanazt az ellenőrzések számát
minden egyes alkalommal, akkor is, ha valójában nem nyúlj semmihez.
>> Tehát egy ilyen esetben, a legjobb és legrosszabb runtimes valójában egyenértékű.
Tehát a várható futási A kiválasztási sorrend,
amely megnevezzük a szimbólum théta, théta, ebben az esetben,
lenne továbbá n négyzeten.
Mindhárom lenne N négyzeten.
Mindenki tisztában, hogy miért A runtime n faragva?
>> Minden rendben.
Szóval én csak fog, hogy gyorsan fut keresztül a többi fajta.
Az algoritmus buborék sort-- emlékszem,
ez volt az első, David odament előadás.
Lényegében lépsz keresztül a teljes listát
és akkor swap-- csak hasonlítsa össze a két egy időben.
És ha az egyik nagyobb, mint ha csak cserélni őket.
Tehát, ha ezek nagyobb, akkor cserélni.
Van hivatalos itt.
>> Szóval maradjunk annyiban, hogy volt 8, 6, 4, 2.
Az ember azt összehasonlítani a 8 és 6.
Meg kéne cserélni őket.
Akkor lenne összehasonlítani a 8 és 4.
Meg kéne cserélni őket.
Ha cserélni a 8. és A 2, megváltoztatni őket is.
Tehát ilyen értelemben, láthatjuk, játszott ki, mint egy hosszú ideig,
milyen értékeket fajta buborék A végén, ezért is hívják
buborékos rendezést.
>> Mi lenne, csak végigmenni újra a második menetben, és a mi harmadik menetben,
és a negyedik menetben.
Lényegében buborékos rendezést csak fut amíg meg nem teszik többé swap.
Tehát ebben az értelemben, ez csak általános pszeudokód érte.
Semmi gond, ezek mind online.
Nem kell, hogy ténylegesen megy át ezt.
>> Mi csak inicializálni egy számláló változó, amely 0-nál kezdődik.
És halad végig az egész tömböt.
És ha egyik érték is-- ha ez érték nagyobb, mint ez az érték,
fogsz cserélni őket.
És akkor te csak fog tartani fog.
És te fogsz számolni.
És csak most fog tartani ezzel Ezalatt a számláló nagyobb
mint 0, ami azt jelenti, hogy a minden alkalommal meg kell cserélni,
tudja, hogy szeretne menni vissza, és ellenőrizze újra.
Azt akarod, hogy nézz, amíg nem tudja hogy nem kell cserélni többé.
>> Tehát mi a legjobb és a legrosszabb esetében runtimes a buborékos rendezést?
És hint-- ez valójában más a kijelölés sort abban az értelemben,
hogy ezek a két válasz nem ugyanaz.
Gondoljon bele, mi történne ügyben akkor, ha már válogatni.
És hiszem, hogy mi történne, ha ez volt
abban az esetben, amelyben nem volt rendezve.
És akkor milyen futtatni keresztül, hogy miért történik.
Adok nektek, mint, 30 másodpercig gondolni.
>> OKÉ.
Van valakinek egy kitalálni, mi a legrosszabb esetben futásidejű buborék rendezés?
Igen.
>> Közönség: lenne, mint n-szer n mínusz 1, vagy valami ilyesmi?
Mint minden alkalommal fut, ez csak, mint, egy csere kevesebb
hogy bármi is volt.
>> ANDI Peng: Igen, te teljesen igaza van.
És ez az az eset, amelyben a válasz valójában sokkal összetettebb,
mint az, meg kell adni.
Szóval ez lesz run-- vagyok fog törölni mindezt itt.
Mindenki jó?
Lehet törölni ezt?
OKÉ.
Fogsz végigmenni n alkalommal először, ugye?
És ők fognak végigmenni n mínusz 1 másodszor, igaz?
És akkor fogsz tartani megy, n az enyém 2, satöbbi.
Dávid tette ezt egy előadás, ahol, ha összeadjuk mindazokat az értékeket,
kapsz valamit, ami az általam elvártnál yeah-- több, mint 2, amely lényegében csak csökkenti
le n faragva.
Fogsz, hogy egy fura frakció ott.
És így csak tudom, hogy Az n-négyzet mindig
elsőbbséget élvez a frakció.
És így ebben az esetben, a legrosszabb futásidejű lenne n faragva.
Ha ez csökkenő érdekében, gondolom, akkor
Van, hogy egy-swap minden egyes alkalommal.
>> Mi lenne, potenciálisan, A legjobb esetben futásidejű?
Mondjuk úgy, ha a lista már annak érdekében, hogy mi lenne a futtató legyen?
>> Közönség: n.
ANDI Peng: Ez n, pontosan.
És miért van az, n?
Közönség: Mert csak van, hogy ellenőrizze az egyes egyszer.
ANDI Peng: Pontosan.
Így a lehető legjobb runtime, Ha ez a lista már
sorted-- mondjuk 1, 2, 3, 4-- akkor csak megy keresztül, akkor kérjük,
Ön is látni, ó, azok mind sikerülni.
Nem kellett cserélni.
Végeztem.
Tehát ebben az esetben, ez csak n vagy a lépések számát csak
Volt, hogy ellenőrizze az első listáján.
>> És miután, most hit beillesztés sort, ahol
Az algoritmus lényegében a szakadék ez egy rendezett és rendezetlen része.
És akkor egy-egy, A szétválogatás nélkül értékek
beilleszteni a megfelelő pozíciókat a lista elején.
>> Így például, hogy van egy listája 3, 5, 2, 6, 4 újra.
Tudjuk, hogy ez jelenleg szétválogatás nélkül, mert most már csak
kezdte néztem.
Veszünk egy pillantást, és tudjuk, hogy Az első érték válogatni, ugye?
Ha csak nézi egy sor méretű, tudod, hogy ez válogatni.
>> Tehát tudjuk, hogy a másik négy szétválogatás nélkül.
Mi megy keresztül, és azt látjuk, hogy értéket.
Menjünk vissza.
Lásd, hogy értéke 5?
Veszünk egy pillantást rá.
Összehasonlítjuk azzal 3.
Tudjuk, hogy ez nagyobb, mint 3, így tudjuk, hogy ami válogatni.
Tehát most már tudjuk, hogy az első két vannak sorolva, és az utolsó három nem.
>> Veszünk egy pillantást 2.
Először ellenőrizze, hogy 5.
Vajon kevesebb, mint 5?
Ez nem.
Tehát meg kell tartani lenézett.
Akkor ellenőrizze 2 db 3.
Vajon kevesebb?
Nem.
Szóval tudja a 2 kell beilleszteni az elülső és a 3. és 5.
mindkettőt fel kell tolta ki.
Ehhez ismét 6 és 4.
És mi csak nézz lényegében ahol csak nézd, nézd, nézd.
És amíg ez a helyes helyzetben vagyunk fajta csak
helyezze be a megfelelő pozícióba, ott, ahol a nevét, ahonnan származik.
>> Szóval ez csak az algoritmus, pszeudokódja önmagában egyfajta,
arról, hogy hogyan fogja valósítani beiktatási sort.
Pszeudókód itt van.
Ez mind az interneten.
Nem gond, ha a srácok próbálja másolni ezt le.
Tehát még egyszer, ugyanazt, amit question-- lenne a legjobb és a legrosszabb runtimes
behelyezhető sort?
Ez nagyon hasonlít az utolsó kérdésre.
Adok nektek, mint, 30 másodperc gondolni ezt is.
>> OK Akar valaki add nekem a legrosszabb futási?
Igen.
>> Közönség: n négyzeten.
>> ANDI Peng: Ez n faragva.
És miért van az, n faragva?
>> Közönség: Mert fordított sorrendben, akkor
átmenni n-szer n, amely is--
ANDI Peng: Igen, pontosan.
Tehát ugyanaz, mint a buborékos rendezést.
Ha ez a lista a csökkenő sorrendben, te
lesz, hogy ellenőrizze először egyszer.
És akkor minden hozzáadott értéket, te
lesz, hogy ellenőrizze ellen minden érték, ugye?
És így összesen, fogsz tenni n időtöltésükkel másik n át, amely
N négyzeten.
Mi a helyzet a legjobb esetben?
Igen.
>> Közönség: n mínusz 1, mert a elsőt már faragva.
>> ANDI Peng: Szóval, közel.
A válasz tulajdonképpen n.
Mert míg az első egy válogatni, akkor nem actually-- meg
mi csak lucked, a hogy például, hogy a 2.
történt, hogy a legkisebb szám.
De ez nem lesz mindig így.
Ha 2 már válogatni az elején de úgy nézel ki, és van egy 1 van,
Az 1 fog bump meg.
És ez lesz a vége fel, hogy ütközött egyébként.
>> Szóval a legjobb forgatókönyv esetén, ez valójában csak lesz n.
Ha 1, 2, 3, 4, 5, 6, 7, 8, te
fog végigmenni hogy teljes listát egyszer
hogy ellenőrizze, hogy ha minden rendben.
Mindenki tisztában futás szer kiválasztását is?
Tudom, min megyek keresztül Ezek nagyon gyors.
De csak tudom, hogy ha tudod, hogy a általános fogalmakat, akkor legyen jó.
OKÉ.
Szóval én csak adni nektek talán, mint, Egy perc beszélni a szomszédok
milyen Íme, néhány A főbb különbségek
E típusok között a fajta.
Átnézzük, hogy hamarosan.
Közönség: Ó, oké.
ANDI Peng: Igen.
OKÉ.
Cool, hadd hívja össze újra, mint egy osztály.
OKÉ.
Tehát ez a fajta egy nyitott kérdések abban az értelemben,
hogy van sok választ rájuk.
És megyünk át néhány közülük röviden.
Csak azt akartam, hogy a srácok gondolkodni, hogy milyen differenciált
mindhárom fajta.
És hallottam, azt is, nagy question-- mit egyesülésről sort csinálni?
Nagy kérdés, mert ez az, amit mi lefedő következő.
>> Így egyesül sort a egyféle, hogy a funkciók
nagyon eltérően a többi fajta.
Ahogy ti is see-- tett Dávid csinálni demo
ahol már a hűvös zajai látta, hogy merge
Rendezés futott, mint a végtelenül gyorsabb, mint a másik két típusú?
OKÉ.
Szóval ez azért van, mert merge Rendezés végrehajtja ezt a szakadék
és uralkodj koncepció, hogy mi már Beszéltünk sok előadás.
Ebben az értelemben, hogy szeretnék dolgozni okosabb, sem nehezebb, ha elosztjuk
és uralkodj problémákat, és megtörni őket le, majd rakjuk őket,
jó dolgok mindig történnek.
>> Tehát az is, hogy egyesíteni rendezés alapvetően működik
az, hogy felosztja egy szétválogatás nélküli tömb felét.
És akkor ez van két fele tömbök.
És ez csak rendezi a két fél.
Ez csak folyamatosan osztjuk ketté, a fele, a felére, amíg nincs minden rendezve
majd rekurzívan olyan, hogy együtt.
>> Szóval ez tényleg elvont.
Tehát ez csak egy kis pszeudokódja.
Van ennek értelme úgy, ahogy fut?
Szóval maradjunk annyiban, hogy van egy tömb n elem, ugye?
Ha n kevesebb, mint 2, akkor vissza.
Mert tudod, hogy ha van csak egy dolog, meg kell válogatni.
Mást, akkor rendezni a bal fele, majd rendezni a jobb fele,
és akkor egyesíteni.
>> Tehát miközben úgy néz ki, nagyon egyszerű, a valóságban, gondoltam, hogy ez
fajta nehéz. Mert te, mint Nos, ez a fajta futó magát.
Jobb?
Ez fut magát.
Tehát ebben az értelemben, David megérintette upon rekurzió osztályban.
És ez egy olyan fogalom, fogunk beszélni többet.
Ez, hogy ez a két vonal Itt valójában csak a program
mondja, hogy fut magát A különböző bemeneti.
Tehát ahelyett, futni magát A teljes egészében az n elem,
Ön tudja bontani a bal fele és a jobb fele
majd indítsuk újra.
>> És akkor majd nézd meg vizuálisan, mert én vagyok a vizuális tanuló.
Ez jobban működik nekem.
Szóval akkor nézd meg a vizuális példának.
>> Mondjuk van egy tömbben, hat elemek, 3, 5, 2, 6, 4, 1, nem rendezve.
Rendben, van egy csomó ezen az oldalon.
Tehát, ha a srácok nézd meg a első lépés itt, 3, 5, 2, 6, 4, 1,
akkor hasít ketté.
Van 3, 5, 2, 6, 4, 1.
Tudja, hogy ezek a aren't-- akkor Nem tudom, ha ők válogatni, akár nem,
így folyamatosan feltörik őket, félbe, fél, fél, míg végül,
Önnek csak az egyik eleme.
És egy elem mindig válogatni, ugye?
>> Tehát tudjuk, hogy a 3, 5, 2, 4, 6, 1, önmagukban vannak sorolva.
És most lehet őket újra együtt.
Tehát tudjuk, hogy a 3, 5.
Azt hogy ezeket össze.
Tudjuk, hogy ez a rendezett.
A 2 még mindig ott van.
Mi is tesz a 4. és a 6. össze.
Tudjuk, hogy ami válogatni, így teszünk, hogy össze.
És az 1 van.
>> És akkor csak nézd meg E két félből itt.
Megvan a 3, 5, 2, 2, 3, 5.
Akkor csak összehasonlítani a elején mindent.
Mert tudod, hogy ez a rendezve és tudod, hogy ami válogatni.
Szóval akkor nem is kell összehasonlítani az 5, akkor csak összehasonlítani a 3.
És a 2 kisebb, mint 3, így Tudja 2 kell menni a végén.
>> Ugyanaz a dolog ott.
Az 1 kell menni innen.
És akkor, amikor megy fel E két érték együtt,
Tudja, hogy ez válogatni és tudod, hogy van rendezve.
Így aztán az 1-es és a 2, a 1 kevesebb, mint 2.
Hogy megmondja, hogy az 1- kell menni a végén ez a
anélkül, hogy ránézett 3 vagy 5.
És akkor a 4, akkor csak ellenőrizze, hogy jól megy itt.
Nem kell, hogy nézd meg a 5.
Ugyanaz a 6.
Tudja, hogy a 6-- ez csak nem kell vizsgálni.
>> És így ezen a módon, akkor Csak megtakarítás magát
sok lépésből ha csak összehasonlítjuk.
Nem kell összehasonlítani minden eleme ellen más elemeket.
Te csak összehasonlítani az is, hogy meg kell összehasonlítani ellen.
Szóval ez a fajta elvont fogalom.
Nem gond, ha ez nem nagyon üti meg a jobb még.
De általában, ez hogyan merge sort működik.
Kérdések, gyors kérdés, mielőtt lépni?
Igen.
>> Közönség: Szóval azt mondta, hogy vegye a 1, majd a 4 és a 6
és tedd őket.
Tehát nem those-- nem Ön nézi őket
különálló elemként, nem olyan az egész?
ANDI Peng: Igen.
Szóval, mi történik az, hogy alapvetően
létrehoz egy új tömböt.
Szóval tudom, hogy itt, van Két tömbök mérete 3, ugye?
Szóval tudom, hogy én rendezett tömbben szüksége van hat elemet.
Szóval csak létre Új memória mennyisége.
Szóval maga olyan, mint hogy pazarló memória,
de ez nem számít mert annyira kicsi.
Szóval nézd meg a 1 és akkor nézd meg a 2.
És tudod, hogy az 1 kevesebb, mint 2.
Szóval tudom, hogy 1 kell menni az elején az összes ilyen.
>> Nem is kell, hogy megnézi az a 3. és az 5.
Szóval tudod 1 odamegy.
Akkor alapvetően levágja az 1.
Ez, mint a halott nekünk.
Ezután már csak 2, 3, 5, majd a 4. és 6..
És akkor tudod, hogy te hasonlítsa össze a 4, és a 2,
ó, a 2 kell menni oda.
Szóval puff a 2 le, akkor vágja le.
Szóval akkor csak azt a 3 és az 5, a 4 és a 6.
És csak folyamatosan darabolás le amíg meg őket a tömbben.
>> Közönség: Szóval te csak mindig összehasonlítjuk az [hallhatatlan]?
>> ANDI Peng: Pontosan.
Tehát ebben az értelemben, te Csak összehasonlítva lényegében
Egy szám a másik ellen számát.
És mert tudja, hogy ez válogatni, akkor
Nem kell, hogy nézze át Az összes szám.
Csak meg kell nézni az elsőt.
És akkor csak puff le őket, mert tudja,
tartoznak, ha kell tartozni.
Igen.
Jó kérdés.
>> És akkor, ha valakinek egy kicsit ambiciózusabb,
nyugodtan nézd meg ezt a kódot.
Ez tulajdonképpen a fizikai megvalósítása
Az, hogy hogyan fog írni merge sort.
És láthatjuk, hogy nagyon rövid.
De az ötletek mögött ez elég bonyolult.
Tehát, ha úgy érzed, rajz ezt ki a házi feladatot ma este, nyugodtan.
>> OKÉ.
Így Dávid is ment át ezt az előadást.
Melyek a legjobb esetben runtimes, legrosszabb esetben runtimes,
és a várható futási időt a merge sort?
Egy pár másodperc gondolni.
Ez elég nehéz, de ilyen intuitív, ha belegondolsz.
Minden rendben.
>> Közönség: a legrosszabb esetben n log n?
ANDI Peng: Pontosan.
És miért van az, n log n.
>> Közönség: Hát nem azért, mert válik exponenciálisan gyorsabb,
így, mint a függvénye, hogy ahelyett, hogy csak egyszerűen csak n
faragva, vagy valami?
ANDI Peng: Pontosan.
Tehát az ok, amiért a futásidejű ezen n log
n because-- mi vagy te Ennek mindezen lépések?
Te csak aprítás félbe, ugye?
És így, amikor csináljuk a jelentkezzen, mindent, amit csinál
elosztjuk a probléma a felére, fél, fél, több részre.
És ebben az értelemben, akkor milyen A megszünteti a lineáris modell
hogy a korábban használt.
Mert ha karaj dolgokat fele, ez egy napló.
Ez csak a matematikai módja képviselője.
>> És végül, a végén, akkor csak hogy egy utolsó áthaladnak
hogy mindet annak érdekében, ugye?
És így ha csak meg kell ellenőrizze egy dolog, ami n.
És így te ilyen megszorozzuk a kettő együtt.
Tehát ez olyan, mint neked, hogy a végső ellenőrizze az N idelent egy log n
itt, fent.
És ha megszorozzuk őket, ami n log n.
>> És így a legjobb és legrosszabb ügyben, és várhatóan mind n log n.
Ez is, mint egy másik fajta.
Ez olyan, mint kiválasztási sorrend abban az értelemben, hogy
Nem számít, milyen a lista, akkor csak megy
hogy nem ugyanaz a dolog minden egyes alkalommal.
OKÉ.
Tehát ahogy ti is látni, annak ellenére, A fajta, hogy eljutottunk addig through-- n
faragva, ez nem túl hatékony.
És még ez n log n nem a leghatékonyabb.
Ha a srácok kíváncsi, van egyfajta mechanizmusok
hogy olyan hatékonyak, hogy ők Szinte alapvetően sík futásidőben.
>> Van néhány log n években.
Van néhány log log n években.
Mi nem érintem őket Ebben az osztályban most.
De ha a fiúk kíváncsi, nyugodtan google, mi
a leghatékonyabb válogatás mechanizmusokat.
Nem tudom, vannak néhány igazán vicces is,
általam elvártnál van néhány igazán vicces is, hogy az emberek.
És vajon hogyan valaha is gondoltam.
Tehát a Google, ha van egy kis tartalék idő szerint, mik vicces módon
hogy people-- valamint hatékony ways-- emberek
lett volna képes végrehajtani fajta.
OKÉ.
És itt van, csak egy praktikus kis táblázatot.
Tudom, mindannyian, előtte kvíz 0, lesz a szobádban valószínűleg megpróbál
megjegyeznünk, hogy.
Szóval ez szép ott a srácok.
Csak ne felejtsük el a logikát, hogy made-- Ezért ezeket a számokat is előforduló.
Ha mindig elvész, csak hogy Biztosan tudom, mi a fajtákat.
És akkor végigmenni ezek a fejedben
kitalálni, hogy miért válaszok ezeket a válaszokat.
>> Minden rendben.
Mi is így fogjuk mozgatni A végül a keresést.
Mert, mint azoknak, akik elolvasták a PSET,
keresés is része e heti probléma határozza.
Meg fogjuk kérni, hogy végre kétféle keresést.
Az egyik egy lineáris keresés és egy bináris keresés.
>> Tehát a lineáris keresés meglehetősen egyszerű.
Csak azt akarom, hogy keressen elem Egy lista, hogy ha kap ez.
Csak meg kell halad végig.
És ha az egyenlő valamit, akkor csak vissza, ugye?
De az, hogy mi vagyunk a legtöbb Érdekel beszél
bináris keresés, jobb, ami a oszd meg és uralkodj mechanizmust, amely
David volt, bizonyítja az előadás.
>> Ne feledje, a telefonkönyvben például hogy ő tartja nevelő,
Az egyik, hogy azt a fajta küzdött egy kicsit az elmúlt évben,
ahol ossza meg a problémát a felére, fél, fél, újra és újra,
amíg meg nem találja, amit keres?
És megvan a futásidejében hogy is.
És láthatjuk, hogy jelentősen hatékonyabbá
mint bármilyen más típusú keresést.
>> Tehát az is, hogy mi járna el végrehajtási bináris kereső
van, ha volt egy tömb, index 0-6, hét elem,
tudjuk meg a közepén, right-- Sajnálom, ha a kérdésünkre first--
ha meg akarjuk feltenni a kérdést az, nem a tömb tartalmazza az elem a 7,
Nyilvánvaló, hogy az emberek, és miután Egy ilyen kis tömb, így könnyű a számunkra
igent mondani.
De a módja a bináris Keresés lenne, hogy nézd közepén.
>> Tudjuk, hogy a mutató 3 a középső, mert mi
tudom, már csak hét elem.
Mit 7 osztva 2?
Akkor vágjunk le, hogy extra 1.
Megvan 3 a közepén.
Tehát tömb 3 egyenlő 7?
Nem, nem igaz?
De tehetünk egy pár ellenőrzések.
Van tömb 3 kevesebb, mint 7, vagy a tömb 3 nagyobb, mint 7?
>> És tudjuk, hogy ez kevesebb, mint 7.
Tehát tudjuk, hogy, jaj, akkor azt nem lehet a bal felét.
Tudjuk, hogy meg kell a jobb fele, ugye?
Szóval mi csak levágja a felét a tömbben.
Nem is kell, hogy nézd meg többé.
Mert tudjuk, hogy fele a problem--
tudjuk, hogy a válasz a jobb fele a mi problémánk.
Szóval csak nézd meg, hogy most.
>> Így most nézzük meg a közepén, ami megmaradt.
Hogy index 5.
Mi nem ugyanaz a csekket Úgy látjuk, hogy ez kisebb.
Így néz ki a bal oldalon, hogy.
És akkor azt látjuk, hogy a bejelentkezés.
A tömb érték index 4 egyenlő 7?
Ez.
Így tudunk visszatérni igaz, mert megtaláltuk az értéket a listánkon.
Vajon az út mentem keresztül Van ennek valami értelme, hogy mindenki?
OKÉ.
Adok nektek talán, mint, Három, négy perc kitalálni
hogyan pszeudókód ezt.
>> Így elképzelhető, kértem, hogy levelet nevű függvény kereső (), hogy vissza
érték, egy logikai érték, hogy igaz-e vagy false-- mint,
Igaz, ha megtalálták a érték, hamis, ha nem.
És akkor volt telt az érték, amit
kerestek be értékeket, amelyek a array-- ó, én határozottan fel
hogy a rossz helyen.
OKÉ.
Egyébként, hogy legyen volt, hogy a jobb értékeket.
És aztán int n a szám Az elemek ebben a tömbben.
Hogyan megy megpróbálni hogy pszeudókód, hogy a problémát?
Adok nektek tetszik Három perc alatt megtenni.
Nem, azt hiszem, van only-- Igen, van még egy egészen itt.
Közönség: Can I?
ANDI Peng: Igen, hoztam neked.
Az, hogy a munkát?
OK, hűvös.
>> OKÉ.
Rendben srácok vagyunk fog fékezni azt.
OKÉ.
Tehát feltételezzük, megvan ez a szép kis tömb n értékeket is.
Én nem a vonalak.
De hogyan érjük el próbál írni?
Akar valaki hogy nekem az első sorban?
Ha azt szeretnénk, hogy nekem a első sorban ennek pszeudokódja.
>> Közönség: [hallható]
Közönség: Az ember azt szeretné, iterációkhoz through--
Közönség: Csak egy újabb hurok?
Közönség: --for.
>> ANDI Peng: Szóval ez az ember egy kicsit trükkös.
Gondolj about-- szeretne tartani fut ez a hurok
újra és újra, amíg mikor?
>> Közönség: Amíg a [hallhatatlan] érték egyenlő az értékkel.
ANDI Peng: Pontosan.
Így valójában csak write-- mi is egyszerűsíti, hogy tovább.
Mi is csak nem egy while ciklus, ugye?
Így csak azt loop-- Tudjuk, hogy ez egy darabig.
De most, megyek mondani, hogy "hurok" - a mi?
Hurok until-- mi mi végződő állapota?
Azt hiszem, hallottam.
Hallottam, hogy valaki mondani.
>> Közönség: Értékek egyenlő közepén.
ANDI Peng: Mondd újra.
Közönség: Vagy, amíg a értéke maga keresett
az egyenlő a középső érték.
>> ANDI Peng: Mi van, ha nem ott?
Mi van, ha az érték, amit keres A valójában nem ez a tömb?
Közönség: Visszatér 1.
>> ANDI Peng: De mit akarunk loop-ig, ha olyan az állapota?
Igen.
>> Közönség: Amíg csak egy van az érték?
ANDI Peng: Tudod hurok until-- úgy tudja, hogy te
Lesz egy maximális érték, ugye?
És tudod, hogy fogsz hogy egy perc értéket, nem igaz?
Mert azt is, hogy valami Elfelejtettem mondani, mielőtt,
hogy valamit, ami kritikusan bináris keresés
az, hogy a tömb már rendezve.
Mert nincs módja a ez, ha ők csak a véletlen értékeket.
Nem tudom, ha az ember nagyobb, mint a másik, ugye?
>> Szóval tudom, hogy a max és Ön perc itt, ugye?
Ha lesz kiigazításáról A max a perc, és a mid--
nézzük csak feltételezik, hogy a közepén érték jobb here--
fogsz alapvetően hurok, amíg a minimum
körülbelül ugyanaz, mint a max, jobbra, vagy ha a max nem ugyanaz, mint a min.
Jobb?
Mert ha ez megtörténik, akkor tudjuk, hogy amit végül elérje ugyanazt az értéket.
Tehát azt szeretnénk, hogy hurkot, amíg a min kevesebb vagy egyenlő, mint az alábbiakra: Hoppá,
nem kevesebb, mint vagy egyenlő, A másik út around-- max.
>> Tudta, hogy van értelme?
Vettem egy pár próbálkozás, hogy ezt a jogot.
De hurok, amíg a maximális érték lényegében szinte kevesebb
vagy egyenlő, mint a minimális, ugye?
Ez az, amikor tudod, hogy már közeledett.
Közönség: Ha azt a maximális értéke kevesebb, mint a minimális?
ANDI Peng: Ha megtartja kiigazítva, amely
mi megyünk hogy csinál ebben.
Ennek van értelme?
Minimális és maximális csak egészek, hogy mi valószínűleg
fog létrehozni kívánt tartani követni, ahol keresünk.
Mivel a tömb létezik függetlenül attól, hogy mit csinálunk.
Mint, nem vagyunk fizikailag darabolás le a tömböt, ugye?
Mi csak beállító ahol keresünk.
Ennek van értelme?
>> Közönség: Igen.
>> ANDI Peng: OK.
Tehát ha ez a feltétele a hurok, mit akarunk belül ez a hurok?
Mit fogunk kell akarnak csinálni?
Tehát most, megvan max és min, igaz,
Valószínűleg készítette fel valahol.
Fogunk érdemes találni egy középső, ugye?
Hogyan fogjuk, hogy képes megtalálni a közepén?
Mi a mathematical--
Közönség: Max plusz min osztva 2.
ANDI Peng: Pontosan.
Ennek van értelme?
És srácok, miért vagyunk Nem csak use-- miért tette ezt
ahelyett, hogy csak n osztva 2?
Ez azért van, mert n értéke hogy fog ugyanaz marad.
Jobb?
De ahogy igazítanunk a minimális és maximum értékek, ők fognak változni.
És ennek eredményeként, a mi középső meg fog változni is.
Szóval ezért szeretnénk Ehhez itt.
OKÉ.
>> És akkor, most, hogy találtunk our-- igen.
>> Közönség: Csak egy gyors question-- amikor azt mondja, min és max,
vagyunk feltételezve, hogy ez már válogatni?
>> ANDI Peng: Igen, ez valóban egy előfeltétele a bináris keresés,
hogy van, hogy tudom, hogy válogatni.
Ezért van az a fajta, írsz a probléma elé a bináris keresés.
OKÉ.
Most, hogy tudjuk, hol a középpont van, mit akarsz itt csinálni?
>> Közönség: Azt akarjuk összehasonlítani hogy a másikat.
ANDI Peng: Pontosan.
Szóval lesz összehasonlítani közép érték, ugye?
És mit mond minket, amikor összehasonlítani?
Mit akarunk csinálni utána?
>> Közönség: Ha az érték nagyobb mint a közepén, azt akarjuk, hogy vágja le.
ANDI Peng: Pontosan.
Tehát, ha az érték nagyobb mint a közepén vagyunk
akarnak változtatni ezen minimum és maxes, ugye?
Mit akarunk változtatni?
Tehát, ha tudjuk, hogy az érték valahol itt, mit is változtatni?
Azt akarjuk, hogy megváltoztassuk a minimális legyen közepéig, igaz?
És akkor még, ha ez ebben a fele, mit akarunk változtatni?
>> Közönség: Az Ön maximális.
ANDI Peng: Igen.
És akkor te csak megy tartani hurok, ugye?
Mert most, miután az egyik ismétlés keresztül, van egy max itt.
És akkor újraszámolja a közepén.
És akkor össze lehet hasonlítani.
És te fogsz tartani fog amíg a perc, és a maxes
lényegében konvergens.
És ez az, amikor tudod, hogy you hit a vége.
És akár már megtalálta vagy még nem ezen a ponton.
>> Van ennek értelme mindenki?
OKÉ.
Ez is nagyon fontos, mert akkor már
hogy megírjam ezt a kódot ma este.
De a srácok egy nagyon jó értelemben, hogy mit kell tennie,
ami jó.
OKÉ.
Tehát van hét perc van hátra részt.
Így fogunk beszélni ez PSET, hogy mi fog csinálni.
Tehát a PSET van osztva két részre.
Az első félidő során végrehajtása találni
amelyben írsz egy lineáris keresés, a bináris keresés, és a rendezési algoritmus.
>> Tehát ez az első időt egy PSET, ahol
mi lesz így a srácok az úgynevezett elosztási kód, amely a kód
hogy már előre megírt, de csak maradt néhány darab ki
Ön számára, hogy befejezze az írás.
Szóval srácok, ha megnézed ezt kódot, akkor lehet, hogy tényleg félek.
Ha csak tetszik, ahh, én Nem tudom, hogy mit csinál,
Nem tudom, tetszik, hogy úgy tűnik, olyan bonyolult, ahh, kikapcsolódásra.
Oké.
Olvassa el a spec.
A spec elmagyarázza Önnek, pontosan mi minden program csinálnak.
>> Például generate.c egy olyan program hogy jön a PSET.
Ugye nem kell hozzányúlni, de meg kell értenie, hogy mit csinál.
És generate.c, minden csinál van sem véletlen szám generálás
vagy lehet, hogy ez egy mag, mint egy Előre megbeszélt számot tart,
és ez generál több számot.
Szóval van egy sajátos módja végre generate.c amelyben
szeretne, csak egy csomó számok Önnek, hogy tesztelje a más módszerekkel tovább.
>> Tehát, ha akarta, a Például, tesztelje a lelet,
amit szeretne futni generate.c, generál egy csomó számot,
majd futtassa a segítők funkciót.
Az Ön segítők feladata, ahol te fizikailag kódot írni.
És gondolom, segítők, mint egy könyvtár fájl írsz, hogy find hív.
És így belüli helpers.c, akkor do keresés és válogatás.
>> És akkor fogsz lényegében Csak őket együtt.
A specifikáció megmondja, hogyan kell tedd, hogy a parancssorban.
És akkor képes lesz arra, hogy tesztelje vagy Nem a sort és a keresési dolgozik.
Hűvös.
Valaki már elkezdődött és felmerült problémák és kérdések
nekik van most ezzel?
OKÉ.
>> Közönség: Várj.
Kérdésem van.
>> ANDI Peng: Igen.
>> Közönség: Szóval elkezdtem A lineáris keresés helpers.c
és ez nem igazán működik.
De aztán később megtudtam mi csak kell törölni, és nem bináris keresés.
Tehát nem mindegy, ha ez nem működik?
>> ANDI Peng: Rövid válasz: nem.
De mivel mi vagyunk nem--
Közönség: De senki ténylegesen ellenőrzi.
ANDI Peng: soha nem vagyunk fog látni.
De akkor érdemes tenni arról a keresést dolgozik.
Mert ha a lineáris keresés nem működik,
akkor jó esélye van a bináris keresés nem fog működni is.
Mert van hasonló logika mind a ketten.
És nem, ez nem igazán számít.
Tehát az egyetlenek, akkor kapcsolja A sort a bináris keresés.
Igen.
>> És azt is, sok gyerek volt megpróbálnád fordítani helpers.c.
Te valójában nem engedélyezettek erre, mert helpers.c
Nincsenek fő funkciója.
És ezért csak akkor ténylegesen összeállítása
generál és megtalálni, mert megtalálják hívások helpers.c és a funkciók benne.
Szóval, ami hibakeresés A fájdalom a seggét.
De ez az, amit tennünk kell.
Közönség: Csak, hogy minden, ugye?
ANDI Peng: Tudod csak hogy minden is, igen.
OKÉ.
Szóval ennyi szempontjából milyen A PSET azt kéri, hogy mindenki tegye.
Ha bármilyen kérdésed van, nyugodtan kérdezz meg szakasz után.
Én itt leszek, Mert mint 20 perc.
>> És igen, a PSET a nem is olyan rossz.
Srácok jónak kell lennie.
Ezek, csak követniük.
Valami van értelme a logikus, hogy mi történniük kellene, és akkor rendben lesz.
Ne legyen túl félek.
Van egy csomó kód Már írt ott.
Ne legyen túl félek, ha nem megérteni, mi minden jelent.
Ha ez a sok, ez teljesen rendben van.
És jönnek munkaidőben.
Segítünk, hogy egy pillantást.
>> Közönség: Az extra funkciók, ne nézzük ezeket fel?
>> ANDI Peng: Igen, ezek a kódot.
A játékban 15, fele ez már írt neked.
Tehát ezek a függvények Már a kódot.
Ja.
Minden rendben.
Nos, sok szerencsét.
Ez egy undorító nap.
Így remélhetőleg nektek nem érzem túl Rosszul bent és kódolás.