computational complexity

computational complexity (tsz. computational complexities)

1. (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.

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:

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

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})}$

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)

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

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

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

• 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)