MUNDARIJA Kirish………………………………………………………………………… 2 1-bob. Dinamik dasturlash g’oyasi…………………………………………. 3 1.1 Yechim g‘oyasi: Rekursiv yondashuv………………………………3 1.2 Taqqoslash: Yodlash va Tabulyatsiya……………………………… 8 1.3 Dinamik dasturlash tarixi.....................................................................9 2-bob. Dinamik dasturlash va rekursiyani taqqoslash ...................................10 2.1 Rekursiya va dinamik dasturlashni kiritish ………………………….. 10 2.2 Dinamik dasturlash haqida…………………………………………..11 2.3 Rekursiya haqida ma’lumot………………………………………….1 2 Xulosa………………………………………………………………………….. 20 Foydalanilgan adabiyotlar…………………………………………………… .21 1

Kirish Ushbu blogning g'oyasi dinamik dasturlash deb ataladigan yangi algoritmni loyihalash texnikasini muhokama qilishdir. Bu kompyuter fanida muammolarni hal qilishda muhim yondashuv bo'lib, biz samaradorlikni oshirish uchun vaqt-xotira almashinuvi g'oyasidan foydalanamiz. Hatto ko'plab texnologiya kompaniyalari o'z intervyularida DP savollarini berishni yaxshi ko'radilar. Ushbu blogda biz DP bilan bog'liq quyidagi tushunchalarni o'rganamiz:  n-Fibonachchini topishning rekursiv yechimi  Vaqt xotirasi almashinuvidan foydalangan holda samaradorlikni oshirish  Yuqoridan pastga amalga oshirish (yodlash)  Pastdan yuqoriga amalga oshirish (jadval)  Taqqoslash: Yuqoridan pastga va Tabulyatsiya  Keyinchalik o'rganish uchun tanqidiy tushunchalar  Yechish uchun tavsiya etilgan muammolar  Keling, birinchi navbatda n-Fibonachchini topish muammosini muhokama qilaylik. Rekursiya - bu asosiy holatlarga erishilgunga qadar funktsiya o'zini chaqiradigan jarayon. Va jarayon davomida murakkab vaziyatlar rekursiv ravishda kuzatiladi va sodda va sodda bo'ladi. Jarayonning butun tuzilishi daraxtga o'xshaydi. Rekursiya yakuniy bosqichga etgunga qadar hech qanday qiymatni saqlamaydi (asosiy holat). Va Dinamik dasturlash asosan oddiy rekursiya bilan solishtirganda optimallashtirishdir. Asosiy g'oya - asl savolni takrorlanadigan naqshlarga ajratish va keyin natijalarni ko'p sub- javoblarni saqlash. Shuning uchun, keyin kerak bo'lganda, biz bosqichdan oldingi javoblarni qayta hisoblashimiz shart emas. Katta O nuqtai nazaridan, ushbu optimallashtirish usuli odatda vaqt murakkabligini eksponensialdan polinomga qisqartiradi. 2

1-bob. Dinamik dasturlash g’oyasi 1.1 Yechim g‘oyasi: Rekursiv yondashuv Yuqoridagi takrorlanish munosabati yordamida masalani rekursiv hal qilishimiz mumkin. Bu erda biz n o'lchamdagi masalani o'lcham (n-1) va o'lcham (n-2) kichik masala yechimi yordamida hal qilamiz, bu yerda F(0) va F(1) asosiy holatlardir . Pseudo kod: int fib (n) { if (n == 0 ) return 0 else if (n == 1 ) return 1 else return fib(n- 1 ) + fib(n- 2 ) } Murakkablik tahlili: Yuqoridagi kod birinchi qarashda oddiy ko'rinadi, lekin u haqiqatan ham samarasiz. Keling, uni tahlil qilamiz va samarasizligining sababini tushunamiz. Mana rekursiya daraxti diagrammasi: 3

Rekursiya daraxti usulida rekursiv qo'ng'iroqlarning umumiy soni = Rekursiya daraxtidagi tugunlarning umumiy soni. Xuddi shunday, agar biz rekursiya daraxtida k darajaga ega bo'lsak, u holda rekursiya bo'yicha bajariladigan operatsiyalarning umumiy soni = L1 + L2 + L3 ......Lk, bu erda har qanday Li - i-darajadagi operatsiyalarning umumiy soni. rekursiya daraxti. Agar diqqat bilan kuzatadigan bo'lsak, quyidagi narsalarni sanab o'tishimiz mumkin: Biz har bir rekursiv chaqiruvda O (1) operatsiyasini bajaramiz. Rekursiv qo'ng'iroqlarning umumiy soni eksponent ravishda o'sib bormoqda, chunki biz daraxtda pastga qarab harakatlanamiz, ya'ni 2, 4, 8, 16 ... va hokazo. Har bir barg tugunining balandligi (n/2, n) oralig'ida. Shunday qilib, rekursiya daraxtining umumiy balandligi = O(n) = cn, deb aytishimiz mumkin, bu erda c qandaydir doimiydir. (O'ylab ko'ring!) Rekursiv qo'ng'iroqlarning umumiy soni = 1 + 2 + 4 + 8 ...+ 2^cn = (2^cn - 1) / (2 - 1) (Geometrik qatorlarning yig'indisi formulasidan foydalanish) = O(2^n) Vaqt murakkabligi = O(2^n). Bu samarasiz algoritm, chunki vaqt murakkabligi kirish hajmiga (n) nisbatan eksponent ravishda o'sib bormoqda. Umuman olganda, 30 yoki 50 yoki 70 kabi kichik n qiymati uchun mahsulot ishlab chiqarish juda uzoq vaqt talab etadi. Keling, 5-Fibonachchini topish uchun rekursiya daraxti yordamida sababni o'rganamiz. 4

Ko'chirib oling, shunda to'liq holda ko'ra olasiz

O'xshashlar