Limite superiore equazione di ricorrenza strana
Ciao a tutti, vorrei chiedervi consiglio su questa ricorrenza lineare che a me sembra strana e cerchero' di spiegare il perchè:
$T(n)=\{(min_(1<=k<=n-1){T[k]+T(n-k)}+1, if n>1), (1, if n<=1):}$
Io non so come affrontare il termine $T[k]$. E come affronto il $min_(1<=k<=n-1)$? Non ho mai incontrato un esercizio di questo tipo e veramente... boh.
Avevo pensato che $T[k]$ sia il contributo fisso al passaggio $k-\text{esimo}$ della $T$ e quindi $=1$.
Invece per quell oche riguarda la gestione del $min_(1<=k<=n-1)$: se devo prendere il minimo, sarebbe stato:
per $n=2$
$T(n)=min_(1<=k<=2-1) {T[1]+ T(2-1)} + 1 = 2 = min_(1<=k<=2-1) {1+1)} + 1=3$ quindi sarebbe $O(n)$ ??
Non so ragazzi, è molto campata in aria. Mi potete dare qualche consiglio?
$T(n)=\{(min_(1<=k<=n-1){T[k]+T(n-k)}+1, if n>1), (1, if n<=1):}$
Io non so come affrontare il termine $T[k]$. E come affronto il $min_(1<=k<=n-1)$? Non ho mai incontrato un esercizio di questo tipo e veramente... boh.
Avevo pensato che $T[k]$ sia il contributo fisso al passaggio $k-\text{esimo}$ della $T$ e quindi $=1$.
Invece per quell oche riguarda la gestione del $min_(1<=k<=n-1)$: se devo prendere il minimo, sarebbe stato:
per $n=2$
$T(n)=min_(1<=k<=2-1) {T[1]+ T(2-1)} + 1 = 2 = min_(1<=k<=2-1) {1+1)} + 1=3$ quindi sarebbe $O(n)$ ??
Non so ragazzi, è molto campata in aria. Mi potete dare qualche consiglio?
Risposte
Non sono molto pratico con le equazioni di ricorrenza, ma direi che
\[ T(n) = \min_{1\le k \le n-1} \bigl[ T(k) + T(n-k) \bigr] +1 \le T(1) + T(n-1) + 1 = T(n-1)+2 \]
Ovvero \(\displaystyle T(n) \le 2(n-1)+1 = 2n-1 \).
Mi chiedo se sia una uguaglianza. Insomma:
\(\displaystyle T(1) = 1 \)
\(\displaystyle T(2) = 3 \) (il minimo viene fatto su un solo valore).
\(\displaystyle T(3) = \min\bigl( T(1) + T(2), T(2) + T(1)\bigr) + 1 = T(2) + 2 = 5 \) (nel futuro evito di ripetere termini)
\(\displaystyle T(4) = \min\bigl\{ T(1)+T(3), 2T(2) \bigr\} + 1 = \min\bigl\{ 6, 6 \bigr\} + 1 = 7\)
\(\displaystyle T(5) = \min\bigl\{ T(1)+T(4), T(2) + T(3) \bigr\} + 1 = \min\bigl\{ 8, 8 \bigr\} + 1 = 9\)
Si potrebbe provare a dimostrare usando l'induzione forte.
Caso base: vale per \(\displaystyle T(1) \)
Ipotesi induttiva: supponiamo che \(\displaystyle T(i) = T(i)+2 \) per ogni \(\displaystyle 1 \ge i < N \). Dimostriamo che \(\displaystyle T(N) = T(N-1) + 2 \).
dimostrazione passaggio induttivo: \(\displaystyle T(N) = \min\bigl[ T(k) + T(N-k) \bigr] + 1\) ma \(\displaystyle T(k) + T(N-k) = T(k+1) - 2 + T(N-k-1) + 2 = T(k-1) + T(N-k+1) \). Procedendo induttivamente su \(\displaystyle k \) risulta che si sta facendo il \(\displaystyle min \) su valori tutti uguali. Quindi \(\displaystyle T(N) = T(1) + T(N-1) + 1 = T(N-1)+1\).
\[ T(n) = \min_{1\le k \le n-1} \bigl[ T(k) + T(n-k) \bigr] +1 \le T(1) + T(n-1) + 1 = T(n-1)+2 \]
Ovvero \(\displaystyle T(n) \le 2(n-1)+1 = 2n-1 \).
Mi chiedo se sia una uguaglianza. Insomma:
\(\displaystyle T(1) = 1 \)
\(\displaystyle T(2) = 3 \) (il minimo viene fatto su un solo valore).
\(\displaystyle T(3) = \min\bigl( T(1) + T(2), T(2) + T(1)\bigr) + 1 = T(2) + 2 = 5 \) (nel futuro evito di ripetere termini)
\(\displaystyle T(4) = \min\bigl\{ T(1)+T(3), 2T(2) \bigr\} + 1 = \min\bigl\{ 6, 6 \bigr\} + 1 = 7\)
\(\displaystyle T(5) = \min\bigl\{ T(1)+T(4), T(2) + T(3) \bigr\} + 1 = \min\bigl\{ 8, 8 \bigr\} + 1 = 9\)
Si potrebbe provare a dimostrare usando l'induzione forte.
Caso base: vale per \(\displaystyle T(1) \)
Ipotesi induttiva: supponiamo che \(\displaystyle T(i) = T(i)+2 \) per ogni \(\displaystyle 1 \ge i < N \). Dimostriamo che \(\displaystyle T(N) = T(N-1) + 2 \).
dimostrazione passaggio induttivo: \(\displaystyle T(N) = \min\bigl[ T(k) + T(N-k) \bigr] + 1\) ma \(\displaystyle T(k) + T(N-k) = T(k+1) - 2 + T(N-k-1) + 2 = T(k-1) + T(N-k+1) \). Procedendo induttivamente su \(\displaystyle k \) risulta che si sta facendo il \(\displaystyle min \) su valori tutti uguali. Quindi \(\displaystyle T(N) = T(1) + T(N-1) + 1 = T(N-1)+1\).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo