[Algoritmi] Dubbio su 2 complessità
Sto svolgendo gli esercizi di questo pdf: http://www.dipmat.unipg.it/%7Epinotti/C ... 0.wsol.pdf (Consigliati nel topic delle dispense in rete)
dei quali trovate anche le soluzioni qui: http://www.dipmat.unipg.it/%7Epinotti/C ... ciziC0.pdf
ma arrivato a svolgere l'esempio 5 e l'esempio 6 mi sono sorti dei dubbi,tra un attimo vi dico quali,prima posto il codice delle due funzioni:
Esempio 5:
Esempio 6:
Negli esercizi che ho svolto precedentemente,quando mi trovavo nella situazione "ciclo for" annidato in un "ciclo while",ho sempre calcolato la ricorrenza nel modo seguente (ovviamente non fate caso al valore iniziale di k e quello finale,è un esempio generalizzato):
$ sum_(k = 1)^(n)T_2(n) $ dove $ T_2(n) $ era ciò che si trovava all'interno del while,ovvero $ 1 + sum_(j = 1)^(n)O(1) $ (prendendo ad esempio un semplice ciclo for dove ogni iterazione si assegna un valore costante ad una variabile,più un eventuale riga di costo O(1) al di fuori del for ma sempre all'interno del while),quindi svolgendo poi calcoli verrebbe $ n*(n+1) $ e quindi $ O(n^2) $ (riferendomi sempre a questo esempio generalizzato).
Ora passiamo ai dubbi che mi sono venuti svolgendo i due esercizi qui sopra,procedendo nel modo che ho sempre seguito fino ad ora,nell'esempio 5 avrei un ricorrenza del tipo $ T_1(n)= 1 + sum_(k = 1)^(log_9(n)) T_2(n) $ dove $T_2(n) $ è quello che trovo all'interno del while,mentre la soluzione sul pdf risolve tale complessità calcolando solo quella del ciclo while e senza tenere conto di ciò che c'è all'interno,e lo fa in questo modo:
$ T(n)=sum_(t = 0)^(log_9(n))9^t <= 9^(log_9(n+1)) in O(n) $
perchè?
Mentre nell'esercizio 6 sembra che venga preso in considerazione solo il ciclo for interno:
$ T(n)=sum_(t = 0)^(log_9(n))O(3^t) $ arrivando ad una complessita $ O(sqrt(n)) $ (per vedere tutti i passaggi basta che guardate il pdf con le soluzioni)
dei quali trovate anche le soluzioni qui: http://www.dipmat.unipg.it/%7Epinotti/C ... ciziC0.pdf
ma arrivato a svolgere l'esempio 5 e l'esempio 6 mi sono sorti dei dubbi,tra un attimo vi dico quali,prima posto il codice delle due funzioni:
Esempio 5:
int k=1,i=1;
while(k<=n){
for(int j=1;j<=k;j++){
w=4;}
k=k*9;
}
Esempio 6:
int k=1;int i=0;
while(k<=n){
for(int j=1,j<=3^i;j++){
w=4;}
k=k*9;i++;
}
Negli esercizi che ho svolto precedentemente,quando mi trovavo nella situazione "ciclo for" annidato in un "ciclo while",ho sempre calcolato la ricorrenza nel modo seguente (ovviamente non fate caso al valore iniziale di k e quello finale,è un esempio generalizzato):
$ sum_(k = 1)^(n)T_2(n) $ dove $ T_2(n) $ era ciò che si trovava all'interno del while,ovvero $ 1 + sum_(j = 1)^(n)O(1) $ (prendendo ad esempio un semplice ciclo for dove ogni iterazione si assegna un valore costante ad una variabile,più un eventuale riga di costo O(1) al di fuori del for ma sempre all'interno del while),quindi svolgendo poi calcoli verrebbe $ n*(n+1) $ e quindi $ O(n^2) $ (riferendomi sempre a questo esempio generalizzato).
Ora passiamo ai dubbi che mi sono venuti svolgendo i due esercizi qui sopra,procedendo nel modo che ho sempre seguito fino ad ora,nell'esempio 5 avrei un ricorrenza del tipo $ T_1(n)= 1 + sum_(k = 1)^(log_9(n)) T_2(n) $ dove $T_2(n) $ è quello che trovo all'interno del while,mentre la soluzione sul pdf risolve tale complessità calcolando solo quella del ciclo while e senza tenere conto di ciò che c'è all'interno,e lo fa in questo modo:
$ T(n)=sum_(t = 0)^(log_9(n))9^t <= 9^(log_9(n+1)) in O(n) $
perchè?
Mentre nell'esercizio 6 sembra che venga preso in considerazione solo il ciclo for interno:
$ T(n)=sum_(t = 0)^(log_9(n))O(3^t) $ arrivando ad una complessita $ O(sqrt(n)) $ (per vedere tutti i passaggi basta che guardate il pdf con le soluzioni)
Risposte
Ho l'impressione che tu ti faccia condizionare da regole fisse che ti sei trovato, invece di cercare di capire che cosa faccia esattamente il codice. Nel primo caso, il ciclo interno viene eseguito \(k\) volte meno quello esterno viene eseguito fino a quando \(k\) è minore di \(n\). Ad ogni iterazione del ciclo \(k\) viene moltiplicato per \(9\) per cui \(k = 9^t\) dove \(t\) è l'iterazione corrente. Imponendo la solita condizione \( k = n \) per la terminazione del ciclo si ottiene \( t = \log_9 n. \) Abbiamo quindi che la complessità globale di questo codice è
\[ \sum_{t = 1}^{\log_9 n} k(t) = \sum_{t = 0}^{\log_9 n} 9^t \]
come nella soluzione.
La seconda soluzione sarebbe corretta (e simile alla precedente) se in C 3^i fosse effettivamente uguale a \(3^i\). In realtà ^ in C e nei linguaggi simili significa XOR bit a bit e il risultato di tale valore è ben diverso da quello che si aspetta la soluzione. Di fatto la complessità del ciclo interno sarebbe probabilmente più vicino a O(t). 3 XOR i è infatti uguale a i con i 2 bit meno significativi invertiti.
\[ \sum_{t = 1}^{\log_9 n} k(t) = \sum_{t = 0}^{\log_9 n} 9^t \]
come nella soluzione.
La seconda soluzione sarebbe corretta (e simile alla precedente) se in C 3^i fosse effettivamente uguale a \(3^i\). In realtà ^ in C e nei linguaggi simili significa XOR bit a bit e il risultato di tale valore è ben diverso da quello che si aspetta la soluzione. Di fatto la complessità del ciclo interno sarebbe probabilmente più vicino a O(t). 3 XOR i è infatti uguale a i con i 2 bit meno significativi invertiti.
"apatriarca":Beh per quanto riguarda le regole fisse,quello che c'è in un ciclo devo comunque prenderlo in considerazione,altrimenti ogni volta sarebbe bastato calcolare soltanto la complessità del ciclo più esterno.Comunque tralasciando un attimo l'esempio 6 dove forse la mia prof non ha proprio trattato questo tipo di esercizi visto che la materia sarebbe "introduzione agli algoritmi" (quindi a livello basilare),il discorso che hai fatto sull'esercizio 5 lo comprendo,però non capisco perchè nella prima sommatoria hai messo $ k(t) $,visto che comunque $ k=9^t $ riguarda solo il ciclo esterno.Potresti illuminarmi?
Ho l'impressione che tu ti faccia condizionare da regole fisse che ti sei trovato, invece di cercare di capire che cosa faccia esattamente il codice. Nel primo caso, il ciclo interno viene eseguito \(k\) volte meno quello esterno viene eseguito fino a quando \(k\) è minore di \(n\). Ad ogni iterazione del ciclo \(k\) viene moltiplicato per \(9\) per cui \(k = 9^t\) dove \(t\) è l'iterazione corrente. Imponendo la solita condizione \( k = n \) per la terminazione del ciclo si ottiene \( t = \log_9 n. \) Abbiamo quindi che la complessità globale di questo codice è
\[ \sum_{t = 1}^{\log_9 n} k(t) = \sum_{t = 0}^{\log_9 n} 9^t \]
come nella soluzione.
La seconda soluzione sarebbe corretta (e simile alla precedente) se in C 3^i fosse effettivamente uguale a \(3^i\). In realtà ^ in C e nei linguaggi simili significa XOR bit a bit e il risultato di tale valore è ben diverso da quello che si aspetta la soluzione. Di fatto la complessità del ciclo interno sarebbe probabilmente più vicino a O(t). 3 XOR i è infatti uguale a i con i 2 bit meno significativi invertiti.
Con k(t) volevo solo indicare il valore che k ha nella iterazione t-esima. Cioè il numero di iterazioni del ciclo interno. Insomma k(t) = 9^t.
"apatriarca":ok ma quanto volte viene eseguito il ciclo for interno? è questo che non mi è chiaro,k volte ogni iterazione del ciclo while,non si dovrebbe moltiplicare per 9^t ?
Con k(t) volevo solo indicare il valore che k ha nella iterazione t-esima. Cioè il numero di iterazioni del ciclo interno. Insomma k(t) = 9^t.
Il ciclo interno viene eseguito un numero di volte diverso ad ogni iterazione del ciclo esterno. Il numero di volte in cui viene eseguito è k(t).
"apatriarca":XD adesso ho capito,stavo facendo una confusione immensa per un cosa alla fine facilissima,mi ero impuntato su quel 9^t ma non ragionavo sul fatto che il ciclo esterno condizionava il secondo tramite la sommatoria,quindi per essere più precisi e seguendo il metodo che stavo utilizzando sarebbe:
Il ciclo interno viene eseguito un numero di volte diverso ad ogni iterazione del ciclo esterno. Il numero di volte in cui viene eseguito è k(t).
$ T(n) = sum_(t = 0)^(log_9(n))T_1(n) $ dove $ T_1(n)= sum_(j = 0)^(k)O(1) $ con $ k=9^t $ e quindi:
$ T(n) = sum_(t = 0)^(log_9(n))sum_(j = 0)^(k)O(1) = sum_(t = 0)^(log_9(n))9^t$
giusto?
Direi di sì.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo