Tere! Tänane loeng tuleb veidi erinev ülejäänutest. See erineb selle poolest, et see on Javaga ainult kaudselt seotud. See teema on aga iga programmeerija jaoks väga oluline. Me räägime algoritmid. Mis on algoritm? Lihtsamalt öeldes on see teatud toimingute jada, mis tuleb soovitud tulemuse saavutamiseks teha. Me kasutame igapäevaelus sageli algoritme. Näiteks seisate igal hommikul silmitsi ülesandega: tulla kooli või tööle ja samal ajal olla:
- Riietatud
- Puhas
- Hästi toidetud
- Ärka üles äratuskella peale.
- Võtke dušš, peske nägu.
- Valmista hommikusöök, tee kohvi/tee.
- Sööma.
- Kui te pole õhtust saadik riideid triikinud, triikige need ära.
- Pane riidesse.
- Lahku majast.
- Ostke või laadige Internetist alla "Vene isikunimede sõnaraamat" 1966. aasta väljaanne.
- Sellest sõnastikust leiate kõik nimed meie loendist.
- Kirjutage paberile, millisel sõnastiku leheküljel nimi asub.
- Pange nimed paberile märkmete abil järjekorda.
Sel juhul oleks kõige tõhusam algoritm faili edastamine Interneti kaudu. See võtab vaid paar minutit! Niisiis, ütleme oma algoritmi uuesti: "Kui teil on vaja teavet failide kujul edastada 5000 kilomeetri kaugusele, peate kasutama andmeedastust Interneti kaudu." Suurepärane. Nüüd analüüsime seda. Kas see lahendab meie probleemi?Üldiselt jah, see lahendab selle täielikult. Aga mida saate selle keerukuse kohta öelda? Hmm, siin lähevad asjad huvitavaks. Fakt on see, et meie algoritm sõltub väga palju sissetulevatest andmetest, nimelt failide suurusest. Nüüd on meil 10 megabaiti ja kõik on korras. Mis siis, kui meil on vaja üle kanda 500 megabaiti? 20 gigabaiti? 500 terabaiti? 30 petabaiti? Kas meie algoritm lakkab töötamast? Ei, kõiki neid andmemahtusid saab siiski edastada. Kas selle valmimine võtab kauem aega? Jah, saab! Nüüd teame oma algoritmi olulist funktsiooni: Mida suurem on edastatavate andmete maht, seda kauem võtab algoritmi täitmine aega.. Kuid me tahaksime täpsemalt mõista, kuidas see seos välja näeb (andmete suuruse ja nende edastamiseks kuluva aja vahel). Meie puhul on algoritmi keerukus lineaarne. "Lineaarne" tähendab, et andmete mahu suurenedes pikeneb nende edastamise aeg ligikaudu proportsionaalselt. Kui andmeid on 2 korda rohkem ja nende edastamiseks kulub 2 korda rohkem aega. Kui andmeid on 10 korda rohkem, pikeneb edastusaeg 10 korda. Kasutades Big-O tähistust, annab meie algoritmi keerukuse PEAL). See tähistus jääb edaspidiseks kasutamiseks kõige paremini meelde – seda kasutatakse alati lineaarse keerukusega algoritmide puhul. Pange tähele: me ei räägi siin üldse erinevatest "muutuvatest" asjadest: Interneti kiirusest, meie arvuti võimsusest ja nii edasi. Algoritmi keerukust hinnates pole sellel lihtsalt mõtet – meil pole selle üle nagunii kontrolli. Big-O hindab algoritmi ise, olenemata sellest, millises „keskkonnas” see töötama peab. Jätkame oma näitega. Oletame, et lõpuks selgub, et ülekantavate failide suurus on 800 terabaiti. Kui me edastame need Interneti kaudu, siis probleem loomulikult laheneb. On ainult üks probleem: ülekanne standardse kaasaegse lingi kaudu (100 megabitti sekundis), mida enamik meist oma kodudes kasutab, võtab umbes 708 päeva. Peaaegu 2 aastat! :O Seega meie algoritm siin ilmselgelt ei sobi. Vajame muud lahendust! Järsku tuleb meile appi IT-hiiglane Amazon! Selle Amazoni mootorsaani teenus võimaldab laadida suuri andmemahtusid mobiilsetesse salvestusseadmetesse ja toimetada need veoautoga soovitud aadressile! 
Nii et meil on uus algoritm! "Kui teil on vaja failide kujul teavet edastada 5000 kilomeetri kaugusel ja protsess võtab Interneti kaudu üle 14 päeva, peate kasutama Amazoni veoautotransporti." Arv 14 päeva valiti siin juhuslikult: oletame, et see on maksimaalne periood, mida saame endale lubada. Analüüsime oma algoritmi. Aga kiirus? Isegi kui veok sõidab vaid 50 km/h, läbib see 5000 kilomeetrit vaid 100 tunniga. See on veidi üle nelja päeva! See on palju parem kui Interneti-edastusvõimalus. Kuidas on lood selle algoritmi keerukusega? Kas see on ka lineaarne, O(N)? Ei, ei hakka. Lõppude lõpuks ei huvita veok, kui palju te seda laadite – see sõidab ikkagi ligikaudu sama kiirusega ja jõuab õigel ajal kohale. Olenemata sellest, kas meil on 800 terabaiti või 10 korda rohkem andmeid, jõuab veok kohale ikkagi 5 päevaga. Ehk siis veoauto kaudu andmete edastamise algoritm pidev raskus. "Püsiv" tähendab, et see ei sõltu algoritmile edastatud andmetest. Pane veokisse 1GB mälupulk ja see saabub 5 päevaga. Pane sinna kettad 800 terabaidise andmemahuga ja saabub 5 päevaga. Big-O kasutamisel tähistatakse pidevat keerukust kui O(1). Alates sellest, kui me kohtusime PEAL) Ja O(1), vaatame nüüd rohkem “programmeerijate” näiteid :) Oletame, et sulle antakse 100 numbrist koosnev massiiv ja ülesandeks on väljastada igaüks neist konsooli. Kirjutate selle ülesande täitva regulaarse for-tsükli int numbers = new int [100]; // ..täitke massiiv numbritega for (int i: numbrid) ( System. out. println (i) ; ) Mis on kirjutatud algoritmi keerukus? Lineaarne, O(N). Toimingute arv, mida programm peab tegema, sõltub sellest, kui palju numbreid sellesse täpselt sisestati. Kui massiivis on 100 numbrit, siis toiminguid (väljundeid ekraanil) on 100. Kui massiivis on 10 000 numbrit, siis tuleb sooritada 10 000 toimingut. Kas meie algoritmi saab parandada? Ei. Igal juhul peame seda tegema N läbib massiivi ja käivitage konsooli N väljundit. Vaatame teist näidet. public static void main(String args) (LinkedList <
Integer>
numbrid = uus LinkedList<
>() ; numbrid. add(0, 20202); numbrid. add(0, 123); numbrid. add(0, 8283); ) Meil on tühi LinkedList, kuhu sisestame mõned numbrid. Peame hindama meie näites ühe numbri lisamise algoritmi LinkedList'i ja seda, kuidas see sõltub loendi elementide arvust. Vastus saab olema O(1) – pidev keerukus. Miks? Pange tähele: iga kord, kui lisame loendi algusesse numbri. Lisaks, nagu mäletate, kui sisestate numbri LinkedListi, ei liigu elemendid kuhugi – lingid määratletakse uuesti (kui unustasite äkki LinkedListi toimimise, vaadake mõnda meie omadest). Kui nüüd on meie loendi esimene number arv x ja sisestame loendi algusesse numbri y, on vaja ainult x. eelmine = y; y. eelmine = null; y. järgmine = x; Selle viite alistamise jaoks meid ei huvita, kui palju numbreid LinkedListis praegu on- vähemalt üks, vähemalt miljard. Algoritmi keerukus on konstantne – O(1). Logaritmiline keerukus
Ära paanitse! :) Kui sõna "logaritmiline" tekitab soovi loengu lõpetada ja mitte edasi lugeda, oodake paar minutit. Siin ei teki matemaatilisi raskusi (sellist selgitust on mujalgi) ja analüüsime kõiki näiteid "näppude peal". Kujutage ette, et teie ülesanne on leida 100 numbri massiivist üks konkreetne arv. Täpsemalt kontrollige, kas see on üldse olemas. Niipea kui vajalik number on leitud, tuleb otsing peatada ja konsoolis kuvada kirje “Vajalik number on leitud!”. Selle indeks massiivis = ....” Kuidas te sellise probleemi lahendaksite? Siin on lahendus ilmne: peate massiivi elemente ükshaaval läbi tegema, alustades esimesest (või viimasest) ja kontrollima, kas praegune arv langeb kokku soovitud numbriga. Sellest lähtuvalt sõltub toimingute arv otseselt massiivi elementide arvust. Kui meil on 100 numbrit, siis peame minema järgmise elemendi juurde 100 korda ja kontrollima numbri sobivust 100 korda. Kui numbreid on 1000, siis kontrollsamme on 1000. See on ilmselgelt lineaarne keerukus, PEAL). Nüüd lisame oma näitele ühe täpsustuse: massiiv, millest peate numbri leidma, on järjestatud kasvavas järjekorras. Kas see muudab midagi meie ülesande jaoks? Soovitud numbrit saame ikkagi otsida toore jõuga. Kuid selle asemel saame kasutada üldtuntud binaarne otsingu algoritm.
Pildi ülemisel real näeme sorteeritud massiivi. Selles peame leidma arvu 23. Selle asemel, et arvude üle itereerida, jagame massiivi lihtsalt kaheks osaks ja kontrollime massiivi keskmist arvu. Leiame numbri, mis asub lahtris 4, ja kontrollime seda (pildil teine rida). See number on 16 ja me otsime 23. Praegune arv on väiksem. Mida see tähendab? Mida kõiki eelnevaid numbreid (mis asuvad enne numbrit 16) ei pea kontrollima: need on kindlasti väiksemad kui otsitav, sest meie massiiv on sorteeritud! Jätkame otsingut ülejäänud 5 elemendi hulgast. Pange tähele: tegime ainult ühe kontrolli, kuid oleme pooled võimalikest valikutest juba kõrvaldanud. Meil on alles vaid 5 elementi. Kordame oma sammu - jagage ülejäänud massiiv uuesti 2-ga ja võtke uuesti keskmine element (joonisel rida 3). See number on 56 ja see on suurem kui see, mida otsime. Mida see tähendab? Et loobume veel 3 valikust - number 56 ise ja kaks numbrit pärast seda (need on kindlasti suuremad kui 23, kuna massiiv on sorteeritud). Kontrollimiseks on jäänud vaid 2 numbrit (joonisel viimane rida) - massiiviindeksitega 5 ja 6 numbrid. Kontrollime neist esimest ja seda me otsisimegi - numbrit 23! Selle indeks = 5! Vaatame oma algoritmi tulemusi ja siis mõistame selle keerukust. (Muide, nüüd saate aru, miks seda nimetatakse binaarseks: selle olemus on andmete pidev jagamine 2-ga). Tulemus on muljetavaldav! Kui otsiksime soovitud arvu lineaarse otsingu abil, oleks meil vaja 10 kontrolli, kuid kahendotsinguga tegime selle 3-ga! Halvimal juhul oleks neid 4, kui viimasel sammul osutus meile vajalik number teiseks, mitte esimeseks. Aga selle keerukus? See on väga huvitav punkt :) Binaarne otsingualgoritm sõltub massiivi elementide arvust palju vähem kui lineaarne otsingu algoritm (ehk lihtne loendus). Kell 10
massiivi elemendid, lineaarne otsing vajab maksimaalselt 10 kontrolli ja binaarne otsing maksimaalselt 4 kontrolli. Erinevus on 2,5 korda. Aga massiivi jaoks 1000 elementi lineaarne otsing vajab 1000 kontrolli ja binaarne otsing kokku 10! Vahe on juba 100-kordne! Pange tähele: massiivi elementide arv on kasvanud 100 korda (10-lt 1000-le), kuid binaarotsingu jaoks vajalike kontrollide arv on suurenenud vaid 2,5 korda - 4-lt 10-le. 10 000 elementi, on erinevus veelgi muljetavaldavam: 10 000 kontrolli lineaarseks otsinguks ja ainult 14 tšekki binaarseks. Ja veel: elementide arv kasvas 1000 korda (10-lt 10000-le), kuid kontrollide arv kasvas vaid 3,5 korda (4-lt 14-le). Binaarse otsingu algoritmi keerukus on logaritmiline või kui kasutame Big-O tähistust, - O(log n). Miks seda nii nimetatakse? Logaritm on astmeni tõstmise pöördväärtus. Kahendlogaritmi kasutatakse 2 astme arvutamiseks. Näiteks on meil 10 000 elementi, mida peame kahendotsingu abil läbima. 
Nüüd on teil pilt silme ees ja teate, et selleks on vaja maksimaalselt 14 kontrolli. Aga mis siis, kui silme ees pole pilti ja peate loendama täpse arvu vajalikke kontrolle? Piisab, kui vastata lihtsale küsimusele: Millise astmeni tuleks tõsta arv 2, et tulemuseks oleks >= kontrollitavate elementide arv? 10 000 eest on see 14. võimsus. 2 kuni 13. aste on liiga vähe (8192) Aga 2 kuni 14. astmeni = 16384, see arv vastab meie tingimusele (see on >= massiivi elementide arv). Leidsime logaritmi – 14. Just nii palju tšekke vajame! :) Algoritmid ja nende keerukus on liiga mahukas teema, et ühte loengusse mahutada. Kuid selle teadmine on väga oluline: paljudes intervjuudes saate algoritmiprobleeme. Teooria osas võin teile soovitada mitmeid raamatuid. Hea koht alustamiseks on YouTube'i suur video. Kohtumiseni järgmistel loengutel! :) Tähtaeg: 8. jaanuar 2010 Enne määratud tähtaega ei tohiks teised projektis osalejad artiklit toimetada. veebisait. Pärast lõpetamist on igal osalejal õigus seda artiklit oma äranägemise järgi parandada ja see hoiatus, mis kuvatakse malli ((Ülesanne)) abil, eemaldada.
Vaata ka juhised Ressursi kasutamise kohta veebisait haridusprotsessis.
Arvutusliku keerukuse teooria- arvutusteooria haru, mis uurib arvutusülesande lahendamiseks vajalikku töömahtu.
Probleemi peetakse keeruliseks, kui ülesande lahendamine nõuab palju ressursse, sõltumata selle lahendamiseks kasutatud algoritmist. Teooria vormistab selle intuitiivse kontseptsiooni, võttes kasutusele matemaatilised arvutusmudelid, et uurida neid probleeme ja kvantifitseerida nende lahendamiseks vajalike ressursside hulk, näiteks kasutatud aeg ja mälu. Võimalikud on ka muud keerukuse mõõdud, näiteks: sõnumite arv (kommunikatsiooni keerukus), elementide arv funktsionaalsete elementide ahelas (ahela keerukus) ja protsessorite arv. Eelkõige määratlevad arvutusliku keerukuse teooriad praktilised piirid sellele, mida arvutid saavad teha ja mida mitte.
Arvutusliku keerukuse teooriatega on tihedalt seotud algoritmide analüüs ja arvutatavuse teooria. Peamine erinevus arvutusliku keerukuse teooria ja algoritmide analüüsi vahel seisneb selles, et viimane tegeleb konkreetse algoritmi jaoks probleemi lahendamiseks vajaliku ressursside hulga analüüsimisega, samas kui esimene esitab üldisema küsimuse kõigi võimalike algoritmide kohta, mida saaks kasutada lahenda sama probleem.probleem. Täpsemalt, arvutusliku keerukuse teooria püüab klassifitseerida probleeme, mida saab või ei saa lahendada sobiva hulga piiratud ressurssidega. Olemasolevatele ressurssidele piirangute kehtestamine on omakorda see, mis eristab arvutusliku keerukuse teooriat arvutatavuse teooriast: viimane küsib, milliseid probleeme saab põhimõtteliselt lahendada algoritmiliselt ilma arvutusressursse piiramata.
Arvutusprobleemid
Ülesande esinemised
Arvutusülesandeid võib vaadelda kui lõpmatut paaride kogumit: (ülesande eksemplar, antud eksemplari lahendus). Arvutusülesande sisendstring on probleemi eksemplari kirjeldav string. Arvutusülesande väljundstring on sisendstringiga kirjeldatud probleemi eksemplari lahenduse kirjeldus. Näiteks arvu algväärtuse äratundmise probleem: ülesande eksemplar on arv, mille puhul on vaja kindlaks teha, kas see on algarv või mitte, lahenduseks on string "jah", kui see arv on algarv ja " ei” muidu. Arvutusliku keerukuse teooria arvestab ainult massiivseid probleeme, s.t. ülesande esinemisjuhtude lõputu hulga nõue on kohustuslik.
Ülesande vaade
Arvutusprobleeme käsitledes on probleemieksemplari kirjelduseks rida tähestiku kohal. Reeglina võetakse tähestikku binaarne (st hulk (0,1)). Erinevad matemaatilised objektid tuleb vastavalt kodeerida. Näiteks saab täisarve esitada binaarselt ja graafikuid saab kodeerida otse nende naabrusmaatriksite või naabrusloendite binaarse kodeerimise kaudu.
Tunnustamise ülesanded
Äratundmisprobleemid on arvutusliku keerukuse teooria üks keskseid uurimisobjekte. Tuvastamisprobleem on arvutusülesannete eriliik, mille vastus on kas "jah" või "ei" (1 või 0). Tuvastamisprobleemi saab sõnastada ülesandena, kas sisendstring kuulub kõigi sisendstringide hulga teatud alamhulka (keelde). Sisendprobleemi string kuulub vastavasse keelde siis ja ainult siis, kui vastus sellele stringile on "jah". Seega on äratundmisülesanne ülesanne tuvastada, kas sisendstring kuulub teatud keelde.
Tuvastamisülesande näide. Sisendrida: suvalise graafiku kirjeldus. Probleem on otsustada, kas antud graaf on ühendatud või mitte. Ühendatud graafikute keel on kõigi ühendatud graafikute kirjelduste kogum. Selle keele täpse määratluse saamiseks tuleb otsustada, kuidas graafikud kodeeritakse binaarstringidena.
Otsi ülesandeid
Otsinguülesanne on arvutuslik ülesanne, mille väljundväärtus on keerulisem kui tuvastusülesande puhul (st see ei ole lihtsalt "jah" või "ei").
Otsinguprobleemi näide on reisiva müügimehe probleem. Rändmüüja probleem (rändkaupmees – rändkaupmees) on üks tuntumaid kombinatoorse optimeerimise probleeme. Ülesandeks on leida kõige tulusam marsruut, mis läbib nimetatud linnu vähemalt korra ja naaseb seejärel algsesse linna. Probleemi tingimustes on märgitud marsruudi tasuvuse kriteerium (lühim, odavaim, koondkriteerium jne) ja vastavad vahemaade, kulude jms maatriksid. Üldjuhul on märgitud, et marsruut peaks läbima iga marsruudi linn ainult üks kord - sellisel viisil Sel juhul tehakse valik Hamiltoni tsiklite hulgast. Sisendstring: kaalutud (st numbriliste siltidega servadel) graafiku kirjeldus. Väljundrida on reisiva müügimehe optimaalse marsruudi kirjeldus.
Tuvastamisülesannete ja otsinguülesannete vahel on paarisuhe. Otsinguprobleemi saab sõnastada äratundmisprobleemina. Näiteks otsinguülesande „kahe arvu korrutamine” korral saab vastava paarilise tuvastamise ülesande esitada kolmikute (A, B, C) kogumina, nii et seos A × B = C kehtib.
Mõõtmisraskused
Arvutusliku keerukuse teooria tekkis vajadusest võrrelda algoritmide jõudlust ja selgelt kirjeldada nende käitumist (käitumisaeg, vajaliku mälu maht jne) sõltuvalt sisendi ja väljundi suurusest.
Algoritmi poolt probleemi konkreetse esinemisjuhtumi lahendamiseks kulutatud elementaaroperatsioonide arv ei sõltu mitte ainult sisendandmete suurusest, vaid ka andmetest endast. Näiteks sisestussortimisalgoritmi toimingute arv on palju väiksem, kui sisendandmed on juba sorteeritud. Selliste raskuste vältimiseks kaaluge algoritmi halvima aja keerukuse kontseptsiooni.
Algoritmi ajaline keerukus (halvimal juhul) on sisend- ja väljundandmete suuruse funktsioon, mis on võrdne algoritmi poolt sooritatud aatomoperatsioonide maksimaalse arvuga, et lahendada kindlaksmääratud suurusega probleemieksemplar. Ülesannetes, kus väljundi suurus ei ole suurem või võrdeline sisendi suurusega, saab ajalist keerukust vaadelda ainult sisendi suuruse funktsioonina.
Sarnaselt ajalise keerukuse mõistega halvimal juhul defineeritakse parimal juhul ka algoritmi aja keerukuse mõiste. Vaatleme ka algoritmi keskmise tööaja mõistet ehk algoritmi tööaja matemaatilist ootust. Mõnikord öeldakse lihtsalt: "Algoritmi ajaline keerukus" või "Algoritmi tööaeg", mis tähendab algoritmi ajalist keerukust halvimal, parimal või keskmisel juhul (olenevalt kontekstist).
Analoogiliselt ajalise keerukusega määratakse algoritmi ruumiline keerukus, ainult et siin ei räägita elementaartehte arvust, vaid kasutatava mälu mahust.
Vaatamata sellele, et algoritmi aja keerukuse funktsiooni saab mõnel juhul täpselt määrata, on enamasti mõttetu selle täpset väärtust otsida. Asi on selles, et esiteks sõltub aja keerukuse täpne väärtus elementaartehte definitsioonist (näiteks keerukust saab mõõta aritmeetiliste tehete või Turingi masina tehete arvus) ja teiseks sisendandmete suurusest. suureneb, muutub täpse tööaja avaldises esinevate konstantsete tegurite ja terminite madalama järgu panus äärmiselt ebaoluliseks.
Suurte sisendandmete arvestamine ja algoritmi tööaja kasvujärjekorra hindamine viib algoritmi asümptootilise keerukuse kontseptsioonini. Lisaks on madalama asümptootilise keerukusega algoritm tõhusam kõigi sisendandmete puhul, välja arvatud väikesed andmed.
Keerukus määratakse selle arvutusmudeli alusel, milles arvutused tehakse.
Arvutuslikud mudelid
Arvutustehnikas on palju erinevaid mudeleid: Postmasin, Minsky masin, lambda-arvutus, osaliselt rekursiivsed funktsioonid, tavalised Markovi algoritmid, muutmälumasinad (RAM-masinad) jne. Mainime vaid kõige populaarsemat arvutusmudelit - Turingi masin.
Turingi masin
Turingi masin (MT) on abstraktne teostaja (abstraktne arvutusmasin). Alan Turing tegi 1936. aastal ettepaneku vormistada algoritmi mõiste.
Turingi masin on lõpliku olekumasina laiendus ja on Church-Turingi teesi kohaselt võimeline simuleerima kõiki teisi täitjaid (määrates üleminekureeglid), mis mingil moel rakendavad samm-sammult arvutamise protsessi, milles iga arvutamise samm on üsna elementaarne.
Turingi masin koosneb lindist, mis on mõlemas suunas lõpmatu (võimalikud on Turingi masinad, millel on mitu lõpmatut linti), mis on jagatud rakkudeks, ja juhtseadmest, mis võib olla ühes paljudest olekutest. Juhtseadme võimalike olekute arv on piiratud ja täpselt määratletud.
Juhtseade võib liikuda mööda linti vasakule ja paremale, lugeda ja kirjutada lindi lahtritesse mõne lõpliku tähestiku sümboleid. Eraldatakse spetsiaalne tühi sümbol, mis täidab kõik lindi lahtrid, välja arvatud need (lõplik arv), millele on kirjutatud sisendandmed.
Juhtseade töötab üleminekureeglite järgi, mis esindavad antud Turingi masina poolt rakendatud algoritmi. Iga üleminekureegel käsib masinal olenevalt hetkeolekust ja praeguses lahtris vaadeldavast sümbolist kirjutada sellesse lahtrisse uus sümbol, liikuda uude olekusse ja liigutada üks lahter vasakule või paremale. Mõnda Turingi masina olekut saab märkida terminaliks ja üleminek ükskõik millisele neist tähendab töö lõppu, algoritmi peatamist.
Turingi masinat nimetatakse deterministlikuks, kui igale oleku ja lindi sümboli kombinatsioonile tabelis on vastav maksimaalselt üks reegel. Kui on paar (lindi sümbol - olek), mille jaoks on 2 või enam käsku, nimetatakse sellist Turingi masinat mittedeterministlikuks.
Turingi masina mudel võimaldab erinevaid laiendusi. Vaadelda võib suvalise arvu lintidega Turingi masinaid ja erinevate piirangutega mitmemõõtmelisi linte; masinad, mis kasutavad juhuslikkuse allikat.
Turingi masin on keerukusteoorias üks peamisi arvutusmudeleid.
Raskusastmed
Keerukusklassid on arvutusprobleemide kogumid, mis on arvutusliku keerukusega ligikaudu võrdsed. Seal on keele keerukuse klassid ja funktsionaalse keerukuse klassid. Keelte keerukusklass on predikaatide kogum (funktsioonid, mis võtavad sisendiks sõna ja tagastavad vastuseks 0 või 1), mis kasutavad arvutamiseks ligikaudu sama palju ressursse. Funktsionaalse keerukuse klassi mõiste on sarnane, välja arvatud see, et see ei ole predikaatide kogum, vaid funktsioonide kogum. Keerukuse teoorias on vaikimisi keerukuse klass keelte keerukusklass. Tüüpiline keerukusklassi määratlus näeb välja selline:
Keerukusklass X on predikaatide hulk P(x), mis on arvutatav Turingi masinatel ja kasutades arvutamiseks O(f(n)) ressursse, kus n on sõna x pikkus.
Ressursiks võetakse tavaliselt arvutusaeg (Turingi masina töötsüklite arv) või tööpiirkond (kasutatud rakkude arv lindil töötamise ajal). Samasse klassi kuuluvad ka keeled, mida tunnevad ära mõne klassi predikaadid (see tähendab sõnade kogum, milles predikaat tagastab 1).
Lisaks saab paljusid klasse kirjeldada ka matemaatilise loogika või mänguteooria kaudu.
Klassid on tavaliselt tähistatud suurtähtedega. Klassi C komplementi (st keelte klassi, mille täiendid kuuluvad C-sse) tähistatakse kaas-C-ga.
Iga klassi jaoks on ülesannete kategooria, mis on "kõige raskem". See tähendab, et iga klassi ülesanne taandub selliseks ülesandeks ja pealegi seisneb ülesanne ise klassis. Selliseid ülesandeid nimetatakse antud klassi täisülesanneteks.
P klass
Klass P (inglisekeelsest polünoomist) on äratundmisülesannete kogum, mida saab lahendada deterministlikul Turingi masinal sisendi pikkuse ajapolünoomis. Samamoodi on otsinguülesannete jaoks defineeritud klass FP (inglise funktsionaalsest polünoomist).
Formaalsemalt kaaluge deterministlikke Turingi masinaid, mis arvutavad vastuse, mis on antud sõnale, sisendlindil antud sisendtähestiku järgi. Turingi masina tööaeg fikseeritud sisendsõna jaoks x Nimetatakse Turingi masina töötsüklite arvu masina algusest kuni lõpuni. Mõne Turingi masina arvutatud funktsiooni keerukus on funktsioon, mis sõltub sisendsõna pikkusest ja on võrdne masina maksimaalse tööajaga kõigi fikseeritud pikkusega sisendsõnade puhul:
.Kui funktsiooni jaoks f seal on Turingi masin M selline, et mõne numbri jaoks c ja piisavalt suur n, siis nad ütlevad, et see kuulub klassi FP või on ajas polünoom.
Klass P on arvutusliku keerukuse teooria üks põhiklasse.
NP klass
NP klass (inglise keelest non-deterministic polynomial) on äratundmisülesannete kogum, mille lahendamise aeg sõltub oluliselt sisendandmete suurusest; samas on olemas algoritm, mis saab koos sisendväärtuste kirjeldusega lisateavet (lahenduse tunnistaja) lahendada ülesande üsna kiiresti (ajaga, mis ei ületa polünoomi andmete suurus).
Formaalsemalt öeldakse, et keel L kuulub klassi NP, kui klassist P on olemas kahekohaline predikaat R(x, y) (st on arvutatav polünoomilise aja järgi) ja polünoom p, nii et mis tahes sõna jaoks x pikkusega n tingimus "x kuulub L-sse" on samaväärne tingimusega "on y pikkus väiksem kui p(n), nii et R(x, y) on tõene." Sõna y nimetatakse tunnistajaks, et x kuulub keelde L. Seega, kui meil on keelde kuuluv sõna ja mõni teine tunnistajasõna, mille pikkus on piiratud (mida võib olla raske leida), saame kiiresti kontrollida, et x kuulub tõesti L-le. Iga NP-sse kuuluvat ülesannet saab lahendada eksponentsiaalse aja jooksul, otsides läbi kõik võimalikud tunnistajad, mille pikkus on väiksem kui p(n).
Näidisülesanne NP-st: äratundmisülesanne "Lineaarse ebavõrdsuse süsteemi täisarvlahenduse olemasolu." Tunnistaja on lahendus ebavõrdsuse süsteemile. Tunnistajalahenduse sobivust on polünoomilise aja järgi lihtne kontrollida.
NP-klass sisaldab P-klassi.
Avatud probleemid
Arvutusliku keerukuse teoorias on palju lahendamata probleeme, need puudutavad peamiselt teatud keerukusklasside jagamise või pesastamise küsimusi. Üks neist küsimustest on klasside P ja NP võrdsuse probleem.
Klasside P ja NP võrdsuse probleem
Lõppkokkuvõttes on klassivõrdsuse P ja NP probleem järgmine: kui küsimuse positiivset vastust saab kiiresti kontrollida (polünoomilises ajas), siis kas on tõsi, et sellele küsimusele saab vastuse kiiresti (polünoomilises ajas) leida?
Klasside P ja NP määratlusest tuleneb kohe järgmine järeldus: . Selle kaasamise rangusest pole aga veel midagi teada, s.t. kas on olemas algoritm, mis peitub NP-s, aga mitte P-s Kui sellist algoritmi ei eksisteeri, siis on kõik klassi NP kuuluvad ülesanded lahendatavad polünoomilises ajas, mis tõotab arvutuslikust seisukohast tohutut kasu. Praegu on kõige keerulisemad NP-ülesanded (nn NP-täielikud probleemid) lahendatavad eksponentsiaalse aja jooksul, mis on peaaegu alati vastuvõetamatu.
Nende kahe klassi võrdsuse küsimust peetakse üheks kõige keerulisemaks lahtiseks probleemiks teoreetilise arvutiteaduse valdkonnas. Praegu usub enamik matemaatikuid, et need klassid ei ole võrdsed. Savi Matemaatika Instituut lisas selle probleemi aastatuhande probleemide nimekirja, pakkudes selle lahendamise eest tasu miljon USA dollarit.
Kirjandus
- Gehry M., Johnson D. Arvutusmasinad ja raskesti lahendatavad probleemid. Kirjastus Mir 1982. aastal. - 420 s. Ameerika teadlaste monograafia on pühendatud keerukate (sh NP-kõvade) kombinatoorsete probleemide lahendamisele, mis tekivad diskreetse optimeerimise, matemaatilise programmeerimise, algebra ja automaatide teoorias koos näidetega.
- Corman, Thomas H.; Leiserson, Charles I.; Rivest, Ronald L.; Stein, Clifford Algorithms: Construction and Analysis, 2nd edition = Introduction to Algorithms second edition. - M.: "Williams", 2005. -
| Määramine | Intuitiivne selgitus | Definitsioon |
|---|---|---|
| fülalpool piiratud funktsiooniga g | style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/101/eebfe73c29ff3f9bc886d263bd3e91f3.png" border="0"> or style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0"> | |
| f allpool piiratud funktsiooniga g(kuni konstantse tegurini) asümptootiliselt | style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/48/0fda981f377ae7b8d361f58ce148c173.png" border="0"> | |
| f all ja ülalt piiratud funktsiooniga g asümptootiliselt | 0), n_0: \forall (n>n_0) \; |Cg(n)| | |
| g domineerib f asümptootiliselt | style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/49/176ce786e936badb831a0bb87f25249d.png" border="0"> | |
| f domineerib g asümptootiliselt | style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/53/554bc3f42cfa6d0638722e58e4a99d8b.png" border="0"> | |
 |
f samaväärne g asümptootiliselt |  |
Näited
Märkmed
Tuleb rõhutada, et halvima juhtumi täitmise aja kasvu määr ei ole algoritmide ja programmide hindamisel ainus ega kõige olulisem kriteerium. Siin on mõned kaalutlused, mis võimaldavad teil vaadata käitusaja kriteeriumi teistest vaatenurkadest.
Kui n-tipulise graafi teatud ülesande lahendamine ühe algoritmiga võtab aega (sammude arv) suurusjärgus n C ja teisega - suurusjärku n+n!/C, kus C on konstantne arv, siis “polünoomilise ideoloogia” järgi on esimene algoritm praktiliselt efektiivne , teine aga mitte, kuigi näiteks C = 10 (10 10) korral on olukord just vastupidine.
- Tõhusad, kuid keerulised algoritmid võivad olla ebasoovitavad, kui valmisprogramme haldavad isikud, kes ei ole nende programmide kirjutamisega seotud. Loodame, et tõhusate algoritmide loomise tehnoloogia põhiaspektid on laialdaselt teada ja üsna keerukaid algoritme kasutatakse praktikas vabalt. Siiski tuleb arvestada võimalusega, et tõhusad, kuid "keerukad" algoritmid ei ole nende keerukuse ja nende mõistmisel tekkivate raskuste tõttu nõudlikud.
- On mitmeid näiteid, kus tõhusad algoritmid nõuavad nii suuri arvutimälu (ilma aeglasema välise andmekandja kasutamise võimaluseta), et see tegur tühistab algoritmi "tõhususe" eelise.
- Numbriliste algoritmide puhul pole algoritmide täpsus ja stabiilsus vähem tähtsad kui nende ajaline efektiivsus.
Raskusastmed
Keerukusklass on äratundmisprobleemide kogum, mille jaoks on arvutusliku keerukuse poolest sarnased algoritmid. Kaks olulist esindajat:
P klass
Klasside P ja NP võrdsuse probleem
Kuulsad teadlased
- Leonid Levin
- Aleksander Razborov
- Eddie Shamir
Vaata ka
Lingid
- Juri Lifshits "Teoreetilise arvutiteaduse kaasaegsed probleemid". NP-raskete probleemide algoritmide loengute kursus.
- A. A. Razborov Teoreetiline arvutiteadus: matemaatiku vaade // Arvuti. - 2001. - nr 2. (alternatiivne link)
- A. A. Razborov Arvutuste keerukuse kohta // Matemaatiline haridus. - MCNMO, 1999. - Nr 3. - Lk 127-141.
Wikimedia sihtasutus. 2010. aasta.
Vaadake, mis on "algoritmi ajaline keerukus" teistes sõnaraamatutes:
ajaline keerukus (algoritmi)- — Teemad infokaitse ET aja keerukus… Tehniline tõlkija juhend
OPERAATORI TEGEVUSTE KEERUKUS- objektiivsete tegurite kogum, mis mõjutab juhtimissüsteemis nõutavate funktsioonide täitmise kvaliteeti ja kestust. S. o. jne jaguneb mitmeks tüübiks, millest igaüht iseloomustab teatud viisil tegurite kombinatsioon... ... Psühholoogia ja pedagoogika entsüklopeediline sõnastik
Arvutusfunktsioon, mis annab numbrilise hinnangu algoritmi lähteandmetele rakendamise protsesside keerukusele (kohmakusele). Selgitades A. s. arvutusi teenindab signaalimisfunktsiooni (või lihtsalt signaalimisfunktsiooni) mõiste, mis on antud... ... Matemaatiline entsüklopeedia
Arvutiteaduses ja algoritmiteoorias on algoritmi arvutuslik keerukus funktsioon, mis määrab mõne algoritmi poolt tehtava töö mahu sõltuvuse sisendandmete suurusest. Arvutuslikku keerukust uurivat osa nimetatakse teooriaks... ... Vikipeediaks
Arvutiteaduses on arvutusliku keerukuse teooria arvutusteooria haru, mis uurib arvutusprobleemi lahendamiseks vajaliku töö maksumust. Väärtust mõõdetakse tavaliselt abstraktsete aja ja ruumi mõistetega, mida nimetatakse... ... Vikipeediaks
See on algoritm elementide järjestamiseks loendis. Kui loendiüksusel on mitu välja, nimetatakse järjestuskriteeriumiks kasutatavat välja sortimisvõtmeks. Praktikas kasutatakse sageli võtmena numbrit ja muudes valdkondades... ... Vikipeedia
Sorteerimisalgoritm on algoritm elementide järjestamiseks loendis. Kui loendiüksusel on mitu välja, nimetatakse järjestuskriteeriumiks kasutatavat välja sortimisvõtmeks. Praktikas kasutatakse numbrit sageli võtmena ja ... ... Vikipeedias
- (GM) avaliku võtmega krüptograafiline süsteem, mille töötasid välja Shafi Goldwasser ja Silvio Micali 1982. aastal. GM on esimene tõenäosuslik avaliku võtmega krüpteerimisskeem, mis on standardse krüptograafilise meetodi korral tõestatult tugev... ... Wikipedia Loe edasi
Tihti on ühe ja sama probleemi lahendamiseks võimalik välja mõelda rohkem kui üks algoritm. Sellega seoses tekib küsimus: milline algoritmidest on "parem"?
Enamasti on "parem" ilmselt algoritm, mis samu sisendandmeid kasutades jõuab probleemile lahenduseni, kulutades vähem arvutusressursse (mälu ja aega). See pole muidugi range põhjendus. Rangema arutelu jaoks tutvustame mitmeid mõisteid.
Algoritmi arvutusprotsess on sammude jada, mis tehakse algoritmi täitmisel teatud sisendandmete jaoks.
Oluline on mõista erinevust algoritmi enda ja selle algoritmi genereeritud arvutusprotsessi vahel. Esimene on ainult kirjeldus teiseks.
Algoritmi ajaline keerukus on aeg \(T\), mis kulub teatud sisendandmete jaoks algoritmi arvutusprotsessi lõpuleviimiseks.
On selge, et täitmise aeg sõltub konkreetsest esinejast. Oletame, et elektrooniline kalkulaator ja superarvuti töötavad tõenäoliselt erinevatel aegadel sama algoritmi.
Aega \(T\) saab aga väljendada elementaartoimingute arvu \(k\) ja elementaartoimingu sooritamise keskmise aja \(t\) kaudu:
Lisaks on \(k\) omadus ise algoritm ja \(t\) on esitaja omadus.
Tulenevalt asjaolust, et \(t\) võib antud täitja puhul pidada konstandiks, hinnatakse algoritmide keerukust tavaliselt kuni konstantse tegurini. Teisisõnu, algoritmi keerukus on hinnanguline kasvu järjekord.
Kasvu järjekord Positiivsel kindlal funktsioonil \(g(x)\) on kasvujärjekord \(f(x)\) (kirjutatud \(g(x)=\mathcal(O)(f(x))\)) kui \(\exists c>0: \: \forall x>x_0, \, g(x) \leq c f(x)\).
Sõltuvalt sisendandmetest võib algoritm töötada erinevatel aegadel. Tavaliselt hinnatakse keskmine keerukus ja keerukus halvimal juhul. Samuti on sõltuvus sellest kogused sisendandmed \(n\) . Tavaliselt hinnatakse kasvu järjekorda alates \(n\).
Näiteks on andmete lugemise ja massiivina mällu salvestamise keerukus \(\mathcal(O)(n)\) või lineaarne keerukus, ja maatrikskorrutamine on juba olemas kuupmeetrit\(\mathcal(O)(n^3)\) .
Lisaks algoritmi ajalisele keerukusele osutub see ka oluliseks ruumiline algoritmi keerukus.
Algoritmi ruumiline keerukus on arv lisaks mälu \(S\), mida algoritm tööks vajab. Sisendandmete salvestamiseks vajalik mälu \(D\) ei sisaldu \(S\) .
\(S\) oleneb üldiselt ka täiturmehhanismist. Oletame, et kui kaks täitmisseadet toetavad vastavalt 4 ja 8 baidi pikkuseid täisarve, siis on algoritmi ruumiline keerukus 8-baidiliste täisarvude puhul kaks korda suurem kui 4-baidiste täisarvude puhul. Seetõttu hinnatakse ka ruumilist keerukust kasvujärjekorra järgi.
Algoritmi keerukusklassid
Teatud raskusklassid: need on sarnase keerukusega kategooriad.
Eristatakse järgmisi peamisi raskusastmeid:
DTIME Turingi masin leiab ülesandele lahenduse piiratud aja (sammude arvu) jooksul. Algoritmi asümptootilist käitumist täpsustatakse sageli, nii et kui tööaja pikenemise järjekord on \(T(n) = \mathcal(O)(f(n))\), siis näidata \(DTIME(f) (n))\) . P Turingi masin leiab ülesandele lahenduse polünoomilises ajas (sammude arvus), s.o. \(T(n) = \mathcal(O)(n^k)\) , kus \(k\in \mathbb(N)\) . \(P=DTIME(n^k)\) EXPTIME Turingi masin leiab ülesandele lahenduse eksponentsiaalse aja (sammude arvu) järgi, s.t. \(T(n) = \mathcal(O)(2^(n^k))\), kus \(k\in \mathbb(N)\) . \(EXPTIME=DTIME(2^(n^k))\) . DSPACE Turingi masin leiab probleemile lahenduse, kasutades piiratud hulka lisamälu (rakke). Algoritmi asümptootilist käitumist täpsustatakse sageli, nii et kui mälutarbimise kasvu järjekord on \(S(n) = \mathcal(O)(f(n))\), siis näidata \(DSPACE(f) (n))\) . L Turingi masin leiab lahenduse logaritmilise ruumilise keerukusega ülesandele, st \(S(n) = \mathcal(O)(\log n)\). \(L=DSPACE(\log n)\) . PSPACE Turingi masin leiab lahenduse polünoomruumi keerukusega ülesandele, st \(S(n) = \mathcal(O)(n^k)\) , kus \(k\in \mathbb(N)\ ) . \(PSSPACE=DSPACE(n^k)\) . EXPSPACE Turingi masin leiab lahenduse eksponentsiaalse ruumilise keerukusega probleemile, st \(S(n) = \mathcal(O)(2^(n^k))\), kus \(k\in \mathbb(N)\) . \(EXPSPACE=DSPACE(2^(n^k))\) .
Lisaks on teoreetilised keerukusklassid, mis toimivad selle kontseptsiooni alusel mittedeterministlik Turingi masinad (TMT). Nende määratlused on samad, mis ülal, Turingi masin on asendatud NMT-ga ja nende nimede ees on N (näiteks NP), välja arvatud NTIME ja NSPACE, kus D on asendatud N-ga.
NMT on puhtalt teoreetiline konstruktsioon, mis on tööpõhimõtetelt sarnane MT-ga, selle erinevusega, et iga oleku jaoks võib olla mõned võimalikud toimingud. Samal ajal valib NMT võimalike toimingute hulgast alati selle, mis viib lahenduseni minimaalse võimaliku arvu sammudega. Samaväärselt teostab NMT arvutusi kõik hargneb ja valib haru, mis viib lahenduseni minimaalse võimaliku arvu sammudega.
Mõnikord võite kuulda, et kvantarvutid on NMT rakendus. Kuigi see võib mõnel juhul tõsi tunduda, on NMT üldiselt võimsam süsteem kui kvantarvuti.
On teada, et \(P \subseteq NP \subseteq PSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE\)
Lisaks \(P \subsetneq EXPTIME\) , \(NP \subsetneq NEXPTIME\) , \(PSPACE \subsetneq EXPSPACE\)
Samuti on teada, et kui \(P = NP\) , siis \(EXPTIME = NEXPTIME\) .
P ja NP võrdsuse küsimus on tänapäeva arvutiteaduse üks peamisi lahendamata küsimusi.
Algoritmide näited
Toome mõned näited lihtsatest algoritmidest ja kaalume nende keerukust.
Tõstmine terve võimsuseni
Seda algoritmi kirjeldati Vana-Indias enne meie ajastut ja seda kasutatakse reaalarvu \(x\) loomuliku võimsuse \(n\) arvutamiseks.
- Kirjutage \(n\) kahendarvusüsteemis
- Asendage selles kirjes kõik 1-d tähepaariga KH ja iga 0 tähega K
- Kriipsutage maha vasakpoolseim paar KX
- Lugedes saadud stringi vasakult paremale, K-tähega kohtudes tee tulemus ruudus ja X-tähega kohtudes korruta tulemus x-ga. Alguses on tulemuseks x.
Selles algoritmis on meil hulk korrutustehteid, mis on parimal juhul võrdne binaarse esituse numbrite arvuga \(n\) ja halvimal juhul \(2(n-1)\). Igatahes ajaline keerukus.
Algoritmi efektiivseks realiseerimiseks pole praktiliselt vaja lisamälu ja see ei sõltu sisendandmetest, seega on ruumiline keerukus \(S(n) = \mathcal(O)(1)\) .
Tuleb märkida, et on olemas tõhusamaid algoritme. Kuid võrreldes "naiivse" teostusega, mis nõuab \(\mathcal(O)(n)\) korrutamistahteid, on see algoritm suhteliselt tõhus.
Täisarvude korrutamine
Seda korrutamisalgoritmi nimetatakse mõnikord vene või talupojaks, kuigi see oli tuntud juba Vana-Egiptuses.
Esimene tegur korrutatakse järjestikku kahega ja teine jagatakse 2-ga. Tulemused kirjutatakse kahte veergu, kuni teises saadakse 1.
Korrutamise tulemus on esimeses veerus olevate arvude summa, mille vastas on teise veeru paaritud arvud.
Kuna täisarvude jagamist ja 2-ga korrutamist saab rakendada nihutamise teel, loob see algoritm \(2 \log_2 n\) nihketoimingud, kus \(n\) on kahest arvust väiksem. Halvimal juhul annab sama tulemuseks \(\log_2 n - 1\) liitmistehte. Igatahes ajaline keerukus \(T(n) = \mathcal(O)(\log n)\).
Algoritmi tõhusaks rakendamiseks pole praktiliselt vaja lisamälu ja see ei sõltu sisendandmetest, seega \(S(n) = \mathcal(O)(1)\)
Jällegi tuleb märkida, et on olemas tõhusamaid algoritme. Kuid võrreldes "naiivse" teostusega, mis nõuab \(\mathcal(O)(n)\) liitmisoperatsioone, on see algoritm suhteliselt tõhus.
Näide
23 korrutamine 43-ga.
Võtame teise tegurina 23.
| 43 | 23 | kummaline |
| 86 | 11 | kummaline |
| 172 | 5 | kummaline |
| 344 | 2 | |
| 688 | 1 | kummaline |
Tulemus \(43+86+172+688 = 989\)
Saime 10 vahetusoperatsiooni ja 4 liitmisoperatsiooni. Viitamiseks \(\log_2(23) \umbes 4,52\) .
Pidev aeg
Nad ütlevad, et algoritm on algoritm pidev aeg(salvestatud kellana O(1)), kui väärtus T(n) on piiratud väärtusega, mis ei sõltu sisendi suurusest. Näiteks ühe massiivi elemendi toomine võtab pidevalt aega, kuna selle asukoha leidmiseks täidetakse üks käsk. Sorteerimata massiivi miinimumväärtuse leidmine ei ole aga konstantse aja toiming, kuna peame läbima massiivi iga elemendi. Seega võtab see tehe lineaarse aja O(n). Kui elementide arv on ette teada ja see ei muutu, võib sellisest algoritmist rääkida kui konstantse aja algoritmist.
Vaatamata nimetusele "konstantne aeg" ei pea tööaeg olema probleemi suurusest sõltumatu, kuid tööaja ülempiir ei tohiks olla. Näiteks ülesanne "vahetada väärtusi a Ja b, kui vaja, et tulemus oleks a≤b", peetakse konstantse aja probleemiks, kuigi algoritmi tööaeg võib sõltuda sellest, kas ebavõrdsus on juba kehtiv a ≤ b või mitte. Siiski on teatud konstant t, mille ülesande täitmise aeg on alati ei ületa t.
Allpool on mõned konstantsel ajal töötavad koodinäited:
Int indeks = 5; int item = loend; kui(tingimus on tõsi) siismuidu teha mõningaid toiminguid pideva tööajaga jaoks i = 1 juurde 100 jaoks j = 1 juurde 200 sooritavad mõned toimingud püsiva tööajaga
Kui T(n) on võrdne O( mingi püsiv väärtus), see on samaväärne T(n) on O(1).
Logaritmiline aeg
logaritmiline aeg, Kui T(n) = O(log n) . Kuna arvutid kasutavad kahendarvusüsteemi, kasutatakse logaritmi alusena 2 (st log 2 n). Siiski, millal aluse vahetus logaritmid log a n ja logi b n erinevad ainult konstantse teguri võrra, mis jäetakse märkuses O-suur kõrvale. Nii et O(log n) on logaritmiliste ajaalgoritmide standardne tähistus, sõltumata logaritmi baasist.
Algoritme, mis töötavad logaritmilises ajas, leitakse tavaliselt kahendpuudega toimingute tegemisel või kahendotsingu kasutamisel.
O(log n) algoritme peetakse ülitõhusaks, kuna elementide arvu suurenedes tööaeg elemendi kohta väheneb.
Väga lihtne näide sellisest algoritmist on stringi jagamine pooleks, teine pool jälle pooleks ja nii edasi. See võtab aega O(log n) (kus n on stringi pikkus, eeldame siin, et console.log Ja str.substring võtke pidevalt aega). See tähendab, et trükiste arvu suurendamiseks tuleb rea pikkust kahekordistada.
// Funktsioon rekursiivse rea parema poole printimiseks var right = funktsioon (str) (var pikkus = str. pikkus; // abistaja funktsioon var abi = funktsioon (indeks) ( // Rekursioon: prindib parem pool kui (indeks< length ) { // Trüki märgid registrist rea lõpuni konsool. log(str. alamstring(indeks, pikkus)); // rekursiivne kõne: abifunktsiooni kutsumine parema poolega abi (Math . ceil ((pikkus + indeks ) / 2 )); ) ) abi ( 0 ); )
Polüloogi aeg
Algoritm väidetavalt töötab polülogi aeg, Kui T(n) = O((log n) k), mõne jaoks k. Näiteks maatriksi korrutamise järjekorra probleemi saab lahendada polülogaritmilises ajas by paralleelse RAM-i masin .
Sublineaarne aeg
Algoritm väidetavalt töötab sublineaarne aeg, Kui T(n) = o( n). Eelkõige hõlmab see ülalloetletud aja-keerukuse algoritme, aga ka muid, nagu Groveri otsing keerukusega O( n ½).
Tüüpilised algoritmid, mis, kuigi täpsed, töötavad siiski alamlineaarses ajas, kasutavad protsesside paralleelsust (nagu ka NC 1 algoritm maatriksi determinandi arvutamiseks), mitteklassikalisi arvutusi (nagu Groveri otsingus) või millel on garanteeritud eeldus sisendi struktuur (nagu need, mis töötavad logaritmilises ajas, binaarsed otsingualgoritmid ja paljud puutöötlusalgoritmid). Kuid formaalsed konstruktsioonid, nagu kõigi stringide kogum, mille bitt 1 on stringi esimese log(n) biti määratud positsioonis, võivad sõltuda igast sisendi bitist, kuid olla ajaliselt siiski alamlineaarsed.
Tähtaeg alamlineaarse tööajaga algoritm kasutatakse tavaliselt algoritmide jaoks, mis erinevalt ülaltoodud näidetest töötavad tavalistel järjestikustel masinamudelitel ega eelda sisendstruktuuri a priori teadmisi. Nende puhul on aga tõenäosuslike meetodite kasutamine lubatud ja veelgi enam, algoritmid peavad enamiku triviaalsete probleemide puhul olema tõenäosuslikud.
Kuna selline algoritm peab andma vastuse ilma sisendandmeid täielikult lugemata, on see väga sõltuv sisendvoos lubatud juurdepääsumeetoditest. Tavaliselt voo jaoks, mis on bitistring b 1 ,...,b k, eeldatakse, et algoritm saab taotleda väärtust O(1) aja jooksul b i kellelegi i.
Sublineaarsed ajaalgoritmid on tavaliselt tõenäosuslikud ja annavad vaid ligikaudse lahenduse. Sublineaarsed käitusaegsed algoritmid tekivad uurimisel loomulikult vara kontrollid.
Lineaarne aeg
lineaarne aeg, või O( n) , kui selle keerukus on O( n). Mitteametlikult tähendab see, et piisavalt suure sisendi suuruse korral pikeneb tööaeg lineaarselt koos sisendi suurusega. Näiteks protseduur, mis summeerib loendi kõik elemendid, nõuab loendi pikkusega võrdelist aega. See kirjeldus ei ole täiesti täpne, kuna tööaeg võib täpsest proportsionaalsusest oluliselt erineda, eriti väikeste väärtuste korral n.
Lineaarset aega peetakse sageli algoritmi soovitavaks atribuudiks. (peaaegu) lineaarse või parema tööajaga algoritmide loomiseks on tehtud palju uuringuid. Need uuringud hõlmasid nii tarkvara kui ka riistvara lähenemisviise. Riistvaralise täitmise korral võivad mõned algoritmid, mis matemaatilisest vaatenurgast ei suuda standardsetes arvutusmudelites kunagi saavutada lineaarset täitmisaega, töötada lineaarses ajas. Mõned riistvaratehnoloogiad kasutavad selle eesmärgi saavutamiseks paralleelsust. Näiteks on assotsiatiivne mälu. Seda lineaarse aja kontseptsiooni kasutatakse stringide võrdlusalgoritmides, nagu Boyer-Moore'i algoritm ja Ukkoneni algoritm.
Kvaasilineaarne aeg
Algoritm töötab kvaasilineaarses ajas, kui T(n) = O( n logi k n) mõne konstantse jaoks k. Lineaar-logaritmiline aeg on erijuhtum k= 1. Kasutades nõrka O tähistust, on need algoritmid Õ( n). Kvaasilineaarsed ajaalgoritmid on samuti o( n 1+ε) iga ε > 0 korral ja töötavad kiiremini kui mis tahes polünoom in n
Algoritmid, mis töötavad kvaasilineaarses ajas, lisaks ülalmainitud lineaar-logaritmilistele algoritmidele hõlmavad järgmist:
- Kohapealne liitmise sortimine, O( n logi 2 n)
- Kiire sorteerimine, O( n logi n), on tõenäosuslikul versioonil lineaarlogaritmiline halvima juhtumi täitmise aeg. Mittetõenäosuslikul versioonil on lineaar-logaritmiline tööaeg ainult keskmise keerukuse mõõtmiseks.
- Heapsort, O( n logi n), liitmise sortimine, sisemine sortimine, kahendpuu sortimine, sujuv sortimine, pasjansi sorteerimine, jne. halvimal juhul
- Kiired Fourier teisendused, O( n logi n)
- Monge maatriksite arvutamine, O( n logi n)
Lineaar-logaritmiline aeg
Lineaarlogaritmiline on kvaasilineaarse aja erijuht astendajaga k= 1 logaritmilisel liikmel.
Lineaar-logaritmiline funktsioon on vormi funktsioon n logi n(st toode lineaarne ja logaritmilised terminid). Nad ütlevad, et algoritm töötab lineaar-logaritmiline aeg, Kui T(n) = O( n logi n) . Seega kasvab lineaarlogaritmiline liige kiiremini kui lineaarne liige, kuid aeglasemalt kui mis tahes polünoom n kraadiga, mis on rangelt suurem kui 1.
Paljudel juhtudel tööaeg n logi n on lihtsalt operatsiooni Θ(log n) nüks kord. Näiteks kahendpuu sortimine loob binaarpuu, lisades iga elemendi üksteise järel massiivi suurusega n. Alates sisestamise operatsioonist tasakaalustatud binaarne otsingupuu võtab O(log) aega n), on algoritmi täitmise koguaeg lineaarlogaritmiline.
Võrdlustüübid halvimal juhul on vaja vähemalt lineaarlogaritmilist arvu võrdlusi, kuna log( n!) = Θ( n logi n) vastavalt Stirlingi valemile. Sama täitmisaeg tuleneb sageli kordusvõrrandist T(n) = 2 T(n/2) + O( n).
Subkvadraatne aeg
Mõned näited polünoomilise aja algoritmidest:
Rangelt ja nõrgalt polünoomne aeg
Mõnes kontekstis, eriti optimeerimisel, eristatakse algoritme, millel on range polünoomaeg Ja nõrgalt polünoomne aeg. Need kaks mõistet kehtivad ainult täisarvude sisendite puhul.
Arvutamise aritmeetilises mudelis on määratletud rangelt polünoomne aeg. Selles mudelis võetakse põhilised aritmeetilised operatsioonid (liitmine, lahutamine, korrutamine, jagamine ja võrdlemine) täitmisühikutena, sõltumata operandide pikkusest. Algoritm töötab rangelt polünoomilises ajas, kui
- aritmeetilise arvutusmudeli tehtete arv on piiratud sisendvoo täisarvude arvu polünoomiga ja
- Algoritmi kasutatav mälu on piiratud sisendi suuruse polünoomiga.
Iga nende kahe omadusega algoritmi saab taandada polünoomilise aja algoritmiks, asendades aritmeetilised tehted vastavate Turingi masina aritmeetiliste toimingute sooritamise algoritmidega. Kui teine ülaltoodud nõuetest ei ole täidetud, ei vasta see enam tõele. Arvestades täisarvu (mis võtab Turingi masinas mälu võrdeliselt n-ga), saab selle arvutada n-i tehtega, kasutades korduvat eksponentsi. Esinduseks kasutatud mälu aga 2 2 n (\displaystyle 2^(2^(n))), proportsionaalne 2 n (\displaystyle 2^(n)), ja see sõltub pigem eksponentsiaalselt kui polünoomiliselt sisendiks kasutatavast mälust. Seetõttu on Turingi masinal võimatu teostada neid arvutusi polünoomilise aja jooksul, kuid neid saab teha polünoomilise arvu aritmeetiliste tehtetega.
Ja vastupidi, on algoritme, mis töötavad Turingi masina sammude arvuga, mis on piiratud binaarse kodeeritud sisendi polünoomi pikkusega, kuid ei tööta aritmeetiliste toimingute arvu puhul, mis on piiratud sisendis olevate arvude arvu polünoomiga. Üheks näiteks on eukleidiline algoritm kahe täisarvu suurima ühisjagaja arvutamiseks. Kahe täisarvu jaoks a (\displaystyle a) Ja b (\displaystyle b) Algoritmi tööaeg on piiratud O ((log a + log b) 2) (\displaystyle O((\log \ a+\log \ b)^(2))) Turingi masina sammud. See arv on arvude binaarse esituse suuruse polünoom a (\displaystyle a) Ja b (\displaystyle b), mida võib umbkaudu kujutada kui log a + log b (\displaystyle \log \a+\log \b). Samas ei saa aritmeetiliste toimingute arvu piirata sisendis olevate täisarvude arvuga (mis antud juhul on konstant - sisendis on ainult kaks arvu). Selle märkuse tõttu ei tööta algoritm rangelt polünoomses ajas. Algoritmi tegelik tööaeg sõltub kogustest a (\displaystyle a) Ja b (\displaystyle b), mitte ainult sisendis olevate täisarvude arv.
Kui algoritm töötab polünoomilises ajas, kuid mitte rangelt polünoomilises ajas, siis öeldakse, et see töötab nõrgalt polünoomne aeg. Tuntud näide probleemist, mille jaoks on teada nõrgalt polünoomne algoritm, kuid rangelt polünoomne algoritm pole teada, on lineaarne programmeerimine. Nõrga polünoomiaega ei tohiks segi ajada pseudopolünoomilise ajaga.
Raskusastmed
Polünoomilise aja mõiste viib arvutusliku keerukuse teoorias mitme keerukuse klassini. Mõned olulised polünoomiaega defineeritud klassid on toodud allpool.
- : Lahendusülesannete klass, mida saab lahendada deterministlikus Turingi masinas polünoomilises ajas.
- : lahendatavusülesannete keerukusklass, mida saab lahendada mittedeterministlikus Turingi masinas polünoomses ajas.
- ZPP: lahendatavusülesannete keerukusklass, mida saab tõenäosuslikus Turingi masinas polünoomses ajas lahendada nullveaga.
- : Lahendatavusülesannete keerukusklass, mida saab lahendada ühepoolsete vigadega tõenäosuslikus Turingi masinas polünoomses ajas.
- BPP tõenäosuslik Turingi masin polünoomses ajas.
- BQP: Lahendatavusülesannete keerukusklass, mida saab lahendada kahesuunaliste vigadega Turingi kvantmasinas polünoomses ajas.
P on deterministliku masina väikseim aja keerukusklass, mis on jätkusuutlik automudeli muutmise osas. (Näiteks ühe lindiga Turingi masinalt mitme lindiga Turingi masinale üleminek võib kaasa tuua ruutkiiruse, kuid mis tahes algoritm, mis töötab ühel mudelil polünoomilise aja järgi, töötab teisel polünoomilise aja järgi.)
Superpolünoomiline aeg
Nad ütlevad, et algoritm töötab superpolünoomne aeg, Kui T(n) ei ole ülalpool polünoomiga piiratud. See aeg on võrdne ω( n c) kõigi konstantide jaoks c, Kus n- sisendparameeter, tavaliselt sisendbittide arv.
Näiteks algoritm, mis rakendab 2 n sammud suuruse sisestamiseks n nõuab superpolünoomilist aega (täpsemalt eksponentsiaalset aega).
On selge, et eksponentsiaalseid ressursse kasutav algoritm on superpolünoom, kuid mõned algoritmid on väga nõrgalt superpolünoomilised. Näiteks, Adleman-Pomeranz-Roumeli lihtsuse test* töötab aja eest n O(logi logi n) peal n-bitine sisend. See kasvab kiiremini kui ükski piisavalt suur polünoom n, kuid sisendi suurus peab muutuma väga suureks, et selles ei domineeriks madala astme polünoom.
Superpolünoomiaega nõudev algoritm jääb keerukusklassist välja. Cobhami lõputöö väidab, et need algoritmid on ebapraktilised ja paljudel juhtudel seda ka on. Kuna klasside P ja NP võrdsuse probleem ei ole lahendatud, ei ole praegu teada ühtegi algoritmi NP-täielike ülesannete lahendamiseks polünoomses ajas.
Kvasipolünoomne aeg
Algoritmid kvaasipolünoomiline aeg on algoritmid, mis töötavad aeglasemalt kui polünoomaeg, kuid mitte nii aeglaselt kui eksponentsiaalse aja algoritmid. Kvaasipolünoomialgoritmi halvim tööaeg on c. Tuntud klassikaline algoritm täisarvu faktoriseerimiseks, , Mitte on kvaasipolünoom, kuna tööaega ei saa esitada kui 2 O ((log n) c) (\displaystyle 2^(O((\log n)^(c)))) mõne jaoks fikseeritud c. Kui kvaasipolünoomilise ajaalgoritmi definitsioonis on konstant "c" 1, saame polünoomilise aja algoritmi ja kui see on väiksem kui 1, siis alamlineaarse aja algoritmi.
Kvaasipolünoomaja algoritmid tekivad tavaliselt siis, kui NP-raske probleem muudetakse probleemiks. Näiteks võite võtta NP-raske probleemi, näiteks 3SAT, ja taandada selle teiseks probleemiks B, kuid probleemi suurus muutub 2 O ((log n) c) (\displaystyle 2^(O((\log n)^(c)))). Sel juhul ei tõesta redutseerimine, et probleem B on NP-raske, see näitab ainult seda, et B jaoks pole polünoomalgoritmi, välja arvatud juhul, kui 3SAT jaoks (ja seejärel kõigi probleemide jaoks) on kvaasipolünoomialgoritmi. Samamoodi on probleeme, mille jaoks me teame kvaasipolünoomaja algoritme, kuid mille jaoks me ei tea polünoomaja algoritme. Sellised probleemid ilmnevad lähendusalgoritmides. Kuulus näide on orienteeritud Steineri probleem, mille jaoks on ligikaudne kvaasipolünoomialgoritm lähenduskoefitsiendiga O (log 3 n) (\displaystyle O(\log ^(3)n))(kus n on tippude arv), kuid polünoom-aja algoritmi olemasolu on lahtine probleem.
Raskusaste klass QP koosneb kõikidest ülesannetest, millel on kvaasipolünoomilised ajaalgoritmid. Seda saab defineerida DTIME kaudu järgmiselt
QP = ⋃ c ∈ N DTIME (2 (log n) c) (\displaystyle (\mbox(QP))=\bigcup _(c\in \mathbb (N) )(\mbox(DTIME))(2^ ((\log n)^(c))))Ühendus NP-ga täielikud probleemid
Keerukuse teoorias küsib klasside P ja NP võrdsuse lahendamata probleem, kas kõigil klassi NP ülesannetel on polünoomaja lahendusalgoritmid. Kõigil NP-täielike probleemide tuntud algoritmidel, nagu 3SAT, on eksponentsiaalne aeg. Veelgi enam, on olemas hüpotees, et paljude loomulike NP-täielike probleemide jaoks pole subeksponentsiaalse tööajaga algoritme. Siin on "subeksponentsiaalne aeg" alljärgneva teise määratluse tähenduses. (Teisest küljest on paljud graafiteooria ülesanded, mis on loomulikult esindatud naabrusmaatriksitega, lahendatavad subeksponentsiaalse aja jooksul lihtsalt seetõttu, et sisendi suurus on võrdne tippude arvu ruuduga.) See oletus (k- SAT probleem) on tuntud kui eksponentsiaalse aja hüpotees. Kuna see eeldab, et NP-täielikel ülesannetel ei ole kvaasipolünoomaja algoritme, eeldatakse lähendamisalgoritmide valdkonnas mõningate mittelähedaste tulemuste tõttu, et NP-täielikel ülesannetel ei ole kvaasipolünoomaja algoritme. Näiteks vaadake üldtuntud tulemusi komplekti katteprobleemi mittelähendatavuse kohta.
Subeksponentsiaalne aeg
Tähtaeg subeksponentsiaalne aega kasutatakse väljendamaks, et mõne algoritmi täitmisaeg võib kasvada kiiremini kui mis tahes polünoomil, kuid jääb oluliselt väiksemaks kui eksponentsiaalne. Selles mõttes on alaeksponentsiaalse aja algoritmidega probleemid paremini jälgitavad kui ainult eksponentsiaalse ajaga algoritmid. "Subeksponentsiaalne" täpne määratlus pole veel üldiselt aktsepteeritud ja allpool esitame kaks kõige levinumat määratlust.
Esimene määratlus
Ülesanne on lahendatud subeksponentsiaalse aja jooksul, kui see on lahendatud algoritmiga, mille tööaja logaritm kasvab vähem kui mis tahes antud polünoomil. Täpsemalt öeldes on ülesandel subeksponentsiaalne aeg, kui iga ε > 0 korral on olemas algoritm, mis lahendab ülesande O(2 n ε) aja jooksul. Kõigi selliste probleemide kogum moodustab keerukuse klassi SUBEXP, mida DTIME-na saab väljendada kui .
SUBEXP = ⋂ ε > 0 DTIME (2 n ε) (\displaystyle (\text(SUBEXP))=\bigcap _(\varepsilon >0)(\text(DTIME))\left(2^(n^(\varepsilon) ))\õige))Pange tähele, et siin ei ole ε osa sisendandmetest ja iga ε jaoks võib ülesande lahendamiseks olla oma algoritm.
Teine määratlus
Mõned autorid defineerivad subeksponentsiaalset aega kui jooksuaega 2 o( n) . See määratlus võimaldab pikemaid tööaegu kui esimene määratlus. Sellise subeksponentsiaalse ajaalgoritmi näide on tuntud klassikaline täisarvude faktoriseerimise algoritm, üldine arv-välja sõela meetod, mis töötab umbes 2 O ~ (n 1/3) (\displaystyle 2^((\tilde (O))(n^(1/3)))), kus on sisendi pikkus n. Teine näide on hästi tuntud algoritm graafi isomorfismi probleemid, mille tööaeg on võrdne 2 O ((n log n)) (\displaystyle 2^(O((\sqrt (())n\log n)))).
Pange tähele, et on vahe, kas algoritm on tippude või servade arvu osas subeksponentsiaalne. IN parameetritega keerukus see erinevus tehakse selgeks, täpsustades paari , lahendatavusprobleemi ja parameetri k. SUBEPT on kõigi parameetritega ülesannete klass, mis töötavad subeksponentsiaalse aja jooksul k ja polünoomi jaoks in n :
SUBEPT = DTIME (2 o (k) ⋅ polü (n)) . (\displaystyle (\text(SUBEPT))=(\text(DTIME))\left(2^(o(k))\cdot (\text(polü))(n)\right).)Täpsemalt on SUBEPT kõigi parameetritega ülesannete klass (L , k) (\displaystyle (L,k)), mille jaoks on olemas arvutatav funktsioon f: N → N (\displaystyle f:\mathbb (N) \to \mathbb (N) ) Koos f ∈ o (k) (\displaystyle f\in o(k)) ja algoritm, mis lahendab L ajal 2 f (k) ⋅ polü (n) (\displaystyle 2^(f(k))\cdot (\text(polü))(n)).
