Greit, så, beregningsorientert kompleksitet. Bare litt av en advarsel før vi dykker i for far-- Dette vil trolig være blant de matematiske-tunge ting vi snakker om i CS50. Forhåpentligvis vil det ikke bli for overveldende og vi skal prøve å veilede deg gjennom prosessen, men bare en bit av en rettferdig advarsel. Det er litt matematikk involvert her. Greit, så for å gjøre bruk av våre beregningsressurser i den virkelige world-- er det virkelig viktig å forstå algoritmer og hvordan de behandler data. Hvis vi har en virkelig effektiv algoritme, vi kan minimere mengden av ressurser vi har tilgjengelig for å håndtere det. Hvis vi har en algoritme som kommer til å ta mye arbeid å behandle en virkelig stort sett av data, er det kommer til å kreve mer og mer ressurser, som er penger, RAM, all den slags ting. 

Så, for å være i stand til å analysere en Algoritmen bruker dette verktøyet sett, utgangspunktet, spør question-- hvordan fungerer denne algoritmen skala som vi kaster mer og mer data på det? I CS50, mengden data vi er arbeider med er ganske liten. Vanligvis er våre programmer kommer å kjøre i et sekund eller less-- sannsynligvis mye mindre spesielt tidlig. 

Men tenk om et selskap som avtaler med hundrevis av millioner av kunder. Og de trenger for å behandle at kundedata. Ettersom antallet kunder de har blir større og større, det kommer til å kreve flere og flere ressurser. Hvor mange flere ressurser? Vel, det avhenger av hvordan vi analysere algoritmen, ved hjelp av verktøyene i denne kassen. Når vi snakker om kompleksiteten en algorithm-- som noen ganger du vil hører det referert til som tids kompleksitet eller plass kompleksitet men vi skal bare å ringe complexity-- vi vanligvis snakker om worst-case scenario. Gitt den absolutt verste haug av data som vi kan kaste på det, hvordan er denne algoritmen skal behandle eller håndtere disse dataene? Vi vanligvis kaller worst-case runtime av en algoritme big-O. Slik at en algoritme kan sies å kjøre i O n eller O n squared. Og mer om hva de betyr i en andre. 

Noen ganger, skjønt, vi bryr oss om best-case scenario. Hvis dataene er alt vi ønsket det skal være, og det var helt perfekt og vi skulle sende dette perfekt sett av data gjennom algoritme. Hvordan ville det håndtere i denne situasjonen? Vi noen ganger refererer til at så big-Omega, slik at i motsetning til stor-O, vi har big-Omega. Big-Omega for best-case scenario. Big-O for worst-case scenario. Vanligvis, når vi snakker om kompleksiteten av en algoritme, vi snakker om worst-case scenario. Så hold det i tankene. 

Og i denne klassen, vi vanligvis går å forlate grundig analyse til side. Det er fag og felt viet til denne typen ting. Når vi snakker om resonnement gjennom algoritmer, som vi vil gjøre bit-for-bit for mange algoritmer vi snakke om i klassen. Vi er egentlig bare snakker om resonnement gjennom den med sunn fornuft, ikke med formler, eller bevis, eller noe sånt. Så ikke bekymre deg, vil vi ikke være snu til en stor matte klasse. 

Så jeg sa at vi bryr oss om kompleksitet fordi det stiller spørsmålet, hvordan gjør våre algoritmer håndtere større og større datasett blir kastet på dem. Vel, hva er et datasett? Hva var det jeg mener når jeg sier det? Det betyr at uansett gjør det meste fornuft i sammenheng, for å være ærlig. Hvis vi har en algoritme, er Prosesser Strings-- vi er trolig snakker om størrelsen av strengen. Det er data set-- størrelsen, antallet tegn som utgjør strengen. Hvis vi snakker om en algoritme som behandler filer, Vi snakker kanskje om hvordan mange kilobyte omfatter denne filen. Og det er datasettet. Hvis vi snakker om en algoritme som håndterer arrays mer generelt, slik som sortering algoritmer eller søker algoritmer, vi trolig snakker om antall av elementer som utgjør en oppstilling. 

Nå kan vi måle en algorithm-- særlig når jeg sier vi kan måle en algoritme, I mener vi kan måle hvor mange ressurser det tar opp. Enten disse ressursene er, hvor mange byte av RAM-- eller megabyte RAM den bruker. Eller hvor mye tid det tar å kjøre. Og vi kan kalle dette måle, vilkårlig, f n. Hvor n er antall elementer i datasettet. Og f n er hvor mange somethings. Hvor mange enheter av ressurser gjør det trenger for å behandle dataene. 

Nå har vi faktisk ikke bryr seg om hva f n er nøyaktig. Faktisk er vi svært sjelden will-- sikkert vil aldri i denne class-- jeg dykke inn i noen virkelig dype analyse av hva f n er. Vi er bare nødt til å snakke om hva f av n er ca eller hva det pleier å. Og tendensen til en algoritme er diktert av sin høyeste orden sikt. Og vi kan se hva jeg mener med at ved å ta en se på en mer konkret eksempel. 

Så la oss si at vi har tre forskjellige algoritmer. Den første av disse tar n cubed, noen enheter av ressurser å behandle et datasett av størrelse n. Vi har en annen algoritme som tar n terninger pluss n squared ressurser å behandle et datasett av størrelse n. Og vi har en tredje algoritme som kjører in-- som tar opp n cubed minus 8n squared pluss 20 n enheter av ressurser å behandle en algoritme med datasett av størrelse n. 

Nå igjen, vi egentlig ikke kommer å komme inn i denne detaljnivå. Jeg er egentlig bare ha disse opp her som en illustrasjon av en punkt at jeg kommer til å være gjør i et sekund, noe som er at vi bare virkelig bryr seg om tendensen ting som datasettene blir større. Slik at hvis datasettet er liten, er det faktisk en ganske stor forskjell i disse algoritmene. Den tredje algoritme der tar 13 ganger lengre, 13 ganger så mye ressurser å løpe i forhold til den første. 

Hvis vår datasettet er størrelse 10, som er større, men ikke nødvendigvis stor, Vi kan se at det er faktisk litt av en forskjell. Den tredje algoritme blir mer effektiv. Det handler om å faktisk 40% - eller 60% mer effektiv. Det tar 40% av mengden av tid. Det kan run-- det kan ta 400 enheter av ressurser å behandle et datasett av størrelse 10. Mens den første algoritmen, derimot, tar 1.000 enheter av ressurser å behandle et datasett av størrelse 10. Men se hva som skjer når våre tall blir enda større. 

Nå, forskjellen mellom disse algoritmene begynner å bli litt mindre tydelig. Og det faktum at det finnes lavere ordens terms-- eller rettere sagt, vilkår med lavere exponents-- begynner å bli irrelevant. Hvis et datasett er av størrelse 1000 og den første algoritme kjører i en milliard trinn. Og den andre algoritmen kjører i en milliard og en million skritt. Og den tredje algoritmen kjører i bare sjenert av en milliard trinn. Det er ganske mye en milliard trinn. De lavere-ordens termer starte å bli virkelig irrelevant. Og bare for å virkelig hammer hjem point-- hvis dataene inngangen er av størrelse en million-- alle tre av disse ganske mye ta ett quintillion-- hvis min matte er correct-- trinn å behandle en data input av størrelse en million. Det er mange av trinnene. Og det faktum at en av dem kan ta et par 100 000, eller et par 100 million enda mindre når vi snakker om en rekke at big-- det er litt irrelevant. De har alle en tendens til å ta ca n terninger, og så ville vi faktisk henviser til alle disse algoritmene som å være av størrelsesorden n isbiter eller big-O n terninger. 

Her er en liste over noen av de mer vanligste beregningsorientert kompleksitet klasser at vi vil møte i algoritmer, generelt. Og også spesielt i CS50. Disse er bestilt fra generelt raskest på toppen, generelt langsomste nederst. Så konstant tids algoritmer pleier å være den raskeste, uavhengig av størrelsen av data input du passerer i. De alltid ta en operasjon eller en enhet av ressurser til å håndtere. Det kan være to, det kan være 3, kan det være fire. Men det er et konstant tall. Det varierer ikke. 

Logaritmiske tids algoritmer er litt bedre. Og et veldig godt eksempel på en logaritmisk tid algoritme du har sikkert sett nå er den rive fra hverandre av telefonboken å finne Mike Smith i telefonboken. Vi kuttet problemet i to. Og slik som n blir større og større og larger-- faktisk, hver gang du dobler n, tar det bare ett trinn. Så det er mye bedre enn for eksempel lineær tid. Som er hvis du dobler n, det tar dobbelt antall skritt. Hvis du tredoble n, tar det tredoble antall skritt. Ett skritt per enhet. 

Så det blir litt mer-- litt mindre bra derfra. Du har lineær rytmisk tid, noen ganger kalt log lineær tid eller bare n log n. Og vi vil et eksempel av en algoritme som kjører i n log n, som fortsatt er bedre enn kvadratisk tid-- n squared. Eller polynomisk tid, n to- hvilket som helst tall større enn to. Eller eksponentiell tid, som er enda C til worse-- n. Så hevet til noen konstant antall kraften av størrelsen på inngangen. Så hvis det er 1,000-- hvis data input er av størrelse 1000, det ville ta C til 1000 th strøm. Det er mye verre enn polynomisk tid. 

Fakultet tid er enda verre. Og faktisk er det egentlig gjøre eksisterer uendelig tid algoritmer, for eksempel, såkalte dum sort-- som jobb er å tilfeldig shuffle en matrise og deretter sjekke for å se enten det er sortert. Og hvis det ikke er, tilfeldig shuffle rekken igjen og sjekk for å se om det er sortert. Og så kan du sannsynligvis imagine-- du kan forestille seg en situasjon hvor i verste fall, at viljen aldri faktisk begynne med array. At algoritmen ville kjøre for alltid. Og så det ville være en uendelig tid algoritme. Forhåpentligvis vil du ikke være å skrive alle fakultet eller uendelig tid algoritmer i CS50. 

Så, la oss ta en litt mer betong titt på noen enklere beregningsorientert kompleksitet klasser. Så vi har en example-- eller to eksempler her-- av konstante tids algoritmer, som alltid tar en enkelt operasjon i verste tilfelle. Så det første example-- vi har en funksjon kalt 4 for deg som tar en rekke størrelse 1000. Men så tilsynelatende faktisk ikke ser på it egentlig ikke bryr seg hva som er innsiden av den, i den oppstillingen. Alltid bare returnerer fire. Så, at algoritmen, til tross for det faktum at den tar 1.000 elementene ikke frem gjøre noe med dem. Bare returnerer fire. Det er alltid et enkelt trinn. 

Faktisk, tilsett 2 nums-- som vi har sett før samt-- bare behandler to heltall. Det er ikke et enkelt trinn. Det er faktisk et par skritt. Du får en, får du b, legger du dem sammen, og du sende resultatene. Så det er 84 trinn. Men det er alltid konstant, uavhengig av a eller b. Du må få en, får b, legg dem sammen, utgang resultatet. Så det er en konstant tid algoritme. 

Her er et eksempel på en lineær tid algorithm-- en algoritme som gets-- som tar en ytterligere trinn, eventuelt som input vokser etter en. Så, la oss si at vi leter etter antall 5 inne i en matrise. Du kan ha en situasjon der du kan finne det ganske tidlig. Men du kan også ha en situasjon hvor det kan være det siste element i matrisen. I en rekke av størrelse 5, hvis Vi leter etter nummer 5. Det ville ta 5 trinn. Og faktisk, forestille seg at det er ikke 5 hvor som helst i denne matrisen. Vi har fortsatt faktisk nødt til å se på hvert enkelt element i matrisen for å bestemme hvorvidt 5 er der. 

Så i verste fall, som er at elementet er sist i rekken eller ikke eksisterer i det hele tatt. Vi har fortsatt å se på alle de n elementene. Og så denne algoritmen kjører i lineær tid. Du kan bekrefte at ved ekstrapolere litt ved å si: hvis vi hadde en 6-element array og vi var ute etter nummer 5, det kan ta 6 trinn. Hvis vi har en 7-element array og Vi leter etter nummer 5. Det kan ta 7 trinn. Som vi legge til en mer element i vår array, tar det enda et steg. Det er en lineær algoritme i verste fall. 

Par raske spørsmål for deg. Hva er runtime-- hva som er worst-case runtime av denne spesielle kodebit? Så jeg har en 4 sløyfe her som kjører fra j er lik 0, hele veien opp til m. Og det jeg ser her, er at legeme av sløyfen kjører i konstant tid. Så bruker terminologien Vi har allerede snakket om-- hva ville være det verste-fall runtime av denne algoritmen? Ta et sekund. Den indre delen av sløyfen kjører i konstant tid. Og den ytre delen av sløyfe kommer til å kjøre m ganger. Så hva er worst-case runtime her? Visste du gjette big-O av m? Du ville være riktig. 

Hva med en annen? Denne gangen har vi en løkke inne i en løkke. Vi har en ytre sløyfe som går fra null til p. Og vi har en indre løkke som går fra null til p, og på innsiden av denne, Jeg sier at kroppen sløyfe går i konstant tid. Så hva er worst-case runtime av denne spesielle kodebit? Vel, igjen, har vi en ytre sløyfe som går p ganger. Og hver tid-- køyring av at loop, heller. Vi har en indre sløyfe som også kjører p ganger. Og så innsiden av det, det er den konstant tid-- liten bit der. 

Så hvis vi har en ytre løkke som løper p ganger innsiden av disse er en indre løkke som kjører p times-- hva er worst-case runtime av denne kodebit? Visste du gjette big-O p squared? 

Jeg er Doug Lloyd. Dette er CS50.