Komplexiteten hos en algoritm

> LeekScript handledning

Allmän uppfattning

För att uppskatta mängden operationer som en funktion eller en algoritm kommer att konsumera, är det användbart att ha en uppfattning om förhållandet mellan storleken på argumenten som ges till den, eller storleken på en parameter, och det maximala antalet operationer som utförs . Detta kallas algoritmisk komplexitet.

Låt oss börja med ett enkelt exempel: a for loop.

för (var i=0; i N har vi f(n) < K x g(n).*

Okej, varsågod, jag fick ut de stora orden. Vad betyder egentligen denna definition? Att funktionen f växer "inte snabbare" än g när n ökar. f kan vara större än g, men förhållandet mellan de två är alltid mindre än ett visst tal (definitionens K). Låt oss tillämpa detta på kod: låt oss ta som en (matematisk) funktion f det maximala antalet operationer som utförs av en given kodbit, givet storleken på dess inmatning. Vi försöker hitta en enkel funktion g så att f(n)=O(g(n)). Det motsvarar ungefär att mäta det största antalet gånger som grundläggande instruktioner kommer att upprepas i koden (kostnaden för dessa instruktioner sopas alltså under mattan: det är definitionens K).

Exempel

Puh. Låt oss gå vidare till exempel, vi kommer att se tydligare. Låt oss gå tillbaka till vår for-loop från tidigare:

för (var i=0; i<n; i++){ say("Jag är en morot"); }

Om vi noterar f det maximala antalet operationer som utförs av denna kodbit, har vi sett att f(n) var ungefär lika med 30 x n, plus den lilla kostnaden för slingan. Faktum är att säg-instruktionen upprepas n gånger, vilket har en konstant kostnad på 30 operationer. Vi kan därför säga att f domineras av funktionen g(n)=n. Således har vi f(n)=O(n). Vi säger också att denna kodbit är "in O(n)".

Och funktionen för skärningspunkten av arrayer av storlek n? Vi har sett att den ungefär förbrukar n² x (antal push-operationer + kostnad för att jämföra två element). Om vi antar att push-kostnaden är konstant (vilket är falskt, men jag vill inte gå in i detalj direkt), har vi, genom att sätta K = (antal push-operationer + kostnad för att jämföra två element ), att kostnaden för skärningsfunktionen domineras av n²: vi säger att skärningsfunktionen är "i O(n²)".

Således gör notationen O det möjligt att mäta tillväxten av kostnaden enligt storleken på inmatningen: skärningsfunktionen kommer att ha en kostnad som växer "i samma hastighet" som n² (med n storleken på arrayerna).

Intresse för Leekwars

Denna uppfattning är intressant eftersom vi ofta ganska enkelt kan uppskatta en O(g(n)), och därmed veta om en funktion kommer att börja kosta mycket dyrt när insatsen ökar. Det är till exempel uti