Joba: Kirisiw Algoritmlerdi analiz qiliw

Tema:Algoritmlerdi en’ jaman ha’m ortasha jag’daylarda bahalaw

Joba:
Kirisiw
1. Algoritmlerdi analiz qiliw
2. Algoritmdıń ush jaǵdayı
3. Algoritmlardıń quramalılıǵın analiz qılıw. Mısallar
Juwmaq
Paydalanilg’an a’debiyatlar

Kirisiw
Algoritmlardı analiz qılıwdıń tiykarǵı waziypası kirisiw maǵlıwmatları kóleminiń asıp barıwı menen resurslarǵa bolǵan talaptı (waqıt hám yad ǵárejetleri) ólshew usılların anıqlaw bolıp tabıladı. Sonnan keyin, ósiw páti nizamlıqların xarakteristikalaw ushın zárúr bolǵan matematikalıq mexanizm islep shıǵıladı. Kirisiw maǵlıwmatları kólemin asırıw menen hár qıylı funktsiyalar ; " bir funktsiya basqasına qaraǵanda tezirek ósedi" sóz dizbegi neni ańlatıwın anıqlap alıwǵa járdem beredi. Birpara hollarda, jaqsı atqarılıw waqıtına erisiw jáne de quramalı maǵlıwmatlar strukturalarınan paydalanıwǵa baylanıslı hám bólim aqırında biz bunday maǵlıwmatlar strukturasınıń júdá paydalı mısalın kórip shıǵamız : ústin turatuǵın gezekler hám olardı úyin (kúsha, heap) tiykarında ámelge asırıw.

1.Algoritmlerdi analiz qiliw
Algoritmlardı analiz qılıwdıń tiykarǵı waziypası kirisiw maǵlıwmatları kóleminiń asıp barıwı menen resurslarǵa bolǵan talaptı (waqıt hám yad ǵárejetleri) ólshew usılların anıqlaw bolıp tabıladı. Sonnan keyin, ósiw páti nizamlıqların xarakteristikalaw ushın zárúr bolǵan matematikalıq mexanizm islep shıǵıladı. Kirisiw maǵlıwmatları kólemin asırıw menen hár qıylı funktsiyalar ; " bir funktsiya basqasına qaraǵanda tezirek ósedi" sóz dizbegi neni ańlatıwın anıqlap alıwǵa járdem beredi. Birpara hollarda, jaqsı atqarılıw waqıtına erisiw jáne de quramalı maǵlıwmatlar strukturalarınan paydalanıwǵa baylanıslı hám bólim aqırında biz bunday maǵlıwmatlar strukturasınıń júdá paydalı mısalın kórip shıǵamız : ústin turatuǵın gezekler hám olardı úyin (kúsha, heap) tiykarında ámelge asırıw.
Tiykarǵı maqset - esaplaw máseleleriniń nátiyjeli algoritmların izlew. Bul ulıwmalıq dárejesinde kompyuterdi esaplawdıń pútkil tarawı bul tema menen baylanıslı bolıp tuyuladi; biziń jantasıwımız basqalardan qanday parıq etedi? Algoritmlardı islep shıǵıwda ulıwma temalar hám proektlestiriw principlerıni anıqlawǵa háreket etemiz. Bizni nátiyjeli algoritmlardı proektlestiriwdiń tiykarǵı usılların minimal maǵlıwmat menen kórsetiw etiwshi paradigmatik máseleler hám usıllar qızıqtiradi.
Algoritmdı atqarılıw qádemi - bul atqarıwshı tárepinen bir kórsetpediń atqarılıwı bolıp tabıladı. Bir masalani hal etiwshi eki algoritmdan kam qádem talap qılınıp atırǵanı natiyjelilew bolıp tabıladı. Nátiyjelililik o'lchovi - bul bar-yo'g'i qádemler sanı bolıp tabıladı. Lekin tereńrek itibar berip qarasak, bul tariypdagi mujmal tomonlarni anıqlaymız. Geyde avval dus kelgen algoritmlardagidan ko'ra jaǵday quramalıroq bo'ladi.
Algoritmlar quramalılıǵı menen de parıqlanishi múmkin. Algoritmdıń quramalılıǵın onıń tekstindegi qatarlar sanı menen o'lchaymiz. Usınıń menen birge quyidagi eki qatardı bir tuzilmaning ikki bólegi bolǵanı ushın birge esaplaymiz
Hár qanday programmist ushın algoritmlar teoriyası tiykarların biliw júdá zárúrli, sebebi naǵız ózi pán algoritmlardıń ulıwma xarakteristikaların hám olardı ańlatıwdıń rásmiy modellerin úyrenedi. Hátte informatika sabaqlarınan da bizni aǵıs sxemaların dúziwdi úyretiwedi, bul keyinirek mektepdagiga qaraǵanda quramalılaw wazıypalardı jazıwda járdem beredi. Hesh kimge sır emeski, arnawlı bir mashqalanı sheshiwdiń derlik mudamı bir neshe usılları ámeldegi: geyparaları kóp waqıt jumsawdı óz ishine aladı, basqaları resursların talap etedi, basqaları bolsa tek shama menen sheshim tabıwǵa járdem beredi.

Siz mudamı wazıypaǵa muwapıq optimaldı izlewińiz kerek, atap aytqanda, máseleler klasın sheshiw algoritmların islep shıǵıwda.

Algoritm túrli kólem hám muǵdardıń baslanǵısh bahaları menen qanday háreket etiwin, oǵan qanday resurslar kerekligini hám juwmaqlawshı nátiyjeni kórsetiw ushın qansha waqıt ketiwin bahalaw da zárúrli bolıp tabıladı.
Bunı algoritmlar teoriyasınıń bólimi - algoritmlardıń asimptotik analizi teoriyası ámelge asıradı.
Men bul maqalada tiykarǵı bahalaw kriteryaların xarakteristikalawdı hám eń ápiwayı algoritmdı bahalawǵa mısal keltiriwdi usınıs etemen. Xabrahabrda algoritmlardı bahalaw usılları haqqında qashannan berli maqala bar, lekin ol tiykarınan licey oqıwshılarına qaratılǵan. Bul baspanı sol maqalanı tereńlestiriw dep esaplaw múmkin.
Tariypler
Algoritmdıń quramalılıǵınıń tiykarǵı kórsetkishi - máseleni sheshiw ushın zárúr bolǵan waqıt hám kerekli yad muǵdarı.
Sonıń menen birge, máseleler klası ushın quramalılıqtı analiz qılıwda málim muǵdardaǵı maǵlıwmatlardı xarakteristikalaytuǵın málim bir nomer anıqlanadı - kirisiw kólemi.
Sonday etip, algoritmdıń quramalılıǵı kirisiw kólemine baylanıslı degen juwmaqqa keliwimiz múmkin.
Algoritmdıń quramalılıǵı birdey kirisiw kólemi ushın hár túrlı bolıwı múmkin, biraq kirisiw maǵlıwmatları basqasha.
Eń jamanı, ortasha yamasa eń jaqsısı quramalılıq túsinikleri bar. Ádetde, quramalılıq eń jaman jaǵdayda bahalanadı.
Eń jaman waqıt quramalılıǵı kirisiw kóleminiń funktsiyası bolıp, ol berilgen ólshem degi máseleni tarqatıp alıwda algoritm processinde atqarılatuǵın operatsiyalardıń maksimal sanına teń.
Eń jaman jaǵdayda sıyımlılıqtıń quramalılıǵı málim ólshem degi mashqalalardi sheshiwde paydalanılǵan yad kletkalarınıń maksimal sanına teń bolǵan kirisiw kóleminiń funktsiyası bolıp tabıladı.

Algoritmlar quramalılıǵınıń ósiw tártibi

Quramalılıqtıń ósiw tártibi (yamasa hákisiomatik quramalılıq ) kirisiw kólemi úlken bolǵanda algoritmdıń quramalılıq funktsiyasınıń shamalıq háreketin xarakteristikalaydı. Bunnan kelip shıǵadıki, waqıt quramalılıǵın bahalawda elementar operatsiyalardı esapqa alıwdıń hájeti joq, algoritmdıń basqıshların esapqa alıw jetkilikli.
Algoritm qádemi izbe-iz jaylastırılǵan elementar ámeller kompleksi bolıp, olardıń atqarılıw waqıtı kiritilgen maǵlıwmatlardıń úlkenligine baylanıslı bolmaǵan, yaǵnıy joqarıdan qanday da turaqlı menen shegaralanǵan.
Asimptotik bahalardıń túrleri
O - eń jaman jaǵday shaması
Quramalılıq f (n) > 0, birdey tártip degi funktsiya g (n) > 0 hám kirisiw kólemi n > 0 ni kórip shıǵayıq.
Eger f (n) = O (g (n)) hám turaqlılar c > 0, n0 > 0 bolsa, ol halda
0 < f (n) < c*g (n),
n > n0 ushın.

Bul halda g (n) funksiya f (n) dıń asimptotik keskin bahosi bolıp tabıladı. Eger f (n) algoritm quramalılıǵı funksiyası bolsa, ol halda quramalılıq tártibi f (n) - O (g (n)) formasında anıqlanadı.

Bul ańlatpa turaqlı koefficiyentge shekem g (n) den tez o'smaydigan funksiyalar klasın belgileydi.

2.Algoritmdıń ush jaǵdayı ámeldegi

eń jaman jaǵday ;

ortasha jaǵday ;
eń jaqsı jaǵday.
Algoritmdıń islew waqıtı $$T (n) $$ degende, biz $$T (n) $$ jumıs waqtıniń joqarı shegarası ekenligin túsinemiz, yaǵnıy ol ólshem degi barlıq kiriwler ushın ámel etedi. $$n $$. Bul eń jaman jaǵday analizi dep ataladı. Algoritm $$n$$ birpara kirgiziw ólshemlerinde sezilerli dárejede tezirek islewi múmkin, biraq bul eń jaman jaǵdaydı bahalawda áhmiyetsiz. Eger algoritm keminde bir kirisiw ushın $$T (n) = cn^2+k$$ qádemlerin talap qilsa, $$n$$ hám basqa barlıq kiriwler ushın $$T (n) = cn+k$$ qádemleri kerek bolsa, biz baribir algoritm kvadrat ekenligin aytıń, yaǵnıy eń jaman jaǵdayda ol $$n^2$$ ga proportsional waqıtta isleydi. Sonı túsiniw kerek, eń jaman jaǵdayda algoritmdıń quramalılıǵın biliw júdá zárúrli, sebebi bul algoritmdı qóllawda sheshiwshi áhmiyetke iye.
Eń jaman jaǵdaylar analizine ataqlı alternativ ortasha jaǵday analizi bolıp tabıladı. Bul erda biz eń jaman jumıs waqtın tabıwǵa háreket etpeymiz, bálki tosınarlı saylanǵan kiriwlerge sarplanǵan kutilgan waqtın esaplawǵa háreket etemiz. Bunday analiz ádetde quramalılaw bolıp tabıladı, sebebi ol itimallıq tiykarların óz ishine aladı hám kóbinese kiritilgen maǵlıwmatlardı bólistiriw boyınsha bilimlerdi talap etedi. Basqa tárepden, ol paydalılaw bolıwı múmkin, sebebi geyde algoritmdıń eń jaman jaǵdayı jalǵanshı dárejede jaman boladı. Buǵan ataqlı operativ saralaw algoritmı jaqsı mısal boladı, onıń $$n$$ uzınlıqtaǵı dızbektegi eń jaman jumıs waqıtı $$n^2$$ ga proportsional, biraq kutilayotgan ortasha islew waqıtı $$n ga proportsional bolıp tabıladı. \log n$$.

Algoritm haqqında júdá kem maǵlıwmat eń jaqsı jaǵdaynı bahalaw arqalı beriliwi múmkin.

Keling, dızbektegi elementti izbe-iz izlew ush jaǵdayda qanday quramalılıqqa iye ekenligin kórip shıǵayıq.

Eń jaman jaǵday
Eń jaman jaǵdaynı analiz qılıwda biz algoritmdıń islew waqıtı boyınsha joqarı shegaranı esaplaymiz. Biz orınlanǵan operatsiyalardıń maksimal sanı orınlanǵan jaǵdaydı biliwimiz kerek. Sızıqlı qıdırıw ushın eń jaman jaǵday dızbekte etiwmey atırǵan elementti qıdırıw bolıp tabıladı. Bunday halda, algoritm dızbektiń hár bir elementin kerekli element menen salıstırıwlaydı. Sonday etip, eń jaman jaǵdayda, sızıqlı qıdırıwdıń waqıt quramalılıǵı $$\Theta (n) $$ boladı, yaǵnıy algoritm kirisiw dızbekiniń ólshemine proporcional sızıqlı tártipke iye.

Ortasha jaǵday

Ortasha jaǵdayda algoritmdıń quramalılıǵın analiz etkende, biz kiritilgen maǵlıwmatlardıń barlıq múmkin bolǵan nátiyjelerin kórip shıǵamız hám nátiyjelerdiń hár biri ushın esaplaw waqtın esaplaymiz. Ortashanı tabıw ushın jıyındın kiriwler sanına bolıw jetkilikli. Ortasha analiz qılıw ushın biz kiritilgen maǵlıwmatlardıń bólistiriliwin biliwimiz kerek. Shama menen oylayıq, sızıqlı qıdırıw mashqalasında barlıq kiriwler birdey bólistirilgen (sonday-aq, etiwmey atırǵan elementti qıdırıw ). Biz algoritmdıń ortasha quramalılıǵın alamız

$$ Ortasha = \dfrac{\sum_{n=1}^{n+1} \Theta (i) }{n + 1} = \dfrac{\Theta ((n+1) \cdot (n+2) /2) }{n + 1} = \Teta (n)

$$

Eń jaqsı jaǵday

Eń jaqsı jaǵdayda algoritmdıń quramalılıǵın analiz etkende, biz algoritmdıń islew waqıtı boyınsha tómengi shegaranı esaplaymiz. Biz minimal muǵdardaǵı operatsiyalar atqarılatuǵın jumıstı biliwimiz kerek. Sızıqlı qıdırıwda eń jaqsı jaǵday dızbektegi birinshi elementti qıdırıw bolıp tabıladı. Bunda sarplanǵan ámeller sanı mudami turaqlı boladı, yaǵnıy kirisiw dızbekiniń ólshemine baylanıslı bolmaydı. Sonday etip, sızıqlı qıdırıw algoritmınıń quramalılıǵı eń jaqsı jaǵdayda $$\Theta (1) $$ bolıp tabıladı.
Kóbinese biz eń jaman ball alıw ushın algoritmdı tekseremiz. Bunday halda, algoritmdıń islew múddeti málim bir nomerden aspawına kepillik beremiz, bul jaqsı maǵlıwmat. Algoritmdıń ortasha quramalılıǵın tabıw onsha ápiwayı jumıs emes, sebebi biz barlıq múmkin bolǵan kiriwler ushın matematikalıq bólistiriwdi biliwimiz kerek. Algoritmdıń quramalılıǵı, eń jaqsı jaǵdayda, algoritmdıń islew waqtın real bahalawda kem járdem beredi. Sonday etip, algoritm eń jaqsı jaǵdayda sekundalar, eń jamanı bolsa kún hám hátte jıllar dawamında islewi múmkin.
Birpara algoritmlar ushın ush quramalılıq jaǵdayı birdey. Mısal ushın, birlestiriw tártibi eń jaqsı, ortasha hám eń jaman jaǵdaylarda $$\Theta (n \log n) $$ quramalılıǵına iye. Biraq, ámeliyat daǵı eń tez saralaw algoritmlarınan biri, operativ saralaw, dızbektegi aqırǵı ajıratıw elementin tańlawda eń jaman jaǵday (dızbek qashannan berli tártiplengen) kvadratik quramalılıqqa iye. Qosıwdı tártiplew ushın dızbek teris tártipte tártiplengende eń jaman jaǵday, eń jaqsı jaǵday bolsa dızbek qashannan berli kerekli tártipte tártiplengen bolsa.