（Dis）证明由于语言内部原因，一种算法比另一种算法运行得更快

Question

对于大学的项目，当给定一组元素和所述元素之间的关系集合时，我们必须实现一些不同的算法来计算等价类。

我们被指示执行Union-Find算法及其优化（Union by Depth，Size）。无意中（做了一些我认为对算法正确性所必需的东西），我发现了另一种优化算法的方法。

它不如联盟深度，但接近。我不能为了我的生活找出它为什么速度如此之快，所以我咨询了一位无法解决问题的助教。

该项目是在Java中，我使用的数据结构是基于整数的简单数组（的对象，而不是int） 后来，在该项目的评价，有人告诉我，它可能有一些东西需要做的Java缓存“，但我无法在网上找到任何关于缓存如何影响的信息。

没有计算算法的复杂度，如何证明或反驳我的优化是如此之快，因为java的做事方式是什么？以另一种（低级？）语言实现它？但是谁会说那种语言不会做同样的事情呢？

我希望我自己清楚，

感谢

Answer 1

的唯一途径是证明该算法的最坏情况（平均情况等）的复杂性。

因为如果你不这样做，它可能只是的

• 组合的结果的具体数据
• 数据
• 硬件的某些方面的大小
• 一些语言实现方面
• 等

Answer 2

如果您有权访问源代码 - 并且JDK源代码可用，我相信 - 那么您可以通过它来找到相关的实现细节。

Answer 3

鉴于现代虚拟机，执行这样的任务通常非常困难！就像你提示他们在背后执行各种各样的东西。方法调用被内联，对象被重用。等等一个最好的例子就是看看如果它们显然没有执行除计数以外的任何其他操作，那么如何编写简单的循环。或者函数式编程中的函数如何内联或尾调优化。

此外，您很难在任何数据集上证明您的观点。 O（n^2）很容易比看起来更快的O（n）算法快得多。两个示例

1. 对排序近似排序的数据收集进行排序比快速排序更快。
2. 在一般情况下快速排序，当然速度更快。

一般来说，大O符号故意忽略常量，在实际情况下可能意味着生命或死亡的实现。而那些常量可能是你打击的东西。所以在实践中0.00001 * n ^ 2（比如你的算法的运行时间）比1000000更快* n log n

所以推理很难给予你提供的有限信息。

Answer 4

编译器或JVM很可能为您的代码找到了优化。您可以尝试读取javac编译器输出的字节码，并使用-Djava.compiler=NONE选项禁用运行时JIT编译。