8

私は高低を検索しましたが、実行時の複雑さ、再帰、および Java に関連する多くの資料を見つけることができないようです。

私は現在、アルゴリズムのクラスで実行時の複雑さと Big-O 表記法を学んでいますが、再帰アルゴリズムの分析に問題があります。

private String toStringRec(DNode d)
{
   if (d == trailer)
      return "";
   else
      return d.getElement() + toStringRec(d.getNext());
}

これは、二重にリンクされたリストを単純に繰り返し処理し、要素を出力する再帰的な方法です。

再帰メソッド呼び出しの数は DList 内のノードの数に依存するため、実行時の複雑さが O(n) であるということだけを思いつくことができますが、それでも快適ではありません。この答え。

dとの追加を考慮する必要があるかどうかはわかりませんd.getNext()。

それとも、私は完全に軌道から外れており、実行時の複雑さは一定DNodesですDList.

4

5 に答える 5

3

一見すると、これは末尾呼び出しの一般化である、末尾再帰 modulo consの典型的なケースのように見えます。反復回数のループに相当します。

ただし、それほど単純ではありません。ここで注意が必要なのはd.getElement()、成長する文字列に を追加することです。これはそれ自体線形操作であり、何N度も繰り返されます。したがって、関数の複雑さは ですO(N^2)。

于 2012-03-02T21:48:46.740 に答える
2

これは非常に単純な例ですが、秘訣は再帰関係を定義することです。これは、指定された入力サイズのランタイムの関数であり、入力サイズが小さいという観点からです。この例では、各ステップで実行される作業に一定の時間 C がかかると仮定し、基本ケースでは作業が行われないと仮定すると、次のようになります。

T(0) = 0
T(n) = C + T(n-1)

次に、置換を使用して実行時間を解決し、シリーズを見つけることができます。

T(n) = C + T(n-1) = 2C + T(n-2) = 3C + T(n-3) = ... = nC + T(n-n) = nC + 0 = nC

O の定義により、この方程式は O(n) です。この例は特に興味深いものではありませんが、mergesort や別の分割統治アルゴリズムの実行時間のようなものを見ると、再帰関係についてより良いアイデアを得ることができます。

于 2012-03-02T21:57:05.110 に答える
2

T(n) が基本操作の数である場合 (この場合 - 関数の本体に入ると、内部の行は最大 1 回実行され、2 番目の戻り値以外はすべて O(1) ではありません) によって実行されます。 n 個の要素のリストで toStringRec を呼び出すと、

  T(0) = 1  - as the only things that happen is the branch instruction and a
              return
  T(n) = n + T(n-1) for n > 0 - as the stuff which is being done in the
              function besides calling toStringRec is some constant time stuff and
              concatenating strings that takes O(n) time; and we also run
              toStringRec(d.getNet()) which takes T(n-1) time

この時点で、アルゴリズムの複雑さについて説明しました。これで、T の閉形式 T(n) = O(n**2) を計算できます。

于 2012-03-02T21:49:08.940 に答える
0

あなたが示唆するように、アルゴリズムの実行時の複雑さは O(n) です。リストには n 個のアイテムがあり、アルゴリズムは各アイテムに対してほぼ一定量の作業を行います (その作業は、Element および Next アクセスと、新しい toStringRec 呼び出しです)。DNode から Element を取得するには一定の時間がかかり、big-O 表記では一定の時間は破棄されます。

再帰的メソッドの興味深い点 (ほとんどの場合) は、空間の複雑さも O(n) であることです。n 回呼び出される toStringRec への呼び出しごとに、(メソッドに渡されたパラメーターを格納するための) 新しいスタック エントリが作成されます。

于 2012-03-02T21:48:41.987 に答える
0

このような再帰アルゴリズムの場合、通常、再帰方程式を記述して次数を計算することができます。T(n) で実行された命令の数を表示するのが通例です。この例では、次のものがあります。

T(n) = T(n - 1) + O(1)

(関数getElementが一定時間で実行されると仮定します。) この方程式の解は自明に T(n) = O(n) です。

それが一般的なケースでした。ただし、そのような方程式を書かなくてもアルゴリズムを解析できる場合があります。この例では、各要素が最大 1 回アクセスされ、一定時間の作業が行われるたびに簡単に主張できます。そのため、仕事をするのに全体で O(n) かかります。

于 2012-03-04T18:34:42.860 に答える