Dubbio su metodo di sostituzione per asintotica di una ricorrenza
Premetto che non ho problemi a comprendere l'induzione, quello che faccio fatica a capire è come gestire la costante nella definizione delle notazioni asintotiche tra un \(n\) e l'altra del passo induttivo.
Faccio un esempio: vogliamo dimostrare per induzione che la seguente ricorrenza appartiene alla classe \(O(2^n)\).
Quindi parto dalla base induttiva: \(n = 1 \) e ottengo \(T(n) \leq c\cdot2^n \rightarrow \theta(1) \leq 2c \rightarrow a \leq 2c \rightarrow c \geq \frac{a}{2} : a, c \in \R \land n = 1\)
Poi il passo induttivo. Per ipotesi induttiva si ha:
\(T(n) \leq c\cdot2^n \rightarrow T(n) + \theta(2^{n+1}) \leq c\cdot2^n + \theta(2^{n+1}) \)
Da cui:
\(T(n+1) \leq c\cdot2^n + \theta(2^{n+1}) \rightarrow T(n+1) \leq c\cdot2^n + d\cdot2^{n+1} \rightarrow T(n+1) \leq (\frac{c}{2} + d)2^{n+1}\) che è proprio la definizione di theta.
Qui però mi sorge un dubbio: anche se la \(c\) deve essere uguale \(\forall n\), il fatto che se la proprietà è vera per \(T(n)\) allora è vera per \(T(n+1)\) con una costante maggiore non è un problema. Infatti con la costante trovata per \(T(n+1)\) la definizione di theta vale sia per \(T(n+1)\) che per \(T(n)\). Ma allora che \(c\) devo prendere? Se per ogni \(n\) trovo che \(T(n+1) \in O(2^n)\) con una costante maggiore, qual'è questa costante?
Spero di essermi spiegato bene. Grazie per l'aiuto.
(Ho scritto nella sezione informatica perché la domanda riguarda il calcolo della complessità asintotica di un'algoritmo ricorsivo. Spero di non aver sbagliato sezione)
Faccio un esempio: vogliamo dimostrare per induzione che la seguente ricorrenza appartiene alla classe \(O(2^n)\).
[math]T\left(n\right)=\begin{cases}\theta\left(1\right) & \text{:}\quad n=1\\ T\left(n-1\right)+\theta\left(2^{n}\right) & \text{:}\quad n>1\end{cases}[/math]
Quindi parto dalla base induttiva: \(n = 1 \) e ottengo \(T(n) \leq c\cdot2^n \rightarrow \theta(1) \leq 2c \rightarrow a \leq 2c \rightarrow c \geq \frac{a}{2} : a, c \in \R \land n = 1\)
Poi il passo induttivo. Per ipotesi induttiva si ha:
\(T(n) \leq c\cdot2^n \rightarrow T(n) + \theta(2^{n+1}) \leq c\cdot2^n + \theta(2^{n+1}) \)
Da cui:
\(T(n+1) \leq c\cdot2^n + \theta(2^{n+1}) \rightarrow T(n+1) \leq c\cdot2^n + d\cdot2^{n+1} \rightarrow T(n+1) \leq (\frac{c}{2} + d)2^{n+1}\) che è proprio la definizione di theta.
Qui però mi sorge un dubbio: anche se la \(c\) deve essere uguale \(\forall n\), il fatto che se la proprietà è vera per \(T(n)\) allora è vera per \(T(n+1)\) con una costante maggiore non è un problema. Infatti con la costante trovata per \(T(n+1)\) la definizione di theta vale sia per \(T(n+1)\) che per \(T(n)\). Ma allora che \(c\) devo prendere? Se per ogni \(n\) trovo che \(T(n+1) \in O(2^n)\) con una costante maggiore, qual'è questa costante?
Spero di essermi spiegato bene. Grazie per l'aiuto.
(Ho scritto nella sezione informatica perché la domanda riguarda il calcolo della complessità asintotica di un'algoritmo ricorsivo. Spero di non aver sbagliato sezione)
Risposte
...ma cos'è \(\theta\)?
j18eos ha scritto:
...ma cos'è \(\theta\)?
Il limite asintotico stretto definito come segue:
[math]f(x)\in\theta(g(x))\Longleftrightarrow\exists c_{1}, c_{2} > 0, n_{0}\in\mathbb{R} :0\leq c_1\cdot g\left(x\right)\leq f\left(x\right)\leq c_2^{}\cdot g\left(x\right) \forall n \geq n_0 [/math]
Non va bene che la costante sia maggiore ad ogni passo induttivo, ovvero si deve dimostrare che
Nel caso in questione poniamo che per opportuno b risulti
e posto c>b vogliamo dimostrare che per qualsiasi n risulta
E' immediato verificare che la proprietà vale per n=1 essendo
Si ha poi per ipotesi induttiva
e quindi
[math]T(n) \le c 2^n[/math]
con c fissato una volta per tutte. A questo riguardo vedi https://martinenghi.faculty.polimi.it/courses/api/2-02Algoritmi.pdfNel caso in questione poniamo che per opportuno b risulti
[math]\Theta\left(2^{n}\right)\le\frac{b}{2}2^{n}[/math]
e posto c>b vogliamo dimostrare che per qualsiasi n risulta
[math]T\left(n)\right)\le c2^n[/math]
E' immediato verificare che la proprietà vale per n=1 essendo
[math]T(1)=\Theta(1)\le\frac{b}{2}2^1=b\le c2^1[/math]
Si ha poi per ipotesi induttiva
[math]T(n-1)\le c 2^{n-1}[/math]
e quindi
[math]T(n)=T(n-1)+\Theta\left(2^{n}\right)\le c2^{n-1}+\frac{b}{2}2^{n}=[/math]
[math]=c2^{n-1}+b2^{n-1} \le c2^{n-1} + c2^{n-1} = c 2^n[/math]
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo