Kijelölés	Intuitív magyarázat	Meghatározás
	f felülről egy függvény korlátozza g	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/101/eebfe73c29ff3f9bc886d263bd3e91f3.png" border="0"> or style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0">
	f alulról a funkció korlátozza g(állandó tényezőig) aszimptotikusan	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/48/0fda981f377ae7b8d361f58ce148c173.png" border="0">
	f felülről és alulról egy függvény határolja g aszimptotikus	0), n_0: \forall (n>n_0) \; |Cg(n)|
	g dominál f aszimptotikus	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/49/176ce786e936badb831a0bb87f25249d.png" border="0">
	f dominál g aszimptotikus	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/53/554bc3f42cfa6d0638722e58e4a99d8b.png" border="0">
	f egyenértékű g aszimptotikus

Példák

Megjegyzések

Hangsúlyozni kell, hogy nem a legrosszabb végrehajtási idő növekedési üteme az egyetlen vagy a legfontosabb kritérium az algoritmusok és programok értékeléséhez. Í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 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 fordított.

1. A hatékony, de összetett algoritmusok nem kívánatosak lehetnek, ha a kész programokat olyan személyek támogatják, akik nem vesznek részt e programok megírásában. Reméljük, hogy a hatékony algoritmusok létrehozásának technológiájának alappontjai széles körben ismertek, és a meglehetősen bonyolult algoritmusok szabadon alkalmazhatók a gyakorlatban. Előre kell azonban látni annak lehetőségét, hogy a hatékony, de "trükkös" algoritmusokra bonyolultságuk és a kitalálásuk során felmerülő nehézségek miatt nem lesz kereslet.
2. Számos példa van arra, amikor a hatékony algoritmusok ilyen nagy mennyiséget igényelnek. gépmemória(anélkül, hogy lassabb külső adathordozót használhatnánk), hogy ez a tényező tagadja az algoritmus „hatékonysági” előnyét.
3. 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 és NP osztályok egyenlőségének problémája

híres tudósok

• Leonyid Levin
• Alekszandr Razborov
• Edie Sheimir

Lásd még

Linkek

• 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: matematikus nézet // Computerra. - 2001. - 2. sz. (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.

Wikimédia Alapítvány. 2010 .

Nézze meg, mi az "algoritmus időbonyolultsága" más szótárakban:

időbonyolultság (az algoritmus)- - Témakörök információvédelem HU időbonyolítás ... Műszaki fordítói kézikönyv

AZ ÜZEMELTETŐI TEVÉKENYSÉGEK KOMPLEXITÁSA- objektív tényezők összessége, amelyek befolyásolják a személy által a HMS-ben szükséges funkciók ellátásának minőségét és időtartamát. Így. több típusra oszlik, amelyek mindegyikét bizonyos tényezők kombinációja jellemzi ... ... Pszichológiai és pedagógiai enciklopédikus szótár

Számítási függvény, amely számszerű becslést ad az algoritmus kiindulási adatokra történő alkalmazásának folyamatainak nehézségére (nehézségére). A. finomítása -val. A számítások egy jelzőfüggvény (vagy egyszerűen csak jelző) függvény fogalma, a széléhez adott ... ... Matematikai Enciklopédia

A számítástechnikában és az algoritmusok elméletében az algoritmus számítási komplexitása olyan függvény, amely meghatározza, hogy valamely algoritmus által végzett munka mennyisége mennyire függ a bemeneti adatok méretétől. A számítási komplexitást tanulmányozó részt elméletnek nevezik ... ... Wikipédiának

A számítástechnikában a számítási komplexitás elmélete a számítási elmélet egyik ága, amely egy számítási probléma megoldásához szükséges munka költségét vizsgálja. A költségeket általában az idő és a tér elvont fogalmaival mérik, amelyeket ... ... Wikipédia-nak hívnak

Ez egy algoritmus az elemek listában való rendezésére. Abban az esetben, ha egy listaelemnek több mezője van, a rendezési feltételként szolgáló mezőt rendezési kulcsnak nevezzük. A gyakorlatban egy szám gyakran kulcsként működik, más területeken pedig ... ... Wikipédia

A rendezési algoritmus egy lista elemeinek rendezésére szolgáló algoritmus. Abban az esetben, ha egy listaelemnek több mezője van, a rendezési feltételként szolgáló mezőt rendezési kulcsnak nevezzük. A gyakorlatban egy szám gyakran kulcsként működik, és a ... ... Wikipédiában

- (GM) nyilvános kulcsú kriptográfiai rendszer, amelyet Shafi Goldwasser és Silvio Micali fejlesztett ki 1982-ben. A GM az első nyilvános kulcsú valószínűségi titkosítási séma, amely bizonyíthatóan biztonságos a szabványos kriptográfiai szabványok mellett. Wikipédia Bővebben

Helló! A mai előadás kicsit más lesz, mint a többi. Abban különbözik, hogy csak közvetve kapcsolódik a Java-hoz. Ez a téma azonban nagyon fontos minden programozó számára. Majd megbeszéljük algoritmusok. Mi az algoritmus? beszél egyszerű nyelv, ez néhány műveletsor, amelyet végre kell hajtani a kívánt eredmény eléréséhez. Gyakran használunk algoritmusokat mindennapi életünkben. Például minden reggel van egy feladatod: jöjjön el iskolába vagy munkába, és ugyanakkor legyen:

• Öltözött
• tiszta
• teljes

Melyik algoritmus lehetővé teszi, hogy elérje ezt az eredményt?

1. Ébresztővel ébredj fel.
2. Zuhanyozz le, mosakodj meg.
3. Reggeli elkészítése, kávé/teafőzés.
4. Eszik.
5. Ha este óta nem vasalta a ruháit, vasalja ki.
6. Öltözz fel.
7. Hagyja el a házat.

Ez a műveletsor biztosan lehetővé teszi a kívánt eredmény elérését. A programozásban munkánk lényege a problémák folyamatos megoldásában rejlik. Ezen feladatok jelentős része már ismert algoritmusokkal is elvégezhető. Például a következő feladattal kell szembenéznie: rendezzen egy 100 nevet tartalmazó listát egy tömbben. A feladat meglehetősen egyszerű, de megoldható különböző utak. Íme egy lehetséges megoldás: A nevek ábécé szerinti rendezésének algoritmusa:

1. Vásárolja meg vagy töltse le az interneten az "Orosz személynevek szótárát" 1966-os kiadás.
2. Keresse meg a listánk összes nevét ebben a szótárban.
3. Írd fel egy papírra, hogy a szótár melyik oldalán található a név.
4. Tedd sorba a neveket egy papírlapra jegyzetekkel!

Megoldja-e a problémánkat egy ilyen műveletsor? Igen, megengedi. Vajon ez a döntés hatékony? Alig. Itt elérkeztünk egy másik nagyon fontos tulajdon algoritmusok – azok hatékonyság. A problémát többféleképpen is megoldhatja. De mind a programozásban, mind a mindennapi életben azt a módszert választjuk, amelyik a leghatékonyabb lesz. Ha az a feladata, hogy vajas szendvicset készítsen, minden bizonnyal kezdheti a búza ültetésével és a tehenfejéssel. De lesz hatástalan megoldás - ez nagyon hosszú ideig tart, és sok pénzbe fog kerülni. Az egyszerű probléma megoldásához egyszerűen vásárolhat kenyeret és vajat. És a búzával és a tehénnel végzett algoritmus, bár lehetővé teszi a probléma megoldását, túl bonyolult ahhoz, hogy a gyakorlatban alkalmazzák. A programozási algoritmusok bonyolultságának felmérésére egy speciális jelölést hoztak létre, az úgynevezett Big-O ("nagy O"). A Big-O lehetővé teszi annak becslését, hogy egy algoritmus végrehajtási ideje mennyire függ a neki továbbított adatoktól. Nézzük a legegyszerűbb példát - az adatátvitelt. Képzelje el, hogy bizonyos információkat fájlként kell átvinnie nagy távolságra (például 5000 kilométerre). Melyik algoritmus lesz a leghatékonyabb? Attól függ, hogy milyen adatokkal kell dolgoznia. Például van egy 10 megabájtos hangfájlunk.
Ebben az esetben a leghatékonyabb algoritmus a fájl interneten keresztüli átvitele lenne. Ez legfeljebb pár percet vesz igénybe! Tehát ismét hangot adunk az algoritmusunknak: "Ha 5000 kilométeres távolságra szeretne információkat fájl formájában továbbítani, akkor az interneten keresztüli adatátvitelt kell használnia." Nagy. Most pedig elemezzük. Megoldja a problémánkat?Általánosságban elmondható, hogy igen. De mi a helyzet a bonyolultságával? Hmm, itt kezdenek érdekesek lenni a dolgok. Az a tény, hogy az algoritmusunk nagyon függ a bejövő adatoktól, nevezetesen a fájlok méretétől. Most 10 megabájtunk van, és minden rendben van. Mi van, ha 500 megabájtot kell átvinnünk? 20 gigabájt? 500 terabájt? 30 petabájt? Leáll az algoritmusunk működése? Nem, ezek az adatmennyiségek továbbra is átvihetők. Tovább fog futni? Igen fog! Most ismerjük algoritmusunk egy fontos jellemzőjét: minél nagyobb az átvinni kívánt adatok mérete, annál tovább tart az algoritmus befejezése. De szeretnénk pontosabban megérteni, hogyan is néz ki ez a függőség (az adatok mérete és átviteli ideje között). Esetünkben az algoritmus bonyolultsága lesz lineáris. A „lineáris” azt jelenti, hogy az adatok mennyiségének növekedésével az átvitelük ideje hozzávetőleg arányosan növekszik. Ha az adatok kétszeresére nőnek, és 2-szer több időt vesz igénybe az átvitelük. Ha az adat 10-szeresére nő, az átviteli idő 10-szeresére nő. A Big-O jelölés használatával algoritmusunk összetettségét a következőképpen határozzuk meg TOVÁBB). Ez a jelölés a legjobban megjegyezhető a jövőre nézve – mindig a lineáris összetettségű algoritmusoknál használják. Figyelem: itt egyáltalán nem beszélünk különféle „változó” dolgokról: az internet sebességéről, számítógépünk teljesítményéről stb. Egy algoritmus összetettségének értékelése során egyszerűen nincs értelme – úgysem tudjuk irányítani. A Big-O magát az algoritmust értékeli, függetlenül a „ környezet” amelyben dolgoznia kell majd. Folytassuk példánkkal. Tegyük fel, hogy a végén kiderült, hogy az átvinni kívánt fájlok mérete 800 terabájt. Ha ezeket az interneten keresztül továbbítjuk, a probléma természetesen megoldódik. Csak egy probléma van: nagyjából 708 napba telne egy szabványos modern linken (100 megabit/másodperc sebességgel), amelyet legtöbben otthon használunk. Majdnem 2 éve! :O Tehát az algoritmusunk itt nyilvánvalóan nem megfelelő. Más megoldás kellene! Váratlanul egy informatikai óriás, az Amazon jön a segítségünkre! Neki Amazon szolgáltatás A motorosszán lehetővé teszi, hogy nagy mennyiségű adatot töltsön be a mobil tárolóba, és teherautóval szállítsa ki a megfelelő címre!
Tehát van egy új algoritmusunk! "Ha 5000 kilométernél hosszabb fájlok formájában szeretne információt átvinni, és ez a folyamat több mint 14 napot vesz igénybe az interneten keresztül, akkor az adatszállítást egy Amazon teherautón kell használnia." A 14 napos számot itt véletlenszerűen választjuk ki: mondjuk ez a maximális időszak, amit megengedhetünk magunknak. Elemezzük az algoritmusunkat. Mi a helyzet a sebességgel? Még ha egy teherautó csak 50 km/h-val halad is, mindössze 100 óra alatt 5000 kilométert tesz meg. Ez alig több mint négy nap! Ez sokkal jobb, mint az internetes átviteli lehetőség. Mi a helyzet ennek az algoritmusnak a bonyolultságával? Lineáris is lesz, O(N)? Nem, nem fog. Végül is a teherautót nem érdekli, hogy mennyit rakod be – továbbra is nagyjából ugyanolyan sebességgel megy, és időben érkezik. Akár 800 terabájt, akár 10-szer több adat áll rendelkezésünkre, a kamion 5 nap múlva is a helyszínre ér. Más szóval, a teherautón keresztüli adattovábbítás algoritmusa állandó komplexitás. Az „állandó” azt jelenti, hogy nem függ az algoritmusnak átadott adatoktól. Tegyél egy 1 GB-os pendrive-ot a kamionba - 5 napon belül megérkezik. Tegyél oda 800 terabájtnyi adatot tartalmazó lemezeket – 5 napon belül megérkezik. A Big-O használatakor az állandó komplexitást a következőképpen jelöljük O(1). Mióta megismertük TOVÁBB)És O(1), akkor most nézzünk még több „programozási” példát :) Tegyük fel, hogy kapsz egy 100 számból álló tömböt, és a feladat az, hogy mindegyiket kinyomtasd a konzolra. Írsz egy normál for ciklust , amely ezt a feladatot végzi int numbers = new int [ 100 ] ; // ..töltsük ki a tömböt számokkal for (int i: számok) ( System. out. println (i) ; ) Mekkora az írott algoritmus bonyolultsága? Lineáris, O(N). A programnak végrehajtandó műveletek száma attól függ, hogy hány számot adtak át a programnak. Ha 100 szám van a tömbben, akkor 100 művelet (kimenet a képernyőn) lesz. Ha 10 000 szám van a tömbben, akkor 10 000 műveletet kell végrehajtani. Javítható-e az algoritmusunk? Nem. Mindenesetre muszáj N áthalad a tömbönés hajtson végre N kimenetet a konzolra. Nézzünk egy másik példát. public static void main(String args) ( LinkedList < Integer> számok = új LinkedList< >() ; számok. hozzáadás (0 , 20202 ); számok. add (0 , 123 ); számok. add (0 , 8283 ); ) Van egy üres LinkedListünk, amelybe beszúrunk néhány számot. Értékelnünk kell a példánkban szereplő LinkedList-be egyetlen szám beillesztésére szolgáló algoritmus bonyolultságát, és azt, hogy ez hogyan függ a lista elemeinek számától. A válasz az lesz O(1) - állandó komplexitás. Miért? Vegye figyelembe, hogy minden alkalommal beszúrunk egy számot a lista elejére. Ezen kívül, mint emlékszel, amikor beszúr egy számot a LinkedListbe, az elemek nem mozdulnak el sehova - a hivatkozások újradefiniálódnak (ha hirtelen elfelejtette a LinkedList működését, nézze meg valamelyikünket). Ha most a listánkban az első szám az x szám, és beszúrjuk az y számot a lista elejére, akkor csak x kell. előző = y; y. előző = null; y. következő = x; Ehhez a link felülbírálásához most nem érdekel, hogy hány szám van a LinkedListben- legalább egy, legalább egy milliárd. Az algoritmus összetettsége állandó - O(1).

Logaritmikus komplexitás

Semmi pánik! :) Ha a „logaritmikus” szónál le szeretné zárni az előadást, és nem szeretne tovább olvasni, várjon néhány percet. Itt nem lesznek matematikai nehézségek (más helyeken is van ilyen magyarázat bőven), és az összes példát „az ujjakon” elemezzük. Képzeld el, hogy az a feladatod, hogy egy 100 számból álló tömbben találj egy adott számot. Pontosabban annak ellenőrzésére, hogy van-e egyáltalán. Amint megtalálta a kívánt számot, a keresést le kell állítani, és a következő bejegyzést kell kiírni a konzolra: „A kívánt szám megtalálható! Az indexe a tömbben = ....” Hogyan oldana meg egy ilyen problémát? Itt a megoldás kézenfekvő: egyenként kell végigmenni a tömb elemein az elsőtől (vagy az utolsótól) kezdve, és ellenőrizni, hogy az aktuális szám megegyezik-e a keresett számmal. Ennek megfelelően a műveletek száma közvetlenül függ a tömb elemeinek számától. Ha 100 számunk van, akkor 100-szor kell a következő elemhez lépnünk, és 100-szor ellenőrizni kell a szám egyezését. Ha 1000 szám van, akkor 1000 ellenőrző lépés lesz. Ez nyilvánvalóan lineáris bonyolultság, TOVÁBB). És most egy pontosítást adunk a példánkhoz: a tömb, amelyben meg kell találnia a számot, növekvő sorrendben van rendezve. Változtat ez valamit a mi feladatunkon? Nyers erővel továbbra is megkereshetjük a kívánt számot. De helyette használhatjuk a jól ismert bináris keresési algoritmus.
A kép felső sorában egy rendezett tömböt látunk. Meg kell találnunk benne a 23-as számot. A számok rendezése helyett egyszerűen csak 2 részre osztjuk a tömböt, és ellenőrizzük az átlagos számot a tömbben. Megkeressük a 4-es cellában található számot, és ellenőrizzük (a képen a második sor). Ez a szám 16, mi pedig 23-at keresünk. A jelenlegi szám kevesebb. Mit is jelent ez? Mit az összes korábbi szám (amely a 16-os előtt található) nem ellenőrizhető: biztosan kevesebben lesznek, mint amit keresünk, mert a tömbünk rendezett! Folytassuk a keresést a fennmaradó 5 elem között. Figyelem: csak egy ellenőrzést végeztünk, de a lehetséges lehetőségek felét már kiküszöböltük. Már csak 5 termékünk maradt. Megismételjük a lépésünket - osszuk el ismét 2-vel a fennmaradó tömböt, és vegyük újra a középső elemet (3. sor az ábrán). Ez a szám 56, és több, mint amit keresünk. Mit is jelent ez? Még 3 lehetőséget elutasítunk - magát az 56-os számot, és két számot utána (ezek határozottan nagyobbak, mint 23, mert a tömb rendezve van). Már csak 2 számot kell ellenőriznünk (az ábra utolsó sora) - 5-ös és 6-os tömbindexű számokat. Ezek közül az elsőt ellenőrizzük, és ezt kerestük - a 23-as számot! Az indexe = 5! Nézzük meg az algoritmusunk eredményeit, majd foglalkozzunk annak összetettségével. (Mellesleg, most már érti, miért nevezik binárisnak: a lényege az adatok állandó 2-vel való osztása). Az eredmény lenyűgöző! Ha lineáris kereséssel a megfelelő számot keresnénk, akkor 10 csekkre lenne szükségünk, bináris kereséssel pedig 3-at kihagytunk! A legrosszabb esetben 4 db lenne, ha az utolsó lépésnél a második, és nem az első szám lenne, amire szükségünk volt. Mi a helyzet a bonyolultságával? Ez egy nagyon érdekes pont :) A bináris keresési algoritmus sokkal kevésbé függ a tömb elemeinek számától, mint a lineáris keresési algoritmus (vagyis egy egyszerű felsorolás). Nál nél 10 egy tömb elemeit, a lineáris keresés legfeljebb 10, a bináris keresés pedig legfeljebb 4 ellenőrzést igényel. A különbség 2,5-szeres. De egy tömbhöz 1000 tétel a lineáris kereséshez 1000 ellenőrzésre lesz szükség, és a bináris - összesen 10! Már 100-szoros a különbség! Vegyük észre, hogy a tömb elemeinek száma 100-szorosára nőtt (10-ről 1000-re), míg a bináris kereséshez szükséges ellenőrzések száma csak 2,5-szeresére, 4-ről 10-re nőtt. Ha megkapjuk nak nek 10000 tétel, a különbség még lenyűgözőbb: 10 000 csekk a lineáris kereséshez, és összesen 14 ellenőrzés binárishoz. És még egyszer: az elemek száma 1000-szeresére nőtt (10-ről 10000-re), az ellenőrzések száma pedig mindössze 3,5-szeresére (4-ről 14-re). A bináris keresési algoritmus bonyolultsága logaritmikus, vagy Big-O jelöléssel, - O(log n). Miért hívják így? A logaritmus a hatványozás inverze. A bináris logaritmus egy 2 szám hatványának kiszámítására szolgál. Például 10 000 elemünk van, amelyeket bináris kereséssel kell rendeznünk.
Most egy kép van a szemed előtt, és tudod, hogy ehhez maximum 14 csekk szükséges. De mi van akkor, ha nincs kép a szeme előtt, és ki kell számítania a szükséges ellenőrzések pontos számát? Elég egy egyszerű kérdésre válaszolni: Milyen hatványra kell emelni a 2-es számot, hogy a kapott eredmény >= az ellenőrizendő elemek száma legyen? 10000-ért a 14. fok lesz. 2 13 hatványához túl kevés (8192) De 2-től a 14. hatványig = 16384, ez a szám kielégíti a feltételünket (ez >= a tömb elemeinek száma). Megtaláltuk a logaritmust - 14. Annyi ellenőrzésre van szükségünk! :) Az algoritmusok és bonyolultságuk túl kiterjedt téma ahhoz, hogy egy előadásba beleférjen. De ennek ismerete nagyon fontos: sok interjúban algoritmikus feladatokat kap. Elméleti szempontból tudok ajánlani néhány könyvet. Kezdheti a „Big-O videó a YouTube-on. Találkozunk a következő előadásokon! :)

Gyakran lehetséges egynél több algoritmus kidolgozása ugyanazon probléma megoldására. Ezzel kapcsolatban felmerül a kérdés: melyik algoritmus a „jobb”?

A legtöbb esetben a „jobb” látszólag egy olyan algoritmus, amely ugyanazon bemeneti adatokon jut el a probléma megoldásához, kevesebb számítási erőforrást (memória és idő) fogyasztva. Ez természetesen laza vita. A szigorúbb érvelés érdekében több fogalmat is bevezetünk.

Az algoritmus számítási folyamata olyan lépések sorozata, amelyeket az algoritmus bizonyos bemenetre történő végrehajtása során hajtanak végre.

Fontos megérteni a különbséget maga az algoritmus és az algoritmus által generált számítási folyamat között. Az első csak leírás második.

Egy algoritmus időbonyolultsága az az idő \(T\), amely az algoritmus számítási folyamatának befejezéséhez szükséges bizonyos bemenetek esetén.

Nyilvánvaló, hogy a végrehajtási idő attól függ konkrét művész. Tegyük fel, hogy egy elektronikus számológép és egy szuperszámítógép valószínűleg ugyanazt az algoritmust fogja futtatni különböző időpontokban.

A \(T\) idő azonban kifejezhető az elemi műveletek számával \(k\) és egy elemi művelet átlagos végrehajtási idejével \(t\):

Ráadásul a \(k\) egy tulajdonság a legtöbb algoritmus, a \(t\) pedig a végrehajtó tulajdonsága.

Tekintettel arra, hogy \(t\) egy adott előadónál konstansnak tekinthető, általában az algoritmusok bonyolultságát egy állandó tényezőig becsülik. Más szóval, az algoritmus bonyolultsága becsült növekedési sorrend.

Növekedési sorrend Egy pozitív-definit függvény \(g(x)\) növekedési sorrendje \(f(x)\) (írva \(g(x)=\mathcal(O)(f(x))\) ) ha \(\exists c>0: \: \forall x>x_0, \, g(x) \leq c f(x)\).

A bemeneti adatoktól függően az algoritmus különböző ideig futhat. Általában minősített átlagos nehézség és összetettség legrosszabb esetben. Van egy függőség is mennyiségeket bemeneti adatok \(n\) . Általában a \(n\)-től kezdődő növekedési sorrend kerül kiértékelésre.

Így például az adatok kiolvasása és a memóriában tömbként való tárolása bonyolultságú \(\mathcal(O)(n)\) , vagy lineáris komplexitás, és a mátrixszorzás már kocka alakú\(\mathcal(O)(n^3)\) .

Az algoritmus időbeli összetettsége mellett az is fontos térbeli az algoritmus bonyolultsága.

Az algoritmus térbeli összetettsége a szám további memória \(S\) , amelyre az algoritmus működéséhez szüksége van. A bemeneti adatok tárolásához szükséges memória \(D\) nem szerepel a \(S\) -ben.

\(S\) általában a végrehajtó eszköztől is függ. Tegyük fel, hogy ha két végrehajtási egység 4, illetve 8 bájtos egész számokat támogat, akkor az algoritmus térbonyolítása a 8 bájtos egész számok esetén kétszerese lesz a 4 bájtos egész számoknak. Ezért a térbeli komplexitást is a növekedési sorrend alapján becsüljük meg.

Algoritmusok összetettségi osztályai

Bizonyos összetettségi osztályok: Ezek hasonló nehézségű kategóriák.

A következő fő összetettségi osztályok vannak:

DTIME A Turing-gép véges idő (lépések száma) alatt talál megoldást egy problémára. Az algoritmus aszimptotikája gyakran finomodik, tehát ha a futási idő növekedési sorrendje \(T(n) = \mathcal(O)(f(n))\) , akkor \(DTIME(f) (n))\) jelzett. P A Turing-gép polinomiális időben (lépések számában) talál megoldást a feladatra, azaz. \(T(n) = \mathcal(O)(n^k)\) , ahol \(k\in \mathbb(N)\) . \(P=DTIME(n^k)\) EXPTIME A Turing-gép exponenciális időben (lépések számában) találja meg a probléma megoldását, azaz. \(T(n) = \mathcal(O)(2^(n^k))\), ahol \(k\in \mathbb(N)\) . \(EXPTIME=DTIME(2^(n^k))\) . DSPACE A Turing-gép véges mennyiségű extra memória (cella) felhasználásával talál megoldást egy problémára. Az algoritmus aszimptotikája gyakran finomodik, tehát ha a memóriafelhasználás növekedési sorrendje \(S(n) = \mathcal(O)(f(n))\) , akkor \(DSPACE(f( n))\) van megadva. L A Turing-gép egy logaritmikus térbonyolultságú feladatra talál megoldást, pl. \(S(n) = \mathcal(O)(\log n)\). \(L=DSPACE(\log n)\) . PSPACE A Turing-gép megoldást talál egy polinomiális tér komplexitású problémára, azaz \(S(n) = \mathcal(O)(n^k)\) , ahol \(k\in \mathbb(N)\) . \(PSSPACE=DSPACE(n^k)\) . KIFEJEZÉS A Turing-gép egy exponenciális térbonyolultságú problémára talál megoldást, pl. \(S(n) = \mathcal(O)(2^(n^k))\), ahol \(k\in \mathbb(N)\) . \(EXPSPACE=DSPACE(2^(n^k))\) .

Ezenkívül vannak elméleti komplexitási osztályok, amelyek a koncepcióval működnek nem determinisztikus Turing gépek (HMT). Definícióik megegyeznek a fentiekkel, a Turing-gépet HMT helyettesíti, és a nevek előtt N szerepel (például NP), kivéve az NTIME és NSPACE, ahol a D helyett N.

Az NMT egy tisztán elméleti konstrukció, amely működési elvei szerint hasonló az MT-hez, azzal a különbséggel, hogy mindegyik állapotra néhány lehetséges cselekvések. Ugyanakkor az NMT a lehetséges akciók közül mindig azt választja ki, amelyik a lehető legkevesebb lépésszámban vezet a megoldáshoz. Ennek megfelelően a HMT számol minden elágaz, és kiválasztja azt az ágat, amely a lehető legkevesebb lépésben a megoldáshoz vezet.

Néha hallani, hogy a kvantumszámítógépek az NMT megvalósítása. Bár ez bizonyos esetekben igaznak tűnhet, általában a BMT több erős rendszer mint egy kvantumszámítógép.

Ismeretes, hogy \(P \subseteq NP \subseteq PSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE\)

Továbbá \(P \subsetneq EXPTIME\) , \(NP \subsetneq NEXPTIME\) , \(PSPACE \subsetneq EXPSPACE\)

Az is ismert, hogy ha \(P = NP\) , akkor \(EXPTIME = NEXPTIME\) .

A P és NP egyenlőségének kérdése a modern számítástechnika egyik fő megoldatlan kérdése.

Algoritmus példák

Adjunk néhány példát egyszerű algoritmusokra, és vegyük figyelembe bonyolultságukat.

Növelés egész hatványra

Ezt az algoritmust az ókori Indiában írták le a korszakunk előtt, és egy valós szám \(n\) természetes erejének kiszámítására használják \(x\)

1. \(n\) binárisan írd be
2. Cserélje le ebben a bejegyzésben az 1-eseket egy-egy KX betűpárra, a 0-t pedig K betűre.
3. Húzd át a bal szélső CH-párt
4. A kapott karakterlánc balról jobbra olvasása, a K betű elérése, az eredmény négyzetre emelése és az X betű elérése esetén az eredményt megszorozzuk x-szel. Az elején az eredmény x.

Ebben az algoritmusban a szorzási műveletek száma megegyezik a benne lévő számjegyek számával bináris reprezentáció\(n\) a legjobb esetben, és \(2(n-1)\) a legrosszabb esetben. Mindenesetre a .

Az algoritmus hatékony megvalósításához gyakorlatilag nincs szükség további memóriára, és nem függ a bemeneti adatoktól, így a térbonyolítás \(S(n) = \mathcal(O)(1)\) .

Meg kell jegyezni, hogy vannak hatékonyabb algoritmusok. Azonban a „naiv” megvalósításhoz képest, amely \(\mathcal(O)(n)\) szorzási műveleteket igényel, ez az algoritmus viszonylag hatékony.

Egész szám szorzás

Ezt a szorzási algoritmust néha orosznak vagy parasztnak nevezik, bár az ókori Egyiptomban ismerték.

Az első tényezőt egymás után megszorozzuk kettővel, a másodikat pedig elosztjuk 2-vel. Az eredményeket két oszlopba írjuk, amíg a második 1 lesz.

A szorzás eredménye az első oszlopban lévő számok összege, amelyek a páratlan számok a második oszlopban.

Mivel az egész számok osztása és 2-vel való szorzása megvalósítható eltolással, ez az algoritmus \(2 \log_2 n\) eltolási műveleteket eredményez, ahol \(n\) a két szám közül a kisebbik. A legrosszabb esetben \(\log_2 n - 1\) összeadási műveleteket is kapunk. Mindenesetre az idő bonyolultsága \(T(n) = \mathcal(O)(\log n)\).

Az algoritmus hatékony megvalósításához gyakorlatilag nincs szükség további memóriára, és ez nem függ a bemeneti adatoktól, ezért \(S(n) = \mathcal(O)(1)\)

Ismét meg kell jegyezni, hogy vannak hatékonyabb algoritmusok. Azonban a „naiv” megvalósításhoz képest, amely \(\mathcal(O)(n)\) összeadási műveleteket igényel, ez az algoritmus viszonylag hatékony.

Példa

Szorozzuk meg a 23-at 43-mal.

Vegyük a 23-at második tényezőnek.

43	23	páratlan
86	11	páratlan
172	5	páratlan
344	2
688	1	páratlan

Eredmény \(43+86+172+688 = 989\)

10 műszakos műveletet és 4 összeadási műveletet kaptunk. Referenciaként: \(\log_2(23) \approx 4.52\) .

Összetettség funkció 0 (1). Az állandó bonyolultságú algoritmusokban a program legtöbb műveletét egyszer vagy többször hajtják végre. Bármely algoritmus, amely mindig (adatmérettől függetlenül) ugyanannyi időt igényel, állandó bonyolultságú.

Bonyolultsági függvény 0(N). A program futási ideje általában lineáris, amikor a bemenő adatok egyes elemeit csak lineárisan kell feldolgozni. Ez a bonyolultsági függvény egy egyszerű ciklust jellemez.

Bonyolultsági függvény 0(N 2), 0(N 3), 0(№) - komplexitás polinomiális függvénye: a négyzettel arányosan nő a műveletek száma N.Általános esetben a probléma összetettségétől függően O(A^) is előfordulhat. Ez a komplexitási függvény egy összetett ciklust jellemez.

Összetettség funkció O(2. napló (A0), 0 (N log 2 (A0). Ez az az időszak, amikor olyan algoritmusok dolgoznak, amelyek egy nagy problémát sok kicsire osztanak, majd miután megoldották azokat, kombinálják a megoldásokat.

0(e N) összetettségi függvény. Az exponenciális bonyolultságú algoritmusok leggyakrabban a nyers erőnek nevezett megközelítésből származnak.

Bonyolultsági függvény 0(M) - a műveletek száma a faktoriálissal arányosan nő N.

A programozónak képesnek kell lennie az algoritmusok elemzésére és bonyolultságuk meghatározására. Egy algoritmus időbonyolultsága a vezérlési struktúráinak elemzése alapján számítható ki.

A hurkok és rekurzív hívások nélküli algoritmusok állandó bonyolultságúak. Ha nincs rekurzió és hurkok, akkor az összes vezérlőstruktúra állandó bonyolultságú struktúrákra redukálható. Ebből következően az egész algoritmust is állandó bonyolultság jellemzi. Egy algoritmus bonyolultságának meghatározása alapvetően a hurkok és a rekurzív hívások elemzésén múlik.

Vegyünk például egy algoritmust a tömbelemek feldolgozására.

/" esetén: = 1-től N do Kezdd

Ennek az algoritmusnak a bonyolultsága RÓL RŐL(A), mert a ciklus törzsét A-szor hajtják végre, és a huroktest összetettsége 0(1). Ha az egyik hurok egy másikba van beágyazva, és mindkét ciklus ugyanannak a változónak a méretétől függ, akkor az egész konstrukciót négyzetes összetettség jellemzi.

A /: = 1-től N csinálni érte j:= 1-től N do Kezdd

A program összetettsége 0(N2).

1. példa Becsüljük meg egy olyan program összetettségét, amely a billentyűzetről belép egy tömbbe, és megtalálja benne a legnagyobb elemet. Az algoritmus a következő lépésekből áll:

• - tömbbevitel (az A elemeket kell olvasni);
• - keresse meg a legnagyobb elemet (A - 1 összehasonlítást kell végeznie);
• - az eredmény kimenete (egy számot vagy karakterláncot kell kiírnia).

Összeadjuk az A + (A - 1) + 1 = 2A műveletek számát, azaz. létezik

olyan állandó, hogy bármely A művelet száma ne haladja meg a CA-t. Ezért az algoritmus összetettsége 0(A).

2. példa Becsüljük meg egy olyan program összetettségét, amely a billentyűzetről belép egy tömbbe és talál benne egy elemet adott ingatlan(például egy bizonyos értékkel egyenlő). Az algoritmus a következő lépésekből áll:

• - tömbbevitel (Input műveletek);
• - adott tulajdonságú elem keresése (egy elem lehet közelebb a tömb elejéhez, vagy a legvégén; ha az elem nem létezik, akkor minden A összehasonlítást el kell végezni, hogy megbizonyosodjunk erről);
• - eredmény kimenet.

A megadott algoritmus legjobb esetben A + 2 műveletet igényel (a teljes tömb bemenete, egyetlen összehasonlítás, kimenet), a legrosszabb esetben (amikor nincs ilyen elem, 2A + 1 művelet). Ha A akarat egy nagy szám, például kb 10 6 , akkor az egység elhanyagolható. Ezért az algoritmus összetettsége az 0(N).

3. példa Határozzuk meg a titkosítási algoritmus összetettségi függvényét egy hosszúságú szóra L helyettesítési módszer. Legyen egy táblázat, amelyben az ábécé minden karakteréhez tartozik egy karakter, amelyre ki kell cserélni. Jelölje az ábécé betűinek számát S. Az algoritmus a következő lépésekből áll:

• - szó bevitele (egy művelet);
• - ciklusszervezés:
  • 1) minden karakterhez keresse meg a helyettesítését a táblázatban (ha a táblázat nincs rendezve, és nincs olyan tulajdonsága, amely megkönnyíti a keresést, akkor a legrosszabb esetben szükséges S műveletek egy karakterre, ha a szükséges elem a legvégén van);
  • 2) a talált szimbólum kimenete;
• - a ciklus vége.

Műveletek teljes száma 1+ (S+)L. Abban az esetben, ha elég nagy SÉs L egységeket elhanyagolhatjuk, és kiderül, hogy a fenti algoritmus komplexitásfüggvénye az O(S L).

4. példa Határozzuk meg a természetes szám-fordítási algoritmus komplexitásfüggvényét 1 V a kettes számrendszerhez (adatbeviteli és -kiadási műveletek nélkül). Az algoritmus a következő lépésekből áll:

• - ciklus addig, amíg egy szám 2-vel való elosztásának eredménye 0 lesz:
• - ossza el a számot 2-vel, és emlékezzen a maradékra;
• - fogadja el az osztás eredményét új számként;
• - a ciklus vége.

A műveletek teljes száma nem haladja meg az 1 + log 2 A-t. Ezért a leírt algoritmus bonyolult 0 (og 2 N).

Hagyományosan egy algoritmus bonyolultsági fokát szokás az általa használt fő számítógépes erőforrások mennyisége alapján értékelni: processzoridő és véletlen hozzáférésű memória. Ebben a tekintetben olyan fogalmakat vezetnek be, mint egy algoritmus időbonyolultsága és egy algoritmus térfogati összetettsége.

Az időbonyolultság paraméter különösen fontossá válik az interaktív programműködési módot magában foglaló feladatoknál, vagy a valós idejű vezérlési feladatoknál. Gyakran egy programozó, aki vezérlőprogramot ír egyeseknek műszaki eszköz, kompromisszumot kell találnunk a számítások pontossága és a program futási ideje között. A pontosság növekedése általában az idő növekedéséhez vezet.

A program volumetrikus összetettsége akkor válik kritikussá, ha a feldolgozott adatok mennyisége a számítógép RAM-jának határán van. A modern számítógépeken a probléma súlyossága csökken mind a RAM mennyiségének növekedése, mind a hatékony felhasználása többszintű tárolórendszer. A program nagyon nagy, szinte korlátlan memóriaterülethez fér hozzá ( virtuális memória). A fő memória hiánya csak a lemezcserék miatti lassuláshoz vezet. Olyan technikákat alkalmaznak, amelyek minimalizálják az időveszteséget egy ilyen csere során. Ez a gyorsítótár használata és a programutasítások hardveres megtekintése a szükséges számú lépéshez, amely lehetővé teszi a szükséges értékek előzetes átvitelét a lemezről a fő memóriába. A fentiek alapján arra a következtetésre juthatunk, hogy a kapacitív komplexitás minimalizálása nem elsődleges prioritás. Ezért a következőkben elsősorban az algoritmusok időbeli összetettségére leszünk kíváncsiak.

A program végrehajtási ideje arányos a végrehajtott műveletek számával. Természetesen az idő dimenziós egységeiben (másodpercben) ez a processzor sebességétől (órajel frekvenciától) is függ. Annak érdekében, hogy az algoritmus időbonyolultságának mutatója invariáns legyen ahhoz képest specifikációk számítógép, relatív mértékegységekben mérik. Az időbonyolultságot általában az elvégzett műveletek számával becsülik meg.

Általános szabály, hogy az algoritmus időbeli összetettsége a kezdeti adatoktól függ. Ez függhet mind a kezdeti adatok méretétől, mind a mennyiségüktől. Ha az α algoritmus időbonyolultsági paraméterének értékét Tα szimbólummal jelöljük, a V betű pedig valamilyen, a kiindulási adatokat jellemző numerikus paramétert, akkor az időbonyolultság Tα(V) függvényként ábrázolható. Az V paraméter kiválasztása a megoldandó problémától vagy a probléma megoldására használt algoritmus típusától függ.

1. példa. Becsüljük meg a pozitív egész szám faktoriálisának számítására szolgáló algoritmus időbonyolultságát.

Függvény Factorial(x:Integer): Integer;

Varm,i: Integer;

For i:=2 To x Do m:=ro*i;

Számítsuk ki a program által végrehajtott műveletek teljes számát mikor adott értéket x. Az m:=1; utasítás egyszer végrehajtásra kerül; a ciklustörzs (amelyben két művelet van: szorzás és hozzárendelés) x - 1 alkalommal kerül végrehajtásra; a hozzárendelés egyszer történik Factorial:=m. Ha mindegyik műveletet komplexitási egységnek vesszük, akkor a teljes algoritmus időbonyolultsága 1 + 2 (x - 1) + 1 = 2x Ebből egyértelmű, hogy az x értéket kell paraméternek venni. . Az időbonyolultsági függvény a következő lett:

Ebben az esetben azt mondhatjuk, hogy az időbonyolultság lineárisan függ az adatparamétertől - a faktoriális függvény argumentumának értékétől.

2. példa: Két vektor skaláris szorzatának kiszámítása A = (a1, a2, ..., ak), B = (b1, b2, ..., bk).

Az i:=l-hez k Do AB:=AB+A[i]*B[i];

Ebben a feladatban a bemeneti adatok mérete n = 2k. Az elvégzett műveletek száma 1 + 3k = 1 + 3(n/2). Itt felvehetjük V= k= n/2. Az algoritmus összetettsége nem függ az A és B vektorok elemeinek értékétől. Az előző példához hasonlóan itt is beszélhetünk az időbonyolultság lineáris függéséről az adatparamétertől.

Egy algoritmus időbonyolultsági paraméteréhez általában két elméleti probléma társul. Az első abban áll, hogy választ találunk arra a kérdésre: az időbonyolultság értékének milyen határa érhető el a problémamegoldó algoritmus fejlesztésével? Ez a határ magától a feladattól függ, és ezért a saját jellemzője.

A második probléma az algoritmusok időbonyolultság szerinti osztályozásával kapcsolatos. A Tα(V) függvény általában V-vel nő. Milyen gyorsan növekszik? Léteznek olyan algoritmusok, amelyekben Tα lineárisan függ V-től (ahogyan az általunk vizsgált példákban volt), másodfokú függőséggel és magasabb fokú függéssel. Az ilyen algoritmusokat polinomiálisnak nevezzük. És vannak olyan algoritmusok, amelyek összetettsége gyorsabban növekszik, mint bármely polinom. A teoretikusok – algoritmuskutatók által gyakran megoldott probléma a következő kérdés: lehetséges-e polinomiális algoritmus egy adott problémára?

Az algoritmusok elemzése során gyakran előforduló funkciók:

• log n(logaritmikus idő),
• n(lineáris idő),
• n log n,
• n 2 (négyzetidő),
• 2n(exponenciális idő).

Az első négy függvény növekedési üteme alacsony, és azok az algoritmusok, amelyek futási idejét ezek a függvények becsülik, gyorsnak tekinthetők. Egy exponenciális függvény növekedési ütemét néha „robbanásveszélyesnek” nevezik. Összehasonlításképpen tegyük fel, hogy vannak olyan algoritmusok, amelyek összetettségét (a műveletek számát) pontosan tükrözik ezek a függvények. Legyen ezek az algoritmusok végrehajtva egy másodpercenként 10 12 műveleti sebességgel működő számítógépen. Bemeneti hosszúsággal n≤ 100000, azok az algoritmusok, amelyek teljesítményét az első négy függvény becsüli meg, a másodperc töredéke alatt kapnak választ. 2-es bonyolultságú algoritmushoz n a működési idő a következőképpen becsülhető:

• n= 50 ≈ 19 perc,
• n= 60 ≈ 320 óra,
• n= 70 ≈ 37 éves.

15. kérdés=49. Szekvenciális, ciklikus és rekurzív algoritmusok.

Szekvenciális algoritmusok - olyan algoritmusok, amelyekben a blokkokat egymás után, egy adott séma sorrendjében hajtják végre.

Példa. Számítsa ki az a,b,c oldalú háromszög kerületét.13

Elágazó szerkezeti algoritmus

A gyakorlatban ritkán lehetséges egy probléma megoldását algoritmus formájában ábrázolni

lineáris szerkezet. Gyakran valamilyen köztestől függően

a számítási eredményeket vagy az egyiken, vagy a másikon hajtják végre

képletek, azaz. valamely logikai feltétel teljesülésétől függően

a számítási folyamatot egyik vagy másik képlet szerint hajtjuk végre.

Az ilyen számítási folyamat algoritmusát algoritmusnak nevezzük

elágazó szerkezet.

Elágazás - irányító szerkezet, amely csak a végrehajtását szervezi meg

a méltányosságtól függően a megadott két intézkedés egyike

valamilyen feltétel.

A feltétel olyan kérdés, amelyre két lehetséges válasz van: igen vagy nem.

Az elágazást két formában rögzítjük: teljes és hiányos (1. a, b ábra).

a) teljes forma b) hiányos nyomtatvány

Ciklikus algoritmusok – algoritmusok, amelyekben ismételten ki kell számítani az értékeket ugyanazon matematikai függőségek (blokkdiagramok) szerint a bennük szereplő mennyiségek különböző értékeire. A ciklusok használata jelentősen csökkentheti az áramkör hangerejét

algoritmus és a megfelelő program hossza. Vannak ciklusok

adott és ismeretlen számú ismétlés. Adott számú ismétlés mellett -

hurok számlálóval. Ismeretlen számú ismétléssel - hurok előfeltétellel,

hurok utófeltétellel.

Azt a függvényt (vagy eljárást), amely közvetlenül vagy közvetve önmagára hivatkozik, rekurzívnak nevezzük. A rekurzió egy függvény definiálási módszere a korábbi és korábban meghatározott értékeken, valamint egy módon

számítások szervezése, amelyben a függvény más argumentummal hívja meg magát

Rekurzív algoritmusok implementálásakor minden egyes rekurziós lépés nem ad közvetlen megoldást a problémára, hanem ugyanarra a problémára redukálja. kisebb. Ennek a folyamatnak olyan méretű feladathoz kell vezetnie, hogy

a megoldás elég egyszerű. Továbbá a "fordított mozgás" egymást követő megoldásokat ad a méretnövekedés problémájára, egészen a kezdetiig. A rekurziós eljárás megvalósítása egy veremre (store típusú memória) épül, amely minden olyan eljáráshívásban érintett adatot tárolja, amelyben még nem fejezte be munkáját. A rekurzió a számítási folyamat megszervezésének egyik módja, amikor az algoritmus önmagára hivatkozik. A rekurzió elve lehetővé teszi egy összetett probléma megoldását egyszerűbb részproblémák szekvenciális megoldásával.A rekurzióra általában olyan esetekben van szükség, amikor túl sok lehetőségen kell keresztülmenni. A rekurziót az egyik fajtának tekintik ciklikus algoritmus. A rekurzív szervezési forma lehetővé teszi az algoritmus tömörebb formáját. Így a probléma az összetetttől az egyszerűig megoldódik - a rekurzív algoritmus tartalma egy összetettebb objektumot tükröz egy azonos típusú egyszerűbb objektumon keresztül. A rekurzív algoritmusok általában a következő fő részeket tartalmazzák:

– a ciklus befejezésének feltétele;

- a rekurzió törzse, amely magában foglalja az erre szánt műveleteket

végrehajtás minden iterációnál;

az a rekurziós lépés, amelynél a rekurzív algoritmus meghívja magát.

Tegyen különbséget a direkt és indirekt rekurzió között. Az első esetben az algoritmus

olyan függvényt tartalmaz, amely meghívja magát. Ha egy függvény meghív egy másik függvényt, amely viszont az elsőt, akkor azt a függvényt

közvetetten rekurzívnak nevezzük.

A rekurzív algoritmusokkal szemben támasztott fő követelmény az, hogy az inverziós folyamat ne legyen

végtelennek kell lennie. Más szóval, végre kell hajtani

a hívás befejezésének ellenőrzése, vagy rekurzív definícióban kell

van egy korlátozás, amely alatt a további inicializálás

a rekurzió megszakad.

A rekurzív függvényre példa egy szám faktoriálisának kiszámítása.

int faktoria(int n)

if (n) visszatér n* factoria(n-1);

else return 1;

Példa egy rekurzív eljárásra:

eljárás Rec(a: integer); kezdődik, ha a>0, akkor Rec(a-1); writeln(a); vége;

Nézzük meg, mi történik, ha a főprogramban egy hívást teszünk fel, például Rec(3) formában. Az alábbiakban egy folyamatábra látható, amely az utasítások végrehajtási sorrendjét mutatja.