DAVID MALAN: Rendben. Visszajöttünk. Tehát ebben a szegmensben a programozás mi Azt hittem, ezt egy mix a dolgokat. Egy, akkor egy kicsit valami gyakorlati, jóllehet egy játékosabb programozás environment-- az egyik, hogy demonstratív pontosan féle gondolatok mi már beszélünk, de egy kicsit több hivatalosan. Két, nézd meg néhány A több technikai szempontból hogy egy programozó valójában megoldani problémák, mint a keresett probléma néztük meg előtt és még egy alapvetően Érdekes probléma a válogatás. 

Mi csak feltételezzük a get menni hogy ez a telefonkönyvet rendezve, de ez önmagában tulajdonképpen egyfajta kemény probléma sok különböző módon hogy oldja meg. Így fogjuk használni ezeket egy osztály a problémák képviselője dolgok lehet megoldani, általában. És aztán majd beszélünk mintegy néhány részlet, amit nevezzük adatok structures-- szakértő módon, mint láncolt listák és hash táblák és fák programozó valójában használni, és általában használja egy táblára festeni egy képet, amit ő képzel végrehajtására Néhány szoftver. 

Tehát lássuk a gyakorlati részével. Tehát csak a kezét piszkos egy környezet úgynevezett scratch.mit.edu. Ez egy olyan eszköz, amit használunk a mi egyetemi osztályban. Annak ellenére, hogy úgy tervezték, A 12 éves és akár, azt használjuk fel része, hogy egy kicsit mivel ez egy szép, vidám grafikus módon a tanulás egy kis valamit a programozás. Így a feje, hogy az URL, ahol megjelenik egy oldal elég, mint ez, és megy előre, és kattintson Csatlakozz Scratch a jobb felső sarokban és válasszon egy felhasználónevet és egy jelszót, és végül magad Egy account-- scratch.mit.edu. Azt hittem, használja ezt a lehetőséget először be kell mutatnia. A kérdés merült fel a szünetben mit kód néznek ki. És beszéltünk A szünetben a helyzet a C, a particular-- különösen a alsó szinten egy régebbi nyelven. És most csináltam egy gyors Google keresés, hogy megtalálja a C kód A bináris keresés, az algoritmus, hogy mi használt keresni, hogy telefonkönyvben korábban. Ez a különleges példa, természetesen, nem keres egy telefonkönyvet. Csak keres egy csomó számok a számítógép memóriájában. De ha azt szeretné, hogy csak kap egy vizuális értelemben, hogy mi a tényleges programozás nyelv néz, úgy néz ki, egy kis valamit, mint ez. Tehát körülbelül 20-plus, 30, vagy úgy sornyi kódot, de a beszélgetés voltak, amelyek felett szünet volt arról, hogy ez valójában gets átalakult nullák és egyesek és ha nem lehet csak visszaállítani, hogy feldolgozására és megy nullák és egyesek vissza a kódot. 

Sajnos, a folyamat olyan átalakító hogy ez sokkal könnyebb mondani, mint megtenni. Mentem előre, és valóban kiderült E program bináris keresés, a nullák és egyesek útján nevű program a fordító, hogy én történik, hogy itt jobb a Mac-emet. És ha megnézi a képernyőt Itt, specifikusan e középső hat oszlop csak, meglátod csak nullák. És ezek a nullák és egyesek, hogy össze, hogy pontosan keresés programot. 

És így minden egyes darab öt bit, Minden byte nullák és egyesek itt, képviselik utasítás jellemzően belsejében egy számítógép. És valóban, ha már hallottam a marketing szlogen: "Intel Inside" - azaz, Persze, csak azt jelenti, hogy van egy Intel processzor, az agy a számítógép belsejében. És hogy ez mit jelent, hogy a CPU hogy van egy utasításkészlet, hogy úgy mondjam. 

Minden CPU a világon, sok azokat az Intel ezekben a napokban, megérti véges utasítások száma. És ezeket az utasításokat olyan alacsony szinten mivel ezt a két számot össze, szaporodnak a két szám együttesen mozog ez az adat innen hogy itt a memóriában, csak ez az információt itt, hogy itt a memóriában, és így forth-- nagyon, nagyon alacsony szintű, szinte az elektronikus adatokat. De azokkal a matematikai műveletek párosul azzal, amit korábban tárgyaltuk, A adatábrázolást a nullák és egyesek, lehet felépíteni mindent hogy a számítógép ma megtehetsz, hogy ez szöveges, grafikus, zenés, vagy más módon. 

Tehát ez nagyon könnyen kap elveszett a gyomok gyorsan. És van egy csomó szintaktikai kihívások amellyel ha a legegyszerűbb, legostobább elírás sem a program működni fog nélkül. És így ahelyett, hogy egy nyelv, mint a C ma reggel, Azt gondoltam, hogy lenne több móka, hogy ténylegesen valami vizuális, amelyek míg célja a gyerekek valójában egy tökéletes megnyilvánulása A tényleges programozás language-- történetesen Képek használata szöveg helyett képviselhetik az ötleteket. 

Tehát ha valóban van egy számla scratch.mit.edu, kattintson a Create gombra bal felső sarkában az oldalon. És akkor megjelenik egy olyan környezetben, mint Az egyik én vagyok arról, hogy a képernyő itt. És mi fogjuk tölteni csak egy kicsit kicsit az idő játszik itt. Lássuk, ha nem tudjuk az összes megoldani problémák együtt a következő módon. 

Tehát mit fog látni ebben a environment-- és valójában csak hagyja nekem szünet. Ha valaki nincs itt? Nem itt? RENDBEN. Tehát hadd rámutatni néhány jellemzői ebben a környezetben. 

Így a bal felső sarokban a képernyő, akkor Van Scratch színpadi, hogy úgy mondjam. Scratch nem csak a neve E programozási nyelv; ez is a neve a macska, hogy látod alapértelmezésben ott narancs. Ő a színpadon, így hasonlóan leírtam A teknős korábban, mint amelyek a négyszögletes fehér tábla környezetben. Ez a macska világa korlátozódott kizárólag a négyszög fel tetején van. 

Közben, a jobb oldalon oldali itt, ez Csak egy script körzetében, üres lappal, ha úgy tetszik. Ez az, ahol megyünk írni a program csak egy pillanatra. És az építőkockák, hogy mi kell használja, hogy megírjam ezt a puzzle program-- darab, ha will-- vannak ezek itt a közepén, és ők kategorizált a működése. Így például, én megyek előre és igazolja, legalább egy ilyen. Megyek, hogy menjen előre, és kattintson A Control kategória fel tetején. 

Tehát ezek a kategóriák fel tetején. Megyek kattintson a Vezérlőpult kategóriában. Inkább megyek, hogy kattintson a Programok kategória, a legelső fel tetején. És ha azt szeretné, hogy kövesse végig még ahogy ezt tesszük, akkor elég szívesen. Megyek kattintson és húzza át a elsőt ", amikor a zöld zászló kattintott." És akkor fogok dobni csak durván a tetején én üres pala. 

És mi szép a Scratch hogy ez a puzzle-darab, amikor egymásba más puzzle darab, fog tenni a szó szoros értelmében mik azok a puzzle darabkái mondják, hogy nem. Így például, Scratch jobb most a közepén a világ. Megyek, hogy menjen előre, és válassza Most, mondjuk, a Motion létesítmény, Ha azt szeretné, hogy ezt a same-- Motion kategóriában. És most észre van egy egész csomó puzzle darab itt hogy ismét a fajta amit mondanak. És én megyek előre, és húzza, és dobja a lépés blokk jobbra itt. 

Azt tapasztaljuk, hogy amint kapsz közel az alján a "zöld zászló kattintott "gombra, értesítés hogy egy fehér vonal jelenik meg, mintha ez szinte mágneses, azt akarja, hogy menjen oda. Csak elengedni, és ez lesz pattintsa együtt, és a formák is illeszkedik. És most talán majdnem kitalálni, hogy hol megyünk ezzel. 

Ha megnézi az Scratch szakaszban ide, és nézd, hogy a tetején, akkor megjelenik egy vörös fény, a stoptábla, és a zöld zászlót. És én megyek előre és nézni a screen-- csak egy pillanatra, ha lehetne. Megyek kattintva zöld zászló most, és ment, amit úgy tűnik, hogy 10 lépés vagy 10 pixel, 10 pontok, a képernyőn. 

És így nem izgalmas, de hadd javasol anélkül, hogy tanítani ezt, csak a saját saját intuition-- let nekem javasolni, hogy kitaláljuk, hogyan lehet hogy Scratch séta jobbra le a színpadról. Van neki helyet csináljanak a jobb oldali a képernyőn, egészen jobbra. Hadd adjak egy pillanatra vagy úgy, hogy birkózni vele. Érdemes egy pillantást más kategóriába tartozó blokkokat. Rendben. Tehát csak zárja, amikor már A zöld zászló kattintott ide és mozgassa 10 lépés van a egyetlen utasítás, minden alkalommal, amikor kattintson a zöld zászlót, mi történik? Nos, ez az én futó programot. Így tudtam ezt talán 10-szer manuálisan, de ez érzi, egy kicsit bit Hackish, hogy úgy mondjam, amellyel nem vagyok igazán A probléma megoldása. Csak azt próbálom újra és újra és újra és újra amíg azt a fajta véletlenül elérjék az irányelv hogy kitűzött céljaikat korábban. 

De tudjuk, hogy a mi pszeudokód korábban, hogy ott van ez a fogalom a programozás a hurok, csinál valamit újra és újra. És így láttam, hogy egy csomó akkor elérte, amit puzzle-darab? Ismételjük, amíg. Így tudnánk tenni valamit mint addig ismételjük, amíg. És mit ismételjük, amíg pontosan? 

RENDBEN. És hadd menjen az egyik, hogy kissé egyszerűbb csak egy pillanatra. Hadd menjek előre, és erre a célra. Figyeljük meg, hogy mivel lehet, hogy felfedezett ellenőrzés alatt, van ez az ismétlődés blokk, amely nem úgy néz ki, mint ez, hogy nagy. Ott nem sok helyet e két sárga vonal. De, mint néhány lehet, hogy észre, ha drag and drop, észre, hogy növekszik, hogy töltse ki a formát. 

És akkor is belegyömöszölni tovább. Akkor csak folyamatosan növekszik, ha drag and lebeg felette. És nem tudom, mi legjobb itt, úgyhogy Számomra legalábbis ismételjük ötször, az Például, majd menj vissza a színpadra és kattintson a zöld zászlót. És most észre, hogy ez nem egészen ott. 

Most néhányan javasolják, Victoria csak nem, ismételje meg 10-szer. És ez általában nem rávenni egészen, de nem ott lesz erőteljesebb mint ahogyan önkényesen kitalálni hány mozog, hogy? Mi lehet a jobb blokk mint ismétlés 10-szer lesz? 

Ja, miért nem csinál valamit örökre? És most hadd mozog ez a puzzle-darab benne van, hogy eltűnjön ez. Most észre nem számít, ha Scratch elindul, megy a szélére. És szerencsére MIT, aki Scratch, csak gondoskodik arról, hogy soha nem teljesen eltűnik. Akkor mindig megragad a farkát. 

És csak ösztönösen, akkor miért mozogni? Mi történik itt? Úgy tűnik, hogy megállt, de akkor, ha azt felvenni, és húzza ő tartja akar menni oda. Miert van az? Valóban, a számítógép szó szerint csinálni, amit mondani, hogy igen. Tehát, ha azt mondta, hogy korábban nem a következő dolog örökre, mozgás 10 lépést, ez megy folyamatosan megy és megy amíg nem nyomja meg a piros stoptábla és állítsa le a program teljesen. 

Tehát akkor is, ha nem Ehhez hogyan tudnám hogy Scratch gyorsabb az egész képernyőt? További lépések, igaz? Tehát ahelyett, hogy 10 egy időben, miért nem megy előre, és változtassa meg az alábbiakra: mit propose-- 50? Tehát most megyek, hogy kattintson a zöld zászló, sőt, megy nagyon gyorsan. 

És ez természetesen csak megnyilvánulása animáció. Mi az animáció? Ez csak megmutatja a humán a csomó állóképek tényleg, nagyon, nagyon gyors. És így, ha mi csak mondom neki, hogy a mozgást lépéseket, mi csak olyan hatást kelt, hogy legyen változás, hogy hol van a képernyőn annál gyorsabban egységnyi idő alatt. 

Most a következő kihívás, amit javasolt az volt, hogy neki lepattan a szélét. És anélkül, hogy tudnánk, mi puzzle darab exist-- mert finom ha nem kap a szakaszában a challenge-- mi akarsz csinálni ösztönösen? Hogyan van vele visszapattanó és tovább, a bal és jobb? 

Igen. Tehát szükségünk van valamilyen Az állapot, és mi úgy tűnik, hogy feltételes, így beszélnek, az ellenőrzési kategóriában. Amely ezeket a blokkokat tudjuk érdemes? Igen, talán "ha, akkor". Így észre, hogy többek között a sárga blokkok van itt, van ez a "ha" vagy ez a "ha más" blokk lesz lehetővé teszi számunkra, hogy a döntést, hogy ezt vagy erre. És akkor még fészket őket csinálni több dolgot. Vagy ha már nem ment még itt, megy előre a Érzékelési kategóriában és-- lássuk, ha itt van. 

Tehát mi blokk hasznos lehet itt érzékelni, hogy ő a színről? Igen, észre, hogy ezek közül néhány blokkok parametrizálhatók, hogy úgy mondjam. Ezek a fajta egyedi, nem ellentétben HTML tegnap attribútumokkal, ahol ezek az attribútumok fajta testre a viselkedése egy címke. Hasonlóképpen itt is megragadom a megható blokk és a változás, és feltenni a kérdést, Ön megérintette az egér pointert a kurzor vagy ha megérinti a szélén? 

Tehát hadd menjen be, és erre a célra. Megyek kicsinyíteni egy pillanatra. Hadd fogd ezt a puzzle darab Itt, ebben a puzzle-darab ez, és megyek összekever őket egy pillanatra. Megyek mozgatni ezt, megváltoztatni ezt a megható él, és fogok mozgás erre. Tehát itt van néhány összetevőjére. Azt hiszem, minden megvan, amit akarok. 

Szeretné valaki szeretné javasolni, hogyan csatlakoztathatja ezeket talán fentről lefelé annak érdekében, hogy megoldják a problémát, Scratch mozog jobbra-balra és jobbra, balról jobbra balra, minden időben csak pattogó le a falat? Mit szeretne tenni? Melyik blokk kéne csatlakozni a "Amikor a zöld zászló elsőként kattintó"? 

OK, így kezdjük a "örökké". Mi megy belül a következő lépés? Valaki más. OK, mozgás lépéseket. Rendben. Akkor mi? Így aztán az, ha. És észre, bár úgy néz ki szendvics össze szorosan, akkor csak nőnek, hogy töltse ki. Ez csak ugorj, ahol akarom. 

És mit tettem között a ha és az akkor? Valószínűleg ", ha megérinti él." És vegyük észre, megint, ez túl nagy érte, de nőni fog kitölteni. Majd kapcsolja 15 fokkal? Hány fok? Igen, így 180 forognak nekem egészen körül. Tehát lássuk, ha kaptam ezt a jogot. Hadd kicsinyítés. 

Hadd húzza Scratch fel. Tehát ő egy kicsit torz most, de ez rendben van. Hogyan állítható vissza őt könnyen? Megyek csalni egy kicsit. Úgyhogy még egy blokk, csak hogy egyértelmű legyen. Azt akarom, hogy pont 90 fok jobbra alapértelmezés szerint így én csak elmondom neki erre programozott. És kész is van. Úgy tűnik, hogy megtettem. Ez egy kicsit fura, mert ő sétál fejjel lefelé. Nevezzük, hogy a hiba. Ez nagy hiba. Egy bogár egy hiba a programban, a logikai hiba, hogy én, az emberi készült. Miért megy fejjel lefelé? Esetleg MIT csavart ki vagy ugye? 

Igen, úgy értem, hogy nem a MIT hiba. Adtak egy puzzle-darab hogy azt mondja, viszont néhány fokban. És Victoria javaslatára Én fordult 180 fokot, ami a helyes intuíció. De fordult 180 fokot szó azt jelenti, fordult 180 fokot, és ez nem igazán amit akarok, úgy tűnik. Mert legalább ő a A kétdimenziós világban, így esztergálás folyik valójában flip fejjel lefelé. 

Azt érdemes használni, mi blokk ehelyett az alapján, amit itt látsz? Hogyan tudnánk ezt orvosolni? Igen, így tudtuk mutatni az ellenkező irányba. És tulajdonképpen még ez nem lesz elég, mert csak akkor tudjuk kódba a mutató jobbra vagy balra. 

Tudod, mit tehetnék? Úgy néz ki, hogy van egy kényelem blokk van. Ha nagyítás, lásd valami, mint itt? Tehát úgy néz ki, mint a MIT területén absztrakció épült itt. Ez a blokk úgy tűnik, hogy ezzel egyenértékű amelyhez más blokkok, többes? 

Ez egyben úgy tűnik, hogy ezzel egyenértékű hogy ez az egész hármas blokk hogy itt van. Így kiderül, tudok egyszerűsíteni én programot, hogy megszabaduljon az összes, hogy és csak hogy ezt itt. És most még egy kicsit hibás, és ez rendben van most. Majd hagyjuk, hogy legyen. De a program még egyszerűbb, és ez is reprezentatív lenne A cél programming-- hogy ideális esetben a kódot egyszerű, minél kisebb, míg továbbra is a olvasható, mint lehetséges. Nem akarjuk, hogy ez annyira tömör, hogy nehéz megérteni. 

De észre azt váltottuk három blokk egy, és ez vitathatatlanul jó dolog. Már absztrahált el a fogalom ellenőrzése, hogy te szélén csak egy blokk. Most lehet szórakozni ezzel, sőt. Ez nem tesz hozzá annyi szellemi érték, hanem játékos értékét. Megyek, hogy menjen előre és megragad ez a hang itt. Tehát hadd menjen előre, és hadd állítsa le a program egy pillanatra. Megyek rögzíteni a következőket, hogy betekintést enged a mikrofon. 

Essünk neki. Jaj. Próbáljuk meg újra. Essünk neki. OK, felvettem a rossz dolog. Essünk neki. Jaj. Jaj. Rendben. Most kell megszabadulni, hogy. Rendben. 

Tehát most van egy rögzítése csak "jaj". Úgyhogy most megyek előre, és ezt "jaj". Megyek, hogy menjen vissza az én szkriptek, és most értesítés van ebben a mondatban, hogy hívják hangot lejátszani "miau" vagy hangot lejátszani "jaj". Megyek húzza ezt, és ahol rakjam ezt a komikus hatás? Igen, így most ez a fajta buggy, mert most ez block-- észre, hogy ez a "ha az élére, ugrál "a fajta önálló. Szóval kell helyrehozni. Hadd menjek előre, és erre a célra. Hadd megszabadulni ez, és menj vissza az eredeti, több szándékos funkcionalitás. Tehát "ha megérinti él, akkor" Azt akarom, fordulni, mint Victoria javasolt, 180 fok. És akarok játszani A hang "jaj" van? 

Igen, észre, hogy ez kívül hogy a sárga blokk. Tehát ez is lenne egy bug, de azt vettem észre azt. Így fogok húzza fel itt, és értesítés most már belül a "ha". Tehát a "ha" ez a fajta hasonló kar-szerű folt ami csak akkor fog tenni, ami a belsejébe. Tehát ha most kicsinyíteni a a kockázatot a annoying-- 

COMPUTER: Jaj, jaj, jaj. 

DAVID MALAN: És csak megy a végtelenségig. Most csak, hogy gyorsítsa fel a dolgokat itt, hadd menjen előre, és nyissa fel, nézzük say-- hadd menjen néhány A saját dolgaim osztályban. És hadd nyissa fel, mondjuk, ez Egy által az egyik tanítási társaik néhány évvel ezelőtt. Így néhányan talán felidézni ezt a játékot ízlését, és ez valóban figyelemre méltó. Annak ellenére, hogy tettünk a legegyszerűbb program most, nézzük meg, hogy ez mit valóban úgy néz ki, mint. Hadd hit játszani. 

Tehát ebben a játékban, van egy béka, és a nyíl keys-- elveszi nagyobb lépésből áll, mint én remember-- Van felett ez béka. És a cél az, hogy az egész elfoglalt út nélkül fut be az autókat. És nézzük see-- ha felmegyek itt, meg kell várni a napló gördülni. Ez olyan, mint egy bogár. Ez a fajta egy bogár. Rendben. Vagyok itt ezt, ott, és akkor tartsa megy, amíg nem kap minden a békák, a liliom párna. Most ez lehet keresni valamennyi a bonyolultabb, de próbáljuk megtörni ez mentálisan és szóban bele összetevő blokkolja. Tehát valószínűleg egy puzzle darab, amely nem láttuk még de ez reagál a billentyűk, a dolog, amit megüt a billentyűzeten. 

Tehát ott valószínűleg valamiféle blokk, amely azt mondja, ha a fő értéke fel, akkor valamit csinálni Scratch-- talán mozgatni 10 lépésben ezen a módon. Ha le gombot megnyomja, mozogni 10 lépés Ily módon, vagy balra gombot, mozogni 10 lépés Ily módon 10 lépésre, hogy. Már világosan kiderült a macska egy béka. Tehát ez csak, ahol a jelmez, mint Scratch hívások it-- mi csak az importált képet a béka. 

De mi más történik? Milyen más sornyi kódot, milyen más puzzle-darabokat tette Blake, a tanítás ember, használni ezt a programot, úgy tűnik? Mi így minden move-- milyen programozási konstrukció? 

Motion, biztos magában, így a mozogni blokkot, az biztos. És mi ez a lépés blokk belsejében, a legvalószínűbb? Igen, valamilyen hurok, talán egy örökre blokk, talán egy ismétlés block-- ismételjük, amíg blokk. És ez az, ami így a naplók és a liliom párna, és minden mást mozog előre-hátra. Ez csak történik a végtelenségig. 

Miért van néhány az autók gyorsabban mozog, mint a többiek? Mi a különbség a ezeket a programokat? Igen, valószínűleg egy részük szed több lépést egyszerre, és néhány közülük kevesebb lépésben egyszerre. És a vizuális hatás gyors versus lassú. 

Mit gondol, mi történt? Amikor megkaptam a béka egészen az utca túloldalán, és a folyó ra a lily pad, valami Figyelemre méltó történt. Mi történt, amint tette ezt? Megállt. Ez a béka megállt, és Van egy másik béka. Tehát mi konstrukciót kell ott használt, mi jellemző? 

Igen, így van valamilyen "Ha" feltétel akár ott is. És kiderül out-- nem láttunk this-- de van más blokkok vannak, hogy lehet mondani, ha megható Egy másik dolog a képernyőn, ha megérinti a lily pad ", majd". És akkor ez mikor hogy a második béka jelenik meg. Tehát annak ellenére, hogy ez a játék minden bizonnyal nagyon kelt, bár első pillantásra van annyira megy on-- és Blake nem ostor ezt fel két perc alatt, valószínűleg elvitte több óra, hogy létrehozza ezt a játékot alapján a memóriája vagy videó a múlt változata is. De mindezen kis dolgok folyik a képernyőn elszigetelten szűkülnek le ezeket a nagyon egyszerű constructs-- mozgások vagy nyilatkozatok mint már említettük, a hurkok és feltételeket, és ennyi. Van néhány más szakértő jellemzői. Néhány ezek közül a tisztán esztétikai vagy akusztikus, mint a hangok csak játszottam. De a legtöbb esetben, akkor Van ezen a nyelven, Scratch, az összes alapvető építőelemeket, hogy Van C, Java, JavaScript, PHP, Ruby, Python, és számos más nyelven. Bármilyen kérdése van Scratch? Rendben. Így nem fogunk merülni a mélyebb semmiből, bár szívesen ezen a hétvégén, különösen, ha gyerekek vagy unokahúga és unokaöccse, és az ilyen, bevezetni őket a semmiből. Ez valójában egy csodálatosan játékos környezetben, mint a szerzők szerint, Nagyon magas mennyezettel. Annak ellenére, hogy kezdődött nagyon alacsony szintű részleteket akkor tényleg egy kicsit vele, és ez talán bemutatót, hogy pontosan. 

De nézzük most átmenet néhány kifinomult problémák, ha úgy tetszik, ismert, mint "keresés" és a "Válogatás", általában. Mi volt ez a telefon könyvet earlier-- itt egy másikat csak discussion-- hogy képesek voltunk keresni hatékonyabban, mert jelentős feltételezés. És csak hogy tisztázzuk, milyen feltételezés azt, hogy ha keres ezen keresztül telefonkönyv? Hogy Mike Smith volt A telefonkönyv, bár lenne képes kezelni A forgatókönyv nélküle ott, ha csak megállt idő előtt. A könyv ábécé. És ez egy nagyon nagylelkű feltételezés, mert jelenti someone-- Olyan vagyok A vágás egy sarokba, mint én vagyok a gyorsabb, mert valaki más tette a sok kemény munka számomra. 

De mi van, ha a telefon könyvben szétválogatott? Talán Verizon kapott lusta, csak dobott mindenki nevek és a számok ott talán abban a sorrendben, amelyben feliratkozott telefon szolgáltatás. És mennyi idő telik nekem találni valakit, mint Mike Smith? 1000 oldal telefon book-- hány oldalak nem azt kell nézni rajta? 

Mindegyikük. Maga a fajta jártál. Ha szó szerint meg kell nézni minden oldalon, ha a telefonkönyvben csak véletlenszerűen rendezve. Lehet, hogy szerencsés és megtalálja Mike a legelső oldalon, mert volt az első vevő rendelni telefon szolgáltatás. De lehetett volna az utolsó is. 

Tehát véletlen sorrendben nem jó. Tegyük fel, hogy van, hogy rendezze a telefonkönyv, illetve általában a fajta adat hogy már kapott. Hogyan tudjuk ezt? 

Nos, hadd próbálja Egy egyszerű példa erre. Hadd menjek előre, és dobálják néhány számot a táblára. Tegyük fel, hogy a számok már vannak, mondjuk, négy, kettő, egy, és három. És Ben, rendezni ezeket a számokat a számunkra. 

Ok, rendben. Hogyan csináltad, hogy? Rendben. Így kezdődik a legkisebb érték és a legmagasabb, és ez igazán jó intuíció. És észre, hogy mi emberek valójában nagyon jó problémák megoldására mint ez, legalábbis amikor az adatok viszonylag kicsi. Amint elkezdi, hogy több száz A számok, több ezer szám, Több millió szám, Ben valószínűleg nem tudta megtenni, hogy elég gyors, feltételezve, hogy voltak hiányosságok a számokat. Elég könnyen számolni egymillió egyébként, csak időigényes. 

Tehát az algoritmus úgy hangzik, mint Ben használt most volt keresést a legkisebb számot. Így, bár mi, emberek is igénybe vehet egy csomó információt vizuálisan, a számítógép valójában egy kicsit korlátozott. A számítógép csak nézd meg egy byte egy időben vagy talán négy byte-os time-- Manapság talán 8 byte-os time-- de egy nagyon kis számú bájtok egy adott időben. 

Tehát, mivel már tényleg Négy különböző értékeket here-- és akkor úgy gondolja, Ben, mint amelyek szemellenzőt mintha egy számítógép, mint hogy nem lát mást, mint egy szám egy time-- tehát általában feltételezzük, mint Angol, akkor jobbról balra. Tehát az első számú Ben valószínűleg nézett A négy éves volt, és aztán nagyon gyorsan rájött, hogy ez egy elég nagy number-- hadd keresd. 

Van kettő. Várj egy percet. Két kisebb, mint négy. Megyek, hogy emlékezzen. Két most a legkisebb. Most one-- ez még jobb. Ez még kisebb. Megyek elfelejteni két és csak emlékezni egyet. 

És tudta megállítani keres? Nos, nem tudott alapján ezt az információt, de jobb lenne, ha a keresés a többi a lista. Mert mi van, ha nulla volt a listán? Mi van, ha negatív volt a listán? Ő csak azt tudja, hogy a válasz akkor helyes, ha ő kimerítően ellenőrizni a teljes lista. Tehát nézzük a többi ezt. Hár volt időpocsékolás. Megvan szerencsétlen, de én még helyes megtenni. És így most feltehetően választotta ki a legkisebb számot és csak tedd az elején A lista, mint én itt. Most mit csinálni, még akkor is Ön nem gondolt, hogy majdnem ilyen mértékben? Ismételjük meg az eljárást, így valamiféle hurok. Van egy ismerős ötlet. Tehát itt van négy. Ez jelenleg a legkisebb. Ez egy jelöltet. Többé nem. Most láttam kettőt. Ez a következő legkisebb eleme. Hár ez nem kisebb, így most Ben tudja tépni ki a kettő. 

És most ismételje meg a folyamatot, és Természetesen a három nő húzta ki legközelebb. Ismételje meg a folyamatot. Négy nő húzta ki. És most éppen ki a számokat, így a lista kell válogatni. 

És valóban, ez egy formális algoritmus. A számítógép-tudós lenne ezt "kiválasztás sort," Az ötlet az volt, egyfajta a list iteratively-- újra és újra és újra kiválasztja a legkisebb szám. És mi szép, hogy az, ez csak olyan rohadt intuitív. Ez ilyen egyszerű. És akkor ismételje meg ugyanezt a műveletet újra és újra. Ez egyszerű. 

Ebben az esetben az volt, gyors, de meddig történik mindez? Nézzük, hogy úgy tűnik, és egy kicsit több unalmas. Tehát egy, kettő, három, négy, öt hat, hét, nyolc, kilenc, 10, 11, 12, 13, 14, 15. 16-- tetszőleges számú. Csak azt akartam többet ezt idő, mint a négy. Tehát ha van egy egész csomó számot now-- azt nem is számít amit are-- nézzük úgy gondolja, hogy ez mit algoritmus nagyon tetszik. 

Tegyük fel, hogy a számok vannak. Ismét nem számít, hogy mit vannak, de ők véletlen. Én alkalmazásával Ben algoritmus. Azt kell, hogy válassza ki a legkisebb számot. Mit tegyek? És megyek, hogy fizikailag csináld ezt az ideje cselekedni ki. Keresi, keresi, látszó, néz, néz. Csak mire eljut a végén a lista Rájöttem a legkisebb szám volt két ebben az időben. Egy nem szerepel a listában. Így tettem le két. 

Mi a teendőm? Látszó, látszó, néz, néz. Most találtam a hetes szám, mert ott hiányos ezen numbers-- de csak önkényes. Rendben. Így most már tudom letenni hét. Looking, néz. 

Most feltételezve, a Persze, hogy Ben nem extra RAM, extra memória, mert, természetesen, Nézem ugyanazt a számot. Bizonyára én is emlékeznék Mindezen számok, és ez teljesen igaz. De ha Ben emlékszik minden A számok azt látta, még nem igazán készült alapvető előrelépés mert már van képes keresni a számok a táblán. Emlékezés az összes számok nem segít, mert még mindig, mint egy számítógépes Csak nézd meg, mi mondtuk, egy szám egy időben. Tehát nincs valami cheat nézve, hogy képes kihasználni. 

Így a valóságban, mint én tovább keresni a listában, A szó szoros értelmében, hogy csak folyamatosan megy oda-vissza rajta, kopasztás ki A következő legkisebb számot. És akkor milyen következtetni én buta mozgások, ez egyre csak nagyon unalmas nagyon gyorsan, és úgy tűnik, hogy megy vissza, és oda, oda-vissza egy kicsit. Most, hogy tisztességes, nem kell menni annyira, nos, see-- hogy tisztességes, Nem kell járni elég annyi lépést minden egyes alkalommal. Mert, persze, ahogy válasszon a listából a számok, A fennmaradó lista egyre rövidebb. 

És így gondoljuk végig, hány lépést én valójában traipsing keresztül minden egyes alkalommal. Az első helyzet mi volt 16 szám, és így maximally-- nézzük csak Ehhez egy discussion-- Volt, hogy nézze át 16 számokat, hogy megtalálják a legkisebb. De ha már váj ki a legkisebb szám, hogyan Hosszú volt a maradék listát, természetesen? Csak 15. Tehát, hogy hány szám volt Ben, vagy én átnézni a második alkalommal? 15, csak hogy menjen, és megtalálja a legkisebb. De most, persze, a lista, is, kisebb, mint korábban volt. Tehát hány lépést tettem van, hogy a következő alkalommal? 14, majd 13, majd 12, plusz pont, dot, dot, amíg én maradt csak egy. Tehát most egy számítógép tudós lenne kérni, illetve, hogy mit csinál, hogy minden egyenlő? Ez tulajdonképpen megegyezik néhány konkrét szám, amit minden bizonnyal do számtanilag, de szeretnénk beszélni hatékonyságáról algoritmusok egy kicsit formulaically, független, milyen hosszú a lista. 

És tudod mit? Ez 16, de mint már mondtam, hívjuk csak a méret a probléma n, ahol n jelentése egyes számot. Lehet, hogy 16, talán három, talán egy millió. Nem tudom. Nem érdekel. Amit igazán szeretnék, a képlet, hogy én is használja összehasonlítani ezt az algoritmust szemben más algoritmusok hogy valaki igényt jobb, vagy rosszabb. 

Így kiderül, és csak tudjuk ezt a általános iskolában hogy ez tényleg működik ki az ugyanazon dolog, mint n keresztül n, plusz egy több mint kettő. És ez történik, hogy egyenlő, a Természetesen n négyzetes plusz n két. Tehát, ha akartam formula hány lépést vettek részt néztem az összes ezeket a számokat, újra és újra és újra és újra, azt mondanám, ez n négyzetes plusz n két. De tudod mit? Ez csak úgy néz ki rendetlen. Csak nagyon szeretnék egy Általános értelemben a dolgok. És lehet előhívni középiskolában, hogy ez a fogalom legmagasabb rendű távon. Amely ezeket a feltételeket, a n négyzete, a N vagy a felét, van a legnagyobb hatása az idő múlásával? Minél nagyobb n kap, amely Ezen ügyek leginkább? 

Más szavakkal, ha azt dugja egy millió, n négyzetes lesz a legvalószínűbb az uralkodó tényező, mert milliószor maga egy sokkal nagyobb mint eggyel több millió. Szóval tudod mit? Ez egy ilyen rohadt nagy számot, ha tér egy számot. Ez nem igazán számít. Mi csak a határokat átlépő, hogy ki, és felejtsd el. És így egy számítógép tudós azt mondaná hogy a hatékonyságot ezen algoritmus van a sorrendben a N squared-- Úgy értem igazán közelítés. Ez a fajta durván n négyzeten. Idővel, a nagyobb és nagyobb n lesz, ezt egy jó becslés, amit a hatékonyságát, illetve a hatékonyság hiánya az algoritmus valójában. És azt levezetni, hogy persze, re valójában csinál a matek. De most csak integetett kezem, mert én csak szeretnék egy általános értelemben az algoritmus. 

Tehát ugyanazt a logikát, eközben nézzük meg egy másik algoritmust már látszott figyeléssel lineáris keresés. Amikor kerestem A telefon book-- nem válogatás, keres telefonon keresztül book-- azt hajtogatta, hogy ez 1000 lépéseket, vagy 500 lépésre. De nézzük, hogy általánosítani. Ha van n oldalak A telefonkönyv, mi A futási idő vagy a hatékonyságát lineáris keresés? Ez a sorrend hány lépés, hogy megtalálják Mike Smith lineáris keresés, a első algoritmus, vagy akár a második? 

A legrosszabb esetben, Mike a végén a könyv. Tehát, ha a telefon könyv 1000 oldal, mondtuk legutóbb, a legrosszabb esetben, ez eltarthat körülbelül mennyi sok oldalt találni Mike? Mint 1000. Ez egy felső korlátot. Ez egy lehető legrosszabb helyzetben. De ismétlem, mi távolodik számokról, mint 1000 most. Ez csak n. 

Tehát mi a logikus következtetést? Megtalálása Mike egy telefon könyv, amely n oldalak eltarthat, a legrosszabb esetben, hány lépés a sorrendben n? És valóban egy számítógépes tudós azt mondaná hogy a futási idő vagy a teljesítmény, illetve a hatékonyság vagy eredménytelensége, az algoritmus, mint a lineáris keresés a sorrendben N. És mi is ugyanezt a logikája átkelés valamit ahogy én csináltam, hogy a második algoritmus volt a telefonkönyvben, ahol mentünk két oldalt egy időben. 

Tehát 1000 oldal telefonkönyv talán minket 500 lapozás, plusz egy megduplázásuk vissza egy kicsit. Tehát ha egy telefonkönyv n oldalt, de csinálunk két oldalt egy időben, Ez nagyjából mi? N két, úgy, hogy olyan, mint n két. De tettem a követelés a perce, hogy n keresztül two-- ez a fajta ugyanaz, mint csak n. Ez csak egy állandó tényezőt, számítógépes szakemberek azt mondják. Nézzük csak összpontosítani változók, really-- a legnagyobb változó az egyenletben. 

Tehát a lineáris keresés, legyen az egy oldal egy időben, vagy két oldalt egy időben, egyfajta alapvetően ugyanaz. Még mindig a sorrendben n. De én azt állította képem korábbi hogy a harmadik algoritmus nem volt lineáris. Nem volt egy egyenes vonal. Úgy volt, hogy görbe vonal, és a algebrai képlet volt, mi? Belépés a n-- így alapú logaritmus két n. És nem kell bemenni túl sokkal részletesebben a logaritmus ma, de a legtöbb számítógépes szakemberek nem még mondani, mi a bázis. Mert ez az egész csak állandó tényező, hogy úgy mondjam, Csak enyhe numerikus különbségeket. És így ez egy nagyon gyakori módja különösen hivatalos számítógépes tudósok egy tábla vagy programozók egy fehér tábla valójában arra hivatkozva, amely algoritmus fogják használni vagy mi a hatékonyság az algoritmus. 

És ez nem feltétlenül valami megbeszélitek, hogy bármilyen nagy részletességgel, de egy jó programozó valaki akinek van egy szilárd, hivatalos háttérrel. Ő képes beszélni Önnek ez a módja és valóban kvalitatív érveket hogy miért egy algoritmust vagy Egy szoftver kiváló valamilyen módon a másikba. Mert akkor minden bizonnyal csak futni egy ember programja és számolja a másodpercek száma kell ahhoz, hogy rendezni néhány számot, és lehet futtatni néhány más személy programja és számolja másodpercek tart. De ez egy általánosabb módon, hogy akkor elemezni algoritmusok ha úgy tetszik, csak papír vagy csak szóban. Anélkül, hogy fut, anélkül, hogy is próbál mintát bemenet, ha csak érvelni rajta. És így a bérleti fejlesztő vagy ha amelynek neki valami azt állítják, hogy Ön Ezért azok algoritmus, a titkos szósz keres milliárdokat A weboldalakat cég jobb, ezek azok a fajta érveiket ideális esetben képes. Vagy legalábbis ezek a dolgokat hogy jön fel a vitát, a Legalább egy nagyon formális vitát. Rendben. Tehát Ben javasolt valamit nevezett kiválasztás sort. De fogom javasolni, hogy ott van Más módon teheti ezt is. Amit nem igazán tetszik körülbelül Ben algoritmus hogy ő csak ment tovább, vagy Miután nekem járni, oda-vissza és oda-vissza, és oda-vissza. Mi lenne, ha inkább én is csinálni olyasmi, mint ezek a számok itt és én csak kezelni az egyes száma viszont ahogy én adtam azt? 

Más szavakkal, itt én számok listája. Négy, egy, három, kettő. És fogok csinálni a következő. Megyek illessze be a számokat ahová tartoznak, hanem mint kiválasztja azokat egyesével. Más szavakkal, itt a négyes szám. 

Itt az eredeti listán. És én fogom fenntartani lényegében egy új lista itt. Tehát ez a régi lista. Ez az új listát. Látom a négyes első. Az új lista kezdetben üres, így triviális esetében hogy négy most válogatott lista. Én csak figyelembe a számot én adott, és én üzembe azt az új lista. 

Ez az új lista sorrendje? Igen. Ez hülye, mert csak egy van elem, de ez teljesen rendezve. Nincs semmi a helyén. Ez érdekes, ez az algoritmus, mikor léphet a következő lépésre. 

Most van egy. Tehát az egyik természetesen tartozik a elejére vagy végére ennek az új lista? A kezdet. Szóval van, hogy némi munkát most. Már vesz néhány szabadságjogok én marker mindössze rajz dolgokat ahol akarom őket, de ez nem igazán pontos a számítógépen. Egy számítógép, mint tudjuk, van RAM, vagy a Random Access Memory, és ez az egyik bájt byte másik byte. És ha van egy gigabájt RAM, van egy milliárd bájt, de ők fizikailag egy helyen. Nem lehet csak mozgatni dolog körül támaszkodva a táblára ahova akarod. Tehát, ha az új listának négy helyszínen a memóriában, sajnos a négyes Már a rossz helyen. 

Tehát, hogy helyezze az első számú Nem tudom csak felhívni itt. Ez a memória hely nem létezik. Ez lenne csalás, és én már csaló képileg néhány percig itt. Tehát valóban, ha azt szeretnénk, hogy egy van, Meg kell ideiglenesen másolja a négy majd tegye az ott. 

Ez rendben van, így van, ez technikailag lehetséges, de észre, hogy ez plusz munkát. Nem csak fel a számot a helyére. Először meg kellett mozgatni számot, majd tegye a helyére, úgyhogy egyfajta megduplázta mennyiségű munkát. Így tartsa szem előtt. 

De én most történik ez az elem. Most azt akarom, hogy megragad a hármas szám. Ahol természetesen nem is tartozik? Közte. Nem tudok csalni többé és csak tedd oda, mert megint ez a memória a fizikai helyszíneken. Tehát azt kell másolni a négy és tegye a három ide. Nem nagy ügy. Ez csak egy plusz lépést again-- úgy érzi, nagyon olcsó. 

De most már lépni a kettő. A két, természetesen, ide tartozik. Most kezd látni, hogyan a munka felhalmozódik. Most mi kell még tenni? Ja, azt meg kell mozgatni a négy, Aztán kell másolni a három, és most helyezze be a kettő. És a fogás ezzel algoritmus, érdekes módon, az, hogy tegyük fel, hogy van egy szélsőségesebb Amennyiben ez mondjuk nyolc, hét, hat, öt, négy, három, kettő, egy. Ez, számos helyzetben, A legrosszabb forgatókönyv esetén, mert a rohadt dolog szó visszafelé. 

Nem igazán hatással Ben-algoritmust, mert Ben kiválasztási rendezés ő fog tartani oda-vissza végig a listát. És mert mindig keresi az egész fennmaradó lista, nem számít ahol az elemek. De ebben az esetben az én behelyezése approach-- próbáljuk meg. 

Tehát egy, kettő, három, négy, öt, hat, hét, nyolc. Egy kettő három négy, öt, hat, hét, nyolc. Megyek, hogy a nyolc, és hová tegyem meg? Nos, az elején listámon, mert ez az új lista. És én áthúzáshoz. 

Hova tegyem a hét? A fene egye meg. El kell menni oda, így Van némi másolás. És most a hét megy itt. Most lépni a hat. Most még több munka. 

Nyolc olyan, hogy megy itt. Hét van, hogy megy itt. Most a hat mehet itt. Most fogd az öt. Most nyolc van, hogy menjen Itt hét van, hogy megy itt, Hat van, hogy megy itt, és most öt és ismételje meg. És én elég sokat mozgatja folyamatosan. 

Így a végén, ez algorithm-- fogunk hívják behelyezés sort-- ténylegesen van egy csomó munka is. Ez csak a különböző a fajta munka, mint Ben. Ben munkája volt nekem megy oda-vissza minden alkalommal, kiválasztja a következő legkisebb elem újra és újra. Így volt ez a nagyon vizuális fajta munka. 

Ez a másik algoritmus, amely még mindig correct-- ez lesz a feladat done-- csak megváltoztatja a munka mennyiségét. Úgy néz ki, kezdetben maga mentés, mert te csak foglalkozik az egyes elemek elöl nélkül séta az az utat a listán, mint Ben. De a probléma, különösen ezekben őrült az esetben, ha ez az egész visszafelé, te csak egyfajta elhalasztása a kemény munka amíg van kijavítani a hibákat. 

És így ha lehet ezt elképzelni Nyolc hét, illetve hat és öt majd négy és három és két mozgó útjukat végig a listán, éppen most változott a típusú munkát csinálunk. Ahelyett, hogy azt a kezdve az én iteráció Én csak csinálom a végén minden iteráció. Így kiderül, hogy ez az algoritmus, is, általában az úgynevezett beillesztés sort, is a sorrendben n négyzeten. Ez valójában nem jobb, nem jobb egyáltalán. 

Azonban van egy harmadik megközelítés Azt javasoljuk, hogy megvizsgáljuk, ami ezt. Tegyük fel, hogy a listát, az egyszerűség kedvéért ismét, négy, egy, három, two-- csak négy számot. Ben már jó intuíció, jó emberi intuíció előtt, ami által rögzített teljes list eventually-- beillesztés sort. Azt coaxed minket. De nézzük meg a legegyszerűbb módja annak, hogy erősít ez a lista. 

Ez a lista nincs rendezve. Miért? Az angol, miért ez valójában nem rendezve. Mit jelent, hogy nem lehet válogatni? 

DIÁK: Ez nem szekvenciálisan. 

DAVID MALAN: Nem szekvenciálisan. Mondj egy példát. 

DIÁK: Tedd őket sorrendben. 

DAVID MALAN: OK. Adj egy konkrét példa. 

DIÁK: Növekvő sorrendben. DAVID MALAN: Nem növekvő sorrendben. Pontosabban. Nem tudom, mit jelent a növekvő. Mi a baj? 

DIÁK: A legkisebb a számok nem az első helyet. 

DAVID MALAN: legkisebb számot a Nem az első helyet. Konkrétabb. Kezdek fogás. Számítunk, de mi elromlott itt? 

DIÁK: Numerikus sorrendben. DAVID MALAN: Numerikus sorrendben. Mindenki egyfajta vezetése ez here-- nagyon magas szinten. Csak szó mondja meg, mi van rossz, mint egy öt éves erejét. 

DIÁK: plusz egy. 

DAVID MALAN: Mi ez? 

DIÁK: plusz egy. 

DAVID MALAN: Mit jelent plusz egy? Adj egy másik öt éves. Mi a baj, anya? Mi a baj, apa? Mit jelent ez nincs rendezve? 

DIÁK: Ez nem a megfelelő hely. 

DAVID MALAN: Mi nem a megfelelő helyen? 

DIÁK: Négy. DAVID MALAN: OK, jó. Tehát négy nem, ahol lennie kellene. Különösen ez igaz? Négy és egy, az első Két szám látok. Ez igaz? Nem, ők elromlott, nem igaz? Sőt, úgy gondolja most körülbelül egy számítógép is. Ez csak akkor nézd meg, talán egy, talán két dolgot once-- és valójában csak egy dolog egy időben, de lehet legalább nézd meg egy dolog, akkor a következő dolog közvetlenül mellette. 

Tehát ezek érdekében? Természetesen nem. Szóval tudod mit? Miért nem veszünk baba lépéseket a probléma elhárításán ahelyett, hogy ezeket a díszes algoritmusok, mint Ben, ahol ő egyfajta rögzítése által átkötése a listán ahelyett, hogy amit tettem, ahol Én csak ilyen fix, hogy ahogy haladunk? Nézzük csak a szó szoros értelmében lebontják fogalma order-- számsorrendben nevezni, amit want-- ezekbe páros összehasonlítás. 

Négy és egy. Ez a helyes sorrendben? Tehát lássuk javítani. Egy és négy, majd akkor csak másolja. Rendben, jó. Én fix, egy és négy. Három és két? Nem. Legyen az én szó egyezik az ujjaim. Négy és három? 

Ez nem azért, úgyhogy megyek hogy nem egy, három, négy, kettő. Ok, rendben. Most négy és kettő? Meg kell, hogy erősít ez is. Tehát egy, három, kettő, négy. Így van ez válogatni? Nem, de ez közelebb válogatni? 

Igen, mert a mi fix ezt hibát javítottuk ezt a hibát, és fix ezt a hibát. Tehát rögzített három hibák vitathatatlanul. Még nem igazán néz ki a rendezett, de objektíve közelebb sorba rendezett mert fix néhány ilyen hibákat. 

Most mi a teendőm? Valahogy a végére ért a listán. Úgy tűnt, hogy fix a hibákat, de nem. Mivel ebben az esetben bizonyos számok Lehet, hogy lassan kialakult szorosabb más számokat még elromlott. Tehát lássuk újra, és én csak csináld helyett ebben az időben. Egy és három? Rendben van. Három és két? Természetesen nem, úgyhogy változtatni. Tehát kettő, három. Három és négy? És most nézzük csak lehet Különösen pedáns itt. Vajon rendezve? Ti emberek tudják, ez rendezve. 

Meg kell próbálni újra. Tehát Olivia javasolja megpróbálom újra. Miért? Mivel a számítógép nem rendelkezik A luxus a mi emberi szem csak nézett back-- OK, kész vagyok. Hogyan működik a számítógép határozza meg hogy a lista most rendezett? Mechanikusan. 

Azt kell átmenni még egyszer, és csak akkor, ha nem tesznek / valamilyen hibára tudok majd kötni, mint a számítógép, aha, vagyunk jó menni. Tehát egy és két, két és három, három és négy. Most már véglegesen mondják, hogy ez válogatni, mert nem tett változások. Most lenne egy hiba, és csak ostoba, ha a számítógépet, Megkérdeztük a ugyanazokat a kérdéseket újra várta különböző válaszokat. Nem történhet meg. 

És így most a lista. Sajnos, futási ideje ez az algoritmus is n négyzeten. Miért? Mert van n számokat, és a legrosszabb esetben meg kell mozgatni n számok n-szer, mert meg kell tartani fog vissza, hogy ellenőrizze és potenciálisan erősít ezeket a számokat. És nem tehetünk egy formai elemzése is. 

Tehát ez az egész, hogy azt mondják, amit tett Három különböző megközelítések egyike Ezekről azonnal intuitív kapásból Ben az általam javasolt beillesztése sort egy ehhez ahol a fajta szabad szem elől téveszteni Az erdőben a fák kezdetben. De akkor, ha egy lépést hátra, íme, kijavítottuk a rendezési fogalom. Tehát ez, mer mondani, egy alacsonyabb szinten talán mint néhány ilyen egyéb algoritmusok, de most hátha nem tudjuk elképzelni ezek útján ezt. 

Tehát ez nagyon szép szoftver, hogy valaki írta segítségével színes sávok, ami fog tenni a következő számunkra. Mindegyik rúd számot jelent. Taller bárban, a nagyobb a szám, annál kisebb a bárban, Minél kisebb a szám. Tehát ideális esetben szeretnénk egy szép piramis ahol kezdődik a kis és nagy lesz, és hogy azt jelentené, hogy Ezek a sávok vannak rendezve. Így fogok menni előre, és válassza ki, például Ben algoritmus first-- kiválasztás sort. 

És észre, mit csinál. Az, ahogyan azt választotta, hogy vizualizálni ezt az algoritmust hogy, mint én séta listámon, ez a program sétál révén számok listája, kiemelve rózsaszín minden szám, amely azt nézi. És mi fog történni most? 

A legkisebb szám, amely I. vagy Ben találtam hirtelen gets költözött a lista elejére. És vegyük észre, ők elkergeti a számot, hogy ott volt, és ez tökéletesen megfelel. Nem bejutni, hogy részletességgel. De meg kell tenni ez a szám valahol, így csak át azt a nyitott helyre jött létre. Így fogom gyorsítani fel, mert különben lesz nagyon unalmas gyorsan. Animáció célozza meg is vagyunk. Tehát most ugyanezt az elvet Azt alkalmazása, de lehet kezdeni, hogy úgy érzi, az algoritmus, ha lesz, vagy nézzük meg egy kicsit tisztábban. És ez az algoritmus az a hatása, kiválasztja a következő legkisebb eleme, így fogsz kezdeni látni rámpa fel a bal oldalon. És minden iterációban, ahogyan azt javasolt, mégis egy kicsit kevesebb munka. Nem kell menni egészen vissza a bal a lista végére, mert már tudja, hogy azok vannak rendezve. Tehát ez a fajta érzés, mintha gyorsuló, bár mindegyik lépés figyelembe ugyanannyi idő alatt. Már csak kevesebb lépésben megmaradt. És most akkor milyen érezni a algoritmus megtisztítása a vége, sőt most már rendezve. 

Tehát behelyezés rendezés mindezt. Azt, hogy újra kell véletlenszerű a tömbben. És észre tudok csak tartsa randomizing azt, és mi lesz közelítése Ugyanezt a megközelítést, beillesztés sort. Hadd lelassítják itt. Kezdjük a dolgot. Állj meg. 

Hagyjuk négy. Ott vagyunk. Véletlenszerű azok tömb. És itt go-- beillesztés sort. Játszani. Figyeljük meg, hogy ez foglalkozik az egyes elem találkozik rögtön, de ha ez tartozik rossz helyen közlemény az egész munkát, hogy meg kell történnie. Meg kell tartani változó több több eleme, hogy helyet Az egyik akarunk bevezetni. 

Tehát mi összpontosítva elhagyta a lista végére csak. Figyeljük mi még nem is nézett figyeléssel mi nem kiemelt rózsaszín semmit jobbra. Mi csak foglalkozik A probléma, ahogy haladunk, De mi hozzuk létre a sok dolgozni magunk is. És így, ha ezt felgyorsíthatja Most megy a befejezésig, van egy másik úgy érzi, hogy ez valóban. Ez csak összpontosítva a bal végén, de ezzel egy kicsit több munkát, mint needed-- fajta elsimítani felett, rögzítő dolgokat, de foglalkozunk végső soron minden elem egyesével amíg eljutunk the-- jól, mi mindannyian tudjuk, hogy ez lesz a vége, így ez egy kicsit underwhelming talán. 

De a lista a end-- spoiler-- fog rendezni. Tehát nézzük meg egy utolsó. Nem csak most kihagyja. Már majdnem ott vagyunk. Két menni, az egyik megy. És íme. Kiváló. 

Tehát most lássuk egy utolsó, újra randomizing buborék sort. És észre, főként, ha azt lassú ez le, ez folyamatosan lecsapó keresztül. De észre ez csak teszi páronként comparisons-- egyfajta helyi megoldásokat. De amint megkapjuk Az a lista végén rózsaszín, mi lesz, hogy újra megtörténjen? Igen, ez lesz, hogy kezdeni, hiszen csak fix páros hibákat. És ez talán kiderült még mások. És így ha ezt felgyorsíthatja, akkor látni, hogy mennyi a neve is mutatja, A kisebb elements-- vagy inkább A nagyobb elements-- kezdik buborék fel a csúcsra, ha úgy tetszik. És a kisebb elemek kezd buborék lefelé a bal oldalon. És valóban, ez a fajta a vizuális hatás is. És így ez lesz a vége befejező egy nagyon hasonló módon is. 

Nem kell lakni ezen a bizonyos egy. Hadd nyissa meg ezt most is. Van néhány más rendezési algoritmusok a világon, néhány, amely elfogják itt. És különösen a tanulók, akik nem szükségképpen vizuális vagy matematikai, mint azelőtt, tudjuk is ezt audially ha társítani a hangot ezzel. És csak a móka kedvéért, itt egy Néhány különböző algoritmusok, és egyikük különösen te fog észrevenni az úgynevezett "egyesítés sort." 

Ez valójában egy alapvetően jobb algoritmust, oly módon, hogy egyesíti a fajta, az egyik az is fogsz látni, nem sorrendben n négyzeten. Ez a sorrend n-szer napló N, ami valójában kisebb, és így gyorsabb, mint a másik három. És van egy pár más buta is, hogy majd meglátjuk. 

Tehát itt vagyunk néhány hang. Ez beillesztés sort, így ismét ez csak foglalkozik az elemeket ahogy jönnek. Ez a fajta buborék, így figyelembe véve azokat párok egy időben. És ismét, a legnagyobb elemei vannak bugyogott fel a csúcsra. 

Következik kiválasztás sort. Ez Ben-algoritmust, ahol ismét ő adja iteratív A következő legkisebb eleme. És ismét, most már tényleg hallani, hogy ez felgyorsítja, de csak annyiban, amennyiben mivel csinál kevésbé dolgozni minden iterációban. Ez a gyorsabb, összeolvad sort, amely válogatás klaszterek számát együtt, majd egyesíti őket. Tehát look-- bal fele már rendezve. 

Most ez a válogatás a jobb oldalát, és most ez lesz, hogy összekapcsolják őket egy. Ez egy úgynevezett "Gnome sort." És akkor milyen látni, hogy ez megy oda-vissza, rögzítő munka egy kicsit itt és ott mielőtt megkezdené az új munkát. És ez az. Van egy másik fajta, ami tényleg csak tudományos célokra, az úgynevezett "buta sort", amely úgy Adatai rendezi meg véletlenszerűen, majd leellenőrzi, hogy van rendezve. És ha ez nem, akkor újra rendezi It véletlenszerűen ellenőrzi, hogy ez rendezve, és ha nem ismétlődik. És elméletileg véletlenszerűen ez a teljes, de miután egy kicsit az időben. Ez nem a leginkább hatékony algoritmusok. Tehát bármilyen kérdése azokon Különösen algoritmusok vagy bármi kapcsolódó ott is? 

Nos, most már ugratni egymástól, mi minden ezek a vonalak, hogy én már rajz és amit én feltételezve, hogy a számítógép tehet a motorháztető alatt. Azt állítják, hogy az összes ezeket a számokat Folyton drawing-- hogy szükséged van tárolni valahol a memóriában. Majd megszabadulni ez a srác most is. 

Tehát egy darab memória egy computer-- így RAM DIMM amit keresett tegnap, kettős belső memória module-- néz ki. És minden egyes ilyen kis fekete chipek néhány byte-ok száma, jellemzően. És akkor az arany csapok, mint a vezetékek csatlakoztassa a számítógéphez, és a zöld szilícium tábla csak mit tart mindent együtt. Tehát mit jelent ez valójában? Ha valahogy felhívni a ugyanazt a képet, Tegyük fel az egyszerűség kedvéért hogy ez a DIMM, dual inline memória modul, egy gigabájt RAM-mal, egy gigabájt memória, ami hány bájt összesen? Egy gigabájt hány bájt? Több annàl. 1124 az kilo, 1000. Mega millió. Giga egy milliárd. 

Vagyok hazudik? Tudunk még olvasni a címkét? Ez valójában 128 gigabyte, így tovább. De majd, mintha ez csak egy gigabájt. Tehát ez azt jelenti, van egy milliárd byte memóriát elérhető számomra vagy 8 milliárd bit, de megyünk beszélni szempontjából byte most, haladni előre. 

Tehát mit jelent az, hogy ez Egy bájt, ez egy másik byte, ez egy másik byte, és ha igazán akart egyedinek mi lett volna felhívni egymilliárd kis négyzetek. De mit jelent ez? Nos, hadd zoom az ezen a képen. Ha van valami, hogy úgy néz ki, mint ez most, ez a négy bájt. 

És így tudtam tenni négy szám van. Egy kettő három négy. Vagy akár fel négy betű vagy szimbólum. "Hé!" mehet ott, mert az egyes betűk, korábban beszéltünk, ábrázolható Nyolc bit vagy ASCII vagy egy bájt. Más szóval, akkor tegye 8000000000 dolog benne Ennek az egy bottal a memória. Most ez mit jelent, hogy a dolgokat vissza hogy háttal a memóriában, mint ez? Ez az, amit a programozó neveznék egy "tömbben". Egy számítógépes program, akkor nem hiszem, a mögöttes hardver önmagában. Te csak gondolsz magadra, mint amelyek hozzáférést egy milliárd byte teljes, és akkor bármit akarsz vele. De az egyszerűség kedvéért sokszor hasznos megtartani a memória jobb egymás mellett, mint ez. Tehát ha Ráközelíthetek this-- mert mi biztosan nem fog felhívni egymilliárd kis squares-- Tegyük fel, hogy ez a testület képviseli hogy bottal a memória most. És én csak felhívni annyi, mint a marker végül, hogy nekem itt. Tehát most van egy bot A memória a fedélzeten hogy van egy, kettő, három, négy, öt, hat, egy, kettő, három, négy, öt, hat, seven-- így 42 byte memória a képernyőn teljes. Köszönöm. Igen, nem az én aritmetikai jobbra. Tehát 42 bájt memóriát itt. Mit is jelent ez valójában? Nos, egy számítógép programozó valójában általában gondolni ezt emlékezet címezhető. Más szóval, minden ilyen helyek memóriájában, a hardver, egyedi címmel rendelkezik. 

Ez nem olyan bonyolult, mint egy Brattle Square, Cambridge, Mass., 02.138. Ehelyett csak egy szám. Ez bájtos szám nulla, ez az egy, ez két, ez a három, és ez a 41. Várj egy percet. Azt hittem, azt mondta, 42 perccel ezelőtt. Elkezdtem számolni nulla, így valójában helyes. Most nem kell ténylegesen rajzolni mint egy rács, és ha rajzolni, mint a rács Azt hiszem, a dolgok valóban egy kicsit félrevezető. Mi egy programozó lenne, a saját szem előtt tartva, Általában úgy gondoljuk, ennek az memória, olyan, mint egy szalag, mint egy darab szalaggal hogy csak megy, és a végtelenségig vagy amíg elfogy a memória. Így egy sokkal gyakoribb módon felhívni és gondoljunk csak a memória lenne, hogy ez a bájt nulla, egy, kettő, három, majd pont, pont, pont. És van 42 ilyen bájt teljes, még bár fizikailag is veszélybe valami több, mint ez. 

Tehát ha most úgy a memória, mint ez, mint egy szalag, ez az, amit a programozó újra nevezném tömb memória. És ha azt szeretné, hogy ténylegesen készlet valamit a számítógép memóriájában, Ön általában nem tárolja a dolgokat back-to-back to back-to-back. Tehát mi már számokról beszélünk. És amikor akartam megoldani a problémákat mint négy, egy, három, kettő, bár én csak rajz Csak a számok négy, egy, három, két a táblán, a számítógép lenne tényleg ez a beállítás a memóriában. 

És mi lesz a következő, hogy a kettő a számítógép memóriájában? Nos, nincs válasz. Nem igazán tudom. És olyan hosszú, mint a számítógép nem kell azt, nem kell törődni, mi mellett A számok igen törődik. És amikor azt mondta korábban, hogy a számítógép Csak nézd meg egy címet, egy időben, ez a fajta, hogy miért. 

Nem eltérően rekord lejátszó és egy olvasó fej csak, hogy képes nézni egy bizonyos groove fizikai old-school rekord egy időben, hasonlóképpen lehet egy számítógép köszönhetően a CPU és Intel utasításkészlet, között, amelynek használati olvasni a memóriából vagy mentse memory-- egy számítógép csak nézd az egyik helyen egy time-- Néha ezek kombinációja, de tényleg csak egy helyen egy időben. Tehát, ha csinálunk A különböző algoritmusok, Én nem csak az írás a vacuum-- négy, egy, három, kettő. Ezek a számok valójában tartozik valahol a fizikai memória. Tehát vannak apró tranzisztorok, vagy valamilyen az elektronika alatt motorháztető tárolására ezeket az értékeket. 

És összesen hány bitet részt most, csak hogy világos? Tehát ez a négy bájt, vagy most már 32 bit összesen. Tehát vannak valójában 32 nullákkal azok alkotó ezt a négy dolgot. Van még itt, de megint nem érdekel. 

Tehát most kérdezzük meg a másik kérdés a memória, mert, hogy a végén A nap a variancia. Nem számít, mit tehetünk a A számítógép, a végén a nap a hardver még mindig a ugyanaz a motorháztető alatt. Hogyan tudom tárolni egy szót itt? Nos, egy szó, egy számítógép, mint a "Hé!" kellene tárolni, mint ez. És ha volna egy hosszabb szó, akkor egyszerűen felülírja ezt, és azt mondják, valami mint a "hello", és tárolja, hogy itt. 

És így itt is, ez contiguousness valójában előny, mert a számítógép már csak jobbról balra. De itt van egy kérdés. Ebben az összefüggésben a szó, H-E-L-L-O, felkiáltójel, hogyan lehet a számítógép tudja, hol a szó kezdődik és hol végződik a szó? Az összefüggésben számok, hogyan működik a számítógép tudom, milyen hosszú a sorrend számok vagy hol kezdődik? Nos, kiderült out-- és nem megyünk túl sokat ebbe szintje detail-- számítógépek mozog dolog körül a memóriában szó útján ezeket a címeket. Tehát egy számítógép, ha kód írása tárolni dolgokat mint a szavak, amit te tényleg csinál gépel kifejezések, amelyek megjegyzik, ahol a A számítógép memóriája ezek a szavak. Tehát hadd csinálni egy nagyon, nagyon egyszerű példát. 

Megyek megy előre, és nyit egy egyszerű szöveges programot, és megyek, hogy hozzon létre nevű fájlt hello.c. Ezen információk többsége azt Nem megyek bele a részletekbe menően, de fogok írni egy programot, hogy ugyanazon a nyelven, C. Ez sokkal megfélemlítő, Azt állítani, mint Scratch, de ez nagyon hasonlít a szellem. Valójában ezek a göndör braces-- akkor milyen gondolni, amit én csináltam, mint ez. 

Csináljuk, valóban. Amikor zöld zászló kattint, tegye a következőket. Szeretnék kinyomtatni "hello". Tehát ez most pszeudokód. Én fajta összemosódnak a vonalak. A C-ben, ezen a nyelven beszélek körülbelül ez a sor nyomtatási szia valóban lesz "printf" a Néhány zárójelben, és pontosvessző. 

De ez pontosan ugyanaz a gondolat. És ez nagyon felhasználóbarát "Amikor a zöld zászló kattintott" válik a sokkal misztikus "int main semmis." És ez tényleg nincs feltérképezése, úgyhogy csak fog figyelmen kívül. De a kapcsos zárójelek, mint a ívelt puzzle darab, mint ez. 

Így a fajta kitalálni. Akkor is, ha soha nem beprogramozott, mit jelent ez a program valószínűleg nem? Valószínűleg kinyomtatja szia felkiáltójellel. 

Úgyhogy próbáljuk ezt. Megyek megmenteni. És ez ismét egy nagyon régi iskolai környezetben. Nem tudok rákattintani, én nem húzza. Van parancsokat. Szóval azt akarom, hogy fut a program, így Talán ezt, mint hello.c. Ez a fájl futottam. De várjunk csak, én eltűnt egy lépést. Mit is mondtunk szükséges lépés a nyelv, mint a C? Most írott forrás kódot, de mit kell tennem? Igen, kell egy fordító. Tehát az én Mac itt van egy nevű program GCC, GNU C fordító, amely lehetővé teszi, hogy tegyek this-- viszont én forráskódot, hívjuk meg, gépi kód. 

És látom, hogy ismét, az alábbiak szerint, ezek a a nullák és egyesek csak készítette az én forráskódját, mind a nullák. És ha azt szeretnénk, hogy futtatni én program-- ez történik hogy hívják a.out számára történelmi reasons-- "hello". Tudok futni újra. Helló helló helló. És úgy tűnik, hogy működik. 

De ez azt jelenti, valahol az én számítógép memóriája a szavak H-E-L-L-O, felkiáltójel. És kiderül, ahogy félre, mi az a számítógép jellemzően Ehhez, hogy tudja, hol a dolgok kezdenek és end-- ez megy, hogy egy speciális szimbólum van. És az egyezmény az, hogy a szám nulla végén egy szó úgy, hogy tudja, hol ténylegesen véget ér, úgy, hogy ne tartsa kinyomtatásával egyre karakterek, mint amit valójában szeretnék. 

De az elvihető, mégha bár ez meglehetősen bonyolult, az, hogy ez végső soron viszonylag egyszerű. Akkor kaptak egyfajta szalag, egy üres hely, amely akkor leveleket. Egyszerűen csak meg, hogy egy speciális szimbólum, mint önkényesen a szám nulla, hogy a végén a szóval, hogy a gép tudja, ó, le kell állítani a nyomtatást követően Látom a felkiáltójel. Mert a következő dolog van egy ASCII értéke nulla, vagy a null karaktert valaki nevezném. De van egyfajta probléma itt, és menjünk visszaállítsák a számok egy pillanatra. Tegyük fel, hogy én nem, sőt, Van egy sor számok, és tegyük fel, hogy a programot írok is mint egy évfolyam könyv egy tanár és a tanárok osztályteremben. És ez a program lehetővé teszi a neki írja be diákjaik pontszámok A vetélkedők. És tegyük fel, hogy a tanuló kap 100 első kvíz, talán mint a 80 a következő, majd a 75, majd 90, a negyedik kvíz. 

Tehát ezen a ponton a történet, a tömb mérete négy. Egyáltalán több memóriát a számítógépet, de a tömb, hogy úgy mondjam, ez a méret négy. Tegyük fel most, hogy a tanár akar hozzárendelni egy ötödik kvíz az osztály. Nos, az egyik dolog, amit vagy ő megy, hogy meg kell csinálni most tárolja további értéket. De ha a tömb a tanár létre ez a program a méret, az egyik probléma egy tömb, amely akkor nem csak folyamatosan növeli a memória. Mert mi van, ha egy másik része a program a "hé" ott? 

Más szavakkal, a memóriát lehet használt semmit a program. És ha előre beírtam, hé, Azt akarom, hogy input négy kvíz pontszámok, lehet, hogy megy itt, és itt. És ha hirtelen meggondolja magát később mondani akarok egy ötödik kvíz pontszámot, akkor nem csak tedd, ahol csak akar, mert mi van, ha ez a a felhasznált memória valami else-- más programot vagy valamilyen más jellemzője a program hogy futsz? Tehát meg kell gondolni előre hogyan szeretné tárolni az adatokat, mert most már festett magát egy digitális sarokban. 

Tehát egy tanár helyett mondjuk írásakor a program tárolására ő évfolyamon, tudod mit? Fogok kérni, írásakor a programot, hogy szeretnék nulla, egy, kettő, három, négy, öt, hat, nyolc évfolyamon összesen. Tehát egy, kettő, három, négy, öt, hat, hét, nyolc. A tanár csak túlzott kiosztani memória írásakor ő programja és azt mondják, tudod mit? Én soha nem fog rendelni több mint nyolc vetélkedők a félévben. Ez csak egy őrült. Soha nem fogom kiosztani ezt. Annak érdekében, hogy ily módon ő is a rugalmasság tárolására pontszámokat, mint 75, 90, és talán egy plusz, ha A diák kapott extra hitel, 105. 

De ha a tanár nem használja a három terek, van egy intuitív elvihető itt. Ő csak kiesik hely. Más szóval, van ezen közös kompromisszum programozás ahol akár kiosztani Pontosan annyi memóriát, amennyit csak akar, A fejjel, amely az, hogy te szuper efficient-- te nem vagy pazarló A all-- de a hátránya az, amely amit ha meggondolja magát, amikor A program használata, hogy a tárolni kívánt több adatot, mint eredetileg tervezte. 

Így talán az a megoldás, akkor írja meg programokat olyan módon hogy több memóriát használ mint amennyi valójában szükséges. Így nem mész befut a problémát, De Te pazarló. És minél több memóriát a program által használt, ahogy megbeszéltük tegnap, a kevésbé memória, amely elérhető más programok, Az előbb a számítógép lelassulhat le, mert a virtuális memóriát. És így ideális megoldás lehet, hogy mi? 

Under-elosztásának tűnik rossz. Túlzott elosztásának tűnik rossz. Tehát mi lehet a jobb megoldás? Átcsoportosítása,. Sokkal dinamikusabb. Ne erőltesse magát, hogy válasszon egy priori, az elején, hogy mit akar. És biztos, hogy nem túl kiosztani, nehogy pazarlás. 

És így, hogy elérjék ezt a célt, kell dobni adatstruktúrát, hogy úgy mondjam, el. És akkor mi van a programozó általában használ az úgynevezett nem tömb, hanem egy láncolt lista. Más szóval, ő lesz elkezd gondolkodni az emléküket mint egyfajta alakja, hogy azok levonhatjuk a következő módon. Ha szeretnék tárolni egy számot Egy program-- így szeptemberben, Megadtam a tanítványaim egy kvíz; Azt akarom tárolja a tanulók első teszt, és van egy 100 it-- I fogom kérni a számítógépet, útján a program, amit írva egy darab memóriát. És én fogom tárolni a száma 100, és ennyi. 

Aztán néhány héttel később mikor kapom meg a második kvíz, és itt az ideje, hogy írja az, hogy 90%, megyek hogy kérje a számítógép, hé, számítógép, lehet még egy darab a memória? Meg fog adni nekem ezt üres darab memória. Azt fogom tenni a szám 90, de az én programban valahogy other-- és akkor nem kell aggódnia A szintaxis this-- szükségem valahogy lánc ezeket a dolgokat együtt. És én láncolni őket együtt ami úgy néz ki, mint egy nyíl van. 

A harmadik kvíz, hogy jön fel, Azt fogom mondani, hé, számítógép, adj még egy darab a memóriát. És én fogom letenni Bármi is volt, mint a 75, és azt kell lánc ezt együtt most valahogy. Negyedik kvíz jön, és talán ez a vége felé a félévben. És ezen a ponton a programot Lehet, hogy a memória az egész hely, az egész fizikailag. És így csak a hecc kedvéért, én fog felhívni a negyedik quiz-- emlékszem, mi volt; én úgy gondolja, talán egy 80 vagy something-- idefelé. 

De ez rendben van, mert képileg Megyek felhívni a vonalat. Más szóval, a valóságban, a számítógép hardver, Az első pont talán kerül ide, mert Rögtön az elején a félévben. A következő, hogy végül itt mert egy kis idő telt el és a program folyamatosan fut. A következő pont, amely 75, lehet itt. És az utolsó pont lehet egy 80, amely több mint itt. 

Így a valóságban, fizikailag, ez lehet amit a számítógép memóriájában néz ki. De ez nem egy hasznos mentális paradigma egy programozó. Miért fontos, ahol a fene az adatok kiöntött? Csak azt, hogy az adatok tárolására. 

Ez olyan, mint a vita korábbi rajz a kocka. Miért érdekel, hogy mit a szög a kocka és hogyan kell fordulni rajzolni? Csak akar egy kocka. Hasonlóképpen, itt csak azt, hogy grade könyvet. Csak azt, hogy úgy gondolja, a ezt a listát a számok. Kit érdekel, hogy milyen ez az megvalósított hardver? 

Tehát a kivételi most ez a kép itt. Ez egy láncolt lista, mint egy programozó nevezném, amennyiben van egy listáját, nyilvánvalóan a számok. De ez kapcsolódik képileg útján a nyilakat, és ezek mind nyilak are-- alatta A motorháztető, ha kíváncsi, Emlékeztetünk arra, hogy a fizikai hardvert címek nulla, egy, kettő, három, négy. Mindezek nyilak olyan, mint egy térkép vagy irány, ahol, ha a 90 is-- most Megvan számolni. 

Nulla, egy, kettő, három, négy, öt, hat, hét. Úgy néz ki, mint a 90 van memóriacím száma hét. Mindezek nyilak jelentése mint egy kis darab papír ami így irány a program, amely azt mondja, kövesse ezt a térképet eljutni helyét hét. És ott meg fogja találni a hallgató második kvíz pontszámot. Eközben a 75-- ha továbbra is ezt, ez hét, nyolc, kilenc, 10, 11, 12, 13, 14, 15. 

Ez a másik nyilat, jelentése Egy térkép memóriahely 15. De ismétlem, a programozó általában nem nem érdekli ez részletességgel. És a legtöbb minden programozási nyelv ma, a programozó Nem is tudom, hol a memóriában ezek a számok valójában. Minden ő kell törődnünk hogy azok valahogy kapcsolódnak egymáshoz egy adatszerkezet, mint ez. 

De kiderül, nem hogy túlságosan technikai. De csak azért, mert talán engedheti meg magának, hogy ezt a vitát itt, tegyük fel, hogy újra ezt a kérdést itt a tömb. Lássuk Sajnálattal megy itt. Ez a 100, 90, 75, és 80. 

Hadd röviden, hogy ezt az állítást. Ez egy tömb, és újra, a legfeltűnőbb jellemzője tömb az, hogy az összes adat vissza háttal memory-- szó Egy bájt vagy talán négy bájt, néhány fix számú byte-re található. A láncolt lista, amit levonhatunk mint ez, a motorháztető alatt, aki tudja, hol van a cucc? Nem is kell, hogy áramlás, mint ezt. Néhány adat lehetne vissza a bal ott. Nem is tudom. 

És így egy sor, akkor a jellemző az úgynevezett véletlen hozzáférésű. És mi véletlen hozzáférésű eszközökkel van hogy a számítógép képes ugrani azonnal bármely részén egy tömbben. Miért? Mivel a számítógép tudja, hogy az első hely nulla, egy, kettő és három. 

És így, ha azt szeretné, hogy megy ez az elem a következő elemre, szó szerint, a számítógép agya, csak adjunk hozzá egy. Ha azt szeretnénk, hogy menjen a harmadik elem, csak add one-- következő elem, csak adjunk hozzá egy. Azonban ez a verzió A történet, tegyük fel, A számítógép jelenleg keresi vagy annak foglalkozó száma 100. Hogyan juthat a következő évfolyamon az évfolyam könyv? 

Meg kell venni a hét lépéseket, ami önkényes. Ahhoz, hogy a következő, meg kell Újabb nyolc lépés, hogy 15. Más szóval, ez nem egy állandó különbség a számok, és így ez csak úgy számítógép több időt a lényeg. A számítógép keresni a memóriában érdekében hogy megtalálja, amit keres. 

Tehát mivel a tömb kezd lenni az adatok gyors structure-- mert szó szerint csak nem egyszerű számtani és kap, ha akar egy hozzáadásával, A instance-- egy láncolt lista, áldozatot, hogy a funkció. Nem lehet csak menni az első a második, harmadik és negyedik. Meg kell, hogy kövesse a térképet. Meg kell venni több lépést hogy azokat az értékeket, amelyek úgy tűnik, hogy egy inflációs. Így fizetünk az ára, de mi volt a jellemzője, hogy Dan keresett itt? Mit csinál egy láncolt lista látszólag lehetővé teszik számunkra, hogy nem, ez volt az eredete ebben a konkrét történetet? 

Pontosan. A dinamikus méretű hozzá. Mi adhat ehhez a listához. Mi is csökken a listán, így hogy mi csak használ annyi memóriát ahogy valójában akar, és így soha nem vagyunk túl elosztásának. 

Most csak az igazán NIT-válogatós, van egy rejtett költség. Szóval nem kell csak hadd meggyőzni Ön, hogy ez egy meggyőző kompromisszum. Van egy rejtett költség itt. Az előny, hogy világos legyen, hogy megkapjuk a dinamizmus. Ha akarok egy másik elem, tudok csak felhívni, és tedd egy szám van. És aztán azt összekapcsolhatja egy képet ide, mivel ide, újra, ha én már festett magam a sarokba, Ha valami más már használja a memória itt, én meg a szerencse. Már festett magam a sarokban. 

De mi a rejtett költség ezen a képen? Ez nem csak az összeg Az hogy mennyi ideig tart menni innen van, amely hét lépésben, majd nyolc lépés, ami több, mint egy. Mi egy rejtett költség? Nem csak időben. További információ eléréséhez szükséges ezt a képet. 

Ja, hogy a térképen, azok a kis darabka papír, ahogy én is leírja őket. Ezek arrows-- azokat nem szabad. A computer-- tudja amit egy számítógép. Meg nullák. Ha azt szeretnénk, hogy képviselje a nyíl, vagy egy térkép vagy egy számot, akkor kell egy kis memóriát. Így a többi árat fizetni egy láncolt lista, közös számítástechnika forrás, szintén helyet. 

És valóban így van, így általában, között a kompromisszumok tervezése szoftverfejlesztés rendszerek időt és space-- kettő a hozzávalókat, két a legköltségesebb összetevőket. Ez olcsóbb több időt mert van, hogy kövesse ezt a térképet, de ez is olcsóbb nekem több helyet mert meg kell tartani ezt a térképet körül. Így a remény, ahogy azt már a fajta megbeszéltük tegnap és ma, az, hogy az előnyök meghaladják a költségeket. 

De nincs egyértelmű megoldást. Lehet, hogy ez better-- a la gyors és piszkos, mint Kareem javasolt earlier-- hogy dobja memória a problémát. Csak vásárolni több memóriát, gondolom kevesebb nehéz erről a probléma megoldásának, és megoldani, hogy egy könnyebb út. És valóban korábban, amikor beszéltünk kompromisszumokat, nem volt hely a számítógép és az időt. Ez volt fejlesztő idő, ami még egy másik forrás. 

Tehát újra, ez Mindezeket mérlegelve próbálta eldönteni, hogy melyek azok a dolgok, vagy hajlandó költeni? Melyik a legolcsóbb? Amelynek eredményeként a jobb eredményeket? Igen? 

Valóban. Ebben az esetben, ha képviselő számok a maps-- ezek az úgynevezett több nyelven "Útmutatását" vagy "címeket" - ez kétszerese a teret. Hogy nem kell olyan rossz, mint a kettős, ha Most mi csak számok tárolása. Tegyük fel, hogy mi volt tárolása beteg nyilvántartás egy hospital-- így Pierson nevek, telefonszámok, társadalombiztosítási számokat, orvos történelem. Ez a doboz lehet sok, sokkal nagyobb, amely esetben Egy apró kis mutató, a címe A következő element-- ez nem egy nagy ügy. Ez egy ilyen béren kívüli költség nem számít. De ebben az esetben, igen, ez megduplázását. Jó kérdés. 

Beszéljünk alkalommal kicsit konkrétabban. Mi a futási idő A keresést a listában? Tegyük fel akartam keresni végig a diákok évfolyamon, és van n fokozat ebben adatszerkezet. Itt is tudunk kölcsönözni a szókincs korábban. Ez egy lineáris adatszerkezet. 

Big O n mi szükséges ahhoz, hogy a végén ez a adatstruktúra, whereas-- és nem láttunk ez before-- tömb ad az úgynevezett konstans idő, ami azt jelenti, egy lépésben vagy két lépésben, vagy 10 steps-- nem számít. Ez egy fix szám. Ennek semmi köze a a méret a tömb. És az oka, hogy a megint, véletlenszerű hozzáférés. A számítógép csak közvetlenül a ugrás egy másik helyre, mert ők mind egyformák távolság minden mást. Nincs gondolkodás szó. Rendben. Tehát, ha tudok, hadd próbálja festék két utolsó kép. Egy nagyon gyakori az úgynevezett hash tábla. Tehát, hogy motiválja ezt a vitát, hadd gondoljon, hogyan kell ezt csinálni. 

Szóval mi a helyzet ez? Tegyük fel, hogy a probléma akarjuk megoldani most hajt végre egy dictionary-- így egy csomó angol szavak vagy mindegy. És a cél az, hogy képes legyen válaszolni kérdések formájában ez a szó? Tehát azt szeretnénk, hogy végre a helyesírás-ellenőrző, csak mint egy fizikai szótár hogy meg lehet keresni dolgokat az. Tegyük fel, hogy én is ezt a tömböt. Tehettem ezt. 

És tegyük fel, a szavak alma és a banán és a sárgadinnye. És nem tudok gondolni gyümölcsök kezdődő d, úgyhogy mi csak megy, hogy három gyümölcsöt. Tehát ez egy tömb, és mi vagyunk tárolására ezeket a szavakat ebben a szótárban, mint egy tömb. A kérdés tehát az, hogy mást lehet tárolni az adatokat? 

Nos, én vagyok a fajta csalás itt, mert mindegyik betűket valóban egyedi bájt. Tehát, ha nagyon akartam lenni nit-válogatós, én tényleg lehet osztani ezt fel sok kisebb darabokat memória, és tudnánk csinálni, hogy pontosan. De megyünk befut ugyanaz a probléma, mint korábban. Mi van, ha a Merriam Webster vagy Oxford nem minden year-- hozzáteszik szavak A dictionary-- mi nem feltétlenül akar festeni magunkat az egyik sarokban egy sor? 

Tehát ahelyett, talán okosabb megközelítés az, hogy az Apple a saját csomópont vagy doboz, ahogy mi mondjuk, banán, és akkor itt van sárgadinnye. És mi húr ezeket a dolgokat együtt. Tehát ez a tömb, és ez a láncolt lista. Ha nem egészen értem, ez csak azt mondja: "array", és ez azt mondja: "listát." 

Tehát ugyanaz pontos kérdések, mint korábban, amellyel most már van dinamizmusa a láncolt lista. De van egy viszonylag lassú szótárban. Tegyük fel, hogy meg akarom nézni egy szót sem. Lehet, hogy nekem nagy O n lépéseket, mert a szó esetleg lennie egészen a végén A lista, mint a sárgadinnye. És kiderül, hogy programozás, sort A szent grál adatok szerkezetek, valami hogy ad állandó idő, mint egy tömb de még mindig ad dinamikát. 

Így tudjuk a legjobb mindkét világból? És valóban, van valami az úgynevezett hash tábla amely lehetővé teszi, hogy pontosan hogy, bár kb. A hash tábla egy szakértő adatszerkezet, hogy mi lehet gondolni, mint a kombinációja egy array-- és fogok rajzolni Így-- és láncolt listák hogy fogom felhívni, mint ez itt. 

És ahogy ez a dolog művek a következő. Ha ez now-- hash table-- az én harmadik adatstruktúra és szeretnék tárolni szóval ebben, én nem szeretnénk, hogy csak tárolja az összes a szavak háttal háttal. Azt akarom, hogy kihasználja néhány darab információ a szó, amely segítségével térjek meg, ahol ez gyorsabb. 

Tehát adott szava alma és a banán és a sárgadinnye, Szándékosan választottam ezeket a szavakat. Miért? Mi a fajta alapvetően különbözik a három? Mi a nyilvánvaló? Kezdik a különböző betűk. 

Szóval tudod mit? Ahelyett, hogy minden az én beszédeimet ugyanazt a vödröt, hogy úgy mondjam, mint egy nagy listát, hogy miért nem Azt legalább próbálni az optimalizálást és hogy az én listák 26/01 mindaddig. A kényszerítő optimalizálás Lehet, hogy miért nem Én-- behelyezésekor egy szó ebbe adatstruktúra, a számítógép memóriájában, hogy miért Nem tettem a 'a' szó van, az összes "b" szó itt, és az összes "C" szó itt? Tehát ez végül véget alma Itt, banán van, sárgadinnye itt, és így tovább. 

És ha van egy további szó, így: mi a másik? Alma, banán, körte. Bárki úgy gondolja, a gyümölcs hogy kezdődik a, b vagy c? Blueberry-- tökéletes. Hogy megy, hogy kerül ide. És így úgy tűnik, hogy van egy marginálisan jobb megoldás, mert most, ha akarom keresni alma, I first-- én nem csak búvár az én adatszerkezet. Nem belevetik magukat a számítógép memóriájában. Először nézd meg az első levelet. 

És ez az, amit egy számítógépes tudós mondaná. Te hash be adatszerkezet. Veszel a bemenet, amely Ebben az esetben van szó, mint az Apple. Te elemezni, nézi az első levél Ebben az esetben, ezáltal hash értékének azt. Hash egy általános kifejezés, amely szerint veszel valamit bemenet és készítsen egy kimenetet. És a kimeneti, hogy esetében az a hely, szeretne keresni, az első helyen, második helyen, a harmadik. Tehát a bemenet alma, a kimenet az első. A bemenet banán, a kimenet legyen a második. A bemenet sárgadinnye, az eredmény a harmadik. A bemenet áfonya, a kimenet ismét második. És ez az, ami segít szedése hivatkozások révén a memória annak érdekében, hogy a szavak vagy az adatok hatékonyabb. 

Most ez lecsökkenti korunk potenciálisan nem kevesebb, mint egy 26-ból, mert ha feltételezzük, hogy annyi "a" szót a "z" szavak, mint a "q" szavakat, amelyek nem igazán realistic-- mész, hogy ferdeség szerte egyes betűket az alphabet-- de ez lenne egy inkrementális megközelítés, amely nem teszi lehetővé teszi, hogy a szavak sokkal gyorsabban. És a valóságban, kifinomult program, a Googles a világ A Facebooks a world-- akkor használja a hash tábla A sok különböző célra. De nem lenne olyan naiv, csak nézd meg az első betű alma vagy banán vagy körte vagy a sárgadinnye, mert mint látható, ezek a jegyzékek még mindig hosszú. 

És így ez talán még a fajta A linear-- így egyfajta lassú, mint a nagy O n hogy a korábban tárgyalt. Tehát mi egy igazi jó hash tábla do-- ez lesz egy sokkal nagyobb tömb. És akkor használja a sokkal kifinomult tördelési funkció, úgy, hogy ne csak nézd meg az "a". Lehet, hogy úgy néz ki, "egy-p-p-l-e", és valahogy átalakítja azokat öt betű a hely, ahol alma kell tárolni. Mi csak naivan az "a" betűt egyedül, mert szép és egyszerű. 

De egy hash tábla, a A végén, akkor úgy gondolja, AS kombinációja egy sor, amelyek mindegyike egy láncolt lista, hogy ideális esetben legrövidebbnek kell lennie, amennyire csak lehetséges. És ez nem kézenfekvő megoldás. Tény, hogy sok a finomhangolás hogy megy a motorháztető alatt, amikor alkalmaz hasonló kifinomult adatstruktúrák az, ami a helyes hossza a tömb? Mi a helyes hash függvény? Hogyan dolgok tárolására a memóriában? 

De hogy milyen gyorsan ez a fajta vita eszkalálódott, sem eddig, hogy ez a fajta A több mint egy feje ezen a ponton, ami rendben van. De elkezdtük, visszahívás, az igazán valami alacsony szintű és elektronikus. És így ez megint ez a téma az absztrakció, ahol ha egyszer elkezd magától nyújtott, OK, megvan it-- van fizikai memóriát, OK, megvan, minden fizikai helyét egy cím, OK, megvan, azt is képviseli ezeket a címeket a arrows-- akkor nagyon gyorsan elindul, hogy kifinomultabb beszélgetések a végén úgy tűnik, hogy lehetővé teszi számunkra, problémák megoldására, mint a kereső és válogatás hatékonyabban. És biztos lehetsz benne, too-- mert azt hiszem, ez a legmélyebb mentünk a néhány Ezen CS témák proper-- voltunk tenni egy nap és fél ebben a pont, amit tipikusan úgy csinálni felett során nyolc hétig félévben. 

Bármilyen kérdése van ilyen? Nem? Rendben. Nos, miért nem szünet van, indul ebéd néhány perccel korábban, folytatódik, csak körülbelül egy óra? És én időzzön egy kicsit a kérdések. Akkor fogok menni egy pár hívásokat, ha nem gond. Majd kapcsolja be egy kis zenét az időközben de az ebéd legyen a sarkon.