Somme prefissi in c ++
Ci sono dieci elementi. Immagina uno 0 che precede questo elenco.
Quindi 0 + 5 = 5, è la prima somma del prefisso.0 + 5 + 2 = 7 è la prossima somma del prefisso.
0 + 5 + 2 + -6 = 1 è la somma del prefisso dopo.
0 + 5 + 2 + -6 + 8 = 9 è la nuova somma del prefisso.
Questo totale in esecuzione in genere continua fino all'ultimo elemento, 7, nell'elenco dato. La seconda sequenza (elenco) ha le somme prefisso di undici elementi. Il primo elemento nell'array di somme prefisso (seconda sequenza) è lo zero ipotizzato (immaginato). Le seguenti due tabelle, in cui la seconda riga per ciascuna tabella ha gli indici dell'array basati su zero, illustrano queste due sequenze:
| Dato tavolo | ||||||||||
| 5 | 2 | -6 | 8 | -4 | 0 | 9 | 3 | -1 | 7 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| Tabella del prefisso somme | ||||||||||
| 5 | 7 | 1 | 9 | 5 | 5 | 14 | 17 | 16 | 23 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
La prima tabella è per l'array dato e la seconda tabella è per l'array di somme prefisso. Se il numero di elementi nell'array dato è n, il numero di elementi nell'array di somme prefissi è N+1. Questo articolo spiega le caratteristiche principali delle somme del prefisso. In questo contesto, "pre-" significa cosa è stato aggiunto prima. Può anche significare il prefisso dell'array prefisso con zero.
Forza bruta
Un programmatore dovrebbe conoscere il significato della forza bruta utilizzata nella programmazione. Forza bruta significa risolvere un problema usando un algoritmo diretto, che di solito non è così efficiente (per usare meno tempo e memoria) come un altro algoritmo accuratamente insegnato.
Prefisso somma dalla forza bruta
Al fine di produrre l'array di somme prefisso, per forza bruta, per l'array sopra dato, 5 verrà prima notato come la prima somma del prefisso. Quindi 5 e 2 verranno aggiunti per dare la prossima somma del prefisso, 7. Quindi 5, 2 e -6 verranno aggiunti per fornire la somma del prefisso dopo 1. Successivamente, 5, 2, -6 e 8 verranno aggiunti per dare la nuova somma del prefisso, 9 e così via. Questa procedura può essere stancante.
Stancante o no, il codice per produrre l'array di somma del prefisso, dal presunto zero, dalla forza bruta è:
int n = 10;int a [] = 5, 2, -6, 8, -4, 0, 9, 3, -1, 7;
int p [n+1];
P [0] = 0;
per (int i = 0; i
int j;
per (j = 0; j
P [j] = somma;
L'esterno per loop itera da 0 a meno di n. Il circuito interno per loop itera da 0 a i, l'indice di iterazione del loop esterno. Con questo, ci sono 55 operazioni principali. La complessità temporale per questo è O (n.tronco d'albero2N).
Prefisso somme in tempo lineare
La complessità temporale precedente è approssimativamente O (n.tronco d'albero2N). L'algoritmo può essere migliorato in modo tale che le somme siano prodotte in tempo lineare per la complessità del tempo, O (N). Il prefisso in questo contesto significa aggiungere la somma di tutti gli elementi precedenti all'elemento dato corrente. Considera le due precedenti tabelle, disegnate come una tabella, con alcune modifiche:
| Tabella del prefisso somme | ||||||||||
| Dato: | 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 |
La prima riga in questa tabella ha gli elementi indicati nelle posizioni assegnate. Per la seconda e la terza riga, si assume lo zero iniziale. Per la seconda e la terza riga, ogni elemento è uguale alla somma di tutti gli elementi precedenti, oltre all'elemento corrente. L'ultima riga ha gli indici di array di somme prefissi (basato su zero). Si noti che l'array di somme prefisso è un elemento più lungo dell'array dato.
Questo algoritmo produce l'array di somme prefisso in tempo lineare della complessità del tempo O (N). Cioè, ci sono circa N operazioni. E il codice di somma prefisso consigliato in C ++ per la complessità del tempo di O (N) è:
int n = 10;int a [] = 5, 2, -6, 8, -4, 0, 9, 3, -1, 7;
int p [n+1];
P [0] = 0;
per (int i = 1; i
Si noti che questa volta non esiste un ciclo nidificato. Le dichiarazioni all'interno delle parentesi del per loop sono essenziali. Anche il funzionamento principale del corpo per loop è importante. Come in precedenza, il per anello per loop itera da 1 a meno di N+1 e non da 0 a meno di N. L'affermazione del corpo per loop è:
P [i] = p [i-1] + a [i-1];Ciò significa che il valore corrente dell'array dato viene aggiunto alla somma prefisso precedente per fornire la somma del prefisso corrente.
Problema comune per somme al prefisso
Si noti che l'indice corrispondente dell'array di somme prefisso ne ha 1 aggiunto rispetto a quello dell'array dato.
Un problema comune per le somme prefisso è trovare in modo efficiente la somma di un sotto-array di elementi consecutivi. Questa è la somma di una fetta. La parola "in modo efficiente" significa che non deve essere usato un algoritmo di forza bruta. Gli indici limitanti per il sotto-array sono xey. Considera l'elenco indicato:
5, 2, -6, 8, -4, 0, 9, 3, -1, 7La somma del sotto-array dall'elemento 8 all'elemento 9 è:
8 + -4 + 0 + 9 = 138 è all'indice 3, per x; e 9 è all'indice 6 per y. Il modo efficiente per farlo è sottrarre la somma del prefisso all'indice 2, per l'array dato, dalla somma del prefisso all'indice 6 per l'array dato. Per l'array prefisso, questi sono indice y+1 e indice x. Il 1 da aggiungere viene rimosso per ottenere l'indice dell'array prefisso, mostrato di seguito, e il codice efficiente è:
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;
per (int i = 1; i
int siosum = p [y+1] - p [x];
cout<
Conclusione
Le somme al prefisso sono i totali in esecuzione degli elementi di un array. Sono coinvolti due array: l'array dato e il prefisso prodotto Array. L'array di somme prefisso è più lungo dell'array dato da un elemento. L'operazione principale per ottenere gli elementi dell'array prefisso è: il valore corrente nell'array di somme prefisso è la somma prefisso precedente, oltre al valore corrente dell'array dato. Per ottenere la somma di una fetta dall'array dato, usa: int secchi = p [y+1] - p [x];
Dove x è l'indice di limite inferiore della fetta nell'array dato e y è l'indice limite superiore della fetta nell'array dato.