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 位字的赋值。<