Legrosszabb eseti komplexitás

A számítástechnikában (kifejezetten a számítási komplexitás elméletében) a legrosszabb eseti komplexitás méri az erőforrásokat (pl. futási idő, memória), amire egy algoritmusnak szüksége van egy tetszőleges méretű bemenet (gyakran n-ként jelölve) esetén. Megadja az algoritmus által használt erőforrások felső korlátját. Futási időben a legrosszabb eseti időkomplexitás jelzi a leghosszabb futási időt, amit egy algoritmus teljesített bármilyen n méretű bemenet esetén, ezzel garantálja, hogy az algoritmus le fog futni a jelzett időtartamon belül. A legrosszabb eseti komplexitás növekedés rendje (pl. lineáris, logaritmikus) gyakran használt algoritmusok hatékonyságának összehasonlítására. Egy algoritmus legrosszabb eseti komplexitását érdemes összevetni az átlagos eseti komplexitásával, ami egy átlagos mértéke az algoritmus által használt erőforrásoknak egy véletlen bemenet esetén.

Definíció

Adott számítási modell és egy $\mathsf{A}$ algoritmus esetén, ami megáll minden $s$ bemenetnél , a $t_{\mathsf{A}}:\{0,1{\}}^{\star }\to \mathbb{\mathbb{N}}$ leképzést $\mathsf{A}$ időkomplexitásának hívjuk, ha minden $s$ bemeneti karakterlánc esetén $\mathsf{A}$ megáll pontosan $t_{\mathsf{A}}(s)$ lépés után. Mivel általában az időkomplexitásnak a különböző bemeneti hosszaktól való függése érdekel, a terminológiát abuzálva az időkomplexitás néha a $t_{\mathsf{A}}:\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$ leképzésre utal, a következő maximális komplexitással:

$t_{\mathsf{A}}(n):=\underset{s\in \{0,1{\}}^n}{\max }{t}_{\mathsf{A}}(s)$

ahol a bemenetek hossza $s$ vagy mérete $\le n$.

Kifejezési módok

Egy $\mathsf{A}$ algoritmus $t_{\mathsf{A}}$ komplexitása gyakran aszimptotikus O jelöléssel van megadva, ami a növekedési mértékét $t_{\mathsf{A}}=O(g(n))$ formában adja meg egy bizonyos valós értékű $g(n)$ függvénnyel és a következő jelentéssel:

• Létezik pozitív valós $M$ szám és egy természetes $n_0$ szám úgy, hogy

$|t_{\mathsf{A}}(n)|\le Mg(n)\mathrm{\forall }n\ge n_0.$

Szavakban ez a következőképp fogalmazható meg:

• „Az $\mathsf{A}$ algoritmus legrosszabb eseti komplexitása $O(g(n))$.”

vagy még rövidebben:

• „Az $\mathsf{A}$ algoritmus komplexitása $O(g(n))$.”

Példák

Vegyük például egy beszúrásos rendezés elvégzését $n$ számon egy véletlen hozzáférésű gépen. A legjobb eset az algoritmusnak az, amikor a számok már rendezettek, ami $O(n)$ lépést jelent a feladat elvégzésére. A legrosszabb bemenet az algoritmusnak az, amikor a számok fordított sorrendben vannak, ekkor $O(n^2)$ lépésre van szükség a rendezésükre; következésképpen a legrosszabb eseti időkomplexitása a beszúró rendezésnek $O(n^2)$.

Fordítás

• Ez a szócikk részben vagy egészben a Worst-case complexity című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Források

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest és Clifford Stein. Introduction to Algorithms. Második kiadás. MIT Press és McGraw-Hill, 2001.ISBN 0-262-03293-7. 2.2. fejezet: Analyzing algorithms, 25-27.
• Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.ISBN 0-521-88473-XISBN 0-521-88473-X, 32. o.