nagy ordó jelölés

Magyar

Kiejtés

• IPA: [ ˈnɒɟ ˈordoː ˈjɛløleːʃ]

Főnév

nagy ordó jelölés

1. (matematika, algoritmusok)

A nagy ${\textstyle O}$-jelölés (Big-O notation) egy matematikai jelölés, amely az algoritmusok aszimptotikus idő- vagy tárhely-igényét írja le, különös tekintettel a legrosszabb esetekre. A nagy ${\textstyle O}$-jelölés nem a pontos időtartamot vagy tárhelyet adja meg, hanem az algoritmus skálázhatóságát mutatja meg a bemeneti adatok méretének növekedésével.

—

Definíció

Egy algoritmus ${\textstyle f(n)}$ futási ideje vagy tárhelyhasználata nagy ${\textstyle O}$-jelöléssel ${\textstyle O(g(n))}$, ha létezik egy ${\textstyle c>0}$ és egy ${\textstyle n_{0}}$ pozitív egész szám, amelyre: $$f(n)\leq c\cdot g(n)\quad {\text{ha}}\quad n\geq n_{0}$$ Ez azt jelenti, hogy ${\textstyle g(n)}$ felső korlátot ad ${\textstyle f(n)}$-re az ${\textstyle n}$ bemeneti méret növekedésével.

—

Fontos tulajdonságok

1. A domináns tényező számít: Csak a leggyorsabban növekvő tagot vesszük figyelembe, mert az dominálja az algoritmus viselkedését nagy bemeneti méretek esetén. Példa: ${\textstyle f(n)=3n^{2}+5n+10}$ esetén ${\textstyle O(n^{2})}$, mert az ${\textstyle n^{2}}$ dominálja az ${\textstyle n}$-t és a konstansokat.

2. Konstans szorzók elhagyhatók: Az algoritmus skálázhatósága nem változik a konstans tényezőkkel. Példa: Ha ${\textstyle f(n)=2n}$, akkor ${\textstyle O(2n)=O(n)}$.

3. Különböző bemeneti méretek: A bemeneti méret, ${\textstyle n}$, lehet például egy lista hossza, egy gráf csúcsainak száma, vagy más paraméter, amely az algoritmus futási idejét meghatározza.

—

Nagy ${\textstyle O}$ komplexitási kategóriák

1. ${\textstyle O(1)}$ – Konstans idő Az algoritmus futási ideje független a bemeneti mérettől. - Példa: Egy lista első elemének elérése.

2. ${\textstyle O(\log n)}$ – Logaritmikus idő Az algoritmus futási ideje logaritmikusan nő a bemeneti mérettel. - Példa: Bináris keresés.

3. ${\textstyle O(n)}$ – Lineáris idő Az algoritmus futási ideje arányos a bemeneti mérettel. - Példa: Egy lista összes elemének bejárása.

4. ${\textstyle O(n\log n)}$ – Lineáris-logaritmikus idő Hatékonyabb algoritmusok időkomplexitása, például rendezési algoritmusok. - Példa: MergeSort, QuickSort (átlagos eset).

5. ${\textstyle O(n^{2})}$ – Kvadratikus idő Az algoritmus futási ideje a bemeneti méret négyzetével nő. - Példa: Két lista összes párosításának vizsgálata.

6. ${\textstyle O(n^{k})}$ – Polinomiális idő Az algoritmus futási ideje a bemeneti méret ${\textstyle k}$-adik hatványával nő. - Példa: Mátrixszorzás (${\textstyle O(n^{3})}$).

7. ${\textstyle O(2^{n})}$ – Exponenciális idő Az algoritmus futási ideje exponenciálisan nő a bemeneti mérettel. - Példa: Backtracking algoritmusok (pl. a teljes kombinációk generálása).

8. ${\textstyle O(n!)}$ – Faktoriális idő A futási idő a bemeneti méret faktoriálisával nő. - Példa: Az összes permutáció generálása.

—

Gyakorlati példák

1. Példa 1: Lineáris keresés Egy lista minden elemét végignézzük. Futási idő: ${\textstyle O(n)}$.
2. Példa 2: Bináris keresés Egy rendezett listán keresünk egy elemet, és minden lépésben megfelezzük a keresési tartományt. Futási idő: ${\textstyle O(\log n)}$.
3. Példa 3: Rendezési algoritmusok - Bubble Sort: ${\textstyle O(n^{2})}$. - MergeSort: ${\textstyle O(n\log n)}$. - QuickSort (legrosszabb eset): ${\textstyle O(n^{2})}$, de átlagosan ${\textstyle O(n\log n)}$.

—

Összehasonlítás és rangsor Az alábbiakban bemutatjuk a komplexitások növekedési sorrendjét ${\textstyle n}$ függvényében:

$$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^{2})<O(2^{n})<O(n!)$$

—

Nagy ${\textstyle O}$-jelölés az algoritmus tervezésben

1. Optimalizáció célja: Az algoritmus tervezésekor a legkisebb idő- és tárhelykomplexitást keressük. 2. Aszimptotikus elemzés: Segít előre jelezni az algoritmus viselkedését nagy bemeneti méreteknél. 3. Pontosítás nélkül: A nagy ${\textstyle O}$ csak az aszimptotikus felső korlátot adja meg, nem az algoritmus konkrét futási idejét.

A nagy ${\textstyle O}$-jelölés megértése és alkalmazása alapvető fontosságú az algoritmusok hatékonyságának elemzéséhez és összehasonlításához.

Fordítások

Tartalom

angol: big O notation (en)

További információk

• nagy ordó jelölés - Értelmező szótár (MEK)
• nagy ordó jelölés - Etimológiai szótár (UMIL)
• nagy ordó jelölés - Szótár.net (hu-hu)
• nagy ordó jelölés - DeepL (hu-de)
• nagy ordó jelölés - Яндекс (hu-ru)
• nagy ordó jelölés - Google (hu-en)
• nagy ordó jelölés - Helyesírási szótár (MTA)
• nagy ordó jelölés - Wikidata
• nagy ordó jelölés - Wikipédia (magyar)