并行算法 - 分析

对算法的分析可以帮助我们确定该算法是否有用。 一般来说，算法是根据其执行时间(时间复杂度)和所需的空间量(空间复杂度)来分析的。

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

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

• 时间复杂度(执行时间)，
• 使用的处理器总数，以及
• 总成本。

时间复杂度

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

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

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

• 最坏情况的复杂性 − 当给定输入的算法所需的时间量为最大值时。

• 平均情况复杂度 − 当给定输入的算法所需的时间为平均值时。

• 最佳情况复杂性 − 当给定输入的算法所需的时间为最小值时。

渐近分析

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

注意 − 渐近是一种直线趋于与曲线相交但不相交的情况。 这里直线和曲线是渐近的。

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

• 大O表示法
• 欧米茄表示法
• θ 符号

大O表示法

在数学中，大O表示法用于表示函数的渐近特征。 它以简单而准确的方法表示大输入时函数的行为。 它是一种表示算法执行时间上限的方法。 它表示算法完成其执行所需的最长时间。 公式 −

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

当且仅当存在正常数 c 和 n₀ 时，对于所有 n(其中 n ≥ n₀)，f(n) ≤ c * g(n) 成立。

欧米茄表示法

欧米茄表示法是一种表示算法执行时间下限的方法。 公式 −

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

如果存在正常数c和n₀，则f(n) ≥ c * g(n)对于所有n，其中n ≥ n₀。

Theta 表示法

Theta 表示法是一种表示算法执行时间的下限和上限的方法。 公式 −

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

当且仅当存在正常数 c₁, c₂, 和 n₀ 时，使得 c1 * g(n) ≤ f(n) ≤ c2 * g(n) 对于所有 n ，其中n ≥ n₀ 。

算法加速

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

使用的处理器数量

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

总成本

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

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

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