检查整数相等：C 中的 O(1) 但 Python 3 中的 O(log n) ？

Question

考虑 C 和 Python 3 中的这些等效函数。大多数开发人员会立即声称两者都是 $O(1)$.

def is_equal(a: int, b: int) -> bool:
  return a == b

int is_equal(int a, int b) {
  return a == b;
}

但请考虑一下表面之下正在发生的事情。整数只是二进制字符串，为了确定相等性，两种语言都会逐位比较字符串。无论哪种情况，此扫描都是 $O(b)$ 在哪里 $b$ 是位数。由于在 C 语言中整数的位大小是固定的，所以这很简单 $O(1)$.

编辑：C 不进行逐位比较 看到这个答案

然而，在 Python 3 中，整数确实如此 不是 具有固定大小并且扫描保持不变 $O(b)$ 输入中的位数，或 $O(\log a)$ 在哪里 $a$ 是以 10 为基数的输入值。

因此，如果您正在分析 Python 中的代码，那么每当您比较两个整数时，您都将踏上一段极其复杂的旅程： $O(\log n)$ 相对于任一数字的以 10 为底的值。

对我来说，这提出了几个问题：

1. 它是否正确？我还没有看到其他人声称 Python 在日志时间中比较整数。
2. 在进行面试时，您是否应该注意到或关心候选人是否这样称呼 $O(1)$?
3. 您应该注意到或关心现实世界中的这种区别吗？

编辑：很容易验证（并且直观），Python 无法在恒定时间内比较任意大的整数。因此，提出上述问题 1 的更好方法可能是“调用此操作的理由是什么（如果有）” $O(1)$？因为它很务实？传统的？RAM 型号暗示的？

Answer 1

长话短说：CS 约定将此类操作描述为 $O(1)$ 对于 Python 来说，在极端情况下它会崩溃。这些案例是 极其 很少见，所以打破了惯例 $O(1)$ 具有负效用。这种实用主义在大公司很正常 $O$.

对于这个问题有很多很好的回答，我鼓励您阅读它们。但我认为他们中的任何一个都不能完全回答我的问题。所以这里有一个综合。

它是否正确？我还没有看到其他人声称 Python 在日志时间中比较整数。

这是令人惊讶的微妙之处。这是 真的 Python 比较非常大的整数 $O(\log n)$ 运行。但这是吗 正确的 将此操作描述为 $O(\log n)$?

最终，我最相信@TomvanderZanden 的这段话：

如果你说 C 或 Python 版本是 $O(1)$ 任何面试官都应该非常高兴。如果你说它（Python版本）是 $O(\log n)$ 他们可能仍然会很高兴，但认为你是一个相当迂腐的人，不遵循正常的惯例。

和

如果我是一名面试官，我会关心你是否知道你正在做的事情在现实世界中的局限性，是否知道什么时候理论问题很重要，并且当且仅在适当的时候你才提出它们。

然而，我不接受这个答案，因为我认为第一段目前具有误导性（很乐意改变）。

归根结底，这个论点是务实的。根据大的严格定义 $O$ Python int 比较仍然是可验证的 $O(\log n)$. 。但这样对待它是没有用的，所以你不应该这样做。我想补充一点，对大的要求要严格 $O$ 就是错过了大的要点 $O$ 分析。

Answer 2

整数只是二进制字符串，为了确定相等性，两种语言都会逐位比较字符串。

不完全的。C ints 是机器字大小并与单个机器指令进行比较；Python ints 以基数表示 $2^{30}$ （参见例如 https://rushter.com/blog/python-integer-implementation/）并在该基数中进行逐位比较。所以对数的相关底是 $2^{30}$.

如果 最后一个 的数字可以限制为 $2^{30天}$ 为了 任何 固定的 $d$, ，比较是 $O(1)$ （因为首先比较位数），如果不能，其他操作可能比相等比较更受关注。所以在实践中我想说这不太可能重要，如果确实如此，你会知道（并且不会使用 int但类似的东西 GNU 多精度算术库 在 C 中也是如此）。

Answer 3

复杂性相对于计算模型定义。例如，P和NP在图灵机方面定义。

进行比较，请考虑Word RAM模型。在此模型中，内存被分成单词，可以在恒定的时间内访问单词，并且可以使用 $ o（1）$ 单词表示问题的大小。

因此，例如，在分析基于比较的排序操作时，我们假设元素 $ n $ 可以存储在 $ O（1）$ 单词，因此在 $ 1 $ 和 $ n $ 。

Answer 4

它是否正确？我还没有看到其他人声称 Python 在日志时间中比较整数。

不（也有一点是）。考虑以下发人深省（但并非真正正确）的主张：计算机只能拥有有限的内存（受宇宙中原子数量的限制），因此Python版本也是 $O(1)$.

问题是我们试图对有限状态机（计算机）的渐进性（与无穷远发生的情况有关）做出陈述。当我们分析代码的复杂性时，我们实际上并不是在分析代码本身，因为它会在计算机上运行，​​而是在分析代码的一些理想化模型。

假设我让你分析一个用 C 编写的排序算法。您可能会说它使用整数来索引数组，因此它只能对大小不超过的数组进行排序 $2^{31}-1$. 。然而，当我们分析这样一段代码时，我们假装它可以处理任意大的数组。显然，我们并不是说 C 整数比较是 $O(1)$ 因为 它只能处理 32 位数字。

在进行面试时，您是否应该注意到或关心候选人是否将此称为 O(1)？

通常情况下，不会。假设我正在进行一次面试，要求你编写一个 C 或 Python 计算机程序来统计员工数据库中出现的女性员工数量。

这将是 难以置信 如果我抱怨你的 C 程序不正确，因为它只能算到 $2^{31}-1$.

我们通常假设数字足够小，可以容纳在一个单词/整数中。我们假设加法（或任何其他数字运算）可以在 $O(1)$, ，因为必须写起来会很烦人 $O(\log n)$ 到处都是，它只会让一切变得不可读，即使 $\log n$ 实在是太小了，反正也没什么关系。

如果你说 C 或 Python 版本是 $O(1)$ 任何面试官都应该非常高兴。如果你说它（Python版本）是 $O(\log n)$ 他们可能仍然会很高兴，但认为你是一个相当迂腐的人，不遵循正常的惯例。

您应该注意到或关心现实世界中的这种区别吗？

是的！当数字变得如此之大时，违反了它们很小的假设就开始变得重要了。假设您正在面试 Google，他们要求您计算过去一年女性用户执行的搜索查询数量。如果你使用整数编写 C 程序，面试官有理由抱怨。

您可以改用 longs 并且仍然有理由调用它 $O(1)$, ，同样，调用Python版本 $O(1)$ 也是有道理的。这 $O(1)$ 与 $O(\log n)$ 只有当数字变得很长时，事情才开始变得重要。例如，如果您的任务是编写一个计算数字的程序 $\pi$ 或一些类似的任务。如果你为这个任务编写了一个 Python 程序，并且在被问到时没有提及复杂性的特殊性，面试官会关心的。

如果我是一名面试官，我会关心你是否知道你正在做的事情在现实世界中的局限性，是否知道什么时候理论问题很重要，并且当且仅在适当的时候你才提出它们。

什么时候你应该关心？

到目前为止，我对“大”和“小”数字有点模糊。在常用的 RAM 模型中，您可以假设整数运算可以在 $O(1)$ 在最多有的数字上 $O(\log n)$ 位（其中 $n$ 是输入的长度）。这个假设的理由是，如果我们有一个长度的输入 $n$, ，我们的编程语言中的指针/索引应该足够长，以便能够寻址整个输入空间。所以，在RAM模型中，如果输入是二进制数 $n$ （二进制）数字，检查相等性的复杂度是 $O(\frac{n}{\log n})$ 因为我们可以检查一组的相等性 $O(\log n)$ 位合一 $O(1)$ 手术。

Answer 5

虽然这看起来像是一个微不足道的问题，但你的第一句话是不正确的。 功能不等同. 。为了使它们等效，C 函数应该使用 GMP（或类似的）来实现任意精度算术。现在，这个观察结果并非微不足道，因为说两者等价的合理程度，正是说 Python 代码是常数时间的合理程度！也就是说，如果我们要忽略 Python 的整数是 bignum，我们可以（并且应该）始终将它们视为固定大小。

类似地，考虑 C 函数 int is_equal(char a, char b) { return a == b; } 和Python函数 def is_equal(a: str, b: str) -> bool: return a == b. 。现在更明显的是，这些功能不相等，但其原因与您的不相等的原因完全相同。我们只是期望在 Python 中一直看到大量字符串，但并不真正期望看到大量整数，尽管我们当然知道它们是可能的。所以，大多数时候我们忽略了Python的整数很大这一事实，我们分析时就好像它们是固定大小的一样。在极少数情况下，我们关心 bignum 运算的时间，您可以使用“真实”复杂度。当然，也可以在 C 代码中使用 GMP。

这一切就是想说：尽管您没有意识到，但您已经知道最后重述版本的问题的答案，答案是“与您将这些函数描述为等效的理由相同”。Python 的不同寻常之处在于没有固定大小的整数类型（好吧，这不是人们常用的类型：当然可以写一个，并且里面有一个 numpy）。但出于实用主义的考虑，我们不希望这妨碍我们对处理整数的算法进行“通常”的复杂性分析，并获得“通常”的答案。很少有必要提供警告，如果我们传递几个几乎相等的 10GB 整数，则可能需要一些时间来比较它们。

在某些情况下，您可以通过说您将分析限制为小整数来形式化这一点（如果您确实需要的话）。然后，您可以根据某些整数数组的大小来考虑某些算法的复杂性，将所有算术运算视为 O(1)。如果您正在考虑真正线性或更差的整数大小的算法，那么您可以通过说您将忽略对数因子来形式化它，因为您真正关心的是复杂性是否更接近线性或二次，因为 O(n log n) 与线性一样适合您的目的。但几乎所有时候，您都不需要形式化算法的复杂性 在Python中. 。如果您已经达到指定编程语言的程度，那么您就不再真正在研究抽象计算机科学了;-)

在进行面试的背景下，您是否应该注意或关心候选人是否致电 $O(1)$?

我想这取决于面试的内容，但作为一名软件专业人士，过去 10 年主要使用 Python 工作，我不会在面试中问这个问题。如果我问一个问题，其中隐藏了整数比较的复杂性（例如，我不知道，“这种排序算法的复杂性是多少？”），那么我会接受一个忽略整个问题的答案。我也愿意接受解决这个问题的一个。我确实认为作为实际编程的一部分，理解和计算复杂性是值得的，我只是不认为它那么重要 用于编程 在正式声明您正在谈论合理大小的整数时要非常小心。

我也永远不会问一个问题，我希望候选人提供 Python 整数是任意精度的信息，当由于某种原因与所涉及的数据有关的问题与问题没有明显相关时。如果问题暗示所涉及的数字可能大于 2⁶⁴ 然后在 C 面试中我希望应聘者注意到这是他们需要处理的问题，而在 Python 面试中我希望应聘者知道事实并非如此，但我不希望他们这样做不遗余力地陈述这一点。在面试中没有时间陈述每一个使某件事不再成为问题的小事实。

如果我想在面试中检查对复杂性的理解，那么很可能我会首先要求一些针对某些问题的代码，其中存在一个非常简单的“天真的”解决方案，但复杂性较差，并且至少有一个不太简单的解决方案，但复杂性还不错使用众所周知的技术。如果候选人提供了简单的解决方案，那么您可以询问复杂性是什么以及他们将如何修改代码以改进它。如果候选人提供了更好的解决方案，那么你可以描述这个简单的解决方案，指出它的代码行数有多少，并询问它有什么问题（也许可以问，“如果你正在审查某人的代码并且他们给了你这个，什么？你会说一下吗？”）。对于大多数实际用途，您所关心的是他们是否能够区分线性、二次和劣于二次之间的区别。O(n log n) 也会出现，但主要是因为排序或数据结构，您在其中谈论比较次数的复杂性。每次比较的成本通常被认为是无关紧要的，因为算法设计者通常无法控制它（它由算法或数据结构的用户提供）。

令人惊讶的是，如果我是计算机科学学者职位的面试官，涵盖任意精度算术，那么我当然希望候选人了解各种运算的各种算法的复杂性，并且确实了解最先进的技术那些不平凡的事情。

Answer 6

它是否正确？我还没有看到其他人声称 Python 在日志时间中比较整数。Python 确实有任意精度的整数格式。但是，我们必须在这里进行一个公平的比较。如果我们考虑边界上的整数子集 $[0,2^{64}]$, ，我们发现Python操作是恒定时间的。

您所看到的是使用大哦表示法测量计算复杂性的限制之一。它描述了当 n 接近无穷大时会发生什么，但不一定能很好地比较较小数字的行为。我们在其中著名地看到了这一点 矩阵乘法算法. 。有一些算法在大的意义上更有效，但实际上在达到巨大的矩阵之前会更慢。

在进行面试时，您是否应该注意到或关心候选人是否将此称为 O(1)？

取决于你雇用他们的目的。对于绝大多数作业，称其为 O(1) 应该没问题。事实上，这就是我们在学校教授它的方式。如果你想把它变成一个了解你的候选人的有用机会，你可能会问他们为什么他们认为加法是常数时间（答案是他们用来确定大哦的模型假设它......这是一个有效的答案）

如果您正在雇用某人来寻找代码中的漏洞之类的东西，您可能需要进一步推动。由您自己的代码生成的 bignum 是一回事，但是是否允许用户输入自己选择的数字？如果是这样，他们可能能够利用这种添加速度非常慢的事实来创建定时攻击和 DOS。检测这种风险可能是他们工作的一部分。

您应该注意到或关心现实世界中的这种区别吗？

实际上来说：不。直到您真正遇到它并在调试中解决问题。Python 做了一个 很多 “总体安全”且非常高效的事物。这就是为什么它成为世界上最流行的语言之一。

对于同等情况：有多快 x.y 在Python中？我们认为它是 O(1)，但实际上有一个哈希查找。该哈希查找使用已知的探测机制，并且查找结果实际上是 O(n)。在普通代码中你永远不会看到这一点。但在对手用自己的内容填充你的字典的代码中，他们可以故意制作以这种方式发生冲突的键。

Answer 7

我从未遇到过的文本，除了恒定的时间之外，将处理“常规”整数操作的文本，尺寸具有一些合理的有限上限（例如64位）的隐式假设。也许陈述假设是更准确的，但是对于一个CS观众来说，我认为它是隐含的。

这样做会引入大量复杂性，讨论基本上无关的主题。Bigint实现通常不通过位实现，但在基本 - （机器字大小）中，使O（b）> o（1）问题仅用于术语，用于非常大的数字。

个人在采访某人的时候，我可能会欣赏与知道Python整数相关的知识的严谨和广度是任意长度的，但是除了陈述所有数学是O（1）会感到非常迂腐的假设之外的任何东西。如果分析开始使用算术和浪费时间越远，并且浪费时间，我会认为这是一个糟糕的候选人。