«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan Mustaqil ish

Taʻriflar

Algoritm murakkabligining asosiy koʻrsatkichi bu muammoni hal qilish uchun sarflanadigan vaqt va kerakli xotira hajmi.
Shuningdek, muammolar klassi uchun murakkablikni tahlil qilishda maʻlum bir maʻlumot miqdorini tavsiflovchi maʻlum bir raqam aniqlanadi - kirish kattaligi.
Shunday qilib, biz shunday xulosaga kelishimiz mumkin algoritmning murakkabligi - kirish kattaligi funktsiyasi.
Algoritmning murakkabligi bir xil kirish kattaligi uchun har xil boʻlishi mumkin, ammo har xil yozuvlar.

Inda murakkablik tushunchalari mavjud eng yomon, oʻrtachayoki eng yaxshi holat... Odatda, eng yomon holatdagi qiyinchilik taxmin qilinadi.

Vaqtning murakkabligi eng yomon holatda, berilgan kattalikdagi masalani echishda algoritm ishlashi davomida bajariladigan operatsiyalarning maksimal soniga teng boʻlgan kirish hajmining funktsiyasi.
Imkoniyatli murakkablik eng yomon holatda, kirish kattaligidagi funktsiya, maʻlum hajmdagi muammolarni echishda kiradigan xotira hujayralarining maksimal soniga teng.

Algoritmlar murakkabligining oʻsish tartibi

Murakkablikni oshirish tartibi (yoki aksiomatik murakkablik) katta kirish hajmi uchun algoritm murakkabligi funktsiyasining taxminiy xatti-harakatini tavsiflaydi. Bundan kelib chiqadiki, vaqt murakkabligini baholashda elementar amallarni koʻrib chiqishning hojati yoʻq, algoritm bosqichlarini koʻrib chiqish kifoya.

Algoritm qadam - ketma-ket joylashgan elementar operatsiyalar toʻplami, uning bajarilish vaqti kirish hajmiga bogʻliq emas, yaʻni u yuqoridan qandaydir doimiy bilan chegaralangan.