[Generale] Costo algoritmi e strutture dati

[gaiapuffo]

Ciao ho la seguente funzione di costo(informatica algoritmi)

T(n-1)+logn (n elevato alla 2)

Se seguo Ii l master theorem, ho la formula

se a=1 allora n^b 
se a>=2 allora a^n*n^b

Allora mi ritrovo nel caso 1,ma mentre se ho T(n-1)+n hoi che beta è 1,qui ho logn e quindi non so cosa fare

[hamming_burst]

Utilizza le formule matematiche, non è la prima volta che te lo scrivo, almeno non in questa sezione.

"gaiapuffo":(n elevato alla 2)

a cosa si riferisce: è una potenza nella funzione logaritmo, è un polinomio a sè?

[gaiapuffo]

no scusa ho sbagliato a scrivere è un semplice logaritmo. Come soluzione mi da O(n*logn),ma non ho capito come ci è arrivato e che come ha applicato il master theorem

[hamming_burst]

Il master non è in nessun modo applicabile con questo tipo di ricorrenze. A te capire il perché.

"gaiapuffo":
$T(n-1)+log_2(n)$

utilizza l'albero oppure l'iterazione, ipotizzando che per $T(0) = 1$

$\log_2(n) -> \log_2(n-1) -> \log_2(n-2) -> ... -> \log_2(n-i)$
è lineare in $n$.

Finisci quando $log(n-i) = 1$ cioè quando $i = n-1$.

$\sum_{i=0}^(n-1) \log_2(n-i) = \sum_{k=1}^(n) \log_2(k) = \log_2(\prod_{k=1}^(n)k) = log_2(n!)$

$log_2(n!)$ è notoriamente esser limitato da $O(nlogn)$ (l'albero delle scelte ti dice nulla?). Ti invito a dimostrare tale fatto per induzione.

[gaiapuffo]

grazie