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

Question

siempre pensé que la complejidad de:

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

Pero hoy leo 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).

¿Qué me falta aquí?

Answer 1

El big O notation se puede utilizar para determinar la tasa de crecimiento de cualquier función.

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

Answer 2

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

Si agrega cada número uno a la vez, entonces es de hecho O (n). La fórmula es un atajo; es un algoritmo diferente y más eficiente. El acceso directo funciona cuando los números que se agregan son todos 1 .. n. Si tiene una secuencia de números no contigua, la fórmula de acceso directo no funciona y tendrá 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á agregando n^2 pares de números distintos para obtener una matriz de n^2 resultados.

Answer 3

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 de Big-oh!

Si pensó en él como una función, entonces el gran-oh complejidad de esta función es O (1):

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

La aplicación ingenua tendría grandes oh 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 sólo mirar a cada celda de una sola matriz n-por-n es O (n^2), ya que la matriz tiene n^2 células.

Answer 4

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, p. 1 + N = 2+ (N-1) = 3+ (N-2) = ... = N + 1. Entonces eso es N + 1, N/2 veces. (Si hay un número impar, uno de ellos será desemparejado, pero con un poco de esfuerzo puede ver que la misma fórmula se cumple 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) significa (aproximadamente) que el número de pasos para calcularlo crece como N^2, para N grande. En este caso, el número de pasos es el mismo independientemente de N.

Answer 5

Realmente no es una complejidad de un problema, sino más bien 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).

Answer 6

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

El tiempo de resumir, una tras otra en funcionamiento, los primeros n números consecutivos es de hecho O ( n).

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

---

Sin embargo, para un gran número arbitrariamente esto es simplista ya que la adición de grandes cantidades lleva más tiempo que la adición de pequeñas cantidades. Para un análisis de tiempo de ejecución preciso, de hecho, 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, al implementar una operación para una biblioteca bignum).

Answer 7

La respuesta de la suma de series de n natural se puede encontrar usando dos formas. La primera forma es agregar todos los números en el ciclo. en este caso el algoritmo es lineal y código serán 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 la operación de adición que es O (n).

segunda manera de encontrar la respuesta de la suma de series de n número natural es la fórmula más n * (n + 1)/2. esta fórmula usa multiplicación en lugar de suma repetitiva. la operación de multiplicación no tiene complejidad de tiempo lineal. 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 multiplicación, la complejidad del tiempo depende de la arquitectura del procesador. pero para el propósito del análisis, la complejidad del tiempo de la multiplicación se considera como O (N^2). por lo tanto, cuando uno usa la segunda manera de encontrar la suma, entonces la complejidad del tiempo será O (N^2).

aquí la operación de multiplicación no es lo mismo que la operación de suma. si alguien tiene conocimiento de la organización de la computadora sujeto, 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. entonces la complejidad del tiempo de la suma de series no puede ser constante.

Answer 8

así que yo creo que esto es realmente una referencia a Cracking the Coding Interview, que tiene el presente apartado StringBuffer aplicación:

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

Por alguna razón me pareció un poco confuso en mi primera lectura a través, también. Lo importante para ver es que n se está multiplicando n, o en otras palabras, que n² está sucediendo, y que domina. Esta es la razón por la que finalmente O(xn²) es solo O(n²) - el x es una especie de arenque rojo.