Calcolare la complessita' con constante c

[jack012]

Come dovrei iniziare a risolvere questa ricorrenza:

$ T(n) = T(n-c) + T(c) + n^2 $ ?

$ T(c) $ e' una costante, e quindi non importa. Cosa dovrei fare con $ T(n-c) $ ?

[vict85]

Di fatto se \(m = \lceil n/c \rceil \) allora \(T(cm) = S(m) = S(m-1) + S(1) + c^2m^2 \). Comincia con il calcolare \(S(m) \).

[jack012]

Non capisco, potresti spiegare in un'altro modo? Grazie.

[hamming_burst]

ti ha solo riscritto la ricorrenza con una sostituzione di variabili.

[vict85]

"vict85":Di fatto se \(m = \lceil n/c \rceil \) allora \(T(cm) = S(m) = S(m-1) + S(1) + c^2m^2 \). Comincia con il calcolare \(S(m) \).

Sopponendo che \(S(1) = c^2 \) e \(S(0) = k \) per qualche costante \(k \) (le condizioni iniziali non sono segnalate), si ha che:

\begin{align} S(m) &= S(0) + mS(1) + c^2\sum_{i=1}^{m} i^2 \\
&= k + c(cm) + c^2\frac{2m^3 + 3m^2 + m}{6} \\
&= k + c(cm) + \frac{2}{6c} (cm)^3 + \frac36 (cm)^2 + \frac{c}{6}(cm) \\
&= \frac{2}{6c} n^3 + \frac36 n^2 + \frac{7}{6}c n + k\\
\end{align}

Ora non ti manca che mostrare che \(S(m-1)

Cita

Segnala