parallel-processing - 並列アルゴリズムの漸近実行時間の定義

Question

私は並列アルゴリズムを理解する初心者です。並列アルゴリズムの漸近的実行時間が何を意味するかを簡単な言葉[または例]で説明できますか?

コンテキスト: 問題 π に対する最もよく知られている逐次アルゴリズムの漸近実行時間が S(n) であり、T(n,p) が並列アルゴリズムの漸近実行時間である場合、並列アルゴリズムの漸近的高速化が定義されます。 as S(n)/T(n,p) S(n)/T(n,p) = Ɵ(p) の場合、アルゴリズムは線形速度が向上したと言われます。

Answer 1

並列アルゴリズムの漸近的な実行時間は、通常、p 個のプロセッサを使用するアルゴリズムが正しい解を得るために必要な時間を意味します。ただし、アルゴリズムの分析は常に、使用しているモデルに依存します。あなたの質問に対する満足のいく答えは長くなりすぎます。Introduction to Algorithmsの第 27 章を読むことを強くお勧めします。並列アルゴリズムの解析を理解するのに最適なテキストです。最初の数ページで、おそらくあなたの質問に対する答えが見つかるでしょう。