3

C++のアルゴリズムでrobertsedwickの次のプログラムがあります

Item max(Item a[], int l, int r){
    if (l == r) return a[l];
    int m = (l+r)/2; 
    Item u = max(a, l, m);
    Item v = max(a, m+1, r);
    if (u > v) 
        return u; 
    else 
        return v;
}

以下はハノイの塔のプログラムです

void hanoi(int N, int d)
  {
    if (N == 0) return;
    hanoi(N-1, -d);
    shift(N, d);    
    hanoi(N-1, -d);
  }

以下は定規のためのプログラムです

void rule(int l, int r, int h)
  { int m = (l+r)/2;
    if (h > 0)
      { 
        rule(l, m, h-1);
        mark(m, h);
        rule(m, r, h-1);
      }
  }

上記の3つの問題はすべて、サイズ2のn乗の2つの問題に分割することにより、サイズ2のn乗の問題を解決します。

定規とマックスについては理解していますが、上記のステートメントのタワーオブハノイについてはどうですか？

上記のプログラムを分析している間、著者は、最大値を見つけるために、入力のサイズに線形時間解があると述べています。定規を描画し、塔を解くために、出力のサイズに線形時間解があります。

上記の出力サイズの線形時間ソリューションとは、作成者が何を意味するのでしょうか。

4

1 に答える 1

1

honoiの塔の場合、再帰的アルゴリズムは（H（1）= 1）です。

H（n）= 2 H（n-1）+ 1 = 2 ^ 2H（n-2）+ 2 + 1 .... = 2 ^（n-1）H（1）+ 2 ^（n-2 ）+ ... + 1 = 2 ^（n-1）+ 2 ^（n-2）+ ... + 1 = 2^n-1。

しかし、honoiの塔のソリューションは、2 ^ n -1の動きを出力する必要があります。これは、アルゴリズムの実行時間に等しいため、出力のサイズとアルゴリズムの関係の実行時間は、実際には線形です。

limn- >∞ 出力/ランタイム=定数。

これは、アルゴリズムの実行時間が出力と線形の関係にあることを意味します（ただし、ご覧のとおり、入力との関係は指数関数的です）。

また、最大値を再度見つける際に、このようなalimを使用して、入力と線形関係があると言うことができます。

于 2012-09-07T18:08:01.757 に答える