¿Cuál es la notación O correcta correcta para un algoritmo que se ejecuta en triangular vez? He aquí un ejemplo:notación Big O para números triangulares?
func(x):
for i in 0..x
for j in 0..i
do_something(i, j)
Mi primer instinto es O(n²), pero no estoy del todo seguro.
Sí, N * (N + 1)/2, cuando suelta las constantes y los términos de orden inferior, lo deja con N-cuadrado.
Sí, O(n^2) es definitivamente correcto. Si recuerdo correctamente, O siempre es un límite superior, por lo que O(n^3) también debería ser correcto, como lo sería O(n^n) o lo que sea. Sin embargo, O(n^2) parece ser el más ajustado que es fácilmente deducible.
Si lo piensas matemáticamente, el área del triángulo que estás calculando es ((n+1)^2)/2. Por lo tanto, este es el tiempo de cálculo: O (((n + 1)^2)/2)
El tiempo de cálculo aumenta por el factor de N * (N + 1)/2 para este código. Esto es esencialmente O (N^2).
cuando la entrada se incrementa de N a 2N entonces el tiempo de funcionamiento de su algoritmo aumentará de t a 4t
corriendo así el tiempo es proporcional al cuadrado de la magnitud de entrada
así algoritmo es O (n^2)
O (! n) maneja casos para un cálculo factorial (tiempo triangular).
También se puede representar como O (n^2) para mí, esto parece ser un poco engañoso ya que la cantidad que se está ejecutando siempre será la mitad que O (n^2).
Por definición, 'O (0.5 * n^2) == O (n^2)' (una igualdad que vale para cualquier factor constante distinto de cero, de hecho), así que desde una perspectiva estrictamente teórica esto no es engañoso. :-) – Gijs
-1. Un [Factorial] (http://en.wikipedia.org/wiki/Factorial) no es lo mismo que un [número triangular] (http://en.wikipedia.org/wiki/Triangular_number). – gilly3
Tiene razón ... O ((n + 1) elija 2) = O (n^2) por definición. – Protostome