Vse je v redu, tako, računska zahtevnost. Samo malo opozorilo preden se potopite v preveč far-- To bo verjetno med Najbolj math-težkih stvari govorimo o v CS50. Upajmo, da ne bo preveč prepričljivo in bomo poskušali, in vas vodi skozi proces, vendar samo malo poštenega opozorila. Tam je malo matematike vključeni tukaj. Vse je v redu, tako da se bo Uporaba naših računalniških virov v resničnem world-- to je res pomembno razumeti algoritme in kako se obdelujejo podatke. Če imamo res učinkovit algoritem smo lahko zmanjša znesek sredstev, imamo na voljo za spopadanje z njo. Če imamo algoritem, ki se dogaja, da se veliko dela obdelati res Velik nabor podatkov, je dogaja, da zahtevajo več in več virov, ki je denar, RAM, vse te vrste stvari. 

Torej, da lahko analiziramo algoritem z uporabo tega orodja set, v bistvu prosi question-- kako se ta algoritem lestvice kot smo metati vse več podatkov na njej? V CS50, količino podatkov smo delo s je precej majhen. Na splošno, naši programi bodo teči v drugo ali less-- verjetno veliko manj predvsem že na začetku. 

Ampak pomislite podjetje, ki se ukvarja z več sto milijonov kupcev. In ki jih potrebujejo za obdelavo da podatki strank. Ker je število strank, ki jih imajo postane večji in večji, to se dogaja, da zahtevajo več in več sredstev. Koliko več sredstev? No, to je odvisno od tega, kako smo analizirali algoritem, uporabo orodij v tej orodjarni. Ko govorimo o kompleksnosti algorithm-- ki včasih boste slišite, da se imenuje čas kompleksnost ali prostorska zahtevnost vendar smo šele tekoč poklicati complexity-- smo na splošno govorimo o najslabšem primeru. Glede na absolutno najslabše kup podatke, ki bi lahko smo metali na to, kako je ta algoritem bo obdelavo ali se ukvarjajo s temi podatki? Smo na splošno imenujemo najslabšim teka algoritma big-O. Torej bi lahko algoritem je dejal, da teči O N ali O n kvadrat. In še o tem, kaj tiste pomeni v sekundi. 

Včasih, čeprav nam ni vseeno o najboljšem primeru. Če podatki, je vse, kar smo želeli da bi bilo in da je absolutno popolna in smo bili pošiljanje to odlično niz podatkov preko našega algoritma. Kako bi bilo ravnati v tem primeru? Včasih se nanašajo na to kot big-Omega, tako da v nasprotju z big-O, imamo velik-Omega. Big-Omega za najboljšem primeru. Big-O za najslabšem primeru. Na splošno, ko govorimo o kompleksnost algoritmom, govorimo približno najslabši scenarij. Tako da se vodijo v mislih. 

In v tem razredu, smo na splošno dogaja zapustiti natančno analizo stran. Obstajajo vede in polja namenjenih za tovrstne stvari. Ko govorimo o obrazložitvi pomočjo algoritmov, katero bomo naredili kos-by-kos za mnoge algoritmi govorimo o v razredu. Mi smo res samo govoriš razmišljanjem skozi to z razumom, ne s formulami, ali dokazila, ali kaj podobnega. Torej, ne skrbite, ne bomo preobrat v velikem matematičnem razredu. 

Zato sem rekel, da je mar kompleksnosti ker se zastavlja vprašanje, kako pa naši algoritmi ročaj večji in Večje podatkovni nizi, ki se vrže na njih. No, kaj je niz podatkov? Kaj sem mislil, ko sem rekel, da je? To pomeni karkoli kar najbolje Občutek v kontekstu, če sem iskren. Če imamo algoritem, na Procesi Strings-- smo verjetno govorimo o velikosti niza. To so podatki set-- velikost, števila znakov, ki sestavljajo niz. Če govorimo o algoritem, ki obdeluje datotek bomo lahko govorili o tem, kako veliko kilobajtov sestavljajo to datoteko. In to je nabor podatkov. Če govorimo o algoritmu ki se ukvarja nizi bolj na splošno, kot so algoritmi za sortiranje ali iskanje algoritmov, bomo verjetno govorimo o številu elementov, ki sestavljajo niz. 

Sedaj lahko ukrep algorithm-- zlasti ko sem rekel, smo lahko merjenje algoritem, I pomeni, da lahko merimo, kako veliko virov, da prevzame. Ali so ti viri, koliko bajtov RAM-- ali MB RAM uporablja. Ali pa, koliko časa je potrebno za vodenje. In lahko rečemo to izmerimo, poljubno, f n. Kjer je n število elementi v podatkovnem nizu. In f n je, koliko somethings. Koliko enot sredstev ne zahteva za obdelavo teh podatkov. 

Zdaj smo pravzaprav ne zanima o tem, kaj f n je točno. V bistvu smo zelo redko will-- zagotovo ne bo nikoli v tej class-- I potopite v nobeno res globok Analiza kaj f n. Mi smo le, da bo govoril o tem, kaj f n je približno ali kaj se nagiba k. In težnja algoritmu je narekuje najvišji izraz naročila. In smo lahko videli, kaj sem mislim s tem, ki ga ob poglej na bolj konkreten primer. 

Torej, recimo, da imamo trije različni algoritmi. Prvi od katerih je n kubikov, nekatere enote virov obdelati podatkovnega niza velikosti n. Imamo drugo algoritem, ki bo n kubikov plus n kvadrati viri obdelati podatkovnega niza velikosti n. In imamo tretja Algoritem, ki teče in-- da zavzema n kubikov minus 8N na kvadrat plus 20 n enot sredstev obdelati algoritem s podatki iz velikosti n. 

Zdaj spet, res se ne bo priti v tej ravni podrobnosti. Res sem samo še ti gor Tukaj kot ilustracija točke da bom lahko izdelavo sekundo, kar je, da smo samo res skrbi o tendenci stvari kot podatkovni nizi dobili večji. Torej, če je podatkovni niz je majhna, obstaja pravzaprav zelo velika razlika V teh algoritmov. Tretji algoritem tam traja 13-krat dlje, 13-kratni znesek sredstev teči glede na prvega. 

Če je naš nabor podatkov je velikost 10, ki je večja, vendar ne nujno velika, lahko vidimo, da obstaja pravzaprav malo razlike. Tretji algoritem postane bolj učinkovita. Gre za dejansko 40% - ali 60% večjo učinkovitost. To traja 40%, se znesek časa. To lahko run-- lahko traja 400 enot sredstev obdelati podatkovnega niza velikosti 10. Ker prva algoritem, nasprotno, je 1.000 enot virov obdelati podatkovnega niza velikosti 10. Ampak poglej kaj se zgodi, naše številke dobil še večji. 

Sedaj pa razlika med temi algoritmov začeli, da postanejo malo manj očitna. In dejstvo, da obstajajo nižji-order terms-- ali bolje, izrazi z nižjo exponents-- začeli, da postanejo nepomembni. Če je podatkovni niz z velikostjo 1000 in prvi algoritem teče čez milijardo korakih. In drugi algoritem teče v milijarda in milijon korakov. In tretji algoritem teče v samo sramežljiv milijarde korakov. To je precej milijarde korakov. Ti pogoji nižje naročilo začetek resnično postala nepomembna. In samo, da bo res kladivo domov Point-- če vhodni podatki dimenzionirati million-- vse tri od teh precej vzemite eno quintillion-- če Moja matematika correct-- koraki obdelati vnos podatkov velikosti milijona. To je veliko korakov. In dejstvo, da je eden od njih lahko traja nekaj 100.000 ali nekaj 100 milijonov še manj, kadar govorimo o številnih da big-- je nekako nepomembno. Vsi težijo, da sprejmejo približno n kubikov, in zato bi se dejansko nanašajo vseh teh algoritmov kot velikostnega reda n kubikov ali big-O n kubični. 

Tukaj je seznam nekaterih bolj skupna računska kompleksnost razredi da bomo naleteli na algoritmi, na splošno. In prav posebej v CS50. Te so razvrščene od splošno najhitrejši na vrhu, na splošno najpočasnejša na dnu. Torej konstanten čas algoritmov nagibajo biti najhitrejši, ne glede velikosti od vhodni podatki se boste peljali v. Vedno vzemite eno operacijo ali ena enota sredstev za reševanje. Morda bi bilo 2, bi bilo lahko 3, morda 4. Vendar je konstantno število. To se ne spreminja. 

Logaritemski čas algoritmov so nekoliko boljši. In res dober primer logaritemski čas algoritem da ste zagotovo videli do sedaj, je odtrgate telefonskega imenika najti Mike Smith v telefonskem imeniku. Cut smo problem na pol. In tako, kot n dobi večji in večje in larger-- v resnici, vsakič, ko podvojilo n, je samo še en korak. Tako, da je veliko bolje, kot, recimo, linearni čas. Ki je, če ste dvakrat n je je dvojno število korakov. Če potrojiti n, je potrebno potrojiti število korakov. En korak na enoto. 

Potem pa se stvari malo more-- Malo manj super od tam. Imate linearno ritmično časa, včasih imenovani dnevnik linearni čas ali pa samo n log n. In bomo zgled od algoritma, ki teče v n log n, ki je še vedno bolje kot kvadratna time-- n kvadrat. Ali polinom čas, n dva poljubno število večje od dve. Ali eksponentna čas, ki Še worse-- C do n. Tako nekateri konstantno število dvigne na Moč velikosti vhoda. Torej, če je 1,000-- Če vhodni podatki velikosti 1000, da bi potrebovali C do 1,000th moči. To je veliko slabše, kot polinomskem casu. 

Faktorski čas je še slabše. In v resnici, je res obstajajo neskončne čas algoritmov, kot so ti neumen sort-- katerih naloga je, da naključno shuffle array in nato preverite, ali je to urejeno. In če to ni naključno ponovno shuffle array in preverite, ali je to urejeno. In kot si verjetno lahko imagine-- si lahko predstavljate situacijo kjer je v najslabšem primeru, da bo Nikoli dejansko začeli s paleto. Ta algoritem bi teči večno. In tako, da bi bila neskončno časa algoritem. Upajmo, da ne bo pisal vsaka faktorsko ali neskončna čas algoritme v CS50. 

Torej, vzemimo malo več beton pogled na nekatere enostavnejše računski kompleksnost razredi. Torej imamo example-- ali dva primera here-- konstantnih časovnih algoritmov, ki vedno ena operacija v najslabšem primeru. Torej, prvi example-- imamo funkcijo pozval 4 za vas, ki prevzame paleto velikosti 1.000. Ampak potem očitno dejansko ne videti na ne it-- res ne zanima, kaj je znotraj njega, od tega niza. Vedno vrne ravno štiri. Torej, da je algoritem, kljub dejstvu, da je je 1.000 elementov ne storiti ničesar z njimi. Samo vrne štiri. To je vedno en sam korak. 

V bistvu, dodamo 2 nums-- ki smo videli prej kot well-- samo obdeluje dve celi števili. To ni en sam korak. To je pravzaprav nekaj korakov. Dobiš, dobiš b, jih dodate skupaj, in ti izhodne rezultate. Torej, to je 84 korakov. Ampak to je vedno konstantna, glede na to, a ali b. Imate, da bi dobili, dobili b, dodajte jih skupaj, izhodni rezultat. Torej, to je stalnica, ko algoritem. 

Tukaj je primer linearni čas algorithm-- algoritem, ki gets--, ki traja en dodaten korak, morebiti kot je vaš vnos raste s 1. Torej, recimo, da iščemo število 5 znotraj matrike. Morda imate situacijo, v kateri lahko zdi dokaj zgodaj. Vendar bi lahko imeli tudi razmere, v katerih je lahko zadnji element matrike. V paleto velikosti 5, če iščemo za številko 5. To bi trajalo 5 korakov. In v resnici, si predstavljajte, da obstaja Ne 5 kjerkoli v tem polju. Še vedno dejansko morali pogledati vsak element matrike da bi določili ali 5 obstaja. 

Torej v najslabšem primeru, to je, da element je zadnji v matriki ali ne obstaja sploh. Še vedno moramo gledati vse n elementov. In tako je ta algoritem teče v linearnem času. Lahko potrdite, da jo ekstrapolacijo malo z besedami, če bi imeli niz 6-element in smo iskali številko 5, to lahko traja 6 korakov. Če imamo niz 7-element in iščemo za številko 5. To lahko traja 7 korakov. Kot smo dodali še en element za naše matrika, ki je potreben še en korak. To je linearni algoritem v najslabšem primeru. 

Par hitrih vprašanj za vas. Kaj je runtime-- kaj je najslabšim runtime tega posebnega odrezka kode? Torej imam 4 zanke tukaj, da teče od j enak 0, vso pot do m. In tisto, kar sem tukaj vidim, je, da je Telo zanke deluje v stalnem času. Torej, z uporabo terminologije smo že govorili about-- kaj bi bilo v najslabšem primeru runtime tega algoritma? Vzemite si trenutek. Notranji del zanke teče v stalnem času. In zunanji del zanka se bo teči m-krat. Torej, kaj je runtime najslabšem primeru tukaj? Ali uganete, Big-O za m? Ti bi bilo prav. 

Kaj pa drugo? Tokrat imamo zanka znotraj zanke. Imamo zunanjo zanko ki teče od nič do str. In imamo notranjo zanko, ki teče od nič do p, in znotraj tega, Izjavljam, da je telo zanka teče v stalnem času. Torej, kaj je runtime najslabšem primeru tega posebnega odrezka kode? No, še enkrat, imamo zunanjo zanko, ki teče p-krat. In vsaka time-- ponovitev navedene zanke, ne. Imamo notranjo zanko ki teče tudi p-krat. In potem znotraj tega, tam je stalna time-- mali košček tam. 

Torej, če imamo zunanja zanka, ki teče p-krat znotraj katerega je notranjo zanko, da teče p times-- kaj je najslabšim runtime tega odrezka kode? Ali uganete, big-O p na kvadrat? 

Sem Doug Lloyd. To je CS50.