Préfixe Sums en C ++

Les sommets du préfixe sont les totaux de course des nombres d'un tableau. C'est une autre séquence complète de nombres. Par exemple, considérez la liste suivante: 5, 2, -6, 8, -4, 0, 9, 3, -1, 7

Il y a dix éléments. Imaginez un 0 qui précède cette liste.

Alors 0 + 5 = 5, est la première somme préfixe.
0 + 5 + 2 = 7 est la somme du préfixe suivant.
0 + 5 + 2 + -6 = 1 est la somme du préfixe après.
0 + 5 + 2 + -6 + 8 = 9 est la nouvelle somme de préfixe.

Ce total de course continue généralement jusqu'au dernier élément, 7, dans la liste donnée. La deuxième séquence (liste) a les sommes préfixes de onze éléments. Le premier élément du tableau des sommets du préfixe (deuxième séquence) est le zéro supposé (imaginé). Les deux tables suivantes, où la deuxième ligne pour chaque table a les index de tableau basés sur zéro, illustrent ces deux séquences:

Table donnée
	5	2	-6	8	-4	0	9	3	-1	7
	0	1	2	3	4	5	6	7	8	9

Table des sommets du préfixe
	5	7	1	9	5	5	14	17	16	23
0	1	2	3	4	5	6	7	8	9	dix

Le premier tableau est pour le tableau donné et le deuxième tableau est pour le tableau des sommets du préfixe. Si le nombre d'éléments dans le tableau donné est n, alors le nombre d'éléments dans le tableau des sommets du préfixe est n + 1. Cet article explique les principales caractéristiques des sommes préfixes. Dans ce contexte, «pré-» signifie ce qui a été ajouté auparavant. Cela peut également signifier préfixer le tableau de préfixe avec zéro.

Force brute

Un programmeur devrait connaître la signification de la force brute telle qu'elle est utilisée dans la programmation. La force brute signifie résoudre un problème en utilisant un algorithme direct, qui n'est généralement pas aussi efficace (pour utiliser moins de temps et de mémoire) comme un autre algorithme soigneusement enseigné.

Somme préfixe par force brute

Afin de produire le tableau des sommets de préfixe, par force brute, pour le tableau ci-dessus, 5 sera d'abord noté comme la première somme préfixe. Alors 5 et 2 seront ajoutés pour donner la somme du préfixe suivant, 7. Alors 5, 2 et -6 seront ajoutés pour fournir la somme du préfixe après 1. Ensuite, 5, 2, -6 et 8 seront ajoutés pour donner la nouvelle somme du préfixe, 9, etc. Cette procédure peut être fatigante.

Tiring ou non, le code pour produire le tableau de somme préfixe, du zéro supposé, par force brute est:

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

P [j] = sum;

La boucle externe itéère de 0 à un peu moins de n. La boucle intérieure itère de 0 à I, l'indice d'itération de la boucle extérieure. Avec cela, il y a 55 opérations principales. La complexité du temps pour cela est o (n.enregistrer₂n).

SUMS PRÉFIQUES EN TEMPS LINÉAR

La complexité de temps précédente est approximativement O (n.enregistrer₂n). L'algorithme peut être amélioré de sorte que les sommes sont produites en temps linéaire pour la complexité temporelle, O (n). Le préfixe dans ce contexte signifie ajouter la somme de tous les éléments précédents à l'élément actuel donné. Considérez les deux tables précédentes, dessinées comme une seule table, avec quelques modifications:

Table des sommets du préfixe
Donné:	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	16	23
0	1	2	3	4	5	6	7	8	9	dix

La première ligne de ce tableau a les éléments donnés à leurs positions assignées. Pour les deuxième et troisième rangées, le zéro de départ est supposé. Pour les deuxième et troisième lignes, chaque élément est égal à la somme de tous les éléments précédents, plus l'élément actuel. La dernière ligne a les index de tableau des sommets du préfixe (basé sur zéro). Notez que le tableau de somme préfixe est un élément plus long que le tableau donné.

Cet algorithme produit le tableau des sommets du préfixe en temps linéaire de la complexité du temps O (n). C'est-à-dire qu'il y a environ n opérations. Et le code de somme préfixe recommandé en C ++ pour la complexité du temps O (n) est:

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

Notez qu'il n'y a pas de boucle imbriquée cette fois. Les déclarations à l'intérieur des parenthèses de la boucle pour. Le fonctionnement principal du corps en boucle à forage est également important. Comme précédemment, la boucle iditère de 1 à moins de n + 1 et non de 0 à moins de n. L'énoncé du corps en boucle à forte boucle est:

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

Cela signifie que la valeur actuelle du tableau donné est ajoutée à la somme préfixe précédente pour fournir la somme du préfixe actuel.

Problème commun pour les sommes préfixes

Notez que l'indice correspondant du tableau des sommets du préfixe y a 1 ajouté par rapport à celui du tableau donné.

Un problème commun pour les sommes préfixes est de trouver efficacement la somme d'un sous-tableau d'éléments consécutifs. C'est la somme d'une tranche. Le mot «efficacement» signifie qu'un algorithme de force brute ne doit pas être utilisé. Les index limitants pour les sous-tableaux sont X et Y. Considérez la liste donnée:

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

La somme du sous-tableau de l'élément 8 à l'élément 9 est:

8 + -4 + 0 + 9 = 13

8 est à l'index 3, pour x; et 9 est à l'index 6 pour y. La façon efficace de le faire est de soustraire la somme du préfixe à l'index 2, pour le tableau donné, de la somme du préfixe à l'index 6 pour le tableau donné. Pour le tableau de préfixe, il s'agit d'index Y + 1 et d'index x. Le 1 à ajouter est supprimé pour obtenir l'index du tableau préfixe, illustré ci-dessous, et le code efficace est:

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;
pour (int i = 1; iP [i] = p [i-1] + a [i-1];

int slicesum = p [y + 1] - p [x];
couter<La sortie est de 13, comme prévu, mais à partir d'un code efficace.

Conclusion

Les sommets du préfixe sont les totaux de course des éléments d'un tableau. Deux tableaux sont impliqués: le tableau donné et le tableau de préfixe produit. Le tableau des sommets de préfixe est plus long que le tableau donné par un élément. L'opération principale pour obtenir les éléments du tableau de préfixe est: la valeur actuelle dans le tableau des sommets du préfixe est la somme préfixe précédente, plus la valeur actuelle du tableau donné. Pour obtenir la somme d'une tranche du tableau donné, utilisez: int slicesum = p [y + 1] - p [x];

Où x est l'indice de limite inférieure de la tranche dans le tableau donné, et y est l'indice de limite supérieure de la tranche dans le tableau donné.