A számítási komplexitása az algoritmus
A számítási komplexitása az algoritmus, más néven időbonyolultsága egyik fő jellemzője az algoritmus, amely meghatározza a költségek gép ideje annak végrehajtását.
Számítási komplexitása az algoritmus (vagy bonyolultsága) nevezzük a lépések számát által végrehajtott algoritmus a legrosszabb esetben. Ez a funkció a méret a probléma által képviselt a bemeneti adatokat. Például, a grafikon által meghatározott listák beesési, a dimenziója a probléma van ábrázolva egy pár (n, m). A komplexitás a algoritmus függvényében határozzuk f, úgy, hogy az f (n, m) a lépések száma az algoritmus számára egy tetszőleges gráf n csúcsú és élek m.
Kevesebb lépés algoritmus érteni gépi utasítás, és ez a meghatározás lépés számítási komplexitás függ az adott rendszer és eljárás sugárzott parancsot. Mi is tovább érdekelt nem pontos komplexitása az algoritmus, amelynek kiszámítása gyakorlatilag lehetetlen, és az aszimptotikus komplexitás, amely függ a növekedés üteme lépést az algoritmus végtelen növekedés dimenziója a problémát. Sőt, számítási komplexitás definiáljuk a különböző rendszerek vagy módszerek műsorszórás parancsok különböznek egymástól p-szer, ahol p - valódi állandó, és a növekedés üteme megegyezik.
Összehasonlításképpen, a növekedési ütem a két funkciót, és használjuk a jelölést vagy. Azt mondjuk, hogy a függvény a sorrendben növekedés többé. mint a funkciót, hogy a kijelölt, és csak akkor, ha vannak olyan C = const és N> 0, hogy
Azt mondjuk, hogy a függvény a sorrendben növekedés nem kevesebb. mint a funkciót, hogy a kijelölt, és csak akkor, ha vannak olyan C = const és N> 0, hogy
Például, a funkció
azáltal, hogy a szimbólumok írhatók, hogy vagy. Általában, ha - a polinom foka k, akkor
A meghatározása a következő tulajdonságokkal rendelkezik: