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

Faktorialni hisoblashda murakkablikni baholashga misol

Faktorialni hisoblash algoritmining murakkabligini tahlil qilish kerak. Buning uchun ushbu muammoni C tilining psevdokodiga yozing:

Void main () (int natija \u003d 1; int i; const n \u003d ...; uchun (i \u003d 2; i<= n; i++) result = result * n; }

Bir xil ogʻirlikdagi vaqtning murakkabligi

Berilgan muammoning kirish kattaligi ekanligini aniqlash oson n.
Bosqichlar soni - (n - 1).

Shunday qilib, MER uchun vaqtning murakkabligi O (n).

Logaritmik tortish testi bilan vaqt murakkabligi

Shu nuqtada siz baholanishi kerak boʻlgan operatsiyalarni taʻkidlashingiz kerak. Birinchidan, bu taqqoslash operatsiyalari. Ikkinchidan, oʻzgaruvchini oʻzgartirish operatsiyalari (qoʻshish, koʻpaytirish). Topshiriqlar hisobga olinmaydi, chunki ular darhol amalga oshishi kerak.

Shunday qilib, ushbu vazifada uchta operatsiya ajratilgan:

1) men<= n

I-bosqichda biz olamiz log (n).
Qadamlardan beri (n-1), ushbu operatsiyaning murakkabligi boʻladi (n-1) * log (n).

2) i \u003d i + 1

I-bosqichda biz olamiz jurnal (i).
.

3) natija \u003d natija * i

I-bosqichda biz olamiz jurnal ((i-1)!).
Shunday qilib, summa olinadi  .

Agar biz barcha olingan qiymatlarni qoʻshsak va ortib borishi bilan sekin oʻsadigan atamalarni bekor qilsak n, biz yakuniy ifodani olamiz  .

Bir xil vazn mezoniga ega boʻlgan sigʻimning murakkabligi

Bu erda hamma narsa oddiy. Oʻzgaruvchilar sonini hisoblashingiz kerak. Agar topshiriq massivlardan foydalansa, massivning har bir katagi oʻzgarmaydigan hisoblanadi. Oʻzgaruvchilar soni kirish hajmiga bogʻliq boʻlmaganligi sababli, murakkablik boʻladi O (1).

Logaritmik tortish testi bilan sigʻimning murakkabligi

Bunday holda, siz xotira katakchasida boʻlishi mumkin boʻlgan maksimal qiymatni hisobga olishingiz kerak. Agar qiymat aniqlanmagan boʻlsa (masalan, i\u003e 10 operand bilan), unda baʻzi bir chegara qiymati mavjud deb hisoblanadi V max. Ushbu muammoda qiymati oshmaydigan oʻzgaruvchi mavjud n (i), va qiymati oshmaydigan oʻzgaruvchi n! (natija)... Shunday qilib, taxmin O (log (n!)).