Számítási komplexitás

A számítási komplexitás egy olyan fogalom a számítástechnikában és az algoritmusok elméletében , amely valamely algoritmus által elvégzett munka mennyiségének a bemeneti adatok méretétől való függésének függvényét jelöli. A számítási komplexitást tanulmányozó ágat számítási komplexitáselméletnek nevezzük . A munka mennyiségét általában a számítási erőforrásoknak nevezett absztrakt idő- és térfogalmakban mérik . Az időt a probléma megoldásához szükséges elemi lépések száma, míg a helyet a memória vagy tárhely mennyisége határozza meg . Így ezen a területen az algoritmusfejlesztés központi kérdésére próbálnak választ adni: „hogyan fog változni a végrehajtási idő és a foglalt memória mennyisége a bemenet méretétől függően?”. Itt a bemenet mérete a probléma adatának leírásának hossza bitben (például az utazó eladó feladatban a bemenet hossza szinte arányos a városok és a közöttük lévő utak számával), és a a kimenet mérete a probléma megoldásának leírásának hossza (a legjobb útvonal az utazó eladó problémában).

A számítási komplexitás elmélete NP-teljes problémákat határoz meg , amelyeket egy nem determinisztikus Turing-gép képes megoldani polinomiális idő alatt , míg a determinisztikus Turing-gépre nem ismert polinomiális algoritmus . Általában ezek összetett optimalizálási problémák , például az utazó eladó problémája .

Az elméleti számítástechnikához szorosan kapcsolódnak olyan területek, mint az algoritmusok elemzése és a kiszámíthatóság elmélete . Az elméleti számítástechnika és az algoritmikus analízis között az a kapcsolat, hogy kialakításuk az egyes algoritmusok feladatmegoldáshoz szükséges erőforrásigényének elemzésére irányul, míg általánosabb kérdés az algoritmusok alkalmazásának lehetősége az ilyen jellegű problémákra. Hogy konkrétak legyünk, megpróbáljuk osztályozni azokat a problémákat, amelyek korlátozott erőforrásokkal megoldhatók vagy nem. A rendelkezésre álló erőforrások erős korlátja különbözteti meg a számítási komplexitás elméletét a számítási elmélettől, ez utóbbi ad választ arra a kérdésre, hogy elvileg milyen problémákat lehet algoritmikusan megoldani.

Idő és tér összetettsége

A számítási komplexitás elmélete abból adódott, hogy össze kellett hasonlítani az algoritmusok sebességét, világosan le kell írni a viselkedésüket (végrehajtási idő és a szükséges memória mennyisége) a bemenet méretétől függően.

Az algoritmus által a probléma egy adott példányának megoldására fordított elemi műveletek száma nemcsak a bemeneti adatok méretétől függ, hanem magától az adattól is. Például a beillesztési rendezési algoritmus műveleteinek száma sokkal kevesebb, ha a bemeneti adatok már rendezve vannak. Az ilyen nehézségek elkerülése érdekében a legrosszabb esetben vegye figyelembe az algoritmus időbeli összetettségének fogalmát .

Egy algoritmus időbonyolultsága (a legrosszabb esetben) a bemeneti adatok méretének függvénye, megegyezik az algoritmus által a megadott méretű problémapéldány megoldására végrehajtott elemi műveletek maximális számával.

Hasonlóan a legrosszabb esetben az időbonyolultság fogalmához , a legjobb esetben az algoritmus időbonyolultságának fogalma is definiálva van . Figyelembe veszik az algoritmus átlagos futási idejének fogalmát is , vagyis az algoritmus futási idejének matematikai elvárását . Néha egyszerűen azt mondják: " Az algoritmus időbonyolultsága " vagy " Az algoritmus futási ideje ", utalva az algoritmus időbeli összetettségére a legrosszabb, legjobb vagy átlagos esetben (kontextustól függően).

Az időbonyolultsággal analóg módon meghatározzák az algoritmus térbeli összetettségét , csak itt nem az elemi műveletek számáról, hanem a felhasznált memória mennyiségéről beszélnek.

Aszimptotikus komplexitás

Annak ellenére, hogy egy algoritmus időbonyolultsági függvénye bizonyos esetekben pontosan meghatározható, a legtöbb esetben értelmetlen annak pontos értékét keresni. A helyzet az, hogy egyrészt az időbonyolultság pontos értéke az elemi műveletek definíciójától függ (például a komplexitás az aritmetikai műveletek, bitműveletek vagy Turing-gépen végzett műveletek számában mérhető ), másodszor pedig a bemenő adatok mérete megnő, a pontos működési időre vonatkozó kifejezésben megjelenő konstans tényezők és alacsonyabb rendű tagok hozzájárulása rendkívül jelentéktelenné válik.

A nagy bemeneti adatok figyelembevétele és az algoritmus futási idejének növekedési sorrendjének becslése elvezet az algoritmus aszimptotikus komplexitásának koncepciójához . Ugyanakkor egy kisebb aszimptotikus komplexitású algoritmus minden bemeneti adatra hatékonyabb, kivéve esetleg a kis méretű adatokat. Az aszimptotikus jelölést az algoritmusok aszimptotikus összetettségének írásához használják :

Kijelölés	Intuitív magyarázat	Meghatározás
$f(n)\in O(g(n))$	$f$ felülről függvény határolja (konstans tényezőig) aszimptotikusan $g$	$\exists (C>0),n_{0}:\forall (n>n_{0})\;\|f(n)\|\leq \|Cg(n)\|$ vagy $\exists (C>0),n_{0}:\forall (n>n_{0})\;f(n)\leq Cg(n)$
$f(n)\in \Omega (g(n))$	$f$ alulról egy függvény határolja (konstans tényezőig) aszimptotikusan $g$	$\exists (C>0),n_{0}:\forall (n>n_{0})\;\|Cg(n)\|\leq \|f(n)\|$
$f(n)\in \Theta (g(n))$	$f$ alulról és felülről a függvény határolja aszimptotikusan $g$	$\exists (C,C'>0),n_{0}:\forall (n>n_{0})\;\|Cg(n)\|\leq \|f(n)\|\leq \|C' g(n)\|$
$f(n)\in o(g(n))$	$g$ aszimptotikusan dominál $f$	$\forall (C>0),\exists n_{0}:\forall (n>n_{0})\;\|f(n)\|<\|Cg(n)\|$
$f(n)\in \omega (g(n))$	$f$ aszimptotikusan dominál $g$	$\forall (C>0),\exists n_{0}:\forall (n>n_{0})\;\|Cg(n)\|<\|f(n)\|$
$f(n)\sim g(n)$	$f$ aszimptotikusan egyenértékű $g$	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1$

Példák

A „szőnyeg porszívózása” a területétől lineárisan ( ) függő időt vesz igénybe , vagyis a kétszer akkora felületű szőnyeg kétszer annyi időt vesz igénybe. Ennek megfelelően a szőnyeg területének százezerszeres növekedésével a munka mennyisége szigorúan arányosan százezerszeresére nő stb. $\Theta (A)$
"Név keresése a telefonkönyvben" csak időbe telik, logaritmikusan a bejegyzések számától ( ) függő , mert a könyvet hozzávetőlegesen középen kinyitva felére csökkentjük a "fennmaradó probléma" méretét (a nevek rendezésével). betűrendben). Így egy 1000 oldalas könyvben minden név legfeljebb egyszerre található meg (könyvnyitások). Az oldalak mennyiségének százezerre növelésekor a probléma továbbra is a látogatásokban oldódik meg. (Lásd a bináris keresést .) $O(\log _{2}(n))$ $\log _{2}1000\kb. 10$ $\log _{2}100000\kb. 17$

Jegyzetek

Mivel az aszimptotikus komplexitásbecslésben a „logaritmust” gyakran az alap említése nélkül írják le – például . $\log _{a}b={\frac {\log _{c}b}{\log _{c}a))$ $O(n\log n)$

Hangsúlyozni kell, hogy az algoritmusok és programok értékelésénél nem a legrosszabb végrehajtási idő növekedési üteme az egyetlen vagy a legfontosabb kritérium. Íme néhány megfontolás, amelyek lehetővé teszik, hogy a futásidejű kritériumot más nézőpontokból is megvizsgálja:

Ha a készülő programot csak néhány alkalommal használjuk, akkor a program teljes költségén a program megírásának és hibakeresésének költsége dominál, vagyis a tényleges végrehajtási időnek nincs jelentős hatása a teljes költségre. Ebben az esetben a legegyszerűbben megvalósítható algoritmust kell előnyben részesíteni.

Ha a program csak "kis" bemeneti adatokkal fog működni, akkor a futási idő növekedési üteme kevésbé lesz fontos, mint a futási idő képletében jelen lévő állandó [1] . Ugyanakkor a bemeneti adatok „kicsinységének” fogalma a versengő algoritmusok pontos végrehajtási idejétől is függ. Vannak olyan algoritmusok, mint például az egész szám szorzási algoritmus , amelyek aszimptotikusan a leghatékonyabbak, de amelyeket soha nem használnak a gyakorlatban, még nagy problémák esetén sem, mert arányossági állandóik jelentősen felülmúlják más, egyszerűbb és kevésbé "hatékony" algoritmusokat. algoritmusok. Egy másik példa a Fibonacci kupacok , aszimptotikus hatékonyságuk ellenére gyakorlati szempontból a megvalósítás szoftveres összetettsége és a futási idő képletek nagy konstansértékei miatt kevésbé vonzóak, mint a közönséges bináris fák [1] .

Ha egy probléma megoldása egy n csúcsú gráfra az egyik algoritmussal n C nagyságrendű idő (lépések száma) , egy másikkal pedig - n+n!/C nagyságrendű, ahol C egy állandó szám , akkor a "polinomiális ideológia" szerint az első algoritmus gyakorlatilag hatékony , a második pedig nem, bár például C=10 (10 10 ) esetén a helyzet éppen az ellenkezője [2] .A. A. Zykov

Vannak esetek, amikor a hatékony algoritmusok akkora gépmemóriát igényelnek (külső adathordozó használatának lehetősége nélkül), hogy ez a tényező érvényteleníti az algoritmus "hatékonyságának" előnyeit. Így gyakran nemcsak az "idő-bonyolultság" fontos, hanem a "memória-bonyolultság" (térbeli komplexitás) is.

A numerikus algoritmusokban az algoritmusok pontossága és stabilitása nem kevésbé fontos, mint az időhatékonyságuk.

Nehézségi osztályok

A komplexitási osztály olyan felismerési problémák halmaza, amelyekhez hasonló számítási komplexitású algoritmusok léteznek. Két fontos képviselője:

P osztály

A P osztály tartalmazza mindazokat a feladatokat, amelyek megoldása "gyorsnak" számít, vagyis amelyek megoldási ideje polinomiálisan függ a bemenet méretétől. Ez magában foglalja a rendezést , a tömbben való keresést, a grafikonok összekapcsolhatóságának kiderítését és még sok mást.

NP osztály

Az NP osztály olyan problémákat tartalmaz, amelyeket egy nemdeterminisztikus Turing-gép meg tud oldani a bemenet méretétől számított polinomiális lépésekben. Megoldásukat egy determinisztikus Turing-géppel polinomiális lépésszámban ellenőrizhetjük. Meg kell jegyezni, hogy a nem determinisztikus Turing-gép csak egy absztrakt modell, míg a modern számítógépek egy korlátozott memóriával rendelkező determinisztikus Turing-gépnek felelnek meg. Mivel a determinisztikus Turing -gép egy nem determinisztikus Turing-gép speciális eseteként fogható fel , az NP osztály magában foglalja a P osztályt, valamint néhány olyan problémát, amelyeknél csak a bemeneti mérettől exponenciálisan függő algoritmusok (azaz nem hatékonyak nagy gépeknél) bemenetek) megoldása ismert. Az NP osztály számos híres problémát tartalmaz, például az utazó eladó problémáját , a Boole-képletek kielégíthetőségi problémáját , a faktorizációt stb.

A P és NP osztályok egyenlőségének problémája

E két osztály egyenlőségének kérdése az egyik legnehezebb nyitott probléma az elméleti számítástechnika területén. A Clay Mathematical Institute felvette ezt a problémát a millenniumi problémák listájára , és egymillió dollár jutalmat kínál a megoldásáért.

Lásd még

Jegyzetek

↑ 1 2 Cormen, Thomas H.; Leizerson, Charles I.; Rivest, Ronald L.; Stein, Clifford. Algoritmusok: Konstrukció és elemzés, 2. kiadás = Bevezetés az algoritmusokba, második kiadás. - M . : "Williams" , 2005. - ISBN 5-8459-0857-4 .
↑ A. A. Zykov. A gráfelmélet alapjai. - 3. kiadás - M . : Vuzovskaya kniga, 2004. - S. 10. - 664 p. — ISBN 5-9502-0057-8 .

Linkek

Girsh EA " Számítási komplexitás és a kriptográfia alapjai " . A számítási komplexitás és a kriptográfia alapjait ismertető előadások tanfolyama.
Jurij Lifshits " Az elméleti informatika modern problémái " . Előadások NP-nehéz problémák algoritmusairól.
A. A. Razborov . Elméleti számítástechnika: egy matematikus nézete // Computerra . - 2001. - 2. sz . (downlink)(alternatív link)
A. A. RAZBOROV A számítások bonyolultságáról // Matematikai oktatás . - MTSNMO , 1999. - 3. sz . - S. 127-141 .

Szótárak és enciklopédiák	Nagy orosz

Algoritmusok összetettségi osztályai
Fénynek tekinthető	DLOGTIME AC 0 ACC 0 TC0 [ hu L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP EQP APX
Állítólag nehéz	U.P. NP NP kész co-NP társNP-teljes AM M.A. QMA PH ⊕P PP #P #P- IP_ PSPACE PSPACE-teljes
Nehéznek tartott	LEJÁRATI IDŐ NEXPTIME KIFEJEZÉS 2-EXPTIME ELEMENTARY R PR RE töltse ki újra Co-RE Co-RE-complete ÖSSZES