再帰的アルゴリズムの時間計算量はどれくらいですか

再帰的アルゴリズムの時間計算量は [T(n)=o(f(n))] です。これは、問題のサイズ n が増加するにつれて、アルゴリズムの実行時間の増加率と f が増加することを意味します。 (n) 成長率はアルゴリズムの漸近時間計算量と呼ばれる成長率に比例します。

#再帰的アルゴリズムの時間計算量

時間計算量:

一般に、アルゴリズムにおける基本演算の繰り返し回数は問題サイズ n の関数 f(n) であり、n による f(n) の変化を分析して T(n) の大きさのオーダーを決定します。 。ここで「o」は大きさの桁を表すために使用され、アルゴリズムの時間計算量を与えます。

T(n)=o(f(n));

これは、問題サイズ n が増加するにつれて、アルゴリズムの実行時間の増加率が、 f(n) 、アルゴリズムの漸近時間計算量と呼ばれます。そして、私たちは通常、最悪の場合の時間計算量について議論します。

推奨コース:

C 言語チュートリアル

空間複雑度:

アルゴリズムの空間複雑度は、実際に占有される空間ではありません。ただし、アルゴリズム空間全体における補助空間ユニットの数を計算するためのものであり、問​​題の規模とは何の関係もありません。アルゴリズムの空間複雑さ S(n) は、アルゴリズムによって消費される空間の大きさのオーダーとして定義されます。

S(n)=o(f(n))

アルゴリズムの実行に必要な補助空間が入力データ n に対して定数である場合、それは空間計算量と呼ばれます。アルゴリズム 補助空間は o (1);

再帰アルゴリズムの空間複雑さ: 再帰の深さ n*各再帰に必要な補助空間 各再帰に必要な補助空間が定数の場合、再帰空間の複雑さは o (n) です。

再帰的アルゴリズムの時間計算量の計算式は再帰的方程式です:

導入する前に例を検討してください。再帰ツリー:

T(n) = 2T(n/2) + n2

2 回反復して取得:

T(n) = n2 + 2(2T(n/4) + (n/2) 2)

さらに反復を続けて完全に展開すると、次の結果が得られます:

T(n) = n2 + 2((n/2) 2 +
2((n/22)2 + 2((n/23) 2 +
2((n/24) 2 +…+2((n/2i) 2 +
2T(n/2i + 1)))…))))……(1)

そして、n/2i 1 = = 1、反復は終了します。

式 (1) の括弧を展開すると、次の結果が得られます。

T(n) = n2 + 2(n/2)2 +
22(n/22) 2 + … + 2i(n/2i)2 +
2i+1T(n/2i+1)

これはたまたまツリー構造になっており、そこから再帰ツリー メソッドを導き出すことができます。

図中の (a)(b)(c)(d) は、それぞれ再帰ツリー生成の 1 番目、2 番目、3 番目、n 番目のステップです。各ノードでは、現在の空きアイテム n2 が保持され、2 つの再帰的アイテム T(n/2)

T(n/2) がそれぞれその 2 つの子ノードに割り当てられます。以下同様です。

グラフ内のすべてのノードの合計は次のとおりです:

[1 + 1/2 + (1/2)2 + (1/2)3 + … + (1/2)i] n2 = 2n2

その時間計算量は

O(n2)

ルールであることがわかります。再帰ツリーの式は次のように取得できます。

(1) 各層のノードは T(n) = kT(n / m) 現在の条件下での f(n) の f(n) の値n/m;

(2) 各ノードの分岐の数は k です;

(3) 各層の右側は、現在の層内のすべてのノードの合計をマークします。

別の例:

T(n) = T(n/3) T(2n/3) n

その再帰ツリーは次のようになります以下の図:

#各層の値が n で、ルートからリーフ ノードまでの最長パスが

# であることがわかります。 ##最後の再帰であるため、停止点は (2/3)kn == 1 です。その後、

then

##つまり、

T(n) = O( nlogn)

要約すると、この方法を使用して再帰アルゴリズムの複雑さを解決します:

f(n) = af(n/b) + d(n)

1. d(n) のときは定数です:

2. d(n) = cn の場合:

3. d(n の場合) ) 他の状況では、再帰ツリーを分析に使用できます。

2 番目のケースから、分割統治法を使用して元のアルゴリズムを改善する場合、焦点は、新しい計算方法を使用して a の値を減らすことです。

以上が再帰的アルゴリズムの時間計算量はどれくらいですかの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。