Odhad zložitosti algoritmov alebo čo je O(log n). Typy funkcie zložitosti algoritmu Aká je zložitosť operácie

Ak existuje jeden algoritmus na riešenie problému, potom je možné vynájsť mnoho ďalších algoritmov na riešenie rovnakého problému. Ktorý algoritmus je najlepší na riešenie konkrétneho problému? Aké kritériá by sa mali použiť na výber algoritmu zo súboru možných? Spravidla robíme úsudok o algoritme na základe jeho posúdenia ľudskou osobou. Algoritmus sa nám zdá zložitý, ak ani po jeho dôkladnom preštudovaní nedokážeme pochopiť, čo robí. Algoritmus môžeme nazvať zložitým a mätúcim vzhľadom na to, že má rozvetvenú logickú štruktúru obsahujúcu množstvo kontrol podmienok a prechodov. Pre počítač však spustenie programu, ktorý implementuje takýto algoritmus, nebude ťažké, pretože vykonáva jeden príkaz za druhým a pre počítač je jedno, či ide o operáciu násobenia alebo test podmienok.

Okrem toho môžeme napísať ťažkopádny algoritmus, v ktorom sa opakujúce akcie vypisujú za sebou (bez použitia cyklickej štruktúry). Z hľadiska počítačovej implementácie takéhoto algoritmu však prakticky nie je rozdiel, či program používa príkaz loop (napríklad slovo „Ahoj“ sa zobrazí 10-krát) alebo či príkazy na zobrazenie slova „Ahoj“ sa za sebou píšu 10-krát.

Na vyhodnotenie efektívnosti algoritmov, pojem zložitosť algoritmu.

Definícia. výpočtový proces, generovaný algoritmom je sekvencia krokov algoritmu, ktoré prejdú počas vykonávania tohto algoritmu.

Definícia. Zložitosť algoritmu- počet základných krokov vo výpočtovom procese tohto algoritmu.

Upozorňujeme, že je to vo výpočtovom procese a nie v samotnom algoritme. Je zrejmé, že na porovnanie zložitosti rôznych algoritmov je potrebné, aby sa zložitosť vypočítala v rovnakých základných operáciách.

Definícia. Časová zložitosť algoritmu je čas T potrebný na jeho dokončenie. Rovná sa súčinu počtu základných akcií a priemerného času na dokončenie jednej akcie: T = kt.

Pretože t závisí od vykonávateľa implementujúceho algoritmus, je prirodzené predpokladať, že zložitosť algoritmu závisí predovšetkým od k. Je zrejmé, že v najväčšej miere závisí počet operácií pri vykonávaní algoritmu od množstva spracovávaných údajov. Na abecedné zoradenie zoznamu 100 priezvisk je skutočne potrebné podstatne menej operácií ako na zoradenie zoznamu so 100 000 priezviskami. Preto je zložitosť algoritmu vyjadrená ako funkcia množstva vstupných údajov.

Nech existuje algoritmus A. Pre neho existuje parameter a, charakterizujúci množstvo údajov spracovaných algoritmom, tento parameter sa často nazýva rozmer úlohy. Označiť podľa T(n)čas vykonávania algoritmu f- nejaká funkcia z P.

Definícia. To si povieme T(n) algoritmus má poradie rastu f(n), alebo, inými slovami, algoritmus má teoretická zložitosťO * (f(n)), ak sú také konštanty od 1, od 2> 0 a číslo n 0,čo c 1 f(n)) < T(p)< c 2 f(n) pre všetkých n >= n°. Tu sa predpokladá, že funkcia f(n) nie negatívne, ale aspoň n >= n°. Ak pre T(p) podmienka T(n)<= cf(n), potom sa hovorí, že algoritmus má teoretická zložitosť O(p) (čítaj „o“ veľké od n).

Napríklad algoritmus, ktorý vykonáva iba operácie čítania údajov a ich vkladania do pamäte RAM, má lineárne zložitosť 0(n). Algoritmus triedenia priameho výberu má kvadratický zložitosť 0 (p 2), pretože pri triedení akéhokoľvek poľa musíte vykonať (p 2 - p) / 2 porovnávacie operácie (zároveň nemusia existovať vôbec žiadne permutačné operácie, napr. na usporiadanom poli, v najhoršom prípade bude potrebné vykonať P permutácie). A zložitosť algoritmu násobenia matice(tabuľky) veľkosť P X P už bude kubický O(n 3) , keďže každý prvok výslednej matice vyžaduje P násobenia a n - 1 dodatky, ale všetky tieto prvky n 2.

Na vyriešenie problému je možné vyvinúť algoritmy akejkoľvek zložitosti. Je logické použiť spomedzi nich to najlepšie, t.j. s najmenšou zložitosťou.

Spolu so zložitosťou je dôležitou charakteristikou algoritmu efektívnosť. Efektívnosťou sa rozumie splnenie nasledujúcej požiadavky: nielen celý algoritmus, ale aj každý jeho krok musí byť taký, aby ich interpret bol schopný dokončiť v konečnom primeranom čase. Napríklad, ak algoritmus, ktorý vytvára predpoveď počasia na nasledujúci deň, bude vykonaný týždeň, potom nikto jednoducho takýto algoritmus nepotrebuje, aj keď je jeho zložitosť minimálna pre triedu podobných problémov.

Ak vezmeme do úvahy algoritmy, ktoré sú implementované na počítači, potom sa k požiadavke na vykonanie v obmedzenom množstve pridáva požiadavka vykonania v primeranom čase. Náhodný vstup do pamäťe.

Je známe, že v mnohých programovacích jazykoch neexistuje žiadna operácia umocňovania, preto takýto algoritmus musí napísať programátor sám. Operácia umocnenia sa realizuje prostredníctvom operácií násobenia; so zvyšujúcim sa exponentom sa zvyšuje počet operácií násobenia, ktorých dokončenie trvá dlho. Preto je dôležitá otázka vytvorenia efektívneho umocňovacieho algoritmu.

Zvážte metódu na rýchly výpočet prirodzenej mocniny reálneho čísla X. Táto metóda bola opísaná pred naším letopočtom v starovekej Indii.

Poďme si zapísať P v dvojkovej sústave.

Nahradme každé "1" v tomto zázname dvojicou písmen KH, a každé "O" - písmeno K.

Vymažte pár CH úplne vľavo.

Výsledný reťazec čítaný zľava doprava dáva pravidlo rýchleho výpočtu xn, ak list Komu považovaný za operáciu kvadratúry výsledku a list X- ako operácia násobenia výsledku o X. Spočiatku je výsledok X.

Príklad 1. Zvýšte x na mocninu n = 100.

Preložme číslo n na binárny systém počet: n \u003d 100 10 \u003d 1100100,

Zostavíme postupnosť KHKKKKKKKK

Prečiarknite AX vľavo => KHKKKKKK

Vypočítame požadovanú hodnotu

K => odmocníme x => dostaneme x 2,

X => vynásobte výsledok x => dostanete x 3

K => druhá mocnina výsledku => získajte x 6

K => výsledok odmocníme => dostaneme x 12,

K => druhá mocnina výsledku => získajte x 24,

X => vynásobte výsledok x => dostanete x 25

K => druhá mocnina výsledku => získajte x 50

K => druhá mocnina výsledku => získajte x 100.

Vypočítali sme teda stotinovú mocninu čísel len v 8 násobeniach. Táto metóda je pomerne efektívna, pretože na ukladanie medzivýsledkov nevyžaduje dodatočnú pamäť RAM. Upozorňujeme však, že táto metóda nie je vždy najrýchlejšia.

Napríklad s n = 49 môžu študenti prísť s nasledujúcim efektívnym umocňovacím algoritmom:

Pri implementácii tohto algoritmu bolo vykonaných 7 operácií násobenia (namiesto 48 operácií pri výpočte „na čelo“) a 3 bunky (na uloženie premennej X, na uloženie hodnoty x 16 a uložiť aktuálny výsledok získaný v každom kroku). Ak použijeme algoritmus „Rýchle umocňovanie“, dostaneme rovnaký počet operácií (7 operácií násobenia), ale na implementáciu tohto algoritmu sú potrebné iba 2 bunky (na uloženie premennej X a uložiť aktuálny výsledok).

Samotná operácia násobenia je v procesore implementovaná nie „na čele“, ale opäť prostredníctvom efektívnych rekurzívnych algoritmov. O jednom z týchto algoritmov si môžete prečítať v aplikácii Reader. Budeme uvažovať o „rýchlom“ multiplikačnom algoritme, ktorý bol známy v starovekom Egypte, nazýva sa aj „ruská“ alebo „roľnícka“ metóda. Pozrime sa na príklad aplikácie tohto algoritmu.

Príklad 2. Vynásobme 23 43 pomocou „ruskej“ metódy.

Odpoveď: 23 x 43 = 23 + 46 + 184 + 736 = 989.

Konečný súčet zahŕňa čísla v prvom stĺpci, vedľa ktorých sú v druhom stĺpci nepárne čísla.

Pred uzávierkou by článok nemal byť upravovaný inými účastníkmi projektu stránky. Na jeho konci má každý účastník právo podľa vlastného uváženia opraviť tento článok a zmazať toto upozornenie zobrazené pomocou šablóny ((Úloha)).

pozri tiež usmernenia o použití zdroja stránky vo výchovno-vzdelávacom procese.

Teória výpočtovej zložitosti Odvetvie výpočtovej teórie, ktoré študuje množstvo práce potrebnej na vyriešenie výpočtového problému.

Úloha sa považuje za zložitú, ak si riešenie problému vyžaduje veľké množstvo zdrojov, bez ohľadu na algoritmus použitý na jej vyriešenie. Teória formalizuje túto intuitívnu predstavu zavedením matematických modelov výpočtov na štúdium týchto problémov a kvantifikáciu množstva zdrojov potrebných na ich vyriešenie, ako je využitie času a pamäte. Možné sú aj iné miery zložitosti, ako napríklad: počet správ (zložitosť komunikácie), počet prvkov v obvode funkčných prvkov (zložitosť obvodu) a počet procesorov. Najmä teória výpočtovej zložitosti definuje praktické limity toho, čo počítače môžu a nemôžu robiť.

S teóriou výpočtovej zložitosti úzko súvisí analýza algoritmov a teória vypočítateľnosti. Hlavný rozdiel medzi teóriou výpočtovej zložitosti a analýzou algoritmov je v tom, že druhá sa zaoberá analýzou množstva zdrojov, ktoré konkrétny algoritmus vyžaduje na vyriešenie problému, zatiaľ čo prvá z nich vyžaduje viac. všeobecný o všetkých možných algoritmoch, ktoré možno použiť na vyriešenie rovnakého problému. Presnejšie povedané, teória výpočtovej zložitosti sa pokúša klasifikovať problémy, ktoré môžu alebo nemusia byť vyriešené primeraným množstvom obmedzených zdrojov. Na druhej strane, uvalenie obmedzení na dostupné zdroje je to, čo odlišuje teóriu výpočtovej zložitosti od teórie vypočítateľnosti: teória vypočítateľnosti sa pýta, aké problémy možno v zásade vyriešiť algoritmicky bez obmedzenia výpočtových zdrojov.

Výpočtové problémy

Inštancie úloh

Výpočtové problémy (problémy) možno považovať za nekonečnú množinu dvojíc: (inštancia problému, riešenie pre tento prípad). Vstupný reťazec pre výpočtový problém je reťazec popisujúci inštanciu problému. Výstupný reťazec pre výpočtový problém je popisom riešenia pre inštanciu problému opísanú vstupným reťazcom. Napríklad problém rozpoznania prvočísla čísla: inštanciou problému je číslo, pre ktoré by sa malo určiť, či je prvočíslo alebo nie, riešením je reťazec „áno“, ak je toto číslo prvočíslo a „nie“. " inak. Teória výpočtovej zložitosti uvažuje len o masívnych problémoch, t.j. požiadavka, aby množina inštancií úloh bola nekonečná, je povinná.

Zobrazenie úloh

Pri zvažovaní výpočtových problémov je popis inštancie problému reťazec nad abecedou. Spravidla sa abeceda považuje za binárnu (t. j. množinu (0,1)). Rôzne matematické objekty musia byť zodpovedajúcim spôsobom zakódované. Takže napríklad celé čísla môžu byť reprezentované binárne a grafy môžu byť kódované priamo prostredníctvom ich matíc susedstva alebo pomocou ich kódovania zoznamov susedstva v binárnom kóde.

Úlohy na rozpoznávanie

Problém rozpoznávania je jedným z ústredných predmetov štúdia teórie výpočtovej zložitosti. Úloha rozpoznávania je špeciálny typ výpočtového problému, na ktorý je odpoveď buď „áno“ alebo „nie“ (1 alebo 0). Problém rozpoznávania možno formulovať ako problém, či vstupný reťazec patrí do určitej podmnožiny (jazyka) množiny všetkých vstupných reťazcov. Vstupný reťazec úlohy patrí do zodpovedajúceho jazyka vtedy a len vtedy, ak je odpoveď na tento reťazec "áno". Úloha rozpoznávania je teda úlohou rozpoznať, že vstupný reťazec patrí do určitého jazyka.

Príklad problému s rozpoznávaním. Vstupný reťazec: popis ľubovoľného grafu. Problémom je rozhodnúť, či daný graf je alebo nie je spojený. Jazyk spojených grafov je množina popisov všetkých spojených grafov. Ak chcete získať presnú definíciu tohto jazyka, musíte sa rozhodnúť, ako sú grafy kódované ako binárne reťazce.

Vyhľadávacie úlohy

Vyhľadávacia úloha je výpočtová úloha, kde je výstupná hodnota zložitejšia ako v úlohe rozpoznávania (to znamená, že nejde len o „áno“ alebo „nie“).

Príkladom problému s vyhľadávaním je problém obchodného cestujúceho. Problém cestujúceho obchodníka je jedným z najznámejších problémov kombinatorickej optimalizácie. Úlohou je nájsť najziskovejšiu trasu, ktorá aspoň raz prechádza cez zadané mestá a potom sa vracia do pôvodného mesta. V podmienkach problému je uvedené kritérium ziskovosti trasy (najkratšie, najlacnejšie, kumulatívne kritérium atď.) a zodpovedajúce matice vzdialeností, nákladov atď.. Spravidla sa uvádza, že trasa by mala prechádzať cez každé mesto iba raz - v takom prípade sa volí medzi hamiltonovskými cyklami. Vstupný reťazec: popis váženého (t. j. s číselnými značkami na okrajoch) grafu. Výstupný reťazec je popis optimálnej trasy obchodného cestujúceho.

Medzi úlohami rozpoznávania a úlohami vyhľadávania existuje párový vzťah. Problém vyhľadávania možno formulovať ako problém rozpoznávania. Napríklad pre problém vyhľadávania "násobenie dvoch čísel" môže byť zodpovedajúci problém rozpoznávania párov reprezentovaný ako množina trojíc (A, B, C), takže vzťah A × B = C je splnený.

Meranie obtiažnosti

Teória výpočtovej zložitosti vznikla z potreby porovnávať rýchlosť algoritmov, jasne popísať ich správanie (čas vykonávania, množstvo potrebnej pamäte atď.) v závislosti od veľkosti vstupu a výstupu.

Počet elementárnych operácií vynaložených algoritmom na vyriešenie konkrétnej inštancie problému závisí nielen od veľkosti vstupných údajov, ale aj od údajov samotných. Napríklad počet operácií algoritmu triedenia vkladania je oveľa menší, ak sú vstupné údaje už zoradené. Aby ste sa vyhli takýmto ťažkostiam, zvážte v najhoršom prípade koncepciu časovej zložitosti algoritmu.

Časová zložitosť algoritmu (v najhoršom prípade) je funkciou veľkosti vstupných a výstupných dát, ktorá sa rovná maximálnemu počtu elementárnych operácií vykonaných algoritmom na vyriešenie problémovej inštancie zadanej veľkosti. V problémoch, kde veľkosť výstupu nepresahuje alebo je úmerná veľkosti vstupu, možno považovať časovú zložitosť iba za funkciu veľkosti vstupných údajov.

Podobne ako pri koncepte časovej zložitosti v najhoršom prípade je definovaný koncept časovej zložitosti algoritmu v najlepšom prípade. Zvážte tiež koncepciu priemerného času chodu algoritmu, to znamená matematického očakávania času chodu algoritmu. Niekedy sa jednoducho hovorí: „Časová zložitosť algoritmu“ alebo „Časová zložitosť algoritmu“, čo sa týka časovej zložitosti algoritmu v najhoršom, najlepšom alebo priemernom prípade (v závislosti od kontextu).

Analogicky s časovou zložitosťou určujú priestorovú zložitosť algoritmu, len tu nehovoríme o počte elementárnych operácií, ale o množstve použitej pamäte.

Napriek tomu, že funkciu časovej zložitosti algoritmu možno v niektorých prípadoch presne určiť, vo väčšine prípadov nemá zmysel hľadať jej presnú hodnotu. Faktom je, že po prvé, presná hodnota časovej zložitosti závisí od definície elementárnych operácií (napríklad zložitosť sa dá merať počtom aritmetických operácií alebo operácií na Turingovom stroji), a po druhé ako veľkosť vstupné údaje sa zvyšujú, príspevok konštantných faktorov a členov nižších rádov, ktoré sa objavujú vo výraze pre presnú prevádzkovú dobu, sa stáva mimoriadne nevýznamným.

Zohľadnenie vstupných údajov veľká veľkosť a odhad poradia rastu doby chodu algoritmu vedie ku koncepcii asymptotickej zložitosti algoritmu. Algoritmus s menšou asymptotickou zložitosťou je zároveň efektívnejší pre všetky vstupné dáta, možno s výnimkou dát malej veľkosti.

Zložitosť sa určuje na základe výpočtového modelu, v ktorom sa výpočty vykonávajú.

Výpočtové modely

Existuje mnoho rôznych výpočtových modelov: Post stroj, Minského stroj, lambda kalkul, čiastočne rekurzívne funkcie, normálne Markovove algoritmy, stroje s náhodným prístupom k pamäti (RAM stroje) atď. Spomeňme len najpopulárnejší výpočtový model - Turingov stroj.

Turingov stroj

Turingov stroj (MT) je abstraktný exekútor (abstraktný počítač). V roku 1936 navrhol Alan Turing formalizovať koncept algoritmu.

Turingov stroj je rozšírením konečného automatu a podľa Church-Turingovej tézy je schopný napodobniť všetkých ostatných vykonávateľov (špecifikovaním prechodových pravidiel), ktoré nejakým spôsobom implementujú postupný proces výpočtu, v ktorom každý výpočet krok je celkom elementárny.

Zloženie Turingovho stroja zahŕňa pásku, ktorá je nekonečná v oboch smeroch (možné sú Turingove stroje, ktoré majú niekoľko nekonečných pások), rozdelená na bunky a ovládacie zariadenie schopné byť v jednom z mnohých stavov. Počet možných stavov riadiaceho zariadenia je konečný a presne daný.

Ovládacie zariadenie sa môže pohybovať po páske doľava a doprava, čítať a zapisovať symboly nejakej konečnej abecedy do buniek pásky. Je pridelený špeciálny prázdny symbol, ktorý vyplní všetky bunky pásky, okrem tých z nich (konečný počet), na ktoré sú zapísané vstupné dáta.

Riadiace zariadenie pracuje podľa prechodových pravidiel, ktoré predstavujú algoritmus implementovaný týmto Turingovým strojom. Každé pravidlo prechodu dáva pokyn stroju v závislosti od Aktuálny stav a symbol pozorovaný v aktuálnej bunke zapíšte do tejto bunky nová postava, prejdite do nového stavu a posuňte sa o jednu bunku doľava alebo doprava. Niektoré stavy Turingovho stroja možno označiť ako terminálne a prechod na ktorýkoľvek z nich znamená koniec práce, zastavenie algoritmu.

Turingov stroj sa považuje za deterministický, ak každá kombinácia symbolu štátu a stuhy v tabuľke zodpovedá najviac jednému pravidlu. Ak existuje dvojica (symbol pásky - stav), pre ktorú existujú 2 a viac inštrukcií, takýto Turingov stroj sa nazýva nedeterministický.

Model Turingovho stroja umožňuje rôzne rozšírenia. Možno uvažovať o Turingových strojoch s ľubovoľným počtom pások a viacrozmerných páskach s rôznymi obmedzeniami; stroje, ktoré využívajú zdroj náhodnosti.

Turingov stroj je jedným z hlavných modelov výpočtov v teórii zložitosti.

Triedy obtiažnosti

Triedy zložitosti sú súbory výpočtových problémov, ktoré sú z hľadiska výpočtovej zložitosti približne rovnaké. Existujú triedy jazykovej zložitosti a triedy funkčnej zložitosti. Trieda zložitosti jazykov je množina predikátov (funkcií, ktoré berú slovo ako vstup a vracajú odpoveď 0 alebo 1), ktoré na výpočet využívajú približne rovnaké množstvo zdrojov. Koncept triedy funkčnej zložitosti je podobný, až na to, že nejde o množinu predikátov, ale o množinu funkcií. V teórii zložitosti je štandardne trieda zložitosti triedou zložitosti jazykov. Typická definícia triedy zložitosti vyzerá takto:

Trieda zložitosti X je množina predikátov P(x), ktoré sú vyčísliteľné na Turingových strojoch a na výpočet používajú zdroj O(f(n)), kde n je dĺžka slova x.

Zdroje sa zvyčajne berú ako výpočtový čas (počet pracovných cyklov Turingovho stroja) alebo pracovná plocha (počet buniek použitých na páske počas prevádzky). Jazyky rozpoznávané predikátmi z určitej triedy (t. j. množina slov, pre ktoré predikát vráti 1), tiež patria do rovnakej triedy.

Okrem toho možno mnohé triedy opísať aj výrazmi matematická logika alebo teória hier.

Triedy sa zvyčajne označujú veľkými písmenami. Doplnok triedy C (t. j. trieda jazykov, ktorých doplnky patria do C) sa označuje ako co-C.

Pre každú triedu je určená kategória úloh, ktoré sú „najťažšie“. To znamená, že každá úloha z triedy je redukovaná na takúto úlohu a navyše samotná úloha leží v triede. Takéto problémy sa nazývajú úplné problémy pre danú triedu.

Trieda P

Trieda P (z angl. polynomial) - súbor rozpoznávacích problémov, ktoré je možné riešiť na deterministickom Turingovom stroji v polynomickom čase na dĺžke vstupu. Podobne pre úlohy vyhľadávania je definovaná trieda FP (z angl. function polynomial).

Formálnejšie zvážte deterministické Turingove stroje, ktoré počítajú odpoveď daného slova na vstupnej páske zo vstupnej abecedy. Doba chodu Turingovho stroja pre pevné vstupné slovo X je počet pracovných cyklov Turingovho stroja od spustenia po zastavenie stroja. Zložitosť funkcie vypočítanej niektorým Turingovým strojom je funkcia, ktorá závisí od dĺžky vstupného slova a rovná sa maximálnej dobe chodu stroja vo všetkých vstupných slovách pevnej dĺžky:

Ak pre funkciu f existuje Turingov stroj M také, že pre nejaké číslo c a dostatočne veľké n, potom hovoríme, že patrí do triedy FP, alebo je polynóm v čase.

Trieda P je jednou zo základných v teórii výpočtovej zložitosti.

triedy NP

Trieda NP (z angl. non-deterministic polynomial) je súbor rozpoznávacích problémov, ktorých čas riešenia výrazne závisí od veľkosti vstupných údajov; zároveň existuje algoritmus, ktorý po prijatí spolu s popisom vstupných hodnôt Ďalšie informácie(svedok riešenia) dokáže dostatočne rýchlo (v čase nepresahujúcom polynóm veľkosti dát) problém vyriešiť.

Formálnejšie sa hovorí, že jazyk L patrí do triedy NP, ak existuje dvojmiestny predikát R(x, y) z triedy P (teda vyčísliteľný v polynómovom čase) a polynóm p taký, že pre akékoľvek slovo x dĺžky n podmienka „x patrí do L“ je ekvivalentná podmienke „y je s dĺžkou menšou ako p(n), takže R(x, y) platí“. Slovo y sa nazýva svedectvo, že x patrí do jazyka L. Ak teda máme slovo, ktoré patrí do jazyka, a ďalšie svedecké slovo obmedzenej dĺžky (ktoré môže byť ťažké nájsť), potom môžeme rýchlo overiť, že x skutočne patrí L. Akýkoľvek problém patriaci do NP sa dá vyriešiť v exponenciálnom čase spočítaním všetkých možných svedkov dĺžky menšej ako p(n).

Príklad úlohy z NP: úloha rozpoznávania "Existencia celočíselného riešenia systému lineárnych nerovníc." Svedok je riešením systému nerovností. V polynomickom čase je ľahké skontrolovať, či sa svedecké riešenie hodí.

Trieda NP zahŕňa triedu P.

Otvorené problémy

V teórii výpočtovej zložitosti je veľa nevyriešených problémov, týkajú sa najmä otázok separácie alebo vnorenia určitých tried zložitosti. Jednou z týchto otázok je problém rovnosti tried P a NP.

Problém rovnosti tried P a NP

V konečnom dôsledku je problém rovnosti tried P a NP takýto: ak sa dá kladná odpoveď na otázku rýchlo skontrolovať (v polynomiálnom čase), potom je pravda, že odpoveď na túto otázku sa dá rýchlo nájsť (v polynomiálnom čase )?

Z definície tried P a NP bezprostredne vyplýva dôsledok: . Zatiaľ však nie je známe nič o prísnosti tohto zaradenia, t. či existuje algoritmus, ktorý je v NP, ale nie v P. Ak takýto algoritmus neexistuje, potom všetky problémy patriace do triedy NP možno vyriešiť v polynomiálnom čase, čo sľubuje obrovský výpočtový prínos. Teraz možno najťažšie NP-problémy (takzvané NP-úplné problémy) vyriešiť v exponenciálnom čase, čo je takmer vždy neprijateľné.

Otázka rovnosti týchto dvoch tried je považovaná za jeden z najťažších otvorených problémov v oblasti teoretickej informatiky. V súčasnosti väčšina matematikov verí, že tieto triedy nie sú rovnaké. Clay Mathematics Institute zaradil tento problém na svoj zoznam problémov tisícročia a za jeho vyriešenie ponúka odmenu jeden milión amerických dolárov.

Literatúra

1. Gehry M., Johnson D. Výpočtové stroje a ťažko riešiteľné problémy. Vydavateľstvo Mir v roku 1982. - 420 str. Monografia amerických vedcov sa venuje riešeniu zložitých (vrátane NP-tvrdých) kombinatorických problémov vznikajúcich v diskrétnej optimalizácii, matematickom programovaní, algebre, teórii automatov s príkladmi.
2. Kormen, Thomas H.; Leizerson, Karol I.; Rivest, Ronald L.; Stein, Clifford Algorithms: construction and analysis, 2. vydanie = Introduction to Algorithms druhé vydanie. - M.: "Williams", 2005. -

Označenie	Intuitívne vysvetlenie	Definícia
	f zhora obmedzená funkciou g	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/101/eebfe73c29ff3f9bc886d263bd3e91f3.png" border="0"> alebo style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0">
	f zospodu obmedzená funkciou g(až do konštantného faktora) asymptoticky	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/48/0fda981f377ae7b8d361f58ce148c173.png" border="0">
	f ohraničené zhora a zdola funkciou g asymptoticky	0), n_0: \forall (n>n_0) \; |Cg(n)|
	g dominuje f asymptoticky	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/49/176ce786e936badb831a0bb87f25249d.png" border="0">
	f dominuje g asymptoticky	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/53/554bc3f42cfa6d0638722e58e4a99d8b.png" border="0">
	f je ekvivalentné g asymptoticky

Príklady

Poznámky

Je potrebné zdôrazniť, že tempo rastu najhoršieho času vykonávania nie je jediným alebo najdôležitejším kritériom hodnotenia algoritmov a programov. Tu je niekoľko úvah, ktoré vám umožnia pozrieť sa na kritérium runtime z iných uhlov pohľadu:

Ak riešenie nejakej úlohy pre n-vrcholový graf jedným algoritmom zaberie čas (počet krokov) rádovo n C a iným - rádovo n+n!/C, kde C je konštantné číslo , potom podľa „polynomiálnej ideológie“ je prvý algoritmus prakticky efektívny a druhý nie, hoci napríklad pri C = 10 (10 10) je situácia práve opačná.

1. Efektívne, ale zložité algoritmy môžu byť nežiaduce, ak sú hotové programy podporované osobami, ktoré nie sú zapojené do písania týchto programov. Dúfajme, že základné body technológie na vytváranie efektívnych algoritmov sú všeobecne známe a pomerne zložité algoritmy sú voľne aplikované v praxi. Je však potrebné predvídať možnosť, že efektívne, ale „zložité“ algoritmy nebudú žiadané kvôli ich zložitosti a ťažkostiam, ktoré vznikajú pri pokuse o ich nájdenie.
2. Je známych niekoľko príkladov, kedy efektívne algoritmy vyžadujú také veľké množstvo pamäte stroja (bez možnosti použitia pomalších externých pamäťových médií), že tento faktor neguje výhodu „efektívnosti“ algoritmu.
3. V numerických algoritmoch nie je presnosť a stabilita algoritmov o nič menej dôležitá ako ich časová efektívnosť.

Triedy obtiažnosti

Trieda zložitosti je súbor problémov rozpoznávania, pre ktoré existujú algoritmy, ktoré sú z hľadiska výpočtovej zložitosti podobné. Dvaja významní predstavitelia:

Trieda P

Problém rovnosti tried P a NP

slávnych vedcov

• Leonid Levin
• Alexander Razborov
• Edie Sheimir

pozri tiež

Odkazy

• Yuri Lifshits "Moderné problémy teoretickej informatiky". Kurz prednášok o algoritmoch pre NP-ťažké problémy.
• A. A. Razborov Teoretická informatika: pohľad matematika // Computerra. - 2001. - č. 2. (alternatívny odkaz)
• A. A. Razborov O zložitosti výpočtov // Matematické vzdelanie. - MTSNMO, 1999. - č. 3. - S. 127-141.

Nadácia Wikimedia. 2010.

Pozrite sa, čo je „Časová zložitosť algoritmu“ v iných slovníkoch:

časová zložitosť (algoritmu)- - Témy ochrana informácií EN časová zložitosť ... Technická príručka prekladateľa

KOMPLEXNOSŤ ČINNOSTÍ OPERÁTORA- súbor objektívnych faktorov ovplyvňujúcich kvalitu a trvanie výkonu požadovaných funkcií človeka v HMS. S. o. je rozdelená do niekoľkých typov, z ktorých každý sa vyznačuje kombináciou faktorov určitým spôsobom ... ... Encyklopedický slovník psychológie a pedagogiky

Výpočtová funkcia, ktorá poskytuje číselný odhad náročnosti (ťažkopádnosti) procesov aplikácie algoritmu na počiatočné údaje. Spresnenie A. s. výpočty je pojem signalizačná funkcia (alebo jednoducho signalizačná) funkcia, na okraj je daná ... ... Matematická encyklopédia

V informatike a teórii algoritmov je výpočtová zložitosť algoritmu funkciou, ktorá určuje závislosť množstva práce vykonanej niektorým algoritmom od veľkosti vstupných údajov. Časť, ktorá študuje výpočtovú zložitosť, sa nazýva teória ... ... Wikipedia

V informatike je teória výpočtovej zložitosti odvetvím výpočtovej teórie, ktorá študuje náklady na prácu potrebnú na vyriešenie výpočtového problému. Náklady sa zvyčajne merajú pomocou abstraktných pojmov času a priestoru nazývaných ... ... Wikipedia

Toto je algoritmus na usporiadanie prvkov v zozname. V prípade, že položka zoznamu má viacero polí, pole, ktoré slúži ako kritérium poradia, sa nazýva kľúč triedenia. V praxi číslo často funguje ako kľúč av iných oblastiach ... ... Wikipedia

Algoritmus triedenia je algoritmus na zoradenie prvkov v zozname. V prípade, že položka zoznamu má viacero polí, pole, ktoré slúži ako kritérium poradia, sa nazýva kľúč triedenia. V praxi číslo často funguje ako kľúč a na ... ... Wikipédii

- (GM) kryptografický systém verejný kľúč, ktorý vyvinuli Shafi Goldwasser a Silvio Micali v roku 1982. GM je prvá pravdepodobnostná šifrovacia schéma s verejným kľúčom, ktorá je preukázateľne bezpečná pri štandardnom šifrovaní ... ... Wikipedia Prečítajte si viac

Funkcia zložitosti 0(1). V algoritmoch konštantnej zložitosti sa väčšina operácií v programe vykonáva raz alebo viackrát. Každý algoritmus, ktorý vždy vyžaduje (bez ohľadu na veľkosť údajov) rovnaký čas, má konštantnú zložitosť.

Funkcia zložitosti 0(N). Doba chodu programu je zvyčajne lineárna, keď každý prvok vstupných údajov je potrebné spracovať iba lineárny počet krát. Táto funkcia zložitosti charakterizuje jednoduchý cyklus.

Funkcia zložitosti 0(N 2), 0(N 3), 0(№) - polynomická funkcia zložitosti: počet operácií rastie úmerne druhej mocnine N. Vo všeobecnom prípade môže existovať O(A^) v závislosti od zložitosti problému. Táto funkcia zložitosti charakterizuje zložitý cyklus.

Funkcia zložitosti O(Záznamník 2 (A0), 0 (N log 2 (A0). Toto je čas, keď fungujú algoritmy, ktoré rozdeľujú veľký problém na veľa malých, a potom, keď ich vyriešia, kombinujú riešenia.

Funkcia zložitosti 0(e N). Algoritmy s exponenciálnou zložitosťou sú najčastejšie výsledkom prístupu nazývaného hrubá sila.

Funkcia zložitosti 0 (M) - počet operácií rastie úmerne faktoriálu N.

Programátor musí byť schopný analyzovať algoritmy a určiť ich zložitosť. Časovú zložitosť algoritmu možno vypočítať na základe analýzy jeho riadiacich štruktúr.

Algoritmy bez slučiek a rekurzívnych volaní majú konštantnú zložitosť. Ak neexistuje rekurzia a slučky, všetky riadiace štruktúry možno zredukovať na štruktúry konštantnej zložitosti. V dôsledku toho je celý algoritmus tiež charakterizovaný konštantnou zložitosťou. Určenie zložitosti algoritmu v podstate spočíva v analýze slučiek a rekurzívnych volaní.

Zvážte napríklad algoritmus na spracovanie prvkov poľa.

Pre /": = 1 až N doBegin

Zložitosť tohto algoritmu O(A), pretože telo cyklu sa vykoná A-krát a zložitosť tela cyklu je 0 (1). Ak je jedna slučka vnorená do druhej a obe slučky závisia od veľkosti tej istej premennej, potom sa celá konštrukcia vyznačuje kvadratickou zložitosťou.

Pre /: = 1 až N urobiť Pre j:= 1 až N doBegin

Zložitosť tohto programu 0 (N2).

Príklad 1 Odhadnime zložitosť programu, ktorý zadá pole z klávesnice a nájde v ňom najväčší prvok. Algoritmus pozostáva z nasledujúcich krokov:

• - vstup poľa (je potrebné čítať prvky A);
• - vyhľadajte najväčší prvok (treba urobiť A - 1 porovnanie);
• - výstup výsledku (potrebujete vypísať jedno číslo alebo reťazec).

Sčítame počet operácií A + (A - 1) + 1 = 2A, t.j. existujú

takú konštantu, že pre žiadne A počet operácií nepresiahne CA. Preto je zložitosť algoritmu 0 (A).

Príklad 2 Odhadnime zložitosť programu, ktorý zadá pole z klávesnice a nájde v ňom prvok s danou vlastnosťou (napríklad rovný určitej hodnote). Algoritmus pozostáva z nasledujúcich krokov:

• - vstup poľa (operácie vstupu);
• - vyhľadajte prvok s danou vlastnosťou (prvok môže byť buď bližšie k začiatku poľa, alebo na úplnom konci; ak prvok neexistuje, potom sa musia vykonať všetky porovnania A, aby ste sa uistili);
• - výstup výsledku.

V najlepšom prípade bude zadaný algoritmus vyžadovať operácie A + 2 (vstup celého poľa, jedno porovnanie, výstup), v najhoršom prípade (ak takýto prvok neexistuje, operácia 2 A + 1). Ak je A veľké číslo, napríklad rádovo 106, potom jednotku možno zanedbať. Preto je zložitosť algoritmu 0 (N).

Príklad 3 Definujme funkciu zložitosti šifrovacieho algoritmu pre slovo dĺžky L substitučná metóda. Nech existuje tabuľka, v ktorej je pre každý znak abecedy znak, za ktorý ho treba nahradiť. Označte počet písmen abecedy S. Algoritmus pozostáva z nasledujúcich krokov:

• - zadanie slova (jedna operácia);
• - organizácia cyklu:
  • 1) pre každý znak nájdite jeho náhradu v tabuľke (ak tabuľka nie je usporiadaná a nemá žiadne vlastnosti, ktoré uľahčujú vyhľadávanie, potom v najhoršom prípade bude potrebné S operácie pre jeden znak, ak je požadovaný prvok na samom konci);
  • 2) výstup nájdeného symbolu;
• - koniec cyklu.

Celkový počet operácií 1 + (S+)L. V prípade dostatočne veľké S a L jednotky možno zanedbať a ukazuje sa, že funkcia zložitosti vyššie uvedeného algoritmu je O(SL).

Príklad 4 Definujme funkciu zložitosti algoritmu prekladu prirodzeného čísla 1 V do dvojkovej číselnej sústavy (bez operácií vstupu a výstupu dát). Algoritmus pozostáva z nasledujúcich krokov:

• - slučka, kým sa výsledok delenia čísla 2 nestane 0:
• - vydeľte číslo 2 a zapamätajte si zvyšok;
• - prijať výsledok delenia ako nové číslo;
• - koniec cyklu.

Celkový počet operácií nepresahuje 1 + log 2 A. Preto je opísaný algoritmus zložitý 0 (napr. 2 N).

Stanovenie zložitosti algoritmu

Odhad funkcie zložitosti získaný v asymptotickej analýze sa nazýva zložitosť algoritmu.

Treba mať na pamäti, že existuje niekoľko odhadov zložitosti algoritmu.

Asymptotické správanie funkcie zložitosti je operačná zložitosť. Okrem toho môžete špecifikovať nasledujúce typy ťažkostí.

Dočasné zložitosť - asymptotický odhad doby chodu algoritmu na vstupných dátach dĺžky P. Je zrejmé, že pri absencii paralelizácie výpočtových postupov je doba chodu algoritmu jednoznačne určená počtom vykonaných operácií. Konštantné koeficienty vyjadrujúce trvanie operácií neovplyvňujú poradie časovej zložitosti, takže vzorce pre prevádzkovú a časovú zložitosť sa často navzájom zhodujú.

kapacitné zložitosť - asymptotický odhad počtu súčasne existujúcich skalárov pri vykonávaní algoritmu na vstupných dátach dĺžky P.

Štrukturálne zložitosť - charakteristika počtu riadiacich štruktúr v algoritme a špecifiká ich relatívnej polohy.

poznávacie zložitosť - charakteristika dostupnosti algoritmu na pochopenie odborníkmi v aplikačných oblastiach.

Typy a zápis asymptotík

Pri asymptotickej analýze algoritmov je zvykom používať označenie matematická asymptotická analýza. V tomto prípade sa berú do úvahy tri odhady (asymptotiky) zložitosti algoritmov, ktoré sú označené nasledovne:

• 1) /(i) = O^(n))- asymptoticky presný odhad funkcie zložitosti /(«), alebo operačnej zložitosti algoritmu;
• 2) /(n) = 0 (§(n)) - asymptoticky presný horný odhad funkcie zložitosti /( P);
• 3) /(l) = ?2(#(l)) - asymptoticky presný dolný odhad funkcie vstupu práce /( P).

Namiesto označenia C1^(n)) veľmi často sa jednoduchšie o(^(“) používa s malým kurzívou písmenom „o“.

Vysvetlime si sémantiku vzorcov na príklade: ak je napísané / (n) = 0 (^2 (n)), TAK TO znamená, že funkcia g(n)=og2 (n) je asymptoticky presný odhad funkcie zložitosti /(«). V skutočnosti existuje dvojpolohová definícia vo forme tvrdenia:

Ak f(n)= @(log2(")),

mo g(n)\u003d denník 2 (l) - asymptoticky presný odhad f(n).

Všimnite si, že konštantný faktor neovplyvňuje poradie zložitosti algoritmu, takže základ logaritmu sa pri špecifikovaní logaritmickej zložitosti vynecháva a jednoducho píšu f(l) = @(lо§(l)), čo znamená, že logaritmus má ľubovoľný základ väčší ako jedna.

Formálne definície asymptotiky

Asymptoticky presný odhad funkcie vstupu práce s, s 2 , l 0 tak, že pre l>l 0 sa funkcia /(l) až po konštantné faktory nelíši od funkcie g( k), potom funkciu g(n) sa nazýva asymptoticky presný odhad funkcie /(k).

• 3 s ] , s 2 e A, s x > 0, s 2 > 0:
  • (3 l 0 e K, l 0 > 0: (/l e K, l > l 0:0 g(n) /(l) = 0 (a(l)),

kde 9^, N sú množiny všetkých reálnych a prirodzených čísel.

Asymptoticky presná horná hranica funkcie zložitosti slovne definované takto: ak existujú kladné čísla s a l 0 , takže pre l>l 0 funkcia /(l) nerastie rýchlejšie ako funkcia g(n) až po konštantný faktor c, potom funkcia g(n) sa nazýva asymptoticky presná horná hranica funkcie Ap).

Presnejšia formálna definícia má tvar:

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

Asymptoticky presná spodná hranica funkcie zložitosti slovne definované takto: ak existujú kladné čísla s a l 0 , takže pre l>l 0 funkcia /(l) nerastie pomalšie ako funkcia g(n) až po konštantný faktor s, potom sa funkcia?(k) nazýva asymptoticky presná dolná hranica funkcie

Presnejšia formálna definícia má tvar:

• 3 s e 9^, s > 0:
  • (3 i 0 e X, i 0 > 0: (/i e K, t.j > ja 0: 0 s? g(n)

/(ja) = 0,^(n))

Všimnite si nasledovné:

• 1) nerovnosti uvedené vo formálnych definíciách asymptotiky môžu byť vo všeobecnom prípade uspokojené nie jednou, ale určitou množinou funkcií, často s nespočetnou množinou termínov, takže konštrukcie Q(g(n)), 0^(n)) a 0,^(n)) symbolizovať súbor funkcií, s ktorým sa porovnáva skúmaná funkcia pracovného vstupu /(i); z tohto dôvodu v zápise asymptotiky tvaru /(n) = 0(?(n)), /(/0 = 0(? max (n)), Dn) = ?2(? m1n (n) )) namiesto znaku "= » by bolo racionálnejšie použiť znak "e";
• 2) dizajny (d^(n)), 0^(n)) a ?1^(n)), používané ako označenia niektorých veličín, treba čítať nasledovne: akákoľvek funkcia, ktorá je rovnaká, nerastie rýchlejšie a nerastie pomalšie g(n).

Zhoda a rozdiel asymptotík

Venujme pozornosť nasledujúcemu faktu: odhad /(s) = 0(?(s)) nastavuje horný aj dolný odhad pre /(s), keďže jeho definícia predpokladá platnosť vzťahu c g g(n)

Nasledujúca vlastnosť asymptotiky je celkom zrejmá: ak odhad φ(n) = ©^(n)) existuje, potom rovnosť /( P) = 0(^(n)) a /(n) = a2(#(n)), t.j. horný a dolný odhad intenzity práce sa navzájom zhodujú; ak /(i) = 0 (a max (i)) a φ(n) = C1^ mn (n)) a g max (n)Фg m 1n(i), potom neexistuje žiadna funkcia g(n), tak, že /(i) = 0 (a(i)).

Zhoda horných a dolných odhadov náročnosti práce je možná v nasledujúcich prípadoch:

• 1) funkcia zložitosti pre všetky hodnoty vstupnej dĺžky je deterministická (nenáhodná) funkcia, t.j. počet vykonaných operácií nezávisí od špecifík počiatočných hodnôt údajov; sú to napríklad funkcie závislosti počtu operácií násobenia a delenia od počtu neznámych veličín v algoritme riešenia sústav lineárnych algebraických rovníc metódou expanzie IS;
• 2) funkcia intenzity práce je náhodná funkcia, t.j. počet vykonaných operácií závisí od špecifík počiatočných údajov a (alebo) poradia ich prijatia a môžete špecifikovať funkcie / m | n (i), / max (i), popisujúce minimálny a maximálny počet operácie vykonávané vykonávateľom algoritmu pre konkrétnu vstupnú dĺžku i, obe tieto funkcie však majú rovnaké dominanty, napríklad ide o polynómy rovnakého rádu.

Pri odhadovaní poradia prevádzkovej zložitosti je potrebné mať na pamäti tri dôležité pravidlá:

• 1) pre určenie poradia zložitosti nezáleží na konštantných faktoroch, t.j. 0 (k? g(n)) = 0 (g("));
• 2) poradie zložitosti súčinu dvoch funkcií sa rovná súčinu ich zložitosti, pretože rovnosť platí:
• 0(gl(i) §2(i)) = 0 (a| (i)) 0 (č. 2 (i));
• 3) poradie zložitosti súčtu funkcií sa rovná poradiu dominanty členov, napríklad: 0 (tj. + n2 + n) = 0 (i 5).

Vyššie uvedené pravidlá používajú symbol iba jednej asymptotiky 0("), ale platia pre všetky asymptotické odhady - a pre 0( ) , a &.{ ).

V množine elementárnych funkcií môžete zadať zoznam funkčnej dominancie: ak je premenná, a,b-číselné konštanty, potom sú pravdivé nasledujúce tvrdenia: i" dominuje i!; i! dominuje a"; a" dominuje Zj“ ak a>b a p dominuje P b, ak a> 1 za všetky b e 9? ; n a dominuje a/ ak a>b i dominuje log q(i), ak a > 1.

Odhad priemernej náročnosti práce

V praxi re Vo výpočtových výpočtoch je veľmi zaujímavé odhadnúť f(n) matematického očakávania zložitosti M, pretože v drvivej väčšine prípadov je f(n) náhodná funkcia. V procese experimentálnych štúdií algoritmov s náhodným /(n) však vzniká ďalší problém - voľba počtu pokusov pre spoľahlivý odhad M. Prekonanie tohto problému je ústrednou úlohou v . Navrhované riešenie je založené na použití beta distribúcie na aproximáciu /(n). Ide o veľmi konštruktívnu a všestrannú techniku. V moderných podmienkach, kedy je výkon počítača pomerne vysoký, je však v mnohých prípadoch možné použiť jednoduchší spôsob výberu rozsahu testov, založený na sledovaní aktuálnej variability hodnôt. f(n) - hodnoty sa odhadujú, kým rozptyl odhadov nebude menší ako špecifikovaná chyba.

Odhad operačnej zložitosti algoritmu

Zložitosť algoritmu možno určiť na základe analýzy jeho riadiacich štruktúr. Algoritmy bez slučiek a rekurzívnych volaní majú konštantnú zložitosť. Preto sa definícia zložitosti algoritmu redukuje hlavne na analýzu cyklov a rekurzívnych volaní.

Zvážte algoritmus vymazania do-tý prvok z poľa veľkosti P, pozostávajúce z presunu prvkov poľa z (do + 1) - až P-choďte o jednu pozíciu späť na začiatok poľa a znížte počet prvkov P za jednotku. Zložitosť slučky spracovania poľa je Oh (p-k), pretože sa vykoná telo slučky (operácia pohybu). PC krát a zložitosť tela slučky je 0(1), t.j. je konštanta.

V uvažovanom príklade je zložitosť charakterizovaná asymptotikou 0("), pretože počet operácií vykonaných v tomto algoritme nezávisí od špecifík hodnôt údajov. Funkcia zložitosti je deterministická a všetky druhy asymptotík sa navzájom zhodujú: f(n) = Q(n-k), f(n) = 0 (n-k) a f(n) = Q(n- až). Túto skutočnosť dokladá označenie presne ©( ). Použite 0(*) a/alebo?2(*) len vtedy, ak sa tieto asymptotiká líšia.

Typ slučky (for, while, repeat) neovplyvňuje zložitosť. Ak je jedna slučka vnorená do druhej a obe slučky závisia od veľkosti tej istej premennej, potom sa celá konštrukcia vyznačuje kvadratickou zložitosťou. Vnorenie opakovaní je hlavným faktorom rastu zložitosti. Ako príklad uvádzame zložitosť známych vyhľadávacích a triediacich algoritmov pre pole veľkostí P:

• počet porovnávacích operácií pri sekvenčnom vyhľadávaní: 0(n);
• počet porovnávacích operácií pri binárnom vyhľadávaní: 0 (log 2 P);
• počet porovnávacích operácií v metóde jednoduchej výmeny (bublinkové triedenie): 0(n 2);
• počet permutačných operácií v bublinovom triedení: 0 (n 2);

Všimnite si, že počet porovnávacích operácií v jednoduchej výmennej metóde má asymptotiku 0 (n 2) a počet permutačných operácií má dve rôzne asymptotiky 0 (p 2) a?2(0), pretože počet porovnaní nezávisí od špecifickosti hodnôt triedených údajov, zatiaľ čo počet permutácií je určený touto špecifickosťou. Permutácie sa nemusia vykonať vôbec - ak je dátové pole na začiatku správne usporiadané alebo počet permutácií môže byť maximálny - objednávky P 2 , - ak je zoradené pole na začiatku usporiadané v opačnom smere.

Názov funkcie g(n) v asymptotike /(x) = @(x(x)) a /(a) = 0(g(n)) funkcia zložitosti /(«) sa používa na charakterizáciu algoritmu. Hovorí sa teda o algoritmoch polynomiálnej, exponenciálnej, logaritmickej atď. zložitosti.