NOIPアウトライン整理:(五)ソートテンプレートとアルゴリズム複雑度分析

ソートアルゴリズム:
よく使われる(役に立つ)ソート思考は、一般的に以下の4種類で、中後期も実際の状況に応じてsortを使うことができます.
1、クイックソート(二分+再帰)
しばらくコードは転載したので、後で更新する機会があって、見て分からないでスキップしてください

#include
inline void Rd(int&res){
    res=0;char c;
    while(c=getchar(),c<48);
    dores=(res<<3)+(res<<1)+(c^48);
    while(c=getchar(),c>47);
}
int res[100005];
void qsort(int L,intR){
    if(L>=R)return;
    int key=res[L],low=L,high=R;
    while(low=res[low])++low;
        if(low

2、集計ソート(二分+遡及)
集計思考は遡及の過程であり、luogu 1309スイスラウンドは、良いテンプレートである.
 
3、ヒープの順序付け(ヒープの概念)
スタックは配列を非線形に想像し,簡単なデータ構造である.時間の複雑さもnlognで、1つのスタックを維持して、上と下の2つの操作があります
しばらくコードは転載したので、後で更新する機会があって、見て分からないでスキップしてください

#include
inline void Rd(int&res){
    res=0;char c;
    while(c=getchar(),c<48);
    dores=(res<<3)+(res<<1)+(c^48);
    while(c=getchar(),c>47);
}
struct Heap{
    static const int M=100005;
    int heap[M],sz;
    Heap(){sz=0;}
    inline void swap(int *a,int *b){
        if(a==b)return;
        int t=*a;*a=*b;*b=t;
    }
    int top(){return heap[1];}
    void push(int val){
        heap[++sz]=val;
        int pos=sz;
        while(pos>>1){
            int nxt=pos>>1;
            if(heap[nxt]>heap[pos])swap(&heap[nxt],&heap[pos]);
            else break;
            pos=nxt;
        }
    }
    void pop(){
        int pos=1;
        heap[pos]=heap[sz--];
        while((pos<<1)<=sz){
            int nxt=pos<<1;
            if(nxt+1<=sz&&heap[nxt+1]

 
4、基数ソート
しばらくコードは転載したので、後で更新する機会があって、見て分からないでスキップしてください

#include
inline void Rd(int&res){
    res=0;char c;
    while(c=getchar(),c<48);
    dores=(res<<3)+(res<<1)+(c^48);
    while(c=getchar(),c>47);
}
static const intM=100005,S=10;
inta[M],s[S][M],sz[S];
int main(){
    int n;Rd(n);
    for(int i=1;i<=n;++i)Rd(a[i]);
    for(int base=1,i=1;i

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
アルゴリズム解析:複雑度解析
アルゴリズム解析の目的は、計算時間(CPU消費)、メモリ空間(RAM消費)、通信時間(帯域幅消費)など、アルゴリズムに必要なリソースを予測することであり、入力規模が与えられた場合に実行される基本動作数、またはアルゴリズム複雑度と呼ばれるアルゴリズムの実行時間を予測することである.
アルゴリズムの実行時間は入力されたデータの特徴に依存し、データの規模と実行時間の上限を入力します(実行時間の上限は使用者に対する承諾であるため).アルゴリズム分析は一般的に機械に依存する定数を無視し、実行時間の増加傾向に注目します.一般的にアルゴリズムの最悪の場合の実行状況のみを考慮し、O記号法を使用して最悪の実行状況の上限を表します.例えば:
線形複雑度O(n)は、各要素が一度処理されることを示す.
二乗複雑度O(n 2)は、各要素がn回処理されることを示す.
複雑さ
タグ記号
説明
コンスタント
 O(1) 
操作の数は定数であり,入力したデータの規模には関係ない.
対数(Logarithmic)
 O(log2n) 
操作の数と入力データの規模nとの割合はlog 2(n)である.
リニア(Linear)
 O(n)
操作の数は入力データの規模nに比例する.
平方(Quadratic)
 O(n2)
操作の数と入力データの規模nとの割合は二次二乗である.
キューブ(Cubic)
 O(n3)
操作の数と入力データの規模nとの割合は3次元である.
指数(Exponential)
 O(2n)  O(kn)  O(n!)
指数級の操作で、急速に成長しています.
通常、時間の複雑さは、実行時間といくつかの一般的な比例関係があります.
複雑さ
10
20
50
100
1000
10000
100000
O(1)
<1s
<1s
<1s
<1s
<1s
<1s
<1s
O(log2(n))
<1s
<1s
<1s
<1s
<1s
<1s
<1s
O(n)
<1s
<1s
<1s
<1s
<1s
<1s
<1s
O(n*log2(n))
<1s
<1s
<1s
<1s
<1s
<1s
<1s
O(n2)
<1s
<1s
<1s
<1s
<1s
2s
3-4 min
O(n3)
<1s
<1s
<1s
<1s
20s
 5 hours 
 231 days 
O(2n)
<1s
<1s
 260 days 
 hangs 
 hangs 
hangs
hangs
O(n!)
<1s
 hangs 
hangs
 hangs 
hangs
hangs
hangs
O(nn)
 3-4 min 
hangs
hangs
 hangs 
hangs
hangs
hangs
コードブロックの漸進的な実行時間、すなわちアルゴリズムの複雑さを計算する方法には、次のステップがあります.
1、アルゴリズムの実行時間を決定する構成ステップを決定する.
2、このステップを実行するコードを見つけて、1とマークします.
3、1とマークされたコードの次の行のコードを表示します.次の行のコードがループである場合、タグ1はループの回数1*nの1倍に変更されます.ネストされた複数のループが含まれている場合は、倍数の計算が続行されます.たとえば、1*n*mです.
4、タグ付けされた最大値を見つけることは、実行時間の最大値、すなわちアルゴリズム複雑度記述の上界である.
例えば、フィボナッチ数列:
Fib(0) = 0,Fib(1)= 1,Fib(n) = Fib(n-1) + Fib(n-2)
F() = 0, 1, 1, 2, 3,5, 8, 13, 21, 34 ...
例1

int Fibonacci(int n)
{
   if (n <= 1)
        return n;
   else
        return Fibonacci(n - 1) + Fibonacci(n -2);
}

ここで、所与の規模nにおいて、Fib(n)を算出するのに要する時間は、Fib(n−1)を算出する時間と、Fib(n−2)を算出する時間との和である.T(n＜＝1)＝O(1),T(n)＝T(n−1)＋T(n−2)＋O(1),再帰ツリーを用いた構造記述からアルゴリズムの複雑さはO(2 n)であることが分かった.
例2

int Fibonacci(int n)
{
   if (n <= 1)
        return n;
   else
   {
        int[] f = new int[n + 1];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i <= n; i++)
        {
          f[i] = f[i - 1] + f[i - 2];
        }
        returnf[n];
    }
}

同様にフィボナッチ数列であり,アルゴリズムの複雑さをO(n)に最適化するために配列fを用いて計算結果を格納した.
例3

int Fibonacci(int n)
{
   if (n <= 1)
        return n;
   else
   {
        int iter1 = 0;
        int iter2 = 1;
        int f = 0;
        for (int i = 2; i <= n; i++)
        {
          f = iter1 + iter2;
          iter1 = iter2;
          iter2 = f;
        }
        return f;
   }
}

同様にフィボナッチ数列ですが、実際には最初の2つの計算結果だけが役に立つため、中間変数を使用して格納することができ、配列を作成してスペースを節約する必要はありません.同様にアルゴリズムの複雑さをO(n)に最適化した.
例4
行列乗のアルゴリズムを用いてフィボナッチ数列アルゴリズムを最適化した.

static intFibonacci(int n)
{
      if (n <= 1)
        return n;
      int[,] f = { { 1, 1 }, { 1, 0 } };
      Power(f, n - 1);
      return f[0, 0];
}
static voidPower(int[,] f, int n)
{
      if (n <= 1)
        return;
      int[,] m = { { 1, 1 }, { 1, 0 } };
      Power(f, n / 2);
      Multiply(f, f);
      if (n % 2 != 0)
        Multiply(f, m);
}
static voidMultiply(int[,] f, int[,] m)
{
      int x = f[0, 0] * m[0, 0] + f[0, 1] *m[1, 0];
      int y = f[0, 0] * m[0, 1] + f[0, 1] *m[1, 1];
      int z = f[1, 0] * m[0, 0] + f[1, 1] * m[1,0];
      int w = f[1, 0] * m[0, 1] + f[1, 1] *m[1, 1];
      f[0, 0] = x;
      f[0, 1] = y;
      f[1, 0] = z;
      f[1, 1] = w;
}

最適化後のアルゴリズムの複雑さはO(log 2 n)であった.