Alle reg, sodat, rekenkundige kompleksiteit. Net 'n bietjie van 'n waarskuwing voordat ons duik in te far-- hierdie sal waarskynlik onder die mees wiskunde-swaar dinge ons praat oor in CS50. Hopelik sal dit nie te oorweldigend wees en ons sal probeer en lei jou deur die proses nie, maar net 'n bietjie van 'n billike waarskuwing. Daar is 'n bietjie van wiskunde hier betrokke. Alle reg, sodat in volgorde na maak gebruik van ons hulpbronne computational in die werklike world-- dit is regtig belangrik om te verstaan ​​algoritmes en hoe hulle verwerk data. As ons 'n werklik doeltreffende algoritme, ons kan die bedrag van die hulpbronne te minimaliseer ons beskikbaar om dit te hanteer. As ons 'n algoritme wat gaan 'n baie werk te neem om werklik te verwerk 'n groot versameling van data, dit is gaan meer nodig en meer hulpbronne, wat is geld, geheue, al daardie soort van dinge. 

So, in staat is om 'n analiseer algoritme gebruik van hierdie hulpmiddel stel, basies, vra die question-- hoe werk hierdie algoritme skaal as ons gooi meer en meer data op dit? In CS50, die bedrag van die data ons werk met is redelik klein. Oor die algemeen, is ons programme gaan uit te voer in 'n tweede of less-- waarskynlik 'n baie minder veral vroeg op. 

Maar dink oor 'n maatskappy wat handel oor met honderde miljoene kliënte. En wat hulle nodig het om te verwerk dat die kliënt data. As die aantal kliënte wat hulle het groter en groter, dit gaan om te vereis meer en meer hulpbronne. Hoeveel meer hulpbronne? Wel, dit hang af van hoe ons analiseer die algoritme, die gebruik van die gereedskap in hierdie toolbox. Wanneer ons praat oor die kompleksiteit van 'n algorithm-- wat soms jy sal hoor dit verwys na die tyd kompleksiteit of ruimte kompleksiteit maar ons gaan net om te bel complexity-- ons praat oor die algemeen die ergste scenario. Gegewe die absolute ergste hopie data wat ons kan gooi dit, hoe word hierdie algoritme gaan verwerk of hanteer dat die data? Ons oor die algemeen noem die ergste geval runtime van 'n algoritme groot-O. So 'n algoritme kan gesê word dat hardloop in O van n of O van n vierkant. En meer oor wat diegene bedoel in 'n tweede. 

Soms, al is, sorg ons doen oor die beste scenario. As die data is alles wat ons wou dit moet wees en dit was absoluut perfek en ons was te stuur hierdie perfekte stel data deur ons algoritme. Hoe sou dit te hanteer in daardie situasie? Ons verwys soms dat groot-Omega, so in kontras met die groot-O, ons het groot-Omega. Big-Omega vir die beste scenario. Big-O vir die ergste scenario. Oor die algemeen, wanneer ons praat oor die kompleksiteit van 'n algoritme, ons praat oor die ergste geval scenario. So hou dit in gedagte. 

En in hierdie klas, is ons oor die algemeen gaan om die akkurate analise opsy te verlaat. Daar is wetenskap en velde gewy aan hierdie soort van dinge. Wanneer ons praat oor redenasie deur algoritmes, wat ons stuk-vir-stuk sal doen vir baie algoritmes ons praat oor in die klas. Ons is regtig net te praat oor redeneer deur dit met gesonde verstand, nie met formules, of bewyse, of iets soos dit. So moenie bekommerd wees nie, sal ons nie draai in 'n groot wiskunde klas. 

So ek sê ons omgee kompleksiteit want dit vra die vraag, hoe doen ons algoritmes te hanteer en groter groter datastelle op hulle gegooi. Wel, wat is 'n datastel? Wat het ek bedoel as ek sê dat? Dit beteken ook al die meeste maak sin in konteks, om eerlik te wees. As ons 'n algoritme, die Prosesse Strings-- ons is waarskynlik praat oor die grootte van die string. Dit is die data set-- die grootte, die aantal karakters wat die string. As ons praat oor 'n algoritme wat lêers prosesse, Ons kan praat oor hoe baie kilogrepe bestaan ​​dat 'n lêer. En dit is die datastel. As ons praat oor 'n algoritme wat hanteer skikkings meer algemeen, soos sorteringsalgoritmes of soek algoritmes, ons waarskynlik praat oor die aantal elemente wat 'n verskeidenheid bestaan. 

Nou, ons kan 'n meet algorithm-- in die besonder, as ek sê ons kan meet 'n algoritme, ek beteken dat ons meet hoe baie hulpbronne dit neem. Of daardie hulpbronne is, hoeveel grepe van RAM-- of megagrepe RAM dit gebruik. Of hoeveel tyd wat dit neem om te hardloop. En ons kan dit noem meet, arbitrêr, f van n. Waar n die aantal elemente in die datastel. En f van N is hoeveel Iets. Hoeveel eenhede van hulpbronne nie dit vereis dat die data te verwerk. 

Nou, ons het eintlik nie omgee oor wat f van N is presies. Trouens, ons baie selde will-- sal seker nooit in hierdie class-- ek duik in enige regtig diep ontleding van wat f van N is. Ons is net gaan om te praat oor wat f van N is ongeveer of wat dit is geneig om. En die neiging van 'n algoritme is bepaal deur die hoogste orde termyn. En ons kan sien wat ek daarmee deur die neem van 'n blik op 'n meer konkrete voorbeeld. 

So kom ons sê dat ons drie verskillende algoritmes. Waarvan die eerste neem n blokkies, sommige eenhede van hulpbronne om 'n datastel van grootte n verwerk. Ons het 'n tweede algoritme wat neem N blokkies plus N kwadraat hulpbronne om 'n datastel van grootte n verwerk. En ons het 'n derde algoritme wat in-- wat loop neem n blokkies minus 8N kwadraat plus 20 N eenhede van hulpbronne om 'n algoritme te verwerk met datastel grootte n. 

Nou weer, het ons regtig nie gaan om te kry in hierdie vlak van detail. Ek is regtig net hierdie up hier as 'n illustrasie van 'n punt dat ek gaan wees maak in 'n tweede, wat is dat ons net regtig omgee oor die neiging van dinge as die data-stelle te kry groter. So as die datastel is klein, daar is eintlik 'n mooi groot verskil in hierdie algoritmes. Die derde algoritme daar neem 13 keer langer, 13 keer die bedrag van hulpbronne om te hardloop met betrekking tot die eerste een. 

As ons datastel is die grootte 10, wat is groter, maar nie noodwendig groot, ons kan sien dat daar eintlik 'n bietjie van 'n verskil maak. Die derde algoritme raak meer doeltreffend te maak. Dit gaan oor die werklikheid 40% - of 60% meer doeltreffend te maak. Dit neem 40% van die bedrag van die tyd. Dit kan run-- dit kan neem 400 eenhede van hulpbronne om 'n datastel grootte 10 verwerk. Terwyl die eerste algoritme, daarenteen, neem 1000 eenhede van hulpbronne om 'n datastel grootte 10 verwerk. Maar kyk wat gebeur as ons getalle te kry, selfs groter. 

Nou, die verskil tussen hierdie algoritmes begin om 'n bietjie minder duidelik geword. En die feit dat daar laer-orde terms-- of eerder, terme met laer exponents-- begin om irrelevant te word. As 'n datastel is die grootte 1000 en die eerste algoritme loop in 'n miljard stappe. En die tweede algoritme loop in 'n miljard en 'n miljoen stappe. En die derde algoritme loop in net minder as 'n miljard stappe. Dit is nogals 'n miljard stappe. Diegene laer-orde terme begin om werklik irrelevant geword. En net om werklik hamer huis die point-- indien die data insette is van grootte van 'n million-- al drie hierdie pretty much een neem quintillion-- as my wiskunde is correct-- stappe om 'n data insette verwerk grootte van 'n miljoen. Dit is 'n baie stappe. En die feit dat een van hulle dalk neem 'n paar 100,000, of 'n paar 100 miljoen selfs minder as ons praat oor 'n aantal dat big-- dit is soort van irrelevant. Hulle het almal geneig om te neem ongeveer N blokkies, en so sal ons eintlik verwys om al hierdie algoritmes as op die einde van N blokkies of groot-O van n blokkies. 

Hier is 'n lys van sommige van die meer algemene rekenkundige kompleksiteit klasse dat ons sal teëkom in algoritmes, oor die algemeen. En spesifiek ook in CS50. Hierdie is bestel algemeen vinnigste by die top, algemeen stadigste aan die onderkant. So konstante time algoritmes is geneig die vinnigste wees, ongeag van die grootte van die data insette wat jy slaag in. Hulle het altyd een operasie of een eenheid van hulpbronne te hanteer. Dit kan wees 2, dit dalk wees 3, kan dit wees 4. Maar dit is 'n konstante getal is. Dit maak nie wissel. 

Logaritmiese time algoritmes is effens beter. En 'n baie goeie voorbeeld van 'n logaritmiese tyd algoritme sekerlik gesien het deur die nou is die uitmekaar skeur van die telefoon boek Mike Smith vind in die telefoon boek. Ons sny die probleem in die helfte. En so n groter word en groter en larger-- in werklikheid, elke keer as jy dubbel N, dit neem net nog 'n stap. So dit is 'n baie beter as, sê, lineêre tyd. Wat is as jy dubbel N, is dit neem dubbel die aantal stappe. As jy verdriedubbel n, dit neem verdriedubbel die aantal stappe. Een stap per eenheid. 

Toe dinge 'n bietjie more-- bietjie minder groot van daar af. Jy het lineêre ritmiese tyd, soms genoem log lineêre tyd of net n teken n. En ons sal 'n voorbeeld van 'n algoritme wat lopies in n log n, wat is nog steeds beter as kwadratiese time-- N kwadraat. Of polinoom tyd, n twee enige getal groter as twee. Of eksponensiële tyd, wat selfs worse-- C om die n. So 'n paar konstante aantal opgewek die krag van die grootte van die insette. So as daar is 1,000-- indien die data insette is van die grootte 1000, dit sou neem om die C 1000 krag. Dit is 'n baie erger as polinoom tyd. 

Faktoriaal tyd is nog erger. En in die feit, daar is regtig nie bestaan ​​oneindige tyd algoritmes, soos sogenaamde stupid sort-- wie werk is om lukraak shuffle 'n skikking en dan check om te sien of dit gesorteer. En as dit is nie, lukraak shuffle die skikking weer en kyk om te sien of dit gesorteer. En as jy kan waarskynlik imagine-- jy kan 'n situasie indink waar in die ergste geval, dit sal nooit eintlik begin met die skikking. Dit algoritme sal vir ewig te hardloop. En so sou dit 'n wees oneindige tyd algoritme. Hopelik sal jy nie skryf enige faktoriaal of oneindige tyd algoritmes in CS50. 

So, laat ons 'n bietjie meer beton blik op sommige eenvoudiger rekenkundige kompleksiteit klasse. So ons het 'n example-- of twee voorbeelde here-- van konstante tyd algoritmes, wat altyd 'n enkele operasie in die ergste geval. So die eerste example-- ons het 'n funksie genoem 4 vir jou, wat neem 'n verskeidenheid van grootte 1000. Maar dan blykbaar nie eintlik kyk op it-- nie regtig omgee wat is binnekant van dit, van daardie skikking. Net altyd terug vier. So, wat algoritme, ten spyte van die feit dat dit neem 1000 elemente nie enigiets doen met hulle. Net terug vier. Dit is altyd 'n enkele stap. 

In werklikheid, voeg 2 nums-- wat ons voor as well-- gesien het net verwerk twee heelgetalle. Dit is nie 'n enkele stap. Dit is eintlik 'n paar stappe. Jy kry 'n, jy b, jy voeg saam, en jy uitset die resultate. So dit is 84 stappe. Maar dit is altyd konstant, ongeag of 'n b. Jy moet 'n te kry, kry b, voeg hulle saam, uitset die resultaat. So dit is 'n konstante tyd algoritme. 

Hier is 'n voorbeeld van 'n lineêre tyd algorithm-- 'n algoritme wat gets-- wat neem een addisionele stap, moontlik, as jou insette groei deur 1. So, kom ons sê ons is op soek na die nommer 5 binnekant van 'n skikking. Jy kan 'n situasie waar het jy kan vind dit redelik vroeg. Maar jy kan ook ' 'n situasie waar dit dalk die laaste element van die skikking wees. In 'n skikking van grootte 5, indien Ons is op soek na die nommer 5. Dit sou 5 stappe te neem. En in die feit, dink dat daar nie 5 oral in hierdie reeks. Ons het nog steeds eintlik moet kyk na elke enkele element van die skikking ten einde te bepaal of 5 is daar. 

So in die ergste geval, en dit is dat die element is die laaste in die skikking of nie bestaan ​​nie. Ons het nog om te kyk na al die elemente N. En so hierdie algoritme loop in lineêre tyd. Jy kan bevestig dat deur ekstrapoleer 'n bietjie deur te sê, as ons het 'n 6-element skikking en Ons was op soek na die nommer 5, dit dalk 6 stappe te neem. As ons 'n 7-element skikking en Ons is op soek na die nommer 5. Dit mag dalk 7 stappe te neem. As ons by te voeg 'n meer element aan ons skikking, dit neem 'n stap. Dit is 'n lineêre algoritme in die ergste geval. 

Paar vinnige vrae vir jou. Wat is die runtime-- wat is die ergste geval runtime van hierdie spesifieke brokkie kode? So ek het 'n 4 lus hier wat loop van J gelyk 0, al die pad tot m. En wat ek hier sien, is dat die liggaam van die lus loop in konstante tyd. So die gebruik van die terminologie wat ons het reeds about-- wat gepraat sou die ergste geval wees runtime van hierdie algoritme? Neem 'n tweede. Die binneste deel van die lus loop in konstante tyd. En die buitenste deel van die lus gaan m keer hardloop. So, wat is die ergste geval runtime hier? Het jy 'n groot-O van m raai? Jy wil reg wees. 

Hoe oor 'n ander een? Hierdie keer het ons 'n lus binnekant van 'n lus. Ons het 'n buitenste lus wat loop van nul tot p. En ons het 'n innerlike lus wat loop van nul tot p, en binnekant van die, Ek verklaar dat die liggaam die lus loop in konstante tyd. So, wat is die ergste geval runtime van hierdie spesifieke brokkie kode? Wel, weer, ons het 'n buitenste lus wat p keer loop. En elke time-- iterasie van daardie lus, eerder. Ons het 'n innerlike lus wat ook loop p keer. En dan binnekant van daardie, is daar die konstante time-- bietjie brokkie daar. 

So as ons 'n buitenste lus wat loop p keer binnekant van wat 'n innerlike lus wat loop p times-- wat die ergste geval runtime van hierdie kode uit? Het jy 'n groot-O p raai kwadraat? 

Ek is Doug Lloyd. Dit is CS50.