Oké, dus, computationele complexiteit. Gewoon een beetje een waarschuwing voordat we duiken in te far-- Dit zal waarschijnlijk worden onder de meeste wiskunde-zware dingen we praten over in CS50. Hopelijk zal het niet al te overweldigend en we zullen proberen en begeleiden u door het proces, maar gewoon een beetje een eerlijke waarschuwing. Er is een beetje van de wiskunde hier betrokken. Oké, dus om te maken gebruik van onze computationele middelen in de echte wereld-- het is echt belangrijk om algoritmes te begrijpen en hoe zij verwerken data. Als we een echt efficiënte algoritme, we kan de hoeveelheid middelen te minimaliseren we beschikbaar hebben om te gaan. Als we een algoritme dat gaat een hoop werk te nemen om echt te verwerken een grote set van gegevens, het is gaan meer nodig en meer middelen, die is geld, RAM, al dat soort dingen. 

Dus, in staat om een ​​analyse algoritme met behulp van deze tool set, eigenlijk, vraagt ​​de question-- hoe werkt dit algoritme schaal zoals we gooien meer en meer gegevens op het? In CS50, de hoeveelheid gegevens die we werken met is vrij klein. In het algemeen zijn onze programma's gaan om te draaien in een tweede of less-- waarschijnlijk een minder bijzonder vroeg. 

Maar na te denken over een bedrijf dat zich bezighoudt met honderden miljoenen klanten. En ze moeten verwerken dat klantgegevens. Aangezien het aantal klanten dat ze hebben groter en groter, het gaat om eisen meer en meer middelen. Hoeveel middelen? Nou, dat hangt af van hoe we analyseren het algoritme, met behulp van de gereedschappen in deze gereedschapskist. Als we praten over de complexiteit van een algorithm-- die soms je zult hoor het wel aangeduid als de tijd complexiteit of ruimte complexiteit maar we gaan gewoon te bellen complexity-- we het over het algemeen het worst-case scenario. Gezien de absolute slechtste stapel gegevens die we konden worden gooien op het, hoe wordt dit algoritme gaat verwerken of omgaan met die gegevens? We over het algemeen noemen het worst-case runtime van een algoritme big-O. Dus een algoritme kan worden gezegd draaien in O n of O n kwadraat. En meer over wat die betekenen in een tweede. 

Soms, hoewel, zorg wij over de best-case scenario. Als de gegevens is alles wat we wilden het aan en het was absoluut perfect en we stuurden deze perfecte set van gegevens via ons algoritme. Hoe zou het behandelen in die situatie? Wij verwijzen soms dat als big-Omega, dus in tegenstelling big-O, we hebben grote-Omega. Big-Omega voor het beste scenario. Big-O voor het worst-case scenario. Over het algemeen, als we praten over de complexiteit van een algoritme, we praten over de in het ergste geval. Dus hou dat in gedachten. 

En in deze klasse, we meestal gaan aan de strenge analyse buiten beschouwing laten. Er zijn wetenschappen en velden gewijd aan dit soort dingen. Wanneer we praten over redeneren door middel van algoritmes, die wij stuk-voor-stuk zal doen voor velen algoritmes we praten over in de klas. We zijn echt alleen over redeneren doorheen met gezond verstand, niet met formules, of bewijzen, of iets dergelijks. Dus maak je geen zorgen, zullen wij niet verandert in een grote wiskunde klasse. 

Dus ik zei dat we de zorg over de complexiteit want het stelt de vraag, hoe weet onze algoritmes verwerken groter en grotere datasets naar hen gegooid. Nou, wat is een data set? Wat heb ik bedoel als ik zei dat? Het betekent dat wat de meeste maakt zin in context, om eerlijk te zijn. Als we een algoritme, het Processen Strings-- we waarschijnlijk over de grootte van de string. Dat is de data set-- de grootte, het aantal tekens die deel uitmaken van de string. Als we praten over een algoritme dat bestanden verwerkt, we zouden kunnen praten over hoe vele kilobytes bestaan ​​dat bestand. En dat is de dataset. Als we praten over een algoritme die verwerkt arrays algemeen, zoals sorteeralgoritmen of zoeken algoritmen, we waarschijnlijk over het aantal elementen die een array omvatten. 

Nu, we kunnen een meten algorithm-- in het bijzonder, als ik zeg dat we kunnen meten van een algoritme, I bedoelen we kunnen meten hoe veel middelen het neemt. Of deze middelen zijn, hoeveel bytes van RAM-- of megabyte RAM-geheugen gebruikt. Of hoeveel tijd het kost om te draaien. En we kunnen dit noemen meten, willekeurig, f n. Waarbij n het aantal elementen in de dataset. En f n is hoeveel plussers. Hoeveel eenheden van de middelen doet zij eisen dat die gegevens te verwerken. 

Nu, we hebben eigenlijk niet schelen over wat f van n is precies. In feite hebben we zeer zelden will-- zeker zal nooit in deze class-- I Duik in een echt diepe analyse van wat f n. We gaan gewoon praten over wat f van n is ongeveer of wat neigt. De neiging van een algoritme gedicteerd door de hoogste orde termijn. En we kunnen zien wat ik bedoel dat door het nemen Een blik op een concreet voorbeeld. 

Dus laten we zeggen dat we drie verschillende algoritmen. De eerste daarvan is nu n blokjes, sommige eenheden van de middelen een dataset van grootte n verwerken. We hebben een tweede algoritme dat neemt n blokjes plus n kwadraat middelen een dataset van grootte n verwerken. En we hebben een derde algoritme dat in-- die loopt neemt n blokjes minus 8n kwadraat plus 20 n eenheden van de middelen een algoritme te verwerken met data set van grootte n. 

Nu weer, we zijn echt niet van plan om in dit niveau van detail. Ik ben echt gewoon deze omhoog hier ter illustratie van een punt dat ik ga worden die in een tweede, die is dat we alleen echt zorg over de tendens van de dingen als de datasets groter. Dus als de dataset is klein, er is eigenlijk een vrij groot verschil in deze algoritmen. De derde algoritme is er duurt 13 keer langer, 13 keer de hoeveelheid middelen te lopen ten opzichte van de eerste. 

Als onze dataset is maat 10, die groter, maar niet noodzakelijkerwijs groot, kunnen we zien dat er eigenlijk een beetje een verschil. De derde algoritme efficiënter. Het is over het daadwerkelijk 40% - of 60% efficiënter. Het neemt 40% van de tijd. Het kan run-- kan nemen 400 eenheden van de middelen een dataset van maat 10 te verwerken. Overwegende dat de eerste algoritme daarentegen neemt 1.000 eenheden van de middelen een dataset van maat 10 te verwerken. Maar kijk eens wat er gebeurt als onze nummers krijgen nog groter. 

Nu het verschil tussen deze algoritmen beginnen iets minder duidelijk worden. En het feit dat er lagere orde terms-- of liever, termen met lagere exponents-- beginnen te irrelevant geworden. Als een dataset is van de grootte 1000 en het eerste algoritme draait in een miljard stappen. En de tweede algoritme draait in een miljard en een miljoen stappen. En de derde algoritme loopt in gewoon verlegen van een miljard stappen. Het is vrij veel een miljard stappen. Die lagere orde termen beginnen om echt irrelevant geworden. En gewoon om echt hamer huis van de point-- Als de data ingang van een groot million-- alle drie van deze vrij veel neem een ​​quintillion-- als mijn wiskunde is correct-- stappen een data-input te verwerken van de grootte van een miljoen. Dat is veel trappen. En het feit dat een van hen zou neem een ​​paar 100.000, of een paar 100 miljoen nog minder wanneer we praten over een aantal dat big-- het is een soort van irrelevant. Ze hebben allemaal de neiging om te nemen ongeveer n blokjes, en dus zouden we eigenlijk verwijzen al deze algoritmen als de orde van n blokjes of big-O n blokjes. 

Hier is een lijst van enkele van de meer gemeenschappelijke computationele complexiteit klassen dat we tegenkomen in algoritmen, algemeen. En ook specifiek in CS50. Deze worden besteld algemeen snelste bovenaan, algemeen langzaamste onderaan. Dus constante tijd algoritmen neiging de snelste, ongeacht de grootte van de gegevensinvoer u passeren. Ze nemen altijd een operatie of een eenheid van de middelen om te gaan met. Het zou kunnen zijn 2, is het misschien 3 zijn, is het misschien 4. Maar het is een constant aantal. Het niet varieert. 

Logaritmische tijd algoritmen zijn iets beter. En een heel goed voorbeeld van een logaritmische tijd algoritme je zeker hebben gezien nu is het openscheuren van het telefoonboek Mike Smith vinden in het telefoonboek. We snijden het probleem in de helft. Dus als n groter wordt en grotere en larger-- In feite, elke keer als je het dubbele n, het duurt maar een stap. Dus dat is een stuk beter dan, zeg, lineaire tijd. Dat is als je Double N, is het neemt het dubbele van het aantal stappen. Als je verdrievoudigen n, het duurt verdrievoudigen het aantal stappen. Een stap per eenheid. 

Dan dingen een beetje more-- iets minder grote vanaf daar. Je hebt lineaire ritmische tijd, soms genaamd log lineaire tijd of gewoon n log n. En we zullen een voorbeeld een algoritme dat runs in n log n, die nog beter dan kwadratisch tijd-- n kwadraat. Of polynomiale tijd, n twee elk getal groter dan twee. Of exponentiële tijd, die zelfs worse-- C n. Dus sommige constant aantal verhoogd tot de kracht van de grootte van de ingang. Dus als er 1,000-- als de gegevensinvoer is van grootte 1000, het zou C nemen om de 1000 de macht. Het is veel erger dan polynomiale tijd. 

Faculteit tijd is nog erger. En in feite is er echt Er bestaan ​​oneindige tijd algoritmen, zoals zogenaamde dom sort-- waarvan taak is om willekeurig shuffle een array en controleer om te zien of het nu opgelost. En als het niet, willekeurig shuffle de array weer en controleren om te zien of het nu opgelost. En zoals je kunt waarschijnlijk imagine-- kunt u een situatie voor te stellen waar in het slechtste geval, dat wil nooit echt beginnen met de array. Dat algoritme zou voor altijd uit te voeren. En dus dat zou een te zijn oneindige tijd algoritme. Hopelijk zult u niet schrijven elke faculteit of oneindige tijd algoritmen in CS50. 

Dus, laten we eens een beetje meer betonnen kijkje bij enkele eenvoudiger computationele complexiteit klassen. Dus we hebben een example-- of twee voorbeelden hier-- van constante tijd algoritmen, die altijd nemen één operatie in het slechtste geval. Dus de eerste example-- we hebben een functie riep 4 voor u, die neemt een reeks van afmetingen 1.000. Maar dan blijkbaar eigenlijk niet kijken bij het-- niet echt schelen wat is erin, van genoemde matrix. Altijd net terug van vier. Dus, dat algoritme, ondanks het feit dat het neemt 1000 elementen niet alles doen met hen. Net terug van vier. Het is altijd een enkele stap. 

In feite, voeg 2 nums-- die we eerder als goed-- hebt gezien slechts verwerkt twee getallen. Het is niet een enkele stap. Het is eigenlijk een paar stappen. Je krijgt een, krijg je b, u ze toevoegen samen, en u de output van de resultaten. Dus het is 84 stappen. Maar het is altijd constant, ongeacht a of b. Je moet een te krijgen, krijgen b, voeg ze samen output het resultaat. Dus dat is een constante tijd algoritme. 

Hier is een voorbeeld van een lineaire tijd algorithm-- een algoritme dat gets-- dat neemt één additionele stap, eventueel, als uw inbreng groeit door 1. Dus, laten we zeggen dat we op zoek naar het aantal 5 binnenkant van een array. Je zou een situatie waar hebben U vindt het vrij vroeg. Maar je kon ook een situatie waarin zou het laatste element van de array. In een array van grootte 5, indien we op zoek naar het nummer 5. Het zou 5 stappen. En in feite, stel dat er 5 niet overal in deze array. We hebben nog steeds eigenlijk moeten kijken naar elk element van de array om te bepalen of 5 is daar. 

Dus in het slechtste geval, namelijk dat het element is de laatste in de reeks of niet bestaan. We hebben nog steeds te kijken naar alle n elementen. En dus dit algoritme draait in lineaire tijd. U kan bevestigen dat door extrapoleren een beetje door te zeggen: als we een 6-element array en we waren op zoek naar het nummer 5, het zou 6 stappen. Als we een 7-element array en we op zoek naar het nummer 5. Het zou 7 stappen. Als we voegen nog een element aan onze array, duurt het nog een stap. Dat is een lineair algoritme in het slechtste geval. 

Paar korte vragen voor u. Wat is het runtime-- wat het slechtste geval runtime van dit bijzondere stukje code? Dus ik heb een 4 loop hier die loopt van j gelijk is aan 0, helemaal tot m. En wat ik hier zien, is dat de body van de lus wordt uitgevoerd in constante tijd. Dus met behulp van de terminologie die we hebben al about-- wat gepraat zou het slechtste geval looptijd van dit algoritme? Neem een ​​tweede. Het binnenste deel van de lus draait in constante tijd. En het buitenste deel van de lus gaat m keer draaien. Dus wat is het slechtste geval runtime hier? Heb je big-O van m raden? Je zou gelijk hebben. 

Wat dacht je van een ander? Deze keer hebben we een lus binnen een lus. We hebben een buitenlus die loopt van nul tot p. En we hebben een innerlijke lus die loopt van nul tot p, en de binnenkant van dat Ik zeggen dat het lichaam de lus loopt constant in de tijd. Dus wat is het worst-case runtime van dit bijzondere stukje code? Nou, nogmaals, we hebben een buitenlus dat p maal uitgevoerd. En elke tijd-- iteratie van die lus, in plaats van. We hebben een innerlijke lus die ook loopt p maal. En dan de binnenkant van dat, is er de constante tijd-- klein fragment daar. 

Dus als we een buitenste lus die rijdt p maal binnen luidt een innerlijke lus die loopt p times-- wat het slechtste geval runtime van dit stukje code? Heb je big-O p denk kwadraat? 

Ik ben Doug Lloyd. Dit is CS50.