Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

Хотира бўйича мураккаблик
Биз асосан алгоритмларнинг вақт бўйича мураккаблигини муҳокама қиламиз, аммо иш бажариш учун у ёки бу алгоритмга қанча хотира кераклиги ҳақида ҳам айтиш мумкин. Компьютер хотираси (ҳам ички, ҳам ташқи) ҳажми чегараланган. Компьютерлар ривожланишининг дастлабки босқичларида бу таҳлил услубий характерга эга эди. Барча алгоритмлар чегараланган хотира етарли ёки қўшимча майдонни талаб қилувчи алгоритмларга бўлинади. Кўпинча дастурловчилар хотирасига эга ва ташқи қурилмалар талаб қилмайдиган секин ишловчи алгоритмни танлашар эди.
Компьютер хотирасига бўлган талаб жуда катта эди, шунинг учун қайси маълумотлар сақланиб қолади, бундай сақлашнинг самарали усуллари қандай каби саволлар ўрганилар эди. Фараз қилайлик, масалан, биз -10 дан +10 гача интервалдаги вергулдан кейин битта ўнли белгига эга бўлган моддий сон ёзяпмиз. Моддий сони ёзишда кўпчилик компьютерлар 4 дан 8 байтгача хотира сарфлайди, леки нагар бу сони аввалдан 10 га кўпайтирсак, -100 дан +100 гача интервалдаги бутун сон ҳосил қиламиз ва уни сақлаш учун бор йўғи бир байт сарфланади. Биринчи вариант билан солиштирсак, 3-7 байт тежашга эришилди. 1000 та шундай сон сақлайдиган дастур 3000 дан 7000 байтгача тежайди. Агар ўтган асрнинг 80-йилларида компьютерларнинг хотираси 65536 байт бўлганлигини эътиборга олсак, жиддий тежаш кўзга ташланади. Айнан шу компьютер дастурларининг узоқ йил ишлаши хотирани тежаш зарурияти Билан бир қаторда 2000 йил муаммо туғдирди. Агар сизнинг дастурингиз турли саналардан фойдаланса, йилни ёзиш учун 1999 ўрнига 99 ифодасини сақлаган ҳолда жойнинг ярмини тежаса бўлади. 80-йиллардаги дастур муаллифлари маҳсулотлари 2000 йилгача яшашини тахмин ҳам қилишмаган эди.
Ҳозирги кунда бозорларда таклиф қилинаётган дастурий таъминотга назар ташласак, хотиранинг бундай таҳлили ўтказилмаганлиги аён бўлади. Оддий дастурлар учун зарур хотира ҳажми мегабайтларда ўлчанади. Дастур тузувчилар жойни тежаш эҳтиёжини ҳис қилмаётганга ўхшайдилар, уларнинг фикрича, агар фойдаланувчида етарли хотира бўлмаса, у дастур бажарилиши учун етмаётган 32 ёки ундан ортиқ мегабайт хотира ёки уни сақлаш учун янги қаттиқ диск сотиб олади. Натижада компьютерлар ўзининг белгиланган муддатидан аввал яроқсиз ҳолга келиб қолади.
Яқинда тарқалган чўнтак компьютерлари (PDA – personal digital assistant) янги оҳанг олиб кирди. Бундай қурилманинг хотираси ҳам маълумотлар, ҳам дастурлар учун 2 дан 8 мегабайтгача. Шунинг учун ҳам маълумотларни ихчам сақлашни таъминловчи кичик дастурларни яратиш қийин бўлиб қолмоқда.