5

空間と時間の複雑さを判断するのに問題があります。たとえば、分岐係数bを持ち、最大で深さdを持つツリーがある場合、時間と空間の複雑さをどのように計算できますか？それらがO（b ^ d）とO（bd）であることは知っていますが、私の問題はこれらの値を取得する方法です。

4

2 に答える 2

8

時間

ツリー内のすべてのノードは、ある時点で一度生成する必要があり、ノードを生成するのに一定の時間がかかると想定cされています (一定の時間は変化する可能性があり、c任意のノードを生成するための最高の一定の時間を選択できます) 。 . 順序はアルゴリズムによって決定され、ノードを繰り返し展開する必要がなくなります。

nodes          b=2                        b=3
b^0             *                          *
              /   \               /        |        \
b^1          *     *             *         *         *
            / \   / \         /  |  \   /  |  \   /  |  \
b^2        *   * *   *       *   *   * *   *   * *   *   * 
               ...                        ...

図でわかるようにc*b^0、最初のレベルを正確に計算するにはコストがかかりますc。ツリーの次のレベルにはb^1ノードが含まれc*b^1 = c*b、2 番目のレベルを生成するにはコストがかかります。第 3 レベルではb、第 2 レベルのすべてのノードに対して再びノードが存在します。これは、b*b^1 = b^2$ノードと のコストを意味しc*b^2ます。

深さのツリーの最も深いレベルにはノードdがありb^d、そのレベルでの作業は ですc*b^d。この時点までに行われた総作業量は ですc*b^0 + c*b^1 + ... + c*b^d。複雑さについては、最も急速に上昇する用語のみを見て、定数を削除して、次のようにします。

O(c + c*b + ... + c*b^d) = O(c*b^d) = O(b^d).

本質的に: 時間は関数f(d) = SUM(i=1..d){c*b^i}であり、O(f(d)) = O(b^d).

スペース

この図は、 のさまざまな段階でのアルゴリズムを示していますb=3。*は現在展開されているノードを?示し、不明なノードを+示し、スコアが完全に計算されたノードを示します。

                    branching factor b = 3                     space
         *             *             *             *             b
       / | \         / | \         / | \         / | \         
      *  ?  ?       *  ?  ?       +  *  ?       +  +  *          b
    / | \         / | \            / | \            / | \      
   *  ?  ?       +  +  *          +  *  ?          +  +  *       b
 / | \               / | \         / | \               / | \   
*  ?  ?             +  *  ?       +  *  ?             +  +  *    b

ノードのスコアを計算するには、ノードを展開し、子を選択して、深さでリーフ ノードに到達するまで再帰的に展開しますd。子ノードが完全に計算されると、次の子ノードに進みます。すべてのb子ノードが計算されると、子ノードに基づいて親スコアが計算され、その時点で子ノードをストレージから削除できます。これは上の図に示されています。ここでは、アルゴリズムが 4 つの異なる段階で示されています。

いつでも 1 つのパスを展開し、c*bすべての子ノードをすべてのレベルに格納するためのストレージが必要です。ここでも、ノードごとに一定量のスペースが必要であるという前提があります。重要なのは、どのサブツリーもそのルートで要約できることです。パスの最大長は であるため、d最大限のスペースが必要c*b*dになります。上記のように、定数項を削除すると、 が得られO(c*b*d) = O(b*d)ます。

于 2012-02-26T00:52:51.187 に答える
4

スペースの複雑さは、「このアルゴリズムに割り当てる必要のあるメモリの量」に相当します。時間計算量は、「（抽象的な意味で）実行にかかる時間」に相当します。

分岐係数bと深さdのツリーには、ゼロ番目のレベルに1つのノード、最初のレベルにbノード、2番目のレベルにb * b = b ^ 2ノード、3番目のレベルにb ^ 2 * b = b^3があります。レベルなど。これらの4つのレベル（深さ3）には、1 + b + b ^ 2 + b^3があります。複雑さの観点から、通常は最上位の項のみを保持し、乗算定数を削除します。したがって、スペースの複雑さのためにO（b ^ d）の複雑さになります。

時間計算量では、カウントするのはノードの数ではなく、アルゴリズムが完了するのにかかるループまたは再帰呼び出しの数です（最悪の場合）。

手足に出て、IDDFSについて話していると仮定します。O（b ^ d）とO（bd）がどこから来たのかについての説明は、このwikiの記事でうまく説明されています。

于 2010-01-17T05:32:29.507 に答える