Stel, je koopt een nieuwe computer, die 10 maal zo snel is als je vorige computer.
Je eerste vraag is: worden alle programma’s nu ook 10 maal zo snel uitgevoerd?
In grote lijnen zal dit wel het geval zijn.
Er zijn echter een paar situaties die voor afwijkingen kunnen zorgen. In de eerste plaats kunnen delen van die programma’s eerder afhangen van de snelheid van de omgeving, dan van de snelheid van de computer; het resultaat kan dan zijn dat je computer 10 maal zo snel op jouw invoer zit te wachten, of op gegevens van het internet. In de tweede plaats is die nieuwe computer waarschijnlijk niet in alle opzichten 10 maal zo snel; de snelheid van de processor is misschien met een factor 10 toegenomen, maar de snelheid van de harde schijf waarschijnlijk niet. Sommige programma’s hebben daar meer last van dan andere.
Een volgende vraag is, kan een programma dat je al jaren gebruikt nu in dezelfde tijd een invoer verwerken die 10 maal zo groot is? Bijvoorbeeld, als je een programma hebt om namen te sorteren, kun je dan op de nieuwe computer in dezelfde tijd 10 maal zoveel namen sorteren als op de oude computer?
In grote lijnen zal dit niet het geval zijn: sommige programma’s vragen bij een input die 10 maal zo groot is, 100 maal zoveel rekentijd; van de snelheid van je nieuwe computer blijft dan nog maar ongeveer een factor 3 (Ö10) over. Voor andere programma’s is dit effect nog veel sterker: met een computer die 10 maal zo snel is kun je dan je invoer maar met een paar elementen uitbreiden, om het antwoord in dezelfde tijd te krijgen als op je vorige computer.
Nog een ander voorbeeld: stel, je hebt een webwinkel, met veel succes. Vrijwel van de ene dag op de andere krijg je 100 maal zoveel klanten. Echter, ondanks het feit dat je ruim 100 maal zoveel rekencapaciteit hebt aangevraagd, blijkt de reactietijd van je website aanzienlijk toegenomen. Dit is een serieus probleem, dat je mogelijk klanten gaat kosten. Een kennis vraagt je of de algoritmen die je gebruikt, wel voldoende schaalbaar zijn.
De schaalbaarheid van oplossingen, onder andere algoritmen, speelt in de informatica een belangrijke rol; dit heeft er onder andere mee te maken dat er veel situaties zijn waarbij in kort tijdsbestek de schaal van het probleem kan veranderen – zoals in het genoemde geval van de webwinkel. In andere gevallen kan het vergroten van de schaal zorgen voor een kwalitatief beter antwoord – zoals bij het voorspellen van het weer. Kennis van algoritmen en hun efficiëntie en schaalbaarheid, en het ontwikkelen van algoritmen die beter efficiënter en beter schaalbaar zijn, is van groot praktisch belang, en een actief gebied van onderzoek zolang er computers bestaan. De efficiëntie en schaalbaarheid van een algoritme heet in de informatica, enigszins verwarrend, de complexiteit: dit is een maat voor de tijd ofwel de hoeveelheid rekenwerk, en soms van de hoeveelheid geheugen die nodig is voor de uitvoering van het algoritme. Het zegt niets over het gebrek aan eenvoud: een eenvoudig algoritme kan een hoge complexiteit hebben, een ingewikkeld algoritme een lage complexiteit.
De schaalbaarheid van oplossingen speelt in veel meer dagelijkse situaties een rol, in het bijzonder in de techniek. In veel gevallen is er extra vakkennis nodig bij de overgang naar een grotere schaal. Een eenvoudig voorbeeld betreft de schaalbaarheid van het bereiden van recepten: als je voor 20 mensen moet koken, in plaats van voor 4, heb je allerlei extra problemen: je moet meer pannen in de gaten houden, in grotere pannen warmen de gerechten anders op, enzovoorts. (Dit is een van de aspecten die het verschil maakt tussen een amateur-kok en een professional.)
In veel technische beroepen gaat het om het maken van grootschalige oplossingen – die veel extra eisen stellen ten opzichte van kleinschalige oplossingen. Het maken van een Erasmusbrug is niet zomaar het opschalen van een plank over een sloot. Voor het produceren van vele tonnen van een chemisch product per dag is meer nodig dan kennis van de reactie in een reageerbuis.
In het onderstaande gaan we dieper op deze problematiek in. We bekijken eerst de kosten van een proces waarbij het algoritme, de processor, en de invoer gegeven zijn. Vervolgens proberen we uitspraken over een algoritme te doen waarbij we de processor en de invoer niet kennen; anders gezegd, uitspraken die gelden voor alle uitvoeringen (processen) van dit algoritme. Tenslotte maken we een aantal opmerkingen over algoritmische problemen – geldig voor alle mogelijke algoritmen als oplossing voor deze problemen.
Wat zijn de kosten van een proces – als uitvoering van een algoritme, op een bepaalde processor, met een bepaalde input?
In het geval van het bereiden van een gerecht volgens een recept hebben we ingrediënten nodig (inputs), maar ook hulpbronnen ofwel resources. In het bijzonder hebben we een aantal verwarmingsbronnen nodig (energie), eventueel speciaal gereedschap (zoals een brander voor een knapperig korstje op de Crème Brulée), en tijd.
In het geval van berekening volgens een rekenalgoritme, uitgevoerd door een bepaalde processor, met een bepaalde input, zijn de belangrijkste hulpbronnen tijd, en de hoeveelheid kladpapier (als we een mens als processor gebruiken). In het geval van een berekening met een bepaalde input volgens een algoritme op een computer computeralgoritme, zijn de hulpbronnen de tijd en de hoeveelheid geheugen die nodig zijn.
In principe kunnen we het gebruik van deze hulpbronnen goed meten – waarbij we er wel rekening mee moeten houden dat een computer soms meerdere dingen uitvoert, die de meting van dat ene proces kunnen beïnvloeden. Soms kunnen we een programma instrumenteren om deze meting uit te voeren; dit kan bijvoorbeeld door een teller in te voeren die de uitvoering van de belangrijkste stappen van het programma telt.
In het bovenstaande geval gaan we uit van de situatie waarbij de input en de processor bekend zijn. We willen ook uitspraken kunnen doen over situaties waarin we beide niet kennen.
Als eerste beschouwen we de processor. Als we, bijvoorbeeld in het geval van de berekening door een menselijke processor, de specifieke eigenschappen van de processor, in het bijzonder de snelheid, buiten beschouwing willen laten, dan kunnen we het aantal elementaire stappen bepalen dat voor de berekening nodig is; de ene processor zal die elementaire stappen sneller uitvoeren dan een andere, maar die eigenschap hebben we dan onderscheiden van de eigenschappen van het proces – als uitvoering van een algoritme.
Als we deze benadering gebruiken, kunnen we bijvoorbeeld stellen dat voor een bepaald proces, bij een bepaalde input, 9873 elementaire stappen nodig zijn; als we de snelheid van de processor weten, in termen van elementaire stappen per seconde, dan weten we ook de tijd die nodig is dit proces.
De vereenvoudiging om alle elementaire stappen over één kam te scheren is soms te simplistisch. Beschouw als eenvoudig voorbeeld optellen en vermenigvuldigen: we kunnen een processor A hebben die 10* zo snel optelt als processor B, maar 100* zo snel vermenigvuldigt als processor B. Als we vermenigvuldigen en optellen beide als elementaire stappen gerekend hebben, kunnen we het verschil tussen A en B niet eenvoudig beschrijven.
Bovenstaande situatie doet zich bijvoorbeeld voor als een technologie zich niet in alle dimensies op eenzelfde manier ontwikkelt. Een voorbeeld hiervan is een harde schijf: de snelheid waarmee gegevens van een schijf gelezen worden is de laatste decennia veel meer toegenomen dan de snelheid waarmee een specifiek gegeven op de schijf geadresseerd wordt (dit laatste wordt bepaald door relatief grove mechanische processen, zoals de rotatie van de schijf, en het positioneren van de arm met de leeskop). Een ander voorbeeld betreft rekenen en datatransport binnen een IC: de snelheid van de transistoren is veel meer toegenomen dan de snelheid van het datatransport.
De volgende stap is dat we proberen een uitspraak te doen over het gebruik van hulpbronnen bij de uitvoering van een algoritme waarbij we de actuele input niet kennen.
Een direct gevolg hiervan is dat we niet meer kunnen meten tijdens het proces; we kunnen alleen een uitspraak doen over het gebruik van hulpbronnen op basis van de beschrijving van het algoritme – bijvoorbeeld, de tekst van het recept, of, de tekst van het computerprogramma.
Opgave. Bepaal aan de hand van de tekst van een recept hoeveel tijd je nodig hebt voor de bereiding, en hoeveel pannen en warmtebronnen. Hoe hangt dit af van het aantal personen voor wie je dit gerecht bereidt?
Beschouw als voorbeeld onderstaand programma, om de som van een rij getallen seq te bepalen:
sum = 0for i in range (0, len(seq)): sum = sum + seq [i]Op basis van de programmatekst kunnen we concluderen dat het aantal stappen evenredig is met de lengte van de invoerrij seq: a*len(seq) + b.
Een wat ingewikkelder voorbeeld is het volgende algoritme om een rij getallen te sorteren. Dit algoritme werkt als volgt: we bepalen eerst het minimale element van de rij; we verwisselen vervolgens het kopelement met dit minimale element. Vervolgens bepalen we het minimale element van de rest van de rij, en verwisselen dit met het tweede element; enzovoorts, totdat we alle elementen verwerkt hebben. Uitgedrukt in de programmeertaal Python wordt dit:
for i in range (0, len(s)): min = i # bepalen van het for j in range (i+1, len(s)): # mimimum van de rest if s[j] < s[min]: min = j # van de rij (vergelijkingsstap) s[i], s[min] = s[min], s[i] # verwisselstapDe basisstap: het bepalen van het minimum van de rest van de rij, kost voor het eerste element, (N-1) vergelijkingsstappen, als N de lengte van de rij voorstelt; voor het tweede (N-2), enzovoorts; het aantal vergelijkingsstappen is dan (N-1) + (N-2) + … (1); dit is te herleiden tot (N-1)*N/2 , ofwel (N^2-N)/2. Daarnaast is er nog sprake van N verwisselstappen. De rekentijd is dan (bij benadering) te beschrijven als a*(N^2-N) + d*N + c, ofwel
a*N^2 + b*N + c,
waarbij a, b, c, en d constanten zijn die onder andere samenhangen met de relatieve tijd nodig voor vergelijken en verwisselen.
Opgave: probeer dit algoritme uit voor het sorteren van een aantal voorwerpen, bijvoorbeeld een aantal speelkaarten.
Opmerking. We kunnen het bovenstaande algoritme nog een beetje efficiënter maken door als bovengrens van de eerste herhaling, len(s)-1 te gebruiken; immers, het laatste element, ofwel een rij ter lengte 1, is per definitie geordend. Dit resulteert in de overbodige maar onschuldige actie s[i], s[i] = s[i], s[i] . Voor de eenvoud van de presentatie hebben we bovengenoemde vorm gekozen. Ga na dat deze verandering alleen invloed heeft op het deel beschreven door de constante c.
We hebben in deze voorbeelden gezien dat het –in elk geval in deze eenvoudige gevallen- mogelijk is om de hoeveelheid rekenwerk (het gebruik van hulpbronnen) uit te drukken in de omvang van het probleem, in deze voorbeelden de lengte van de invoer. Wat is in het algemene geval een goede maat voor de omvang van het probleem?
In veel gevallen is dit in één of twee getallen uit te drukken. Traditioneel wordt de omvang van een probleem aangeduid met de letter N. Enkele voorbeelden:
Merk op dat bij het optellen van twee getallen (volgens het basisschool-algoritme) het aantal stappen niet afhangt van de waarde van de getallen, maar van het aantal cijfers; het aantal cijfers van een getal is evenredig met de logaritme van de waarde.
Hierboven hebben we een eerste voorbeeld gezien waarbij we de kosten van (de uitvoering van) een algoritme uitdrukken in de omvang van de input - zonder de input te kennen. In veel praktische gevallen is dat niet goed mogelijk, omdat het aantal stappen afhangt van de actuele waarden van de input. Een voorbeeld daarvan zien we in het bovenstaande sorteeralgoritme: zonder de invoer te kennen, weten we niet hoe vaak de operatie min=j uitgevoerd wordt.
In de praktijk gebruiken we daarom een benadering, door een schatting te maken van het maximale aantal stappen (worst case) dat we moeten doorlopen, bij de meest ongelukkige invoer.
In plaats van een schatting van het slechtste geval (worst case), kunnen we ook een schatting maken van het gemiddelde geval (average case). Dit is vaak lastig, omdat we niet weten hoe de invoerwaarden verdeeld zijn. Een manier om hier aan tegemoet te komen is door het gebruik van een zogenaamd randomized algoritme, waarbij delen van de invoer of de verwerking gebaseerd zijn op een (pseudo-) toevalsgenerator - waarvan we de verdeling zelf in de hand hebben.
In het bovenstaande voorbeeld van het sorteeralgoritme hebben we gezien dat we het aantal benodigde stappen bij een invoer ter lengte N, kunnen beschrijven als f(N)=a*N^2 + b*N + c. Hierop kunnen we nog een tweetal vereenvoudigingen toepassen:
Voor het gegeven sorteeralgoritme houden we dan over als maat voor het aantal stappen nodig bij een invoer ter lengte N: N^2.
Deze vereenvoudigingen zijn geformaliseerd in de definitie van de "grote-O" notatie, die meestal gebruikt wordt als maat voor de "complexiteit" - de rekentijd, of eigenlijk de schaalbaarheid van een algoritme. O(N) beschijft dan de verzameling functies die voor voldoend grote N, van boven begrensd wordt door g(N) = c*N. Dit beschrijft de algoritmen in de klassen "lineaire complexiteit". Preciezer geformuleerd:
O(N) = { f(n) | er bestaan positieve constanten c en n0 zodat 0<= f(n) < c*N, voor alle n >= n0 }
Met de constante n0 geven we aan dat dit het gedrag “voor voldoend grote N” betreft; met de constante c zorgen we ervoor dat alle functies van de vorm f(N)=a*N eronder vallen.
Grafisch
In het algemeen krijgen we O( g ) waarbij g een functie van N is, gewoonlijk de omvang van de het probleem, of van de input:
O( g(n) ) = { f(n) | er bestaan positieve constanten c en n0 zodat 0<= f(n) < c*g(n), voor alle n >= n0}
Onderstaand overzicht geeft een aantal veel voorkomende complexiteitsklassen:
O(log N) << O(N) << O(N log N) << O(N^2) << O(N^3) << … << O(2^N)
Enkele typische voorbeelden: