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

Question

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

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

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

Answer 1

时间复杂度不是时间的度量。它是 "basic operations" 的度量，可以根据需要定义。通常，任何算术运算都被视为基本运算。有时（比如考虑排序算法的时间复杂度，或者hashtable操作），基本操作就是比较。有时，"basic operations" 是对单个位的操作（在这种情况下，j=j/3 的时间复杂度为 O(log(j)).

倾向于遵循的规则是：

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