[Powered by Google Translate] [3. hét, folytatás]
>> [David J. Malan - Harvard University]
>> [Ez CS50. - CS50.TV]
>> Rendben van. Üdv újra. Ez CS50, és ez a vége a 3. hét.
>> Így azok számára ismeretlen, az elmúlt évben a Harvard elindította az úgynevezett az Innovation Lab,
vagy i-labor, amely egy csodálatos épület a folyón a HBS campus
amely nyitott a főiskolai hallgatók, GSAS hallgatók, diákok egész campus,
beleértve a kar, és ez a hely, hogy jöjjön össze dolgozni innovatív dolgokat,
különösen a vállalkozói dolgok
ha te és 0 vagy több barátai gondolsz csinál valamit vállalkozói
vagy ez alatt az osztály, miután ez az osztály, illetve azon túl.
>> Tehát az egyik dolog, mégis több mint J távon ezeknek az utazásoknak,
amelyek közül az egyik az, hogy New York, amelyek közül az egyik a Silicon Valley.
A tér nagyon korlátozott, de ez egy lehetőség, hogy dörzsölje vállát MBA
és végzős hallgatók az egész egyetemen, és valóban időt e egyes területeken
csevegés up induló, csevegni fel a vállalkozók és a hasonlók.
Tehát, ha érdekel, nézd meg ezt az URL-t ide.
Ugyancsak elérhető a diák online.
>> Tudnánk hang le a ház hang, csak egy kicsit?
Ha azt szeretné, hogy csatlakozzon hozzánk ebédre a péntek, 13:15 in Fire & Ice, kérjük fejét ott.
Elnézést, ha az űrlap már ki van töltve, mire odaér.
De mi is ezt a hagyományt kezdve.
>> Ma továbbra is a magasabb szintű vita a különböző problémákat, hogy meg tudjuk oldani,
élességállítás sokkal kevesebb, ma legalább a kódot, és sokkal inkább ötleteket.
Szóval szerintem vissza a 0. héten, amikor elszakadt a telefonkönyvet a felére,
amelynek célja az volt, hogy tegyen valamit, igaz, egy kicsit drámai
hanem elküldeni a pontra, hogy keresési nem kell, szükségképpen,
annyira nyilvánvaló első pillantásra, mint gondolnád.
És problémamegoldás általában nem feltétlenül mindig a legjobb -
A legkézenfekvőbb megoldás lehet, hogy nem feltétlenül a legjobb.
Így volt ez a telefonkönyvben, és őszintén szólva, mindannyian ebben a szobában volt, az ösztönök,
legvalószínűbb, hogy indítsa el a közepén, ha keres Mike Smith, majd menj balra vagy jobbra
alapuló bármilyen betűvel mi történt a végén be.
>> De az egyszerű ötlet, hogy az emberek adottnak oly sokáig
Tényleg meg kell kezdeni, hogy jöjjön az élvonalban a fejedben
mert a problémák kap sokkal bonyolultabb, mint egy telefonkönyv,
ugyanezen egyszerű, briliáns meglátásai mit fog lehetővé teszi számunkra,
megoldása sokkal bonyolultabb és több érdekes problémák,
köztük néhány dolog, amit magától értetődőnek már ezekben a napokban.
Milliárdjai weboldalak ott, és még a Google és Bing és hasonlók
képesek a dolgok nekünk ilyesmi.
Ez nem történik a lineáris kereső, kereső segítségével az összes lehetséges weboldalakat.
Facebook tudja mondani, hogy ki az összes barátok vagy ismerősök ismerősei,
és hogy túl lehet tenni látszólag egy pillanat ezekben a napokban
annak ellenére, hogy több millió felhasználó.
>> És hogyan tudjuk valójában megoldani a problémákat, hogy a skála végső soron csökkenti
Az ötleteket néztük, a 0. héten, és egy kicsit ma.
Nem fogunk újra végrehajtani ezt az algoritmust, de emlékszem mi is tette 0. héten e feladat
ahol már mindenki feláll, veszi a 1-es szám,
és akkor már mindenki saját count által párosítás ki, hozzátéve, a számok együtt,
akkor fele banda leült minden iteráció.
Így mentünk 500-tól a tanulókat, hogy 250-125 és így tovább.
De ahogy azt mondta hétfőn, a hatalmas ötlet, ott
az volt, hogy ha megduplázta a méretét, hogy a probléma
és az összes gyerekek Bíróság vagy Ec 10 jött vissza a szobába, és csatlakozott hozzánk,
nos, valószínűleg számolni, hogy az egész csoport összesített
mindössze 1 további nagy iteráció a hurok, mert csak talán kétszeresen
vagy az EK 10 esetében egy kicsit több mint a duplája a méret.
És így kellene költeni egy kicsit több időt,
de nem kell költeni 400 vagy 700 több lépésben.
>> Csak festeni ezt a képet úgy, hogy ez egy kicsit kevésbé elméleti, ne már mindenki álljon fel.
De ha azok, akik úgy döntöttek, hogy üljön a zenekar ma nem bánnám állva,
lássuk, tudunk kitalálni köztetek, aki a legmagasabb ember
ezzel ugyanaz a fajta összehasonlító algoritmus.
Szóval, ha ül a zenekar, elnézést kérek, de az 1. lépésben, állj fel;
2. lépés pár le valaki a közelben van,
kitalálni, aki magasabb, és ülj le, ha rövidebb.
Ezután ismételjük meg.
[Diákok zúgolódás]
>> Oké.
Oké. Egy maradt állva. Mi a neve? >> Andrew.
>> Andrew, te vagy a legmagasabb ember a zenekar pont ma.
>> Gratulálok. [Taps és éljenzés] Oké. Van egy helyet. Így találtunk Andrew.
De meddig tartott volna meg, például, hogy megtalálják Andrew
ebben a zenekarban részén 50 + vagy, így az emberek?
Tudtam volna egy viszonylag egyszerű megközelítést, és itt kezdődnek.
És én 2 ember feláll, és én csak hasonlítsa össze őket,
és akkor azt mondom, hogy aki egy kicsit rövidebb, "Oké, te ülj le,"
és fogok emlékezni, akik a magasabb ember volt.
Aztán Ismétlem, ismétlem, ismétlem, én tarts ki, hogy a legmagasabb ember
amíg nem találok valakit, kicsit magasabb, mint őket, ekkor a
A valamivel rövidebb személynek kell majd ülnie.
De ez az algoritmus ebben a zenekarban szakaszban, ha van n van,
hány lépést, hogy algoritmus fog tartani? >> [Hallgató] N.
>> Ez fog tartani n, igaz, mert a legrosszabb, hogy úgy mondjam,
a legmagasabb ember az utolsó ember, hogy kapok, hogy csak véletlen balszerencse.
Így a legrosszabb esetben a futási ideje, hogy az algoritmus lineáris, ez n,
ahol n értéke a teljes száma, akik a térben, a méret a probléma.
Mi ez az algoritmus?
Az a tény, hogy az összes felállt, majd ismét a felét maga leült,
fele úgy ült le, a fele akkor leült.
Hány lépéseket kell tenni, hogy ha van n ide?
[Hallgató] N log n. >> Lenne rosszabb. Jelentkezzen n.
>> Így log n, akkor is, ha nem igazán emlékszem, mi a logaritmus van,
most, csak nyilvánvaló, hogy vonatkozik valahogy ennek felére csökkentését és a felére csökkentését és a felére csökkentését.
Nem kell, hogy egy 2-es szorzóval. Ez lehet egy tényező a 3.
De ez a megismétlése ugyanolyan tényező, hogy a méret a probléma itt kezdődik
de aztán rögtön megy itt, akkor itt, akkor itt, akkor itt.
Ugye nem vesz kis harap ki a problémát, akkor tényleg aprítás el rajta
egy nagy csapásra minden alkalommal.
Így volt 50 fő, majd 25, majd a 12 ½ vagy 13 ember áll,
majd 6 ½ és így tovább, míg végül csak Andrew maradt állva.
Így fogjuk hívni, hogy a log n, és tudod vizualizálni ezt az alábbiak szerint.
Emlékezzünk vissza, ezt a képet itt, ahol egy lineáris algoritmus olyan, mint a piros vonal van,
a sárga vonal volt a számolás által 2s algoritmust, hogy mi használt számláló diákok
a múltban, de ma a Szent Grál lesz, hogy továbbra is ezt a zöld vonal
ahol ha megduplázta a száma, akik a zenekari szakasz vagy csak azt mondta:
pokol, vessünk mindenki az egész terem feláll, nem olyan nagy dolog
mert nagyjából kétszerese hány ember van itt lenn,
1 további iteráció, nem probléma.
>> Úgy találtuk, Andrew vagy akárki történik, hogy magasabb, mint Andrew
a mezzanine, vagy az erkélyen.
Tehát ez az egyszerű ötlet, hogy mi volt annyira magától értetődőnek a telefonkönyv,
észre, hogy olyan sok különböző helyen, ahol mi is alkalmazzák.
Csak néhány pofon zsargont - valójában, ahelyett zsargon első,
engedj el ezt a képet itt.
Most beszéltünk n és n / 2, majd jelentkezzen be n,
de természetesen jön ki, ahogy majd során a félév,
egyéb fajta matematikai képletek, hogy leírja ezt az általános fogalmat a futási idő.
Ezek közül az összefüggésben most, mert meglátjuk nemsokára
algoritmusok, hogy ezek valóban képviselnek.
>> De észre, itt a lineáris vonal n, az egyenes, valójában nagyon alacsony mutat most.
Ez a fajta optikai illúzió, hogy mi csak változtatni, amit az x tengely
és az y tengelyen, és tudjuk, hogy egy egyenes vonal pontjára tetszőleges irányban akarunk.
De az oka annak, hogy ez olyan látszólag sima most
azért van, mert szükséges, hogy legyen hely a grafikonon sokkal lassabban fut alkalommal.
Most, tudom, hogy van néhány nagyon rossz algoritmusok az életben,
amelyek közül néhány nem veszi n lépéseket, vagy, ami még jobb, jelentkezzen n lépéseket, de több.
Így a vonal fölé n itt alul nyilatkozat van n-szer log n,
és meglátjuk, hogy ez mit jelent, mielőtt hosszú.
Fent mely n négyzet, és nem láttunk semmilyen n faragva algoritmusok még de mindjárt.
És úgy néz ki, nagyon rossz.
Van 2-n, valami exponenciális, amely úgy érzi, még rosszabb.
És mégis, furcsa módon, akkor nincs n cubed, ami ha valami előre gondolkodás,
ha a fajta nem a matematika, a 2 az n valóban lesz sokkal egyenesebb,
jóval feljebb, mint n CubeD, ha megnézi a tengelyek elég messzire ki.
Így észre most ezek tengelye önkényesen 2-10 az x tengelyen.
>> És mit jelent ez?
Ez azt jelenti, 2 fő 10 fő részére a szobában.
Ez minden x: olyan méretű probléma, függetlenül a kontextus.
És egy függőleges tengely körül most is több másodperc, vagy több lépésben -
bizonyos időegység.
De észre, hogy ez a 0-60 és 0 10-ig.
De ha ilyen zoom ki, ahogy azt az Excel vagy valamilyen ábrázolási szoftver,
és felmegyünk a 200.000, észre, hogy valami hasonló a 2 az n
fog teljesen elborít a működési idők n négyzetes,
n CubeD, n log n - mindent, amit beszéltünk eddig.
És mégis, a fogás, amikor elkezd beszélni a dolgokat, mint a Facebook
ahol még sok, sok, sok ember minden összekapcsolt,
Ön n az emberek, akik mindegyike lehet, annyi, mint n barátai
ha mindenki egyfajta kishaver a világon,
nos, ez n-szer n már úgy, hogy ez n négyzetes lehetséges barátságok,
legalább 1 irányba, n faragva lehetséges barátságok.
Annak érdekében, hogy már azt sugallja, hogy a Facebook keresést szociális grafikonon, hogy úgy mondjam,
lehet kezdeni kell kifejezni ilyen típusú képleteket.
>> Majd gyere vissza, és hogy ez sokkal több konkrét,
de most a cél a következő hetek
lesz arra, hogy ne menjen a végrehajtási algoritmusok vagy kódot
Ebből a célból vesz fel annyi időt, mint valami, mint ez.
De érdekes dolog számítógép-tudomány, ha továbbra is az ezen a területen
vevő osztályok, mint a CS121, CS124, mindkettő elméleti tanfolyamok,
az, hogy vannak valójában néhány probléma, hogy létezik a világon
hogy alapvetően, amennyire tudjuk, nem lehet megoldani gyorsabban
mint a legrosszabb ezeket grafikonok ténylegesen sugallja.
Tehát van egy csomó nyitott problémák ebben a világban, hogy nem sokkal jobb, mint az embereknek eddig.
>> Szóval kezdjük majd ezt a példát.
Láttunk Sean küzdenek ezzel a kamera, túl ügyetlenül videón.
De a valóság az volt, amikor Sean bízták meg találni egy táblán, mint ez a szám 7,
Emlékeztetek arra, hogy azt mondtam, hogy "van valahol mögött ezeket a darabokat papír vagy fehér ajtók
"A 7-es számú. Sean, találják meg a számunkra."
És ez csodálatosan kínos nézni
mert ő tényleg küzd ezzel a problémával.
A valóság azonban az volt, Sean ugyanolyan jól, mint bárki más a szobában volna tenni.
Vett egy kicsit hosszabb, mint egy átlagos ember is van,
de feltételezte, hogy volt valami trükk, hogy ezt a problémát,
azt feltételezte, hogy ő hiányzik valami.
És ez sem segített, hogy a több száz szeme szem le rá.
>> De a valóság az volt, ha a bemenet a probléma egy csomó véletlen számok
és te azt kérik, hogy megtalálják 1 ilyen száma,
A legjobb, amit tehetünk, lineáris keresés.
Indítsa el a bal oldalon, lépjünk át a jobb, vagy indítsa el a megfelelő, mozgassa balra.
Visszamenőlegesen, akkor lehet gondolkodni, "Sean, miért nem csak elkezd a másik végén?"
Nos, 7 volna éppen olyan könnyen már itt véletlenszerűen,
de én szándékosan tettem oda, mert gondoltam, hogy nem fog kezdeni a végén.
Szóval ilyen manipulált a helyzetet, hanem a véletlen esélye 7 lehetett volna sehol.
Tehát kezdve a jobb szélen talán jobb lett volna akkor,
de mi van, ha a következő évben a 7-mailt?
Ez nem egy gyökeresen új megoldást a problémára -
1-jétől kezdődően végét, vagy a másik -, amikor nem adott más feltételezéseket.
Így Sean kezdte nézegette a számokat, és azt mondta, "5. Ez nem itt."
Aztán itt van, és látta, 19, aztán megállt, körülbelül 20 másodpercig
Aztán kinyitotta ezt a 13, majd nyilvánvalóvá vált,
hogy nem úgy tűnik, hogy a minta itt.
Nem volt 1, 2, 3, 4 vagy a hasonló. Voltak hiányosságok a számok, ami nem segített.
És túl az a tény, hogy ezek az olcsó használt darab papír, hogy fedezze fel a számokat
valójában szándékos, mert ha én el ezeket a darab papír,
a legtöbben, Sean benne, talán volna pillantott fajta makroszkóposan
a tábla, és azt mondta: "Ó, 7 nyilvánvalóan ott van." Megcsináltuk azonnal.
>> És hogy lehet az út az emberi agy munkálatok bizonyos mértékig,
de a valóságban, a szeme vagy az elme valószínűleg futást a számokat jobbról balra,
balról jobbra, középen out - valami folyik élettanilag
oly módon, hogy úgy éreztem, mintha ez történt azonnal,
de odds még belsőleg volt valamilyen módszert találni 7.
És valóban, most, hogy beszélünk tömbök és adatszerkezetek
és a memória belsejében egy számítógép, az egyetlen dolog, amit az emberek tehetünk
hogy nézd meg az egyedi memóriahelyek 1 egy időben.
>> Szóval minden egyéb helyszín is lehet a fedett fel néhány darab papírt
mert nem látni egyébként. Mi csak akkor van 1 dolog egy időben.
Tehát ebben az esetben, a Sean esetében, mentünk ide, majd mentünk itt
aztán mentünk itt, itt, itt, itt, van okos végére
és csak egyfajta átugrott ezt önkényesen és találat 7 ott.
Ez nem volt különösebben különleges. Ez is volt az elromlott.
De végre megtalálta 7.
De most a elvitelre valóban az, hogy a legjobb, amit tehetünk, ha nem adott információt
más, mint a véletlenszerűen válogatott számok kezdeni a bal vagy indítsa el a jobb.
Vagy fene, akkor véletlenszerűen nyit ajtót, de akkor mit is jelent, hogy véletlen?
Nos, volna, hogy valahogy hivatalossá, hogy mit jelent itt kezdődnek,
akkor megy itt, akkor menj ide. Sean volt nagy, és ez csak szórakoztató nézni.
Mi lenne, ha ehelyett változtatni a probléma egy kicsit, és töltsük fel az idei Sean, ha úgy tetszik?
Kér valaki, hogy kényelmes jön a színpadra, és megoldani egy kicsit más probléma
és a megjelenő kamera?
>> Menjünk túl a zenekar, mert ti már elég részt ma már.
Mit szólnál rózsaszín, a kalap? Gyere le. Mi a neve? >> Alex. >> Alex. Oké.
Szóval Alex lesz az idei Sean és meg fog jelenni a következő néhány évben
értékű CS50 előadások.
Alex, örülök, hogy találkoztunk. >> Örülök, hogy találkoztunk is.
A kihívás kéznél az Ön számára, hogy van, hogy egy kicsit könnyebb
az, hogy én mondom ugyanazt a számok itt, de ők most rendezve.
Szóval most a cél az, hogy megtalálják a 7-es szám.
És valóban, mi kéne, hogy ez a - készen a fajta csalás, mint egy számítógép, nem,
megnézi, mi a számok egy pillanattal ezelőtt.
A kréta ez valójában nem fog segíteni, hogy sok minden,
de most úgy tesznek, mintha nem tudod, mi az eredeti tömb.
Minden, amit most már tudom, hogy van egy sor rendezett számok
hogy lehetnek különbségek közöttük, és a cél az, hogy megtalálják a 7-es szám.
Hogyan, egy ésszerű ember, menjen a megállapítás a 7-es szám?
>> Tovább alacsony és magas? >> Oké. Tovább növekvő sorrendben.
És ne tépje őket. Nézzük csak emeljük fel őket, így mi is újra őket.
Oké, tehát 1. Várj. Mielőtt folytasd, ez 1, nyilvánvalóan rossz.
Szóval, mi megy keresztül a fejedben a következő lépés? Mi a következő lépés?
A következő egy. >> Oké. A következő egy. Jó. 3, így helytelen. Mi a következő lépés?
Keep on megy. >> Rendben. Keep on megy. 5.
Így tovább megy, és hadd adja ezt az utókor számára.
7. >> Kiváló. Nagyon jó. Megtaláltam a 7-es szám. [Taps]
Szóval ez jó volt, de Sean is megtalálta a 7-es szám.
És azt állítják, hogy még nem igazán kihasználva ez a kiegészítő információként,
amely szerint ezek a számok vannak rendezve.
Így tehetünk a jobb? Akármi javaslatok itt? Igen, vissza.
[Hallgató] bináris keresés. >> Fogalmam sincs, hogy mi a bináris keresés.
>> [Hallgató] Indítsa el a közepén. >> Indítása a közepén. Oké. Szóval hátha tudunk eljutni.
Tehát, ha ahelyett, amit mondtam kezdetét a középső, megy előre, és nyissa ki a középső ajtót.
Van 8 őket, szóval kell majd önkényesen választani az egyik
kissé balra vagy jobbra. Oké. 7! [Taps] Very nice.
Oké, de hol voltak megyünk ezzel?
Tegyük fel, csak azért, hogy megtörje a nyakkendő akkor kezdett itt
mert ez is történhetett volna is.
Mi csak véletlenül tudom, hogy 7 volt. Szóval ez a 13.
Tehát, ha ők válogatják, és mi csak most kezdődött el a közepén,
mi lenne az optimális következő lépés lett volna?
Menj a bal oldalon. És itt jön a telefonkönyv példa újra.
Ha 13 van, és tudjuk, hogy a sorrend,
akkor az összes ilyen darab papír érdektelen a számunkra most
mert mi már tudjuk, hogy 7 kell, hogy legyen a bal
Ha ezek a számok vannak rendezve, és találtunk 13.
>> Szóval, mi a következő lépés itt? >> Ugrás a bal oldalon. >> Oké, jó.
Akkor menj balra, és - várj, hé, hé, hé. Ez csalás.
Szóval találat 7, de mi volt az algoritmus már csak alkalmazni?
Indítsa el a közepén. >> Jó. Szóval mi a logikus kiterjesztését ugyanezen ötlet?
Ó, csak ezeket. >> Pontosan. >> Szóval itt kezdődnek. >> Jó.
Tehát most mentünk kissé balra újra. Ez 3.
De az érdekes elvihető most melyik ugye nem kell törődni?
Ezek a 2. >> Ezek a 2. Így most ez lehet menni, ez az egy is elmegy.
Most a probléma, hogy volt 8 akkori 4-es méretű most 2-es méret.
Mi megvagyunk elég közel. Ismét megy a közepére e 2 elemeket.
>> Oké. Szóval ez a fajta sajnálatos, hogy most mi lesz mindig marad, mert mi vagyunk a lefelé kerekítés.
De ez rendben van, mert most dobjuk ezt el, és minden mást, így nekünk csak 7.
Adjunk a tapsot. Találtunk 7 újra. [Taps] Oké. Persze.
Várj, mindössze további 1 másodpercig.
Jóllehet ez a következő folyamat a fajta egy kicsit tovább tartott, mint azt érezte volna,
őszintén szólva, az első ösztöne volt a legjobb, igaz? Találtunk 7 azonnal.
De mi lett volna találat 7 gyorsabb, nem számít, mit, ebben a példában szemben ezt
mert ha a számok minden rendezve, akárcsak az oldalakat a telefonkönyv,
Ön valóban vágjuk fele a probléma ki újra és újra és újra.
És ez nem annyira egyszerű, hogy ez a mindössze 8 számot
szemben a 1000 oldalas telefonkönyv, ahol valóban látni vizuális,
de ebben az esetben itt amikor Sean kerestek és 7,
hány lépést a legrosszabb esetben lenne volna neki? >> [Hallgató] 7.
7 a legrosszabb eset. Nos, a legrosszabb esetben sem, ha van 7 8 ajtó van.
Ez volna neki 8 lépésben.
>> Szóval, ha van n ajtókat, talán volna Sean egy pár évvel ezelőtt n lépéseket.
Most, a te esetedben, Alex, tekintettel arra, hogy ezek a számok vannak rendezve -
és mi lehet a fajta e arra következtetnek, ahol voltunk eddig ebben a történetben -
mi a működési ideje Alex látna intelligens algoritmus
indulunk ki, a középső, majd ismétlődő?
[Hallgató] 3. >> Így lesz 3, durván, ha megy 8-4 to 2-1.
Szóval 3 lépés, vagy még általánosabban, ez log n újra.
Minden alkalommal, amikor éppen felére csökkentését és a felére csökkentését, valamint felére csökkentését és a felére csökkentését,
ez egy kifejezése ez a gondolat a log n.
És így volna, csak 3 lépés, és valóban meg is tett
amint kinyitotta az ajtót, és a felére csökkentése felére csökkentését,
mivel ez volna Sean mintegy 7 vagy 8 lépéseket.
Szóval köszönöm, hogy velünk ebben az évben. >> Köszönöm. Örülök, hogy találkoztunk.
Köszönöm Alex. Hasonlóképpen >>. [Taps]
>> Mi akkor az igazi hatása ez?
Most képzeld el, hogy ez nem 8 ajtó, ami, őszintén szólva, mindannyian találtam valamit
mögött, 8 ajtó elég gyorsan csak a szakadás a darab papír és megy a mi ösztönök.
De mi van, ha ez egy millió ajtókat? Mi van, ha 4000000000 ajtókat?
Abban az esetben, 4 milliárd ajtó, te tényleg szeretne majd menni Alex-algoritmus,
bináris keresést kezdünk hívó, vagy oszd meg és uralkodj, még általánosabban,
ahol tartod felére csökkentését, és felére csökkenteni a problémát,
mert ha 4000000000 ajtó, hányszor tudsz chop 4 milliárd félidőben?
[Hallgató] 32. >> Ez valójában 32. Akkor ezt oldani egy darab papír, vagy a fejedben.
Menj 4000000000-2000000000 to 1 milliárd fél milliárd 250 millió, pont, pont, pont.
És ha te meg a matek, fogsz kapni valóban 32,
és a ténylegesen kapcsolódik számítógép-tudomány, mert általában számolnak 2 hatványai.
2 a 32 történetesen 4000000000.
Szóval van egy csomó releváns ilyen típusú 2 hatványai számítástechnika.
>> De mi a helyzet 8000000000? Hány lépés az, hogy fog tartani, ha van 8000000000 ajtókat?
[Hallgató] 33. Szóval >> 33. Mi van, ha 16000000000 ajtókat? Hány lépés az, hogy fog tartani?
[Hallgató] 34. >> 34. Mi lehet a fajta folytassa ezt orrvérzésig. De ez egy hatalmas dolog.
Lehet bevezetni milliárd látna bemenetek a probléma, de nem nagy ügy,
csak hogy további 1 falatot belőle, és így ad nekünk valami hasonló bináris keresés
vagy oszd meg és uralkodj, általában.
De én vagyok a fajta csalás, igaz?
Abban az esetben, Alex algoritmus, volt előnyt Sean.
Tudta, hogy ezek a számok voltak rendezve, de Alex nem kellett rendezni őket magának.
Én előre jött a táblához, és gondoskodott arról, hogy milyen
hogy felhívta őket arra, rendezetten, aztán fedett őket papírra.
De milyen sok munka volt, hogy engem?
Ha már elindult a számokat valamilyen látszólag véletlen sorrendben -
ebben az esetben ezek egyszerűbb számokat 1-től 8 itt -
hogyan megy a válogatás ezeket az értékeket?
Ha volt egy ember megkapja ezt a feladatot, milyen intuitív megközelítés szedése
válogatásnak egy csomó számok?
Ezek a dolgok rakták ki, mint a puzzle darabkái. Igen.
>> [Hallgató] I venné az egyes számot, és hasonlítsa össze a minden egyes
és menj balra. >> Oké, jó.
Tehát hogy egyes szám, hasonlítsa össze az egyik mellette,
és aztán csak folyamatosan mozog a listában, milyen rejiggering dolgok, ahogy megy.
Tehát itt van egy esély talán még néhány emberek belekeveredni.
Ne már 8 további önkéntesek, akik szeretnék, hogy jöjjön fel?
Egy kicsit kevesebb nyomást, mivel nem te vagy az egyetlen. 1, 2, 3, 4, 5, 6, 7, 8.
Gyere le. Ti lesznek a számokat 1-től 8.
Lássuk, ha nem tudjuk ezt válogatás Alex sok ugyanúgy csináltam előre.
1, 2, 3, 4.
Menj előre, és ha lenne, sorban a színpadra a zeneállvány és ide
ugyanabban a sorrendben, mint a dia a képernyőn.
Uh-oh.
Majd működik, a következő példa. Oh, várj, várj. Itt vagyunk. Várj.
A következő példa most. Tessék. Szám 8. Gyere fel.
Rendben van. Sort magatokat eszerint.
Csúsztassa egy kicsit oldalra a zene itt állni.
Tehát 4, 2, 6 - kap oda, ide, ott - 3.
Igen. Oké. Menj ide. Nem, te maradj ott.
Igen, ott. Nem tévedek. Ott van. Jó, nagyon jó. Oké.
És most nézzük rendezni őket növekvő sorrendben.
>> Hogyan kezdjen csinálja ezt?
Az algoritmus, amely javasolta egy perce volt, miért nem csak összehasonlítani
Az emberek, akik a fajta egymás mellett, majd rögzítse az esetleges hibákat,
mozgó balról jobbra.
Tehát itt van 4 és 2, nyilvánvalóan elromlott. Hadd csere téged. Oké.
Úgyhogy most megyek mozgatni le a pályáról. 4 és 6, nope. [Nevetés]
6 és 8, nagyon jó. 8 és 1, hadd cserélni srácok. Rendben van.
Szóval 8 és 3, csere srácok.
8 és 7, hadd cserélni srácok. 5 és 8, kiváló.
Adok egy rendezett listát.
Rendben van. Tehát nem egészen.
De jobb, mert a nagyobb szám - esetben a 8 -
már fajta buborékoltatunk fel balról át a jobbra.
Szóval 1-et közülük van, de úgy érzi, mintha ez nem igazán oldja meg a problémát.
>> Szóval mit javasolna mi a következő lépés? >> [Hallgató] Tartsuk csinálja. >> Mi folyamatosan csinálja.
És észre újra, mi meg a dolgokat azzal, csak úgy, minden ember
egyfajta intelligens intézkedik magukat alapuló kép
de most már, hogy sokkal módszeres.
Kell lennünk algoritmikus róla, mintha írunk kód -
Ebben az esetben a szóbeli pszeudokód.
Szóval hadd próbáljam meg újra. Ez nagyon jól működött. Ez nem oldja meg.
De amikor kétségbe, csak próbálja és próbálja újra. Tehát 2 és 4, nem segít többé.
4 és 6. Ah! 6 és 1, valamivel jobb most.
6 és 3, jó. 6. és 7, 7 és 5, 7 és 8, a jó.
És tudod, én valószínűleg figyelmen kívül 8 most már, mert ő az a lista végére.
Talán nem kell aggódnia, hogy valaki megy mellette.
De lássuk, hogy ez egy biztonságos feltételezés.
Most lista - rohadt - nem válogatják szét. Próbáljuk meg újra.
SO 2 és 4, 4 és 1, 4 és 3.
4 és 6, jó. 6 és 5, jó.
6, 7, és 8, a jó. De a nyilatkozat, akkor csak meg itt, és most meg itt most?
[Hallgató] Igen. >> Igen?
Mi lenne, ha egyikőtök volt a 9-es számú végig ott?
Ez lett volna rendezve. >> Jó. Ez lett volna rendezve az első alkalommal kb.
Jó. Akkor menjünk vissza. Már majdnem ott vagyunk.
Az 1. és 2., a 2. és 3, 3 és 4, 4 és 5, 5 és 6, 6 és 7, 7 és 8.
>> Én kész, de most megint én vagyok a számítógép csak csinálni, amit én mondtam, hogy nem,
és az egyetlen emléke most, hogy én valójában csak tettem egy kis munka.
Valami megváltozott itt.
Szóval még technikailag nem erősítette vizuálisan vagy algoritmikusan hogy ez a lista valóban rendezve.
Szóval csak a jó intézkedés, csak hogy anális erről, csináljuk ezt az 1 több időt.
Így az 1. és 2., a 2. és 3., 3. és 4.. És tudod mit?
Csak jó intézkedés, megyek, hogy nyomon követhesse a kezem ebben az időben
mennyi swap teszek, csak azért, hogy tudom, hogy mennyi munka, amit valójában tenni.
A 3. és 4, 4 és 5, 5 és 6, 6 és 7, 7 és 8. Nincs swap.
Szóval most azt törvényesen egy idióta, hogy ezt újra
mert ha nem dolgozott ezen keresztül át az emberek,
akkor egyértelmű, hogy ez fog történni újra, ha egyikük sem valami véletlenszerűen
adversarially mozgó maguk körül. Így most tudom abbahagyni.
Most feltenni a kérdést, hogy sok munka volt ez valójában engem?
Hány lépés volt, hogy az el? >> N négyzeten.
Igen, n faragva. Hol kapsz n négyzetes származik?
Be kell, hogy ellenőrizze minden egyes száma -
Van n számokat, és van, hogy ellenőrizze minden egyes szám a többi n számokat.
Jó. >> Szóval ez n faragva. >> Jó.
>> Tehát úgy érzi, hogy nagyon is n négyzetes, ugye?
Van n ezek a srácok, 8 konkrétan ebben az esetben,
de minden alkalommal mentem keresztül ezen a listán voltam összehasonlítva az első, aki ellen a második,
a második ellen a harmadik újra és újra és újra,
és amikor megkaptam a végére, mit tettem? Én redid meg.
Tehát ha általánosítani ezt a magyarázatot, már n emberek
és én vagyok így, nyilván, 8 lépés, n lépéseket, minden alkalommal, amikor megyek keresztül algoritmus.
De hányszor a legrosszabb esetben nem tudom, hogy menjen át ezt a listát az emberek?
[Hallgató] N-szer. Valószínűleg >> n, igaz, mert a legrosszabb esetben
Mi valószínűleg a legrosszabb esetben elrendezése ezek a srácok a get-go?
Ha ők teljesen fordított sorrendben
mert csak tegyük fel, szellemileg, let's - Mi a neve? >> Bowen.
Bowen. Oké. Szóval Bowen, gyere ide egy pillanatra.
>> Tegyük fel, hogy Bowen volt itt elején az algoritmus,
és nem tudom, mi mindenki más, de itt Bowen szerint ez az algoritmus -
és ha azt szeretnénk, hogy csak sétáljon velem - fog buborék fel, mint ahogy az első alkalommal,
egészen a végéig.
De tegyük fel, hogy az adott személy mellett Bowen volt a 7-es szám.
Van, hogy menjen vissza, és kap a 7, ami azt jelenti, hogy el kell menni egészen vissza ide.
Most van, hogy ugyanezen séta a személy, aki a 7-es számú.
De mi van, ha majd 6-os szám mellett volt neki is?
Aztán vissza kell mennem, és kap 6.
Szóval megint minden iterációs e ciklus beszélek az egyes n emberek,
és talán van, hogy n e séták hogy győződjön meg arról vagyok húzva
minden a legnagyobb elem vissza, és vissza, majd vissza a legvégén a listán.
Tehát n dolgok n-szer csak n-szer n vagy n faragva.
>> Tehát itt már van egy algoritmus, amely már nem n, hogy már nem log n,
ez valóban rosszabb, mint bármi, amit eddig csináltunk.
Szóval Alex ilyen szerencsés az, hogy én mindent megtettem a munka látszólag előre neki,
az összes drága munkát, hogy tudta élvezni ebben a bináris keresési algoritmust,
amely a log n.
De ez összhangban van a hétfői témát.
Adtunk egy kicsit több helyet, szoktuk több bit, annak érdekében, hogy felgyorsítsa a működési idő.
Annyira, mint itt van ez a trade-off közötti térben és időben,
ott azt is csak lenni kompromisszumok között eltöltött idő elöl a fajta a dolgok kész
és ténylegesen végrehajtó algoritmus, mint a keresés. Próbáljunk egy másikat.
Ha ti nem bánja csak gyorsan átrendezve magatokat egyeznie újra,
próbáljunk valami kicsit más, ha ez nem olyan egyszerű
mint csak rögzíti az összes páros hibákat, ami szuper intuitív.
Nézzünk inkább egy kicsit szándékos és ezt.
Ez is azt javaslom, valószínűleg elég intuitív.
>> Nézzük válasszuk ki a legkisebb személyt a listáról újra és újra. Szóval itt vagyunk.
4, te vagy a legkisebb ember, akivel így láttam eddig,
így fogok emlékezni, hogy mentálisan, egyszerűen mutatva, hogy most.
2. Ó! Felejtsd el a 4-es számú. Most találtam az új legkisebb elem a listában.
Fogok a fajta emlékszem. 6, 8.
Ó! 1. Viszontlátásra. Tehát most fogok emlékezni az 1.
Tudjuk, hogy 1-es a legkisebb, de én vagyok a számítógépet. Mi van, ha van egy 0?
Mi van, ha a -1? Meg kell tartani fog.
Így 3, 7, 5, nope. Oké. Szóval, 1-es szám volt a legkisebb.
Hadd válassza ki Ön a listáról - we'll menni ezen a módon -
és tegye meg önkényesen elején a lista.
Na, várj egy percet. Valahogy csalt.
Ha ezek a srácok nem képviselnek egy listát 8 fős, hanem egy tömb,
8 darabokat összefüggő memóriaterületet - nem bánja megerősítéséről vissza egy pillanatra?
Itt tényleg nincs hely neked itt.
Szóval hogyan tesszük helyet - mi a neve? >> Sammy. >> Sammy.
Hogyan teszünk helyet Sammy?
>> Mi mozog a n, amelyek előttem. >> Oké.
Így tudnánk mozgatni az n, akik előtte,
így ha akartok, hogy 1 a szándékos, drámai lépést a bal oldalon.
Mindannyian tette, hogy egyszerre, de a múltkor írtam egy kódot,
nem tudja rendezni a mozgás sok dolgot egyszerre.
Megtehetjük azt egy hurok, mozgó mindenki egyszer egy időben.
Tehát, ha ti nem bánja lépett vissza a jobb oldalon,
és Sammy, ha tudna lépést vissza, mert még mindig nincs hely az Ön számára,
Most csináljuk ezt. Hol volt Sammy egy pillanattal ezelőtt? Ott van.
Szóval van egy rés van. Szóval lehet beköltözni Sammy helyszínen.
Most következő személyt, és most következő személyt, most következő személyt. Most szoba Sammy.
Most, hogy valaki a közönség soraiból -, hogy jó volt, hogy helyes volt,
úgy éreztem, egy kicsit időigényes - mi a gyorsabb? Igen.
[Hallgató] Egy új tömb? >> Mi ez? >> [Hallgató] Egy új tömb? >> Oké, jó.
>> Így összhangban e téma csak kompromisszumok, miért nem csak, hogy egy új tömb
és azután Sammy kerül úszás térben előtt ezeknek az embereknek, például,
és mi is csak elkezd kitöltésével egy új tömb összesen. Ez is működni fog.
De nem érdekel kiadások több helyet ma. Mi a másik megközelítés?
[Hallgató] Swap. >> Oké. Mi is csak csere e 2 srácok. Mi a neve?
Mario. >> Mario. Szóval Mario, te voltál a jelenleg itt van.
Sammy, tudsz biztonsági másolatot csak egy pillanatra? Mario itt volt.
Jelenleg nincs hely többé, úgyhogy ha nem bánja majd, ha Sammy van,
berakunk Sammy itt, és most azt állítják, hogy Sammy csere művelet sokkal gyorsabb.
Sikerült 1 művelet csere ezek a srácok, vagy talán a 2 cserélni ezeket a fickókat,
de nem tettünk 1, 2, 3, 4, hogy a jobban érzi magát. Na, várj egy percet.
Valahogy tett a probléma rosszabb, mert 4-es számú kedves volt, közel az elején.
Most 4-es szám egy kicsit közelebb e célból, de nem igazán tudja, vagy érdekel.
Tehát ez csak balszerencse, hogy a 4-es szám egy kicsit távolabb a szánt helyen.
Szóval most ismételje meg ezt algoritmus.
>> Ahhoz, hogy újra bedugni, amíg a történet, minden, amit tett, séta a listán
keresi a legkisebb számozott személy.
Tehát most csináljuk újra. Nem kell aggódni Sammy többé.
Mi is csak ide. Ó! 2. szám. Ez elég kevés.
6, 8, 4, 3, 7, 5. Oké, jó.
És szerencsére, a véletlen, nem kell mozgatni - >> Willie.
Willie mert ő az ő helyén most.
Csináljuk újra, és figyelmen kívül hagyja ezeket a 2 srácok.
6. Ez elég kevés. Ó! 8 határozottan nagyobb.
4. Nézzük összpontosít 4. Ó! 3 még jobb.
7 és 5. Szóval, mit csináljunk most - >> Roger. >> Roger?
Nézzük csere őt 6-os szám.
Tehát, ha 6 és 3 szeretném cserélni,
voltunk már ilyen ütött szerencsés az, hogy a 6 közelebb hol kell lennie,
de ez csak véletlen egybeesés van. Úgyhogy most ide.
8 egy nagyon kis számban. Ó! 4 kisebb.
6, 7, 5. Mit fogunk most csinálni? Swap >>. >> Pontosan.
Tehát most csináljuk ezt a fajta gyorsabb.
8, 6, 7, 5. Amennyiben ez 5 menni? Jó. Oké.
6, 7, 8. 6 kap, hogy maradjon, ahol van. Mi a neve? >> Rosalie.
Rosalie kap, hogy maradjon, ahol van. 7 kerül - Lássuk csak. 7, 8. Oké.
Így 7 lesz, hogy maradjon, ahol van. Mi a neve? >> Amna. >> Amna.
>> Szóval Amna kap szállást, hol van, és a 8-as szám már ahol most kell.
Oké, jó. Érzés mi csak létre munkát magunknak itt, mégis.
Mi végül a futási ideje ez az algoritmus?
Ha végiggondoljuk ezeket az embereket nem 8, hanem n? >> Ez n.
Ez n lépéseket, de mi ellenőrzése minden egyes alkalommal.
Oké. N de te ellenőrzése minden egyes alkalommal?
Oké, de ha ez n lépéseket, nem voltam képes rendezni Önnek csak lesz 1, 2, 3, 4?
Oh! Oké, ez egy nagy különbség.
Tehát n kockás miért? Mi történik valójában?
Van n ember ebben a listában, de megtalálni a legkisebb ember a listán
a legrosszabb esetben, hány lépést kell még tenni? N. >>
>> N, igaz, mert a legrosszabb esetben az 1-es szám az egész az út ott,
így azt kell menj vele.
És akkor, amikor végre észre, 1 volt a legkisebb, akkor elég gyorsan cserélni őket.
De most el kell kezdeni az elejétől, és keresse meg kicsoda?
A következő legkisebb ember, amely 2. Amennyiben a legrosszabb esetben 2?
Ó, Istenem. Ez egészen ide a végén.
Szóval most már csak tett egy lépést n, egy másik n lépéseket.
És ha van n az emberek és a legrosszabb esetben a legkisebb személy n lépésre,
ez megint n-szer n, és így megint van n faragva.
Ez nem érzi túl jól.
És valóban, még a legjobb esetben - tegyük fel, hogy elindul rendezve -
hány lépést tart nekem ezt az algoritmust, hogy rendezni ezeket n az emberek?
N kockás. >> Hallottam n faragva. Miért n kockás?
Mert még mindig van, hogy ellenőrizze minden egyes alkalommal. >> Igen.
És meg kell cserélni őket. >> Annak ellenére, hogy az emberek ilyen mindentudó
abban az értelemben, hogy vizuálisan tudunk csak egyfajta látni, hogy ez van rendezve,
a számítógép nem olyan okos.
Úgy fog kinézni itt és itt és itt,
de ha mit keres a legkisebb elem,
csak tudja, hogy megtalálta a legkisebb elem, amit pont? Ha már a végén.
De ezen a ponton még csak megtalálta a jelenleg legkisebb elem.
Nem feltétlenül tudnak mást arról, az állam a világon.
Szóval kell menni újra és újra és újra.
>> Szóval ezúttal tényleg nézd buta, mert én ellenőrzése, oké, 2, te vagy a legkisebb,
de nem tudom, hogy összességében még.
3, 4, 5, 6, 7, 8. Oké, jó. 2 volt valóban a legkisebb.
Most megtalálja a következő legkisebb. Oké.
3, te vagy a jelenleg a legkisebb. Lássuk. 4, 5, 6, 7, 8. Oké, szerencséje volt megint.
3 valóban a megfelelő helyen. De megyek, hogy ezt újra és újra és újra.
Hogyan tudjuk ezt valaha is így kicsit jobban?
Ahelyett, hogy az emberek bubble up páros a legkisebbtől a legnagyobbig
és ahelyett, hogy előre és hátra a listában kiválasztja az akkori legkisebb személy,
miért nem inkább be ezeket az embereket egy új listát lépésről lépésre?
Próbáljuk ezt. Most hadd hívjam fel ezt a dolgot beszúrás sort.
Tehát itt vagyunk itt. 1. szám. Nem érdekel senki más ebben a listában.
A célom most az, hogy az 1-es szám elején egy rendezett lista.
És én fogom javasolni, mert én csak 8 darabokat memória,
önkényesen most én vagyok a fal között én állítólag rendezetlen lista,
és bárki, aki a hátam mögött fogom igénypont van rendezve.
Tehát most már 1-es szám.
Azt szeretné szúrni neki az én rendezett lista, szóval én csak fog elmozdulni falamon ide,
és most azt állítják, ez a sorrend, ez a lista a szétválogatás nélküli - legalábbis amennyire én tudom.
Nem látom az összes számot egyszerre.
>> Most történetesen találkozik a 2. Mit csináljak vele?
Én be most a rendezett lista. De észre, milyen könnyű volt.
Csak meg kell nézni. 1. szám ott van. Oh, természetesen 2 megy mellé 1-es szám.
Most mit csináljak, 3? Én be titeket a rendezett lista. De ez szuper volt könnyű.
Ez szuper könnyű, ez szuper könnyű, ez szuper könnyű, szuper könnyű, szuper könnyű.
És most mindent rendezve a hátam mögött, és hány lépést tett, hogy az el?
[Tanulók] N. >> Szóval ez csak n. Szerencsések vagyunk.
Csak n miért? >> [Hallgató] Mivel a lista sorrendje.
A lista már rendezve. Szóval szerencsénk volt.
De Ajánlott egy algoritmust, ebben az időben, hogy kihasználja ezt a fajta szerencse,
hogy a legjobb esetben is, azáltal, hogy nem vesztegeti felesleges időt.
Tehát most már mit fogunk hívni buborék féle
ahol az emberek a fajta buborék felfelé páros.
Most már van választék sort ahol tépni ki a legkisebb ember újra és újra.
És most már a beszúrási sort, ahol egyfajta proaktív az embereket, ha azok tartoznak
az egyre inkább rendezett listát.
Ha tudnánk, a tapsot ezeket a fickókat itt. [Taps]
Nézzük mi 5-perces szünet van.
És mikor jön vissza, akkor fújja az összes ilyen algoritmusok ki a vízből
valami jobb. Rendben van. Köszönöm szépen. Tudod tartani ezeket emlékbe.
Rendben van. Mi vissza.
>> És újra bedugni igazi böjt, mi volt a 3 különböző megközelítések válogatás,
a lényege az volt, hogy arra a pontra, ahol valaki, mint Alex
lehetne keresni számok listájának gyorsabb, mint valaki, mint Sean tudott.
És bár van ilyen egyszerű példákat 8 számot,
akkor kivetíteni könnyedén 8-weboldalakat, 8 milliárd weboldal,
vagy 800.000.000 barátait a Facebook.
Így ezek az algoritmusok természetesen méretezni, hogy az ilyen jellegű értékek,
és az ötletek végül ugyanaz.
Szóval buborék rendezés volt az első, ahol ilyen vezetünk ki a legnagyobb ember
egészen jobbra swapping ember páros.
Aztán volt, mit fogunk hívni kiválasztási sort, ahol egy kicsit szándékosan
tartotta nézi át a listát, kiválasztja a legkisebb számú, újra és újra és újra,
a logikus következménye, amely szerint a listát végül rendezve.
Aztán a harmadik, én ki az embereket a megfelelő helyre,
és csináltunk egy nagyon kitalált példa, hogy a lista már rendezve,
de ez volt az üzenet, hogy a beszúrási sort esetében,
akkor szerencséd lesz.
Ha a számok már rendezve, ez csak akkor fog eljuthat n lépéseket alátámasztani
mivel a kiválasztási sort te egy kicsit csőlátás
és soha ne észre, hogy a lista már rendezve.
Tehát lássuk buborék nemében akció itt.
A következő példában azt mindjárt látni függőleges sávok
amelynek magasságát a számoknak, hogy mi is egyfajta Visualize válogatás történik.
Minél kisebb a sáv, annál kisebb ez a szám, annál nagyobb a sáv, annál nagyobb a szám.
>> És fogunk játszani ezen alapértelmezett sebességet.
Ez lesz mozogni egy kicsit gyorsan most, de a vörös, ami megmutatja 2 bár
összehasonlított egymás mellett.
És ha közelről nézni, hogy mi történik, hogy ha a sávok ki annak érdekében,
a kisebbik lesz mozgatni a bal, a nagyobb egy jobb,
és akkor folyamatosan halad.
Tehát ha ezt újra és újra, észrevenni, hogy a legkisebb rudak
megy folyamatosan araszolnak az utat a bal
és a legnagyobb bárok fog tartani araszolnak az utat a jobb oldalon.
És valóban, mi kezdik látni a minta végig a jobb oldali
mint láttuk, 8, majd végül 7 bugyogott fel a túlsó végén az emberi listáját.
Tehát ez lesz nagyon gyorsan egy kicsit unalmas, úgyhogy hadd megállítani ezt egy pillanatra.
Hadd változik a sebesség sokkal gyorsabb lesz.
Én nem változik az algoritmus, én csak azt, hogy az animáció történik gyorsabb.
Mégis buborék rendezés, azonos algoritmus,
de most már láthatod sokkal gyorsabban, mint a verbális demonstrációs
hogy a legnagyobb elemek valóban bugyogott fel a csúcsra.
>> Mint félretéve, ezek a kis négyzetek a bal alsó és a jobb alsó
csak kis emlékeztető, hogy hány összehasonlítást csinálsz.
De most, tudunk összpontosítani a piramist, ami kialakulóban, és ott megy.
A legkisebb elem a bal oldalon, a legnagyobb a jobb oldalon, és minden más között.
Most ahelyett, hogy egy pillantást kiválasztás sort.
Én megyek előre, és nyomja meg a Stop gombot. Megyünk, hogy egy új random sor bárok.
Selection sort, visszahívás, megy át a listát újra és újra és újra,
kopasztás ki a legkisebb elem. Tehát itt van választás sort.
Úgy néz ki, ott van kevesebb munkával történik most, mert nem vagyunk páronkénti összehasonlításával
de mi csak egyfajta cseresznye szedés a legkisebb elemeket jobbról balra.
Ez volt nagyon kevés időt, így van egy kettősség már.
Csak azért, mert egy algoritmus azt mondta, hogy n négyzetes időt, mint a buborék rendezés
és hasonló kiválasztás sort, ezek tényleg legrosszabb esetben üzemidő.
Például abban az esetben, mondjuk, kiválasztás sort,
Igazából én kiválasztja a legkisebb személy és üzembe őt ide,
akkor csinálom újra, akkor csinálom újra,
de volt egy kis optimalizálási tudtam tenni.
>> Amint költözött szám 1 itt - Sammy ebben az esetben -
mit kell tennem vele ezután? >> [Hallgató] Hagyd őt.
Hagyd őt, ugye? Semmi.
Nem kell, hogy valaha is beszélni Sammy újra, mert ha én kiválasztotta a legkisebb elem
és tedd, hogy itt, miért vesztegeti az idejét, majd a végén a teljes listát?
A következő iteráció hadd ténylegesen mozgatni csak a 2-es számot, csak a 3-as szám.
Így valójában, én nem csinálok dolgokat n n-szer.
Csinálok n dolgokat, akkor n - 1 a dolgokat, akkor n - 2 dolog, akkor n - 3 dolog,
akkor n - 4, pont, pont, pont.
Van egy kis mértani sorozat, ami csak azt jelenti,
te összeadásával egyre kisebb számban.
Nem n + n + n + n de n + 7 + 6 + 5 + 4 + 3 + 2 + 1.
És mi van, hogy általában működik ki, hogy -
Fogom elrontani a fórumon itt egy pillanatra -
ez működni fog ki, hogy valami hasonló n (n - 1) / 2
ha csak ilyen pillantást a hátán egy matematikai könyv, ahol az összes cheat lapok
a képleteket.
Ha csak hozzá valami n + n - 1 + n - 2, működik ki, hogy valami ilyesmi.
És ha csak egyfajta szorzás ezt ki, ez n négyzeten mínusz n / 2.
Azt hajtogatta n négyzetes, bár, és ez azért van, mert én voltam a fajta vesz egy mentális parancsikont
mert a valóságban, n négyzetnagyságrendű mínusz n osztva 2 valóban a valódi lépésszám
hogy egy algoritmus, mint kiválasztási sort venné, ha valóban számít fel
az összes ilyen összehasonlítások és az összes kicsit elfoglalt munkát csinálunk.
De őszintén szólva, ha n kap, hogy legyen, mint egy millió, vagy milliárd, ki a fene törődik
ha csinálsz egy milliárd squared mínusz egy milliárd osztva 2?
Egy milliárd squared egy hatalmas szám.
Tudod hogy egy milliárd le azt - n. Ez nem olyan nagy ügy.
Tehát minél nagyobb a számokat kap, a kevésbé fontos az alacsonyabb rendű kifejezések.
Kit érdekel, ha osszuk el 2, ha te beszélsz quadrillions számok a lépések?
>> Így általában, számítógépes szakemberek hajlamosak eldobni mindent, de a legnagyobb ciklus,
és mi csak egyfajta egyszerűsítése a világot, és azt mondják, hogy az algoritmus
tudomásul durván faragva n lépéseket. Ez a működési idő egy algoritmus.
Szóval jövünk vissza ezt egy pillanat néhány konkrét példákkal,
de most, hogy ez a fajta az intuitív motivációja éppen egyszerűsítése világunk
és beszél a legfontosabb feltételeket, ahelyett, hogy az összes ilyen divatos képleteket.
Szóval ez volt a kiválasztás sort, és van egy kis szerencséje van.
Nézzük beszúrási sort. Hadd menjek előre, és indítsa el ezt is.
Most már észre, a minta, ami történik, egy kicsit más,
és elkezdtük a véletlen számokat,
de ha tényleg számít fel a lépések száma a legrosszabb esetben,
ha a lista indult teljesen a megfelelő sorrendben,
mi lenne csak n lépéseket megvalósítani annyi.
>> De ha a lista ténylegesen hátrafelé - például, ebben az esetben itt -
akkor észre, valójában meg kell csinálni egy sokkal több munkát, ebben az esetben.
És ez kell, milyen érzés úgy, mint ez a fajta munka nehezebb
hogy a kisebb elemeket a bal oldalon, és ez azért van, mert mi van szerencsétlen.
A lista sorrendje véletlenül fordított.
Ezzel szemben, beillesztés sort, ha utánozzák, amit tettünk a mi emberek itt
kiindulva mindenki osztályozzák, majd indítsa el, ez egy elég jó algoritmus, ugye?
Ez már, sőt, rendezve.
Akkor próbáljuk meg összefoglalni, hogy pontosan mennyi ideig ezek a dolgok vesznek minket
bevezetésével egy kicsit a zsargon vagy jelölési, hogy valójában sokkal egyszerűbb
mint fanciness fajta sugallja.
Ez a dolog itt, ez a nagy O a képernyőn, amit egy számítógép tudós általában használni
leírni a legrosszabb futási ideje algoritmus.
>> Ismét, a legrosszabb esetben, ez teljesen kontextus-függő.
Mit értünk a legrosszabb esetben teljesen függően változik a probléma beszélünk.
De abban az esetben a válogatás, mi a lehető legrosszabb forgatókönyv?
Minden visszafelé, mert csak úgy érzi, mintha azt jelenti, hogy a sok munka számunkra.
Már papírra vetette néhány olyan algoritmusok láttunk eddig:
lineáris keresés, bináris keresés, mint a telefonkönyv, illetve a darab papír,
majd buborék rendezés, kiválasztás sort, és a beillesztés sort, mint láttuk, a mi emberek,
majd az 1 másik, ami végül lesz hívják egyesíteni sort.
Tehát a lineáris keresés a legrosszabb esetben, hány lépést tart, hogy megtalálják a 7-es szám
ha van n ajtók, mint Sean képű? >> [Hallgató] N.
N. Így fogunk írni nagy O n.
Én csak majd töltse ki néhány üres. Ez csak egy rács üres.
De a legjobb esetben a lineáris keresés, 7 lehetett volna legelején a lista,
és Sean volna elkezdtem keresni elején a listán.
Szóval, ha lineáris keresést, és csak ellenőrzés balról jobbra, vagy talán jobbról balra -
ők ezzel egyenértékű - a legjobb esetben hány lépést talán lineáris keresés,
mint Sean algoritmus, el? Csak 1 lépés.
>> Szóval fogom mondani, hogy ez az omega jelölést.
Ez csak a tőke omega.
Omega csak a szexi szóval legjobb esetben működési idő.
Tehát a legjobb esetben a futási idő egy lépésben vagy állandó lépések száma -
1 ebben az esetben -, de a legrosszabb esetben, nagy O, valójában N lépésben.
És ez itt, theta, mi valójában nem fog nézni most.
Ez nem vonatkozik az adott példát.
De most próbáljuk bináris keresés.
A legrosszabb esetben a bináris keresés, hány lépést is fog tartani, hogy megtalálják a 7-es szám
vagy bármilyen keresünk? >> [Hallgató] Bejelentkezés n.
Még mindig megy, hogy log n, mert ugyanúgy, mint Alex kapott szerencsétlen
amikor valóban eljutott a problémát módszeresen
és ő nem találta a 7-es számú, amíg az utolsó ajtó nézett,
még akkor is, méltányosság, megkapta eldobni bizonyos ajtókat az út mentén,
bináris keresés legrosszabb esetben egy futási ideje log n.
És megint, hogy beszél e elosztjuk és hódító.
De mi a helyzet a legjobb esetben?
És Alex tényleg tapasztaltam, hogy a legjobb esetben is igaza van, amikor jött fel a színpadra.
Hány lépés volt, hogy vegye a bináris keresés? >> [Hallgató] 1.
1, csak azért, mert szerencsés.
De ez jó, mert omega hivatkozik legjobb forgatókönyv esetén,
legjobb esetben bemenet, akkor is, ha ez csak véletlen buta szerencse.
>> Nos, ezt is fogjuk csak egyfajta szabadság üres most.
Hogy van most bubble sort?
A legrosszabb esetben a buborék rendezés, mindenki fordított sorrendben,
így kell csinálni egy csomó pezsgő.
De hány lépés az, hogy megy, hogy a legrosszabb esetben? >> [Hallgató] N faragva.
Ez volt az a n négyzetes, mert ha belegondolsz,
Ha a lista teljesen hátra - 8 ide, az 1 ide -
A dolog kezd buborék, a 8-as számú fog mozogni e az út, ezt,
Ily módon, ez az út, de hol van a 7-es szám a legrosszabb esetben?
Itt van még mindig ott van. Tehát meg kell csinálni újra és újra.
És ez az, ahol megkapjuk n lépésben, majd n - 1 lépésben, majd n - 2 lépéseket.
És ha veszem a szót -, hogy ha ilyen megszorozzuk ki,
ez durván faragva n a végén néhány más feltételekkel, akkor ne törődj most -
akkor a legrosszabb esetben buborék rendezés n négyzetes ide vagy oda.
De mi a helyzet a legjobb esetben a bubble sort?
Mi a legjobb esetben? Minden a számok sorrendje már.
És mi volt a heurisztikus használtam, a trükköt használtam,
jönnöm, hogy nem tettek a munka és így megállítani korán?
[Hallgató] Ellenőrizze egyszer. Ellenőrizze >> egyszer. De mit csináltam az út mentén?
Én annak nyomon követését, hogy hány swap csináltam.
És rájöttem, ha még nem számított semmilyen csereügyletek ujjaim, aztán csináltam nincs munka.
Én biztosan nem próbálkozik semmilyen munkát újra, így tudok csak megáll.
>> Így a legjobb esetben a buborék rendezés, ha a lista már rendezve,
mit mondana az omega jelölés, a legjobb esetben futási idő?
Ez csak n. Van, hogy némi munkát, de csak meg kell csinálni 1 sétát érdemes a munka.
És itt is fogom elhagyni ezt a részt üresen.
És most kiválasztás sort.
Selection sort már nekem kopasztás a legkisebb ember újra és újra.
És mit mondunk a futás ideje, hogy az volt?
Ez n kihúzta a legrosszabb esetben.
És sajnos, a legjobb esetben ez is n squared
mert nem az a fajta mindentudó kilátás nyílik az egész világon;
Csak azt tudom, hol teljes iterációs hogy én valóban találtam a legkisebb ember.
Szóval kiválasztása fajta ilyen szar ebben az értelemben,
de a fejjel ez a fajta intuitív.
Elég könnyű kódolni, mert csak annyit kell tennie, hogy írjon egy pár beágyazott a hurkok,
általában, hogy megy keresztül keresi a legkisebb elem
és majd hozza a legkisebb elem, ahova tartozik az a lista végén.
Tehát itt is lesz egy trade-off.
Az az idő tart, hogy úgy gondolja, és hogy ténylegesen dolgozzanak valamit kódírás
nagyon is több időt vesz igénybe, ha szeretne egy jobb algoritmust és gyorsabb teljesítményt.
>> De ha tényleg csak ilyen kód valamit gyors és piszkos
és csak a fajta meghozza a lehető legostobább ötlet lehet gondolni,
hogy eltart egy pár percig kódot, de a nagy adathalmazok
az algoritmus akár órákig is futtatni.
És még azt a doktori iskola néha ezeket a kompromisszumokat.
Lenne 03:00, próbáltam elemezni nagyon nagy adathalmaz
kapcsolatos biztonsági kutatás csinálok, és azt sem költeni 5 perc
csípés a program elemzi az adatokat, és menj aludni
vagy eltölteni 8 órát kapok csak jobbra, úgy fut azonnal, és nem megy aludni.
És így is ez a fajta tudatos döntés.
Kevesebb fejlesztési időt, több alvás.
Visszatekintve, valószínűleg nem ösztönözhet, hogy a
ha a cél itt az, hogy optimalizálja minősége a kódot,
de ez is a valós világ egy nagyon ésszerű kompromisszum.
Kevesebb idő, kevesebb a teljesítmény vagy fordítva.
Tehát itt végre kap egy esélyt, hogy beszélni theta.
Theta jelölés van valami számítógépes tudósok hozza fel beszélgetés
amikor a nagy O és omega történetesen ugyanaz.
Azt mondod, theta, hogy valóban az üzenetet, hogy ez a fajta egy szűk kötve.
Nem számít, hogy a forgatókönyv jó vagy rossz, ez n faragva.
Szóval csak nem releváns ezeket a történeteket itt.
Insertion sort az utolsó néztük,
ahol éppen behelyezése mindenkit a megfelelő helyre.
A legjobb esetben mi volt a futási idő a behelyezés sort ahogy láttuk itt?
[Hallgató] A legjobb esetben? >> A legjobb esetben.
>> Azt n, mert a legjobb esetben mindenki rendezve,
és Sammy és senki más nem igazán kellett költözniük egyáltalán.
Ők már a megfelelő helyen.
Így beszúrásos rendezés a legjobb esetben az, ebben az esetben, n.
De a legrosszabb esetben ez a fajta n négyzeten. Miért?
Ha a listát emberben fordított sorrendben,
Én először kezdi el a 8-as számú, és beilleszteni őt a jobb helyzetben, ami itt van.
Valahogy mozog oldalra. Ezek a srácok a szétválogatás nélküli, ő van rendezve.
De most történik, hogy megtalálja, aki a következő? >> [Hallgató] 7.
7 a legrosszabb esetben, mert fordított sorrendben.
>> Tehát itt van 7. Amennyiben nem 7 tartozik? Határozottan mögöttem.
De most 7 ténylegesen tartozik közvetlenül nem a hátam mögött, de mögötte száma 8,
így azt kell mondani, hogy "Elnézést, 8-as számú, legyen szíves mozogni így
"Hogy helyet csináljon 7?" Most találkozom 6.
"Ó, bocsánat, a 8 és a 7-es számú, tud mozogni, hogy a szoba 6?"
Más szóval, a beszúrási sort, bár én nem csinál sok mozgás,
az emberek a hátam mögött csinál sokkal több munkát, és hogy van a költségek valaki időt.
Ez fog kerülni a számítógép idő.
Tehát abban az esetben, helyezés sort még mindig szenved.
Ha elkezd összeadjuk az összes lépést, a végén üti durván négyszögletesre n
mert ezek a srácok kell, hogy helyet csináljon az ember kell beilleszteni vissza ezt a listát.
És így ebben az esetben a theta csak nem alkalmazható az adott történetet kéznél.
Ez mind szép és jó. Jelenleg a 3 különböző módon beszél a működési idő.
De mit jelent ez valójában azt jelenti, reálértéken, ha valóban megpróbál kódolásához ki egy algoritmust?
>> Hadd javasolni, hogy van egy még jobb algoritmust ott
hogy maga is bizonyos kompromisszumokat.
Fogjuk hívni egyesítése sort, és ez a fajta e varázslatos algoritmus
hogy csak gyorsabban dolgozik, valahogy, és ez olyan könnyű, hogy kifejezze, legalábbis pszeudokód.
Végrehajtása az algoritmus merge fajta lesz a következő.
Amikor adott n elemek - n számok, n az emberek, függetlenül - először van egy józan csekket.
Ha n kisebb, mint 2, merge sort csak megáll. Ez visszatér, hogy úgy mondjam.
Miért hagyja abba, ha n kisebb, mint 2? >> [Hallhatatlan tanulói válasz]
Rendben. És megint, n nem a szám a listán, n a méret a listán.
Ha n értéke kisebb, mint 2, azt jelenti, hogy a lista az vagy 1,
hová nyilvánvalóan válogatni, ha ez száma 1,
vagy 0, ebben az esetben nincs mit rendezni,
ezért szükségünk van erre a fajta alapeset.
Ha a lista annyira rövid, hogy csak semmi köze, a szó szoros értelmében nem csinál semmit. Vissza.
Ellenkező esetben rendezni bal felén az elemek, majd rendezni a jobb felét az elemek,
majd egyesíteni a 2 fél rendezve.
>> Ez a fajta úgy tűnik, mint egy kis csaló, amelyben azt kérem, hogyan kell rendezni elemek
, és azt mondod: "Rendezze a bal felét, rendezze a jobb felét."
Olyan vagyok, mint: "Rendben. Hogyan rendezheti a bal felét?"
"Sort a bal fele a bal fele, rendezheti jobb felét a bal felét, majd a kész."
Te milyen ciklikusan meghatározása, hogy mit jelent rendezni,
de kiderült, hogy ez valóban zseniális ebben az esetben.
Ez nem igazán az ördögi kört, amely soha nem ér véget
mert ez nem fejeződik be, amikor? >> [Hallgató] Mikor éri el az 1 dolog.
Mikor éri el az 1 dolog.
Így, bár lehet, hogy kezdeni 8 ember, és azt mondják, "sort a bal fele ezeknek az embereknek,
E 4 személy ", akkor azt mondom," Hogyan rendezheti a bal felét? "
"Nos, rendezheti 2 személy itt." És akkor te, mint: "Oké, rendben."
"Hogyan rendezheti bal felén azokat az embereket?"
"Csak rendezni ezt 1 ember itt." Mi a zseniális kinyilatkoztatás most?
Meg kell rendezni 1 fő részére. Kész. Nem tudom, hogy csináljanak valamit.
De most el kell rendezni ezt a személyt, de ők egy személy, semmi köze.
>> Tehát a mágia nyilvánvalóan ebben harmadik lépés: összevonja a rendezett felét.
Szóval merge sort veszi ezt a ragyogó betekintést, hogy ha törik egy nagy probléma le
a 2 kisebb, azonos méretű problémák
és majd csak ilyen ragasztó a kisebb megoldásokkal együtt a végén,
Azt javaslom, hogy tehetünk sokkal, de sokkal jobbak [megérinti hang]
mint bármelyik kiválasztási szettbe vagy beszúrási sort.
Már valóban figyelmen kívül hagyják, hogy egy fél órát, de én tényleg nem tudom, hogy mi folyik itt
ezen kívül ma. [Berregő hang] [nevetés]
Tehát lássuk, ha látja ezt egy kis segítség a barátunk Rob Bowden.
Van 2 nagy lépés a folyamat merge sort.
Először is, folyamatosan szét a listáját cups figyelembe félidőt
amíg van egy csomó listák csak 1 csésze őket.
Ne aggódjon, ha a lista tartalmazza a páratlan számú
és nem lehet, hogy egy teljesen tiszta vágás között.
Csak önkényesen válasszon, amely lista tartalmazza az extra pohár be
Szóval szét ezeket a listákat.
Most van 2 listákat.
Most már 4 listákat.
Most már 8 listák egy csésze mindegyik listán.
Szóval ez azt az 1. lépést.
A 2. lépés már többször egyesítése pár listák segítségével az egyesítés algoritmus tudtuk korábban.
Egyesítése 108 és 15 a végén a listát 15, 108.
Összevonása 50 és 4 a végén 4, 50.
Egyesítése 8 és 42 a végén 8, 42.
És egyesülő 23 és 16-a végén 16, 23.
Most minden a mi listák a 2-es méret.
Figyeljük meg, hogy mind a 4 listák sorrendje,
így tudjuk kezdeni egyesülő pár listák újra.
Összevonása 15. és a 108. és 4 és 50 mi előbb a 4, akkor a 15,
akkor a 50, majd a 108.
Összevonása 8, 42 és 16, 23 mi előbb a 8, akkor a 16,
akkor a 23, majd a 42.
Így most már csak 2 listák 4 nagyság, amelyek mindegyike rendezve.
Tehát most már eleget a 2 listákat.
Először vegyük a 4, majd vesszük a 8, akkor vesszük a 15
és 16 és 23, valamint 42 és 50 és 108.
És mi történt. Most már van egy rendezett listát.
>> Rob kedves volt kihasználják valamit, amit mi még nem.
Azt javasolták, de valójában nem csinálni.
Ő csinál valamit fizikailag a cups azt sugallja, hogy
ben töltött néhány forrás mellett időt. >> [Hallgató] Space. >> Volt hely.
Az a tény, hogy volt ez a fajta bi-szintű asztalhoz, ahol volt hely ide
és a tér itt lent valójában arra utal, hogy ő használja kétszer annyi helyet
mint bármelyik eddigi algoritmusok - beillesztés sort, buborék rendezés, vagy kiválasztás sort -
de ő kihasználva ezt a további helyet a fajta mozgás dolog oda-vissza
miközben a dolgokat.
És bár úgy érzi, mintha van egy rendezett lista, hogy úgy éreztem, hogy volt egy darabig.
A valóságban, amit Rob csinált pontosan ez az algoritmus.
Először volt a probléma a mérete n, osztva be a bal oldalán, és a jobb felét.
Ekkor költözött a csészéket. Aztán megismételte ezt a folyamatot.
Ő osztva 4 a 2 db 2-át itt és itt.
Aztán megismételte a folyamatot, és osztva 2 a 2 db 1 minden e különböző csészéket.
És ez az, ahol a ragyogó lehetőség felmerül.
Ezen a ponton a történet, Rob már 8 listák méret 1,
melyek mindegyike rendezett már.
>> Akkor mit is folytatni kell csinálni?
Páronkénti vette ezt a rendezett listát, és ezt a rendezett listát, és összevonták őket.
Aztán vette ezt, és összevonták őket, majd ezt, és összevonták őket,
akkor ez egy és egyesítették őket.
És akkor mit csinált ezután?
Ezután újra egyesült a nagyobb listákat, majd újra egyesült a nagyobb listáját.
És ha úgy gondolja, erre csak ösztönösen most, mit csinál ő valójában?
Ő volt elosztjuk a problémát fél, fél, fél, fél
annak érdekében, hogy ezeket a szuper kis listákat.
Aztán volt olyan kedves, hogy egyesítené dupla, dupla, dupla, dupla.
Így csinál kétszer annyi munkát, mint láttuk eddig
bármi bevonásával oszd meg és uralkodj, de nem nagy ügy.
Kétszer annyi a munka nem is olyan nagy ügy. Ez csak egy állandó tényező.
És még sok minden, mint a mi aritmetikai kifejezés előtt, én csak megy át ki állandó tényezők
mint a szer 2. Kit érdekel? Ha ez 2 milliárd-szer 2, ez még mindig sok lépésből áll.
Szóval ez egyesülő lépés úgy tűnik, hogy a kulcs betekintést.
Sétáljunk át ez csak numerikusan előtt - Ó, ez nem lehet folytatni még.
Sétáljunk át ezt számszerűleg csak azért, hogy valóban látni, hogy ez hogyan játssza ki.
Ez többnyire csak egy kis szegény ember animáció.
Nézzük ezt a javaslatot.
A működési idő merge sort - már csak be kell egy módja beszél erről.
Ez nem matek, ez csak egyfajta tömör kifejezési módja magunkat.
Tehát T jelentése időben és n jelentése mi? >> [Hallgató] A méret a -
>> [Malan] A méret a probléma, az emberek száma.
Szóval arra hivatkozva, hogy a működési idő rendezni n embereknek lesz 0 időt
ha n kisebb, mint 2, mert ha 1 csésze vagy nem csészék, nincs mit rendezni.
De általánosságban fogom javasolni, hogy a működési idő rendezni n elemet
lesz, hogy mennyi időt vesz igénybe, hogy rendezze a bal felét, plusz a jobb felét
plus - mi ez a kiegészítő + n? >> [Hallgató] Merge sort.
[Malan] Ez valójában egyesülő, mert ha van n / 2 elem van
és van n / 2 elem van, mennyi időbe telik egyesíteni őket?
Csakúgy, mint Rob, van, hogy összeszedi ez ide, talán összeszedi ide,
bátorság ide, bátorság ide, bátorság ide.
Meg kell érinteni az egyes csészék egyszer.
És ha van 4 csésze plusz 4 csésze, ez 8 csésze
vagy még általánosabban, 8 N csésze.
Tehát az egyesülő lépésben képes kifejezni, mint n,
és hogy szó szerint magában foglalja a szám, ahányszor a Rob fizikailag érintett
egyike azoknak a hungarocell csésze.
Szóval most csinál egy tetszőleges példát.
Ha van 16 csésze, mi a futási idő a válogatás, a Rob-algoritmus, 16 cups?
Ez a 2-szer annyi időt vesz igénybe, hogy rendezni 8 csésze
mert van 8 csésze van, 8 csésze ide.
Nem tudom, mennyi ideig tart, úgyhogy általánosítani, hogy a T a pillanatban.
Ki tudja, mi ez?
De most is egyfajta rekurzív vagy többször fel ugyanazt a kérdést.
Mennyi időbe telik, hogy rendezni 8 csésze?
8 csésze fogom mondani, úgy időt vesz igénybe, hogy rendezni 4 csésze plusz 4 csésze,
majd egyesülő őket.
Fine. Mi bekerülni a ciklus már. Mennyi időbe telik, hogy rendezni 4 csésze?
A szükséges idő rendezni 4 csésze a 2 csésze plusz 2 csésze válogatása plusz az egyesülő folyamatot.
Fine. Mennyi időbe telik, hogy rendezni 2 csésze?
2 csésze az mennyi időt vesz igénybe, hogy rendezni 1 csésze plusz időt, hogy rendezze egy csésze
plusz időt vesz igénybe, egyesíteni, ami mindössze 2.
>> Fine. Utolsó kérdés. Mennyi időbe telik, hogy rendezni 1 csésze?
Itt az alap eset, hogy mi várható mi lenne hit korábban.
Az a tény, hogy nem veszi a munka egyáltalán rendezni a legkisebb problémák
azt jelenti, hogy most, a fajta iskolában stílus,
akkor csak menj kezdeni dugulás ezeket a számokat ismét bejelentkezni!
Most már tudom, mit T 1, így tudok csatlakoztatni a 0 T: 1 db.
Ez ad nekem választ T 2, amit akkor lehet csatlakoztatni feljebb.
Ez ad nekem T 4, amit lehet csatlakoztatni feljebb.
Ez ad nekem T 8, amit tud csatlakoztatni feljebb.
És ha ténylegesen arra, hogy a matematika a dugulás ezeket a válaszokat,
Aztán kap egy T 16-64.
És mit jelent 64 képvisel?
Ha a T-16, igen, ez 16-szor 4.
Szóval most azt állítják, hogy a futási idő ez a dolog az úgynevezett merge sort -
és ez lesz a fanciest az is láttunk eddig -
fog hívni n log n
mert hányszor lehet rabolni megosztani egy csomó csésze félidőben? Jelentkezzen n.
Ez ugyanaz, mint a telefonkönyv Például, ez ugyanaz, mint az ön-számlálás példa.
>> Hányszor lehet osztani valamit félidőben?
Azonban ez a beolvadó lépést.
Lehet, hogy meg kell osztani a poharak a 1/2, újra és újra és újra,
de minden alkalommal fogsz össze kell fésülni.
És mi azt mondtuk korábban, hogy egyesülő n kupák előnyben n lépések
mert meg kell tépni egy csésze, bátorság egy csésze, és van, hogy miden csésze egyszer,
mint Rob tette.
Tehát, ha csinálunk valamit, log n-szer, és csinálunk n dolgokat minden ilyen ismétléseket
Minden ilyen halvings, már n-szer log n.
Ha tehát csatlakoztassa 16 ebben a példában, 16-szor log 16 -
ne aggódj, hogy miért ez a helyzet most, mert én már nem készítették az alap -
de log 2 alaprész 16 4, 16-szer 64 4.
De ezzel szemben, ha mi is használta bubble sort vagy szelekciós szettbe vagy beszúrási sort, 16 szám,
mi lenne a futási idő lett volna, ha n 16?
Lenne 16 négyzeten, ami 256, ami még akkor is ha nem teljesen követi a matek,
256 nagyobb, mint 64. Ez tényleg a mágikus elvitelre itt.
És észre, hogy a munka ezen keresztül kisebb példákat fogsz egy Pset
teszi, hogy sokkal több intuitív.
De mit jelent valójában szempontjából az érzést az algoritmus a következő:
Ha tényleg megnézi merge sort itt - hadd vessem fel ebben az ablakban van -
ez egy kicsit más példa, amelyben van mind a 3 Ezen algoritmusok -
buborék, a kiválasztás, és egyesíti - csak egymás mellett.
>> Ők egész kezdődött véletlenszerű bárok, és ez jó.
Senki sem alapvető előnye a másikkal szemben.
Megyek egy pillanat kattintson minden egyes ilyen animációk - a Start, Start, Start -
, amilyen gyorsan csak lehet, hogy a, durván, ők minden kezdődik egyszerre,
és nézzük meg, hogy a buborék rendezés a rosszabb esetben futási idő mi? >> [Hallgató] N faragva.
N kockás. Selection sort a legrosszabb futási idő van? N kockás.
És merge sort nyilvánvalóan - akkor is, ha nem igazán követi a matek most
ez lesz sokkal intuitívabb idővel - az, hogy azt állítják, n-szer log n.
És mivel log n szigorúan kisebb, mint n, ha már nagy számok,
n-szer log n kisebb, mint n-szer n-vagy n négyzetével.
Szóval mit érzés, hogy valóban egy jobb algoritmust tekintetében működési idő,
n-szer log n, szemben az n négyzet? Itt vagyunk. Klikk, klikk, klikk.
>> Ez az, hogy mit jelent használni valami ilyesmit merge sort.
Van egy pillanat. Lássuk, mi történik itt.
[Kuncog] Kinek pénz van a bubble sort?
Sokkal inkább függ a bemeneti néha.
Lássuk.
Gyerünk. Olyan érzés, mintha a felzárkózás. >> [Hallgató] Menj, bubble sort!
[Diákok zúgolódás]
[Malan] Igen, igen.
[Diákok zúgolódás] Menj, menj, menj!
[Összes éljenzés] [taps]
Tehát most az 1 utolsó, záró demo, ha ez egy kicsit trükkös, hogy tekerje elméd köré a matek
vagy valami a vizualizáció van, akkor valóban hallani a sebesség
a különböző algoritmusok másképp.
Ez egy animáció valaki tett, amely ténylegesen társult hangzik
abba a folyamatba, és a csere magasságát a rudak.
Mint látni fogjuk itt, van még néhány rendező algoritmus, hogy ott emberek is gondoltam.
Az első lesz beillesztés sort, és ez repülnek át
és kapsz egy hallható értelemben, hogy ezek a különböző algoritmusok munka.
Itt helyezés sort.
[Elektronikus csipogás]
[Malan] Bubble sort.
[Gyorsabb elektronikus csipogó]
[Malan] Selection sort.
[Gyorsabb elektronikus csipogó]
[Malan] Merge sort.
[Elektronikus csipogás]
[Csipogó lelassítja] [nevetés]
[Malan] Gnome sort.
[Elektronikus csipogás]
>> Ez CS50. Találkozunk jövő héten. [Taps és éljenzés]
>> [CS50.TV]