并行算法 - 分析

算法分析帮助我们确定算法是否有用。通常，算法的分析是基于其执行时间（时间复杂度）和所需的存储空间（空间复杂度）。

由于我们拥有价格合理的先进存储设备，存储空间不再是一个问题。因此，空间复杂度不再那么重要。

并行算法旨在提高计算机的计算速度。在分析并行算法时，我们通常考虑以下参数：

时间复杂度

开发并行算法的主要原因是减少算法的计算时间。因此，评估算法的执行时间对于分析其效率至关重要。

执行时间是根据算法解决问题所花费的时间来衡量的。总执行时间是从算法开始执行到停止执行的那一刻计算的。如果所有处理器并非同时开始或结束执行，则算法的总执行时间是从第一个处理器开始执行的那一刻到最后一个处理器停止执行的那一刻。

算法的时间复杂度可以分为三类：

算法的复杂度或效率是指算法为获得所需输出而执行的步骤数。渐近分析用于在其理论分析中计算算法的复杂度。在渐近分析中，使用较长的输入长度来计算算法的复杂度函数。

注意 - 渐近线是指一条线趋向于与曲线相交，但它们并不相交。此处，直线和曲线彼此渐近。

渐近符号是使用速度的高限和低限来描述算法最快和最慢可能的执行时间的简便方法。为此，我们使用以下符号：

在数学中，大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)。

并行算法的性能是通过计算其加速比来确定的。加速比定义为特定问题的最快已知顺序算法的最坏情况执行时间与并行算法的最坏情况执行时间的比率。

加速比 =

特定问题最快已知顺序算法的最坏情况执行时间 / 并行算法的最坏情况执行时间

使用的处理器数量是分析并行算法效率的重要因素。计算购买、维护和运行计算机的成本。算法用于解决问题所使用的处理器越多，获得的结果就越昂贵。

并行算法的总成本是时间复杂度和该特定算法中使用的处理器数量的乘积。

总成本 = 时间复杂度 × 使用的处理器数量

因此，并行算法的效率为：

效率 =

顺序算法的最坏情况执行时间 / 并行算法的最坏情况执行时间

打印页面