Complessità

[alby941]

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!

[apatriarca]

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..

[alby941]

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?

[Giova411]

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.

[alby941]

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...

[alby941]

La mia risposta precedente è giusta?

[apatriarca]

Sì, la risposta era corretta.

[alby941]

Matematicamente come andava scritto? Perché io l'ho detto un po a logica ma penso debba esserci qualche sommatoria ..

[apatriarca]

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)\).

[alby941]

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