Maximale Teilsequenz- und Algorithmusanalyse

Problembeschreibung: Gegeben n ganzzahlige Folgen {a1, a2,...,an}, finden Sie die Funktion f(i,j)=max{0,Σa_k} (k: stetig von i bis j);

Das Problem besteht darin, den Maximalwert der Summe aufeinanderfolgender Unterspalten zu finden. Wenn der Maximalwert eine negative Zahl ist, nehmen Sie 0, z. B. die 8er-Zahlenfolge {-1, 2, -3 ,4,-2,5,-8,3}, die maximale Teilsequenzsumme von Namo beträgt 4 (-2) 5=7.

Dieses Problem hat vier Algorithmus mit unterschiedlicher Komplexität, die zeitliche Komplexität der Algorithmen 1 bis 4 beträgt O(n³), O(n²), O(nlogn), O(n);

Algorithmus 1:

Die direkteste Methode ist die erschöpfende Methode. Wir können das linke Ende i und das rechte Ende j der Teilsequenz festlegen und dann eine Ebene verwenden, um a[i ] zur Summe von a[j].

//Maximale Unterspalte und erschöpfende Methode
#include
using namespace std;
int Find_Maxsun(int*a, int n ) ;
int main(){
int n, i;
int a[100];
cin >> n;
cout << << n << "Nummer:" << endl;
für (i = 0; i < n; i )
cout< return 0;
}
int Find_Maxsun(int*a, int n){
int MaxSun = 0, i , j, k;
int NowSum;
for (i = 0; i < n; i ) /*linkes Ende der Teilsequenz*/
for (j = 0; j < n; j ){ /*Rechtes Ende der Teilsequenz*/
NowSum = 0;
for (k = i; k <= j; k )
NowSum = a[k]; /*From a[i ] zu einer Teilfolge von [j]*/
if (NowSum>MaxSun)
MaxSun = NowSum; /*Update result*/
}
return MaxSun;
}

Offensichtlich verwendet die Brute-Force-Methode drei for-Schleifen, und die Zeitkomplexität des Algorithmus beträgt O(n

3^{). Dies ist natürlich der dümmste Algorithmus, aber wenn die Daten sehr groß sind, selbst wenn es so ist ist toter Rhythmus, wir können die dritte Ebene der for-Schleife deutlich erkennen. Jedes Mal, wenn}

j hinzugefügt wird, muss die Unterspaltensumme erneut berechnet werden. Warum verwenden wir also nicht das Ergebnis von j? 1? Das heißt, wir speichern das Ergebnis von j-1. Bei der Berechnung des Ergebnisses von Schritt j müssen wir nur a[j] auf der Grundlage von Schritt j-1 hinzufügen, sodass es Algorithmus 2 gibt.

Algorithmus 2:

#include

using namespace std;
int Find_Maxsun2(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n;
cout << :" << endl;
for (i = 0; i < n; i )
cin >> a[i];
cout << Find_Maxsun2(a, n ) << endl;
return 0;
}
int Find_Maxsun2(int*a, int n){
int i, j, NewSum = 0, MaxSum= 0;
for (i = 0; i < n; i ){ /*ist der linke Endpunkt der Sequenz*/
NewSum = 0;
for (j = i; j < n; j ){ / *j Für den rechten Endpunkt der Reihe*/
NewSum = a[j]; /*Update NewSum jedes Mal unter j-1-Bedingung*/
if (NewSum>MaxSum) /*Update MaxSum*/
MaxSum = NewSum;
}
}
return MaxSum;
}

Dieser Algorithmus ist intelligenter als 1 und die Algorithmuskomplexität beträgt O(n

2^{), was offensichtlich besser ist. Nicht die Komplexität, die wir wollen.}

Algorithmus 3:

Algorithmus 3 nutzt die Idee des Teilens und Herrschens. Die Grundidee ist selbstverständlich: Erst teilen und dann erobern, das Problem in kleine Probleme zerlegen und Um die kleinen Probleme zu lösen, teilen wir die ursprüngliche Sequenz in zwei Teile, dann befindet sich die größte Teilsequenz links, rechts oder jenseits der Grenze. Die Grundidee ist wie folgt:

Schritt 1: Teilen Sie die ursprüngliche Sequenz in zwei Teile und teilen Sie sie in eine linke Sequenz und eine rechte Sequenz auf.

Schritt 2: Finden Sie rekursiv die Teilfolgen S left und S right.

Teil 3: Scannen Sie von der Mittellinie nach beiden Seiten, um die größte Teilfolge über die Mittellinie und S zu finden.

Schritt 4: Finden Sie S=max{S links, S Mitte, S rechts}

Der Code wird wie folgt implementiert:

#include
using namespace std;
int Find_MaxSum3(int*a,int low,int high);
int Max(int ​​​​a,int b,int c);
int main(){
int n, i;
int a[100];
cin >>
cout << < n << " Zahl:" << für (i = 0; i < n; i )
cout < < Find_MaxSum3(a,0,n-1) << endl;
return 0;
}
int Find_MaxSum3(int*a,int low,int high){
int MaxSum = 0, MidSum, LeftSum, RightSum,i;
MidSum = 0;
if (low == high){ /*Abbruchbedingung der Rekursion*/
if (a[low] > 0)
return a[low];
else
return 0;
}
int mid = (low high) / 2; //Finde den Mittelpunkt der Punktzahl
LeftSum = Find_MaxSum3(a, low, mid); /*Rekursiv die maximale Summe der linken Sequenz ermitteln*/
RightSum = Find_MaxSum3(a, mid 1, high); /*Rekursiv die maximale Teilsequenzsumme der rechten Sequenz ermitteln */
/*Dann können Sie die maximale Summe der grenzüberschreitenden Zwischensequenzen ermitteln */
int NewLeft = 0,Max_BorderLeft=0, NewRight = 0,Max_BorderRight=0;
für (i = mid; i >= low; i--) { /*Nach links scannen, um die maximale Summe zu finden*/
NewLeft = a[i];
if (NewLeft > Max_BorderLeft)
Max_BorderLeft = NewLeft ;
}
for (i = mid 1; i <= high; i ){ /*Nach rechts scannen, um die größte Teilsequenz zu finden und*/
NewRight =a[i];
if (NewRight >= Max_BorderRight)
Max_BorderRight = NewRight ;
}
MidSum = Max_BorderRight Max_BorderLeft;
return Max(LeftSum, MidSum, RightSum); /*Gibt das Ergebnis der Behandlung zurück*/
}
int Max(int ​​​​a, int b, int c){ /*Finde die größte Zahl unter den 3*/
if ( a>= b&&a >= c)
return a ;
if (b >= a&&b >= c )
return b;
if (c >= b&&c>=a)
return c;
}

Berechnen wir die zeitliche Komplexität dieses Algorithmus:

T(1)=1;

T(n)=2T(n/2) O(n);

=2

k

T( n/2^k) kO(n)=2^kT(1) kO(n) (wobei n=2 ^k)=n nlogn=O (nlogn);Obwohl dieser Algorithmus sehr gut ist, ist er nicht der schnellste.

Algorithmus 4:

Algorithmus 4 wird Online-Verarbeitung genannt. Dies bedeutet, dass jedes Mal, wenn ein Datenelement eingelesen wird, es rechtzeitig verarbeitet wird und das erhaltene Ergebnis für die aktuell gelesenen Daten gilt, dh der Algorithmus kann an jeder Position die richtige Lösung liefern und der Algorithmus kann geben beim Lesen die richtige Lösung finden.

#include

using namespace std;

int Find_MaxSum4(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> cout << 🎜> for (i = 0; i < n; i )
cin >> a[i];
cout << Find_MaxSum4(a,n) << > return 0;
}
int Find_MaxSum4(int*a, int n){
int i, NewSum = 0, MaxSum = 0;
for (i = 0; i < n; i ){
NewSum = a[i]; /*Aktuelle Teilsequenzsumme*/
if (MaxSum < NewSum)
MaxSum = NewSum; /*Maximale Teilsequenzsumme aktualisieren*/
if ( NewSum < 0) /*Wenn es kleiner als 0 ist, verwerfen Sie es*/
NewSum = 0;
}
return MaxSum;
}

Dieser Algorithmus liest The Die Daten werden einzeln gescannt und es gibt nur eine for-Schleife. Die Algorithmen zur Lösung desselben Problems sind sehr unterschiedlich. Der Trick besteht darin, den Computer einige wichtige Zwischenergebnisse merken zu lassen, um wiederholte Berechnungen zu vermeiden.

Das Obige stellt die maximale Teilsequenz- und Algorithmusanalyse vor, einschließlich Aspekten des Inhalts. Ich hoffe, dass es für Freunde hilfreich ist, die sich für PHP-Tutorials interessieren.