ilpuntotecnicoeadsl.com
09 Settembre 2010, 23:56 *
Benvenuto, Visitatore. Per favore, effettua il login o registrati.
Hai perso la tua email di attivazione?

Login con username, password e lunghezza della sessione

News: Aggiornato il forum alla versione 1.1.11 di SMF.
 
   Home   Help Ricerca Calendario Login Registrati  
Pagine: [1]
  Stampa  
Autore Topic: Analisi della complessita' algoritmica O(...)  (Letto 1083 volte)
0 Utenti e 1 Utente non registrato stanno visualizzando questa discussione.
aduri
Nuovo Iscritto
*
Offline Offline

Posts: 18


« il: 10 Ottobre 2006, 19:45 »

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
Loggato
magnus1
Nuovo Iscritto
*
Offline Offline

Posts: 4


« Risposta #1 il: 19 Gennaio 2009, 23:01 »

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 !!!
Loggato
Pagine: [1]
  Stampa  
 
Salta a:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.11 | SMF © 2006-2008, Simple Machines LLC
Traduzione Italiana a cura di SMItalia
XHTML 1.0 valido! CSS valido!