Sarežģītības secība ir termins, ko datorzinātnēs izmanto, lai novērtētu algoritma vai programmas efektivitāti. Tas attiecas uz laika un resursu daudzumu, kas nepieciešams problēmas risināšanai vai uzdevuma veikšanai. Programmēšanā sarežģītības secību parasti izsaka kā Lielais O apzīmējums, kas dod augšējo robežu algoritma laika vai telpas prasībām. Šajā rakstā mēs apspriedīsim sarežģītības secību C programmēšanas valodā un tās nozīmi.
C programmēšanas valodas sarežģītības secība:
C programmēšanā algoritma sarežģītības secība ir atkarīga no programmas veikto darbību skaita. Piemēram, ja mums ir masīvs ar izmēru n un mēs vēlamies masīvā meklēt noteiktu elementu, algoritma sarežģītības secība būs atkarīga no elementu skaita masīvā. Ja mēs izpildām a Lineārā meklēšana caur masīvu Sarežģītības kārtība būs O(n) , kas nozīmē, ka elementa meklēšanai nepieciešamais laiks lineāri palielināsies līdz ar masīva lielumu. Ja mēs izmantojam a Binārās meklēšanas algoritms tā vietā būs sarežģītības kārtība O(log n) , kas nozīmē, ka elementa meklēšanai nepieciešamais laiks logaritmiski palielināsies līdz ar masīva lielumu.
Tāpat arī citu algoritmu sarežģītības secība, piemēram, Šķirošanas algoritmi , Grafiku algoritmi , un Dinamiskās programmēšanas algoritmi atkarīgs arī no programmas veikto darbību skaita. Šo algoritmu sarežģītības secību var izteikt, izmantojot Lielais O apzīmējums.
izpildīt skripta čaulu
Apskatīsim dažas izplatītākās sarežģītības kārtas un tām atbilstošos algoritmus:
Tas nozīmē, ka algoritms aizņem nemainīgu laiku neatkarīgi no ievades lieluma. Piemēram, piekļuve elementam masīvā notiek O(1) laiku, jo elementam var piekļūt tieši, izmantojot tā indeksu.
Tas nozīmē, ka algoritma laiks logaritmiski palielinās līdz ar ievades lielumu. Tas parasti ir redzams Dali un valdi algoritmi patīk Binārā meklēšana , kas sadala ievadi mazākās daļās, lai atrisinātu problēmu.
Tas nozīmē, ka algoritma darbības laiks lineāri palielinās līdz ar ievades lielumu. Šādu algoritmu piemēri ir Lineārā meklēšana un Burbuļu kārtošana .
Tas nozīmē, ka algoritma laiks palielinās ar n, kas reizināts ar n logaritmu. Šādu algoritmu piemēri ir Ātrā šķirošana un Mergesort .
Tas nozīmē, ka algoritma laiks palielinās kvadrātiski līdz ar ievades lielumu. Šādu algoritmu piemēri ir Burbuļu kārtošana un Ievietošanas kārtošana .
koka karte
Tas nozīmē, ka algoritma laiks dubultojas ar katru ievades lieluma palielinājumu. Tas parasti ir redzams Rekursīvie algoritmi kā Fibonači sērija .
Ir svarīgi zināt, ka sarežģītības secība nodrošina tikai algoritma aizņemtā laika augšējo robežu. Faktiskais laiks var būt daudz mazāks par šo robežu atkarībā no ievades datiem un algoritma ieviešanas.
C programmēšanā algoritma sarežģītības secību var noteikt, analizējot kodu un saskaitot veikto darbību skaitu. Piemēram, ja mums ir cilpa, kas atkārtojas caur masīvu ar izmēru n, cilpas laika sarežģītība būs O(n) . Līdzīgi, ja mums ir rekursīva funkcija, kas sevi izsauc k reizes, funkcijas laika sarežģītība būs tāda O(2^k) .
Lai optimizētu programmas veiktspēju, ir svarīgi izvēlēties algoritmus ar zemāku sarežģītības pakāpi. Piemēram, ja mums ir jākārto masīvs, mums jāizmanto kārtošanas algoritms ar zemāku sarežģītības pakāpi, piemēram, Ātrā šķirošana vai Mergesort , nevis Burbuļu kārtošana , kam ir augstāka sarežģītības pakāpe.
Analīzes sarežģītības secība:
Lai analizētu algoritma sarežģītības secību, mums ir jānosaka, kā palielinās tā darbības laiks vai vietas lietojums, palielinoties ievades lielumam. Visizplatītākā metode, kā to izdarīt, ir algoritma veikto pamatoperāciju skaita saskaitīšana.
jframe
Pamatdarbība ir darbība, kuras izpildei nepieciešams nemainīgs laiks, piemēram, divu skaitļu pievienošana vai piekļuve masīva elementam. Saskaitot algoritma veikto pamatoperāciju skaitu atkarībā no ievades lieluma, mēs varam noteikt tā sarežģītības secību.
Piemēram, apsveriet šādu C funkciju, kas aprēķina pirmo n veselo skaitļu summu:
C kods:
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></=>