Ho loop in questo modo:
for(int i = 0; i < n; i++) {
for(int j = 0; j < i; j++) {
sum += 1;
}
}
È O (n *), ma non sono sicuro di cosa sia j < è il ciclo.
Ho alcuni test che ho eseguito,
n = 10, runs = 45
n = 20, runs = 190
n = 40, runs = 780
n = 80, runs = 3160
n = 10, runs = 12720
Sembra che converga in .5 * n ^ 2, ma non ne sono del tutto sicuro.
Si stanno sommando i numeri da 1 a n, incrementando il valore di uno ogni volta. Questa è essenzialmente la classica somma di Gauss che è:
sum(1 .. n) = (n * n-1)/2
Questo è anche il numero di volte nel ciclo.
(n^2 - n) / 2
(n^2)/2 - n/2
Quando si rappresenta Big O , viene usato solo il termine con la massima potenza e le costanti vengono gettate via, e quindi la risposta è O (n 2 ).
Maggiori informazioni su questo particolare problema possono essere lette su CS.SE su Big O: annidato per loop con dipendenza
Il 1 ° iterazione del ciclo esterno (i = 0), il ciclo interno itererà 0 volte
Il 2 iterazione del ciclo esterno (i = 1), il ciclo interno itererà 1 volta
Il 3 iterazione del ciclo esterno (i = 2), il ciclo interno itererà 2 volte
.
.
Nella versione finale del ciclo esterno (i = n - 1), il ciclo interno sarà
iterare n - 1 volte
Così, il numero totale di volte verrà eseguito le istruzioni nel ciclo interno sarà pari alla somma dei numeri interi da 1 a n - 1, che è:
((n ‐ 1)*n) / 2 = (n^2)/2 ‐ n/2 = O(n^2) times
se i == 0 allora j varia da 0 a -1 == > (non possibile) 0 se io == 1 allora j varia da 0 a 0 == > 1 se io == 2 , , , 1 == > 2 . . . se ho == n-1 allora j da 0 a n-2 == > iterazioni n-1
sommandoli
È S = 0 + 1 + 2 + 3 + ....... + n-2 + n-1 come S = n-1 + n-2 + ...... + 1 + 0
summing 2 * S = (n-1) + (n-1) + ............. (n-1) // n volte
== > 2 * S = (n-1) * n == > S = (n-1) * n / 2
Puoi vedere che segue una particolare equazione che è (n*(n-1))/2 . e, g per n = 5, runs = (n * (n-1)) / 2 = 5 * 4/2 = 10. Quindi è O (n * (n-1)) = O (n ^ nn) = O (n ^ 2) [Come nel caso di Big-O, i termini di ordine inferiore e le costanti vengono ignorati]
Leggi altre domande sui tag algorithms big-o