Newsgroup: it.scienza.informatica
Titolo: Calcolo complessità...

Salvbe a tutti, sono al primo anno di ingegneria informatica, volevo
chiedervi una cosa che non mi è molto chiara nel calcolo della complessità
di un programma.
Faccio subito un esempio.
Il linguaggio è il Java:
Il prof dice che la complessita la si calcola dai cicli di for, ma:
se ho ad esempio:
For (int i=0; i<n; i++)
   For (int i=0; i<n; i++)
      For (int i=0; i<n; i++)
         For (int i=0; i<n; i++)
           System.out.println();
la complessità sarà (n^4), e fin qui... ci siamo.
ma se ad esempio ho:
..........
For (int i=0; i<n; i++)                         // fa 3 istruzioni per volta
quindi (3*n)
{
    System.out.println();
    System.out.println();
    For (int j=0; i<n; j++)                   // fa 2 istruzione per volta
quindi (2*n)
      System.out.println();
      System.out.println();
 }
..........
in questo caso la complessità secondo me è ((3*n)*(2*n))     cioè    (6*n^2)
sbaglio?
Grazie in anticipo quanti mi chiariranno questo dilemma!!

 ha scritto nel messaggio 
news:43de73f6$0$22092$4faf...@reader1.news.tin.it...

Forse il tuo prof. voleva introdurti alla notazione O grande (big-Oh in 
inglese) che introduce una comoda abbreviazione. Infatti i valori costanti 
sono trascurabili per valori di n dopo una certa soglia. Se ci pensi bene se 
n vale ad esempio 100.000 (ma anche 1000) o più il valore costante 6 è 
trascurabile nel valutare l'efficenza dell'algoritmo. Infatti l'ordine di 
grandezza è grosso modo sempre lo stesso. Inoltre il numero esatto di 
operazioni macchina e il numero effettivo di microsecondi che il computer 
dedica ad esse per ogni istruzione non è di semplice determinazione in 
quanto ogni istruzione ha il suo "peso".
Quindi se hai una cosa del genere:
2*n^2 + 3*n - 3
la complessità è O(n^2)
Come noterai anche la variabile n viene trascurata in quanto apportatrice di 
un contributo non particolarmente influente rispetto a quello di n^2.
Come regola generale basta individuare il termine che aumenta più 
rapidamente e ignorare il suo coefficiente indipendentemente dal fatto che 
sia piccolo o grande.
In modo più formale: per tutti i valori di n maggiori di una certa soglia, 
si ha f(n)/g(n) <= K per un qualche valore costante di K, dove g è scelta in 
modo semplice come n^2 nel tuo caso.
Saluti,
Silverh 

 ((3*n)*(2*n))
stai attento che qui tu hai scritto che esegui 3n volte una operazione che 
costa 2n
cioè avresti:
for 1 to 3n
  for 1 to n
     println
     println
esegui n volte 3 operazioni che costano 2n cadauna si scrive n * (3* (2n)) 

 sbaglio?
da quello che hai scritto suppongo che facciate i calcoli in modo abbastanza 
approsimattivo
cioè che diate costo 1 a una singola operazione println e che non contiate 
il costo della istruzione for
partiamo dall'inizio e troviamo subito un ciclo for che viene eseguito n 
volte
quindi per n volte esegui:
1) la prima println
2) la seconda println
3) il ciclo for interno
hai quindi un costo totale ( ricordando che una singola println costa 1):
n * ( costo_prima_println + costo_seconda_println + costo_for_interno) = n * 
( 1 + 1 + costo_for_interno ) = n + n + n * costo_for_interno = 2n + n * 
costo _for_interno
costo_for_interno lo hai già calcolato te (2n) quindi basta andare a 
sostituire
2n + n * 2n = 2n + 2n^2
quindi il costo totale è 2n^2 + 2n
hai capito il tuo errore ?
prova a scrivere il codice di un programma che ha la complessità che hai 
calcolato te 

 (2n))
Scusami ma non ho capito questa ultima parte e cioč la differenza tra
"n*(3*(2n))", e "(6*n^2)".
In pratica, se ad n, assegno un valore 2  i for che quindi partono da 0 a 2
ripetono 3 volte le istruzioni, e dovrebbero fare cosě:
1 - operazione del primo ciclo for = 2(println del primo for)+6(println del
ciclo innestato)
2 - operazione del primo ciclo for = 2(println del primo for)+6(println del
ciclo innestato)
3 - operazione del primo ciclo for = 2(println del primo for)+6(println del
ciclo innestato)
quindi (2+6)+(2+6)+(2+6) = 24... giusto?
Grazie ancora!