Order of Complexity er et begrep som brukes i informatikk for å måle effektiviteten til en algoritme eller et program. Det refererer til hvor mye tid og ressurser som kreves for å løse et problem eller utføre en oppgave. I programmering uttrykkes Order of Complexity vanligvis i form av Stor O notasjon, som gir en øvre grense for tids- eller plassbehovet til en algoritme. I denne artikkelen vil vi diskutere kompleksitetens orden i programmeringsspråket C og dens betydning.
Rekkefølge av kompleksitet i C-programmeringsspråk:
I C-programmering avhenger rekkefølgen av kompleksitet til en algoritme av antall operasjoner som utføres av programmet. For eksempel, hvis vi har en matrise med størrelse n og vi ønsker å søke etter et bestemt element i matrisen, vil rekkefølgen av kompleksitet til algoritmen avhenge av antall elementer i matrisen. Hvis vi utfører en Lineært søk gjennom arrayet vil kompleksitetens orden være På) , som betyr at tiden det tar å søke etter elementet vil øke lineært med størrelsen på matrisen. Hvis vi bruker en Binær søkealgoritme i stedet vil kompleksitetens orden være O(log n) , som betyr at tiden det tar å søke etter elementet vil øke logaritmisk med størrelsen på matrisen.
Tilsvarende er rekkefølgen av kompleksitet til andre algoritmer, som f.eks Sorteringsalgoritmer , Grafalgoritmer , og Dynamiske programmeringsalgoritmer avhenger også av antall operasjoner programmet utfører. Rekkefølgen av kompleksitet til disse algoritmene kan uttrykkes ved hjelp av Stor O notasjon.
La oss ta en titt på noen vanlige rekkefølger av kompleksitet og deres tilsvarende algoritmer:
Dette betyr at algoritmen tar en konstant tid, uavhengig av inngangsstørrelsen. For eksempel tar det å få tilgang til et element i en matrise O(1) tid, siden elementet kan nås direkte ved hjelp av indeksen.
Dette betyr at algoritmens tidsbruk øker logaritmisk med inngangsstørrelsen. Dette er ofte sett i Del-og-hersk-algoritmer som Binært søk , som deler innspillet i mindre deler for å løse problemet.
Dette betyr at algoritmens tidsbruk øker lineært med inngangsstørrelsen. Eksempler på slike algoritmer er Lineært søk og Boblesortering .
Dette betyr at algoritmens tidsbruk øker med n multiplisert med logaritmen til n. Eksempler på slike algoritmer er Quicksort og Mergesort .
Dette betyr at algoritmens tidsbruk øker kvadratisk med inngangsstørrelsen. Eksempler på slike algoritmer er Boblesortering og Innsettingssortering .
Dette betyr at algoritmens tid det tar dobles med hver økning i inngangsstørrelsen. Dette er ofte sett i Rekursive algoritmer som Fibonacci-serien .
Det er viktig å vite at kompleksitetens orden bare gir en øvre grense for tiden algoritmen tar. Den faktiske tiden det tar kan være mye mindre enn denne grensen, avhengig av inndataene og implementeringen av algoritmen.
I C-programmering kan kompleksiteten til en algoritme bestemmes ved å analysere koden og telle antall utførte operasjoner. For eksempel, hvis vi har en løkke som itererer gjennom en matrise med størrelse n, vil tidskompleksiteten til løkken være På) . Tilsvarende, hvis vi har en rekursiv funksjon som kaller seg selv k ganger, vil tidskompleksiteten til funksjonen være O(2^k) .
For å optimere ytelsen til et program er det viktig å velge algoritmer med lavere kompleksitetsrekkefølge. Hvis vi for eksempel trenger å sortere en matrise, bør vi bruke en sorteringsalgoritme med lavere kompleksitetsrekkefølge, som f.eks. Quicksort eller Mergesort , heller enn Boblesortering , som har en høyere rekkefølge av kompleksitet.
Analyse av kompleksitetsrekkefølge:
For å analysere en algoritmes kompleksitetsrekkefølge, må vi finne ut hvordan dens kjøretid eller plassbruk vokser etter hvert som inngangsstørrelsen øker. Den vanligste metoden for å gjøre dette er å telle antall grunnleggende operasjoner utført av algoritmen.
En grunnleggende operasjon er en operasjon som tar en konstant mengde tid å utføre, for eksempel å legge til to tall eller få tilgang til et matriseelement. Ved å telle antall grunnleggende operasjoner utført av algoritmen som en funksjon av inngangsstørrelsen, kan vi bestemme dens kompleksitetsrekkefølge.
Tenk for eksempel på følgende C-funksjon som beregner summen av de første n heltallene:
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></=>