A komplexitás sorrendje egy olyan kifejezés, amelyet a számítástechnikában egy algoritmus vagy program hatékonyságának mérésére használnak. Arra utal, hogy egy probléma megoldásához vagy egy feladat elvégzéséhez mennyi időre és erőforrásra van szükség. A programozás során a komplexitás sorrendjét általában a következőkkel fejezik ki Nagy O jelölés, amely egy algoritmus idő- vagy térigényének felső korlátját adja meg. Ebben a cikkben a C programozási nyelv bonyolultsági sorrendjét és jelentőségét tárgyaljuk.
A C programozási nyelv bonyolultsági sorrendje:
A C programozásban egy algoritmus bonyolultsági sorrendje a program által végrehajtott műveletek számától függ. Például, ha van egy n méretű tömbünk, és egy adott elemet akarunk keresni a tömbben, akkor az algoritmus bonyolultsági sorrendje a tömb elemeinek számától függ. Ha végrehajtjuk a Lineáris keresés a tömbön keresztül a komplexitás sorrendje lesz Tovább) , ami azt jelenti, hogy az elem kereséséhez szükséges idő lineárisan növekszik a tömb méretével. Ha használunk a Bináris keresési algoritmus helyette a Bonyolultság Rendje lesz O(log n) , ami azt jelenti, hogy az elem kereséséhez szükséges idő logaritmikusan növekszik a tömb méretével.
Hasonlóan, a bonyolultsági sorrend más algoritmusok, mint pl Rendezési algoritmusok , Grafikonalgoritmusok , és Dinamikus programozási algoritmusok a program által végrehajtott műveletek számától is függ. Ezeknek az algoritmusoknak a bonyolultsági sorrendje a segítségével fejezhető ki Nagy O jelölés.
Vessünk egy pillantást néhány általános összetettségi sorrendre és a hozzájuk tartozó algoritmusokra:
Ez azt jelenti, hogy az algoritmus a bemenet méretétől függetlenül állandó időt vesz igénybe. Például egy tömb elemének eléréséhez szükséges O(1) időt, mivel az elem közvetlenül elérhető az indexe segítségével.
Ez azt jelenti, hogy az algoritmus ideje logaritmikusan növekszik a bemeneti mérettel. Ez általában látható a Oszd meg és uralkodj algoritmusok mint Bináris keresés , amelyek a bemenetet kisebb részekre osztják a probléma megoldása érdekében.
Ez azt jelenti, hogy az algoritmus ideje lineárisan növekszik a bemenet méretével. Példák az ilyen algoritmusokra Lineáris keresés és Buborékos rendezés .
Ez azt jelenti, hogy az algoritmus időtartama n-nel növekszik, megszorozva n logaritmusával. Példák az ilyen algoritmusokra Quicksort és Mergesort .
Ez azt jelenti, hogy az algoritmus ideje négyzetesen növekszik a bemeneti mérettel. Példák az ilyen algoritmusokra Buborékos rendezés és Beszúrás rendezése .
Ez azt jelenti, hogy az algoritmus ideje megduplázódik a bemeneti méret minden egyes növekedésével. Ez általában látható a Rekurzív algoritmusok mint a Fibonacci sorozat .
Fontos tudni, hogy a bonyolultsági sorrend csak felső korlátot ad az algoritmus által igénybe vett időnek. A tényleges idő a bemeneti adatoktól és az algoritmus megvalósításától függően ennél jóval kevesebb is lehet.
A C programozásban egy algoritmus bonyolultsági sorrendje a kód elemzésével és a végrehajtott műveletek számának megszámlálásával határozható meg. Például, ha van egy ciklusunk, amely egy n méretű tömbön iterál, akkor a ciklus időbonyolultsága Tovább) . Hasonlóképpen, ha van egy rekurzív függvényünk, amely k-szer hívja meg magát, akkor a függvény időbonyolultsága a következő lesz O(2^k) .
Egy program teljesítményének optimalizálásához fontos, hogy alacsonyabb bonyolultsági sorrendű algoritmusokat válasszunk. Például, ha rendeznünk kell egy tömböt, akkor használjunk alacsonyabb bonyolultságú rendezési algoritmust, mint pl. Quicksort vagy Mergesort , inkább mint Buborékos rendezés , amelynek összetettsége magasabb.
shloka mehta
A bonyolultsági sorrend elemzése:
Egy algoritmus bonyolultsági sorrendjének elemzéséhez meg kell határoznunk, hogyan növekszik az algoritmus futási ideje vagy helyhasználata a bemeneti méret növekedésével. Ennek legáltalánosabb módja az algoritmus által végrehajtott alapvető műveletek számának megszámlálása.
Az alapművelet olyan művelet, amelynek végrehajtása állandó időt vesz igénybe, például két szám hozzáadása vagy egy tömbelem elérése. Az algoritmus által elvégzett alapműveletek számát a bemeneti méret függvényében megszámolva meghatározhatjuk annak összetettségi sorrendjét.
Vegyük például a következő C függvényt, amely az első n egész szám összegét számítja ki:
C kód:
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></=>