並列アルゴリズム-分析

アルゴリズムの分析は、アルゴリズムが有用かどうかを判断するのに役立ちます。一般に、アルゴリズムは、実行時間*（時間の複雑さ）および必要なスペースの量（スペースの複雑さ）*に基づいて分析されます。

洗練されたメモリデバイスを手頃な価格で利用できるため、ストレージスペースは問題になりません。したがって、スペースの複雑さはそれほど重要ではありません。

並列アルゴリズムは、コンピューターの計算速度を向上させるように設計されています。並列アルゴリズムを分析するために、通常、次のパラメータを考慮します-

時間の複雑さ（実行時間）、
使用されているプロセッサの合計数、および
総費用。

時間の複雑さ

並列アルゴリズムを開発した主な理由は、アルゴリズムの計算時間を短縮することでした。したがって、アルゴリズムの実行時間を評価することは、その効率を分析する上で非常に重要です。

実行時間は、アルゴリズムが問題を解決するのにかかった時間に基づいて測定されます。合計実行時間は、アルゴリズムが実行を開始してから停止するまでの時間を計算します。すべてのプロセッサが同時に実行を開始または終了しない場合、アルゴリズムの合計実行時間は、最初のプロセッサが実行を開始した瞬間から最後のプロセッサが実行を停止する瞬間までです。

アルゴリズムの時間の複雑さは、3つのカテゴリに分類できます。

最悪の複雑さ-特定の入力のアルゴリズムに必要な時間が*最大*の場合。
平均ケースの複雑さ-特定の入力のアルゴリズムに必要な時間が*平均*の場合。
ベストケースの複雑さ-特定の入力のアルゴリズムに必要な時間が*最小*の場合。

漸近解析

アルゴリズムの複雑さまたは効率は、目的の出力を得るためにアルゴリズムによって実行されるステップの数です。漸近解析は、理論解析でアルゴリズムの複雑さを計算するために行われます。漸近解析では、アルゴリズムの複雑度関数を計算するために長い入力が使用されます。

注-*漸近*は、線が曲線に接する傾向があるが交差しない条件です。ここで、直線と曲線は互いに漸近しています。

漸近表記法は、速度の上限と下限を使用するアルゴリズムの可能な限り最も速い実行時間と最も遅い実行時間を記述する最も簡単な方法です。このために、我々は次の表記法を使用します-

ビッグオー表記
オメガ表記
シータ表記

ビッグオー表記

数学では、関数の漸近的特性を表すためにBig O表記が使用されます。シンプルで正確な方法で、大規模な入力に対する関数の動作を表します。これは、アルゴリズムの実行時間の上限を表す方法です。これは、アルゴリズムが実行を完了するのにかかる最長時間を表します。機能-

f（n）= O（g（n））

すべての n に対して f（n）≤c g（n）となる正の定数 *c および* n〜0〜が存在する場合（ただし、 n≥n〜0〜*）。

オメガ表記

オメガ表記法は、アルゴリズムの実行時間の下限を表す方法です。機能-

f（n）=Ω（g（n））

すべての n に対して f（n）≥c g（n）となる正の定数 *c および* n〜0〜が存在する場合（ n≥n〜0〜*）。

シータ表記

シータ表記は、アルゴリズムの実行時間の下限と上限の両方を表す方法です。機能-

f（n）=θ（g（n））

すべての n に対してc1 g（n）≤f（n）≤c2 g（n）となるような正の定数* c〜1〜、c〜2〜、および n〜0〜が存在する場合 n≥n〜0〜*。

アルゴリズムの高速化

並列アルゴリズムのパフォーマンスは、 speedup を計算することにより決定されます。スピードアップは、特定の問題に対する既知の最速のシーケンシャルアルゴリズムの最悪の場合の実行時間と、パラレルアルゴリズムの最悪の場合の実行時間の比率として定義されます。

スピードアップ=

Worst case execution time of the fastest known sequential for a particular problem / Worst case execution time of the parallel algorithm

使用プロセッサ数

使用されるプロセッサの数は、並列アルゴリズムの効率を分析する上で重要な要素です。コンピューターの購入、保守、および実行のコストが計算されます。問題を解決するためにアルゴリズムが使用するプロセッサーの数が増えると、得られる結果がより高価になります。

総費用

並列アルゴリズムの総コストは、時間の複雑さと特定のアルゴリズムで使用されるプロセッサの数の積です。

総コスト=時間の複雑さ×使用するプロセッサの数

したがって、並列アルゴリズムの*効率*は-

効率=

Worst case execution time of sequential algorithm / Worst case execution time of the parallel algorithm

Parallel-algorithm-analysis

目次