[Zenelejátszási] 

Tanár: Rendben. Ez CS50 és ez hét végéig három. Tehát itt vagyunk ma, és nem a Sanders Színház, hanem a Weidner Könyvtár. Amelynek belsejében egy stúdió néven Hauser Studio, vagy mondjuk Studio H, vagy meg kell mi say-- ha tetszett, hogy vicc, ez valójában a osztálytársa, Mark, az interneten, aki azt javasolta, amennyire a Twitteren keresztül. Most mi erről hűvös hogy itt egy stúdióban hogy én vagyok körülvéve E zöld falak, egy zöld képernyő vagy chromakey, hogy úgy mondjam, ami azt jelenti, hogy a CS50 produkciós csapat, ismeretlenül nekem Most, lehet üzembe engem leginkább a világ bármely pontján, jobb vagy rosszabb. 

Most mi vár ránk, a probléma beállítva Két az ön kezében van erre a hétre, de a probléma beállítva Három a jövő héten, akkor lehet megtámadni a az úgynevezett játék 15, Egy régi fél javára, hogy talán felidézni részesülő mint a gyermek, hogy van egy csomó A számok, hogy lehet csúszni lefelé, felfelé, balra és jobbra, és van egy rés a puzzle, amelybe valóban csúszik ezeket puzzle-darabokat. Végül is megkapja ezt puzzle néhány félig véletlenszerű sorrendben, és a cél az, hogy szortírozni, fentről lefelé, balról jobbra, egyik egészen a 15. 

Sajnos, a végrehajtás akkor kéznél lesz szoftverek alapuló, nem fizikailag. Te tényleg kell majd írni kódot, amellyel a tanuló vagy felhasználó A játék 15. És valóban, a hekker kiadás játék 15, akkor lesz egy kihívás, hogy hajtsák végre, Nem csak a játék ennek a régi iskola játék, hanem a megoldási belőle, végrehajtási isten mód, hogy úgy mondjam, hogy ténylegesen megoldja a puzzle az emberi, biztosítva számukra a célzást, után hint után hint. Így még az, hogy a jövő héten. De ez mi vár ránk. 

Most emlékeztetnek arra, hogy a hét elején mi volt ez a filmsorozat, ha úgy tetszik, ahol a legjobb csinálunk válogatás bölcs volt, egy felső korlát a nagy o n négyzeten. Más szóval, a buborék rendezés, kiválasztási sorrend, beillesztés sort, mindegyiket, míg a különböző a végrehajtásban, decentralizált egy n futó faragva ideje a legrosszabb esetben. És általában azt feltételezik, hogy A legrosszabb esetben a válogató az egyik, hogy a bemenetek teljesen hátra. És valóban, ez volt jó néhány lépést hogy végre minden egyes ilyen algoritmusok. 

Most a legvégén osztály Emlékezzünk, összehasonlítottuk buborékos rendezést elleni szelekció egyfajta ellen egy másik hogy hívják merge sort abban az időben, és azt javaslom, hogy túl sok időt vesz Használja ki a leckét a héten nulla, Oszd meg és uralkodj. És valahogy eléréséhez valamiféle logaritmikus futási idő végső soron, valami helyett ez tisztán másodfokú. És ez nem elég logaritmikus, ez egy kicsit több annál. De ha visszahívja osztály, ez sokkal, sokkal gyorsabb. Vessünk egy pillantást, ahol abbahagytuk. 

Bubble sort versus kiválasztása Rendezés versus merge sort. Most meg az összes futó, a elmélet, ugyanabban az időben. A CPU fut azonos sebességgel. De akkor érezni, milyen unalmas ez a nagyon gyorsan fog válni, és milyen gyorsan, amikor injekciót egy kicsit a heti nulla algoritmusok, lehet felpörgetni a dolgokat. 

Tehát védjegy a fajta néz ki, csodálatos. Hogyan tudjuk kiterjesszük, annak érdekében, a számok sorrendje gyorsabban. Hát lássuk csak vissza hogy egy összetevő, hogy mi volt vissza héten nulla, hogy a keres valaki egy telefonkönyv, és emlékszem, hogy a pszeudokódja hogy mi javasolt, amelyen keresztül találunk valaki, mint Mike Smith, nézett egy kicsit valami ilyesmi. 

Most vessünk egy pillantást különösen sorban a 7. és a 8., és a 10. és 11., indukáló, hogy hurok, amely által tartott megy vissza a 3. sorban újra, és újra, és megint. De kiderül, hogy mi lehet megtekinteni Az algoritmus, itt pszeudokódja, egy kicsit több holisztikusan. Tény, hogy mit keresek meg itt a képernyőn, egy algoritmus keresésére Mike Smith között néhány sor oldalakon. És valóban, mi is leegyszerűsítik ezt algoritmus ezeket a sorokat a 7. és 8., 10 és 11, hogy csak ezt mondom, amit már itt bemutatott sárga. Más szavakkal, ha Mike Smith korábban a könyvet, nem kell megadni lépésben lépésre most hogyan megy találni. Nem kell megadni hogy menjen vissza a 3. sorban, Miért nem csak ahelyett, mondjuk, általánosabban, keresni Mike a bal fele a könyv. 

Ezzel szemben, ha Mike igazából később a könyvben, miért nem csak idézni idézet vége keresés Mike a jobb fele a könyv. Más szóval, miért nem megyünk fajta punt magunkat, mondván, keresni Mike ezen részhalmaza a könyv, és hagyja, hogy a már meglévő algoritmust, hogy elmondja nekünk hogyan kell keresni Mike hogy bal fele a könyv. Más szavakkal, a mi algoritmus dolgozik, hogy ez telefonkönyv ennek vastagsága, ennek vastagsága, vagy bármilyen vastagságú nélkül. Így tudjuk rekurzív határozzák meg ezt az algoritmust. Más szavakkal, a képernyőn van, egy algoritmus keresésére Mike Smith között az oldalak egy telefonkönyv. Tehát a sorban a 7 és 10, nézzük csak annyit, hogy pontosan. És én ezt a kifejezést egy pillanatra ezelőtt, és valóban, rekurzió a szlogen most, és ez ebben a folyamatban csinál valamit ciklikus által valahogy kóddal, hogy már van, és hív meg újra, és újra, és újra. Most lesz fontos hogy valahogy alján ki, és nem csinál ilyet végtelenül hosszú. Ellenkező megyünk valóban van egy végtelen ciklus. De lássuk, mi lehet kölcsönözni ezt az elképzelést A rekurzív, hogy valami újra és újra és újra, hogy megoldja A válogatás probléma keresztül merge rendezés, mind a hatékonyabb. 

Szóval adok neked merge sort. Vessünk egy pillantást. Tehát itt van pszeudokódja, a amely tudtuk megvalósítani rendezési, ezt az algoritmust nevű egyesítési sort. És ez egészen egyszerűen ez. Input n elem, más szóval, ha Adott n elem és számok levelek, vagy bármi a bemenet, ha adott n elem, ha n értéke kisebb, mint 2, csak vissza. Jobb? Mert ha n értéke kisebb, mint 2, hogy azt jelenti, hogy én elemek listája jelentése vagy a mérete 0 vagy 1, és mindkét ilyen triviális esetekben A lista már válogatni. Ha nincs lista, ez válogatni. És ha van egy lista hosszát 1, ez nyilván válogatni. Tehát az algoritmus csak arra, hogy tényleg valami érdekeset, ha van két vagy több, elemek adott nekünk. Szóval nézzük meg a mágikus majd. Else rendezni a bal fele az elemek, majd rendezni a jobb fele elemek, majd egyesíti a rendezve félidőt. És mi van egyfajta elme hajlító Itt, az, hogy én nem igazán Úgy tűnik, hogy megmondtam semmit csak még, ugye? Minden, amit mondtam az, kap egy listát n elem, rendezheti a bal fele, majd a jobb oldalát, majd egyesíti a rendezve félidőt, de hol van a tényleges titkos szósz? Hol van az algoritmus? Kiderült, hogy a két vonal első, egyfajta bal fele elemek, és egyfajta jobb fele elemek, rekurzívak hívások, hogy úgy mondjam. 

Végtére is, ebben a időpontban, tudom már, egy algoritmust, amellyel rendezni egy csomó elemek? Igen. Itt van. Itt van a képernyőn, és így tudom használni, hogy ugyanazokat a lépéseket rendezni a bal fele, amennyit csak tudok jobb felét. És valóban, újra, és újra. Szóval valahogy, és ha hamarosan látni ezt a varázslatos merge sort van ágyazva, hogy nagyon végső vonal, összevonása a rendezett félidőt. És úgy tűnik, meglehetősen intuitív. Veszel két felét, és akkor, valahogy egyesíteni őket együtt, és majd meglátjuk, ez konkrétan egy pillanat. 

De ez egy teljes algoritmus. És lássuk, pontosan miért. Hát tegyük fel, hogy mi mivel ugyanezek nyolc elem van a képernyőn, az egyik a nyolc, de ők A látszólag véletlenszerű sorrendben. És a cél kéznél van rendezni ezeket az elemeket. Hát hogy is megy a csinálja segítségével ismét merge sort, mint egy ennek pszeudokódja? És ismét, ingrain ezt fejedben, csak egy pillanatra. Az első esetben elég triviális, ha ez kevesebb, mint 2, csak vissza, nincs tennivaló. Szóval tényleg ott van csak három lépéseket, hogy valóban szem előtt tartani. Újra, és újra, én vagyok szeretne majd meg rendezni a bal fele, rendezni a jobb fele, majd miután azok két félből vannak sorolva, Azt szeretné egyesíteni őket együtt egyetlen rendezett listát. Tehát hogy tartsa szem előtt. 

Tehát itt az eredeti listán. Nézzük kezelni ezt, mint egy tömb, ahogy kezdett héten két, ami egy összefüggő blokk memória. Ebben az esetben, amely nyolc szám, vissza háttal. És nézzük most alkalmazni merge sort. Tehát először szeretnék rendezni A bal fele ezt a listát, és nézzük tehát, összpontosítani 4, 8, 6 és 2. 

Most hogyan megy körülbelül válogató listáját 4-es méretű? Hát azt kell most úgy válogatás a bal oldalon a bal fele. Ismét nézzük a visszatekerés csak egy pillanatra. Ha a pszeudokódja ez, és én adott nyolc elem, 8 nyilvánvalóan nagyobb mint vagy egyenlő 2. Tehát az első esetben nem alkalmazható. Tehát rendezni nyolc elem, először rendezni a bal fele elemek, aztán rendezni a jobb oldalát, majd Egyesíthetem A két sorba rendezett felét, mindegyik 4-es méretű. OKÉ. 

De ha már csak azt mondta nekem, rendezni a bal fele, amely most a 4-es méretű, hogyan tudom oldani a bal fele? Nos, ha van egy bemeneti négy elem, Én először rendezni a bal két, majd a jobb oldali két, és aztán egyesíteni őket együtt. Tehát újra, ez lesz egy kicsit Egy elme hajlító játék itt, mert, fajta, meg kell emlékszem, hogy hol van a történet, de a végén a nap, adott semmilyen elemek száma, először szeretné rendezni a bal felét, majd a jobb oldalát, majd egyesíti őket. Kezdjük pontosan erre. Itt a bemeneti nyolc elem. Most éppen a bal fele itt. Hogyan rendezni a négy elem? Hát először rendezni a bal fele. Most hogyan tudom oldani a bal fele? Nos Kaptam két elem. Úgyhogy rendezni ezt a két elemet. 2-nél nagyobb vagy egyenlő 2, természetesen. Úgy, hogy az első esetben nem alkalmazható. 

Szóval most már rendezni a bal a fele a két elemet. A bal fele, persze, csak 4. Szóval hogyan tudom rendezni a lista egy elemét? Nos, hogy a különleges alapeset fel tetején, hogy úgy mondjam, vonatkozik. 1 kevesebb, mint 2, és az én lista valóban az 1-es méret. Szóval csak vissza. Én nem csináltam semmit. És valóban, nézd meg amit én kész, 4 már válogatni. Mint én már részben sikeres itt. 

Most, hogy úgy tűnik, elég hülyén igényelni, de igaz. 4 van egy lista a 1-es méretű. Ez már válogatni. Ez a bal felét. Most rendezni a jobb fele. Én bemenet egyik eleme, 8 Hasonlóképpen, már válogatni. Hülye is, de a lényeg, Ezen alapelv fog engedje meg, hogy most építenek Ezen felül sikerrel. 4 válogatni, 8 rendezve, most Mi volt az utolsó lépés? Tehát a harmadik és utolsó lépés, bármilyen alkalommal, amikor válogatás egy listát, visszahívás volt, hogy összevonja a két felét, a bal és a jobb oldalon. Tehát lássuk, hogy pontosan. A bal fele, természetesen, 4. A jobb fele 8. 

Tehát lássuk ezt. Először fogok kiosztani Néhány további memória, hogy én képviselek, mint csak egy másodlagos tömb, de nagy ahhoz, hogy elférjen ebben. De el lehet képzelni meghosszabbításáról E négyszögben a teljes hosszában, ha több kell majd. Hogyan szedjem 4 és 8, és egyesíti E listáknak a mérete 1 együtt? Itt is elég egyszerű. 4. előbb, aztán jön 8. Mert ha azt akarom, hogy rendezze a bal felét, majd a jobb oldalát, majd egyesíteni a két félből együtt, rendezett sorrendben, 4. előbb, aztán jön 8. 

Tehát úgy tűnik, hogy előrelépéseket tett, sőt bár én még nem történt semmilyen tényleges munkát. De ne felejtsd el, hogy hol vagyunk a történetben. Eredetileg vett nyolc elem. Mi válogatni a bal fele, amely 4. Aztán válogatni a bal fele A bal fele, amely 2. És itt vagyunk. Végeztünk ezt a lépést. 

Tehát, ha egy rendezést a bal fele 2, most kell rendezni a jobb fele 2. Így a jobb fele 2 E két érték itt, a 6. és a 2. Úgyhogy most felvesznek egy bemeneti méret 2, és a sort a bal fele, majd a jobb oldalán, majd egyesíti őket. Hát hogyan tudom rendezni egy listát a méretet 1, amely csak a 6-os szám? Én már megtette. Ezt a listát az 1-es méret van rendezve. 

Hogyan rendezni egy másik listát 1-es méret, az úgynevezett jobb felét. Hát ez is, már válogatni. A 2-es szám van egyedül. Így most már két fele, a bal és Rendben, azt kell egyesíteni őket együtt. Hadd hozzak magamnak egy kis szabad hely. És tedd 2 oda, majd 6 odabent, ezáltal válogatás a listán, jobbra és balra, és összefonódó össze, végső soron. Szóval én valamivel jobb állapotban van. Még nem végeztem, mert egyértelműen 4, 8, 2, 6 nem a végleges rendezés, amit akar. De most már két lista 2. méretű, hogy egyaránt, illetve rendezve. Tehát most, ha visszalép az agyad szem, hol, hogy el minket? Elkezdtem a nyolc elem, akkor én szűkítették le, hogy a bal fele 4, majd a bal fele a 2, és majd a jobb fele a 2, Befejeztem, ezért a válogatás a bal fele 2, és a jobb fele a 2, akkor mi a harmadik és egyben utolsó lépés itt? Meg kell egybeolvadnak két lista 2. méretű. Szóval menjünk előre. És a képernyőn van, így nekem néhány további memória, bár alakilag észre, hogy én már Van egy csomó üres hely akár felső ott. Ha azt akarom, hogy különösen hatékony tér bölcs, Tudtam csak elindulni az elemek oda-vissza, alul és felül. De csak a vizuális tisztaságért, Megyek, hogy tegye le az alábbiakban, hogy a dolgok szép és tiszta. 

Így kaptam két lista 2. méretű. Az első lista a 4 és 8. A második lista 2 és 6. Nézzük összevonjátok együtt rendezett sorrendben. 2, természetesen, az első, majd 4, majd 6, majd 8. És most úgy tűnik, hogy egyre egy érdekes helyen. Most már válogatni fele listára, és véletlenül, ez az összes páros számot, de hogy Valóban, csak véletlen egybeesés. És most már rendezni a bal fele, úgy, hogy ez a 2., 4., 6., és 8.. Semmi sem elromlott. Hogy érzi magát, mint haladást. 

Most úgy érzem, mintha volna Beszéltem örökre most, akkor mi még a jövő zenéje, ha ezt algoritmus, sőt, hatékonyabb. De megyünk keresztül szuper módszeresen. Egy számítógép, természetesen, megtenném, mint ezt. Szóval hol vagyunk? Azzal kezdtük, hogy nyolc elem. Én válogatni a bal fele 4. Úgy látszik, hogy készen van. Tehát most a következő lépés az, hogy rendezni a jobb fele a 4. És ez a rész mehetünk keresztül egy kicsit több, Gyorsan, bár te Üdvözöljük vissza- vagy szüneteltetheti, csak végiggondolni azt a saját tempójában, de mi mi most egy lehetőség, hogy nem pontosan ugyanazt az algoritmust négy különböző számokat. 

Szóval menjünk előre, és figyelembe véve a a jobb oldalát, ami itt vagyunk. A bal felét jobb fele, és most a bal fele a bal oldali fele a jobb felét, és hogyan rendezheti a listát mérete 1, amely csak az 1. számú? Ez már megtörtént. Hogyan csináljam ugyanezt a listát Az 1-es méret, amely mindössze 7? Ez már megtörtént. Harmadik lépés erre a felét, majd van, hogy egyesítsék e két elem egy új listát a mérete 2, 1 és 7. Nem úgy tűnik, hogy mindent megtettünk hogy sok érdekes munka. Lássuk, mi történik ezután. Én csak válogatni a bal fele jobb fele az eredeti input. Most rendezni a jobb fele, amely 5 és 3. Nézzük újra nézd meg a bal fele, válogatni, jobb fele, válogatni, és egyesíti a két együttes, a néhány további hely, 3 jön először, aztán jön 5. És így most, már válogatni a bal fele a jobb fele az eredeti probléma, és A jobb felét a jobb fél Az eredeti probléma. Mi a harmadik és egyben utolsó lépés? Nos, hogy összevonja a két fél együtt. Szóval hadd tegyem magam néhány extra helyet foglalnak el, de én Lehet használni, hogy tartalék helyre fel tetején. De mi akarsz tartani egyszerű szemrevételezéssel. Hadd úsznak most 1, és majd 3, majd az 5, majd 7. Hagyva nekem most a jobb fele az eredeti probléma Ez tökéletesen rendezett. 

Tehát mi marad? Úgy érzem, mondogatom a Ugyanazokat a dolgokat újra, és újra, de ez tükrözi a Tény, hogy mi használ rekurzió. A folyamat, amelynek során egy algoritmus újra, és újra, A kisebb részhalmaza Az eredeti probléma. Szóval most már egy bal rendezve a fele az eredeti probléma. Jogom van a rendezett fele Az eredeti probléma. Mi a harmadik és egyben utolsó lépés? Ó, ez összevonása. Tehát lássuk, hogy. Nézzük kiosztani néhány további memória, de istenem, mi sodorhatják bárhol őt. Van annyi hely áll rendelkezésre nekünk, de mi legyen egyszerű. Ahelyett, hogy oda-vissza oda a mi eredeti memória, nézzük csak csináld Akadálymentes ide alább, befejezni összevonásával bal fele és a jobb fele. 

Szóval összevonásával, mit kell tennem? Azt akarom, hogy az elemek érdekében. Így nézett a bal fele, Látom az első szám a 2. Nézem a jobb fele, Látom az első szám 1, így nyilván, amelyek számú akarom tépni ki, és tedd az első az én végleges listát? Természetesen, 1. Most azt szeretném megkérdezni, hogy ugyanezt a kérdést. A bal fele, már Még mindig megvan a 2-es szám. A jobb felét, Megvan a 3-as szám. Melyiket szeretné választani? Természetesen, a 2 és Most észre a jelöltek 4 a bal oldalon, a 3. a jobb oldalon. Nézzük, persze, válassza ki a 3. Most a jelöltek 4. a bal, 5 a jobb oldalon. Mi, persze, válassza a 4. 6 bal, 5 a jobb oldalon. Mi, persze, válassza 5. 6 a bal oldalon, a 7. a jobb oldalon. Úgy döntünk, 6, és aztán válassza a 7, majd úgy döntünk, 8. Voila. 

Szóval rengeteg szó később, csoportosítottad ezt a listát a nyolc elem egy listát egytől nyolc, ami növeli minden egyes lépésnél, De vajon mennyi idő volt ez visz minket erre. Hát én már szándékosan eljárással készült dolgokat képileg Itt, hogy mi lehet a fajta látja, vagy értékelik a divízió A hódító, ami történt. 

Sőt, ha visszatekintünk a nyomában, Hagytam az összes ilyen szaggatott vonalak A távtartók, akkor, fajta, lásd, fordított sorrendben, ha a fajta néz vissza történelem most, az eredeti lista Természetesen, a 8-as méret. És akkor a korábban voltam, foglalkozó két listáját 4-es méretű, majd négy lista 2-es méret, majd nyolc listák 1-es méret. 

Mit is jelent ez, fajta, emlékeztessem önöket? Nos, valóban, bármely Az algoritmusok voltunk nézett eddig, ahol szakadék, és oszd meg, és oszd meg, tartani, amelynek a dolgokat újra, és ismét eredményezi ezt a közvélekedést. És így van valami logaritmikus folyik itt. És ez nem elég log n, de van egy logaritmikus alkatrész hogy amit az imént történt. 

Most nézzük meg, hogyan, hogy valójában. Szóval jelentkezzen n, ismét volt nagy működési idő, amikor nem valami ilyesmi bináris keresés, ahogy manapság nevezik, Az oszd meg és uralkodj stratégia amelyen keresztül megtaláltuk Mike Smith. Most technikailag. Ez log alap 2 n, akkor is, Bár a legtöbb matematikai osztályok, 10 Általában a bázis, amit vállal. De számítógépes szakemberek szinte mindig gondolkodni és beszélni szempontjából alap 2, tehát általában csak annyit naplót N, ahelyett, log bázis 2 N, de ők pontosan egy és ugyanazt a világon a számítógépes a tudomány, és mint félre, Van egy állandó tényező különbség a kettő között, így ez vitathatónak egyébként, több formai okok miatt. 

De most, mi érdekel körülbelül ez a példa. Szóval nem tudja bizonyítani a példa, de a legalább használja egy példa a számok kéznél van, hiszen a józan csekket, ha úgy tetszik. Így a korábban a képlet volt, napló adatbázis 2 n, de mi n ebben az esetben. Volt n eredeti számokat, illetve 8 Az eredeti szám konkrétan. Most már egy kicsit míg, de nem vagyok elég arról, hogy log 2 alap Az érték 8 jelentése 3, sőt, mi szép erről van hogy a 3 pontosan az a szám, ahányszor hogy lehet osztani egy listát A hossza 8 újra, és újra, és újra, amíg te maradt A listák csak 1-es méret. Jobb? 8 megy 4, megy a 2, megy 1, és ez tükrözi pontosan, hogy kép volt, csak egy pillanattal ezelőtt. Szóval egy kis józanság ellenőrizze, hogy hol A logaritmus valójában szó. 

Tehát most, mi más van itt szó? n. Tehát észre, hogy minden Mire szét a listán, bár fordított sorrendben a történelemben Itt voltam, mindig csinál n dolgokat. Beolvadása a lépés szükséges, hogy Én miden egyik szám, annak érdekében, hogy tolja azt a a megfelelő helyre. Így bár a magassága ezen rajz mérete log n n vagy 3, Konkrétabban, más szóval, Én három hadosztály itt. Mennyi munkát csináltam vízszintesen végig ezt a táblázatot minden egyes alkalommal? 

Nos, én n lépései dolgozni, mert ha én már Van négy elem és a négy elemet, és azt kell egyesíteni őket együtt. Azt kell átmenni E négy és ez a négy, végül egyesíteni őket vissza nyolc elem. Ha fordítva Megvan a nyolc ujját mint itt, amit nem, és nyolc fingers-- sorry--, ha már Van négy ujj ide, amit teszek, négy ujj mint itt, amit csinál, akkor ez ugyanaz Például, mint korábban, ha megteszem nyolc ujját bár teljes, amit tud, egyfajta tegye. Én is pontosan itt, akkor én is biztosan egyesíti az összes ilyen listák Az 1-es méretű össze. De természetesen meg kell nézni minden eleme pontosan egyszer. Tehát a magassága ez a folyamat log n, a szélessége e folyamat, hogy úgy mondjuk, n, akkor mi úgy tűnik, hogy végső soron az, futásidejű méretű n-szer log n. 

Más szavakkal, mi osztva A lista log n-szer, de minden egyes alkalommal tettük, hogy mi volt hogy miden egyik eleme annak érdekében, hogy egyesíti őket minden együtt, ami az n lépés, így már n-szer log n, vagy mint egy számítógép tudós azt mondaná, aszimptotikusan, amely lenne a nagy szó leírni a felső köti a működési idő, mi fut egy nagy o log n idő, hogy úgy mondjam. 

Most ez jelentős, mert felidézni, amit a futási idők voltak buborék rendezés, és a kiválasztás rendezése és beillesztés sort, és még néhány más, hogy létezik, n faragva volt, ahol voltunk. És tudod, milyen, nézd meg ezt itt. Ha n faragva nyilvánvalóan n-szer n, de itt van n-szer log n, és már tudjuk hétről zero, log n, a logaritmikus, jobb, mint valami lineáris. Végtére is, emlékszem a kép A piros és a sárga és a zöld vonalak felhívtuk a zöld logaritmikus vonal sokkal alacsonyabb volt. És ezért sokkal jobban és gyorsabban mint az egyenes sárga és piros vonalak, n-szer log n is, sőt, jobb, mint n-szer n vagy N négyzeten. 

Tehát úgy tűnik, hogy azonosított egy algoritmus merge Rendezés futó sokat gyorsabb, és valóban, ezért, a hét elején, amikor láttuk, hogy verseny között buborék rendezés, kiválasztás sort, és egyesíti rendezés, merge sort nagyon, nagyon megnyerte. És valóban, mi sem várta A buborékos rendezést és kiválasztási sorrend befejezni. 

Most vessünk egy másik menetben ezen, egy valamivel több Formális szempontból, csak a esetben ez rezonál jobban mint hogy a magasabb szintű vitát. Tehát itt az algoritmus újra. Kérdezzük magunkat, amit a futási idő az ezen algoritmusok különböző lépések? Nézzük osszuk az első ügy és a második esetben. A BA és a máshol a HA esetben, Ha n kevesebb, mint 2, csak vissza. Olyan, mint a folyamatos időt. Ez, a fajta, mint a két lépést, Ha n kevesebb, mint 2, majd vissza. De ahogy mondta hétfőn, konstans időben, vagy nagy o 1, lehet két lépésben, három lépéseket, még 1000 lépéseket. A fontos az, hogy ez az konstans számú lépést. Tehát a sárga kiemelt pszeudokódja Itt fut, hívjuk meg, konstans időt. Tehát formálisan, és megyünk az alábbiakra: ezt lesz, hogy milyen mértékben mi hivatalossá ezt a jogot now-- T n, A működési idő a probléma vevő n asok a bemenet, egyenlő nagy o egy, Ha n kevesebb, mint 2. Szóval ez feltétele, hogy. Tehát, hogy világos legyen, ha n kisebb, mint 2, van egy nagyon rövid lista, akkor a futási idő, T n, ahol n értéke 1 vagy 0, ebben a nagyon különleges esetben, ez csak lesz állandó időt. Ez lesz, hogy az egyik lépésre, két lépésben, mindegy. Ez egy fix számú lépést. 

Tehát a szaftos része bizonyosan a A másik esetben a pszeudokódja. Az else ügyben. Rendezés bal fele elemek, egyfajta jobb fele elemek, összeolvad a rendezett félidőt. Mennyi ideig tart minden ilyen lépést tartani? Nos, ha a futó a rendezés n elemek van, nevezzük nagyon generikusan, T n, majd válogatás a bal fele az elemek van, olyan, mintha azt mondanánk, T n osztva 2, és hasonlóan válogatás a jobb fele Az elemek, a fajta, mintha azt mondanánk, T n osztva a 2, majd összevonásával rendezve félidőt. Nos, ha van pár elemek száma itt, mint a négy, és néhány szám Az elemek itt, mint négy, és azt kell egyesíteni mind a négy -ban, és minden egyes ilyen négy, az egyik a másik után, úgy, hogy végső soron azt kell nyolc elem. Olyan, mintha ez nagy o n lépéseket? Ha megvan n ujjait és az egyes nekik kell egyesíteni a helyére, ez olyan, mint egy másik n lépéseket. 

Tehát valóban formulaically, tudjuk fejezni ezt, ámbátor kissé ijesztően első pillantásra, de ez valami amely rávilágít, hogy pontosan logika. A működési idő, T n, ha n nagyobb mint vagy egyenlő 2. Ebben az esetben, az ELSE esetben T n osztva 2, plusz a T N osztva 2, plusz nagy o n, néhány lineáris lépések számát, Talán pontosan n, talán 2-szer n, de ez durván, sorrendben n. Szóval, hogy is, hogy miként lehet kifejezni ezt formulaically. Most azt nem tudom, ezt, hacsak amit felvett a fejedben, vagy keresse fel a vissza a tankönyv, hogy Lehet, hogy egy kicsit csalni lap végén, de ez valóban megy ad nekünk egy nagy o n log n, mert a kiújulás látsz itt a képernyőn, ha ténylegesen ki, a végtelen számú példák, vagy megcsináltad formulaically, akkor látni, hogy ezt, mert ez a képlet Maga rekurzív, a t n át valami jobb, és t n át a bal oldalon, ez lehet ténylegesen kifejezhető, végső soron, akkora go n log n. Ha nem győzte, ez finom most, csak hogy a hit, hogy ez valóban, hogy ez mit megismétlődését vezet, de ez csak egy kicsit nagyobb matematikai megközelítése keres a menetideje merge sort alapuló pszeudokód egyedül. 

Most vessünk egy kicsit visszavezető minden adott, és vessen egy pillantást a bizonyos korábbi szenátor, aki Lehet nézni egy kicsit ismerős, aki leült a Google Eric Schmidt, néhány évvel ezelőtt, egy interjú a színpadon, előtte egy csomó emberek, beszél végső soron egy témát, hogy elég már jól ismert. Vessünk egy pillantást. 

Eric Schmidt: Most szenátor, vagy itt a Google-nál, és szeretem azt hinni, a elnökség, mint egy állásinterjú. Most nehéz munkát találni, mint elnök. Obama elnök: Így van. Eric Schmidt: És te fog tenni [hallhatatlan] most. Ez is nehéz munkát találni a Google-nál. Obama elnök: Így van. 

Eric Schmidt: Van kérdésekre, és kéri, hogy a jelöltek kérdéseket, és ez az egyik a Larry Schwimmer. 

Obama elnök: OK. 

Eric Schmidt: Mi? Azt hiszitek, viccelek? Itt van. Mi a leghatékonyabb módja annak, hogy rendezni egy millió 32 bites egész? 

Obama elnök: Well-- Eric Schmidt: Néha, Talán Sajnálom, maybe-- Obama elnök: Nem, nem, nem, nem, nem, én think-- Eric Schmidt: Ez nem it-- Obama elnök: Én gondolom, azt hiszem, a buborék Rendezés lenne rossz irányba menni. Eric Schmidt: Gyerünk. Ki mondta ezt neki? OKÉ. Én nem a számítógép-tudomány on-- 

Obama elnök: kaptunk Megvan a kémek vannak. Tanár: Rendben. Hagyjuk magunk mögött most a elméleti világa algoritmusok A aszimptotikus elemzés pontjára, és térjen vissza néhány téma hétről nulla és egy, a start hogy távolítsa el néhány képzés kerekek, ha úgy tetszik. Úgy, hogy valóban megértsék végső soron az alapoktól kezdve, mi folyik a motorháztető alatt, ha levelet, összeállítják, és végre programokat. Emlékezzünk különösen, hogy ez volt Az első C program néztük, kanonikus, egyszerű program a fajta, viszonylag szerény, ahol, kinyomtatja, Hello World. És emlékszem, hogy azt mondtam, a folyamat hogy a forráskód megy keresztül Pontosan ez az. Veszel a forráskódot, át ez egy fordító, mint csenget, és ki jön tárgykód, hogy így nézhet ki, nullák hogy a számítógép CPU, központi feldolgozó egység vagy agy, végül megérti. 

Kiderül, hogy ez egy kicsit túlzott leegyszerűsítés, hogy mi most egy helyzetben, hogy ugratni egymástól megérteni, hogy mi volt igazán folyik a motorháztető alatt minden indítás Csengés, vagy általánosabban, Minden alkalommal, amikor egy programot, felhasználásával készítsünk és CF 50 IDE. Különösen, ilyesmi ez az első generált, amikor először fordítsa le a programot. Más szavakkal, ha hogy a forráskód és lefordítani, akkor mi az első hogy outputted által csenget valami ismert assembly kódot. És valóban, úgy néz ki, mint ez. 

Futottam egy parancsot a parancssori korábban. Clang kötőjel tőke s hello.c, és ez teremtett egy fájlt Nekem nevű hello.s, belsejében amelyek pontosan ezek a tartalmak, és egy kicsit több felett, és egy kicsit több, az alábbiakban, de tettem a juiciest információk itt a képernyőn. És ha jobban megnézed, látni fogod legalább néhány ismerős kulcsszavakat. Van fő tetején. Mi már printf le a közepén. És mi is hello world backslash n idézőjelbe lent. 

És itt minden nagyon alacsony szintű utasítások hogy a számítógép CPU megérti. CPU utasításokat, hogy mozog a memória körül, hogy terhelés húrok a memóriából, és végül, a nyomtatási dolgokat a képernyőn. Most mi történik, bár után ez a szerelvény kódot generál? Végső soron, akkor nem, sőt, továbbra is generálnak tárgykód. De a lépéseket, amelyek valóban óta folyik a motorháztető alatt nézni egy kicsit, mint ez. Forráskód válik assembly kódot, ami aztán lesz tárgyi kód és az operatív szó itt, hogy amikor fordítod a forráskódot, ki jön assembly kód, majd ha össze a gyülekezési kódot, ki jön tárgykód. 

Most Clang szuper kifinomult, mint a sok fordítóprogramok, és ez nem az összes ezeket a lépéseket együtt, és ez nem feltétlenül kimeneti valamennyi közbenső fájlokat lehet még látni. Csak lefordul a dolgokat, amely olyan általános kifejezés, amely leírja a teljes folyamatot. De ha igazán akar hogy különösen ott sokkal több folyik ott is. 

De nézzük is úgy most, hogy még hogy szuper egyszerű program, hello.c, nevű függvény. Felszólította printf. De nem én írtam printf, sőt, hogy jön c, hogy úgy mondjam. Ez egy funkciót emlékeztetnek arra, hogy az bejelentett szabvány io.h, amely egy header fájl, ami egy olyan téma, akkor tulajdonképpen belevetik magukat mélyebben nemsokára. De a fejléc fájl jellemzően együtt egy kód fájlt, forráskód fájlt, így hasonlóan létezik szabvány io.h. 

Valamikor ezelőtt valaki, vagy valakiknek is írt nevű fájl szabvány io.c, a amely a tényleges definíciók, vagy megvalósítások printf, és csokor egyéb funkciók, ténylegesen leírt. Tehát mivel, ha arra gondolunk, amelynek Itt a bal oldalon, hello.c, hogy amikor összeállított, ad nekünk hello.s, akkor is, ha Csengés nem zavar megtakarítás egy helyen látjuk azt, és assembly kód lesz összeállítva hello.o, amely Valóban, az alapértelmezett név nyújtására, amikor fordítod forrás kódot tárgykód, de nem teljesen kész végrehajtani még, mert újabb lépés meg kell történnie, és történt az elmúlt pár hétig, esetleg tudtán kívül van. 

Különösen valahol A CS50 IDE, és ez, is lesz egy kicsit egy leegyszerűsítés egy pillanatra, van, vagy volt, hol nem volt, nevű fájl szabvány io.c, hogy valaki fordítva szabvány io.s vagy az azzal egyenértékű, hogy valaki majd össze szabványos io.o, vagy kiderül, egy kicsit más fájl formában, hogy lehet más fájl kiterjesztését összesen, de elméletileg és fogalmilag pontosan ezeket a lépéseket meg kellett történnie valamilyen formában. Ami azt jelenti, hogy most ha írok egy programot, hello.c, hogy csak azt mondja, hello world, és én vagyok a valaki másnak a kódját mint a printf, ami egyszer volt, hol ideje, nevű fájlt szabványos io.c, aztán valahogy el kell vennem az én tárgykód, én nullák, és annak a személynek a tárgy kódot, vagy nullák, és valahogy össze őket össze Egy utolsó file, hello, hogy az összes nullák és azok az én fő funkciója, és az összes nullák és azok a printf. 

És valóban, az utolsó folyamat nevű, összekapcsolja a tárgykód. Amelynek kimenete egy futtatható fájl. Tehát a méltányosság, a A nap végén, semmi óta változott a héten az egyik, amikor először kezdett összeállítása programok. Valóban, az összes ez volt történik a motorháztető alatt, de most mi vagyunk abban a helyzetben, ahol tudunk valójában ugratni egymástól a különböző lépéseket. És valóban, a végén A nap, még mindig maradt nullák, amelyek valójában egy nagy Segue most egy másik képessége C, hogy mi már nem volt képes mozgósítani a legvalószínűbb a mai napig, az úgynevezett bitműveletek. Más szóval, eddig, bármikor mi ve foglalkozott az adatokat a C vagy C változók, mi már voltak dolgok, mint karakter és úszók és modulok és vágyik és páros és a hasonló, de az összes ilyen legalább nyolc bit. Mi soha nem sikerült még manipulálni egyes biteket, annak ellenére, hogy az egyén kicsit, mi tudható, hogy képviselje a 0 és 1. Most kiderül, hogy a C, akkor kaphat hozzáférést az egyes biteket, Ha tudod, hogy a szintaxis, amellyel kap rájuk. 

Szóval vessünk egy pillantást A bitműveletek. Tehát képen itt van néhány szimbólum, amely mi már, milyen, fajta, látott. Látok egy jelet, egy függőleges bár, és mások is, és emlékszem, hogy jelet jelet van valami, amit eddig láttunk. A logikai ÉS operátor, ahol van, ketten együtt, vagy a logikai VAGY üzemben, ahol két függőleges rúd. Bitműveletek, amit majd lásd működnek bit egyénileg, csak használ egy jelet, egy Egyetlen függőleges vonal, a kalap szimbólum következik, a kis tilde, majd balra konzol bal oldali konzol, vagy szögletes zárójel szögletes zárójel. Mindegyik más-más jelentése van. 

Tény, hogy vessünk egy pillantást. Menjünk régi iskola ma, és felhasználása érintőképernyős származó múlt, néven ismert fehér tábla. És ez a fehér tábla fog lehetővé teszi számunkra, kifejezni néhány meglehetősen egyszerű szimbólumok, vagy inkább néhány meglehetősen egyszerű képletek, hogy mi lehet majd a végső tőkeáttétel, annak érdekében, eléréséhez az egyéni bitek egy C program. Más szóval, csináljuk ezt. Először essék egy pillanatra jelet, amely a bitenkénti ÉS operátor. Más szavakkal, ez az az üzemben, amely lehetővé teszi nekem van egy bal oldali változó jellemzően, és a jobb oldali változó, vagy egy egyedi értéket, hogy ha mi és őket, ad nekem egy végeredményt. Szóval mit gondolok? Ha egy program, van egy változó amely tárolja a következő értékek egyikét, vagy nézzük, hogy ez egyszerű, és csak kiírja nullák egyénileg, Íme a jelet üzemeltető működik. 0-jel 0 lesz egyenlő 0. Most miért van ez? 

Ez nagyon hasonlít a Logikai kifejezések, hogy már tárgyalt eddig. Ha úgy gondolja, elvégre a 0 hamis, 0 hamis, hamis és téves van, ahogy már tárgyalt logikailag is hamis. Így kapunk 0 itt is. Ha az előírtnál 0-jel 1, nos ez is lesz 0, mert erre bal oldali kifejezés, hogy igaz legyen, vagy 1, lenne szükség ahhoz, hogy igaz és valódi. De itt van a hamis és igaz, vagy 0 és 1. Most újra, ha van 1-jel 0, ez is lesz 0, és ha van 1-jel 1, Végül van még egy 1 bites. Más szóval, mi nem csinál valami érdekes, hogy ennek az üzemeltető csak még, ez az & karakter üzemeltető. Ez a bitenkénti ÉS operátor. De ezek az összetevők amelyen keresztül meg tudjuk csinálni Érdekes dolog, ahogy hamarosan látni. 

Most nézzük meg, csak az egységes függőleges sáv felett van a jobb oldalon. Ha van egy 0 és én kicsit VAGY azt, bitenkénti VAGY operátor, a másik 0 bit, hogy fog adni nekem 0. Ha én 0 darab és OR azt 1 kicsit, aztán megyek kap 1. És valóban, csak egyértelműség, hadd menjen vissza, hogy az én függőleges vonalak nem tévednek az 1-es. Hadd írjam át az összes én 1 egy kicsit egyértelműen, hogy mi lesz ezután, ha én van egy 1 vagy 0, hogy lesz egy 1, és ha van egy 1 vagy 1, hogy is lesz egy 1. Tehát látható, logikusan, hogy az OR üzemeltető viselkedik nagyon eltérő. Ez ad nekem 0 vagy 0 ad nekem 0, de Minden más kombináció ad nekem 1. Mindaddig, amíg van egy 1 a általános képletű, az eredmény lesz 1. 

Ezzel szemben az ÉS üzemeltető, a jelet, csak akkor, ha van két 1-esek egyenletet, tudom tényleg kap egy 1 out. Most van néhány más üzemeltetők is. Ezek közül az egyik egy kicsit nagyobb szerepet. Szóval hadd menjen előre, és törli ezt, hogy szabadítson fel helyet. És vessünk egy pillantást a kalap szimbólum, csak egy pillanatra. Ez tipikusan egy karaktert beírhatja a billentyűzeten Shift és Ezután az egyik szám tetején, a US billentyűzet. 

Tehát ez az exkluzív VAGY operátor, exkluzív VAGY. Tehát most láttam a VAGY operátor. Ez a ERCW. Mi valójában a különbség? Nos nézzük csak nézd meg a képletet, és ezt összetevőként végül. 0 XOR 0. Azt fogom mondani mindig 0. Ez a meghatározás a XOR. 0 XOR 1 lesz 1. 1 XOR 0 lesz 1, és 1 XOR 1 lesz? Rossz? Vagy nem? Nem tudom. 0. Most mi folyik itt? Nos gondoljon a neve ennek üzemeltető. Kizáró vagy, így például a név, fajta, azt sugallja, A válasz csak lesz 1, ha a bemenetek exkluzív, kizárólag különböző. Tehát itt a bemenetek a azonos, így a kimenet 0. Itt a bemenetek a azonos, így a kimenet 0. Itt vannak a kimenetek különböznek egymástól, kizárólagosak, és így a kimenet 1. Tehát ez nagyon hasonlít a És ez nagyon hasonló, vagy inkább ez nagyon hasonlít a VAGY, de csak egy exkluzív módon. Ez az egy már nem egy 1, mert van két 1-es, és nem kizárólag, csak az egyiket. Minden rendben. Mi van a többiekkel? Nos, a hullámvonal, eközben valóban szép és egyszerű, szerencsére. És ez egy egyváltozós üzemben, ami azt jelenti, ez kizárólag egy input, Egy operandus, hogy úgy mondjam. Nem egy jobb és bal. Más szóval, ha Ön hullámvonal a 0, a válasz az ellenkezője. És ha veszel tilde 1, a válasz lesz az ellenkezője. Tehát a hullámvonal üzemeltető egy módja a tagadásának egy kicsit, vagy essek egy kicsit a 0-1, vagy 1-0. 

És, hogy hagy bennünket végre mindössze két záró szereplők, Az úgynevezett baloldali váltás, és a az úgynevezett jobb shift üzemeltető. Vessünk egy pillantást, hogyan ezek a munkák. A balra tolt üzemben, írásos két csúcsos zárójel ilyesmi, a következőképpen működik. Ha a bemenet, vagy én operandus, hogy a bal oldali eltolás operátora egész egyszerűen egy 1. És én majd mondd el a számítógépet balratolást, hogy 1, mondjuk hét helyen, Az eredmény az, hogy én venni, hogy 1, és mozgassa hét helyen át a bal, és alapértelmezés szerint fogjuk feltételezni, hogy A hellyel jobbra lesz nullákkal töltődik. Más szavakkal, 1 fűzött műszak 7 megy adj, hogy az 1, majd 1, 2, 3, 4, 5, 6, 7 nullák. Tehát úgy, hogy lehetővé teszi, hogy hogy egy kis szám, mint 1, és világosan, hogy sokkal sokkal, sokkal nagyobb ezen a módon, de mi történt valójában látni okosabb megközelítés érte helyett, valamint, 

Minden rendben. Ennyi héten három. Látni fogjuk legközelebb. Ez volt CS50. 

[Zenelejátszási] 

1. Előadó: Ő volt a snack bár eszik egy fagylaltkehely forró csokoládéöntettel. Ő volt az egész arcát. Ő visel, hogy a csokoládé, mint egy szakáll Hangszóró 2: Mit csinálsz? Hangszóró 3: Hmmm? Mi? 

Hangszóró 2: Csak nem kettős dip? Ha kétszer mártott a chip. Hangszóró 3: Elnézést. Hangszóró 2: Ön mártott a chip, akkor beleharapott, és akkor mártott újra. Hangszóró 3: Hangszóró 2: Szóval ez olyan, mintha az egész szája közvetlenül a dip. Legközelebb veszel egy chip, Csak mártsuk meg egyszer, és vége. 

Hangszóró 3: Tudod mit, Dan? Ön mártsuk a kívánt módon dip. Majd mártsuk az is, hogy szeretnék dip.