Vaqt murakkabligi
O(n)
Fibonachchi ketma-ketligi dinamik dasturlashning klassik misolidir. Har bir son o‘zidan oldingi ikkita sonning yig‘indisiga teng: F(n) = F(n-1) + F(n-2).
Qanday ishlaydi (Bottom-Up jadval usuli):
1. Hisoblangan qiymatlarni saqlash uchun jadval yaratish
2. Boshlang‘ich holatlarni belgilash: F(0) = 0, F(1) = 1
3. Jadvalni ketma-ket to‘ldirish: F(i) = F(i-1) + F(i-2)
4. F(n) qiymatini qaytarish
Vaqt murakkabligi: O(n)
Xotira murakkabligi: O(n) — O(1) gacha optimallashtirish mumkin
Taqqoslash:
- Sodda rekursiya: O(2^n) — eksponensial murakkablik
- Memoizatsiya (top-down): O(n)
- Jadval usuli (bottom-up): O(n)
Dinamik dasturlash oldin hisoblangan natijalarni saqlash orqali takroriy hisob-kitoblarning oldini oladi. Fibonachchi ketma-ketligi ushbu usulning eng sodda namunasidir.
O'xshash algoritmlar
Ko'p beriladigan savollar
- Fibonachchi (Dinamik dasturlash) nima?
- Fibonachchi ketma-ketligi dinamik dasturlashning klassik misolidir. Har bir son o‘zidan oldingi ikkita sonning yig‘indisiga teng: F(n) = F(n-1) + F(n-2).
- Fibonachchi (Dinamik dasturlash) murakkabligi qanday?
- Vaqt (o'rtacha): O(n) · Xotira: O(n)
- Ushbu Fibonachchi (Dinamik dasturlash) vizualizatori kimlar uchun?
- Fibonachchi (Dinamik dasturlash) vizualizatsiyasi "Dinamik dasturlash" kategoriyasida o'rta darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- Fibonachchi (Dinamik dasturlash) ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Dinamik dasturlash) quyidagilarni ko'rishingiz mumkin: Knapsack 0/1, Longest Common Subsequence. Har biri interaktiv vizualizatsiyaga ega.