Előadó: Rendben, ez CS50. Ez a három hét végén, és ha Ön még nem vette igénybe már, tudja, hogy nem lesz ebéd pénteken a szokásos módon, ahol élvezheti a jó beszélgetés és élelmiszerek Tűz és jég néhány CS50 a munkatársak és osztálytársak. Fej ezt az URL itt. 

Most már emlékszem, vagy hamarosan meg kell ismertetni, ezeket a dolgokat itt, ami kapnak ki a végén A félév számos osztályok. Úgynevezett vizsga kék könyvet, amelyben írjuk meg a választ vizsgák. Most van itt 26 ilyen kék könyv, mindegyiken van írva a név, A-tól Z és valóban a nevek, hogy egyszerű, A keresztül Z. És az egyik a célok kéznél ma lesz, hogy továbbra is mi mi hétfőn kezdődött, ami nem annyira nézett kódot, de tényleg nézett ötletek és problémamegoldás. Az egyik a célok és ígéretek a tanfolyam az, hogy megtanít gondolkodni alaposan, több módszeresen, és megoldani a problémákat hatékonyabban. És valóban, amit tehetünk, hogy valóban anélkül, érintése egy sor kódot. Szóval van egy pár elefánt ma ide, narancs és kék, ha tudnánk egy önkéntes, talán a távolabb, mint máskor. Mi a helyzet ott, gyere le. Melynek célja lesz, hogy segít plusz kezeli ezt a vizsgát itt. Mi a neve? 

Közönség: Mary Beth. Előadó: Mary Beth, gyere fel. Hadd a mikrofont itt. Örülök, hogy találkoztunk. 

Közönség: Örülök, hogy találkoztunk. Előadó: Rendben, így már itt kék könyvet A-tól Z-ig, és én fogom állítani, hogy Van egy, a diákok, és jönnek a némileg véletlenszerűen a végén egy három órás vizsga blokk, így ők kiöntött néhány félig véletlen sorrendben, mint ez. Most a munka egy pillanat lesz a be-- ez valójában hogyan kap fordult végén az osztály, a legvalószínűbb. Az Ön feladata most lesz, egészen egyszerűen, hogy rendezni ezeket a kék könyv nekünk A-tól Z- 

Közönség: Ó, ez fog tartani örökre. 

Előadó: És mi lesz nézni ahogy ezt megteszi, nincs nyomás. Közönség: Nem, nincs nyomás, vagy bármi. 

SPEAKER: És a móka kedvéért, tegyük fel egy időzítő. 

Közönség: Annyira szórakoztató, annyira szórakoztató. 

Előadó: tudom tartani a mikrofont az Ön számára. Rendben, most már csak megduplázódott a sebesség. Tehát addig is, hadd tegyek fel, mi van lesz a kérdés Mary Beth az, amit csinál, hogy van megy a megoldásában? És valóban, lehet, hogy nincs már, gondoltam valami olyan egyszerű, mint amikor kiválasztotta akár 26 könyv, mint ez, amelyek egy természetes rendelési nekik. Mi az a folyamat hogy ténylegesen használni? Ez meglehetősen véletlenszerű csak szedés az első látható és megvalósítják azt a helyére? Ön először mozgatni a kezét körül Keresek egy majd keres B? Ön vessünk egy pillantást a pár egymás mellé és csak annyit, várj egy percet, ez nem helyes, és majd cserélni a sorrendben? Láttuk már hétfő hogy van számos módon melyben meg tudjuk csinálni, és Valóban, ahogy a vége felé itt, Azt tudomásul veszik talán , amit Mary Beth csinál. Van néhány cölöpök úgy tűnik, a nagyobbat, három kisebb. 

Közönség: Én elrendelő ha találok két betű hogy tudom, hogy együtt vannak a sorrendben, Tettem őket, hogy én nem kell aggódnia, hogy nyomon pálya egy egész sor könyvet. Ez csak, ó, az első, Van ez a verem itt. Előadó: Szóval, mintha a puzzle darabokat, hogy joguk alakja egyeznek meg egymással. Közönség: Nagyjából, igen. Előadó: OK, kiváló. És most minden egyes ilyen cölöpök feltételezhetően sorrendje? 

Közönség: Igen. 

Előadó: Rendben, A-tól Z-All jobb, gratulálok, megcsináltad. Megvan a választás. Kék? Rendben, köszönöm, hogy. Így Mary Beth nem javasol mi a megközelítés, de mi egy másik megközelítés, hogy hogyan Lehet, megy a válogatás ezeket a dolgokat? Mit tettél? A rekord, hogy megverte volna egy perc és 50 vagy még több másodpercre, plusz az is elfelejtettem számolni. Mit tettél? Igen? Közönség: Fogd a verem. Kezdje az elején. Ellenőrizze a papírokat. És ha az első egy nagyobb mint, talán, igen, az egyik az alsó magasabb, akkor váltani őket. 

Előadó: OK, így kezdődik a felső és az alsó, majd a munka az utat befelé, mint, hogy swapping őket? OK, így egy kicsit hasonló a szellem buborék sort, De a választás a szélsőségeket nem a szomszédos párok. De rövid az az, hogy van biztosan egy csomó különböző módon mi is ezt, és őszintén szólva, azt hiszem, ilyen elfogadott egy pár megközelítést, igaz? Ön tett valami négy rendezett aranyér, és akkor gyakorlatilag összeolvadt őket. És ez, mondhatnám, egy másik technika teljesen. Nem kezelik, mint egy nagy halom, Ön osztva a problémát négy quadok, ha úgy tetszik, és majd valahogy egyesült őket a végén. 

Tehát nézzük meg, végül, hogy mást is lehet csinálni ezt. Mi hivatalossá a fogalom buborék sort utoljára, és buborék sort visszahívás volt algoritmus, hogy láthatóvá nyolc az osztálytársaival fel itt, látszólag véletlenszerűen rendezett először. És akkor úgy döntött, páros, ha két elem elromlott, csak cserélni őket. Tehát négy és kettő nyilvánvalóan ki annak érdekében, így a két osztálytársak helyet cserélt. Aztán megismételtük négy és hat, majd hat és nyolc, minden ismétlés, mozog jobbra. 

Tehát adott nyolc ember, hány páronként összehasonlításokat tettem járás közben a balról jobbra az egyik iterációban ilyen? Hány összehasonlítás? Hét, nem? Mert ha van nyolc emberek, de van a pár őket, és folyamatosan mozgásban egyik hop jobbra, akkor nem lesz nyolc összehasonlítás, mert nem lehet összehasonlítani egy elem maga ellen, vagy akkor csak értelmetlen, így hét. Vagy még általánosabban, ha van n emberek, mi do n mínusz 1 összehasonlítást A buborék sort. 

Tehát nézzük meg most, hogy jó, vagy rossz buborék sort valójában volt, és próbálja meg hogy magunkat szókincset amely a kritika algoritmusok, mint ez, és hamarosan a saját. Tehát az első lépés a buborék sort, az első alkalommal Mentem balról jobbra haladva a szakasz, elvitt n mínusz 1 összehasonlítást. És ez lesz az én mértékegység, igaz? Én ilyen beszéd és sétáló, kissé gyors, kissé lassú, így számolás a másodpercek száma nem különösebben erős, de számolás száma műveletek én hétfőn, összehasonlítása a két ember, hogy úgy érzi, mint egy szép mértékegység. 

Tehát n mínusz 1 lépést az első alkalommal, de akkor mi történt? Mi az az egy fejjel az egy menetben keresztül egyébként rendezetlen listát? Mit tud mondani a elem aki egészen ott? Igen? Ez volt a legnagyobb elem, ugye? Nyolcas, annak ellenére, hogy itt kezdődött, minden alkalommal, amikor összehasonlítva a szemben a szomszéd, ő tartotta bugyogott fel a jobb oldali a listából. És valóban, ez az, ahol Az algoritmus kapta a nevét. 

Most az a logika, hogy hány összehasonlítást kell azt, hogy a második alkalommal Azt, hogy hogy át balról jobbra? n mínusz 2, ugye? Ez csak vesztegeti az időmet, ha folyamatosan összehasonlítva nyolc valaki ellen mást, mert mi már tudjuk, ő volt a megfelelő helyen. Szóval ez egy kicsit egy optimalizálás, így a következő lépés lesz, plusz n mínusz két lépést, ahol n az emberek száma. Most már ilyen extrapolálni, még ha nem egy számítógép tudós, hogy ez véget ér. Végén ezen algoritmus, feltehetően megvan csak egy összehasonlítás maradt. Meg kell, hogy milyen rögzítse a a lista elején ebben az esetben két és az egyik nincs rendben kell lennie, és az egy és két, így ez fenekek ki plusz 1 utolsó összehasonlítást. 

Most a pont, pont, pont olyan hullámokat ez kezét néhány juicier részletek De tételezzük fel, megy előre, és egyszerűbbé. Ha felidézzük a nagy iskola, őszintén szólva, sok van volt matematikai könyvek, hogy már egy kis puskát az előlapot, illetve a hátlap hogy mutattam milyen sorozat összegzések, mint a ez végül össze kell adni. Általános esetben, ha van egy változó, mint n, és valóban ez az egy, ha ránézett a old school matematika könyvet, akkor láthatjuk, hogy ez valójában tesz ki, ezt az összeget itt, n-szer n mínusz 1 egész osztva 2. Tehát most hadd kikötik ez igaz, így egy ugrás a hit, ez az, amit ez összegzi ig, és mi is azt bizonyítják, hogy egy általánosabb eset. De most nézzük bővíteni ezt ki. Szóval szaporodnak ezt ki, annak érdekében, hogy ez n négyzeten, mínusz n, mind osztva 2. Ez tényleg n faragva, osztva 2, mínusz n több mint 2, hogy minden szép és érdekes. De mi történik, ha Most plug-in egy értéket? Tegyük fel, hogy nem volt nyolc emberek, de mondjuk egy millió. És egy millió csak azért, mert ez egy nagyon nagy szám, hadd csatlakoztassa, hogy, és meglátjuk, mi történik. Tehát ha csatlakoztatok egy millió abba a formula Megyek, hogy egy millió kockás, osztva 2, mínusz a millió, osztva 2. Most mi lesz, hogy egyenlő? Tehát 500 milliárd, mínusz 500.000. És ha tényleg nem hogy a matematika ki, azt jelenti, hogy a válogatás a millió emberek a buborék sort Lehet, hogy nekem 499.999.500.000 lépések vagy összehasonlítások a végén, mi csak kivetítve. 

Hogy úgy érzi, elég lassú, de őszintén szólva mérése egy adott bemenet mint ez, nem olyan sokatmondó. De valójában ez nem azt sugallják, hogy az n egyre nagyobb és nagyobb, ez az algoritmus a fajta érzés rosszabb és rosszabb, vagy tényleg kezd érezni a fájdalmat, hogy a hatványozás, hogy n faragva, amely hozzáteszi fel elég gyorsan. És ez a részlet nem elveszett ember, sőt néhány évvel ezelőtt egy bizonyos szenátor, aki kampány, leült egy interjú a Google Eric Schmidt, vezérigazgató abban az időben, , és megtámadta a kérdés hasonlóan mi feltárása ma. Vessünk egy pillantást. 

[Videolejátszás] 

-Senator, Te itt a Google, és szeretem gondolni az elnökség mint egy állásinterjú. Nos, ez nehéz, hogy munkát, mint elnök, és megy keresztül a szigorú most. Ez is nehéz munkát találni a Google. Van kérdés, és mi Kérje jelöltek kérdéseket, és ez az egyik a Larry Schwimmer. Mi-- srácok hiszem, viccelek, ez itt van. Mi a leghatékonyabb módja annak, hogy rendezni egy millió 32 bites egész? 

-Well-- 

Ne haragudj, maybe-- 

Nem, nem, nem. Azt hiszem, a buborék fajta lenne a rossz út. 

Gyerünk, ki mondta ezt neki? Nem láttam a számítógép tudomány a háttérben. 

-Van A kémek is. 

-OK, Kérdezzük más interjú kérdés. 

[END Videolejátszás] 

SPEAKER: Tehát beszél konkrét számokat azonban, Nem lesz minden, hogy hasznos. Ez nem egy élet leckét, hogy buborék sort, mivel a millió bemenet, Lehet, hogy több mint 500 milliárd lépéseket. Nem igazán lehet általánosítani is hatékonyan az és a jó tervezési döntések írásakor programok. Szóval összpontosít mégis hogyan talán egyszerűsíteni ezt az eredményt. 

Szóval sárga színnel van az eredmény N négyzethálós osztva 2, így egy millió kockás osztva a 2, majd Már kiemelt milyen A végső válasz ha egyszer le kell vonni le n osztva 2. És a követelés fogok tenni most, Ki a fene törődik, ha kivonni ki egy kis régi n több mint 2, amikor az első része ez a képlet sokkal nagyobb? Uralja a többi kifejezés, n négyzethálós osztva 2 annyival nagyobb, tisztán, mint n egyre nagyobb lesz, mint egy millió, ez valóban egy nagy különbség a végén a nap között 500 milliárd és 499.999.500.000? Nem igazán. És mit fogunk tegye a számítógép tudósok figyelmen kívül hagyja ezeket az alacsonyabb rendű tagokat és hogy valami ilyesmi, és tényleg csak egyszerűsíti azt a kifejezés ez fog számítani. A nagyobb az adathalmazok kap, a nagyobb adatbázisaink kap, a több weboldalak meg kell keresni, a több ember van a Facebookon. 

Az n lesz nagyobb, vagyunk igazán fog törődni a legnagyobb kifejezés bármely ilyen elemzés az algoritmusok teljesítmény. És azt fogom mondani, tudod mit, buborék rendezés a sorrendben nagy O, A rendelés n négyzeten. Ez nem pontosan n kockás mint láttuk, de aki igazán érdekel azokról a kisebb szempontból és őszintén szólva, aki igazán érdekel, ha elosztjuk 2? Ez csak egy állandó tényező. És 500 milliárd versus 250 milliárd tényleg olyan nagy dolog? Én is csak várni egy évet, hagyja a laptop a szó szoros értelmében kétszer olyan gyorsan kap a hardver, és az a fajta különbség csak elmegy természetesen az idő múlásával. 

Mi törődünk az a kifejezés a része, A kifejezés, hogy fog változtatni mint a bemenő egyre nagyobb és nagyobb. És valóban, a valós világban, ez az, ami történik inkább a bemenetek a problémák és algoritmusok egyre nagyobb. Tehát nagy O lesz a jelölés, az aszimptotikus jelölés, hogy mi csak használja a számítógép-tudósok leírni a teljesítmény, illetve a működési idő, egy algoritmus. Ahhoz, hogy össze tudjuk hasonlítani algoritmusokat különböző számítógépeken írott különböző emberek, segítségével néhány alapvetően hasonló metrikus mint az összehasonlítások száma te így, vagy esetleg a számát swapok írsz. 

Amit nem fog száma az időt hogy átadja az óra jellemzően a falon. Amit nem fog aggódni arról van szó, hogy mennyi memória Ön használ ma legalábbis, bár ez Egy másik forrás talán mérni. Fogunk próbálja alapozni elemzések az csak az alapvető műveleteket, azok, őszintén, hogy lehet látni a legtöbb vizuálisan. Tehát valami, mint a nagy O n faragva, azt állítom, hogy O-n négyzetes egy felső korlát az úgynevezett menetideje buborék sort. Más szóval, ha akarta állítani, hogy van Ez a felső határ, hogy hány lépéseket egy algoritmus eltarthat, ez lesz a nagy O n kockás ebben az esetben, egy felső korlát. 

Mi van, ha én inkább változtatni a történet, hogy nem a buborék sort, de erről a felső korlátot. Nem gondolod, hogy egy algoritmus hogy megnéztük már amelynek a felső határ, maximum intézkedés az idő vagy a műveletek azt lehet mondani, hogy korlátos n, egy lineáris függvény, nem egy másodfokú az egyik, hogy görbe? Mi az az algoritmus, amely mindig nem több mint például N lépésben, vagy 2n lépést, vagy 3n lépések? Igen? 

Közönség: Megtalálni a legnagyobb szám a listán? 

Előadó: Tökéletes, találni a legnagyobb szám a listán. Ha én egy listát, emberek például, mindegyik, aki a kezében egy számot, mi az a maximális száma lépést meg kell tennie nekem, meglehetősen okos ember, hogy megtalálják a legnagyobb ember a listán? n, igaz? Mivel a legrosszabb esetben, amikor talán a legnagyobb érték legyen? Jobb, egészen a végén. Tehát a legrosszabb esetben felső kötött, talán kell menni egészen ide, és mint a Ó, itt van a nyolcas számú, vagy bármi ez az érték. Most ez csak hülye ha folyamatosan megy, ugye? Keresi a több és több elemet ha az utolsó közülük ott? Szóval biztosan, n egy felső korlát. Nem kell, hogy több lépést, mint a. 

Mi van, ha ehelyett azt javasolta, hogy vannak algoritmusok ebben a világban, hogy Van egy futó idő, ami által határolt nagy O log n log n? Hol láttuk ezt korábban? Igen? 

Közönség: a telefonkönyvben probléma? SPEAKER: Mint a telefonkönyv probléma. Mi volt az intézkedés, hogy milyen sok időt vagy hány könny az elvitt találni valakit, mint a Mike Smith a telefonkönyvben? Azt állította, hogy log n, és akkor is, ha ismeretlen, vagy azt, hogy ez egy kicsit homályos, amit egy logaritmus vagy kitevő volt, Csak arra emlékszem, hogy a log n általában arra a folyamatra utal, Ebben az esetben, az osztódó valami félbe újra, és újra, és újra, és újra, úgy, hogy lesz egyre kisebb, ahogy csinálni. 

Tehát log n utal, biztos, A telefonkönyv példa, bináris keresés elméletben, amikor volt a virtuális kapuit a táblán, vagy amikor Sean volt keres valamit. Ha ő használt bináris keresés, log n lenne a felső határ, hogy mennyi alkalom, hogy vesz. De azok algoritmusok futott log n feltételezett milyen kulcsfontosságú részlet? Hogy a lista sorrendje, igaz? Ön algoritmus baj, ha a bemenet nincs rendezve, és mégis használ olyasmi, mint a bináris keresés mert lehet, hogy ugrik jobb az elem anélkül, hogy észrevennénk, hogy ez valóban ott van. 

Most, hogy mi ez, a nagy O egy? Ez nem azt jelenti, hogy az algoritmus vesz egy és csak egy lépés, ez csak azt jelenti, hogy vesz egy állandó számát. Lehet, hogy 1, lehet, hogy 10, lehet, hogy 1000, de ez független a méret a problémát. Nem számít, milyen nagy n, állandó idő algoritmus mindig úgy azonos lépések számát. Szóval, mi lehet egy algoritmus beszéltünk, vagy csak ösztönösen, hogy jön, hogy mindig fut az úgynevezett konstans idő? Igen? 

Közönség: Add két szám. Előadó: Add két szám, 2 plusz 2 egyenlő 4, kész. Annak érdekében, hogy működhet, mi más? Mi lenne, még a valós világban, ugye? 

Közönség: Megtalálni a első dolog, amit egy listában. SPEAKER: Megtalálni az első elem a listán, biztos. Már valóban beszélt a tömbök már, hogyan kap a első eleme egy tömb, nem számít, milyen hosszú a tömb a C kód? Csak használja, mint a konzol nulla jelölés, bumm, ott vagy. És valóban tömbök, mint egy félre, támogatás valami általánosan ismert A véletlen hozzáférés, véletlen elérésű memória, mert akkor szó szerint ugrás minden egy helyen. Meg tudjuk csinálni ezt még egyszerűbben akkor hátra hétig nulla amikor nem Scratch. Mennyi idő telt el a mondjuk blokk Scratch végrehajtani? Csak állandó, igaz? Mondj valamit, mondjuk valamit, akkor nem számít milyen nagy karcolások világ, ez mindig megy, hogy ugyanannyi idő alatt hogy egyszerűen mondani valamit. 

Szóval ez az állandó idő, de mi van a másik oldala? Ha ez volt a felső határokat, mi van, ha azt akarjuk, leírni az alsó határt mi algoritmusok futási idő? Majdnem egy legjobb esetben esetleg, ha úgy tetszik, bár ezek a feltételek nem alkalmazhatók a legjobban esetek, legrosszabb esetben az átlagos esetek több általában, de most csak a hangsúly az alsó határ általában. Mi az az algoritmus, amely alsó határát n lépések vagy 2n lépést, vagy 3n lépések? Néhány tényező n lépések, ez az alsó határ. Igen? 

Közönség: Bubble sort? 

Előadó: Bubble sort tart Ön minimálisan n lépések, miért? Miért van ez? Miért kell, hogy a kezdetektől a hozzád ösztönösen, akkor is, ha ez nem csak még? Igen? 

KÖZÖNSÉG: [nem hallható]. Előadó: Pontosan. A lehető legjobb forgatókönyv szerint buborék sort, és sok algoritmusok ha átadom neked nyolc embert akik már válogatni, butaság lenne az Ön számára, az algoritmus, hogy menjen oda-vissza többször, nem igaz? Mert amint séta a listában egyszer, fel kell ismerniük, ó, nem tett swap, ez lista, kilép. De ez fog tartani N lépésben. 

És fordítva, mi egy másik gondolkodásmód ez? Bubble sort egy omega, hogy úgy mondjam, n, mert ha megnézi kevesebb, mint n elem, amit az alapvető probléma ott? Nem tudom, ha ez válogatni, igaz. Mi, emberek talán pillantást nyolc emberek, és mint, ó, ez válogatni, hogy nem engem n lépést, de ez nem. A szemed, még akkor is, kedves Az egy nagy látómező, Megnézted nyolc elem, Megnézted nyolc ember, Ez nyolc lépésben hatékonyan. És csak akkor, ha sétálok az egész lista nem látom, igen, válogatni. Ha megáll félúton gondoltam, minden jobb, ez elég válogatott eddig, mi az esélye, hogy nem válogatott? Hogy algoritmusok nem lesz helyes. Lehet, hogy gyorsabb, de helytelen. 

Tehát most van egy módja leíró alacsonyabb határt, És mi a helyzet változatlan idő? Mi az az algoritmus, amely alacsonyabb kötött annak futási ideje egy? 1. lépés, 2 lépés, 10 lépés, de állandó, független n, a méret a bemeneti? Igen, vissza. 

Közönség: printf? Előadó: Mi ez? Közönség: printf? Előadó: printf. OK, biztos. Tehát vesz egy fix számát. És én now-- most, hogy beszélünk C kód és nem karcolja, valami mint mondják, a printf, meg kell kezdeni, hogy óvatos. Mivel a printf nem veszi bemenet, ez egy string, és vonósok még technikailag is hosszú. Tehát, ha most szeretnénk felvenni rád, ha nem bánod, technikailag mi lehetne vitatkozni, hogy printf nem fog egy változó hosszúságú bemenet, és biztosan lehet, hogy több ideje, hogy nyomtassa ki a húr ezt a hosszú, mint ilyen sokáig. 

Mi van, ha figyelembe vesszük, csak a válogatás és keres példát? Mi a Mike Smith, a telefon könyv, vagy bináris keresés általában? A legjobb esetben, hogy mi fog történni? Kinyitom a telefonkönyvben, és bumm, ott van Mike Smith számát. Én hívom azonnal. 

Tett egy lépést, talán két lépést, de állandó lépések száma ha szerencsém volt. És őszintén szólva, láttuk a Hétfő az osztálytársa kap elég szerencsés kétszer egymás után. És ez valóban állandó időt egy alsó korlát az algoritmus a szóban forgó megállapítás a szám 50 mögött zárt ajtókat. 

Most, mint egy félre, ha rájössz hogy mind a nagy O, a felső határ, és omega, az alsó határ, egyek ugyanaz, hogy azonos képlet zárójel, akkor is azt mondják, csak a képzelet, hogy valami van a theta n vagy theta valamilyen más értéket. Ez csak azt jelenti, amikor a nagy O és omega azonos. Most mi a kiválasztás sort? Használjuk ezt az új szókincs. A kiválasztás sort, mi voltunk csinál újra, és újra, és újra? Úgy volt, oda-vissza a listán, akik a kinek? A legkisebb szám. 

Szóval, hány lépés, hogyan sok összehasonlítást tettem kell tenni annak érdekében, hogy kitaláljuk, ki a legkisebb elem a listán volt? n mínusz 1, igaz? Mert ha csak kezdeni az egyik én vagyok adott és elkezdek összehasonlítása neki, majd neki, őt vagy őt, őt, én csak párosítani elemek együtt n mínusz 1 alkalommal. Tehát kiválasztás sort hasonlóan úgy n mínusz 1 lépést az első alkalommal. 

Hány lépést tart engem meg a második legkisebb elem? n mínusz 2, mert én vagyok, hogy hülye Ha tovább néztem ugyanazok az emberek újra, ha már választott neki vagy neki, és tedd a helyükre. És a harmadik lépés, n mínusz 3, akkor n mínusz 4. Láttuk ezt a mintát előtt, és valóban kiválasztás sort hasonlóan van egy felső korlát n négyzetes ha ezt tesszük fel, hogy az összegzés. Mi az alsó határ, a kiválasztás sort? Minimálisan, mennyi idő kiválasztás sort, hogy, amint azt határozta meg hétfőn? Javaslatot tesz két lehetőség. Lehet, hogy n, mint korábban. Lehet, hogy az n faragva, hiszen most mivel a felső határ. 

Közönség: n négyzeten. SPEAKER n négyzeten. Miért? 

Közönség: Mert van határozza meg [nem hallható]. 

Előadó: Pontosan. Legalábbis ahogy én meghatározott kiválasztás sort volt elég naiv, folytasd, megtalálja a legkisebb elem. Megint, meg a legkisebb elem. Megint, meg a legkisebb elem. Nincs valami optimalizálás ott Lehet, hadd szakítsa után csak n vagy olyan lépéseket. Tehát valóban, a kiválasztás sort, omega n négyzeten. 

Mi a beillesztés sort, ahol vettem aki kaptam, aztán lehuppant rá töltse le a megfelelő helyen? Aztán folytatta, hogy a másik személy, lehuppant rá a megfelelő helyen. Aztán a következő személy, lehuppant őt a megfelelő helyen. Vegyük észre, hogy ez nagyon lineáris, hogy úgy mondjam. Én egy egyenes vonal, én vagyok nem megy oda-vissza, Még soha nem nézett vissza igazán, de mi történik, amikor beszúrni neki vagy őt elejére A lista, mint mi hétfőn? Mi történik? Igen? KÖZÖNSÉG: [nem hallható]. Előadó: Igen, volt a fogás, igaz? Lehet, hogy visszahívja a az osztálytársaival, ha arra, hogy bármilyen mozgás lábuk, ez a művelet. Tehát, ha három ember itt Az új személy tartozott út oda, egy hosszú szakasz, mint ez, biztos, hogy vagy ő is csak megy a legvégén. De ha nem gondolkodik a és egy sor számítógépes memória, ezek az emberek mennek hogy a shuffle át hogy helyet csináljon az ember. És így, hogy n mínusz 1 shufflings, n mínusz 2 shufflings, n mínusz 3 shufflings csak egyfajta történik a hátam mögött, nem előttem mint korábban, bizonyos értelemben. Most, mint egy félre, és mint lehet, hogy látható az interneten ha elkezd dugta körül a fajta, van olyan sok más is ott, néhány közülük jobb, mint mások. Valóban, bogosort egy ez a fajta szórakozás, hogy néz ki. Bogosort vesz egy sor számokat, vagy mondjuk egy pakli kártya, véletlenszerűen összekeveri őket, és ellenőrzi, hogy ők rendezve. És ha nem, nem tesz ilyet. És ha nem, nem tesz ilyet. Ha nem, akkor újra. Hihetetlenül ostoba. 

És valóban, ha olvas mint a Wikipedia cikket, a beceneve hülye sort. Ez végül a munka, remélhetőleg, elegendő idő, de, hogy mennyi időt is eltarthat egy ideig. Tehát, ha én is, hadd sebesség dolgok fel Mary Beth példa korábban, azáltal, hogy még néhány elemet, de két processzort. Két ember, ha nem bánnám csatlakozik hozzám. Mit szólnál 1 ide, és nézzük van-- nincs ott? Nincs ott? OK. Te a fekete ing, igen, gyere le. Rendben, mi a neve? 

Közönség: Peter. 

Előadó: Mi ez? 

Közönség: Peter. Előadó: Peter, David, örülök, hogy találkoztunk. Rendben, van Peter itt, ha akar jönni az asztalra itt. És mi a neved? 

Közönség: Elena. Előadó: Elena. OK, örülök, hogy találkoztunk. Elena megfelelnek Peter. Peter, Elena. És szükségünk lesz Andrew itt is, kérem. És a kihívás lesz hogy rendezni egy pakli kártya. És ha ismeretlen, fedélzet kártyák végső soron lehet válogatni egy kis valami hasonló ez, ahol mi nem a klub, akkor a pikk, majd a szív-és gyémánt, az ász, mint az egyik, egészen a király. 

A kártyák fogok adni lesznek 52 mennyiségben. Megyünk hasonlóan alkalommal, csak egy pillanat. Fogunk dobni Andrew a képernyőn itt, így nézni, mint te ezt. És így, hogy mindez annál is inkább látható, Ezek a kártyák kaptam az Amazon. Így már véletlenszerűen válogatni, és fogunk időt. És fogunk tartsa valós ebben az időben, így fogunk próbálni, hogy nyomást Ön mert különben ez lesz unalmas gyorsan. Ha lehetne folytatni rendezni 52 elemek együtt keresztül valamilyen módon, most. 

És ismét, ahogy nézni ezeket a fiúk, amit, a végén lesz, hogy készítsen egy nyilvánvaló eredmény, gondoljon tényleg hogyan ők minden csinálja, hogyan lehet leírni. Mivel ismét, ezek minden folyamat, algoritmusok hogy magától értetődőnek, mint egy ember. De akkor már valószínűleg régóta intuíció, hosszú, mielőtt még gondoltam, hogy egy számítástechnika osztály van lehetett volna az intuíció és ami a problémák megoldásában, mint ez. De ha egyszer elismerik A minták és kezdődik hogy hivatalossá a lépéseket, amelyek te megoldani ezeket a problémákat, rájössz, hogy meg lehet oldani sok érdekesebb és sokkal bonyolultabb problémák gyors. Tehát valaki a közönség, ami legalább az egyik eleme az algoritmus hogy ők a itt? 

KÖZÖNSÉG: [nem hallható] Előadó: Mi ez? Közönség: Az öltöny. Előadó: Az öltöny. Így először ezeket csoportosításával az összes gyémánt együtt úgy tűnik, mind a szív együtt úgy tűnik, és így tovább, tekintet nélkül A számokat a kártya. És most úgy tűnik, például, hogy válogatás őket szám. Nagyon jó. 

Rendben, mi fog az utolsó lépés, akkor itt? Ha már négy rendezett ruhák, milyen ezt meg kell tennie, hogy a négy cölöpök annak érdekében, hogy az egyik sorrendje fedélzet, egyszerűen? Így kell egyesíteni őket. 

Szóval van egy érdekes gondolat, hogy újra, mondhatnám, nagyon intuitív is ha talán soha nem csapott hogy ilyen címke rajta. Ez az alapvető elképzelés az osztódó a probléma nem fele ebben az időben, de legalább négy darab. Megoldása nagyon sok alapvetően azonos problémák elszigetelten egymástól, majd összevonása az eredményeket. És kiváló, kész. Rendben, egy nagy kerek A taps, ha tudnánk. 

[Taps] 

Előadó: Fogalmam sincs, hogy mit fog csinálni ezekkel, de itt van. Köszönöm szépen. Tehát lássuk, két perc és nyolc másodperc, Ha azt szeretné, hogy kihívást jelent a barátok. Mi akkor fog lehet elvenni ezt hogy mi is kihasználhatják általában? Nos, gondolj vissza Ez a tömb számát, és most visszagondolok, hogy néhány pszeudokódja is írtam korábban, és ez volt az pszeudokód a oldja meg a telefonkönyv probléma. Amelynek pszeudokód I felsorolt ​​egy módszeres módon Az, hogy miként csináltam egy nagyon intuitív emberi algoritmus felosztásának a telefon könyv fél, ismétlés, ismétlés, ismétlés, amíg nem találok valakit, mint Mike Smith, ha ő valóban a telefonkönyvben. 

De fajta használt, amit én hívom Nagyon iteratív megközelítés itt, különösen értesítés sorban 8. és 11. sor. Ezek bizonyíték ismétlődő megközelítés, a looping megközelítés, mert ez pontosan a viselkedés arra késztetik. Ezek a vonalak mind azt mondják, menj vonal három, és akkor milyen gondolom, hogy a lelki szemei ​​előtt, hogy a hurok. Azt mondja, hogy menj vissza lépéshez három és ismételje meg, újra és újra, és újra. 

De mi van, ha kihasználja a lényeg itt, hogy nem az utolsó alkalom, és egyszerűsítése sor a 8. és 11. sor és szomszédaik mivel csak ezt, a sárga. Ez alapvetően nem lerövidítése A pszeudokód nagyon sok, de ez alapvetően változik jellege én algoritmus. Amit én most azt mondja, 7. lépésben, a 10. lépésben, az, hogy keressük Mike az pontosan ugyanolyan módon, de csak a bal fél vagy a jobb felét. 

Tehát más szavakkal, ha Én lépéstől kezdve egy, vedd fel telefonkönyv, nyitott közép A telefonkönyv, nézd meg nevét, ha Smith között neve, hívja Mike, más ha Smith korábbi könyv, Hét lépés keresni Mike bal fele könyv. De ez a fajta érzés, ez így nekem lóg, nem igaz? A sárga, egy oktatás, de hogyan tudom keresni Mike a bal fele a telefonkönyv? Hol van egy algoritmus, amit lehet keresni, hogy valaki, mint Mike Smith? Nos, bámult minket az arca. Én szó szerint használhatja pontosan ugyanazt program hatékony megy fel a csúcsra újra és újra lefolytatja az azonos sornyi kódot. 

Tehát annak ellenére, hogy ezt kell éreznie mint egy kis ciklikus meghatározás ahol választ valaki kérdést csak egyfajta kérdezi ugyanazt a kérdést újra, mint, hogy miért, miért, miért? A valóság az, mert mi már keményen kódolt egy pár speciális vonalak, a 4. lépésben amely ha, és a 12. lépésben, amely gyakorlatilag egy másik ága, azért van, mert ezek a hézagpótló intézkedések, ez az algoritmus megszűnik, ha talál Mike, vagy ha nem. De a 7. lépésben és 10 most már mi hívjuk a rekurzív algoritmus. És rekurzió valóban hatalmas ötlet hogy egy kicsit elme hajlító először, hogy most már alkalmazni az alábbiak szerint. 

Merge sort lesz az utolsó sort, hogy nézzük, legalábbis az osztályban hivatalosan. És ez alapvetően különbözik a az utolsó három, és minden bizonnyal utolsó négy, ha mi is bogosort. Itt a pszeudokód a merge sort. Ha a bemeneti n elemek, így adott egy n méretű tömb, ha n értéke kisebb, mint 2, vissza. Akkor miért van, hogy józanság ellenőrizze először? Mi a következménye, ha kéznél van olyan tömb, amelynek hossza n értéke kisebb, mint 2? Ez már válogatni, nyilván, nem igaz? Mivel a lista vagy van egy elem, ami triviálisan válogatni, mert az egyetlen dolog ott. Vagy, ez a méret nulla, ami azt jelenti nincs mit rendezni, így a természet van rendezve. Már csak semmi baj ott. Szóval ez a mi úgynevezett alap eset. 

Hogy hasonló szellemben hogy mit csináltunk Mike. Ha Mike a telefonkönyvben, hívd fel. Ha nincs ott, feladja. Ez egy úgynevezett alap eset, hogy megbizonyosodjon arról, ez az algoritmus a végén a nap leáll bizonyos körülmények között. 

De itt van az ugrás a hit most más, rendezni a bal fele az elemek, majd rendezni a megfelelő fele az elemek, majd egyesíteni a válogatott felét. És itt van, ahol úgy érzi, mint mi copping ki. Kértem, hogy rendezni n elem, és én vagyok mondván: OK, azt válogatás A bal és a válogatás a jobb. De mondok egy más dolog, és ez a legfontosabb téma úgy tűnik, Az intuíció eddig, itt van ez a harmadik lépés összevonása. Ami még akkor is, úgy tűnik, hogy néma lélekben, mint éppen összeolvad dolgok együtt, úgy tűnik kulcsfontosságú lépés a összeszereléséhez két probléma, hogy a osztották végül ketté. 

Tehát merge sort, csináljuk ezt, ha lesz humor engem, még egy bemutató, csak azért, hogy van néhány számok dolgozni. Tudok cserélni nyolc stressz golyó nyolc ember? Rendben, mi lenne, ha három, akkor négy Az ebben a részben, öt, hat, és hagyja, hogy a Nem 7, 8, gyere fel. OK, igen az OK gombra. Mínusz 8, ott vagyunk, plusz 1. Kiváló. Rendben gyere fel, menjünk gyorsan kapsz számokat. A kettes, hármas, négyes, szám öt, hat, hét, illetve nyolc. Én nyolc helyesen ezúttal. 

OK, így megy előre, ha meg tudná, és nézzük rendezni az eredeti sorrendben hogy mi volt tegnap, amely úgy nézett mint ez, ha nem bánja. És tegyük elé az asztalra. Rendben, merge sort. Ez az, ahol ez lesz hogy milyen érdekes, mert úgy tűnik, hogy így magam így sokkal kevesebb információ ma. 

Így egyesíteni fajta először input n elemek, és nyilvánvalóan nem kevesebb, mint két, ez nyolc, így még egy kis munka. Tehát most mentálisan is, mint egy osztály most a más ág, ami azt jelenti, három lépésből áll. Először is, meg kell rendezni a bal fele az elemek. Szóval, hogyan kezdjen csinálja ezt? Nos, én megyek, hogy milyen szellemileg osztani a listát itt, nem kell fizikailag mozog, és én vagyok majd, hogy csak a bal felén az elemek itt. Szóval, hogyan megy a válogatás A lista most már a méret négy? Mi az én algoritmus? Először ellenőrizd, n kevesebb, mint két, nem, így folytassa a más blokk újra. Fajta bal fele elemekkel. 

Így most újra, szellemileg, és ez az, ahol meg kell felhalmozni sok szellemi történelem, ha úgy tetszik. Most válogatás a bal fele a bal felét. Rendben, most hívom ugyanaz merge rendezési algoritmus, n kevesebb, mint két? Nem, ez két, úgyhogy meg kell rendezni a bal oldalán, és a jobb fele. Szóval itt vagyunk, rendezni a bal felét. Miért nem csak tegyél egy lépést előre. Mi a neve? 

Közönség: Darren. 

Előadó: Dan. Dan előrelépett. 

Közönség: Darren. Előadó: Darren, kész. Azt mondta, Darren vagy Dan? 

Közönség: Darren. 

Előadó: Darren. OK, Darren fokozta előre, és ő most rendezve. És ez majdnem egy ostoba állítás, igaz? Én nem igazán úgy tűnik, hogy eléréséhez semmit, de nézzük tovább. Most hadd rendezni a megfelelő fele az elemekkel. Mi a neve? 

Közönség: Luke. 

Előadó: Luke. Gyerünk, lépjen előre. Kész, már rendezve Luke. A bal fele most válogatni és a jobb fele ma már rendezett, de a lényeg, van egy kulcsfontosságú lépés itt. Mit mellett kell tennem? Egyesíti a válogatott felét. Most fogunk csak meg mindenki oda-vissza ezen a módon, mert a fajta kell néhány karcolás helyet. Ez majdnem olyan, mint ezek a srácok az asztalra, és szükségem van egy kis szoba mozgatni őket körül. Úgyhogy egyesíteni srácok a keresett A bal oldalán és a jobb fele. És aki nyilvánvalóan az első, balra félig vagy jobb felét? Tehát jobb oldalán, tehát menjünk Luke át ide Darren eredeti helyzetébe. És most, hogy egyesítik a bal fele a, Darren fog mozogni ott. 

Tehát úgy érzi, szinte a buborék sort hatás de én alapvető algoritmus, nagyon más ebben az időben. De most, ahol a dolgok egy kicsit bosszantó, mert kell visszaforgatni mentálisan Hol hagytam ki. Épp most összevonták a rendezett felét, ami azt jelenti, ott vagyok, ahol az én algoritmus? Meg kell rendezni a jobb fél, ugye? 

Ha visszalép, a szó szoros értelmében A videó, akkor látni, hogy mi van, hogy ezt a pont Luke és Darren válogatás a bal fele a bal felét. Aztán egyesült azokat rendezett felét, ami azt jelenti, a következő lépés a sort a jobb felét a bal felét. Rendben, szóval Ehhez gyorsabban. Rendben, hat, megyek igényt Ön most válogatni, gyerünk előre. Mi a neve? 

Közönség: Adriano. 

Előadó: Adriano. Adriano most rendezve. És mi a neved? 

Közönség: Alex. 

Előadó: Alex most rendezve. Bal fele, jobb felét, mi a végső lépés? Egyesítése. Elég triviális, úgyhogy majd összevonni hat, egy lépést hátra, nyolc, egy lépést hátra. És most észre ezt hasznos elvihető, milyen most igaz a bal fele a listáját, függetlenül attól, hogy mi kezdődött? Ez van rendezve. 

Most már nem rendezve A nagy dolgok rendjében, de van rendezve függetlenül a másik felét. Most mi lépés vagyok az, ha én is visszacsévélés, hogy a történet kezdődött? Most kell rendezni a jobb felét. Így most már vissza a az elején a történetet, és csináljuk gyorsabban. Így fogok rendezni a jobb fele a teljes lista. Mi a következő lépés? Rendezni a bal fele a jobb felét. Rendezni a bal fele a bal fele a jobb felét. És mi a neved? 

Közönség: Omar. 

Előadó: Omar, lépjen előre, kész. Bal fele van rendezve. És mi a neved? 

Közönség: Chris. 

Előadó: Chris, egy lépést előre, akkor most rendezve. Mi az a legfontosabb lépés most? Egyesítése. Tehát az egyik fog egyesíteni a helyére Itt, ha lehetne egy lépést hátra, és három fog egy lépést hátra, összeolvad. Tehát a bal fele a jobb oldalán, most rendezve. Őszintén szólva, ez az algoritmus olyan, mint mi pazarolsz így több időt, mint korábban, de ha nem ez a valós időben, akkor mi az elvitelre lesz. Most itt vagyok, jobb fele a jobb felét, hadd menjen előre, és rendezni a bal felét. Lépjen előre, mi a neve? Közönség: Ramsey. Előadó: Ramsey most rendezve. Mi a neve? 

Közönség: Marina. 

Előadó: Marina most sorrendje a Nos, ha veszel egy lépést előre. Kulcsfontosságú lépés itt most összeolvad, vagyok majd összeszedi az én két listát, balra és jobbra. Öt fog jönni az első, és hét fog jönni legközelebb. És ismét, ez szándékos. Az a tény, hogy ők figyelembe lépést előre és vissza célja, hogy képviselje, hogy nem tudjuk Ehhez algoritmus helyen könnyen A buborék rendezés, és a kiválasztás sort, és beillesztés sort, ahol csak tartotta csere emberek. Szó szerint kell egyfajta A semmiből papírt, amelyben , hogy ezek az emberek míg én az egyesülő, és akkor én is őket vissza a helyére. És ez kulcsfontosságú, mert én egy új forrás, hely, nem csak időt. 

OK, ez fantasztikus. Bal fele van rendezve, jobb fele rendezett, most, hogy kulcs összevonása lépés. Hogyan fogom egyesíteni ezt? Tehát, ha lesz követni a bal és jobb kéz, Fogom mutatni a bal oldali a bal fele, a jobb kezem a jobb oldalán, és most azt kell dönt lépésről lépésre akit összevonni. Aki nyilvánvalóan előbb? Számú. Szóval gyerünk ide, itt van a jegyzettömb. Így most első számú, és a közlemény mit fogok csinálni a jobb kezemmel, Fogom mozgatni a jobb kezét egy átlépni pont száma három, és most már, hogy a ugyanazt a döntést. És valóban áll közvetlenül előtt Luke ide, ha lehetne, mert ez a mi jegyzettömb. Szóval, ki lesz a következő? Van Luke a kettes számú vagy Chris a hármas szám. Nyilvánvaló Luke, szám két, így jön ide. 

De a bal kezem most fog növekedhet, hogy rámutasson Darren, és itt van a kulcs, hogy el összevonása, fogom tartani ezt, Nyilvánvaló, hogy ha kedves a logikáját követik. De a kezem soha megyek vissza, ami azt jelenti, hogy én mindig csak költözik A bal oldali az én összefonódó folyamat, és ez lesz a kulcs elemzés csak egy pillanat. 

Tehát most fejezzük be ezt fel gyorsan. Tehát három következik, majd négy következik, és most öt következik, akkor hat, és hét, és végül nyolc. Olyan, mint a leglassabb algoritmus még, de akkor nem, ha tényleg futtatni ugyanazon fajta Az órajel, így a beszél, az azonos óra ketyeg, mint korábban. Miért? Nos, hogy egy nézd meg a végeredmény. 

Menjünk vissza ide, hadd húzza fel a bemutató vizuálisan Az, amit most csináltunk. Nagyítás itt, ezen oldalon van, és azt mondta a Firefox hogy azt akarjuk, hogy sorban fel ebben a dobozban, nézzük mondjuk buborék sort, amellyel mi most jól ismert, kiválasztás sort, amely egy másik meglehetősen egyszerű egy, és most a mai merge sort, amely lesz a klimatikus véget. Az ok tartott ilyen sokáig itt az emberek, és én szóban is, Nyilvánvaló, hogy én elmagyarázza minden lépésnél. De ha ki ezt a sok mint mi buborék sort és kiválasztás fajta nem csak vizuálisan, óra hogy mennyi hatékonyabban ez kiegyenlítését megosztottság és hódító lehet alkalmazni egy adathalmaz, ami sem méret nyolc, de még sok, sokkal nagyobb. Adok egyesíteni sort, egymás oldalán az egyéb algoritmusok. Ez fog kapni fájdalmas gyorsan, és a vége nem különösebben éghajlati, ők csak a végén rendezve. De a legfontosabb, hogy el, hogy Nézd, milyen sokkal gyorsabb merge sort volt, kivéve, ha azt hiszed, csak egyfajta szórakozik veled. Ha ezt egy utolsó alkalommal, Nézzük reload ezt, menjünk vissza , és válassza a buborék sort, és csak a hecc kedvéért, hadd válassza beillesztés sort, csak a jó intézkedés. És újra, nézzük választani merge sort és nézzük valójában futtatni ezeket egymás mellett. 

És ez nem, sőt, a véletlen. Amit gyakorlatilag kész van én már osztva a bemenet félbe, megint, és újra, és újra. És csak annyi alkalommal lehet ossza meg bevinni fele, bal és jobb. Mi az a formula, amit folyamatosan látják hogy leírja a hadosztály fele újra, és újra, és újra, és újra? 

Közönség: log n. 

Előadó: log n. De akkor van egy másik fontos lépés, Ez az algoritmus nem log n. Ha csak log n, mi lenne ugyanaz a probléma mint korábban, ahol nem lehet Biztos minden rendben rendezve. Meg kell minimálisan nézni n eleme hogy biztos, n elemek sorrendje, egyébként ez egy ugrás a hit. 

Szóval ez minimálisan log n lépést, de Mi van ezzel a kulcs összevonása lépés ahol egyesült a bal felét és a jobb fél és átsétált a színpadon? Hány lépés az, hogy egyesíteni? Ez n, de én nem csak egyesíti a végső idő. Minden ilyen beágyazott hívások, minden azok beágyazott egyesítés, én még mindig rendezve. Én egyesült a két fickó, akkor ez a két srácok, akkor ez a két fickó, és így tovább. 

Úgyhogy összevonása újra, és újra. Hányszor? Így minden alkalommal, amikor megosztotta a lista félbe, csináltam egy merge. Osszuk a listát fél, nem a merge. Tehát, ha elosztjuk a lista lehet tenni log n-szer, és az egyesülő végül vesz n lépések, mi lehet most a felső kötött a futó idő a mi algoritmus? n log n. 

És valóban, ez az, ami értünk el itt. Így az érzést, amit látsz vizuálisan amikor a három dolog fut egymás mellett n négyzetes ellen n kockás ellen n log n. Amely alapvetően majd meglátjuk, nem csak ma, hanem a jövőben, sokkal, de sokkal gyorsabb. A tapsot ezek a srácok, Én megjutalmazza őket stressz labda. Hadd vonuljon ma, és majd meglátjuk, hogy hétfőn.