Newsgroup: it.comp.lang.c
Titolo: Re: complessita` asintotica

 Grazie.
Per caso č Theta(n*x)?

Non capisco perchè si debba impostare la non archiviazione del
messaggio !!!!
Non mi sembra un comportamento molto corretto !!!
maxim2k ha scritto:


 arrivarci, cosi` magari qualcuno puo` anche correggerli se sono sbagliati?
Potresti rimuovere quell'opzione che dice di non archiviare i messaggi
? cosi' magari in un futuro qualche d'uno potrà beneficiare di questo
thread ?

 ha scritto nel messaggio
news:45740ec2$0$13764$4faf...@reader3.news.tin.it...

La soluzione non puň dipendere da 'x'. E nemmeno da 'y'.
Sono delle semplici variabili interne, quindi "dummy".
Il tempo di esecuzione (e "myvar") dipende solo da 'n'.
cioč la soluzione č: Theta(F) con F = F(n)
Ho fatto il seguente ragionamento:
(Ovviamente con ^ indico l'esponenziazione e non
lo XOR !)
poniamo n del tipo 2^(2^k), tanto se non lo
č posso sempre limitare tale valore con due
interi n1 e n2 del tipo:
n1 < n < n2 con
n1 = 2^(2^k)
e
n2 = 2^(2^(k+1))
x assume valori:
x = 2 = 2^(2^0)                      i = 0
x = 2*2 = 4 = 2^(2^1)            i = 1
x = 4*4 = 16= = 2^(2^2)        i = 2
x = 16 * 16 = 256 = 2^(2^3)  i = 3
...
...
x = 2^(2^k)                            i = k = log2(log2(n1))   [N1]
se n1 < n, oppure
x = 2^(2^(k-1))                      con k = log2(log2(n))    [N]
se n = 2^(2^k).
Il loop interno 'costa' x, cioč 2^(2^i) al
generico passo 'i'.
Quindi si tratta di valutare la sommatoria (faccio il caso [N1], l'altro
č uguale):
(***)
S(k) = 2^(2^0) + 2^(2^1) + ... + 2^(2^i) + ... + 2^(2^k)
con k = log2(log2(n)).
Ho fatto la seguente considerazione:
č noto che
S(k) = 2^0 + 2^1 + ... + 2^i + ... + 2^k č Theta(2^k) cioč
conta sostanzialmente solo l'ultimo termine.
Quindi "a maggior ragione" anche in (***), visto
che i termini aumentano maggiormente se passo
dal termine 'i' a quello 'i+1', conta solo l'ultimo (in termini di Theta).
Pertanto:
    F(n) = Theta(n)
Essendo 2^(2^k) = 2^(2^log2(log2(n))) = n
Cioč il tempo di esecuzione č lineare in 'n'.
--
Giorgio Silvestri
DSP/Embedded/Real Time OS   Software Engineer

 myvar++;
Il primo for viene eseguito un numero di volte pari all'intero inferiore del 
logaritmo in base due del logaritmo in base 2 di n, il tutto più 1. Non sono 
sicurissimo, ma mi sembra sia così.
Il secondo for viene eseguito 2, 4, 16, 256, 64536, ecc... volte. Cioè 2 
alla 2 alla numero della volta in cui viene eseguito.
L'operazione interna ha peso unitario.
Mettendo insieme la cosa direi che l'operazione viene eseguita un numero di 
volte pari a
int(log_2(log_2(n))+1)
___
\
/   2^2^i
---
i=1
Io direi che in generale si possono trascurare tutti i termini della 
sommatoria rispetto all'ultimo, quindi viene una cosa del tipo:
2^2^int(log_2(log_2(n))+1)
Trascurerei il discorso dell'intero inferiore e quindi viene:
2^2^(log_2(log_2(n))+1) = 2^(2*2^(log_2(log_2(n))) = 2^(2*log_2(n)) = 
2^(log_2(n^2)) = n^2
Adesso che ci ho provato: qual'è la risposta giusta?
-- 
Costantino Grana 

 Adesso che ci ho provato: qual'č la risposta giusta?


 Nel primo caso la sommatoria da valutare è:

Volendo invece esprimere, "precisamente"  la
complessità f(n) in termini di Theta si ha, sapendo
che abbiamo i casi (A) + (B):
f(n) = Theta(2^2^(ceil(log2(log2(n))) - 1))
che è addirittura qualcosa meno che lineare !
Comunque dire che f(n) è Theta(2^2^(ceil(log2(log2(n))) - 1))
implica f(n) = O(n)
Non vale il viceversa naturalmente:
cioè f(n) = O(n)  NON IMPLICA f(n) = Theta(2^2^(ceil(log2(log2(n))) - 1))
In "conclusione" si ha che in ogni caso
il numero di operazioni non cresce asintoticamente
più di una funzione lineare in 'n'.
Davvero interessante...
