Futási idő

A Programozás Wiki wikiből

A futási idő egy program végrehajtásához szükséges idő.

Mivel ez erősen függ a futtató számítógéptől, és a használt környezettől, vagy fordítótól is, ezért sok esetben csak a futás lépéseinek számát adják meg a feldolgozandó adatok elemszámának arányában.

Egy algoritmus futási idejének jellemzéséhez gyakran a nagy ordó jelölést használjuk. Pl. a Lineáris keresés futásideje O(n) azt jelenti, hogy az algoritmus kétszer annyi adat esetén várhatóan kétszer olyan sokáig fog futni.

Bonyolultsági kategóriák[szerkesztés]

Az algoritmus futási idejét különböző kategóriákba sorolhatjuk aszerint, hogy milyen a nagy ordója:

Név Nagy ordó Megjegyzés
konstans O(1) A futás ideje nem függ a bemenet méretétől
logaritmikus O(log x) A gyakorlatban általában konstansnak vehető, a logaritmus függvény lassú növekedése miatt
lineáris O(x) Az elemek számával lineárisan növekszik a futásidő, vagyis ha az elemek száma kétszeresére növekszik, akkor a futásidő is kétszeresére nő.
log-lineáris O(x*log x) A gyakorlatban a lineárishoz áll közel, a logaritmus függvény lassú növekedése miatt
négyzetes O(x^2) Az elemek számával négyzetesen növekvő futásidő, vagyis ha az ez elemek száma kétszeresére növekszik, akkor a futásidő a négyszeresére nő.
polinomiális O(x^n), ahol n természetes szám Bár elméletileg egy kategóriába szokás őket sorolni, az n értéke a gyakorlatban nagyon fontos, hiszen a négyzetes/köbös/stb. növekedés nagyságrendileg eltérő időigénnyel bír.
exponenciális O(c^x), ahol c>1 valós szám Az ilyen algoritmus általában csak nagyon rövid bemenetre képes belátható időn belül megoldást nyújtani, hiszen nagy elemszám esetén az időigény radikálisan (nem tolerálható mértéküre) megnő.

Szélső esetek[szerkesztés]

Algoritmusok futási idejének vizsgálatakor fontos lehet a lehetséges legkisebb, valamint legnagyobb futási idő meghatározása. Az előbbit a legjobb eset idejének, az utóbbit a legrosszabb eset idejének nevezzük. A közvetlen beszúrásos rendezés például legjobb esetben lineáris idejű, legrosszabb esetben négyzetes.

Beszélünk még ezeken kívül az átlagos eset futásidejéről is, amely az algoritmushoz általában használt bemeneteken nyújtott futásidő. Az átlagos adatok meghatározása nem mindig egyszerű feladat, illetve az algoritmus felhasználási környezetétől is függhet. Egy rendezési algoritmus átlagos bemenetének például egy véletlenszerűen feltöltött tömböt szokás tekinteni.