並列アルゴリズム-分析

アルゴリズムの分析は、アルゴリズムが有用かどうかを判断するのに役立ちます。一般に、アルゴリズムはその実行時間に基づいて分析されます(Time Complexity) とスペースの量 (Space Complexity) 必要です。

洗練されたメモリデバイスをリーズナブルなコストで利用できるため、ストレージスペースはもはや問題ではありません。したがって、スペースの複雑さはそれほど重要ではありません。

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

  • 時間計算量(実行時間)、
  • 使用されたプロセッサの総数、および
  • 総費用。

時間計算量

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

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

アルゴリズムの時間計算量は、3つのカテゴリに分類できます-

  • Worst-case complexity −特定の入力に対してアルゴリズムに必要な時間が次の場合 maximum

  • Average-case complexity −特定の入力に対してアルゴリズムに必要な時間が次の場合 average

  • Best-case complexity −特定の入力に対してアルゴリズムに必要な時間が次の場合 minimum

漸近解析

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

NoteAsymptotic線が曲線と交わる傾向があるが、それらが交差しない状態です。ここでは、線と曲線は互いに漸近的です。

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

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

ビッグO表記

数学では、関数の漸近特性を表すためにBigO表記が使用されます。これは、単純で正確な方法で、大きな入力に対する関数の動作を表します。これは、アルゴリズムの実行時間の上限を表す方法です。これは、アルゴリズムが実行を完了するのにかかる可能性のある最長の時間を表します。関数-

f(n)= O(g(n))

正の定数が存在する場合 c そして n0 そのような f(n) ≤ c * g(n) すべてのために n どこ n ≥ n0

オメガ表記

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

f(n)=Ω(g(n))

正の定数が存在する場合 c そして n0 そのような f(n) ≥ c * g(n) すべてのために n どこ n ≥ n0

シータ表記

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

f(n)=θ(g(n))

正の定数が存在する場合 c1, c2, そして n0 すべてについてc1 * g(n)≤f(n)≤c2* g(n)となるように n どこ n ≥ n0

アルゴリズムの高速化

並列アルゴリズムのパフォーマンスは、その計算によって決定されます speedup。スピードアップは、特定の問題に対する最速の既知の順次アルゴリズムの最悪の実行時間と、並列アルゴリズムの最悪の実行時間の比率として定義されます。

スピードアップ=
特定の問題に対する最速の既知のシーケンシャルの 最悪実行時間/ 並列アルゴリズムの最悪実行時間

使用されたプロセッサーの数

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

総費用

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

総コスト=時間計算量×使用されたプロセッサの数

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

効率=
シーケンシャルアルゴリズムの 最悪実行時間/ 並列アルゴリズムの最悪実行時間