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

アルゴリズムは、目的の出力を取得するために特定の順序で実行される一連の命令を定義するステップバイステップの手順です。アルゴリズムは通常、基礎となる言語とは無関係に作成されます。アルゴリズムは複数のプログラミング言語で実装できます。

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

検索-データ構造内のアイテムを検索するアルゴリズム。
ソート-特定の順序でアイテムをソートするアルゴリズム。
挿入-データ構造にアイテムを挿入するアルゴリズム。
更新-データ構造内の既存のアイテムを更新するアルゴリズム。
削除-データ構造から既存のアイテムを削除するアルゴリズム。

アルゴリズムの特性

すべての手順がアルゴリズムと呼ばれるわけではありません。アルゴリズムは、次の特性を持つ必要があります-

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

アルゴリズムの書き方

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

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

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

例

例を使用して、アルゴリズムの記述を学習してみましょう。

問題-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 &plus; b
Step 4 − display c
Step 5 − STOP

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

ステップ番号*の記述はオプションです。

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

1つの問題、多くの解決策

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

アルゴリズム分析

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

A Priori Analysis -これはアルゴリズムの理論的分析です。アルゴリズムの効率は、プロセッサー速度などの他のすべての要因が一定であり、実装に影響を与えないと仮定して測定されます。
* _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 &plus; B &plus; 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）が線形に増加することがわかります。

Data-structures-algorithms-algorithms-basics

目次