Algoritmlarni loyihalash”

Faktorialni hisoblashda murakkablikni baholash misoli

Faktorialni hisoblash algoritmining murakkabligini tahlil qilish kerak. Buning uchun biz ushbu vazifani C tilining psevdokodiga yozamiz:

void main() { int result = 1; int i;

const n = ...;

for (i = 2; i <= n; i++) result = result * n;

}

Vaqtning murakkabligi yagona og'irlik mezonlari bilan

Ushbu vazifaning kirish o'lchamlari n ekanligini aniqlash kifoya qiladi . Bosqichlar soni (n - 1) .
Shunday qilib, RVC uchun vaqt murakkabligi O (n) dir .

Vaqtning murakkabligi logarifmik og'irlik mezoni bilan

Ushbu paragrafda baholanishi kerak bo'lgan operatsiyalar ko'rsatilishi kerak. Birinchidan, bu taqqoslash operatsiyalari. Ikkinchidan, o'zgaruvchan

parametrlarning ishlashi (qo'shish, ko'paytirish). Belgilanish operatsiyalari hisobga olinmaydi, chunki u darhol sodir bo'ladi deb taxmin qilinadi.
Shunday qilib, ushbu vazifada uchta operatsiya ajratiladi:
1) i <= n
I bosqichda biz log (n) ni olamiz .

Bosqichlar (n-1) bo'lganligi sababli, ushbu operatsiyaning murakkabligi (n-1) * log (n) bo'ladi .