time complexity

time complexity (tsz. time complexities)

1. (informatika) A futásidő-komplexitás (time complexity) azt méri, hogy egy algoritmus milyen mértékben „drága” a bemenet méretének növekedésével, tipikusan azzal arányosítva, hogy a műveletek száma (vagy időigénye) hogyan skálázódik a bemeneti n elemével. A leggyakoribb jelölések a Big O, Big Θ és Big Ω, amelyek a futásidő felső-, pontos- illetve alsó becslését adják meg.

$${\displaystyle T(n)=O(f(n))}$$

ha vannak pozitív konstansok ${\textstyle c}$ és ${\textstyle n_{0}}$, hogy minden ${\textstyle n\geq n_{0}}$-ra

$${\displaystyle T(n)\,\leq \,c\cdot f(n).}$$

Ez azt jelenti, hogy nagy ${\textstyle n}$-nél a futásidő legrosszabb esetben nem nő gyorsabban, mint valamilyen egyszerűbb függvény, például ${\textstyle n}$, ${\textstyle n\log n}$, ${\textstyle n^{2}}$, ${\textstyle 2^{n}}$ stb.

$${\displaystyle T(n)=\Theta (f(n))}$$

ha egyszerre

$${\displaystyle c_{1}f(n)\,\leq \,T(n)\,\leq \,c_{2}f(n)}$$

teljesül nagy ${\textstyle n}$-re. Ilyenkor ${\textstyle f(n)}$ pontosan jellemzi a növekedést mind alsó, mind felső irányból.

$${\displaystyle T(n)=\Omega (f(n))}$$

ha van ${\textstyle c>0}$, ${\textstyle n_{0}}$, hogy

$${\displaystyle T(n)\,\geq \,c\,f(n)}$$

minden ${\textstyle n\geq n_{0}}$-ra. Ez a legjobb eset („best-case”) viselkedés alsó korlátját adja meg.

Osztály	Jelölés	Példa algoritmus
Konstans	${\textstyle O(1)}$	tömb­indexelés, változó­hozzáférés
Logaritmikus	${\textstyle O(\log n)}$	bináris keresés
Lineáris	${\textstyle O(n)}$	egyszeri végigjárás, összegzés
**Lineáris-logarit­	${\textstyle O(n\log n)}$	Quicksort (átlagosan), MergeSort
Kvadratikus	${\textstyle O(n^{2})}$	buborékrendezés, Shellsort (worst case gap-ssel)
Kúbikus	${\textstyle O(n^{3})}$	Floyd–Warshall (legrövidebb utak)
Exponenciális	${\textstyle O(2^{n})}$	brute-force részhalmaz-vizsgálat
Faktoriális	${\textstyle O(n!)}$	teljes permutációs próba

• Legrosszabb eset (worst-case): ${\textstyle T_{\max }(n)}$ a legnagyobb idő, amit a legrosszabb bemenettel okozhatunk.
• Átlagos eset (average-case): ${\textstyle T_{\mathrm {avg} }(n)}$ a bemenetek valószínűségi eloszlásán vett várható futásidő.
• Legjobb eset (best-case): ${\textstyle T_{\min }(n)}$ a leggyorsabb lehetséges végrehajtás ideje.

Egy algoritmust gyakran a legrosszabb eseti komplexitása alapján osztályozunk, mert ez garantált határ.

1. Skálázhatóság előrejelzése Mérjük, hogy 10 × nagyobb adatnál mennyi futásidő-növekedésre számíthatunk.
2. Algoritmus-összehasonlítás Ugyanarra a feladatra választhatjuk a gyorsabb aszimptotikailag kedvezőbb eljárást.
3. Erőforrás-tervezés Memória- és időigényt becsülhünk előre nagy rendszerekben.

A futásidő-komplexitás formális fogalmai (Big O, Θ, Ω) nélkülözhetetlenek az algoritmusok elemzésében és összehasonlításában. Segítségükkel nemcsak a mai inputméretekre, de a jövőbeni skálázódásra is rálátást nyerünk, és megalapozottabb döntéseket hozhatunk arról, melyik algoritmust érdemes választani.

• time complexity - Szótár.net (en-hu)
• time complexity - Sztaki (en-hu)
• time complexity - Merriam–Webster
• time complexity - Cambridge
• time complexity - WordNet
• time complexity - Яндекс (en-ru)
• time complexity - Google (en-hu)
• time complexity - Wikidata
• time complexity - Wikipédia (angol)