Vrstni red kompleksnosti je izraz, ki se v računalništvu uporablja za merjenje učinkovitosti algoritma ali programa. Nanaša se na količino časa in virov, potrebnih za rešitev problema ali izvedbo naloge. V programiranju je vrstni red kompleksnosti običajno izražen v smislu Veliki O zapis, ki daje zgornjo mejo časovnih ali prostorskih zahtev algoritma. V tem članku bomo razpravljali o vrstnem redu kompleksnosti v programskem jeziku C in njegovem pomenu.
Vrstni red kompleksnosti v programskem jeziku C:
Pri programiranju C je vrstni red kompleksnosti algoritma odvisen od števila operacij, ki jih izvaja program. Na primer, če imamo matriko velikosti n in želimo poiskati določen element v matriki, bo vrstni red kompleksnosti algoritma odvisen od števila elementov v matriki. Če izvajamo a Linearno iskanje skozi matriko bo vrstni red kompleksnosti O(n) , kar pomeni, da se bo čas iskanja elementa povečeval linearno z velikostjo matrike. Če uporabimo a Algoritem binarnega iskanja namesto tega bo vrstni red zapletenosti O(log n) , kar pomeni, da se bo čas iskanja elementa povečeval logaritemsko z velikostjo matrike.
Podobno je vrstni red kompleksnosti drugih algoritmov, kot npr Algoritmi za razvrščanje , Algoritmi grafov , in Algoritmi dinamičnega programiranja odvisno tudi od števila operacij, ki jih program izvede. Vrstni red kompleksnosti teh algoritmov je mogoče izraziti z uporabo Veliki O zapis.
gimp, kako preklicati izbiro
Oglejmo si nekaj običajnih vrst zahtevnosti in njihove ustrezne algoritme:
To pomeni, da algoritem traja konstanten čas, ne glede na velikost vnosa. Na primer, dostop do elementa v matriki traja O(1) čas, saj je do elementa mogoče dostopati neposredno z njegovim indeksom.
To pomeni, da se čas, ki ga porabi algoritem, povečuje logaritemsko z velikostjo vnosa. To se pogosto vidi v Algoritmi deli in vladaj kot Binarno iskanje , ki razdeli vhod na manjše dele za rešitev problema.
To pomeni, da čas, ki ga porabi algoritem, narašča linearno z velikostjo vnosa. Primeri takih algoritmov so Linearno iskanje in Bubble Sort .
To pomeni, da se čas, ki ga porabi algoritem, poveča za n, pomnoženo z logaritmom n. Primeri takih algoritmov so Hitro razvrščanje in Mergesort .
To pomeni, da se čas, ki ga porabi algoritem, povečuje kvadratno z velikostjo vnosa. Primeri takih algoritmov so Bubble Sort in Razvrščanje vstavljanja .
b+ drevesa
To pomeni, da se čas, ki ga porabi algoritem, podvoji z vsakim povečanjem velikosti vnosa. To se pogosto vidi v Rekurzivni algoritmi kot Fibonaccijeva serija .
Pomembno je vedeti, da vrstni red kompleksnosti zagotavlja samo zgornjo mejo časa, ki ga porabi algoritem. Dejansko porabljeni čas je lahko veliko krajši od te omejitve, odvisno od vhodnih podatkov in izvajanja algoritma.
Pri programiranju C je vrstni red kompleksnosti algoritma mogoče določiti z analizo kode in štetjem števila izvedenih operacij. Na primer, če imamo zanko, ki ponavlja matriko velikosti n, bo časovna kompleksnost zanke O(n) . Podobno, če imamo rekurzivno funkcijo, ki se kliče k-krat, bo časovna kompleksnost funkcije O(2^k) .
Za optimizacijo delovanja programa je pomembno izbrati algoritme z nižjo stopnjo kompleksnosti. Na primer, če moramo razvrstiti matriko, bi morali uporabiti algoritem za razvrščanje z nižjo stopnjo kompleksnosti, kot je npr. Hitro razvrščanje oz Mergesort , raje kot Bubble Sort , ki ima višji red kompleksnosti.
Analiziranje vrstnega reda kompleksnosti:
Za analizo vrstnega reda kompleksnosti algoritma moramo ugotoviti, kako se njegov čas delovanja ali uporaba prostora povečujeta z večanjem velikosti vnosa. Najpogostejša metoda za to je štetje števila osnovnih operacij, ki jih izvede algoritem.
java seznam v polje
Osnovna operacija je operacija, ki traja stalno količino časa, kot je seštevanje dveh števil ali dostop do elementa matrike. S štetjem števila osnovnih operacij, ki jih izvede algoritem, kot funkcijo velikosti vnosa, lahko določimo njegov vrstni red kompleksnosti.
Na primer, razmislite o naslednji funkciji C, ki izračuna vsoto prvih n celih števil:
Koda C:
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></=>