Haki wote, hivyo, kuhesabu utata. Kidogo tu ya onyo kabla ya sisi kupiga mbizi katika pia far-- hii pengine utasikia kuwa miongoni mwa mambo ya hesabu-nzito tunazungumzia kuhusu katika CS50. Nadhani itakuwa si kuwa pia balaa na tutaweza kujaribu na kuongoza wewe kupitia mchakato, lakini kidogo tu ya onyo haki. Kuna kidogo ya hisabati kushiriki hapa. Haki wote, hivyo ili kufanya matumizi ya rasilimali zetu Computational katika world-- halisi ni kweli muhimu kuelewa algorithms na jinsi mchakato wa data. Kama tuna kweli algorithm ufanisi, sisi unaweza kupunguza kiasi cha rasilimali tuna inapatikana kwa kukabiliana nayo. Kama tuna algorithm kwamba ni kwenda kuchukua mengi ya kazi na mchakato wa kweli kuweka kubwa ya data, ni kwenda zinahitaji zaidi na rasilimali zaidi, ambayo ni fedha, RAM, kwamba aina zote za mambo ya ajabu. 

Hivyo, kuwa na uwezo wa kuchambua algorithm kutumia seti chombo hiki, kimsingi, anauliza question-- jinsi gani hii algorithm wadogo kama sisi kutupa data zaidi na zaidi katika hilo? Katika CS50, kiasi cha data tuko kufanya kazi na ni pretty ndogo. Kwa ujumla, mipango yetu ni kwenda kuendesha katika pili au less-- pengine mengi chini hasa mapema. 

Lakini fikiria kampuni hiyo mikataba na mamia ya mamilioni ya wateja. Na wanahitaji mchakato kwamba data kwa wateja. Kama idadi ya wateja wao na anapata kubwa na kubwa zaidi, itakuja kuhitaji zaidi na zaidi na rasilimali. Jinsi wengi zaidi rasilimali? Naam, hiyo inategemea jinsi sisi kuchambua algorithm, kutumia zana katika sanduku la vifaa hii. Tunapozungumzia kuhusu utata wa algorithm ambayo wakati mwingine utasikia kusikia inajulikana kama wakati utata au nafasi utata lakini tunakwenda tu kuwaita complexity-- sisi ni ujumla kuzungumza juu ya mbaya zaidi kesi. Kutokana na mbaya kabisa rundo la data kwamba tunaweza kutupa saa hiyo, jinsi ni algorithm hii kwenda mchakato au kukabiliana na takwimu ambazo? Sisi kwa ujumla kuwaita mbaya zaidi kesi Runtime ya algorithm big-O. Hivyo algorithm inaweza kuwa alisema kukimbia katika O ya n au O ya n squared. Na zaidi juu ya nini wale maana katika pili. 

Wakati mwingine, ingawa, sisi kufanya huduma kuhusu bora kesi. Kama data ni kila kitu tulitaka kuwa ni na ilikuwa kamilifu kabisa na tulikuwa kutuma hii kamili seti ya data kwa njia ya kompyuta yetu. Jinsi gani ni kushughulikia katika hali hiyo? Sisi wakati mwingine kutaja kwamba kama big-Omega, hivyo tofauti na big-O, tuna big-Omega. Big-Omega kwa bora kesi. Big-O kwa hali mbaya zaidi kesi. Kwa ujumla, wakati sisi majadiliano juu utata wa algorithm, tunazungumzia mbaya zaidi kesi. Hivyo kuendelea kuwa katika akili. 

Na katika darasa hili, tuko kwa ujumla kwenda kuondoka uchambuzi ukali kando. Kuna sayansi na mashamba kujitoa kwa aina hii ya mambo. Tunapozungumzia kuhusu hoja kupitia algorithms, ambayo tutaweza kufanya kipande-by-kipande kwa wengi algorithms tunazungumzia kuhusu darasani. Sisi ni kweli tu kuzungumza juu ya hoja kwa njia hiyo kwa akili ya kawaida, si kwa kanuni, au hoja, au kitu kama hicho. Hivyo msiwe na wasiwasi, Hatutaki kuwa kugeuka katika hesabu kubwa darasani. 

Kwa hiyo mimi nikasema sisi huduma ya juu utata kwa sababu anauliza swali, jinsi Je, algorithms wetu kushughulikia kubwa na seti kubwa data kutupwa saa yao. Naam, ni nini seti data? Je, I mean wakati mimi alisema kuwa? Ina maana chochote hufanya wengi maana katika mazingira, kuwa waaminifu. Kama tuna algorithm, Taratibu Strings-- tuko pengine kuzungumza juu ya ukubwa wa kamba. Hiyo ni takwimu set-- ukubwa, idadi ya wahusika kwamba kufanya juu ya kamba. Kama tunazungumzia algorithm kwamba michakato mafaili, tupate kuzungumza kuhusu jinsi kilobytes wengi wanaunda faili hilo. Na hiyo ndiyo kuweka data. Kama tunazungumzia juu ya algorithm ambacho kinafanya arrays kwa ujumla zaidi, kama vile kuchagua algorithms au kutafuta algorithms, sisi ni pengine kuzungumza juu idadi ya mambo ambayo wanaunda safu. 

Sasa, tunaweza kupima algorithm hasa, wakati mimi kusema tunaweza kupima algorithm, mimi maana tunaweza kupima jinsi rasilimali nyingi inachukua up. Kama rasilimali hizo ni, jinsi wengi ka wa RAM-- au megabaiti ya RAM anatumia. Au ni kiasi gani wakati inachukua kukimbia. Na tunaweza kuwaita hii kupima, kiholela, f ya n. Ambapo n ni idadi ya mambo katika kuweka data. Na f ya n ni somethings wangapi. Jinsi vitengo ya rasilimali nyingi anafanya ni zinahitaji mchakato wa data hiyo. 

Sasa, sisi kweli hawana huduma kuhusu nini f la n ni sawa kabisa. Kwa kweli, sisi mara chache sana will-- hakika kamwe katika hili mimi class-- mbizi katika yoyote kwa kweli kina Uchambuzi wa nini f la n ni. Sisi ni kwenda tu kuzungumza kuhusu nini f ya n ni takriban au nini inaelekea. Na tabia ya algorithm ni dictated na utaratibu wake wa juu mrefu. Na tunaweza kuona nini mimi maana na kwamba kwa kuchukua a tuangalie mfano thabiti zaidi. 

Basi hebu kusema kwamba tuna algorithms tatu tofauti. Kwanza ambayo inachukua n cubed, baadhi ya vitengo ya rasilimali na mchakato wa kuweka data ya ukubwa n. Tuna algorithm pili kwamba inachukua n cubed pamoja na rasilimali n squared na mchakato wa kuweka data ya ukubwa n. Na tuna tatu algorithm kwamba anaendesha in-- kwamba unachukua n cubed bala 8n mraba pamoja na 20 n vitengo ya rasilimali na mchakato algorithm na data seti ya ukubwa n. 

Sasa tena, sisi kweli si kwenda kupata katika ngazi hii ya kina. Mimi nina kweli tu na hizi up hapa kama mfano wa hatua kwamba mimi nina kwenda kuwa kufanya katika pili, ambayo ni kwamba sisi tu kweli huduma kuhusu tabia ya mambo kama data seti kupata kubwa. Hivyo kama seti data ni ndogo, kuna kweli tofauti pretty kubwa katika algorithms haya. Algorithm tatu kulikuwa inachukua mara 13 tena, Mara 13 kiasi cha rasilimali kuendesha jamaa na moja ya kwanza. 

Kama kuweka wetu data ni ukubwa 10, ambayo ni kubwa, lakini si lazima kubwa, tunaweza kuona kwamba kuna kweli kidogo ya tofauti. Algorithm tatu inakuwa ufanisi zaidi. Ni kuhusu kweli 40% - au 60% ufanisi zaidi. Inachukua 40% ya kiasi cha muda. Ni inaweza run-- inaweza kuchukua Vitengo 400 wa rasilimali na mchakato wa kuweka data ya ukubwa 10. Wakati kwanza algorithm, kwa kulinganisha, inachukua vitengo 1,000 ya rasilimali na mchakato wa kuweka data ya ukubwa 10. Lakini angalia nini kinatokea kama idadi yetu kupata hata kubwa. 

Sasa, tofauti kati ya algorithms haya kuanza kuwa kidogo kidogo dhahiri. Na ukweli kwamba kuna ili kupunguza terms-- au tuseme, masharti na chini exponents-- kuanza kuwa lisilo na maana. Kama kuweka data ni wa kawaida 1,000 na algorithm kwanza anaendesha katika bilioni hatua. Na algorithm pili anaendesha katika bilioni na milioni hatua. Na algorithm tatu anaendesha katika aibu tu ya bilioni hatua. Ni pretty much bilioni hatua. Wale suala ili kupunguza kuanza kuwa kweli lisilo. Na tu kwa kweli nyundo nyumbani point-- kama pembejeo data ni wa kawaida a million-- zote tatu wa haya pretty much kuchukua quintillion-- moja ikiwa math yangu ni hatua correct-- na mchakato wa pembejeo data ukubwa milioni. Kwamba mengi ya hatua. Na ukweli kwamba mmoja wao wapate kuchukua michache 100,000 au wanandoa 100 milioni hata kidogo wakati tunazungumzia idadi kwamba big-- ni aina ya lisilo na maana. Wote huwa na kuchukua takriban n cubed, na hivyo sisi ingekuwa kweli rejea kwa wote wa algorithms hizi kuwa juu ya utaratibu wa n cubed au kubwa-O ya n cubed. 

Hapa ni orodha ya baadhi ya zaidi kawaida madarasa Computational utata kwamba tutaweza kukutana katika algorithms, kwa ujumla. Na pia hasa katika CS50. Hizi ni amri kutoka ujumla kwa kasi juu, kwa ujumla madogo zaidi chini. Hivyo algorithms wakati mara kwa mara huwa kuwa kasi, bila kujali ukubwa wa pembejeo data kupita katika. Wao daima kuchukua operesheni moja au kitengo moja ya rasilimali ya kushughulikia. Ni inaweza kuwa 2, inaweza kuwa 3, inaweza kuwa 4. Lakini ni idadi ya mara kwa mara. Ni haina kutofautiana. 

Logarithmic algorithms wakati ni kidogo bora. Na mfano mzuri wa logarithmic wakati algorithm umefanya hakika kuonekana na sasa ni akamtikisatikisa peke yao ya kitabu cha simu kupata Mike Smith katika kitabu cha simu. Sisi kupunguza tatizo katika nusu. Na hivyo kama n anapata kubwa na kubwa na larger-- kwa kweli, kila wakati mara mbili n, tu inachukua hatua moja zaidi. Hivyo hiyo ni mengi zaidi kuliko kusema, wakati linear. Ambayo ni kama mara mbili n, ni inachukua mara mbili ya idadi ya hatua. Kama mara tatu n, inachukua mara tatu idadi ya hatua. Hatua moja kwa kila kitengo. 

Kisha mambo kupata kidogo more-- kidogo kidogo kubwa kutoka huko. Una linear wakati utungo, wakati mwingine aitwaye gogo wakati linear au tu n logi n. Na tutaweza mfano ya algorithm kwamba anaendesha katika n logi n, ambayo bado ni bora kuliko quadratic time-- n squared. Au wakati polynomial, n wawili idadi yoyote kubwa kuliko hizo mbili. Au kielelezo wakati, ambayo ni hata worse-- C kwa n. Hivyo baadhi ya idadi ya mara kwa mara kufufuka kwa nguvu ya ukubwa wa pembejeo. Hivyo kama kuna 1,000-- kama pembejeo data ni wa kawaida 1,000, itachukua C madarakani 1000. Ni mengi zaidi kuliko wakati polynomial. 

Muda factorial ni mbaya zaidi. Na kwa kweli, kuna kweli kufanya kuwepo usio algorithms muda, kama vile, kinachojulikana kijinga sort-- ambao kazi ni kwa nasibu shuffle safu na kisha kuangalia kuona kama ni yamepangwa. Na kama siyo, nasibu changa safu tena na kuangalia kuona kama ni yamepangwa. Na kama pengine unaweza imagine-- unaweza kufikiria hali ambapo katika hali mbaya zaidi kesi, kwamba mapenzi kamwe kweli kuanza na safu. Algorithm kwamba ingekuwa kukimbia milele. Na hivyo kwamba itakuwa usio wakati algorithm. Hopefully huwezi kuwa kuandika wakati wowote factorial au usio algorithms katika CS50. 

Hivyo, hebu kuchukua kidogo zaidi kuangalia saruji katika baadhi rahisi Computational utata madarasa. Hivyo tuna example-- mifano moja au mbili here-- ya mara kwa mara algorithms muda, ambayo daima kuchukua operesheni moja katika kesi mbaya. Hivyo example-- kwanza tuna kazi aitwaye 4 kwa ajili yenu, ambayo inachukua safu ya ukubwa 1,000. Lakini basi inaonekana haina kweli kuangalia katika it-- kweli haina huduma nini ndani yake, ya kwamba safu. Daima tu anarudi nne. Hivyo, kwamba algorithm, licha ya ukweli kwamba inachukua mambo 1,000 haina kufanya kitu chochote pamoja nao. Tu anarudi nne. Ni siku zote hatua moja. 

Kwa kweli, kuongeza 2 nums-- ambayo tumeona kabla kama well-- michakato tu integers mbili. Siyo hatua moja. Ni kweli hatua kadhaa. Kupata, kupata b, wewe kuongeza yao pamoja, na wewe pato matokeo. Hivyo ni hatua 84. Lakini mara nyingi ni mara kwa mara, bila kujali au b. Una kupata, kupata b, kuongeza nao pamoja, pato matokeo. Hivyo hiyo ni mara kwa mara wakati algorithm. 

Hapa ni mfano wa linear wakati algorithm algorithm kwamba gets-- kwamba inachukua hatua moja zaidi, pengine, kama mchango wako kukua na 1. Hivyo, hebu sema sisi ni kuangalia kwa namba 5 ndani ya safu. Unaweza kuwa na hali ambapo unaweza kuipata haki mapema. Lakini unaweza pia kuwa Hali ambako inaweza kuwa kipengele mwisho wa safu. Katika safu ya ukubwa 5, ikiwa sisi ni kuangalia kwa namba 5. Itachukua hatua 5. Na kwa kweli, kufikiria kwamba kuna si 5 popote katika safu hii. Sisi bado kweli kuwa na kuangalia kila kipengele moja ya safu ili kujua iwapo au 5 ni huko. 

Hivyo katika hali mbaya zaidi kesi, ambayo ni kuwa kipengele ni ya mwisho katika safu au haipo kabisa. Bado tuna kuangalia wote wa mambo n. Na hivyo algorithm hii anaendesha katika muda linear. Unaweza kuthibitisha kwamba kwa extrapolating kidogo kwa kusema, kama tulikuwa na 6-kipengele safu na tulikuwa kuangalia kwa namba 5, inaweza kuchukua hatua 6. Kama tuna 7-kipengele safu na sisi ni kuangalia kwa namba 5. Inaweza kuchukua 7 hatua. Kama sisi kuongeza moja zaidi kipengele kwa wetu safu, inachukua hatua moja zaidi. Hiyo ni algorithm linear katika hali mbaya zaidi kesi. 

Wanandoa maswali ya haraka kwa ajili yenu. Nini runtime-- nini mbaya zaidi kesi Runtime ya snippet hii hasa wa kanuni? Hivyo nina 4 kitanzi hapa kwamba anaendesha kutoka j sawa na 0, njia yote hadi m. Na nini mimi nina kuona hapa, ni kwamba mwili wa kitanzi anaendesha katika muda wa mara kwa mara. Hivyo kwa kutumia istilahi kwamba tumekuwa tayari kuongelea about-- nini itakuwa mbaya zaidi kesi Runtime ya algorithm hii? Kuchukua pili. Sehemu ya ndani ya kitanzi anaendesha katika muda wa mara kwa mara. Na sehemu ya nje ya kitanzi ni kwenda kukimbia m nyakati. Basi nini mbaya zaidi kesi Runtime hapa? Je, nadhani big-O wa m? Ningependa kuwa na haki. 

Vipi kuhusu mtu mwingine? Wakati huu tuna kitanzi ndani ya kitanzi. Tuna kitanzi nje kwamba anaendesha kutoka sifuri kwa kupita. Na tuna kitanzi kwamba anaendesha ndani kutoka sifuri kwa kupita, na ndani ya kwamba, Mimi hali ya kuwa mwili kitanzi anaendesha katika muda wa mara kwa mara. Basi nini mbaya zaidi kesi Runtime ya snippet hii hasa wa kanuni? Naam, tena, tuna nje kitanzi kwamba anaendesha mara uk. Na kila iteration time-- ya kwamba kitanzi, hasa. Tuna kitanzi ndani kwamba pia anaendesha mara uk. Na kisha ndani ya kwamba, kuna mara kwa mara time-- snippet kidogo huko. 

Hivyo kama tuna kitanzi nje kwamba anaendesha mara p ndani ya ambayo ni kitanzi ndani ambayo anaendesha p times-- nini mbaya zaidi kesi Runtime ya snippet hii ya kificho? Je, nadhani big-O wa p mraba? 

Mimi nina Doug Lloyd. Hii ni CS50.