Dimostrazione complessità
Buongiorno a tutti!
Mi trovo in difficoltà su un esercizio in riferimento alla complessità di un algoritmo di tipo Las Vegas che campiona casualmente i vincoli e calcola il valore ottimo (LVIncrementalLP(V), programmazione lineare).
Devo dimostrare, applicando il metodo di sostituzione, che per un opportuna costante b,
$ T(n,d)<= T(n-1,d) + O(d)+ d/n(O(dn)+T(n-1,d-1)) $
è risolta da
$ T(n,d)<= bnd! $
Ovvero che la complessità è, per una costante b, lineare in n e fattoriale in d.
Non dev'essere difficile dimostrarlo, ma non saprei come fare!
Mi trovo in difficoltà su un esercizio in riferimento alla complessità di un algoritmo di tipo Las Vegas che campiona casualmente i vincoli e calcola il valore ottimo (LVIncrementalLP(V), programmazione lineare).
Devo dimostrare, applicando il metodo di sostituzione, che per un opportuna costante b,
$ T(n,d)<= T(n-1,d) + O(d)+ d/n(O(dn)+T(n-1,d-1)) $
è risolta da
$ T(n,d)<= bnd! $
Ovvero che la complessità è, per una costante b, lineare in n e fattoriale in d.
Non dev'essere difficile dimostrarlo, ma non saprei come fare!
Risposte
Spero di non aver sbagliato sezione... Nel caso spostate pure 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo