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

最大部分列とアルゴリズム分析

問題の説明: n 個の整数列 {a1, a2,...,an} が与えられた場合、関数 f(i,j)=max{0,Σa _{k}(k: i から j まで連続して取得);}

問題は、連続するサブ列の合計の最大値を見つけることです。最大値が負の数の場合は、0 を取得します。 8 つの数列 {-1,2,-3,

4,-2,5,-8,3} として、Namo の最大部分列合計は 4 (-2) 5=7 です。

この問題には複雑度の異なる 4 つのアルゴリズムがあり、アルゴリズム 1 ～ 4 の時間計算量は O(n

3^)、O(n2^{)、O(nlogn) です。 、O(n);}

アルゴリズム 1:

最も直接的な方法は、すべての状況をリストする網羅的な方法であり、次の式の左端 i を設定できます。

//最大のサブ列と網羅的なメソッド

#include;
名前空間 std を使用;
int Find_Maxsun(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n ;
cout << "数値:" <
を入力してください。 n; i )
cin >> a[i];
cout return 0;
}
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 = NowSum;
}
return MaxSun;
}

明らかに、総当たり法では 3 つの for ループが使用され、アルゴリズムの時間計算量は O(n

3^{) です。もちろん、最も愚かなアルゴリズムですが、データが非常に難しい場合、たとえそれが死ぬほど計算されたとしても、}

j が追加されるたびに、for ループの 3 番目のレベルが明らかにわかります。 -列の合計を再度計算する必要があるので、j-1 の結果を使用しないのはなぜでしょうか。つまり、j-1 の結果を保存します。ステップ j の結果を計算するときは、ステップ j-1 に基づいて a[j] を加算するだけで済みます。したがって、アルゴリズム 2 が存在します。

アルゴリズム 2:

#include

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

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

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

アルゴリズム 3:

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

ステップ 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 << "を入力してください。 < n << " 数値:" < for (i = 0; i a[i];
< < Find_MaxSum3(a,0,n-1) < return 0;
}
int Find_MaxSum3(int*a,int low,int high) int MaxSum = 0, MidSum, LeftSum, RightSum,i;
MidSum = 0;
if (low == high){ /*再帰の終了条件*/
if (a[low] > 0)
return a[low];
else
return 0;
}
int mid = (low high) / 2 //スコアの中間点を見つける
LeftSum = Find_MaxSum3( a, low, mid); /*左のシーケンスの最大合計を再帰的に求めます*/
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 < for (i = 0; i cin >> 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 < 0) /*0 未満の場合は破棄します*/
NewSum = 0;
}
return MaxSum;
}

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