linux - 为什么我的汇编代码应该在 O(N*sqrt(N)) 时间内运行，但它却在线性时间内运行？

Question

所以我用汇编写了一个素数生成器(学习语言)，当我开始对程序进行基准测试时，我发现它在线性时间内运行，而不是预期的 O(N * sqrt(N )) 时间。

为什么会这样？

我检查并评论了代码并将其放在 github 上:https://github.com/kcolford/assembly_primes .它应该是相当可读的，但如果有人希望我更彻底地评论它(比如对每条指令的解释)，我很乐意这样做，我只是认为没有必要。

我使用的汇编器和链接器是在 GNU binutils 中找到的，它是为运行 linux 内核的 x86_64 架构编写的。

Answer 1

Big-O 复杂性很难通过实验测量。正如 Phil Perry 所建议的，通常有线性项(或其他项)压倒“小”运行的主要 O() 项。这些隐藏在大 O 表示法中的额外术语始终存在于真实代码中，并且在分析某些事物的实际运行时时是必需的。

当我在我的测试机器上测量你的示例代码时，我得到了一个明显的非线性关系。由于声誉不佳，我无法发布情节，但这是一张表格:

N (= n^2)     Time
  1000000    0.386
  4000000    1.846
  9000000    4.673
 16000000    9.275
 25000000   15.850
 36000000   24.690
 49000000   35.850
 64000000   49.887
 81000000   66.509
100000000   86.855

此外，我没有彻底查看您对算法的确切实现，但是 Sieve of Eratosthenes是 O(n log log n)，而不是 O(n sqrt(n))。

另请注意，与数字运算相比，I/O 通常非常昂贵。在您的情况下，在我的测试机器上，在 n = 5000 时，I/O 几乎占总运行时间的 30%。这将是运行时分析中的重要线性项。您必须彻底分析代码正在执行的所有其他操作，以找出影响测量的其他因素。