algorithm - 师大O

Question

在大多数现代 ISA 中，除法的大 O 是什么？是否有某种优化或者是天真的 O(numerator/denominator)？我正在编写严重依赖模运算的代码。

例如，执行 10/5、20/5 和 40/5 的相对时间是多少？来自 Intel、nVidia、Qualcomm 等的现代处理器是否具有相同的 Big-O 划分？

注意:假设除法是 O(分子的大小)，我在这里可能是错误的，这个问题可能根本没有任何意义。如果是这样，请纠正我。

Answer 1

这个问题不太好。但这也不是那么“愚蠢”，所以我尝试回答/澄清一些要点:

几乎所有现代 CPU/GPU 都有除法指令。由于它适用于默认字长，因此它的速度有多快并不重要，就 Big-O 而言，它是常数，因此它始终为 O(1)。即使对于没有除法指令的嵌入式处理器、微 Controller 和类似产品也是如此，因为它是在软件中模拟的，并且软件模拟受字大小的限制，所以执行除法指令的时间总是恒定的操作(这意味着它也是 O(1))。

异常(exception)是在谈到对非字大小的数据执行操作时。这发生在例如在谈论 BigInt 库时。但在这种情况下，所有操作(加法、乘法...)不再是 O(1)，而是取决于数字的大小。

但请注意:Big-O 并没有说明实际计算时间。它只是忽略常数因子的渐近行为。这意味着，即使您有两个采用 O(n) 的算法，时间差也可能是 1000 倍(或一百万或任何您想要的)。最好的例子是部门:它是一个例子。加法都是 O(1)，但通常执行除法比加法需要更多的周期/时间。