[Algoritmi]Svolgimento ricorrenza

[krak]

Allora, provo a dimostrare che:
\( \displaystyle T(n)=3T(\frac{n}{4})+ n \log n \leq c(n \log n) \)

Supponiamo che il costo base della ricorrenza sia: \( \displaystyle O(1) \) if \( \displaystyle n=1 \) .

Provo per \( \displaystyle n=1 \) ed ottengo:
\( \displaystyle T(1)=(\frac{3}{4})+ 1 \log 1 = (\frac{3}{4})\leq 1 \log 1 \) che è falsa!

Provo per \( \displaystyle n=2 \) ed ottengo:
\( \displaystyle T(2)=T(1)+ 2 \log 2 = (\frac{7}{2}) \leq c(2 \log 2) \) che è vera per \( \displaystyle c\geq (\frac{7}{4}) \)

Perciò possiamo dire che \( \displaystyle T(n) \) appartiene a \( \displaystyle O(n \log n) \) per qualunque \( \displaystyle n>2 \) e
\( \displaystyle c= (\frac{7}{4}) \) .

Adesso ci siamo? è corretto?

[hamming_burst]

Adesso ci siamo? è corretto?

a costo di essere stucchevole, devo dirti che c'è sempre qualcosa che non va... Cerchiamo di riordinare un po' tutto.

Provo per \( \displaystyle n=1 \) ed ottengo:
\( \displaystyle T(1)=(\frac{3}{4})+ 1 \log 1 = (\frac{3}{4})\leq 1 \log 1 \) che è falsa!

perchè \( \displaystyle \frac{{3}}{{4}} \)? a me risulta che abbiamo ipotizzato essere \( \displaystyle {1} \)...

Provo per \( \displaystyle n=2 \) ed ottengo:
\( \displaystyle T(2)=T(1)+ 2 \log 2 = (\frac{7}{2}) \leq c(2 \log 2) \) che è vera per \( \displaystyle c\geq (\frac{7}{4}) \)

\( \displaystyle \frac{{7}}{{2}} \) ma perchè?
fai così dimmi il ragionamente/sostituzione che fai...

Perciò possiamo dire che \( \displaystyle T(n) \) appartiene a \( \displaystyle O(n \log n) \) per qualunque \( \displaystyle n>2 \) e
\( \displaystyle c= (\frac{7}{4}) \) .

te hai reso "vero" il caso base, ma il passo induttivo dove sta?

Ti mostro come si inizia, è una normale dimostrazione per induzione...

\( \displaystyle {T}{\left({n}\right)}={\left\lbrace\matrix{{O}{\left({1}\right)}{\quad\text{if}\quad}{n}={1}\\{3}{T}{\left(\frac{{n}}{{4}}\right)}+{n}{\log{{n}}}\ {o}{t}{h}{e}{r}}\right.} \)

Guess: \( \displaystyle {T}{\left({n}\right)}\in{O}{\left({n}{\log{{n}}}\right)} \)
Proof: \( \displaystyle \exists{c}\gt{0},\ {m}\ge{0}\ :\ {T}{\left({n}\right)}\le{c}{n}{\log{{n}}},\ \forall{n}\ge{m} \)

• caso base: consiglio di trattarlo sempre alla fine, si evitano possibili inutili calcoli se l'ipotesi è sbagliata e dobbiamo modificarla.
• Ipotesi induttiva: \( \displaystyle \forall{m}\lt{n}\wedge{c}\gt{0}\ :\ {T}{\left({m}\right)}\le{c}{m}{\log{{m}}} \)
• Passo induttivo:
  
  \[T(n) = 3T(n/4) + nlogn\]
  \[\text{sostituzione dell’ipotesi induttiva}\]
  \[\leq 3c\frac{n}4log(\frac{n}4) + nlogn\]
  
  
  lascio continuare te
  
  
• caso base: \(T(1) = 1 \not\leq c*1log1 = 0, \forall c > 0\)
  
  lascio continuare te anche qua

[krak]

Per prima cosa ti ringrazio per la tua pazienza, mi stai aiutando a capire i miei errori!

Ci riprovo..
Devo dimostare che:
\( \displaystyle T(n)\leq 3c(\frac{n}{4})\log (\frac{n}{4})+ cn \log n \)
\( \displaystyle 3c(\frac{n}{4})\log n - 3c(\frac{n}{4})\log 4 + cn \log n \)
\( \displaystyle (\frac{7}{4})cn \log n - 3c(\frac{n}{4})\log 4 \)
\( \displaystyle (\frac{7}{4})cn \log n - 2(\frac{3}{4})cn \)
\( \displaystyle \frac{7}{4}cn \log n - \frac{3}{2} cn \)
A questo punto, penso(a meno che non ho sbagliato di nuovo), possiamo concludere che la soluzione è \( \displaystyle O(n \log n) \) .

Il caso base l'hai scritto tu, io adesso continuo:
\( \displaystyle T(2)=T(1)+ 2\log 2=3 \leq c(2\log 2) \) che è vera per \( \displaystyle c=(\frac{3}{2\log 2})=\frac{3}{2} \)

Perciò possiamo dire che \( \displaystyle T(n) \) appartiene a \( \displaystyle O(n \log n) \) per qualunque \( \displaystyle n>2 \) e \( \displaystyle c=\frac{3}{2} \) .

Adesso come va?

[hamming_burst]

Per prima cosa ti ringrazio per la tua pazienza, mi stai aiutando a capire i miei errori!

Ci riprovo..
Devo dimostare che:
\( \displaystyle T(n)\leq 3c(\frac{n}{4})\log (\frac{n}{4})+ cn \log n \)
\( \displaystyle 3c(\frac{n}{4})\log n - 3c(\frac{n}{4})\log 4 + cn \log n \)
\( \displaystyle (\frac{7}{4})cn \log n - 3c(\frac{n}{4})\log 4 \)
\( \displaystyle (\frac{7}{4})cn \log n - 2(\frac{3}{4})cn \)
\( \displaystyle \frac{7}{4}cn \log n - \frac{3}{2} cn \)
A questo punto, penso(a meno che non ho sbagliato di nuovo), possiamo concludere che la soluzione è \( \displaystyle O(n \log n) \) .

ti direi che sono ok i concetti. Ma ho sbagliato a consigliarti questa ricorrenza, ho visto solo ora che può essere sbagliata la soluzione (\( \displaystyle {O}{\left({n}{\log{{n}}}\right)} \)) oppure ci sono alcuni passaggi non troppo banali per dimostrare effettivamente l'ipotesi. Ti scriverò una soluzione, almeno a quella a cui ho pensato. L'esercizio mi sembrava facile.

Se vedi, facendo delle maggiorazioni, si può subito smentire l'ipotesi:
\( \displaystyle 3c(\frac{n}{4})(\log n - \log 4) + n \log n <= 3c(\frac{n}{4})\log n + n \log n = 7c(\frac{n}{4})\log n \not\leq cnlogn \)
cadendo in un vicolo cieco. Devo rivedermela quando ho più tempo.

Il caso base l'hai scritto tu, io adesso continuo:
\( \displaystyle T(2)=T(1)+ 2\log 2=3 \leq c(2\log 2) \) che è vera per \( \displaystyle c=(\frac{3}{2\log 2})=\frac{3}{2} \)

bhe questo mi pare ok

[krak]

Comunque mettendo da parte questo esercizio in particolare, più che altro volevo sapere se il modo di procedere era giusto, e cioè:

1) Ipotizzo una soluzione alla mia ricorrenza.
2) Dimostro, tramite induzione, se effettivamente l'ipotesi è corretta o meno.
3) Trovo una \( \displaystyle m \) e una \( \displaystyle c \) per i quali è verificata la soluzione.

Fatto questo ho concluso lo studio della mia ricorrenza.

E' corretto tutto ciò?
Grazie

[krak]

3) Trovo una \( \displaystyle m \) e una \( \displaystyle c \) per i quali è verificata la soluzione.

Ho sbagliato è n invece di m.
3) Trovo una \( \displaystyle n \) e una \( \displaystyle c \) per i quali è verificata la soluzione.

[hamming_burst]

Comunque mettendo da parte questo esercizio in particolare, più che altro volevo sapere se il modo di procedere era giusto, e cioè:

1) Ipotizzo una soluzione alla mia ricorrenza.

L'ipotesi la puoi costruire con tutte le tecniche messe a disposizione dall'analisi degli algoritmi (dal metodo algebrico al Master Theorem)

2) Dimostro, tramite induzione, se effettivamente l'ipotesi è corretta o meno.

esatto (o se vuoi, chiamalo metodo della sostituzione).

3) Trovo una \( \displaystyle m \) e una \( \displaystyle c \) per i quali è verificata la soluzione.

questo in accordo con 2), è un'implicazione di verità. E' esatto dire che cerchi un \( \displaystyle {m} \) (ricorda \( \displaystyle \ldots\ {m}\ge{0},\ \ldots.\ \forall{n}\ge{m} \))
ed infine (come ho consigliato per evitare calcoli possibilmente inutili) dimostrare il caso base.

Tutto questo sarebbe da fare sempre. Ma alle volte basta anche fermarsi al passo 1), per capire l'andamento di una ricorrenza e perciò la complessità di un algoritmo. La dimostrazione viene dopo.

[hamming_burst]

Ho avuto qualche momento oggi, così ho riguardato la ricorrenza.
Devi dirlo, mi son perso in un bicchier d'acqua (come si dice), troppo lavoro dato dalla tesi

Sì, è vero che \( \displaystyle {T}{\left({n}\right)}\in{O}{\left({n}{\log{{n}}}\right)} \), io mi ero fissato nel voler dimostrare che \( \displaystyle {T}{\left({n}\right)}\in{O}{\left({n}{\log}_{{4}}{\left({n}\right)}\right)} \) cosa vera ma con risvolti formalmente non troppo semplici, per questo è nato il dubbio.
Perciò il tutto rimane con base generale ed anonima, rimane vero ciò che avevamo già scritto, ma con un passaggio semplice in più, manca semplicemente da definire la costante:

\( \displaystyle 3c(\frac{n}{4})\log (\frac{n}4) + nlogn = 3c(\frac{n}{4})(\log n - \log 4) + n \log n \leq \frac{3}4cn\log n + n \log n \leq cnlogn \) per \( \displaystyle {c}\ge{4} \).

Il caso base è valido per un qualche \( \displaystyle {n}\ge{2} \).

più semplice di così

[krak]

Data questa ricorrenza:

\( \displaystyle T(n)=9T(\frac{n}{3})+n^{2}\log n \)

L'ho svolta applicando il secondo caso generalizzato del teorema Master, e ho dato come soluzione: \( \displaystyle \Theta (n^{2} \log ^{2}n) \)

E' corretto?

[hamming_burst]

Data questa ricorrenza:

\( \displaystyle T(n)=9T(\frac{n}{3})+n^{2}\log n \)

L'ho svolta applicando il secondo caso generalizzato del teorema Master, e ho dato come soluzione: \( \displaystyle \Theta (n^{2} \log ^{2}n) \)

E' corretto?

ok.
Avedo un dubbio e son andato a controllare su di un libro, hai utilizzato il metodo generale del caso 2, non lo ricordavo