並行演算法 - 分析

演算法分析幫助我們確定演算法是否有用。通常，演算法的分析是基於其執行時間（時間複雜度）和所需的儲存空間（空間複雜度）。

由於我們擁有價格合理的先進儲存裝置，儲存空間不再是一個問題。因此，空間複雜度不再那麼重要。

並行演算法旨在提高計算機的計算速度。在分析並行演算法時，我們通常考慮以下引數：

時間複雜度

開發並行演算法的主要原因是減少演算法的計算時間。因此，評估演算法的執行時間對於分析其效率至關重要。

執行時間是根據演算法解決問題所花費的時間來衡量的。總執行時間是從演算法開始執行到停止執行的那一刻計算的。如果所有處理器並非同時開始或結束執行，則演算法的總執行時間是從第一個處理器開始執行的那一刻到最後一個處理器停止執行的那一刻。

演算法的時間複雜度可以分為三類：

演算法的複雜度或效率是指演算法為獲得所需輸出而執行的步驟數。漸近分析用於在其理論分析中計算演算法的複雜度。在漸近分析中，使用較長的輸入長度來計算演算法的複雜度函式。

注意 - 漸近線是指一條線趨向於與曲線相交，但它們並不相交。此處，直線和曲線彼此漸近。

漸近符號是使用速度的高限和低限來描述演算法最快和最慢可能的執行時間的簡便方法。為此，我們使用以下符號：

在數學中，大O符號用於表示函式的漸近特性。它以簡單而準確的方法表示函式在大輸入下的行為。這是一種表示演算法執行時間上限的方法。它表示演算法完成執行所需的最長時間。函式：

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

當且僅當存在正常數c和n₀使得對於所有n（其中n ≥ n₀）f(n) ≤ c * g(n)。

歐米茄符號是一種表示演算法執行時間下限的方法。函式：

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

當且僅當存在正常數c和n₀使得對於所有n（其中n ≥ n₀）f(n) ≥ c * g(n)。

西塔符號是一種表示演算法執行時間下限和上限的方法。函式：

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

當且僅當存在正常數c₁, c₂,和n₀使得對於所有n（其中n ≥ n₀）c1 * g(n) ≤ f(n) ≤ c2 * g(n)。

並行演算法的效能是透過計算其加速比來確定的。加速比定義為特定問題的最快已知順序演算法的最壞情況執行時間與並行演算法的最壞情況執行時間的比率。

加速比 =

特定問題最快已知順序演算法的最壞情況執行時間 / 並行演算法的最壞情況執行時間

使用的處理器數量是分析並行演算法效率的重要因素。計算購買、維護和執行計算機的成本。演算法用於解決問題所使用的處理器越多，獲得的結果就越昂貴。

並行演算法的總成本是時間複雜度和該特定演算法中使用的處理器數量的乘積。

總成本 = 時間複雜度 × 使用的處理器數量

因此，並行演算法的效率為：

效率 =

順序演算法的最壞情況執行時間 / 並行演算法的最壞情況執行時間

列印頁面