Algoritmlarni loyihalash”

Logarifmik og'irlik mezoni bilan sig'im murakkabligi

Bunday holda, xotira hujayrasida bo'lishi mumkin bo'lgan maksimal qiymatni ko'rib chiqing. Agar qiymat aniqlanmasa (masalan, operand i> 10 bilan), u

holda V _maksimal qiymatining chegarasi bor deb hisoblanadi .

Ushbu muammoda qiymati n (i) dan oshmaydigan o'zgaruvchi va qiymati n dan oshmaydigan o'zgaruvchi mavjud ! (natija) . Shunday qilib, bal O (log (n!)) .

Algoritmlarning murakkabligini o'rganish juda qiziqarli vazifadir. Hozirgi vaqtda eng oddiy algoritmlarning tahlili IT sohasidagi informatika va amaliy matematikaga jalb qilingan texnik mutaxassisliklar o'quv dasturiga kiritilgan (aniqrog'i "Informatika va kompyuter injiniringi" yo'nalishi).

Murakkablikka qarab, har xil vazifalar sinflari ajralib chiqadi: P , NP , NPC . Ammo bu endi algoritmlarni asimptotik tahlil qilish nazariyasi muammosi emas.

lgoritmlarning resurs samaradorligini baholash usullari

Asosiy algoritmik konstruktsiyalar protsessual dasturlash quyidagilardan iborat:dallanma va pastadir. Belgilangan kirish o'lchamiga ega bo'lgan eng yaxshi, o'rta va eng yomon holatlar uchun murakkablik funktsiyalarini olish uchun asosiy algoritmik dizaynlarni baholashda farqlarni hisobga olish kerak.

1. 
   "Quyidagi" dizaynning murakkabligi - bloklarning ketma-ket ketma-ketlikdagi yig'indisi: f = f ₁ + f ₂ + ... + f _n .
   
2. 
   "Dallanma" dizaynining murakkabligi orqali aniqlanadishart bilan belgilanadigan har bir ko'rsatmalarga o'tish ehtimoli . Bundan tashqari, holatni tekshirish ham ma'lum bir murakkablikka ega. Eng yomon holatlarning murakkabligini hisoblash uchun, yanada
   

murakkabroq bo'lgan dallanma birligi tanlanishi mumkin, eng yaxshi holatda esa, pastki darajasi murakkabroq bo'lgan blok. f _agar = f ₁ + f _keyin xp _keyin + f _yana x (1-p _keyin )

3. 
   "Tsikl" dizaynining murakkabligi tsikl turiga bog'liq. Parametrlari bo'lgan tsikl uchun quyidagi formula adolatli bo'ladi: f _uchun = 1 + 3n + nf , bu erda n - takrorlash soni.tana aylanishi , f - murakkabliktana aylanishi .
   

Amalga oshirish shartli va bilan tsiklpostkondensiya uning murakkabligini baholash uslubini o'zgartirmaydi. Har bir o'tish joyida vaziyatning murakkabligi, parametrlarning o'zgarishi (agar mavjud bo'lsa) vatana aylanishi . Shartli tsikllarni baholash bo'yicha umumiy ko'rsatmalar qiyin. Ular ko'p jihatdan dastlabki ma'lumotlarga bog'liq.

4. 
   Foydalanish holatida ularning murakkabliklari ichiga kiritilgan tsikllar ko'paytiriladi. Shunday qilib, algoritmning murakkabligini baholash uchun funktsiyaning murakkabligini olishning umumiy usulini shakllantirish mumkin.
   
   1. 
      Algoritmning parchalanishi algoritmda asosiy tuzilmalarni ajratish va ularning murakkabligini baholashni o'z ichiga oladi. Bunday holda, quyidagi asosiy algoritmik inshootlar ko'rib chiqiladi.
      
   2. 
      Tilning asosiy operatsiyalarining murakkabligini bosqichma-bosqich tahlil qilish yoki umumiy tahlilni (barcha operatsiyalarni hisobga olish) yoki operatsion tahlilni (har bir operatsiyaning murakkabligini hisobga olish) talab qiladi.
      
   3. 
      Fikr-mulohaza eng yaxshi, o'rta va yomon holatlar uchun asosiy algoritmik konstruktsiyalarni tahlil qilish metodologiyasi asosida mehnatni talab qiladigan funktsiyaning tarkibi .
      

Rekursiv algoritmlarning resurs samaradorligini baholashning o'ziga xos xususiyati xotiraning qo'shimcha xarajatlari va rekursionni tashkil qilish mexanizmini hisobga olish zarurati hisoblanadi. Shu sababli, algoritmlarni rekursiv amalga oshirishning murakkabligi bitta rekursiv qo'ng'iroq paytida bajarilgan operatsiyalar soniga, shuningdek, bunday qo'ng'iroqlar soniga bog'liq. Shuningdek, hisobga olinganqiymatlarni qaytarish va boshqaruvni raqamli ulanish tizimiga

o'tkazish xarajatlari . Rekursiv chaqiriqni qaytarish mexanizmining murakkabligini tahlil qilish uchun quyidagi parametrlarni hisobga olamiz: p - uzatiladiganlar sonihaqiqiy parametrlar , r - zaxirada saqlanadigan registrlar soni, k - manzil havolasi orqali qaytarilgan qiymatlar soni, l - mahalliy funktsiyalar hujayralarining

soni. Keyinbitta qo'ng'iroqni qaytarishda murakkablik funktsiyasi quyidagi shaklni oladi:

f = 2 (p + k + r + l + 1),

qo'shimcha qaerda birlik hisobga olinadiQaytish manzili bilan operatsiyalar .

Kerakli stek xotirasining bahosini quyidagicha olish mumkin: rekursiv qo'ng'iroqlar ketma-ket ishlov berilganligi sababli, ma'lum bir vaqtning o'zida steksiyada rekursion daraxtning bo'lagi saqlanmaydi, balki rekursiv qo'ng'iroqlar zanjiri - daraxtning notekis bo'lagi. Shuning uchun, stack hajmi bir vaqtning o'zida qabul qilinadigan rekursiv qo'ng'iroqlar mumkin bo'lgan maksimal soniga qarab belgilanadi.

Rekursiv algoritmning umumiy murakkabligini tahlil qilish asosiy operatsiyalarning umumiy miqdorini shakllantirishga qarab turli xil usullar bilan amalga oshirilishi

mumkin: rekursiv qo'ng'iroqlar va qaytishlar zanjiri bo'ylab, rekursiv daraxtning uchlari bo'ylab.

1. 
   misol . Funktsiyaning vaqt murakkabligini baholashpufakchalarni saralash .
   

// Saralash funktsiyasini qabariq usuli bilan tavsiflash bo'shliq BubbleSort (int k, int x [max]) {

int i, j, buf;

uchun (i = k-1; i> 0; i--) uchun (j = 0; j x [j + 1]) { buf = x [j];

x [j] = x [j + 1]; x [j + 1] = buf;

}
}

Vaqtning murakkabligini baholang eng yomon holatda qabariqni tartiblash , ya'ni. boshlang'ich ma'lumotlar teskari tartibda tartiblanganda. Bunday holda, har

bir i uchun ichki pastadir i-1 marta bajariladi va almashinuvlar bo'ladi. Shunga ko'ra, eng yomon holatda algoritmning murakkabligi O (k ² ) almashinuvidir.

Algoritmning vaqt murakkabligini baholang pufakchani o'rta harflarda saralash , ya'ni. boshlang'ich ma'lumotlar tasodifiy tartibda bo'lganda. Bunday holda, ichki

pastadirdagi shart 1,2, ..., i-1 marta bajarilishi mumkin . Qo'shish, biz olamiz va shunga mos ravishda har bir i uchun ichki tsiklning sharti o'rtacha bir

marta bajariladi va almashinuvlar sodir bo'ladi . Shunga ko'ra, algoritmning o'rtacha holati O (k ² ) ga teng .

2. 
   misol . Hisoblash funktsiyasining vaqt murakkabligini baholash binom koeffitsienti .
   

// Binomial koeffitsientni hisoblash funktsiyasining tavsifi

int Binom (int n, int m) {

if (m == 0) return 1; // rekursion asos

qaytish Binomial (n-1, m-1) * n / m; // parchalanish

}

Biz funktsiyaning vaqtincha murakkabligini eng yomon holatda baholaymiz, ya'ni. qachon m = n . U bajariladi ( n + 1 )Vazifaga qo'ng'iroqlar amalga oshirish

etadi n hollarda uchoperatsiyalar , va birida qaytadiqiymati .Funktsiya har bir qo'ng'iroq paytida ikkita parametrni uzatadi, mahalliy parametrlardan foydalanmaydi va u ( n + 1 ) marta qaytib , boshqaruvni chaqiruv punktiga o'tkazadi. Shunga ko'ra, eng yomon holatda algoritmning murakkabligi O (n) yoki O (m) dir .

Biz funktsiyaning vaqt murakkabligini o'rtacha holatda baholaymiz, ya'ni. qachon m

Eng yaxshi holatga m = 0, yagona bo'lganida erishiladi funktsiyani chaqirish, ikkita parametrdan o'tib, qo'ng'iroq nuqtasiga qaytish, ya'ni O (1) holatini baholash .