Allt í lagi, svo computational flókið. Bara smá viðvörun áður en við kafa í of far-- þetta verður sennilega að vera meðal mest stærðfræði-þungur hlutur við tölum um í CS50. Vonandi mun það ekki vera of yfirþyrmandi og við munum reyna að leiða þig gegnum ferlið, en bara hluti af Fair Warning. Það er svolítið af stærðfræði þátt hér. Allt í lagi, svo í því skyni að gera Notkun computational auðlindir okkar í alvöru world-- það er í raun mikilvægt að skilja reiknirit og hvernig þeir vinna úr gögnum. Ef við höfum mjög duglegur reiknirit, við getur lágmarka magn af fjármagni við höfum í boði til að takast á við það. Ef við höfum reiknirit sem er að fara að taka a einhver fjöldi af vinna að vinna mjög stór sett af gögnum, það er að fara að krefjast meira og fleiri úrræði, sem er peningar, RAM, allt að hvers konar efni. 

Svo, að vera fær um að greina að reiknirit nota þetta tól setja, grundvallaratriðum, spyr question-- hvernig virkar þetta reiknirit mælikvarða eins og við kasta fleiri og fleiri gögn á það? Í CS50, hversu mikið af gögnum sem við erum vinna með er nokkuð lítið. Almennt eru forrit okkar fara að keyra í annað eða less-- sennilega mikið minni sérstaklega snemma. 

En hugsa um fyrirtæki sem fæst með hundruð milljóna viðskiptavina. Og þeir þurfa að vinna sem viðskiptavinur gögn. Sem fjöldi viðskiptavina sem þeir hafa fær stærri og stærri, það er að fara að krefjast fleiri og fleiri úrræði. Hversu margir fleiri auðlindir? Jæja, það fer eftir því hvernig við greina reiknirit, nota verkfæri í þessari kistu. Þegar við tölum um flókið An algorithm-- sem stundum þú munt heyra það nefnt tíma flókið eða rúm flókið en við erum bara að fara að hringja complexity-- við erum yfirleitt að tala um versta falli. Í ljósi alger versta stafli af gögn sem við gætum verið að henda á það, hvernig er þetta reiknirit fara að vinna eða takast á við þessi gögn? Við köllum yfirleitt versta afturkreistingur af reiknirit stór-O. Svo reiknirit mætti ​​segja að hlaupa í O á n eða O í n veldi. Og meira um hvað þá meina í annað. 

Stundum, þó, gera við umönnun um besta falli atburðarás. Ef gögn er allt sem við vildum það að vera og það var fullkomið og við vorum að senda þetta fullkomið setja af gögnum í gegnum reiknirit okkar. Hvernig væri það höndla í því ástandi? Við vísa stundum til að sem stór-Omega, svo ólíkt stór-O, við höfum stóra-Omega. Big-Omega fyrir besta falli atburðarás. Big-O fyrir versta. Almennt, þegar við tölum um flókið reiknirit, við erum að tala um versta. Svo halda að í huga. 

Og í þessum flokki, við erum almennt að fara að yfirgefa strangt greiningu hliðar. Það eru vísindi og sviðum helgaður þessu tagi efni. Þegar við tölum um rökhugsun gegnum reiknirit, sem við munum gera stykki-við-stykki fyrir marga reiknirit við tölum um í bekknum. Við erum í raun bara að tala um reasoning gegnum það með skynsemi, ekki með formúlur eða fylgigögn, eða eitthvað svoleiðis. Svo ekki hafa áhyggjur, Við munum ekki vera beygja inn í a stór stærðfræði bekknum. 

Svo ég sagði við vænt um flókið vegna þess að það spyr spurningu, hvernig ekki reiknirit okkar höndla stærri og stærri gagnagrunna verið kastað á þá. Jæja, hvað er gögnum? Hvað gerði ég meina þegar ég sagði það? Það þýðir hvað gerir mest vit í samhengi, til að vera heiðarlegur. Ef við höfum reiknirit, á Processes Strings-- erum við líklega að tala um stærð af the band. Það er gögn set-- stærð, fjölda stafi sem mynda band. Ef við erum að tala um að reiknirit sem vinnur skrár, við gætum verið að tala um hvernig margir kílóbæti samanstanda að skrá. Og það er gögnum. Ef við erum að tala um reiknirit sem annast fylki almennt, svo sem flokkun reiknirit eða leita reiknirit, við erum líklega að tala um fjölda þætti sem samanstanda fylki. 

Nú getum við mæla sem algorithm-- einkum, þegar ég segi við getum mæla algrím, ég meina við getum mælt hversu margar auðlindir sem það tekur upp. Hvort þessar auðlindir eru, hversu margir bytes RAM-- eða megabæti af RAM það notar. Eða hversu mikinn tíma það tekur að keyra. Og við getum kallað þetta mæla, geðþótta, f á n. Þar sem n er fjöldi þættir í gögnum. Og f n er hversu margir somethings. Hversu margar einingar af auðlindum er það þurfa að vinna þessi gögn. 

Nú, reyndar við ekki sama um hvað f n er nákvæmlega. Í raun erum við will-- mjög sjaldan vissulega mun aldrei í þessu class-- I kafa í hvaða raunverulega djúpt greining á því hvaða f-n er. Við erum bara að fara að tala um hvað f n er um eða hvað það hefur tilhneigingu til að. Og tilhneigingu reiknirit er ráðist af hæsta röð þess tíma. Og við getum séð hvað ég meina með því með því að taka a líta á áþreifanlegri dæmi. 

Svo skulum segja að við höfum þrjár mismunandi reiknirit. Fyrsta sem tekur N cubed, sumum einingum auðlindir að vinna úr gögnum sett af stærð n. Við höfum annað reiknirit sem tekur n cubed plús n veldi auðlindir að vinna úr gögnum sett af stærð n. Og við höfum þriðja reiknirit sem keyrir in-- að tekur upp n cubed mínus 8n veldi auk 20 n einingar af auðlindum að vinna reikniriti með gögn sem sett eru af stærð n. 

Nú aftur, við í raun ekki að fara að komast inn í þennan nákvæmnina. Ég er í raun bara hafa þetta upp hér til skýringar punkti sem ég ætla að vera gera í annað, sem er að við sama bara virkilega um tilhneigingu hlutum sem gagnagrunnar fá stærri. Þannig að ef gögnum er lítill, það er reyndar mjög mikill munur í þessum reiknirit. Þriðja reiknirit það tekur 13 sinnum lengur, 13 sinnum the magn af fjármagni að keyra miðað við það fyrsta. 

Ef gögnum okkar er stærð 10, sem er stærri en ekki endilega mikið, getum við séð að það er reyndar svolítið af a mismunur. Þriðja reiknirit verður skilvirkari. Það er um raunverulega að 40% - eða 60% skilvirkari. Það tekur 40% af því magni af tíma. Það getur run-- það getur tekið 400 einingar af auðlindum að vinna úr gögnum sett af stærð 10. En fyrsta reiknirit, hins vegar tekur 1.000 einingar af auðlindum að vinna úr gögnum sett af stærð 10. En líta hvað gerist þegar númer okkar fá jafnvel stærri. 

Nú er munurinn milli þessara reiknirit byrja að verða svolítið minna áberandi. Og sú staðreynd að það eru minni röð terms-- eða öllu heldur, Skilmálar með lægri exponents-- byrja að verða óviðkomandi. Ef gögnum er stærð 1000 og fyrsta reiknirit keyrir í milljarð skrefum. Og seinni reiknirit keyrir í milljarð og milljón skref. Og þriðja reiknirit keyrir í bara feiminn af milljarð skrefum. Það er ansi mikið milljarð skref. Þeir minni pöntun skilmálar byrja að verða mjög óviðkomandi. Og bara til að virkilega hamar heim í point-- ef gögn inntak er stærðar million-- öll þrjú af þessum ansi mikið taka einn quintillion-- ef stærðfræði minn er correct-- skref að vinna gögn inntak stærð milljón. Það er mikið af skrefum. Og sú staðreynd að einn af þeim gæti taka nokkra 100.000 eða nokkra 100 milljónir jafnvel minna þegar við erum að tala um fjölda að big-- það er góður af óviðkomandi. Þeir allir tilhneigingu til að taka um n cubed, og svo við myndum í raun átt að allar þessar reiknirit eins og að vera á röð n cubed eða stór-O n cubed. 

Hér er listi af sumir af the fleiri algengar computational bekkjum flókið að við munum lenda í reiknirit, almennt. Og einnig sérstaklega í CS50. Þetta er raðað frá almennt festa efst, almennt hægur neðst. Svo föstu reiknirit hafa að vera the festa, óháð til stærðar á gögn inntak þú fara í. Þeir taka alltaf eina aðgerð eða ein eining af auðlindum til að takast á við. Það gæti verið 2, gæti það vera 3, gæti það verið 4. En það er stöðug tala. Það breytist ekki. 

Lógaritmískum tíma reiknirit eru örlítið betri. Og mjög gott dæmi um Logarythmiskur tími reiknirit þú hefur örugglega séð nú er rífa í sundur af símaskránni að finna Mike Smith í símaskránni. Við skera vandamál í tvennt. Og svo eins og n fær stærri og stærri og larger-- í raun í hvert skipti sem þú tvöfaldur n, það tekur aðeins eitt skref. Svo það er mikið betra en, segjum, línuleg tími. Sem er ef þú tvöfaldur n, það tekur tvöfalda fjölda af skrefum. Ef þú þrefaldur n, það tekur þrefalda fjölda skrefum. Eitt skref á hverja einingu. 

Þá það fá smá more-- aðeins minna mikill þaðan. Þú hefur línulega takt tíma, stundum kallaði þig línuleg tími eða bara n log n. Og við munum dæmi af reiknirit sem keyrir í n log n, sem er enn betra en annars stigs time-- n veldi. Eða margliða tíma, n tveir allir tala meiri en tveir. Eða veldisvísis tíma, sem er jafnvel worse-- C í n. Svo sumir stöðug tala hækkuð í kraftur stærð inntak. Þannig að ef það er 1,000-- standi gögn inntak af stærð 1.000, það myndi taka C til 1.000 th völd. Það er mikið verra en margliðunnar tíma. 

Factorial tími er jafnvel enn verra. Og í raun, það er í raun að gera eru óendanlega tíma reiknirit, svo sem, svokölluð heimskur sort-- sem starf er að handahófi uppstokkun fylki og þá athuga hvort sem það er flokkað. Og ef það er ekki, af handahófi uppstokkun array aftur og athuga til að sjá hvort það er flokkað. Og eins og þú geta sennilega imagine-- þú getur ímyndað sér aðstæður hvar í versta falli, að vilji aldrei að byrja með array. Að reiknirit myndi hlaupa að eilífu. Og svo að væri óendanlegur tími reiknirit. Vonandi verður þú ekki vera að skrifa allir þáttatilraun eða óendanlega tíma reiknirit í CS50. 

Svo, við skulum taka a lítill fleiri steypu líta á sumir einfaldara computational flókið bekkjum. Þannig að við höfum example-- eða tvö dæmi here-- föstu tíma reiknirit, sem alltaf taka einn gangur í versta falli. Svo fyrsta example-- við höfum virka kallað 4 fyrir þig, sem tekur á fjölbreytta stærð 1.000. En þá virðist er í raun ekki líta á it-- er eiginlega alveg sama hvað er inni af því, að þessi fylking. Alltaf bara skilar fjórum. Svo, að reiknirit, Þrátt fyrir að það tekur 1.000 þætti ekki gera neitt með þeim. Bara skilar fjórir. Það er alltaf einu skrefi. 

Í raun, bæta við 2 nums-- sem við höfum séð áður og well-- bara ferli tvær heiltölur. Það er ekki einu skrefi. Það er í raun nokkur skref. Þú færð, þú færð b, þú bætir við þeim saman, og þú framleiðsla niðurstöður. Svo það er 84 skrefum. En það er alltaf stöðug, óháð a eða b. Þú þarft að fá, fá b, bæta þá saman, framleiðsla niðurstaðan. Svo er það stöðug tími reiknirit. 

Hér er dæmi um a línuleg tími algorithm-- reiknirit sem gets-- sem tekur einu viðbótar skref, hugsanlega, eins inntak vex um 1. Svo, við skulum segja að við erum að leita að fjöldi 5 inni fylki. Þú gætir hafa aðstæður þar þú getur fundið það nokkuð snemma. En þú getur líka hafa ástand þar sem það gæti verið síðasta þáttur í array. Í fjölda af stærð 5, ef við erum að leita að númer 5. Það myndi taka 5 skref. Og í raun, ímynda sér að það er ekki 5 hvar sem er í þessu fylki. Við enn í raun að líta á hvert einasta þáttur í fylkinu í því skyni að ákvarða hvort 5 er þar. 

Svo í versta tilfelli, sem er að þáttur er síðasta í array eða er ekki til á öllum. Við höfum enn að horfa á öllu af N þáttum. Og svo þetta reiknirit keyrir í línulegum tíma. Þú getur staðfest það með því að framreikna svolítið með því að segja, ef við hefðum 6 þátturinn array og við vorum að leita að númer 5, það gæti tekið 6 skrefum. Ef við höfum 7 þátturinn array og við erum að leita að númer 5. Það gæti tekið 7 skrefum. Eins og við bæta við einum stak okkar array, það tekur eitt skref. Það er línulegt reiknirit í versta falli. 

Par fljótur spurningar fyrir þig. Hvað er runtime-- hvað er versta afturkreistingur af þessu tiltekna runu af kóða? Þannig að ég hef 4 lykkju hér sem keyrir frá J jafngildir 0, alla leið upp að m. Og það sem ég er að sjá hér, er að Lík lykkju keyrir á föstu tíma. Svo nota hugtök sem við höfum þegar talað about-- hvað væri versta afturkreistingur þessa reiknirit? Taktu annað. Innri hluta lykkju keyrir í föstu tíma. Og ytri hluti af lykkja er að fara að keyra m sinnum. Svo er það versta afturkreistingur hér? Vissir þú giska stór-O á m? Þú vilt vera rétt. 

Hvernig væri annað? Í þetta sinn höfum við lykkja inni í lykkju. Við höfum ytri lykkju sem liggur frá núll til bls. Og við höfum innra lykkja sem keyrir frá núll til p, og inni í því, Ég fullyrði að líkaminn er lykkja keyrir á föstu tíma. Svo er það versta afturkreistingur af þessu tiltekna runu af kóða? Jæja, aftur, við höfum ytri lykkja sem keyrir bls sinnum. Og hver time-- endurtekning þeirrar lykkju, frekar. Við höfum innra lykkja sem einnig rekur bls sinnum. Og þá inni að það er stöðug time-- lítið runu þar. 

Svo ef við höfum ytri lykkja sem rekur p sinnum inni sem er innri lykkja sem rekur bls times-- hvað er versta afturkreistingur þessarar runu af kóða? Vissir þú giska stór-O p veldi? 

Ég er Doug Lloyd. Þetta er CS50.