>> [MUSIC PLAYING]
>> DAVID J. MALAN: Rendben.
Szóval szívesen vissza.
Ez CS50, és az is A három hét végére.
>> Így felidézni az elmúlt néhány hét, mi már töltött egy kicsit a
idő a C, a programozás, a szintaxis.
És ez teljesen normális, ha még mindig küzd Probléma Set 2, hogy
dörömböl a fejét a falba.
Ez rejtélyes külsejű hibaüzenetek és a hibákat, hogy
nem egészen üldözőbe le.
Mert, biztos lehetsz benne, hogy csak egy Néhány héten belül akkor tekint vissza
dolgok, mint Caesar, és a [? V-genair,?] talán Crack, és
észre, hogy milyen messzire jöttél egy rövid idő alatt.
Tehát, ha ez vigasztal, Tarts ki most.
>> Ma azonban kezdjük átmenet a dolgok magasabb szintre.
És elkezdjük magától értetődőnek, hogy tudjátok, hogyan kell programozni, vagy
legalább kezdetei hogy kényelmet.
És kezdjük, hogy fontolja meg, hogyan lehet megy a tervezés programokat
hatékonyan.
Hogyan lehet menni optimalizálása hatékonyságát algoritmusok és
általában több megoldása érdekes probléma.
És kezd magától értetődőnek, hogy a ha akarnánk, tudnánk kódot fel semmilyen
A példa van szem előtt.
Így ma már ne érintse meg a billentyűzetet bármilyen formában a kódot.
Ez lesz sokkal magasabb szinten, és végül, a problémamegoldás.
>> Tehát, hogy az ezen a ponton, hadd javaslatot hogy a következő hét
téglalapok képviseli hét ajtó mögött amely egy csomó
számok, amelyek közül az a szám, 50.
Hadd vetíteni ezt a képernyő itt is.
És javaslom, hogy szükségünk van egy önkéntes segítsen megtalálni nekem a szám előtt
az internet ide.
Gyere fel, a rózsaszín.
Rendben van.
Mi a neve?
>> Jennifer: [hangtalan]
>> DAVID J. MALAN: Tessék?
>> Jennifer: Jennifer.
>> DAVID J. MALAN: Jennifer.
Rendben, Jennifer.
Örülök, hogy megismerhetem.
Gyere fel.
Tehát ezek itt hét ajtók, és milyen Szeretném, ha tenni minket,
előtt minden az osztálytársaival, A hozzánk a szám, 50.
Találni egy számot, akkor kandikál mögött bármelyik ajtó egyszerűen megérinti
az egyik ajtót, és felfedi annak számát.
És lássuk, milyen gyorsan talál minket a számot, 50.
>> 15..
16..
50..
Szép munka.
Rendben van.
Tapsot Jennifer.
>> [Taps]
>> Rendben van.
Szóval, mi volt a stratégia megtalálni a számot, 50?
>> Jennifer: Um, azt gondoltam, ha -
[Nem hallható]
>> DAVID J. MALAN: Oh.
Adj egy percet.
Így volt a stratégia megtalálni a számot, 50?
>> Jennifer: Szóval csak elindítani a kezd, hogy mi az első szám
volt, és úgy gondoltam, talán ha ők sorrendje, én csak tartani
megérinti feljebb?
>> DAVID J. MALAN: OK.
És úgy tűnik, hogy megtalálta hogy ez a helyzet.
Bár hadd húzza vissza a rétegek csak egy kicsit, és azt szeretné, hogy menjen
előre, és felfedi a többi ajtó akkor választott?
>> Jennifer: Ó, drágám.
>> DAVID J. MALAN: Ah.
>> Jennifer: Szóval én csak szerencsém volt.
>> DAVID J. MALAN: Szóval szerencsém volt.
Rendben van.
Tehát nem rossz.
De ez egy érdekes betekintést, nem igaz?
Ha feltételezzük, és nem kap, Valóban, egy kicsit szerencsés is.
De ha feltételezzük, hogy a számok sorrendje, lehet pontosabban
, hogy hogyan befolyásolja a viselkedése?
>> Jennifer: Tehát, ha őket sorrendje, azt gondoltam, a legkisebbtől a legnagyobbig.
>> DAVID J. MALAN: OK.
>> Jennifer: Vagy, ha ez végül is igazán nagy, akkor legnagyobbtól a legkisebb felé.
>> DAVID J. MALAN: OK.
Így legnagyobb a legkisebb, vagy legkisebbtől a legnagyobbig.
De hadd javaslom, tegyük fel, hogy van ütött szerencsétlen, és tegyük fel, hogy a
nem, sőt, válogatott, hány az ajtók is meg kellett volna kandikál
mögött, hogy a legrosszabb esetben?
>> Jennifer: Mindannyian.
>> DAVID J. MALAN: Mindegyik.
Szóval általánosítani, hogy az n.
Előfordul, hogy 7, de most inkább Általában azt mondják, az n kapuit a
képernyő itt.
Így a legrosszabb esetben, ha volna mögé nézni 7 ajtók, vagy n ajtók.
És ez tényleg, ez egy kicsit szerencse ma, de ez tényleg egy lineáris
algoritmus a fajta, még akkor is, volt ilyen kihagyás körül.
Ez tisztességes?
>> Jennifer: Igen.
>> DAVID J. MALAN: Nos, lássuk, ha a stratégia változik, ha mozgok, hogy
A második példa itt 7 különböző ajtók.
Ugyanazt a számot, de ez a alkalommal, amikor a helyére kerül.
Mi a stratégia itt lesz, próbál tenni az eszed, mi
A többi szám is -
>> Jennifer: OK.
>> DAVID J. MALAN: - korábban?
>> Jennifer: Kezdjük az első.
>> DAVID J. MALAN: Rendben.
Kezdjük az elsővel.
4..
Most hová fogsz menni, és miért?
>> Jennifer: 4 nagyon kicsi.
Tehát, ha ők valami talán legkisebb a legnagyobb, meg kell
legyen kétszer, és -.
>> DAVID J. MALAN: OK.
Lássuk, amely úgy gondolja?
>> Jennifer: Próbálja az utolsó.
Szép.
>> DAVID J. MALAN: nagyon jól tette.
Rendben van.
>> [Taps]
>> DAVID J. MALAN: OK.
Szóval tényleg ezt rettenetesen, mert te
csinálja jól.
Ami hagy minket nem bizonyos pontokat.
Így próbáljuk dobni ide.
>> Jennifer: OK.
>> DAVID J. MALAN: Nagyon jó kész, mégis.
Így kezdődött az elején, Ön látta, hogy ez 4, akkor
költözött a végére.
De tegyük fel, hogy nem szerencsés ott, és tegyük fel, 50
valahol máshol.
Amit a harmadik lépés volt?
>> Jennifer: Menj vissza az elejére.
>> DAVID J. MALAN: Vissza az elejére.
OK, így akkor már megérintett ezt az ajtót, ami 8.
Rendben van.
Szóval ez nem 50.
Hová is néztem a következő lépés?
>> Jennifer: Ha nem tudják, hogy rendezve.
>> DAVID J. MALAN: Helyes.
Nos, ha nem tudja, voltak rendezve -
>> Jennifer: Ó, nem tudja, igen.
>> DAVID J. MALAN: - de nem tetted tudja, hol 50 volt még?
>> Jennifer: Csak menj tovább.
>> DAVID J. MALAN: Rendben.
OK.
Folytasd.
OK, hogy tudok dolgozni.
>> Jennifer: OK.
>> DAVID J. MALAN: Most, ha csak majd menj tovább, mi a
algoritmus háruló hátrált.
>> Jennifer: A lineáris -.
>> DAVID J. MALAN: Ez a fajta lineáris.
De hadd javasolja, legyen nekem fel a helyszínen.
Hadd frissíteni kell az oldalt.
ugyanazt a számot, ugyanabban az elrendezésben, ugyanaz ajtók.
De gondolom, vissza, hogy az első napon osztály, amikor elszakadt a telefonkönyvet
fele, valami, és mi Stratégiánk ott?
>> Jennifer: Kezdjük a közepén.
>> DAVID J. MALAN: OK.
Így kezdődik a közepén.
Szóval menjünk előre, és szimulálni ezt.
Kezdjük a középső felfedve, hogy ajtót.
Így a 16-os számú.
Tehát mi is az erős fickó volna, Ki tépte a telefonkönyv a felére,
hogy a következő kitalálni?
>> Jennifer: Menj el ezzel a felét.
>> DAVID J. MALAN: És miért a jobb?
>> Jennifer: Ha ők valami legkisebb a legnagyobb, akkor 50 kell
az ennek érdekében.
>> DAVID J. MALAN: Jó.
Teljesen ésszerű.
Szóval, mint egy telefonkönyv, megy a jobb szemben a bal oldalon, de itt
a kulcs elvihető.
Most is dobja el, és ne tépje le, a fele ezt a problémát, így ha nem
7 ajtók, de tényleg csak 3.
Ami nagyjából a fele a a probléma nagyságát.
Rendben van.
Tehát most, hogy mit kellett volna tenni, miután jobbra?
>> Jennifer: Tehát 16 még mindig elég kicsi, képest 50, így talán megpróbálom,
mint ez.
>> DAVID J. MALAN: Rendben.
42..
Jól van, most mi a ösztön mondom?
>> Jennifer: Én dobni ezt, és aztán csak -
>> DAVID J. MALAN: OK.
Jó, akkor dobja el bal oldalán is.
>> JENNIFER: - vedd ezt.
>> DAVID J. MALAN: És a jobb oldalon.
>> Jennifer: Igen.
>> DAVID J. MALAN: Tehát annak ellenére, hogy nehéz hogy talán, ha már csak
7 ajtók, gondolj, most az összhang a
algoritmust csak alkalmazni.
Az előző esetben nem szerencsés, ami nagyon jó volt.
De nem használ heurisztikus, Azt mondanám.
Használt fajta az ösztönök, és tudva, hogy válogatott, ha ez elég
kicsi az elején, természetesen, most már van, hogy menjen inkább a jobb.
De bizonyos értelemben, akkor szerencséje, mert talán ez volt a 100-as
50 és talán több volt a közepén.
Lehet, hogy 50 volt még itt.
>> De amit tett, egy kicsit másképp ebben az időben volt, akkor nem ugyanaz a dolog
újra és újra.
És azt állítják, hogy amit most volt, bár befolyásolja a telefon
könyv például, valami sokkal több algoritmikus, és még sok minden
kevésbé speciális tokozású.
Sokkal kevésbé ösztönös.
Így a végén a nap, hogyan jellemezné a hatékonyságát
els ˝ o, hol járt balról jobbra, szemben a
második algoritmus itt?
>> Jennifer: Ez kell, mondjuk, talán felére az idő, vagy még több, igen.
>> DAVID J. MALAN: OK, talán még inkább.
Nézzük nyomja egy kicsit nehezebb, hogy.
Ami igazán, ha továbbra is ezt logika, akkor biztosan a felére csökkent
futó idő a második algoritmus dobtak el fele
számok, de mit teszünk a következő iteráció, amikor Jennifer kiderült
a második szám?
>> Mi felére csökkent a száma az ajtók újra.
És akkor mit csinálunk utána, hogy ha több volt ajtó játszani?
Azt felére őket, és újra, és újra, és újra.
És ez olyan volt, mint ti srácok állva az első héten
osztály fele ülsz le félig A ülsz le, a fele meg
leült, amíg egy magányos lélek állt.
És azt mondta, hogy a futási ideje , hogy a lépések száma elég volt
a sorrendben, mi?
>> SPEAKER 1: [hangtalan]
>> DAVID J. MALAN: Tehát log alap 2 n, vagy csak egyszerűbben, jelentkezzen n.
Tehát valami logaritmikus.
És a grafikon volt nem egy egyenes vonal hogy csak rosszabb és rosszabb lesz, nem volt
ezt az érdekes görbe, ami nem hogy olyan rossz az idő múlásával.
Szóval tartsd ezt az elképzelést.
Nézzük köszönöm Jennifer.
Köszönöm, hogy jön fel.
És egy pillanat.
No asztali lámpa ma, de megvan CS50 stressz labda.
>> Jennifer: Yay.
>> DAVID J. MALAN: Rendben, itt.
Köszönjük, hogy ebből A stressz itt.
Rendben van.
Szóval ha most nem formálissá ezt egy kicsit.
Tehát újra, amit most tett, lényegében ugyanaz, mint a mi
abban az első héten.
De ahelyett, hogy vége csak egy lineáris algoritmus, amit ábrázolt
korábban, mint ez egyenes vonal, amely, ha teszünk még egy ajtó
a képernyőn, majd Jennifer lenne kellett nézni, potenciálisan
mögött még egy ajtó.
Ha fel két ajtó, ő lehet, hogy mögé nézni két ajtó.
>> És így volt ez a lineáris közötti kapcsolat a méret a
probléma, mondjuk, az x-tengely mentén, és a mennyi időt vesz igénybe,
oldja meg az y.
De a kép voltam utalva, hogy korábban volt ez a zöld vonal.
Zöld szándékosan, mert csak jobban érezte magát.
Elméletileg, az algoritmus, amikor megcsináltuk A telefonkönyv, amikor megcsináltuk
veletek számít egymást, és a második esetben, amikor csak Jennifer
tette fel itt, ez valami Az alapvetően jobb.
Mivel ez nem csak kétszer olyan gyors.
Még csak nem is négyszer olyan gyorsan.
Ez teljes mértékben függ, hogy milyen a a bemeneti mérete volt, hogy hány
lépések végső soron volt.
>> És így ez az egyszerű ötlet, hogy mi minden volt számára biztosították a telefonkönyvben,
hasonlóképpen lehet alkalmazni valami, mint ez.
És ez talán még véletlenül ismert, ahogy azt
elképzelni, oszd meg és uralkodj.
Nem úgy, mint amit tett, természetesen, A telefonkönyv.
>> De a pszeudokódját, emlékszem, volt ez.
Így nem fog még egyszer, de emlékszem , hogy az első héten, mindannyian felálltak
a másik felét meg leült, a fele ültél le, a fele meg leült.
Ez az algoritmus végre a kicsit egy csaló módon, az, hogy ez
nem csak az egyik én számolás, alapvetően, hatékonyabban.
Ebben az esetben én is kihasználva másodlagos forrás.
Valahogy, több processzor, több agy, több okos ember van a
szoba is segítettél kap valamit lineáris valami
logaritmikus, valamiben piros valami zöld.
>> De ebben az esetben, Jennifer egyedül képes alapvetően javítja fel a
teljesítménye az első algoritmus, újra, csak gondoltam, egy kicsit nehezebb.
És most, ha eljön az ideje, hogy végre ezeket a dolgokat, kitalálni
milyen sornyi kódot lehet írni, mint hogy lehet megismételni újra, és
újra, és újra, valami egy hurok módon.
Mert nem megy, hogy a luxus, mint a Jennifer volt az első, a
csak egy csomó IFS és azt mondják, hmm, ha ez az első szám 4,
hadd ugrani egészen a végéig.
Ó, ha ez a szám túl nagy, hadd mozog önkényesen vissza
a második elem.
Megtudja, hogy ez lesz a sok nehezebb hivatalossá, amit az emberek
magától értetődőnek, mint kedvező heurisztikus, de a számítógép csak
fog tenni, amit mondani, hogy igen.
>> Most ez nagyon érdekes következményei.
Ez a grafikon a fajta célja, hogy egyfajta elborít vizuálisan, de észre, amikor
az egyenes vonal a grafikonon?
Hol van a lineáris grafikon hogy hívjuk n?
Nos, ez a fajta alja felé ezt a képet, nem igaz?
Tehát minden, amit tettem az, hogy mi már egyfajta ránagyít az x tengely és az
y-tengely, hogy próbálja meg egy értelemben, hogy mi más típusú görbék néz.
>> És a pontos részletek a matematikai kifejezések ma nem számít annyira
sok, de észrevettem, hogy van egy csomó algoritmusok sokkal rosszabb, mint a
valamit, ami lineáris.
Sőt, n kockára vágott néz ki rosszul.
2. A n úgy néz ki, nagyon rossz. n kockás néz ki rosszul.
És majd meglátjuk, mi néhány ilyen Lehet, hogy a valóságban ma.
És log n nem érzi magát olyan rosszul, de jobb, mint n log alapja 2 n.
De tudod, hogy lett volna még inkább hihetetlen, ha Jennifer, vagy mi,
, hogy az első héten jött össze valamit, ami log log n.
>> Más szóval, van ez az egész a lehetséges megoldások
problémák, de még itt is, értesítés mi fog történni.
Mikor kicsinyíteni, melyik görbék lesz bizonyítani, hogy az abszolút
legrosszabb az is a képernyőn most?
Tehát n kocka néz ki rossz abban a pillanatban.
De ha kicsinyíteni, és még több a x és az y tengely, ki fog
dominálnak végül?
Így tulajdonképpen kiderül, hogy a 2 a n, és akkor ezt meg csak a
dugulás néhány egyre nagyobb számokat, és látni fogod, hogy a 2 a
n, sőt, egyre nagyobb lesz sokkal gyorsabb.
Ha tényleg kicsinyíteni, 2 a n algoritmus teljesen szar.
Úgy értem, ez fog tartani egy kicsit az idő a
számítógép lemorzsolódás keresztül.
>> De látni fogod azt idővel, különösen a jövőbeli probléma határozza sőt
utolsó projektekre az adatok set lesz nagy, rendben?
Még az első verzió a Facebook, mint a barátok száma, és a
A regisztrált felhasználó van a nagy, akkor valami telefon is és
végre valami lineáris keresés vagy egy nagyon egyszerű válogatás
algoritmus, mint látni fogjuk ma.
Meg kell kezdeni gondolkodni nehezebb és nehezebb ezekről a problémákról.
És a típusú problémák olyan helyeken, mint Facebook, és a Google és a Microsoft,
és mások dolgoznak éppen ezek valami nagy adat fajta kérdések
inkább ezekben a napokban.
>> Rendben van.
Tehát Jennifer sikere, hogy a második algoritmus, őszintén szólva, ő volt meglepően
Nos az első alkalom, de most írd a szerencse, hogy mi
is, hogy ezen a ponton.
A második esetben, ő egy tőkeáttételes algoritmus újra és
újra, de ő vette biztosra a bizonyos feltételezés, hogy lehetővé tette
, de ő kihasznált néhány részlet a másodszor, hogy ő nem volt a
első alkalommal.
Mi volt az?
>> Ez a lista sorrendje.
Tehát amint a lista rendezve, mi azt állítják, hogy Jennifer volt képes
alapvetően jobb.
7 ajtók, igen, nem olyan érdekes, de hiszem, mi vagyunk 7000000 ajtók.
Log n határozottan fog elvégzésére sokkal, de sokkal
gyorsabb hosszú távon.
De volt, hogy a ajtók sorrendje neki.
Most vettem a bátorságot, és csinálja előre a számítógép képernyőjén
itt, de tegyük fel, hogy Jennifer kellett tennem, hogy maga?
Tegyük fel, hogy az ajtók a kérdéses képviselte az adatokat egy adatbázisban, vagy
barátok regisztrált a Facebook, vagy a olyan weboldalak az interneten,
különböző honlapokon szüksége lehet az index vagy a keresést.
>> Tegyük fel, hogy most volt a nyers adatok meg, és maradt meg, illetve a
Jennifer a teendő, hogy a válogatás?
Ez inkább megköveteli, hogy választ az a kérdés, nos, mennyi időt
volna Jennifer, vagy akár én, rendezni ezeket a számokat előre,
hogy ő is kihasználni ezt?
Nem igaz?
Mivel a hatása, természetesen, ha elvisz egy darabig, hogy rendezni
A számok, ki a fene törődik, hogy Megtalálható számos hasonló 50 olyan gyorsan,
mint Jennifer esetében, ha több mint túlterheltek az összeg a teljes idő
ez volt a válogatás a dolgokat előre?
>> Tehát lássuk, ha nem tudjuk a festeni a képet.
Van egy csomó nagyobb hangsúlyt golyók, ha ez segít
megtöri a jeget itt.
És ha nem bánja, akkor kell hét önkéntes -
az, OK.
Wow.
Tehát nem kell költeni az asztali lámpa, úgy tűnik.
Rendben van.
Szóval, mi lenne, ha kettő elöl.
Mi lenne, ha két srác vissza.
Szóval ez a négy.
Mi lenne, ha előtte öt, hat és hét.
Ott.
Ismerőse mutat ki, így kap a díjat.
>> Rendben van.
Gyere fel.
És miért nem voltál srácok gyere ide.
Meg fogom adni egy-egy számot.
És megy előre, és intézkedik magatokat azonos a mi
látható a képernyőn.
>> [Közbeiktatásával VOICES]
>> DAVID J. MALAN: Hopp, bocsi.
Bug.
Rendben van.
Nos, itt vagyunk.
Az ötödik.
Hatos.
Egy, kettő, három, négy, öt, hat, hét.
Ó, ez kínos.
>> SPEAKER 2: én csak kap egy -.
>> DAVID J. MALAN: jó üzlet.
Rendben van.
Köszönjük, hogy részt.
>> [Taps]
>> OK.
Rendben van.
Tehát négy, kettő, hat, egy, három, hét, öt.
Tökéletes, így már hét önkéntesek itt, akik egyenlő szélessége a
tömb játszunk a korábbi.
És én választottam hét okokból hogy lesz csak
kényelmes egy kicsit.
És én fogom javasolni, hogy az első mi rendezni a hét önkéntesek.
Ha szeretné, az első, köszönni mégis.
Mivel ez lesz az kínos néhány percig.
Tegyünk magatokat.
>> GRACE: Szia, én vagyok Grace.
Vagyok másodéves Leverett House.
>> Branson: Szia.
Én Branson.
Én egy újonc a Weld.
>> GABE: Szia.
Én Gabe.
Én vagyok a junior Cabot.
>> NEIL: Én vagyok Neil.
Én egy újonc a Matthews.
>> JASON: Én vagyok Jason.
Én egy újonc a Greenough.
>> MIKE: Én vagyok Mike.
Én egy újonc a Grays.
>> JESS: Én vagyok Jess.
Vagyok másodéves Leverett.
>> DAVID J. MALAN: Excellent.
Rendben van.
Nos, köszönöm, hogy minden a mi önkéntesek itt eddig.
És a kihívás kéznél most folyik hogy rendezni ezek a srácok, de aztán
mi lesz, hogy szerintem egy kicsit kemény, hogyan hatékonyan valójában
rendezve őket.
Szóval először próbálja meg ezt.
Ti Láthatjuk egymás számok csak azáltal körül a sarkokban.
Menj előre, és néhány másodpercig, és a sort magatokat legkisebb a
balra legnagyobb a jobb oldalon.
Go.
>> OK.
Jó.
Ez tényleg rohadt gyorsan.
Most itt valaki, mi volt az algoritmus hogy ezek a srácok alkalmazni?
>> SPEAKER 1: legkevésbé a legnagyobb.
>> DAVID J. MALAN: OK.
Legalábbis legnagyobb valóban rendezni a cél, de nem vagyok benne biztos, hogy ez
tényleg egy algoritmus.
Legalábbis legnagyobb nem mondja nekem lépésről-lépésre, hogy mit kell tennie.
Igen?
>> SPEAKER 1: [hangtalan]
>> DAVID J. MALAN: OK.
Tehát, ha egy embernek kisebb a számot, majd lépjen
a jobb közülük.
Szóval ez már egyre kifejezőbb, több, mint egy algoritmus, mert
lehet mondani, ha ez, akkor azt.
Tehát valamilyen feltételes konstrukció.
És ezek a srácok úgy tűnt, hogy ezt, hogy néhány alkalommal, mert néhányan át egy kicsit
a távolság.
Tehát feltehetően valamilyen hurok folyik a fejükben.
>> De próbáljuk meg, hogy hivatalossá.
Ha ti is visszaáll hogy ez a megállapodás.
Lássuk, ha nem ezt a hivatalossá bit, majd fel a kérdést, csak
mennyire hatékony ez?
Természetesen, ha ezt lassabban, ez meg fog érezni, jó
egy algoritmus, de lássuk, ha tudjuk fel ujjainkat a pontos lépéseket.
>> Szóval két srác négy és két.
Vagy helyes vagy helytelen-e?
Nyilvánvalóan helytelen.
Így cserélték.
Most fogok félre itt, és azt mondják, 4-6.
Ön a helyes vagy helytelen?
>> GABE: Helyes.
>> DAVID J. MALAN: Helyes.
Hat, egy?
Nem.
Swap.
Szóval ez két swap.
Hat és három?
Nem.
Swap.
Hat és hét?
Jól néz ki.
Hét és öt?
>> JESS: [hangtalan]
>> DAVID J. MALAN: OK, csere.
És rendezett.
Rendben van.
Tehát nyilvánvalóan nem igaz?
Így nem volt még folyik.
De, sőt, ezek a fiúk, még csak ösztönösen.
mozgott.
Nem csak megáll, amint javított egy probléma.
Így.
Sőt, megyek, hogy hogy nem ugyanaz a dolog.
Megyek kell rendezni a visszatekerés vissza az elején ezt a problémát,
vagy az elején ez a tömb emberek, kezdjük nevezve őket.
>> És most mit kell az algoritmus A második lépésben az?
>> SPEAKER 1: Ugyanaz.
>> DAVID J. MALAN: Ugyanaz.
És ez, kezdek tetszik, ugye?
Amint megtalálja magát csinál ugyanaz a dolog, újra és újra, hogy ez
egyre inkább, mint egy algoritmus, és kevésbé az emberi ösztön.
>> Tehát most, itt vagyunk megint.
Kettő és négy?
Nem.
Négy és egy?
Ah, ott valóban valami munka még hátra.
A, három?
Jó.
Négy és hat?
Hat, öt?
Hat és hét?
OK, most kész.
OK, nem.
Mennem kell vissza.
>> Tehát most megint ezt csináljuk egy kicsit szándékosan.
És most már csak egy agy végrehajtása az algoritmus.
Egy CPU, ha úgy tetszik.
És őszintén szólva, ez az egyetlen forrás, mi lesz, hogy hozzáférjenek.
És ha már nem megy vissza a billentyűzet és van valami, mint a C-on a
rendelkezésére, mi csak írni egy programot , amely egy dolgot egy időben.
Mivel ezek a srácok egy kicsit ezelőtt, tőkeáttételes kollektív agyak
mint ti tette hét nulla.
Szóval csinálom ezt.
>> Kettő és egy.
Kettő, három.
Három, négy.
Négy és öt.
Öt és hat.
Hat és hét.
Kész?
Tehát én vagyok, de hadd játsszon ördög ügyvédje.
Tudom, az a fajta, aki csak számítógép kikezdett ezen keresztül tömb
ember, tudja, hogy kész vagyok?
>> SPEAKER 1: Nem.
>> DAVID J. MALAN: Miért?
Mit kell tennem annak érdekében, hogy következtetni, döntően, hogy én tettem?
Talán még egy menetben.
Nem igaz?
Mert minden, amit tudok az, hogy a korábbi át, hogy én javított hiba.
És ez azt jelenti, lehet, hogy van még egy hiba
amit ki kell javítani.
Szóval csak biztos a felhúzás, és majd ellenőrzi, 1-2, két-és
három, három és négy, négy és öt, Öt, hat, hat és hét.
OK, most már nem dolgozott.
>> Én biztosan emlékszem, hogy nem tett dolgozni valami, mint egy változó,
mint egy int.
Nevezzük swap, és ha a swapok 0 egyszer ide, és kezdődött a 0, akkor
Én csak hülye, hogy tartani fog oda-vissza, ellenőrzés ismét, és
újra, és újra, igaz?
Mert elakad néhány ilyen végtelen ciklusba.
Tehát amint ott 0 swap, azt állítják, hogy ez a
algoritmus valóban befejeződött.
>> Nos, mondjuk a nevemet.
Az algoritmus, hogy azt javaslom, mi csak végre az úgynevezett buborék
sort, az úgynevezett így abban az értelemben, hogy a a számok, melyek nagyobb fajta
buborék az utat felfelé a csúcsra, vagy akár hogy a végén a tömb a számok.
De milyen hatékony volt ez az algoritmus?
Hány lépést tettem fizikailag kell Vegyük például, hogy rendezni ezeket a
hét ember?
>> Négy-öt?
OK, túl sok végső soron lesz a válasz.
De még akkor is, az adott szám nem olyan érdekes.
Nézzük általánosítani, mint n.
Tehát, ha én n ember van itt, és volt, valami, véletlenszerű sorrendben, a
elején, az, hogy az eredeti sorrendben.
Nos, hány lépést tettem meg hogy az első lépésben?
Ez volt egy, kettő, három, négy, öt, hat, és ők hét ember, így
ez hét, hat -, hogy az n mínusz egy lépést az első alkalommal.
>> Most, hogy hány lépést tettem meg hogy mikor Visszatekertem?
Nos, mi is valójában kétszer, hogy ha akartunk, de most én vagyok
csak mondani, rendben, másik n mínusz 1.
Tehát az n mínusz 1 fog kapni bosszantó, hogy nyomon követni, úgyhogy
csak felhajt kicsit.
Tehát 2n lépéseket.
Tehát 14 lépésben, ide vagy oda.
>> Hányszor veszek egy lépés a következő alkalommal?
Nos, ez 3n.
igazán.
És most, a legrosszabb esetben, a Például, hányszor kellene már
ment oda-vissza, oda-vissza, végrehajtása az algoritmus, csere
emberek minden lépésben, durván?
Ez tulajdonképpen n négyzeten, igaz?
>> Mivel a legrosszabb esetben, akkor milyen Az gondolni ezt ösztönösen,
annak ellenére, hogy lehet, hogy egy kicsit kis idő süllyedni be
A legrosszabb esetben, mi lenne ezek a hét ember nézett ki, mint a
tekintetében a megállapodás a számok?
Teljesen hátra, igaz?
És csak, hogy szimulálja, hogy a mi volt a neve?
>> MIKE: Mike.
>> DAVID J. MALAN: Mike?
OK, Mike, csak velem át Itt csak egy pillanatra?
Igazából nem.
Sajnálom Mike, hadd visszatekerés.
Mi a neved?
>> NEIL: Neil.
>> DAVID J. MALAN: Neil.
OK, Neil, jössz nekem, ha nem bánod.
Így fogom javasolni, csak egyszerűség, hogy Neil most az ő
legrosszabb esetben.
De emlékszem, hogy azt végre az algoritmus.
Én összehasonlítása, összehasonlítása, összehasonlítása, összehasonlítása, összehasonlítása, oh.
Most ezek a srácok ki a rend, így javítani.
Szóval srácok cserélni.
De gondolja most, hogy sokkal messzebb nem Neil kell menni?
Ez nagyjából n.
Tudod, ez valójában nem n.
Ez olyan, mint, n mínusz 1, de kapok bosszús nyomon követése a kis
szám, úgyhogy csak ez n.
>> Tehát, ha Neil egy lépéssel tovább megy maximálisan minden időt, és hogy mozog egy lépéssel Neil,
Azt kell, hogy ez tényleg unalmas át oda-vissza, ez nagyjából
ezt, N lépésben, összesen N-szer, mert ez fog vinni
hogy sok lépés, hogy Neil minden a módja annak, hogy ahová tartozik.
Nemhogy mindenki más, ha ti mind rosszul rendelhető.
>> Így nevezzük buborék sort n négyzeten.
A futási ideje ez az algoritmus, a teljesítmény ez az algoritmus, a
hatékonyságát ez az algoritmus, fogjuk csak le több
általánosságban N négyzeten.
Ami szép és jó, mert én is ezt a ugyanaz például nyolc ember, kilenc
emberek, egy millió ember, és hogy a válasz nem fog megváltozni.
>> Tehát, ha ti nem bánja, most vissza, hogy hol kezdődött.
És próbáljuk két másik megközelítés és hátha nem alapvetően
jobb, mint ez.
Ez alkalommal, fogom javasolni egyfajta másik algoritmust.
Ez nagyon okos volt velünk utoljára, és ti igaza volt, hogy a
jobb ösztönei csak ilyen A csere páronként.
De ha igazán akartam megközelíteni ezt egyszerűen, és a cél az, hogy
mind a kis számok így, és nyomja minden a nagy számok
út, miért nem csak csinálni, hogy a legtöbb naiv módja lehetséges, és ha én
nem jobb, mint ami a meglehetősen összetett algoritmus?
>> Tehát lássuk csak.
Négy egy nagyon kevés, úgyhogy fogja hagyni ott pillanatban.
Ó, a második még jobb.
Így tud csak lépés előre egy pillanatra?
Ez jelenleg a legkisebb sorszámú jelölt, és fogok emlékezni
hogy az, mint egy változó.
De én, hogy nézz.
Van valaki, akinek szám kisebb?
Hat, nem.
Ó, ott van Neil megint.
>> Úgyhogy, hogy álljon vissza fajta fogalmilag.
Neil fog előterjeszteni.
És most, a változó, hogy én vagyok használ nyomon követni, hogy ki van a legkisebb
szám frissítve tartalmaz Neil helyét.
Nos, lássuk csak.
Három hét, öt.
OK, tudom, hogy Neil volt a legkisebb.
Mi a legegyszerűbb dolog , mit tegyek most?
Nem fogom vesztegetni az időt, csak fortyogó Neil egy helyen balra.
Miért nem csak fel Neil ahol tartozik, ami persze hol?
>> Egészen az elején.
Tehát Neil, gyere velem.
És mi volt a neve?
>> GRACE: Grace.
>> DAVID J. MALAN: Grace.
OK.
Tehát Grace, sajnos, akkor ilyen az úton.
Szóval hogyan lehet megoldani ezt a problémát?
Nem igaz?
Ha ez egy tömb, van csak hét helyszínen.
Emlékezzünk, hogy a Rob, beszélgettünk kijelentette korosztály, és csak volt egy
véges számú korosztály?
Ugyanaz ötlet.
Már csak véges számú ints.
Grace a fajta a mi módon, így hogyan lehet megjavítani?
>> A legegyszerűbb módja, mint a, Grace, sajnálom.
Te kell majd menjen át ott így tudjuk, hogy szobát.
Nos, ha úgy gondolja, erről, talán Csak tette a probléma rosszabb.
És talán nem, mert mi van, ha Grace volt a jó helyen?
De tudjuk, hogy ő nem, mert a egyébként, ő lett volna
álló előre helyett Neil ebben az időben, nem igaz?
Már ellenőrizte a számot ki.
>> Rendben van.
Tehát most, Neil van a megfelelő helyen, és Meg tudom csinálni egy kis optimalizálás.
A következő pillanatban, fogom figyelmen kívül hagyni Neil együtt, úgy, hogy ne
vesztegette az idejét, vagy véletlenül csere, hogy a rossz helyen.
Tehát most, hogy tudom megtalálni a következő elem legkisebb?
Kettő.
Ez egy nagyon jó szám, ha szeretnénk előre lépni, és
Én emlékszem rád.
Hat, nem jó.
Négy, három, hét, öt, nem jó.
Hadd mozog, hogy A megfelelő helyre.
És csak most szerencsés ebben az időben.
>> Most fogom figyelmen kívül hagyni ezeket két srác, és most még egyet
áthaladnak ezen.
Hat, hogy egy szép kis szám.
Gyerünk előre.
Ó, sajnálom.
Grace szám jobb, így lépjen előre.
Négy.
Sajnálom, Grace.
Menj vissza.
Száma három jobb.
Hét.
Öt.
És most mi is a neved?
>> JASON: Jason.
>> DAVID J. MALAN: Jason.
Tehát Jason most a legkisebb elem, amit választott.
Hova megy, hogy megy?
Szóval hol hatos.
És a név ismét?
>> GABE: Gabe.
>> DAVID J. MALAN: Gabe.
Gabe az úton.
Mi a legegyszerűbb dolog?
Swap ez a két fickó, és folytassa.
Tehát most lássuk.
Ki az a legkisebb?
Négy.
Hadd ilyen cheat.
Öt lesz a legkisebb.
Találom a következő, ha azt szeretnénk, hogy lépést előre, mit kell csinálni
ezek a srácok, és Gabe?
Swap újra.
Tehát most, még mindig kicsit elromlott.
Én találtam Gabe, hogy a legkisebb, így Én pop őt vigye srácok vége.
És kész.
>> Tehát válasz ugyanaz.
A végeredmény ugyanaz.
Melyik két algoritmus a jobb?
A második, hallottam.
Miért?
>> SPEAKER 3: Ez N lépésben [hallható].
>> DAVID J. MALAN: Ez n lépés a legtöbb.
Érdekes.
Szóval, hogy mégis?
Szóval hogyan találom meg a legkisebb elem?
Hány lépést kellett nekem, hogy az megtalálja a legkisebb elem?
Megnéztem végig a végén, nem igaz?
Mert hogy a legrosszabb esetben, milyen ha Neil volt itt?
Tehát csak megtalálni a legkisebb elem elvisz n lépéseket, vagy n mínusz 1.
De, OK.
Így fix Neil.
Ne feledje, hogy egy perc múlva óra.
>> De hogyan találom meg a következő legkisebb elem?
Ez n mínusz 1 vagy mínusz 2 n igazán, a lépések számát.
Így az OK gombra.
Úgyhogy n mínusz 2.
Rendben van.
Annak érdekében, hogy úgy érzi, egy kicsit jobban.
Rendben van.
Hány lépést a következő alkalommal találni a harmadik?
Tehát n mínusz 4.
Szóval ez csökken, eggyel kevesebb lépést minden iteráció.
Tehát ez jobban érzi magát, nem igaz?
Ha utóbbi időben ez volt nagyjából n-szer n ezúttal n mínusz 1, plusz mínusz n
2, plusz n mínusz 3, és n mínusz 4, pont, pont, pont.
De ha visszahívja a gimnázium tankönyvek, a kis csaló
lapot a hátsó, amely képleteket, ha hozzá ezt a számsort,
mi a lépcsőfokok számát lesz, hogy veszek itt?
>> Ez egyike azoknak, mint, n mínusz 1 alkalommal n, osztva 2-vel.
Hadd hátha tudok húzni ezt fel egy pillanatra.
És ismét, én vagyok ilyen kerekítés bizonyos számok csak hogy életünk egyszerű,
de ha jól emlékszem, ez olyasmi, mint ha Én n mínusz 1 dolog, akkor n mínusz
2, akkor n mínusz 3, ez nagyjából valami ilyesmi több mint 2, és ha
szaporodnak ezt ki, ez valójában N téren.
Ez nem érzi túl jól. n N mínusz több mint 2.
>> De itt van a dolog.
A számítógép-tudomány, amikor a problémák kezd érdekessé válni, amikor n
lesz igazán nagy.
És amikor n lesz igazán nagy, ami a ezeket az értékeket fogja uralni minden
a többiek?
Elég az n négyzetes, igaz?
Igen, elosztjuk a 2 nagyon jó.
De ha beszélünk milliárd A darab az adatok, vagy milliárdjai
darab adat, OK, így te kétszer olyan gyorsan.
De aki igazán érdekel, ha ez a nagy szám, ha ez a tényező az, amit kap
nagyobb és nagyobb.
És biztos, hogy van több a a különbség, mint ez a fickó.
Tehát annak ellenére, Igazatok van, a második algoritmus, hívjuk meg
kiválasztás sort, az, hogy a való világban, a kicsit gyorsabb potenciálisan, mert én vagyok
figyelembe egyre kevesebb lépéseket minden egyes alkalommal.
>> Ez nem igazán alapvetően gyorsabb.
Mert ha tényleg játszani ezt a ki n értéke nagy, a végén
a nap, elég nagy n, még mindig majd úgy érzi, elég lassú.
Nos, hadd vegyen be egy utolsó lépés az, hogy.
Ez az, amit én neveznék kiválasztás sort.
Tudtok vissza magatokat utoljára?
És ebben az utóbbi esetben, megyek javasolni valamit
nevű beszúrás sort.
Beillesztése sort, hogy fogalmilag, egy kicsit más.
>> Ahelyett, hogy megy oda-vissza, és kiválasztja a legkisebb elem, én vagyok
csak fog foglalkozni minden egyes ilyen fiúk, mint én találkozni velük, és helyezze
azokat a megfelelő helyre.
Szóval csak fog kezdeni Grace, és látom, hogy ő a negyedik.
Hol négyes tartozik?
Még nem indult válogatás semmit, így Grace lesz, hogy maradjon ott.
És most fogok igényt, ha lehet egy lépést a helyes, ez a
a rendezett lista, ez az én rendezetlen maradék listát.
Szóval most megyek, hogy folytassa a következő, és mi a neved?
>> Branson: Branson.
>> DAVID J. MALAN: Branson.
Tehát Branson a kettes számú.
Így fogok vinni ki egy pillanatra.
És most, hol tartoznak ebben a tömbben?
Tehát, hogy a jobb Grace.
Tehát újra, mi olyan, hogy Grace sokat dolgoznak itt.
Hol téged?
Így fogunk csúszni, hogy a balra, és helyezze Branson ott.
De most már azt állítják, hogy srácok kész.
De vegyük észre, én nem használ extra helyet.
Még mindig 2 elem Itt, 5. ide.
Total tömb mérete 7, úgyhogy nem csalás, rendben?
>> Tehát most már, és Gabe itt, a hatos, hol tartozol?
Van szerencsém újra.
Szóval, hogy maradjon ott.
Csak egy kis lépés, hogy a megfelelő csak azért, hogy világos, hogy te rendezve.
És most már Neil ismét szám Egy, hová mész?
És most, amikor elkezdjük látni, hogy Az algoritmus, de az első
Dióhéjban, úgy érzi, elég okos, nézni mi fog történni.
Ha lehet előrelépés.
>> Hol akarjuk, hogy Neil?
Tehát nyilvánvaló itt, akkor hogyan jutunk Neil oda?
Csináljuk lépésről-lépésre.
Gabe, hol kell menni?
Igen, így, hogy egy nagy lépést, vagy két fél lépéseket, hogy
egy lépéssel ott.
Grace, hová mész?
Jó.
Tehát még egy lépést.
És végül, Branson?
Újabb lépés.
És most is fel Neil helyére.
>> Tehát most, továbbra is ezt a logikát.
Annak ellenére, hogy mi nem változó Neil újra és újra, és újra, hogy őt
hová megy, a legrosszabb esetben, a következő szám talán találkozunk lehetett
száma legyen, mondjuk, volt egy számot nulla, akkor fogunk váltani minden
ezek a srácok.
Tegyük fel, hogy van egy szám, negatív egy, akkor meg kell váltani
mind ezek a srácok.
Szóval tényleg csak ilyen essek A probléma körül, úgy, hogy mi
át a költség a kiválasztási folyamat így a beillesztés
folyamat, úgy, hogy ti most volt mozog nagyjából n mínusz valamit
számát.
És ez a szám a lépést csak akkor fog növelni, ahogy válasszon több számot,
ha van, hogy tolta a srácok vissza, és vissza, és vissza.
>> Tehát a szomorú dolog most az összes ilyen algoritmusokat n négyzeten.
Menjünk előre, és ezeknek köszönhetően fiúk, és elképzelni ezeket egy kicsit
másképp.
Nagyon jól sikerült.
>> [Taps]
>> Rendben van.
Tessék.
Köszönöm -
>> Branson: [hangtalan] tartsa a számokat.
>> DAVID J. MALAN: Nem, Ön hogy a számok is.
Rendben van.
Szép munka.
Rendben van.
Tehát lássuk, ha nem most összegezni gyorsabban, és megjelenését,
Pontosan mi történt Itt a következők szerint.
Én megyek előre és húzza fel a Firefox.
Majd kapcsolja a demonstráció A kurzus honlapján.
Java egy kicsit bosszantó, hogy kap munka egyes böngészőkben ezekben a napokban.
Tehát, ha játszani ezt otthon, rájössz, hogy szükség lehet használni Firefox
, hogy ez működik.
És mit fogok csinálni a bemutató a következő.
>> Alul van egy csomó menüpontok, beleértve a kezdő és a
stop gombot.
Továbbá, mint egy félre, úgy tűnik, hogy egy bug ezekben a programokban, amely akkor
nem láthatók a kezdeti és a gombot, ha nem tartja Command vagy az Alt
plus és nagyítás, ami furcsa azt mutatja, hogy több gomb.
Tehát csak FYI, ha játszik ezzel otthon.
Most megyek kattintson a Start gombra, mindössze egy pillanatban megadása után a késleltetés,
mint 200 milliszekundum itt, csak így látjuk, mi történik.
>> Szóval azt állítják, hogy ez a megjelenítés Az első algoritmust
ezek a srácok nem, buborék sort, amely mi cserélték emberek páros.
A legfontosabb betekintést a megjelenítés az, hogy a magassága a rudak
képviseli a méret a számot.
Így a magasabb a sáv, Minél nagyobb a szám.
Rövidebb az oszlop, annál kisebb a szám.
És ha azt veszi észre, mi megy keresztül az első iteráció ezen algoritmus,
csere nagy és kis mennyiségben, hogy a A kis számú az első, és
A nagy szám megy jobbra.
>> És amint megkapjuk a végén a tömb A több mint hét számot, vagyunk
megyek vissza az elejére.
És előre ezt.
A bal szélen, az a kis fickó fog cserélni az oldalra, és ez a
folyamat ismétlődik.
Most ez a megjelenítés gyorsan kerül unalmas, hadd menjen előre, és megáll
, változtassa meg a késés valami sokkal gyorsabb csak azért, hogy most egy érezni
Ezt az algoritmust.
>> Így, bár én már felgyorsult fel, ez mint a korszerűsítés a processzor, vásárlási
egy új számítógépet.
Én alapvetően nem változtak az algoritmus, de valójában még több
világosabban, mint az emberek, hogy a nagy számok bugyogott fel a csúcsra,
, és a kis számok átbuborékoltatásával le az aljára.
És most ez a dolog itt rendezve.
És mint egy félre, a terek, van csak néhány könyvelés ott
segít hány összehasonlítást, vagy hány swap van
valóban megtörtént.
>> Nos, nézzük meg egy a többi, amit láttunk.
Hadd kattintson bubble sort itt, és én döntöm el, és ez az egész weboldal
egy kicsit bugos.
Fogadjuk el a kockázatot és futtassa újra.
Ott vagyunk.
Tehát lássuk kiválasztás sort.
Én nem tudom, miért a menü jelenik meg ott.
Nézzük nagyítás rögzíteni, hogy a bug, változtatni 50-re.
Ah, most ténylegesen hogy sokkal gyorsabb.
Öt ezredmásodperc, vagy úgy, és a Start gombot.
>> Tehát ez a fajta választás.
Tehát még egyszer, gondolom, hogy mi vagyunk tette az emberek itt.
Mentünk a tömb és kiválasztott a legkisebb elem ismét
és újra, és újra.
Most azt állítják, hogy még mindig nagyon rossz.
Még mindig n négyzetes, ide vagy oda, de ez, a való világban, egy kicsit
gyorsabb, mert én valóban figyelembe valamivel kevesebb lépést minden egyes alkalommal.
De mi csak beszélünk, mi?
Lehet, hogy 40, vagy úgy bar itt?
Mi nem beszélünk a 40 millió.
Szóval ez nem teljesen világos számomra, hogy valóban jelentős nyereséget.
>> Hadd menjek vissza, és változtatni a mi harmadik algoritmus, melyet válasszuk
beszúrás sort.
És most már tényleg hibás, mert az étlap tényleg nem lehet ott.
Tehát most akkor lépjünk vissza ide és meg kell kezdeni az algoritmus.
Whoop, start és stop.
Tehát ez a fajta, egy szép minta hozzá, ahol vagyunk újra
behelyezése az emberek, vagy Ebben az esetben a rudakat
a megfelelő helyre.
És ez már azelőtt Megfordultam.
De ez is, elvileg, még n négyzeten.
>> Tehát lássuk, ha nem tudjuk összefoglalni ezek a következők szerint.
Én megyek előre, és csak azért, hogy bennünket egyfajta közös módon beszél
ezekről a dolgokról, hadd mutassam be csak egy kis jelölés itt.
Mindjárt látni úgynevezett nagy O, mert ez egy nagy szó
O. És ez az egyik módja, hogy a számítógép tudós vagy matematikus akár használt
leírni a működési idő néhány algoritmus.
Hány lépés történik mindez?
>> Most fogok zavarba magam a kézírás itt csak egy pillanatra.
De hadd menjek előre, és azt mondják, hogy ez lesz a nagy O ide.
És hadd mutassam be egy másik szimbólum, a tőke omega.
Omega lesz a másik, lényegében nagy O. mivel nagy O
azt jelenti, hogy a legrosszabb esetben mennyi idő talán néhány algoritmus, hogy, a
feltételek n, omega fog , hogy mennyi idő lehet, hogy ez
hogy a legjobb esetben.
És majd meglátjuk, mit értünk legjobb esetben csak egy pillanat.
>> Tehát kezdjük valami egyszerű.
Hadd kezdjem egy lineáris keresést.
Tehát nem válogatás.
Hívjuk ezt lineáris keresést.
És most, hogy egy kis táblázat ebből.
És most, abban az esetben a lineáris keresés a legrosszabb esetben, hogy hány lépés van
fog tartani, hogy találjak egy száma önkényes választás?
És ott van n összesen ajtók vagy n teljes számokat.
Legrosszabb esetben.
Hány lépést fogok kell hogy a megfelelő számú 50 tömbben
n ajtók?
És miért?
Mert lehet, hogy az összes utat át rá a végén.
Annyira, mint Jennifer találkozott, a száma 50 volt, egészen át, így
a legrosszabb esetben lineáris keresés nagy O n, akkor mondjuk.
>> Mi a helyzet a legjobb esetben, ha igazán szerencsés?
Ez csak megy, hogy egy lépést, vagy állandó számú lépésben.
Tehát leírjuk, hogy az 1.
Szóval ez nagyon jó.
Most mi van, ha nem valami mint bináris keresés?
Tehát bináris keresés, a legrosszabb esetben volt, hogy mennyi idő alatt?
>> [Közbeiktatásával VOICES]
>> DAVID J. MALAN: Tehát tulajdonképpen azt hallotta egy pár helyen.
Tehát valójában log n, ide vagy oda, mert ahogy osztani a lista fele
újra, és újra, és újra, képesek vagyunk megtalálni, végső soron, az érték,
ha ott van, de van egy fogás.
Mi az a feltételezés, hogy meg kell adottnak a bináris keresés?
Meg kell válogatni.
Ez nem válogatni, akkor hasít a dolog fél újra és újra, és
mehet balra, és akkor menj jobbra, és akkor megy bal és a jobb, de te
nem fog találni az elem, ha A lista nincs rendezve, mert
lehet eltéveszteni.
Mert a heurisztikus, az megy bal vagy jobbra lesz hibás, ha ez
Valóban nincs rendezve.
Tehát van egyfajta rejtett költség használata valami ilyesmi.
>> Nos, menjünk be a válogatás algoritmusok nem keres -
oh, tényleg menjünk üresen.
Bináris keresés a legjobb esetben?
Ez is 1, ha ez csak történik, hogy kellős közepén a tömb, vagy a
a közepén a telefonkönyvben.
Most ismét egy buborék sort.
Tehát újra, most pedig belépő fajta, nem a keresést.
>> A legrosszabb esetben, hogy hány lépést tettünk igény bubble sort fog tartani?
N négyzeten.
Így fogok rajzolni.
Ó, az én kézírás néz ki, még rosszabb amikor ez várható, hogy nagy.
Rendben van.
Szóval ez n négyzeten.
És a legjobb esetben a buborék sort, hány lépést fog ez tartani?
1, hallottam.
>> SPEAKER 1: n.
>> DAVID J. MALAN: n, hallottam.
>> SPEAKER 2: 1.
>> DAVID J. MALAN: 2, hallottam.
Nem hallom 3?
Rendben van.
Én is úgy hallottam 1, n, 2, de hadd vegye egymástól legalább az első azoknak
javaslatok, 1.
Ez nem egy rossz ösztön, mert egyfajta mintát követ itt.
De ha csak úgy 1 lépés, hogy a világ is azt állítom, hogy a lista
van rendezve, mert ha én csak szabad hogy 1 lépés, hogy sok eleme
Igazából lehet ellenőrizni, hogy biztos?
Nos, csak 1, ami azt jelenti, van n mínusz 1 elem, hogy lehet ki
rend, és én csak megy a hit után néztem 1 elem a
dolog van rendezve.
Tehát 1 nem helyes itt.
Tehát minimálisan hány tudom kell nézni?
>> [Közbeiktatásával VOICES]
>> DAVID J. MALAN: n mínusz 1, vagy nagyon, n, mert meg kell nézni minden
elem, hogy megbizonyosodjon arról, hogy az ez nem elromlott.
De ismétlem, mi fajta hullám a kezét a kisebb számok és
feltételezik, hogy az n egyre nagyobb lesz, ők érdektelen egyébként.
Szóval ez buborék sort.
És most csináljuk az utolsó kettő.
Selection sort, és aztán do beszúrás sort.
És akkor majd robbantani a fejében valami sokkal
jobb, mint az összes ilyen.
Rendben van.
>> Mi a legrosszabb esetben futó ideje kiválasztás sort?
>> SPEAKER 4: n négyzeten.
>> DAVID J. MALAN: n tér, hallok.
De miért n kihúzta, ösztönösen?
>> SPEAKER 4: Mivel mi csak tette.
>> DAVID J. MALAN: Mivel mi csak tette.
OK.
Jó válasz.
De ösztönösen, miért kiválasztás sort n négyzete?
Mit kell tennünk újra és újra?
Meg kellett, hogy a szkennelés, az akkor a legkisebb, te vagy a
legkisebb, te vagy a legkisebb.
És adott, tudtuk, hogy n lépésben, akkor n mínusz 1, akkor n mínusz 2.
De ha ilyen hozzá az egészet, vagy hogy azt hittel, hogy én már hozzá
őket előre, kapunk durván n négyzet mínusz néhány kisebb számokat.
Így fogom hívni ezt a N négyzeten.
De kiválasztás sort a legjobb eset, hogy hány lépés van
fog tartani engem?
>> SPEAKER 5: [hangtalan]
>> DAVID J. MALAN: Ez sajnos még n négyzet, nem igaz?
Mert ha én kiválasztja a legkisebb elem, és mi volt hét ember van,
Csak azt tudom, ha egyszer eljut a nagyon vége, hogy én találtam a legkisebb
szám, bárhol is vagy ő lehetett.
De hogyan találom meg a következő legkisebb szám?
Meg kell csinálni egy menetben.
Így a legjobb esetben, mi a bemenet kiválasztás sort?
Ez egy már rendezni, első számú, kettes, hármas, négyes.
De én vagyok egy számítógép.
Én csak nézni egy dolog egy időben.
Nem tudok valahogy egy lépést vissza, mint egy ember, és azt mondják,
ó, ez úgy néz ki a helyes.
>> Én csak határozni korrektség kiválasztás Rendezés kiválasztásával
legkisebb szám.
De még ha találok számú első, Ha nem tudom, mást a
A többi szám, amit én nem, én tudom, hogy már átadott tömb
vagy egy sor ajtó mögött, amely számok, az egyetlen módja, tudom, hogy egy
volt a legkisebb?
Ha kapok egészen idáig, és rájönnek, A fenébe, az egyik valóban a legkisebb.
>> De hogyan, akkor megállapítható, hogy kettő a következő kisebb?
Ezzel ugyanaz a hatékonysági újra és újra.
Így végül, a beillesztés sort, hogyan, a legrosszabb esetben,
nem azt mondják, hogy végre?
Ez is n négyzeten.
És mi a helyzet a legjobb esetben?
Majd hagyjuk, hogy a filmsorozat.
Majd töltse ki az üres legközelebb, de előbb hadd javaslom, hogy
alapvetően jobban, mint Mindezen, rendben?
>> Szóval szerintem magad milyen beillesztés fajta lesz.
Nos, ez nem túl drámai, mert én vagyok az egyetlen
hogy látta a változást.
Wow.
OK.
Tehát itt van egy kicsit különböző bemutató.
Ha nagyítani itt, látni fogja, hogy a A bal oldali van buborék sort, a
középen van választék sort, valamint a a szélsőjobboldali, van valami, amit
még nem nézett még nevű merge sort.
De gondolja meg, amit már itt eddig ma.
Amikor Jennifer először jött fel a színpadra, mentünk át a tömböt a számok
újra, és újra, és lineáris keresés és mi van a lineáris működési idő, nagy O
n, hogy úgy mondjam.
>> Ha most úgy az első héten osztály, amikor már oszd meg és uralkodj,
és mi volt a telefonkönyv könnyezés, és Jennifer, és közösen
alátámasztani, hogy a legfontosabb betekintést, ami az volt, hogy ismételje meg magát újra és újra
valahogy eldobja, eldobja, eldobja, fele a probléma, vagy a
általában elosztjuk a probléma a felére, kezeljük, majd a kisebb darab
A probléma fogalmilag egyenértékű a másik, akkor valahogy
alapvetően jobb.
De buborék sort, a kiválasztás sort, a beillesztés sort, most már lehet
ilyen betekintést, hogy Jennifer nem.
Mi nagyjából csak sétált vissza oda egy csomó idő, és mi
csípett a dolgokat egy kicsit, csere ebben a sorrendben, talán
behelyezése vagy kiválasztásával.
De a végén a nap, csináltam egy csomó A kínos séta oda-vissza.
Nem igazán tőkeáttétel valami okos, mint Jennifer tetszett elválasztó
és hódító.
>> Tehát merge sort, ezzel szemben, amit nem fogja látni, amíg a jövő héten, hogy megy
hogy kiterjessze e lényeg, hogy elosztjuk a bemeneti, majd felére, majd
felére, majd a felére.
És iterációk hogy hurok, válogatás a bal felére, és a megfelelő
felét, majd a bal fele a bal felét, és a jobb fele a bal oldalon, majd
a bal fele a jobb felére, és a jobb fele a jobb felét.
És ismétlődő újra és újra.
>> Szóval majd meglátjuk, ezt vizuálisan, de ez a az, mi vár ránk a jövő héten.
És általában, amikor azt gondoljuk, egy kicsit kicsit nehezebb minden ilyen probléma.
Mi n négyzetes a bal oldalon, n négyzetes a közepén, és n
log n a jobb oldalon.
Tehát az igazi Cliffhanger.
Találkozunk hétfőn.
>> [Taps]