データ構造における時間と空間の複雑さ

アルゴリズム分析

アルゴリズムの効率の分析は、実装前と実装後の2つの異なる段階で実行できます。

事前分析-これは、アルゴリズムの理論的分析として定義されます。アルゴリズムの効率は、他のすべての要因を想定して測定されます。プロセッサの速度は一定であり、実装には影響しません。

事後分析-これは、アルゴリズムの経験的分析として定義されます。選択したアルゴリズムは、プログラミング言語を使用して実装されます。次に、選択したアルゴリズムがターゲットコンピュータマシンで実行されます。この分析では、実行時間や必要なスペースなどの実際の統計が収集されます。

アルゴリズム分析は、関連するさまざまな操作の実行時間または実行時間を処理します。操作の実行時間は、操作ごとに実行されるコンピューター命令の数として定義できます。

アルゴリズムの複雑さ

Xがアルゴリズムとして扱われ、Nが入力データのサイズとして扱われるとすると、アルゴリズムXによって実装される時間と空間は、Xの効率を決定する2つの主な要因です。

時間係数-時間は、並べ替えアルゴリズムの比較などの主要な操作の数を数えることによって計算または測定されます。

スペースファクター-スペースは、アルゴリズムに必要な最大メモリスペースをカウントすることによって計算または測定されます。

アルゴリズムの複雑さf（N）は、入力データのサイズとしてのNに関して、アルゴリズムに必要な実行時間やストレージスペースを提供します。

スペースの複雑さ

アルゴリズムのスペースの複雑さは、アルゴリズムのライフサイクルで必要なメモリスペースの量を表します。

アルゴリズムに必要なスペースは、次の2つのコンポーネントの合計に等しくなります

問題のサイズに依存しない、特定のデータと変数（つまり、単純な変数と定数、プログラムサイズなど）を格納するために必要なスペースである固定部分。

変数部分は変数に必要なスペースであり、そのサイズは問題のサイズに完全に依存します。たとえば、再帰スタックスペース、動的メモリ割り当てなど。

任意のアルゴリズムpの空間複雑度S（p）はS（p）=A + Sp（I）です。ここで、Aは固定部分として扱われ、S（I）はインスタンス特性Iに依存するアルゴリズムの可変部分として扱われます。 。以下は、概念を説明しようとする簡単な例です

アルゴリズム

SUM(P, Q)
Step 1 - START
Step 2 - R ← P + Q + 10
Step 3 - Stop

ここでは、3つの変数P、Q、Rと1つの定数があります。したがって、S（p）=1+3です。現在、スペースは特定の定数型と変数のデータ型に依存しており、それに応じて乗算されます。

時間計算量

アルゴリズムの時間計算量は、アルゴリズムが実行して完了するまでに必要な時間を表します。時間要件は、数値関数t（N）として表すか、定義できます。ここで、t（N）は、各ステップに一定の時間がかかる場合、ステップ数として測定できます。

たとえば、2つのnビット整数を加算する場合、Nステップが実行されます。したがって、合計計算時間はt（N）=c * nです。ここで、cは2ビットの加算にかかる時間です。ここでは、入力サイズが大きくなるにつれてt（N）が直線的に増加することを確認しています。