[Algoritmi] Ricorrenza con componente non ricorsiva fratta
Salve a tutti, mi sono bloccato durante lo svolgimento della seguente ricorrenza.
\begin{equation} \nonumber
T(n)=\begin{cases}
T(n-1)+\frac{2}{n} & \text{$n\geq 2$}.\\
O(1) & \text{$n < 2$}.
\end{cases}
\end{equation}
Iterando ottengo
\begin{align*}
T(n) & = T(n-1) + \frac{2}{n} \\
& = T(n-2) + \frac{2}{n} + \frac{2}{n-1} \\
& = T(n-3) + \frac{2}{n} + \frac{2}{n-1} + \frac{2}{n-2}\\
& = \dots \\
& = T(n-i) + \sum_{k=0}^{i-1} \frac{2}{n-k} \text{, con } n - i = 1 \text{, quindi } i = n - 1\\
\\
T(n) & = \sum_{k=0}^{n-2} \frac{2}{n-k}
\end{align*}
Arrivato davanti a questa sommatoria non riesco ad andare avanti, innanzitutto mi chiedo se ci sono dei passaggi che ho sbagliato, altrimenti come posso risolvere?
Nel materiale didattico del mio docente c'è questa serie armonica che viene trasformata nel modo seguente
\[ \sum_{k=1}^{n} \frac{1}{k} = \ln n + O(1)\]
ma nel mio caso non so come trattare il denominatore $n-k$ della funzione.
Grazie a tutti!
\begin{equation} \nonumber
T(n)=\begin{cases}
T(n-1)+\frac{2}{n} & \text{$n\geq 2$}.\\
O(1) & \text{$n < 2$}.
\end{cases}
\end{equation}
Iterando ottengo
\begin{align*}
T(n) & = T(n-1) + \frac{2}{n} \\
& = T(n-2) + \frac{2}{n} + \frac{2}{n-1} \\
& = T(n-3) + \frac{2}{n} + \frac{2}{n-1} + \frac{2}{n-2}\\
& = \dots \\
& = T(n-i) + \sum_{k=0}^{i-1} \frac{2}{n-k} \text{, con } n - i = 1 \text{, quindi } i = n - 1\\
\\
T(n) & = \sum_{k=0}^{n-2} \frac{2}{n-k}
\end{align*}
Arrivato davanti a questa sommatoria non riesco ad andare avanti, innanzitutto mi chiedo se ci sono dei passaggi che ho sbagliato, altrimenti come posso risolvere?
Nel materiale didattico del mio docente c'è questa serie armonica che viene trasformata nel modo seguente
\[ \sum_{k=1}^{n} \frac{1}{k} = \ln n + O(1)\]
ma nel mio caso non so come trattare il denominatore $n-k$ della funzione.
Grazie a tutti!
Risposte
$ \sum_{k=0}^{n-2} \frac{1}{n-k} = \frac{1}{n} + \ldots + \frac{1}{2} = \sum_{k=2}^{n} \frac{1}{k} $ 
Ciao!
Ciao!
"probid":
$ \sum_{k=0}^{n-2} \frac{1}{n-k} = \frac{1}{n} + \ldots + \frac{1}{2} = \sum_{k=2}^{n} \frac{1}{k} $
Ciao!
Ti ringrazio per la risposta!
Dunque ricapitolando, la soluzione della ricorrenza dovrebbe essere così, giusto?
\[ T(n) = \sum_{k=0}^{n-2} \frac{2}{n-k} = \frac{1}{n} + \ldots + \frac{1}{2} = \sum_{k=2}^{n} \frac{1}{k} = \ln n + O(1) = O(\log n)\]
Attendo conferme e/o correzioni, grazie ancora!
"Leyxargon":
$ \sum_{k=0}^{n-2} \frac{2}{n-k} = \frac{1}{n} + \ldots + \frac{1}{2} $
Il 2 non è che scompare, lo porti fuori per la proprietà distributiva delle sommatorie e quindi moltiplica le somme dopo.
Poi essendo una costante non cambia nulla in termini di complessità (potresti anche mettere tutto in $O()$ e non curartene affatto...), ma l'uguaglianza così com'è scritta non vale.
Ciao!
"probid":
[quote="Leyxargon"]$ \sum_{k=0}^{n-2} \frac{2}{n-k} = \frac{1}{n} + \ldots + \frac{1}{2} $
Il 2 non è che scompare, lo porti fuori per la proprietà distributiva delle sommatorie e quindi moltiplica le somme dopo.
Poi essendo una costante non cambia nulla in termini di complessità (potresti anche mettere tutto in $O()$ e non curartene affatto...), ma l'uguaglianza così com'è scritta non vale.
Ciao![/quote]
Ok, capito. Senza dilungarmi in ulteriori dettagli, semplicemente affermo che $T(n) = \sum_{k=0}^{n-2} \frac{2}{n-k} = \frac{1}{n} + \ldots + \frac{1}{2} = \sum_{k=2}^{n} \frac{1}{k} = O(\log n)$
Ti ringrazio!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo