Pages: [1]   Go Down
Print
Author Topic: Dubbio ricorrenza 4.1-1 Cormen  (Read 1099 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Liuba
Matricola
*
Offline Offline

Gender: Female
Posts: 82


« on: 16-02-2011, 22:16:21 »

Salve ragazzi,
stavo provando a risolvere questo esercizio (4.1-1 Cormen)
Dimostrare che la soluzione di T(n) = T(\lceil n/2 \rceil) + 1 è O(logn)

Io ho eseguito questi passaggi:
T(n) \le c log[\lceil n/2 \rceil] + 1
essendo x\le \lceil x \rceil < x + 1 sostituendo si ha
T(n) < c log(n/2 + 1) + 1
T(n) < c log[(n+2)/2]+1
< c log(n +2) -c +1 che dovrebbe essere
\le c logn

ma non riesco a dimostrarlo. Dove sto sbagliando? Qualcuno mi può aiutare?  
« Last Edit: 16-02-2011, 22:25:25 by Liuba » Logged

"Stay Hungry. Stay Foolish."
Liuba
Matricola
*
Offline Offline

Gender: Female
Posts: 82


« Reply #1 on: 16-02-2011, 22:55:21 »

Salve ragazzi,
stavo provando a risolvere questo esercizio (4.1-1 Cormen)
Dimostrare che la soluzione di T(n) = T(\lceil n/2 \rceil) + 1 è O(logn)

Io ho eseguito questi passaggi:
T(n) \le c log[\lceil n/2 \rceil] + 1
essendo x\le \lceil x \rceil < x + 1 sostituendo si ha
T(n) < c log(n/2 + 1) + 1
T(n) < c log[(n+2)/2]+1
< c log(n +2) -c +1 che dovrebbe essere
\le c logn

ma non riesco a dimostrarlo. Dove sto sbagliando? Qualcuno mi può aiutare?  

stavo pensando, ma se svolgessi i calcoli considerando x \leq \lceil x \rceil ?
Verrebbe così
T(n) \leq clog \lceil n/2 \rceil + 1 \geq clog(n/2) +1 = clogn - c + 1

quindi:
T(n) \geq clogn - c + 1 \leq clogn per c\geq 1

però così non dimostro che T(n) \leq clogn .....
...mi sto confondendo... 
Logged

"Stay Hungry. Stay Foolish."
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #2 on: 16-02-2011, 23:11:27 »

dimostrero' che
T(n)\ \leq\ c \log(n - b)
per una qualche costante b\geq 0

Supponiamo quindi che valga
T(\lceil\frac{n}{2}\rceil)\ \leq\ c \log(\lceil\frac{n}{2}\rceil - b)
allora

T(n)\ \leq\ c \log(\lceil\frac{n}{2}\rceil - b)

          \leq\ c \log(\frac{n}{2} +1 -b)\

          =\ c \log(\frac{n-2b+2}{2})

          =\ c \log(n-2b+2) -c\

          \leq\ c\log(n-b) -c

          \leq\ c\log(n-b)

per b\geq 2

Cosi' dovrebbe andare... spero di esserti stato d'aiuto
« Last Edit: 16-02-2011, 23:16:27 by shiny » Logged
Liuba
Matricola
*
Offline Offline

Gender: Female
Posts: 82


« Reply #3 on: 16-02-2011, 23:37:12 »

Sei stato gentilissimo!!!! Grazie mille! 

ho solo un dubbio, non ho capito come mai il +1 presente nell'equazione, non si considera.
In teoria seguendo il tuo ragionamento, alla fine a me risulta
clog(n-2b+2) - c + 1

Ometti sia i 2 che il +1? Togliere i 2 riesco forse a capirlo perché comunque prosegui con un \leq, ma non capisco perché non si considera il +1
...forse è una domanda stupida perdonami, ma avere alla fine
clog(n-b) -c o clog(n-b) -c + 1 non cambia tutto? il primo riesco a capire che è minore di clog(n-b) ma il secondo?  scusami....
Logged

"Stay Hungry. Stay Foolish."
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #4 on: 17-02-2011, 00:00:02 »

il +1 (costo esterno) l'avevo completamente scordato  ... sono circa 3 anni che non tocco ste' cose e sono un po' arrugginito. Comunque questi passaggi adesso dovrebbero essere corretti sotto le stesse ipotesi di prima 

T(n)\ \leq\ c \log(\lceil\frac{n}{2}\rceil - b) + 1

          \leq\ c \log(\frac{n}{2} +1 -b)\ +\ 1\

          =\ c \log(\frac{n-2b+2}{2})\ +\ 1

          =\ c \log(n-2b+2)\ -\ c\ +\ 1\

          \leq\ c\log(n-b)\ -\ c\ +\ 1

          \leq\ c\log(n-b)

per b\geq 2 e c\geq 1
« Last Edit: 17-02-2011, 01:55:05 by shiny » Logged
Liuba
Matricola
*
Offline Offline

Gender: Female
Posts: 82


« Reply #5 on: 17-02-2011, 00:05:12 »

  Non so davvero come ringraziarti!!!  Gentilissimo!!!! Tutto chiarissimo!

Grazie anche per la pazienza    ciao
Logged

"Stay Hungry. Stay Foolish."
Pages: [1]   Go Up
Print
Jump to: