アルゴリズムレコードの逆シーケンスペア.
4830 ワード
問題は次のとおりです.
長さNの配列、a 1、a 2...aNは、逆順ペアの個数を尋ね、逆順ペアの定義はiajである.
1,比較的素朴な考えは直接forサイクルであり,内層のもう一つのforサイクルはこの数の前に彼より大きい数を見つけた.
このような複雑さはN^2で、比較的遅い.
2,前のアルゴリズムは比較的に遅くて、最適化することができますか?
外層のforサイクルの各aiについて,内層forサイクルではなく他の方法で前のaiより大きい個数をより速く算出すれば,より速くなる.
データ構造BSTでメンテナンスする.
各数について、BSTの中で彼より大きい個数を求めて、それからretは直接加えて、それからBSTの中でこの数を挿入します.
これで複雑度はNlognなので、もう十分速いです.
3,もう1つはNlognのアルゴリズムであり,速度は比較的安定している.集計ソートの知識が必要です.
まず集計ソートを見て、a 1,a 2,a 3を...aNを半分に分解し,それぞれ再帰的に並べ替え,その後,この2つの配列をO(N)で統合する.
では、その中にいくつかのコードを追加します.
N個数の逆順対個数が要求されると仮定し,先にa 1,a 2を再帰的に求めると.aaN/2とaaN/2+1..aNという2つのサブ配列の逆シーケンス対個数.
そしてiが左でjが右の逆順の個数を求め、加算すると答えになります.
iは左、jは右なので、forループで計算すると、またN^2になって計算します.
一つの性質に注意すると、左と右がそれぞれ再帰的に求められているので、今iが左、jが右の逆順ペアを求めるとき、2つのサブ配列の中で数の順序はもうどうでもいいので、まず左の数と右の数に順番を並べます.
ではforは右のものを循環して、2点の検索ごとに左のどれだけ彼より大きいかを見つけます.
例は次のとおりです.
2 4 3 5 1 7 9 8の逆順の個数を求めます:
2 4 3 5と1 7 9 8の逆順対個数が1と1であることをそれぞれ再帰的に求め,次いでiが左,jが右であることを求める.まず2 3 4 5と1 7 8 9を並べ替えます
それから左の中で1より大きい個数を求めます(秩序があるので、直接2点でいいです.)4なのでretに4を加えます.
更に左の中で7より大きいことを求めて、更に8より大きいことを求めて、更に9より大きいことを求めます.全部合わせると答えです.
このようにマージ時にはNlogN(二分探索)の複雑さであり,主定理に基づいてT(N)=2*T(N/2)+NlogN得T(N)=NlogNlogNの複雑さを求める.
4、上のアルゴリズムはやはり効率が高くなくて、更に最適化することができます.
findという二分探索にはlogの複雑さが必要であり,O(1)に最適化できる.
左右の2つが秩序化されているため,右配列のaiにとって左配列の中で彼より大きい最初の数の位置をbiとすると,biが増加していることが証明される.
例:
2 4 5 7と1 3 6 9
1より大きい左配列の最初の数の位置は1であり、3より大きい最初の位置は2であり、6より大きい最初の位置は4であり、9より大きい最初の位置は5(表示を超えていない)であり、つまりこの4つのbはインクリメントされる.
では,左配列のxより大きい数の位置を探すたびにfind関数ではなく,直接ポインタを1つ増やしてもよい.
コードは次のとおりです.
複雑度の場合,pは増加するだけで減少しないのでwhileは最大N回,割り勘にすると複雑度もO(1)のforごとに総複雑度がO(N)のものとして集計計算を行う.
T(N)=2*T(N/2)+N T(N)=Nlognの複雑さを求める.
長さNの配列、a 1、a 2...aNは、逆順ペアの個数を尋ね、逆順ペアの定義はi
1,比較的素朴な考えは直接forサイクルであり,内層のもう一つのforサイクルはこの数の前に彼より大きい数を見つけた.
1 int getans() {
2 int ret=0;
3 for(int i=1;i<=N;++i)
4 for(int j=1;j<i;++j)
5 if(a[j]>a[i])
6 ++ret;
7 return ret;
8 }このような複雑さはN^2で、比較的遅い.
2,前のアルゴリズムは比較的に遅くて、最適化することができますか?
外層のforサイクルの各aiについて,内層forサイクルではなく他の方法で前のaiより大きい個数をより速く算出すれば,より速くなる.
データ構造BSTでメンテナンスする.
各数について、BSTの中で彼より大きい個数を求めて、それからretは直接加えて、それからBSTの中でこの数を挿入します.
1 int getans() {
2 BIT tree;
3 int ret=0;
4
5 for(int i=1;i<=N;++i) {
6 ret+=tree.findMax(a[i]);
7 tree.insert(a[i]);
8 }
9
10 return ret;
11 }これで複雑度はNlognなので、もう十分速いです.
3,もう1つはNlognのアルゴリズムであり,速度は比較的安定している.集計ソートの知識が必要です.
まず集計ソートを見て、a 1,a 2,a 3を...aNを半分に分解し,それぞれ再帰的に並べ替え,その後,この2つの配列をO(N)で統合する.
では、その中にいくつかのコードを追加します.
N個数の逆順対個数が要求されると仮定し,先にa 1,a 2を再帰的に求めると.aaN/2とaaN/2+1..aNという2つのサブ配列の逆シーケンス対個数.
そしてiが左でjが右の逆順の個数を求め、加算すると答えになります.
iは左、jは右なので、forループで計算すると、またN^2になって計算します.
一つの性質に注意すると、左と右がそれぞれ再帰的に求められているので、今iが左、jが右の逆順ペアを求めるとき、2つのサブ配列の中で数の順序はもうどうでもいいので、まず左の数と右の数に順番を並べます.
ではforは右のものを循環して、2点の検索ごとに左のどれだけ彼より大きいかを見つけます.
1 int getans(int L,int R) {
2 if(R==L) return 0;
3
4 int M=(L+R)/2;
5 int ret=getans(L,M)+getans(M+1,R); // （ ）
6
7 for(int i=M+1;i<=R;++i)
8 ret+=M-find(L,M,a[i])+1; // L M ai 。
9
10 merge(L,R); // 。
11 }例は次のとおりです.
2 4 3 5 1 7 9 8の逆順の個数を求めます:
2 4 3 5と1 7 9 8の逆順対個数が1と1であることをそれぞれ再帰的に求め,次いでiが左,jが右であることを求める.まず2 3 4 5と1 7 8 9を並べ替えます
それから左の中で1より大きい個数を求めます(秩序があるので、直接2点でいいです.)4なのでretに4を加えます.
更に左の中で7より大きいことを求めて、更に8より大きいことを求めて、更に9より大きいことを求めます.全部合わせると答えです.
このようにマージ時にはNlogN(二分探索)の複雑さであり,主定理に基づいてT(N)=2*T(N/2)+NlogN得T(N)=NlogNlogNの複雑さを求める.
4、上のアルゴリズムはやはり効率が高くなくて、更に最適化することができます.
findという二分探索にはlogの複雑さが必要であり,O(1)に最適化できる.
左右の2つが秩序化されているため,右配列のaiにとって左配列の中で彼より大きい最初の数の位置をbiとすると,biが増加していることが証明される.
例:
2 4 5 7と1 3 6 9
1より大きい左配列の最初の数の位置は1であり、3より大きい最初の位置は2であり、6より大きい最初の位置は4であり、9より大きい最初の位置は5(表示を超えていない)であり、つまりこの4つのbはインクリメントされる.
では,左配列のxより大きい数の位置を探すたびにfind関数ではなく,直接ポインタを1つ増やしてもよい.
コードは次のとおりです.
1 int getans(int L,int R) {
2 if(R==L) return 0;
3
4 int M=(L+R)/2;
5 int ret=getans(L,M)+getans(M+1,R); // （ ）
6
7 int p=L;
8 for(int i=M+1;i<=R;++i) {
9 while(p<=M && a[p]<=a[i]) ++p; // 。
10 ret+=M-p+1;
11 }
12
13 merge(L,R); // 。
14 }複雑度の場合,pは増加するだけで減少しないのでwhileは最大N回,割り勘にすると複雑度もO(1)のforごとに総複雑度がO(N)のものとして集計計算を行う.
T(N)=2*T(N/2)+N T(N)=Nlognの複雑さを求める.