Qual è la notazione O grande corretta per un algoritmo eseguito nel tempo triangular? Ecco un esempio:Notazione Big O per numeri triangolari?
func(x):
for i in 0..x
for j in 0..i
do_something(i, j)
Il mio primo istinto è O(n²), ma io non sono del tutto sicuro.
Sì, N * (N + 1)/2, quando si rilasciano le costanti e i termini di ordine inferiore, si lascia con N-al quadrato.
Sì, O(n^2) è decisamente corretto. Se ricordo correttamente, O è comunque sempre un limite superiore, quindi O(n^3) dovrebbe anche essere corretto, come lo sarebbe O(n^n) o qualsiasi altra cosa. Tuttavia, O(n^2) sembra il più stretto e facilmente deducibile.
Se ci pensi matematicamente, l'area del triangolo che stai calcolando è ((n+1)^2)/2. Questo è quindi il tempo di calcolo: O (((n + 1)^2)/2)
Il tempo di calcolo aumenta del fattore di N * (N + 1)/2 per questo codice. Questo è essenzialmente O (N^2).
quando aumenta ingresso da N a 2N quindi eseguendo tempo dell'algoritmo aumenterà da tt 4t
esecuzione così il tempo è proporzionale al quadrato della dimensione dell'input
così algoritmo è O (n^2)
O (! n) gestisce i casi per un calcolo fattoriale (tempo triangolare).
Può anche essere rappresentato come O (n^2) per me questo sembra essere un po 'fuorviante in quanto la quantità che viene eseguita sarà sempre la metà di O (n^2).
Per definizione, 'O (0.5 * n^2) == O (n^2)' (un'uguaglianza che vale per qualsiasi fattore costante diverso da zero, in effetti), quindi da una prospettiva strettamente teorica questo non è fuorviante. :-) – Gijs
-1. Un [Fattoriale] (http://en.wikipedia.org/wiki/Factorial) non è lo stesso di [numero triangolare] (http://en.wikipedia.org/wiki/Triangular_number). – gilly3
Hai ragione ... O ((n + 1) scegli 2) = O (n^2) per definizione. – Protostome