Labi, tāpēc, skaitļošanas sarežģītība. Tikai mazliet brīdinājums pirms mēs nirt pārāk far-- Tas droši vien būtu starp Visvairāk math smago lietas mēs runājam par in CS50. Cerams, ka tas nebūs pārāk milzīgs un mēs cenšamies, un palīdzēs jums izmantojot procesu, bet tikai mazliet taisnīgu brīdinājuma. Tur ir mazliet math iesaistīti šeit. Labi, tāpēc, lai veiktu izmantošana mūsu skaitļošanas resursu reālajā world-- tas ir patiešām svarīgi saprast algoritmus un kā tās apstrādā datus. Ja mums ir patiešām efektīvs algoritms, mēs var samazināt resursu apjomu mums ir pieejami, lai risinātu ar to. Ja mums ir algoritmu, kas gatavojas veikt daudz darba apstrādāt patiešām liels datu kopums, tas ir gatavojas pieprasīt vairāk un vairāk resursu, kas ir nauda, ​​RAM, viss, kas veida sīkumi. 

Tātad, to var analizēt algoritms, izmantojot šo rīku komplektu, būtībā lūdz question-- Kā tas algoritms skalu kā mēs mest vairāk un vairāk datu pie tā? In CS50, datu apjomu, mēs esam strādājot ar ir diezgan maza. Parasti mūsu programmas dodas palaist otrā vai less-- iespējams, daudz mazāk īpaši sākumā. 

Bet domāju par uzņēmumu, kas nodarbojas ar simtiem miljoniem klientu. Un viņiem ir nepieciešams, lai apstrādātu ka klientu dati. Kā uz klientu skaitu tie ir kļūst lielāka un lielāka, tas prasīs vairāk un vairāk resursu. Cik daudz vairāk resursu? Nu, tas ir atkarīgs no tā, cik mēs analizējam algoritmu, izmantojot instrumentus šajā instrumentu kopumu. Kad mēs runājam par sarežģīto algorithm-- kas dažreiz jūs dzirdēt tekstā laiks sarežģītība vai telpas sarežģītība bet mēs esam tikai gatavojas zvanīt complexity-- mēs parasti runājam par sliktākais scenārijs. Ņemot absolūtais sliktākais kaudzi dati, ka mēs varētu tikt throwing pie tā, kā tas ir algoritms gatavojas apstrādāt vai nodarbojas ar šiem datiem? Mēs parasti saucam par sliktāko runtime no algoritma big-O. Tātad algoritms varētu teikt, ieskriet O N vai O n brusas. Un vēl par to, tie nozīmē sekundē. 

Dažreiz, lai gan, mēs aprūpe par labāko scenāriju. Ja dati ir viss, ko mēs vēlējāmies ka tas ir, un tas bija absolūti perfekta un mēs bijām nosūtot šo perfekts datu kopums caur mūsu algoritmu. Kā tas rīkoties šajā situācijā? Mēs dažreiz atsaucas uz, ka big-Omega, tāpēc atšķirībā no big-O, mums ir liels-Omega. Big-Omega par labāko scenāriju. Big-O, lai sliktākajā gadījumā. Parasti, kad mēs runājam par sarežģītība algoritmu, mēs runājam par sliktāko scenāriju. Lai saglabātu, ka prātā. 

Un šajā klasē, mēs parasti dodas atstāt nopietnu analīzi malā. Ir zinātnes un lauki veltīta šāda veida sīkumi. Kad mēs runājam par argumentācijas izmantojot algoritmus, ko mēs darīsim gabalu pa gabalu daudzi algoritmi mēs runājam par šajā klasē. Mēs esam tiešām tikai runā par argumentācija caur to ar veselo saprātu, ne ar formulām, vai pierādījumus, vai kaut kā tā. Tāpēc neuztraucieties, mēs nebūs pārvēršas lielā matemātikas klasē. 

Tāpēc es teicu, mēs rūpējamies par sarežģīto jo tā uzdod jautājumu, cik Vai mūsu algoritmi rīkoties lielāks un Lielāki datu kopas izkrišanas pie viņiem. Nu, kas ir datu kopa? Ko es domāju, kad es teicu, ka? Tas nozīmē, kāds padara visvairāk jēgas kontekstā, lai būtu godīgi. Ja mums ir algoritms, ar Procesi Strings-- mēs esam droši runājot par lielumu virknes. Tas ir dati set-- lielums, skaits rakstzīmju kas veido virkni. Ja mēs runājam par algoritms, kas apstrādā failus mēs varētu runāt par to, kā daudzi kilobaiti veido šo failu. Un tas ir datu kopa. Ja mēs runājam par algoritmu kas strādā bloki vispārīgāk, piemēram, šķirošanas algoritmi vai meklē algoritmus, mēs, iespējams, runājam par numuru no faktoriem, kas ietilpst masīvu. 

Tagad mēs varam izmērīt algorithm-- it īpaši, kad es saku, ka mēs varam pasākums algoritmu, es nozīmē, ka mēs varam izmērīt, cik daudz resursu, tas aizņem. Vai šie resursi ir, cik daudz no RAM-- baiti vai megabaiti RAM tā izmanto. Vai, cik daudz laika nepieciešams, lai palaistu. Un mēs varam zvanīt šis pasākums, patvaļīgi, f n. Kur n ir skaitlis no elementi datu kopas. Un f n ir, cik daudz somethings. Cik daudz resursu vienības dara tā ir nepieciešama, lai apstrādātu šo informāciju. 

Tagad mēs patiesībā ir vienalga par to f n ir tieši. Patiesībā, mēs ļoti reti will-- protams nekad šajā class-- I nodoties jebkurš tiešām dziļi analīze par to f n ir. Mēs esam tikai gatavojas runāt par to, ko no f n ir aptuveni vai ko tai ir tendence. Un tendence algoritms ir diktē savu augstāko pasūtījuma termiņā. Un mēs varam redzēt, ko es domāju ar, ka, ņemot apskatīt daudz konkrētu piemēru. 

Tātad pieņemsim, ka mums ir trīs dažādi algoritmi. Pirmais no tiem aizņem n kubā, daži resursu vienības apstrādāt datu kopu lieluma n. Mums ir otrais algoritmu, kas notiek n kubā plus n Kvadrātveida resursi apstrādāt datu kopu lieluma n. Un mums ir trešā algoritms, kas darbojas in-- ka aizņem n kubā mīnus 8N brusas plus 20 n vienības resursu apstrādāt algoritmu ar datiem, kas no lieluma n. 

Tagad atkal, mēs tiešām neesam gatavojas nokļūt šajā detalizācijas pakāpē. Es esmu patiešām vienkārši ir šie up šeit kā ilustrācija punkta ka es esmu būs padarot sekundē, kas ir tā, ka mēs tikai patiešām rūp par tendenci lietām kā datu kopas iegūt lielākas. Tātad, ja datu kopa ir mazs, tur ir patiesībā ir diezgan liela atšķirība Šajās algoritmiem. Trešais algoritms tur aizņem 13 reizes ilgāk, 13 reizes resursu apjoms palaist, salīdzinot ar pirmo. 

Ja mūsu datu kopa ir izmērs 10, kas ir lielāks, taču ne vienmēr milzīgs, mēs varam redzēt, ka tur ir faktiski mazliet starpību. Trešais algoritms kļūst efektīvāka. Tas ir par faktiski 40% - jeb 60% efektīvāk. Tas aizņem 40% laika daudzums. Tas var run-- tas var aizņemt 400 resursu vienības apstrādāt datu kopumu izmēru 10. Tā kā pirmais algoritmu, gluži pretēji, aizņem 1000 resursu vienības apstrādāt datu kopumu izmēru 10. Bet izskatās, kas notiek, kā Mūsu numuri iegūtu vēl lielāku. 

Tagad, atšķirība starp šiem algoritmiem sāk kļūt mazliet mazāk acīmredzama. Un fakts, ka pastāv zemākas kārtas terms-- vai drīzāk, noteikumi, ar zemāku exponents-- sāk kļūt nozīmes. Ja datu kopa ir lielums 1000 un pirmais algoritms trašu miljarda soļiem. Un otrs algoritms darbojas viens miljards un miljons soļi. Un trešais algoritms darbojas tikai kautrīgam miljards soļiem. Tas ir diezgan daudz miljards soļi. Šie zemākas pakāpes termini sākt kļūt tiešām nav nozīmes. Un tikai, lai patiešām āmurs mājās tajā point-- ja datu ievades ir no A izmēra million-- visi trīs šie diezgan daudz veikt vienu quintillion-- ja mana matemātika ir correct-- soļi apstrādāt datu ievadi no to lieluma miljons. Tas ir daudz soļiem. Un fakts, ka viens no viņiem varētu veikt pāris 100000, vai pāris 100 miljoni vēl mazāk, ja mēs runājam par vairākiem ka big-- tas ir sava veida nozīmes. Viņi visi mēdz veikt aptuveni n kubā, un tāpēc mēs faktiski atsaukties uz visiem šiem algoritmiem kā par n secībā kubā vai big-O n kubā. 

Šeit ir saraksts ar dažiem no vairāk kopēji skaitļošanas sarežģītība nodarbības ka mēs sastopas algoritmi, parasti. Un arī īpaši CS50. Tie ir pasūtīts no parasti ātrāk augšpusē, līdz parasti vislēnākais apakšā. Tātad nemainīgs laika algoritmi mēdz būt ātrākais, neskatoties no no lieluma datu ievade jums pāriet. Viņi vienmēr veikt vienu operāciju vai viena vienība no resursiem, lai risinātu ar. Tas varētu būt 2, tas varētu būt 3, tas varētu būt 4. Bet tas ir konstante. Tas nemainās. 

Logaritmiska laika algoritmi ir nedaudz labāk. Un ļoti labs piemērs logaritms laiks algoritms Jūs esat droši redzējis līdz šim ir noplēšot no tālruņu kataloga atrast Mike Smith tālruņu grāmatā. Mēs samazināt problēmu pusi. Un tā kā n izpaužas lielāks un lielāki un larger-- Patiesībā, katru reizi, kad jūs divreiz n, tas aizņem tikai vēl vienu soli. Tātad tas ir daudz labāk nekā, teiksim, lineārais laiks. Kas ir, ja jūs dubultā n, tas ņem dubultu skaitu soļus. Ja jums triple n, tas aizņem trīskāršot vairākus pasākumus. Viens solis uz vienu vienību. 

Tad lietas iegūt nedaudz more-- nedaudz mazāk lieliski no turienes. Jums ir lineārs ritmisku laiks, dažreiz sauc log lineārā laika vai vienkārši n log n. Un mēs piemērs par algoritmu, kas Darbojas n log n, kas ir vēl labāk nekā kvadrāta LAIKU_ n brusas. Vai polinoma laiks, n divi jebkurš skaitlis ir lielāks par diviem. Vai eksponenciālā laiks, kas ir pat worse-- C līdz n. Tātad daži konstante skaits jāpalielina līdz spēks lieluma ievadi. Tātad, ja tur ir 1,000-- ja datu ievade ir izmērs 1000, tas būtu nepieciešams C līdz 1,000th varas. Tas ir daudz sliktāk, nekā polinomu laika. 

Faktoriāls laiks ir vēl sliktāk. Un patiesībā, tur tiešām pastāv bezgalīgs laika algoritmi, piemēram, tā saukto stulba sort-- kuru uzdevums ir nejauši shuffle masīvs un pēc tam pārbaudiet, vai tas ir sakārtoti. Un, ja tas tā nav, nejauši shuffle masīvs atkal un pārbaudiet, vai tas ir sakārtoti. Un kā jūs varat droši imagine-- Jūs varat iedomāties situāciju kur sliktākajā gadījumā, ka griba nekad faktiski sākt ar masīvu. Tas algoritms varētu palaist uz visiem laikiem. Un lai būtu bezgalīgs laiks algoritms. Cerams, ka jums nebūs rakstiski jebkurš factorial vai bezgalīgs laiks algoritmus CS50. 

Tātad, pieņemsim nedaudz vairāk betona apskatīt dažus vienkāršāku skaitļošanas sarežģītība nodarbības. Tātad mums ir example-- vai divi piemēri here-- pastāvīga laika algoritmu, kas vienmēr viena operācija sliktākajā-lietas. Tātad pirmajā example-- mums ir funkcija aicināja 4 jums, kas aizņem masīva izmēru 1000. Bet tad acīmredzot tas tiešām neizskatās at it-- nav īsti aprūpi, kas ir iekšpusē tā, šī masīva. Vienmēr tikai atgriežas četri. Tātad, ka algoritms, neskatoties uz to, ka tas aizņem 1000 elementi nav darīt kaut ko ar viņiem. Vienkārši atgriežas četri. Tas vienmēr ir viens solis. 

Patiesībā, pievieno 2 nums-- kas mēs esam redzējuši agrāk kā well-- vienkārši apstrādā divus veselus skaitļus. Tas nav viens solis. Tas ir faktiski pāris soļi. Jūs saņemsiet, jums b, jūs pievienojat tos kopā, un izvadīt rezultātu. Tātad, tas ir 84 soļus. Bet tas vienmēr ir nemainīgs, neatkarīgi no tā, a vai b. Jums ir, lai saņemtu, iegūtu B, pievieno tos kopā, izejas rezultāts. Tātad tas ir pastāvīgs laiks algoritmu. 

Lūk piemērs lineārais laiks algorithm-- algoritms, kas gets-- kas notiek viens papildu solis, iespējams, jo jūsu ieguldījums palielinās par 1. Tātad, pieņemsim, ka mēs meklējam skaits 5 iekšpusē masīva. Jums varētu būt situācija, kad Jūs varat atrast to diezgan agri. Bet jūs varētu arī būt situācija, kad to varētu būt pēdējais elements masīva. Masīva izmēru 5, ja mēs meklējam numuru 5. Tas būtu jāņem 5 soļi. Un patiesībā, iedomāties, ka tur ir nevis 5 jebkur šajā masīvā. Mums vēl tiešām ir jāskatās katru elementu masīva lai noteiktu vai vai nav 5 ir tur. 

Tātad sliktākajā gadījumā, proti, ka elements ir pēdējais masīva vai neeksistē vispār. Mums vēl ir jāskatās visi no n elementiem. Un tā šis algoritms trašu lineārā laika. Jūs varat apstiprināt, ka, ekstrapolējot mazliet, sakot, ja mums bija 6-elementu masīvu un mēs meklējām skaitu 5, tas var aizņemt 6 soļus. Ja mums ir 7-elementu masīvu un mēs meklējam numuru 5. Tas var aizņemt 7 soļi. Kā mēs pievienot vēl vienu elementu, lai mūsu masīvs, tas aizņem vēl vienu soli. Tas ir lineārs algoritms sliktākajā-lietas. 

Pāris ātri jautājumi jums. Kas ir runtime-- kas ir sliktākajā gadījuma runtime Šī konkrētā fragmentu kodu? Tāpēc man ir 4 cilpu šeit, kas darbojas no j ir vienāds ar 0, visu ceļu līdz pat m. Un ko es esmu redzēt šeit, ir tas, ka ķermenis cilpas trašu pastāvīgu laiku. Tātad, izmantojot terminoloģiju, kas mēs jau esam runājuši about-- ko būtu sliktākajā gadījumā runtime šo algoritmu? Veikt sekundi. Iekšējā daļā cilpas trašu pastāvīgu laiku. Un ārējā daļa no cilpa ir gatavojas palaist m reizes. Tātad, kas ir sliktākais runtime šeit? Vai jūs uzminēt liels-O m? Tu būsi taisnība. 

Kā par otru? Šoreiz mums ir cilpa iekšpusē cilpas. Mums ir ārējo cilpu kas iet no nulles līdz p. Un mums ir iekšējais cilpa, kas darbojas no nulles līdz p, un iekšpusē, kas, Man jānorāda, ka iestādi par cilpa trašu pastāvīgu laiku. Tātad, kas ir sliktākais runtime Šī konkrētā fragmentu kodu? Nu, atkal, mums ir ārējā kontūra, kas darbojas p reizes. Un katrs LAIKU_ atkārtojuma Šīs cilpas, drīzāk. Mums ir iekšējās cilpa kas arī vada p reizes. Un tad iekšpusē, ka tur ir konstante LAIKU_ maz fragments tur. 

Tātad, ja mums ir ārējā kontūra, kas iet p reizes iekšpusē, kas ir iekšējo cilpa, kas iet p times-- to, kas ir sliktākajā gadījuma runtime par šo koda fragmentu? Vai jūs uzminēt big-O P brusas? 

Es esmu Doug Lloyd. Tas ir CS50.