再帰アルゴリズムの実行時の複雑さ

私は高低を検索しており、実行時の複雑さ、再帰、およびJavaに関連する多くの資料を見つけることはできないようです。再帰アルゴリズムの実行時の複雑さ

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

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

これは二重リンクされたリストを単純に反復して要素を出力する再帰的な方法です。

私が思いつくことができるのは、再帰的メソッド呼び出しの数がDListのノード数に依存するため、実行時の複雑さがO（n）ですが、この答えに心地よく感じる。

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

DListのDNodesから要素を取得しているため、完全にオフトラックで、実行時の複雑さは一定ですか？

出典

2012-03-02 Jimmie J

参照：http://stackoverflow.com/questions/1126388/slow-string-concatenation-over-large-input – dyoo

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

（ほとんどの場合）再帰的メソッドについての興味深い点は、それらも空間の複雑さにおいてもO（n）であるということです。新しいスタックエントリ（メソッドに渡されたパラメータを格納するため）は、n回と呼ばれるtoStringRecの各呼び出しに対して作成されます。

出典

2012-03-02 21:48:41 sgmorrison

この説明は残念ながら間違った結論を提供します。文字列連結のコストを考慮していません。つまり、各項目のコストは**一定ではありません**。それがこの問題の大きなポイントです。これを修正してください。 – dyoo

私は各項目のコストが一定ではないが、O（n）であることに同意しないことに同意します。 'string1 + string2'のコストはO（m）であり、mは結果のStringの長さです。具体的には、2つのストリングを連結することは、最悪の場合、長さmの新しいchar []の作成と、元のストリングからの各文字の1度に1つのコピーです。与えられたコードのn回目の繰り返しで、toStringRecが非常に長いStringを返すかもしれませんが、連結のコストは依然としてO（m）です。 'getElement'は空文字列または非常に長い文字列を返す可能性があるので、この例ではmはnに直接結び付けられていません。 – sgmorrison

特定のd.getElement（）のサイズの上限である長さ 'm 'があるとします。 'toStringRec（node）'から返される返される文字列のサイズは、 'node'で始まるチェーンの長さによって制限されます。 T（n）を計算コストとする。次に、いくつかの定数「C1」、「C2」、「C3」について、「T（n） dyoo

これは、テールコールの一般化tail recursion modulo consの古典的なケースのように見えます。反復回数を持つループと同等です。

しかし、それはそれほど単純ではありません。ここでのトリッキーなことは、成長している文字列にd.getElement()の追加です：これは、それ自体で線形操作であり、それはN回繰り返されます。したがって、あなたの機能の複雑さはO(N^2)です。

出典

2012-03-02 21:48:46 dasblinkenlight

ええと、私はd.getElement（）がノードdに格納されたデータを取得すると考えていました。彼は私が推測するこの質問を少し明確にする必要があります... –

@XiaoChuanYuいいえ、 'd.getElement（）'は 'O（1）'です。後に続く文字列連結は線形です。 – dasblinkenlight

はい、文字列連結のコストを無視してくれてありがとう、ありがとうございます。これはまさに正しいことです。ガウス和「1 + 2 + ... + n」が作用し、それは二次関数が出てくるところです。 – dyoo

T（n）が基本操作の数である場合（この場合、関数の本体を入力すると、内部の行は最大で1回実行され、2回目以外のすべての行はO ））は、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-02 21:49:08

いいえ：「機能で完了したもの」はO（1）ではありません。各要素の文字列のサイズが空でないと仮定して、 'n 'に比例する時間がかかる作業です。したがって、 'T（n） 'の閉じた形は、ある定数Cに対して' T（n）= 1C + 2C + 3C + ... + nC'のようになります。 'T（n）'は線形ではなく、二次的です。 – dyoo

良いキャッチ、ありがとう！ –

これは非常に簡単な例ですが、トリックは反復関係を定義することです。これは入力サイズが小さい場合のランタイムの関数です。この例では、と仮定すると、各ステップで行われる作業は、一定時間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-02 21:57:05 cjm

もちろん、この例でも共通の意味があります。リンクされたリストのすべてのノードを印刷しているので、実行するプリントの数はリストのサイズとまったく同じになります。それは線形時間です。 – cjm

この特定の例では、Javaの文字列連結がどのように機能するかを考えて、各ステップで実行される作業が一定時間であると仮定することはできません。 – dyoo

この問題のポイントは、Javaライブラリ関数の複雑さを調べるのではなく、この種の再帰アルゴリズムをどのように一般的に分析できるのかを理解することだから、この前提を立てても問題ないと思います。 – cjm

このような再帰アルゴリズムでは、通常、順序を計算するための再帰方程式を書くことができます。 T（n）で実行される命令の数を表示することが慣例です。この例では、我々は：

T（N）=（N - 1）T + O（1）

（getElement実行時定数関数と仮定する。）この式のソリューションは自明Tです（ n）= O（n）である。

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

出典

2012-03-04 18:34:42 MMS

再帰アルゴリズムの実行時の複雑さ

答えて

関連する問題