Algoritmlerdi analizlew

N + 256

Yuklash	257
tеkshirish	N + 258

Sonday etip 500 belginen ibarat fayl berilsa algoritmda 1771 ámel atqarıladı, olardan 770 tasi nátiyje beredi (43%). Endi N dıń ma`nisi asqanda ne bolıwın kóremiz. Eger fayl 50 000 belginen ibarat bolsa, ol jaǵdayda algoritm 100 771 ámel atqaradı, olardıń 770 tasi nátiyje ushın (jámi ámeller sanınıń 1% ini quraydı ). Sheshimge qaratılǵan ámeller sanı aspayapti, lekin N úlken bolǵanda olardıń procenti júdá kem.

Endi basqa tárepine itibar qaratamız. Kompyuterde maǵlıwmatlar menen sonday islewge mólsherlengenki, úlken kólem degi maǵlıwmatlar blokın kóshiriw hám júklew birdey tezlikte ámelge asıriladı. Sol sebepli biz aldın 16 esaplagichga baslan? ish baha 0 ni júkleymiz, keyin qalǵan esaplagichlarni toltırıw ushın sol bloktan 15 nusqa alamız. Bul bolsa cikl atqarılıw dawamında tekseriwler sanın 33 ke, júklewler sanın 33 hám asırıwlar sanın 31 ge azayıwına alıp keledi. Sonday eken ámel atqarılıwlar sanı 770 ten 97 ge shekem kemeydi, yaǵnıy 87%. Eger erisilgen nátiyjeni 50000 belginen ibarat fayl ústinde atqarsak, puxtalıq 0. 7% ni quraydı (100771 ámel ornına 100098 ámel atqaramız ). Egerde barlıq ámellerdi sikldan paydalanmay 31 júklewler arqalı atqarganimizda, waqtın jáne de tejagan bolar edik, biraq bul usıl 0. 07 payda keltiredi. Jumısımız ónimli bolmaydı. Kórip turǵanimizdek, algoritmdıń atqarılıw waqtı menen bo? liq barlıq ámeller paydasız. Analiz tili menen aytqanda, baslan? ish maǵlıwmatlar kóleminiń artıwına ayrıqsha itibar qaratıw kerek.
Algoritmlardı analiz qılıwdıń basqa jaqsılaw usılı - onı qandayda bir joqarı basqıshlı til Pascal, C, C++, JAvA de jazıw yamasa ápiwayı psevdokodlarda jazıw bolıp tabıladı. Barlıq algoritmlardıń tiykarǵı basqarıw strukturasın ańlatpalaganda psevdokodlarning ózgeshelikleri áhmiyetke iye emes. Qálegen til biziń talabımızǵa juwap beredi, sebebi for yamasa while formasındaǵı cikller, if, case yamasa switch kórinisindegi tarmaqlanıw mexanizmleri barlıq programmalastırıw tillerinde bar. Hár gezek biz bir anıq algoritmdı kórip shıǵıwımızǵa to'? ri keledi - ol jaǵdayda birdan artıq funkciya yamasa programma fragmenti kiritilgen boladı, sol sebepli joqarıda keltirilgen tillerdiń tezligi ulıwma zárúrli emes. Psevdokodlardan paydalanıwimizning sebebi sonda.
Kóplegen programmalastırıw tillerinde logikalıq ańlatpanıń bahaları qısqartirilgan formada esaplanadı. Bul A and v ańlatpa daǵı v hadning ma`nisi qashanda A ras bolsaǵana esaplanadı, keri jaǵdayda nátiyje v ga baylanıslı bolmaǵan tárzde ótirik boladı. Tap sonday A or B ańlatpada A dıń ma`nisi ras bolsa, B hadning ma`nisi esaplanbaydı. Kórinip turıptı, olda, quramalı shártlerdiń 1 yamasa 2 ge teńligidegi salıstırıwlashlarining sanın esaplaw shárt emes.
2. Baslanǵısh berilgenler klası
Algoritmlardıń analizinde kiretuǵın maǵlıwmatlardıń roli joqarı, sebebi algoritm háreketleriniń izbe-izligi kiretuǵın maǵlıwmatlar menen belgilenedi. Mısalı, N ta elementten shólkemlesken dizimdiń eń úlken elementin tabıw ushın tómendegi algoritmnan paydalanıw múmkin:
largest = list [l]
for i =2 to N do
if (list [i] > largest) then
largest = list[i]
end if
end for


Eger dizim azayıw tártibinde bolsa, ol halda cikl baslanıwınan aldın bir ózlestiriw atqarıladı, cikl denesinde bolsa ózlestiriw bolmaydı. Eger dizim ósiw tártibinde bolsa, ol halda N ta ózlestiriw atqarıladı (cikl baslanıwınan aldın bir hám N-1 siklda). Biz analiz qılıw dawamında kiretuǵın bahalar kompleksiniń túrli múmkinshiliklerin kórip shıǵıwımız kerek, eger bir jıynaq menen shegaralansak, bul sheshim eń tez (yamasa eń aste) bolǵan jıynaq bolıp shıǵıwı múmkin. Nátiyjede biz algoritm haqqındaǵı ótirik oyda sawlelendiriwge iye bolamız. Bunıń ornına kiretuǵın jıynaqlar turining barlıǵın kórip shıǵamız. Biz kiretuǵın jıynaqlardı hár bir jıynaqtaǵı algoritm jaǵdayına baylanıslı halda klasslarǵa bolıp shıǵamız. Bunday bóliniw kórip shıǵılıp atırǵan jıynaqlar muǵdarın kemeytiw imkaniyatın beredi. Mısalı, 10 sandan ibarat dizim ushın eń úlken elementti tabıw algoritmın qollaymiz. Birinshi sanı eń úlken bolǵan 362 880 kiretuǵın jıynaqlar ámeldegi, olardı bir klasqa jaylastırıw múmkin. Eger ma`nisi boyınsha eń úlken san ekinshi orında turǵan bolsa, ol halda algoritm eki ózlestiriwdi ámelge asıradı. Eń kata san ekinshi orında turǵan jıynaq 362 880. Olardı basqa klasqa kirgiziw múmkin. 1 den N ge shekem bolǵan sanlar arasında eń úlken sannıń ózgeris jaǵdayında ózlestiriwler sanınıń qanday ózgeriwin kóriwimiz múmkin. Sonday etip, barlıq kiretuǵın jıynaqlardı orınlanǵan ózlestiriwler sanı boyınsha N ta túrli klasqa bolıw kerek. Kórip turǵanıńız siyaqlı, hár bir klassta jaylasqan jıynaqlardı Birma -bir jazıw yamasa jazıp alıw shárt emes. Tek ǵana hár bir jıynaqtaǵı klasslar muǵdarı hám jumıs kólemin biliw jetkilikli. Kiretuǵın berilgenlerdiń múmkin bolǵan kompleksi N úlkenlashganda júdáyam úlken bolıwı múmkin. Mısalı, 10 túrli sanı dizimde 3 628 800 usılda jaylastırıw múmkin. Bul usıllardıń barlıǵın kórip shıǵıwdıń múmkinshiligi joq. Biz bunıń ornına algoritm orınlanıwına kóre dizimdi klasslarǵa bólemiz. Joqarıda kórsetilgen algoritm ushın bóliniw eń úlken bahanıń jaylasıwı ornına tiykarlanadı. Nátiyjede 10 túrli klass payda boladı. Basqa algoritm ushın, mısalı, eń úlken hám eń kishi sannı tabıw algoritmında bóliniw eń úlken hám eń kishi sannıń jaylasıwına tiykarlanadı. Bunday bóliniwde 90 ta klass boladı. Klasslardı ajıratıp bo'lgach, hár bir klasstan bir jıynaqta algoritm jaǵdayın kóriw múmkin. Eger klasslar tuwrı saylanǵan bolsa, ol halda bir klasstaǵı kiretuǵın berilgenler kompleksinde algoritm birdey muǵdardaǵı ámellerdi atqaradı, basqa klasstıń jıynaqları ushın bolsa ámeller muǵdarı basqasha boladı.