最大サブシーケンスとアルゴリズムの分析

問題の説明: n 個の整数シーケンス {a1, a2,...,an} が与えられた場合、関数 f(i,j)=max{0,Σa_k}(k: i から j まで連続);

問題は、連続する部分系列の合計の最大値を見つけることです。最大値が負の数の場合は、8 つの数列 {-1,2,-3,4,-2 など) をとります。 ,5, -8,3}、Namo の最大部分列合計は 4+(-2)+5=7 です。

この問題には複雑さの異なる 4 つのアルゴリズムがあります。アルゴリズム 1 から 4 の時間計算量は O( n ³),O(n²),O(nlogn),O(n);

アルゴリズム 1:

最も直接的な方法は、すべての状況をリストし、その後の順序を設定できます。左端 i と右端 j を計算し、レイヤーを使用して a[i] から a[j] までの合計を計算します。

//最大のサブカラムと網羅的なメソッド
#include
namespace を使用std;
int Find_Maxsun (int*a, int n);
int main(){
int n, i;
int a[100];
cin >>
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int Find_Maxsun(int*a, int n){
int MaxSun = 0, i, j, k;
int NowSum;
for ( i = 0; i for (j = 0; j NowSum = 0;
for ( k = i; k NowSum += a[k]; /* a[i] から a[j] までのシーケンス */
if (NowSum>MaxSun)
MaxSun; Update result*/
}
return MaxSun;
}

明らかに、総当たり法では 3 つの for ループが使用され、アルゴリズムの時間計算量は もちろん最も愚かなアルゴリズムですが、データは非常に大きいので、たとえ死ぬほど計算しなければならないとしても、j が追加されるたびにサブカラムの合計を再度計算する必要があることがわかります。 j-1の結果は？つまり、j-1 の結果を保存します。ステップ j の結果を計算するときは、ステップ j-1 に基づいて a[j] を加算するだけで済みます。したがって、アルゴリズム 2 が存在します。

アルゴリズム 2:

#include

名前空間 std を使用;

int Find_Maxsun2(int*a, int n);
int main(){
int n, i;
int a[100];
cin >>
cout 」(i=0;i cin >> a[i];
cout return 0;
}
int Find_Maxsun2(int*a, int n) , j, NewSum = 0, MaxSum= 0;
for (i = 0; i NewSum = 0;
for (j = i; j NewSum += a[j] /* j-1 条件で毎回 NewSum を更新します*/
if (NewSum>MaxSum) /* Update MaxSum*/
MaxSum = NewSum;
}
}
return MaxSum;
}

このアルゴリズムは 1 よりも賢く、アルゴリズムの複雑さは O(n
2

) ですが、これは明らかに私たちが望む複雑さではありません。

^{アルゴリズム 3:}

アルゴリズム 3 は分割統治のアイデアを使用します。基本的な考え方は自明です。最初に分割してから征服し、問題を小さな問題に分解し、次に解決する小さな問題を合計します。元のシーケンスを 1 つに分割し、最大のサブシーケンスを左側、右側、または境界を越えて配置します。 基本的な考え方は次のとおりです:

ステップ 1: 元のシーケンスを 2 つに分割します。左のシーケンスと右のシーケンス。

ステップ 2: サブシーケンス S left と S right を再帰的に見つけます。

パート 3: 中心線から両側に向かってスキャンして、中心線と S を横切る最大のサブシーケンスを見つけます。

ステップ 4: S=max{S left, S middle, S right} を求める

コードは次のように実装されます。

#include
名前空間 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 >> n;
cout cin >> a[i];
cout return 0;
}
int Find_MaxSum3(int*a,int low,int high){
int MaxSum = 0, MidSum, LeftSum, RightSum,i;
MidSum = 0;
if (low == high){ /*終了条件recursion* /
if (a[low] > 0)
return a[low];
else
return 0;
}
int mid = (low + high) // 分の中間点を見つける
; LeftSum = Find_MaxSum3 (a, low, middle); /*左のシーケンスの最大合計を再帰的に求めます*/
RightSum = Find_MaxSum3(a, mid + 1, high); /*右のシーケンスの最大のサブシーケンスの合計を再帰的に求めます*/
/*次に、中間の境界を越えるシーケンスの最大合計を見つけることができます*/
int NewLeft = 0,Max_BorderLeft=0, NewRight = 0,Max_BorderRight=0;
for (i = Mid; i >= low; i --){ /*左をスキャンして最大合計を見つけます*/
NewLeft += a[i];
if (NewLeft > Max_BorderLeft)
Max_BorderLeft = NewLeft;
}
for (i = mid + 1; i NewRight+=a[i];
if (NewRight >= Max_BorderRight)
Max_BorderRight = NewRight;
}
MidSum = Max_BorderRight + Max_BorderLeft;
return Max(LeftSum, MidSum, RightSum) ; /*ルールの結果を返します*/
}
int Max(int a, int b, int c){ /*3 つの中で最大の数値を見つけます*/
if ( a>= b&&a >= c)
return a;
if (b >= a&&b >= c)
return b;
if (c >= b&&c>=a)
return c;
}

このアルゴリズムの時間計算量を計算してみましょう:

T(1)=1;

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

=2

k^{T(n /2}k^{)+kO(n) =2}k^{T(1)+kO(n) (n=2}k^{)=n+nlogn=O(nlogn);}

このアルゴリズムは非常に優れていますが、最速のアルゴリズムではありません。

アルゴリズム 4:

アルゴリズム 4 はオンライン処理と呼ばれます。これは、データが読み込まれるたびに、時間内に処理され、得られた結果が現在読み込まれているデータに当てはまります。つまり、アルゴリズムはどの位置でも正しい解を与えることができ、アルゴリズムは次のことを行うことができます。読みながら正しい解決策を見つけてください。

#include

名前空間 std を使用;
int Find_MaxSum4(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> ;
cout (i = 0; i ; a[i];
cout return 0;
}
int Find_MaxSum4(int*a, int n){
int i, NewSum = 0, MaxSum = 0;
for (i = 0; i NewSum += a[i]; /*現在のサブシーケンスの合計*/
if (MaxSum MaxSum = NewSum;最大サブシーケンス合計を更新します*/
if (NewSum NewSum = 0;
}
return MaxSum;
}

このアルゴリズムは、データを 1 つ読み取ります1 回スキャンすると、for ループは 1 つだけになります。同じ問題を解決するためのアルゴリズムは大きく異なります。重要な中間結果をコンピューターに記憶させ、計算の繰り返しを避けることにあります。

以上、最大サブシーケンスとアルゴリズム解析を内容も含めて紹介しましたが、PHPチュートリアルに興味のある方の参考になれば幸いです。