Tema ocenka_slozhnosti_algoritmov ereklye 590
Számítástechnika, számítási komplexitás elmélet egyik ága a elméleti számítás, tanulmányozza a munka költségeinek megoldásához szükséges számítási problémákat. Az ára mérése általában elvont fogalmak térben és időben, az úgynevezett számítási erőforrások. Idő száma határozza meg a triviális szükséges lépéseket a probléma megoldására, míg a tér meghatározott memória mérete és elhelyezkedése adathordozón. Így ezen a területen megpróbálunk választ adni a központi kérdés a fejlesztési algoritmusok, „hogyan kell változtatni az idő a végrehajtás és a memória mennyisége, attól függően, hogy a bemeneti 1 méret) és kimenet 2)?”.
Különösen, az elmélet a számítási komplexitás határozza NP-teljes problémák, amelyek nem-determinisztikus Turing-gép polinomiális időben megoldható, mivel a determinisztikus Turing-gép egy polinomiális algoritmus nem ismert.
Számú elemi műveletek töltött egy algoritmust megoldására adott esetben a probléma nem csak attól függ, mekkora a bemeneti adatokat, hanem az adatokból. Például száma rendezési műveletek algoritmus betétekkel lényegesen kisebb, ha a bemenő adatok már rendezve. Az ilyen problémák elkerülése, úgy az idő fogalma összetettsége a legrosszabb esetben.
Idő bonyolultsága (legrosszabb eset) - függvényében a méret a bemeneti és kimeneti adatok, amely egyenlő a maximális számú elemi műtétei algoritmus a probléma megoldására fokon megadott méretre. Sok problémát a kimeneti mérete nem haladja meg, vagy méretével arányos a bemeneti - ebben az esetben tekinthető időbonyolultsága a méret a funkció csak a bemenő adatok.
A térbeli komplexitása az algoritmus (legrosszabb eset) - függvénye a méret a bemeneti és kimeneti adatok, egyenlő a maximális memória elfogyása fordított algoritmus a probléma megoldásának példány a megadott méret. Sok problémát a kimeneti mérete nem haladja meg, vagy méretével arányos a bemeneti - ebben az esetben is figyelembe kell venni, mint a méret a térbeli komplexitás a funkció csak a bemenő adatok.
Annak ellenére, hogy az idő függvényében komplexitás bizonyos esetekben lehet pontosan meghatározni, a legtöbb esetben, meg egy pontos érték értelmetlen. A tény az, hogy egyrészt a jelenlegi értéke időbonyolultsága függ meghatározása elemi műveletek (például komplexitás lehet mérni mennyiségben aritmetikai művelet vagy a műveletek egy Turing-gép), másrészt növeli a bemenő adat mérete hozzájárulás állandó tényező és szempontjából alsóbb megjelenő kifejezés pontos futási idő lesz elhanyagolható.
Aszimptotikus komplexitás - tekintve bemeneti és értékelése nagy, hogy a növekedés az algoritmus időben. Jellemzően algoritmus aszimptotikus komplexitás hatékonyabb minden bemeneti adatot, kivéve esetleg kis mennyiségű adat.
az alábbi szimbólumokat használjuk, hogy írjon az aszimptotikus algoritmusok bonyolultsága:
Ha a program által létrehozott fogják felhasználni csak néhány alkalommal, akkor a költség az írás és a hibakeresés programok fog dominálni a teljes költségét a program. Ebben az esetben meg kell választani egy algoritmust, amely a legkönnyebben megvalósítani.
Ha a program csak akkor működik a „kis” input adatok, a mértéke a növekedés a végrehajtási idő lesz kisebb értékű, mint az állandó jelen a képlet futás közben. Azonban a „kicsiség” a bemeneti adat függ a pontos végrehajtási idő versengő algoritmusok. Vannak algoritmusok, mint például integer szorzás algoritmus, amely aszimptotikusan leghatékonyabb, de ez soha nem használják a gyakorlatban még a nagy feladatok, mint az arányossági jelentősen felülmúlja a többi hasonló állandók, egyszerűbb és kevésbé „hatékony” algoritmusok.
Hatékony, de bonyolult algoritmusok nemkívánatos lehet, ha a program lesz kész támogatni a személy, aki nem vesz részt az írásban ezeket a programokat.
Számos példa van a hatékony algoritmusok ilyen nagy mennyiségű számítógép memóriájában (anélkül, hogy a lehetőségét, hogy a lassabb külső adathordozók), hogy ez a tényező cáfolja az az előnye a „hatékonyság” az algoritmus.
A numerikus algoritmusok pontosságát és stabilitását az algoritmus nem kevésbé fontos, mint az idejüket hatékonyan.
P osztály tartalmazza mindazokat a problémákat, amelyek megoldása „gyorsnak”, azaz polinomiális a bemenet méretének. Ez magában foglalja a válogatás, keresés a különböző, a megállapítás kapcsolat grafikonok, és még sokan mások.
Az osztály NP tartalmazza a problémákat, hogy a nem-determinisztikus Turing-gép képes megoldani polinomiális idő alatt. Meg kell jegyezni, hogy nederminirovannaya Turing-gép csak egy elméleti, míg a modern számítógépek megfelelnek-determinisztikus Turing-gép korlátozott memória. Így, NP osztály tartalmazza osztályú P, valamint néhány problémát, hogy mely megoldások ismertek csak algoritmusok exponenciálisan függ a bemeneti mérete (azaz, nem hatékony nagy bemenetek). Az NP osztályba tartozó számos jól ismert problémák, mint egy utazó ügynök probléma, logikai SAT problémát, stb faktorizáció.
ha az input tömb mérete nőtt 2-szer az iterációk algoritmusának annak kezelése növeli 4-szer, ez - a másodfokú függését.
Tudod kap ez a funkció és a kísérleti - csak meg kell mérni az időt az algoritmus különböző mennyiségű input adatok és felhívni a grafikon.
Lehet, hogy az algoritmus időigényesebb, hogy hatékonyabb, kisebb mennyiségű adat, hiszen az együtthatók számítása általában elhagyjuk, és úgy vélik, marginális értékelték. Például az algoritmus nyilvánvalóan hatékonyabb kisebb mennyiségben. Ezért érdekes lehet mérni a tényleges teljesítmény, és kap egy grafikont a kísérletileg.
1) Az adatok hossza a leírást a probléma a bitek
2) a hossza a leírás a probléma megoldása