performance - ejemplo - Big O, ¿cuál es la complejidad de sumar una serie de n números?

ejemplo de big o (8)

Entonces, supongo que esto es en realidad una referencia a Cracking the Coding Interview , que tiene este párrafo en una implementación de StringBuffer :

En cada concatenación, se crea una nueva copia de la cadena, y las dos cadenas se copian, carácter por carácter. La primera iteración requiere que copiemos x caracteres. La segunda iteración requiere copiar 2x caracteres. La tercera iteración requiere 3x , y así sucesivamente. Por lo tanto, el tiempo total es O(x + 2x + ... + nx) . Esto se reduce a O(xn²) . (¿Por qué no es O(xnⁿ) ? Porque 1 + 2 + ... n es igual a n(n+1)/2 o, O(n²) .)

Por la razón que sea, también encontré esto un poco confuso en mi primera lectura. Lo importante que hay que ver es que n está multiplicando n , o en otras palabras, que n² está sucediendo y que domina. Esta es la razón por la que, en última instancia, O(xn²) es solo O(n²) : la x es una especie de O(xn²) falsa.

Siempre pensé en la complejidad de:

1 + 2 + 3 + ... + n es O (n), y sumar dos matrices n por n sería O (n ^ 2).

Pero hoy leí de un libro de texto, "por la fórmula para la suma de los primeros n enteros, esto es n (n + 1) / 2" y luego, así: (1/2) n ^ 2 + (1/2) n, y por lo tanto O (n ^ 2).

¿Que me estoy perdiendo aqui?

Está confundiendo la complejidad del tiempo de ejecución y el tamaño (complejidad) del resultado .

El tiempo de ejecución de la suma, uno después del otro, los primeros n números consecutivos es de hecho O ( n ). ¹

Pero la complejidad del resultado, que es el tamaño de "suma de 1 a n " = n ( n - 1) / 2 es O ( n ^ 2).

¹ Pero para números arbitrariamente grandes, esto es simplista ya que agregar números grandes lleva más tiempo que agregar números pequeños. Para un análisis preciso del tiempo de ejecución, debe considerar el tamaño del resultado. Sin embargo, esto no suele ser relevante en la programación, ni siquiera en la informática puramente teórica. En ambos dominios, la suma de números generalmente se considera una operación O (1) a menos que el dominio lo requiera explícitamente (es decir, cuando se implementa una operación para una biblioteca bignum).

Hay una diferencia entre sumar N enteros arbitrarios y sumar N que están todos en una fila. Para 1 + 2 + 3 + 4 + ... + N, puede aprovechar el hecho de que se pueden dividir en pares con una suma común, por ejemplo, 1 + N = 2+ (N-1) = 3+ ( N-2) = ... = N + 1. Así que eso es N + 1, N / 2 veces. (Si hay un número impar, uno de ellos no estará emparejado, pero con un poco de esfuerzo podrá ver que la misma fórmula es válida en ese caso).

Eso no es O (N ^ 2), sin embargo. Es solo una fórmula que usa N ^ 2, en realidad O (1). O (N ^ 2) significaría (aproximadamente) que el número de pasos para calcularlo crece como N ^ 2, para un N grande. En este caso, el número de pasos es el mismo independientemente de N.

La notación O grande se puede utilizar para determinar la tasa de crecimiento de cualquier función.

En este caso, parece que el libro no habla de la complejidad del tiempo de cálculo del valor, sino del valor en sí. Y n(n+1)/2 es O(n^2) .

La respuesta de la suma de las series de n natural se puede encontrar de dos maneras. La primera forma es sumando todos los números en bucle. En este caso, el algoritmo es lineal y el código será así.

int sum = 0; for (int i = 1; i <= n; i++) { sum += n; } return sum;

es análogo a 1 + 2 + 3 + 4 + ...... + n. en este caso, la complejidad del algoritmo se calcula como el número de veces que se realiza una operación de adición, que es O (n).

La segunda forma de encontrar la respuesta de la suma de las series de n número natural es la fórmula más directa n * (n + 1) / 2. Esta fórmula utiliza la multiplicación en lugar de la suma repetitiva. La operación de multiplicación no tiene complejidad lineal de tiempo. hay varios algoritmos disponibles para la multiplicación que tienen una complejidad de tiempo que va desde O (N ^ 1.45) a O (N ^ 2). por lo tanto, en caso de tiempo de multiplicación, la complejidad depende de la arquitectura del procesador. pero para el propósito de análisis, la complejidad de tiempo de la multiplicación se considera O (N ^ 2). por lo tanto, cuando se usa una segunda forma para encontrar la suma, entonces la complejidad del tiempo será O (N ^ 2).

Aquí la operación de multiplicación no es la misma que la operación de suma. Si alguien tiene conocimiento de la organización de la computadora, entonces puede entender fácilmente el funcionamiento interno de la operación de multiplicación y suma. El circuito de multiplicación es más complejo que el circuito sumador y requiere mucho más tiempo que el circuito sumador para calcular el resultado. así que la complejidad del tiempo de la suma de las series no puede ser constante.

Realmente no hay una complejidad de un problema, sino una complejidad de un algoritmo.

En su caso, si elige iterar a través de todos los números, la complejidad es, de hecho, O(n) .

Pero ese no es el algoritmo más eficiente. Una más eficiente es aplicar la fórmula - n*(n+1)/2 , que es constante, y por lo tanto la complejidad es O(1) .

Tiene una fórmula que no depende de la cantidad de números que se agregan, por lo que es un algoritmo de tiempo constante , o O (1).

Si sumas cada número uno a la vez, entonces es O (n). La fórmula es un atajo; Es un algoritmo diferente, más eficiente. El acceso directo funciona cuando los números que se agregan son todos 1 .. n . Si tienes una secuencia de números no contiguos, entonces la fórmula de acceso directo no funciona y tendrás que volver al algoritmo de uno por uno.

Sin embargo, nada de esto se aplica a la matriz de números. Para agregar dos matrices, sigue siendo O (n ^ 2) porque estás agregando n ^ 2 pares de números distintos para obtener una matriz de n ^ 2 resultados.

n (n + 1) / 2 es la forma rápida de sumar una secuencia consecutiva de N enteros (comenzando desde 1). ¡Creo que estás confundiendo un algoritmo con notación grande-oh!

Si pensaste en esto como una función, entonces la complejidad de esta función es O (1):

public int sum_of_first_n_integers(int n) { return (n * (n+1))/2; }

La implementación ingenua tendría una gran complejidad de O (n).

public int sum_of_first_n_integers(int n) { int sum = 0; for (int i = 1; i <= n; i++) { sum += n; } return sum; }

Incluso solo mirando a cada celda de una matriz n por n es O (n ^ 2), ya que la matriz tiene n ^ 2 celdas.