>> [Zenelejátszási]
>> David J. MALAN: Ez CS50.
És ez az a hét elején három.
Tehát van egy csomó izgalmas dolgokat, hogy fedezze ma.
Sok lehetőséget önkéntesek a színpadon.
És végül, a ma Nem a kódot egyáltalán.
De ez a gondolatok, és ez körülbelül algoritmusok,
és valóban hozza vissza néhány tanulságait héten nulla,
ahol emlékszem, mi vezette be ezt a szörnyűséget.
És hitelfelvételi ihletet attól, hogy kezdeni
megoldására egyre kifinomultabb problémákat algoritmikusan.
De először, egy pár bejelentések.
Tehát az egyik, ha szeretne csatlakozni CS50 személyzete és az osztálytársak ebédre
ez a péntek, itt és Cambridge és New Haven,
kérjük, látogasson el a pálya honlapján, ahol egy URL megtalálható.
Előadás szerdán lesz Nem lehet itt Sanders.
Ez lesz csak online, így ráhangolódni a CS50 honlapján,
hogy itt Cambridge vagy New Haven is.
>> És akkor a probléma meg két már a kezedben.
Ha még nem merültem a még engedjék meg, kínálnak a határozottan megfogalmazott javaslatot
hogy különösen most, A probléma határozza előre,
ha tényleg akar kezdeni most, ha nem pancsolás egy kicsit a hétvégén, vagy előzetes
amikor először kimenni Pénteken, mert akkor
találják, hogy ők nem feltétlenül egyre hosszabb vagy nagyobb kihívást per
se.
Azt hiszem, rájössz, hogy Általánosságban, azok hajlamosak arra, hogy durván
körül ugyanannyi idő.
De ez persze függ a diák, és ez
függ a gondolkodásmód amellyel megközelíteni.
De mindig, fogsz hogy belebotlik néhány falat,
és máris megy, hogy elérje néhány hiba, és te csak
Nem lesz képes túl lesz rajta egy bizonyos ponton.
És ez rendkívül értékes, hogy képes a lépésre, gyere vissza másnap,
megy munkaidejében hozzászólás CS50 Beszéljétek vagy hasonló, hogy valóban kap feloldják.
Tehát hogy tartsa szem előtt.
Kezdve legkorábbi lehető a legjobb dolog, amit tehetünk.
Tehát itt van, ahol elkezdtük az osztály, mint a heti nulla.
És tudjuk, hogy egy önkéntes itt, hogy segítsen nekem megtalálni mikrofonok?
OKÉ.
Állva már.
Gyere fel.
Találd ki, hogy ez hogyan fog működni.
Mi a neved?
ALAN ESTRADA: Alan Estrada.
David J. MALAN: Alan Estrada.
Gyere fel.
Örvendek.
ALAN ESTRADA: Örülök, hogy találkoztunk.
David J. MALAN: És itt lennél velünk héten nulla, persze.
ALAN ESTRADA: voltam.
Voltam.
>> David J. MALAN: Így lehetne mész előre, és megtalálni a számunkra Mike Smith,
amilyen gyorsan csak lehet?
Amilyen gyorsan csak lehet.
Szó tépte a problémát félbe, ahogy kell.
>> ALAN ESTRADA: Hm.
David J. MALAN: Szó szerint tépte a probléma felét.
>> ALAN ESTRADA: Oh.
Mm.
Nagyon jó.
>> David J. MALAN: OK.
Jó.
Köszönöm.
ALAN ESTRADA: Nagyon jó.
OKÉ.
>> David J. MALAN: És így most, amit szűkítették le
fele a méret a problémát.
Most vagyunk egészen a negyede.
Figyelsz, hogy melyik oldalon vagyunk tartani?
>> [Nevet]
>> ALAN ESTRADA: Igen, én think--
>> David J. MALAN: Mit részén vagyunk itt?
ALAN ESTRADA: nyaksál, így van.
>> David J. MALAN: OK.
De Mike Smith megy hogy miután kipufogócsövek.
Na--
>> [Nevet]
>> Minden rendben.
ALAN ESTRADA: Hol keresünk?
David J. MALAN: Mike Smith.
ALAN ESTRADA: Mike Smith.
David J. MALAN: Most mi vagyunk a sebészeti.
Most, orvosok.
Most--
>> ALAN ESTRADA: Let's- menjünk igazi.
Real.
>> David J. MALAN: Real.
OKÉ.
Ha szüksége van a Real.
Most, merre van Mike Smith?
>> ALAN ESTRADA: Ez így.
>> David J. MALAN: Merre?
ALAN ESTRADA: Várj.
M is-- ugye?
Elkezdtünk with--
>> David J. MALAN: Igen.
Ők maradt.
A jobb.
>> ALAN ESTRADA: Igen.
>> David J. MALAN: Szóval Mike itt.
ALAN ESTRADA: Mi?
>> [Nevet]
>> Rossz példa srácok.
Bocsánat.
David J. MALAN: Ez megtanít hogy kiugrik a széket.
>> ALAN ESTRADA: Oh.
Ó.
Elkaptalak.
Ó.
Ez is-- OK, hoztam neked.
Smith itt?
>> David J. MALAN: Smith, köszönöm.
Szóval fogom tartani keresi fel Smith?
>> ALAN ESTRADA: Ó, igen.
Nem nem nem.
Oh ne.
Ez az enyém.
>> David J. MALAN: Ó, megvan Smith.
OKÉ.
>> ALAN ESTRADA: Igen, Van Smith itt.
Bocs, srácok.
Azt hittem Michael-- vagyunk kerestek Michael.
Bocsánat.
>> David J. MALAN: Nem baj.
Rendben, most mi vagyunk a Paccini and Sons.
>> ALAN ESTRADA: Paccini és fiai.
David J. MALAN: csak te és én már ezen.
OKÉ.
Keresse meg minket Mike Smith.
Smith.
>> ALAN ESTRADA: Smith.
>> David J. MALAN: Smith.
Mi vagyunk a K szeméthez.
ALAN ESTRADA: Vacak.
Ó.
Ez el fog tartani egy darabig.
>> [Nevet]
David J. MALAN: Cipő.
Mi vagyunk a cipő.
>> ALAN ESTRADA: Most már gonna--
>> David J. MALAN: Szép.
ALAN ESTRADA: Which--
[Nevet]
Ó, ez nagyszerű.
[Nevet]
>> David J. MALAN: Nem baj.
>> ALAN ESTRADA: Ó, ez jó.
Nem hiszem, hogy fogok Van PSAT haverok után.
David J. MALAN: Jó.
Sporting.
ALAN ESTRADA: Sporting.
Um, L, M, N, O, P.
David J. MALAN: OK.
Úgyhogy szakadjon ennek a fele.
Oké.
Ez a vége rosszul egyébként, mert Mike Smith nem lesz a sárga lapok.
>> ALAN ESTRADA: Ó.
>> David J. MALAN: Nem, nem baj.
De nézzük úgy, mintha ő ezen az oldalon.
Tehát most, hogy már szűkítették a problémát le az egyik oldalon, és azt találtuk, Mike Smith.
>> [Éljenzés]
Rendben köszönöm.
OKÉ.
Ez volt rendkívüli.
De ez még mindig gyorsabb mint a lineáris keresés,
ahol kezdjük meg a A könyv elején,
és haladunk utunkat balról jobbra, végül keres Mike Smith.
És így, ha a telefonkönyvben volt talán 1000 oldal,
talán ez volna nekünk 10, vagy úgy oldalon könnyek.
>> De lehet, hogy tőkeáttételes megérintette a feltételezés
alatt minden, hogy ami azt hogy a telefonkönyv előre mi volt?
Közönség: Rendezés.
David J. MALAN: Ez válogatni.
Jobb?
Ez ábécé-sorrendben, így hogy az összes ilyen nevek és számok
vannak sorolva a A. a Z, és betűrendben között.
De ma, hogy most megkérdezzük A kérdést, nos,
Milyen volt a Verizon vagy a telefon cég kap ez az állapotban?
>> Mert az egy dolog, hogy felerősítse hogy a feltételezés, és ezért,
megoldani egy problémát egy algoritmus hatékonyabban.
De soha nem kérdezte héten nulla, nos,
mennyibe került ez költsége Verizon vagy valaki más
kap, hogy a telefonkönyv rendezett sorrendben?
>> Jobb?
Nem számít, ha felnézett Mike Smith
szuper gyors, ha ez visz egy évben rendezni az oldalakat kezdetben.
Jobb?
Lehet, hogy azt is csak szitál egy randomizált telefonkönyv,
ha lesz szuper drága szortírozni.
Tehát, ha tudjuk, hogy egy másik önkéntes.
Vessünk egy pillantást fel itt hogyan might-- gyere up-- hogyan
talán megy a válogatás ezeket.
>> És ha Jordan ténylegesen csatlakozzon hozzánk itt a színpadon.
Gyere fel egy pillanatra.
Mi a neved?
Caroline: Caroline.
David J. MALAN: Caroline, gyere fel.
És máris csatlakozott én és Jordan itt.
Caroline, köszönöm.
Minden rendben.
Szóval mi van itt Caroline 26 kék könyvek
hogy FAS használ adminisztrálni Bizonyos záróvizsgák.
Ezek egyre nehéz találni, de mit tettünk előre
az, hogy már fel valakinek a nevét az első az egyes ilyen,
de már tartotta egyszerűek majd kidugta a teljes nevét.
Tehát tenné a személy nevét L, D, J, B, egészen a A-Z,
de ők véletlenszerű sorrendben.
És így ha lenne, beszél a végig a problémát, ahogy
csinálni, akkor megy előre, és rendezni ezeket a számunkra, A-tól Z-
>> Közönség: OK, így L, mint a közepén.
C kezd.
B. J előtt L. B, Q.
>> David J. MALAN: tartsd meg elgondolkodott egy pillanatra.
Mivel egyébként, ez csak Érdekes, hogy te, én, és a Jordan.
Ott vagyunk.
Közönség: [hallható].
R.
David J. MALAN: OK.
Mit csinálsz?
>> Caroline: M után jön O.
>> David J. MALAN: OK.
>> Caroline: O.
David J. MALAN: O, jó.
>> Caroline: E.
>> David J. MALAN: E, F. Igen.
>> Caroline: T, U, V
>> David J. MALAN: V, T, U, V Tehát úgy néz ki, mint te vagy making-- tartani fog.
Úgy néz ki, hogy még van egy nagy halom ide,
és milyen egy nagy halom ott.
Tehát az első felében az ábécé, második felében az ábécé.
OKÉ.
Jó.
Kind ketté a problémát kettő.
M, N, X. Igen.
Caroline: K.
David J. MALAN: OK.
K. Szóval fajta kiválasztása sorban egymás után,
megvalósítják azt balra vagy jobbra, vagy Z folyik a padlóra.
OKÉ.
>> Caroline: Z folyik a padlóra.
>> David J. MALAN: OK.
Y folyik a padlóra.
Most már tudjuk tenni X.
>> Caroline: G.
David J. MALAN: G megy a bal.
S lesz jobb.
Rendben, egy megy végig maradt.
>> Caroline: A, B, C, D.
>> David J. MALAN: Most jó.
Van A, B, C W folyik odalent.
Rendben, T.
>> Caroline: H, I, J.
David J. MALAN: H, I, J Jó.
Caroline: A központban, én gonna--
David J. MALAN: OK.
Tehát most, megyünk a fajta A eleget a különböző cölöpök.
Tehát A-C, akkor látom D, és E és F, valamint a G, és H, és I. Nice.
J, K És akkor ez a halom fejjel lefelé, de ez rendben van.
Persze.
Mi lehet vágni néhány sarkok.
OKÉ.
És akkor mi van szüksége W, X, Y, Z
>> Caroline: Igen.
>> David J. MALAN: Kitűnő.
Szóval egy nagy köszönet Caroline válogatás ezeket.
>> [Éljenzés]
>> Köszönöm.
Köszi szépen.
Tehát most nézzük meg egy pillanatra hogyan Caroline széjjeljárt, hogy
és pontosan mit is képesek voltak az alábbiakra: hogyan
voltak képesek megoldani, hogy probléma, amikor mi éppen
adott egy csomó véletlen bemenetre.
>> Nos, úgy tűnik, van Volt egy kis rendszer van?
Jobb.
Így a korábbi leveleket az ábécé, a lány
volt, amivel a bal oldalon, és a Később betű az ábécében,
ő rakta be a jobb.
És amint rájött, Néhány közeli betűket, akik
hogy megy jobb egymás mellett, ő is tesz azok érdekében.
És így egyfajta kellett ezeket a kis halom sorba rendezett bemenetek előforduló.
>> És ez az egész, mint amit a legtöbben emberek tennék.
Azt a fajta keresgélést meg, és mi lenne egyfajta mechanizmust.
De lehet, hogy nehéz írni le egy képletet önmagában.
Úgy éreztem, egy kicsit több szerves annál.
Szóval lássuk, mi most megkötött A probléma a kevesebb bemenettel.
>> Ahelyett, hogy 26, nézzük tenni valamit sokkal kevesebb
csak azt mondják, hét, mögötte ezek az ajtók, hogy úgy mondjam.
Van csak hét számot?
És ha a cél most kezét az, hogy megtaláljuk az érték,
lássuk, milyen hatékonyan mehetünk körülbelül ezt.
És lássuk, mi most akkor kell alkalmazni, néhány számot,
vagy néhány képletek, amelyekkel leírására hatékonyságát a telefonkönyvben
algoritmus, mi vizsgát könyv algoritmust, és általánosabban információk megtalálása.
>> Tehát erre, hadd menjen előre, és az érintőképernyőn át ide,
elvállal egy web böngészőt, Pontosan ez a hét ajtó.
És ha tudnánk egy másik önként gyere ide,
Már fel ugyanezek ajtók ide.
Gyors önkéntes.
>> Ez one-- demók mennek a gyorsabb és gyorsabb most.
Gyere le.
Mi a neved?
TREVOR: Trevor.
>> David J. MALAN: Trevor?
Rendben, Trevor, gyere le.
Tehát Trevor önként ide csinál egy hasonló probléma, de az egyik, hogy
korlátozottabb, és ez fog hogy lehetővé teszik számunkra, hogy megpróbálja hivatalossá most
A folyamat válogatás ezeket a számokat.
>> Szóval Trevor, örülök, hogy találkoztunk.
Tehát itt van egy tömbben, így a beszélnek, egy listát a hét ajtók.
Menj, és talál minket száma 50.
Majd miután az a tény, mondja el, hogyan találta meg.
Amennyiben be-- minden rendben.
Igen, ez az egy van?
UH Oh.
OKÉ.
Ön kattintott, hogy az egyik.
Jó.
>> És jó.
Most már kattintott, hogy az egyik.
És hadd adjak a mikrofont, úgy, hogy ez csak egy pillanatra.
Menj előre, és kattintson a a szomszédban, hogy kíván.
Igen, jó.
TREVOR: Tudok unclick egy ajtót?
David J. MALAN: Nem, nem tudod unclick.
TREVOR: OK.
Ezt.
David J. MALAN: Hol akarod, hogy menjen?
Melyik az?
>> TREVOR: Ez az egyik.
>> David J. MALAN: No.
>> TREVOR: OK.
Ezt.
>> David J. MALAN: Igen.
Az jó volt.
Minden rendben.
Tehát mi volt az algoritmus vagy eljárás ezt, Trevor?
>> TREVOR: Én most ment át ajtók, amíg találtam egy 50.
David J. MALAN: OK.
Kiváló algoritmus.
Szóval ez rendben van.
Mert valójában, ha elárulom, mi van mögött két másik ajtó, mit
találunk itt az, hogy már csak véletlen bemenet.
Szóval ez volt tulajdonképpen a jó, mint lehetne még.
És valóban, van jobb, mint a kimerítően keres az egész tömböt,
mert ez lett volna igazán szerencsétlen, ha megütötte száma
50 az utolsó ajtó.
De mi lenne, ha ahelyett, kaptál egy feltételezés.
Tegyük fel, hogy azt a fajta összes ezek az ajtók körül,
úgy, hogy a számok rendezve ebben az időben,
de ezúttal ez valójában egy different-- ebben az időben,
mert tulajdonképpen ez válogatni az Ön számára.
És most a cél kéznél az, hogy elérje a szám 50.
>> TREVOR: OK.
>> David J. MALAN: Mi Ön algoritmus lesz?
>> TREVOR: Nos, ha ez válogatni, ez sem megy,
hogy be-- ha legnagyobb a legnagyobb, csökkenő, ez lesz az első,
vagy ha ez ellentétes, ez lesz az utolsó.
Szóval én csak érintse az ajtót, és akkor csak érintse az utolsó ajtó.
David J. MALAN: Kitűnő.
Minden rendben.
Így találtunk száma 50.
Így amint tudta, őket válogatni, akkor
képesek voltak mozgósítani ezt a feltételezést.
Tehát ők túl sokat, mint A telefonkönyv példa.
Amint van, még egy kis probléma, mint ez,
A bemenetek előválogatva, tudjuk valóban megtalálja az értéket vitathatatlanul
hatékonyabban.
>> És én nem mondtam el, ha azt válogatni kis és nagy, vagy nagy a kis,
És ez így volt, nagyon ésszerű kezdeni az egyik végén, vagy a másik
hogy valóban úgy találják, hogy célérték.
Szóval köszönöm, hogy Trevor is.
És én propose-- szépen tenni.
Van egy kis klip, valóban, hogy között a kedvenc pillanatait CS50,
ahol néha ezek a demók Nem egészen a terv szerint megy.
És valóban, most én húzta fel a rossz interfész
amellyel az érintőképernyő használatához.
Szóval ez az én hibám volt ott.
>> Szóval ez lehetővé teszi majd a jövő évi csipesz
hogy miért voltam kattintva saját képernyőjén.
De vessünk egy gyors pillantást hogy mi történt tavaly
Jay, aki jött, sok mint Trevor itt, önként,
és ebben a rövid klip, látni fogod hogy ez ugyanaz a demo nem egészen
leleplezik a hasonlóan tanulságokat.
[Videó lejátszás]
-Minden Azt akarom, hogy ne most találni nekem, és nekünk,
Tényleg, a szám 50 egy lépéssel egy időben.
>> -A 50-?
>> -A Száma 50.
És akkor mutatják mi mögött minden ilyen ajtók
egyszerűen érjen hozzá az ujjával.
Basszus.
>> [Nevet]
>> [Lejátszás vége]
David J. MALAN: Úgy, hogy nagyon jól ment.
Ezek voltak a szétválogatás nélküli ajtók.
És Jay, természetesen, találtam túl gyorsan.
Trevor nem sokkal jobb munkát szempontjából egy tanítható pillanatra,
hogy úgy mondjam, ebben az évben hosszabb időt vesz igénybe, hogy megtalálja.
Persze, akkor adta Jay egy második esélyt,
ami által rendezett az ajtók, mint ahogy tettük Trevor,
és Trevor tette szuper jól ebben az időben.
De Jay csinálta fele olyan gyorsan.
[Videó lejátszás]
-A Cél most az, hogy is talál minket száma 50,
de azt algoritmus, és mondja el, hogyan fogsz róla.
>> -OKÉ.
>> -És Ha megtalálja, akkor tartsa a filmet.
Ha nem találja meg, akkor add vissza.
>> -man.
>> -Ó!
>> - [Hallható] OK.
Így fogok, hogy ellenőrizze a végek Először határoztam meg, ha there's-- Oh.
>> [Taps]
>> [Lejátszás vége]
David J. MALAN: OK.
Tehát a válogatás ajtók egyértelműen vezet a nagyobb hatékonyság érdekében.
És így, kétszer olyan gyorsan az, amit akartam ott.
És így Jay szerencséje volt mindkét alkalommal.
És ő is szerencsém volt, hogy az utolsó év, én elrendelte a Blu-ray lemezek
hogy valóban ad ki.
Sajnálom idén is nem volt azonos, Trevor.
De még jobb volt néhány évvel ezelőtt.
És néhányan talán tudják ezt fickó, Sean, aki amikor ő volt a CS50,
megtámadta a pontos Ugyanez a probléma, jóllehet SD,
mint hamarosan látni, vissza a nap.
És rájössz, hogy nem csak hogy ő egy kicsit tovább tart, mint Jay,
egy kicsit hosszabb, mint Trevor, ez volt ténylegesen ezt a csodálatos lehetőséget
hogy vegyenek szinte mindenki a tömegben a la ár megfelelő, ösztönözve
neki, hogy megtalálják a szám, amit kerestek.
Nézzük. hogy egy gyors pillantást.
>> [Videó lejátszás]
>> -OKÉ.
Tehát a feladat itt, Sean, a következő.
Én mögött ezeket a ajtók száma hét.
De élj néhány ilyen ajtók valamint más negatív számok.
És a cél az, hogy úgy gondolja, E felső sorban a számok
mint csak egy tömb, vagy csak szekvenciája darab papír
számokkal mögöttük.
És a cél az, csak használ a felső tömb van, keresse meg a hetes szám.
És mi majd lesz kritika hogyan kezdjen csinálja.
-Minden rendben.
-Find Velünk a hetes szám, kérem.
Nem.
Öt, 19, 13.
>> [Nevet]
>> Ez nem egy trükkös kérdés.
Egy.
>> [Nevet]
Ezen a ponton, a pontszám nem túl jó, így akár meg is tartani fog.
Három.
>> [Nevet]
>> Tovább.
Őszintén szólva, nem tudok segíteni, de csoda, mit is gondol, so--
>> [Nevet]
Csak a felső sorban, így megvan a három bal.
Szóval rám talál hét.
>> [Nevet]
17.
Hét.
>> [Taps]
>> Minden rendben.
>> [Lejátszás vége]
>> David J. MALAN: így sikerült nézni ezeket egész nap.
És persze, néhány Az idei bemutatók talán
Most a végén a következő évi videó is.
Így most nézzük a ténylegesen összpontosítani algoritmusok
Itt, és nézd meg, mi nem Most kezd hivatalossá
hogyan tudunk menni körülbelül szerzés adatainkat ebbe az állapotba, hogy ez válogatni,
hogy aztán végül, mi is valójában keresni azt hatékonyabban.
És bár megyünk használni viszonylag kis adathalmazok,
mint a nyolc számban vagyunk Van itt a fórumon,
végül ugyanezek az elképzelések alkalmazni 1000 bemenet, egy millió be-,
4 milliárd bemenetek, mert az algoritmusok lesznek alapvetően ugyanaz.
>> És így ez az utolsó lehetőséget önkéntesek ma,
de talán a leginkább érintett az egyik, amelyhez szükség van a nyolc önkéntesek
hogy jöjjön fel és járj minket a folyamata a válogatás, amit hamarosan
legyen a következő zene áll itt.
Hadd kezdjem vissza ide.
>> Tehát az egyik a turquoise-- zöld ez?
Te elkövető?
Kettő.
Gyere le.
OKÉ.
Három.
Négy.
Hadd me-- OK, öt.
Te jelölése alapján a barátod.
Hat, hét, illetve nyolc.
Gyere fel.
Minden rendben.
Köszönöm szépen.
Gyere fel.
>> Minden rendben.
Szóval mi van here-- és ez az egyik több kínos is,
mivel ez megköveteli, hogy a humor nekem csak egy kis idő.
Te leszel az első.
Mi a neved?
>> ANNAN: Annan.
>> David J. MALAN: Annan.
David.
Mi a neved?
>> Joseph: Joseph.
>> David J. MALAN: Joseph, Ön a két számot.
>> Serena: Serena, a hármas számú.
Stefan, száma négy.
CYNTHIA: Cynthia.
David J. MALAN: Cynthia, az ötödik.
[Hallhatatlan]
David J. MALAN: [hallható].
David, a hatos.
Matt: Matt.
David J. MALAN: Matt száma hét.
És?
>> WAVERLY: Waverly.
>> David J. MALAN: Waverly, száma nyolc.
Minden rendben.
Ha could-- Hoppá.
Ha az összes, mint a első kihívás, ott
Nyolc zenepavilonokkal Itt a közönség felé.
Ha lehetne tenni a számok ezek zene áll, oly módon,
hogy közvetlenül az ugyanolyan számokat a táblán.
Úgyhogy győződjön meg magatokat kinézni, hogy a teszed a szám a következő zene
Itt áll.
Kiváló eddig.
>> Kitűnő.
OKÉ.
Tehát most, megyünk kérni a kérdést néhány különböző módokon.
Hogyan tudjuk járni válogatás ezek az emberek itt?
Mert volt néhány megközelítés korábban, ahol voltunk
fajta, hogy két különböző vödrök.
És akkor általában piecing dolgokat együtt.
Amint láttuk, a két szám hogy összetartoznak,
rakjuk őket össze.
Két betű, hogy összetartozunk.
>> De lássuk, ha Nem formát ennek,
hogy mi végső soron néhány pszeudo-kód lesz,
amellyel meg lehet oldani ezeket a problémákat.
Szóval most én keresem ki ezeket a számokat itt.
És látok egy csomó hibát.
Végül, szeretnék egyet a bal és nyolc a jobb oldalon.
>> És így nézem E két, négy és két.
És mi a probléma, nyilván?
Igen.
Na.
Két nyilván szó előtt Négy, hogy tudd, mi?
Először is hadd vessen egy kapzsi megközelítést, ha úgy tetszik, ugyanúgy, mint probléma
állítsa one-- ha visszaemlékeztek a Standard Edition Probléma Set One,
ahol én csak helyben megoldani a problémát ez itt előttem
és nézd meg, hova vezet engem.
>> OKÉ.
Tehát két és négy, hadd menjen előre, és csak csere ti ketten.
Ha fizikailag mozgatni magad és papír,
Úgy tűnik, hogy ütött az listához jobb állapotban.
>> Most, hogy jók.
Megyek lépni, négy és hat, jól néz ki.
Nem probléma.
Hat és nyolc, az OK gombra.
Nyolc és egy másik probléma.
Mert ami igaz, körülbelül nyolc és egyet?
Egy szó nyolc előtt, és így mit tegyünk?
Nézzük cserélni a két.
Egy-nyolc.
És most, fogok tartani fog.
Én fogom tartani előretekintve.
És lássuk, mi történik.
Nyolc és három, a Természetesen elromlott.
Nézzük csere.
Nyolc és hét, természetesen.
Nem működik.
Nézzük csere.
Nyolc és öt, persze, hadd csere.
Minden rendben.
Lista.
Igen?
>> OK, nyilván nem.
De ez egy kicsit jobb, ugye?
Mert észre, hogy mi történt.
Minden alkalommal, amikor végre a swap, egy kisebb számú fajta főzött, hogy így,
és minél nagyobb számú átszűrődő így, vagy mi
kezdeni azzal vezetünk a balra vagy vezetünk a jobb.
>> Most, hogy ez nem elég, mert a legjobb egy számot talán
költözött egy helyen előre, vagy a legrosszabb esetben,
Számos volna költözött egy helyen további.
Szóval tudod mit, ez a fajta A nagyon jól működött eddig.
Hadd próbálja meg újra.
Két és négy, ők az OK gombra.
Négy és hat, ők az OK gombra.
Hat, egy, elromlott.
Úgyhogy cserélni ti ketten.
És most, észre a probléma vagy már egy kicsit jobban meg újra.
Hat és három, elromlott.
Nézzük cserélni ti ketten.
Hat-hét, te jó.
Hét és öt, persze, elromlott.
Hét és nyolc, annak érdekében.
És most, talán kell Ehhez még néhány alkalommal.
És valóban, gondolom magatoknak Talán hányszor maximálisan
Lehet, hogy én már járni oda-vissza?
>> Majd vissza kell térni.
Tehát két és négy még mindig OK.
Négy és egy, dehogy.
Nos, nézzük csere.
És ismét, észre vizuálisan az egyik fajta fortyogó
balra, ahol lennie kell.
Négy és három csere.
Négy-hat.
Hat és öt csere.
Hat-hét.
Hét és nyolc jók.
>> Jó.
Mi megvagyunk, még jobb.
Tehát lássuk.
Most már két és egy.
Természetesen cserélni.
Két és három, három és négy, négy és öt, hat, hét, hét és nyolc.
Jó.
És tudod mit?
Mert elkövettem egy változás van, hadd tegye józanság csekket.
Hadd menjen végig vissza az elejére.
OKÉ.
Az egyik, two-- Ja, látod?
Valami nem volt rendben.
Három, négy, öt, hat, hét, nyolc.
És ebben az utolsó lépés, a kényelmes az én most
azt állítva, hogy válogatni?
OKÉ.
Vizuálisan, ez teljesen igaz.
De funkcionálisan, mit nem is csak úgy történnek
ebben az utolsó lépés, amely lehetővé teszi annak igazolására, hogy ez a lista valóban
válogatni?
>> Mit csináltam, vagy nem tudja ezt az utolsó menetben?
Közönség: Nem volt változás.
David J. MALAN: Sajnáljuk?
Közönség: Nincs változás.
David J. MALAN: Nem volt változás.
Így lenne hülye vagyok, hogy Ehhez ugyanazt az algoritmust újra
ha nem tesz megváltoztatja az első alkalommal.
És az állam nem változott.
Bizonyára nem fogok tenni bármilyen változás a második alkalommal.
És így, most már biztonságban mondani, lista.
>> És valóban, ez most valami, amit akkor általában
Hívás buborékos rendezést, amely szerint a páros, korrigálta a hibákat újra,
és újra, és újra, és meg menj oda-vissza,
és oda-vissza, amíg meg nem hogy nincs ilyen csereügyletek, ekkor
Ön biztos lehet benne, igen, én befejezte rögzítéséről az összes hibát.
Nézzük reset és megpróbál egy másik megközelítés.
Ha a srácok mehet vissza A megrendelés volt egy perce
amely úgy nézett ki, mint ez.
Most, vessünk egy megközelítést a kicsit több, mint a vizsgán könyvet,
ahol voltunk állandóan kiválasztja a betűvel
hogy azt a fajta akarta foglalkozni másikra.
Talán egy nagy levél, mint az A, illetve az alacsony levelet Z.
>> Szóval mindenki vissza ebben a sorrendben.
És most hadd csináljam ezt.
Lássuk, tudom, hogy van nyolc számból itt.
Megyek megy előre, és Csak szándékosan válasszon
A legkisebb eleme.
Jobb?
Úgy tűnik, ez az intuitív is.
Miért nem találom a legkisebb elemet, tedd ahová tartozik,
akkor kap a következő legkisebb eleme, tedd ez, ahová tartozik, és csak ismételni.
>> Mert ösztönösen, hogy is működnie kell.
Tehát négy, ez egy nagyon kevés.
Megyek, hogy emlékezzen, ahol ez.
Várj egy percet.
Két kisebb.
Hadd ne feledje, ha két van, és felejtse el a négy.
Majd foglalkozik, hogy később.
Hat, nem vagyok érdekelt.
Nyolc, nem vagyok érdekelt.
Az egyik az én új kis számot.
Így fogok visszaemlékezni, hol az egyik.
Három, nem érdekli.
Hét, nem érdekli.
Öt, nem érdekli.
>> Tehát nélkül esett le A színpadon idén,
Megyek megragad száma one-- és mi volt a neve?
>> ANNAN: Annan.
>> David J. MALAN: Annan.
És ha tudna csatlakozni hozzám az elején a lista,
mondjuk, hol tartoznak.
Unfortunately-- mi a neved?
>> STEFAN: Stefan.
>> David J. MALAN: Stefan van az út.
Szóval mielőtt Stefan megoldja ezt probléma, mit tegyünk?
Mit csináljunk Stefan?
>> Közönség: [hallható].
David J. MALAN: OK.
Így lehet megtenni.
Mi lehetne egyfajta vegye Stefan és ő négy, és csak tedd egy változóban
és tartsd meg az bizonyos mennyiségű időt,
ezáltal teret számú.
És ez nem is rossz.
Én azt sugallhatja, hogy miért nem mi csak tesz Stefan itt?
Miért lehet ez sérti az egyik Az ötletek kezdtük
beszélünk utoljára, a múlt héten?
Igen?
>> Közönség: [hallható].
>> David J. MALAN: Nincs indexe érte.
Ha úgy gondolja, ennek, sőt, mint tömb, ez olyan, mint negatív,
így nincs memória ténylegesen Itt, ha ez valóban egy olyan tömb,
mint mi nyilvánította a múlt héten előadást.
Tehát nem ezt.
Lehet, hogy tárolja egy változóban.
>> Vagy tudod mit?
Hallottam, hogy valaki mást javasoljuk.
Mi mást tehettünk volna Stefan?
Miért nem csak kilakoltatására neki, és tedd őt, ahol számú volt.
Tehát, ha azt szeretnénk, hogy menjen oda.
És valóban, ez egy nagyon jó megoldás.
Most egyrészt, én már ilyen A tett a probléma rosszabb.
Négy most távolabb re, ahol lennie kell.
Meg kell felé a másikon.
>> De tudod mit?
Hogy lehetett volna a balszerencse.
Talán nyolcas itt volt.
És igen, talán mi lenne ütött szerencsés,
és tolta nyolc közelebb a végére.
Így a végén a nap, ez a fajta minden átlagosan ki.
Nem kell törődnünk négy.
Csak az érdekel, most is kiválasztja a legkisebb eleme.
>> És most, mit fogok tennie, hogy felejtse el a number one
véglegesen, mert tudom, hogy a listát a hátam mögött most válogatni.
Szóval a lista a korábban mérete nyolc.
Most, ez a méret a hét.
Szóval a probléma egyre alacsonyabb, ámbár lineárisan.
Tehát most, megyek ki a jelenlegi legkisebb eleme, kettő.
Hat, nyolc, négy, három, hét, öt.
Ez volt a legkisebb eleme.
Szóval mit fogok csinálni with-- mi volt a neve?
>> Joseph: Joseph.
>> David J. MALAN: Joseph?
Fogunk hagyja József helyére.
Most megyek, mintha hogy ezek a srácok are-- is,
Tudom, hogy ez a két már rendezve.
Nézzük most összpontosítani fennmaradó lista.
Hat jelenlegi legkisebb.
Nyolc nagyobb.
Négy most a jelenlegi legkisebb.
Három most a jelenlegi legkisebb.
És így most fogom kiválasztani a három, aki is-- mi is a neved?
Serena: Serena.
David J. MALAN: Serena, ha tehetnéd fogd meg a számot és swap with--
Kalsang: Kalsang.
David J. MALAN: Kalsang.
Gyere vissza, és mi vagyunk fog cserélni a kettő között.
És most, tegyük ezt a robotpilóta.
Én megyek, és hagyja, hogy a srácok válassza ki a következő legkisebb eleme.
Dun, ordas, ordas, ordas.
A négyes számú, mit tegyünk?
Kitűnő.
Most megyek, hogy egy másik labdát.
Dun, ordas, ordas, ordas.
Látom ötös a következő kisebb.
Most megyek újabb passz.
Dun, ordas, ordas, ordas.
Hat a legkisebb.
Jó.
Hét a legkisebb.
Nincs változás.
Nyolc a legkisebb.
Kész.
>> Tehát amit az imént végzett iteratív kiválasztunk egy elemet a másik után
A végre valami, ami mi vagyunk lesz, hogy hivatalossá a kiválasztási sorrend.
És ez talán még egyszerűbb elmagyarázni,
abban a szó szoros értelmében minden, amit akarok csak tartani
oda-vissza végig a listát kiválasztásával, a következő legkisebb eleme,
amíg kész.
>> Szóval ez még egyszerűbb, talán ösztönösen, mint az utolsó.
Próbáljuk az egyik utolsó.
Ha ti is vissza magatokat a következő pozíciók
még egyszer utoljára, lássuk, ha nem tudjuk Most hivatalossá egy másik megközelítés.
Tény, akar valaki ott szeretném javasolni
hogy mást elmehetnénk csinálja ezt?
Anélkül dobált ki hívószavak vagy rendezési A választ a már ismert,
Csak ösztönösen, mit tehetünk?
>> Közönség: [hallható].
David J. MALAN: Igen.
Szóval van néhány nagy intuíció van.
Jó dolgok fognak történni, eddig a számítógép-tudomány, ha elosztjuk
és meghódítsa a problémát a választóvonal félbe, és fele-fele.
És így valóban, indulhasson erre.
És valóban, hogy ez lesz, akkor lásd, az egyik legjobb megoldás még.
De térjünk vissza, hogy nemsokára.
Tény, hogy fogunk csinálni hogy egy kicsit később ezen a héten.
Mi mást lehet tennünk azért, hogy megoldja ezt?
Szóval itt mindenki a látszólag véletlenszerű sorrendben.
Tudod mit?
Ahelyett, hogy menjen előre és hátra, oda-vissza, oda-vissza
minden egyes alkalommal, ez az érzés Csinálok a sok gyaloglás.
Miért nem tudok csak kezdődik az elején a lista,
és csak tedd négy ahova tartozik?
Szóval hadd vállalnak a pillanatban, hogy listámon csak az első eleme.
A négy válogatni ebben a pillanatban az időben, ha minden érdekel, hogy itt minden?
Ez a fajta triviálisan igaz, ugye?
Mint a listát, amely egy számot, és ez a szám négy nyilvánvalóan rendezve.
>> Szóval hadd kikötik hogy ez a lista.
De most már a többi ezt a listát.
Tehát most, találkozom kettő.
Hol két nyilvánvalóan tartoznak tekintetében négy?
Mielőtt négy.
Szóval mit lehet itt csinálni?
Mi is a neved?
>> Joseph: Joseph.
>> David J. MALAN: Joseph, ha tudna lépést hátra
egy pillanatra a saját számát.
És most mi legyen Stefan itt csinálni?
Nézzük elmozdulás Stefan ide.
És most, hadd Joseph jönnek ide.
És most hadd állítják, hogy itt minden van rendezve.
Tehát, hasonló eredménnyel, de egy alapvetően más megközelítést.
Én még nem is látszott, mi van odalent.
Csak azt figyelembe az elemek mivel ők a kezembe,
és foglalkoznak velük.
>> Tehát most, látom a hatos.
Hol száma hat tartozik?
Van két, négy, hat.
Pontosan hol van most.
Szóval hagyjuk, hogy egyedül, és most azt állítják, hogy ez a lista egy részét
most válogatni.
És igen, ez olyan, alapvetően különbözik, hogy én csak
halad át a listát itt lineárisan, és én soha nem megduplázva vissza.
Igen.
Minden rendben.
Tehát nyolc, ahol tartozol?
Pont itt.
Tökéletes.
Tehát most, az egyik.
UH Oh.
Ez olyan, mint ez lesz drága.
Most, az előző algoritmust, Én csak cserélték az embereket.
Szóval lehet, hogy őt egészen a az elején, de utána költözött József.
De ha mozgok József, most mi lesz baj?
>> Most, én már egyfajta undone-- voltam tett egy lépést előre, majd
egy lépést hátra, mert most Joseph lenne elromlott.
Tehát lássuk ezt.
Ha lehetne számú és lépjen vissza egy pillanatra.
Hogyan tudjuk mi put-- volt a neved?
>> ANNAN: Annan.
>> David J. MALAN: Annan helyett?
Mit kell történnie tekintetében két, négy, hat, illetve nyolc?
Mindannyian kell váltani.
Tehát, ha a nyolc szeretne váltani először, majd hat, majd négy, majd kettő.
És akkor Annan, ha azt szívesen jövök ide, jó.
De itt, most már csak fajta árat fizetett
egy másik pontján az algoritmus.
Mivel utoljára a kiválasztási sort, és még buborékos rendezést,
Sétálok vissza oda, oda-vissza,
ami minden bizonnyal összeadjuk idő-bölcs, és szó szerint lépésenként.
>> Behelyezés sort, az első pillantásra úgy néz ki, mintha
szuper okosabb, az, hogy én vagyok hogy lassú, fokozatos haladást,
de nem fogom ezt oda-vissza.
De ha valaki valóban elromlott, értesítés
az összes munka csak meg kellett csinálni.
Azt kellett költözniük a fele a listát csak azért, hogy legyen hely az első számú.
Tehát ugyanazt az összeget A munka eddig is
úgy érzi, csak egy másik típusú munkát.
>> Folytassuk.
Tehát most már tudjuk, hogy mindenki egy-nyolc sorrendje.
Itt van három.
Ha szeretné, hogy vegye fel A hármas számú, lépjen vissza egyet.
És mit srácok kell tenned?
Ja.
Szóval ez egy másik egy, kettő, három lépésben.
Három egység, ameddig csak költség Számomra úgy, hogy a három most illik.
Végül hét.
>> Menjünk előre, és Ön egy lépést hátra.
Ez csak akkor fog kerülni nekünk Egy egységnyi idő alatt, de ez rendben van.
És most, öt meg fog egy kicsit drágább.
Ha azt szeretné, hogy lépjen vissza.
Meg kell mozgatni nyolc, valamint hét, illetve hat.
És akkor mindenki őt rendezve.
Szóval egy nagy kezét, hogy önkénteseink itt.
Köszönöm szépen.
>> [Taps]
>> Köszönök mindent.
Köszönök mindent.
Nézzük most, hogy mennyire költséges minden volt.
Nézzük meg talán a legegyszerűbb ilyen, buborékos rendezést.
És én azt mondom legegyszerűbb, csak azért, mert meg lehet oldani, hogy mohón mellett csak
erősít a páros probléma van.
Fix páros probléma itt, újra és újra
és újra ismételve annyi ahányszor csak tényleg kell.
>> Így kiderül, hogy a egy buborék rendezés, valamint,
hány lépést kell lennem ahhoz, hogy a Az első lépés az, hogy algoritmus?
Talán take-- nézzük see-- egy, kettő, három, négy, öt, hat, hét.
És ott van a nyolc elem van.
Tehát ez olyan, mint n mínusz 1 lépéseket hogy a lista elején
hogy a végén a lista.
>> De kiválasztási sorrend, emlékszem, hogy én vagyok az elemek kiválasztása újra és újra
és újra, hogy ez a legkisebb, Leteszem a helyén,
de aztán nem vagyok keres mögöttem újra.
Tehát úgy gondolom, hogy ez egy kicsit világosabb akkor ez az első alkalom, talán
meg kell tennie minden n mínusz 1 lépéseket hogy megtalálják a legkisebb eleme.
Aztán tedd a helyére, és én kilakoltatására aki itt volt korábban.
>> De aztán nem kell folyamatosan nézi ezt az elemet,
mert tudom, hogy ez Már a legkisebb.
Szóval, most nézd meg mindössze hét elemeket, majd hat elem,
Ezután öt elem, majd négy elem.
És így matematikailag, ha n Az elemek száma vagy számok
hogy mi kezdődött, el lehet képzelni, hogy ez ugyanaz, mint az n mínusz 1,
plusz n mínusz 2 lépésben, + n mínusz 3 lépéseket,
plusz n mínusz 4 lépésben, az összes lement csak egy lépés.
És én vagyok az utolsó ember.
>> És ha emlékeztetnek arra, hogy a sok A statisztika könyv vagy matematikai könyvek
hogy ezeket a képleteket a keménykötésben vissza, vagy előttük,
kiderül, hogy ez a sorozat fejezhető több egyszerűen
mint n-szer n mínusz 1 több mint 2.
És ez rendben van, ha ez nem élen jár a fejedben.
De ez valóban igaz.
Ez csak egy egyszerűbb módja írás is.
És aztán, ha úgy gondolja, vissza az általános iskolában
ha csak elkezd szorozni dolgokat, ez természetesen
csak n faragva mínusz n osztva 2.
Minden, amit tettem az bővíteni A kifejezések vannak.
És így írjuk át ezt a egy kicsit másképp.
Ez az n négyzethálós osztva 2 mínusz n / 2.
>> Szóval megint én vagyok csak ilyen alkalmazása Néhány számtani szabályokat is.
De észre most, hogy a legnagyobb távon ebben a kifejezésben, hogy úgy mondjam,
az, hogy n négyzeten.
Szóval igen, ez n négyzetes osztva 2, mínusz n / 2.
>> De általában, ha n lesz egy nagy érték,
Megyek állítják, hogy n négyzeten lesz a meghatározó tényező.
Ez csak lesz nagyobb mértékben járul
a lépések számát, mint n / 2.
Szóval mit értünk ez alatt?
Próbáljunk egy egyszerű példát, sőt bár a matek kap egy kicsit nagy.
>> Tehát tegyük fel, hogy 1 millió ember a színpadon, vagy 1 millió dolgot
hogy szeretnénk rendezni.
Nézzük dugja egy millió be pontosan azt a képletet
hogy hány lépést tart összesen rendezni egy millió elemek felhasználásával mondjuk,
kiválasztási sorrend.
>> Szóval mi lenne azonos képlet, mint korábban.
Én dugja egy millió, így kapok egy millió négyzethálós osztva 2,
mínusz egymillió osztva 2.
Ha tudom, hogy a matematika előre Itt van 500 milliárd
mínusz 500.000, amelyek ad nekünk 499.999.500.000,
ami elég rohadt nagy.
>> Sőt, ha összehasonlítjuk a vállalattal 499 milliárd forint, 999.000.000,
500.000 ellen eredeti érték, 500 milliárd, ez annyira rohadt közel.
Jobb? n négyzethálós osztva 2 ad us-- vagy inkább n négyzethálós osztva 2
adott nekünk 500 milliárd.
Ez elég rohadt közel a 499.999.500.000,
ami azt levonjuk ki 500.000, vagy általánosabban, kivonva le
n faragva, nem igazán nagy dolog.
Az n faragva teszi ezeket szám nőni nagyon gyorsan.
>> Nos, ez a fontos csak annyiban mint mi, számítógépes szakemberek,
általában nem fog érdekel annyira a árnyalatok ezeket a képleteket
és pontosan mi a pontos válaszok.
Mi érdekel csak, hogy tudod, mit?
Végén a nap, ez a képlet ez a sorrend n négyzeten.
>> Igen, mi elosztjuk 2 odabent.
Igen, mi levonjuk le n mínusz 2.
De a végén a nap, a kifejezés ami igazán bánt minket, és kerül nekünk
sok lépésből áll, hogy a négyzet távon.
És akkor mi van egy számítógép tudós fog általában nem
A figyelmen kívül hagyja az összes ilyen kisebb rendű tagokat,
és csak nézd meg az egyik, hogy a leginkább hozzájárul a költségek.
>> És ez a szép és jó, mert nem tudjuk Most beszéljünk sokkal nagyobb általánosság
mintegy algoritmusok, és össze lehet hasonlítani őket.
És az a tény, hogy én vagyok Ezzel a O szándékos.
Amikor azt mondom, a rend Az vagyok, konkrétan
dologra utal úgynevezett nagy O. és a nagy O
egy jelölést, hogy a számítógép tudós használ, hogy leírja
egy felső korlátot valamit.
>> Tehát ha azt mondod, hogy egy algoritmus a nagy O n faragva,
ahogy javasolt csak egy perce, hogy úton
hogy tekintve a működési idő vagy annak hatékonyságát,
ez megváltó érdekében n faragva lépéseket.
Talán több, talán kevesebb.
De ez a sorrend n négyzeten.
És ez a felső határ.
Ez nem lesz fájdalmasabb, mint ezt.
Ez nem lesz n kockára vágott, vagy 2 A n, vagy valami sokkal nagyobb.
Ez egy felső korlát akármilyen hogy a költségek.
Tehát tekintettel arra, hogy lássuk úgy ez csak néhány példa.
És ez csak egy véges lista A nagyon gyakori futásidoket
algoritmusok, ami azt jelentette, hogy bemutatnak néhány dolgot, amit
láttam már.
>> Így például, abban az esetben, kiválasztási sorrend, amit én itt azt állítva,
az, hogy a kiválasztási sorrend fut idő nagyságrendileg n négyzeten.
A legrosszabb esetben, én megyek is egy csomó véletlen számokat itt.
És ahogy láttuk matematikailag, ha folyamatosan séta
Ha a listában, a listát, kiválasztja a következő legkisebb
elemet újra és újra, ha én ténylegesen sorold fel azokat a lépéseket,
Elviszem én javasolt formulaically előtt, ez a sorrend n négyzetes
lépéseket, hogy én viszem.
>> És kiderül, hogy a buborék rendezés és beillesztés sort
ugyanolyan lassú a legrosszabb esetben.
Vegyük például, beillesztés sort, A legutolsó algoritmus foglalkoztunk,
ami volt számunkra nézd meg a elemet, majd helyezze, ahová tartozik.
Aztán megnéztük a következő elem, és bedugta, ahova tartozik.
>> Tehát úgy a lehető legjobb forgatókönyv.
Tegyük fel, hogy már én önkéntesek sorakoznak Szó szerint, mint ez, egytől nyolc,
Már rendezve.
Hány lépés az illesztési sorrend fog tartani rendezni nyolc embert,
ha megérkeznek a színpadon így néz ki?
>> Nyolc ember már válogatni.
És tudom használni behelyezés sort.
Ez az utolsó algoritmusok.
Nos, nézzük reenact igazi böjt.
Tehát, ha én itt kezdődnek, látok egyet.
Hol az egyik tagja?
Tartozik itt.
Látom kettő.
Hol kettő tartozik?
Pont itt.
Látom három.
Hol három tartozik?
Pont itt.
>> Látom négy.
Pont itt.
Öt, hat, hét, nyolc.
Nincs oka ismételni magam.
És igen, hány lépést az, hogy szempontjából n?
Ez a sorrend n lépések, ugye? n mínusz 1.
De vettem egy lineáris száma A lépés, és most kész vagyok.
Szóval ez a legjobb esetben mégis.
Mi a helyzet a legrosszabb esetben?
Milyen nyolc volt ott, hét pedig ott,
és egy, kettő pedig több mint itt, így hogy a listán volt igazán fordított?
>> Nos, mi történik valójában Ha ez a szám?
És mi nem csak egy pár példa.
Mi lenne, ha valóban a nyolcas szám itt van, és a number-- Hoppá.
Szóval mi van, ha valóban száma A nyolcas egészen át ide,
és én vagyok a behelyezés sort?
>> OKÉ.
Azt állítják, abban a pillanatban, hogy ez a hely.
De most, seven-- hol hét menni?
Persze, ez megy itt.
Szóval meg kell mozgatni nyolc alatt egy helyen.
Most hat, ahol nem is megy?
Nos, rendben.
Most azt kell mozgatni nyolc fölött egy hely, és a hét egy helyen,
és aztán lehuppansz hat.
>> Tehát az első alkalom, hogy költség nekem egy lépéssel rögzíteni a dolgokat,
akkor ez nekem két lépésben rögzíteni a dolgokat.
Hány lépés van fog tartani rögzíteni
dolgokat, hogy öt jó helyen?
Három.
Mert most már, hogy mozgatni egy, kettő, három.
Hány lépés ez fog venni hogy négy jó helyen?
4 és 5, és 6, plusz 7.
>> És így matematikailag megegyezik amit leírt kiválasztási sorrend.
Van ez a sorozat ez csak növekszik.
1 plusz 2 + 3 + 4, vagy fordítva, 7 plusz 6
plusz 5 plusz 4 összeadja a mai célú nagyságrendű n négyzeten.
>> Szóval hadd kikötik azt is, hogy buborékos rendezést is n négyzeten.
Mivel a buborék rendezés, minden alkalommal megyek át a listát,
Elviszem nagyjából hány lépést?
Minden alkalommal, amikor szó szerint séta onnan van?
Nagyjából n lépéseket.
De hányszor lehet, hogy én kell, hogy menjen végig a listán?
>> Nos, nagyjából n időt.
Talán n mínusz 1, de nagyjából n-szer.
Nos, miért van ez?
Nos, a buborékos rendezést, ha kezdjük buborékos rendezést,
A lista a lehető legrosszabb helyzetet, ami szintén teljesen
hátra, mi fog történni?
Én végig a listát, és a szám Egy tartozik egészen ott.
>> De buborékos rendezést, milyen messze egy lépni az első áthaladnak a listán?
Hány foltok nem ő kap közelebb a megfelelő helyre?
Csak egy.
Tehát, ha ilyen okból ezen keresztül, minden alkalommal át ezt az algoritmust,
Dávid véve nagyjából n lépéseket.
De hány menetben Ha a listában van
fog tartani egy buborék balra, ahova tartozik?
>> Neki mozogni, mint, N terek ezen a módon.
Szóval, csak hogy ne a válogatás a listán, Én már járni oda-vissza n-szer.
És minden alkalommal, én vagyok néztem n eleme.
Tehát nem n dolgokat n-szer nagyságrendű n négyzeten.
>> Most majd meglátjuk néhány a nadrág, hogy
ágyazódnak CS50 következő probléma állítva, egy másik megközelítés ezeket,
de most, nézzük csak úgy néhány más futási idők,
különösen, ha a válogatás is megteszi egy kis időt, hogy elsüllyed.
Mi az az algoritmus, láttunk már hogy felveszi a rendelést n lépések?
>> Mi kell egy lineáris száma A lépések, amiket láttam eddig?
Az mi?
A telefonkönyv kereső.
Az első algoritmust.
Jobb?
Hol vagyunk lineárisan keres Mike Smith?
Valóban.
Hétről nulla, amikor elkezdtem fordult egy oldalt egy időben,
és még azt is mondta, hogy ez a fajta lineáris érzés algoritmus,
és mi volt, hogy a képet a fórumon, hogy az egyenes piros vonal
és az egyenes sárga vonal, azok valóban
algoritmusok, amelyek a nagy O n.
>> Mert, hogy megtalálja Mike Smith egy telefont könyvében n oldalak, a legrosszabb esetben,
Lehet, hogy engem n lépéseket.
Mi a helyzet figyelembe látogatottsága?
Egy kettő három négy öt hat.
Mi a menetideje ezt algoritmus figyelembe látogatottsága?
Big O n, mert az elméletet én van, hogy pont a teremben mindenki.
>> Most Mellesleg, mi a helyzet a más optimalizálási hétről nulla?
Kettő, négy, hat, nyolc, 10, 12.
A számítógép-tudós lenne megvalósítani, várj egy percet,
ez a sorrend N osztva két lépésben.
Jobb?
Mert én csinálok két ember egy időben.
De mi lesz figyelmen kívül hagyni Ezeket az alsó rendű tagokat,
és mi csak fog dobja el a osszuk el 2,
és csak azt mondom, nagy O n számára, hogy az algoritmus is.
>> Mit szólsz ehhez?
Majd átugrik néhány ilyen, de mi volt egy algoritmus, hogy volt log n?
Hogy elvitt körülbelül log n?
Az oszd meg és uralkodj.
Pontosan.
Mint a telefonkönyvben például heti nulla és a korábbi ma,
ahol osztva a problémát újra és újra és újra.
Felhívtuk a táblára a héten nulla ívelt zöld vonal,
és azt mondtuk, hogy a nap volt logaritmikus algoritmus.
>> És valóban, a lépések számát is úgy, hogy végre oszd meg és uralkodj,
vagy bináris keresés, mint fogjuk kezdeni amelyben ez, mint a telefonkönyvben,
ez a sorrend napló és lépéseket.
És ez egy kicsit furcsa.
>> Mit vesz egy lépéssel, vagy pontosabban
konstans számú lépést?
Lehet, hogy ez a két, talán három, de egy számítógép tudós csak
leegyszerűsíti azt a nagy O 1, Néhány állandó lépések számát.
Mi az, amit tehet, hogy úgy konstans számú lépést?
>> Mi a menetideje taps?
Állandó időt.
Jobb?
Mint, mi a menetideje csinál semmit, hogy már csak egy
működését, mint a print F Hello World.
Hogy lehet mondani, hogy az állandó idő, kivéve, ha kevesebb sarkában esetében nyomtatási N,
Mi lehet a futási idő A nyomtatási F valóban?
És miért?
Mi n mérési ebben az esetben?
>> Közönség: [hallható].
David J. MALAN: Pontosan.
A karakterek száma szeretnénk nyomtatni.
Így nagyon környezetfüggő.
Ma már összpontosítva sokat Betűk és számok itt a fórumon.
De ez is lehet karakterek tényleges húr.
Így kiderül, van egy másik intézkedés, amely indul törődve,
és ez az ellenkezője A nagy O, hogy úgy mondjam.
>> Ez omega jelölés.
Mivel nagy O azt jelenti, mi, a felső korlátot a futási időt?
Maximálisan, hogy mennyi időt Lehet valamit tenni?
Omega-- sajnálom ezt tartja jön up-- az ellentéte, hogy
ahol ez egy alsó korlátot a időt valamit eltarthat.
>> Na. Például, mi az algoritmus vevő mindig n faragva lépéseket?
Nos, az egyik algoritmusok láttunk ma, sőt, lehet, hogy is.
Válogatás a fajta.
Válogatás a fajta elég hülye.
Még ha a algorithm-- sajnálom, még ha a tömb már rendezve,
kiválasztási sorrend fog tartsa séta a listát
hogy megbizonyosodjon arról, hogy a legkisebb elemet újra és újra és újra.
És bár az emberek a közönség tudja, hogy várj egy percet,
Ön már túljutott az legkisebb elem, a számítógép
Nem tudja, hogy amíg úgy néz ki végig a listán.
Hasonlóképpen, az alsó határát, hogy Esetleg ezek is figyelembe kell venni
Lehet, hogy a lineáris idő.
>> Mennyi időt vesz igénybe a Rendezés n elem a legjobb
esetében segítségével olyasmi, mint buborékos rendezést?
Tegyük fel, hogy a listán már válogatni.
Azt mondtuk, buborékos rendezést veszi nagyságrendű n faragva lépéseket.
De mi van, ha ez már válogatni?
Mi van, ha rájössz után egy áthaladás az array
hogy már nem tett csereügyletek?
Szüksége van-e tartani, hogy több menetet?
>> Nem.
Tehát egy alsó korlátot buborékos rendezést Lehet, hogy azt mondják, hogy a lineáris.
Omega n.
És nézd meg mások ezeket is.
Szóval vessünk egy gyors pillantást mindössze egy vizualizációs itt
belátni, hogy ezek megkülönböztetni magukat.
Én megyek le ide ebbe Oldal hogy a rendelkezésre álló C50 honlapján,
de ez lesz a fájdalom, amelyek a dolgozó, mivel az általa használt technológia az úgynevezett
Java applet, amely egy nagyrészt támogatott ezekben a napokban,
legalább Chrome és bizonyos mások.
>> És hadd menjen előre, és meggyorsíthatja ezt fel, és elmagyarázza, mi folyik itt.
Ez egy demo buborék sort, az első algoritmus néztük.
És ez egy vizualizációs, hogy az egyes Ezen rudak számot jelent.
Minél nagyobb a bárban, Minél nagyobb a szám.
Minél kisebb a bárban, Minél kisebb a szám.
És mit lehet látni vizuálisan is bár ez lesz szuper gyors,
az, hogy a piros sáv, mint én, séta oda-vissza a problémák.
Láthatjuk, hogy a nagyobb elemek valóban bugyogott fel a jobb,
és a kisebb elemek vannak bugyogott fel, hogy a bal oldalon.
És itt lent, ha ténylegesen meg közelebbről,
mi is valójában számít a összehasonlítások száma és csereügyletek
amelyeket nem történt.
>> De ahelyett, nézzük meg a második algoritmus
néztük korábban a mi önkéntesek, a kiválasztás sort.
Vizuálisan van egy nagyon különböző hatást.
De ez megint nagyon intuitív, a hogy megtartjuk adja meg a következő legkisebb
elemet, és kaptunk egy kis szerencséje.
Hogy érezte alapvetően gyorsabb.
De ha már futott ez újra és újra és ismét sok bemenet,
látnánk, hogy ez valóban Még mindig nagy O n négyzeten.
>> Csináljuk egy utolsót Itt, beillesztés sort,
amely volt a harmadik algoritmus néztük, és visszahívás
hogy ez az egy foglalkozik a elemeket nem találkozik velük,
de akkor talán műszakban dolgokat, hogy legyen hely,
behelyezése elemek, ahová tartoznak.
>> És ez is véget ér fel, amely a végeredmény. Most itt felsorolt ​​három
éreztem elég gyors.
És valóban, futottam velük egy nagyon jó klip.
De alapvetően, ők mind elég szörnyű, hogy őszinte legyek.
Mindezek a algoritmusok eddig futó nagy O n faragva
hogy egy kicsit a időt futni a végén.
>> És valóban, azt látjuk, és úgy érzi, ez végül
ha kihúzom ezt a harmadik és egyben utolsó demo.
Ez egy másik vizualizáció, hogy folyik
megmutatni buborékos rendezést a bal oldalon, kiválasztási sorrend közepén,
és valami, mint az egyik kéz emel korábban javasolták,
merge sort a jobb oldalon.
A Oszd meg és uralkodj stratégia a helyes.
És ez, sőt, mi vagyunk Ismerkedjünk meg szerdán.
De nézzük az időben ezek fut párhuzamosan.
Ez nagyjából azonos számú elemek, minden futó ugyanabban az időben.
Bubble sort vs kiválasztása Rendezés vs merge sort.
>> Most, ők minden futó elméletileg ugyanabban az időben.
A CPU fut azonos sebességgel, de
úgy érezhetik, hogy unalmas ez nagyon gyorsan fog válni,
és milyen gyorsan, amikor mi adja egy kicsit a héten
Zero algoritmusok mi gyorsítsák fel a dolgokat.
>> És most nézzük összehasonlítani Ezek egy utolsó formában.
Megyek, hogy menjen előre a CS50 honlapján, ahol
itt van ez a végső kapcsolatot a mai napra, ahol valaki az interneten
Kérjük össze egy videót, hogy rögzíti, amit a különböző rendezési
algoritmusok hangzik.
Ez behelyezés sort.
>> [Csipogó]
>> Amellyel te alkalmazásával infó alapján a magassága a bar bar.
Ez buborékos rendezést.
>> [Warped csipogó]
>> Következik is-- jön mellé is-- kiválasztási sorrend,
ahol újra, mi kiválasztása A következő legkisebb eleme,
és látjuk, hogy egyre balról jobbra.
>> Merge sort, mi nyertese eddig ma.
Figyeljük meg, hogy ez elosztjuk a dolgokat a [hallhatatlan] felében és negyedek.
Gnome sort, amit már nem beszélt, és létrehoz vizuálisan
és audally egy kicsit különböző alakú és a hang.
Megy oda-vissza, takarítás a dolgokat.
Szintén nézd meg kupacrendezés ez a fickó honlapján.
>> És ez az.
Látni fogjuk legközelebb.
>> [Whooshing ÉS ZENE]