algorithm - 为什么假设乘以 n 的时间复杂度是常数？

Question

无论乘法（或除法）运算如何实现（即是软件功能还是硬件指令），都无法及时求解O(1)。对于大n值，处理器甚至无法通过一条指令计算它。

在这样的算法中，为什么这些操作是恒定的而不依赖于n？

for (i = 1; i <= n; i++) {
    j = n;
    while (j > 1)
        j = j / 3;    //constant operation
}

Answer 1

时间复杂度不是时间的度量。它是对“基本操作”的衡量标准，可以根据需要进行定义。通常，任何算术运算都被认为是基本运算。有时（例如，在考虑排序算法或哈希表操作的时间复杂度时），基本操作是比较。有时，“基本操作”是对单个位的操作（在这种情况下j=j/3，时间复杂度为 O(log(j)）。

倾向于遵循的规则是：

• 如果您在谈论排序或哈希表，则基本操作是比较
• 如果您在谈论任何其他实用算法，则基本运算是算术运算和赋值。
• 如果您在谈论 P / NP 类，则基本操作是确定性图灵机的步数。（我认为这相当于位操作）。
• 如果您作为复杂性理论专家谈论实用算法，您通常会假设基本类型具有 ~log n 位，并且基本运算是算术运算和对这些 ~log n 位字的赋值。