Calcolo complessità algoritmo

[Black27]

Buongiorno! Sto cercando di calcolare per sostituzione il limite superiore di un algoritmo, ma non ci riesco...Sia con i teoremi che con l'albero di ricorsione sono arrivato alla soluzione che il limite è $O(n^(log_2 3))$, ma per sostituzione non riesco a dimostrarlo...Qualcuno mi può aiutare?
L'algoritmo è $ T(n) = 3T(n/2) + n$
Grazie mille

P.S. l'algoritmo in questione non è altro che Karatsuba

[hamming_burst]

Ciao black, ti dai all'algoritmica

Allora vediamo...
ipotizziamo che ad $n=1$ sia complessità costante $O(1)$.

$T(n) = {(O(1) if n=1),(3T(n/2) + n \ other):}$

Guess: $T(n) in O(n^{\log_{2}(3)})$
Proof: $\exists c > 0,\ m >= 0\ :\ T(n) <= cn^{\log_{2}(3)},\ \forall n >= m$

[*:3k0eipjx]caso base: banalmente vero.
[/*:m:3k0eipjx]
[*:3k0eipjx]Ipotesi induttiva: $\forall m < n ^^ c>0\ :\ T(m) <= cm^{\log_{2}(3)}$ [/*:m:3k0eipjx]
[*:3k0eipjx]Passo induttivo:

\[T(n) = 3T(\frac{n}2) + n\]
\[\text{sostituzione dell’ipotesi induttiva}\]
\[\leq 3c(\frac{n}2)^{\log_{2}(3)} + n = \frac{3}{3^{\log_{2}(2)}}cn^{\log_{2}(3)} + n \]
\[= cn^{\log_{2}(3)} + n \nleq cn^{\log_{2}(3)}\][/*:m:3k0eipjx][/list:u:3k0eipjx]

la disuguaglianza è falsa. Perciò che si fa? Sappiamo che la complessità è corretta (ho ricalcolato la complessità della ricorrenza per sicurezza), ma l'ipotesi è sbagliata. Abbiamo un $n$ di grandezza polinomialmente inforiore che preclude la correttezza, basta toglierlo di mezzo cambiando l'ipotesi da dimostrare: $T(n) in O(n^{\log_{2}(3)} - n)$

prova a fare la dimostrazione così, vedrai la magia. Se avrai problemi basta postare

[Black27]

Ciao eh si, mi dò all'algoritmica causa forze maggiori

Innanzitutto grazie della risposta, ho provato ad applicare il nuovo limite superiore ma il risultato mi viene $c <= -1/2$. Però ho notato che se sostituisco $O(n^(log_2(3)) - 2n)$ viene tutto corretto, con $c>=0$. Può andare bene lo stesso? Ti posto i passaggi del secondo caso (così mi dici se ho sbagliato qualcosa)

$3T(n/2) + n$

$<= 3 c (n/2)^(log_2(3)) - (2n/2) + n$

$= 3 c ( (n^(log_2(3)))/(3^(log_2(2))) ) - n + n$

$= c n^(log_2(3)) <= cn^(log_2(3)) - cn$

$cn <= 0$

$c >= 0$

Ma quindi in questo caso la complessità sarà sempre $O(n^(log_2(3)))$ oppure è $O(n^(log_2(3)) - 2n)$ ? La prima giusto? Visto che in teoria bisogna tenere solo l'esponente di grado massimo del polinomio (?)

[hamming_burst]

secondo la tua dimostrazione questo dovrebbe essere l'ultimo passo induttivo:

$= c n^(log_2(3)) <= cn^(log_2(3)) - cn$

mi pare di non vedere che la disuguaglianza sia basata sull'ipotesi modificata ma su quella precedente.
Per essere valida dovrebbero comparire tutte le componenti in entrambe le parti es.
$c n^(log_{2}(3)) - cn + n <= cn^(log_{2}(3)) - cn$
ma è cmq sbagliato perchè le due costanti dovrebbero essere differenti.

Vediamo di sistemare.
Vogliamo dimostrare che $T(n) in O(n^{\log_{2}(3)} - n)$

proviamo che \(T(n) \leq c(n^{\log_{2}(3)} - n)\) il passaggio successivo è fondamentale, dobbiamo dividere la costante per entrambe le componenti perciò due sottocostanti $>0$ dove diventerà: \(T(n) \leq c'n^{\log_{2}(3)} - c''n\)

sotto utilizzo $c=c'$ e $d=c''$ così per semplicità, ma è più corretto utilizzare la notazione con apice.

\[T(n) \leq 3c(\frac{n}2)^{\log_{2}(3)} - 3d\frac{n}2 + n= cn^{\log_{2}(3)} - \frac{3}2dn +n =cn^{\log_{2}(3)} - dn - \frac{1}2dn + n\]
\[= cn^{\log_{2}(3)} - dn - \frac{1}2dn + n \leq cn^{\log_{2}(3)} - dn\ \Longrightarrow \ - \frac{1}2dn + n \leq 0\]
\(- \frac{1}2dn + n \leq 0\)
\(d \geq 2\)

Perciò la disequazione è vera quando $d>=2 ^^ c>0$.

"Black27":Ma quindi in questo caso la complessità sarà sempre O(nlog2(3)) oppure è O(nlog2(3)−2n) ? La prima giusto? Visto che in teoria bisogna tenere solo l'esponente di grado massimo del polinomio (?)

$O(n^{log_2(3)) - n) in O(n^{log_2(3)})$ tutto il ragionamento di dimostrazione e per la risposta alla tua domanda, si basa su questa appartenenza, ricordati che sono insiemi o classi di complessità.

PS: se ti servono esercizi svolti sulle ricorrenze prova a cercare nella sezione, ne sono state dimostrate con tutti i passaggi molte volte.
Ti propongo due discussioni interessanti sulle tecniche di risoluzione, che penso ti posson esser utili:
- Discussione su un po' tecniche e risoluzione di una ricorrenza con più metodi: risoluzione-equazioni-di-ricorrenza-t87993.html
- Discussione sul metodo dell'albero e l'applicazione ad alcune ricorrenze particolari: ricorrenze-e-notazioni-asintotiche-t87686.html

[Black27]

Ho letto tutto con attenzione e ora mi è chiaro ti ringrazio tanto!
Adesso mi guardo i link che mi hai messo...Grazie ancora