čo bude časová zložitosť vzťahu T (n) = nT (n-1) + n - c, algoritmus, časová zložitosť

ČO bude časová zložitosť vzťahu T (n) = nT (n-1) + n v mojom prog niečo také

f(int n)
{
c++;
if(n>0)
for(i=1;i<=n;i++)
f(n-1);
}

Počítal som, koľko časových funkcií sa volá dáva odpoveď medzi n a n! Vďaka.

odpovede:

-1 pre odpoveď č. 1

Môžeme uviesť niekoľko pojmov

T(0) = 0
T(1) = 1 * 0 + 1
T(2) = 2 * 1 + 2 = 4
T(3) = 3 * 4 + 3 = 15
T(4) = 4 * 15 + 4 = 64
...

Môžeme si všimnúť pár vecí. Po prvé, funkcia rastie rýchlejšie ako n !; začína to menšie ako to (pri n = 0), doháňa (pri n = 1) a prevyšuje ho (pri n> = 2). Takže vieme, že dolná hranica je n !.

Teraz potrebujeme hornú hranicu. Môžeme si všimnúť jednu vec: T (n) = nT (n-1) + n <nT (n-1) + nT (n-1) pre všetky dostatočne veľké n (n> = 2, myslím). Môžeme však ľahko ukázať, že T (n) = nT (n-1) je opakujúci sa vzťah pre n !, takže vieme, že opakujúci sa vzťah pre T (n) = nT (n-1) + nT (n-1) ) = 2nT (n-1) je (n!) (2 ^ n). Môžeme robiť lepšie?

Navrhujem, že môžeme. Môžeme ukázať, že pre ľubovoľné c> 0, T (n) = nT (n-1) + n <nT (n-1) + cnT (n-1) pre dostatočne veľké hodnoty n. Už vieme, že T (n-1) je ohraničené nižšie (n-1) !; takže, ak vezmeme c = n / (n-1)! obnovíme presne náš výraz a vieme, že horná hranica je (c ^ n) (n!). Aký je limit c, keď n ide do nekonečna? 0. Aká je maximálna hodnota predpokladaná do [n / (n-1)!] ^ N?

Veľa šťastia pri výpočte. Wolfram Alpha jasne ukazuje, že maximálna hodnota predpokladaná touto funkciou je okolo 5 alebo 6 pre n ~ 2,5. Za predpokladu, že ste tým presvedčení, čo je to so sebou?

n! <T (n) <~ 6n! pre všetky n. n! je Theta-viazaný pre váš opakovanie.

---

1 pre odpoveď č. 2

Vášmu kódu chýba +n časť rekurzie, takže predpokladám, že kód je nesprávny a rekurzia

T(n) = n*T(n-1) + n

je správne.

nechať f(n)=T(n)/n!, potom

f(n) = T(n)/n! = n(T(n-1)+1)/n!
= T(n-1)/(n-1)! + 1/(n-1)!
= f(n-1) +  1/(n-1)!
= sum(1,n-1, 1/k!)
~ e

teda T(n) ~ e*n!.

---

-1 pre odpoveď č. 3

Funkcia sa volá

n*f(n-1)

časy. výmena f(n-1) s touto definíciou dáva

n*((n-1)*f(n-2)

Opätovná výmena dáva:

n*((n-1)*((n-2)*f(n-3)))

Odstránenie zátvoriek:

n*(n-1)*(n-2)*...(1)

To dáva:

n= 3: 3*2*1 = 6
n= 4: 4*3*2*1 = 24
n= 5: 5*4*3*2*1 = 120

ktorý je n!.

---