big O notation

Angol

Főnév

big O notation (tsz. big O notations)

1. (informatika) nagy ordó jelölés

---

A Big O jelölés (ejtsd: “big ó”) egy matematikai eszköz, amellyel algoritmusok hatékonyságát írjuk le, különösen a bemenet méretének növekedésével kapcsolatban. A Big O nem az algoritmus pontos futási idejét vagy memóriahasználatát adja meg, hanem annak aszimptotikus viselkedését mutatja meg: hogyan növekszik az erőforrásigény a bemenet növekedésével.

---

🧠 Miért használjuk?

• Hogy összehasonlítsuk: melyik algoritmus skálázódik jobban nagy adatokon.
• Független a konkrét géptől, nyelvtől vagy implementációtól.
• Segít teljesítményproblémákat felismerni és optimalizálni.

---

🔢 Alapötlet

$$T(n)={\text{algoritmus futási ideje a bemenet mérete alapján}}$$

A Big O az a függvény, amely a futási idő felső határát adja meg egy konstans szorzó figyelmen kívül hagyásával, pl.:

$$T(n)=3n^{2}+5n+8\Rightarrow O(n^{2})$$

---

🧩 Gyakori Big O osztályok

Jelölés	Név	Példa működés
O(1)	Konstans idő	Lista első eleme
O(log n)	Logaritmikus idő	Bináris keresés
O(n)	Lineáris idő	Lista bejárása
O(n log n)	Lineáris-logaritmikus	Gyorsrendezés
O(n²)	Kvadratikus idő	Két ciklus egymásban
O(2ⁿ)	Exponenciális idő	Naiv rekurzió (pl. Fibonacci)
O(n!)	Faktoriális idő	Permutációk teljes bejárása

---

🛠️ Példa

def print_pairs(lst):
    for i in lst:
        for j in lst:
            print(i, j)

• Külső ciklus: O(n)
• Belső ciklus: O(n)
• → Összesen: O(n²)

---

📦 Mit jelent valójában az O(n)?

Ez azt jelenti, hogy a futási idő legfeljebb egy konstansszorosánál nő gyorsabban, mint n.

Matematikailag:

$$f(n)\in O(g(n))\iff \exists c>0,\exists n_{0},{\text{hogy }}\forall n>n_{0}:f(n)\leq c\cdot g(n)$$

---

📉 Hogyan ábrázoljuk?

Az alábbi diagram azt mutatja, hogyan nőnek a különböző komplexitásos osztályok:

f(n)
│
│            O(2ⁿ)
│         O(n²)
│      O(n log n)
│   O(n)
│ O(log n)
│ O(1)
└──────────────────▶ n

---

🧾 További jelölések

Jelölés	Jelentés
O(…)	Felső korlát (legrosszabb eset)
Ω(…)	Alsó korlát (legjobb eset)
Θ(…)	Pontos korlát (átlagos vagy tipikus eset)

---

✅ Összefoglalás

A Big O jelölés egy aszimptotikus leírás arra, hogy egy algoritmus hogyan viselkedik nagy bemeneti méretek mellett. Segít az algoritmusok teljesítményének összehasonlításában, és alapvető eszköz az algoritmuselmélet, adatstruktúrák és szoftveroptimalizálás terén.

További információk

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