乘法和除法在最常用的计算机架构上的实现方式是 O(1) 吗？
例如，在 x86 和 ARM 上，乘法和除法是 O(1) 吗？如果我使用 Java 的 BigInteger 类并将两个 BigInteger 实例相乘或相除会怎样？这显然可能不是 O(1) 但复杂度是多少？
BigIntegerBigDecimal对于任意大的操作数，复杂性似乎不太可能保持不变。除非你可以拥有任意大型硬件来遵循它（并且它可能不会线性增长）。
回答你的问题：它在不同的系统和不同的语言中有所不同。
但是对于“正常”大小的整数，您可以查看 ARM 文档。
例如，ARM 汇编乘法指令包含不同的小节。假设使用汇编语言和特定的 ARM 平台，您可以深入了解官方文档。 这给出了执行乘法所需的周期数。因为ARM是RISC机器，所以这样使用很方便。然后将其与您的供应商芯片频率进行比较。
例如对于 ARM7 处理器。
另外，您可能想看看wikipedia Multiplication_algorithm
只有当 n 实际上可以在很大范围内变化时，谈论 O(f(n)) 才有意义。大 O 的要点是我们忽略小事情并专注于运行时如何在广泛的 n 范围内扩展。
如今，CPU 级乘法运算通常是恒定时间，尽管在过去有些乘法运算确实会随着参数的大小而有所不同。即使在今天，除法也可能需要不同的时间，但我们仍在谈论相对较小且有限的变化。乘以固定大小值应视为 O(1)。
另一方面，对于 bigint 库，我会假设 O(n*m)，其中 n 和 m 是两个操作数的位长度。这代表了最基本、最明显的乘法和除法算法的复杂性。
有些算法比简单算法具有更好的渐近复杂性，但在假设任何特定的大整数库使用它们之前我想得到确认。
不幸的是，Java 标准大整数库的文档对计算复杂性问题只字未提。