如何比较两个具有恒定运行时的算法？

Question

我目前正在写一篇论文，旨在开发一种计算矩形和三角形之间相交面积的算法。在我的结论中，我想将它与众所周知的扫描线算法进行比较。

但问题是，由于该算法不会在任何 form/by 任何变量中缩放（它只需要一个矩形和一个三角形），所以我不能使用渐近大 O 表示法。

我应该测量什么来比较这两者？我目前的想法是计算所有乘法并优化这两种算法以尽可能少地使用它们。

其他想法是计算所有算术运算and/or所有比较。

我将不胜感激任何有关此事的提示或论文链接，因为当我研究这个主题时，我总是只找到对 Big-O 的引用。

Answer 1

您可以计算算术运算，尤其是最难执行的乘法和除法。添加很容易。

从技术上讲，您输入的“大小”仍然可以根据坐标的位数进行缩放。如果坐标是 (1, 0)、(0, 1) 等，那么它当然会比坐标是 (0.97659532947896743856826735964827, 0.597865467885453586248625678) 等更快，并且您希望得到该区域的精确答案.因此，您可以根据 n（输入中的总位数）来表示算法的复杂度。但考虑到这一点可能与仅计算乘法和除法的次数相同。

Answer 2

如果我要将一个函数的性能与另一个进行比较，我会生成一大组圆和三角形（其中任何圆 ci 与任何三角形 ti 相交）作为输入，那么我会这样做：

double timeMyAlgorithm = 0;
double timeSweepLine   = 0;
double chronometer = 0;
double tests = 0;

foreach(Triangle ti : triangles){
    foreach(Circle ci : circles){

        chronometer = Time.currentTime();
        MyAlgorithm(ti, ci);
        chronometer = Time.currentTime() - chronometer;
        timeMyAlgorithm += chronometer;

        chronometer = Time.currentTime();
        SweepLine(ti, ci);
        chronometer = Time.currentTime() - chronometer;
        timeMyAlgorithm += chronometer;

        tests += 1;
    }
}

print("Full time: " + timeMyAlgorithm + " x " + timeSweepLine);
print("Average time: " + (timeMyAlgorithm/tests) + " x " + (timeSweepLine/tests));

如何比较两个具有恒定运行时的算法？

How do I compare two Algorithms with constant Runtime?

algorithm

comparison

complexity-theory