Python-data-structure-python-algorithm-analysis

Python-アルゴリズム分析

アルゴリズム分析

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

• アプリオリ分析-これはアルゴリズムの理論的分析です。 アルゴリズムの効率は、プロセッサー速度などの他のすべての要因が一定であり、実装に影響を与えないと仮定して測定されます。
• * A事後分析*-これはアルゴリズムの実証分析です。 選択したアルゴリズムは、プログラミング言語を使用して実装されます。 これは、ターゲットコンピューターマシンで実行されます。 この分析では、実行時間や必要なスペースなどの実際の統計が収集されます。

アルゴリズムの複雑さ

*X* がアルゴリズムであり、 *n* が入力データのサイズであり、アルゴリズムXで使用される時間とスペースが2つの主な要因であり、Xの効率を決定すると仮定します。

• 時間係数-時間は、ソートアルゴリズムの比較などの主要な操作の数をカウントすることで測定されます。
• スペース係数-スペースは、アルゴリズムに必要な最大メモリスペースをカウントすることにより測定されます。

アルゴリズムの複雑さ* f（n）は、入力データのサイズとしての *n に関して、アルゴリズムに必要な実行時間および/またはストレージスペースを与えます。

スペースの複雑さ

アルゴリズムのスペースの複雑さは、そのライフサイクルでアルゴリズムが必要とするメモリスペースの量を表します。 アルゴリズムに必要なスペースは、次の2つのコンポーネントの合計に等しいです-

• 特定のデータと変数を保存するために必要なスペースであり、問​​題のサイズに依存しない固定部分。 たとえば、使用される単純な変数と定数、プログラムサイズなど。
• 変数部分は、変数が必要とするスペースであり、そのサイズは問題のサイズに依存します。 たとえば、動的なメモリ割り当て、再帰スタックスペースなど。

任意のアルゴリズムPの空間複雑度S（P）は、S（P）= C＆plus;です。 SP（I）、ここでCは固定部分で、S（I）はインスタンス特性Iに依存するアルゴリズムの可変部分です。 以下は、概念を説明しようとする簡単な例です-

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

ここには、3つの変数A、B、Cと1つの定数があります。 したがって、S（P）= 1＆plus; 3。 現在、スペースは特定の変数のデータ型と定数型に依存し、それに応じて乗算されます。

時間の複雑さ

アルゴリズムの時間の複雑さは、アルゴリズムが完了するまでに実行するのに必要な時間を表します。 時間要件は数値関数T（n）として定義できます。各ステップが一定の時間を消費する場合、T（n）はステップ数として測定できます。

たとえば、2つのnビット整数の加算には、 n ステップかかります。 したがって、合計計算時間はT（n）= c ∗ nです。ここで、cは2ビットの加算にかかる時間です。 ここで、入力サイズが増加するにつれてT（n）が線形に増加することがわかります。