Algoritmlerdi analizlew

ALGORITMLERDI ANALIZLEW
Algoritm analizin, qoyılǵan máseleni bul algoritm menen sheshiw qansha waqıt talap etiwi dárejesi dep oyda sawlelendiriw múmkin. Hár bir qaralayotgan algorimtni N ólshewli baslanǵısh maǵlıwmatlar dızbekindegi máselelerdiń qanshellilik tez sheshiliwi menen bahalaymiz. Mısalı, saralaw algoritmı N ta bahadan ibarat dizimdi ósiw tártibinde jaylastırıw ushın qansha salıstırıwlaw talap etedi yamasa N*N ólshemli eki matritsani kóbeytiwde qansha arifmetik ámeller zárúr ekenligin esaplaw. Bir máseleni túrli algoritmlar menen sheshiw múmkin. Algoritmlar analizi bizge algoritmdı tańlaw ushın qural boladı. Tórtew bahadan eń úlkenin tańlaytuǵın eki algoritmdı qaraymız :

largest = a if b > largest then largest = b end if return a if s > largest then largest = s end if if d > largest then largest = d end if return largest

if a > b then if a > s then if a > d then return a else return d end if else if s > d then return s else return d end if end if else if b > s then if b > d then return b else return d end if else if s > d then return s else return d end if end if end if

Kórinip turıptı, olda, qaralayotgan algoritmlardıń hár birinde ush salıstırıwlaw atqarıladı. Birinshi algoritmdı oqıw hám túsiniw ańsat, biraq kompyuterde atqarılıw kózqarasınan olardıń quramalılıq dárejeleri teń. Bul eki algoritm waqıt kózqarasınan teń, lekin birinshi algoritm largest atlı qosımsha ózgeriwshi esabına kóbirek yad talap etedi. Egerde san yamasa belgiler salıstırıwlansa, bul qosımsha ózgeriwshi úlken áhmiyetke iye bolmaydı, lekin basqa túrdegi maǵlıwmatlar menen islegende bul zárúrli áhmiyetke iye. Kóplegen zamanagóy programmalastırıw tilleri úlken hám quramalı ob'ektlerdi yamasa jazıwlardı salıstırıwlaw operatorların anıqlaw imkaniyatın beredi. Bunday jaǵdaylarda qosımsha ózgeriwshilerdi jaylastırıw úlken jay talap etedi. Algoritmlardıń effektivligini analizi qılıwda bizni birinshi náwbette waqıt máselesi qızıqtiradi, biraq yad zárúrli rol atqaratuǵın jaǵdayda onı da talqılaw etemiz. Algoritmlaring túrli ózgeshelikleri bir máseleni sheshiwshi eki túrdegi algoritmlardıń effektivligini salıstırıwlaw ushın xızmet etedi. Biz sol sebepli hesh qashan matritsalarni kóbeytiw algoritmı menen saralaw algoritmın emes, bálki eki túrli saralaw algoritmların bir-biri menen salıstırıwlaymız.

Algoritm analiziniń nátiyjesi - belgilengen algoritmdıń kompyuterden qansha waqıt yamasa tákirarlaw talap etiwin anıq esaplaytuǵın formula emes. Bunday maǵlıwmat zárúrli emes, bul jaǵdayda kompyuter túri, ol bir yamasa odan artıq paydalanıwshı tárepinen isletilyaptimi, onıń protsessori hám chastotası qanday, protsessor chipida komandalar tolıqpa hám kompilyator atqarılıp atırǵan kodtı qaysı dárejede ámelge asırıp atır sıyaqlı táreplerdi názerde tutıw kerek. Bul shártler algoritm atqarılıw nátiyjesinde programmanıń islew tezligine tásir etedi. Joqarıdaǵı shártler esabına programmanı basqa tez isleytuǵın kompyuterge ótkerilgende algoritm jaqsı islegendey orınlanıwı tezirek ámelge asadı. Tiykarınan bolsa oday emes, biz sol sebepli analizimizde kompyuterdiń múmkinshiliklerin inabatqa almaymız.
Ápiwayı hám úlken bolmaǵan programmalarda atqarılatuǵın ámeller sanın N dıń funkciyası kórinisinde anıq esaplaw múmkin. Kópshilik jaǵdaylarda buǵan zárúriyat qalmaydı. 8. 4 § de keltirilgen N =5 hám N =250 ta ámel atqarılatuǵın eki algoritm arasında N dıń jetkiliklishe úlken bahalarında derlik parq bolmaydı. Soǵan qaramay, biz algoritmlardı atqarılatuǵın ámeller sanına qaray analiz etemiz.
Algoritm tárepinen atqarılatuǵın processler bar, biz olardıń hámmesin esaplab o'tirmaymiz, óytkeni sonda, hátte onıń eń kishi sazlawı da nátiyjelililiktiń sezilmas jaqsılanıwına alıp keledi. Mısalı, fayl daǵı túrli belgiler sanın esaplaytuǵın algoritmdı qaraymız. Bul másele sheshimi ushın algoritmdıń shamalıq kórinisi tómendegishe boladı :
for all 256 belgilerdi do
esaplagichni nolge teńles end for
while eger faylda belgi qalsa do
náwbettegi belgin kórset hám esaplagichni birge asır end while do
esaplagichni nolge teńlestiriw end for
while faylda belgi ámeldegi bolsa do
náwbettegi belgin kórset hám esaplagichni birge asır
end while
Bul algoritmdı kórip shıǵamız. Ol tákirarlanıw orınlanıwında 256 ótiw etedi. Eger berilgen faylda N ta belgi bolsa ol jaǵdayda ekinshi tákirarlanishda N ta ótiw etiledi. «Bul qanday esaplaw? » degen soraw tuwıladı. For siklida aldın cikl ózgeriwshisi atqarıladı, keyin hár bir ótiwde onıń cikl shegarasınan shıqpayotganligi tekseriledi hám ózgeriwshi ma`nisin asıradı. Bul bolsa cikl orınlanıwında 257 júklew atqarıladı (biri cikl ózgeriwshisi, 256 tasi esaplaǵısh ushın ), yaǵnıy 256 asırıw hám 257 cikl shegarasınan shıqpaǵanlıǵın tekseriw (bir ámel siklni toqtatıw ushın qosılǵan ). Ekinshi siklda N + 1 ret shárt tekseriledi (+1 fayl bos bolǵandaǵı aqırǵı tekseriw), hám N esaplagichni asırıw. Jámi ámeller:

Oshirish