Atqardı : Bayniyazov. O qabılladı : Qutlimuratov. Y joba

n=	n	n*logn	n^2	n^3	1,5^n	2^n
n!
10
30						18min	10^25y
50					11min	36y	Ju’da’ ko’p
100					12892y	10^17y	----
1000				18min	---	----	----
10000			2min	12ku’n	--	---	---
100000			3saat	32y	---	---	---
1 mln.		20s	12ku’n	31710y	---	---	---

3. Asimptotik joqarı shegaralar

Algoritmdıń natiyjeliligi bul algoritmdı qóllaw ushın qansha kúsh talap etiliwin yamasa onıń ma`nisi qansha ekenligin ańlatadı. Bunday baha hár túrlı kriteryalar menen ólsheniwi múmkin. Bul erda olardan ekewin : waqıt hám keńislik muǵdarındı nátiyjelililik kriteryaları retinde alınadı. Bunda waqıt kriteryası keńislikn áhmiyetlilew esaplanadı, sol sebepli nátiyjelililik tiykarlanıp maǵlıwmatlarnu qayta islewge ketken waqıtqa salıstırǵanda alınadı. Nátiyjelililikti bahalaw ushın logikalıq birlikler, yaǵnıy fayl yamasa dızbektiń ólshemi n hám qayta islew ushın ketken waqıt muǵdarı t alınadı.
Eger n ólshew hám t waqıt arasında t1=c*n sızıqlı baylanıslılıq bolsa, ol halda kólemdi bir neshe ret, soniń menen birge 5 ret, asırıw nátiyjesinde, olardı qayta islewge ketken waqıt da 5 ret asadı yaǵnıy n2=5*n bolsa, t2=5*t orınlı boladı. Yamasa, eger baylanıslılıq t1=logn bolsa, ol halda n 2 ret asırılsa waqıt sarpı bar yo'g'i bir birlikke artadı, yaǵnıy t2=log2*n=t1+1 boladı. n hám t ni baylanıslılıǵın ańlatiwshı funksiya ádetde quramalı boladı hám bunday funksiyanı esaplaw úlken kólem degi maǵlıwmatlardı qayta islewde júdá zárúrli esaplanadı. Payda etińan f-ya berilgen funksiyanıń strukturalıq natiyjeliligin ańlatadı. Soǵan qaramay bul jaqınlasıw funksiyaǵa jaqın esaplanadı, hám úlken kólem degi maǵlıwmatlar ushın originalga júdá jaqın boladı. Nátiyjelililiktiń bul ólshewi assimtotik jaqınlashuvchi ólshew dep ataladı hám ol nátiyjelililikti anıqlawshı funksiya málim xadlarini esapqa alǵanda yamasa nátiyjelililikti anıq esaplas qıyın, yamasa múmkin bolmaǵanda qollanıladı.
Eger n ólshew hám t waqıt arasında t1=c*n sızıqlı baylanıslılıq bolsa, ol halda kólemdi bir neshe ret, soniń menen birge 5 ret, asırıw nátiyjesinde, olardı qayta islewge ketken waqıt da 5 ret asadı yaǵnıy n2=5*n bolsa, t2=5*t orınlı boladı. Yamasa, eger baylanıslılıq t1=logn bolsa, ol halda n 2 ret asırılsa waqıt sarpı bar yo'g'i bir birlikke artadı, yaǵnıy t2=log2*n=t1+1 boladı. n hám t ni baylanıslılıǵın ańlatiwshı funksiya ádetde quramalı boladı hám bunday funksiyanı esaplaw úlken kólem degi maǵlıwmatlardı qayta islewde júdá zárúrli esaplanadı. Payda etińan f-ya berilgen funksiyanıń strukturalıq natiyjeliligin ańlatadı. Soǵan qaramay bul jaqınlasıw funksiyaǵa jaqın esaplanadı, hám úlken kólem degi maǵlıwmatlar ushın originalga júdá jaqın boladı. Nátiyjelililiktiń bul ólshewi assimtotik jaqınlashuvchi ólshew dep ataladı hám ol nátiyjelililikti anıqlawshı funksiya málim xadlarini esapqa alǵanda yamasa nátiyjelililikti anıq esaplas qıyın, yamasa múmkin bolmaǵanda qollanıladı.
Tómendegi mısaldı kóremiz:
n dıń kishi bahalarında ohirgi had 1000 dıń funksiya ma`nisin ónim bolıwı daǵı úlesu qalǵanlarına salıstırǵanda úlken esaplanadı. n=10 bolǵanda 2-xad 100 n hám ohirgi 1000 xadlar teń boladı hám basqalarǵa salıstırǵanda funksiya ma`nisine birdey tásir kórsetedi. Bul xadlarni funksiya xar bir xadining onıń ma`nisine qanday tásir etiwiniń kólemi n dıń hár túrli bahaları ushın tómendegi kestede keltirilgen.
Hadlarning funksiya ma`nisine tásir qılıw kólemi.
Bahalaw funkciyalar klassifikatsiyasi.
Berilgen eki f hám g funksiyalar ushın tómendegi tariypni keltiremiz:
1-tariyp. f (n) funksiya 0 (g (n)) boladı dep ataladı, eger sonday oń c hám N sanlar ámeldegi bolsaqı, barlıq n>=N lar ushın f (n) <=c g (n) teńsizlik atqarılsa.
Bul tariypga tiykarlanıp eger f (n) funksiya 0 (g (n)) bolsa, ol halda onıń ósiw tártibi jetkilikli úlken n lar ushın álbette cg (n) funksiya ósiw rejiminen kishi yamasa teń bo'lar eken. Sonday eken, bul halda f (n) funksiya úlken n larda cg (n) funksiyadan tez óse almaydı. Bul jerde c hám N sanların anıqlaw mashqala bolıp qaladı, sebebi tariypda olardı anıqlawdıń konkret yoli korsatilmagan. Ekinshiden, bul sanlarǵa hesh qanday shártler qoyılmaǵan. Sol sebepli olardıń bahaları júdá kóp bolıwı múmkin

f (n) =2 n^2+ 3 n+1=O (n^2) (2)

f (n) =2 n^2+ 3 n+1=O (n^2) (2)

Ol halda g (n) =n^2 funksiyanı tarifdagi funksiya retinde alıwshı funksiyalardan biri dep esaplaw múmkin. Tariypga tiykarlanıp, c hám N lar ushın tómendegi suwretdegi sanlar juplıqların alıw múmkin boladı. (2) funksiya ushın c hám N larning bahaları.

N hám c dıń bahaların anıqlaw
N hám c dıń bunday bahaların tómendegi teńsizlikti sheshiw arqalı anıqlanadı :

2 n^2+3 n+1<=cn^2; (3)

Odan tısqarı n dıń dárejeleri boyınsha da assimptotik funksiyalardı júdá kópin alıw múmkin. Bul halda eń kishi tártiplisi tańlap alınadı. Bunday anıq emesliklerdi sheshiw berilgen funksiya daǵı kishi tártipli xadlarni barlıǵın tastap jiberiw hám tómendegishe belgilew arqalı ámelge asıriladı. Mısalı, (1) funksiya ushın

f (n) =n^2+100 n+O (log10 n)

kóriniste alıw, (2) funksiya ushın bolsa f (n) =2 n^2+O (n) sıyaqlı kóriniste alıw múmkin boladı.
O- úlken funksiyalardıń ózgeshelikleri
Tranzitivlik. Eger f (n) funksiya O (h (n)) bolsa, ol halda sf (n) funksiya O (h (n)) boladı.
Eger f (n) hám g (n) funksiyalardıń xar biri O (h (n)) bolsa, ol halda olardıń jıyınfisi f (n) +g (n) da O (h (n)) boladı.

f=an^k funksiya O (n^k) boladı.

f=n^k funksiya qálegen j>=0 ushın O (n^k+j) boladı.

Eger f (n) =Cg (n) bolsa, ol halda f (n) funksiya O (g (n)) boladı. Ihtiyoriy a teń emes 1, b teń emes 1 sanlar ushın log (an) funksiya O (log (bn)) boladı.

O- notasiya járdeminde funksiyanı joqarıdan assimptotik bahalawdı kórdik. Tap sonday bahalawdı tómenden da beriw múmkin. Bunday bahalawdı sigma (Ω) bahalaw dep ataladı hám ol tómendegishe anıqlanadı :
2- tariyp. f (n) funksiya Ω (g (n)) dep ataladı, eger sonday oń c hám N lar ámeldegi bolsaqı, barlıq n>=N lar ushın f (n) >=cg (n) teńsizlik orınlı bolsa.
Bul tariyp da birinshi tariypga júdá uqsas, tek bul jerde teńsizlik teris bolıp tabıladı.
Joqarıdaǵı eki tariypdan paydalanıp tómendegio tariypni keltiriw múmkin.
Tariypga tiykarlanıp f (n) funksiya keminde g (n) funksiya sıyaqlı ósedi. Bul eki tariyp járdeminde funksiyalar ortasında tómendegi munasábetler orınlı bolıwın anıqlaw múmkin:
Tariypga tiykarlanıp f (n) funksiya keminde g (n) funksiya sıyaqlı ósedi. Bul eki tariyp járdeminde funksiyalar ortasında tómendegi munasábetler orınlı bolıwın anıqlaw múmkin:
3-tariyp. f (n) funksiya Θ (g (n)) dep ataladı, eger sonday oń c1, c2 hám N sanlar ámeldegi bolsaqı, olar ushın barlıq n>=N larda tómendegi teńsizlik orınlı bolsa : c1*g (n) <=f (n) <=c*2 g (n).
Mısallar :
Endi biz bir neshe mısallarda assiptotik funcsiyalarni anıqlawdı kórip shıǵamız.
Ápiwayı cikl járdeminde dızbek elementleri jıyındısın esaplawdan baslaymız. for (i = sum = 0; i < n; i++) sum += a[i]; Aldın 2 ózgeriwshin inisializatsiya etemiz, cikl n ta iteratsiyadan ibarat bolıp, hár bir qádemde jıyındı ma`nisi sum hám i ni ma`nisi jańalanadı. Sonday eken, algoritm wazıypanı tolıq sheshiw ushın 2+2 n ret ámeller orınlawı kerek boladı, yaǵnıy bul halda assimptotik funksiya O (n) boladı.
Eger ichma-ish jaylasqan cikller bolsa assimptotik funksiya dárejesi de artıp baradı. Bunı tómendegi barlıq nul jaǵdaydan baslanıwshı dızbek astıların jıyındısın esaplaw mısalında kóriw múmkin. Onıń kodı : for (i = 0; i < n; i++) { for (j = 1, sum = a[0]; j <= i; j++) sum += a[j]; cout<<< i <ret isleydi, hám hár bir islegende ishki sikldagi 2 ámel i ret, 3 ta ámel n ret tákiraran atqarıladı. Ol halda orınlanǵan ámeller sanı 1+3 n + ∑2 i=1+3 n+n (n-1) =O (n) + O (n^2) = O (n^2) sıyaqlı boladı. Sonday eken, máseleni sheshiw ushın O (n^2) tártip degi sanda ámeller orınlanıwı kerek.
Eger ichma-ish jaylasqan cikller bolsa assimptotik funksiya dárejesi de artıp baradı. Bunı tómendegi barlıq nul jaǵdaydan baslanıwshı dızbek astıların jıyındısın esaplaw mısalında kóriw múmkin. Onıń kodı : for (i = 0; i < n; i++) { for (j = 1, sum = a[0]; j <= i; j++) sum += a[j]; cout<<< i <Assimptotik funksiyanı anıqlaw iterasiyalar sanı ózgeriwshen bolǵanda qıyınlasadı. Bul jaǵday tómendegishe mısalda kórinisi múmkin.
Assimptotik funksiyanı anıqlaw iterasiyalar sanı ózgeriwshen bolǵanda qıyınlasadı. Bul jaǵday tómendegishe mısalda kórinisi múmkin.
Elementleri ósiw tártibinde jaylasqan eń uzın bólim dızbektiń uzınlıǵın anıqlaw kerek bolsın. Mısalı,[1 8 1 2 5 0 11 12] dızbekte tártiplengen elementlerden ibarat eń uzın bólim dızbek [1 2 5] bolıp, onıń uzınlıǵı 3 ke teń. Eń uzın osuvchi bólim dızbekti anıqlaw kodı tómendegishe boladı :

for (i=0, length=1; i

for (i1=i2=k =i;k< n-1 &&a[k]
if (length
length =i2-i1 +1;
}

Eger dızbek elementleri kamayuvchi bolsa, sırtqı cikl n-1 ret isleydi, xar bir sırtqı cikl iterasiyasida ishki cikl 1 ret atqarıladı. Sonday eken, bul halda nátiyjelililik O (n) boladı. Eger elementler o'suvchi tártipte jaylasqan bolsa bul algoritm tómen nátiyje beredi. Sebebi bul halda sırtqı cikl n-1 ret atqarıladı, ishki cikl bolsa n-1-i xar bir i 0, 1, … n-2 ushın, sonday eken, bul túrde algoritm natiyjeliligi O (n^2) boladı.

Eger dızbek elementleri kamayuvchi bolsa, sırtqı cikl n-1 ret isleydi, xar bir sırtqı cikl iterasiyasida ishki cikl 1 ret atqarıladı. Sonday eken, bul halda nátiyjelililik O (n) boladı. Eger elementler o'suvchi tártipte jaylasqan bolsa bul algoritm tómen nátiyje beredi. Sebebi bul halda sırtqı cikl n-1 ret atqarıladı, ishki cikl bolsa n-1-i xar bir i 0, 1, … n-2 ushın, sonday eken, bul túrde algoritm natiyjeliligi O (n^2) boladı
Eń jaqsi, ortasha hám eń jaman algoritmlar.
Joqarıdaǵı mısallarǵa tıykarlanıp sonı aytıw múmkin, algoritmlar natiyjeliligi boyınsha 3 hil bolıwı mumrin: 1) Eń jaman jaǵday bunda algoritm máseleni tarqatıp alıw ushın maksimal sandaǵı ámellerdi orınlawdı talap etedi; 2) Eń jaqsı jaǵday bunda algoritm máseleni tarqatıp alıw ushın minimal sandaǵı ámellerdi orınlawdı talap etedi; 3) Ortacha jaǵday bunda algoritm máseleni tarqatıp alıw ushın maksimal hám minimal sanlar arasındaǵı sandaǵı ámellerdi orınlawdı talap etedi.
Ápiwayı jaǵdaylarda ortacha nátiyjelililikti anıqlaw algoritmǵa múmkin bolǵan kiriwler, hár bir kirisiw ushın algoritm tiykarında atqarılıp atırǵan etaplar sanın anıqlaw, barlıq kiriwler ushın qádemler sanın anıqlaw hám olardıń hámmesin qasıb esaplanǵannan song kiriwler sanına bolish járdeminde ámelde asıriladı. 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ı funkciyalar ; " bir funkciya basqasına qaraǵanda tezirek ósedi" sóz dizbegi neni ańlatıwın anıqlap alıwǵa járdem beredi. Birpara jaǵdaylarda, jaqsı atqarılıw waqtı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ǵı tema - 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.