Quale sarebbe l'ordine di crescita del codice qui sotto. La mia ipotesi era che la crescita di ogni loop fosse lineare ma l'affermazione if mi confondeva. Come includo ciò con il tutto. Gradirei molto una risposta esplicativa in modo da poter comprendere il processo in questione.Ordine di crescita per loop
int count = 0;
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
for (int k = j+1; k < N; k++)
if(a[i] + a[j] + a[k] == 0)
count++;
Ci sono due cose che possono essere fonte di confusione quando si cerca di determinare la complessità del codice.
Il fatto che non tutti i cicli iniziano da 0. Il secondo ciclo inizia dal i + 1 e la terza da j + 1. Questo influenza la complessità? Non è così. Consideriamo solo i primi due cicli. Per i = 0, la seconda esegue N - 1 volte, per i = 1 viene eseguito N - 2 volte, ..., per i = N - 1 viene eseguito 0 volte. Aggiungere tutti questi up:
0 + 1 + ... + N - 1 = N(N - 1)/2 = O(N^2).
Quindi non a partire da 0 non influenza la complessità (ricordiamo che big-oh ignora i termini e le costanti di ordine inferiore). Pertanto, anche in questa impostazione, l'intera cosa è O(N^3).
La dichiarazione if. L'istruzione if è chiaramente irrilevante qui, perché è solo una parte dell'ultimo ciclo e non contiene alcuna istruzione break o altro codice che possa influire sui loop. Influisce solo sull'incremento di un conteggio, non sull'esecuzione di nessuno dei loop, quindi possiamo tranquillamente ignorarlo. Anche se il conteggio non viene incrementato (operazione O(1)), viene verificata la condizione if (anche un'operazione O(1)), quindi viene eseguito lo stesso numero approssimativo di operazioni con e senza lo if.
Pertanto, anche con l'istruzione if, l'algoritmo è ancora O(N^3).
Posso chiedere perché hai diviso N (N-1) per 2. – JVTura
@ JVTura - perché la somma viene calcolata raggruppando il primo termine con l'ultimo, il secondo con il penultimo ecc. Per '0 + 1 + 2 + 3 + 4' per esempio, dovremmo raggruppare '(0 + 4) + (1 + 3) + (2 + 2) + (3 + 1) + (4 + 0)'. Ci sono gruppi 'N = 5', ciascuno con somma' N - 1 = 4'. Ma dobbiamo dividere per 2 perché ogni gruppo si verifica due volte, quindi superiamo se non dividiamo: '5 * 4/2 = 10', che è corretto. – IVlad
Quale sarebbe l'ordine di crescita di questo snippet di codice? 'int sum = 0; for (int n = N; n> 0; n/= 2;) per (int i = 0; i
L'ordine di crescita del codice sarebbe O (N^3).
In generale k cicli annidati di lunghezza N contribuiscono alla crescita di O (N^k).
Il fatto che i cicli nidificati si riducano ogni iterazione influisce sul risultato? Mi aspettavo un fattoriale o un altro modificatore – Alter
Non proprio. Mentre influenzerebbe la costante accanto a N^k, non influisce in realtà sulla notazione O. – Riko
Forse ho sbagliato, ancora nuovo: O (n * (n - 1) * (n-2)) = O (n^3 - 3 * n^2 + 2n) – Alter
Qui ci sono due è stato trovare che la complessità temporale è Theta (N^3) senza molti calcoli.
Innanzitutto, selezionare i<j<k dall'intervallo 0 a N-1. Il numero di modi per scegliere 3 oggetti da N è il binomial coefficient N scegliere 3 = N*(N-1)*(N-2)/(3*2*1) ~ (N^3)/6 = O(N^3) e più precisamente Theta (N^3).
In secondo luogo, un limite superiore è che si scelgono i, j e k da N possibilità, quindi ci sono al massimo N*N*N = N^3 scelte. Questo è O (N^3). È anche possibile trovare un limite inferiore dello stesso tipo poiché è possibile scegliere i da 0 a N/3-1, j da N/3 a 2N/3-1 ek da 2N/3 a N-1. Questo ti dà almeno le opzioni di floor (N/3)^3, che è circa N^3/27. Poiché hai un limite superiore e un limite inferiore della stessa forma, la complessità temporale è Theta (N^3).
(La (mancanza di) commenti e indentazione delle linee di codice lasciano dubbi su cosa dovrebbe fare.) Si prega di essere espliciti riguardo a '[guess] la crescita di ogni ciclo è lineare'. Qual è la tua domanda? Hai una dichiarazione il cui costo può essere considerato costante, come il suo controllo. Questo è in un ciclo annidato triplo: cosa succede se tutti i loop sono passati da 0 a N? Cosa succede in caso di valori iniziali dall'alto? – greybeard