Мундарижа Кириш
Download 0.91 Mb.
|
algoritm
- Bu sahifa navigatsiya:
- I I . боб
- Хулоса ...............................................................................................................
- ............................................................................................................... Кириш
- Алгоритмларни таҳлил қилиш зарур бўлган усулларни аниқлаш, уларни математик асосларни келтириш ва ўрганиш;
- Алгоритмлар асосида амалий дастурий таъминот яратиш ва таҳлил натижасида олинган ечимларни таққослаш;
- 1.1. Алгоритм таҳлили нима
- 1.1.1. Маълумотлар синфлари
- 1.1.2. Хотира жиҳатидан мураккаблик
- 1.2. Нимани ҳисоблаш ва нимани ҳисобга олиш керак
|
Мундарижа Кириш ......... I . боб. Алгоритмларни таҳлил қилиш асослари......................................... 1.1. Алгоритм таҳлили нима? .......... Маълумотлар синфлари................................................... Хотира жиҳатдан мураккаблик........................................ 1.2. Нимани ҳисоблаш ва нимани ҳисобга олиш керак .......... 1.3. Алгоритмни таҳлил қилиш учун зарур бўлган асосий математик тушунчалар ......... Логарифм ......... Бинар дарахт ......... Эҳтимоллик ......... Йиғиндини ҳисоблаш формулалари ........ 1.4. Баҳолаш мезонининг хусусиятлари…………………………….. Баҳолаш мезонини усуллари ........ 1.5. «Бўлаклаш ва бошқариш» шаклидаги алгоритмлар…………... Рекурсияга асосланган усуллар………………………….. Алгоритм самарадорлигининг қуйи чегараси……………. 1.6. Рекуррент муносабатлар…………………………………………… 1.7. Дастурлар таҳлили…………………………………………….. I I . боб. Саралаш ва қидириш алгоритмларининг синфлари ва уларни қиёсий ҳарактеристикалари…………………………….. 2.1. Қидириш алгоритмлари ва уларни баҳолаш................................... Кетма-кет қидириш алгоритми ва унинг таҳлили ........ Иккилик дарахт бoйича қидириш ва унинг таҳлили ........ Қидириш алгоритмларининг қиёсий ҳарактеристикалари.. 2.2. Саралаш алгоритмлари ва уларни баҳолаш...................................... Ўрнинга қўйиш усули ва унинг таҳлили…………………… Ўрин алмаштириш (пуфакча) усули ва унинг таҳлили........ Шелл усули ва унинг таҳлили............................................... Пирамида усули ва унинг таҳлили........................................ Бирлаштириб саралаш усули ва унинг таҳлили.................. Тез саралаш (QuickSort) усули ва унинг таҳлили................. Кўп фазали саралаш усули ва унинг таҳлили....................... Саралаш алгоритмларининг қиёсий ҳарактеристикалари.. I I I. боб . Дастурий воситанинг тузилиши ва тавсифи ҳамда ундан фой- даланиш учун кўрсатмалар. ......... 3.1. Дастурий воситанинг умумий структураси...................................... 3.2. Асосий ва бошқарилувчи модуллар тавсифи....................................... 3.3. Дастурий воситадан фойдаланиш учун кўрсатмалар...................... Хулоса ............................................................................................................... Фойдаланилган адабиётлар ......................................................................... Илова ............................................................................................................... Кириш Айрим тижоратга оид дастурий маҳсулотларни кузатиб шунга амин бўлиш мумкинки, уларни яратувчилари на дастурларнинг вақтий самарадорлигига, на хотирадан оқилона фойдаланишга эътибор беришмайди. Улар, агар дастур жуда кўп жой эгалласа, у ҳолда фойдаланувчи қўшимча хотира сотиб олади, агар у жуда узоқ вақт ишласа, у ҳолда фойдаланувчи тезроқ ишлайдиган компьютер сотиб олади деб ҳисоблашади. 80-йилларнинг бошларида компьтерларнинг архитектураси уларнинг тезлиги ва хотира ҳажмини жиддий чегаралаган эди. Кўпинча дастурнинг умумий ҳажми ва маълумотлари 64 К дан ошмаган. Замонавий шахсий копьютерларда бу ўлчов 1000 бараварга ўсган. Аммо компьютерларнинг тезлиги чексиз оша олмайди. У электронларнинг симдаги кўчиш тезлиги билан, ёруғликнинг оптик кабеллардаги тарқалиш тезлиги билан ва ҳисоблашларда иштирок этувчи компьютерлар алоқаси каналлар коммутацияси тезлиги билан чекланган. Бошқа чекланишлар компьютернинг унумдорлигидан боғлиқ бўлмасдан, балки бевосита ечиладиган масаланинг мураккаблигидан боғлиқ бўлади. Замонавий дастурий таъминотлар 1980 йиллардагиларига нисбатан мураккаброқ ва компьютерлар сезиларли яхши бўлди, аммо бу дастурларни тузиш пайтида уларнинг самарадорлиги билан боғлиқ масалаларни эътиборсиз қолдиришга сабаб бўла олмайди. Айрим лойиҳаларнинг таснифида дастурчиларни натижавий маҳсулот билан хотирани тежаш ва бажарилиш тезлигини оширишга мажбур қилувчи чекланишлар киритилган. Шундай масалалар борки, уларни ечиш учун ҳатто энг тез алгоритмлардан фойдаланган ҳолда ҳам инсон умри етмайди. Бундай масалалар ичида шундай муҳимлари мавжудки, тахминий жавобларни олиш учун алгоритмлар керак. Шунинг учун дастурий таъминот яратишда алгоритмларнинг самарадорлигини баҳолаш ва уларни амалда тадбиқ этиш муҳим назарий, амалий ва услубий аҳамиятга эга. Ишнинг мақсади амалий дастурлаштириш жараёнида энг кўп қўлланиладиган масалалар, яъни “Саралаш” ва “Қидириш” алгоритмлари бўйича тадқиқотлар олиб бориш ва қуйидаги масалаларни ечишдан иборат:
Алгоритмларни таҳлил қилиш зарур бўлган усулларни аниқлаш, уларни математик асосларни келтириш ва ўрганиш; Ўрганилган таҳлил қилиш воситаларини маълумотларни саралаш ва қидириш алгоритмларининг самарадорлигини боҳолашга тадбиқ этиш; Алгоритмлар асосида амалий дастурий таъминот яратиш ва таҳлил натижасида олинган ечимларни таққослаш; Дастурий таъминот орқали маълумотларни саралаш ва қидириш жараёнини ўргатишни визуаллаштириш. I. АЛГОРИТМЛАРНИ ТАҲЛИЛ ҚИЛИШ АСОСЛАРИ Алгоритмлар таҳлили компьютерга ёки ишлатиладиган дастурлаш тилига боғлиқ эмас, шунинг учун ушбу ишда алгоритмлар псевдокодда ёзилади. Бу алгоритмларни шартли ифодалар (IF ёки CASE/SWITCH), цикллар (FOR ёки WHILE) ва рекурсия тушунчаларига эга бўлган исталган киши ўқий олади. Бир масалани кўп алгоритмлар ечиши мумкин. Уларнинг ҳар бирининг самарадорлиги турли хил характеристикалар билан тавсифланади. Алгоритмнинг самарадорлигини таҳлил қилишдан олдин аввало ушбу алгоритм масалани тўғри ечишини исботлаш лозим. Акс ҳолда самарадорлик ҳақидаги саволларнинг ҳеч қандай аҳамияти бўлмайди. Агар алгоритм қўйилган масалани ечса, у ҳолда биз ушбу ечимнинг қанчалик самарадорлигини кўриб чиқишимиз мумкин. Ушбу боб ўзига таҳлил ва етарлича мураккаб алгоритмларни қиёслаш асосларини бириктирган. Алгоритмнинг таҳлили жараёнида унинг бажарилиши учун керак бўлган “вақт” лар сони аниқланади. Бу ҳақиқий секундлар сони ёки бошқа вақт оралиқлари бўлмасдан, балки алгоритм томонидан бажариладиган тақрибий операциялар сонидир. Операциялар сони алгоритмнинг бажарилиш вақтини нисбий ўлчовидир. Шу сабабли арим ҳолларда “вақт” билан алгоритмнинг ҳисоблаш мураккаблигини атаймиз. Таҳлил учун алгоритмнинг компьютерда бажарилиши учун талаб қилинадиган секундлар сони яроқсиздир, бизни фақат аниқ масалани ечувчи алгоритмнинг тақрибий самарадорлиги қизиқтиради. Аслида алгоритмнинг фактик амаллари сони у ёки бу кирувчи маълумотларда катта қизиқиш намоён қилмайди ва алгоритм ҳақида кўп нарса хабар бермайди. Бу ҳолда бизни аниқ алгоритмнинг кирувчи маълумотлар ўлчамидан боғлиқ амаллар сони қизиқтиради. Биз икки алгоритмни амаллар сони ўсиш тезлиги орқали қиёслашимиз мумкин. Айнан ўсиш тезлиги муҳим аҳамиятга эга, модомики кирувчи маълумотларнинг кичик ўлчамида А алгоритм В алгоритмга қараганда кам амаллар сонини талаб қилади, аммо кирувчи маълумотларнинг ўсиши билан бу ҳолат аксинча юз беради. Алгоритмларнинг икки йирик синфи – бу такрорланувчи ва рекурсив алгоритмлардир. Такрорланувчи алгоритмларнинг асосини цикллар ва шартли ифодалар ташкил этади. Бундай алгоритмларни таҳлил қилиш учун цикл ичида бажариладиган амаллар сонини ва циклдаги итерациялар сонини баҳолаш талаб қилинади. Рекурсив алгоритмлар катта масалаларни қисмларга бўлади ва ҳар бир қисмга алоҳида қўлланилади. Бундай алгоритмлар айрим ҳолларда “бўлаклаш ва бошқариш” деб номланади ва уларнинг қўлланилиши жудда катта самадорликка олиб келади. Катта масалани бўлиш йўли билан ечиш жараёнида кичик оддий ва тушунарли алгоритмлар тузилади. Рекурсив алгоритмнинг таҳлили масалани қисмларга бўлиш учун, алгоритмни ҳар бир қисм учун бажарилиши ва алоҳида натижаларни масалани бутун ечими учун бирлаштиришга кетадиган амаллар сонини ҳисоблашни талаб қилади. Ушбу маълумотларни ва қисмлар сони ва уларнинг ўлчами ҳақидаги маълумотларни йиғиб биз алгоритмнинг мураккаблиги учун реккурент боғланишни келтириб чиқаришимиз мумкин. Олинган реккурент боғланишга ёпиқ шакл бериш мумкин, кейин натижани бошқа ифодалар билан таққослаш мумкин. Биз ушбу бўлимни таҳлил нима ва у нима учун керак кабиларни тавсифлаш билан бошлаймиз. Сўнгра биз таҳлил ўтказишда кўриладиган амаллар ва параметрлар доирасини ажратамиз. Мадомики бизнинг таҳлил учун математика зарур, кейинги бўлимларда итератив ва рекурсив алгоритмлар таҳлилида қўлланиладиган муҳим математик тушунчалар ва хусусиятлар келтирилган. 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 ҳисобидан кўпроқ хотирани талаб қилади. Бу қўшимча жой агар сон ёки белгилар солиштирилса муҳим аҳамият ўйнамайди, аммо бошқа маълумотлар турлари билан ишлаганда у катта аҳамиятга эга. Кўпчилик замонавий дастурлаш тиллари катта ва мураккаб объектлар ёки ёзувларни солиштириш операторларини аниқлашга имкон беради. Бу ҳолларда вақтинчалик ўзгарувчилардан фойдаланиш кўп жойни талаб этади. Алгоритмларни самарадорлигини таҳлил қилишда бизни биринчи навбатда вақт масаласи қизиқтиради, лекин айрим хотира муҳим аҳамият ўйнаган ҳолларда биз уларни муҳокама қиламиз. Алгоритмларнинг турли хил ҳарактеристикалари бир масалани ечувчи икки хил алгоритмни таққослаш учун мўлжалланган. Шунинг учун биз ҳеч қачон саралаш алгоритми билан матрицаларни кўпайтириш алгоритмини таққосламаймиз, балки иккита турли саралаш алгоритмларини бир-бири билан таққослаймиз.
Яна бир алгоритм томонидан бажариладиган амалларни ҳисобламаслигимизнинг сабаби шундаки, ҳатто энг пухта созлаш ҳам алгоритмнинг унумдорлигини яхшиланишига олиб келади. Қуйида файлдаги турли белгиларнинг сонини ҳисобловчи алгоритмни кўрамиз. Бундай масалани ечувчи алгоритм қуйидагича кўринишга эга бўлиши мумкин: 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 В ифодадаги В аъзо агар А рост бўлса ҳисобланмайди. Кўриб турибмизки мураккаб шартларни текширишда айрим таққослашларни ҳисобга олмаслик мумкин. 1.1.1. Маълумотлар синфлари Кирувчи маълумотларнинг алгоритмларнинг таҳлилида ўта катта аҳамият касб этади, мадомики алгоритмнинг ҳаракат кетма-кетлиги кирувчи маълумотларни охирги ўринда қарамайди. Масалан, N элементдан иборат рўйхатдан энг катта элементни топиш учун қуйидаги алгоритмдан фойдаланиш мумкин: largest = list [1] for i = 2 to N do if (list [i] > largest) then largest = list[i] end if end for Тушунарлики, агар рўйхат камайиш тартибида тартибланган бўлса, у ҳолда цикл бошланишидан олдин битта таъминлаш бажарилади, цикл ичида эса таъминлаш бажарилмайди. Агар рўйхат ўсиш тартибида тартибланган бўлса, у ҳолда ҳаммаси бўлиб N таъминлаш бажарилади (битта цикл олдидан ва N-1 цикл ичида). Таҳлил чоғида биз кирувчи қийматларнинг мумкин бўлган турли хил тўпламини қарашимиз керак. Агар биз битта тўплам билан чеклансак у ҳолда у ечимнинг жуда тез (ёки жуда секин) бўлишига олиб келиши мумкин. Натижада биз алгоритм ҳақидаги нотўғри тасаввурга эга бўламиз. Бунинг ўрнига биз кирувчи тўпламларнинг барча турини қараймиз. Биз турли хил кирувчи тўпламларни алгоритмнинг ҳар бир тўпламдаги хусусиятига боғлиқ равишда синфларга ажратишга ҳаракат қиламиз. Бундай ажратиш кўриладиган имкониятлар сонини камайтиради. Масалан, 10 та ҳар хил сонларни рўйхтага турлича жойлаштиришлар сони 10!= 3 628 800 га тенг. 10 та сондан иборат рўйхатга энг катта элементни топиш алгоритмини қўллаймиз. Биринчи сони энг катта бўлган 362 880 та кирувчи тўпламларга эга бўламиз, уларнинг барчасини бир синфга киритиш мумкин. Агар катталиги бўйича энг катаси 2 ўринда турган бўлса, у ҳолда алгоритм икки таъминлаш бажаради. Бундай тўпламлар сони ҳам 362 880 ни ташкил қилади, уларни бошқа синфга киритиш мумкин. Кўриниб турибдики, энг катта соннинг ўрнини 1 дан N гача алмаштириш билан таъминлашлар сони ҳам ўзгаради. Шу сабабли биз барча кирувчи тўпламларни қилинган таъминлашларги кўра N та турли синфларга бўлишимиз керак. кўриб турибсизки ҳар бир синфга кирувчи барча тўпламларни ёзиб чиқишнинг ёки тавсифлашнинг зарурати йўқ. Синфларлар сонини ва ҳар синф тўпламидаги иш ҳажмини билиш керак холос. Кирувчи маълумотларнинг мумкин бўлган тўплами сони N нинг ошиши билан жуда катта бўлиши мумкин. Масалан, 10 та турли сонларни рўйхатга 3 628 800 усул билан жойлаштириш мумкин. Бу усулларнинг барчасини кўриб чиқишнинг имкони йўқ. Бунинг ўрнига биз рўйхатларни алгоритмнинг нима қилишига боғлиқ равишда синфларга ажратамиз. Юқорида кўрсатилган алгоритм учун ажратиш энг катта қийматнинг жойлашувига асосланади. Натижада 10 та турли синфлар ҳосил бўлади. Бошқа алгоритм учун, масалан, энг катта ва энг кичик қийматни топиш алгоритмида бизнинг ажратишлар энг катта ва энг кичик қийматнинг қаерда жойлашганлигига асосланиши мумкин. Бундай ажратишлар 90 синфни ташкил қилади. Биз синфларни ажратиб олгач, ҳар синфдаги бир тўпламда алгоритмнинг ҳолатини кўришимиз мумкин. Агар синфлар тўғри танланган бўлса, у ҳолда бир синфдаги барча кирувчи тўпламларда алгоритм бир хил сондаги амаллар бажаради, бошқа синфдаги тўпламларда эса бу амаллар сони бошқача бўлади. 1.1.2. Хотира жиҳатидан мураккаблик Биз асосан алгоритмларнинг вақт бўйича мураккаблигини муҳокама қиламиз, аммо у ёки бу алгоритм бажарилиши учун қанча хотира кераклиги ҳақида гапиришимиз мумкин. Компьютерларнинг дастлабки чегараланган хотира бўйича (ҳам ички, ҳам ташқи) ривожланиш босқичларида бундай таҳлил муҳим аҳамият касб этган. Барча алгоритмлар икки турга – етарлича чекланган хотира билан ишлайдиган ва қўшимча жой талаб қиладиган алгоритмларга бўлинади. Кўпинча дастурчиларга секинроқ алгоритмни танлашга тўғри келган, чунки у мавжуд хотира билан кифояланган ва қўшимча ташқи қурилма талаб қилмаган. Бугунги кунда таклиф қилинаётган дастурий таминотларни кузатиб шуни кўриш мумкинки хотира бўйича таҳлилга катта эътибор қаратилмайди. Ҳатто оддий дастурлар учун хотира ҳажми мегабайтларни ташкил қилади. Дастурларни яратувчилар эса фойдаланувчини қўшимча хотира сотиб олиши билан ўзларини оқлашади. Натижада компьютерлар ўз ишлаш вақтларидан аввалроқ эскириб қолишади. Кейинги пайтларда кенг тарқалган чўнтак компьютерлари (PDA -- personal digital assistant) да маълумотлар ва дастурлар учун 2 дан то 8 мегабайтгача хотира ўрнатилган. Шу туфайли маълумотларни ихчам сақлашни таъминловчи кичик дастурларни яратиш долзарб бўлиб қолаверади. 1.2. Нимани ҳисоблаш ва нимани ҳисобга олиш керак Нимани ҳисоблаш керак саволини ечиш икки қадамдан иборат. Биринчи қадамда асосий амал ёки амаллар гуруҳи танланади, иккинчидан бу амалларнинг қайсилари алгоритм танасида таркиб топади, қайсилари қўшимча сарфларга ёки маълумотларни рўйхатга олишга ва ҳисобга олишга кетиши аниқланади. Асосан икки турдаги амаллар ишлатилади: солиштириш ва арифметик амаллар. Барча солиштириш амаллари эквивалент ҳисобланади ва улар саралаш ва қидириш алгоритмларида ҳисобга олинади. Бундай алгоритмларнинг муҳим жиҳати икки ўлчовни солиштириш ҳисобланади, қидиришда – ушбу ўлчов берилганларга москеладими, саралашда – у ушбу интервалдан чиққанлиги текширилади. Солиштириш операторлари бир ўлчовни икинчисига тенг ёки тенг эмаслигини, кичик ёки катталигини, кичик ёки тенглигини, катта ёки тенглигини текширади.
Бутун кўпайтириш ёки икки даражасига бўлиш махсус ҳолни юзага келтиради. Бу амал силжишга мос келади, охиргиси тезлик буйича қўшишга эквивалент. Аммо кўпайтириш ва 2 га бўлиш биринчи ўринда “бўлаклаш ва бошқариш” алгоритмларида учрайди, қайсики солиштириш амаллари асосий аҳамиятни ўйнайди. Маълумотлар синфлари Алгоритмларни таҳлили чоғида кирувчи маълумотлар танлови унинг ишига жиддий таъсир кўрсатиши мумкин. Айрим саралаш алгоритмлари агар кирувчи рўйхат сал кам сараланган бўлса жуда тез ишлайди, у ҳолда ушбу рўйхатда бошқа алгоритмлар жуда оддий натижа кўрсатади. Тасодифий рўйхатда эса тескари нтижага олиб келади. Шу сабабли биз битта кирувчи маълумотларда алгоритмларнинг таҳлили билан чекланмаймиз. Амалиётда биз алгоритмнинг бажарилишига энг тезликни ва энг секинликни таъминловчи маълумотларни излаймиз. Бундан ташқари биз алгоритмнинг барча мумкин бўлган маълумотлар тўпламидаги ўртача самарадорлигини баҳолаймиз. Энг яхши ҳол Алгоритм учун энг яхши ҳолат шундай кирувчи маълумотлар тўпламики, бунда алгоритм энг кам вақтда бажарилади. Бундай маълумотлар тўплами ўзида шундай қийматлар комбинациясини намоён қиладики бунда алгоритм энг кам ҳаракатлар бажаради. Агар биз қидириш алгоритмини қарасак, у ҳолда кирувчи маълумотлар энг яхши ҳисобланади – агар қидирилаётган қиймат (одатда мақсад қиймат ёки калит дейилади) текширилаётган тўпламнинг бринчи ўринида ёзилган бўлса. Бундай алгоритм учун унинг қанчалик мураккаблигидан қатъий назар битта солиштириш талаб қилинади. Сезиш мумкинки, рўйхатда қидиришда у қандай узунликда бўлишидан қатъий назар энг яхши ҳол доимий вақтни талаб қилади. Умуман энг яхши ҳолатда алгоритмнинг бажарилиш вақти кичик ёки оддий доимий бўлади, шунинг учун бундай таҳлилни кам олиб борамиз. Энг ёмон ҳол Энг ёмон ҳолатни таҳлил қилиш энг муҳим ҳисобланиб, у алгоритмнинг максимал бажарилиш вақтини намоён қилади. Энг ёмон ҳолни таҳлил қилиш чоғида алгоритм энг узоқ вақт талаб қиладиган кирувчи маълумотларни қидириш керак. Қидириш алгоритми учун мос кирувчи маълумотлар бу шундай рўйхатки унда қидирилаётган калит энг охиририда жайлашган ёки умуман мавжуд бўлмаган ҳолатдир. Натижада N солиштиришлар талаб қлиниши мумкин. Энг ёмон ҳолни таҳлил қилиш танланган алгоритмдан боғлиқ равишда бизнинг дастуримиз қисмининг ишлаш вақти учун юқори баҳолашларини беради. Ўртача ҳол Ўртача ҳолни таҳлил қилиш энг мураккаб ҳисобланиб, у турли тафсилотларни ҳисобга олишни талаб қилади. Ушбу таҳлил асосида мумкин бўлган кирувчи маълумотлар тўламини ажратувчи гуруҳларни аниқлаш ётади. Иккинчи қадамда кирувчи маълумотлар тўпламининг ҳар бир гуруҳга тегишлилик эҳтимоли аниқланади. Учинчи қадамда алгоритмнинг ҳар қайси маълумотлардаги бажарлиш вақти ҳисобланади. Алгоритмнинг бир гуруҳдаги барча маълумотлардаги бажарлиш вақти бир хил бўлиши керак, акс ҳолда гуруҳни қайта бўлиш керак. Алгоритм бажарилиш вақтининг ўртача вақти қуйидаги формула бўйича ҳисобланади:  (1.1)
бунда n билан кирувчи маълумотлар ўлчови, т билан гуруҳлар сони, pi билан кирувчи маълумотларнинг i рақамли гуруҳга тегишлилик эҳтимоли, ti билан эса i рақамли гуруҳ маълумотларини алгоритм томонидан қайта ишлашга кетадиган вақт белгиланган. Айрим ҳолларда биз кирувчи маълумотларнинг ҳар қайси гуруҳларга тушиш эҳтимоли бир хил деб тахмин қиламиз. Бошқача қилиб айтганда, агар гуруҳлар 5 та бўлса, у ҳолда биринчи гуруҳга тушиш эҳтимоли иккинчи гуруҳга тушиш эҳтимолидек ва ҳ.к., яъни ҳар бир гуруҳга тушиш эҳтимоли 0.2 га тенг. Бу ҳолда ўртача бажарилиш вақти юқоридаги формула орқали топилади ёки унга эквивалент тенг эҳтимолли барча гуруҳларга оид қисқа формуладан фойдаланиш мумкин  (1.2)
Download 0.91 Mb. Do'stlaringiz bilan baham: 
|