[Muusika mängib] DAVID J. Malan: Olgu. Nii tere tulemast tagasi. See on CS50 ja on nädala lõpuks kolm. Nii meenutavad möödunud mitu nädalat, oleme veetnud üsna natuke aega C, programmeerimine, on süntaks. Ja see on täiesti normaalne, kui sa ikka hädas Ülesanded 2, peksma oma pead vastu seina. See on segasena ilmega veateated ja vead, mis sa ei saa päris jälitama maha. Sest kindel, et just Mõne nädala pärast saad tagasi vaadata asjad nagu Caesar ja [? V-genair,?] võibolla isegi crack, ja aru, kui kaugele olete jõudnud lühikese aja jooksul. Nii et kui see sind lohutab, riputada sinna nüüd. Täna aga hakkame üleminek asju kõrgemal tasemel. Ja hakkame enesestmõistetavaks, et te teate, kuidas programmi, või vähemalt algus et mugavuse tase. Ja me hakkame mõtlema, kuidas me saame minna umbes projekteerimisel programmid enam tõhusalt. Kuidas me saame minna optimeerides tõhusust meie algoritmide ja üldiselt lahendamisel rohkem huvitav probleeme. Ja hakanud enesestmõistetavaks, et kui me tahame, saame koodi üles iga näited on meil meeles. Nii et täna me ei puutu klaviatuur mis tahes kujul koodi. See oleks palju kõrgem, ja lõpuks, umbes probleemide lahendamisele. Nii, et saada selle punktini, andke mulle ettepaneku et järgmised seitse ristkülikud kujutavad seitse uste taga mis on terve hunnik numbrid, mille hulgas on number 50. Lubage mul projitseerida see sellel ekraan ka siin. Ja ettepanekuid, et me vajame vabatahtlikku aidata leida minu number ees internet siin. Tule üles, et roosa. Hea küll. Mis su nimi on? JENNIFER: [kuuldamatu] DAVID J. Malan: Vabandust? JENNIFER: Jennifer. DAVID J. Malan: Jennifer. Olgu, Jennifer. Meeldiv kohtuda. Tule üles. Nii et need siin on seitse uksed ja mida Ma tahaks, et sa meid siin, ees kõik oma klassikaaslastega, on meid leida number, 50. Et leida number, saate piiluda taga kõik need uksed lihtsalt puudutades on üks ustest, ja see paljastab oma number. Ja vaatame, kui kiiresti sa meid leida number, 50. 15. 16. 50. Ilusti tehtud. Hea küll. Aplaus Jennifer. [APLAUS] Hea küll. Niisiis, milline oli teie strateegia leida number 50? JENNIFER: Um, ma mõtlesin, et äkki kui - [Kuuldamatu] DAVID J. Malan: Oh. Anna see üks teine. Nii oli oma strateegia leida number 50? JENNIFER: Nii et ma lihtsalt alustada hakkame nägema mida esimene number oli, ja siis ma mõtlesin, et äkki kui nad järjestatud, siis ma muudkui koputades kõrgemal? DAVID J. Malan: OK. Ja näib, et oleme leidnud et oleks. Kuigi, olgem koor tagasi kihid natuke, ja sa tahad minna käia ja paljastada uksed sa oleks võinud valida? JENNIFER: Oh, kallis. DAVID J. Malan: Ah. JENNIFER: Nii et ma lihtsalt vedas. DAVID J. Malan: Nii vedas. Hea küll. Nii ei ole halb. Aga see on huvitav ülevaate, eks? Kui sa endale, ja sa ei saa, Tõepoolest, veidi õnnelik seal. Aga kui sa eeldada, et numbrid olid sorteeritud, saab olema täpsem selle kohta, kuidas see mõjutab oma käitumist? JENNIFER: Nii et kui nad sorteeritud, I mõtlesin, et äkki väiksemast ja lõpetades suuremaga. DAVID J. Malan: OK. JENNIFER: Või kui see oli lõpuks tõesti suur, siis suuremast väiksema. DAVID J. Malan: OK. Nii suuremast väiksema või väiksemast ja lõpetades suuremaga. Aga lubage mul pakkuda oletame, et teil oli saanud õnnetu, ja arvan, et nad ei, tegelikult, sorteeritud, kui palju need uksed võivad olete pidanud piiluda maha, et halvimal juhul? JENNIFER: kõik. DAVID J. Malan: kõik. Teeme üldistada, et n. Seal juhtub olema 7, kuid olgem rohkem üldiselt öelda, et seal on n uksed ekraan siin. Nii et halvimal juhul, siis oleks otsima taga 7 ust või n uksed. Ja nii see tõesti on, et see on natuke õnne täna, aga see on tõesti lineaarne algoritm kehvasti, kuigi te oli selline hüppamine. Kas see on õiglane? JENNIFER: Jah. DAVID J. Malan: Noh, las ma vaatan, kas teie strateegia muutused, kui ma liigutan meid meie teine ​​näide siin 7 erinevaid uksi. Samad numbrid, kuid see kord, kui nad on järjestatud. Mis su strateegia siin saab olema, üritab panna välja meelt, mida muud numbrid olid - JENNIFER: OK. DAVID J. Malan - varem? JENNIFER: Alustame koos esimene. DAVID J. Malan: Olgu. Alusta esimene. 4. Nüüd, kus sa lähed minema, ja miks? JENNIFER: 4 on tõesti väike. Nii et kui nad omamoodi ehk väikseim et suurim, see peaks olema kaks korda suurem, ja -. DAVID J. Malan: OK. Vaatame, mis sa arvad? JENNIFER: Proovige viimane. Nice. DAVID J. Malan: Väga kenasti tehtud. Hea küll. [APLAUS] DAVID J. Malan: OK. Nii et sa teed seda jubedalt, sest sa oled teevad seda väga hästi. Mis jätab meile suuda teha teatud punkte. Seega proovime rulli tagasi siin. JENNIFER: OK. DAVID J. Malan: Väga hästi tehtud, sellegipoolest. Nii et sa hakkasid alguses, nägid, et see oli 4, siis kolis lõpuks. Aga oletame, et sa ei saada õnnelik seal, ja arvan, et 50 oli kuskil mujal. Mida teie Kolmas samm on olnud? JENNIFER: Mine tagasi algusesse. DAVID J. Malan: Mine tagasi alguses. OK, nii et teil oleks olen puudutanud see uks, mis oli 8. Hea küll. Nii et see ei ole 50. Kuhu on otsinud järgmine? JENNIFER: kui ma ei tean, et nad sorteerida. DAVID J. Malan: Õige. Noh, kui sa ei tea, nad olid järjestatud - JENNIFER: Oh, ei tea, jah. DAVID J. Malan - aga sa ei teinud seda tea, kus 50 oli veel? JENNIFER: Minge edasi. DAVID J. Malan: Olgu. OK. Lase edasi. OK, et ma ei tööta. JENNIFER: OK. DAVID J. Malan: Nüüd, kui sa oled lihtsalt läheb edasi minema, mis su algoritm läinud toetavad arvesse. JENNIFER: lineaarne -. DAVID J. Malan: On selline lineaarne. Aga lubage mul pakkuda, andke Panen kohapeal. Las ma värskenda lehekülge. sama number, sama korraldus, sama uksed. Aga arvan, et tagasi, et esimene päev klassi, kui me rebis telefoniraamat poole, omamoodi, ja milline oli Meie strateegia on? JENNIFER: Algus keskel. DAVID J. Malan: OK. Nii algab keskel. Lähme edasi ja simuleerida seda. Alusta keskel paljastavad, et uks. Nii number 16. Niisiis, milline oleks tugev mees on teinud, kes rebis telefoniraamatu pooleks, et saada järgmisele oletus? JENNIFER: Mine selle poole. DAVID J. Malan: Ja miks nii? JENNIFER: Kui nad olid omamoodi väikseim et suurim, siis 50 peaks olema sel eesmärgil. DAVID J. Malan: Hea. Täiesti mõistlik. Nii nagu telefoniraamat, lähete õigus mitte vasakule, kuid siin on võti Buffee. Nüüd saab visata või ära rebida, pool seda probleemi, jättes teile ei koos 7 ust, aga tõesti vaid 3. Mis on umbes pool Probleemi suurus. Hea küll. Nüüd mida sa oleks teha pärast lähete õige? JENNIFER: Nii 16 on ikka päris väike, võrreldes 50, nii et võib-olla ma püüan, nagu see üks. DAVID J. Malan: Olgu. 42. Olgu, nüüd, mis on oma instinkt ütleb teile? JENNIFER: võin visata see ja siis lihtsalt - DAVID J. Malan: OK. Hea, võite visata vasakul pool on. JENNIFER: - vali see. DAVID J. Malan: ja õigus. JENNIFER: Jah. DAVID J. Malan: Nii et kuigi see on raske näha võib-olla siis, kui seal on ainult 7 ust, mõtle nüüd, järjepidevus algoritm sa lihtsalt rakendada. Eelmises juhul sa tegid saada õnnelik, mis oli suurepärane. Aga sa ei kasuta heuristiline, Ma ütleks. Sa kasutasid justkui oma instinkte ja teades, et see sorteeritud, kui see on päris väike alguses, ilmselt oleme pean minema rohkem paremale. Kuid mõnes mõttes sul veab, sest võib-olla oli see arv 100, ja võibolla 50 oli keskelt. Ehk 50 oli isegi siin. Aga mida sa tegid natuke teistmoodi sel ajal oli, sa tegid sama asja uuesti ja uuesti. Ja ma väidan, et see, mida sa ei, kuigi mõjutatud telefon raamat näiteks on midagi palju rohkem algoritmilise ja palju vähem eraldi kastidesse. Palju vähem instinktiivne. Nii et lõpuks, kuidas oleks sa kirjeldada tõhususe esimene algoritm, kus sa käisid vasakult paremale, versus Teine algoritm siin? JENNIFER: See üks peaks nagu, võibolla poole võrra aega, või isegi rohkem, jah. DAVID J. Malan: OK, võib-olla isegi rohkem. Olgem suruda veidi raskem selle kohta. Mis tegelikult, kui me jätkame seda loogika, me kindlasti poole võrra sõiduaega selle teine ​​algoritm visates ära poole numbrid, aga mis me teha järgmisel iteratsiooni kui Jennifer selgus teine ​​number? Me poole numbrid uste uuesti. Ja siis me tegime pärast seda, kui oli rohkem uksi mängida? Oleksime poole võrra neid, ja jälle, ja uuesti ja uuesti. Ja see oli just nagu te kõik püsti esimesel nädalal klassi, pool sa istud, pool teist istudes, pooled teist istudes, kuni üks üksildane soul seisis. Ja me ütlesime, et sõiduaega et mitmeid meetmeid selleks oli kohta, et mida? SPEAKER 1: [kuuldamatu] DAVID J. Malan: Nii logaritmi alusega 2 n, või lihtsalt rohkem lihtsalt sisse n. Seega midagi logaritmiline. Ja graafik ei olnud sirge et just hullemaks, see oli see huvitav kõver, mis ei saada nii halb ajas. Niisiis olgem hoidke seda ideed. Olgem tänada Jennifer. Tänu nii palju tulevad üles. Ja üks sek. No laualambid täna, kuid me ei ole CS50 stress pallid. JENNIFER: Jee. DAVID J. Malan: Olgu, siin. Täname tekiks stress siin. Hea küll. Vaatame, kui me ei saa praegu ametlikult selle natuke rohkem. Nii et taas, mida me tegime oli sisuliselt sama asi nagu tegime selle esimese nädala jooksul. Kuid selle asemel end lihtsalt lineaarne algoritm, mis me kujutatud varem kui see sirge kusjuures, kui me paneme veel ühe ukse ekraan, siis Jennifer pidanud otsima potentsiaalselt taga veel üks uks. Kui me paneme kaks ust, ta võib olla otsima taga kaks ust. Ja nii oli see lineaarne suhe suurus probleem on, ütleme, x-telg, ja aega, mis kulub lahendamiseks on y. Kuid pildil olin vihjates varem oli see roheline joon. Green tahtlikult, sest see tundus parem. Teoreetiliselt algoritm, kui me tegime seda koos telefoniraamat, kui me tegime seda teiega arvestamata üksteisega ning teisel juhul, kui Jennifer lihtsalt tegi seda siin, see oli omamoodi põhimõtteliselt parem. Sest see ei olnud ainult kaks korda kiiremini. See ei olnud isegi neli korda kiiremini. See oli täielikult sõltuv mida sisendi suuruse suhtes oli, kui palju meetmetest, mida ta lõpuks võttis. Ja nii see lihtne idee, et me kõik võtsid kohta, mis on antud telefoniraamatust saab samamoodi kohaldada et midagi sellist. Ja see võib olla juhuslikult tuntud, kui võiks kujutan ette, jaga ja valitse. Ei erinevalt, mida me tegime, muidugi, koos telefoniraamatust. Aga pseudokoodi, mäletate, oli see. Nii et me ei tee seda uuesti, kuid meenutada et esimesel nädalal, kõik meist püsti ja siis poole sa istusid, pooled sa istusid, pooled teist istus. Seda algoritmi rakendatakse natuke petmine moel, et see ei olnud vaid üks minu lugemist põhimõtteliselt, tõhusamalt. Sellisel juhul, ma olin võimendamise sekundaarse ressursina. Omamoodi, Mitme protsessoriga, mitu aju, Mitme smart inimesed tuba aitasid mind saada midagi lineaarne midagi logaritmiline millestki punasest midagi rohelist. Aga sel juhul, Jennifer üksi põhimõtteliselt täiustada täitmiseks tema esimene algoritm poolt, uuesti, lihtsalt mõtlesin natuke raskem. Ja nüüd, kui on aeg, et rakendada need asjad, figuring mis rida koodi saab kirjutada sellist et võid korrata neid uuesti ja uuesti ja uuesti, omamoodi aastal silmukoiminen mood. Sest sa ei kavatse on luksus, nagu Jennifer tegi esiteks lihtsalt terve hunnik IFS ja öelda, hmm, kui esimene number on 4, andke mulle hüppama kõik viis lõpuks. Ooh, kui see number on liiga suur, lase mul liikuda suvaliselt tagasi Teise element. Leiad, et see saab olema palju raskem vormistama, mida me inimestele enesestmõistetavaks nagu väga mõistlik heuristika, kuid arvuti on ainult teeme, mida sa öelda tahad. Nüüd see on väga huvitav tagajärjed. See graafik on justkui mõeldud omamoodi uputama visuaalselt, kuid teate, kus on sirgjoon selle graafik? Kus on lineaarne graafik mida me nimetame n? Noh, see on omamoodi põhja poole Selle pildi, eks? Nii et kõik, mida oleme teinud, et me oleme omamoodi suurendatud tähelepanu, et x-telg ja y-telje proovida saada tunnet, mida muud liiki kõverad nägema. Ja eripära matemaatiline väljendeid täna ei ole, nii et palju, kuid märkad, et seal on palju algoritme, mis on palju hullem kui midagi, mis on lineaarne. Tõepoolest, n kuubis tundub päris halb. 2 kuni n tundub päris halb. n ruudus näeb päris halb. Ja me näeme, mida mõned neist võib olla tegelikult täna. Ja samamoodi n ei tunne nii halb, kuid parem kui n on logaritm alusel 2 n. Aga tead, see oleks olnud veelgi rohkem hämmastav kui Jennifer, või kui me, et esimesel nädalal, oli tulla midagi, mis on samamoodi log n. Nii teisisõnu, seal on see kogu Võimalike lahenduste probleeme, kuid isegi siin, teate mis juhtub. Kui ma välja suumida, mis nende kõverate läheb osutuda absoluutne halvim ones ekraanil nüüd? Nii n kuubis tundub päris halb hetkel. Aga kui me vaadet ja vaata rohkem x ja y-telg, kes läheb domineerivad lõpuks? Nii see tegelikult välja, et 2 n, ja te saate seda välja mõelda lihtsalt ühendades mõned üha suuremaid numbreid, ja te näete, et 2 n tõepoolest muutub suuremaks kiiremini. Kui me tõesti suumimiseks 2 n algoritm absoluutselt imeb. Ma mõtlen, et see saab võtta üsna natuke aega arvuti läbi hammustada. Aga näete, aja möödudes, eriti tulevaste probleem komplekti ja isegi lõplik projektidele, on oma andmed komplekti saab suur, eks? Isegi esimese versiooni Facebook, kui mitu sõbrad ja Registreeritud kasutajad said suured saate sortida telefoni see ja rakendada midagi Lineaarse otsing, või väga lihtne sorteerimine algoritm, nagu me täna näeme. Sa pead hakkama mõtlema raskem ja raskem nendest probleemidest. Ja milliste probleemidega kohtades nagu Facebook ja Google ja Microsoft, ja teised tööd on täpselt need omamoodi suur andmed omamoodi küsimused enam nendel päevadel. Hea küll. Nii Jennifer edu, et teine algoritm, öeldes, et ta tegi hämmastavalt samuti esimest korda, kuid olgem kirjuta see õnn, et me teha selles küsimuses. Teisel juhul on ta võimendatud algoritm, mis kordub ja uuesti, kuid ta võttis enesestmõistetavaks teatud eeldusel, et me lubada , kuid ta ära mõned detail teist korda, et tal ei ole esimest korda. Mis oli mis? See loetelu on järjestatud. Seega niipea, kui loetelu on järjestatud, me väidavad, et Jennifer oli võimalik teha fundamentaalselt parem. 7 ust, jah, ei ole, et huvitav, kuid arvan, et see meil 7000000 uksed. Logi n on kindlasti kavatse teha palju, palju kiiremini pikemas perspektiivis. Aga ta pidi olema uste järjestatud teda. Ma võtsin vabaduse teed, et eelnevalt arvutiekraanil siin, kuid arvan, et Jennifer pidin tegema, et ise? Oletame, et uksed küsimus esindatud andmed andmebaasi või sõbrad registreeritud Facebook, või tahes veebilehti Internetis, erinevate veebilehtede võib olla vaja indeks või otsi üle. Oletame, et teil oli just algandmete määratud ja see jäi teile või Jennifer teha, et sorteerida? Et pigem nõuab, et me vastame küsimus, noh, kui palju aega oleks võtnud Jennifer või isegi mulle, sorteerida neid numbreid ette nii et ta võiks ära kasutada seda? Õigus? Kuna kaudselt muidugi kui ta võtab mind mõnda aega, et sortida numbreid, kes kuradit see huvitab, et sa võib leida mitmeid nagu 50 nii kiiresti, nagu Jennifer juhtum, kui me üle ülekoormatud summa koguaeg kulus sorteerimisel asju ette? Vaatame, kui me ei saa maalida pilti siit. Mul on terve hunnik rohkem stressi pallid, kui see aitab murda jääd siia. Ja kui sa ei pahanda, me pea seitse vabatahtlikku - kohta, OK. Wow. Nii et me ei pea kulutama edasi laualambid tundub. Hea küll. Niisiis, kuidas sa kaks ees. Kuidas te kaks meest tagasi. Nii et neli. Kuidas sinust ees viis, kuus ja seitse. Just seal. Sinu sõbra juhtides teid, nii saad auhinna. Hea küll. Tule üles. Ja miks me ei pea te poisid tulge siia. Ma annan sulle iga number. Ja minna ja korraldada ise identne mis kujutatud ekraanil. [Astudes VOICES] DAVID J. Malan: OOP, sorry. Vika. Hea küll. Noh, siin me läheme. Number viis. Number kuus. Üks, kaks, kolm, neli, viis, kuus, seitse. Oh, see on ebamugav. SPEAKER 2: ma lihtsalt saada -. DAVID J. Malan: Good deal. Hea küll. Aitäh osalemise. [APLAUS] OK. Hea küll. Nii et meil on neli, kaks, kuus, üks, kolm, seitse, viis. Perfect seega on meil seitse vabatahtlikud siin, kes on võrdse laiusega massiivi me mängime Varasema. Ja ma valisin seitse põhjustel mis on lihtsalt mugav natuke. Ja ma lähen ettepaneku, et esiteks me järjestada need seitse vabatahtlikku. Kui soovite kõigepealt tere öelda küll. Kuna see saab olema ebamugav mitu minutit. Tutvusta ennast. GRACE: Tere, ma olen Grace. Ma olen üliõpilane in Leverett House. Branson: Hi. Olen Branson. Ma olen uustulnuk keevitada. Gabe: Hi. Olen Gabe. Ma olen junior Cabot. NEIL: ma olen Neil. Ma olen uustulnuk Matthews. JASON: ma olen Jason. Ma olen uustulnuk Greenough. MIKE: ma olen Mike. Ma olen uustulnuk hallid. JESS: Olen Jess. Ma olen üliõpilane in Leverett. DAVID J. Malan: Suurepärane. Hea küll. Tänan kõiki meie vabatahtlike siin siiani. Ja väljakutse käepärast nüüd läheb et sorteerida need poisid, kuid siis me peame mõtlema natuke raske, kuidas tõhusalt me ​​tegelikult järjestatud neid. Teeme kõigepealt proovida seda. Te näete teineteise numbrid lihtsalt pannes umbes nurkades. Lase käia ja võtta paar sekundit, sort hoiduda väikseim Vasakult suurim paremal. Mine. OK. Hea. See oli tõesti pagana kiire. Nüüd keegi siin, mis oli algoritm et need kutid kohaldatud? SPEAKER 1: Vähimast suurim. DAVID J. Malan: OK. Vähimast suurim on tõesti omamoodi eesmärk, kuid ma ei ole kindel, et see tõesti algoritm. Vähemalt kuni suurima ei ütle mulle samm-sammult, mida teha. Jah? SPEAKER 1: [kuuldamatu] DAVID J. Malan: OK. Nii et kui näete isik väiksem oma number, siis liikuda õige neist. Nii et nüüd saan rohkem väljendusrikas, rohkem nagu algoritmi, sest sa ei saa öelda, kui seda, siis see. Nii et meil on mingi tingimuslik ehitada. Ja need kutid paistis teha mõned korda, sest mõned teist kolis natuke kohta vahemaa. Nii oli arvatavasti mingi silmukoiminen toimub oma mõtetes. Aga proovime vormistama seda. Kui te võiks reset tagasi Selle kokkuleppe. Vaatame, kas me ei ole ametlikult selle bit, ja seejärel küsida, lihtsalt kuidas tõhus see on? Muidugi, kui me teeme seda aeglasemalt, see läheb tunne nii hea algoritm, kuid vaatame, kas me saame pane oma sõrme täpne samme. Nii et kaks meest on neli ja kaks. Või siis õige või vale järjekord? Ilmselt vale. Nii me vahetaks. Nüüd ma lähen liikuma kõrvale siin ja öelda, 4-6. Kas sa oled õige või vale? Gabe: Õige. DAVID J. Malan: Õige. Kuus ja üks? Nope. Vaheta. Nii et kaks vahetustehinguid. Kuus ja kolm? Nope. Vaheta. Kuus ja seitse? Paistab hea. Seitse ja viis? JESS: [kuuldamatu] DAVID J. Malan: OK, vahetada. Ja sorteerida. Hea küll. Nii et ilmselt ei, eks? Nii oli veel pooleli. Aga tõepoolest, need kutid, isegi lihtsalt instinktiivselt. hoida liigub. Nad ei ole lihtsalt lõpetada, kui nad parandatud üks probleem. Nii. Tõepoolest, ma lähen on teha sama asi. Ma pean omamoodi tagurpidi tagasi et alguses see probleem, või alguses massiivi inimesed, alustame kutsudes neid. Ja nüüd, mis peaks minu algoritm teisel pass olema? SPEAKER 1: sama asi. DAVID J. Malan: sama asi. Ja see, ma olen hakanud meeldima, eks? Niipea kui leiad ise teed sama asja ikka ja jälle, et see on muutumas nagu algoritm, ja vähem inimese instinkt. Nüüd, siin me läheme uuesti. Kaks ja neli? Ei. Neli ja üks? Ah, seal oli tõesti mõned tööd on veel teha. Ja kolm? Hea. Neli ja pool? Kuus ja viis? Kuus ja seitse? OK, nüüd tehtud. OK, ei. Ma pean tagasi minema. Nüüd jällegi, me teeme seda veidi rohkem teadlikult. Ja nüüd, seal on üks aju täidesaatva seda algoritmi. Üks CPU, kui soovite. Ja ausalt öeldes, see on ainus ressurss me on juurdepääs. Ja kui me ei lähe tagasi klaviatuuril ja midagi nagu C juures meie kõrvaldamine, et me oleme ainult kirjalikult programm mida saab teha üks asi korraga. Arvestades, et need kutid hetk tagasi, me võimendatud nende kollektiivne mõttejõu nagu te tegite nädalal null. Jätame teed. Kaks ja üks. Kaks ja kolm. Kolm ja neli. Neli ja viis. Viis ja kuus. Kuus ja seitse. Valmis? Nii et ma olen, kuid lubage mul mängida saatana kaitsja. Kas mul on mingi arvuti, kes lihtsalt tehtud läbida seda massiivi inimesed teavad, et ma olen teinud? SPEAKER 1: Ei DAVID J. Malan: Miks? Mida ma pean tegema, et sõlmida otsustavalt, et ma olen teinud? Ilmselt üks pass. Õigus? Sest kõik, mida ma tean, et eelmine pass on, et ma parandatud viga. Ja see tähendab, äkki seal on veel üks viga et mul on vaja parandada. Ma võin kindel olla ainult poolt tagasikerimiseks ja siis kontrolli, 01:59, kaks ja kolm, kolm ja neli, neli ja viis, viis ja kuus, kuus ja seitse. OK, nüüd ma ei teinud tööd. Võin kindlasti meeles pidada, et ma ei ole töötada koos midagi nagu muutuja, nagu int. Kõne see vahetuslepingud ja kui vahetustehingud on 0, kui ma siia, ja see algas 0, siis Ma oleks lihtsalt rumal Jätkab edasi-tagasi, kontroll uuesti, ja uuesti ja uuesti, eks? Kuna te jänni mõned selline lõputu silmuse. Seega niipea, kui seal on 0 vahetuslepingud võib väita, et see algoritm on tõepoolest lõpetatud. Nüüd paneme selle nimi. Algoritm, pakun me lihtsalt rakendatud on midagi, mida nimetatakse mull sort, mida tuntakse näiteks selles mõttes, et numbrid, mis on suurem liiki mull oma teed kuni üleval, või üles aasta lõpuni massiivi numbrid. Aga kuidas tõhus oli see algoritm? Mitu sammu ma füüsiliselt pea Võtame näiteks, et järjestada need seitse inimestele? Neli kuni viis? OK, liiga palju on lõppkokkuvõttes saab olema vastus. Aga isegi siis, konkreetsed number ei ole nii huvitav. Olgem üldistada seda n. Nii et kui ma olin n inimesed siin, ja nad olid omamoodi, juhuslikus järjestuses alguses, et esialgses järjekorras. Noh, kui palju samme ei mul võtta esimesel pass? See oli üks, kaks, kolm, neli, viis, kuus, ja nad on seitse inimest, nii mis on seitse, kuus -, nii et see n miinus üks astub esmakordselt. Nüüd, kui palju samme ei mul võtma, kui ma tagasi kerida? Noh, me võiksime tegelikult kahekordistada, et kui me tõesti tahtsid, aga praegu olen ma lihtsalt ütlen, eks, teise n miinus 1. Nii n miinus 1 on hakka tüütu jälgida, niiet lihtsalt ümardada veidi. Nii 2n samme. Nii 14 sammu, anda või võtta. Mitu korda ma võtma sammu järgmine kord? Noh, see on 3n. tõesti. Ja nüüd, halvimal juhul jaoks Näiteks, kui mitu korda ma olema läinud edasi ja tagasi, edasi ja tagasi, täidesaatva see algoritm, vahetades inimesed iga pass, jämedalt? See on tegelikult n ruudus, eks? Sest halvimal juhul saate lahke ning mõtlema intuitiivselt, kuigi see võib võtta veidi natuke aega vajuma sisse Halvimal juhul, milline oleks nende seitse inimest on tundus, et kokkuleppe tingimused nende numbrid? Täiesti tagasi, eks? Ja just, et simuleerida seda, mis su nimi oligi? MIKE: Mike. DAVID J. Malan: Mike? OK, Mike, kas sa lihtsalt minuga üle siin lihtsalt üks teine? Tegelikult, ei. Vabandust Mike, olgem tagasi kerida. Mis su nimi oligi? NEIL: Neil. DAVID J. Malan: Neil. OK, Neil, tulete Usu mind, kui sa ei pahanda. Nii et ma lähen ettepaneku, lihtsalt lihtsus, et Neil on nüüd oma halvimal võimalikul juhul. Aga mäletate, kuidas ma ellu minu algoritm. Ma võrrelda, võrrelda, võrrelda, võrrelda, võrrelda, oh. Nüüd need kutid on välja töökorras, nii et ma saan määrata. Nii et te vahetada. Aga pean nüüd, kui palju kaugemal ei Neil on vaja minna? See on umbes n. Sa tead, et see pole tegelikult n. See on nagu, n miinus 1, kuid ma saan pahane jälgida vähe number, nii et olgem lihtsalt nimetame seda n. Nii et kui Neil käib ühe sammu maksimaalselt iga aega ja liikuda Neil üks samm, Ma pean seda tõesti tüütu pass edasi-tagasi, et see on enam-vähem Seejuures n samme, kokku n korda, sest see läheb võtab mind et palju samme, et saada Neil kõik viis, kus ta kuulub. Rääkimata kõik teisedki, kui te olid kõik valesti tellitud samuti. Seega kutsume mull sort n ruudus. Sõiduaega see algoritm, tulemuslikkust selle algoritmi, tõhusust see algoritm, me lihtsalt kirjeldada rohkem üldiselt kui n ruudus. Mis on tore, sest ma võiks teha sama näiteks kaheksa inimest, üheksa inimesed, miljon inimest, ja et Vastus on ei muutu. Nii et kui te ei oleks midagi, lähme reset teil kui sa hakkasid. Ja proovime kaks lähenemist ja vaata, kui me ei saa põhimõtteliselt parem kui see. Nii et see aeg, ma lähen ettepaneku omamoodi algoritmi. See oli väga tark meist viimane kord, ja te olite õigus õigus instinktid lihtsalt selline Vahetatakse paarikaupa. Aga kui ma tõesti tahtsin läheneda lihtsalt, ja minu eesmärk on liikuda kõik vähe numbrid niimoodi, ja push kõik suured numbrid, mis Muide, miks ei ma lihtsalt seda teha kõige naiivne viisil ja vaata, kas ma saab teha paremini kui see, mis oli üsna keeruline algoritm? Seega vaatame. Neli on üsna väike number, nii et ma olen jäta sa seal hetkel. Ooh, number kaks on veelgi parem. Nii saab lihtsalt samm edasi hetkeks? See on praegu minu väiksema numbriga kandidaat, ja ma lähen meeles et koos nagu, muutuja. Aga ma lähen hoida kontrolli. Kas on keegi, kelle number on väiksem? Kuus, ei. Oh, seal on Neil uuesti. Nii, et ma sunnin sind tagasi omamoodi kontseptuaalselt. Neil tulevad edasi. Ja nüüd, muutuja, mis ma kasutan, et jälgida, kes on väikseim number on ajakohastatud sisaldada Neil asukohast. Noh, vaatame. Kolm, seitse, viis. OK, ma tean Neil oli väikseim. Mis on kõige lihtsam asi minu jaoks teha? Ma ei kavatse raisata oma aega, lihtsalt vahustamine Neil üks koht vasakule. Miks ma ei lihtsalt panna Neil kus ta kuulub, mis on muidugi kus? Kogu tee alguses. Nii Neil, tule minuga. Ja mis su nimi oligi? GRACE: Grace. DAVID J. Malan: Grace. OK. Nii Grace kahjuks oled liiki viisil. Niisiis, kuidas me seda probleemi lahendada? Õigus? Kui see on massiiv, seal ainult seitsmes kohas. Tuletame meelde, et koos Rob, me rääkisime kuulutatakse vanuses ja oli meil ainult hulga vanuses? Sama mõte siin. Meil on ainult piiratud arv ints. Grace on selline meie Muide, nii kuidas me määrata? Lihtsaim viis on nagu, Grace, sorry. Sa lähed minema üle seal, et me saaksime teha ruumi. Nüüd, kui sa mõtled seda, äkki me just probleemi hullemaks. Ja võib-olla me tegime, sest mis siis, kui Grace oli õiges kohas? Aga me teame, et ta ei ole, sest muidu ta oleks olnud seistes edasi asemel Neil seekord, eks? Meil on juba kontrollitud tema number välja. Hea küll. Nüüd, Neil on õiges kohas, ja Ma saan veidi optimeerimine. Sest järgmisel hetkel, et ma lähen ignoreerida Neil kõik koos, et mitte raiska oma aega, või kogemata swap teda vales kohas. Nüüd, kuidas ma leida järgmise element, mis on väiksem? Kaks. See on päris hea number, kui soovite samm edasi ja Ma mäletan sind. Kuus, ole hea. Neli, kolm, seitse, viis, ei ole hea. Nii et lubage mul liikuda teil oma õigesse kohta. Ja me lihtsalt vedas seekord. Nüüd ma lähen neid eirata kaks meest ja nüüd veel ühe läbida seda. Kuus, et üsna väike hulk. Tule edasi. Oh, vabandust. Grace number on parem, nii samm edasi. Neli. Vabandust, Grace. Mine tagasi. Number kolm on parem. Seven. Viis. Ja nüüd, mis su nimi oligi? JASON: Jason. DAVID J. Malan: Jason. Nii Jason on nüüd kõige väiksem element olen valinud. Kuhu ta läheb minema? Nii et kui kuus on. Ja teie nimi on jälle? Gabe: Gabe. DAVID J. Malan: Gabe. Gabe on ees. Mis on kõige lihtsam asi, mida teha? Vaheta need kaks meest ja jätkata. Nüüd vaatame. Kes on kõige väiksem? Neli. Lubage mul lihtsalt selline petta. Viis saab olema väikseim. Ma leian kõrval, kui soovite astuda edasi, mida ma pean tegema koos need kutid koos Gabe? Vaheta uuesti. Nüüd veel pisut rikkis. Leidsin Gabe väikseim, nii I pop teda välja, liiguta kutid üle. Ja teha. Seega vastus on sama. Lõpptulemus on sama. Milline neist kaks algoritmid on parem? Teine, ma kuulsin. Miks? SPEAKER 3: See on n sammud [kuuldamatu]. DAVID J. Malan: See on n sammu järel. Huvitav. Nii on see küll? Niisiis, kuidas ma leida väikseim element? Mitu sammu ma pidin võtma Leida väikseim element? Vaatasin kõik viis aasta lõpus, eks? Sest, et halvimal juhul mida kui Neil oli siin? Nii lihtsalt leida väikseim element võtab mind n samme, või n miinus 1. Aga OK. Nii määrata Neil. Pea meeles, et minut või nii tagasi. Aga kuidas ma leida järgmise väikseim element? See on n miinus 1 või n miinus 2 tõesti, alates sammude arvu. Nii OK. Nii et ma ei n miinus 2. Hea küll. Nii et tundub natuke parem. Hea küll. Mitu sammu järgmine kord leida number kolm? Nii n miinus 4. Nii, et see väheneb, üks vähem astuda iga iteratsiooni. Nii et see ei tunne parem, eks? Kui viimane kord, kui ta oli umbes n korda n, seekord on n miinus 1, pluss n miinus 2, pluss n miinus 3 pluss n miinus 4, dot, dot, dot. Aga kui te mäletate oma keskkooli õpikud, vähe petma leht taga, mis on valemid, kui sa küündivad see numbrikombinatsiooniga, mida on kokku mitmeid samme saab olema, mida ma käin siin? See on üks neist, nagu, n miinus 1 korda n, jagatuna 2. Nii las ma vaatan, kas ma saan tõmmata see üles hetkeks. Ja veel, ma olen selline ümardamine mõned numbrid lihtsalt hoida meie elu lihtne, aga nagu ma mäletan, et see on midagi sellist, kui I do n miinus 1 asja, siis n miinus 2, siis n miinus 3, see on enam-vähem midagi sellist üle 2 ja kui ma korrutada see läbi, see on tegelikult n ruut. See ei tunne liiga hea. n miinus n üle 2. Aga siin on asi. Computer Science, kui probleemid hakkama saada huvitav on, kui n saab tõesti suur. Ja kui n saab tõesti suur, mis on need väärtused läheb domineerivad kõik teistel? See on selline n ruudus, eks? Jah, jagades 2 on päris hea. Aga kui sa räägid miljardeid infokilde või triljoneid tükid andmed, OK, sa oled kaks korda kiiremini. Aga kes tõesti hoolib, kui see suur number, kui see tegur on see, mida saab suuremaks. Ja kindlasti, see teeb rohkem erinevust kui see kutt. Nii et kuigi te olete õige, Teine algoritm, me nimetame seda valiku sorteerida, on reaalses maailmas, natuke kiirem olla, sest ma olen võttes vähem ja vähem samme iga kord. See ei ole tegelikult täiesti kiiremini. Sest kui me tegelikult mängivad seda läbi suur n väärtuste, lõpus päeval, aga piisavalt suur, n, see on ikka läheb tunne üsna aeglane. Noh, lubage mul võtta üks viimase söödu seda. See on see, mida ma kutsuksin valik sort. Kas te poisid reset ise viimast korda? Ja viimasel juhul, ma lähen pakkuda midagi nimetatakse sisestamise sort. Insertion sort on, kontseptuaalselt natuke erinev. Selle asemel läheb edasi ja tagasi ja valides väikseim element, ma olen lihtsalt hakkab tegelema kõigi nende poisid nagu ma kogevad neid, ja sisestada need oma õige koht. Nii et ma olen lihtsalt kavatse alustada Grace, ja ma näen, et ta on number neli. Kust number neli kuuluvad? Ma ei ole alustatud sorteerimine midagi, nii Grace saab jääda sinna. Ja nüüd ma lähen väita, kui sa saaksid sammu oma õige, see minu järjestatud nimekirja, see on minu sortimata ülejäänud nimekirja. Nüüd ma lähen edasi järgmisele, ja mis su nimi oligi? Branson: Branson. DAVID J. Malan: Branson. Nii Branson on number kaks. Nii et ma lähen teile välja hetkeks. Ja nüüd, kui sa kuuluvad Selles massiivi? Nii paremal Grace. Nii et taas, me oleme omamoodi tegemine Grace tegema palju tööd siin. Kust me sind? Nii et me läheme libisema teil vasakule ja sisesta Branson seal. Aga nüüd ma väita, et te olete teinud. Aga teate, ma ei kasuta ruumi. See on ikka 2 elementi siin, 5 siin. Kõik massiivi suurus on 7, nii et ma olen ei peta, eks? Nüüd on meil koos Gabe siin number kuus, kus Te kuulute? Sul vedas jälle. Nii saad viibida seal. Lihtsalt võta väike samm õiges lihtsalt selgeks teha, et sa ei järjestatud. Ja nüüd on meil Neil jälle number üks, kus sa lähed? Ja nüüd on koht, kus me hakkame nägema, et Selle algoritmi, kuigi esimesel pilgul tundub päris nutikas, vaadata Mis hakkab juhtuma. Kui teil oleks samm edasi. Kui me tahame panna Neil? Nii et ilmselt siin, kuidas me saame Neil on seal? Teeme seda samm-sammult. Gabe, kus sa pead minema? Jep, nii et võta üks suur samm, või kaks poole samme üks samm sinna. Grace, kus sa lähed? Hea. Nii teine ​​samm. Ja lõpuks, Branson? Teine samm. Ja nüüd saame panna Neil paika. Nüüd, jätkata seda loogikat. Kuigi me ei ole minnes Neil üle ja üle ja üle, et panna teda kuhu ta läheb, halvimal juhul Järgmine number me sattuda võib olema number, ütleme, seal oli number null, siis läheme minema kõik need kutid. Oletame, et seal on number, negatiivne üks, siis peame muutma kõik need mehed. Nii et me oleme tegelikult lihtsalt selline flipping probleemi ümber, nii et me oleme ülekandmise kulu valikuprotsessi nii sisestamist protsess, nii et kutid lihtsalt pidin liikuda umbes n miinus midagi mitmeid samme. Ja et mitmeid meetmeid on ainult kavatse suurendada, kui ma valida rohkem numbreid kui ma pean hoidma tuupimine kutid tagasi ja tagasi ja tagasi. Nii kurb asi nüüd on kõik need algoritmid on n ruudus. Lähme edasi ja tänu nendele poisid, ja visualiseerida neid natuke erinevalt. Väga hästi tehtud. [APLAUS] Hea küll. Seal sa lähed. Täname - Branson: [kuuldamatu] hoida numbrid. DAVID J. Malan: Ei, te võite hoida numbrid samuti. Hea küll. Ilusti tehtud. Hea küll. Vaatame, kui me ei saa nüüd kokku kiiremini ja rohkem visuaalselt, täpselt, mis just juhtus siin järgmiselt. Ma lähen edasi minna ja tõmba Firefox. Me siduda see demonstratsioon on muidugi kodulehel. Java on natuke tüütu, et saada töö mõned brauserid nendel päevadel. Nii et kui sa mängid seda kodus, mõistma, et peate kasutama Firefox saada see töö. Ja see, mida ma lähen tegema seda demonstratsioon on järgmine. Allosas, mul on terve hunnik menüüvalikuid, sealhulgas algust ja stopp-nupule. Samuti, nagu kõrvale, siis tundub, et bug neis programmides, mille te tegelikult näha ei saa käivitada või peatada nuppu, kui te ei hoia Command või Alt pluss ja suurendada, mis uudishimulikult näitab teile rohkem nuppe. Nii lihtsalt FYI, kui sa mängid seda kodus. Nüüd ma lähen klõpsa Start vaid hetk, täpsustades hilinemise, nagu, 200 millisekundit siin, just et me saaksime näha, mis juhtub. Nii et ma väita, et see on visualiseerimine esimese algoritm need poisid tegid, mull sortida, mille me vahetasid inimesed paarikaupa. Võtmeküsimuseks on see visualiseerimine on see, et tulpade kõrgust esindab suurus number. Nii pikem on riba, seda suurem number. Lühem bar, väiksem number. Ja kui te märkate, me läheme läbi esimese iteratsiooni see algoritm, Vahetatakse suur ja väike number, nii et väike arv on esimesel ja suur number läheb paremale. Ja niipea, kui saame lõpuks massiiv palju rohkem numbreid kui seitse, me oleme lähen tagasi algusesse. Ja ennetada seda. On palju vasakule, et väikemees läheb swap kõrval, ja see protsess kordub. Nüüd on see visualiseerimine kiiresti muutub igav, nii et lubage mul minna ja lõpetada see, Viivituse midagi palju kiiremini lihtsalt saada nüüd, tunne Selle algoritmi. Nii et kuigi ma olen kiirustas ta üles, et see on nagu ümberehitamise mu protsessor, osta uus arvuti. Ma ei ole oluliselt muutnud mu algoritm, kuid võite tõesti näha rohkem selgelt kui inimestega, et suur numbrid on vahustamine kuni top, ja väikesed numbrid on vahustamine alaserva. Ja nüüd on see asi siin sorteeritud. Ja kõrvale, väljakud, seal vaid mõned raamatupidamine seal aitab teil arvutada, mitu võrdlusi, või kuidas paljud vahetustehingud on tegelikult tehtud. Noh, proovime ühte teised nägime. Lubage mul klõpsa mull sort siin ja Lase mul valida, ja kogu see veebileht on natuke lollakas. Teeme aktsepteerima riski ja käivitage see uuesti. Vot nii. Teeme valiku sort. Ma ei tea, miks menüü ilmub sinna. Olgem suurendada määrata, et bug, seda muuta 50. Ah, lähme tegelikult teha et palju kiiremini. Viis millisekundit või nii, ja Start. Nii et see on valik sort. Nii et taas, mõelda, mida me tegid inimesed siin. Käisime läbi massiivi ja valitud väikseim element jälle ja uuesti ja uuesti. Nüüd ma väita, et oli ikka päris halb. See oli ikka n ruuduga, anda või võtta, kuid see oli, reaalses maailmas, veidi kiiremini, sest olin tõesti võttes veidi vähem samme iga kord. Aga me ainult räägime, mida? Võib-olla 40 või nii baarides here? Me ei räägi 40000000. Nii see ei ole täiesti selge, et oli tõepoolest märkimisväärne tõus. Lubage mul nüüd minna tagasi ja muuta oma kolmas algoritm, mida valida sisestamise sort. Ja nüüd on see tõesti lollakas sest menüü tõesti ei tohiks olla seal. Nüüd me kerida tagasi siia ja hakata seda algoritmi. Hõiskama, alustada ja lõpetada. Nii et see üks omamoodi on päris muster et see, mille me oleme jälle sisestades inimesele või Sel juhul vardad oma sobivas kohas. Ja see on juba tehtud enne Keerasin ümber. Aga see ka teoreetiliselt veel n ruudus. Vaatame, kui me ei suuda kokku need järgmised. Ma lähen edasi minna ja lihtsalt anda meile omamoodi ühise kõnemaneer neid asju, lubage mul tutvustada lihtsalt natuke märke siin. Sa parasjagu näha midagi, mida nimetatakse suureks O, sest see on sõna otseses mõttes suur O. Ja see on nii, et arvuti teadlane või matemaatik isegi kasutab kirjeldada sõiduaega mõnede algoritm. Mitu sammu see tegelikult aega võtab? Nüüd ma lähen häbistada ennast minu käekiri siin üks hetk. Aga lubage mul minna ja öelda, et see saab olema suur O siin. Ja lubage mul tutvustada üht sümbol, kapitali omega. Omega saab olema vastupidine, sisuliselt suur O. arvestades suur O vahenditega, halvimal juhul, siis kui palju aega võivad mõned algoritm võtab kasutusele seisukohast n, omega läheb olema, kui palju aega võib see võtma parimal juhul. Ja me näeme, mida me mõistame parimal juhul vaid hetk. Alustame midagi lihtsat. Lubage mul alustada lineaarne otsing. Nii ei sorteerimine. Me nimetame seda lineaarset otsingut. Ja nüüd, teha väike tabel läbi selle. Ja nüüd, kui tegemist on lineaarse otsing, halvimal juhul, kui palju samme on see aega võtab mind leida number suvalise valiku? Ja seal on n kokku uksed või n koguarvu. Halvim. Mitu sammu ma tegema pean võtta, et leida number 50 array n uksed? Ja miks? Sest see võib olla kõik kuidas üle koridori lõpus. Nii palju nagu Jennifer tekkinud, number 50 oli kogu tee üle, nii et Halvimal juhul lineaarne otsing on suur O n, me ütleme. Aga parimal juhul kui sa tõesti õnnelik? See on lihtsalt aega võtab ühe sammu, või pidev sammude arvu. Nii me kirjeldada, et kui 1. Nii et see on päris hea. Nüüd kui me tegime midagi nagu binaarne otsing? Nii binaarne otsing, halvimal juhul võttis palju aega? [Astudes VOICES] DAVID J. Malan: Nii tegelikult ma kuulsin seda paar kohti. Nii et see on tegelikult sisse n, anda või võtta, sest kui me jagame nimekirja pooleks uuesti ja uuesti ja uuesti, et me oleme võimelised leida lõppkokkuvõttes raha, kui see on olemas, kuid ei saagi. Mis on eeldus, et me peame enesestmõistetavaks eest binaarne otsing? See peab olema lahendatud. See ei ole sorteeritud, saad jagada asi pooleks ja jälle, ja sa võib minna vasakule ja võid minna paremale ja võid minna vasakule ja paremale, aga sa oled ei kavatse leida element kui loetelu ei ole sorteeritud, sest võite jääda ta. Kuna teie heuristiline, läheb vasakule või paremale läheb vigane, kas see on tõepoolest ei järjestatud. Nii et seal on mingi varjatud kulud kasutades midagi sellist. Nüüd lähme meie sorteerimine algoritme mitte otsida - oh, tegelikult lähme selle tühjaks. Binary otsing parimal juhul? See on ka 1, kui see lihtsalt juhtub olema aastal väga keset massiiv või Keset telefoniraamatust. Teeme nüüd mull omamoodi. Nii et taas, nüüd oleme sisenemist kehvasti, ei otsingud. Halvimal juhul, kui palju samme teinud me nõude mull omamoodi aega võtab? n ruudus. Nii et ma lähen joonistan selle. Ooh, mu käekiri tundub isegi hullem kui see on prognoositud, et suur. Hea küll. Nii et n ruudus. Ja parimal juhul mull sorteerida, kui palju samme on see aega võtab? 1, ma kuulsin. SPEAKER 1: n. DAVID J. Malan: n, ma kuulsin. SPEAKER 1: 2. DAVID J. Malan: 2, ma kuulsin. Kas ma kuulen 3? Hea küll. Nii et ma olen kuulnud, 1, n, 2, kuid valime peale vähemalt esimene neist ettepanekuid, 1. See ei ole halb instinkt, sest see liiki järgmiselt muster siin. Aga kui see võtab vaid 1 samm, kuidas maailm võiks ma väita, et nimekiri on järjestatud, sest kui ma olen lubatud ainult võtta 1 samm, kui palju elemente kas ma tegelikult kontrollida, et olla kindel? Noh, lihtsalt 1, mis tähendab, et seal on n miinus 1 elemente, mida võiks välja et, ja ma olen lihtsalt läheb edasi usus pärast vaatab 1 element, mis asi on lahendatud. Nii 1 pole õige siin. Nii minimaalselt, kui palju ma pean vaatama? [Astudes VOICES] DAVID J. Malan: n miinus 1, või tegelikult, n, sest mul on vaja vaadata iga element veenduda, et see ei ole rikkis. Aga jälle, me omamoodi laine meie käed väiksema arvu ja eeldada, et kui n saab suur, siis on nad ebahuvitav niikuinii. Nii et see mull omamoodi. Ja nüüd, teeme need kaks viimast. Selection sort, ja siis me teha sisestamise sort. Ja siis me löök oma mõtetes millegi palju parem kui kõik need. Hea küll. Mis on halvim töötab valimise ajal sort? SPEAKER 4: n ruudus. DAVID J. Malan: n ruutu, ma kuulen. Aga miks n ruudus, intuitiivselt? SPEAKER 4: Kuna me tegime seda. DAVID J. Malan: Kuna me tegime seda. OK. Hea vastus. Aga intuitiivselt, miks on valik sort n ruudus? Mida me peame tegema, uuesti ja uuesti? Meil oli hoida skaneerimise kaudu, on sa väikseim, sa oled väikseim, sa oled kõige väiksem. Ja antud suutsime võtta n samme, siis n miinus 1, siis n miinus 2. Aga kui sa omamoodi lisada need kõik üles, või võtta see usk, et olen lisatud neid ette, saame umbes n ruudus miinus mõned väiksemad numbrid. Nii et ma lähen kutsun seda n ruudus. Aga valik omamoodi parimal juhul, kui palju samme on ta kavatseme mind? SPEAKER 5: [kuuldamatu] DAVID J. Malan: See on kahjuks ikka n ruudus, eks? Sest kui ma olen valides väikseim element, ja meil oli seitse inimest siin, Ma tean vaid, kui ma saan väga end, et ma olen leidnud väikseim number, kuhu iganes ta või ta võis olla. Aga kuidas ma saan teada järgmise Väikseim number? Ma pean seda tegema teisele pass. Nii et parim, siis millised on sisendi valik sort? See on juba omamoodi nimekirja, number üks, number kaks, number kolm, number neli. Aga ma olen arvuti. Ma võin ainult vaadata üks asi korraga. Ma ei saa omamoodi sammu tagasi, nagu inimeste ja öelda, ooh, see näeb välja õige. Võin vaid lahendab õigsuse valik sorteeri valides väikseim number. Aga isegi siis, kui ma leian number üks esimene, kui ma ei tea, midagi muud muud numbrid, mida ma ei ole, ma tean, et ma olen tehtud massiivi või komplekti uste taga, mis on numbrid, vaid viis, kuidas ma tean, et üks Väikseim oli? Kui ma saan kogu tee siia ja saavad aru, Kurat, üks oli tõepoolest kõige väiksem. Aga kuidas ma saan siis otsustada, et kaks on järgmine kahanevas järjekorras? Tehes sama ebatõhususe uuesti ja uuesti. Nii et lõpuks, koos nende sort, kuidas, halvimal juhul me öelda, et see täidab? See liiga on n ruudus. Ja kuidas on parim nii? Me lahkume, et pinge. Me täitke et tühi järgmine kord, Aga kõigepealt lubage mul ettepanek, et me põhimõtteliselt teha paremini kui kõiki neid, eks? Nii et mõtle ise, mida sisestamise sort saab olema. Noh, see ei olnud väga järsk, sest ma olen ainuke et nägid muutust. Wow. OK. Nii et siin on meil mõnevõrra erinevate meeleavaldus. Kui ma suumida siin, näete, et vasakul meil mull sorteerida, et keskel on meil valik sort ning palju parem, meil on midagi, mida me pole vaadanud veel kutsus ühendada sortida. Aga mõelda, mida me oleme siin teed seni täna. Kui Jennifer esimene tuli lavale, läksime läbi massiivi numbrid uuesti ja uuesti, lineaarse otsing, ja me saime lineaarne sõiduaega, suur O n-ö. Kui me nüüd kaaluma esimesel nädalal klassi, kui olime jaga ja valitse, ja meil oli telefoniraamatust rebimine, ja Jennifer ja me kollektiivselt võimendatud et Võtmeküsimuseks, mis pidi kordan ennast uuesti ja uuesti kuidagi ära visata, ära visata, visata ära, pool probleemi või üldiselt, jagades probleemi pooleks, ja siis ravivad väiksem tükk probleem kontseptuaalselt samaväärne teistele, me kuidagi ei fundamentaalselt parem. Aga mull sorteerida ja valida sort, koos nende sort, meil võib selliseid teadmisi, et Jennifer tegi. Oleme päris palju lihtsalt kõndis tagasi ja edasi terve hulk kordi, ja me Tweaked asju natuke, vahetades selles, et võib-olla sisestamist või valimist. Aga lõpus päeval, ma tegin palju ebamugav jalgsi edasi-tagasi. Me ei tõesti võimendavat midagi nutikas nagu Jennifer tegi nagu jagades ja vallutavad. Nii Tarkvaraprojekteerimise seevastu, mida me ei näe, kuni järgmisel nädalal, see läheb võimendada, et Põhiidee jagades sisend ja siis poole võrra, ja siis poole võrra, ja siis poole võrra. Ja iga iteratsiooni et loop, sorteerimine vasakul pool ja paremal poole, siis vasakul pool vasakul pool, ja paremal pool vasakul, siis vasakul pool paremal poolel, ja paremal poolel paremale poole. Ja korrates ikka ja jälle. Nii näete seda visuaalselt, kuid see on see, mis ootab meid järgmisel nädalal. Ja üldiselt, kui me arvame, et vähe natuke raskem selliseid probleeme. Meil on n ruudus vasakul, n ruuduline keskel ja n logi n paremal. Nii et teie tõeline pinge. Näeme esmaspäeval. [APLAUS]