最大部分列和アルゴリズム解析、部分列アルゴリズム解析_PHPチュートリアル

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

問題の説明: 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³)、O(n²)、O(nlogn)、O(n);

アルゴリズム 1:

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

#include
using namespace std;
int Find_Maxsun(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_Maxsun(int*a, int n) MaxSun = 0, i, j, k;
int NowSum;
for (i = 0; i for (j = 0; j < n; j++ ) { /*サブシーケンスの右端*/
NowSum = 0;
for (k = i; k <= j; k++)
NowSum += a[k] /* a[i] から a[j] へ*/
if (NowSum>MaxSun)
MaxSun = NowSum のシーケンス /*結果を更新*/
}
return MaxSun;
}

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

) になります。これはもちろん最も愚かなアルゴリズムですが、データが非常に大きい場合は、たとえ死ぬほど計算されたとしても、 for ループの 3 番目の層がはっきりとわかります j が追加されるたびに部分系列の合計を再度計算する必要があるため、j-1 の結果を使用しないのはなぜでしょうか?つまり、j-1 の結果を保存します。ステップ j の結果を計算するときは、ステップ j-1 に基づいて a[j] を加算するだけで済みます。したがって、アルゴリズム 2 が存在します。

#include

int Find_Maxsun2(int*a, int n);
int main(){
int n, i;
int a[100];
cin >>
cout << "数値を入力してください:" < 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 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 左、S 中央、S 右} を見つけます。

#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;
}

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

アルゴリズム 4: