[Muusika mängib] DAVID Malan: Olgu. Olgu, tere tulemast tagasi. Nii et see on 4. nädalal alguses arvestades, et juba. Ja sa meenutada, et eelmisel nädalal paneme koodi kõrvale natuke ja me hakkasime rääkima natuke rohkem kõrgetasemelised asju nagu otsimine ja sorteerimine, mis on küll mõnevõrra lihtsad ideed, on esindaja klass probleeme hakkate lahendada eriti kui hakkate mõtlema lõplik projekte ja huvitavaid lahendusi võib-olla reaalse maailma probleeme. Nüüd mull sort oli üks lihtsamaid selline algoritme, ja see töötas omades väikest arvu nimekirja või massiivi omamoodi mull oma teed kuni ülemise ja big numbrid liikuda oma tee alla aasta lõpuks, et nimekirja. Ja meenutada, et me võiks visualiseerida mull omamoodi väike midagi sellist. Nii et lubage mul minna ja klõpsake nuppu Start. Olen valmis valitud mull omamoodi. Ja kui te mäletate, et pikem sinine Jooned tähistavad suured numbrid, väike sinised jooned kujutavad vähe, kui me minna läbi see uuesti ja uuesti ja jälle, võrreldes kaks baari kõrval iga teine ​​punane, me ei kavatse vahetada suurima ja väikseima kui nad on rikkis. Nii see läheb ja edasi minna ja minna kohta, ja te näete, et suurem elemendid teevad oma tee õige, ja väiksemad elemendid on tegemise teel vasakule. Aga meil hakkas kvantifitseerida Tõhususe kvaliteet selle algoritmi. Ja me ütlesime, et halvimal juhul on see algoritm võttis ligikaudu, mitu sammu? Nii n ruudus. Ja mis oli n? Publik: elementide arv. DAVID Malan: So n oli mitmeid elemente. Ja nii me teeme seda sageli. Iga kord, kui me tahame rääkida suurus probleem või suuruse sisend, või kui palju aega kulub toota toodangut, me lihtsalt üldistatud iganes sisend on n. Nii tagasi nädal 0, number lehekülge aastal telefoniraamat oli n. Õpilaste arv ruumis oli n. Nii ka siin, me pärast et muster. Nüüd n ruudus ei ole eriti kiire, nii oleme püüdnud teha paremini. Ja nii me vaatasime paar teiste algoritme, mille hulgas olid valiku sort. Seega valik sort oli veidi erinev. See oli peaaegu lihtsam, ma julgen öelda, kusjuures ma hakkasin alguses nimekiri meie vabatahtlikele ja ma lihtsalt uuesti ja jälle läks läbi nimekiri, kitkumise välja väikseim element korraga ja paneb teda või teda alguses nimekirja. Aga ka see, kui me hakkasime mõtlema läbi matemaatika ja suurem pilt, mõelnud mitu korda Ma läksin edasi ja tagasi ja tagasi edasi ja me ütlesime halvimal juhul valik sort oli ka see, mida? n ruudus. Nüüd reaalses maailmas, see võib tegelikult ainult natuke kiiremini. Kuna uuesti, ma ei pea hoidma tagurdusmeetod kord olin järjestatud väikseim elemente. Aga kui me mõtleme väga suur n ja kui sa omamoodi tegema läbi matemaatika kui Tegin laual, koos n ruudus miinus midagi, kõik muu peale n ruudus, kui n saab tõesti suur, ei tegelikult küsimus, kui palju. Nii nagu arvuti teadlased, oleme omamoodi silmi kinni pigistama, et väiksemate teguritest ja keskenduda ainult tegur mõiste, mis läheb teha suurim erinevus. Noh, lõpuks, me vaatasime kell sisestamise sort. Ja see oli sarnase sisuga, kuid mitte läbida korduvalt ja valida väikseim element ükshaaval aega, ma selle asemel võttis kätte, et ma arutati, ja ma otsustasin, kõik õige, sa kuulud siia. Siis kolisin järgmisele element ja otsustas, et ta või ta kuulus siin. Ja siis kolisin edasi ja edasi. Ja ma võiks üles, mööda teed, suunata need kutid, et teha ruumi neile. Nii et oli omamoodi vaimne pöördumise Valiku sort, et meil nimetatakse sisestamise sort. Nii et need teemad tekivad reaalses maailmas. Paar aastat tagasi, kui teatud senaator presidendiks kandideerida, Eric Schmidt ajal tegevjuht Google, tegelikult oli võimalus küsitleda teda. Ja me arvasime me tahaks jagada seda YouTube'is Videoklipp sa siin, kui me võiks omakorda üles helitugevust. [VIDEO PLAYBACK] -Senaator, et sa siin oled Google, ja mulle meeldib mõelda eesistujariigi nagu tööintervjuu. [Naer] -Nüüd on raske saada töö kui president. Ja sa lähed läbi külmavärinad nüüd. Samuti on raske saada tööd Google. Meil on küsimused ja palume Meie kandidaadid küsimusi. Ja see on Larry Schwimmer. [Naer] -Te vist teen nalja? See on siinsamas. Mis on kõige tõhusam viis Kuvatud miljonit kaks-bit täisarvud? [Naer] -Noh, uh - Anna andeks. Võib-olla me peaks - -Ei, ei, ei, ei, ei. -See ei ole - OK. -Ma arvan, et mull sort oleks olla vale tee. [Naer] [Cheering JA APLAUS] Tule, kes rääkis talle seda? OK. [END VIDEO PLAYBACK] DAVID Malan: Nii et teil on see. Niisiis hakkasime arvuliselt töötab korda, nii et rääkida, millegi nimetatakse asümptootiliseks märke, mis on lihtsalt viidates meie omamoodi keerates silma need väiksemad tegurid ja ainult vaadates sõiduaega, täidaksid neid algoritme, kui n saab tõesti suur ajas. Ja nii me kasutusele suur O. Ja suur O esindab midagi, mida me arvasime AS ülemise. Ja tegelikult, Barry, saame alandada kui mic natuke? Me arvasime, et sellest on ülemise. Nii suur O n ruudus tähendab, et halvimal juhul midagi valik omamoodi võtaks n ruudus samme. Või midagi sellist sisestamise sort oleks n ruudus samme. Nüüd midagi sisestamise sort, mis oli halvim? Arvestades massiiv, mis on kõige hullem võimalik stsenaarium, et te võite leida ise silmitsi? See on täiesti tagurpidi, eks? Sest kui see on täiesti tagurpidi, mida sa pead tegema palju tööd. Sest kui sa oled täiesti tagurpidi, sa lähed leida suurim element siin, kuigi see kuulub sinna alla. Nii et sa lähed öelda, olgu, kell Praegusel ajahetkel, sa kuulud siia, nii et jäta ta rahule. Siis sa mõistad, oh, neetud, ma pean liiguta see veidi väiksem element vasakul teile. Siis ma pean tegema, et uuesti ja uuesti ja uuesti. Ja kui ma kõndis edasi-tagasi, siis oleks omamoodi tunne tulemuslikkust et algoritm, sest pidevalt ma olen lohistades kõik teisedki alla massiivi teha ruumi. Nii et halvim. Seevastu - ja see oli pinge viimast korda - me öelda, et sisestamise sort oli omega mida? Milline on parim puhul töötab on asetatud sort? Nii et see on tegelikult n. See oli tühi, et jätsime laual viimast korda. Ja see on omega n sest miks? Noh, väga parim, siis millised on sisestamise omamoodi kavatse antakse? Noh, nimekiri, mis on täielikult järjestatud juba, minimaalne tööd teha. Aga mis on puhas umbes sisestamise sorteeri on see, et kuna see algab siin ja otsustab, oh, sa oled number üks, sa kuulud siia. Oh, mis õnn. Sa oled number kaks. Samuti kuuluvad siia. Number kolm, isegi parem, sa kuulud siia. Niipea, kui ta saab lõpuks nimekirja kohta sisestamise sort on pseudokoodi et me kõndinud läbi suuliselt viimane kord, see on tehtud. Aga valiku sorteerida, seevastu hoida seda, mida? Hoitud läbimas nimekiri uuesti ja uuesti ja uuesti. Sest Võtmeküsimuseks oli ainult kui olete otsinud kõik viis nimekirja lõppu sa saad olla kindel et element valisite oli tõepoolest praegu väikseim element. Nii et need erinevad vaimse mudelid lõppu üles saades mõned väga reaalse erinevused meile, samuti nende teoreetiline asümptootiliseks erinevusi. Nii lihtsalt sulgege siis suur O n ruudus, me oleme näinud vähe selliseid algoritme siiani. Big O n? Mis on algoritm, mis võiks pidada suur O n? Halvimal juhul kulub lineaarne arvu. OK, lineaarne otsing. Ja halvimal juhul, kui see on element otsite kui lineaarse otsing? OK, halvimal juhul see ei ole isegi seal. Või teine ​​halvim, see on kõik viis lõpuks, mis on pluss-või-miinus üks samm vahe. Nii et lõpuks, võime öelda, et see on lineaarne. Big O n oleks lineaarne otsing, sest halvimal juhul, element ei ole isegi seal või see on kogu tee lõpus. Noh, suur O log n. Me ei saa rääkida väga üksikasjalikult seda, kuid me oleme seda varem näinud. Mis töötab nn logaritmiline aega, halvimal juhul? Jah, nii binaarne otsing. Ja binaarne otsing halvimal juhul võib olla element kuskil keskel või kuskil sees massiiv. Aga te ainult leida see, kui olete Jaga nimekirja pooleks, in pool, poole, pooleks. Ja siis voila, see on seal. Või veel, halvimal juhul see ei ole isegi seal. Aga te ei tea, et see ei ole seal kuni sa omamoodi jõuda, et viimane kõige alumine elementide poole võrra ja poole võrra ja vähendada poole võrra. Big O 1. Et me saaksime suur O 2, suur O 3. Anytime soovite lihtsalt konstant, me lihtsalt sorteerida just lihtsamaks et kui suur O 1. Isegi kui reaalselt kulub 2 või isegi 100 sammu, kui see on pidev mitmeid samme, me lihtsalt öelda suur O 1. Mis on algoritm, mis on aastal suur O 1? Publik: Leida pikkus muutuv. DAVID Malan: Leida pikkus muutuv? Publik: Ei, pikkus kui see on juba järjestatud. DAVID Malan: Hea. OK, nii leida pikkust midagi kui pikkus, et midagi nagu massiiv, on salvestatud mõned muutuja. Sest sa võid lugeda muutuja, või printida muutuja või lihtsalt tavaliselt juurdepääs, et muutuja. Ja voila, mis võtab pidevalt aega. Seevastu arvan, et tagasi tühjalt. Mõtle tagasi esimesel nädalal C, kutsudes lihtsalt printf ja trükkimine midagi ekraanil on väidetavalt pidev ajal, sest see lihtsalt võtab mõned mitmeid protsessori näidata et teksti ekraanil. Või oodake - kas pole? Kuidas muidu võiks me modelleerida täitmise printf? Kas keegi meeldib nõus, et võibolla see ei ole tõesti pidev ajal? Mis mõttes võib printf jookseb ajal tegelikult trükkimine string ekraanil olema midagi peale pidevalt. Publik: [kuuldamatu]. DAVID Malan: Jah. Seega sõltub meie vaatenurgast. Kui me tegelikult mõtleme sisendi printf olevaks string, ja Seetõttu me suuruse mõõtmiseks, mis sisend selle pikkus - nii kutsume et pikkus n samuti - Väidetavalt printf on ise suur O n sest see läheb teid n samme välja trükkida kõik need n tähemärki, kõige tõenäolisem. Vähemalt sel määral, et me eeldame, et äkki ta kasutab silmus all kapuuts. Aga me peame vaatama, et koodi seda paremini mõista. Ja tõepoolest, kui te alustada analüüsida oma algoritme, saate sõna otseses mõttes teha just seda. Omamoodi silmamuna oma kood ja mõelda kohta - kõik õige, mul on see ahel siin või ma pean nested silmuseid siin et kavatseb teha n asjad n korda, ja saate sortida mõistuse teed läbi koodi, isegi kui see on pseudokoodi ja mitte tegelikku koodi. Nii kuidas omega n ruudus? Mis oli algoritm, et parimal juhul ikka võttis n ruudus sammud? Jah? Publik: [kuuldamatu]. DAVID Malan: Nii valiku sort. Sest, et probleem on tõesti vähenenud asjaolust, et jälle, ma ei tea, Olen märganud, praegune väikseim kuni Olen vaadanud kõik darn elemente. Nii omega, ütleme, n, me lihtsalt tulid üks. Insertion sorti. Kui loend juhtub olema järjestatud juba, parimal juhul me lihtsalt teha üks läbib see, sel hetkel oleme kindlad. Ja siis, et võiks öelda, olema lineaarne, kindlasti. Aga omega 1? Millised on parimal juhul võiks võtta pidev sammude arv? Nii lineaarne otsing, kui sa lihtsalt veab ja element, mida otsid on õige alguses nimekirja kui see, kui sa oled hakanud oma lineaarne läbipääsusüsteemid selles nimekirjas. Ja see on tõsi mitmeid asju. Näiteks isegi binaarne otsing on omega 1. Sest kui sa saad tõesti darn õnnelik ja Ihan keset oma massiiv on number otsite? Nii saad õnnelik seal samuti. See üks lõpuks omega n log n. Nii n log n, me tegelikult ei rääkida, aga - Publik: Merge sort? DAVID Malan: Merge sort. See oli pinge on viimane kord, kui tegime ettepaneku, ja me näitasime visuaalselt, et on olemas algoritme. Ja liita omamoodi lihtsalt üks selline algoritm, mis on põhimõtteliselt kiiremini kui mõned neist teised poisid. Tegelikult ühendada lühike on mitte ainult Parimal juhul n log n, halvimal juhul n log n. Ja kui teil on see kokkusattumus omega ja suur O on sama asi? Me saame tegelikult kirjeldada, et mis nimega beta, kuigi see on veidi vähem levinud. Aga see tähendab lihtsalt kaks piire, sel juhul on samad. Nii ühendab sort, mida see tegelikult taandub meie jaoks? Noh, meenutada motivatsiooni. Las ma tõmba teine ​​animatsioon me ei vaata viimast korda. See üks, sama idee, kuid see on veidi suurem. Ja ma lähen edasi minna ja rõhutada esimene - meil sisestamise sorteerida top vasakule, siis valiku sorteerida, mull sorteerida, paar teist liiki - kest ja kiire - et me ei rääkinud kohta, ja hunnik ja ühendada sort. Nii vähemalt proovida keskenduda oma silmad esikolmikusse vasakul ja seejärel Tarkvaraprojekteerimise Napsautan see roheline nool. Aga ma lasen nad kõik kulgema, lihtsalt annab teile tunde mitmekesisust algoritme, mis on olemas kogu maailmas. Ma lasen selle run vaid paar sekundit. Ja kui teil keskenduda oma silmi - vali algoritm, keskendub ta vaid sekundit - saate hakata näha muster, et see rakendatakse. Merge sort, teate, on tehtud. Heap sort, kiire sort, koorimata - nii tundub tutvustasime kolm halvim algoritme eelmisel nädalal. Aga see on hea, et me oleme täna siin, et vaata Tarkvaraprojekteerimise, mis on üks lihtsam ones on vaadata, isegi kuigi see ilmselt painutada meelt natuke. Siin näeme, kui palju valik omamoodi jama. Aga Tagakülg, see on tõesti lihtne rakendada. Ja võibolla P Set 3, mis on üks algoritme valisid rakendada jaoks standard edition. Täiesti korras, täiesti õige. Aga jälle, kui n saab suur, kui te soovi korral rakendada kiiremini algoritm meeldib liita sort, koefitsiendid on suurem ja suurem sisendite teie kood on lihtsalt läheb kiiremini töötada. Teie koduleheküljel läheb paremini. Kasutajad saavad olema õnnelikumad. Ja nii on nende mõjude tegelikult annab meile mõned sügavamad arvasin. Võtame pilk liita sort on tegelikult kõike. Lahe asi on see, et ühendada sort on just see. See on jällegi see, mida me oleme kutsutud pseudokoodi, pseudokoodi olend Inglise-like süntaks. Ja lihtsus on omamoodi põnev. Nii on sisend n elemente - nii et tähendab lihtsalt, siin on massiiv. See sai n asju ta. See on kõik, mida me ütleme seal. Kui n on väiksem kui 2 tagasi. Nii et lihtsalt triviaalne puhul. Kui n on väiksem kui 2, siis ilmselt on see 1 või 0, mille puhul asi on juba järjestatud või olematu, nii lihtsalt tagasi. Ei ole midagi teha. Nii et see on lihtne asi kisu maha. Else, meil on kolm etappi. Sorteeri vasakul poolel elemente, sorteerida paremal pool elemendid, ja siis liita järjestatud pooleks. Huvitav on see, et Ma olen selline punting, eks? Seal on selline ümmargune definitsioon Selle algoritmi. Mis mõttes on see algoritm on määratlus ümmargune? Publik: [kuuldamatu]. DAVID Malan: Jah, minu sorteerimise algoritm, kaks tema sammud on "omamoodi midagi. "Ja nii see tekitab küsimus, noh, mida ma ei kavatse kasutada sorteerida vasakul pool ja paremal pool? Ja ilu on selles, et kuigi Jällegi, see on Hallutsinatsioone osa potentsiaalselt võid kasutada sama algoritm sorteerida vasakul pool. Kuid oodake minut. Kui sulle öeldakse, et järjestada vasakul pool, mis on kaks samme saab olema järgmine? Me sorteerida vasakul poolel vasakul pool ja paremal pool vasakul pool. Kurat, kuidas ma sorteeri need kaks pooleks, või kvartalite nüüd? Aga see on OK. Meil on sorteerimise algoritm siin. Ja kuigi võite muretsema juures esimene see on selline lõputu loop, see on tsükkel, mis kunagi läheb lõpuks - see läheb lõpeb siis, kui see, mis juhtub? Kui n on väiksem kui 2. Mis lõpuks juhtub, sest kui te ei hoia poole võrra ja vähendamine poole võrra on poole võrra nende pooleks, kindlasti lõpuks sa lähed lõpuni koos vaid 1 või 0 elemente. Sel hetkel, see algoritm ütleb, et sa oled teinud. Nii et tegelik võlu selles algoritm tundub olevat et viimane samm, ühinevad. See lihtne mõte lihtsalt ühendada kaks asjad, mis on see, mida on lõppkokkuvõttes läheb et võimaldada meil sorteerida massiivi, ütleme, kaheksa elemente. Nii et mul on veel kaheksa stress pallid üles Siin kaheksa paberitükke ja üks Google Glass - mis ma saan hoida. [Naer] DAVID Malan: Kui me võiksime võtta kaheksa vabatahtlike, ja vaatame, kas me saame mängida seda välja, nii et. Wow, OK. Arvutiteadus muutub lõbus. Hea küll. Niisiis, kuidas te kolm, Suurim käsi seal. Neli taga. Ja kuidas me teeme teile kolm selles reas? Ja neli ees. Nii et sa kaheksa, tulge siia. [Naer] DAVID Malan: ma olen tegelikult ei ole kindel, mis see on. Kas see stress pallid? Laualambid? Materjal? Internet? OK. Nii et tulge siia. Kes soovib - hoida tulemas. Vaatame. Ja see paneb sind asukoht - sa oled kohas üks. Uh-oh, oota natuke. 1, 2, 3, 4, 5, 6, 7 - oh, hea. Olgu, me oleme head. Olgu, nii et igaüks istet, kuid mitte Google Klaas. Lubage mul sabas need üles. Mis su nimi on? MICHELLE: Michelle. DAVID Malan: Michelle? Olgu, sa saad nägema geek, kui see on OK. Noh, mina ka, ma arvan, hetkeks. Olgu, ooterežiimis. Oleme püüdnud tulla kasutada juhul Google Klaas ja me arvasin, et see oleks tore lihtsalt teha see, kui inimesed on laval. Me salvestame maailma vaatenurgast. Hea küll. Pole ilmselt mida Google ette. Olgu, kui sa ei pahanda seljas see järgmiseks ebamugav minuti et oleks tore. Olgu, meil on siin hulgaliselt elemente ja et massiivi kohta paberitükid need inimesed " käed, praegu sortimata. MICHELLE: Oh, see on nii imelik. DAVID Malan: See on päris palju juhuslikult. Ja üks hetk, me ei kavatse proovida rakendada Tarkvaraprojekteerimise kokku ja vaata, kui see Võtmeküsimuseks on. Ja trikk siin Tarkvaraprojekteerimise on midagi, mida me ei ole endale veel. Me tegelikult vajan lisaruumi. Mis siis saab olema eriti Huvitav on see, et need poisid hakkavad liikuda vähe natuke, sest ma lähen eeldada, et seal on ekstra massiivi ruumi öelda, eks nende taga. Nii et kui nad on jäänud oma tool, see on sekundaarne massiivi. Kui nad istuvad siin, see on esmane massiivi. Aga see on ressurss, mis meil on ole võimendatud seni mulli sort ja valida sort, koos nende sort. Meenuta eelmisel nädalal kõigile lihtsalt liiki segatud paigas. Nad ei kasuta ühtegi täiendavat mälu. Tegime ruumi inimesi liikuvad inimesed ümber. Nii et see on oluline mõista ka. Seal on see kompromiss, üldiselt infotehnoloogia vahendeid. Kui soovite, et kiirendada midagi nagu aeg, sa lähed peavad maksma hinda. Ja üks neist, hinnad on väga sageli ruum, mälu või kõva kettaruumi, et te kasutate. Või ausalt, summa programmeerija aega. Kui palju aega kulub teil, inimese, tegelikult rakendada veidi rohkem keeruline algoritm. Aga täna, kaubandus-off on ajas ja ruumis. Nii et kui te poisid võiks lihtsalt hoida oma numbrid, et me näeme, et sa oled tõepoolest sobitamine 4, 2, 6, 1, 3, 7, 8. Suurepärane. Nii et ma lähen püüta asjad, siis kui sa suudad lihtsalt jälgi mind siin. Nii ma rakendada esiteks Esimene samm pseudokoodi, mis on on sisend n elementi, kui n on vähem kui 2, siis tagasi. Ilmselt see ei sätteid, et me liigume edasi. Nii sorteerida vasakul poolel elemente. See tähendab, et ma lähen keskenduda oma tähelepanu hetkeks nendel neli poisid siin. Olgu, mida ma järgmisena teha? Publik: Sorteeri vasakul pool. DAVID Malan: Nüüd pean sortida vasakul pool need kutid. Sest jällegi oletada, et ise eesmärk on sorteerida vasakul pool. Kuidas sa seda tegid? Jälgi juhiseid, isegi kuigi me teeme seda jälle. Nii sorteerida vasakul pool. Nüüd ma sorteerimine need kaks venda. Mis saab edasi? Publik: Sorteeri vasakul pool. DAVID Malan: Sorteeri vasakul pool. Nüüd need, see koht on siin, on nimekiri suurus 1. Ja mis su nimi oligi? PRINCESS DAISY: Princess Daisy. DAVID Malan: Princess Daisy on siin. Ja nii ta on juba järjestatud, sest nimekiri on suurus 1. Mida ma järgmisena teha? OK, tagasi, sest see nimekiri on suurus 1, mis on väiksem kui 2. Siis milline on järgmine samm? Ja nüüd on selline Taganeda meelt. Sorteeri paremal pool, mis on - Mis su nimi on? LINDA: Linda. DAVID Malan: Linda. Ja mis me nüüd teeme, et Meil on nimekiri suurus 1? Publik: Return. DAVID Malan: Ettevaatust. Me naaseme esimene ja nüüd kolmas samm - ja kui ma mingi kujutada seda omaks kaks istet nüüd, nüüd ma on ühendada need kaks elementi. Nüüd kahjuks elemendid on rikkis. Aga see, kui ühinevad protsessi hakkab saama veenvad. Nii et kui te ei seisa lihtsalt Hetkeks ma vajan sind, et Praegu sammu taga oma tool. Ja kui Linda, sest 2 on väiksem kui 4, siis miks mitte sa tuled ümber esimesena? Seal viibida. Nii Linda, tule ümber esimese. Nüüd tegelikult kui see on lihtsalt massiivi me võiks lihtsalt liikuda oma reaalajas selle tooli selle koha. Nii kujutan ette, et võttis mõned pidev mitmeid samme 1. Ja nüüd - kuid me peame teile Esimene asukoha. Ja nüüd, kui te võiks tulla ringi, samuti me läheme olema asukoha kaks. Ja kuigi see tundub nii võttes samal ajal, mis on tore praegu et vasakul poolel vasakul pool on nüüd järjestatud. Mis siis oli järgmine samm, kui me nüüd kerida edasi lugu? Publik: Parem pool. DAVID Malan: Sorteeri paremal pool. Nii et te ei pea seda tegema, samuti. Nii et kui sa võiksid seista hetkeks? Ja mis sinu nimi on? JESS: Jess. DAVID Malan: Jess. OK, nii et Jess on nüüd vasakul poole paremal poolel. Ja nii ta on nimekiri suurus 1. Ta ilmselt sorteerida. Ja su nimi oligi? MICHELLE: Michelle. DAVID Malan: Michelle on ilmselt nimekirja suurus 1. Ta on juba järjestatud. Nüüd magic juhtub, ühinevate protsessi. Nii et kes tulemas esimene? Ilmselt Michelle. Nii et kui sa võiks tulla umbes tagasi. Ruumi on meil olemas oma nüüd on õigus selle taga tool siin. Ja nüüd, kui te saaksite tagasi tulla ka, meil on nüüd, et oleks selge, kaks pooleks, kusjuures suurus 2 - ja lihtsalt kirjeldus pärast, kui te võiks teha natuke ruumi - üks vasakul pool siin, üks paremale poole siin. Keri edasi lugu. Mis samm on järgmine? Publik: Merge. DAVID Malan: Nüüd on meil ühineda. Nii OK, nüüd õnneks me lihtsalt vabanenud neli tooli. Nii et me oleme kasutatakse kaks korda rohkem mälu, kuid saame anda flip-flopping vahel kaks massiivid. Nii et mis number on esikohal? Nii Michelle ilmselt. Nii tulevad ümber ja võtma oma kohale siin. Ja siis number 2 on ilmselt Järgmine, siis tule siia. Number 4, number 6. Ja veel, kuigi seal on natuke jalgsi kaasatud tõesti, need võib juhtuda koheselt, liigutades üks - OK, hästi mängitud. [Naer] DAVID Malan: Ja nüüd me oleme päris heas seisus. Vasakul pool kogu sisend on nüüd järjestatud. Olgu, need kutid olid ära mu - kuidas see lõpuks kõik tüdrukud vasakule ja kõik poisid paremal? OK, nii poisid "kord nüüd. Nii et ma ei sõelub neid samme. Eks me näe, kas me saame uuesti Samal pseudokoodi. Kui soovite minna ja seista, ja teid, lubage mul anda teile mic. Vaata, kas sa ei saa dubleerida seda, mida me tegime siin muu loendi lõppu. Kes peab rääkima kõigepealt, põhineb algoritm? Nii selgitab, mida sa teed enne Te teete suu liigutusi. SPEAKER 1: Olgu, kuna Ma olen vasakul pool vasakul pool, ma tagasi. Õigus? DAVID Malan: Hea. SPEAKER 1: Ja siis - DAVID Malan: Kes mic minna edasi? SPEAKER 1: Järgmine number. SPEAKER 2: Nii et ma olen parem pool on vasakul pool vasakul pool, ja ma tagasi. DAVID Malan: Hea. Naasete. Nüüd mis on järgmine kuni teile kaks? SPEAKER 2: Me tahame näha, kes on väiksem. DAVID Malan: Täpselt. Me tahame ühendada. Ruumi me ei kavatse kasutada ühendada teid, kuigi need on ilmselt järjestatud juba, me ei kavatse järgima sama algoritmi. Niisiis, kes läheb tagasi esimene? Nii 3 ja siis 7. Ja nüüd mic läheb et need kutid, OK? SPEAKER 3: Nii et ma olen paremal pool vasakul pool ja minu n on väiksem kui 1, nii et ma olen lihtsalt läheb edasi - DAVID Malan: Hea. SPEAKER 4: Ma olen paremal pool paremale poole paremal poolel, ja ma olen ka üks inimene, nii et ma olen läheb tagasi. Nüüd me ühinevad. SPEAKER 3: Nii et me tagasi minna. DAVID Malan: Nii et te lähete tagasi. Nii 5 läheb esimesena, seejärel 8. Ja nüüd publik, mis on astuma peame nüüd tagasi kerida tagasi meie mõtetes? Publik: Merge. DAVID Malan: Ühinevad vasakul pool ja paremal pool esialgsest vasakul pool. Nüüd - ja lihtsalt selgeks teha, teha natuke ruumi teie kahe vahel kutid. Nüüd, et on kaks nimekirja, vasakule ja paremale. Niisiis, kuidas me nüüd ühendada te poisid ees istmerida jälle? 3 läheb esimesena. Siis 5, ilmselt. Siis 7 ja nüüd 8. OK, ja nüüd me oleme? Publik: Ei kärbita. DAVID Malan: Ei ole tehtud, kuna Ilmselt seal on üks samm jäänud. Aga jälle, miks ma olen, kasutades seda kõnepruugis nagu "tagasikerimine meelt," see on, sest see on tõesti mis toimub. Me läheme läbi kõik need sammud, aga me oleme omamoodi tõmbamata hetk, sukeldumine sügavamale algoritm, peatades hetkeks sukeldumine sügavamale algoritm, ja nüüd peame omamoodi tagurpidi meie mõtetes ja tühistada kõik need kihid et me oleme justkui ootele. Nüüd on meil kaks nimekirjad suurus 4. Kui te võiks püsti viimast korda ja teha natuke ruumi siia selgeks teha, et see on vasakul pool originaal, paremale poole originaal. Kes on esimene number, et me pead tõmba tagasi? Michelle, muidugi. Nii paneme Michelle siin. Ja kes on number 2? Number 2 süttib tagasi samuti. Number 3? Suurepärane. Number 4, number 5, number 6, number 7 ja number 8. OK, nii see tundus palju samme, kindlasti. Aga nüüd vaatame, kui me ei saa kinnitada, omamoodi intuitiivselt, et see algoritm põhimõtteliselt, eriti n saab tõesti suur, sest me oleme näinud koos animatsioonid, on põhimõtteliselt kiiremini. Nii et ma väita seda algoritmi, halvimal juhul ja isegi parimal juhul on suur O n korda log n. See tähendab, et seal on mõned aspekt algoritm, mis võtab n samme, kuid seal on teine ​​aspekt kusagil et iteratsiooni et silmukoiminen, et võtab log n samme. Kas me paneme oma sõrme, millised need kaks numbrit viitavad? Noh, kus - Kust mic minna? SPEAKER 1: kas sisse n purustamine meid kaheks - jagades kaks sisuliselt. DAVID Malan: Täpselt. Iga kord, kui me näeme iga algoritm seega kaugele, et siin on see muster jagamisel, vahesein, jagades. Ja see on tavaliselt vähendada midagi, mis on logaritmiline, logaritm alusel 2. Aga see võib tõesti olla midagi, kuid sisse alus 2. Mida aga n? Ma näen, et meil selline jagatud sa poisid - jagatud teid jagada teile, jagatud teile jagatud teile. Kuhu see lõpuks tuli? Nii et see on ühinevate. Sest mõelda. Kui liita kaheksa inimest koos, kusjuures pooled neist on komplekt neljast ja teine ​​pool on teise komplekt neli, kuidas sa minna seda teed ühinevad? Noh, te tegite seda üsna intuitiivselt. Aga kui ma selle asemel tegi seda veidi metoodiliselt, ma oleks osutanud vasakpoolsema inimene kõigepealt mu vasak Samas osutas vasakpoolsema inimene selle poole minu paremal käel, ja lihtsalt hiljem kõndis läbi nimekiri, osutades väikseim element iga kord, liigub mu sõrmi ja üle kui vaja kogu nimekiri. Aga mis on võti selle ühinevad protsessi ma võrrelda neid paari elemente. Paremalt pool ja vasak pool, ma ei ole kunagi üks samm tagasi võrreldes. Nii ühendamise ise võtab mitte rohkem kui n samme. Ja mitu korda tegin ma mida teha, et ühinevad? Noh, mitte rohkem kui n, ja me lihtsalt nägin, et selle lõpliku ühendamisega. Ja kui te teete midagi, mis võtab logi n sammud n korda, või vastupidi, see läheb meile n korda log n. Ja miks see nii on parem? Noh, kui me juba teame, et register n on parem kui n - eks? Nägime binaarne otsing, telefoniraamat Näiteks log n oli kindlasti parem kui lineaarne. Nii et see tähendab n korda log n on kindlasti parem kui n korda teine n, AKA n ruudus. Ja see, mida me lõpuks tunne. Nii suur aplaus, kui Võiksime need kutid. [APLAUS] DAVID Malan: Ja teie lahkuminek kingitused - võite hoida numbrid kui soovite. Ja teie peokink, nagu tavaliselt. Oh, ja me saadame sulle footage, Michelle. Aitäh. Hea küll. Aita ennast stressi pall. Ja las ma tõmba vahepeal, Meie sõber Rob Bowden pakkuda veidi erineva vaatenurga see, sest sa ei mõtle neid samme toimub mõnevõrra teistmoodi. Tegelikult ülesseadmist mida Rob on umbes et näidata meile, eeldab, et me oleme juba teinud jagamise kohta suur nimekiri kaheksaks väike nimekirjade Iga suurus 1. Nii et me muutuvad pseudokoodi natuke lihtsalt omamoodi nöökima põhiidee kuidas ühinevate töötab. Aga sõiduaega, mida ta on umbes, mida teha on veel saab olema sama. Ja jälle, set-up on see, et ta on alustatud kaheksa nimekirjad suurus 1. Nii et olete jäänud osa, kus ta on tegelikult tehtud log n log n log n lõhestab sisend. [VIDEO PLAYBACK] -Ongi esimene etapp. Sest samm kaks, korduvalt ühendada paari nimekirju. DAVID Malan: Hm. Ainult heli on tulemas välja minu arvuti. Proovime uuesti. -Just suvaliselt valida mis - Nüüd on meil neli nimekirja. Lugege enne. DAVID Malan: Vot nii. -Ühinevad 108 ja 15, me lõpetame välja nimekiri 15 108. Ühinevad 50 ja 4, me lõpetame 4, 50. Ühinevad 8 ja 42, me lõpetame 8, 42. Ja ühinevate 23 ja 16, siis lõpetame 16, 23. Nüüd on kõik meie nimekirjad on suurus 2. Pange tähele, et iga neli nimekirja sorteeritakse. Nii saame alustada ühinevad paari nimekirjad uuesti. Ühinevad 15 ja 108 ning 4 ja 50, siis kõigepealt 4, siis 15, siis 50, siis 108. Ühinevad 8, 42 ja 16, 23, me kõigepealt 8, siis 16, siis 23, siis 42. Nüüd on meil vaid kaks nimekirjad suurus 4, millest igaüks on järjestatud. Nüüd me ühinevad need kaks nimekirja. Esiteks, me 4, siis me võtame 8, siis me võtame 15, siis 16, siis 23, siis 42, siis 50, siis 108. [END VIDEO PLAYBACK] DAVID Malan: Jällegi, teate, ta ei ole kunagi puudutanud antud tass rohkem kui üks kord pärast edeneb väljaspool. Nii ta on kunagi korrata. Nii ta on alati liigub küljele, ja see on, kus me saime oma n. Miks ei lase mul tõmba üks animatsioon et me nägime, kuid seekord keskendudes ainult Tarkvaraprojekteerimise. Lubage mul minna ja suurendamiseks aastal selle siin. Esiteks lubage mul valida juhuslik sisend, võimendada ja saate sortida ja vaata mida me pidasin enesestmõistetavaks, varem liita omamoodi tegelikult teeb. Nii teate, et saad need pooleks või Nende kvartalite või nende kaheksandikku probleem, et äkki hakkamist heas korras. Ja siis lõpuks, näed kell Päris lõpus, et BAM kõik on ühendatud kokku. Nii et need on vaid kolm erinevat võtab sama mõte. Aga võti teadmisi, nagu lõhe ja vallutada väga esimese klassi oli see, et me otsustasime, et kuidagi jagada probleem millekski suur sisseveo midagi omamoodi identne vaimu aga väiksemaid ja väiksemaid ja väiksem. Nüüd teine ​​lõbus viis omamoodi mõelda nendest, kuigi see ei ole annan sulle sama intuitiivne mõistmist, on järgmine animatsioon. Nii et see on video keegi kokku panna mis on seotud erinevate kõlab erinevate toimingute eest sisestamise sort, sest Tarkvaraprojekteerimise ja paariks teised. Nii et hetkel, ma lähen lüüa Play. See on umbes ühe minuti pikkune. Ja kuigi võite veel näha mustrid juhtub, sel ajal võite ka kuulata, kuidas need algoritmid täidab erinevalt ja mõnevõrra erinevad mustrid. See on sisestamise sort. [Toonid MÄNGIB] DAVID Malan: See jälle üritab sisestada iga element arvesse, kui ta kuulub. See on mull omamoodi. [Toonid MÄNGIB] DAVID Malan: Ja saab omamoodi tunne kuidas suhteliselt vähe tööd ta teeb iga samm. See on see, mida igavus kõlab. [Toonid MÄNGIB] DAVID Malan: See on valiku sorteerida, kus valime elemendi tahame poolt läbimas uuesti ja uuesti ja uuesti ja paneb selle alguses. [Toonid MÄNGIB] DAVID Malan: See on ühendada sort, mis saab tõesti hakata end. [Toonid MÄNGIB] [Naer] DAVID Malan: midagi, mida nimetatakse gnome sort, mida me ei ole vaadanud. [Toonid MÄNGIB] DAVID Malan: Nii et lubage mul näha, et nüüd, segane nagu te loodetavasti on poolt muusika, kui ma ei libise vähe natuke matemaatikat siin. Nii et seal on neljas võimalus, et me ei mõelda, mida see tähendab, need funktsioonid olla kiirem kui need et me oleme näinud. Ja kui sa oled tulemas kursuse matemaatika taust, siis tegelikult teavad ehk juba, et sa saab laksu perspektiivis seda tehnikat - nimelt rekursioon, funktsioon et kuidagi nimetab ennast. Ja jälle meenutada, et Tarkvaraprojekteerimise pseudokoodi oli rekursiivne mõttes et üks Tarkvaraprojekteerimise sammudest oli helistada sort - mis on iseenesest. Aga õnneks, sest me hoida kutsudes sort, või ühendada sorteerida, Konkreetsemalt on väiksemaid ja väiksem nimekirja, me lõpuks põhja tänu mida me kutsume tugipunkti, kodeeritud nii, et ütles, et kui nimekiri on väike, vähem kui 2 sel juhul lihtsalt kohe tagasi. Kui me ei ole, et erijuhul, algoritm oleks kunagi alt välja, ja sa tõesti sattuda lõputu silmuse tõesti igavesti. Aga oletame, et tahame nüüd panna mõned numbrid selle taas kasutades n nagu suurus sisend. Ja ma tahtsin teilt küsida, millised on kogu aeg kaasatud töötab Tarkvaraprojekteerimise? Või üldisemalt mis kulu see aeg? Noh see on üsna lihtne mõõta seda. Kui n on väiksem kui 2 korda kaasatud sorteerimine n elementi, kus n on 2, on 0. Sest me lihtsalt tagasi. Pole mingit tööd teha. Nüüd väidetavalt äkki see on üks samm või kaks samme nuputada summa töö, kuid see on piisavalt lähedal, et 0, et Ma lihtsalt ütlen tööd ei nõutav, kui loetelu on nii väike, tuleb ebahuvitav. Aga sel juhul on huvitav. Rekursiivne juhul oli filiaal pseudokoodi et ütles veel, sorteerida vasakul pool, sorteerida õigus poole, liita kaks poolt. Nüüd miks see väljend Kinnitan, et kulu? Noh, T n tähendab lihtsalt aega, et sortida n elemente. Ja siis paremal pool võrdusmärk seal, T n jagatud 2 viitab kulud, mida? Sorteerimine vasakul pool. Teine T n jagatud 2 on arvatavasti viidates kulusid Kuvatud paremale poole. Ja siis pluss n? Kas ühinevad. Sest kui sul on kaks nimekirja, mis on üks suurus n üle 2 ja teise suurus n üle 2, siis pead sisuliselt puudutada kõik need elemendid, nagu Rob puudutanud iga tassi ja lihtsalt nagu me märkisime igal vabatahtlike laval. Nii n on arvel ühinevad. Nüüd kahjuks see valem on ka ise kirjutan. Seega, kui küsis, kui n on, ütleme, 16, kui seal on 16 inimest laval või 16 tassi video, kui palju kokku samme see võtta neid sorteerida koos Tarkvaraprojekteerimise? See on tegelikult mitte selge vastus, sest nüüd on mingisugune rekursiivselt vastata selle valemi. Aga see on OK, sest lubage mul pakkuda et me teeme järgmine. Ajakulu sortida 16 inimest või 16 tassi läheb esindatud üldiselt kui T 16. Aga mis võrdub vastavalt meie eelmine valem, 2 korda suurem aeg, mis kulub, et järjestada 8 tassi pluss 16. Ja veel, pluss 16 on aeg ühineda, ja kaks korda T 8. on aega, et sortida vasakul pool ja paremal pool. Aga jälle, see ei ole piisav. Meil on sukelduda sügavamale. See tähendab, et me peame vastama küsimus, mis on T 8? Noh T 8. on vaid 2 korda T 4 pluss 8. Nii, mis on T 4? T 4 on lihtsalt 2 korda T 2 pluss 4. Nii, mis on T 2? T 2 on vaid 2 korda T 1 pluss 2. Ja veel, me oleme omamoodi saada kinni selles tsüklis. Aga see on umbes lüüa, et niinimetatud tugipunkti. Sest see, mis on T 1, me väita? 0. Nüüd lõpuks saame teha tagurpidi. Kui T 1 on 0, võin nüüd minna tagasi kuni üks rida see kutt siin, ja ma ei saa pistik 0 T 1. See tähendab, see on võrdne 2 korda null, muidu tuntud 0, pluss 2. Ja nii, et kogu avaldis on 2. Nüüd, kui ma võtan T 2, kelle vastus on 2, ühendage see keset rida, T 4, mis annab mulle 2 korda 2 pluss 4, seega 8. Kui ma siis ühendan 8 eelmise line, et annab mulle 2 korda 8, 16. Ja kui me siis jätkama, et koos 24, lisades 16, me lõpuks saada väärtus 64. Nüüd, ja iseenesest justkui räägib midagi n märke, suur O, omega, mida me oleme rääkinud. Aga selgub, et 64 on tõepoolest 16 suurus sisend, logaritm alusel 2 16. Ja kui see on veidi harjumatu, vaid arvan, et tagasi, ja ta tulen tagasi et sa lõpuks. Kui see on samamoodi baasi 2, see on nagu 2 tõsteti mis annab sulle 16? Oh, see on 4, nii et see on 16 korda 4. Ja veel, see ei ole suur asi, kui see on omamoodi udune mälu nüüd. Aga nüüd, võtta usk et 16 log 16 on 64. Ja nii tõesti, selle lihtsa meelerahu vaadake, me oleme kinnitanud - kuid ei osutunud ametlikult - et sõiduaega ühendamist sort on tõepoolest n log n. Nii ei ole halb. See on kindlasti parem kui algoritme oleme näinud siiani, ja see on sellepärast, et me oleme võimendatud, üks, tehnikat nimega rekursiooni. Aga huvitavam kui see, mis mõiste jagades ja vallutavad. Jällegi tõeliselt nädal 0 kraami, isegi nüüd on taasteket selgem viis. Nüüd lõbus väike harjutus, kui olete kunagi seda teinud - ja siis ilmselt ei oleks, sest omamoodi normaalne inimesed ei usu, et seda teha. Aga kui ma lähen google.com ja kui Ma tahan õppida midagi rekursioon, Enter. [Naer] [MORE naer] DAVID Malan: Bad joke aeglaselt levib. [Naer] DAVID Malan: Igaks juhuks, et see on olemas. Ma ei saa kirjutada seda valesti, ja seal on nali. Hea küll. Selgitage see inimestele sinu kõrval, kui see ei ole päris klõpsanud veel. Aga recursion üldisemalt viitab et protsessi funktsioon helistades ise, või üldisemalt, jagades probleem millekski, mis võib olla lahendada tükkhaaval lahendades identne esindaja probleeme. Noh, olgem käiku vahetada hetkeks. Meile meeldib end teatud cliffhangers, Alustame seada etapp, mitu minutit, on väga lihtne idee - et Vahetatakse kahe elemendi, eks? Kõik need algoritmid me oleme räägi paari viimase loengud hõlmata omamoodi vahetada. Täna oli visualiseeritud neid saada üles välja oma toolid ja jalutamas, kuid kood, oleksime lihtsalt võtta osa ühest array ja sulpsti see teise. Niisiis, kuidas me minna seda teed? Noh, lubage mul minna ja kirjutada kiire programm siin. Ma lähen edasi minna ja teha see on järgmine. Kutsume seda - Mida me tahame helistada see üks? Tegelikult, ei. Lubage mul kerida. Ma ei taha seda teha, pinge veel. See on sõjasaak lõbus. Teeme seda mitte. Oletame, et ma tahan kirjutada vähe programm ning nüüd hõlmab see Idee rekursiooni. Ma nagu sain enne ise seal. Ma lähen tegema järgmist. Esiteks, kiire sisaldavad standardi io.h, samuti nagu on cs50.h. Ja siis ma lähen edasi minna ja deklareerima int main void tavalisel viisil. Mul tuli misnamed faili, nii et Lubage mul lisada. c pikendamine siin nii et saaksime koostada seda korralikult. Alusta seda funktsiooni välja lülitada. Ja funktsioon ma tahan kirjutada, üsna lihtsalt, on üks, mis palub kasutaja number ja siis lisab kõik numbrid vahel, et number ja, ütleme, 0. Nii et kõigepealt ma lähen edasi minna ja deklareerima int n. Siis ma saan kopeerida mõned kood, mis Me kasutasime mõnda aega. Kuigi midagi on tõsi. Ma tulen tagasi, et hetkel. Mida ma tahan teha? Ma tahan öelda printf positiivne täisarv palun. Ja siis ma lähen öelda n saab saada int. Nii et taas, mõned stereotüüp kood et me oleme varem kasutanud. Ja ma kavatsen seda teha kui n on väiksem kui 1. Nii, et see tagab, et kasutaja annab mulle positiivne täisarv. Ja nüüd ma lähen tegema järgmist. Tahan lisada kuni kõik numbrid vahemikus 1 ja n või 0 ja n, võrreldavalt saada kogu summa. Nii suur sigma sümbol et te võiks meenutada. Nii et ma lähen tegema seda esimene helistaja funktsiooni nimetatakse sigma, kulgeb seda n, ja siis ma lähen öelda printf, vastus on siin. Nii lühike, saan ja int kasutaja. Ma veenduge, et see on positiivne. Kinnitan muutuja nimega vastus tüüpi int ja kaupluse see tagasi väärtus sigma, läbides n sisendiks. Ja siis ma välja printida, et vastata. Kahjuks, kuigi sigma kõlab nagu midagi, mis võiks olla math.h fail oma avalduses, see on tegelikult mitte. Nii et pole midagi. Võin rakendada seda ise. Ma lähen, et rakendada funktsioon nimega sigma ja see vőtab parameeter - Ütleme nii, et m, lihtsalt nii et see on teistsugune. Ja siis siin, ma lähen öelda, Noh, kui m on alla 1 - see on väga ebahuvitav programm. Nii et ma lähen edasi minna ja kohe tagasi 0. See lihtsalt ei ole mõtet lisada kuni kõik numbrid vahemikus 1 m, kui m ise 0 või negatiivne. Ja siis ma lähen edasi minna ja seda väga korduvalt. Ma teen seda omamoodi vana kooli, ja ma lähen edasi minna ja öelda, et ma lähen kuulutada summa olema 0. Siis ma lähen on jaoks silmus int - ja las ma teen seda, mis vastavad meie jaotus kood, nii et teil on koopia kodus. int i saab 1 kuni i on väiksem või võrdne m. i pluss pluss. Ja siis seestpoolt seda loop - me oleme peaaegu kohal - summa muutub summa pluss 1. Ja siis ma lähen tagasi summa. Nii et ma tegin seda kiiresti, päris tõsi. Aga jälle, mille peamine ülesanne on päris arusaadav, mis põhineb kood oleme kirjaliku siiani. Kasutab dual loop saada positiivne int kasutaja. Ma siis edasi, et int uue funktsiooni nimetatakse sigma, nimetades seda jällegi n. Ja ma salvestada tagastatav väärtus, vastus alates musta kasti praegu tuntud Sigma, muutuv kutsutud vastus. Siis ma printida. Kui nüüd jätkata lugu, kuidas on sigma rakendada? Teen ettepaneku rakendada järgmised. Esiteks natuke Tõrkekontroll veenduda, et kasutaja ei mulle jama ja kulgeb mõned negatiivsed või 0 väärtust. Siis ma kuulutada muutuja nimega Kokkuvõttes ja sisesta 0.. Ja nüüd ma hakkan liikuma i võrdub 1. kõik viis kuni m, sest ma tahan, et see hõlmaks kõiki numbrid ühest kuni m, kaasa arvatud. Ja sees selle jaoks silmus, ma lihtsalt teha summa muutub mis iganes see on nüüd, pluss väärtus i. Plus väärtus i. Nagu kõrvale, kui sul ei ole seda näinud enne, seal on mõned süntaktiline suhkur Selle liini. Võin selle uuesti kirjutada pluss võrdub i, lihtsalt säästa ennast mõne klahvivajutusega ja vaatama natuke jahedam. Aga see on kõik. See on funktsionaalselt sama asi. Kahjuks on see kood on ei kavatse koostada veel. Kui ma saan teha sigma 0, kui olen Ma hakka karjus? Kuidas see läheb ei meeldi? Publik: [kuuldamatu]. DAVID Malan: Jah, ma ei tunnistanud funktsioon üleval, eks? C on tobe, sest see ainult teeb mida sa öelda tahad, ja sa on seda teha selles järjekorras. Ja nii kui ma Enter siin, ma lähen saada hoiatuse sigma kaudne deklaratsioon. Oh, ei ole probleem. Ma ei saa minna kuni top, ja ma ei öelda, olgu, oota natuke. Sigma on funktsioon, mis tagastab int ja see eeldab int sisend, semikoolon. Või ma võiksin panna kogu funktsioon eespool peamine, kuid üldiselt, ma soovitan vastu, et kuna see on tore on alati peamine tipus nii saate sukelduda paremale ja teavad, mida Programm teeb lugedes peamine esimene. Nüüd lubage mul selge ekraan. Uusversiooni sigma 0. Kõik tundub, et kontrollida. Lubage mul joosta sigma 0. Positiivne muu. Ma annan see number 3. hoida lihtsa. Nii et peaks mulle 3 pluss 2 pluss 1, seega 6. Sisesta ning tõepoolest saan 6. Ma ei tee midagi suuremat - 50, 12, 75. Just nagu puutuja, ma lähen tegema midagi naeruväärne nagu tõesti suur number, Oh, mis tegelikult välja töötatud - eh, ma ei usu, et see on õige. Vaatame. Olgem tõesti jama see. See on probleem. Mis toimub? Kood ei ole nii halb. See on ikka lineaarne. Vilistamine on hea mõju, kuigi. Mis toimub? Ei ole kindel, kui ma kuulsin seda. Nii selgub - ja see on nagu kõrvale. See ei ole tuum Idee rekursiooni. Selgub, sest ma üritan esindab nii suur number, kõige tõenäoliselt see kuramuse valesti poolt C, ei positiivne arv, kuid negatiivne number. Me ei ole sellest rääkinud, kuid see Selgub, on negatiivsed arvud maailmas lisaks positiivseid numbreid. Ja vahendid, mille abil saab esindama negatiivne arv sisuliselt on, siis kasutage ühte eriline natuke näidata positiivne jooksul negatiivne. See on natuke keerulisem kui see, aga see on põhiidee. Nii kahjuks kui C ajab üks need bitti kui tegelikult tähendab, oh, see on negatiivne arv, mu loop siin näiteks on tegelikult kunagi kavatse lõpetada. Nii et kui ma tegelikult trükkimine midagi ikka ja jälle, oleksime vaata palju. Aga jälle, see on peale punkti. See on tõesti lihtsalt omamoodi intellektuaalne uudishimu, et me tuleme Tagasi lõpuks. Aga nüüd, et see on õige rakendamist, kui me eeldame, et kasutaja annab ints mis mahuvad ints. Aga ma väita, et see kood, ausalt, võiks teha nii palju lihtsalt. Kui eesmärk käepärast on võtta mitmeid nagu m ja liita kõik numbrite vahel see ja 1 või vastupidi vahel 1 ja see, ma väita, et võin seda laenata idee, et ühendada sort oli, mis oli võttes probleem Selle suurus ja jagades selle millekski väiksem. Võib-olla mitte pool, aga väiksem, kuid esindavad sama. Sama mõte, kuid väiksem probleem. Nii et ma olen tegelikult - las ma salvestan selle faili erineva versiooni number. Me nimetame seda versiooni 0 asemel 1. Ja ma väita, et ma ei saa tegelikult implementeerid seda selline Raske tee. Ma jätan selle osa üksi. Ma ütlen, kui m on vähem kui või isegi võrdne 0 - Ma lihtsalt olema natuke rohkem anal seekord minu viga kontroll - Ma lähen edasi minna ja tagasi 0. See on meelevaldne. Ma lihtsalt lihtsalt otsustada, kas kasutaja annab mulle negatiivne number, ma olen tagasi 0 ja nad oleks pidanud lugema dokumentatsioon tihedamalt. Muu - teate, mida ma teen. Else ma tagasi m pluss - mis on sigma m? Noh, sigma m pluss m miinus 1, pluss m miinus 2, pluss m miinus 3. Ma ei taha, et kirjutada kõik, et välja. Miks ma ei lihtsalt punt? Rekursiivselt kutsuvad ennast veidi väiksem probleem, semikoolon, ja nimetavad seda päeva? Õigus? Nüüd ka siin, võite tunda või muretsema et see on lõputu silmuse, et ma olen tekitavaid, mille ma olen rakendamisel sigma väljakutsel sigma. Aga see on täiesti OK, sest ma arvasin enne lisatud, mis read? Publik: [kuuldamatu]. DAVID Malan: 23-26, mis on minu kui seisukorras. Sest see, mis on ilus umbes lahutamine siin, sest ma hoida teisaldus sigma väiksemad probleemid, väiksem probleeme, väiksem - see ei ole poole väiksem. See on ainus laps samm väiksem, kuid see on OK. Sest lõpuks, me töö meie tee alla 1 või 0. Ja kui me tabanud 0, Sigma ei läheb kutsuvad ennast enam. See läheb kohe tagasi 0. Seega mõju, kui sa omamoodi tuul see üles meelt, on lisada m pluss m miinus 1 pluss m miinus 2, pluss m miinus 3, pluss dot, dot, dot, m miinus m, lõpuks annab teile 0, ja mõju on lõpuks lisada kõik need asjad kokku. Nii et me ei ole, kus rekursioon, lahendada probleemi, et me ei suudetud lahendada enne. Tõepoolest, versioon 0 sellest ja iga probleem siiani olnud lahendatav vaid kasutades silmuseid või kui silmuseid vms konstrueerib. Aga rekursioon, Julgen öelda, annab meile teistmoodi mõtlema probleeme, mille kohaselt juhul saame probleem, jagada see midagi mõnevõrra suur millekski mõnevõrra väiksem, ma väita, et me saame seda lahendada võibolla veidi rohkem elegantselt poolest disain, kus on vähem koodi, ja võib-olla isegi lahendada probleeme, mis olla raskem, kui paneme lõpuks vaata, lahendades puhtalt korduvalt. Aga pinge, mis ma tegin, taha jätta meid oli see. Lubage mul minna ja avada üles faili - tegelikult, lase mul minna ja seda päris kiiresti. Lubage mul minna ja ettepanekuid järgmised. Seas tänane kood on see pilt siin. See üks siin, noswap. Nii et see on rumal väike programm, mis Ma vahustatud up et väited, mida teha järgmised. In peamine, see esimene deklareerib int nimetatakse x ja annab see väärtus 1. Siis ta teatab, int y ja määrab see väärtus 2. Siis ta prindib välja, mis x ja y on. Siis ta ütleb, vahetada, dot dot dot. Seejärel väidab ta, et kutsudes funktsioon kutsutakse swap, läbides x ja y, idee, mis on see, et loodetavasti x ja y tulevad tagasi erinevad, vastupidine. Siis väidavad vahetasid! hüüumärk. Siis ta prindib välja x ja y. Aga selgub, et see väga lihtne tutvustamise alla siin on tegelikult lollakas. Kuigi ma kuulutab ajutine muutuv ja ajutiselt panna sisse , siis ma ümberjagamise väärtus b - mis tundub mõistlik, sest ma olen salvestatud koopia ka temp. Siis ma uuendada b võrdsele mis iganes oli temp. Selline kest mäng liigub arvesse B ja b ümber, kasutades seda Lähis-nimeline mees temp tunneb täiesti mõistlik. Aga ma väita, et kui ma saan seda kood, nagu ma teen nüüd - lase mul minna ja kleebi see siin. Ma nimetan seda noswap.c. Ja nagu nimigi ütleb, ei ole see kavatse olla õige programm. Tee noswap. / Ei swap. x on 1, y on 2, vahetada, vahetada. x on 1, y 2. See on põhimõtteliselt vale, isegi kuigi see tundub täiesti mõistlik mulle. Ja seal on põhjus, kuid me ei ole kavatse paljastada põhjus veel. Nüüd teine ​​pinge tahtsin lahkuda teile on see, teadaanne kehvasti edasi Kupongi koodid. Meie innovatsiooni hilinenud päeva tänavu on tekitanud mitte-triviaalne number küsimusi, mis on mitte meie eesmärk. Kavatsusega need Kupongi koodid, kusjuures, kui sa osa probleemist seada varakult, seeläbi muutub lisapäev, oli tõesti aidata teid aidata ise alustada varakult, sorteerida teel Lisatasusid lubavad sulle. Aitab meil levitada lasti üle tööaega paremini, et see on omamoodi võidavad. Kahjuks ma arvan, et minu juhiseid ei ole olnud siiani väga selge, et Läksin tagasi sel nädalavahetusel ja ajakohastatud spec suurem, julgem teksti selgitada täppe nagu need. Ja just seda öelda veel avalikult, mida Vaikimisi probleem komplekti on tingitud neljapäev Keskpäeval kohta ainekava. Kui alustate varakult, viimistlus osa probleem kehtestatud kolmapäeval kell 12:00 PM, see osa, mis on seotud kupong kood, idee on see, et saate laiendada oma tähtpäeva P seada kuni reede. See on natuke off tilluke osa P määrata suhteline, mida tavaliselt on suurem probleem, ja kui osta ise lisapäev. Jällegi, see läheb sa mõtled Ülesanded, saab teil tööajal varem. Aga kuponkikoodi probleem on endiselt nõutav, isegi kui sa ei esita see. Aga rohkem compellingly on see. (Lavasosin) Ja need inimesed lahkuvad vara on veel kahetsed seda. Nagu on inimesed rõdul. Vabandan ette, et inimesed on rõdu põhjustel, mis on selge hetk. Nii et meil on õnnelik, et on üks CS50 endine juht õpetamise stipendiaatide kell firma nimega dropbox.com. Nad on väga heldelt annetatud kuponkikoodi siin nii palju ruumi, mis on üles tavaliselt 2 gigabaiti. Niisiis, mida ma arvasin, et me teeks seda Lõpetuseks on teha natuke give kusjuures vaid hetk, me paljastada võitja ja kes on kupong kood, mis saab siis minna oma kodulehel, kirjuta see ja voila, saada palju rohkem Dropbox ruumi oma seadme ja oma isiklikke faile. Ja esimene, kes sooviksid osaleda Selles joonisel? OK, nüüd, mis muudab ta isegi lõbusam. Isik, kes saab see 25 GB kuponkikoodi - mis on palju ahvatlevamaks kui hilja päeva nüüd, ehk - on see, kes istub peal istmepadja all, mis on et kuponkikoodi. Nüüd võite vaadata all oma istmepadja. [VIDEO PLAYBACK] -Üks, kaks, kolm. [Karjuvad] -Sa saad auto! Sa saad auto! DAVID Malan: Me näeme, sa kolmapäeval. -Sa saad auto! Sa saad auto! Sa saad auto! Sa saad auto! Sa saad auto! DAVID Malan: Rõdu inimesed, tulge siia alla ees, kus meil on lisad. -Kőik saab auto! Igaüks saab auto! [END VIDEO PLAYBACK] Jutustaja: Järgmisel CS50 - SPEAKER 5: Issake jumal jumal jumal issand jumal jumal jumal jumal jumal - [Ukelele PLAYS]