您如何证明一种算法比另一种算法更有效？

Question

我不是专业的程序员,我也不研究它.我是一名航空航天学生,为我的毕业论文做了一个数字方法,并编写了一个程序来证明它是有效的.

我做了几种方法并实现了几种算法,并试图证明为什么不同的情况需要他们自己的算法来解决任务.

我用数学方法做了这个证明,但是有些算法是如此具体,以至于我确实知道他们做了什么并且他们做得对,但很难找到一个数学函数或某些东西来显示它有多少次迭代或循环直到它完成.

所以,我想知道你是如何进行这种比较的.你是否也提出了一个数学函数,或者你只是对这两种算法进行了最快速的测试,如果你以数学方式进行,你是如何做到的？你在大学期间学到了这个,或者怎么样？

安德烈亚斯,提前谢谢你

Answer 1

比较不同算法的标准方法是使用Big O表示法比较它们的复杂性.在实践中,您当然也会对算法进行基准测试.

作为示例,排序算法冒泡排序和堆排序分别具有复杂度O(n ²)和O(n log n).

作为最后一点,很难构建具有代表性的基准,请参阅Christer Ericsson关于此主题的这篇有趣帖子.

Answer 2

首先,需要定义更有效的手段,更快意味着,使用更少的系统资源(如内存)等......(这些因素有时是相互排斥的)

就效率的标准定义而言,通常会使用Big-0表示法,但是在学术界以外的"现实世界"中,通常会对这两个方程进行分析/基准测试,然后比较结果.

通常很难对Big-0表示法做出一般假设,因为这主要涉及循环并假设循环中代码的固定成本,因此基准测试将是更好的方法.

需要注意的一点是,有时根据您正在使用的数据集大小,结果会有很大差异 - 对于循环中的小N,有时候会发现差异不大

Answer 3

虽然big-O表示法可以为您提供一种区分可怕算法和合理算法的方法,但它只会告诉您有关计算复杂性的特定定义.在现实世界中,这实际上不允许您在两种算法之间进行选择,因为:

1)具有相同复杂度的两种算法,让我们调用它们,f并且g两者的O(N^2)复杂性可能在运行时有几个数量级不同.Big-O表示法不会测量与每次迭代相关的单个步骤的数量,因此f可能需要100个步骤,而g需要10 个步骤.

此外,不同的编译器或编程语言可能会为算法的每次迭代生成更多或更少的指令,并且算法描述中的细微选择可能使高速缓存或CPU硬件执行10到1000倍的更差,而不会更改大 - O订单,或步骤数!

2)O(N)算法可能胜过O(log(N))算法

Big-O表示法不会测量与每次迭代相关的单个步骤的数量,因此如果O(N)采用100步,但O(log(N))每次迭代需要1000步,那么对于一定大小的数据集O(N)将更好.

相同的问题适用于上述编译器.

解决方案是对Big-O表示法进行初步数学分析,然后使用基准驱动的性能调整周期,使用时间和硬件性能计数器数据,以及良好的经验.