java - 如何从理论上计算某些方法的执行时间？

Question

假设我有“堆排序”方法，其复杂性时间为 O(nlogn)。当我在 1000000 个输入上测量此方法的执行时间时，我得到了 0.375770669 秒。理论上如何计算该方法的执行时间？

Answer 1

There is no way to calculate this theoretically. It depends on many factors such as:

• The java edition and major / minor / patch release numbers.
• The various JVM tuning parameters; e.g. how big the heap is.
• Your hardware platform; CPU, memory size, even motherboard and clock speed.
• The load on the machine; i.e. what else it is doing.
• The amount of fluff on the CPU heatsink. Seriously ... the clock speed may be reduced if the processor chip gets too hot, and the motherboard oscillator clock speed is (a bit) temperature sensitive too.

Even if you knew all of those, the calculation would essentially be a forensic simulation of the Java JIT compiler and hardware execution. It is far too complicated to contemplate.

The best you can reasonably expect to achieve in terms of a theoretical measure of "speed" is to count abstract operations at the source-code level. Even drilling down and counting bytecodes executed is probably too difficult to be practical.

I want to compare between the measured one and the theoretical one.

Basically, you can't.

Answer 2

What you can possibly do is to run your code for various number of inputs such as 1000, 10000, 100000, 1000000, 10000000 etc and record the time spent in sorting. Then plot those records times against # of elements in a X-Y graph and see if you get O(nlogn) complexity curve.

Also look at this document for heap sort analysis and demo: http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/heap/heapen.htm

Answer 3

请记住，O(·) 或 Θ(·) 表示法描述了在n 接近无穷大时的渐近增长率：它描述了当你将输入大小乘以 10 时算法的速度有多慢。这与实际输入大小（与“无穷大”相比总是无限小）的实际执行时间的对应程度取决于用于分析算法的理论模型与您拥有的实际机器的对应程度。

具体来说，“堆排序需要 Θ(n log n) 时间”意味着存在常数 c ₁和 c ₂使得对于足够大的 n，如果 T(n) 是它在大小为 n 的输入上所花费的时间，那么

c ₁ n log n < T(n) < c ₂ n log n

n = 1000000 的大小可能会或可能不会“足够大”以使渐近行为生效。

尽管如此，假设它是，并将该语句解释为表示对于某个常数 c，所花费的时间大致为 (cn log n)，等于

c1000000lg(1000000) = 0.375770669 秒

给出 c ≈ 1.88 × 10 ^-8。这意味着大小为 n=2000000 的输入大约需要 0.79 秒，而 n=10000000 大约需要 4.38 秒。您可以将此“理论”结果与通过使用该大小的输入运行算法获得的实验结果进行比较。

---

典型计算机的粗略经验法则是，对于慢速计算机和算法，c 介于 10 ^-7之间，对于相当不错的计算机和算法，c 介于 10 ^-9之间。为了安全起见，在两端乘以另外几个 10 的因数。（这个想法是，典型的分析给出的常数 c 在某个地方，比如 1-200，典型的计算机的速度在一个或两个数量级之内。当然，“典型”是主观的，如果你用斐波那契试试这个堆你可能会失望。）

从大约 10 ^-8的先验猜测 c开始，运行时间大约为 0.2 秒。