Мундарижа Кириш

1.1. Алгоритм таҳлили нима?
Алгоритмни таҳлил қилиб ушбу алгоритм ёрдамида қўйилган масалани ечиш қанча вақт олиши ҳақида тушунчага эга бўлиш мумкин. Ҳар бир кўриладиган алгоритм учун биз N узунликдаги массив кирувчи маълумотларда масала қанчалик тез ечилишини баҳолаймиз. Масалан, биз N ўлчовли рўйхатни саралаш учун саралаш алгоритмига қанча солиштиришлар ёки NхN ўлчовли икки матрицани кўпайтириш учун қанча арифметик амаллар талаб қилинишини баҳолашимиз мумкин.
Маълумки, бир масалани турли хил алгоритмлар ёрдамида ечиш мумкин. алгоритмлар таҳлили бизга алгоритмни танлаш воситасини беради. Масалан қуйидаги тўртта сондан энг катасини топувчи икки алгоритмни қараймиз:
I. II.
largest = a if a > b then
if b > largest then if a > с then
largest = b if a > d then
end if return a
return a else
if с > largest then return d
largest = с end if
end if else
if d > largest then if с > d then
largest = d return с
end if else
return largest return d
end if
end if
else
if b > с then
if b > d then
return b
else
return d
end if
else
if с > d then
return с
else
return d
end if
end if
end if
Ушбу алгоритмлардан кўриниб турибдики уларнинг ҳар бирида учта солишириш бажарилади. Биринчи алгоритм ўқиш ва тушунишга осон, аммо уларнинг компьютерда бажарилиши жиҳатидан бир хил мураккаблик даражасига эга. Бу икки алгоритм вақт жиҳатидан бир хил, лекин биринчи алгоритм вақтинчалик ўзгарувчи largest ҳисобидан кўпроқ хотирани талаб қилади. Бу қўшимча жой агар сон ёки белгилар солиштирилса муҳим аҳамият ўйнамайди, аммо бошқа маълумотлар турлари билан ишлаганда у катта аҳамиятга эга. Кўпчилик замонавий дастурлаш тиллари катта ва мураккаб объектлар ёки ёзувларни солиштириш операторларини аниқлашга имкон беради. Бу ҳолларда вақтинчалик ўзгарувчилардан фойдаланиш кўп жойни талаб этади. Алгоритмларни самарадорлигини таҳлил қилишда бизни биринчи навбатда вақт масаласи қизиқтиради, лекин айрим хотира муҳим аҳамият ўйнаган ҳолларда биз уларни муҳокама қиламиз.
Алгоритмларнинг турли хил ҳарактеристикалари бир масалани ечувчи икки хил алгоритмни таққослаш учун мўлжалланган. Шунинг учун биз ҳеч қачон саралаш алгоритми билан матрицаларни кўпайтириш алгоритмини таққосламаймиз, балки иккита турли саралаш алгоритмларини бир-бири билан таққослаймиз.
Алгоритмнинг таҳлили натижаси – бу аниқ алгоритм томонидан талаб қилинадиган аниқ секундлар сони ёки компьтер цикллари формуласи эмас. Бундай маълумот фойдасиз, бу ҳолатда компьютернинг турини ҳам кўрсатиш лозим, у бир ёки кўп фойдаланувчи томонидан ишлатиладими, унинг процессори ва тактик частотаси қанақа, процессор чипидаги буйруқлар тўплами тўлиқми ёки соддалашганми ҳамда бажариладиган кодни қанчалик яхши оптималлаштиради кабиларни ҳам кўрсатиш керак бўлади. Бу шартлар алгоритмни ишлатувчи дастурга таъсир кўрсатади. Ушбу шартларни ҳисобга олиш дастурни тезроқ компьютерга кўчириш орқали унинг тез ишлашига қараб алгоритм яхши деган хулосага олиб келарди. Аммо бундай эмас, шунинг учун ҳам бизнинг таҳлил компьютернинг хусусиятларини ҳисобга олмайди.
Кичик ёки оддий дастурларда N дан боғлиқ функция каби бажарилган амалларни аниқ ҳисоблаш мумкин. Аммо кўп ҳолларда бунга ҳожат йўқ. 1.4 бўлимда N + 5 амаллар бажарувчи ва N + 250 амаллар бажарувчи алгоритмлар ўртасидаги фарқ N жуда катта бўлганда сезилмаслиги кўрсатилган. Шунга қарамай биз алгоритмлар таҳлилини амаллар сонини аниқ ҳисоблашдан бошлаймиз.
Яна бир алгоритм томонидан бажариладиган амалларни ҳисобламаслигимизнинг сабаби шундаки, ҳатто энг пухта созлаш ҳам алгоритмнинг унумдорлигини яхшиланишига олиб келади. Қуйида файлдаги турли белгиларнинг сонини ҳисобловчи алгоритмни кўрамиз. Бундай масалани ечувчи алгоритм қуйидагича кўринишга эга бўлиши мумкин:
for all 256 белгилар do
ҳисоблагичга нолни таъминлаш
end for
while файлда яна белгилар бўлса do
кейинги белгини чиқариш
ўқилган белгини ҳисоблагични бирга ошириш
end while
Ушбу алгоритмни кўриб чиқамиз. У таъминлаш циклида 256 ўтиш бажаради. Агар файлда N белгилар бўлса, у ҳолда иккинчи циклда N ўтиш бажарилади. «Нимани ҳисоблаш керак?» деган савол туғилади. Цикл for да дастлаб цикл ўзгарувчиси ўрнатилади, кейин ҳар бир ўтишда цикл бажарилиши черасидан чиқиб кетмаганлиги текширилади ва ўзгарувчи орттирилади. Бу шуни билдирадики, ўрнатиш цикли 257 таъминлаш (битта цикл ўзгарувчиси учун ва 256 ҳисоблагич учун), 256 цикл ўзгарувчиси орттирилади ва ўзгарувчини цикл чегерасидалигини 257 текшириш (битта қўшимча циклни тўхтатиш учун) бажарилади. Иккинчи циклда N + 1 марта шартни текшириш бажариш керак (+1 сўнгги файл бўш бўлгандаги текшириш) ва N ҳисоблагични ортиши бажарилади. Демак барча амаллар:
Орттиришлар N + 256
Таъминлашлар 257
Шартни текширишлар N + 258
Шундай қилиб, кирувчи файлда 500 белгилар бўлган ҳолда алгоритм 1771 амал бажаради, улардан 770 (43%) таси ўрнантишга тўғри келади. Энди N ўлчов оширилганда нима содир бўлишини кўрамиз. Агар файл 50 000 белгидан иборат бўлса, у ҳолда алгоритм 100 771 амал бажаради, улардан 770 таси ўрнатишга боғлиқ (умумий амаллар сонининг 1% ни ташкил қилади.). Ўрнатишдаги амаллар сони ўзгармади, аммо N нинг ошиши билан унинг фоиз кўрсаткичи тоборо камаяди.
Энди бошқа томондан қараймиз. Маълумотлар компьютерда шундай ташкил қилинган бўлсинки, катта маълумот блокларини кўчириш тезлиги таъминлашлар тезлигидек бўлсин. Биз дастлаб 16 ҳисоблагични бошланғич қийматини 0 га таъминлашимиз мумкин, сўнгра ушбу блокни қолган ҳисоблагичларни тўлдириш учун 15 марта кўчирамиз. Бу ўрнатиш циклида текширишлар сони 33 баравар, таъминлашлар 33 баравар ва орттиришлар 31 баравар камайишига олиб келади. Ўрнатишдаги амаллар сони 770 дан 97 гача камаяди, яъни 87% га камаяди. Агар биз олинган ютуқни 50 000 белгидан иборат файлни қайта ишлаш амаллари билан таққосласак тежамкорлик 0.7% камроқни ташкил этади (100 771 амал ўрнига 100 098 амал сарфлаймиз). Кузатишимиз мумкинки вақт бўйича тежамкорлик агар биз ўрнатишларни цикл ёрдамисиз бажарсак жуда юқори бўлиши мумкин, яъни оддий 31 таъминлашлар керак бўлар эди, аммо бу 0.07% тежамкорликни беради.
Кўриб турибмизки барча ўрнатишлар алгоритмнинг бажарилиш вақтига кам боғлиқ. Кирувчи маълумотларнинг ҳажми ўсиши билан ўрнатишлар баҳоси камайиб боради.
Аввал алгоритмларнинг таҳлили ишларида алгоритмнинг Тюринг машинасидаги ҳисоби аниқланган. Таҳлил чоғида масалани ечиш учун кетадиган барча ўтишлар сони ҳисобланган. Алгоритмнинг таҳлили шуни назарда тутадики, бунда масалани ечими учун Тюринг машинаси лентасидаги катаклар саналади. Таҳлилнинг бундай тури ўринли ва у икки алгоритмнинг нисбий тезлигини тўғри аниқлашга имкон беради, аммо унинг амалий амалга ошиши жуда мураккаб ва жуда кўп вақтни олади. Дастлаб алгоритмни бажарувчи Тюринг машинасида ўтувчи функциянинг бажарилиш жараёнини жиддий тавсифлаш керак, сўнгра бажарилиш вақтини ҳисоблаш керак – жуда зерикарли бажариладиган иш.
Бошқа алгоритмларни таҳлил қилишнинг онгли усули алгоритмнинг қандайдир юқори босқичли тилда, масалан Pascal, С, C++, Java да ёки умумий псевдокодда ёзилганлигини кўзда тутади. Псевдокоднинг хусусияти агар у барча алгоритмлар учун умумий бўлган асосий бошқарувчи структуралардан фойдаланилган ҳолда муҳим аҳамият ўйнамайди. Бундай for ёки while цикллар, тармоқланишлар if, case ёки switch структуралари исталган дастурлаш тилида мавжуд. Шу туфайли биз псевдокодлардан фойдаланамиз.
Айрим дастурлаш тилларида буль ифодаларининг қиймати қисқа шаклда ҳисобланади. Бу шуни билдирадики A and В ифодадаги В аъзо агар А рост бўлса ҳисобланади, акс ҳолда В нинг қиймати қандай бўлишидан қатъий назар натижа ёлғон бўлади. Ҳудди шундай A or В ифодадаги В аъзо агар А рост бўлса ҳисобланмайди. Кўриб турибмизки мураккаб шартларни текширишда айрим таққослашларни ҳисобга олмаслик мумкин.