アルゴリズムの分類と例

アルゴリズムの分類は、特定のタスクに最適なアルゴリズムを選択するのに役立ち、開発者がコードを最適化してパフォーマンスを向上させることができます。コンピューター サイエンスにおいて、アルゴリズムとは、問題を解決したり特定のタスクを実行したりするために使用される、明確に定義された一連の命令です。これらのアルゴリズムの効率と有効性は、プログラムの全体的なパフォーマンスを決定する上で重要です。

この記事では、アルゴリズムを分類する 2 つの一般的な方法、つまり時間計算量に基づく方法と設計手法に基づく方法について説明します。

main 関数の構文は両方のメソッドのコードで使用されます -

解決すべき問題を決定します。

• アルゴリズムを分類する適切な方法を選択します。

• 選択した方法を使用して C でコードを作成します。

• コードをコンパイルして実行します。

• 出力を分析します。

• 時間計算量とは何ですか?

時間計算量は、入力サイズの関数としてアルゴリズムの実行にかかる時間を測定します。これは、入力サイズの増加に伴うアルゴリズムの効率とスケーラビリティを説明する方法です。

時間計算量は通常、アルゴリズムの実行時間の上限を与えるビッグ O 表記法で表現されます。たとえば、時間計算量が O(1) のアルゴリズムは、入力サイズに関係なく実行時間が一定のままであることを意味しますが、時間計算量が O(n^2) のアルゴリズムは、実行時間が時間に応じて二次関数的に増加することを意味します。入力サイズです。アルゴリズムの時間計算量を理解することは、問題を解決するために適切なアルゴリズムを選択するとき、およびさまざまなアルゴリズムを比較するときに重要です。

方法 1: 時間計算量に基づいてアルゴリズムを分類する

このアプローチでは、時間計算量に基づいてアルゴリズムを分類します。

これには、まずアルゴリズムの継続時間計算量を解釈し、次に経過時間計算量に基づいて次の 5 つのカテゴリのいずれかに分類する必要があります。 O(1) 定数時間計算量、O(log n) 対数 時間計算量、O(n ) 線形時間計算量、O(n^2) 二次時間計算量、または O(2^n) 指数時間計算量。この分類によりアルゴリズムの有効性が明らかになり、アルゴリズムを選択する際に入力データのサイズと予想される完了時間を考慮することができます。

Example-1

Example-1

以下のコードは、線形時間計算量が O(n) の線形検索アルゴリズムのデモを示しています。このアルゴリズムは、配列内の要素の系統的なチェックを実行して、指定された検索要素に一致する要素があるかどうかを判断します。見つかった場合、関数は要素のインデックスを返します。それ以外の場合は、要素が配列内にないことを示す -1 を返します。 main 関数は、配列の初期化と要素の検索から始まり、linearSearch 関数を呼び出して、最後に結果を表示します。

方法 2: 設計手法に基づいてアルゴリズムを分類します。

分析アルゴリズムの設計スキル。

アルゴリズムを次のカテゴリのいずれかに分類します -
ブルートフォースアルゴリズム

• 分割統治アルゴリズム
  貪欲なアルゴリズム
  動的プログラミング アルゴリズム
  バックトラッキングアルゴリズム

  • Example-2

    の中国語訳は次のとおりです:
  Example-2
次のプログラムは、分割統治戦略を使用し、対数時間計算量 O(log n) を持つ二分探索アルゴリズムの実装を示しています。このアルゴリズムは、配列を繰り返し 2 つの部分に分割し、中央の要素をチェックします。この中間要素が検索対象の検索要素と等しい場合、インデックスが直ちに返されます。中央の要素が検索要素を超える場合、検索は配列の左半分で続行され、中央の要素が小さい場合、検索は右半分で続行されます。 main 関数は、配列を初期化して要素を検索し、並べ替えによって配列を配置し、binarySearch 関数を呼び出して、最後に結果を表示します。

したがって、この記事では、分類アルゴリズムに対する 2 つのアプローチ (時間計算量に基づくものと設計方法に基づくもの) について説明します。例として、C で実装された線形探索アルゴリズムと二分探索アルゴリズムを紹介します。線形探索アルゴリズムは総当たり法を使用し、線形時間計算量は O(n) ですが、二分探索アルゴリズムは分割統治法を使用し、対数計算量は O(log n) です。アルゴリズムのさまざまな分類を完全に理解すると、特定のタスクに最適なアルゴリズムを選択し、コードを改善してパフォーマンスを向上させるのに役立ちます。

以上がアルゴリズムの分類と例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。