データ構造-アルゴリズムの基本

アルゴリズムは段階的な手順であり、目的の出力を取得するために特定の順序で実行される一連の命令を定義します。アルゴリズムは通常、基礎となる言語から独立して作成されます。つまり、アルゴリズムは複数のプログラミング言語で実装できます。

データ構造の観点から、以下はアルゴリズムのいくつかの重要なカテゴリです-

Search −データ構造内のアイテムを検索するアルゴリズム。
Sort −アイテムを特定の順序で並べ替えるアルゴリズム。
Insert −データ構造にアイテムを挿入するアルゴリズム。
Update −データ構造内の既存のアイテムを更新するアルゴリズム。
Delete −データ構造から既存のアイテムを削除するアルゴリズム。

アルゴリズムの特徴

すべてのプロシージャをアルゴリズムと呼ぶことができるわけではありません。アルゴリズムには次の特性が必要です-

Unambiguous−アルゴリズムは明確で明確でなければなりません。その各ステップ（またはフェーズ）、およびそれらの入力/出力は明確である必要があり、1つの意味のみにつながる必要があります。
Input −アルゴリズムには、0個以上の明確に定義された入力が必要です。
Output −アルゴリズムには、明確に定義された1つ以上の出力があり、目的の出力と一致している必要があります。
Finiteness −アルゴリズムは、有限のステップ数の後に終了する必要があります。
Feasibility −利用可能なリソースで実行可能である必要があります。
Independent −アルゴリズムには段階的な指示が必要であり、プログラミングコードから独立している必要があります。

アルゴリズムの書き方は？

アルゴリズムを作成するための明確に定義された標準はありません。むしろ、それは問題とリソースに依存します。特定のプログラミングコードをサポートするようにアルゴリズムが作成されることはありません。

すべてのプログラミング言語は、ループ（do、for、while）、フロー制御（if-else）などの基本的なコード構造を共有していることがわかっています。これらの一般的な構造を使用して、アルゴリズムを記述できます。

アルゴリズムは段階的に記述しますが、常にそうであるとは限りません。アルゴリズムの記述はプロセスであり、問題のドメインが明確に定義された後に実行されます。つまり、ソリューションを設計している問題のドメインを知る必要があります。

例

例を使ってアルゴリズムの書き方を学んでみましょう。

Problem − 2つの数値を加算し、結果を表示するアルゴリズムを設計します。

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

アルゴリズムは、プログラマーにプログラムのコーディング方法を指示します。あるいは、アルゴリズムは次のように書くことができます-

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

アルゴリズムの設計と分析では、通常、2番目の方法を使用してアルゴリズムを記述します。これにより、アナリストは不要な定義をすべて無視してアルゴリズムを簡単に分析できます。彼は、使用されている操作とプロセスの流れを観察できます。

書き込み step numbers、はオプションです。

与えられた問題の解決策を得るためのアルゴリズムを設計します。問題は複数の方法で解決できます。

したがって、特定の問題に対して多くのソリューションアルゴリズムを導出できます。次のステップは、提案されたソリューションアルゴリズムを分析し、最適なソリューションを実装することです。

アルゴリズム分析

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

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

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

アルゴリズムの複雑さ

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

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

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

スペースの複雑さ

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

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

任意のアルゴリズムPの空間複雑度S（P）はS（P）= C + 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 + 3です。ここで、スペースは指定された変数と定数タイプのデータ型に依存し、それに応じて乗算されます。

時間計算量

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

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