3

私は、一般に O(b m ) で動作するツリー トラバーサル アルゴリズムを持っています。ここで、b は分岐係数、m は最大深度です。

反復深化を使用して、このアルゴリズムは深さを増やしながら m 回繰り返し実行されます。

O(b m ) = b⁰ + b¹ + b² + ... + b m

時間の複雑さに関する私の限られた理解に基づいて、最大の要素を採用します。これは、時間の経過とともに最も重要な要素であるためです。その要素は b mになります。ここで、m は到達した最大深度です。

したがって、その知識があれば、反復深化アルゴリズムも O(b m )で実行されると結論付けます。

ただし、論理的な観点から、アルゴリズムが深さmで1回実行されるか、深さmまでm回実行されるかにかかわらず、ツリートラバーサルがまったく同じ時間の複雑さを持つ方法を理解するのに苦労しています。

b mは本質的に Σ k=0,..,m b kより小さくなります。したがって、反復深化の時間計算量は高くするべきではありませんか?

それとも、私が理解できない何かがありますか？

4

2 に答える 2

3

基本的に、次の 2 つの関数が大きな O に関して同じ時間の複雑さを持っている理由を尋ねています (両方とも O(n^m) であるため)。

  • n^0 + n^1 + n^2 + ... + n^m
  • n^m

その理由は、ある時点で、n と m の値に対して項 n^m がこれらの関数の他のすべての項を小さくするからです。入力が大きくなると、関数全体の実行時間は n^m によって決まります。

n^m + 1000000000000 かかる関数を思いついたとしても、ある時点で n^m が実行にかかる時間を決定する用語になります。つまり、両方の関数の実行時間は、n^m 倍の定数を持つ関数によって制限されます。

あなたの例では、ツリートラバーサルを深さ m で 1 回実行するか、深さ m まで m 回実行すると、ツリーが成長するにつれて、深さ m で実行するランタイムが他のすべての実行を矮小化するため、同じ時間の複雑さがあります。深さ m での実行にかかる時間を調べるだけで、基本的に両方のタスクの実行時間を制限する関数を見つけることができます。

別の例を挙げると、両方とも O(n) である 2 つの関数を考えることができます。

  • f1(n) = 1000000000n + 5
  • f2(n) = 3n

n が大きくなるにつれて f1 がより多くの作業を行うように見える場合があるため、両方が O(n) であると言うのは「公平」ではありません。しかし、それらの時間計算量は線形関数によって制限されます: いくつかの (大きな) 定数 c の場合、両方の関数の実行時間は f(n) = cn 未満になるため、全体としての時間計算量は O(n) であると言えます。

于 2013-12-08T20:31:46.977 に答える
2

「まったく同じ」時間の複雑さは、「正確な時間をとること」と同じではありません。「まったく同じ時間の複雑さ」と言うのは、「一定の係数まで同じ速度で成長する」と言っているようなものです。これは大まかな見積もりです。

たとえば、b = 3次の 2 つの数列を比較している場合:

3^m,             or (1, 3,  9, 27,  81, ...)
3^0+3^1+...+3^m, or (1, 4, 13, 40, 121, ...)

D(m)最初の数字（「DFS」の場合）と2番目の数字（ I(m)「反復的な深化」の場合）を示しましょう。

I(m) = 3/2 * D(m) - 1/2

I(m) が D(m) より大きいことは確かですが、成長の「順序」は同じです。この考え方は で表されI(m) = O(D(m))ます。

数学的にはI(m) = O(D(m))、 、すべての; ここに。kI(m) < k * D(m)mk = 3/2

于 2013-12-08T20:36:20.243 に答える