并行算法-分析

对算法的分析可以帮助我们确定该算法是否有用。通常，根据算法的执行时间（时间复杂度）和所需的空间量（空间复杂度）来分析算法。

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

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

时间复杂度

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

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

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

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

注意-渐近是直线趋于与曲线相交但它们不相交的情况。这里直线和曲线彼此渐近。

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

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

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)。

Theta 表示法是一种表示算法执行时间的下限和上限的方法。该函数 -

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

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

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

加速比=

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

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

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

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

因此，并行算法的效率是 -

效率=

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