asymptotic computational complexity

Angol

Főnév

asymptotic computational complexity (tsz. asymptotic computational complexities)

(informatika, mesterséges intelligencia) Az aszimptotikus számítási bonyolultság (angolul: asymptotic computational complexity) egy módszer az algoritmusok hatékonyságának elemzésére, amely a bemenet méretének növekedése esetén vizsgálja az algoritmus futási idejének vagy memóriaigényének növekedési ütemét.

Mi az az aszimptotikus számítási bonyolultság?

Az algoritmus futási idejét vagy erőforrásigényét a bemenet méretének ( ${\textstyle n}$ ) függvényében vizsgálja, különösen akkor, amikor ${\textstyle n}$ nagyon nagy lesz.
A cél annak meghatározása, hogy az algoritmus hogyan skálázódik növekvő adatméret esetén.
Nem a pontos futási időt méri, hanem az általános növekedési tendenciát (trendet).

Jelölések (Big O és társai)

Big O (legrosszabb eset): ${\textstyle O(f(n))}$ — maximális növekedési felső korlát.
Omega (legjobb eset): ${\textstyle \Omega (f(n))}$ — minimális növekedési alsó korlát.
Theta (pontosan): ${\textstyle \Theta (f(n))}$ — növekedési sebesség pontos leírása.

Példa

Egy algoritmus futási ideje lehet például:

${\textstyle O(n)}$ : lineárisan nő a bemenet méretével.
${\textstyle O(n^{2})}$ : kvadratikusan nő.
${\textstyle O(\log n)}$ : logaritmikusan nő.

Miért fontos?

Segít kiválasztani a hatékony algoritmust nagy adathalmazok feldolgozásához.
Megmutatja, hogy az algoritmus hogyan viselkedik extrém esetekben.
Elméleti alapot nyújt az algoritmusok összehasonlításához.

Összefoglalás

Az aszimptotikus számítási bonyolultság egy elméleti eszköz az algoritmusok hatékonyságának elemzésére, amely a futási idő vagy erőforrásigény növekedését vizsgálja a bemenet méretének növekedésével.

További információk

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