>> [MUSIC PLAYING]
DAVID MALAN: Rendben.
Rendben, szívesen vissza.
Szóval ez a 4. héten, az elején erről már.
És emlékezzünk csak vissza, hogy a múlt héten, tesszük kódot félre egy kicsit
és elkezdtünk beszélgetni egy kicsit magas szintű, a dolgok, mint a
keresés és válogatás, amely ugyan kissé egyszerű ötletek, amelyek
képviselője osztály a problémák akkor kezdenek megoldani különösen
ahogy elkezd gondolkodni végső projektek és érdekes megoldásokat
Lehet, hogy valós problémákat.
Most buborék fajta volt az egyik legegyszerűbb ilyen algoritmusok, és ez
dolgozott, azáltal, hogy ezek a kis számú listában, vagy egy sor olyan
buborék az utat felfelé a csúcsra, és a nagy számban mozognak az utat lefelé
a végén, hogy a listán.
>> És emlékszem, hogy mi lehetett képzelni bubble sort egy kicsit
valami ilyesmi.
Hadd megy előre, és kattintson az Indítás gombra.
Már előre kiválasztott bubble sort.
És ha emlékeztetni arra, hogy a magasabb kék vonalak nagy számok, kis-
kék vonalak kis számban, mint megyünk át ezt újra és újra, és
Ismét, összehasonlítva két bár egymás mellett másik piros, megyünk, hogy a csere a
legnagyobb és a legkisebb, ha ezek elromlott.
>> Tehát ez megy, és megy és megy tovább, és látni fogod, hogy a nagyobb
elemek teszik az utat, hogy a jobbra, és a kisebb elemek
útjukat balra.
De elkezdett számszerűsíteni A hatékonyság, a
minősége az algoritmus.
És azt mondta, hogy a legrosszabb esetben, ez az algoritmus került
nagyjából hány lépés?
>> Tehát n négyzeten.
És mi volt n?
>> Közönség: Elemek száma.
>> DAVID MALAN: Tehát n volt elemek száma.
És így fogjuk ezt gyakran.
Minden alkalommal, amikor szeretnénk beszélni a méret a probléma, vagy a mérete
bemenet, vagy az időt vesz igénybe hogy a kimenet, akkor csak
általános bármi a bemenet, amint n.
Tehát vissza a 0. héten, hogy hány oldalt a telefonkönyvben volt n.
A hallgatók száma A szobát n.
Tehát itt is, mi után ezt a mintát.
>> Most n squared nem különösebben gyors, így megpróbáltuk jobban.
És így nézett néhány más algoritmusok, amelyek közül
volt kiválasztás sort.
Így kiválasztás sort volt egy kicsit más.
Már majdnem egyszerűbb, merem mondani, ahol kezdtem elején a
lista a önkéntesek, és én csak újra és újra és újra ment keresztül
A lista kopasztás ki a legkisebb elem egy időben és üzembe neki, vagy
őt a lista elején.
>> De ez is, miután elkezdtünk gondolkodni a matematika és a nagyobb
kép, gondoltam, hányszor Én megyek vissza oda-vissza
oda, azt mondta, a legrosszabb esetben, kiválasztás sort is, mi volt?
N négyzeten.
Most a valós világban, talán valóban kis mértékben gyorsabb.
Mert megint nem kell tartani visszalépés egyszer én is rendezett a
legkisebb elem.
De ha belegondolunk nagyon nagy n, és ha valami tenniük ki a matematika, mint
Én a táblán, az n négyzetes mínusz valami, minden más
mellett az n négyzetes, ha n lesz nagyon nagy, nem
igazán számít annyira.
Szóval mint számítógépes szakemberek, azt valahogy szemet huny a kisebb
tényezők, és elsősorban csak a tényező kifejezés, ami megy, hogy
a legnagyobb különbség.
>> Nos, végül, néztünk A beszúrás sort.
És ez volt a hasonló szellemben, de nem megy át iteratív és
válassza ki azt a legkisebb elemet egyenként időben, ahelyett, hogy vette a kezemet,
foglalkozott, és úgy döntöttem, minden van, akkor ide tartozik.
Aztán haladt, hogy a következő elem és úgy döntött, hogy ő maga vagy
ő ide tartozik.
Aztán haladt tovább.
És talán az, az út mentén, váltás ezek a srácok, hogy
hogy helyet nekik.
Szóval ez volt az a fajta mentális megfordítása A kiválasztás sort, hogy mi
nevű beszúrás sort.
>> Tehát ezek a témák fordulnak elő a valós világban.
Csak néhány évvel ezelőtt, amikor egy bizonyos szenátor elnöki székért,
Eric Schmidt, abban az időben a vezérigazgató Google, valóban volt lehetősége
hogy interjút vele.
És azt hittük, ossza meg ezt a YouTube klip itt, ha tudnánk előkerülnek
a hangerőt.
>> [VIDEÓ LEJÁTSZÁS]
>> -Nos, szenátor, hogy itt vagy a Google, és szeretem azt hinni, az elnökség
mint egy állásinterjún.
>> [Nevetés]
>> -Most már nehéz, hogy munkát mint elnök.
És megy keresztül a borzongás most.
Az is nehéz, hogy a munkát a Google.
Van kérdése és kérjük a jelöltek kérdésekre.
És ez az egyik a Larry Schwimmer.
>> [Nevetés]
-Azt hiszitek, viccelek?
Ez itt van.
Mi a leghatékonyabb módja annak, hogy rendezni a két millió bites egész?
>> [Nevetés]
>> -Nos, hát -
>> -Sajnálom.
Talán meg kellene -
>> -Nem, nem, nem, nem, nem.
>> -Ez nem egy -
OK.
>> -Azt hiszem, a buborék fajta lenne nem a megfelelő út.
>> [Nevetés]
>> [Éljenez és tapsol]
>> -Ugyan már, ki mondta ezt neki?
OK.
>> [END VIDEÓ LEJÁTSZÁS]
>> DAVID MALAN: Szóval ott van ez.
Így elkezdtünk számszerűsíteni a működési alkalommal, hogy úgy mondjam, valami
nevű aszimptotikus jelölés, amely csak utal a fajta fordult
egy vak szemet a kisebb tényezők és csak nézte a működési idő,
teljesítményét ezen algoritmusok, az n lesz igazán nagy az idő múlásával.
És így be nagy O. és nagy O képviseltem valamit, hogy azt gondoltuk,
, mint egy felső határ.
És valóban, Barry, tudunk alacsonyabb mint a mikrofon egy kicsit?
>> Úgy gondoltuk, ez egy felső határ.
Olyan nagy O n négyzetes azt jelenti, hogy A legrosszabb esetben, valami hasonló
kiválasztás sort venne n négyzeten lépéseket.
Vagy valami hasonló beszúrás sort lenne n négyzeten lépéseket.
Most valami hasonló beillesztés sort, hogy mi volt a legrosszabb?
Adott egy tömb, mi a legrosszabb, lehetséges forgatókönyv, hogy lehet találni
magát szembe?
>> Ez teljesen hátra, igaz?
Mert ha ez teljesen hátra, meg kell csinálni egy csomó munkát.
Mert ha teljesen hátra, fogsz találni a
legnagyobb elem itt, annak ellenére, tartozik oda.
Így fogsz mondani, minden rendben, a ebben a pillanatban, akkor ide tartozik,
így hagyja békén.
>> Aztán rájössz, ó, a fenébe, meg kell mozog ez valamivel kisebb elemet
A bal oldali a ketten.
Akkor azt kell csinálni, hogy újra és újra és újra.
És ha mentem oda-vissza, akkor ami egyfajta érezni a teljesítmény
ez az algoritmus, mert állandóan vagyok csoszogó mindenki le a
array, hogy helyet is.
Szóval ez a legrosszabb esetben.
>> Ezzel szemben -
és ez volt a filmsorozat utoljára -
azt mondta, hogy a beszúrás sort volt egy omega, mi?
Mi a legjobb eset futás behelyezés sort?
Szóval ez tényleg n.
Ez volt az üres, hogy mi maradt a táblán utoljára.
>> És ez az omega n, mert miért?
Nos, a legjobb helyzet, mi a beillesztés sort fog adni?
Nos, a lista, amelyet teljesen rendezett már, minimális munka.
De mi szép a beszúrás sort az, hogy mivel itt kezdődik, és
úgy dönt, ó, te vagy a szám egy, akkor ide tartozik.
Ó, milyen jó szerencse.
>> Te vagy a kettes számú.
Azt is ide tartozik.
A hármas számú, még jobb, ide tartozol.
Amint ez lesz a végén a lista, egy beszúrás sort a pszeudokódja
hogy sétált szóban utoljára, ez kész.
De kiválasztás sort, ezzel szemben, tartotta mit csinál?
>> Folyamatosan megy a listában újra és újra és újra.
Mivel a kulcs betekintést már csak ha már úgy nézett végig a
A lista végén lehet biztos hogy az elem kiválasztott volt
sőt a jelenleg legkisebb elem.
Tehát ezek a különböző mentális modellek vége fel engedve néhány nagyon valós
különbségek számunkra, valamint az ilyen elméleti aszimptotikus különbségeket.
>> Szóval összefoglalva, akkor nagy O n négyzet, láttunk néhány olyan
algoritmusok eddig.
Big O n?
Mi az az algoritmus, amely elmondható, hogy nagy O n?
A legrosszabb esetben, hogy úgy lineáris lépések számát.
>> OK, lineáris keresést.
És a legrosszabb esetben, amikor a elem, amit keres, ha
alkalmazása lineáris keresést?
>> OK, a legrosszabb esetben, még csak nem is ott van.
Vagy a második legrosszabb esetben ez egészen a végén, amely a
plusz vagy mínusz egy lépésben a különbség.
Így a végén a nap, azt mondhatjuk, hogy lineáris.
Big O n lesz lineáris keresés mivel a legrosszabb esetben a
elem még csak nem is ott, vagy ez egészen a végén.
>> Nos, nagy O log n.
Mi nem beszélünk nagy részletesen , de már láttam ilyet.
Mi fut úgynevezett logaritmikus időt, a legrosszabb esetben?
>> Igen, bináris keresés.
És bináris keresés legrosszabb esetben lehet, hogy az elem valahol
A közép-, vagy valahol belül a tömbben.
De csak akkor találja meg, ha osztani a lista felét, az
fél, fél, fél.
És akkor íme, itt van.
Vagy megint a legrosszabb esetben még csak nem is ott van.
De nem tudod, hogy ez nincs amíg el nem éri a fajta, hogy az utolsó
legalsó elemek felére és megfelezve és felére.
>> Big O 1.
Így lehet nagy O 2, O 3 nagy.
Amikor csak akar, csak egy állandó szám, Mi csak a fajta csak egyszerűsítése
hogy olyan nagy O 1.
Annak ellenére, hogy reálisan, hogy úgy 2 vagy akár 100 lépést, ha ez a
konstans lépések számát, Csak mondjuk nagy O 1.
Mi az az algoritmus, ami nagy O 1?
>> KÖZÖNSÉG: Finding hosszát változó.
>> DAVID MALAN: Megtalálni a hossza egy változó?
>> Közönség: Nem, a hosszúság ha már rendezve.
>> DAVID MALAN: Jó.
OK, így a megállapítás a hossza valami ha a hossza, hogy valami, mint a
tömb, tárolják néhány változó.
Mert akkor csak olvasd el a változó, vagy nyomtassa ki a változó, vagy
csak általában elérni az adott változó.
És íme, hogy vesz konstans id.
>> Ezzel szemben, gondolom, vissza a semmiből.
Gondolj vissza az első héten a C, hívás csak printf és nyomtatás
valamit a képernyőn, vitathatatlanul konstans időben, mert ez csak úgy
bizonyos számú CPU mutatni ezt a szöveget a képernyőn.
Vagy várj - nem igaz?
Másképp hogyan tudnánk modellezni teljesítménye printf?
Akar valaki szeretne egyet, hogy a talán nem is konstans id?
Milyen értelemben lehet printf fut idő, tulajdonképpen nyomtatás a string
a képernyőn, hogy valami nem állandó.
>> Közönség: [hangtalan].
>> DAVID MALAN: Igen.
Tehát attól függ, hogy mi szempontunkból.
Ha valóban úgy gondolja, a bemenet printf mint a húr, és
ezért mérni a méretét, hogy a bemenet a hossza - így hívjuk
hogy n hosszúságú is -
vitathatóan, printf maga nagy O n mert fog tartani, N lépésben
hogy nyomtassa ki minden egyes ilyen n karakterekből legvalószínűbb.
Legalább olyan mértékben, hogy azt feltételezzük, hogy talán ez egy for ciklus
a motorháztető alatt.
>> De akkor meg kell nézni, hogy az kódot, hogy jobban megértsétek.
És valóban, ha egyszer elkezd srácok elemezve a saját algoritmusokat, akkor
szó szerint nem csak ezt.
Valahogy szemgolyó a kódot, és gondolom, a - minden rendben, itt van ez loop
itt, vagy van egy egymásba ágyazott hurkok itt, hogy fog csinálni a dolgokat n n-szer,
és akkor valami okból az utat át a kódot, akkor is, ha ez
pszeudokódját, és nem maga a kód.
>> Szóval mi van omega n négyzete?
Mi volt egy algoritmust, amely a legjobban esetben még csak n négyzeten lépések?
Igen?
>> Közönség: [hangtalan].
>> DAVID MALAN: Tehát kiválasztás sort.
Mert, hogy a probléma valóban csökkent arra, hogy újra, nem tudom,
Találtam a jelenlegi legkisebb, amíg Megnéztem az összes rohadt elemekkel.
Tehát omega, mondjuk, n, akkor most jött egy.
Beillesztése sort.
Ha a lista történik rendezhető már, a legjobb esetben is csak
hogy az egyik átmegy rajta, ekkor biztosak vagyunk benne.
És akkor, hogy lehet mondani a lineáris, az biztos.
>> Mi a helyzet omega 1?
Mi a legjobb esetben, eltarthat állandó számú lépésben?
Tehát lineáris keresés, ha csak szerencséd lesz és az elem, amit keresel
igaza van a lista elején, ha ez az, ahol te kezdő
lineáris bejárása a listán.
>> És ez igaz a számú dolog.
Például, akár bináris keresés omega 1.
Mert mi van, ha igazán rohadt szerencsés és íz-DAB közepén
A tömb a szám keres?
Így szerencsés ott is.
>> Ez végül omega n log n.
Tehát n log n, akkor nem igazán beszélni még, de -
>> Közönség: Merge sort?
>> DAVID MALAN: Merge sort.
Ez volt az a Cliffhanger utoljára, ahol javasolta, és megmutattuk,
vizuálisan, hogy vannak algoritmusok.
És egyesíti a fajta csak egy ilyen algoritmus alapvetően gyorsabb
mint néhány ilyen többiek.
Tény, egyesítése rövidzárlat nemcsak a legjobb esetben n log n, a legrosszabb
Az N log n.
És ha ez a véletlen omega és a nagy O, hogy ugyanaz a dolog?
Mi valóban leírni, hogy mivel mi nevű theta, bár ez a
kevésbé gyakori.
De ez csak azt jelenti, a két határt, ebben az esetben azonosak.
>> Tehát merge sort, mit jelent ez a Tényleg szűkülnek le nekünk?
Nos, emlékszem a motiváció.
Hadd húzza fel egy animáció mi nem nézni utoljára.
Ez az egy, ugyanaz a gondolat, de a ez egy kicsit nagyobb.
És én megyek előre, és rámutatni először - már behelyezés sort a
A bal felső sarokban, majd a kiválasztás sort, buborék sort, néhány más típusú -
héj és gyorsan -, hogy nem beszéltünk szól, és halom és egyesíti sort.
>> Így legalább próbáljuk összpontosítani a szemét az első három, a bal oldalon, majd a
merge sort amikor rákattintok ez a zöld nyíl.
De hagyom mindet futni, csak azért, hogy ad egyfajta sokszínűségének
algoritmusok, hogy létezik a világon.
Én hagyom, hogy ezt a futamot csak néhány másodpercig.
És ha összpontosítani a szemed - válasszon egy algoritmus, összpontosítani, hogy csak egy
másodperc - akkor kezdődik, hogy a minta, hogy ez megvalósítani.
>> Merge sort, értesítés, kész.
Heap sort, gyorsan sort, héj -
így úgy tűnik, hogy bevezette a három legrosszabb algoritmusok a múlt héten.
De jó, hogy itt vagyunk ma nézd meg merge sort, ami az egyik
a legkönnyebben, hogy nézd meg, még de ez valószínűleg hajlik a fejében
csak egy kicsit.
Itt láthatjuk, hogy mennyi kiválasztás sort szar.
>> De a másik oldala, hogy nagyon könnyen megvalósítható.
És talán a P Set 3, ez az egyik, a algoritmusok úgy döntött, hogy végre
A standard változat.
Tökéletesen, teljesen korrekt.
>> De ismétlem, az n lesz nagy, ha úgy dönt, hogy végre egy gyorsabb algoritmust
mint merge sort, esély a nagyobb és nagyobb bemenet, a kódot csak
majd, hogy gyorsabban fusson.
Saját honlap fog jobban működnek.
A felhasználók lesznek boldogabbak.
És így van ez a hatás A tényleges adó
nekünk mélyebb gondolat.
>> Szóval vessünk egy pillantást, amit egyesíteni sort valójában szól.
A jó dolog az, hogy egyesíti rendezés csak ez.
Ez megint mi már az úgynevezett pszeudokódját, pszeudokódja lény
Angol, mint a szintaxis.
És az egyszerűséget az valami lenyűgöző.
>> Szóval input n elemű - hogy csak azt jelenti, hogy itt egy sor.
Van rajta n dolgokat benne.
Ez minden, amit mondasz ott.
>> Ha n kisebb, mint 2, vissza.
Szóval ez csak a triviális.
Ha n kisebb, mint 2, akkor nyilván ez 1 vagy 0, ebben az esetben a dolog
már rendezett, vagy nem létező, így csak vissza.
Nincs mit tenni.
Szóval ez egy egyszerű eset, hogy összeszedi le.
>> Else, van három lépésből áll.
Rendezze a bal oldalán az elemek, sort a jobb fele az elemek,
majd egyesíteni a rendezett felét.
Ami érdekes az, hogy Én vagyok a fajta punting, igaz?
Van egyfajta körkörös definíció ez az algoritmus.
Milyen értelemben ez az algoritmus meghatározása kerek?
>> Közönség: [hangtalan].
>> DAVID MALAN: Igen, a rendezési algoritmus, annak két lépés "sort
valami. "És, hogy felveti a kérdés, nos, mit fogok használni
rendezni a bal felét és a jobb fele?
És a szépség az, hogy annak ellenére, megint ez a pszichedelikus
rész potenciálisan, akkor ugyanazt algoritmus rendezni a bal felét.
>> De várjunk csak egy percet.
Amikor mondták, hogy rendezze a bal oldalán, melyek a két
lépés lesz a következő?
Majd rendezni a bal fele a bal oldalán, a jobb
a fele a bal felét.
A fenébe, hogyan tudom rendezni a két fél, vagy negyed, most?
>> De ez rendben van.
Van egy rendezési algoritmust itt.
És bár lehet, hogy aggódik a az első ez a fajta végtelen
loop, ez egy ciklus, amely soha nem lesz a vége - ez lesz a
ér véget, amikor mi történik?
Miután n értéke kisebb, mint 2.
Amely végül fog történni, mert ha folyamatosan felére és
felére a felére következő részre, biztosan végül maga lesz a vége
fel csak 1 vagy 0 elemeket.
Ekkor ez az algoritmus azt mondja, hogy kész.
>> Tehát az igazi varázslat ebben algoritmust úgy tűnik, hogy
hogy a végső lépést, összevonása.
Ez az egyszerű ötlet, csak két összefonódó dolog, hogy az, ami végül is lesz
hogy lehetővé teszik számunkra, hogy rendezni egy sor, mondjuk nyolc elem.
Szóval van még nyolc stressz labda fel Itt nyolc darab papír, és egy
Google Glass -
amit kap, hogy.
>> [Nevetés]
>> DAVID MALAN: Ha tudnánk, hogy nyolc önkéntesek, és nézzük meg, ha tudjuk
játszani ezt, így.
Wow, OK.
Számítástechnika egyre szórakoztató.
Rendben van.
Mi lenne, ha három, legnagyobb kezét oda.
Négy hátul.
És mi lenne, ha majd te három ebben a sorban?
És négy az első.
Szóval nyolc, gyere fel.
>> [Nevetés]
>> DAVID MALAN: Én tényleg nem tudja, mi az.
Ez a stressz labda?
Az asztali lámpa?
Az anyag?
Az interneten?
>> OK.
Szóval, gyere fel.
Ki szeretne -
jönnek fel.
Lássuk.
És ez hozza meg a helyszínen -
te egy helyre.
Uh-oh, várj egy percet.
1, 2, 3, 4, 5, 6, 7 - ó, jó.
Rendben, rendben vagyunk.
Rendben, mindenki helyet, de nem a Google Glass.
Hadd sorban e fel.
Mi a neve?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle?
Rendben, hogy néz ki, mint A stréber, ha nem gond.
Nos, én is, azt hiszem, csak egy pillanatra.
Rendben, készenlét.
Próbáltuk, hogy dolgozzon ki egy használni az esetben a Google Glass, és
gondoltam, hogy jó, hogy csak nem ezt, amikor az emberek a színpadon.
Mi rögzíti a világot a saját szemszögéből.
Rendben van.
Nem talán, amit a Google szánták.
Rendben, ha nem bánod visel ez a következő kínos perc
hogy csodálatos lenne.
>> Rendben, van itt egy sor elemeket, és hogy a tömb, mint egy a
papírdarab ezek az emberek " kéz, jelenleg unsorted.
>> MICHELLE: Ó, ez olyan furcsa.
>> DAVID MALAN: Elég sok véletlen.
És csak egy pillanatra, fogunk próbálni végrehajtása egyesíteni sort össze
és hol a kulcs meglátás.
És a trükk itt merge sort is valamit, amit még nem vállalt még.
Igazából kell egy kis további helyet.
Tehát mi lesz különösen érdekes az, hogy ezek a
srácok fognak mozogni egy kicsit kicsit, mert én fogom fel, hogy
van egy extra sor a tér, mondani, ugye mögöttük.
>> Tehát, ha ők mögött szék, ez a második tömb.
Ha ők ülnek itt, ez az elsődleges tömb.
De ez egy olyan erőforrás, hogy van nem tőkeáttételes eddig buborék
sort, a kiválasztás sort, A behelyezés sort.
Emlékezzünk a múlt héten, mindenki csak ilyen csoszogott a helyén.
Nem használja a memóriát.
Csináltunk helyet emberek mozgó emberek.
>> Tehát ez egy fontos betekintést is.
Van ez a trade-off, az általános számítástechnika, a források.
Ha szeretné, hogy gyorsítsák fel valamit mint az idő, fogsz
kell fizetni az árát.
És az egyik ilyen árak gyakran hely, a memória vagy kemény
lemezterület használ.
Vagy, őszintén szólva, az összeg A programozó idő.
Mennyi időt vesz igénybe, az ember, ténylegesen alkalmazni néhány
bonyolult algoritmus.
De ma, a trade-off az idő és a tér.
>> Tehát, ha ti is csak tartsa be a számokat, így láthatjuk, hogy te
Valóban megfelelő 4, 2, 6, 1, 3, 7, 8.
Kiváló.
Úgyhogy megpróbálom hangszerel dolgok, ha ti csak
kövess engem itt.
>> Így fogok végrehajtani, először az első lépésében a pszeudokód, amely
bemeneten n elemű, ha n kevesebb, mint 2, majd vissza.
Nyilvánvaló, hogy ez nem vonatkoznak, így megyünk tovább.
Így rendezni a bal fele az elemek.
Ez azt jelenti, fogok összpontosítani a figyelmet egy pillanatra a következő
négy srác itt.
Rendben, mit tegyek a következő csinálni?
>> Közönség: Rendezze a bal felét.
>> DAVID MALAN: Tehát most már rendezni a bal fele ezek a srácok.
Mert megint fel magadnak a célja, hogy rendezze a bal felét.
Hogy csinálod ezt?
Kövesse az utasításokat, sőt bár mi csináljuk újra.
Így rendezni a bal felét.
Most válogatás a két srác.
Mi jön ezután?
>> Közönség: Rendezze a bal felét.
>> DAVID MALAN: rendezés a bal felét.
Tehát most ezek, ez a hely itt, egy lista az 1-es méretű.
És mi a neved?
>> PRINCESS DAISY: Princess Daisy.
>> DAVID MALAN: Princess Daisy itt.
És ő már válogatott, mert a lista az 1-es méretű.
Mit csinál a következő?
OK, vissza, mert ez a lista a 1-es méret, ami kevesebb, mint 2.
Akkor mi a következő lépés?
És most meg kell, hogy milyen visszalép a fejedben.
>> Rendezze a jobb fele, ami -
mi a neve?
>> LINDA: Linda.
>> DAVID MALAN: Linda.
És mit teszünk most, hogy van egy lista a méret 1?
>> Közönség: Return.
>> DAVID MALAN: Óvatosan.
Mi vissza először, és most a harmadik lépés - és ha valahogy ábrázolják azt
felölelő két ülés most, most már kell egyesíteni ezt a két elemet.
Tehát most sajnos az elemek ki a rend.
De ez az, ahol az összefonódó folyamat kezd lenyűgöző.
>> Tehát, ha ti is állni csak Egy pillanatra fogok szükségem van rád, egy
Jelenleg lépéssel mögötte a széket.
És ha Linda, mert 2 kisebb, mint 4, miért nem
jössz körül az első?
Maradj ott.
Szóval Linda, akkor magához tér az első.
>> Most, a valóságban, ha ez csak egy tömb tudtuk csak mozgatni a valós időben
ebből a székből, hogy ezen a helyen.
Így elképzelhető, hogy volt néhány állandó lépések száma 1.
És most -
de meg kell, hogy tegye meg a Az első hely itt.
>> És most, ha tudnál jönni körül, is, fogunk
legyen hely két.
És bár ez olyan, mintha egy darabig, mi szép most
hogy a bal fele a bal fele ma már rendezve.
Tehát mi volt a következő lépés, ha most hátra tovább a történet?
>> Közönség: jobb felét.
>> DAVID MALAN: rendezés a jobb felét.
Szóval srácok ezt is.
Tehát, ha meg tudná állni egy pillanatra?
És mi a neve?
>> JESS: Jess.
>> DAVID MALAN: Jess.
OK, így Jess most a bal felét a jobb felét.
És ő a lista 1-es méretű.
Ő nyilvánvalóan rendezve.
És a neve?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle nyilvánvalóan egy listát a 1-es méretű.
Már így is rendezve.
Tehát most a varázslat történik, az egyesülő folyamat.
Szóval, ki fog jönni az első?
Nyilvánvalóan Michelle.
Tehát, ha meg tudná magához tér vissza.
A tér már elérhető neki most igaza van e mögött székét.
És most, ha tudna jönni vissza is, most már, hogy világos legyen, két
fele, egyenként 2-es méret -
és csak az ábrázolás kedvéért, ha lehet, hogy egy kicsit a tér -
Egy bal fele itt, egy jobb felét itt.
>> Rewind tovább a történet.
Mi a következő lépés?
>> Közönség: Merge.
>> DAVID MALAN: Tehát most már össze kell fésülni.
Tehát OK, így most, szerencsére, akkor csak felszabadult négy szék.
Ezért is használtam kétszer annyi memóriát, de adhatunk flip-flopra között
A két tömb.
Tehát melyik szám az első helyen?
Tehát Michelle, nyilván.
Így jár, és hogy itt a helyed.
És akkor 2-es szám nyilvánvalóan következő, így jön ide.
4. szám, 6-os szám.
És ismét, bár van egy kis séta szó,
Tényleg ezek megtörténhet azonnal, mozgatásával egy -
OK, jól játszott.
>> [Nevetés]
>> DAVID MALAN: És most mi vagyunk elég jó formában.
A bal fele a teljes input most rendezve.
Rendben, ezek a srácok voltak az az előnye, az én -
hogyan csinálta a végén a lányok a balra, és a fiúk a jobb?
>> OK, így fiúk viszont most.
Tehát nem fogok járni végig ezeket a lépéseket.
Meglátjuk, ha tudjuk újra ugyanaz pszeudokódja.
Ha azt szeretné, hogy menjen előre, és felállni, és ti, hadd adjak a mikrofont.
Nézd meg, hogy nem tudja megismételni, amit Csak nem itt a
másik végét a listából.
Kinek kell beszélni az első, alapján az algoritmus?
Szóval, elmagyarázni, hogy mit csinálsz, mielőtt bármit láb mozgását.
>> SPEAKER 1: Rendben, mert Én vagyok a bal fele a
bal fele, visszatérek.
Nem igaz?
>> DAVID MALAN: Jó.
>> SPEAKER 1: És akkor -
>> DAVID MALAN: Ki a mikrofon megy tovább?
>> SPEAKER 1: Következő szám.
>> SPEAKER 2: Szóval én vagyok a jobb felét a bal fele a
bal fele, és én vissza.
>> DAVID MALAN: Jó.
Visszatér.
Akkor most mi lesz a következő az Ön számára két?
>> Hangszóró 2: Azt akarjuk látni, ki kisebb.
>> DAVID MALAN: Pontosan.
Azt akarjuk, hogy egyesíteni.
A tér fogunk használni, hogy egyesíteni került, annak ellenére, hogy
nyilvánvalóan sorrendje már, megyünk hogy ugyanezt az algoritmust.
Tehát, aki megy vissza az első?
Így 3, majd 7.
És most a mikrofon megy hogy ezek a srácok, oké?
>> SPEAKER 3: Szóval én vagyok a jobb felét a bal fele, és az én n kisebb, mint
1, úgyhogy csak átutazóban -
>> DAVID MALAN: Jó.
>> SPEAKER 4: én vagyok a jobb felét a jobb felét a jobb fele, és én vagyok
is egy ember, úgyhogy majd vissza.
Szóval most mi egyesítése.
>> SPEAKER 3: Szóval vissza.
>> DAVID MALAN: Szóval megy vissza.
Tehát 5 megy először, majd a 8.
És most közönség, amely a lépésre meg kell teremteni a visszatekerés
vissza, hogy a fejekben?
>> Közönség: Merge.
>> DAVID MALAN: egyesítése bal oldalán és a jobb a fele az eredeti bal felét.
Tehát most -
és csak azért, hogy ez világos, hogy egy kis helyet
köztetek srácok.
Tehát most, hogy ez a két listát, balra és jobbra.
Szóval hogyan most egyesíteni titeket a Az első üléssor megint?
>> 3. kezd.
Ezután 5 nyilván.
Ezután 7, és most 8.
OK, és most már?
>> Közönség: Nem történik.
>> DAVID MALAN: nem történik meg, mert a Nyilvánvaló, hogy ez egy lépés van hátra.
De ismétlem, azért én ezzel a zsargon, mint a "hátra a fejedben,"
azért, mert ez tényleg mi történik.
Megyünk végig ezeket a lépéseket, de mi valami megállt egy
pillanat, búvárkodás mélyebbre algoritmus, megállt egy pillanatra,
Mélyebben az algoritmus, és most már rendezni a visszatekerés a mi
elmék és visszavonás mindezen rétegek hogy már egyfajta tartásba kerül.
>> Tehát most már két listát 4-es méret.
Ha ti is állni utoljára és egy kis hely itt
egyértelművé teszi, hogy ez a bal a fele az eredeti, a
jobb felére.
Ki volt az első szám, amit kell húzni a hátsó?
Michelle, természetesen.
>> Tehát fel Michelle itt.
És aki a 2?
2. szám jön vissza is.
3. szám?
Kiváló.
4. szám, 5-ös, 6-os, 7-es és a 8-as szám.
>> OK, így úgy éreztem, mint sok lépések, az biztos.
De most nézzük meg, ha nem tudjuk megerősíteni fajta ösztönösen, hogy ez a
algoritmus alapvetően, különösen n lesz nagyon nagy, ahogy láttam
A animációk, a alapvetően gyorsabb.
Tehát azt állítom, ez az algoritmus, a legrosszabb eset, és még a legjobb esetben,
nagy O n log n-szer.
Vagyis, van néhány szempont a algoritmus vesz n lépéseket, de
van egy másik szempont valahol hogy ismétlés, hogy a hurok, hogy
vesz log n lépésben.
Lehet tesszük ujját, hogy mi az két szám utal?
Nos, hol -
Hol a mikrofon el?
>> SPEAKER 1: Vajon a log n törés minket két -
elosztjuk két, lényegében.
>> DAVID MALAN: Pontosan.
Bármikor látjuk minden algoritmus tehát messze van már ez a minta
elválasztó, elválasztó, osztódását.
És ez általában csökken valami, ami
logaritmikus, log alap 2.
De tényleg bármi lehet, de log alap 2.
>> Mi a helyzet a n?
Látom, hogy milyen osztott meg srácok - osztott meg, osztott meg,
osztott meg, osztott meg.
Hol a végén származik?
>> Tehát ez az összevonása.
Mert gondolni.
Ha egyesíteni nyolc embereket, amelynek a fele egy olyan négy
és a másik felét egy másik meg négy, hogyan megy
csinál az egyesülő?
Nos, srácok tette meglehetősen intuitív.
>> De ha inkább nem, hogy egy kicsit módszeresen, talán már rámutatott
a bal szélső személy először az én bal Ugyanakkor rámutatott a bal szélső ember
Az, hogy a fele az én jobb kezemben, és a csak később ment át a
lista, mutatva a legkisebb elem minden egyes alkalommal, mozog az ujját, és
mint ahogy szükség az egész listát.
De mi a kulcs ebben összevonása folyamat Én összevetjük a pár
elemek.
A jobb felét, és a bal oldali fél, én egyszer sem visszalépés.
>> Tehát az egyesítés is vesz nem több, mint n lépésben.
És hányszor volt már erre összevonása?
Nos, nem több, mint n, és mi csak látta, hogy a végső egyesítés.
És ha valami, hogy úgy log n lépésben n-szer, vagy fordítva,
ez meg fog adni nekünk n log n-szer.
>> És miért van ez jobb?
Nos, ha már tudjuk, hogy log n jobb, mint n - igaz?
Láttuk bináris keresés a telefonkönyvben Például log n határozottan
jobb, mint a lineáris.
Ez azt jelenti, n-szer log n határozottan jobb, mint n-szer egy másik
N, N AKA négyzeten.
És ez az, amit végül is érezni.
>> Olyan nagy tapsot, ha tudnánk, mert ezek a srácok.
>> [Taps]
>> DAVID MALAN: És az elválás ajándékok - lehet tartani a számokat,
ha szeretné.
És az elválás ajándék, mint mindig.
Ja, és mi elküldjük Önnek a felvételeket, Michelle.
Köszönöm.
Rendben van.
Segíts magadon, hogy a stressz labdát.
>> És hadd húzza fel, az időközben barátunk Rob Bowden nyújt
némileg más szemszögből e, mert akkor gondol ezekről
lépés történik egy kissé más módon.
Tény, hogy a set-up, amit Rob van szó hogy megmutassa azt feltételezi, hogy már
már megtette a felosztva a nagy listát nyolc kis lista,
minden 1-es méretű.
>> Szóval változó pszeudokód a kicsit csak rendezni a kap a
központi gondolata, hogy az egyesülő működik.
De az üzemidő, amit mindjárt nem is mindig
lesz ugyanaz.
És ismét, a set-up az, hogy ő kezdődött nyolc listáját méret 1.
Szóval hiányzott az a része, ahol ő ténylegesen elvégzett log n log n log n
elosztjuk a bemeneti.
>> [VIDEÓ LEJÁTSZÁS]
>> -Ez az a lépés.
A második lépés, többször merge pár listák.
>> DAVID MALAN: Hm.
Csak a hang jön ki a számítógépet.
Próbáljuk meg újra.
>> -Csak önkényesen felvenni, amely - most már négy lista.
Tanulj előtt.
>> DAVID MALAN: Tessék.
>> -Összevonása 108. és 15, akkor a végén fel a lista 15., 108..
Egyesítése és 4. 50, mi a végén a 4, 50.
Összevonása 8 és 42, akkor a végén a 8., 42..
És összevonással 23 és 16, akkor a végén a 16., 23..
>> Most minden listák a 2-es méret.
Figyeljük meg, hogy az egyes négy lista van rendezve.
Tehát lehet kezdeni összevonása pár listák újra.
15 egyesítése és 108., valamint a 4. és 50, mi előbb a 4., majd a 15, majd a
Az 50, akkor a 108.
Összevonása 8., 42. és 16., 23., először vegye a 8, akkor a 16, akkor a 23,
akkor a 42.
>> Így most már csak két lista mérete 4, amelyek mindegyike rendezve.
Tehát most már eleget a két listát.
Először is, hogy a 4, akkor tegye meg a 8, akkor vesszük a 15, majd 16, majd
23, majd 42, majd 50, majd 108.
>> [END VIDEÓ LEJÁTSZÁS]
>> DAVID MALAN: Megint értesítés, soha nem megérintette adott pohár több mint egyszer
miután előre túl.
Tehát soha nem ismétlődő.
Szóval ő mindig mozog oldalra, és ez az, ahol megvan a n.
>> Miért nem engedi, hogy húzza fel egy animáció hogy láttuk korábban, de ezúttal
koncentrálva csak merge sort.
Hadd menjek előre, és nagyítás az ezen a itt.
Először is hadd válasszon egy véletlen bemenet, magasztalja ezt, és akkor valahogy látni
amit biztosra vett, korábban, merge sort valójában csinál.
>> Így veszi észre, hogy lehet ezeket a fél, illetve ezek a negyedek, vagy ezeket a nyolcad
probléma, hogy hirtelen kezd, hogy jó formában.
És végül, látod a a legvégén, hogy a BAM,
minden összefűzve.
>> Tehát ezek csak három különböző veszi fel ugyanezt a gondolatot.
De a legfontosabb betekintést, mint szakadék és meghódítani az első osztályú,
az volt, hogy úgy döntöttünk, hogy valahogy osztani A probléma valami nagy, a
valami fajta azonos szellemben, de kisebb és kisebb és kisebb
és kisebb.
>> Most másik módját valahogy gondolni ezekről, annak ellenére, hogy nem
fog adni ugyanazt intuitív megértés, az
az alábbi animáció.
Tehát ez egy videót valaki össze hogy a kapcsolódó különböző
hangokat a különböző műveletek beszúrás sort, a merge sort, és
egy pár mások.
Így egy pillanat, megyek hit játszani.
Arról van szó, egy perc hosszú.
És bár még mindig látni a minták történik, ez alkalommal is
azt is hallani, hogy ezek algoritmusok végző másképp és
némileg különböző mintákat.
>> Ez a beillesztés fajta.
>> [HANGOK Playing]
>> DAVID MALAN: Ismét megpróbálja beilleszteni egyes elemek
bele, ahová tartozik.
Ez a fajta buborék.
>> [HANGOK Playing]
>> DAVID MALAN És akkor valami érzést hogy viszonylag kevés munka csinál
minden egyes lépést.
Ez az, amit unalom hangzik.
>> [HANGOK Playing]
>> DAVID MALAN: Ez a szelekció sort, ahol válassza ki az elemet szeretnénk a
megy keresztül, újra és újra és újra és üzembe azt az elején.
>> [HANGOK Playing]
>> DAVID MALAN: Ez merge sort, amely akkor tényleg elkezd érezni.
>> [HANGOK Playing]
>> [Nevetés]
>> DAVID MALAN: Valami úgynevezett gnome sort, amit nem nézett.
>> [HANGOK Playing]
>> DAVID MALAN: Tehát lássuk csak, most, zavart, ahogy remélhetőleg a
zene, ha tudok csúszik egy kicsit kis matek itt.
Tehát van egy negyedik módszer is, hogy tudjuk gondolni, mit jelent ezeknek
funkciók, hogy gyorsabb, mint azok hogy már látott.
És ha jön a kurzust a matematika háttérben, akkor
valójában talán már tudják, hogy pofon a távon ez a technika -
nevezetesen rekurzió, a függvény valahogy nevezi magát.
>> És ismét, emlékeztetni arra, hogy merge sort pszeudokódját volt rekurzív abban az értelemben,
hogy az egyik merge sort lépteit volt, hogy hívja sort -
hogy van, maga is.
De szerencsére, mert folyamatosan hívás sort, vagy összeolvad sort,
Konkrétabban, egy kisebb és kisebb és kisebb listát, hogy végül
mélypontját köszönhetően mit fogunk hívni alapesetben a beégetett esetben,
azt mondta, ha a lista kicsi, kevesebb, mint 2 Ebben az esetben csak vissza azonnal.
Ha nem volt, hogy a speciális esetben a algoritmus soha mélypontot,
és akkor tényleg kap egy végtelen ciklusba igazán örökre.
>> De tegyük fel, hogy mi volna a most is Egyes számok ezt újra, ahol n
mint a méret a bemenet.
És meg akartam kérdezni, mi a a teljes időt vesz részt
futó merge sort?
Vagy még általánosabban, mi költsége az időben?
>> Nos, ez elég könnyen mérhető, hogy az.
Ha n kisebb, mint 2, az idő részt A válogatás n eleme,
ahol n értéke 2, 0..
Mert csak vissza.
Nincs tennivaló.
Most kétségtelenül, lehet, hogy egy-két lépést lépéseket, hogy kitaláljuk, az összeget a
működik, de elég közel van ahhoz, hogy a 0 Én csak úgy nemet mondani a munka
szükség, ha a lista olyan kicsi hogy érdektelen.
>> De ez az eset érdekes.
A rekurzív ügy az ága A pszeudokód azt mondta más, sort
A bal oldalán, rendezni a megfelelő fele, összevonja a két fél.
Most miért ez a kifejezés képviseli, hogy a terhére?
Nos, T n csak azt jelenti, a ideje rendezni n eleme.
És akkor a jobb oldali egyenlőségjel ott, a T n megosztott
2-utal, hogy a költségek, mi?
Válogatás a bal felét.
A többi T n osztva 2 feltehetően utalva a költsége
rendezni a jobb felét.
>> És akkor a plusz n?
Van az összevonása.
Mert ha van két listát, az egyik size n több mint 2 és egy másik n méretű
több mint 2, akkor lényegében megérinteni minden egyes ilyen elemek, mint Rob
megérintette az egyes csészék, és csak ahogy mutatott az egyes
önkéntesek a színpadon.
Tehát n rovására összevonása.
>> Most sajnos, ez a formula is maga rekurzív.
Tehát, ha a kérdést, ha n, mondjuk, 16, ha van 16 ember a színpadon
vagy 16 csésze a videó, hogy hány teljes lépést tart rendezni őket
A merge sort?
Ez valójában nem egy nyilvánvaló válasz, mert most meg kell rendezni az
rekurzívan válaszolni ezt a képletet.
>> De ez rendben van, mert hadd javaslatot , hogy mi a következő.
Az idő részt rendezni 16 ember, vagy 16 csésze lesz képviselt
általánosságban T 16.
De ez egyenlő, szerint a korábbi formula, 2-szer annyi
idő kell ahhoz, hogy rendezni 8 csésze és 16.
És ismét, és 16 az idő, hogy egyesülnek, és a két T-szer 8 az
ideje rendezni bal oldalán és a jobb felét.
>> De ismétlem, ez nem elég.
Meg kell merülni a mélyebb.
Ez azt jelenti, meg kell válaszolni a kérdés, mi T 8?
Hát T 8 mindössze 2 T-szor 4 plusz 8.
Nos, mi T 4?
T 4 csak 2-szer T 2 és 4.
Nos, mi T 2?
T 2 csak 2-szer T 1 és 2.
>> És ismét, mi fajta egyre megragadt ebben a ciklusban.
De arról, hogy elérje, hogy az úgynevezett alapeset.
Mert mi a T 1, nem azt állítjuk?
0-ra.
Tehát most végre, akkor a munka hátra.
>> Ha a T 1 0, én most menj vissza egyet sorban ennek az embernek itt, és én is
plug in 0 T 1.
Tehát ez azt jelenti, hogy egyenlő 2-szer nulla, más néven 0, plusz 2.
És így, hogy az egész kifejezés 2 lehet.
>> Most, ha veszek a T 2, melynek válasz 2, dugja be a középső sor, T
4, hogy ad nekem 2-szer 2 és 4, így a 8.
Ha majd dugja 8 a korábbi vonal, hogy ad nekem 2-szer 8, 16.
És ha majd folytassa, hogy a 24, hozzátéve, a 16, végül kap egy
értéke 64,.
>> Most, hogy már önmagában egyfajta beszél semmit az n jelölést, a
nagy O, az Omega, hogy már beszélt.
De kiderül, hogy a 64 valóban 16, a méret a bemenet,
log alap 2 16.
És ha ez egy kicsit szokatlan, csak gondoljon vissza, és akkor gyere vissza
hogy akkor végül.
Ha ez log 2-es alapú, ez olyan, mint 2 emelt, amit ad 16?
Ó, ez 4, így 16-szor 4.
>> És ismét, ez nem egy nagy dolog, ha ez egyfajta ködös emlék már.
De most, hogy a hit hogy 16 log 16 64.
És így valóban, ezzel az egyszerű józan ész ellenőrizze, már megerősített -
de nem bizonyult formálisan -
hogy a futási ideje egyesítése sort valóban n log n.
>> Tehát nem rossz.
Tuti, hogy jobb, mint a algoritmusok láttunk eddig, és
ez azért van, mert megmutatta, egy, nevezett technikával rekurziót.
De sokkal érdekesebb, mint az, hogy a fogalma osztódó és hódító.
Ismét igazán 0. hét dolog, hogy még most is visszatérő a
vonzóbb módon.
>> Most egy jó kis testmozgás, ha már soha nem csináltam - és valószínűleg
nem lett volna, mert valami normális ember nem gondol erre.
De ha elmegyek a google.com, és ha Szeretnék tanulni valamit
rekurzió, Enter.
>> [Nevetés]
[Még több nevetés]
DAVID MALAN: rossz vicc lassan terjed.
[Nevetés]
DAVID MALAN: Csak abban az esetben, hogy ott van.
Nem varázslat rosszul, és ott van a vicc.
Rendben van.
Magyarázd el, hogy az emberek mellett, ha nem egészen kattintott csak még.
De rekurzió, általában arra utal, A folyamat egy függvény hívás
maga, vagy még általánosabban, elosztjuk a probléma, valami, hogy lehet
megoldani darabonként megoldásával azonos képviselő problémákat.
>> Nos, a változás fogaskerekek csak egy pillanatra.
Azt szeretném befejezni bizonyos cliffhangers, úgyhogy kezdjük beállítani
a színpadon, néhány percig, egy nagyon egyszerű ötlet -
hogy a csere két elem, nem igaz?
Mindezek algoritmusok voltunk beszélt az elmúlt pár
előadások is némi a fajta csere.
Ma is láthatóvá kezd velük fel ki a szék és
sétálni, de kódot, akkor azt csak hogy egy elem egy tömb
és nyár, hogy egy másik.
>> Szóval hogyan megy körülbelül ezt?
Nos, hadd menjen előre, és írni gyors program itt.
Én megyek előre, és nem ezt a következő.
Nevezzük ezt -
mit akarunk hívni ezt?
>> Igazából nem.
Hadd visszatekerés.
Én nem akarom, hogy az Cliffhanger még.
Ez rontja a móka.
Csináljuk ezt helyette.
>> Tegyük fel, hogy szeretnék írni egy kicsit programot, és hogy most magában a
ötlete rekurzió.
Valahogy van előtt magam ott.
Megyek tegye a következőket.
>> Először is, a gyors is a szabványos io.h, valamint egy include a cs50.h.
Aztán megyek előre és kijelentik, int main érvénytelennek
a szokásos módon.
Rájöttem már misnamed a fájlt, így hadd hozzá. c kiterjesztés itt ilyen
hogy tudjuk fordítani rendesen.
Indítsa el ezt a funkciót.
>> És a függvény akarok írni, elég Egyszerűen, az egyik, hogy kéri a
felhasználó a számot, majd hozzáteszi fel minden szám között, hogy a
szám, és azt mondják, 0-ra.
Tehát először fogok menni előre és kijelentik, int n.
Aztán másolni néhány kód már használják egy ideig.
Amíg valami igaz.
Jövök vissza, hogy egy pillanat alatt.
>> Mit akarok?
Azt akarom mondani printf pozitív egész kérem.
És akkor fogok mondjuk n lesz kap int.
Tehát még egyszer, néhány boilerplate kód hogy már korábban használt.
És én fogom ezt míg n értéke 1-nél kisebb.
Tehát ez biztosítja, hogy a felhasználó ad nekem egy pozitív egész szám.
>> És most megyek és tegyük a következőket.
Azt akarom, hogy összeadjuk a számok közötti és n és 1, illetve 0 és n,
azzal egyenértékű, hogy a teljes összeget.
Tehát a nagy szigma szimbólum hogy lehet felidézni.
Így fogom, hogy ezt az első hívás függvény szigma nevű,
halad n, aztán megyek mondjuk printf, a válasz ott van.
>> Tehát röviden, kapok, és int a felhasználó elől.
Azt biztosítja, hogy pozitív.
Kijelentem, változó nevű válasz int típusú, és tárolja azt a visszatérő
értéke sigma, átadva az n bemenet.
Aztán kinyomtatni ezt a választ.
>> Sajnos, annak ellenére, szigma hangzik mint valami, ami lehet, hogy
A math.h fájlt, a nyilatkozatát, ez valójában nem az.
Szóval ez rendben van.
Én végre ezt magam.
Megyek, hogy végre egy függvényt nevű szigma, és ez fog tartani egy
paraméter -
hívjuk csak azt m, csak így más.
És akkor itt, azt fogom mondani, Nos, ha m értéke 1-nél kisebb - ez egy
nagyon érdektelen programot.
Szóval megyek előre, és azonnal vissza 0-ra.
Csak nincs értelme, hogy adja ki az összes A számok 1 és m, ha m
maga 0 vagy negatív.
>> Aztán megyek előre és ezt nagyon iteratív.
Fogom ezt a fajta old-school, és én megyek előre
és azt mondják, hogy én fogok kijelentik összeget, hogy 0-ra.
Aztán megyek is a for ciklus int -
és engedi, hogy megfeleljen a elosztás kódot, így van egy példány
otthon. int i lesz az 1-ig i kisebb vagy egyenlő, mint m.
i plus plus.
Aztán belül ez a for ciklus -
majdnem ott vagyunk -
összeget kap összeg plusz 1.
Aztán megyek vissza az összeget.
>> Így aztán ezt gyorsan, nagyon igaz.
De ismétlem, a fő funkciója elég egyszerű, alapuló kód voltunk
írt eddig.
Használja a kettős hurok, hogy egy pozitív int a felhasználó elől.
Aztán át, hogy int egy új funkció nevű sigma, amelyben ez, megint, n.
És tárolja a visszatérési értéket, a válasz A fekete doboz jelenleg
néven Sigma, egy változóban nevű válasz.
Aztán nyomtassa ki.
>> Ha most is a történetet, hogyan szigma végrehajtani?
Azt javaslom, hogy hajtsák végre a következő.
Először is, egy kis hiba-ellenőrzés annak biztosítása, hogy a felhasználó nem
szórakozik velem, és halad néhány negatív vagy 0-t.
Aztán, hogy egy változót nevű Összefoglalva és állítsa 0-ra.
>> És most kezd mozogni i értéke 1 egészen bezárólag m,
mert azt akarom, hogy az összes a számokat egytől m, befogadó.
És azon belül a for ciklus, csak csinálni összeget kapja amit most, valamint a
i értéke.
Plusz az i értékét.
>> Mellesleg, ha már nem látta ezt előtt, van néhány szintaktikai cukor
ezen a vonalon.
Tudom átírni ezt a plusz egyenlő i, csak azért, hogy mentsem magam néhány karakternél
és egy kicsit hűvösebb.
De ez minden.
Ez funkcionálisan ugyanaz.
>> Sajnos, ezt a kódot a nem fog össze még.
Ha futok, hogy szigma 0, mennyire vagyok Fogok kapni kiabált?
Mit fog ez nem tetszik?
>> Közönség: [hangtalan].
>> DAVID MALAN: Igen, én nem nyilvánítja A funkció fel csúcsra, igaz?
C a fajta hülye, az, hogy csak a mit mondani, hogy igen, és
meg kell csinálni, ebben a sorrendben.
És ha én Enter itt fogok kap egy figyelmeztetést szigma implicit
nyilatkozat.
>> Ó, nem probléma.
Mehetek fel a csúcsra, és én is mondjuk, rendben, várj egy percet.
Sigma egy olyan függvényt, amely egy int és vár
int bemenet, pontosvessző.
Vagy sodorhatják az egész funkció fenti fő, de általában, azt
Javasoljuk, ellen, mert szép, hogy mindig fő a tetején, így
lehet zuhanásra és tudja, mi a programot csinál, ha elolvassa legfontosabb először.
>> Tehát most hadd törölje a képernyőt.
Remake szigma 0-ra.
Úgy tűnik, hogy nézd meg.
Engedik szigma 0-ra.
Pozitív inter.
Odaadom a számot 3, hogy ez egyszerű.
Annak érdekében, hogy adjon nekem 3 plusz 2 plusz 1, így 6.
Adja meg, sőt kapok 6.
>> Tehetek valami nagyobb -
50., 12., 75..
Csakúgy, mint egy érintő, azt fogom tenni valami nevetséges, mint egy nagyon nagy
szám, Ó, hogy valóban dolgozott ki -
eh, én nem hiszem, hogy így van.
Lássuk.
Nézzük igazán rendetlenség vele.
>> Ez a probléma.
Mi folyik itt?
A kód nem is olyan rossz.
Még mindig lineáris.
Fütyörészve egy jó hatással, mégis.
Mi folyik itt?
>> Nem biztos, hogy hallottam.
Így kiderül - és ez, mint egy félre.
Ez nem a mag ötlete rekurzió.
Kiderült, hogy azért, mert próbálok jelentenek olyan nagy szám, a legtöbb
valószínűleg ez is félreértelmezik a C, mint egy nem pozitív szám,
de negatív szám.
>> Még nem beszéltünk erről, de a Kiderült, vannak negatív számok
a világ mellett a pozitív számok.
És azokat az eszközöket, amelyek segítségével képviselnek negatív szám
lényegében, van ilyen speciális bit jelzi
pozitív lesz negatív.
Ez egy kicsit bonyolultabb, mint az, de ez az alapötlet.
>> Tehát sajnos, ha a C zavaró egy Az ezeket a biteket ténylegesen jelenti,
ó, ez egy negatív szám, a hurok Itt például, valójában soha
majd megszűnik.
Tehát, ha én tényleg valami nyomtatás újra és újra, mi lenne
lát egy csomó.
De ismétlem, ez mellett a lényeg.
Ez tényleg csak egyfajta intellektuális kíváncsiság, hogy mi fog jönni
vissza, hogy végül.
De most, hogy ez a helyes végrehajtás, ha feltételezzük, hogy a
felhasználó biztosítja ints illik a ints.
>> De azt állítják, hogy ezt a kódot, őszintén szólva, lehet tenni, így sokkal egyszerűbben.
Ha a cél a kezét, hogy egy számot mint m, és adja ki az összes
közötti számok, és 1, vagy fordítva 1 és, azt állítják,
, hogy én is ezt a gondolatot, hogy a kölcsön egyesíteni sort is, amely vesz egy probléma
Az ilyen méretű, és azt elosztjuk valami kisebb.
Lehet, hogy nem fél, de kisebb, de reprezentatív ugyanaz.
Ugyanez a gondolat, de a kisebb probléma.
>> Szóval tényleg - hadd menteni a fájlt egy másik verzió számot.
Hívjuk ezt a verziót 1 0 helyett.
És azt állítják, hogy én valóban újraimplementálni ezt a fajta
pszichedelikus módon.
>> Fogom hagyni részét egyedül.
Azt fogom mondani, ha m kisebb vagy akár mint az egyenlő 0 -
Én csak lesz egy kis több anális ezúttal
az én hibaellenőrzés -
Én megyek előre, és vissza 0-ra.
Ez önkényes.
Én egyszerűen annak eldöntéséhez, hogy a felhasználó ad nekem egy negatív szám, én vagyok
visszatérő 0, és kellett volna olvasni a dokumentáció jobban.
>> Else -
észre, mit fogok csinálni.
Else fogok visszatérni m plus -
mi szigma m?
Nos, szigma m plusz mínusz 1 m, plusz mínusz m 2, plusz mínusz 3 m.
Én nem akarok írni minden adott ki.
Miért nem csak punt?
Rekurzívan hívja magam egy kicsit Kisebb probléma, pontosvessző,
és ez egy nap?
>> Nem igaz?
Most itt is, úgy érezheti, vagy aggódni hogy ez egy végtelen ciklus, hogy én vagyok
indukáló, ahol én végrehajtási sigma sigma meghívásával.
De ez teljesen rendben van, mert én gondolt előre hozzáadott melyik vonal?
>> Közönség: [hangtalan].
>> DAVID MALAN: 23-26, ami az én, ha a feltétel.
Mert mi a jó a kivonás itt, mert én is
átadta szigma kisebb problémák, kisebb problémák, kisebb - ez nem
feleakkora.
Ez csak egy apró lépés a kisebb, de ez rendben van.
Mert végül is, akkor a munka utunkat lefelé 1-re vagy 0-ra.
És ha elérünk 0, Sigma nem fogja hívni magát többé.
Ez lesz, hogy azonnal vissza 0-ra.
>> Így a hatás, ha a fajta szél a a fejedben, hogy adjunk m plusz
m mínusz 1, plusz mínusz m 2, plusz mínusz m 3-hoz, pont, pont, pont, m mínusz
m, végül így 0, és a hatás végül hozzá az összes
ezeket a dolgokat együtt.
Tehát nem a rekurzió, megoldotta a problémát, hogy mi
nem tudta megoldani előtt.
Sőt, 0-s verzió ezt, és minden probléma a mai napig, már megoldható
csak használ hurkok, vagy pedig hurkok vagy hasonló konstrukciók.
>> De rekurzió, merem állítani, ad más módon való gondolkodás
probléma, amely ha tudunk egy probléma, ossza azt valami
kissé nagy valami kissé Kisebb, azt állítom, hogy meg tudjuk oldani
talán egy kicsit elegánsabban szempontból A design, a kevesebb kód,
és talán még megoldani a problémákat, amelyek nehezebb lesz, hiszen akkor végül
Látod, megoldása tisztán iteratív.
>> De az, hogy én nem Cliffhanger akarja elhagyni minket volt ez.
Hadd menjek előre, és nyitott egy fájl -
tényleg, hadd menjen, és ezt nagyon gyorsan.
Hadd menjek előre, és javaslatot a következő.
Napjaink kódja a fájl itt.
Ez itt, noswap.
>> Tehát ez egy hülye kis program, amely Én felkorbácsolta, hogy azt állítja, hogy nem
a következő.
A legfontosabb, hogy először kijelenti egy int hívott x és hozzárendeli
az 1 értéket.
Aztán kijelenti egy int y és hozzárendeli az érték 2.
Aztán kiírja, hogy milyen x és y.
Majd azt mondja, csere, pont, pont.
>> Majd azt állítja, hogy hívja a függvényt nevezett csere, átadva x és
y, az ötlet, amely szerint remélhetőleg x és y vissza fog térni
más, az ellenkezője.
Akkor állítják cserélték!
egy felkiáltójel.
Aztán kiírja x és y.
>> De kiderül, hogy ez a nagyon egyszerű bemutató le
Itt valóban hibás.
Bár én nyilvánított átmeneti változó ideiglenesen amivel egy a
, akkor én átcsoportosításával egy az értéke B -
amely úgy érzi, indokolt, mert én már mentett egy példányát a temp.
Aztán frissítse b egyenlő bármi volt temp.
Ez a fajta shell játék mozgatása a b és b egy ezzel a
közép-man nevű temp érez teljesen ésszerű.
>> De azt állítják, hogy amikor elindul a kódot, ahogy én nem most -
hadd menjen előre, és illessze be itt.
Hívom ezt noswap.c.
És ahogy a neve is mutatja, ez nem lesz megfelelő programot.
Legyen noswap. / Nincs csere.
x értéke 1, y értéke 2, csere, cserélték.
x értéke 1, y értéke 2.
Ez alapvetően rossz, még de ez úgy tűnik, tökéletesen
ésszerű nekem.
És van egy ok, de mi nem vagyunk lesz, hogy felfedje az ok csak még.
>> Mert most a második Cliffhanger akartam itt hagyni ez, egy
bejelentése a fajta a kupon kód.
Az innováció végén napok idén váltott ki a nem elhanyagolható számban
A kérdés, ami Nem célunk.
A szándék e kupon kód, amely, ha nem a probléma része
meg korán, így kapok egy extra napot, igazán, hogy segítsen nektek segíteni
magad korán kezdeni, sort Az a ösztönzünk téged.
Segít terjeszteni terhelést a nyitvatartási jobban, hogy
Ez a fajta win-win.
>> Sajnos, azt hiszem az utasításaimat nem volt, a mai napig, nagyon világos, így
Visszamentem a hétvégén és frissített A spec a nagyobb, merészebb szöveg
megmagyarázni golyók, mint ezek.
És csak azt mondom, hogy több nyilvános, a Alapértelmezésben probléma határozza miatt csütörtök
délben, egy a tananyag.
Ha korán kezdeni, befejező része A probléma által szerda 12:00
PM, az a része, amely kapcsolódik egy kupon kódot, az ötlet, hogy akkor terjed
A határidő a P meg péntekig.
Ez azt jelenti, kicsit le egy kis része a P beállítva ahhoz képest, amit jellemzően a
nagyobb probléma, és veszel magadnak egy extra napot.
Ismét lesz gondoltál A probléma meg, kap, hogy
munkaidőben hamarabb.
De a kupon kód probléma még mindig szükséges, akkor is, ha nem nyújtja be azt.
>> De még ez a feltűnően.
(Színpadi suttogással) És azok emberek így elején fognak bánni.
Ahogy az emberek az erkélyen.
Előre is elnézést, hogy az emberek a az erkélyen okok miatt lesz
világos csak egy pillanat.
>> Így szerencsések vagyunk, hogy az egyik CS50 korábbi vezetője tanítása fiúk at
nevű cég dropbox.com.
Ők nagylelkűen adományozott a kuponkódja ide a sok helyet,
amely akár a szokásos 2 gigabájt.
Tehát mi azt gondoltuk, hogy ezt ezen a utolsó megjegyzés nem egy kicsit giveaway,
ahol csak egy pillanat, mi fog kiderülni a győztes, aki a szelvényt
kódot, akkor majd megy a website, írja be, és íme, kap egy
az egész sokkal több hely a Dropbox készülék és a személyes fájlok.
>> És az első, aki szeretne részt venni ebben a rajzban?
OK, most, hogy teszi még szórakoztatóbb.
Az a személy, aki megkapja ezt a 25 GB-os szelvény kód - amely messze
vonzóbb, mint a néhai Napok óta, talán -
az, aki ül a tetején egy ülőpárna, amely alatt van
hogy kupon kód.
Lehet, hogy most meg alatta az ülőpárna.
>> [VIDEÓ LEJÁTSZÁS]
>> -Egy, kettő, három.
>> [Screaming]
>> -Kapsz egy autó!
Kapsz egy autót!
>> DAVID MALAN: Meglátjuk akkor szerdán.
>> -Kapsz egy autó!
Kapsz egy autót!
>> DAVID MALAN: Erkély emberek, gyere ide, hogy az első,
ahol már extrával.
>> -Mindenki kap egy autót!
Mindenki kap egy autó!
>> [END VIDEÓ LEJÁTSZÁS]
>> Srácok A következő CS50 -
>> SPEAKER 5: Oh, istenem istenem istenem gosh Istenem Istenem Istenem Istenem Istenem Istenem -
>> [Ukelele PLAYS]