formula - ¿Cuál es la prueba de(N – 1)+(N – 2)+(N – 3)+…+1=N*(N – 1)/2
proof (9)
Obtuve esta fórmula de un libro de estructura de datos en el algoritmo de clasificación de burbujas.
Sé que somos (n-1) * (n veces), pero ¿por qué la división por 2?
¿Puede alguien explicarme esto o darme la prueba detallada?
Gracias
Sé que somos (n-1) * (n veces), pero ¿por qué la división por 2?
Es solo (n - 1) * n si usas una burbuja de burbujas ingenua. Puede obtener un ahorro significativo si observa lo siguiente:
Después de cada comparación e intercambio, el elemento más grande que haya encontrado estará en el último lugar en el que estuvo.
Después de la primera pasada, el elemento más grande estará en la última posición; después del paso k th , el elemento k th más grande estará en la k th última posición.
Por lo tanto, no tiene que ordenar todo el asunto cada vez: solo necesita ordenar n - 2 elementos la segunda vez, n - 3 elementos la tercera vez, y así sucesivamente. Eso significa que el número total de comparaciones / swaps que tienes que hacer es (n - 1) + (n - 2) + ... Esta es una serie aritmética , y la ecuación para el número total de veces es (n - 1) * n / 2.
Ejemplo: si el tamaño de la lista es N = 5, entonces hace 4 + 3 + 2 + 1 = 10 swaps, y observa que 10 es lo mismo que 4 * 5/2.
Aquí hay una prueba por inducción, considerando los términos de N , pero es lo mismo para N - 1 :
Para N = 0 la fórmula es obviamente verdadera.
Supongamos que 1 + 2 + 3 + ... + N = N(N + 1) / 2 es cierto para algunos N naturales.
Demostraremos que 1 + 2 + 3 + ... + N + (N + 1) = (N + 1)(N + 2) / 2 también es cierto al usar nuestro supuesto anterior:
1 + 2 + 3 + ... + N + (N + 1) = (N(N + 1) / 2) + (N + 1) = (N + 1)((N / 2) + 1) = (N + 1)(N + 2) / 2 .
Así que la fórmula se mantiene para todo N
Empieza con el triángulo ...
*
**
***
****
representando 1 + 2 + 3 + 4 hasta ahora. Cortar el triángulo por la mitad a lo largo de una dimensión ...
*
**
* **
** **
Gire la parte más pequeña 180 grados y péguela sobre la parte más grande ...
**
*
*
**
**
**
Cerrar la brecha para obtener un rectángulo.
A primera vista, esto solo funciona si la base del rectángulo tiene una longitud uniforme, pero si tiene una longitud impar, simplemente corta la columna del medio a la mitad; todavía funciona con una media unidad de ancho dos veces más alto ( todavía área entera) tira en un lado de su rectángulo.
Cualquiera que sea la base del triángulo, el ancho de su rectángulo es (base / 2) y la altura es (base + 1) , dando ((base + 1) * base) / 2 .
Sin embargo, mi base es su n-1 , ya que la ordenación de las burbujas compara un par de elementos a la vez y, por lo tanto, itera solo en las posiciones (n-1) del primer bucle.
Esta es una prueba bastante común. Una forma de demostrar esto es usar la inducción matemática. Aquí hay un enlace: http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html
Intenta hacer pares de números del conjunto. Lo primero + lo último; el segundo + el anterior al último. Significa n-1 + 1; n-2 + 2. El resultado es siempre n. Y como están sumando dos números, solo se pueden hacer pares (n-1) / 2 a partir de números (n-1).
Así que es como (N-1) / 2 * N.
Suma de progresión aritmética.
(A1 + AN) / 2 * N = (1 + (N-1)) / 2 * (N-1) = N * (N-1) / 2
Supongamos que n = 2. Entonces tenemos 2-1 = 1 en el lado izquierdo y 2 * 1/2 = 1 en el lado derecho.
Denote f (n) = (n-1) + (n-2) + (n-3) + ... + 1
Ahora supongamos que hemos probado hasta n = k. Entonces tenemos que probar para n = k + 1.
en el lado izquierdo tenemos k + (k-1) + (k-2) + ... + 1, así que es f (k) + k
En el lado derecho tenemos entonces (k + 1) * k / 2 = (k ^ 2 + k) / 2 = (k ^ 2 + 2k - k) / 2 = k + (k-1) k / 2 = k f (k)
Entonces esto tiene que mantenerse para cada k, y esto concluye la prueba.
Ver los números del triángulo .
(N-1) + (N-2) +...+ 2 + 1 es una suma de N-1 elementos. Ahora reordene los elementos para que después de lo primero venga el último, luego el segundo, luego el segundo para durar, es decir (N-1) + 1 + (N-2) + 2 +.. La forma en que se ordenan los elementos ahora puede ver que cada uno de esos pares es igual a N (N-1 + 1 es N, N-2 + 2 es N). Como hay elementos N-1, hay (N-1) / 2 pares. Entonces, está agregando N (N-1) / 2 veces, por lo que el valor total es N*(N-1)/2 .