computational complexity

Angol

Főnév

computational complexity (tsz. computational complexities)

(informatika) számítási bonyolultság

Computational complexity – magyarul: számítási bonyolultság – a számítástudomány egyik központi ága, amely azzal foglalkozik, hogy milyen erőforrások (idő, memória stb.) szükségesek egy algoritmus vagy probléma megoldásához. A cél az algoritmusok hatékonyságának elemzése és a problémák nehézségi szintjének osztályozása.

🧠 1. Alapfogalom

A számítási bonyolultság azt vizsgálja:

Mennyi időt vesz igénybe egy algoritmus egy bemenet feldolgozásához?
Mennyi memóriát használ?
Hogyan skálázódik a futási idő/memória a bemenet méretének növekedésével?

Ezeket aszimptotikus jelölésekkel írjuk le:

$O(n),\quad O(n^{2}),\quad O(\log n),\quad O(2^{n}),{\text{ stb.}}$

📊 2. Erőforrás-típusok

Erőforrás	Jelentés
Időkomplexitás	Hány lépés kell a végrehajtáshoz
Térkomplexitás	Mekkora memóriaterület szükséges
Kommunikációs komplexitás	Két vagy több fél közötti adatcsere mértéke
Költség	Összesen felhasznált processzoridő, párhuzamos modellekben

🧮 3. Példa: időkomplexitás

Vegyük az alábbi algoritmusokat:

Algoritmus	Időkomplexitás
Lista bejárása	${\textstyle O(n)}$
Binaris keresés rendezett tömbön	${\textstyle O(\log n)}$
Két ciklus egymásban	${\textstyle O(n^{2})}$
Faktoriális rekurzió	${\textstyle O(n!)}$
Kombinációs brute-force keresés	${\textstyle O(2^{n})}$

🏷️ 4. Aszimptotikus jelölések

Jelölés	Jelentés
${\textstyle O(f(n))}$	Felső korlát – legrosszabb eset
${\textstyle \Omega (f(n))}$	Alsó korlát – legjobb eset
${\textstyle \Theta (f(n))}$	Pontos komplexitás (alsó és felső is)

🧩 5. Problémaosztályok

Osztály	Jelentés
P	Polinomiális időben megoldható problémák (hatékonyan)
NP	Megoldásuk polinomiális időben ellenőrizhető
NP-nehéz	Nehezebb vagy legalább olyan nehéz, mint a legnehezebb NP-probléma
NP-teljes (NP-complete)	NP osztályhoz tartozik és NP-nehéz
EXPTIME	Exponenciális időben megoldható problémák
PSPACE	Polinomiális hely (memória) alatt megoldható problémák

🧪 6. Példa NP-teljes problémákra

Utazó ügynök probléma (TSP)
3-SAT
Knapsack probléma
Hamilton-kör keresés
Színezési probléma (graph coloring)

📐 7. Mit vizsgál a bonyolultságelmélet?

Téma	Kérdés
Algoritmus elemzés	Milyen gyors/lassú az algoritmus?
Problémaosztályozás	Milyen típusú a probléma (P, NP, EXPTIME…)?
Redukciók	Egy probléma visszavezethető-e egy másikra?
Alsó korlátok	Milyen gyors megoldás lehetséges legjobb esetben?

🔒 8. A P vs NP probléma

A számítástudomány egyik legnagyobb nyitott kérdése:

Vajon minden probléma, amelynek a megoldása gyorsan ellenőrizhető (NP), gyorsan meg is oldható (P)?

Ha P = NP, az alapjaiban rengetné meg a kriptográfiát
Ha P ≠ NP, az megerősítené, hogy vannak „nehezen megoldható, de könnyen ellenőrizhető” problémák

Ez a probléma a Millennium Prize Problems egyike, 1 millió dolláros díjjal

🧾 9. Összefoglalás

Fogalom	Leírás
Számítási komplexitás	Az algoritmus erőforrásigényének vizsgálata
Idő / tér komplexitás	Futási idő és memóriaigény
Aszimptotikus jelölés	${\textstyle O(n),\Theta (n^{2})}$ stb.
P, NP, NP-teljes	Problémák osztályozása nehézség szerint
P vs NP	A modern informatika egyik legnagyobb kérdése

További információk

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