Order of Complexity is een term die in de computerwetenschappen wordt gebruikt om de efficiëntie van een algoritme of een programma te meten. Het verwijst naar de hoeveelheid tijd en middelen die nodig zijn om een probleem op te lossen of een taak uit te voeren. Bij het programmeren wordt de Orde van Complexiteit meestal uitgedrukt in termen van Grote O notatie, die een bovengrens geeft aan de tijd- of ruimtevereisten van een algoritme. In dit artikel bespreken we de Orde van Complexiteit in de programmeertaal C en de betekenis ervan.
Volgorde van complexiteit in C-programmeertaal:
Bij C-programmeren hangt de volgorde van complexiteit van een algoritme af van het aantal bewerkingen dat door het programma wordt uitgevoerd. Als we bijvoorbeeld een array met grootte n hebben en we naar een bepaald element in de array willen zoeken, zal de volgorde van complexiteit van het algoritme afhangen van het aantal elementen in de array. Als we een Lineair zoeken door de array zal de Orde van Complexiteit zijn Op) , wat betekent dat de tijd die nodig is om naar het element te zoeken lineair toeneemt met de grootte van de array. Als we gebruik maken van een Binair zoekalgoritme in plaats daarvan zal de Orde van Complexiteit dat zijn O(logboek n) , wat betekent dat de tijd die nodig is om naar het element te zoeken, logaritmisch zal toenemen met de grootte van de array.
Op dezelfde manier is de volgorde van complexiteit van andere algoritmen, zoals Sorteeralgoritmen , Grafiekalgoritmen , En Dynamische programmeeralgoritmen hangt ook af van het aantal bewerkingen dat het programma uitvoert. De volgorde van complexiteit van deze algoritmen kan worden uitgedrukt met behulp van Grote O notatie.
Laten we eens kijken naar enkele veel voorkomende complexiteitsorden en de bijbehorende algoritmen:
Dit betekent dat het algoritme een constante hoeveelheid tijd in beslag neemt, ongeacht de invoergrootte. Het benaderen van een element in een array duurt bijvoorbeeld O(1) tijd, omdat het element rechtstreeks toegankelijk is via de index.
stapelen in Java
Dit betekent dat de tijd die het algoritme nodig heeft logaritmisch toeneemt met de invoergrootte. Dit wordt vaak gezien bij Verdeel-en-heers-algoritmen leuk vinden Binaire zoekopdracht , die de invoer in kleinere delen verdelen om het probleem op te lossen.
Dit betekent dat de tijd die het algoritme nodig heeft lineair toeneemt met de invoergrootte. Voorbeelden van dergelijke algoritmen zijn Lineair zoeken En Bellen sorteren .
Dit betekent dat de tijd die het algoritme nodig heeft toeneemt met n vermenigvuldigd met de logaritme van n. Voorbeelden van dergelijke algoritmen zijn Snel sorteren En Samenvoegen .
Dit betekent dat de tijd die het algoritme nodig heeft kwadratisch toeneemt met de invoergrootte. Voorbeelden van dergelijke algoritmen zijn Bellen sorteren En Invoegsortering .
Dit betekent dat de tijd die het algoritme nodig heeft, verdubbelt bij elke toename van de invoergrootte. Dit wordt vaak gezien bij Recursieve algoritmen zoals de Fibonacci-reeks .
bash elif
Het is belangrijk om te weten dat de Order of Complexity slechts een bovengrens geeft voor de tijd die het algoritme nodig heeft. De werkelijke tijd die nodig is, kan veel korter zijn dan deze grens, afhankelijk van de invoergegevens en de implementatie van het algoritme.
Bij C-programmeren kan de volgorde van complexiteit van een algoritme worden bepaald door de code te analyseren en het aantal uitgevoerde bewerkingen te tellen. Als we bijvoorbeeld een lus hebben die door een array met grootte n itereert, zal de tijdscomplexiteit van de lus zijn Op) . Op dezelfde manier, als we een recursieve functie hebben die zichzelf k keer noemt, zal de tijdscomplexiteit van de functie gelijk zijn O(2^k) .
Om de prestaties van een programma te optimaliseren, is het belangrijk om algoritmen te kiezen met een lagere orde van complexiteit. Als we bijvoorbeeld een array moeten sorteren, moeten we een sorteeralgoritme gebruiken met een lagere complexiteitsgraad, zoals Snel sorteren of Samenvoegen , liever dan Bellen sorteren , die een hogere orde van complexiteit heeft.
Volgorde van complexiteit analyseren:
Om de volgorde van complexiteit van een algoritme te analyseren, moeten we bepalen hoe de looptijd of het ruimtegebruik ervan toeneemt naarmate de invoergrootte toeneemt. De meest gebruikelijke methode om dit te doen is het tellen van het aantal basisbewerkingen dat door het algoritme wordt uitgevoerd.
Een basisbewerking is een bewerking die een constante hoeveelheid tijd in beslag neemt, zoals het optellen van twee getallen of het benaderen van een array-element. Door het aantal basisbewerkingen dat door het algoritme wordt uitgevoerd te tellen als een functie van de invoergrootte, kunnen we de volgorde van complexiteit bepalen.
Beschouw bijvoorbeeld de volgende C-functie die de som van de eerste n gehele getallen berekent:
C-code:
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></=>