Okay, så, beregningsmæssige kompleksitet. Bare lidt af en advarsel før vi dykker i alt for far-- dette vil sandsynligvis være blandt de mest matematiske-tunge ting vi taler om i CS50. Forhåbentlig vil det ikke være for overvældende og vi vil forsøge at guide dig gennem processen, men bare lidt af en retfærdig advarsel. Der er en lille smule af matematik involveret her. Okay, så for at gøre brug af vores it-ressourcer i den virkelige verden-det er virkelig vigtigt at forstå algoritmer og hvordan de behandler oplysninger. Hvis vi har en rigtig effektiv algoritme, vi kan minimere mængden af ​​ressourcer vi har til rådighed til at behandle den. Hvis vi har en algoritme, kommer til at tage en masse arbejde at behandle en virkelig store datasæt, er det vil kræve mere og flere ressourcer, som er penge, RAM, alle den slags ting. 

Så at kunne analysere et algoritme, der anvender dette værktøj sæt, dybest set, spørger question-- hvordan gør denne algoritme skala som vi smider flere og flere data på det? I CS50, mængden af ​​data er vi arbejder med er temmelig lille. Generelt er vores programmer går at køre i en anden eller less-- sikkert en masse mindre især tidligt. 

Men tænk på et firma, der handler med hundredvis af millioner af kunder. Og de har brug for at behandle at kundernes data. Da antallet af kunder, de har bliver større og større, det kommer til at kræve flere og flere ressourcer. Hvor mange flere ressourcer? Tja, det afhænger af, hvordan vi analysere algoritme, ved hjælp af de værktøjer i denne værktøjskasse. Når vi taler om kompleksitet en algorithm-- som undertiden vil du høre det omtalt som tiden kompleksitet eller rum kompleksitet men vi bare at kalde complexity-- vi generelt taler om det værst tænkelige scenarie. I betragtning af den absolutte værste bunke data, som vi kunne smide på det, hvordan denne algoritme vil forarbejde eller beskæftige sig med disse data? Vi generelt kalder det værst tænkelige runtime af en algoritme big-O. Så en algoritme kan siges at køre i O n eller O n potens. Og mere om, hvad dem betyde i et sekund. 

Nogle gange, selv om, vi gør pleje om det bedste tænkelige scenario. Hvis dataene er alt, hvad vi ønskede det at være, og det var helt perfekt og vi var at sende denne perfekte sæt af data gennem vores algoritme. Hvordan ville det håndtere i denne situation? Vi nogle gange henviser til, at så big-Omega, så i modsætning til store-O, vi har big-Omega. Big-Omega for bedste fald. Big-O for det værst tænkelige scenarie. Generelt, når vi taler om kompleksiteten af ​​en algoritme, vi taler om den værst tænkelige scenario. Så holder det i tankerne. 

Og i denne klasse, er vi generelt går at forlade grundig analyse til side. Der er videnskaber og felter viet til den slags ting. Når vi taler om ræsonnement via algoritmer, som vi vil gøre stykke-for-stykke for mange algoritmer vi taler om i klassen. Vi er virkelig bare taler om ræsonnement gennem det med sund fornuft, ikke med formler, eller beviser, eller sådan noget. Så du skal ikke bekymre dig, vil vi ikke være ved at blive en stor matematik klasse. 

Så jeg sagde, at vi interesserer os for kompleksitet fordi det stiller spørgsmålet, hvordan gør vores algoritmer håndtere større og større datasæt kastes på dem. Nå, hvad er et datasæt? Hvad gjorde jeg mener, når jeg sagde det? Det betyder, hvad gør mest mening i sammenhæng, at være ærlig. Hvis vi har en algoritme, den Processer Strings-- vi er nok tale om størrelsen af ​​strengen. Det er data set-- størrelsen, antallet tegn, der udgør strengen. Hvis vi taler om en algoritme der behandler filer, vi måske tale om, hvordan mange kilobyte omfatter denne fil. Og det er datasættet. Hvis vi taler om en algoritme der håndterer arrays mere generelt, såsom sortering algoritmer eller søge algoritmer, vi nok taler om antallet elementer, der omfatter et array. 

Nu, vi kan måle en algorithm-- i særdeleshed, når jeg siger, vi kan måle en algoritme, jeg mener, vi kan måle, hvor mange ressourcer, det tager op. Hvorvidt disse ressourcer er, hvor mange bytes RAM-- eller megabyte RAM det bruger. Eller hvor meget tid det tager at køre. Og vi kan kalde denne måle, vilkårligt, f af n. Hvor n er antallet af elementer i datasættet. Og f af n er, hvor mange somethings. Hvor mange enheder af ressourcer gør det kræve at behandle disse data. 

Nu, vi faktisk ligeglad hvad f n er præcis. Faktisk vi meget sjældent will-- helt sikkert vil aldrig i denne class-- I dykke ned i enhver virkelig dyb analyse af, hvad f n er. Vi er lige kommer til at snakke om, hvad f af n er ca. eller hvad det har tendens til. Og tendensen af ​​en algoritme er dikteret af dets højeste orden sigt. Og vi kan se, hvad jeg mener med at ved at tage et kig på et mere konkret eksempel. 

Så lad os sige, at vi har tre forskellige algoritmer. Hvoraf den første tager n kubik, nogle enheder af ressourcer at behandle et datasæt størrelse n. Vi har en anden algoritme, der tager n kubik plus n firkantede ressourcer at behandle et datasæt størrelse n. Og vi har en tredje algoritme, der kører in-- at fylder n kubik minus 8n kvadreret plus 20 n enheder af ressourcer at behandle en algoritme med datasæt størrelse n. 

Nu igen, vi virkelig ikke vil at komme ind i dette niveau af detaljer. Jeg er virkelig bare har disse op her som en illustration af et punkt at jeg har tænkt mig at være gør i en anden, hvilket er, at vi kun virkelig pleje om tendensen ting som datasættene bliver større. Så hvis datasættet er lille, er der faktisk en temmelig stor forskel i disse algoritmer. Den tredje algoritme der tager 13 gange længere tid, 13 gange den mængde ressourcer at køre i forhold til den første. 

Hvis vores datasæt er størrelse 10, som er større, men ikke nødvendigvis store, Vi kan se, at der er faktisk lidt af en forskel. Den tredje algoritme bliver mere effektiv. Det handler om faktisk 40% - eller 60% mere effektiv. Det tager 40% mængden af ​​tid. Det kan run-- det kan tage 400 enheder af ressourcer at behandle et datasæt af størrelse 10. Mens den første algoritme, derimod, tager 1.000 enheder af ressourcer at behandle et datasæt af størrelse 10. Men se, hvad der sker som vores tal bliver endnu større. 

Nu forskellen mellem disse algoritmer begynder at blive lidt mindre synlige. Og det faktum, at der er lavere ordens terms-- eller rettere, vilkår med lavere exponents-- begynder at blive irrelevant. Hvis et datasæt størrelse 1.000 og den første algoritme kører i en milliard trin. Og anden algoritme kører i en milliard og en million trin. Og den tredje algoritme kører på bare genert af en milliard trin. Det er temmelig meget en milliard trin. Disse lavere ordens led starter til at blive virkelig irrelevant. Og bare for at virkelig hammer hjem point-- hvis input data er størrelse en million-- alle tre af disse temmelig meget tage en quintillion-- hvis min matematik er correct-- skridt at behandle en dataindgang størrelse million. Det er en masse trin. Og det faktum, at en af ​​dem kan tage et par 100.000, eller et par 100 million endnu mindre, når vi taler om et nummer der big-- det er slags irrelevant. De har alle en tendens til at tage ca n kubik, og så ville vi faktisk henvise til alle disse algoritmer som værende af størrelsesordenen n kubik eller store-O n kubik. 

Her er en liste over nogle af de mere fælles beregningsmæssige kompleksitet klasser at vi vil støde på algoritmer generelt. Og også specifikt i CS50. Disse er bestilt fra generelt hurtigste foroven, generelt langsomste nederst. Så konstant tid algoritmer tendens at være den hurtigste, uanset af størrelsen af ​​den datainput du passerer i. De har altid tage en operation eller en enhed af ressourcer at beskæftige sig med. Det kunne være 2, det måske være 3, kan det være 4. Men det er et konstant antal. Det varierer ikke. 

Logaritmiske tid algoritmer er lidt bedre. Og en rigtig godt eksempel på en logaritmisk tid algoritme du har sikkert set af nu er det oprivning af telefonbogen at finde Mike Smith i telefonbogen. Vi sender problemet i halve. Og så n bliver større og større og larger-- i virkeligheden, hver gang du fordobler n, det tager kun et skridt. Så det er meget bedre end fx lineær tid. Hvilket er, hvis du dobbelt n, det tager fordoble antallet af trin. Hvis du tredoble n, det tager tredoble antallet af skridt. Et skridt pr. 

Så tingene bliver lidt more-- lidt mindre fantastisk derfra. Du har lineær rytmisk tid, nogle gange kaldet log lineær tid eller bare n log n. Og vi vil et eksempel af en algoritme, kører i n log n, som stadig bedre end kvadratisk time-- n potens. Eller polynomiel tid, n to hvilket som helst antal større end to. Eller eksponentiel tid, hvilket er endda worse-- C til n. Så nogle konstant antal hævet til magt størrelsen af ​​input. Så hvis der er 1,000-- hvis input data størrelse 1.000, det ville tage C til 1000. magt. Det er meget værre end polynomiel tid. 

Faktorielt tid er endnu værre. Og i virkeligheden, virkelig gøre der Der findes uendelig tid algoritmer, såsom såkaldte dum sort-- hvis job er at tilfældigt shuffle et array og derefter kontrollere, at se uanset om det er sorteret. Og hvis det ikke er, tilfældigt shuffle array igen og kontrollere, om det er sorteret. Og som kan du sikkert imagine-- du kan forestille dig en situation, hvor i det værst tænkelige, der vil faktisk aldrig begynde med arrayet. Denne algoritme ville køre for evigt. Og så det ville være et uendelig tid algoritme. Forhåbentlig vil du ikke skrive enhver fakultet eller uendelig tid algoritmer i CS50. 

Så lad os tage lidt mere beton kig på nogle enklere beregningsmæssige kompleksitet klasser. Så vi har en example-- eller to eksempler her-- af konstant tid algoritmer, som altid tager en enkelt operation i det værst tænkelige. Så den første example-- vi har en funktion kaldte 4 for dig, som tager en bred vifte af størrelse 1000. Men så tilsyneladende faktisk ikke ser på det-- ikke rigtig ligeglad, hvad der er inde i den, for den opstilling. Altid bare returnerer fire. Så denne algoritme, på trods af, at det tager 1.000 elementer ikke gøre noget med dem. Bare returnerer fire. Det er altid et enkelt trin. 

Faktisk, tilsættes 2 nums-- som vi har set før, som well-- lige processer to heltal. Det er ikke et enkelt trin. Det er faktisk en par trin. Du får en, får du b, du tilføje dem sammen, og du output resultaterne. Så det er 84 trin. Men det er altid konstant, uanset a eller b. Du er nødt til at få en, få b, tilføj dem sammen, output resultatet. Så det er en konstant tid algoritme. 

Her er et eksempel på en lineær tid algorithm-- en algoritme, der tager gets-- et yderligere skridt, muligvis, som dit input vokser med 1. Så lad os sige, at vi leder efter nummer 5 indersiden af ​​et array. Du har måske en situation, hvor du kan finde det forholdsvis tidligt. Men man kunne også have en situation, hvor det kan være den sidste element i array. I en vifte af størrelse 5, hvis Vi leder efter nummer 5. Det ville tage 5 trin. Og i virkeligheden, forestille sig, at der er ikke 5 overalt i dette array. Vi har faktisk stadig nødt til at se på hvert enkelt element af arrayet med henblik på at bestemme hvorvidt 5 er der. 

Så i det værst tænkelige, nemlig at elementet er sidst i arrayet eller findes ikke på alle. Vi har stadig til at se på alle de n elementer. Og så denne algoritme kører i lineær tid. Du kan bekræfte, at ved ekstrapolere en lille smule ved at sige, hvis vi havde en 6-element array og vi ledte efter nummer 5, det kan tage 6 trin. Hvis vi har en 7-element array og Vi leder efter nummer 5. Det kan tage 7 trin. Som vi tilføje endnu en element til vores array, det tager endnu et skridt. Det er en lineær algoritme i det værst tænkelige. 

Par hurtige spørgsmål til dig. Hvad er runtime--, hvad der er det værst tænkelige runtime af denne særlige stykke kode? Så jeg har en 4 løkke her, der kører fra j lig 0, hele vejen op til m. Og hvad jeg ser her, er, at organ af løkken kører i konstant tid. Så ved hjælp af terminologi, Vi har allerede talt om-- hvad ville være det værst tænkelige runtime af denne algoritme? Tag et sekund. Den indre del af sløjfen kører i konstant tid. Og den ydre del af loop kommer til at køre m gange. Så hvad er den værst tænkelige runtime her? Vidste du gætte big-O m? Du ville have ret. 

Hvad med en anden? Denne gang har vi en loop inde i en løkke. Vi har en ydre sløjfe der løber fra nul til s. Og vi har en indre sløjfe, der kører fra nul til p, og inde i det, Jeg anfører, at kroppen loop kører i konstant tid. Så hvad er den værst tænkelige runtime af denne særlige stykke kode? Nå, igen, har vi en ydre loop, der kører p gange. Og hver time-- iteration af denne løkke, snarere. Vi har en indre sløjfe , der også kører p gange. Og så inde i det, der er den konstant time-- lille uddrag der. 

Så hvis vi har en ydre løkke, der kører p gange, inden i hvilken er en indre løkke, kører p gange-- hvad der er det værst tænkelige runtime af denne stump kode? Vidste du gætte big-O af p potens? 

Jeg er Doug Lloyd. Det er CS50.