Texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muxammad al-xorazmiy nomidagi toshkent

3. Algoritmning murakkabligi turlari. Vaqtinchalik, hajmiy va intellektual murakkablik.

Algoritmdan nimani xohlaymiz? Birinchidan, uni iloji boricha tezroq ishlashi uchun. Ikkinchidan, talab qilinadigan xotira hajmini iloji boricha kamroq ushlab turish. Uchinchidan, uni iloji boricha sodda va tushunarli qilish, bu dasturni disk raskadrovka qilishni osonlashtiradi. Afsuski, bu talablar bir-biriga ziddir va jiddiy muammolarda kamdan-kam hollarda har jihatdan boshqalarga qaraganda yaxshiroq algoritm topish mumkin.

Algoritmning murakkabligi haqida gapirganda, qaysi ijrochi haqida gaplashayotganimizni, qanday elementar operatsiyalardan foydalanayotganimizni aniqlab olishimiz kerak. Odatda, bu universal ijrochilardan biridir (ko'p hollarda kompyuterni universal ijrochi deb hisoblash mumkin). Algoritmning murakkabligini o'lchashning bir necha yo'li mavjud: vaqtinchalik, hajmiy va intellektual.

Algoritmning vaqtinchalik murakkabligi (ishlash) - berilgan algoritmga muvofiq ishlaydigan dasturning bajarilish vaqti haqida tez-tez aytiladi. Algoritmning ishlash vaqti bu T tomonidan bajarilgan elementar operatsiyalar soni. Ushbu yondashuv algoritmning bajaruvchisi xususiyatlarini emas, balki sifatini baholashga imkon beradi (masalan, algoritm bajariladigan kompyuter tezligi).

Algoritmning vaqtinchalik murakkabligi bu kirish ma'lumotlariga qarab uni bajarish uchun zarur bo'lgan T vaqtidir. U bitta harakatning o'rtacha bajarilish vaqti bilan k elementar harakatlar k sonining ko'paytmasiga teng: T = kt.

T algoritmni amalga oshiruvchi ijrochiga bog'liq bo'lganligi sababli, algoritmning murakkabligi birinchi navbatda k ning qiymati bilan belgilanadi deb taxmin qilish tabiiydir. Shubhasiz, algoritmni bajarish jarayonida operatsiyalar soni eng ko'p ishlov beriladigan ma'lumotlar miqdoriga bog'liq. Darhaqiqat, 100 ta familiya ro'yxatini alifbo tartibida saralash 100000 ta familiya ro'yxatiga nisbatan ancha kam operatsiyalarni talab qiladi. Shuning uchun algoritmning murakkabligi kirish ma'lumotlari miqdori funksiyasi sifatida ifodalanadi.

Hajmiy murakkablik. Dasturchilar odatda algoritm tezligiga e'tibor qaratishadi, ammo boshqa ko'rsatkichlar ham unchalik muhim emas - xotira hajmiga talablar, diskdagi bo'sh joy. Tezkor algoritmdan foydalanish kutilgan natijalarni bermaydi, agar u kompyuterga qaraganda ko'proq xotirani talab qilsa. Hajmiy samaradorlik dasturni ishga tushirish uchun zarur bo'lgan xotira hajmi bilan o'lchanadi.

Ular zarur bo'lgan xotira miqdori bilan belgilanadigan hajmiy murakkablik haqida gapirishadi.

Kompyuterlarning xotirasi cheklangan. Agar ikkita dastur bir xil funksiyalarni bajaradigan bo'lsa, unda kamroq xotira ishlatadigan dastur ko'proq hajmiy samaradorlikka ega. Ba'zida dasturlarning samaradorligini baholashda xotira yetakchi omilga aylanadi. Biroq so'nggi yillarda narxning tez pasayishi tufayli samaradorlikning ushbu komponenti asta-sekin o'z ahamiyatini yo'qotmoqda.

Algoritmning intellektual murakkabligini tahlil qilishda algoritmlarning tushunarliligi va ularni ishlab chiqish murakkabligi tekshiriladi.

Quicksort algoritmi qo'shilish tartibiga qaraganda ancha murakkab. Agar siz yuzlab odamlardan ob'ektlar ketma-ketligini saralashni so'rasangiz, ehtimol ularning aksariyati namunalarni saralash algoritmidan foydalanadi. Bundan tashqari, ularning ikkalasi ham tezkor kortortidan foydalanishi ehtimoldan yiroq emas. Tezkor saralashning intellektual va fazoviy murakkabligining sabablari aniq: algoritm rekursiv, uni ta'riflash juda qiyin, algoritm sodda tartiblash algoritmlariga qaraganda uzoqroq (dastur matni degan ma'noni anglatadi).

Murakkablikning uchta shakli ham bir-biriga bog'liqdir. Odatda, vaqtinchalik murakkablikni taxmin qiladigan algoritmni loyihalashtirish uning fazoviy va / yoki intellektual murakkabligini qurbon qilishi kerak. Muammoni tezda hal qilish mumkin, katta hajmdagi xotira yordamida yoki sekinroq, kam joydan foydalaniladi. Bu holatda odatiy misol eng qisqa yo'l qidirish algoritmidir. Shaharning jazolanishini tarmoq sifatida ifodalash orqali algoritm yozilib, tarmoqdagi istalgan ikki nuqta orasidagi eng qisqa masofani aniqlash mumkin. Ushbu masofalarni kerak bo'lganda hisoblab chiqmaslik uchun biz barcha nuqtalar orasidagi eng qisqa masofani chiqaramiz va natijalarni jadvalda saqlaymiz. Berilgan ikkita nuqta orasidagi eng qisqa masofani bilishimiz kerak bo'lsa, biz shunchaki jadvaldan tayyor masofani bosib o'tamiz. Natija bir zumda olinadi, ammo bu juda katta hajmdagi xotirani talab qiladi. Katta shahar xaritasi o'n minglab nuqtalarni o'z ichiga olishi mumkin. Keyin yuqorida tavsiflangan jadvalda 10 milliarddan ortiq hujayralar bo'lishi kerak. O'sha. algoritmning ish faoliyatini yaxshilash uchun qo'shimcha 10 Gb xotiradan foydalanish kerak. Ushbu aloqadan hajm-vaqt murakkabligi g'oyasi paydo bo'ladi. Ushbu yondashuv bilan algoritm bajarish tezligi bo'yicha ham, sarflangan xotira bo'yicha ham baholanadi.