Redoslijed složenosti je izraz koji se koristi u računalnoj znanosti za mjerenje učinkovitosti algoritma ili programa. Odnosi se na količinu vremena i resursa potrebnih za rješavanje problema ili obavljanje zadatka. U programiranju se redoslijed složenosti obično izražava u terminima Veliki O notacija, koja daje gornju granicu vremenskih ili prostornih zahtjeva algoritma. U ovom ćemo članku raspravljati o redoslijedu složenosti u programskom jeziku C i njegovom značaju.
Redoslijed složenosti u programskom jeziku C:
U C programiranju, redoslijed složenosti algoritma ovisi o broju operacija koje program izvodi. Na primjer, ako imamo niz veličine n i želimo tražiti određeni element u nizu, redoslijed složenosti algoritma ovisit će o broju elemenata u nizu. Ako izvedemo a Linearno pretraživanje kroz niz, Redoslijed složenosti bit će Na) , što znači da će vrijeme potrebno za traženje elementa rasti linearno s veličinom niza. Ako koristimo a Algoritam binarnog pretraživanja umjesto toga, Redoslijed složenosti bit će O(log n) , što znači da će vrijeme potrebno za traženje elementa rasti logaritamski s veličinom niza.
Slično, Redoslijed složenosti drugih algoritama, kao što je Algoritmi sortiranja , Algoritmi grafova , i Algoritmi dinamičkog programiranja također ovisi o broju operacija koje program izvodi. Redoslijed složenosti ovih algoritama može se izraziti pomoću Veliki O notacija.
preimenuj mapu linux
Pogledajmo neke uobičajene redoslijede složenosti i njihove odgovarajuće algoritme:
To znači da je algoritmu potrebno konstantno vrijeme, bez obzira na veličinu ulaza. Na primjer, pristup elementu u nizu traje O(1) vrijeme, jer se elementu može pristupiti izravno pomoću njegovog indeksa.
To znači da vrijeme potrebno algoritmu raste logaritamski s veličinom ulaza. Ovo se obično viđa u Algoritmi zavadi i vladaj Kao Binarno pretraživanje , koji dijele ulaz na manje dijelove kako bi riješili problem.
To znači da vrijeme potrebno algoritmu raste linearno s veličinom ulaza. Primjeri takvih algoritama su Linearno pretraživanje i Bubble Sort .
To znači da se vrijeme potrebno algoritmu povećava za n pomnoženo s logaritmom od n. Primjeri takvih algoritama su Brzo sortiranje i Spajanje .
To znači da vrijeme potrebno algoritmu kvadratno raste s veličinom ulaza. Primjeri takvih algoritama su Bubble Sort i Sortiranje umetanjem .
uzorci dizajna java
To znači da se vrijeme potrebno algoritmu udvostručuje sa svakim povećanjem veličine unosa. Ovo se obično viđa u Rekurzivni algoritmi poput Fibonaccijev niz .
Važno je znati da Redoslijed složenosti daje samo gornju granicu vremena potrebnog algoritmu. Stvarno potrebno vrijeme može biti puno manje od ove granice, ovisno o ulaznim podacima i implementaciji algoritma.
U C programiranju, redoslijed složenosti algoritma može se odrediti analizom koda i brojanjem izvršenih operacija. Na primjer, ako imamo petlju koja ponavlja niz niza veličine n, vremenska složenost petlje bit će Na) . Slično, ako imamo rekurzivnu funkciju koja samu sebe poziva k puta, vremenska složenost funkcije bit će O(2^k) .
Za optimizaciju izvedbe programa, važno je odabrati algoritme nižeg reda složenosti. Na primjer, ako trebamo sortirati niz, trebali bismo koristiti algoritam sortiranja nižeg reda složenosti, kao što je Brzo sortiranje ili Spajanje , rađe nego Bubble Sort , koji ima viši red složenosti.
Analizirajući redoslijed složenosti:
Da bismo analizirali redoslijed složenosti algoritma, moramo odrediti kako njegovo vrijeme rada ili korištenje prostora raste s povećanjem veličine ulaza. Najčešća metoda za to je brojanje osnovnih operacija koje je izvršio algoritam.
java tutoriali
Osnovna operacija je operacija za koju je potrebno konstantno vrijeme da se izvrši, kao što je zbrajanje dvaju brojeva ili pristup elementu niza. Brojanjem broja osnovnih operacija koje izvodi algoritam kao funkcije veličine ulaza, možemo odrediti njegov redoslijed složenosti.
Na primjer, razmotrite sljedeću C funkciju koja izračunava zbroj prvih n cijelih brojeva:
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></=>