Reje: 1 Algoritm quramalılıǵın statikalıq hám dinamikalıq ólshewleri waqıt hám yad hajimi boyınsha qıyınshılıqlar

Algoritmlardıń waqıt hám kólemi boyincha qıyınshılıqlar
REJE:
1) Algoritm quramalılıǵın statikalıq hám dinamikalıq ólshewleri. waqıt hám yad hajimi boyınsha qıyınshılıqlar.
2) Algoritmlardı eń jaman hám ortasha xolatlarda bahalaw
3) Algoritmlardı waqıt hám kólemlik marakkabligini bahalawda tegis hám logorifmik salıstırma kriteryaları.

Algoritmdıń waqıt quramalılıǵın bahalaw. Algoritmlar quramalılıǵı funksiyalarınıń túrleri

Turaqlı jáneqt
Algoritmǵa algoritm dep ataladı turaqlı jáneqt (waqıt retinde belgilengen O (1)) baha bolsa T (n) kirisiw kólemine baylanıslı bolmaǵan baha menen sheklengen. Mısalı, dızbekte bir elementti alıw turaqlı jáneqtni aladı, sebebi onı tabıw ushın bir buyrıq atqarıladı. Biraq, tártiplenbegen dızbekte minimal bahanı tabıw turaqlı jáneqtdagi operatsiya emes, sebebi biz dızbektiń hár bir elementin skanerlashimiz kerek. Sonday etip, bul operatsiya sızıqlı waqtın aladı, O (n). Eger elementlerdiń sanı aldınan málim bolsa hám ózgermeytuǵına, bunday algoritmdı turaqlı jáneqt algoritmı dep ataw múmkin.
" Turaqlı jáneqt" atına qaramay, jumıs waqtı wazıypa kóleminden ǵárezsiz bolıwı shárt emes, lekin jumıs waqtıniń joqarı shegarası bolmawi kerek. Mısalı, " bahalardı almaslaw" wazıypası a hám b, zárúr bolsa, nátiyjede biz alamız a≤b", turaqlı jáneqt mashqalası esaplanadı, eger algoritmdıń islew waqtı teńsizliktiń bar ekenligine baylanıslı bolıwı múmkin. a ≤ b yamasa joq. Biraq, málim bir turaqlılıq ámeldegi t, olar ushın wazıypanı orınlaw waqtı mudamı aspaydı t.
Tómende turaqlı jáneqtda isleytuǵın birpara kod mısalları keltirilgen:
Int indeksi = 5; int element = dizim; eger (shárt tuwrı ) keyinboshqa turaqlı jumıs waqtı menen birpara operatsiyalardı orınlaw ushın i = 1 ushın 100 ushın j = 1 ushın 200 turaqlı jumıs waqtı menen birpara operatsiyalardı atqaradı
Eger T (n) bul O ( birpara turaqlı baha ), bul ga teń T (n) O (1) bolıp tabıladı.
Logarifmik waqıt
logarifmik waqıt, eger T (n) = O (log n)... Kompyuterler ekilik sistemadan paydalanǵanligi sebepli, logarifmdiń hasası retinde 2 isletiledi (yaǵnıy log 2). n). Biraq, menen bazanı almastırıw logaritmalar log a n hám jurnal b n tek turaqlı koefficiyent menen parıq etedi, bul bolsa O-úlken belgisinde biykar etiledi. Sonday etip, O (log n) - logarifm tiykarından qaramastan, logarifmik waqıt algoritmları ushın standart belgi.
Logarifmik waqıt algoritmları ádetde binar terek operatsiyalarında yamasa ekilik qıdırıwdan paydalanǵande tabıladı.
O (log n) algoritmları joqarı nátiyjeli esaplanadı, sebebi hár bir elementtiń atqarılıw waqtı elementler sanınıń kóbeyiwi menen azayadı.
Bunday algoritmdıń júdá ápiwayı mısalı qatardı ekige bolıw, ekinshi yarımın taǵı yarımına bolıw hám taǵı basqa. Bul O (log n) waqtın aladı (bul erda n - qatar uzınlıǵı, biz bul erda shama etemiz console. log hám str. substring turaqlı jáneqt talap etedi). Bul sonı ańlatadıki, baspalar sanın kóbeytiw ushın sızıq uzınlıǵı eki esege asırılıwı kerek.
// Sızıqtıń oń yarımın rekursiv baspadan shıǵarıw funksiyası var oń = funkciya (str) (var uzınlıǵı = kóshe uzınlıǵı ; // járdemshi funksiya var help = funkciya (indeks) ( // Rekursiya: oń yarımın baspadan shıǵarıń eger (indeks< length ) { // Belgilerdi indeksten qatar aqırıǵa shekem baspadan shıǵarıw konsol. log (str. substring (indeks, uzınlıq )); // rekursiv shaqırıw : ońı menen járdemshi funksiyanı shaqırıń járdem (Math. ceil ((uzınlıq + indeks) / 2)); )) járdem (0); )
Polilogarifmik waqıt
Algoritm jumısqa kirisiwi aytıladı polilogarifmik waqıt, eger T (n) = O ((log n) k), geyparalar ushın k... Mısalı, matritsalarni kóbeytiw tártibi máselesin polilogarifmik waqıtta sheshiw múmkin.parallel PAM mashinası.
Sublinear waqıt
Algoritm jumısqa kirisiwi aytıladı sublinear waqıt, eger T (n) = o ( n). Atap aytqanda, bul joqarıda sanap ótilgen waqıt quramalılıǵı algoritmların, sonıń menen birge basqalardı óz ishine aladı, mısalı, Grover qıdırıwı quramalılıǵı O ( n ½).
Tuwrı bolsa -de, ele da subchiziqli waqıtta isleytuǵın ádetiy algoritmlar processlerdi parallellashtirishdan (mısalı, matritsa determinantini esaplaw ushın NC 1 algoritmında ), klassik bolmaǵan esaplawlardan (Grover qıdırıwında bolǵanı sıyaqlı ) yamasa kepillik berilgen shamaǵa iye bolǵan algoritmlardan paydalanadı. kirisiwdiń dúzilisi (logarifmik waqıtta isleytuǵın, ekilik qıdırıw algoritmları hám kóplegen tereklerdi qayta islew algoritmları ). Biraq, qatardıń birinshi log (n) bıytları tárepinen anıqlanǵan jaǵdayda 1 bitga iye bolǵan barlıq qatarlar kompleksi sıyaqlı rásmiy konstruktsiyalar kirisiwdiń hár bir bitiga baylanıslı bolıwı múmkin, biraq waqıt ótiwi menen ele da tómengi sızıqlı bolıp qaladı.
Múddeti sublinear jumıs waqtı algoritmı ádetde, joqarıdaǵı mısallardan ayrıqsha bolıp esaplanıw, dástúriy izbe-iz mashina modellerinde isleytuǵın hám kirisiw strukturası haqqında aprior bilimdi talap etpeytuǵın algoritmlar ushın isletiledi. Biraq, olar ushın itimallıq usıllarınan paydalanıwǵa ruxsat beriledi hám odan da kóbirek, algoritmlar eń áhmiyetsiz máseleler ushın itimallıq bolıwı kerek.
Bunday algoritm kirisiw maǵlıwmatların tolıq o'qimasdan juwap beriwi kerekligi sebepli, bul kirisiw aǵımında ruxsat etilgen kirisiw usıllarına júdá baylanıslı. Ádetde bıyt string aǵımı ushın b 1,.. ., b k, algoritm bahanı soranıwı múmkin dep shama etiledi b i hár kim ushın i.
Sublinear waqıt algoritmları, qaǵıyda jol menende, itimallıq bolıp tabıladı hám tek shamalıq sheshimdi beredi. Sublinear jumıs waqtı algoritmları izertlew waqtında tábiy payda boladı mulkni tekseriw.
Lineer waqıt
sızıqlı waqıt, yamasa O ( n) eger onıń quramalılıǵı O bolsa ( n). Rásmiy bolmaǵan túrde, bul etarli dárejede úlken kirisiw kólemi ushın jumıs waqtı kirisiw kólemi menen sızıqlı túrde asıp barıwın ańlatadı. Mısalı, dizimdiń barlıq elementlerin jıynaytuǵın procedura dizim uzınlıǵına proportsional waqtın aladı. Bul xarakteristika tolıq anıq emes, sebebi jumıs waqtı anıq proportsionallıqtan sezilerli dárejede parıq etiwi múmkin, ásirese kishi bahalar ushın. n.
Sızıqlı waqıt kóbinese algoritmdıń kerekli atributı retinde qaraladı. (derlik) sızıqlı jumıs waqtı yamasa odan joqarı bolǵan algoritmlardı jaratıw ushın kóplegen izertlewler ótkerildi. Bul izertlewler programmalıq támiynat hám apparat jantasıwların óz ishine aladı. Úskeneni orınlaw jaǵdayında, standart esaplaw modellerinde matematikalıq tárepten hesh qashan sızıqlı orınlaw waqtına erise almaytuǵın birpara algoritmlar sızıqlı waqıtta islewi múmkin. Bul maqsetke erisiw ushın parallellikdan paydalanatuǵın birpara apparat texnologiyaları bar. Mısalı, assotsiativ yad. Bul sızıqlı waqıt túsinigi Boyer-Mur algoritmı hám Ukkonen algoritmı sıyaqlı qatarlardı salıstırıwlaw algoritmlarında qollanıladı.
Kvazilinear waqıt
Algoritm kvazizikli waqıtta isleydi, dep ataladı, eger T (n) = O ( n jurnal k n) birpara turaqlı ushın k... Sızıqlı -logarifmik waqıt menen bólek jaǵday k= 1. Hálsiz-O belgilerinen paydalanilganda, bul algoritmlar Õ ( n). Kvazilinear waqıt algoritmları da o ( n 1 + e) hár qanday e> 0 ushın hám hár qanday polinomdan tezirek isleydi n
Joqarıda aytıp ótilgen sızıqlı -logarifmik algoritmlarǵa qosımsha túrde, kvaziziiqli waqıtta isleytuǵın algoritmlarǵa tómendegiler kiredi:
• Óz jayında birlestiriw tártibi, O ( n jurnal 2 n)
• Tez tártiplew, O ( n jurnal n), itimallı versiyada eń jaman jaǵdayda sızıqlı -logarifmik atqarılıw waqtı bar. Múmkin bolmaǵan versiyada ortasha qıyınshılıqtı ólshew ushın sızıqlı jurnaldıń islew waqtı bar.
• Uyumni tańlaw, O ( n jurnal n), birlespe tártiplew, introsort, ekilik terek tártibi, tegis tártiplew, solitaire túri, hám taǵı basqa. eń jamanı
• Tez Furye ózgeriwi, O ( n jurnal n)
• Monge matritsalarini esaplaw, O ( n jurnal n)
Sızıqlı logarifmik waqıt
Sızıqlı -logarifmik - bul kórsetkishli kvazizikli waqtıniń arnawlı jaǵdayı k= 1 logarifmik hadda.
Sızıqlı logarifmik funkciya formanıń funkciyası bolıp tabıladı n jurnal n (mısalı, ónim sızıqlı hám logarifmik atamalar ). Algoritm islewi aytıladı sızıqlı -logarifmik waqıt, eger T (n) = O ( n jurnal n)... Sonday etip, sızıqlı -logarifmik element sızıqlı haddan tezirek, lekin hár qanday polinomga qaraǵanda astelew ósedi. n 1 den qatań joqarı dárejege iye.
Kóbinese jumıs waqtı n jurnal n ápiwayıǵana operatsiya nátiyjesi bolıp tabıladı t (log n) n bir ret. Mısalı, ekilik terek menen tártiplew hár bir elementti n ólshemli dızbekke Birma -bir kirgiziw arqalı ekilik terek payda etedi. Insert operatsiyasınan berli teń salmaqlılıqlı ekilik qıdırıw tereki O ni aladı (log n), algoritmdıń ulıwma atqarılıw waqtı sızıqlı -logarifmik boladı.
Salıstırıwlaw boyınsha saralaw hesh bolmaǵanda logdan berli eń jaman jaǵdaylardaǵı salıstırıwlashlarning sızıqlı jurnalın talap etedi ( n!) = Θ ( n jurnal n) Stirling formulası boyınsha. Tap sol atqarılıw waqtı kóbinese tákirarlanıw teńlemesinen kelip shıǵadı T (n) = 2 T (n/ 2) + O ( n).
Kvadrat waqıt
Polinomli waqıt algoritmlarına birpara mısallar :
Qattı hám kúshsiz polinom waqtı
Birpara kontekstlerde, ásirese optimallastırıwda, algoritmlar menen ajralıp turadı qatań polinom waqtı hám hálsiz polinom waqtı... Bul eki túsinik tek pútkil sanlardan shólkemlesken kirgiziw ushın ámel etedi.
Arifmetik esaplaw modelinde qatań polinom waqtı anıqlanadı. Bul modelde operandlar uzınlıǵınan qaramastan, atqarılıw birlikleri retinde tiykarǵı arifmetik ámeller (qosıw, ayırıw, kóbeytiw, bolıw hám salıstırıwlaw ) alınadı. Algoritm qatań polinom waqtında isleydi, eger
1. arifmetik esaplaw modelindegi operatsiyalar sanı kirisiw aǵımındaǵı pútkil sanlar sanı daǵı polinom menen sheklengen hám
2. algoritm tárepinen qollanılatuǵın yad kirisiw ólshemindegi polinom menen shegaralanadı.
Bul eki ózgeshelikke iye bolǵan hár qanday algoritmdı Tyuring mashinasında arifmetik ámellerdi orınlaw ushın tiyisli algoritmlar menen arifmetik ámellerdi almastırıw arqalı kóp atlı waqıt algoritmına keltiriw múmkin. Joqarıdaǵı talaplardıń ekinshisi atqarılmasa, bul endi tuwrı bolmaydı. Pútkil san (Tyuring mashinasında n ga proportsional yadtı iyeleydi) berilgen bolsa, onı qayta dárejege kóteriw járdeminde n ta ámelde esaplaw múmkin. Biraq, yad ańlatıw ushın isletiledi 2 2 n (\ displaystyle 2 ^ (2 ^ (n))), ga proporcional 2 n (\ displaystyle 2 ^ (n)), hám ol kirisiw ushın isletiletuǵın yadqa polinom emes, bálki eksponensial tárepten baylanıslı. Sonday eken, Tyuring mashinasında bul esaplardı kópnomli waqıtta orınlaw múmkin emes, lekin kóp atlı arifmetik ámellerdi orınlaw múmkin.
Kerisinshe, Tyuring mashinasınıń qádemler sanında isleytuǵın, ekilik kodlı kirgiziwdiń polinom uzınlıǵı menen shegaralanǵan, lekin arifmetik ámeller sanında islemeytuǵın, sanlar sanı daǵı polinom menen sheklengen algoritmlar bar. kirgiziw. Buǵan Evklidning eki pútkil sannıń eń úlken ulıwma bóliwshisin esaplaw algoritmı mısal bóle aladı. Eki pútkil san ushın a (\ displaystyle a) hám b (\ displey usılı b) algoritmdıń islew múddeti sheklengen O ((log ⁡ a + log ⁡ b) 2) (\ displaystyle O ((\ log \ a + \ log \ b) ^ (2))) Tyuring mashinasınıń qádemleri. Bul nomer sanlardıń ekilik kórinisiniń ólsheminiń polinomi bolıp tabıladı a (\ displaystyle a) hám b (\ displey usılı b), shama menen retinde ańlatılıwı múmkin log ⁡ a + log ⁡ b (\ displaystyle \ log \ a + \ log \ b)... Usınıń menen birge, arifmetik ámeller sanın kirgiziw degi pútkil sanlar sanı menen sheklep bolmaydı (bul halda bul turaqlı esaplanadı - kirgiziwde tek eki nomer ámeldegi). Bul esletpeni esapqa alǵan halda, algoritm qatań polinom waqtında islemeydi. Algoritmdıń haqıyqıy islew waqtı bahalarǵa baylanıslı a (\ displaystyle a) hám b (\ displey usılı b), tek kirisiw degi pútkil sanlar sanı emes.
Eger algoritm polinom waqtında islese, lekin qatań polinom waqtında emes, dep ataladı. hálsiz polinom waqtı... Kúshsiz kóp aǵzalılarlı algoritmı málim bolǵan, lekin qatań kóp aǵzalılarlı algoritmı belgisiz bolǵan máseleniń belgili mısalı sızıqlı programmalastırıw bolıp tabıladı. Hálsiz polinom waqtın psevdo polinom waqtı menen aralastırıp jibermaslik kerek.
Qıyınshılıq klassları
Polinom waqıt túsinigi esaplaw quramalılıǵı teoriyasında bir neshe quramalılıq klasslarına alıp keledi. Polinom waqtı járdeminde anıqlanǵan birpara zárúrli klasslar tómende kórsetilgen.
• : Polinom waqtında deterministik Tyuring mashinasında sheshiliwi múmkin bolǵan sheshiliwi múmkin bolǵan mashqalalardıń quramalılıq klası.
• : Polinom waqtında deterministik bolmaǵan Tyuring mashinasında sheshiliwi múmkin bolǵan sheshiliwi múmkin bolǵan mashqalalardıń quramalılıq klası.
• ZPP: Polinom waqtında itimallı Tyuring mashinasında nol qáte menen sheshiliwi múmkin bolǵan sheshiliwi múmkin bolǵan mashqalalardıń quramalılıq klası.
• : Polinom waqtında itimallı Tyuring mashinasında bir tárepleme qáteler menen sheshiliwi múmkin bolǵan sheshiliwi múmkin bolǵan mashqalalardıń quramalılıq klassi.
• BPP polinom waqtındaǵı itimallıq Tyuring mashinası.
• BQP: Polinom waqtında kvant Tyuring mashinasında óz-ara qáteler menen sheshiliwi múmkin bolǵan sheshiliwi múmkin bolǵan mashqalalardıń quramalılıq klassi.
P - deterministik mashina daǵı eń kishi waqıt quramalılıǵı klası, yaǵnıy turaqlı mashina modelin ózgertiw kózqarasınan. (Mısalı, bir lentali Tyuring mashinasınan kóp tarmaqlı Tyuring mashinasına ótiw kvadratik tezlikke alıp keliwi múmkin, lekin bir modelde polinom waqtında isleytuǵın hár qanday algoritm basqasında polinom waqtında isleydi.)
Super polinom waqtı
Algoritm islewi aytıladı superpolinom waqtı, eger T (n) joqarıda kóp aǵzalılar menen shegaralanbaǵan. Bul waqıt ō ga teń ( n c) barlıq konstantalar ushın c, qay jerde n kirisiw parametri, ádetde kirisiw bıytları sanı.
Mısalı, 2 ni ámelge asıratuǵın algoritm n kólemin kirgiziw ushın qádemler n superpolinom waqtın talap etedi (anıqrog'i, eksponensial waqıt).
Kórsetkishli resurslardan paydalanatuǵın algoritm superpolinom ekenligi anıq, lekin birpara algoritmlar júdá hálsiz superpolinom bolıp tabıladı. Mısalı, Adleman-Pomeranza-Roumeli ápiwayılıǵı testi * waqıt ushın isleydi n O (jurnal jurnalı n) ústinde n-bıyt kirgiziw. Ol etarlicha úlken bolǵan hár qanday polinomdan tezirek ósedi n, lekin kirisiwdiń ólshemi kútá úlken bolıwı kerek, sol sebepli ol kishi dárejedegi polinom tárepinen húkimranlıq etpesligi kerek.
Superpolinom waqıt talap etetuǵın algoritm quramalılıq klasınan sırtda. Kobhamning tezisleri bul algoritmlar ámeliy emes, dep dawa etedi hám kóbinese olar. P hám NP klasslarınıń teńligi máselesi hal etilmegenligi sebepli, házirgi waqıtta NP-tolıq máselelerdi polinom waqtında sheshiw algoritmları málim emes.
Kvazi-polinomli waqıt
Algoritmlar kvazi-polinomli waqıt Bul algoritmlar polinom waqtından astelew isleydi, lekin eksponensial waqıt algoritmları sıyaqlı aste emes. Kvazi-polinomli algoritm ushın eń jaman jumıs waqtı c... Pútkil sannı faktorlarǵa ajıratıw ushın belgili klassik algoritm, emes kvazi-polinom esaplanadı, sebebi jumıs waqtın tómendegishe ańlatpalap bolmaydı 2 O ((log ⁡ n) c) (\ displaystyle 2 ^ (O ((\ log n) ^ (c)))) geyparaları ushın turaqlı c... Kvazipolinomli waqıt algoritmı tariypidagi turaqlı " c" 1 ge teń bolsa, kóp atlı waqıt algoritmın, 1 den kishi bolsa, tómengi sızıqlı waqıt algoritmın alamız.
Kvazi-polinomli waqıt algoritmları ádetde NP-qıyın mashqalanı basqa máselege qısqartirganda payda boladı. Mısalı, siz NP ushın qıyın máseleni qabıllawıńız múmkin, mısalı, 3 SAT jáne onı basqa B mashqalasına kemeytiwińiz múmkin, biraq mashqalanıń kólemi úlkenlesedi. 2 O ((log ⁡ n) c) (\ displaystyle 2 ^ (O ((\ log n) ^ (c))))... Bunday halda, kemeytiw B mashqalası NP-qıyın ekenligin tastıyıqlamaydi; bunday kemeytiw tek B ushın polinom algoritmı joq ekenligin kórsetedi, eger 3 SAT ushın kvazipolinomli algoritm ámeldegi bolmasa (hám keyin barlıq máseleler ushın ). Tap sonday, birpara máseleler ámeldegi bolıp, olar ushın biz kvazi-polinomli waqıtlı algoritmlardı bilamiz, lekin olar ushın kóp atlı waqıtlı algoritmlar belgisiz. Bunday máseleler shamalıq algoritmlarda payda boladı. Ataqlı mısal - Shtaynerning jóneltirilgen mashqalası bolıp, ol ushın jaqınlasıw koefficiyentine iye bolǵan shamalıq kvazi-polinom algoritmı bar. O (log 3 ⁡ n) (\ displaystyle O (\ log ^ (3) n)) (bul erda n - shıńlar sanı ), lekin kóp atlı waqıt algoritmınıń bar ekenligi ashıq mashqala bolıp tabıladı.
Qıyınshılıq klassi QP kvazi-polinomli waqıt algoritmları menen baylanıslı barlıq máselelerden ibarat. Onı DTIME kózqarasınan tómendegishe anıqlaw múmkin
QP = ⋃ c ∈ N DTIME (2 (log ⁡ n) c) (\ displaystyle (\ mbox (QP)) = \ bigcup _ (c \ ın \ mathbb (N)) (\ mbox (DTIME)) (2 ^ ((\ log n) ^ (c))))
NP-tolıq máseleler menen munasábetler
Quramalılıq teoriyasında P hám NP klassları arasındaǵı teńliktiń sheshilmagan mashqalası NP klası daǵı barlıq máselelerdi polinom waqtında sheshiw algoritmları bar ekenin so'raydi. 3 SAT sıyaqlı NP-tolıq máseleler ushın barlıq belgili algoritmlar eksponensial waqıtqa iye. Bunnan tısqarı, kóplegen tábiyiy NP-tolıq máseleler ushın subeksponensial orınlaw waqtı menen algoritmlar joq degen gipoteza bar. Bul jerde “subeksponensial waqıt” tómendegi ekinshi tariyp mánisinde alınǵan. (Basqa tárepden, tábiy qońsılas matritsalar menen kórsetilgen kóplegen grafik teoriyası máseleleri subeksponensial waqıtta sheshiliwi múmkin, sebebi kirisiwdiń ólshemi shıńlar sanınıń kvadratına teń bolıp tabıladı.) Bul gipoteza (k-SAT mashqalası ushın ) retinde belgili eksponensial waqıt gipotezasi... NP-tolıq máselelerde kvazi-polinomli waqıt algoritmları joq dep shama etilgenligi sebepli, birpara jaqınlashmaslik nátiyjeleri jaqınlasıw algoritmları tarawına alıp keledi, NP-tolıq máselelerde kvazi-polinomli waqıt algoritmları joq dep shama etiledi. Mısal ushın, jıynaqtı oraw mashqalasınıń jaqınlashmasligi haqqındaǵı belgili nátiyjelerge qarang.
Subeksponensial waqıt
Múddeti subeksponensial waqıt birpara algoritmlardıń atqarılıw waqtı hár qanday kóp aǵzalılarǵa qaraǵanda tezirek ósiwi múmkinligin ańlatıw ushın isletiledi, lekin ol eksponensialdan sezilerli dárejede kemrek bolıp qaladı. Usı mánisten alıp qaraǵanda, subeksponensial waqıt algoritmları menen baylanıslı máseleler tek eksponensial waqıtlı algoritmlarǵa qaraǵanda talay maslasıwshı. " Sub-eksponensial" dıń anıq tariypi ele ulıwma qabıl etilmegen hám biz tómende eń keń tarqalǵan eki tariypni keltiremiz.
Birinshi tariyp
Eger mashqala jumıs waqtıniń logarifmi hár qanday berilgen kóp aǵzalılardan kemrek ósetuǵın algoritm menen sheshilse, mashqala subeksponensial waqıtta sheshilgen dep ataladı. Anıqlaw etip aytatuǵın bolsaq, hár qanday e> 0 ushın mashqalanı O (2 n e) waqtında sheshiwshi algoritm ámeldegi bolsa, másele subeksponensial waqıtqa iye boladı. Bunday máselelerdiń barlıǵı quramalılıq klasın quraydı SUBEXP, bul DTIME tárepinen ańlatılıwı múmkin.
SUBEXP = ⋂ e> 0 DTIME (2 n e) (\ displaystyle (\ text (SUBEXP)) = \ bigcap _ (\ varepsilon> 0) (\ text (DTIME)) \ shep (2 ^ (n ^ (\ varepsilon) ))) \ tuwrı ))
Itibar beriń, bul erda e kiritilgen maǵlıwmatlardıń bir bólegi emes hám hár bir e ushın mashqalanı sheshiwdiń ayriqsha algoritmı bolıwı múmkin.
Ekinshi tariyp
Birpara avtorlar subeksponensial waqtın jumıs waqtı retinde belgileydiler 2 o ( n). Bul tariyp birinshi tariypdan kóre uzaǵıraq islewge múmkinshilik beredi. Bunday subeksponensial waqıt algoritmına mısal retinde pútkil sanlardı faktorlarǵa ajıratıwdıń ataqlı klassik algoritmı, shama menen 100 ge jaqın waqtın quraytuǵın ulıwma sanlı maydan elek usılın keltiriw múmkin. 2 O ~ (n 1/3) (\ displaystyle 2 ^ ((\ tilde (O)) (n ^ (1/3))), kirisiwdiń uzınlıǵı qayda n... Taǵı bir mısal ushın ataqlı algoritm Grafik izomorfizm máseleleri kimning jumıs waqtı 2 O ((n log ⁡ n)) (\ displaystyle 2 ^ (O ((\ sqrt (()) n \ log n)))).
Itibar beriń, bul algoritm shıńlar sanında yamasa qırlardıń sanında sub-eksponensial bola ma, parıq etedi. v parametrlengen quramalılıq bul parq juplıq, sheshilish mashqalası hám parametrdi kórsetiw arqalı anıq kórinetuǵın boladı k. SUBEPT jılda subeksponensial waqıtta atqarılatuǵın barlıq parametrlengen máseleler klası bolıp tabıladı k hám polinom ushın n :
SUBEPT = DTIME (2 o (k) ⋅ poli (n)). (\ displaystyle (\ text (SUBEPT)) = (\ text (DTIME)) \ shep (2 ^ (o (k)) \ cdot (\ tekst (poli)) (n) \ oń).)
Anıqlaw aytqanda, SUBEPT barlıq parametrlengen wazıypalar klası bolıp tabıladı (L, k) (\ displaystyle (L, k)) onıń ushın esaplaw funkciyası ámeldegi f: N → N (\ displaystyle f: \ mathbb (N) \ tap \ mathbb (N)) Menen f ∈ o (k) (\ displaystyle f \ ın o (k)) hám sheshiwshi algoritm L dawamında 2 f (k) ⋅ poli (n) (\ displaystyle 2 ^ (f (k)) \ cdot (\ tekst (poli)) (n)).
Algoritmlardıń waqıt hám esaplaw quramalılıǵı.
Algoritmdıń waqıt quramalılıǵı (T (N), qay jerde N- tapsırmanıń ólshemi) - qádemler menen ólshenerlik algoritmdıń atqarılıw waqtı (nátiyjege erisiw ushın orınlanıwı kerek bolǵan algoritm kórsetpeleri). Yaǵnıy, bul mashqalanı sheshiw algoritmın quraytuǵın elementar operatsiyalar sanı (: =, <>, =, +,-, *, /; hám, yamasa, emes, qor; qońıraw qılıw, qaytıw ).
Mashqalanı sheshiwde kiritilgen maǵlıwmatlardıń kombinatsiyasına (ekvivalentligi, siyrekligi, tártipliligi hám kiritilgen maǵlıwmatlardıń basqa qásiyetleri) baylanıslı bolǵan úsh qıylı waqıt quramalılıǵı bar.
https://pandia. ru/text/78/183/images/image002_151.gif " keńlik =" 178 biyiklik = 60 " biyiklik =" 60 " >
Bolıp atır T (N) = C* N2 kvadrat matritsa ushın ámel etedi.
Bul halda elementar operatsiyalar " +" hám " *" kombinatsiyası esaplanadı.
Eger túp matritsa identifikaciya bolsa, biz eń jaqsı jaǵdaydı alamız.
Eger matritsada elementlerdiń yarımı 0, yarımı 1 bolsa, biz Ortasha jaǵdaydı alamız.
Turaqlı BILAN, anıq ańlatpalap bolmaytuǵın, sırtqı faktorlardıń algoritmlardı orınlaw waqtına tásirin xarakteristikalaydı (kompyuter tezligi, kompilyatsiya tezligi). Sol sebepli algoritmlardıń waqıt quramalılıǵın bahalaw ushın waqıt birliklerinen paydalanıw ulıwma tuwrı emes. Bul halda matritsa-vektordı kóbeytiw algoritmınıń waqıt quramalılıǵı ga proportsional dep ataladı. N2.
2. 2 Ova Ō - belgiler.
waqıt quramalılıǵınıń turpayınıń tábiyaatı artıp baratırǵanında N (N® ¥ ) shaqırdı algoritmdıń asimptotik quramalılıǵı.
Asimptotik quramalılıqtıń ósiw tezligin xarakteristikalaw ushın biz paydalanamız O-notatsiyasi. Algoritmdıń waqıt quramalılıǵı tártibinde delingende N2 :
T (N) = O (N2 ) = O (f (N)),
Keyin oń konstantalar bar ekenligi shama etiledi C, n0 =const (C>0), hámme ushın sonday N ³ N0 teńsizlik ámel etedi
T (N) £ C* f (N)
Bul quramalılıq bahosining joqarı shegarası.
2-mısal :
Meyli T (0) = 1, T (1) = 4,.. ., T (N) = (N+1) 2, keyin bul algoritmdıń waqıt quramalılıǵı ósiw tártibinde boladı T (N) = O (N2 ).
Bunı hámme ushın kórsetiw múmkin N > n0 de n0 = 1, C = 4 teńsizlik (1) atqarıladı.
(N+1) 2 £ 4* N2
3-mısal :
waqıt quramalılıǵı polinom retinde jazılsa
T (N) = C1 N2 + C2 N+ C3,
ol halda bunday algoritm polinomning maksimal elementi dárejesine márteli quramalılıq rejimine iye, sebebi ol eń tez ósedi. N® ¥ :
T (N) = O (N2 ).
Mısalı :
3 n2 +5 n+1 £ 5 n2
" n ³ 1
4-mısal :
Eger birpara algoritm bir neshe quramalılıqqa iye bolsa 3 n, ol halda tezliktiń ósiw tártibi kóbeytpeli bolıwı múmkin emesligin kórsetiw múmkin O (2 n):
T (N) =3 n¹ O (2 n).
Turaqlılar bolsın C, n0, sonday etip, tómendegi teńsizlik ámel etedi:
3 n £ C*2 n, n > n0.
Bul erdan biz alamız :
BILAN³ (3/2) 2, n > n0.
Lekin menen n® ¥ bunday turaqlı joq BILAN bul teńsizlikti qandiradi.
Quramalılıqtıń joqarı shegarasınan tısqarı, waqtınshalıq quramalılıqtıń ósiw tezliginiń tómengi shegarası da ámeldegi:
T (N) ³ v (f (N))
Teńsizlik (2) qanday da turaqlı bar ekenin ańlatadı BILAN onıń ushın N® ¥ waqıt quramalılıǵı
T (N) ³ C* f (N).
T (N) (asimptotik waqıt quramalılıǵı ) ni anıq anıqlawdıń quramalılıǵın esapqa alǵan halda, dáslepki maǵlıwmatlardıń kólemine qaray, ámelde algoritmdıń waqıt quramalılıǵınıń tómengi hám joqarı shegaraları qollanıladı :
T (N) = q (f (N))
Konstantaning ma`nisine qaray BILAN algoritm quramalılıǵınıń ósiw tezligi sezilerli dárejede parıq etiwi múmkin.
5-mısal :
waqıt quramalılıǵı formula menen jazılsin
T (N) = 3 n2 -100 n + 6 = O (n2)
3 n2> 3 n2 -100 n + 6, n³ 1, C = 3.
Eger C1» 0 (C1 = 0, 00001), keyin teńsizlik
10 -5 n2 > 3 n2 -100 n+6, n³ 1
atqarılmaǵan.
Biraq quramalılıqtıń ósiw rejimin kórsetiw múmkin
3 n2 -100 n + 6¹ O (N).
C * N< 3 N2, N>C.
3 n2 -100 n + 6 = (n2)
C=2. 29, n ³ n0.
2. 99* n2 < 3 n2 -100 n+6
Tómengi shegara ekenligin kórsetiw múmkin
3 n2 -100 n+6 ¹ v (n3 ) de C = 1.
Teńsizlik 3 n2 -100 n+6 ³ n3 atqarılmaǵan.
3 n2 -100 n+6= v (n)
C1 =, n> n0.
https://pandia. ru/text/78/183/images/image007_89.gif " keńlik =" 305 " biyiklik =" 247 src = " >
f1 (N) =100 n2
f2 (N) =5 n3
n0 =20 - sın kózqarastan noqat.
Quramalılıq dárejesi tómenlew bolǵan algoritmlarǵa ústinlik beriwdiń taǵı bir sebebi sonda, quramalılıq tártibi qanshellilik tómen bolsa, máseleniń kólemi sonshalıq úlken boladı. N ámeliy tárepten sheshiw múmkin.
0 " style =" margin-left: 5, 4 pt; shegaranı jıynaw : jıynaw ; shegara : joq " >
n!