Okej, så, beräkningskomplexitet. Bara en bit av en varning innan vi dyker i för far-- Detta kommer förmodligen att vara bland de matematiktunga saker vi talar om i CS50. Förhoppningsvis kommer det inte vara alltför överväldigande och vi ska försöka guida dig genom processen, men bara en bit av en rättvis varning. Det finns en liten bit matematik inblandade här. Okej, så för att göra användning av våra beräkningsresurser i den verkliga world-- det verkligen viktigt att förstå algoritmer och hur de behandlar uppgifter. Om vi ​​har en riktigt effektiv algoritm, vi kan minimera mängden resurser vi har till förfogande för att ta itu med det. Om vi ​​har en algoritm som kommer att ta en hel del arbete att bearbeta en riktigt stor uppsättning av data, är det kommer att kräva mer och mer resurser, vilket är pengar, RAM, alla den typen av saker. 

Så, att kunna analysera en algoritm att använda detta verktyg set, princip frågar question-- hur fungerar denna algoritm skala som vi kastar mer och mer data på det? I CS50, mängden data som vi är arbetar med är ganska liten. Generellt är våra program går att köra i en andra eller less-- förmodligen mycket mindre särskilt tidigt. 

Men tänk om ett företag som behandlar med hundratals miljoner kunder. Och de behöver för att bearbeta kunden uppgifter. Eftersom antalet kunder som de har blir större och större, det kommer att kräva mer och mer resurser. Hur många fler resurser? Tja, det beror på hur vi analyserar algoritmen, med hjälp av verktygen i verktygslådan. När vi talar om komplexiteten i en algorithm-- som ibland du kommer höra det kallas tid komplexitet eller utrymme komplexitet men vi ska bara ringa complexity-- vi generellt talar om det värsta scenariot. Med tanke på den absolut värsta högen av data som vi kan kasta på det, Hur är denna algoritm kommer att bearbeta eller ta itu med dessa uppgifter? Vi kallar allmänhet värsta fall runtime av en algoritm big-O. Så en algoritm kan sägas köra i O n eller O av n kvadrat. Och mer om vad de innebär i en sekund. 

Men ibland gör vi vård om det bästa scenariot. Om uppgifterna är allt vi ville det ska vara och det var absolut perfekt och vi skickar denna perfekt datauppsättning genom vår algoritm. Hur skulle det handtag i en sådan situation? Vi hänvisar ibland till det som big-Omega, så till skillnad från big-O, Vi har big-Omega. Big-Omega för bästa scenariot. Big-O för det värsta scenariot. Generellt när vi talar om komplexiteten av en algoritm, vi pratar om i värsta fall. Så ha det i åtanke. 

Och i denna klass, vi generellt gå att lämna noggrann analys åt sidan. Det finns vetenskaper och fält ägnas åt den här typen av grejer. När vi talar om resonemang genom algoritmer, som vi kommer att göra bit-för-bit för många algoritmer vi talar om i klassen. Vi egentligen bara talar om resonemang igenom det med sunt förnuft, inte med formler, eller bevis, eller nåt sånt. Så oroa dig inte, vi kommer inte att förvandlas till en stor matte klass. 

Så jag sa att vi bryr oss om komplexitet eftersom det ställer frågan, hur gör våra algoritmer hanterar större och större datamängder som kastas på dem. Nå, vad är en datamängd? Vad jag menar när jag sa det? Det betyder vad gör mest mening i sitt sammanhang, för att vara ärlig. Om vi ​​har en algoritm, den Processer Strings-- vi förmodligen talar om storleken på strängen. Det är data set-- storleken, antalet tecken som utgör strängen. Om vi ​​pratar om en algoritm som behandlar filer, vi kan tala om hur många kilobyte omfattar den filen. Och det är datamängden. Om vi ​​pratar om en algoritm som hanterar arrayer mer generellt, såsom sorteringsalgoritmer eller sökalgoritmer, vi förmodligen pratar om antalet element som utgör en array. 

Nu kan vi mäta en algorithm-- särskilt när jag säger att vi kan mäta en algoritm, jag menar vi kan mäta hur många resurser det tar upp. Huruvida dessa resurser är, hur många bytes RAM-- eller megabyte RAM-minne den använder. Eller hur mycket tid det tar att köra. Och vi kan kalla detta mäta, godtyckligt, f n. Där n är antalet element i datamängden. Och f n är hur många things. Hur många enheter av resurser gör det behöver för att behandla dessa uppgifter. 

Nu, vi faktiskt inte bryr vad f n är exakt. I själva verket mycket sällan will-- vi säkert kommer aldrig i denna class-- jag dyka in i någon riktigt djup analys av vad f hos n är. Vi ska bara tala om vad f från n är ungefär eller vad det tenderar att. Och tendensen av en algoritm är dikteras av sin högsta ordningens term. Och vi kan se vad jag menar med detta genom att ta En titt på en mer konkret exempel. 

Så låt oss säga att vi har tre olika algoritmer. Den första som tar n kubik, vissa enheter av resurser att behandla en datauppsättning av storlek n. Vi har en andra algoritm som tar n kubik plus n kvadrerade resurser att behandla en datauppsättning av storlek n. Och vi har en tredje algoritm som körs in-- att tar upp n kubik minus 8n kvadrat plus 20 n enheter av resurser att behandla en algoritm med uppgifter som storlek n. 

Nu igen, vi verkligen inte kommer att komma in i denna detaljnivå. Jag är verkligen bara har dessa upp här som en illustration av en punkt att jag kommer att vara vilket i ett andra, som är att vi bara verkligen bryr om tendensen hos saker som datamängderna blir större. Så om datamängden är liten, det finns faktiskt en ganska stor skillnad i dessa algoritmer. Den tredje algoritmen där tar 13 gånger längre, 13 gånger så mycket resurser att köra i förhållande till den första. 

Om vår datamängden är storlek 10, som är större, men inte nödvändigtvis stora, Vi kan se att det finns faktiskt lite av en skillnad. Den tredje algoritmen blir mer effektiv. Det handlar om faktiskt 40% - eller 60% effektivare. Det tar 40% av mängden tid. Det kan run-- det kan ta 400 enheter av resurser att behandla en datauppsättning av storlek 10. Medan den första algoritm, däremot, tar 1.000 enheter av resurser att behandla en datauppsättning av storlek 10. Men titta vad som händer när våra siffror bli ännu större. 

Nu, skillnaden mellan dessa algoritmer börjar bli lite mindre uppenbar. Och det faktum att det finns lägre ordningens terms-- eller snarare, termer med lägre exponents-- börjar bli irrelevant. Om en datauppsättning är av storlek 1000 och den första algoritmen körs i en miljard steg. Och den andra algoritmen körs i en miljard och en miljon steg. Och den tredje algoritmen körs på bara blyg av en miljard steg. Det är ganska mycket en miljard steg. De lägre ordningens termer börjar att bli riktigt irrelevant. Och bara för att verkligen hammare hem point-- om dataingången är av storlek en million-- alla tre av dessa ganska mycket ta en quintillion-- om min matte är correct-- steg att bearbeta en dataingång storlek en miljon. Det är en mängd åtgärder. Och det faktum att en av dem kanske ta ett par 100000, eller ett par 100 miljoner ännu mindre när Vi pratar om ett antal som big-- det är ganska irrelevant. De tenderar alla att ta approximativt n kubik, och så skulle vi faktiskt hänvisar till alla dessa algoritmer som i storleksordningen n kubik eller big-O n i kubik. 

Här är en lista över några av de mer gemensamma beräkningskomplexitetsklasser att vi kommer att stöta in algoritmer, i allmänhet. Och även specifikt i CS50. Dessa beställs från allmänhet snabbast på toppen, allmänt långsammaste i botten. Så konstant tids algoritmer tenderar att vara den snabbaste, oavsett av storleken på den inmatning av data du skickar in. De tar alltid en operation eller en enhet av resurser för att ta itu med. Det kan vara två, kanske det vara 3, kan det vara 4. Men det är ett konstant antal. Det varierar inte. 

Logaritmisk tidsalgoritmer är något bättre. Och en riktigt bra exempel på en logaritmisk tidsalgoritm Du har säkert sett vid det här laget är det isärrivning av telefonboken att hitta Mike Smith i telefonboken. Vi skär problemet i hälften. Och så n blir större och större och larger-- i själva verket varje gång du dubbla n tar det bara ett steg. Så det är en mycket bättre än, säg, linjär tid. Vilket är om du dubbla n, det tar dubbelt så många steg. Om du tredubbla n tar det tredubbla antalet steg. Ett steg per enhet. 

Då det blir lite more-- lite mindre bra därifrån. Du har linjär rytmisk tid, ibland kallas log linjär tid eller bara n log n. Och vi ska ett exempel av en algoritm som körningar i n log n, som fortfarande är bättre än kvadratisk time-- n kvadrat. Eller polynomtid, n två valfritt antal större än två. Eller exponentiell tid, vilket är även worse-- C till n. Så några konstant antal höjas till kraften i storleken av insignalen. Så om det finns 1,000-- om dataingång är av storlek 1000, det skulle ta C till åter 1000:e kraften. Det är mycket värre än polynomisk tid. 

Faktoriell tid är ännu värre. Och faktiskt, det verkligen gör Det finns oändliga tids algoritmer, såsom, s.k. dum sort-- vars jobb är att slumpmässigt blanda en array och sedan kontrollera oavsett om det är för sortering. Och om det inte är slumpmässigt shuffle arrayen igen och kontrollera om det sorteras. Och som ni kan nog imagine-- du kan föreställa sig en situation var i värsta fall kommer att aldrig faktiskt börjar med matrisen. Denna algoritm skulle köra alltid. Och så det skulle vara en oändlig tid algoritm. Förhoppningsvis kommer du inte att skriva varje fakultet eller oändlig tid algoritmer i CS50. 

Så, låt oss ta en lite mer betong titt på några enklare beräkningskomplexitetsklasser. Så vi har en example-- eller två exempel här-- av konstanta tidsalgoritmer, som alltid tar en enda operation i värsta fall. Så den första example-- vi har en funktion kallade 4 för dig, som tar en rad storlek 1000. Men sedan tydligen inte faktiskt ser på det-- egentligen inte bryr sig vad som är insidan av det, i nämnda matris. Alltid bara returnerar fyra. Så att algoritmen, trots det faktum att det tar 1000 element inte göra något med dem. Bara tillbaka fyra. Det är alltid ett enda steg. 

I själva verket, tillsätt 2 nums-- som vi har sett tidigare som well-- bara behandlar två heltal. Det är inte ett enda steg. Det är faktiskt ett par steg. Du får en får du b, du lägga till dem tillsammans, och du matar ut resultaten. Så det är 84 steg. Men det är alltid konstant, oavsett a eller b. Du måste få en, få b, lägg ihop dem, mata ut resultatet. Så det är en konstant tidsalgoritm. 

Här är ett exempel på en linjär tids algorithm-- en algoritm som gets-- som tar ett ytterligare steg, eventuellt, som din input växer med 1. Så, låt oss säga att vi letar efter antalet 5 insidan av en matris. Du kanske har en situation där du kan finna det ganska tidigt. Men du kan också ha en situation där det kan vara det sista elementet i uppsättningen. I en matris med storleken 5, om Vi letar efter nummer 5. Det skulle ta 5 steg. Och faktiskt, föreställa sig att det finns inte 5 någonstans i denna uppsättning. Vi har fortfarande faktiskt måste titta på varje enskilt element i matrisen i syfte att fastställa huruvida 5 är där. 

Så i värsta fall, vilket är att elementet är sist i gruppen eller inte existerar alls. Vi måste fortfarande titta på alla av n element. Och så denna algoritm körs i linjär tid. Du kan bekräfta detta genom att extrapolera lite genom att säga, om vi hade en 6-elementgrupp och Vi letade efter nummer 5, det kan ta 6 steg. Om vi ​​har en 7-elementgrupp och Vi letar efter nummer 5. Det kan ta 7 steg. Som vi lägga till ytterligare en faktor till vår array, tar det ett steg. Det är en linjär algoritm i värsta fall. 

Par snabba frågor till dig. Vad är runtime-- vad värsta fall runtime av denna speciella kodsträng? Så jag har en 4 slinga här som körs från j är lika med 0, hela vägen upp till m. Och vad jag ser här, är att kropp av slingan körs i konstant tid. Så använder den terminologi som Vi har redan talat about-- vad skulle vara det värsta runtime av denna algoritm? Ta en andra. Den inre delen av slingan körs i konstant tid. Och den yttre delen av den slinga kommer att köra m gånger. Så vad är det värsta fall runtime här? Har du gissa big-O m? Du skulle bli rätt. 

Vad sägs om en annan? Den här gången har vi en slinga i en slinga. Vi har en yttre slinga som går från noll till sid. Och vi har en inre slinga som löper från noll till p, och insidan av det, Jag konstatera att kroppen slinga körs i konstant tid. Så vad är det värsta fall runtime av denna speciella kodsträng? Tja, återigen, har vi en yttre slinga som löper p gånger. Och varje time-- iteration av denna slinga, snarare. Vi har en inre slinga som körs också p gånger. Och sedan inne i det, det är konstant time-- lilla utdrag där. 

Så om vi har en yttre slinga som körs p tider inuti vilket är en inre ögla som löper p times-- vad som är värsta fall runtime av detta utdrag av koden? Har du gissa big-O p kvadrat? 

Jag är Doug Lloyd. Detta är CS50.