Complexiteit van een algoritme

Complexiteit van een algoritme

> LeekScript-zelfstudie

Algemeen idee

Om het aantal bewerkingen te schatten dat een functie of een algoritme zal verbruiken, is het handig om een idee te hebben van de relatie tussen de grootte van de argumenten die eraan worden gegeven, of de grootte van een parameter, en het maximale aantal uitgevoerde bewerkingen . Dit wordt algoritmische complexiteit genoemd.

Laten we beginnen met een eenvoudig voorbeeld: een for-lus.

voor (var i=0; i N, we f(n) < K hebben xg(n).*

Oké, daar ga je, ik heb de grote woorden eruit. Wat houdt deze definitie eigenlijk in? Dat de functie f "niet sneller" groeit dan g naarmate n toeneemt. f kan groter zijn dan g, maar de verhouding van de twee is altijd kleiner dan een bepaald getal (de K van de definitie). Laten we dit toepassen op code: laten we als (wiskundige) functie f het maximale aantal bewerkingen nemen dat wordt uitgevoerd door een bepaald stuk code, gegeven de grootte van de invoer. We zoeken naar een eenvoudige functie g zodat f(n)=O(g(n)). Het komt ruwweg neer op het meten van het grootste aantal keren dat basisinstructies in de code worden herhaald (de kosten van deze instructies worden dus onder het tapijt geveegd: het is de K van de definitie).

Voorbeelden

Opluchting. Laten we verder gaan met voorbeelden, we zullen duidelijker zien. Laten we teruggaan naar onze for-lus van eerder:

voor (var i=0; i<n; i++){ say("Ik ben een wortel"); }

Als we f het maximale aantal bewerkingen noteren dat door dit stuk code wordt uitgevoerd, hebben we gezien dat f(n) ongeveer gelijk was aan 30 x n, plus de kleine kosten van de lus. De zeg-instructie wordt inderdaad n keer herhaald, wat een constante kost van 30 bewerkingen heeft. We kunnen dus zeggen dat f wordt gedomineerd door de functie g(n)=n. We hebben dus f(n)=O(n). We zeggen ook dat dit stuk code "in O(n)" is.

En de functie van snijpunt van arrays van grootte n? We hebben gezien dat het ruwweg n² x verbruikt (aantal push-operaties + kosten om twee elementen te vergelijken). Ervan uitgaande dat de push-kosten constant zijn (wat onjuist is, maar ik wil niet meteen in detail treden), hebben we, door K = (aantal push-bewerkingen + kosten van het vergelijken van twee elementen) in te stellen, dat de kosten van de snijfunctie wordt gedomineerd door n²: we zeggen dat de snijfunctie "in O(n²)" is.

De notatie O maakt het dus mogelijk om de groei van de kosten te meten volgens de grootte van de input: de intersectiefunctie zal kosten hebben die "met dezelfde snelheid" groeien als n² (met n de grootte van de arrays).

Interesse in Prei

Dit idee is interessant omdat we vaak vrij gemakkelijk een O(g(n)) kunnen schatten, en dus weten of een functie erg duur gaat worden als de invoer toeneemt. Het is bijvoorbeeld uti