O`zbekiston respublikasi axborot texnologiyalar va kommunikatsiyalarni rivojlantirish vazirligi

Algoritmni baholash

Algoritmning murakkabligini o'lchashning bir necha usullari mavjud. Dasturchilar odatda algoritm tezligiga e'tibor qaratishadi, ammo boshqa ko'rsatkichlar ham bir xil ahamiyatga ega - xotira hajmiga, diskdagi bo'sh joyga talablar. Tez algoritmdan foydalanish, agar kompyuter ishlashi kerak bo'lganidan ko'proq xotirani talab qilsa, kutilgan natijalarga olib kelmaydi.

Xotira yoki vaqt

Ko'pgina algoritmlar xotira hajmi va tezligi o'rtasida tanlovni taklif qiladi. Muammoni tezroq, katta hajmdagi xotiradan foydalangan holda yoki ozroq hajmni olib, sekinroq hal qilish mumkin.

Bu holatda odatiy misol eng qisqa yo'llarni qidirish algoritmi hisoblanadi. Tarmoq shaklida shahar xaritasini taqdim etib, siz ushbu tarmoqning har qanday ikkita nuqtasi orasidagi eng qisqa masofani aniqlash uchun algoritm yozishingiz mumkin. Bu masofalarni kerak bo'lganda hisoblamaslik uchun barcha nuqtalar orasidagi eng qisqa masofani ko'rsatib, natijalarni jadvalga saqlashimiz mumkin. Berilgan ikkita nuqta orasidagi eng qisqa masofani aniqlashimiz kerak bo'lsa, biz shunchaki jadvalning tugagan masofasini olishimiz mumkin.

Natija bir zumda olinadi, ammo bu juda katta hajmdagi xotirani talab qiladi. Katta shahar xaritasida o'n minglab fikrlar bo'lishi mumkin. Keyin, yuqorida tavsiflangan jadvalda 10 milliarddan ortiq hujayralar bo'lishi kerak. Bular Algoritmning ishlashini yaxshilash uchun qo'shimcha 10 Gb xotirani ishlatish kerak.

Ushbu qaramlikdan kosmik-vaqt murakkabligi g'oyasi kelib chiqadi. Ushbu yondashuv bilan, algoritm bajarilish tezligi va iste'mol qilinadigan xotira nuqtai nazaridan baholanadi.

Vaqtinchalik murakkablikka e'tiborni qaratamiz, ammo shunga qaramay, biz iste'mol qilingan xotiraning hajmini aniq belgilaymiz.