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

1.1.2. Хотира жиҳатидан мураккаблик
Биз асосан алгоритмларнинг вақт бўйича мураккаблигини муҳокама қиламиз, аммо у ёки бу алгоритм бажарилиши учун қанча хотира кераклиги ҳақида гапиришимиз мумкин. Компьютерларнинг дастлабки чегараланган хотира бўйича (ҳам ички, ҳам ташқи) ривожланиш босқичларида бундай таҳлил муҳим аҳамият касб этган. Барча алгоритмлар икки турга – етарлича чекланган хотира билан ишлайдиган ва қўшимча жой талаб қиладиган алгоритмларга бўлинади. Кўпинча дастурчиларга секинроқ алгоритмни танлашга тўғри келган, чунки у мавжуд хотира билан кифояланган ва қўшимча ташқи қурилма талаб қилмаган.
Бугунги кунда таклиф қилинаётган дастурий таминотларни кузатиб шуни кўриш мумкинки хотира бўйича таҳлилга катта эътибор қаратилмайди. Ҳатто оддий дастурлар учун хотира ҳажми мегабайтларни ташкил қилади. Дастурларни яратувчилар эса фойдаланувчини қўшимча хотира сотиб олиши билан ўзларини оқлашади. Натижада компьютерлар ўз ишлаш вақтларидан аввалроқ эскириб қолишади.
Кейинги пайтларда кенг тарқалган чўнтак компьютерлари (PDA -- personal digital assistant) да маълумотлар ва дастурлар учун 2 дан то 8 мегабайтгача хотира ўрнатилган. Шу туфайли маълумотларни ихчам сақлашни таъминловчи кичик дастурларни яратиш долзарб бўлиб қолаверади.
1.2. Нимани ҳисоблаш ва нимани ҳисобга олиш керак
Нимани ҳисоблаш керак саволини ечиш икки қадамдан иборат. Биринчи қадамда асосий амал ёки амаллар гуруҳи танланади, иккинчидан бу амалларнинг қайсилари алгоритм танасида таркиб топади, қайсилари қўшимча сарфларга ёки маълумотларни рўйхатга олишга ва ҳисобга олишга кетиши аниқланади.
Асосан икки турдаги амаллар ишлатилади: солиштириш ва арифметик амаллар. Барча солиштириш амаллари эквивалент ҳисобланади ва улар саралаш ва қидириш алгоритмларида ҳисобга олинади. Бундай алгоритмларнинг муҳим жиҳати икки ўлчовни солиштириш ҳисобланади, қидиришда – ушбу ўлчов берилганларга москеладими, саралашда – у ушбу интервалдан чиққанлиги текширилади. Солиштириш операторлари бир ўлчовни икинчисига тенг ёки тенг эмаслигини, кичик ёки катталигини, кичик ёки тенглигини, катта ёки тенглигини текширади.
Биз арифметик амалларини аддитив ва мультипликатив каби икки гуруҳга ажратамиз. Аддитив операторлар (қисқача қўшиш) ўзига қўшиш, айириш, ҳисоблагични оширувчи ва камайтирувчиларни қамраб олади. Мультипликатив операторлар (қисқача кўпайтириш) ўз ичига кўпайтириш, бўлиш ва модул бўйича қолдиқ олиш кабиларни бириктиради. Бундай икки гуруҳга бўлиниш кўпайтиришнинг қўшишга қараганда узоқ ишлашига боғлиқ. Амалиётда айрим алгоритмлар агар уларда кам кўпайтиришлар бўлса бошқаларига нисбатан афзал ҳисобланади, ҳатто уларда қўшишлар сони пропорционал ўсса ҳам.
Бутун кўпайтириш ёки икки даражасига бўлиш махсус ҳолни юзага келтиради. Бу амал силжишга мос келади, охиргиси тезлик буйича қўшишга эквивалент. Аммо кўпайтириш ва 2 га бўлиш биринчи ўринда “бўлаклаш ва бошқариш” алгоритмларида учрайди, қайсики солиштириш амаллари асосий аҳамиятни ўйнайди.