時間計算量と空間計算量

一般に、時間計算量 と 空間計算量 は、リソース使用量がどのようにスケールされるかに基づいてアルゴリズムの効率を測定する方法です。入力のサイズ。基本といくつかの一般的な例を見てみましょう。

時間計算量

時間計算量は、入力のサイズ (通常は n で示されます) に基づいてアルゴリズムが完了するまでにかかる時間を表します。

1. 定数時間 – O(1):

   • アルゴリズムの実行時間は入力サイズによって変わりません。
   • 例: arr[5] のように、インデックスによって配列内の要素にアクセスします。

2. 対数時間 – O(log n):

   • アルゴリズムの実行時間は、入力サイズが増加するにつれて対数的に増加します。これは、各ステップで問題が半分に分割されることを意味します。
   • 例: ソートされた配列の二分探索。

3. 線形時間 – O(n):

   • アルゴリズムの実行時間は、入力サイズに応じて直線的に増加します。
   • 例: n 要素の配列を 1 回走査します。

4. 線形時間 – O(n log n):

   • 各要素が対数的に処理される効率的な並べ替えアルゴリズムでは一般的で、通常は再帰的な除算と線形結合または処理が原因です。
   • 例: マージソート、クイックソート。

5. 二次時間 – O(n²):

   • 実行時間は入力サイズの 2 乗に比例して増加します。
   • 例: 配列内の各要素を他のすべての要素と比較するなど、ネストされたループ。

6. 3 次時間 – O(n³):

   • 実行時間は入力サイズの 3 乗に応じて増加します。まれですが、3 つのネストされたループを含むアルゴリズムで発生する可能性があります。
   • 例: ブルート フォース アルゴリズムを使用して特定の行列演算を解決します。

7. 指数時間 – O(2^n):

   • 入力に要素が追加されるたびに、実行時間は 2 倍になります。通常は、考えられるすべての組み合わせで部分問題を解決する再帰的アルゴリズムによるものです。
   • 例: フィボナッチ数列の単純な解法。各呼び出しがさらに 2 つの呼び出しにつながります。

8. 階乗時間 – O(n!):

   • 実行時間は入力サイズに比例して増加します。多くの場合、考えられるすべての順列または組み合わせの生成を伴うアルゴリズムからのものです。
   • 例: 巡回セールスマンの問題を総当たりで解決します。

空間の複雑さ

空間複雑度は、入力サイズと比較してアルゴリズムが使用するメモリの量を測定します。

1. 定数スペース – O(1):

   • アルゴリズムは、入力サイズに関係なく、固定量のメモリを使用します。
   • 例: 整数やカウンターなどのいくつかの変数を保存します。

2. 対数空間 – O(log n):

   • メモリ使用量は対数的に増加します。これは、各ステップで問題を半分にする再帰的アルゴリズムでよく見られます。
   • 例: 再帰的二分探索 (呼び出しスタックによるスペースの複雑さ)。

3. 線形空間 – O(n):

   • メモリ使用量は入力サイズに応じて直線的に増加します。これは、入力を保存するために追加の配列またはデータ構造を作成するときによく発生します。
   • 例: サイズ n の配列のコピーを作成します。

4. 二次空間 – O(n²):

   • サイズ n x n の 2D 行列を保存する場合など、メモリ使用量は入力サイズの 2 乗に応じて増加します。
   • 例: n 個のノードを持つグラフの隣接行列を保存します。

5. 指数空間 – O(2^n):

   • メモリ使用量は、入力の可能なサブセットごとにデータを保存する再帰的ソリューションで多くの場合、入力サイズに応じて指数関数的に増加します。
   • 例: 多くの重複する部分問題を伴う再帰的アルゴリズムにおけるメモ化。

実践例

• 線形時間 (O(n)) および線形空間 (O(n)):

  • 配列を反復処理し、各要素を新しい配列に格納する関数。

• 二次時間 (O(n²)) と定空間 (O(1)):

  • 配列に対して 2 つのネストされたループを持つ関数ですが、いくつかの変数を超える追加のストレージは必要ありません。

複雑さを分析する

時間と空間の複雑さについてコードを分析する場合:

1. ループを特定する: ネストされたループは通常、複雑さを増加させます (例: 1 つのループでは ( O(n) ) が与えられ、2 つのネストされたループでは ( O(n^2) ) が与えられます。
2. 再帰を探します: 再帰呼び出しは、分岐係数と再帰の深さに応じて、時間と空間が指数関数的に複雑になる可能性があります。
3. データ構造を考慮する: 配列、リスト、ハッシュ マップなどの追加のデータ構造を使用すると、空間の複雑さに影響を与える可能性があります。

一般的なヒント

• 時間計算量 は、入力サイズの関数として操作をカウントすることについてです。
• 空間の複雑さ は、必要な追加メモリの量をカウントすることです。

これらの要素を評価することで、アルゴリズムがどの程度効率的に実行されるか、また入力サイズに基づいて消費されるメモリの量を推定できます。

以上が時間計算量と空間計算量の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。