Sudėtingumo tvarka yra kompiuterių moksle vartojamas terminas algoritmo ar programos efektyvumui matuoti. Tai reiškia, kiek laiko ir išteklių reikia problemai išspręsti arba užduočiai atlikti. Programuojant sudėtingumo tvarka paprastai išreiškiama Didysis O žymėjimas, kuris suteikia viršutinę algoritmo laiko ar erdvės reikalavimų ribą. Šiame straipsnyje aptarsime C programavimo kalbos sudėtingumo tvarką ir jos reikšmę.
C programavimo kalbos sudėtingumo tvarka:
C programuojant algoritmo sudėtingumo tvarka priklauso nuo programos atliekamų operacijų skaičiaus. Pavyzdžiui, jei turime n dydžio masyvą ir norime masyve ieškoti tam tikro elemento, algoritmo sudėtingumo tvarka priklausys nuo elementų skaičiaus masyve. Jei atliksime a Linijinė paieška per masyvą bus sudėtingumo tvarka O(n) , o tai reiškia, kad laikas, per kurį reikia ieškoti elemento, ilgės tiesiškai didėjant masyvo dydžiui. Jei naudosime a Dvejetainės paieškos algoritmas vietoj to bus sudėtingumo tvarka O(log n) , o tai reiškia, kad elemento paieškos laikas logaritmiškai didės didėjant masyvei.
Panašiai ir kitų algoritmų sudėtingumo tvarka, pvz Rūšiavimo algoritmai , Grafikų algoritmai , ir Dinaminio programavimo algoritmai taip pat priklauso nuo programos atliekamų operacijų skaičiaus. Šių algoritmų sudėtingumo tvarka gali būti išreikšta naudojant Didysis O žymėjimas.
eilučių tvarkymas c++
Pažvelkime į kai kurias įprastas sudėtingumo tvarkas ir jas atitinkančius algoritmus:
Tai reiškia, kad algoritmas trunka pastoviai, nepriklausomai nuo įvesties dydžio. Pavyzdžiui, norint pasiekti masyvo elementą, reikia O(1) laiko, nes elementą galima pasiekti tiesiogiai naudojant jo indeksą.
Tai reiškia, kad algoritmo laikas logaritmiškai didėja atsižvelgiant į įvesties dydį. Tai dažniausiai pastebima Skaldyk ir užkariauk algoritmai Kaip Dvejetainė paieška , kurios padalija įvestį į mažesnes dalis, kad išspręstų problemą.
Tai reiškia, kad algoritmo laikas didėja tiesiškai didėjant įvesties dydžiui. Tokių algoritmų pavyzdžiai yra Linijinė paieška ir Burbulų rūšiavimas .
Tai reiškia, kad algoritmo laikas padidėja n, padauginta iš n logaritmo. Tokių algoritmų pavyzdžiai yra Greitas rūšiavimas ir Mergesort .
Tai reiškia, kad algoritmo laikas didėja kvadratiškai didėjant įvesties dydžiui. Tokių algoritmų pavyzdžiai yra Burbulų rūšiavimas ir Įterpimo rūšiavimas .
Tai reiškia, kad algoritmo laikas padvigubėja kiekvieną kartą padidinus įvesties dydį. Tai dažniausiai pastebima Rekursyviniai algoritmai kaip Fibonačio serija .
foreach mašinraštis
Svarbu žinoti, kad sudėtingumo tvarka suteikia tik viršutinę algoritmo laiko ribą. Faktinis laikas gali būti daug trumpesnis už šią ribą, priklausomai nuo įvesties duomenų ir algoritmo įgyvendinimo.
C programuojant algoritmo sudėtingumo eiliškumą galima nustatyti išanalizavus kodą ir skaičiuojant atliktų operacijų skaičių. Pavyzdžiui, jei turime kilpą, kuri kartojasi per n dydžio masyvą, ciklo sudėtingumas laike bus O(n) . Panašiai, jei turime rekursinę funkciją, kuri išsikviečia save k kartų, funkcijos laiko sudėtingumas bus toks O(2^k) .
Norint optimizuoti programos veikimą, svarbu pasirinkti mažesnio sudėtingumo algoritmus. Pavyzdžiui, jei mums reikia rūšiuoti masyvą, turėtume naudoti mažesnio sudėtingumo rūšiavimo algoritmą, pvz. Greitas rūšiavimas arba Mergesort , geriau nei Burbulų rūšiavimas , kurios sudėtingumo laipsnis yra didesnis.
Sudėtingumo analizės tvarka:
Norėdami analizuoti algoritmo sudėtingumo tvarką, turime nustatyti, kaip didėja jo veikimo laikas arba erdvės naudojimas didėjant įvesties dydžiui. Dažniausias būdas tai padaryti yra suskaičiuoti pagrindinių algoritmo operacijų skaičių.
Pagrindinė operacija – tai operacija, kuriai atlikti reikia pastovaus laiko, pavyzdžiui, pridėti du skaičius arba pasiekti masyvo elementą. Skaičiuodami algoritmo atliekamų pagrindinių operacijų skaičių kaip įvesties dydžio funkciją, galime nustatyti jo sudėtingumo tvarką.
Pavyzdžiui, apsvarstykite šią funkciją C, kuri apskaičiuoja pirmųjų n sveikųjų skaičių sumą:
C kodas:
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></=>