Order of Complexity är en term som används inom datavetenskap för att mäta effektiviteten hos en algoritm eller ett program. Det hänvisar till mängden tid och resurser som krävs för att lösa ett problem eller utföra en uppgift. Inom programmering uttrycks Order of Complexity vanligtvis i termer av Stora O notation, som ger en övre gräns för tids- eller utrymmeskraven för en algoritm. I den här artikeln kommer vi att diskutera komplexitetens ordning i programmeringsspråket C och dess betydelse.
np var
Ordning av komplexitet i programmeringsspråk C:
I C-programmering beror komplexitetsordningen för en algoritm på antalet operationer som utförs av programmet. Till exempel, om vi har en array av storlek n och vi vill söka efter ett visst element i arrayen, kommer algoritmens komplexitetsordning att bero på antalet element i arrayen. Om vi utför a Linjär sökning genom arrayen kommer komplexitetens ordning att vara På) , vilket innebär att tiden det tar att söka efter elementet kommer att öka linjärt med storleken på arrayen. Om vi använder en Binär sökalgoritm istället kommer komplexitetens ordning att vara O(log n) , vilket innebär att tiden det tar att söka efter elementet kommer att öka logaritmiskt med storleken på arrayen.
På samma sätt, Order of Complexity för andra algoritmer, som t.ex Sorteringsalgoritmer , Grafalgoritmer , och Dynamiska programmeringsalgoritmer beror också på antalet operationer som programmet utför. Ordningen av komplexitet för dessa algoritmer kan uttryckas med hjälp av Stora O notation.
Låt oss ta en titt på några vanliga komplexitetsordningar och deras motsvarande algoritmer:
Detta innebär att algoritmen tar en konstant tid, oavsett indatastorlek. Till exempel tar åtkomst till ett element i en array O(1) tid, eftersom elementet kan nås direkt med hjälp av dess index.
Detta innebär att algoritmens tid ökar logaritmiskt med indatastorleken. Detta ses ofta i Dela-och-härska-algoritmer tycka om Binär sökning , som delar upp insatsen i mindre delar för att lösa problemet.
Detta innebär att algoritmens tid tar linjärt med ingångsstorleken. Exempel på sådana algoritmer är Linjär sökning och Bubblesort .
Det betyder att algoritmens tid ökar med n multiplicerat med logaritmen för n. Exempel på sådana algoritmer är Quicksort och Mergesort .
Detta innebär att algoritmens tid tar kvadratiskt med ingångsstorleken. Exempel på sådana algoritmer är Bubblesort och Insättningssortering .
Detta innebär att algoritmens tid det tar fördubblas med varje ökning av indatastorleken. Detta ses ofta i Rekursiva algoritmer som Fibonacci-serien .
fabriksmetod designmönster
Det är viktigt att veta att Order of Complexity endast ger en övre gräns för den tid som algoritmen tar. Den faktiska tiden det tar kan vara mycket mindre än denna gräns, beroende på indata och implementeringen av algoritmen.
I C-programmering kan en algoritms komplexitetsordning bestämmas genom att analysera koden och räkna antalet utförda operationer. Till exempel, om vi har en slinga som itererar genom en array av storlek n, kommer slingans tidskomplexitet att vara På) . På samma sätt, om vi har en rekursiv funktion som kallar sig k gånger, kommer tidskomplexiteten för funktionen att vara O(2^k) .
För att optimera prestandan för ett program är det viktigt att välja algoritmer med en lägre komplexitetsordning. Om vi till exempel behöver sortera en array bör vi använda en sorteringsalgoritm med en lägre komplexitetsordning, som t.ex. Quicksort eller Mergesort , hellre än Bubblesortering , som har en högre ordning av komplexitet.
Analys av komplexitetsordning:
För att analysera en algoritms komplexitetsordning måste vi bestämma hur dess körtid eller utrymmesanvändning växer när indatastorleken ökar. Den vanligaste metoden för att göra detta är att räkna antalet grundläggande operationer som utförs av algoritmen.
En grundläggande operation är en operation som tar en konstant tid att utföra, som att lägga till två nummer eller komma åt ett matriselement. Genom att räkna antalet grundläggande operationer som utförs av algoritmen som en funktion av indatastorleken kan vi bestämma dess komplexitetsordning.
Tänk till exempel på följande C-funktion som beräknar summan av de första n heltal:
C-kod:
int sum(int n) { int total = 0; for (int i = 1; i <= n; i++) { total +="i;" } return total; < pre> <p>In this function, the loop runs n times, and each iteration performs a constant amount of work (adding i to the total). Therefore, the number of basic operations performed by this algorithm is proportional to n, and its time complexity is <strong>O(n)</strong> .</p> <hr></=>