idkomplexitás

Az időkomplexitás (időbeli komplexitás) az algoritmus futási idejének növekedési ütemét írja le a bemeneti adatok méretének függvényében. Célja, hogy megértse, hogyan nő a szükséges idő asztnievekedéssel, és lehetővé tegye különböző megoldások összehasonlítását anélkül, hogy konkrét hardverre vagy implementációra támaszkodnánk. A legtöbb elemzés a bemeneti méretet n-nel jelöli.

A megfogalmazás legismertebb eszköze a Big-O jelölés. A leggyakoribb időosztályok közé tartozik az O(1) (állandó idő), O(log n) (logaritmikus), O(n) (lineáris), O(n log n), O(n^2), O(2^n) és O(n!). A Big-O a felső korlátot adja meg; a Big-Theta a pontos növekedést, a Big-Omega pedig az alsó határt jelöli. Gyakorlati elemzéskor beszélhetünk legjobb, átlagos és legrosszabb esetről.

Az időkomplexitás meghatározásához gyakran rekurzív vagy iteratív struktúrákat elemeznek. Rekurzív algoritmusoknál gyakran alkalmazzák a Master Theoremet vagy helyettesítést. Bizonyos esetekben amortizált időkomplexitás is releváns, például dinamikus adatszerkezeteknél, ahol egy sorozat műveletét egy iteráció alatt olcsósítják meg.

Fontos megkülönböztetni az időkomplexitást a memóriahasználattól (memóriakomplexitás), mert a futási idő mellett a helyfoglaltság is jelentősen befolyásolhatja a teljesítményt. A valós futási idő továbbra is függ a hardvertől, fordítótól és megvalósítástól, de az időkomplexitás irányadó becslést ad a skálázódásra és az összhatékonyságra.