Analisi della complessita' algoritmica big O

aduri

Nuovo Utente
3 Ott 2006
13
2
0
59
Genova
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
 
Discussioni simili
Autore Titolo Forum Risposte Data
C analisi numero parole Programmazione 2
felino Google Search Console: analisi delle ricerche SEO e Posizionamento 2
enzonero Errore di analisi php line 1 PHP 11
G Analisi disponibilità prodotti MS Access 2
F Analisi Hardware su un dominio Windows e Software 0
F BSOD (con analisi) : soluzioni? Windows e Software 4
R Aiuto!! per Magento/analisi sito - Meta e Tag duplicati e voci non trovate Magento 6
N Analisi SEO del vostro dominio/sito SEO e Posizionamento 5
N Analisi SEO Dominio Presenta il tuo Sito 0
R Analisi dei log PHP 1
S Caricamento JPG attraverso analisi nome Flash 0
borgo italia analisi Discussioni Varie 15
borgo italia google analytics analisi comparativa Google Analytics 0
Blogmasterpg Analisi Transazionale Presenta il tuo Sito 0
K Analisi dell'indicizzazione SEO e Posizionamento 0
F stampare a video i risultati della query PHP 1
B Stampare una porzione della pagina PHP 0
Samuele Ronzani Click e reload della pagina PHP 1
R Cercare un file all'interno della directory virtuale IIS PHP 3
L Creare un countdown con giorno specifico della settimana PHP 3
Y verificare condizione dopo esecuzione della funzione Programmazione 0
M calcolo della velocità MS Access 5
C input in sostituzione della select PHP 2
B Saturazione della rete. Reti LAN e Wireless 0
X Dichiarare variabili solo al caricamento della pagina PHP 3
felino Excel: popolare una cella con la data di modifica della riga a cui appartiene Windows e Software 3
R Obbligare all'utente un pagamento al momento della registrazione PHP 3
G Eseguire codice solo al termine della chiamata ajax Ajax 1
C [HTML] modificare la scritta della copyright HTML e CSS 2
M Non corretta lettura del file php.ini della sezione CLI PHP 3
maxnegri Conoscere giorni della settimana fra due date con php PHP 2
S [PHP] Selezionare i campi non in comune con le altre colonne della tabella PHP 4
Cosina Andare a capo nel testo della mail ricevuta dal form php PHP 1
GiErre [PHP] [HTML] Disabilitare un link in funzione della piattaforma PHP 7
A [WordPress] Ridimensionare immagini preview della fotogallery WordPress 8
F INSERIRE IN UN'UNICA CASELLA DI TESTO REPORT ACCESS I VALORI DELLA TABELLA DI UN'INTERA COLONNA MS Access 2
M [Xamarin] personalizzare la schermata della chiamata in arrivo Sviluppo app per Android 0
I [Javascript] mantenere un bottone abilitato al refresh della pagina Javascript 1
usura18 [PHP] Perdita contenuto cookie al reload della pagina PHP 6
T [PHP] impedire un doppio INSERT INTO dopo reload della pagina PHP 3
F [Javascript] spiegazione della closure Javascript 3
T selezionare terza colonna della relatica row Database 2
Merlina3377 link sui post della pagina facebook Annunci servizi di Social Media Marketing 3
A [Javascript] modificare il contenuto della barra indirizzi di un browser Javascript 1
A [Javascript] [HTML] RISOLTO...Allungare un box all'apertura della pagina No Mouse over Javascript 9
A Creazione automatica pagina php da id della riga di una tabella PHP 1
G A che punto è della pagina jQuery 0
D Come salvare scelta della select "dinamica" ajax-php? Come dato php o attributo value tag option? Ajax 5
gnech91 problema: non funzionano alcuni tasti della tastiera Hardware 5
S [Javascript] [HTML] problema nella stampa degli elementi della pagina Javascript 3

Discussioni simili