Order of Complexity er et begreb, der bruges i datalogi til at måle effektiviteten af en algoritme eller et program. Det refererer til mængden af tid og ressourcer, der kræves for at løse et problem eller udføre en opgave. I programmering udtrykkes kompleksitetens orden normalt i form af Store O notation, som giver en øvre grænse for tids- eller pladsbehovet for en algoritme. I denne artikel vil vi diskutere kompleksitetens orden i programmeringssproget C og dens betydning.
Rækkefølgen af kompleksitet i C-programmeringssprog:
I C-programmering afhænger rækkefølgen af kompleksitet af en algoritme af antallet af operationer, der udføres af programmet. For eksempel, hvis vi har et array af størrelse n, og vi ønsker at søge efter et bestemt element i arrayet, vil rækkefølgen af kompleksitet af algoritmen afhænge af antallet af elementer i arrayet. Hvis vi udfører en Lineær søgning gennem arrayet vil kompleksitetens orden være På) , hvilket betyder, at den tid, det tager at søge efter elementet, vil stige lineært med størrelsen af arrayet. Hvis vi bruger en Binær søgealgoritme i stedet bliver kompleksitetens orden O(log n) , hvilket betyder, at den tid, det tager at søge efter elementet, vil stige logaritmisk med størrelsen af arrayet.
Tilsvarende er rækkefølgen af kompleksitet af andre algoritmer, som f.eks Sorteringsalgoritmer , Grafiske algoritmer , og Dynamiske programmeringsalgoritmer afhænger også af antallet af operationer programmet udfører. Rækkefølgen af kompleksitet af disse algoritmer kan udtrykkes ved hjælp af Store O notation.
Lad os tage et kig på nogle almindelige rækkefølger af kompleksitet og deres tilsvarende algoritmer:
Det betyder, at algoritmen tager konstant tid, uanset inputstørrelsen. For eksempel tager det at få adgang til et element i et array O(1) tid, da elementet kan tilgås direkte ved hjælp af dets indeks.
Det betyder, at algoritmens tidsforbrug stiger logaritmisk med inputstørrelsen. Dette ses almindeligvis i Del-og-hersk-algoritmer synes godt om Binær søgning , som deler inputtet op i mindre dele for at løse problemet.
Det betyder, at algoritmens tidsforbrug stiger lineært med inputstørrelsen. Eksempler på sådanne algoritmer er Lineær søgning og Boble sortering .
Det betyder, at algoritmens tidsforbrug øges med n ganget med logaritmen af n. Eksempler på sådanne algoritmer er Quicksort og Mergesort .
Det betyder, at algoritmens tidsforbrug stiger kvadratisk med inputstørrelsen. Eksempler på sådanne algoritmer er Boble sortering og Indsættelsessortering .
Det betyder, at algoritmens tidsforbrug fordobles med hver stigning i inputstørrelsen. Dette ses almindeligvis i Rekursive algoritmer ligesom Fibonacci-serien .
Det er vigtigt at vide, at kompleksitetsordenen kun giver en øvre grænse for den tid, algoritmen tager. Den faktiske tid, det tager, kan være meget mindre end denne grænse, afhængigt af inputdata og implementeringen af algoritmen.
I C-programmering kan rækkefølgen af kompleksitet af en algoritme bestemmes ved at analysere koden og tælle antallet af udførte operationer. For eksempel, hvis vi har en sløjfe, der itererer gennem en matrix af størrelse n, vil tidskompleksiteten af sløjfen være På) . På samme måde, hvis vi har en rekursiv funktion, der kalder sig selv k gange, vil tidskompleksiteten af funktionen være O(2^k) .
For at optimere et programs ydeevne er det vigtigt at vælge algoritmer med en lavere kompleksitetsorden. Hvis vi for eksempel skal sortere et array, skal vi bruge en sorteringsalgoritme med en lavere kompleksitetsorden, som f.eks. Quicksort eller Mergesort , hellere end Boble sortering , som har en højere grad af kompleksitet.
Analyse af kompleksitetsrækkefølge:
For at analysere en algoritmes kompleksitetsorden skal vi bestemme, hvordan dens køretid eller pladsforbrug vokser, efterhånden som inputstørrelsen øges. Den mest almindelige metode til at gøre dette er at tælle antallet af grundlæggende operationer udført af algoritmen.
En grundlæggende handling er en handling, der tager en konstant mængde tid at udføre, såsom at tilføje to tal eller få adgang til et array-element. Ved at tælle antallet af grundlæggende operationer udført af algoritmen som funktion af inputstørrelsen, kan vi bestemme dens kompleksitetsrækkefølge.
Overvej for eksempel følgende C-funktion, der beregner summen af de første n heltal:
C-kode:
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></=>