Analisi della complessita' algoritmica O(...)

[aduri]

Qualcuno mi puo' spiegare come si possano ottenere i seguenti risultati?
Cortesemente potete spiegarmi i passaggi?

La prima analisi e' abbastanza chiara (anche a vista sono 2 cicli nidificati quindi implica O(n^2)):

for(i=0; i<a.length;i++){
for(j=1,sum=a[0]; j<=i;j++)
sum+=a[j];
System.out.println("Somma sub "+sum);}

e si ottiene:
T(n)= 1+ 3n + sum (da i=1 a n-1)*2i = 1+3n+n(n-1) = O(n^2)

in sequenza: non capisco 1; capisco 3n perche' sono i 3 assegnamenti i,j,sum; capisco l'ultima parte quando si itera n-1 volte sia su sum che su j;
non capisco nella seconda espressione n(n-1)


e

for(i=4; i<a.length;i++){
for(j=i-3,sum=a[i-4]; j<=i;j++)
sum+=a[j];
System.out.println("Somma sub "+sum);}

qua capisco che anche se sono 2 cicli nidificati uno cicla meno ma a parte (n-4) il resto non lo capisco.

T(n)= 1+ (n-4)(1 + 2 + 4·2) = O(n)


Grazie

[magnus1]

Salve ,
aduri premetto che non sono fresco da Algoritmi ma ,

Allora nel primo caso credo che il tuo " 1 " è una costante relativa al fatto che cmq bisogna fare una valutazione del problema e cmq lo puo sapere trovandosi la formula della tecnica  "divide ed impera" a cui tu fai riferimento con la formula iterativa T(n)....  .
L'altra domanda n(n-1) vuole indicare in un'altra forma matematica tutte le operzioni restanti .
Infine l'analisi che tu stai conducendo io penso che non sia molto corretta perchè quando si valutano gli algoritmi specie se in java per tutto quello che java crea all'avvio(oggetti) si trascurano tutte le costanti quindi 1 ... dovresti valutare all'infinito come nei limiti il termine con esponente maggiore da la " O " (o grande=ovvero il peggio che un algortimo possa fare , il massimo delle operazioni che si possono fare per risolvere un problema ; quindi non ottimale) .

Il secondo quesito prova a guardare il tutto così :

for(i=4; i<a.length;i++){
    for(j=i-3,sum=a[i-4]; j<=i;j++)                       
        sum+=a[j];                                             
        System.out.println("Somma sub "+sum);       
}
      T(n)= 1+ (n-3)(1 + 2 + 4·2) = O(n) è giusto !

qui mi pare che la condizione cardine è j<=i , esecuzione :
        per i=4 --> j=1   cond j<=i  è vera
        per i=5 --> j=2   cond   "    è vera
        per i=6 --> j=3   cond   "    è vera
        per i=7 --> j=4   cond   "    è vera
        per i=8 --> j=5   cond   "    è vera
        per i=9 --> j=6   cond   "    è vera
        per i=10 -> j=7   cond   "    è vera
        per i=11 -> j=8   cond   "    è vera
        per i=12 -> j=9   cond   "    è vera
        per i=13 -> j=10 cond   "    è vera
        per i=14 -> j=11 cond   "    è vera
Duufferenza costante è sempre n-3 e non n-4 , ci pensi !!!