Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

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%. Агар эришилган натижани 50000 белгидан иборат файл устида бажарсак, тежамкорлик 0.7% ни ташкил қилади (100771 та амал ўрнига 100098 амал бажарамиз).
Агарда барча амалларни циклдан фойдаланмай 31 та юклашлар орқали бажарганимизда, вақтни янада тежаган бўлардик, аммо бу усул 0.07 фойда келтиради. Ишимиз унумли бўлмайди.
Кўриб турганимиздек, алгоритмнинг бажарилиш вақти билан боғлиқ барча амаллар бефойда. Таҳлил тили билан айтганда, бошланғич маълумотлар ҳажмининг ортишига алохида эътибор қаратиш керак.
Аввалги ишларда алгоритмларни таҳлил қилишда алгоритмларни Тьюринг машинасида ҳисоблаш аниқланган. Таҳлилда масалани ечиш учун зарур бўлган ўтишлар сони ҳисобланган. Бу турдаги таҳлил тўғри бўлиб, икки алгоритмнинг нисбий тезликларини аниқлаш имконини беради, аммо унинг амалиётда қўлланилиши кам, чунки кўп вақт талаб қилади.
Аввал бажариладиган алгоритмнинг Тьюринг машинасидаги ўтиш функцияларини ёзиш, кейин эса бажарилиш вақти ҳисобланади.
Алгоритмларни таҳлил қилишнинг бошқа яхшироқ усули - уни бирор юқори босқичли тил Pascal, C, C++, JAVA да ёзиш ёки оддий псевдокодларда ёзишдир. Барча алгоритмларнинг асосий бошқарув структурасини ифодалаганда псевдокодларнинг хоссалари аҳамиятга эга эмас. Ихтиёрий тил бизнинг талабимизга жавоб беради, чунки for ёки while шаклидаги цикллар, if, case ёки switch кўринишидаги тармоқланиш механизмлари барча дастурлаш тилларида мавжуд. Ҳар гал биз битта аниқ алгоритмни кўриб чиқишимизга тўғри келади – унда бирдан ортиқ функция ёки программа фрагменти киритилган бўлади, шунинг учун юқорида келтирилган тилларнинг тезлиги умуман муҳим эмас. Псевдокодлардан фойдаланишимизнинг сабаби шунда.
Кўплаб дастурлаш тилларида мантиқий ифоданинг қийматлари қисқартирилган шаклда ҳисобланади. Бу A and В ифодадаги В ҳаднинг қиймати қачонки A рост бўлсагина ҳисобланади, акс ҳолда натижа В га боғлиқ бўлмаган тарзда ёлғон бўлади. Худди шундай A or В ифодада А нинг қиймати рост бўлса, В ҳаднинг қиймати ҳисобланмайди. Кўриниб турибдики, мураккаб шартларнинг 1 ёки 2 га тенглигидаги таққослашларининг сонини ҳисоблаш шарт эмас. Шунинг учун бу бобни ўрганишда мантиқий ифодаларнинг қийматини қисқартириб ҳисобланишини эътиборсиз қолдирамиз.