Prefijo sumas en C ++

Las sumas de prefijo son los totales de los números de una matriz. Es otra secuencia completa de números. Por ejemplo, considere la siguiente lista: 5, 2, -6, 8, -4, 0, 9, 3, -1, 7

Hay diez elementos. Imagina un 0 que precede a esta lista.

Entonces 0 + 5 = 5, es la primera suma de prefijo.
0 + 5 + 2 = 7 es la siguiente suma de prefijo.
0 + 5 + 2 + -6 = 1 es la suma de prefijo después.
0 + 5 + 2 + -6 + 8 = 9 es la nueva suma de prefijo.

Este total de ejecución generalmente continúa hasta el último elemento, 7, en la lista dada. La segunda secuencia (lista) tiene las sumas de prefijo de once elementos. El primer elemento en la matriz de sumas de prefijo (segunda secuencia) es el cero asumido (imaginado). Las siguientes dos tablas, donde la segunda fila para cada tabla tiene los índices de matriz basados ​​en cero, ilustran estas dos secuencias:

Mesa dada
	5	2	-6	8	-4	0	9	3	-1	7
	0	1	2	3	4	5	6	7	8	9

Tabla de sumas de prefijo
	5	7	1	9	5	5	14	17	dieciséis	23
0	1	2	3	4	5	6	7	8	9	10

La primera tabla es para la matriz dada y la segunda tabla es para la matriz de sumas de prefijo. Si el número de elementos en la matriz dada es n, entonces el número de elementos en la matriz de sumas de prefijo es n+1. Este artículo explica las características principales de las sumas de prefijo. En este contexto, "pre-" significa lo que se ha agregado antes. También puede significar prefijo la matriz de prefijo con cero.

Fuerza bruta

Un programador debe conocer el significado de la fuerza bruta como se usa en la programación. La fuerza bruta significa resolver un problema usando un algoritmo directo, que generalmente no es tan eficiente (para usar menos tiempo y memoria) como otro algoritmo cuidadosamente enseñado.

Suma de prefijo de la fuerza bruta

Para producir la matriz de sumas de prefijo, por fuerza bruta, para la matriz anterior, 5 se observará primero como la primera suma de prefijo. Luego se agregarán 5 y 2 para dar la próxima suma de prefijo, 7. Luego se agregarán 5, 2 y -6 para proporcionar la suma del prefijo después de 1. A continuación, se agregarán 5, 2, -6 y 8 para dar la nueva suma de prefijo, 9, etc. Este procedimiento puede ser agotador.

Agotador o no, el código para producir la matriz de suma de prefijo, desde el cero asumido, por fuerza bruta es:

int n = 10;
int a [] = 5, 2, -6, 8, -4, 0, 9, 3, -1, 7;
int p [n+1];
P [0] = 0;
para (int i = 0; iint sum = 0;
int j;
para (j = 0; jsum = suma + a [j];

P [j] = suma;

El bucle for-bucle externo de 0 a solo menos de n. El bucle interno itera de 0 a i, el índice de iteración del bucle exterior. Con esto, hay 55 operaciones principales. La complejidad del tiempo para esto es o (n.registro₂norte).

Sumas de prefijo en tiempo lineal

La complejidad del tiempo anterior es aproximadamente o (n.registro₂norte). El algoritmo se puede mejorar de tal manera que las sumas se producen en tiempo lineal para la complejidad del tiempo, o (n). Prefijo en este contexto significa agregar la suma de todos los elementos anteriores al elemento actual dado. Considere las dos tablas anteriores, dibujadas como una tabla, con algunas modificaciones:

Tabla de sumas de prefijo
Dado:	5	2	-6	8	-4	0	9	3	-1	7
	0 + 5 =	5 + 2 =	7 + -6 =	1 + 8 =	9 + -4 =	5 + 0 =	5 + 9 =	14+3 =	17+ -1 =	16+7 =
0	5	7	1	9	5	5	14	17	dieciséis	23
0	1	2	3	4	5	6	7	8	9	10

La primera fila en esta tabla tiene los elementos dados en sus posiciones asignadas. Para la segunda y tercera filas, se supone el cero inicial. Para la segunda y tercera filas, cada elemento es igual a la suma de todos los elementos anteriores, más el elemento actual. La última fila tiene los índices de matriz de sumas de prefijo (basados ​​en cero). Tenga en cuenta que la matriz de sumas de prefijo es un elemento más largo que la matriz dada.

Este algoritmo produce la matriz de sumas de prefijo en tiempo lineal de complejidad de tiempo o (n). Es decir, hay aproximadamente n operaciones. Y el código de suma de prefijo recomendado en C ++ para la complejidad del tiempo O (n) es:

int n = 10;
int a [] = 5, 2, -6, 8, -4, 0, 9, 3, -1, 7;
int p [n+1];
P [0] = 0;
para (int i = 1; iP [i] = p [i-1] + a [i-1];

Observe que esta vez no hay bucle anidado. Las declaraciones dentro de los paréntesis del for-bucle son esenciales. La operación principal del cuerpo del bucle también es importante. Como antes, el bucle for-loop itera de 1 a menos de n+1 y no de 0 a menos de n. La declaración del cuerpo for-bucle es:

P [i] = p [i-1] + a [i-1];

Esto significa que el valor actual de la matriz dada se agrega a la suma de prefijo anterior para proporcionar la suma de prefijo actual.

Problema común para sumas de prefijo

Observe que el índice correspondiente de la matriz de sumas de prefijo se ha agregado 1 en comparación con el de la matriz dada.

Un problema común para las sumas de prefijo es encontrar la suma de un subrainal de elementos consecutivos de manera eficiente. Esta es la suma de una porción. La palabra "eficientemente" significa que no se debe usar un algoritmo de fuerza bruta. Los índices limitantes para la subarray son x e y. Considere la lista dada:

5, 2, -6, 8, -4, 0, 9, 3, -1, 7

La suma de la subarray del elemento 8 al elemento 9 es:

8 + -4 + 0 + 9 = 13

8 está en el índice 3, para x; y 9 está en el índice 6 para y. La forma eficiente de hacerlo es restar la suma de prefijo en el índice 2, para la matriz dada, de la suma de prefijo en el índice 6 para la matriz dada. Para la matriz de prefijo, estos son índice Y+1 e índice x. El 1 a agregar se elimina para obtener el índice de matriz de prefijo, que se muestra a continuación, y el código eficiente es:

int n = 10;
int a [] = 5, 2, -6, 8, -4, 0, 9, 3, -1, 7;
int p [n+1];
P [0] = 0;
int x = 3, y = 6;
para (int i = 1; iP [i] = p [i-1] + a [i-1];

int slicesum = p [y+1] - p [x];
cout<La salida es 13, como se esperaba, pero desde un código eficiente.

Conclusión

Las sumas de prefijo son los totales de los elementos de una matriz. Están involucradas dos matrices: la matriz dada y la matriz de sumas de prefijo producidas. La matriz de sumas de prefijo es más larga que la matriz dada por un elemento. La operación principal para obtener los elementos de la matriz de prefijo es: el valor actual en la matriz de sumas de prefijo es la suma de prefijo anterior, más el valor actual de la matriz dada. Para obtener la suma de una porción de la matriz dada, use: int slicesum = p [y+1] - p [x];

Donde x es el índice de límite inferior de la porción en la matriz dada, e y es el índice de límite superior de la porción en la matriz dada.