Prefikset summer i C ++
Det er ti elementer. Se for deg en 0 som går foran denne listen.
Da 0 + 5 = 5, er den første prefikset sum.0 + 5 + 2 = 7 er neste prefiks -sum.
0 + 5 + 2 + -6 = 1 er prefikset sum etter.
0 + 5 + 2 + -6 + 8 = 9 er den nye prefiks -summen.
Denne løpende totalen fortsetter typisk til det siste elementet, 7, i den gitte listen. Den andre sekvensen (listen) har prefikset av elleve elementer. Det første elementet i prefikset summerer (andre sekvens) er den antatte (forestilte) null. Følgende to tabeller, der den andre raden for hver tabell har de nullbaserte arrayindeksene, illustrerer disse to sekvensene:
| Gitt tabell | ||||||||||
| 5 | 2 | -6 | 8 | -4 | 0 | 9 | 3 | -1 | 7 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| Prefiks summer tabell | ||||||||||
| 5 | 7 | 1 | 9 | 5 | 5 | 14 | 17 | 16 | 23 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Den første tabellen er for den gitte matrisen, og den andre tabellen er for prefikset summer -matrisen. Hvis antallet elementer i den gitte matrisen er n, er antall elementer i prefikset summer -matrisen n+1. Denne artikkelen forklarer hovedfunksjonene i prefikset. I denne sammenhengen betyr "pre-" det som er lagt til før. Det kan også bety prefiksing av prefikset med null.
Ren styrke
En programmerer skal kjenne betydningen av brute force som brukt i programmering. Brute Force betyr å løse et problem ved å bruke en direkte algoritme, som vanligvis ikke er like effektiv (for å bruke mindre tid og minne) som en annen nøye lært algoritme.
Prefiks sum av brute force
For å produsere prefikset summerer matrise, med brute force, for den ovennevnte matrisen, vil 5 først bli notert som den første prefiks-summen. Deretter vil 5 og 2 bli lagt til for å gi neste prefiks -sum, 7. Deretter vil 5, 2 og -6 bli lagt til for å gi prefiks sum etter 1. Neste, 5, 2, -6 og 8 vil bli lagt til for å gi den nye prefiks -summen, 9, og så videre. Denne prosedyren kan være slitsomme.
Slitsom eller ikke, koden for å produsere prefikset sum -matrisen, fra antatt null, med brute force er:
int n = 10;int a [] = 5, 2, -6, 8, -4, 0, 9, 3, -1, 7;
int p [n+1];
P [0] = 0;
for (int i = 0; i
int j;
for (j = 0; j
P [j] = sum;
Ytre for-loop itererer fra 0 til bare mindre enn n. Den indre for-loopen itererer fra 0 til i, iterasjonsindeksen for den ytre sløyfen. Med dette er det 55 hovedoperasjoner. Tidskompleksiteten for dette er o (n.Logg2n).
Prefikset summerer i lineær tid
Forrige tidskompleksitet er omtrent o (n.Logg2n). Algoritmen kan forbedres slik at summen produseres i lineær tid for tidskompleksitet, O (n). Prefiks i denne sammenhengen betyr å legge til summen av alle de tidligere elementene til det nåværende gitte elementet. Tenk på de to foregående tabellene, tegnet som en tabell, med noen modifikasjoner:
| Prefiks summer tabell | ||||||||||
| Gitt: | 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 | 10 |
Den første raden i denne tabellen har de gitte elementene i sine tildelte stillinger. For andre og tredje rad antas startnullet. For andre og tredje rad er hvert element lik summen av alle de tidligere elementene, pluss det nåværende elementet. Den siste raden har prefikset summer-indekser (nullbasert). Merk at prefikset summerer array er ett element lenger enn den gitte matrisen.
Denne algoritmen produserer prefikset summerer i lineær tid for O (n) tidskompleksitet. Det vil si at det er omtrent n operasjoner. Og den anbefalte prefikset sumkoden i C ++ for o (n) tidskompleksitet er:
int n = 10;int a [] = 5, 2, -6, 8, -4, 0, 9, 3, -1, 7;
int p [n+1];
P [0] = 0;
for (int i = 1; i
Legg merke til at det ikke er noen nestet sløyfe denne gangen. Uttalelsene inne i parentesene til for-loopen er essensielle. Hovedoperasjonen av for-loop-kroppen er også viktig. Som før itererer for-loopen fra 1 til mindre enn n+1 og ikke fra 0 til mindre enn n. Uttalelsen fra for-loop-organet er:
P [i] = p [i-1] + a [i-1];Dette betyr at den nåværende verdien av den gitte matrisen legges til den forrige prefikset sum for å gi den nåværende prefikset sum.
Vanlig problem for prefikset
Legg merke til at den tilsvarende indeksen for prefikset summer -arrayen har 1 lagt til den sammenlignet med den av den gitte matrisen.
Et vanlig problem for prefiks-summer er å finne summen av en underoppdrag av påfølgende elementer effektivt. Dette er summen av en skive. Ordet "effektivt" betyr at en brute force -algoritme ikke skal brukes. De begrensende indeksene for underarrangen er x og y. Tenk på den gitte listen:
5, 2, -6, 8, -4, 0, 9, 3, -1, 7Summen av underarrangen fra element 8 til element 9 er:
8 + -4 + 0 + 9 = 138 er ved indeks 3, for x; og 9 er ved indeks 6 for y. Den effektive måten å gjøre dette på er å trekke prefikset sum ved indeks 2, for den gitte matrisen, fra prefikset sum ved indeks 6 for den gitte matrisen. For prefiks -matrisen er dette indeks y+1 og indeks x. 1 som skal legges til, fjernes for å få prefiks -arrayindeksen, vist nedenfor, og den effektive koden er:
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;
for (int i = 1; i
int skiver = p [y+1] - p [x];
cout<
Konklusjon
Prefikset summer er de løpende totalen av elementene i en matrise. To matriser er involvert: den gitte matrisen og den produserte prefikset. Prefikset summerer er lengre enn den gitte matrisen med ett element. Hovedoperasjonen for å oppnå elementene i prefiks -matrisen er: Den nåværende verdien i prefikset summerer er den forrige prefiks -summen, pluss den nåværende verdien av den gitte matrisen. For å få summen av en skive fra den gitte matrisen, bruk: int skiver = p [y+1] - p [x];
Der x er den nedre grenseindeksen for skiven i den gitte matrisen, og y er den øvre grenseindeksen til skiven i den gitte matrisen.