Az algoritmus időbonyolultságának becslése. Az algoritmusok komplexitásának függvénytípusai

Állandó idő

Az algoritmust algoritmusnak mondják állandó idő(időként rögzítve O (1)) ha az érték T(n) olyan értékre korlátozódik, amely nem függ a bemenet méretétől. Például egy tömb egy elemének megszerzése állandó időt vesz igénybe, mivel egyetlen parancs végrehajtásával keresi meg. A minimális érték megtalálása egy rendezetlen tömbben azonban nem állandó idejű művelet, mivel a tömb minden elemét át kell vizsgálnunk. Tehát ez a művelet lineáris időt vesz igénybe, O (n). Ha az elemek száma előre ismert és nem változik, akkor egy ilyen algoritmust konstans idejű algoritmusnak nevezhetjük.

Az "állandó idő" elnevezés ellenére a futási időnek nem kell függetlennek lennie a feladat méretétől, de a futási idő felső korlátja nem lehet az. Például az "értékek cseréje aés b, ha szükséges, hogy ennek eredményeként kapjuk a≤b", állandó idejű problémának tekinthető, bár az algoritmus futási ideje függhet attól, hogy az egyenlőtlenség a ≤ b vagy nem. Van azonban egy bizonyos állandó t, amelynél a feladat végrehajtási ideje mindig nem haladja meg t.

Az alábbiakban néhány állandó időben futó kódpélda látható:

Int index = 5; int item = lista; ha(a feltétel igaz) azutánmás hajtson végre néhány műveletet állandó futási idővel számára i = 1 nak nek 100 számára j = 1 nak nek 200 hajt végre bizonyos műveleteket állandó futási idővel

Ha T(n) az O ( valami állandó érték), ez megegyezik a T(n) jelentése O(1).

Logaritmikus idő

logaritmikus idő, ha T(n) = O (log n) ... Mivel a számítógépek bináris rendszert használnak, a 2 a logaritmus alapja (vagyis a log 2 n). Azonban azzal alapcsere logaritmus log a nés log b n csak egy állandó tényezővel különböznek, amit az O-nagy jelölésben el kell hagyni. Tehát O (log n) a logaritmikus időalgoritmusok szabványos jelölése, függetlenül a logaritmus alapjától.

A logaritmikus időalgoritmusok általában megtalálhatók a bináris faműveletek során vagy bináris keresés használatakor.

Az O (log n) algoritmusok rendkívül hatékonynak tekinthetők, mivel az elemenkénti végrehajtási idő az elemek számának növekedésével csökken.

Egy nagyon egyszerű példa egy ilyen algoritmusra, hogy egy karakterláncot kettéosztunk, a másik felét újra felezzük, és így tovább. Ez O (log n) időt vesz igénybe (ahol n a karakterlánc hossza, itt ezt feltételezzük console.logés str.substringállandó időt vesz igénybe). Ez azt jelenti, hogy a nyomatok számának növelése érdekében a sorhosszt meg kell duplázni.

// Funkció a sor jobb felének rekurzív nyomtatásához var right = függvény (str) (var hossz = str. hossza; // segítő függvény var help = függvény (index) ( // Rekurzió: kinyomtatja a jobb felét ha (index< length ) { // Karakterek nyomtatása az indextől a sor végéig konzol. log (szt. részkarakterlánc (index, hossz)); // rekurzív hívás: hívja meg a helper függvényt a jobb oldallal help (Math.ceil ((hossz + index) / 2)); )) segítség (0); )

Polilogaritmikus idő

Azt mondják, befut az algoritmus polilogaritmikus idő, ha T(n) = O ((log n) k), néhány k... Például a mátrixszorzás rendjének problémája polilogaritmikus időben megoldható a következővel párhuzamos PAM gép .

Szulineáris idő

Azt mondják, befut az algoritmus szublineáris idő, ha T(n) = o ( n). Különösen tartalmazza a fent felsorolt ​​időbonyolultsági algoritmusokat, valamint másokat, például a Grover-keresést O összetettséggel ( n ½).

Tipikus algoritmusok, amelyek bár pontosak, mégis szublineáris időben futnak, folyamatok párhuzamosítását használják (mint az NC 1 algoritmus a mátrix determinánsának kiszámításához), nem klasszikus számításokat (mint Grover keresésében), vagy garantált feltételezésük van a bemenet szerkezete (logaritmikus időben történő működés, bináris keresési algoritmusok és sok fafeldolgozási algoritmus). Azonban a formális konstrukciók, például az 1 bittel rendelkező összes karakterlánc halmaza a karakterlánc első log (n) bitje által meghatározott pozícióban, függhetnek a bemenet minden bitétől, de időben továbbra is szublineárisak maradnak.

Term szublineáris futásidejű algoritmusáltalában olyan algoritmusokhoz használják, amelyek a fenti példákkal ellentétben közönséges szekvenciális gépmodelleken működnek, és nem feltételezik a bemeneti struktúra előzetes ismeretét. Számukra azonban a valószínűségi módszerek használata megengedett, sőt, az algoritmusoknak valószínűséginek kell lenniük a legtöbb triviális probléma esetén.

Mivel egy ilyen algoritmusnak a bemenet teljes beolvasása nélkül kell válaszolnia, ez nagymértékben függ a bemeneti adatfolyamban engedélyezett hozzáférési módoktól. Általában egy kicsit karakterláncos adatfolyamhoz b 1 ,...,b k, feltételezzük, hogy az algoritmus O (1) idő alatt kérhet értéket b i bárkinek én.

A szublineáris időalgoritmusok általában valószínűségiek, és csak közelítő megoldást adnak. A szublineáris futásidejű algoritmusok természetesen felmerülnek a vizsgálat során ingatlanellenőrzések.

Lineáris idő

lineáris idő, vagy O ( n) ha összetettsége O ( n). Informálisan ez azt jelenti, hogy elég nagy bemeneti méret esetén a futási idő lineárisan növekszik a bemeneti mérettel. Például egy olyan eljárás, amely egy lista összes elemét összegzi, a lista hosszával arányos időt vesz igénybe. Ez a leírás nem teljesen pontos, mivel a futási idő jelentősen eltérhet a pontos arányosságtól, különösen kis értékek esetén. n.

A lineáris időt gyakran egy algoritmus kívánatos attribútumaként tekintik. Sok kutatást végeztek olyan algoritmusok létrehozására, amelyek (majdnem) lineáris vagy jobb futási idővel rendelkeznek. Ezek a vizsgálatok szoftveres és hardveres megközelítéseket is tartalmaztak. Hardveres végrehajtás esetén egyes algoritmusok, amelyek matematikailag soha nem képesek elérni a lineáris végrehajtási időt a szabványos számítási modellekben, lineáris időben futhatnak. Vannak olyan hardvertechnológiák, amelyek párhuzamosságot használnak e cél elérése érdekében. Ilyen például az asszociatív memória. A lineáris időnek ezt a fogalmát olyan karakterlánc-összehasonlító algoritmusok használják, mint például a Boyer - Moore és az Ukkonen.

Kvázilineáris idő

Egy algoritmusról azt mondjuk, hogy kvázilineáris időben fut, ha T(n) = O ( n log k n) valamilyen állandónak k... A lineáris-logaritmikus idő speciális esete k= 1. Ha gyenge-O jelölést használunk, ezek az algoritmusok Õ ( n). A kvázilineáris időalgoritmusok is o ( n 1 + ε) bármely ε> 0 esetén, és gyorsabban működnek, mint bármely in polinom n

A kvázilineáris időben futó algoritmusok a fent említett lineáris-logaritmikus algoritmusokon kívül a következők:

• Helyi összevonás rendezés, O ( n log 2 n)
• Gyors rendezés, O ( n log n), a valószínűségi változatban a legrosszabb esetben lineáris-logaritmikus végrehajtási idővel rendelkezik. A valószínűtlen változatnak lineáris naplózási ideje van, csak az átlagos bonyolultság mérésére.
• Heapsort, O ( n log n), egyesítési rendezés, introsort, bináris fa rendezés, sima rendezés, pasziánsz fajta stb. legrosszabb esetben
• Gyors Fourier transzformációk, O ( n log n)
• Monge mátrixok számítása, O ( n log n)

Lineáris logaritmikus idő

A lineáris-logaritmikus a kvázilineáris idő speciális esete kitevővel k= 1 a logaritmikus tagon.

Lineáris-logaritmikus függvény a forma függvénye n log n(azaz a termék lineárisés logaritmikus tagok). Az algoritmus állítólag működik lineáris logaritmikus idő, ha T(n) = O ( n log n) ... Így a lineáris-logaritmikus elem gyorsabban növekszik, mint a lineáris tag, de lassabban, mint bármely polinom n szigorúan 1-nél nagyobb végzettséggel.

Sok esetben a futási idő n log n egyszerűen a Θ művelet eredménye (log n) n egyszer. Például egy bináris fával történő rendezés úgy hoz létre bináris fát, hogy minden elemet egyenként beszúr egy n méretű tömbbe. A beszúrási művelet óta kiegyensúlyozott bináris keresőfa O-t vesz (log n), az algoritmus teljes végrehajtási ideje lineáris-logaritmikus lesz.

Összehasonlítás alapján rendezi legalább a legrosszabb eset összehasonlításainak lineáris-logaritmikus számát kell megkövetelni, mivel log ( n!) = Θ( n log n) a Stirling-képlet alapján. Ugyanez a végrehajtási idő gyakran adódik az ismétlődési egyenletből T(n) = 2 T(n/ 2) + O ( n).

Négyzetes idő

Néhány példa polinomiális idő algoritmusokra:

Szigorúan és gyengén polinomiális idő

Bizonyos esetekben, különösen az optimalizálásban, az algoritmusokat megkülönböztetik szigorú polinomidőés gyengén polinomiális idő... Ez a két fogalom csak az egész számokból álló bemeneti adatokra vonatkozik.

A szigorúan polinomiális időt az aritmetikai számítási modell határozza meg. Ebben a modellben az alapvető aritmetikai műveleteket (összeadás, kivonás, szorzás, osztás és összehasonlítás) végrehajtási egységnek vesszük, függetlenül az operandusok hosszától. Az algoritmus szigorúan polinomiális időben működik, ha

1. az aritmetikai számítási modellben a műveletek számát a bemeneti adatfolyamban lévő egész számok polinomja korlátozza, és
2. az algoritmus által használt memóriát egy polinom határolja a bemenet méretében.

Bármelyik algoritmus, amely rendelkezik ezzel a két tulajdonsággal, redukálható polinomiális idő algoritmussá, ha az aritmetikai műveleteket lecseréljük a Turing-gépen végzett számtani műveletek megfelelő algoritmusaira. Ha a fenti követelmények közül a második nem teljesül, ez többé nem lesz igaz. Adott egy egész szám (amely a Turing-gépben n-nel arányos memóriát foglal el), ismételt hatványozással n művelettel kiszámítható. A memória azonban korábban reprezentált 2 2 n (\ displaystyle 2 ^ (2 ^ (n))), arányos 2 n (\ displaystyle 2 ^ (n)), és nem polinomiálisan, hanem exponenciálisan függ a bemenethez használt memóriától. Ezért - lehetetlen ezeket a számításokat polinomiális időben elvégezni egy Turing-gépen, de lehetséges polinomiális számú aritmetikai művelet végrehajtása.

Ezzel szemben vannak olyan algoritmusok, amelyek a Turing-gép lépéseinek számában működnek, amelyeket a binárisan kódolt bemenet polinomiális hossza korlátoz, de nem működnek az aritmetikai műveletek számában, amelyeket a számok számának polinomja korlátoz. a bemenet. Euklidész algoritmusa két egész szám legnagyobb közös osztójának kiszámítására egy példa. Két egész számra a (\ displaystyle a)és b (\ displaystyle b) az algoritmus futási ideje korlátozott O ((log ⁡ a + log ⁡ b) 2) (\ displaystyle O ((\ log \ a + \ log \ b) ^ (2))) egy Turing-gép lépései. Ez a szám a számok bináris reprezentációjának méretének polinomja a (\ displaystyle a)és b (\ displaystyle b), ami nagyjából így ábrázolható log ⁡ a + log ⁡ b (\ displaystyle \ log \ a + \ log \ b)... Ugyanakkor az aritmetikai műveletek számát nem korlátozhatja a bemenetben lévő egész számok száma (ami ebben az esetben konstans - csak két szám van a bemenetben). E megjegyzésre tekintettel az algoritmus szigorúan polinomiális időben nem működik. Az algoritmus valós futási ideje az értékektől függ a (\ displaystyle a)és b (\ displaystyle b), nem csak az egész számok száma a bemenetben.

Ha egy algoritmus polinomiális időben fut, de nem szigorúan polinomiális időben, akkor azt mondjuk, hogy gyenge polinomidő... Egy jól ismert példa egy olyan problémára, amelyre gyengén polinomiális algoritmus ismert, de szigorúan polinomiális algoritmus nem ismert, a lineáris programozás. A gyengén polinomiális időt nem szabad összetéveszteni a pszeudopolinom idővel.

Nehézségi osztályok

A polinomiális idő fogalma több összetettségi osztályhoz vezet a számítási komplexitáselméletben. Az alábbiakban bemutatunk néhány fontos polinomiális idővel definiált osztályt.

• : Determinisztikus Turing-gépben polinomiális időben megoldható megoldhatósági feladatok összetettségi osztálya.
• : Nem-determinisztikus Turing-gépben polinomiális időben megoldható megoldhatósági feladatok összetettségi osztálya.
• ZPP: A valószínűségi Turing-gépben polinomiális időben nulla hibával megoldható megoldhatósági feladatok összetettségi osztálya.
• : A valószínűségi Turing-gépben polinomiális időben egyirányú hibával megoldható megoldhatósági feladatok összetettségi osztálya.
• BPP valószínűségi Turing-gép polinomiális időben.
• BQP: Kétoldali hibákkal megoldható megoldhatósági feladatok komplexitási osztálya kvantum Turing-gépben polinomiális időben.

P a legkisebb időbonyolultsági osztály egy determinisztikus gépen, ami az fenntartható a gépmodell megváltoztatása szempontjából. (Például, ha egy egyszalagos Turing-gépről egy többszalagos Turing-gépre váltunk, ez négyzetes gyorsulást eredményezhet, de minden olyan algoritmus, amely az egyik modellen polinomiális időben fut, polinomiális időben fut egy másik modellen.)

Szuperpolinom idő

Az algoritmus állítólag működik szuperpolinomiális idő, ha T(n) felett nincs polinom határa. Ez az idő egyenlő ω ( n c) minden állandóra c, ahol n egy bemeneti paraméter, általában a bemeneti bitek száma.

Például egy algoritmus, amely megvalósítja a 2 n lépések a méret megadásához n szuperpolinomiális időt (pontosabban exponenciális időt) igényel.

Nyilvánvaló, hogy az exponenciális erőforrásokat használó algoritmus szuperpolinom, de néhány algoritmus nagyon gyengén szuperpolinom. Például, Adleman-Pomeranza-Roumeli egyszerűségi teszt * időben működik n O (naplónapló n) tovább n-bit bemenet. Gyorsabban növekszik, mint bármely polinom egy elég nagy mérethez n, de a bemenet méretének nagyon nagynak kell lennie, hogy ne kis fokú polinom uralja.

A szuperpolinomiális időt igénylő algoritmus kívül esik a komplexitási osztályon. Cobham tézise azt állítja, hogy ezek az algoritmusok nem praktikusak, és sok esetben azok is. Mivel a P és NP osztályok egyenlőségének problémája nem megoldott, jelenleg nem ismertek olyan algoritmusok, amelyek NP-teljes feladatokat polinomiális időben oldanának meg.

Kvázipolinomiális idő

Algoritmusok kvázi-polinomiális idő olyan algoritmusok, amelyek lassabban futnak, mint a polinomiális idő, de nem olyan lassan, mint az exponenciális idő algoritmusai. A kvázipolinomiális algoritmus legrosszabb futási ideje az c... Egy jól ismert klasszikus algoritmus egész szám faktorokká alakítására, nem kvázi polinom, mivel a futási idő nem ábrázolható így 2 O ((log ⁡ n) c) (\ displaystyle 2 ^ (O ((\ log n) ^ (c)))) néhány fix c... Ha a kvázipolinom idő algoritmus definíciójában a "c" konstans 1, akkor a polinomiális idő algoritmust kapjuk, ha pedig kisebb, mint 1, akkor a szublineáris idő algoritmust.

A kvázipolinomiális idő algoritmusok általában akkor merülnek fel, amikor egy NP-nehéz problémát egy másik problémává redukálnak. Például vehet egy NP-nehéz problémát, mondjuk a 3SAT-ot, és redukálhatja egy másik B problémára, de a probléma mérete 2 O ((log ⁡ n) c) (\ displaystyle 2 ^ (O ((\ log n) ^ (c))))... Ebben az esetben a redukció nem bizonyítja, hogy a B probléma NP-nehéz, az ilyen redukció csak azt mutatja, hogy B-re nincs polinomiális algoritmus, hacsak nincs kvázipolinomiális algoritmus a 3SAT-hoz (és akkor minden -problémához). Hasonlóképpen - vannak olyan problémák, amelyekre ismerünk kvázipolinom idejű algoritmusokat, de amelyekre polinomiális idejű algoritmusok ismeretlenek. Ilyen problémák a közelítő algoritmusokban jelennek meg. Híres példa erre az irányított Steiner-probléma, amelyre létezik egy közelítő kvázipolinomiális algoritmus közelítési együtthatóval O (log 3 ⁡ n) (\ displaystyle O (\ log ^ (3) n))(ahol n a csúcsok száma), de a polinomiális idejű algoritmus megléte nyitott probléma.

Nehézségi osztály QP A kvázipolinomiális időalgoritmusokkal kapcsolatos összes problémát tartalmazza. DTIME-ban a következőképpen definiálható

QP = ⋃ c ∈ N DTIME (2 (log ⁡ n) c) (\ displaystyle (\ mbox (QP)) = \ bigcup _ (c \ in \ mathbb (N)) (\ mbox (DTIME)) (2 ^ ((\ log n) ^ (c))))

Kapcsolat NP-teljes problémákkal

A komplexitáselméletben a P és NP osztályok közötti egyenlőség megoldatlan problémája azt kérdezi, hogy az NP osztályból származó összes feladatnak van-e algoritmusa polinomiális időben történő megoldásra. Minden jól ismert algoritmus NP-teljes problémákra, mint például a 3SAT, exponenciális idővel rendelkezik. Ezenkívül van egy hipotézis, hogy sok természetes NP-teljes probléma esetén nincs szubexponenciális végrehajtási idővel rendelkező algoritmus. Itt a "szubexponenciális időt" az alábbi második definíció értelmében vettük. (Másrészt sok gráfelméleti probléma, amelyet természetesen szomszédsági mátrixok reprezentálnak, megoldható szubexponenciális időben, egyszerűen azért, mert a bemenet mérete megegyezik a csúcsok számának négyzetével.) Ez a hipotézis (a k-SAT probléma esetén ) úgy is ismert mint exponenciális idő hipotézis... Mivel azt feltételezi, hogy az NP-teljes problémáknak nincs kvázipolinomiális idejű algoritmusa, néhány nem közelítési eredmény a közelítő algoritmusok tartományában feltételezi, hogy az NP-teljes feladatoknak nincs kvázipolinom idő algoritmusa. Lásd például a jól ismert eredményeket a halmazlefedési probléma nem közelíthetőségére vonatkozóan.

Szubexponenciális idő

Term szubexponenciális idő A kifejezés annak kifejezésére szolgál, hogy egy bizonyos algoritmus végrehajtási ideje gyorsabban nőhet, mint bármely polinom, de lényegesen kisebb marad, mint az exponenciális. Ebben az értelemben a szubexponenciális idő algoritmusaival kapcsolatos problémák jobban alakíthatók, mint a csak exponenciális idejű algoritmusok. A "szubexponenciális" pontos meghatározása még nem általánosan elfogadott, és az alábbiakban bemutatjuk a két leggyakoribb definíciót.

Első meghatározás

Egy feladatot szubexponenciális idő alatt megoldottnak mondunk, ha egy olyan algoritmussal oldjuk meg, amelynek futási idejének logaritmusa kisebb, mint bármely adott polinom. Pontosabban, a feladatnak van szubexponenciális ideje, ha bármely ε> 0 esetén létezik olyan algoritmus, amely O (2 n ε) idő alatt megoldja a feladatot. Az összes ilyen probléma halmaza alkotja a komplexitási osztályt SUBEXP, ami DTIME-ban kifejezhető így.

SUBEXP = ⋂ ε> 0 DTIME (2 n ε) (\ displaystyle (\ text (SUBEXP)) = \ bigcap _ (\ varepsilon> 0) (\ text (DTIME)) \ left (2 ^ (n ^ (\ varepsilon) )) \ jobb))

Megjegyzendő, hogy itt ε nem része a bemeneti adatoknak, és minden ε-hez lehet saját algoritmus a probléma megoldására.

Második meghatározás

Egyes szerzők a szubexponenciális időt a futási időként 2 o ( n). Ez a definíció hosszabb futási időt tesz lehetővé, mint az első definíció. Ilyen szubexponenciális időalgoritmusra példa az egész számok faktorokká alakításának jól ismert klasszikus algoritmusa, az általános számmező szita módszer, amely kb. 2 O ~ (n 1/3) (\ displaystyle 2 ^ ((\ tilde (O)) (n ^ (1/3)))), ahol a bejárat hossza n... Egy másik példa a jól ismert algoritmus gráfizomorfizmus problémák, melynek működési ideje az 2 O ((n log ⁡ n)) (\ displaystyle 2 ^ (O ((\ sqrt (())) n \ log n)))).

Megjegyzendő, hogy van különbség, hogy az algoritmus szubexponenciális a csúcsok vagy az élek számában. V paraméterezett komplexitás ez a különbség kifejezetten jelen van egy pár, egy megoldhatósági probléma és egy paraméter megadásával k. SUBEPT Az összes olyan paraméterezett probléma osztálya, amely szubexponenciális időben fut be k polinomhoz pedig in n :

SUBEPT = DTIME (2 o (k) ⋅ poly (n)). (\ displaystyle (\ text (SUBEPT)) = (\ text (DTIME)) \ left (2 ^ (o (k)) \ cdot (\ text (poly)) (n) \ right).)

Pontosabban, a SUBEPT az összes paraméterezett feladat osztálya (L, k) (\ displaystyle (L, k)) amelyre van egy kiszámítható függvény f: N → N (\ displaystyle f: \ mathbb (N) \ to \ mathbb (N)) val vel f ∈ o (k) (\ displaystyle f \ in o (k))és egy algoritmus, amely megoldja L alatt 2 f (k) ⋅ poly (n) (\ displaystyle 2 ^ (f (k)) \ cdot (\ text (poly)) (n)).

2. fejezet Algoritmusok összetettsége.

2.1 Algoritmusok idő és számítási bonyolultsága.

Az algoritmus időbeli összetettsége (T(N) , ahol N- a feladat mérete) az algoritmus lépésekben mért végrehajtási ideje (az eredmény eléréséhez végrehajtandó algoritmus utasításai). Vagyis ennyi elemi műveletek alkotják a probléma megoldásának algoritmusát (: =,<>, =, +, -, *, /; és vagy nem xor; hívás, visszatérés).

Az időbonyolításnak három típusa van, amelyek a probléma megoldása során a bemeneti adatok kombinációjától függenek (a bemeneti adatok ekvivalenciája, ritkasága, rendezettsége és egyéb tulajdonságai).

https://pandia.ru/text/78/183/images/image002_151.gif "width =" 178 height = 60 "height =" 60 ">

Esemény T(N)= C* N2 négyzetmátrixra alkalmazható.

Az elemi műveletek ebben az esetben a "+" és a "*" kombinációi.

Ha az eredeti mátrix az azonosság, akkor a legjobb esetet kapjuk.

Ha a mátrixban az elemek fele 0, fele 1, akkor az Átlagos esetet kapjuk.

Állandó VAL VEL, amely pontosan nem fejezhető ki, külső tényezők hatását jellemzi az algoritmusok végrehajtási idejére (számítógép sebessége, fordítási sebessége). Ezért az időegységek használata az algoritmusok időbonyolultságának becslésére nem teljesen helyes. Ebben az esetben a mátrix-vektor szorzási algoritmus időbonyolultságát arányosnak mondjuk N2 .

2.2 Oés Ω jelölések.

Az időbonyolultság viselkedésének jellege növekedéskor N (N® ¥ ) hívott az algoritmus aszimptotikus összetettsége.

Az aszimptotikus komplexitás növekedési ütemének leírására használjuk O-jelölés. Amikor azt mondjuk, hogy egy algoritmus időbonyolultsága nagyságrendileg N2 :

T(N)= O(N2 )= O(f(N)),

Ekkor feltételezzük, hogy vannak pozitív állandók C, n0 =const (C>0), olyan, hogy mindenkinek N ³ N0 az egyenlőtlenség érvényesül

T(N) £ C* f(N)

Ez a komplexitásbecslés felső korlátja.

2. példa:

Legyen Т (0) = 1, Т (1) = 4, ..., Т (N)=(N+1) 2, akkor ennek az algoritmusnak az időbonyolultsága növekedési sorrendű T(N)= O(N2 ).

Ezt mindenkinél meg lehet mutatni N > n0 nál nél n0 = 1, C = 4 az (1) egyenlőtlenség érvényesül.

(N+1)2 £ 4* N2

3. példa:

Ha az időbonyolultságot polinomként írjuk fel

T(N)= C1 N2 + C2 N+ C3 ,

akkor egy ilyen algoritmus bonyolultsági sorrendje a polinom maximális eleme fokszámának többszöröse, mivel az növekszik a leggyorsabban N® ¥ :

T(N)= O(N2 ).

Például:

3 n2 +5 n+1 £ 5 n2

" n ³ 1

4. példa:

Ha valamelyik algoritmus összetettségi többszörös 3 n, akkor kimutatható, hogy a sebesség növekedési sorrendje nem lehet többszöröse O(2 n):

T(N)=3 n¹ O(2 n).

Legyenek állandók C, n0 , így a következő egyenlőtlenség teljesül:

3n £ C*2 n, n > n0 .

Innen kapjuk:

VAL VEL³ (3/2)2, n > n0 .

De azzal n® ¥ nem létezik ilyen állandó VAL VEL ami kielégítené ezt az egyenlőtlenséget.

A komplexitás felső határa mellett az időbeli komplexitás növekedési ütemének alsó határa is van:

T(N) ³ W(f(N))

A (2) egyenlőtlenség azt jelenti, hogy van valamilyen állandó VAL VEL amihez at N® ¥ idő összetettsége

T(N) ³ C* f(N).

Figyelembe véve a T (N) (aszimptotikus időbonyolultság) pontos meghatározásának bonyolultságát, a kiindulási adatok nagyságától függően, a gyakorlatban az algoritmus időbonyolultságának alsó és felső határát alkalmazzuk:

T(N) = q (f(N))

Az állandó értékétől függően VAL VEL az algoritmus komplexitásának növekedési üteme jelentősen változhat.

5. példa:

Írjuk fel az időbonyolultságot a képlettel

T (N) = 3n2 –100n + 6 = O (n2)

3n2> 3n2 –100n + 6, n³ 1, C = 3.

Ha C1» 0 (C1 = 0,00001), akkor az egyenlőtlenség

10-5 n2 > 3 n2 –100 n+6, n³ 1

nem végezték ki.

De kimutatható, hogy a komplexitás növekedési sorrendje

3n2 –100n + 6¹ TOVÁBB).

C*N< 3N2, N>C.

3n2 –100n + 6 = (n2)

C=2.29, n ³ n0.

2.99* n2 < 3 n2 –100 n+6

Kimutatható, hogy az alsó korlát

3 n2 –100 n+6 ¹ W(n3 ) nál nél C = 1.

Egyenlőtlenség 3 n2 –100 n+6 ³ n3 nem végezték ki.

3 n2 –100 n+6= W(n)

C1 = , n> n0 .

https://pandia.ru/text/78/183/images/image007_89.gif "width =" 305 "height =" 247 src = ">

f1 (N)=100 n2

f2 (N)=5 n3

n0 =20 – kritikus pont.

Egy másik ok, amiért előnyben részesítjük az alacsonyabb bonyolultságú algoritmusokat, hogy minél kisebb a bonyolultsági sorrend, annál nagyobb a probléma mérete. N gyakorlatilag megoldható.

0 "style =" margin-left: 5.4pt; border-collapse: collapse; border: none ">

n!

6. példa:

Nem szabad megfeledkezni arról, hogy az algoritmusok összetettségének nagyobb növekedési sorrendje általában kisebb állandóval rendelkezik. C1 az állandóval jellemezhető kis komplexitási növekedési sorrendhez képest C2.

Ebben az esetben egy gyorsan növekvő összetettségű algoritmus előnyösebb lehet kis adatméretű problémák megoldására ( n® 0 ).

Adjunk meg öt algoritmust ugyanazon probléma megoldására, amelyek nehézségekkel küzdenek:

A1: 100 N

A2: 100 N* logN

A3: 10 N2

A4: N3

A5: 2 N

Aztán a problémákra N=2 ¸ 9 gyorsabb lesz A5 ( f(N) ~ 4 ¸ 512 ). Más algoritmusok, ha helyettesítik, lényegesen alacsonyabb arányt adnak.

Nál nél N=10 ¸ 58 Az A3 preferált.

Nál nél N=59 ¸ 1024 a leghatékonyabb az A2 lesz.

Nál nél N>1024 Az A1 előnyös.

Több egymás után vagy párhuzamosan futó algoritmusból álló programok esetén a bonyolultságot a következőképpen becsüljük meg: összeg szabályés művek szabálya.

Összeg szabály : Legyen a program két, egymás után futó Р1 és Р2 algoritmusból, amelyek nehézségei vannak meghatározva. O(f(n)) és O(g(n)) illetőleg. Ekkor a teljes program időbonyolultságát az egyes algoritmusok időbonyolultságának összegeként határozzuk meg:

T(n) = T1 (n)+ T2 (n)

Általában a következőket kapjuk:

T (n)Þ O (max. f (n), g (n))

Munkavégzés szabálya: Legyen két párhuzamos végrehajtó algoritmusból álló program időbonyolultsága összetettségi sorrendben O(f(n)) és O(g(n)) ennek megfelelően az egyes algoritmusok időbonyolultságának szorzataként definiálható:

T(n) = T1 (n)* T2 (n)

Általánosságban:

T(n) Þ O(f(n)* g(n))

Logaritmusok.

2.3. Rekurzió.

A rekurzív algoritmusok bonyolultságát nem könnyű megbecsülni az algoritmikus struktúrák egymásba ágyazása miatt

f(n) Þ f(n* f(n-1))

Például az n algoritmus rekurzív kiértékeléséhez! A komplexitás a rekurzióban szereplő egyes algoritmusok összetettségétől függ.

Általánosságban T(n) ~ O(N).

Más rekurzív algoritmusok általában időben bonyolultak T(n) ~ O(an) , ahol a= const, ami egy nem rekurzív algoritmus összetettségénél nagyobb teljes komplexitást eredményez ugyanazon probléma megoldására.

2.4 Algoritmusok és programok komplexitásának becslése.

2.4.2 Függőség-helyreállítási algoritmusok.

Egyes esetekben a program felépítése ismeretlen, és csak különböző méretű bemeneti adatok esetén tudja meghatározni a működési idejét. T(N) (mp)

A program komplexitásának, a függvénynek analitikus függőségének megalkotása T(N) bizonyos időközönként [ Nmin, Nmax] ... Ezután valamilyen analitikus függvény talált görbéjének közelítését hajtjuk végre a függvény paramétereinek megváltoztatásával és a közelítési hiba becslésével.

Általában az időbonyolítás jól ismert függvényeit használják ilyen függvényként: O(n!), O(XN), O(NX), O(logN), O(https://pandia.ru/text/78/183/images/image010_72.gif "width =" 307 "height =" 225 src = "> A programon végzett kísérlet eredményeként elkészült egy táblázat az időbeli nehézségekről kapott:

A függvény közelítésének keresése eredményeként a következő analitikai függést kaptuk:

https://pandia.ru/text/78/183/images/image012_68.gif "width =" 321 "height =" 143 src = ">

2. példa:

Gyakran előfordul, hogy ugyanannak az algoritmusnak a működési idejét a probléma nagyságán kívül más, a felhasználó által megadott paraméterek is befolyásolják.

Ebben az esetben egy közelítő függvénycsaládot hozunk létre, és analitikusan meghatározzuk az algoritmus összetettségét.

Munkaintenzitás "href =" / szöveg / kategória / trudoemkostmz / "rel =" bookmark "> munkaintenzitás (munkaidő).

Az algoritmus polinomiális vagy exponenciális jellege invariáns a bemeneti adatok formájától (bináris, decimális vagy egyéb számrendszer).

Egy algoritmust polinomnak nevezünk, ha futási idejét, azaz időbonyolultságát felülről egy bizonyos fokú polinom határolja. T(N)= O(Nm) ... Ekkor minden probléma, amelyet egy ilyen algoritmus megold, a problémák P-osztályát alkotja. Ezek a feladatok állítólag benne vannak az R-ben.

Problémák az exponenciális időbonyolítással ( T(N)= O(KN) ) nem szerepelnek az R-ben.

Megjegyzés : Kimutatható, hogy a lineáris komplexitású problémák benne vannak a P-ben

T(N)= O(N1 )

Mutassuk be az NP-problémák egy osztályát, amely polinomiális időben is megoldható egy nem determinisztikus algoritmus segítségével.

Határozzuk meg az algoritmus állapotát az éppen végrehajtott parancs címének és az összes változó értékének halmazaként, amely ekvivalens a folyamat állapotának vektorával. Ezért a legtöbb algoritmus determinisztikus, azaz minden állapothoz csak egy megengedett következő állapot van (beleértve a feltétel- és kiválasztási műveleteket is). Ez azt jelenti, hogy egy ilyen algoritmus egyszerre csak egy dolgot tud végrehajtani.

V nem determinisztikus algoritmus (NDA) egy adott állapothoz több megengedett következő állapot is lehet, azaz egy ilyen algoritmus egyszerre több operátort is végrehajthat.

Az NDA nem véletlenszerű vagy valószínűségi algoritmus. Ez egy sokféle állapotú algoritmus (ez egyenértékű egy probléma megoldásával párhuzamosan sok lehetőséggel).

Példa:

Egy determinisztikus algoritmus (DA) ezt a problémát szekvenciálisan oldaná meg (az összes opció felsorolása, összehasonlítás a K0 optimalitási feltétellel, amíg az A0 alternatívát választja).

Az NDA egyszerre (párhuzamosan) megkaphatja az összes alternatívát, és összehasonlíthatja a K0-val, minden alternatívához külön folyamatként másolva önmagát, amely önállóan hajtódik végre.

Ebben az esetben, ha valamelyik másolat azt észleli, hogy hibás eredmény érkezett, vagy az eredmény nem jött létre, akkor leállítja a végrehajtását. Ha a másolat olyan megoldást talál, amely kielégíti a K0-t, akkor sikert hirdet, és az összes többi másolat leáll.

Hogy. Az NDA-t három paraméter jellemzi:

1. választás- többértékű függvény, amelynek értékei az S halmaz elemei;

2. kudarc az algoritmus másolatának leállását okozza;

3. siker hatására az algoritmus minden másolata leáll, és eredményt produkál.

Nyilvánvalóan egyetlen fizikai eszköz sem képes korlátlan, nem determinisztikus viselkedésre, ami azt jelenti, hogy az NDA elméleti módszer.

A polinomiális NDA használatával megoldható problémák az NP-problémák egy osztályát alkotják.

2.5.2 NP- nehéz ésNP-Végezze el a feladatokat.

P-ben a probléma az NP- nehéz ha létezik a megoldásának polinomja DA (PDA), amivel az NP-ben szereplő összes problémára megoldást kaphatunk. Vagyis egy ilyen probléma NP-nehéz, ha legalább olyan nehéz, mint bármely NP-beli probléma.

Az NP-hez tartozó NP-nehéz problémát ún NP-teljes feladat. Az ilyen problémák nem kevésbé bonyolultak, mint bármely NP probléma. Sőt, a PDA megléte egy NP-kemény vagy NP-teljes probléma esetén azt jelenti, hogy a P és az NP osztályok egybeesnek, azaz a 3. osztály összes problémája megoldható egy gyors algoritmussal.

Annak bizonyításához, hogy a probléma NP-nehéz, meg kell mutatni, hogy ha van a problémára PDA, akkor azzal más PDA-megoldást lehet kapni az NP-ben szereplő problémákra.

Annak megállapításához, hogy egy probléma NP-teljes, be kell bizonyítani, hogy NP-hez tartozik.

Az algoritmusok elméletének egyik legfontosabb algoritmusa az az ötlet, hogy egy algoritmust kell használni egy probléma megoldására, hogy egy másik megoldást kapjunk.

1. definíció: Az Р1 feladat Р2 feladattá alakul, ha az Р1 feladat bármely speciális esete polinomiális időben átalakítható az Р2 feladat valamilyen speciális esetévé. Ekkor az Р1 megoldás polinomiális időben megkapható az Р2 feladat adott esetének megoldásából.

https://pandia.ru/text/78/183/images/image024_39.gif "width =" 158 height = 56 "height =" 56 ">

Például:

f2 (xi)=(x1 Ú x2 ) Ù ( ) Ù ()

nem kivitelezhető, hiszen bármelyikre xi f2 (xi)= hamis.

Tétel :

A kielégítési probléma NP-teljes.

xi kiválasztás (igaz, hamis)

ha E (x1, x2,…, xN), akkor siker

más kudarc

A P1 probléma P2-vé való transzformációjával kimutatható, hogy a kielégítési probléma korlátozott esete is NP-teljes.

K-megvalósíthatóság .

A K-elégedettség azt jelenti, hogy a CNF-ben szereplő bármely záradék legfeljebb K logikai változót tartalmaz.

A minimális eset K = 3. Egy CNF-ben ábrázolt Boole-függvényhez polinomiális időben megtalálhatjuk a függvényt E * (x2) amelyek mindegyik tagmondatban legfeljebb három változót tartalmaznak. Azután E megvalósítható, ha kivitelezhető E *.

E* (x1 , x2 ,…, xn) ® E* (xi)

Ehhez a záradéksorrend csökkentésének módszerét alkalmazzuk

(a1 Ú a2 Ú … Ú ak)=(a1 Ú a2 Ú z) Ù (a3 Ú a4 Ú … Ú ak Ú )

Iteratív bontási folyamat alkalmazásával megkaphatjuk E*.

Keressen megoldási algoritmust E* egyszerűbb, mint a funkciók E... De ugyanakkor, miután bebizonyította a megvalósíthatóságot E*, bizonyítjuk az eredeti függvény kielégíthetőségét E.

Speciális eset: K = 2-nél a függvény E belép R.

Példák az NP-osztály problémáira is grafikon problémák :

1) Egy irányítatlan gráf klikkjeinek maximumának meghatározása (NP-nehéz probléma).

2) Egy teljes részgráf meghatározásának problémája (NP-teljes probléma).

3) Az L számosság csúcsfedésének meghatározása irányítatlan gráf esetén (NP-teljes feladat).

4) Irányítatlan gráf maximális csúcsfedésének meghatározása (NP-nehéz feladat).

5) Hamilton-ciklus létezésének meghatározása gráfra (NP-teljes probléma).

6) Utazó értékesítő probléma: Az optimális mozgás meghatározása a grafikon mentén minden csúcsban egyetlen bejegyzéssel (NP-nehéz feladat).

7) Ütemezési probléma (NP-teljes probléma).

2.6 Algoritmikusan megoldhatatlan problémák

Ossza meg a problémákat egyetlenés tömeges.

Például:

5 + 7 =? Egyetlen probléma.

x + y =? Óriási probléma.

A paradox objektumok megszerzésére szolgáló algoritmusok, vagy olyan problémák megoldása, amelyek paradox objektumok létezéséhez vezetnének, alapvetően megoldhatatlanok legyenek.

Például a paradoxonok a következők:

1. példa:

Hilbert 10. problémája.

D. Hilbert 1901-ben a diofantusi egyenletek megoldása során egy feladatot terjesztett elő, amely így hangzik:

Keress egy olyan algoritmust, amely egy tetszőleges Diofantusz-egyenlet egész számú megoldását határozza meg

F(x, y, …)=0

Ez egy polinom egész kitevőkkel és egész együtthatókkal az ismeretlenekre

anxn + an-1xn-1 +… + a2x2 + a1x + a0 = 0

A fenti egyenletnek van egy sajátos megoldása, amely abból áll, hogy minden egész szám gyök xi egy osztó a0 ... Ahol a0 bomlik fel elsődleges tényezőkre, és ellenőrizze, hogy minden tényező megfelel-e a gyökérnek.

1970-ben a leningrádi matematikus, Yu. Matiyasevics matematikai úton bebizonyította, hogy a diofantini egyenlet általános formában történő megoldásának algoritmikusan lehetetlen.

2. példa:

Fermat-tétel:

Nincsenek ilyen egész számok a, b, s, n (n>2) amelyre az egyenlőség

an + bn = cn

Ez a tétel számos értékre bizonyítást nyert nés speciális esetekre igazolt, de a tétel általános bizonyítása még nem készült el.

3. példa:

Goldbach problémája.

H. Holbach 1742-ben Eulernek írt levelében megfogalmazta a problémát:

Bizonyítsuk be, hogy minden egész szám N³ 6 három prím összegeként ábrázolható

N= a+ b+ c

Ez azt jelenti, hogy meg kell találnia egy olyan algoritmust, amely bármilyen egész számot lehetővé tesz N³ 6 találjon legalább egy bontást három egyszerű tagra.

Euler gyakori megoldást javasolt erre a problémára: az egyenletes N ez a probléma megoldható, és egyenértékű a két egyszerű tagra bontással.

I. Vinogradov 1937-ben bebizonyította, hogy páratlan N három egyszerű kifejezés található, de páros számokra még nem sikerült megoldást találni.

O (1) - Egy programban a legtöbb műveletet csak egyszer vagy csak néhány alkalommal hajtják végre. Állandó bonyolultságú algoritmusok. Bármilyen algoritmus, amely mindig ugyanannyi időt igényel, függetlenül az adatok méretétől állandó komplexitás.

TOVÁBB) - Program futási ideje lineárisanáltalában amikor a bemenet minden elemét csak lineárisan kell feldolgozni.

O (N 2), O (N 3), O (N a) - Polinom komplexitás.

O (N 2) - kvadratikus komplexitás, O (N 3) - köbös komplexitás

O (Napló (N)) - Mikor fut a program logaritmikus, a program sokkal lassabban kezd el futni az N növekedésével. Ilyen futási idők általában azoknál a programoknál találhatók, amelyek egy nagy problémát apróra osztanak és külön oldanak meg.

O (N * log (N)) - Egy ilyen futási időnek megvannak azok az algoritmusai, amelyek ossza fel a nagy problémát kicsire, majd miután megoldotta őket, kombinálja a megoldásaikat.

O (2 N) = Exponenciális komplexitás. Az ilyen algoritmusok leggyakrabban a nyers erőnek nevezett megközelítésből származnak.

A programozónak képesnek kell lennie az algoritmusok elemzésére és összetettségük meghatározására. Az 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 konstans 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.
i esetén: = 1-től N-ig
Kezdődik
...
Vége;

Ennek az algoritmusnak a bonyolultsága O (N), hiszen a ciklus törzsét N-szer hajtjuk végre, és a hurok törzsének összetettsége O (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.
i esetén: = 1-től N-ig
j esetén: = 1-től N-ig
Kezdődik
...
Vége;
Ennek a programnak a bonyolultsága O (N 2).

Létezik egy algoritmus bonyolultságának elemzésének két módja: alulról felfelé (a belső irányítási struktúráktól a külsőkig) és ereszkedő (külsőről és belsőről).

O (H) = O (1) + O (1) + O (1) = O (1);
O (I) = O (N) * (O (F) + O (J)) = O (N) * O (feltételek dominánsai) = O (N);
O (G) = O (N) * (O (C) + O (I) + O (K)) = O (N) * (O (1) + O (N) + O (1)) = O (N 2);
O(E)=O(N)*(O(B)+O(G)+O(L))=O(N)*O(N2)=O(N3);
O (D) = O (A) + O (E) = O (1) + O (N 3) = O (N 3)

Ennek az algoritmusnak a bonyolultsága O (N 3).

Általános szabály, hogy a program futási idejének körülbelül 90%-a igényel ismétléseket, és csak 10%-a kerül kiszámításra közvetlenül. A programok összetettségének elemzése megmutatja, hogy mely töredékek esnek ebbe a 90%-ba – ezek a legnagyobb beágyazási mélység ciklusai. Az ismétlések beágyazott hurkokként vagy beágyazott rekurzióként szervezhetők.

Ezeket az információkat a programozó felhasználhatja egy hatékonyabb program elkészítéséhez az alábbiak szerint. Először is megpróbálhatja csökkenteni az ismétlések egymásba ágyazásának mélységét. Ezután érdemes megfontolni a legmélyebb hurkokban lévő utasítások számának csökkentését. Ha a végrehajtási idő 90%-a a belső hurkok végrehajtása, akkor ezekben a kis szakaszokban 30%-kal csökkentve a teljes program végrehajtási idejét 90% * 30% = 27% csökkenti.

Ez a legalapvetőbb példa.

A matematikának külön fejezete foglalkozik az algoritmusok hatékonyságának elemzésével, és nem is olyan egyszerű megtalálni a legoptimálisabb függvényt.

Értékeljük bináris keresési algoritmus egy tömbben - dichotómia.

Az algoritmus lényege: a tömb közepére megyünk, és megkeressük a kulcs és a középső elem értékének megfelelőségét. Ha nem találunk egyezést, akkor megnézzük a relatív kulcsméretet és a középső elemértéket, majd ugorjunk a lista alsó vagy felső felére. Ebben a felében ismét megkeressük a közepét, és ismét összehasonlítjuk a kulccsal. Ha nem működik, oszd el újra az aktuális intervallumot felével.

függvénykeresés (alacsony, magas, kulcs: integer): egész szám;
var
mid, adatok: integer;
kezdődik
míg alacsony<=high do
kezdődik
közép: = (alacsony + magas) div 2;
adatok: = a;
ha kulcs = adat akkor
keresés: = mid
más
ha kulcs< data then
magas: = közép-1
más
alacsony: = közép + 1;
vége;
keresés: = - 1;
vége;

A ciklus első iterációja a teljes listával foglalkozik. Minden következő iteráció felére csökkenti az allista méretét. Tehát az algoritmushoz tartozó lista méretei:

n n / 2 1 n / 2 2 n / 2 3 n / 2 4 ... n / 2 m

A végén lesz olyan m egész szám, hogy

n / 2 m<2 или n<2 m+1

Mivel m az első egész szám, amelyre n / 2 m<2, то должно быть верно

n / 2 m-1> = 2 vagy 2 m =

Ebből következik, hogy
2 m = Vegyük az egyenlőtlenség egyes részeinek logaritmusát, és megkapjuk
m = Az m érték a legnagyobb egész szám, amely =<х.
Tehát O (log 2 n).

Általában a megoldandó problémának van egy természetes "mérete" (általában az általa feldolgozott adatmennyiség), amelyet N-nek nevezünk. Végső soron egy kifejezést szeretnénk kapni arra az időre, amelyre egy programnak szüksége van az N méretű adatok feldolgozásához. Általában nem érdekel minket az átlagos eset - a program várható futási ideje "tipikus" bemeneteken, és a legrosszabb eset a program várható futási ideje a legrosszabb bemeneti adatokon.

Egyes algoritmusok jól tanulmányozottak abban az értelemben, hogy ismertek az átlagos és a legrosszabb esetek pontos matematikai képletei. Az ilyen képleteket a programok gondos tanulmányozásával dolgozzák ki, hogy a matematikai jellemzők alapján megtalálják a futási időt, majd elvégezzék azok matematikai elemzését.

Számos fontos oka van az ilyen típusú elemzésnek:
1. A magas szintű nyelven írt programokat gépi kódokká fordítják le, és nehéz lehet megérteni, mennyi ideig tart egy adott operátor végrehajtása.
2. Sok program nagyon érzékeny a bemeneti adatokra, és teljesítményük nagyban függhet tőlük. Az átlagos eset matematikai fikciónak bizonyulhat, amely nem kapcsolódik a program használatának adataihoz, és a legrosszabb eset nem valószínű.

A válogatásban nagy szerepe van a legjobb, átlagos és legrosszabb eseteknek.
Rendezési számítás

Az O-komplexitás elemzése számos gyakorlati alkalmazásban elterjedt. Ennek ellenére világosan meg kell értenünk a korlátait.

NAK NEK a megközelítés fő hátrányai a következőket tartalmazzák:
1) összetett algoritmusok esetén az O-becslések megszerzése általában vagy nagyon időigényes, vagy szinte lehetetlen,
2) gyakran nehéz "átlagosan" meghatározni a bonyolultságot,
3) Az O-becslések túl durvák ahhoz, hogy az algoritmusok közötti finomabb különbségeket tükrözzék,
4) Az O-analízis túl kevés információt (vagy egyáltalán nem) ad az algoritmusok viselkedésének elemzéséhez kis mennyiségű adat feldolgozásakor.

Az O-jelölés bonyolultságának meghatározása korántsem triviális. A bináris keresés hatékonyságát nem a hurkok egymásba ágyazásának mélysége határozza meg, hanem az egyes egymást követő próbálkozások kiválasztásának módja.

Egy másik nehézség az „átlagos eset” meghatározása. Ez általában meglehetősen nehézkes az algoritmus működési feltételeinek előrejelzésének lehetetlensége miatt. Néha egy algoritmust egy nagy, összetett program részeként használnak. Néha a hardver és/vagy operációs rendszer, vagy a fordító egyes összetevőinek hatékonysága jelentősen befolyásolja az algoritmus bonyolultságát. Gyakran ugyanaz az algoritmus sok különböző alkalmazásban használható.

Az algoritmusok „átlagosan” időbeli összetettségének elemzésével kapcsolatos nehézségek miatt gyakran meg kell elégedni a legrosszabb és legjobb esetekre vonatkozó becslésekkel. Ezek a becslések lényegében meghatározzák az "átlagos" nehézség alsó és felső határát. Valójában, ha nem lehetséges "átlagosan" elemezni az algoritmus összetettségét, akkor marad az egyik Murphy-törvény követése, amely szerint a legrosszabb esetre kapott becslés jó közelítésként szolgálhat az "átlagosan" bonyolultságra. ".

Az O-függvények fő hátránya talán az, hogy túl durvák. Ha az A algoritmus 0,001 * N s alatt hajt végre valamilyen feladatot, míg a B algoritmussal történő megoldásához 1000 * N s, akkor B milliószor gyorsabb, mint A. Ennek ellenére A és B azonos időbonyolítással O (N).

Az előadás nagy részét az algoritmusok időbeli összetettségének elemzésére szánták. Vannak a komplexitásnak más formái sem, amelyeket nem szabad elfelejteni: a térbeli és intellektuális komplexitás.

A térbeli komplexitást, mint egy program futtatásához szükséges memória mennyiségét már korábban említettük.

Egy algoritmus intellektuális komplexitásának elemzése során az algoritmusok érthetőségét és fejlesztésük összetettségét vizsgáljuk.

A komplexitás mindhárom formája általában összefügg. Egy jó időbeli komplexitásbecsléssel rendelkező algoritmus kidolgozásakor jellemzően fel kell áldozni annak térbeli és/vagy intellektuális komplexitását. Például a gyors rendezési algoritmus lényegesen gyorsabb, mint a minta rendezési algoritmus. A rendezési sebesség növeléséért járó fizetés a rendezéshez szükséges több memóriában fejeződik ki. A gyors rendezéshez további memória szükségessége több rekurzív híváshoz kapcsolódik.

A gyorsrendezés is intelligensebben összetettebb, mint a beszúrásos rendezés. Ha száz embert kér meg egy objektumsorozat rendezésére, akkor valószínűleg a legtöbbjük egy minta rendezési algoritmust használ. Valószínűtlen az sem, hogy bármelyikük is használja a gyorsválogatást. A gyorsrendezés nagyobb intellektuális és térbeli bonyolultságának okai nyilvánvalóak: az algoritmus rekurzív, leírható, meglehetősen nehéz, az algoritmus hosszabb (értsd a program szövegét), mint az egyszerűbb rendezési algoritmusok.

Ugyanazon probléma megoldására gyakran több algoritmus is kidolgozható. 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 ugyanazokat a bemeneti adatokat felhasználva, kevesebb számítási erőforrást (memória és idő) emésztve jut el a probléma megoldásához. Ez természetesen laza érvelés. 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, amelyek az algoritmus végrehajtásán mentek keresztül bizonyos bemeneti adatok esetében.

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.

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

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

Azonban az idő \ (T \) 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, és \ (t \) - a végrehajtó tulajdonsága.

Mivel \ (t \) egy adott végrehajtó esetén 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 határozott függvény \ (g (x) \) növekedési sorrendje \ (f (x) \) (írva \ (g (x) = \ mathcal (O) (f (x)) \)) ha \ (\ létezik c> 0: \: \ minden x> x_0, \, g (x) \ leq c f (x) \).

A bemeneti adatoktól függően az algoritmus különböző időpontokban futhat. Általában osztályozva átlagos komplexitás és összetettség legrosszabb esetben... Van egy függőség is Mennyiség bemeneti adatok \ (n \). Általában a \ (n \) növekedési sorrendje 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ú lesz \ (\ 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 \) alatt.

\ (S \) általában az aktuátortól is függ. Például, ha két végrehajtási egység 4, illetve 8 bájtos egész számokat támogat, akkor a 8 bájtos egész számok algoritmusának térbeli összetettsége kétszer akkora lesz, mint a 4 bájtos egész számok esetében. Ezért a térbeli komplexitást ugyanabban a növekedési sorrendben becsüljük meg.

Algoritmus bonyolultsági osztályai

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

A következő fő nehézségi osztályokat különböztetjük meg:

DTIME A Turing-gép véges idő (lépések száma) alatt talál megoldást egy feladatra. Az algoritmus aszimptotikáját gyakran megadják, például ha a futási idő növekedési sorrendje \ (T (n) = \ mathcal (O) (f (n)) \), akkor \ (DTIME (f ( n)) \) jelzi. 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ál megoldást a feladatra, azaz. \ (T (n) = \ matematikai (O) (2 ^ (n ^ k)) \), ahol \ (k \ in \ mathbb (N) \). \ (EXPTIME = DTIME (2 ^ (n ^ k)) \). DSPACE A Turing-gép véges mennyiségű további memória (cella) felhasználásával talál megoldást egy problémára. Az algoritmus aszimptotikáját gyakran megadják, tehát ha a memóriafelhasználás növekedési sorrendje \ (S (n) = \ mathcal (O) (f (n)) \), akkor \ (DSPACE (f ( n)) \) jelzi. L A Turing-gép logaritmikus térbeli komplexitású feladatra talál megoldást, pl. \ (S (n) = \ matematikai (O) (\ log n) \)... \ (L = DSPACE (\ log n) \). PSPACE A Turing-gép megoldást talál egy polinomiális térbeli komplexitású problémára, azaz \ (S (n) = \ mathcal (O) (n ^ k) \), ahol \ (k \ in \ mathbb (N) \ ). \ (PSPACE = DSPACE (n ^ k) \). KIFEJEZÉS A Turing-gép exponenciális térbeli komplexitású problémára talál megoldást, pl. \ (S (n) = \ matematikai (O) (2 ^ (n ^ k)) \), ahol \ (k \ in \ mathbb (N) \). \ (EXPSPACE = SZÓKÖZ (2 ^ (n ^ k)) \).

Ezen kívül vannak elméleti komplexitási osztályok, amelyek a koncepció alapján működnek meghatározatlan Turing gépek (TMT). Meghatározásuk egybeesik a fentiekkel, a Turing-gépet HMT-re cserélték, és a nevek előtagja N (például NP), kivéve az NTIME és NSPACE, ahol D helyett N.

Az LMT egy tisztán elméleti konstrukció, amely működési elvét tekintve hasonló az MT-hez, azzal a különbséggel, hogy mindegyik állapotra számos 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ámításokat végez mindenböl elágaz, és a lehető legkisebb lépésszámban kiválasztja azt az ágat, amelyik a megoldáshoz vezet.

Néha lehet hallani, hogy a kvantumszámítógépek a HMT megvalósításai. Bár ez bizonyos esetekben igaznak tűnhet, általában a HMT erősebb 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

Íme néhány példa az egyszerű algoritmusokra, és vegye figyelembe azok összetettségét.

Hatványozás

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. Írja be \ (n \) bináris jelöléssel
2. Ebben a rekordban cserélje ki az 1-et egy-egy KX betűpárra, a 0-t pedig egy K betűre
3. Húzd át a bal szélső KX párt
4. A kapott sztringet balról jobbra olvasva, a K betűvel találkozva, az eredményt négyzetre emelve és az X betűvel találkozva megszorozzuk az eredményt x-szel. Az elején az eredmény x.

Ebben az algoritmusban a szorzási műveletek száma megegyezik a bináris ábrázolásban szereplő számjegyek számával \ (n \) a legjobb esetben, és \ (2 (n-1) \) a legrosszabb esetben. Amúgy az időbonyolítás.

Az algoritmus hatékony megvalósításában gyakorlatilag nincs szükség többletmemóriára, és ez nem függ a bemeneti adatoktól, ezért a térbeli komplexitás \ (S (n) = \ mathcal (O) (1) \.

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

Egészek szorzása

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

Az első szorzót szekvenciálisan megszorozzuk kettővel, a másodikat pedig teljesen elosztjuk 2-vel. Az eredményeket két oszlopban rögzítjük, amíg a második 1 nem lesz.

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

Mivel az egész számok osztása és 2-vel való szorzása eltolással is végrehajtható, ez az algoritmus \ (2 \ log_2 n \) eltolási műveleteket ad, ahol \ (n \) a két szám közül a kisebbik. A legrosszabb esetben a \ (\ log_2 n - 1 \) összeadási műveleteket is megkapjuk. Amúgy az idő bonyolultsága \ (T (n) = \ matematikai (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. A \ (\ mathcal (O) (n) \) összeadási műveleteket igénylő „naiv” megvalósításhoz képest azonban 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 és 4 összeadási műveletet kaptunk. Referenciaként \ (\ log_2 (23) \ kb. 4,52 \).

Egy algoritmus összetettségének meghatározása

Az aszimptotikus elemzés során kapott komplexitási függvény becslését az algoritmus komplexitásának nevezzük.

Nem szabad megfeledkezni arról, hogy az algoritmus összetettségére többféle becslés létezik.

A komplexitási függvény aszimptotikája a műveleti komplexitás. Ezen kívül a következő nehézségi típusokat adhatja meg.

Ideiglenes A komplexitás az algoritmus futási idejének aszimptotikus becslése a hosszúságú bemeneti adatokon NS. Nyilvánvaló, hogy a számítási eljárások párhuzamosításának hiányában az algoritmus futási idejét egyértelműen a végrehajtott műveletek száma határozza meg. A műveletek időtartamát kifejező állandó együtthatók nem befolyásolják az időbonyolultság sorrendjét, így a műveleti és az időbonyolultság képlete gyakran egybeesik egymással.

Kapacitívösszetettség - az egyidejűleg létező skalárok számának aszimptotikus becslése az algoritmus hosszúságú bemeneti adatokon történő végrehajtása során NS.

Szerkezeti komplexitás - az algoritmusban lévő vezérlőstruktúrák számának és interpozíciójuk sajátosságainak jellemzője.

Kognitívösszetettség - az alkalmazott területek szakemberei általi megértéshez szükséges algoritmus elérhetőségének jellemzője.

Az aszimptotikumok típusai és jelölése

Az algoritmusok aszimptotikus elemzésénél a matematikai aszimptotikus elemzés jelölését szokás használni. Ebben az esetben az algoritmusok összetettségének három becslését (aszimptotikumát) veszik figyelembe, amelyeket a következőképpen jelölünk:

• 1) / (i) = O ^ (n))- aszimptotikusan pontos becslés a komplexitásfüggvény / («), vagy az algoritmus működési összetettségére;
• 2) /(n) = 0 (§ (n)) - aszimptotikusan éles felső korlát a komplexitásfüggvényhez / ( NS);
• 3) / (n) =? 2 (# (n)) aszimptotikusan pontos alsó korlátja a komplexitásfüggvénynek / ( NS).

Jelölés helyett C1 ^ (n)) nagyon gyakran az egyszerűbb o (^ ("))" o "betűt kis dőlt betűvel használják.

Magyarázzuk meg a képletek szemantikáját egy példán keresztül: ha / (i) = 0 (^ 2 (l)), akkor EZ azt jelenti, hogy a függvény g (n) = og2 (n) az f (α) komplexitásfüggvény aszimptotikusan pontos becslése. Valójában van egy kétpozíciós meghatározás állítás formájában:

Ha f (n)= @ (log 2 (")),

mo g (n)= log 2 (l) - aszimptotikusan éles becslés f (n)-re.

Megjegyzendő, hogy a konstans tényező nem befolyásolja az algoritmus összetettségének sorrendjét, ezért a logaritmus alapját kihagyjuk a logaritmikus komplexitás megadásakor, és egyszerűen csak a / (n) = @ (log (n)) szöveget írják, ami arra utal, hogy a logaritmusnak tetszőleges bázisa van egynél nagyobb.

Az aszimptotika formális definíciói

A munkaintenzitás függvény aszimptotikusan éles becslése val vel, val vel 2, n 0 úgy, hogy n> n 0 esetén az f (n) függvény állandó tényezőkig nem tér el a függvénytől g ( l), majd a függvény g (n) aszimptotikusan éles becslésnek nevezzük az f (x) függvényre.

• 3 s], s 2 e F, x-szel > 0, 2>-val 0:
  • (3 l 0 e K, l 0> 0: (/ l e K, l> l 0: 0 g (n) / (l) = 0 (? (L)),

ahol 9 ^, N az összes valós és természetes szám halmaza.

Aszimptotikusan éles felső határ a komplexitási funkcióhoz szóban a következőképpen definiálható: ha vannak pozitív számok val velés n 0 úgy, hogy n> n 0 esetén az f (n) függvény nem nő gyorsabban, mint a függvény g (n) egy állandó c tényezőig, majd a függvény g (n) a függvény aszimptotikusan éles felső korlátjának nevezzük Ap).

A definíció pontosabb formális jelölése a következő:

• 3 val vel e % c> 0:
  • (3 l 0 e X, l 0> 0: (/ l e K, l> l 0: 0 s? # (L))) 0 (g (n))

Aszimptotikusan éles alsó határ a komplexitási funkcióhoz szóban a következőképpen definiálható: ha vannak pozitív számok val velés n 0 úgy, hogy n > n 0 esetén az f (n) függvény nem nő lassabban, mint a függvény g (n)állandó tényezőig val vel, akkor a függvényt?(l) a függvény aszimptotikusan éles alsó korlátjának nevezzük

A definíció pontosabb formális jelölése a következő:

• 3 val vel e 9 ^, val vel > 0:
  • (3 i 0 e X, i 0> 0: (/ i e K, i > Én vagyok 0: 0 s? g (n)

/(Én vagyok) = 0. ^ (N))

Vegye figyelembe a következőket:

• 1) az aszimptotika formális definícióiban jelzett egyenlőtlenségeket általános esetben nem egy, hanem egy bizonyos függvényhalmaz elégítheti ki, gyakran végtelen taghalmazzal, ezért a konstrukciók Q (g (n)), 0 ^ (n))és 0. ^ (N)) szimbolizálják sok funkció amellyel az f (i) munkaintenzitás vizsgált függvényét hasonlítjuk össze; ennek értelmében az f (x) = 0 (q (x)), f (f0 = 0 (q max (n)), dj) = q 2 (q mn (x) alakú aszimptotika jelölésében ) a "= »Racionálisabb lenne az" e " jelet használni;
• 2) építmények (d ^ (n)), 0 ^ (n))és ? 1 ^ (n)), egyes mennyiségek megjelöléseként használva a következőképpen értelmezendő: minden olyan függvény, amely egybeesik, nem növekszik gyorsabban és nem növekszik lassabban g (n).

Az aszimptotikumok egybeesése és különbsége

Figyeljünk a következő tényre: az f (i) = 0 (? (I)) becslés felállítja f (i)-re mind a felső, mind az alsó becslést, mivel definíciója feltételezi az összefüggés érvényességét. c g (n)

Teljesen nyilvánvaló az aszimptotika következő tulajdonsága: ha a becslés φ (n) = © ^ (n)) létezik, akkor az egyenlőségek / ( NS) = 0 (^ (i)) és f (i) = 2 (# (i)), azaz. a munkaintenzitás felső és alsó becslése egybeesik egymással; ha f (i) = 0 (? max (i)) és φ (n) = C1 ^ mm (n)), és g max (n) фg m Ln (i), akkor nincs függvény g (n),úgy, hogy / (i) = 0 (? (i)).

A munkaintenzitás felső és alsó becslésének egybeesése a következő esetekben lehetséges:

• 1) a komplexitási függvény a bemeneti hossz összes értékére egy determinisztikus (nem véletlenszerű) függvény, pl. az elvégzett műveletek száma nem függ a kezdeti adatok értékeinek sajátosságaitól; ilyenek például a szorzási és osztási műveletek számának az ismeretlen mennyiségek számától való függésének függvényei a lineáris algebrai egyenletrendszerek IZ-dekompozíciós módszerrel történő megoldására szolgáló algoritmusban;
• 2) a munkaintenzitás függvény egy véletlen függvény, azaz. a végrehajtott műveletek száma a kezdeti adatok sajátosságaitól és (vagy) a beérkezésük sorrendjétől függ, és megadhatja a / t | n (i), / max (i) függvényeket, leírva a minimális és maximális számot. Az algoritmus végrehajtója által meghatározott i bemeneti hosszra végrehajtott műveletek, azonban mindkét függvénynek ugyanazok a dominánsai - például azonos rendű polinomok.

Három fontos szabályt kell szem előtt tartani, amikor a műveleti összetettség sorrendjének becsléséről van szó:

• 1) az állandó tényezők nem számítanak a komplexitási sorrend meghatározásánál, pl. 0 (к? g (n)) = 0 (g ("));
• 2) két függvény szorzatának összetettségi sorrendje egyenlő a komplexitásuk szorzatával, mivel az egyenlőség igaz:
• 0 (gl (i) §2(i)) = 0 (? | (i)) 0 (# 2 (i));
• 3) a függvények összegének összetettségi sorrendje megegyezik a kifejezések dominánsának sorrendjével, például: 0 (azaz + n 2 + n) = 0 (i 5).

A fenti szabályokban csak egy aszimptotikum szimbóluma 0 (»), de ezek minden aszimptotikus becslésre érvényesek - és 0( ) , és &.{ ).

Az elemi függvények halmazában megadható a funkcionális dominancia listája: if egy változó, a, b - numerikus állandókat, akkor a következő állítások igazak: I "Én dominálok!; Én! dominálok a "; a" uralja Zj "if a> b a n dominál NS b ha a> 1 bármely b e 9? ; n a uralja a / ha a> b i uralja log q (i) if a > 1.

Az átlagos munkaintenzitás becslése

A gyakorlatban re Egyes számításokban az M komplexitásának matematikai elvárásának f (n) becslése jelentős érdeklődésre tarthat számot, mivel az esetek túlnyomó többségében f (n) véletlen függvény. A véletlenszerű f (i) algoritmusok kísérleti vizsgálata során azonban további probléma merül fel - a tesztek számának kiválasztása az M megbízható becsléséhez. A javasolt megoldás a béta eloszlás / (i) közelítésén alapul. Ez egy nagyon konstruktív és sokoldalú technika. Azonban modern körülmények között, amikor a számítógép termelékenysége meglehetősen magas, sok esetben lehetőség nyílik a tesztek mennyiségének egyszerűbb megválasztására, az értékek aktuális változékonyságának szabályozására. f (n) - az értékeket addig értékeljük, amíg a becslések változékonysága kisebb lesz, mint a megadott hiba.

Egy algoritmus működési összetettségének becslése

Az algoritmus összetettsége a vezérlési struktúrák elemzése alapján határozható meg. A hurkok és rekurzív hívások nélküli algoritmusok állandó bonyolultságúak. Ezért az algoritmusok bonyolultságának meghatározása főként a hurkok és a rekurzív hívások elemzésére korlátozódik.

Fontolja meg az eltávolítási algoritmust Nak nek elemet a mérettömbből NS től mozgó tömbelemekből áll (k + 1) th to NS-edik egy pozícióval vissza a tömb elejére és csökkentve az elemek számát NS egységenként. A tömbfeldolgozási ciklus összetettsége az Ó (p-k) mivel a hurok törzsét (mozgatási műveletet) hajtják végre PC alkalommal, és a huroktest összetettsége 0 (1), azaz. állandó.

A vizsgált példában a bonyolultságot a 0 (") aszimptotika jellemzi, mivel az algoritmusban végrehajtott műveletek száma nem függ az adatértékek sajátosságaitól. A komplexitásfüggvény determinisztikus, és minden típusú aszimptotika egybeesik egymással: f (n) = Q (n-k), f (n) = 0 (n-k)és f (n) = Q (n- to). Ezt a tényt © () jelzése bizonyítja. Csak akkor használjon 0 (*) és/vagy 2 (*) értéket, ha ezek az aszimptotikumok eltérőek.

A hurok típusa (for, while, ismétlés) nem befolyásolja a bonyolultságot. 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. Az ismétlődő beágyazás a nehézségek növekedésének fő tényezője. Példaként bemutatjuk a jól ismert keresési és rendezési algoritmusok bonyolultságát egy méretű tömbhöz NS:

• összehasonlítási műveletek száma szekvenciális keresésben: 0 (i);
• összehasonlítási műveletek száma bináris keresésben: 0 (log 2 NS);
• az összehasonlítási műveletek száma az egyszerű cseremódszerben (buborékos rendezés): 0 (i 2);
• permutációs műveletek száma buborékos rendezésben: 0 (n 2);

Vegye figyelembe, hogy az egyszerű cseremódszerben az összehasonlítási műveletek száma aszimptotikus 0 (n 2), és a permutációs műveletek számának két különböző aszimptotikája van 0 (n 2)és 2 (0), mivel az összehasonlítások száma nem függ a rendezett adatok értékének sajátosságaitól, míg a permutációk számát pontosan ez a sajátosság határozza meg. A permutáció egyáltalán nem hajtható végre, - ha az adattömb kezdetben helyesen van rendezve, vagy a permutációk száma maximális lehet - kb. NS 2, - ha a rendezendő tömb eredetileg ellenkező irányban van rendezve.

Funkció neve g (n) az aszimptotikában f (n) = @ (t (n)) és f (a) = 0 (g (n)) a komplexitásfüggvény / (") az algoritmus jellemzésére szolgál. Így tehát polinomiális, exponenciális, logaritmikus stb. bonyolultságú algoritmusokról beszélünk.