Data Structures-Algorithms Basics

Posted on
Advertisements

アルゴリズムは、目的の出力を得るために特定の順序で実行される命令のセットを定義するステップバイステップのプロシージャです。 アルゴリズムは一般に基礎となる言語とは独立して作成され、アルゴリズムは複数のプログラミング言語で実装できます。,

データ構造の観点から、以下のアルゴリズムのいくつかの重要なカテゴリーがあります−

  • 検索−データ構造内の項目を検索するアルゴリズム。

  • Sort−アイテムを特定の順序でソートするアルゴリズム。

  • Insert-データ構造にアイテムを挿入するアルゴリズム。

  • Update-データ構造内の既存のアイテムを更新するアルゴリズム。

  • Delete-データ構造から既存のアイテムを削除するアルゴリズム。

アルゴリズムの特性

すべてのプロシージャがアルゴリズムと呼ばれるわけではありません。, アルゴリズムは次の特性を持つ必要があります−

  • 明確−アルゴリズムは明確かつ明確でなければなりません。 その各ステップ（またはフェーズ）、およびそれらの入力/出力は明確でなければならず、唯一の意味につながる必要があります。

  • 入力-アルゴリズムは0以上の明確に定義された入力を持つ必要があります。

  • 出力-アルゴリズムには1つ以上の明確に定義された出力があり、目的の出力と一致する必要があります。

  • 有限性-アルゴリズムは有限数のステップの後に終了する必要があります。,

  • 実現可能性-利用可能なリソースで実現可能でなければなりません。

  • 独立−アルゴリズムは、任意のプログラミングコードから独立している必要があり、ステップバイステップの方向を持つ必要があります。/p>

アルゴリズムを書くには？

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

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

我々は、ステップバイステップの方法でアルゴリズムを書くが、それは常にそうではありません。 アルゴリズム書き込みはプロセスであり、問題領域が明確に定義された後に実行されます。 つまり、ソリューションを設計している問題領域を知る必要があります。

Example

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

問題−二つの数字を追加し、結果を表示するアルゴリズムを設計します。

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

アルゴリズムは、プログラムのコーディング方法をプログラマに伝えます。, あるいは、アルゴリズムは−

Step 1 − START ADDStep 2 − get values of a & bStep 3 − c ← a + bStep 4 − display cStep 5 − STOP

アルゴリズムの設計と分析では、通常、第二の方法は、アルゴリズムを記述するために使用されます。 アナリストは、不要な定義をすべて無視してアルゴリズムを簡単に分析できます。 彼は認められる業務に使用して、どのように流れています。

ステップ番号の書き込みはオプションです。

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

したがって、与えられた問題に対して多くの解アルゴリズムを導出することができます。 次のステップは，提案された解アルゴリズムを分析し，最適な解を実装することである。

アルゴリズム解析

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

  • 先験的分析−これはアルゴリズムの理論的分析です。, アルゴリズムの効率は、プロセッサ速度などの他のすべての要因が一定であり、実装に影響を与えないと仮定することによって測定されます。

  • 事後分析−これはアルゴリズムの経験的分析です。 選択したアルゴリズムを実装用のプログラミング言語. その後、実行対象コンピュータ機です。 この分析では、実行時間や必要なスペースなどの実際の統計が収集されます。

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

アルゴリズムの複雑さ

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

  • 時間因子−時間は、ソートアルゴリズムにおける比較などのキー操作の数を数えることによって測定される。,

  • スペースファクタ−スペースは、アルゴリズムに必要な最大メモリ空間を数えることによって測定されます。アルゴリズムｆ（ｎ）の複雑さは、入力データのサイズとしてｎの観点から、アルゴリズムに必要とされる実行時間および／または記憶空間を与える。

    スペースの複雑さ

    アルゴリズムのスペースの複雑さは、アルゴリズムのライフサイクルにおいて必要なメモリ空間の量を表します。, アルゴリズムに必要なスペースは、次の二つのコンポーネントの合計に等しいです−

    • 特定のデータと変数を格納するために必要なスペースである固定部分 たとえば、使用される単純な変数や定数、プログラムサイズなどです。

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

    任意のアルゴリズムPの空間複雑度S(P)はS(P)=C+SP(I)ここで、Cは固定部分であり、S(I)はインスタンス特性Iに依存するアルゴリズムの変数部分です。

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

    ここでは、三つの変数A、Bがあります。、およびcと一つの定数。 したがって、S(P)=1&プラス;3。 これで、スペースは与えられた変数と定数型のデータ型に依存し、それに応じて乗算されます。,

    時間複雑度

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

    たとえば、二つのnビット整数の加算はnステップをとります。 したがって、総計算時間はＴ（ｎ）＝ｃ∈ｎであり、ここで、ｃは二つのビットの加算にかかる時間である。 ここでは、入力サイズが大きくなるにつれてt(n)が線形に成長することを観察します。,

    広告

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です