asymptotic analysis

asymptotic analysis (tsz. asymptotic analysises)

1. (informatika) aszimptotikus analízis

Az aszimptotikus analízis egy olyan matematikai eszköz, amely az algoritmusok növekedési viselkedését vizsgálja, amikor a bemenet mérete ${\textstyle n}$ a végtelen felé tart. Célja, hogy meghatározza az algoritmus teljesítményét nagy bemeneti értékek esetén, elhanyagolva az alacsonyabb rendű tagokat és konstans szorzókat.

• Lehetővé teszi algoritmusok összehasonlítását anélkül, hogy implementálnánk őket.
• Megmondja, milyen gyorsan nő egy algoritmus erőforrásigénye (pl. idő, memória).
• Segít megtalálni a legjobb algoritmust nagyméretű bemenetek esetén.

• Felső korlát

• Azt mondja meg, hogy az algoritmus legrosszabb esetben legfeljebb milyen gyorsan nő.

• Példa: Ha egy algoritmus időigénye ${\textstyle f(n)=3n^{2}+2n+5}$, akkor

  $${\displaystyle f(n)=O(n^{2})}$$

• Alsó korlát
• Azt mondja meg, hogy legalább milyen gyorsan nő az algoritmus erőforrásigénye.

• Szigorú növekedési rend – pontos rend
• Ha ${\textstyle f(n)=\Theta (n^{2})}$, akkor ${\textstyle f(n)}$ nagyjából ${\textstyle n^{2}}$-ként nő, se gyorsabban, se lassabban.

Algoritmus típusa	Növekedés	Jelölés
Konstans idejű	1	${\textstyle O(1)}$
Logaritmikus	${\textstyle \log n}$	${\textstyle O(\log n)}$
Lineáris	${\textstyle n}$	${\textstyle O(n)}$
Lineáris-logaritmikus	${\textstyle n\log n}$	${\textstyle O(n\log n)}$
Kvadratikus	${\textstyle n^{2}}$	${\textstyle O(n^{2})}$
Exponenciális	${\textstyle 2^{n}}$	${\textstyle O(2^{n})}$
Faktoriális	${\textstyle n!}$	${\textstyle O(n!)}$

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n-1; j++) {
        if (a > a) {
            swap(a, a);
        }
    }
}

• Belső ciklus futása: ${\textstyle O(n)}$
• Külső ciklus: ${\textstyle O(n)}$
• Összesen: ${\textstyle O(n^{2})}$

• Nagy-O – ha felső korlátra vagyunk kíváncsiak (pl. legrosszabb eset)
• Omega – ha alsó korlát kell (pl. legjobb eset)
• Theta – ha pontos rend kell (pl. mindig ugyanúgy viselkedik)

• Ne az implementáció részleteit nézd – az aszimptotikus analízis az elméleti teljesítményt vizsgálja.
• Konstansok, alacsonyabb rendű tagok nem számítanak (pl. ${\textstyle 3n^{2}+100n+7=O(n^{2})}$).

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