[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! Kapsz egy autót! Kapsz egy autót! 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]