Complessità
Buongiorno, è la prima volta che prova a fare esercizi sulla complessità asintotica di caso peggiore di codice Java e non ho ben capito il ragionamento da fare. Le "regole" da usare sono quella dell'istruzione dominante, delle parti ripetute...
Ad esempio in questo codice l'istruzione dominante è quella del println, che viene ripetuta O(a) volte , la quale viene ripetuta da 0 a (n-1) volte... ora però devo assegnare ad a un valore e non riesco a capire come "concatenare " il fatto che a sia presente nella porzione di codice superiore, siccome dipende da esso. Da notare che per la regola della porzione più costosa la parte superiore non verrà considerata ai fini del risultato finale se non per l'assegnazione di a.
Se avete esercizi simili svolti ben venga.
Grazie!
Ad esempio in questo codice l'istruzione dominante è quella del println, che viene ripetuta O(a) volte , la quale viene ripetuta da 0 a (n-1) volte... ora però devo assegnare ad a un valore e non riesco a capire come "concatenare " il fatto che a sia presente nella porzione di codice superiore, siccome dipende da esso. Da notare che per la regola della porzione più costosa la parte superiore non verrà considerata ai fini del risultato finale se non per l'assegnazione di a.
Se avete esercizi simili svolti ben venga.
Grazie!
Risposte
Il valore di \(a\) cambia solo nel ciclo iniziale, che, come hai già osservato, non è determinante per il calcolo della complessità asintotica. Puoi quindi pensare di modificare il codice eliminando quel ciclo e inizializzando direttamente \(a\) al valore che assume all'uscita di quel ciclo. Che valore assume? A questo punto \(a\) è costante nei due cicli concatenati, quindi può essere vista come una costante. Ma allora i due cicli successivi sono entrambi ripetuti per un numero costante di iterazione e dovresti essere in grado di concludere..
Mi verrebbe allora da dire O(n^2) pensando ad a come un numero appunto che evolve in maniera lineare essendo una costante .. però il procedimento formale matematico sarebbe di scrivere sommatoria che va da 0 a n-1 di k?
http://www.moreno.marzolla.name/teaching/ASD2014/
e vai su "Dispensa di esercizi svolti": nella prima parte trovi esercizi simili che ti chiariranno ogni dubbio.
e vai su "Dispensa di esercizi svolti": nella prima parte trovi esercizi simili che ti chiariranno ogni dubbio.
A prima vista sembra una notazione che non usiamo e penso che sia anche più avanzato di quello che facciamo noi... alla fine ci sono state date 3 regole da usare( istruzione dominante ...) mentre vedo che voi trovate un'espressione precisa + un certo O(.). Ecco noi dobbiamo solo dire se è O(n) o O(n^2) è così via...
La mia risposta precedente è giusta?
Sì, la risposta era corretta.
Matematicamente come andava scritto? Perché io l'ho detto un po a logica ma penso debba esserci qualche sommatoria ..
L'impressione è che non ti hanno fornito gli strumenti matematici per descriverlo in modo matematico. In ogni caso devi semplicemente dire che il primo ciclo viene eseguito \(n\) volte e ha come unico obiettivo quello di settare \(a = n\). Il ciclo esterno tra i due annidati viene eseguito \(n\) volte e quello interno \(a\) volte. Siccome \(a\) non varia all'interno di questi cicli, il ciclo interno verrà quindi eseguito \(n\) volte. L'istruzione interna ai due cicli annidati (quella in questo caso dominante) verrà quindi eseguita \(n^2\) volte e la complessità finale sarà quindi \(O(n^2)\).
Grazie, questo mi è chiaro ed effettivamente non era molto complicato. Tuttavia ci sono esercizi che richiedono un ragionamento diverso perchè non viene dato a priori , come nell'esercizio di prima, il valore della costante. Ad esempio, qua quanto vale k? Penso debba essere portato ad un qualche esponenziale ma non so in quale modo. Che strumenti matematici devo usare in questo caso?
E nel caso in cui avessi due condizioni dentro all'if come lo considero?
Se ci sono particolari ragionamenti da fare oppure si usano sempre gli stessi criteri.... Grazie ancora
E nel caso in cui avessi due condizioni dentro all'if come lo considero?
Se ci sono particolari ragionamenti da fare oppure si usano sempre gli stessi criteri.... Grazie ancora
Anche nel primo caso hai una costante per \(k\). L'unica differenza è che questa constante è un po' più complicata da calcolare. \(k\) parte da zero e sommi quindi a questo valore \(i\,n\) con \( 0 \le i < n\). Stai insomma calcolando il valore della sommatoria
\[ k = \sum_{i=0}^{n-1} i\,n = n\,\sum_{i=1}^{n-1} i = \frac{n^2\,(n - 1)}{2}. \]
Il risultato è stato ottenuto calcolando la sommatoria con la formula per i numeri triangolari. Avrai quindi che la complessità del metodo sarà \(O(n^3)\).
Nel secondo caso hai che le due condizioni si possono in realtà riscrivere come \( h < \min (n, i+2) \). Siccome \(h = i\) prima del ciclo hai che il ciclo ha un massimo di due iterazioni. È insomma poco influente sulla complessità del metodo che sarà \(O(n)\).
\[ k = \sum_{i=0}^{n-1} i\,n = n\,\sum_{i=1}^{n-1} i = \frac{n^2\,(n - 1)}{2}. \]
Il risultato è stato ottenuto calcolando la sommatoria con la formula per i numeri triangolari. Avrai quindi che la complessità del metodo sarà \(O(n^3)\).
Nel secondo caso hai che le due condizioni si possono in realtà riscrivere come \( h < \min (n, i+2) \). Siccome \(h = i\) prima del ciclo hai che il ciclo ha un massimo di due iterazioni. È insomma poco influente sulla complessità del metodo che sarà \(O(n)\).
Quindi è come se il ciclo interno fosse $O(1)$ ?
Leggendo il tuo ragionamento il discorso fila ... poi però quando ci metto le mani ci sono dei casi che non ho mai visto e mi blocco... in generale è sbagliato partire da un approccio solo matematico dal ciclo più interno per poi andare verso l'esterno( matematicamente con sommatorie e altro) ? O è meglio prima interpretarlo anche in senso logico?
Leggendo il tuo ragionamento il discorso fila ... poi però quando ci metto le mani ci sono dei casi che non ho mai visto e mi blocco... in generale è sbagliato partire da un approccio solo matematico dal ciclo più interno per poi andare verso l'esterno( matematicamente con sommatorie e altro) ? O è meglio prima interpretarlo anche in senso logico?
Qua ho ragionato così: la prima volta il ciclo interno viene ripetuto una sola volta perchè poi j diventa minore di 0, la seconda 2 volte, la terza 3 e cos' via quindi viene ripetuto $n(n+1)/2$ volte. E questo qua per ogni n... quindi è $O(n^3)$... Non sono però sicuro sul fatto che sia al cubo e non al quadrato
Qualcuno? Sto cercando di imparare .. :')
No, ti stai sbagliando, allora:
Il ciclo "for" interno viene eseguito come hai detto tu $(n+1)/2$ volte.
Il ciclo while esterno invece viene eseguito solo $n$ volte (da 0 ad n).
I cicli annidati "aumentano la complessità esponenzialmente", difatti il ciclo interno viene eseguito ad ogni ciclo esterno, quindi in questo caso avremo $n*(n+1)/2$ $~$ $O(n^2)$.
In esercizi cosí semplici, prova a farti qualche passaggio a mano, conta le operazioni e poi trova la formula, ad esempio se ponessimo $n=2$, il programma procederebbe così:
Primo giro: ${i=0 : j=0}$
Secondo giro: ${i=0 : j=0 => j=1}$
Terzo giro: $i>2 =>$ Fine.
Come vedi le assegnazioni di "j" (quindi i cicli fatti, quindi il totale delle operazioni compiute ad ogni ciclo esterno) sono $3=2*(2+1)/2=>n*(n+1)/2$.
Spero di essere stato chiaro.
Ciao.
Il ciclo "for" interno viene eseguito come hai detto tu $(n+1)/2$ volte.
Il ciclo while esterno invece viene eseguito solo $n$ volte (da 0 ad n).
I cicli annidati "aumentano la complessità esponenzialmente", difatti il ciclo interno viene eseguito ad ogni ciclo esterno, quindi in questo caso avremo $n*(n+1)/2$ $~$ $O(n^2)$.
In esercizi cosí semplici, prova a farti qualche passaggio a mano, conta le operazioni e poi trova la formula, ad esempio se ponessimo $n=2$, il programma procederebbe così:
Primo giro: ${i=0 : j=0}$
Secondo giro: ${i=0 : j=0 => j=1}$
Terzo giro: $i>2 =>$ Fine.
Come vedi le assegnazioni di "j" (quindi i cicli fatti, quindi il totale delle operazioni compiute ad ogni ciclo esterno) sono $3=2*(2+1)/2=>n*(n+1)/2$.
Spero di essere stato chiaro.
Ciao.
Si sei stato molto chiaro, tuttavia non mi torna il fatto che mi dici che il ciclo for venga eseguito $(n+1)/2$ volte e non $n*(n+1)/2$ volte dato che : la prima volta 1 poi 2 poi 3 poi 4 e cosi via per circa n volte e quindi la somma dei primi n numeri è $n*(n+1)/2$ volte , le quali verranno ripetute n volte... forse sbaglio qualcosa.. non ho capito poi il tuo esempio, perchè $i$ non diventa mai uno nel tuo esempio ma solo j che in teoria viene inizializzato pari ad i
Ops.. ho sbagliato (colpa del copia incolla), scusa!!. Nel secondo passaggio ovviamente su ha "$i=1$"!
Quando dici:
consideri anche il ciclo "while", che sono proprio le $n$ ripetizioni del ciclo "for"!
Ti rifaccio l'esempio (stando più attento a quello che scrivo...) e scrivendo in ordine tutti i passaggi:
Poniamo $n=4$, lo scopo dell'esercizio è verificare la complessità asintotica, ovvero approssimare il numero di operazioni che l'algoritmo esegue asintoticamente.
In pratica, dobbiamo contare le operazioni, tralasciando "quelle semplici" (cioè quelle eseguite una sola volta, che hanno come $O(1)~1$, quindi trascurabili).
Le uniche operazioni svolte da questo programma sono le assegnazioni di "$j$" e la sua stampa a video (come vedi in realtà sarebbero 2, ma ci interessa solo l'ordine di grandezza, cioè $n~2n~3n~4n~...~O(n)$), quindi vediamo ciclo per ciclo:
Primo ciclo:${i=0; j=0 }$
Secondo ciclo:${i=1; j=1 => j=0}$
Terzo ciclo:${i=2; j=2 => j=1 => j=0}$
Quarto ciclo:${i=3; j=3 => j=2 => j=1 => j=0}$
Quinto ciclo: $i=4>=4 => (i>=n)$ Termina (quindi NON esegue nessuna operazione interna al ciclo stesso!)
Ora se tu conti le assegnazioni di "$j$" (o le stampe a video, in questo caso è la stessa cosa) vedi che sono $10$ ovvero $4*(4+1)/2$ che nel caso generale corrisponde a $=>n⋅(n+1)/2$, dove $n$ sono le volte che viene eseguito il "ciclo esterno" ed $(n+1)/2$ le assegnazioni di $"j"$ ad ogni "assegnazione di $i$".
Scusami i giochi di parole, ma non è semplicissimo spiegare queste cose "scrivendole", ho solo cercato di essere il più preciso possibile, spero di essere stato più chiaro questa volta.
Hola!
Quando dici:
la prima volta 1 poi 2 poi 3 poi 4 e cosi via per circa n volte e quindi la somma dei primi n numeri è $n⋅(n+1)/2$ volte
consideri anche il ciclo "while", che sono proprio le $n$ ripetizioni del ciclo "for"!
Ti rifaccio l'esempio (stando più attento a quello che scrivo...) e scrivendo in ordine tutti i passaggi:
Poniamo $n=4$, lo scopo dell'esercizio è verificare la complessità asintotica, ovvero approssimare il numero di operazioni che l'algoritmo esegue asintoticamente.
In pratica, dobbiamo contare le operazioni, tralasciando "quelle semplici" (cioè quelle eseguite una sola volta, che hanno come $O(1)~1$, quindi trascurabili).
Le uniche operazioni svolte da questo programma sono le assegnazioni di "$j$" e la sua stampa a video (come vedi in realtà sarebbero 2, ma ci interessa solo l'ordine di grandezza, cioè $n~2n~3n~4n~...~O(n)$), quindi vediamo ciclo per ciclo:
Primo ciclo:${i=0; j=0 }$
Secondo ciclo:${i=1; j=1 => j=0}$
Terzo ciclo:${i=2; j=2 => j=1 => j=0}$
Quarto ciclo:${i=3; j=3 => j=2 => j=1 => j=0}$
Quinto ciclo: $i=4>=4 => (i>=n)$ Termina (quindi NON esegue nessuna operazione interna al ciclo stesso!)
Ora se tu conti le assegnazioni di "$j$" (o le stampe a video, in questo caso è la stessa cosa) vedi che sono $10$ ovvero $4*(4+1)/2$ che nel caso generale corrisponde a $=>n⋅(n+1)/2$, dove $n$ sono le volte che viene eseguito il "ciclo esterno" ed $(n+1)/2$ le assegnazioni di $"j"$ ad ogni "assegnazione di $i$".
Scusami i giochi di parole, ma non è semplicissimo spiegare queste cose "scrivendole", ho solo cercato di essere il più preciso possibile, spero di essere stato più chiaro questa volta.
Hola!
le assegnazioni di $j$ non vengono solo 4 ? poi si, il ciclo con la stampa viene ripetuto più volte... Vorrei trovare un riscontro matematico di tutto ciò e non solo per via empirica. Fatto sta che sei stato chiarissimo! Avrei anche in questo altro esercizio un dubbio::
in questo esercizio l'istruzione dominante è quella inferiore( a istinto, non so perchè però); e il compito di quella superiore è quello di settare c ad un certo valore. A prima vista mi verrebbe da dire che segue una crescita lineare, in quanto egli segue con il modello c+=i--> +i-->+i -->.. e così via .. però allo stesso tempo in termini matematici questa non è la sommatoria per i che va da 0 a n-1 di i*n?? In quel caso l'istruzione sotto sarebbe un $O(n^2)$... dare ragione alla matematica o all'istinto?
in questo esercizio l'istruzione dominante è quella inferiore( a istinto, non so perchè però); e il compito di quella superiore è quello di settare c ad un certo valore. A prima vista mi verrebbe da dire che segue una crescita lineare, in quanto egli segue con il modello c+=i--> +i-->+i -->.. e così via .. però allo stesso tempo in termini matematici questa non è la sommatoria per i che va da 0 a n-1 di i*n?? In quel caso l'istruzione sotto sarebbe un $O(n^2)$... dare ragione alla matematica o all'istinto?
In questo caso il primo ciclo viene eseguito $n-1$ volte, quindi al termine si ha $c=n-1$.
Di conseguenza, il ciclo successivo viene eseguito $n-1$ (perché la condizione di uscita dal while è $j>c$).
I cicli non sono annidati, ma vengono eseguiti uno dopo l'altro, quindi avremo $(n-1)+(n-1)$ operazioni, sommando il tutto si avrà $2n-2~O(n)$ asintoticamente, quindi è lineare in $n$.
Ragionando per sommatorie, il primo ciclo è pari a $c=\sum_(i=1)^(n-1)i$ ed il secondo ciclo$ \sum_(j=1)^(c)j$, se contassimo le occorrenze di $i$ e le sommassimo a quelle di $j$ (i cicli NON sono annidati, quindi è una semplice somma tra le operazioni) vedremo che sono pari a $2n-2$ e giungiamo sempre al costo lineare in $O(n)$
Di conseguenza, il ciclo successivo viene eseguito $n-1$ (perché la condizione di uscita dal while è $j>c$).
I cicli non sono annidati, ma vengono eseguiti uno dopo l'altro, quindi avremo $(n-1)+(n-1)$ operazioni, sommando il tutto si avrà $2n-2~O(n)$ asintoticamente, quindi è lineare in $n$.
Ragionando per sommatorie, il primo ciclo è pari a $c=\sum_(i=1)^(n-1)i$ ed il secondo ciclo$ \sum_(j=1)^(c)j$, se contassimo le occorrenze di $i$ e le sommassimo a quelle di $j$ (i cicli NON sono annidati, quindi è una semplice somma tra le operazioni) vedremo che sono pari a $2n-2$ e giungiamo sempre al costo lineare in $O(n)$
occio però, perchè il primo ciclo non è c++ ma c+=i quindi viene a sommarsi sempre i al c precedentemente ottenuto... e tra l'altro la sommatoria che hai scritto tu non è corretta.. se non erro quella è la formula di Eulero ossia n(n+1)/2 e quindi verrebbe $O(n^2)$
Hai ragione, ho scritto una stupidata, scusa ma andavo di fretta e non ho letto bene l'esercizio.
Si, in questo caso il primo ciclo viene eseguito $n-1$ volte (c assume il valore di $n(n+1)/2$) e quindi il secondo ciclo viene eseguito $n(n+1)/2$ volte, con costo computazionale complessivo pari a: $n-1+n*(n+1)/2~O(n^2)$.
Si, in questo caso il primo ciclo viene eseguito $n-1$ volte (c assume il valore di $n(n+1)/2$) e quindi il secondo ciclo viene eseguito $n(n+1)/2$ volte, con costo computazionale complessivo pari a: $n-1+n*(n+1)/2~O(n^2)$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo