什么是后验和先验分析的算法操作



我是一名新开发人员。请帮助我理解算法运算的a后验a先验分析是什么。我用谷歌搜索了一下,但没有得到任何正确的答案。

算法的Apriori分析:这意味着我们在特定系统上运行算法之前对算法进行(空间和时间)分析——也就是说,我们通过观察算法来确定算法的时间和空间复杂度,而不是在特定系统(不同的处理器和编译器)上运行算法。

算法的Apostiari分析:即算法在系统上运行后才进行分析。它直接依赖于系统,并且随着系统的不同而变化。

在行业中,我们不能做Apostiari分析,因为软件通常是为匿名用户开发的,该用户在不同的系统上运行(在处理器上,如Pentium 3或Pentium 4)。

在Apriory中,这就是我们使用渐近符号来确定时间和空间复杂性的原因,因为它们在不同的计算机之间变化,但渐近它们是相同的。

先验分析-这是关于算法的理论分析。算法的效率是通过假设所有其他因素(例如处理器速度)都是恒定的并且对实现没有影响来衡量的。

A Posterior Analysis -这更像是对算法的实证分析。所选算法用编程语言实现,然后在目标机上执行。在此分析中,将收集实际统计数据,如运行时间和所需空间。

总之

在一个优先分析中,我们得到了一个约束算法的函数计算时间。

在后验分析中,我们收集实际统计数据关于算法的时间和空间消耗,虽然它是执行。

书在这儿。

有点长:

维基百科的定义

另一篇文章引用

到目前为止,分析算法最重要的原因是使肯定能正确解决你的问题。如果我们的算法没有工作,其他都不重要。所以我们必须分析它来证明它总是会像预期的那样工作。

我们还必须考虑算法的效率。如果它能解决问题,但在O(nn)时间(或空间!)内完成,那么我们应该可能会考虑重新设计。

在后验分析中,我们在系统上运行算法以检查其原始静态,以便我们可以计算其时间和空间复杂性。但由于系统不同,效果也不同,所以效果不是很好。我们根据一个特定的系统需求来计算它的时间复杂度。

在先前的分析中,我们只看到算法,并根据渐近符号给出它的分析。它不会改变系统间的渐近符号

在《管理软件测试》(Peter farrel - vinay)的12.7节中,先验分析是使用一些理论模型(如有限状态机)定义函数的阶段。然后使用该模型确定该函数的各种特征(如时间和空间使用)。

a后验阶段,收集函数特征(如时间和空间使用)的证据,并与先验分析计算的结果进行比较。

后验分析取决于硬件算法和编程语言算法,它会给出确切的答案

先验分析与硬件无关,它取决于语句执行的次数

最新更新